Tomografia dyskretna

Dyskretny problem rekonstrukcji tomografii dla dwóch kierunków pionowych i poziomych (po lewej) wraz z jego (nieunikalnym) rozwiązaniem (po prawej). Zadanie polega na pokolorowaniu niektórych białych punktów na czarno, tak aby liczba czarnych punktów w rzędach i kolumnach odpowiadała niebieskim cyfrom.

Tomografia dyskretna koncentruje się na problemie rekonstrukcji obrazów binarnych (lub skończonych podzbiorów sieci całkowitej ) z niewielkiej liczby ich projekcji .

Ogólnie rzecz biorąc, tomografia zajmuje się problemem określania informacji o kształcie i wymiarach obiektu na podstawie zestawu rzutów. Z matematycznego punktu widzenia obiekt odpowiada funkcji, a postawiony problem polega na zrekonstruowaniu tej funkcji z jej całek lub sum po podzbiorach jej dziedziny . Ogólnie problem inwersji tomograficznej może być ciągły lub dyskretny. W tomografii ciągłej zarówno dziedzina, jak i zakres funkcji są ciągłe i stosuje się całki liniowe. W tomografii dyskretnej dziedzina funkcji może być dyskretna lub ciągła, a zakres funkcji to skończony zbiór liczb rzeczywistych, zwykle nieujemnych. W tomografii ciągłej, gdy dostępna jest duża liczba projekcji, dokładne rekonstrukcje można wykonać za pomocą wielu różnych algorytmów. Typowe dla tomografii dyskretnej jest to, że stosuje się tylko kilka projekcji (sum liniowych). W tym przypadku wszystkie konwencjonalne techniki zawodzą. Szczególny przypadek tomografii dyskretnej dotyczy problemu rekonstrukcji obrazu binarnego z niewielkiej liczby projekcji. Nazwa tomografia dyskretna pochodzi od Larry'ego Sheppa , który zorganizował pierwsze spotkanie poświęcone tej tematyce ( DIMACS Mini-Symposium on Discrete Tomography, 19 września 1994, Rutgers University ).

Teoria

Tomografia dyskretna ma silne powiązania z innymi dziedzinami matematyki, takimi jak teoria liczb , matematyka dyskretna , teoria złożoności obliczeniowej i kombinatoryka . W rzeczywistości wiele problemów tomografii dyskretnej zostało po raz pierwszy omówionych jako problemy kombinatoryczne. W 1957 roku HJ Ryser znalazł warunek konieczny i wystarczający dla pary wektorów będących dwoma rzutami ortogonalnymi zbioru dyskretnego. W dowodzie swojego twierdzenia Ryser opisał również algorytm rekonstrukcji, pierwszy algorytm rekonstrukcji ogólnego zbioru dyskretnego z dwóch rzutów ortogonalnych. W tym samym roku David Gale znalazł te same warunki spójności, ale w związku z problemem przepływu w sieci . Innym wynikiem Rysera jest zdefiniowanie operacji przełączania, za pomocą której zbiory dyskretne mające te same rzuty mogą być przekształcane w siebie.

Problem rekonstrukcji obrazu binarnego z niewielkiej liczby projekcji generalnie prowadzi do dużej liczby rozwiązań. Pożądane jest ograniczenie klasy możliwych rozwiązań tylko do tych, które są typowe dla klasy obrazów, w której znajduje się obraz rekonstruowany z wykorzystaniem informacji a priori, takich jak wypukłość czy spójność.

Twierdzenia

$m$ skończonych) płaskich zestawów krat z ich jednowymiarowych promieni rentgenowskich jest problemem NP-trudnym , jeśli promienie rentgenowskie są pobierane z $m=2}$ dla ${\$ problem jest w P).
Problem rekonstrukcji jest wysoce niestabilny dla $displaystyle m =$ co oznacza, że niewielkie zaburzenie promieni rentgenowskich może prowadzić do zupełnie innych rekonstrukcji) i stabilny dla $m$ } Widzieć.
Kolorowanie siatki za pomocą $problem$ z zastrzeżeniem, że każdy wiersz i każda kolumna ma określoną liczbę komórek każdego koloru, jest znane jako atomu ${\ Displaystyle (k-1)}$ w społeczności tomografii dyskretnej. Problem jest NP-trudny dla ${\ Displaystyle k \ geq 3}$ , patrz.

Dalsze wyniki zob.

Algorytmy

Wśród metod rekonstrukcji można znaleźć techniki rekonstrukcji algebraicznej (np. DART lub ), algorytmy zachłanne (patrz gwarancje aproksymacji) oraz algorytmy Monte Carlo .

Aplikacje

Różne algorytmy zostały zastosowane w przetwarzaniu obrazów , medycynie , trójwymiarowych problemach bezpieczeństwa danych statystycznych, inżynierii i projektowaniu wspomaganym tomografem komputerowym, mikroskopii elektronowej i materiałoznawstwie , w tym mikroskop 3DXRD .

Forma tomografii dyskretnej stanowi również podstawę nonogramów , rodzaju układanki logicznej , w której informacje o wierszach i kolumnach obrazu cyfrowego są wykorzystywane do rekonstrukcji obrazu.

Zobacz też

Tomografia geometryczna

Linki zewnętrzne