Komputerowe modelowanie rozrostu drzewa naczyń krwionośnych

Jedynym sposobem na otrzymanie drzew naczyn krwionosnych o duzej rozdzielczosci
jest symulacja za pomoca komputera. Istnieje wiele sposobów rozwiazania tego problemu,
wiekszosc z nich opiera sie na algorytmach iteracyjnych. Czas wykonania owych
algorytmów jest zazwyczaj długi, a zbudowane drzewa róznia sie od naturalnych. W
pracy zostanie przedstawione podejscie umozliwiajace skrócenie wykonania algorytmu
oraz pomysły na rozwiazanie problemu wzajemnych przeciec naczyn.
Algorytm został opracowany w jezyku Python z uzyciem bibliotek SciPy i NumPy. W
pracy został porównany czas wykonania algorytmu przy uzyciu róznych metod optymalizacji.
Opisane zostały równiez pomysły dotyczace wykrywania i usuwania wzajemnych
przeciec naczyn krwonosnych oraz rozbudowa drzewa w bryle. Zanalizowany
został wpływ tych rozwiazan na wyniki oraz czas wykonania algorytmu.
Najlepsza metoda optymalizacji sposród testowanych okazało sie sekwencyjne programowanie
z uzyciem metody najmniejszych kwadratów. Przeciecia segmentów moga zostac
wykryte, podczas iteracji lub w obróbce koncowej, pierwsze rozwiazanie wydłuza
czas wykonania, ale skutkuje pozadana liczba koncówek w przeciwienstwie do drugiego
podejscia, którego wyniki sa mniej przewidywalne.
Dane zebrane podczas próbnych wykonan pozwoliły na porównanie wyników róznych
modyfikacji algorytmu. Optymalizacja jest w stanie przyspieszyc czas wykonania, jednak
sprawdzanie przeciec znaczaco spowalnia algorytm. Najlepszym podejsciem do
wykrywania przeciec miedzy segmentami okazało sie wykrywanie na biezaco, a nie w
obróbce koncowej. Co wiecej bardziej efektywne okazało sie wstepne ocenianie odległosci
segmentów od siebie oraz zasadnosc rozwazania wzajemnych przeciec.
Zastosowane funkcje pozwoliły na zbudowanie drzewa naczyn krwionosnych wewnatrz
pewnej objetosci przechowywanej jako binarny obraz 3D. Warto jednak zauwazyc, ze
niektóre obszary moga nie zostac wypełnione naczyniami.
Zostało stworzonych wiele uzytecznych funkcji, w celu poprawy budowania drzew naczyn
krwionosnych. Zmodyfikowany algorytm moze zostac zastosowany do modelowania
przepływu krwi, poniewaz nie generuje błedów zwiazanych z wzajemnym przecinaniem
sie naczyn. Oczywiscie wszystkie modyfikacje wpływaja równiez na czas wykonania
algorytmu.

The only method to obtain blood vessel tree of high precision is to generate them
artificially, because angiographic techniques have limitations [1]. There exist many
approaches to the problem, which mainly use iterative algorithms. The execution time
of those algorithms is long and trees are different than natural structures. In the thesis
an approach to make execution time shorter will be presented as well as ideas for
solving segments intersections problem.
The algorithm is implemented in Python with use of SciPy and NumPy libraries. Optimization
methods are compared in terms of execution time. Ideas concerning detection
of intersections and its removal are described. Impact of solutions on the tree properties
is analysed.
The best optimization method among considered is sequential least-squares quadratic
programming. Intersections can be detected, however the time of algorithm execution
is then elongated. Post processing makes the results worse, because the number of
terminals is not predictable.
The data gathered during experiment allows to make reliable comparison of results. The
optimized algorithm can be faster, however intersection analysis slows it down the algorithm,
depending on how it is applied. The best approach to detect segment-segment
intersection is to do this during execution time, not as post processing. Preliminary
judgement if segments are close and if intersection checking is justified, makes the
algorithm more effective.
Implemented functions allow to generate blood vessel trees inside certain volume stored
as binary 3D image. The greater resolution and complexity of the volume the slower
the execution is. It is also worth to remark that some regions may not be filled with
vessels.
Many useful functions were implemented to improve blood vessel tree generation. The
algorithm with modifications can be used in modelling of flow, because possible errors
concerning intersections are avoided. Of course all those modification influence time of
execution.