ACM Snake. Orvosi képdiagnosztika 11. előadás első fele

ACM Snake Orvosi képdiagnosztika 11. előadás első fele

ACM Snake (ismétlés) • A szegmentáló kontúr egy paraméteres görbe: – x  s    X  s  , Y  s  , Z  s   ,s 

• A szegmentáció – energia funkcionál minimalizálása: – E  x   Eint  x   Eim  x   Eext  x  – Zárt görbe esetén periodicitási kényszer: x  i   x  i  k 

i  k 

• Belső energia ( Eint  x  ): – Általában: Eint  x  

2

1 x  x  s    s  ds     2  2 s 0 s s 1

2

2

– Regularizációként is értelmezhető – Első tag bünteti a kontrollpontok eloszlásának egyenetlenségét – Második tag bünteti a görbületet

ACM Snake (ismétlés) • Képből származó energia ( E  x  ): im

–

Eim  x  

1

 P  x  s   ds

s 0

– Detektálandó alakzat „vonzáskörzetébe” kell inicializálni a görbét. DoG, LoG, (diff, Laplace helyett); GVF

• Külső energia ( E  x ): felhasználói beavatkozás ext

F x  k  i  x F x  k  i  x

2 2

2 2

Snake implementációja • Cél az energia összefüggés minimalizációja:

– x  arg min  E  x   Eint  x   Eim  x   Eext  x  x

1

– E  x    P  x  s   ds  0



1

2

x  s  s

0

2

ds 



1

2 0

 xs 2

s

2

2

ds

• E  x  nem konvex globális optimum: NP nehéz • Lokális minimalizálás iteratív algoritmusokkal: – Legmeredekebb lejtő / Szemi-implicit minimalizáció – Iterációk: x t 1  x t   arg min E x t    x  E x t  x

 

  

– Hátránya, hogy első derivált csak lokális információt ad

Legmeredekebb lejtő módszere 1

•

•

E  x    P  x  s   ds 





1

1

  2 2 0 0 0 2 2 – x'  x s , illetve x "   x s – továbbiakban zárt görbét feltételezünk: x  i   x  i  k  1

x' ds 

E  x   x    P  x   x  ds 

2



1

2

x" ds



1

  2 2 0 0 0 – x középpontú elsőfokú Taylor polinom alapján: T P  x   x   P  x    P  x   P  x    P x    x 1! x'   x ' ds  2

x"   x " ds

– tetszőleges ν ,  ν  ν esetén:

ν   ν  ν  2  ν   ν   ν  ν  2  νT   ν 2

2

T

2

2

i  k  2

Legmeredekebb lejtő módszere • Minden iterációs lépéssel ( x ) E-t minimalizáljuk: 1

•

P E x   x  E x     x     x'T   x '     x "T   x " ds x 0 1   P   T T  x  arg min  E     x     x'   x '     x "   x " ds  x  x     0  – Problémát jelent  x ', és  x " , cél ezeket eliminálni. – Szorzatfüggvény deriváltjának azonossága alapján: 1 1 1  v T T T u 0 u  s ds  u  v  0  0 v  s ds 1 T u  v   0 – Zárt görbe miatt u  0   u 1 , v  0   v 1 0

Legmeredekebb lejtő módszere T v T u – Tehát  u  ds    v  ds összefüggést alkalmazva s 1 1 s 0 0 T T •     x'   x ' ds      x "   x  ds 1

1

0 1

0

1

1

0

0

T T T   x "   x " ds     x "'   x ' ds    x ""   x  ds      •   

•

0

 P   E       x "   x ""    xds -t minimalizáljuk: x  0  P   x    t     x "    x "" – Az optimális lépés:    x   • Csak a lépés irányát határozza meg az összefüggés • A hibafelületről csak lokális jellemzőket vesz figyelembe 1

T

Legmeredekebb lejtő iterációja •x

 t 1

 x   x , ahol  xt    t   Pt     xt  "   xt  ""  t 

t 

 x

• Átrendezve az egyenletet (és elhagyva a t-ket):  x  t    x "  P x     x ""   E x

•

x 2x  4 x P Infinitezimiális  t esetén    2    4  : t x s s – Első tag az úgynevezett tenziós erő – Második tag az úgynevezett merevségi (stiffness) erő – Haramdik tag a kép / külső erő – Ezek az erők fizikai értelembe véve sebességek



Euler Lagrange feltétel • Euler-Lagrange feltétel – optimum szükséges feltétele:  E  x   0  P x    x "   x ""  0 – Inflexiós pontok / lokális maximumok esetén is igaz – Első tag miatt a jelekből / szabályozástechnikából megismert módszerek nem alkalmazhatóak. – Legmeredekebb lejtő módszerének leállási feltétele

• Deriváltak approximációja: x  i   s   s '  x  i   s  x – s

 lim

s  i  s

 s ' 0

– x i  : x  i   s  ;

 s'

 s  1 fs



x i  1 2  x i  1 2

s

Deriváltak approximációja 2  1  x i  1  x i  x i   x i  1  1 – x     x  1, 2,1 i    2 2  s s s s i  s  s   s

– Magasabb rendű deriváltak közelítése: általános formula:  n x s n   s n  x  Pn  i  s  i  s • Pn az előjeles Pascal háromszög n-edik sora:

n:

i-2

i-1

i

i+1

i+2

Szemi-implicit minimalizáció • Iteratívan P xt     xt  "   xt  ""   t   xt   xt 1  • Szeparálható a görbe koordináták szerint: t  – u j jelölje az egyik 1D-s görbe j-edik elemét t-időben (iteráció)

 ut  0,5  2 xt 1  4 xt 1 P –      t  , approximációk: 2 4 t s s x  t  0,5  t  ut 1  ut   t • u  t 1 2  t 1 2 2  u  s  u  1,  2,1  s •    t 1 4  t 1 4 2  u  s  u  1,  4, 6,  4,1  s •  



 







– Explicit Euler lépés: külső erők kezelése, Implicit Euler lépés: belső erők kezelése (t+1. iterációban vizsgáljuk)

Szemi-implicit minimalizáció  t 1

• Behelyettesítve, és u j  t 1

 t 1

 t 1

p  u j  2  q  u j 1  r  u j

t 



t 

: u j   t  P u j  t 1

 t 1

:  t 1

 q  u j 1  p  u j  2  u j

– M ciklikus pentadiagonális mátrix, ezért M 1 előállítása O  N  komplexitású, ahol N a kontrollpontok száma

Lokális optimum probléma • Lokális optimum probléma: – Fontos a kezdeti pozíció megválasztás (2 lépéses eljárások) – Kezelése az erőmező regularizációjával (GVF) illetve a képi potenciálok deriválás előtti (multiscale) elmosásával

Probléma kezelése multiscale szűréssel • Multiscale Gauss bankkal az Energiapotenciál elmosása:

  180

  10

Probléma kezelése multiscale szűréssel • Energiapotenciál elmosása: – Nagy szigma: globális optimum „vonzásába” kerül a görbe – Kisebb szigma: nem kezeli a lokális optimumok problémáját – Lényegében egy regularizáció (szigma ~ NSR)

• Szükséges-e a globális optimumot megkeresni: – Orvosi szegmentálások esetén tipikusan nem – Kétfázisú algoritmusokkal kezelhető a probléma: • 1. fázis: közelítően helyes szegmentáció • 2. fázis: Snake futtatása az első fázis eredményéből

Time step megválasztásának nehéségei • Time step (  t ) megválasztásának nehézségei: – Túl kicsi: lassú konvergencia – Túl nagy: oszcilláció / divergencia / rossz helyre konvergál

Zsugorodó Snake problémája •

2 1 2 2   1 x  x arg min  Eint  x      s      s   2 ds   ξ  2 s 0 s s x  

• Ballon erővel történő kompenzáció:  P   x   t      x "   x ""   n  x  

 x  – n  x  az x helyen lévő, egységhosszú normálvektor – optimális  esetén a görbe magától nem zsugorodik – Kezdeti szegmentáció pontatlanságai is kezelhetőek: • Túlszegmentálás esetén cél a zsugorodás:   0 • Alulszegmentálásnál cél a tágulás:   1

2

Esettanulmány

Esettanulmány • Tumorok szegmentálása mellkas tomoszintézis rétegfelvételen: – Input: vizsgálandó elváltozás egy pontja – Output: elváltozás körvonala – Motiváció: onkológiai kezelés hatásának vizsgálata

• Implementáció kétfázisú eljárással: 1. Fázis: Elváltozás középpontjának detektálása, elváltozás skálájának becslése – negatív LoG szűrőbank 2. Fázis: Problémára szabott energiatagokkal Sanke Gradiens iránya ellentétes a sugár irányával

Esettanulmány

Fekete kereszt: input belső pont Piros kereszt: becsült középpont Kék görbe: LoG-os kezdeti szegmentáció eredménye Piros görbe: Snake-el finomított szegmentáció eredménye