Detekce hřebene - Ridge detection

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Září 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Detekce hřebene je pokus pomocí softwaru lokalizovat hřebeny (nebo hrany) v obraze.

v matematika a počítačové vidění, hřebeny (nebo hřebenová sada) a plynulá funkce ze dvou proměnných je sada křivek, jejichž body jsou, v jednom nebo více způsobech, které budou přesněji uvedeny níže, místní maxima funkce alespoň v jedné dimenzi. Tato představa zachycuje geografickou intuici hřebeny. Pro funkci N proměnné, jeho hřebeny jsou množinou křivek, jejichž body jsou lokálními maximy v N - 1 rozměry. V tomto ohledu pojem hřebenových bodů rozšiřuje koncept a místní maximum. Odpovídajícím způsobem pojem údolí pro funkci lze definovat nahrazením podmínky místního maxima podmínkou a místní minimum. Spojení hřebenových sad a údolních sad spolu se související sadou bodů zvaných sada konektorů tvoří spojenou sadu křivek, které rozdělují, protínají nebo se setkávají v kritických bodech funkce. Toto sjednocení množin dohromady se nazývá funkce relativní kritická množina.^[1][2]

Hřebenové množiny, údolní množiny a relativní kritické množiny představují důležité geometrické informace, které jsou vlastní funkci. Svým způsobem poskytují kompaktní reprezentaci důležitých funkcí funkce, ale otázka, do jaké míry je lze použít k určení globálních funkcí funkce, je otevřenou otázkou. Primární motivace pro vytvoření detekce hřebene a detekce údolí postupy přišly analýza obrazu a počítačové vidění a je zachytit vnitřek podlouhlých objektů v doméně obrazu. Zastoupení související s hřebeny, pokud jde o povodí byly použity pro segmentace obrazu. Byly také pokusy zachytit tvary objektů grafickými reprezentacemi, které odrážejí hřebeny, údolí a kritické body v doméně obrazu. Taková znázornění však mohou být vysoce citlivá na hluk, pokud jsou počítána pouze v jednom měřítku. Protože teoretické výpočty v měřítku a prostoru zahrnují konvoluci s Gaussovským (vyhlazovacím) jádrem, doufalo se, že použití víceúrovňových hřebenů, údolí a kritických bodů v kontextu měřítko prostoru teorie by měla umožňovat robustnější zobrazení objektů (nebo tvarů) v obraze.

V tomto ohledu lze hřebeny a údolí považovat za doplněk přírodních úrokové body nebo místní extremální body. S vhodně definovanými pojmy, hřebeny a údolími v intenzita krajiny (nebo v jiném znázornění odvozeném od krajiny intenzity) může tvořit a měřítko neměnné kostra pro organizaci prostorových omezení místního vzhledu s řadou kvalitativních podobností se způsoby Blumu transformace střední osy poskytuje a tvarová kostra pro binární obrazy. V typických aplikacích se deskriptory hřebenů a údolí často používají k detekci silnic v letecké snímky a pro detekci cévy v obrázky sítnice nebo trojrozměrný obrazy magnetické rezonance.

Diferenciální geometrická definice hřebenů a údolí v pevném měřítku v dvourozměrném obrazu

Nechat ${displaystyle f (x, y)}$ označit dvourozměrnou funkci a nechat ${displaystyle L}$ být měřítko-prostorová reprezentace z ${displaystyle f (x, y)}$ získaný konvolucí ${displaystyle f (x, y)}$ s Gaussovou funkcí

${displaystyle g (x, y, t) = {frac {1} {2pi t}} e ^ {- (x ^ {2} + y ^ {2}) / 2t}}$.

Kromě toho ${displaystyle L_ {pp}}$ a ${displaystyle L_ {qq}}$ označit vlastní čísla z Hesenská matice

${displaystyle H = {egin {bmatrix} L_ {xx} & L_ {xy} L_ {xy} & L_ {yy} end {bmatrix}}}$

z měřítko-prostorová reprezentace ${displaystyle L}$ s transformací souřadnic (rotací) aplikovanou na místní operátory derivace směru,

${displaystyle partial _ {p} = sin eta částečný _ {x} -cos eta částečný _ {y}, částečný _ {q} = cos eta částečný _ {x} + sin eta částečný _ {y}}$

kde p a q jsou souřadnice otočeného souřadného systému.

Je možné ukázat, že smíšený derivát ${displaystyle L_ {pq}}$ v transformovaném souřadnicovém systému je nula, pokud se rozhodneme

${displaystyle cos eta = {sqrt {{frac {1} {2}} vlevo (1+ {frac {L_ {xx} -L_ {yy}} {sqrt {(L_ {xx} -L_ {yy}) ^ { 2} + 4L_ {xy} ^ {2}}}} vpravo)}}}$,${displaystyle sin eta = operatorname {sgn} (L_ {xy}) {sqrt {{frac {1} {2}} vlevo (1- {frac {L_ {xx} -L_ {yy}} {sqrt {(L_ { xx} -L_ {yy}) ^ {2} + 4L_ {xy} ^ {2}}}} vpravo)}}}$.

Poté formální diferenciální geometrická definice hřebenů ${displaystyle f (x, y)}$ v pevném měřítku ${displaystyle t}$ lze vyjádřit jako množinu bodů, které splňují^[3]

${displaystyle L_ {p} = 0, L_ {pp} leq 0, | L_ {pp} | geq | L_ {qq} |.}$

Odpovídajícím způsobem údolí údolí ${displaystyle f (x, y)}$ v měřítku ${displaystyle t}$ jsou množinou bodů

${displaystyle L_ {q} = 0, L_ {qq} geq 0, | L_ {qq} | geq | L_ {pp} |.}$

Z hlediska a ${displaystyle (u, v)}$ souřadnicový systém s ${displaystyle v}$ směr rovnoběžný s přechodem obrazu

${displaystyle partial _ {u} = sin alfa částečný _ {x} -cos alfa částečný _ {y}, částečný _ {v} = cos alfa částečný _ {x} + sin alfa částečný _ {y}}$

kde

${displaystyle cos alpha = {frac {L_ {x}} {sqrt {L_ {x} ^ {2} + L_ {y} ^ {2}}}}, sin alpha = {frac {L_ {y}} {sqrt {L_ {x} ^ {2} + L_ {y} ^ {2}}}}}$

lze ukázat, že tato definice hřebene a údolí může být místo toho rovnocenná^[4] být napsán jako

${displaystyle L_ {uv} = 0, L_ {uu} ^ {2} -L_ {vv} ^ {2} geq 0}$

kde

${displaystyle L_ {v} ^ {2} L_ {uu} = L_ {x} ^ {2} L_ {yy} -2L_ {x} L_ {y} L_ {xy} + L_ {y} ^ {2} L_ {xx},}$

${displaystyle L_ {v} ^ {2} L_ {uv} = L_ {x} L_ {y} (L_ {xx} -L_ {yy}) - (L_ {x} ^ {2} -L_ {y} ^ {2}) L_ {xy},}$

${displaystyle L_ {v} ^ {2} L_ {vv} = L_ {x} ^ {2} L_ {xx} + 2L_ {x} L_ {y} L_ {xy} + L_ {y} ^ {2} L_ {yy}}$

a znamení ${displaystyle L_ {uu}}$ určuje polaritu; ${displaystyle L_ {uu} <0}$ na hřebeny a ${displaystyle L_ {uu}> 0}$ pro údolí.

Výpočet hřebenů proměnného měřítka z dvourozměrných obrazů

Hlavním problémem výše uvedené definice hřebene pevné stupnice je, že může být velmi citlivá na výběr úrovně stupnice. Experimenty ukazují, že parametr měřítka Gaussova pre-vyhlazovacího jádra musí být pečlivě nastaven na šířku struktury hřebene v doméně obrazu, aby detektor hřebene vytvořil spojenou křivku odrážející podkladové struktury obrazu. Abychom tento problém vyřešili, aniž by byly k dispozici předchozí informace, je třeba použít pojem hřebeny v měřítku byla zavedena, která považuje parametr měřítka za inherentní vlastnost definice hřebene a umožňuje měnit úrovně měřítka podél hřebene měřítka-prostoru. Koncept vyvýšeniny v měřítku a prostoru navíc umožňuje automatické naladění parametru měřítka na šířku hřebenových struktur v doméně obrazu, ve skutečnosti v důsledku dobře definované definice. V literatuře byla na základě této myšlenky navržena řada různých přístupů.

Nechat ${displaystyle R (x, y, t)}$ označuje míru pevnosti hřebene (bude specifikováno níže). Potom pro dvourozměrný obraz je hřeben měřítka-prostor množina bodů, které splňují

${displaystyle L_ {p} = 0, L_ {pp} leq 0, částečný _ {t} (R) = 0, částečný _ {tt} (R) leq 0,}$

kde ${displaystyle t}$ je parametr měřítka v měřítko-prostorová reprezentace. Podobně, a scale-space údolí je sada bodů, které splňují

${displaystyle L_ {q} = 0, L_ {qq} geq 0, částečný _ {t} (R) = 0, částečný _ {tt} (R) leq 0.}$

Okamžitým důsledkem této definice je, že u dvourozměrného obrazu koncept hřebenů měřítkového prostoru zametá sadu jednorozměrných křivek v trojrozměrném měřítkovém prostoru, kde se parametr měřítka může měnit podél měřítka - vesmírný hřeben (nebo údolí měřítka-prostor). Deskriptor hřebene v doméně obrazu pak bude projekcí této trojrozměrné křivky do roviny dvojrozměrného obrazu, kde lze informace o měřítku atributů v každém bodě hřebene použít jako přirozený odhad šířky hřebenové struktury v doména obrázku v sousedství tohoto bodu.

V literatuře byla navržena různá opatření síly hřebene. Když Lindeberg (1996, 1998)^[5] vytvořil termín měřítko-prostorový hřeben, uvažoval o třech opatřeních síly hřebene:

• Hlavní hlavní zakřivení

${displaystyle L_ {pp, gamma -norm} = {frac {t ^ {gamma}} {2}} vlevo (L_ {xx} + L_ {yy} - {sqrt {(L_ {xx} -L_ {yy}) ^ {2} + 4L_ {xy} ^ {2}}} vpravo)}$

vyjádřeno v ${displaystyle gamma}$-normalizované deriváty s

${displaystyle partial _ {xi} = t ^ {gamma / 2} částečné _ {x}, částečné _ {eta} = t ^ {gamma / 2} částečné _ {y}}$.

• Náměstí ${displaystyle gamma}$-rozdíl normalizovaných čtvercových vlastních čísel

${displaystyle N_ {gamma -norm} = left (L_ {pp, gamma -norm} ^ {2} -L_ {qq, gamma -norm} ^ {2} ight) ^ {2} = t ^ {4gamma} (L_ {xx} + L_ {yy}) ^ {2} vlevo ((L_ {xx} -L_ {yy}) ^ {2} + 4L_ {xy} ^ {2} ight).}$

• Náměstí ${displaystyle gamma}$-normalizovaný rozdíl vlastních čísel

${displaystyle A_ {gamma -norm} = left (L_ {pp, gamma -norm} -L_ {qq, gamma -norm} ight) ^ {2} = t ^ {2gamma} left ((L_ {xx} -L_ { yy}) ^ {2} + 4L_ {xy} ^ {2} ight).}$

Pojem ${displaystyle gamma}$-normalizované deriváty jsou zde zásadní, protože umožňují správnou kalibraci algoritmů detektoru hřebene a údolí. Vyžadováním toho, aby u jednorozměrného Gaussova hřebene vloženého do dvou (nebo tří rozměrů) měla být detekční stupnice rovna šířce hřebenové struktury měřené v jednotkách délky (požadavek shody mezi velikostí detekčního filtru a struktura obrazu, na kterou reaguje), z toho vyplývá, že je třeba si vybrat ${displaystyle gamma = 3/4}$. Z těchto tří měr síly hřebene první entita ${displaystyle L_ {pp, gamma -norm}}$ je měřítko síly hřebene pro všeobecné použití s ​​mnoha aplikacemi, jako je detekce krevních cév a extrakce silnic. Subjekt nicméně ${displaystyle A_ {gamma -norm}}$ byl použit v aplikacích, jako je vylepšení otisků prstů,^[6] sledování ruky v reálném čase a rozpoznávání gest^[7] stejně jako pro modelování statistik místního obrazu pro detekci a sledování lidí v obrazech a videích.^[8]

Existují také další úzce související definice hřebenů, které využívají normalizované deriváty s implicitním předpokladem ${displaystyle gamma = 1}$.^[9] Rozvíjejte tyto přístupy podrobněji. Při detekci hřebenů pomocí ${displaystyle gamma = 1}$, nicméně, detekční stupnice bude dvakrát větší než pro ${displaystyle gamma = 3/4}$, což má za následek více tvarových zkreslení a nižší schopnost zachytit hřebeny a údolí s blízkými interferujícími strukturami obrazu v doméně obrazu.

Dějiny

Pojem hřebeny a údolí v digitálních obrazech představil Haralick v roce 1983^[10] a Crowley týkající se rozdíl Gaussianů pyramidy v roce 1984.^[11][12] Aplikace hřebenových deskriptorů při analýze lékařského obrazu byla rozsáhle studována Pizerem a jeho spolupracovníky^[13][14][15] což má za následek jejich představu o M-opakováních.^[16] Lindeberg zavedením detekce hřebenů také podpořil ${displaystyle gamma}$-normalizované deriváty a hřebeny v měřítku a prostoru definované z lokální maximalizace vhodně normalizovaného hlavního hlavního zakřivení hesenské matice (nebo jiné míry síly hřebene) v prostoru a v měřítku. Tyto pojmy byly později vyvinuty s aplikací na těžbu silnic Steger et al.^[17][18] a k segmentaci krevních cév Frangi et al.^[19] stejně jako k detekci křivočarých a tubulárních struktur Sato et al.^[20] a Krissian a kol.^[21] Přehled několika klasických hřebenových definic v pevném měřítku, včetně vztahů mezi nimi, podali Koenderink a van Doorn.^[22] Přehled technik extrakce cév představili Kirbas a Quek.^[23]

Definice hřebenů a údolí v N rozměrech

