Morphing rastrově reprezentovaných tvarů

Vzhledem k tomu, že jde o poměrně komplexní úlohu je třeba ji rozdělit na několik částí. Každou z těchto částí je možné řešit různými způsoby. Je na řešiteli, která část ho víc zaujme. Jednotlivé možnosti řešení konkrétních částí jsou ohodnoceny podle obtížnosti. Celkový součet bodů za jednotlivé části bude odrážet obtížnost úlohy jako celku a bude přepočítán (1:1) na bodový zisk z této úlohy pro získání zápočtu. Pro jednoduchost, bude započítána jen jedna možnost řešení konkrétní části.

Jednotlivé podúlohy:

Data:

- 4 2D rastr
- 8 3D data převod z lékařských objemových dat na binární obrázek
- 12 3D data převod čehokoliv vhodného (uzavřená plocha) z povrchové reprezentace (například raytracingem) na binární obrázek

EDT:

- 4 naivní algoritmus
- 16 Meijster algoritmus 2D
- 24 Meijster algoritmus 3D
- 24 Jiný algoritmus

Morphing:

- 4 Lineární interpolace
- 16 Levelset evoluce

Vizualizace:

- 4 2D jednotlivé obrázky
- 8 2D animace (video)
- 12 DVR zobrazení jednotlivých vygenerovaných objemů
- 16 Animace DVR zobrazení (video)
- 24 Animace předpočítaných objemů pomoci DVR v programu (jak to paměťové nároky dovolí, např. smyčka 20 snímků)
- 12 Převod na povrchovou reprezentaci a zobrazení jednotlivých tvarů
- 16 Animace povrchů (video)
- 24 Zobrazení předpočítané animace povrchů v programu (jak to paměťové nároky dovolí, např. smyčka 20 snímků)
- 40 Online výpočet i zobrazení

max 12+24+16+40=92, min 1+1+1+1=16

Poznámky:

EDT:

  • Algoritmus hledá spodní obálku množiny parabol. Hodnota paraboly v obálce pro x znamená nejkratší vzdálenost. Vrchol, který parabolu generuje pak nejbližší bod odpovídající nejkratší vzdálenosti.
  • Doplnění popisu algoritmu: s tvoří zásobník parabol, q ukazatel na vrchol zásobníku. Na zásobník se přidává, pokud parabola v části řádku tvoří spodní obálku (nejkratší vzdálenosti), odebírá se pokud parabola "překryla" předchozí hodnoty (while cyklus hledá kam až překryv zasahuje). Průsečíky v t se používají, aby se dalo skákat po celých parabolách a testovat překryv.
  • Rozšíření do 3D: Hlavní rozdíl oproti publikovanému algoritmu (Meijster 2000) je, že algoritmus má ještě třetí fázi, tři for cykly v každé z fází a b, g jsou trojrozměrná pole. Třetí fáze prochází objem přes všechny sloupečky ve směru osy z. Funkce Sep se nemění. V podstatě se opět počítají paraboly (ne paraboloidy, jak by se mohlo očekávat). Důležité je uvědomit si, že si algoritmus pamatuje tzv. částečné eukleidovské vzdálenosti na druhou v poli g (pokud je x^2+y^2+z^2 úplná e. vzdálenost na druhou, pak x, nebo x^2+y^2 je částečná e. vzdálenost na druhou). Výslednou e. vzdálenost na druhou ukládá do df až poslední fáze. Druhá fáze 3D verze je stejná jako druhá fáze 2D algoritmu, ale ukládá pouze částečnou e. vzdálenost na druhou, kterou třetí fáze používá podobně jako používá druhá fáze 2D algoritmu pole g ve funkci Sep a f. V třetí fázi funkce f k částečné e. vzdálenosti v g přidá další (z-i)^2 a dostaneme úplnou e. vzdálenost na druhou.

    Evoluce levelsetu:

  • POZOR na numerické derivace!: Aby byla evoluce levelsetů stabilní je třeba použít tzv. up-wind schéma pro výpočet F v rekurentním vztahu psi_(n+1) = psi_n + delta t * F. F = f * |nabla psi| - to bylo na přednášce omylem vynecháno. |nabla psi| je velikost gradientu (vektoru parciálních derivací) psi. Je třeba ji spočítat podle schématu např z článku [Breen et al 2001] str 7. f je pak směr pohybu, ven-dovnitř podle potřeby.
  • Hrubé schéma algoritmu: 
    psi = EDT(a)
for n
  for x,y,z //nebo urychlovaci datova struktura
    f = psi(x,y,z) > 0 & b(x,y,z) ? -1 : 1
    psi = psi + delta t * f * |nabla psi|
  ulož/zobraz mezivýsledek

    Literatura: