Wykrywanie grzbietu

Aby zapoznać się z innymi elementami zwanymi grzbietami, zobacz Grzbiet (ujednoznacznienie) .

W przetwarzaniu obrazu wykrywanie grzbietów to próba zlokalizowania grzbietów na obrazie za pomocą oprogramowania , zdefiniowanych jako krzywe, których punkty są lokalnymi maksimami funkcji, podobnymi do grzbietów geograficznych .

Dla funkcji N zmiennych jej grzbiety są zbiorem krzywych, których punkty są lokalnymi maksimami w N - 1 wymiarach. Pod tym względem pojęcie punktów grzbietowych rozszerza koncepcję maksimum lokalnego . Odpowiednio pojęcie dolin dla funkcji można zdefiniować, zastępując warunek lokalnego maksimum warunkiem lokalnego minimum . Połączenie zestawów grzbietowych i dolinowych wraz z powiązanym zbiorem punktów zwanym zbiorem łączników , tworzą połączony zestaw krzywych, które dzielą, przecinają lub spotykają się w punktach krytycznych funkcji. Ta suma zbiorów nazywana jest względnym zbiorem krytycznym funkcji .

Zestawy grzbietów, zestawy dolin i względne zbiory krytyczne reprezentują ważne informacje geometryczne właściwe dla funkcji. W pewnym sensie zapewniają zwartą reprezentację ważnych cech funkcji, ale zakres, w jakim można je wykorzystać do określenia globalnych cech funkcji, pozostaje kwestią otwartą. Główną motywacją do stworzenia grzbietów i dolin jest analiza obrazu i wizja komputerowa , a celem jest uchwycenie wnętrza wydłużonych obiektów w domenie obrazu. Reprezentacje związane z grzbietem pod względem segmentacji obrazu wykorzystano zlewnie . Podejmowano również próby uchwycenia kształtów obiektów za pomocą reprezentacji graficznych, które odzwierciedlają grzbiety, doliny i punkty krytyczne w domenie obrazu. Takie reprezentacje mogą jednak być bardzo wrażliwe na szum, jeśli są obliczane tylko w jednej skali. Ponieważ obliczenia teoretyczne w przestrzeni skali obejmują splot z jądrem Gaussa (wygładzającym), spodziewano się, że wykorzystanie wieloskalowych grzbietów, dolin i punktów krytycznych w kontekście teorii przestrzeni skali powinno pozwolić na bardziej solidną reprezentację obiektów ( lub kształty) na obrazku.

Pod tym względem grzbiety i doliny można postrzegać jako uzupełnienie naturalnych punktów orientacyjnych lub lokalnych punktów ekstremalnych. Przy odpowiednio zdefiniowanych koncepcjach, grzbiety i doliny w krajobrazie intensywnym (lub w innej reprezentacji wywodzącej się z krajobrazu intensywnego) mogą tworzyć niezmienny w skali szkielet organizujący ograniczenia przestrzenne lokalnego wyglądu, z wieloma jakościowymi podobieństwami do sposobu, w jaki środkowa część Bluma transformacja osi zapewnia szkielet kształtu dla obrazów binarnych . W typowych zastosowaniach deskryptory grzbietów i dolin są często używane do wykrywania dróg na zdjęciach lotniczych oraz do wykrywania naczyń krwionośnych na obrazach siatkówki lub trójwymiarowych obrazach rezonansu magnetycznego .

Różniczkowa definicja geometryczna grzbietów i dolin w ustalonej skali na obrazie dwuwymiarowym

Niech $f (x, y)}$${\ displaystyle f ( x, y)}$$displaystyle$ oznacza funkcję dwuwymiarową i niech będzie reprezentacją w przestrzeni skali fa otrzymane przez splot z funkcją Gaussa ${\ displaystyle f (x, y)}$

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

$}$ niech i ${\ displaystyle L_ {pp$ oznaczają wartości macierzy Hessego

${\ Displaystyle H = {\ początek {bmatrix} L_ {xx} i L_ {xy} \\ L_ {xy} i L_ {yy} \ koniec {bmatrix} }}$

w przestrzeni skali z transformacją współrzędnych (obrótem) zastosowaną do lokalnych operatorów pochodnych kierunkowych, ${\ displaystyle L}$

${\ Displaystyle \ częściowe _ {p} = \ sin \ beta \ częściowe _ {x} - \cos \beta \partial _{y},\partial _{q}=\cos \beta \partial _{x}+\sin \beta \partial _{y}}$

gdzie p i q są współrzędnymi obróconego układu współrzędnych.

Można wykazać, że pochodna mieszana $układzie$ współrzędnych wynosi zero, jeśli tak wybierzemy

${\ Displaystyle \ cos \ beta = {\ sqrt {{\ Frac {1 } 2}}}}\right)}}}$ , ${\ Displaystyle \ sin \ beta = \ nazwa operatora {sgn} (L_ {xy} ){\sqrt {{\frac {1}{2}}\left(1-{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^ {2}+4L_{xy}^{2}}}}\right)}}}$ .

Następnie formalną różniczkową geometryczną definicję grzbietów w ustalonej skali $}$ wyrazić jako zbiór punktów spełniających $\ displaystyle f (x, y)$

${\ Displaystyle L_ {p} = 0, L_ {pp} \ równoważnik 0, | L_ {pp} | \ geq | L_ {qq} |.}$

Odpowiednio doliny w skali $}$ zbiorem punktów ${\ displaystyle f (x, y)$

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

W układzie współrzędnych z $v)}$ równoległym do gradientu obrazu za $displaystyle (u,$

${\ Displaystyle \ częściowe _ {u} = \ sin \ alfa \ częściowe _ {x} - \cos \alpha \partial _{y},\partial _{v}=\cos \alpha \partial _{x}+\sin \alpha \partial _{y}}$

Gdzie

${\ Displaystyle \ cos \ alfa = {\ Frac {L_ {x}} {\ sqrt {L_ { x}^{2}+L_{y}^{2}}}},\sin \alpha ={\frac {L_{y}}{\sqrt {L_{x}^{2}+L_{y} ^{2}}}}}$

można wykazać, że tę definicję grzbietu i doliny można zamiast tego równoważnie zapisać jako

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

Gdzie

${\ 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 znak określa polaryzację; ${\ displaystyle L_ {uu}} ;$${\ displaystyle L_ {uu} <0}$ dla grzbietów i ${\ displaystyle L_ {uu}> 0}$ dla dolin.

Obliczanie grzbietów o zmiennej skali na podstawie obrazów dwuwymiarowych

Głównym problemem związanym z przedstawioną powyżej definicją grzbietu o stałej skali jest to, że może ona być bardzo wrażliwa na wybór poziomu skali. Eksperymenty pokazują, że parametr skali jądra wstępnego wygładzania Gaussa musi być starannie dostrojony do szerokości struktury grzbietu w domenie obrazu, aby detektor grzbietu wytworzył połączoną krzywą odzwierciedlającą leżące pod spodem struktury obrazu. Aby poradzić sobie z tym problemem w przypadku braku wcześniejszych informacji, pojęcie grzbietów w przestrzeni skali wprowadzono, który traktuje parametr skali jako nieodłączną właściwość definicji grzbietu i pozwala na zmianę poziomów skali wzdłuż grzbietu w przestrzeni skali. Co więcej, koncepcja grzbietu w przestrzeni skali umożliwia również automatyczne dostrojenie parametru skali do szerokości struktur grzbietowych w domenie obrazu, w rzeczywistości w wyniku dobrze podanej definicji. W literaturze zaproponowano wiele różnych podejść bazujących na tej koncepcji.

Niech ${\ displaystyle R (x, y, t)}$ oznacza miarę wytrzymałości grzbietu (określoną poniżej). Następnie dla obrazu dwuwymiarowego grzbiet w przestrzeni skali jest zbiorem spełniających punktów

${\ Displaystyle L_ {p} = 0, L_ {pp} \ równoważnik 0, \ częściowy _ {t} (R )=0,\częściowy _{tt}(R)\równ. 0,}$

gdzie jest $skali$ w reprezentacji w przestrzeni skali . Podobnie dolina w przestrzeni skali to zbiór punktów, które spełniają

${\ Displaystyle L_ {q} = 0, L_ {qq} \ geq 0, \ częściowe _ {t} ( R)=0,\częściowy _{tt}(R)\równ. 0.}$

Bezpośrednią konsekwencją tej definicji jest to, że w przypadku obrazu dwuwymiarowego koncepcja grzbietów przestrzeni skali wykreśla zbiór jednowymiarowych krzywych w trójwymiarowej przestrzeni skali, gdzie parametr skali może zmieniać się wzdłuż skali -grzbiet kosmiczny (lub dolina łuskowa). Deskryptor grzbietu w dziedzinie obrazu będzie wówczas rzutem tej trójwymiarowej krzywej na dwuwymiarową płaszczyznę obrazu, gdzie informacje o skali atrybutów w każdym punkcie grzbietu mogą zostać wykorzystane jako naturalne oszacowanie szerokości struktury grzbietu w domena obrazu w sąsiedztwie tego punktu.

W literaturze zaproponowano różne miary wytrzymałości grzbietu. Kiedy Lindeberg (1996, 1998) ukuł termin grzbiet w przestrzeni skali, wziął pod uwagę trzy miary wytrzymałości grzbietu:

• Główna główna krzywizna

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

$\ gamma /2}\częściowe _{x},\częściowe _{\eta }=t^{\gamma /2}\częściowe _{y}}$ .

