Bináris képek feldolgozása Digitális képelemzés alapveto˝ algoritmusai
1
Alapok Még egy kis digitális geometria Futam-hossz kód és komponens-analízis
Eötvös Lóránd Egyetem, Budapest
[email protected] http://vision.sztaki.hu
2
Középvonal
Informatikai Kar
3
Távolság-transzformáció Távolság-transzformáció és középvonal
4
Vékonyítás és váz
Csetverikov Dmitrij
Bináris képek
Bináris képfeldolgozás témái
Két osztályba soroltuk a pixeleket: objektum (figure) háttér (ground, or background)
A továbbiakban az algoritmusokban objektum értéke 1 háttér értéke 0
Az illusztrációkban objektum fekete háttér fehér
Bináris (kétszintu) ˝ képeket kétféleképpen kaptunk ˝ küszöböléssel ⇒ összefüggosséget nem vizsgáltunk régió alapú szegmentálással ⇒ összefüggo˝ régiók
Adatstruktúrák futam-hossz kód (run-length code) lánc-kód (chain code)
˝ Összefüggosség-elemzés összefüggo˝ objektum-régiók keresése ⇒ tipikusan, küszöbölés után
Régiók leírása váz morfológia alak
˝ Összefüggosség objektumra és háttérre
Lyukok és határok
?
S
p
S hole
q S
interior pixel
S
set
S 4−connected set
8−connected set
4−border
8−border
are p and q connected?
˝ Ellentmondást kapunk, ha ugyanazt az összefüggosséget alkalmazzuk S objektumra és S háttérre is. ⇒ S és S pixelpárjai "kereszbe" összekötve
˝ Megoldás: más összefüggosség a két halmazra ha 8-as S-re, akkor 4-es S-re ha 4-es S-re, akkor 8-as S-re
Összefüggo˝ komponensek
Az "összekötve" reláció (↔) reflexív: p ↔ p szimmetrikus: ha p ↔ q, akkor q ↔ p tranzitív: ha p ↔ q és q ↔ r , akkor p ↔ r
⇒ Az "összekötve" reláció ekvivalencia-reláció
⇒ Bináris képet összefüggo˝ komponensekre bont. maximális összefüggo˝ halmazokra
Összefüggo˝ komponens-analízis: összefüggo˝ komponensek keresése
Lyuk az S halmazban az S által körülvett S-komponens
Az S határpixele olyan S-pixel, amelynek S-beli szomszédja van ˝ ⇒ az S-re alkalmazott összefüggosség értelmében
Az S belso˝ pixele minden nem határpixel
Futam-hossz kód
x,y
S
label L 2
label L 1
Bináris képet vízszintes futamokkal reprezentálunk. futam: objektum-pixelek maximális összefugg ˝ o˝ sorozata angolul: run-length code, RLC
Egy R futamot az alábbiakkal kódolunk: x, y az elso˝ pixel koordinátái S a futam hossza, pixelben L a futam címkéje: R az L-ik komponenshez tartózik
Futam-hossz kódolás
Az egyszeru˝ rekurzív algoritmus vázlata
Címke nélküli futam-hossz kód a bináris kép letapogatásával nyerheto˝
Címkézett futam-hossz kód komponens-analízis külön muvelet ˝ címke nélküli RLC alapján
˝ Egy kép simán visszaállítható RLC-jébol RLC vesztesség-mentes kódolás
Két komponens-analízis algoritmust mutatunk be: 1
˝ egyszeru˝ rekurzív algoritmust képen muköd ˝ o,
2
futam-hossz kóddal operáló, bonyolultabb algoritmust
Képmátrixban megkeressük a következo˝ be nem járt pontot. Rekurzív függvényhívással bejárjuk a szomszédokat. ⇒ ezzel bejárjuk a kiinduló pont összefüggo˝ komponensét
A bejárt pixelekhez hozzárendeljuk az aktuális cimkét. Növeljük a cimkét és megismételjük az eljárást.
⇒ nem mindig hatékony ⇒ hatékony
Az egyszeru˝ algoritmus tulajdonságai
RLC alapú összefüggo˝ komponens-analízis Bemenet: címke nélküli RLC
A programkód nagyon egyszeru. ˝ néhány sor ciklussal és rekurzív függvényhívással
Nagy komponensek esetén nem hatékony. mély rekurzió ⇒ lassú ⇒ el is szállhat, ha túlcsordul a stack
Nem lehet kontrollálni a komponens-bejárás sorrendjét. Csak akkor használjuk, amikor a komponensek kicsik.
Kimenet: komponens sorszámával cimkézett RLC Tipikus algoritmus címke-ekvivalencia táblát használ két menetben muködik ˝
Az elso˝ menet három alapveto˝ muveletet ˝ tartalmaz: új címke megnyítása létezo˝ címke továbbterjesztése ekvivalens címkék egyesítése, ekvivalencia-tábla kitöltése
A második menetben az ekvivalencia-tábla alapján módosítjuk a címkéket. ˝ ⇒ folytonos novekv o˝ címkesort kapunk
Az elso˝ menete áttekintése
open
Az elso˝ menet inicializálása
˝ Választunk objektum-összefüggosséget.
L1 propagate
open
L3
L2
open
8−connected runs
˝ gyakran a 8-összefüggosséget választjuk objektumra ⇒ ezzel objektumot "preferálunk" háttérrel szemben
Inicializáljuk a címke-ekvivalencia táblát: merge
4−connected runs alapveto˝ muveletek ˝
futamok összefüggése
A három alapveto˝ muvelet: ˝ új címke megnyítása (open) létezo˝ címke továbbterjesztése (propagate) ekvivalens címkék egyesítése (merge)
Új, címke nélküli futam kezelése 1/2
˝ o˝ Amikor egy új, címke nélküli R futamot találunk, az eloz sorban vele összefüggo˝ futamokat keresünk. Ha nincs összefüggo˝ futam, új címkét nyítunk. hozzárendeljük L-t az R-hez növeljük L-t
Ha egy összefüggo˝ futam van, továbbterjesztjuk címkéjét. az összefüggo˝ futam címkéje L′ ≤ L hozzárendeljük L′ -t az R-hez
Eii = 1 Eij = 0, i 6= j Inicializáljuk a címke-számlálót: L=0
Új, címke nélküli futam kezelése 2/2
Ha több, R-rel összefüggo˝ futam van, egyesítjuk az ekvivalens címkéket. az összefüggo˝ futamok címkéi L′k ≤ L kiválasztjuk a legkisebbet: L′m < L′k , k 6= m hozzárendeljük L′m -t az R-hez kitöltjük az ekvivalencia-táblát: minden k -ra Ekm = 1
Középvonal definíciója folytonos esetben
Egyszeru˝ alakzatok középvonala
Egy alakzat középvonala az alábbi feltételeket teljesíto˝ p(x, y ) pontok halmaza: p(x, y ) az alakzat egyik belso˝ pontja p(x, y ) egyenlo˝ távolságon van két vagy több legközelebbi kontúrponttól
A középvonal tükrözi az alakzat struktúráját. ˝ A középvonalat eloállító muveletet ˝ középvonal-transzformációnak hívják. Angolul: medial axis, MA medial axis transform, MAT
Középvonal tulajdonságai
Egy lemez középvonala a lemez középpontja. Minden szögfelezo˝ a középvonal ága.
Alakzat visszaállítása középvonalából
˝ Egy folytonos alakzat középvonala mindig összefüggo. ⇒ egy diszkrét alakzat középvonala nem mindig összefüggo˝
Egy alakzat visszaállítható középvonalából ⇒ ha tudjuk az MA minden pontja és a legközelebbi kontúrpont közti távolságot ⇒ egyébként, nem
A középvonal egy alakzat kompakt és hatékony reprezentációja ˝ áll ⇒ ha az alakzat hosszúkás részekbol pl. betu, ˝ kromoszóma
A középvonal torzítás- és zaj-érzékeny. kis alakzat-torzításra nagy középvonal-változás
MA a beírt körök középpontjainak halmaza. Az alakzat visszaállítható, ha ismerjuk a körök sugarát. az összes beírt kör konvex burka vagy egyszeruen ˝ a lemezek uniója
Középvonal torzítás-érzékenysége
DT-definíció folytonos esetre
Távolság-transzformáció angolul: distance transform, DT
Bemenet: egy vagy több alakzat Minden sarokból indul egy középvonal ág. csatlakozik a többi ághoz, mert folytonos MA összefüggo˝ ⇒ MA struktúrája függ a torzítás irányától
Középvonal-transzformációt regularizálni kell.
Kimenet: távolság minden belso˝ pont és a legközelebbi kontúrpont között ⇒ külso˝ pontokra és kontúrpontokra nulla
Euklideszi távolságot használunk.
a legegyszerubb ˝ megoldás a kontúrsimítás hatékonysága azonban nem biztos
DT-definíció diszkréts esetre
DT érzékeny kis torzításra
Bemenet: egy vagy több alakzatot tartalmazó bináris kép Kimenet: távolság minden objektumpixel és a legközelebbi háttérpixel között √ ⇒ háttérpixelekre 0, határpixelekre 1 vagy
2
téglalap
távolság-transzformáció
hibás téglalap
távolság-transzformáció
Eredményképekben a távolságot intenzitással kódoljuk. nagyobb távolság ⇒ vilagosabb pixel
Euklideszi távolság diszkrét közelítését használjuk. pontosabb közelítés ⇒ pontosabb, de lassúbb eredmény
Távolság-transzformáció továbbterjeszti a torzítást ⇒ a két DT lényegesen különbözik
DT függ a távolság approximációjától
lemez
DT finom approx.
A DT és a MAT közötti kapcsolat
DT durva approx.
téglalap, DT
Az Euklideszi távolság finomabb approximációja
A DT gerincei a MAT ágai
nagyobb maszkot használ pontosabb eredményt nyújt lassúbb
MA meghatározása távolság-transzformációval
téglalap, MAT
˝ pontok sorozata DT-gerinc a lokálisan legbelsobb ˝ állítsünk össze MA-t ⇒ keressünk DT-gerinceket, ezekbol
A DT-MAT algoritmus összefoglalója Algoritmus: Egyszeru˝ diszkrét DT és MAT
Olyan egyszerusített ˝ algoritmust adunk, amely 4-összefüggést használ objektum-pixelekre kap egy u(x, y ) bináris képet kiszámítja az uDT (x, y ) távolság-transzformációt ˝ meghatározza az uMA (x, y ) középvonalat uDT (x, y )-bol
1 2
minden k = 1, 2, . . .-ra rekurzívan kiszámítjuk a DT-t: uk (x, y ) = u0 (x, y ) + min {uk −1 (i, j); (i, j) : ∆(x, y ; i, j) ≤ 1)}
Megjegyzések uDT (x, y ) az (x, y ) objektumpixel és a legközelebbi háttérpixel közti távolság uMA (x, y ) egy bináris kép ∆(x, y ; i, j) a city-block távolság (x, y ) és (i, j) között a gyakorlatban finomabb közelítést alkalmaznak, de az elv ugyanaz
DT inicializálása: u0 (x, y ) = u(x, y ) DT meghatározása
i,j
megállunk, ha nincs több változás: uk (x, y ) = uk −1 (x, y ) minden (x, y )-ra az eredmény: uDT (x, y ) = uk (x, y ) 3
˝ uMA (x, y ) középvonal meghatározása DT-bol: {(x, y ) : uDT (x, y ) ≥ uDT (i, j); ∆(x, y ; i, j) ≤ 1}
Numerikus példa DT-MAT-ra 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 u0 (x, y )
1 1 1 2 1 2 1 2 1 1 uDT
1 1 1 1 1
1 1 1 1 1 2 2 2 2 1 3 3 3 2 1 2 2 2 2 1 1 1 1 1 1 = u3 = u2
→
1 1 1 1 1
1 2 2 2 1
Hámozás és kiterjesztés
1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 u1 (x, y )
1
1 1 1 1 1
•
2 3 3 3
2
1 2 2 2 1
→
2
1 1 1 1 2 2 2 2 3 3 3 2 2 2 2 2 1 1 1 1 u2 (x, y )
1 1 1 1 1
1 1 uDT maximumai
• •
• • •
•
•
•
• • uMA középvonal
DT megáll, amikor k eléri az alakzat max. mérétének felét. "Megfordítással" az alakzat visszaállítható uDT maximumaiból.
Numerikus példák hámozásra és kiterjesztésre
shrink
S (−1) az S halmaz hámozása az S határának törlése
S (−n) az S halmaz n-szeri hámozása a hámozás n-szeri megismétlése
S (1) az S halmaz kiterjesztése
1 2
→
→
1 1 1 1 1
˝ felcseréljük S és S összefüggosségét hámozzuk az S halmazt
S (n) az S halmaz n-szeri kiterjesztése a kiterjesztés n-szeri megismétlése
Angolul: (n-step) shrinking (n-step) expanding
A vékonyítás és a váz definíciója
shrink
˝ o˝ iteratív hámozás Vékonyítás: topológiát megorz 8−connected set
4−connected set
˝ meg az összefüggosséget. ˝ Hámozás nem orzi ⇒ eltuntethet ˝ objektumokat
expand
4−connected set
angolul: thinning
Váz: a vékonyítás eredménye angolul: skeleton
Definíció: Az S halmazt iteratív hámozással vázzá vékonyítjuk úgy, hogy expand
8−connected set
˝ ˝ megorizzük az S összefüggosségét nem törlünk végpontokat
Vékonyítás példája
A váz tulajdonságai Definíció szerint a váz összefüggo˝ halmaz. A középvonalhoz hasonlóan több ágból áll. ˝ álló objektum alakját követi hosszsúkás részekbol más esetekben objektum és váza közti kapcsolat nem ennyire egyszeru˝
Általában hasonlít a középvonalra. emiatt gyakran nem tesznek külonbséget MA és váz között ⇒ a középvonalat is "váznak" nevezik ⇒ vázszeru˝ reprezentációról beszélnek, amely MAT-tal és vékonyítással is nyerheto˝
bináris kép
De lehet egészen más is, mint a középvonal.
váz
⇒ pl. egy téglalap váza és középvonala
Vékonyító algoritmus 8-összefüggo˝ vázra
Az algoritmus összefoglalója Algoritmus: Vékonyítás
Tekintsünk egy p1 pontot és 3 × 3-as környezetét. Legyen a háttér értéke 0, objektumé 1. Legyen TR(p1 ) a 0 → 1 átmenetek száma a {p2 , p3 , p4 , p5 , p6 , p7 , p8 , p9 , p2 } sorozatban.
p3 p4 p5
p2 p1 p6
p9 p8 p7
1
Az u1 (x, y ) és u2 (x, y ) segédképeket inicializáljuk az u0 (x, y ) bemeneti képpel.
2
Letapogatjuk u1 -t, pontokat törlünk u2 -ben. Akkor törlunk egy p1 = 1 pontot, ha egyszerre teljesül
p1 pont és környezete
⇒ körbejárjuk a p1 pontot ⇒ megszámoljuk az átmeneteket
Legyen NZ (p1 ) a p1 pont 1-es szomszédainak száma.
2 ≤ NZ (p1 ) ≤ 6
(1)
TR(p1 ) = 1
(2)
p2 · p4 · p8 = 0 vagy TR(p2 ) 6= 1
(3)
p2 · p4 · p6 = 0 vagy TR(p4 ) 6= 1
3
Ha végig mentünk u1 -n és nem volt törlés, megállunk. egyébként, másolunk u1 = u2 és a 2.lépésre ugrunk
(4)
Három példa, amikor p1 = 1 nem törölheto˝
1 1 0
1 0 p1 1 0 0 (a)
0 1 0
0 0 p1 0 0 0 (b)
1 0 1
0 p1 1 (c)
Megjegyzések a vékonyító algoritmushoz
Pixel körbejárása és az átmenetek számolása egyébként is hasznos muvelet. ˝
1 0 1
Vékonyított képek elemzésére is alkalmazzák. ⇒ vonal-végpontok keresésére ˝ ⇒ vonal-keresztezodések keresésére, stb.
(a) p1 törlése kettészakíthat egy régiót. (b) p1 törlése lerövidíthet egy vonalvéget. (c) 2 ≤ NZ (p1 ) ≤ 6, (3, 4) is teljesül, de p1 mégsem törölheto˝ ⇒ mert TR(p1 ) = 3 6= 1
A vékonyító algoritmushoz aszimmetriája
Kiszámítja TR(p2 )-t és TR(p4 )-t. De TR(p6 )-t és TR(p8 )-t nem számítja ki. ⇒ lásd (3, 4)
p3 p4 p5
p2 p1 p6
Az aszimmetria révén egypixelnyi vastagságú vázat kapunk páras vastagságú vonalak esetén is. ⇒ félpixelnyi eltolás lehet az "igazi" vázhoz képest
Mellékhatás: bizonyos vonalak teljesen eltunhetnek ˝ ˝ erre példát adunk ⇒ késobb ⇒ a gyakorlatban ez nagyon ritkán fordul elo˝
p9 p8 p7
Az algoritmus igazából nem 3 × 3-as, hanem 4 × 4-es ablakot használ.
⇒ Mert körbejárja p2 , p4 -t, amikor TR(p2 ), TR(p4 )-t számolja.
p3 p4 p5
p2 p1 p6
p9 p8 p7