V nejširším smyslu pojem ridge zobecňuje myšlenku místního maxima funkce se skutečnou hodnotou. Bod ${displaystyle mathbf {x} _ {0}}$ v doméně funkce ${displaystyle f: mathbb {R} ^ {n} ightarrow mathbb {R}}$ je místní maximum funkce, pokud je vzdálenost ${displaystyle delta> 0}$ s majetkem, že pokud ${displaystyle mathbf {x}}$ je uvnitř ${displaystyle delta}$ jednotky ${displaystyle mathbf {x} _ {0}}$, pak ${displaystyle f (mathbf {x})$. Je dobře známo, že kritické body, z nichž jsou lokální maxima pouze jedním typem, jsou izolované body v doméně funkce ve všech, s výjimkou neobvyklých situací (tj., negenerické případy).

Zvažte uvolnění tohoto stavu ${displaystyle f (mathbf {x})$ pro ${displaystyle mathbf {x}}$ v celé čtvrti ${displaystyle mathbf {x} _ {0}}$ mírně vyžadovat pouze to, aby toto držení na ${displaystyle n-1}$ dimenzionální podmnožina. Tato relaxace pravděpodobně umožňuje, aby soubor bodů, které splňují kritéria, které budeme nazývat hřeben, měl alespoň v obecném případě jediný stupeň volnosti. To znamená, že sada hřebenových bodů vytvoří jednorozměrný lokus nebo hřebenovou křivku. Všimněte si, že výše uvedené lze upravit tak, aby zobecnil myšlenku na místní minima a vedl k tomu, co by se dalo nazvat jednorozměrnými údolními křivkami.

Tato následující definice hřebenu navazuje na knihu Eberly^[24] a lze jej chápat jako zobecnění některých výše uvedených definic hřebene. Nechat ${displaystyle Usubset mathbb {R} ^ {n}}$ být otevřenou sadou a ${displaystyle f: Uightarrow mathbb {R}}$ být hladký. Nechat ${displaystyle mathbf {x} _ {0} v U}$. Nechat ${displaystyle abla _ {mathbf {x} _ {0}} f}$ být gradientem ${displaystyle f}$ na ${displaystyle mathbf {x} _ {0}}$a nechte ${displaystyle H_ {mathbf {x} _ {0}} (f)}$ být ${displaystyle n imes n}$ Hesenská matice ${displaystyle f}$ na ${displaystyle mathbf {x} _ {0}}$. Nechat ${displaystyle lambda _ {1} leq lambda _ {2} leq cdots leq lambda _ {n}}$ být ${displaystyle n}$ objednané vlastní hodnoty z ${displaystyle H_ {mathbf {x} _ {0}} (f)}$ a nechte ${displaystyle mathbf {e} _ {i}}$ být jednotkovým vlastním vektorem ve vlastním prostoru pro ${displaystyle lambda _ {i}}$. (K tomu je třeba předpokládat, že všechny vlastní hodnoty jsou odlišné.)

Bod ${displaystyle mathbf {x} _ {0}}$ je bod na jednorozměrném hřebenu ${displaystyle f}$ pokud platí následující podmínky:

1. ${displaystyle lambda _ {n-1} <0}$, a
2. ${displaystyle abla _ {mathbf {x} _ {0}} fcdot mathbf {e} _ {i} = 0}$ pro ${displaystyle i = 1,2, ldots, n-1}$.

Tím je přesný koncept, který ${displaystyle f}$ omezeno na tento konkrétní ${displaystyle n-1}$-dimenzionální podprostor má místní maximum na ${displaystyle mathbf {x} _ {0}}$.

Tato definice se přirozeně zobecňuje na k-dimenzionální hřeben takto: bod ${displaystyle mathbf {x} _ {0}}$ je bod na k-rozměrný hřeben ${displaystyle f}$ pokud platí následující podmínky:

1. ${displaystyle lambda _ {n-k} <0}$, a
2. ${displaystyle abla _ {mathbf {x} _ {0}} fcdot mathbf {e} _ {i} = 0}$ pro ${displaystyle i = 1,2, ldots, n-k}$.

V mnoha ohledech tyto definice přirozeně zobecňují definici lokálního maxima funkce. Vlastnosti hřebenů maximální konvexity staví Damon na pevnou matematickou základnu^[1] a Miller.^[2] Jejich vlastnosti v rodinách s jedním parametrem stanovil Keller.^[25]

Maximum Scale Ridge

Následující definici lze vysledovat k Fritschovi^[26] který se zajímal o extrakci geometrických informací o obrázcích do dvourozměrných obrázků ve stupních šedi. Fritsch filtroval svůj obraz filtrem „mediality“, který mu poskytoval informace analogické „vzdáleným hranicím“ dat v měřítku-prostoru. Hřebeny tohoto obrazu, jakmile byly promítnuty do původního obrazu, měly být analogické s kostrou tvaru (např., Blum Medial Axis) původního obrazu.

Následuje definice maximálního rozsahu stupnice funkce tří proměnných, z nichž jedna je parametrem „scale“. Jedna věc, kterou chceme, aby byla v této definici pravdivá, je, pokud ${displaystyle (mathbf {x}, sigma)}$ je bod na tomto hřebeni, pak je hodnota funkce v bodě maximální v měřítku. Nechat ${displaystyle f (mathbf {x}, sigma)}$ být plynulá diferencovatelná funkce na ${displaystyle Usubset mathbb {R} ^ {2} imes mathbb {R} _ {+}}$. The ${displaystyle (mathbf {x}, sigma)}$ je bod na hřebenu maximálního měřítka právě tehdy

1. ${displaystyle {frac {částečné f} {částečné sigma}} = 0}$ a ${displaystyle {frac {částečné ^ {2} f} {částečné sigma ^ {2}}} <0}$, a
2. ${displaystyle abla fcdot mathbf {e} _ {1} = 0}$ a ${displaystyle mathbf {e} _ {1} ^ {t} H (f) mathbf {e} _ {1} <0}$.

Vztahy mezi detekcí hran a detekcí hřebenů

Účelem detekce hřebene je obvykle zachytit hlavní osu symetrie podlouhlého objektu,^{[Citace je zapotřebí ]} vzhledem k tomu, že účelem Detekce hrany je obvykle zachytit hranici objektu. Některá literatura o detekci hran však chybně^{[Citace je zapotřebí ]} zahrnuje pojem hřebenů do konceptu hran, což zaměňuje situaci.

Pokud jde o definice, existuje úzké spojení mezi detektory hran a hřebenovými detektory. S formulací maxima, jak uvádí Canny,^[27] platí, že hrany jsou definovány jako body, kde velikost přechodu předpokládá lokální maximum ve směru přechodu. Po diferenciálním geometrickém způsobu vyjádření této definice^[28] můžeme ve výše uvedeném ${displaystyle (u, v)}$-coordinate system state that the gradient magnitude of the scale-space representation, which is equal to the first-order directional derivative in the ${displaystyle v}$-směr ${displaystyle L_ {v}}$, by měl mít svůj směrový derivát prvního řádu v ${displaystyle v}$-směr rovný nule

${displaystyle partial _ {v} (L_ {v}) = 0}$

zatímco směrová derivace druhého řádu v ${displaystyle v}$- směr ${displaystyle L_ {v}}$ by měl být záporný, tj.

${displaystyle částečný _ {vv} (L_ {v}) leq 0}$.

Napsáno jako explicitní výraz z hlediska místních parciálních derivací ${displaystyle L_ {x}}$, ${displaystyle L_ {y}}$ ... ${displaystyle L_ {yyy}}$, tuto definici hran lze vyjádřit jako křivky přechodu nuly diferenciálního invariantu

${displaystyle L_ {v} ^ {2} L_ {vv} = L_ {x} ^ {2}, L_ {xx} + 2, L_ {x}, L_ {y}, L_ {xy} + L_ {y} ^ {2}, L_ {yy} = 0,}$

které splňují podmínku znaménka na následujícím diferenciálním invariantu

${displaystyle L_ {v} ^ {3} L_ {vvv} = L_ {x} ^ {3}, L_ {xxx} + 3, L_ {x} ^ {2}, L_ {y}, L_ {xxy} + 3, L_ {x}, L_ {y} ^ {2}, L_ {xyy} + L_ {y} ^ {3}, L_ {yyy} leq 0}$

(viz článek na Detekce hrany Pro více informací). Zejména takto získané hrany jsou hřebeny magnitudy gradientu.

Viz také

• Měřítko prostoru
• Detekce funkcí (počítačové vidění)
• Detekce hrany
• Detekce úrokových bodů
• Detekce blobů
• Počítačové vidění

Reference

externí odkazy