w postaci $x$ znormalizowanych pochodnych z

• Kwadrat różnicy wartości $γ$ kwadratowej

$}$

${\ Displaystyle N _ {\ gamma -norm} = \ lewo (L _ {pp, \ gamma -norm} ^ {2} -L_ {qq, \ gamma -norm} ^ {2} \ prawo) ^ {2} = t ^{4\gamma }(L_{xx}+L_{yy})^{2}\left((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right )$

${\ Displaystyle A _ {\ gamma -norm} = \ lewo (L _ {pp, \ gamma -norm} -L_ {qq, \ gamma -norm} \ prawo) ^ {2} = t ^ {2 \ gamma} \ lewo ((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right).}$

• Kwadrat znormalizowanej $m$ wartości własnej

Pojęcie $-znormalizowanych pochodnych jest tutaj istotne, ponieważ pozwala na prawidłową$ algorytmów detektora grzbietów i dolin. Wymagając, aby w przypadku jednowymiarowego grzbietu Gaussa osadzonego w dwóch (lub trzech wymiarach) skala wykrywania była równa szerokości struktury grzbietu mierzonej w jednostkach długości (wymóg dopasowania rozmiaru filtra detekcyjnego $displaystyle \ gamma = 3/4}$ że należy wybrać . Z tych trzech miar wytrzymałości grzbietu, pierwsza jednostka $.$ takich jak wykrywanie i wydobycie dróg. $,$ jednostka została wykorzystana w takich zastosowaniach, jak ulepszanie odcisków czasie i rozpoznawanie gestów , a także modelowanie lokalnych statystyk obrazu w celu wykrywania i śledzenia ludzi na obrazach i wideo.

$założeniem$ grzbietów, które wykorzystują znormalizowane pochodne z . Rozwiń te podejścia bardziej szczegółowo. $1$ przy wykrywaniu grzbietów będzie dwukrotnie większa niż w przypadku $displaystyle \ gamma$ , co skutkuje większymi zniekształceniami kształtu i mniejszą zdolnością do uchwycenia grzbietów i dolin z pobliskimi zakłócającymi strukturami obrazu w domenie obrazu.

Historia

Pojęcie grzbietów i dolin w obrazach cyfrowych zostało wprowadzone przez Haralicka w 1983 r. i Crowleya w odniesieniu do różnic w piramidach Gaussa w 1984 r. Pizer i jego współpracownicy szeroko badali zastosowanie deskryptorów grzbietów do analizy obrazów medycznych, co doprowadziło do ich koncepcji powtórzeń M. Lindeberg polepszył także wykrywanie grzbietów, wprowadzając -znormalizowane pochodne i grzbiety w przestrzeni skali zdefiniowane na podstawie lokalnej maksymalizacji odpowiednio znormalizowanej głównej krzywizny macierzy Hessego (lub innych miar wytrzymałości grzbietu) ${\ displaystyle \ gamma}$ ponad przestrzenią i ponad skalą. Pojęcia te zostały później rozwinięte w zastosowaniu do ekstrakcji dróg przez Stegera i in. oraz segmentację naczyń krwionośnych przeprowadzoną przez Frangi i in. a także do wykrywania struktur krzywoliniowych i rurowych przez Sato i in. oraz Krissian i in. Przeglądu kilku klasycznych definicji grzbietów w ustalonej skali, łącznie z relacjami między nimi, przeprowadzili Koenderink i van Doorn. Przegląd technik ekstrakcji naczyń przedstawili Kirbas i Quek.

Definicja grzbietów i dolin w wymiarach N

W najszerszym znaczeniu pojęcie grzbietu uogólnia ideę lokalnego maksimum funkcji o wartościach rzeczywistych. Punkt w dziedzinie funkcji ${\ displaystyle f: \ mathbb {R} ^ {n} \rightarrow \ mathbb {R$$}$ jest lokalnym maksimum funkcji, jeśli istnieje odległość $\ displaystyle \ delta$ właściwością, że jeśli mieści się w obrębie $δ$$> 0$ jednostki ${\ Displaystyle \ mathbf {x} _ {0}}$ , następnie ${\ Displaystyle f (\ mathbf {x}) <f (\ mathbf {x} _ {0} )}$ . Powszechnie wiadomo, że punkty krytyczne, których maksima lokalne są tylko jednym typem, są izolowanymi punktami w dziedzinie funkcji we wszystkich sytuacjach z wyjątkiem najbardziej nietypowych (tj. przypadków nieogólnych).

$x$ warunku, że $displaystyle$ mathbf w całym sąsiedztwie $,$ aby to się trzymało ${\ displaystyle n-1}$ podzbiór wymiarowy. Prawdopodobnie to rozluźnienie pozwala, aby zbiór punktów spełniających kryteria, który nazwiemy grzbietem, miał jeden stopień swobody, przynajmniej w przypadku ogólnym. Oznacza to, że zbiór punktów grzbietowych utworzy jednowymiarowe miejsce lub krzywą grzbietową. Należy zauważyć, że powyższe można zmodyfikować, aby uogólnić pomysł na lokalne minima i uzyskać coś, co można nazwać jednowymiarowymi krzywymi doliny.

Poniższa definicja grzbietu jest zgodna z książką Eberly'ego i może być postrzegana jako uogólnienie niektórych z wyżej wymienionych definicji grzbietów. Niech $będzie$ i $_$ _ Niech ${\ displaystyle \ mathbf {x} _ {0} \ w U}$ . Niech ${\ displaystyle \ nabla _ {\ mathbf {x} _ {0}} f}$ będzie gradientem ${\ displaystyle f}$ w ${\ displaystyle \ mathbf {x} _ {0}}$ i niech ${\ displaystyle H _ {\ mathbf {x} _ {0}} (f)}$ będzie ${\ displaystyle n \ razy n}$ macierz Hesja z ${\ displaystyle f}$ w ${\ displaystyle \ mathbf {x} _ {0}}$ . Niech ${\ Displaystyle \ lambda _ {1} \ równoważnik \ lambda _ {2} \ równoważnik \ cdots \ równoważnik \ lambda _ {n}} być$ uporządkowanymi $displaystyle$ własnymi $H_ {\ mathbf {x} _ {0}} (f)}$ i $mathbf {e} _ {i}}$ jednostkowym wektorem własnym w przestrzeni własnej dla $}}$${\ displaystyle \$ . (W tym celu należy założyć, że wszystkie wartości własne są różne.)

Punkt jest punktem na 1-wymiarowym grzbiecie, jeśli spełnione są następujące warunki: $} _ {0}}$${\ displaystyle \ mathbf {$

1. ${\ displaystyle \ lambda _ {n-1} <0}$ i
2. ${\ Displaystyle \ nabla _ {\ mathbf {x} _ {0}} f \ cdot \ mathbf {e} _ {i} = 0}$ dla ${\ Displaystyle i = 1,2, \ ldots, n-1}$ .

$ograniczona$ koncepcję, że $miejscu$ tej konkretnej ma lokalne maksimum $.$

$są$ naturalny sposób uogólnia się na k -wymiarowy $grzbiet$ w następujący sposób: punkt jest punktem na k -wymiarowym grzbiecie, jeśli spełnione następujące warunki :

1. ${\ displaystyle \ lambda _ {nk} <0}$ i
2. ${\ Displaystyle \ nabla _ {\ mathbf {x} _ {0}} f \ cdot \ mathbf {e} _ {i} = 0}$ dla ${\ Displaystyle ja = 1,2, \ ldots, nk}$ .

Pod wieloma względami definicje te w naturalny sposób uogólniają definicję maksimum lokalnego funkcji. Właściwości maksymalnych grzbietów wypukłych zostały oparte na solidnych podstawach matematycznych przez Damona i Millera. Ich właściwości w rodzinach jednoparametrowych ustalił Keller.

Maksymalny grzbiet skali

Poniższą definicję wywodzi się od Fritscha, który interesował się wydobywaniem informacji geometrycznych o figurach z dwuwymiarowych obrazów w skali szarości. Fritsch przefiltrował swój obraz za pomocą filtra „medialności”, który dostarczył mu informacji analogicznych do danych „odległych od granicy” w przestrzeni skali. Grzbiety tego obrazu, rzutowane na obraz oryginalny, miały być analogiczne do szkieletu kształtu ( np . środkowej osi Bluma ) obrazu pierwotnego.

Poniżej znajduje się definicja maksymalnego grzbietu skali funkcji trzech zmiennych, z których jedna jest parametrem „skali”. Jedną rzeczą, którą chcemy, aby była prawdziwa w tej definicji, jest to, że jeśli jest punktem na tym grzbiecie, to wartość funkcji w tym punkcie wynosi ${\ displaystyle (\ mathbf {x}, \ sigma)}$ maksimum w wymiarze skali. Niech będzie gładką funkcją różniczkowalną na ${\ displaystyle f (\ mathbf {x}, \ sigma)}$${\ Displaystyle U \ podzbiór \ mathbb {R} ^ {2} \ razy \ mathbb {R} _ {+}}$ . $(\ mathbf {x}, \ sigma)}$ displaystyle jest punktem na grzbiecie maksymalnej skali wtedy i tylko wtedy, gdy

1. ${\ Displaystyle {\ Frac {\ częściowe f} {\ częściowe \ sigma}} = 0}$ i ${\ Displaystyle {\ Frac {\ częściowe ^ {2} f} \partial \sigma ^{2}}<0}$ i
2. ${\ Displaystyle \ nabla f \ cdot \ mathbf {e} _ {1} = 0}$ i ${\ Displaystyle \ mathbf {e} _ {1} ^ {t}H(f)\mathbf {e} _{1<0}$ .

Zależności pomiędzy wykrywaniem krawędzi a wykrywaniem grzbietów

Celem wykrywania grzbietów jest zwykle uchwycenie głównej osi symetrii wydłużonego obiektu, , podczas gdy celem wykrywania krawędzi jest zwykle uchwycenie granicy obiektu. Jednakże w niektórych publikacjach na temat wykrywania krawędzi błędnie włącza pojęcie grzbietów do pojęcia krawędzi, co dezorientuje sytuację.

Pod względem definicji istnieje ścisłe powiązanie pomiędzy detektorami krawędzi i detektorami grzbietów. Przy sformułowaniu niemaksimum podanym przez Canny'ego utrzymuje się, że krawędzie definiuje się jako punkty, w których wielkość gradientu przyjmuje lokalne maksimum w kierunku gradientu. Kierując się różniczkowym geometrycznym sposobem wyrażania tej definicji, możemy w wyżej wymienionym układzie współrzędnych stwierdzić, że wielkość gradientu reprezentacji w przestrzeni skali, która jest równa ( $\ displaystyle (u, v)}$ pochodna kierunkowa pierwszego rzędu w ${\ displaystyle v}$ -kierunek $równym$$mieć swoją$ pochodną kierunkową pierwszego rzędu w

${\ Displaystyle \ częściowe _ {v} (L_ {v}) = 0}$

podczas gdy pochodna kierunkowa drugiego rzędu w $powinna$ być ujemna, tj. ${\ displaystyle L_ {v}}$

${\ Displaystyle \ częściowe _ {vv} (L_ {v}) \ równoważnik 0}$ .

Zapisane jako wyraźne wyrażenie w kategoriach lokalnych pochodnych cząstkowych , to ${\ displaystyle L_ {x}}$ , ${\ displaystyle L_ {y}}$ ... ${\ displaystyle L_ {yyy}}$ definicję krawędzi można wyrazić jako krzywe przecinające zero niezmiennika różniczkowego

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

które spełniają warunek znaku na następującym niezmienniku różniczkowym

${\ 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}\równ. 0}$

więcej informacji można znaleźć w artykule na temat wykrywania krawędzi ). Warto zauważyć, że krawędzie uzyskane w ten sposób są grzbietami wielkości gradientu.

Zobacz też

• Wykrywanie plam
• Wizja komputerowa
• Wykrywanie krawędzi
• Wykrywanie cech (wizja komputerowa)
• Wykrywanie punktów procentowych
• Skaluj przestrzeń