Kiedy patrzymy na dwuwymiarowy obraz dowolnej trójwymiarowej sceny (na obrazie, fotografii, ekranie monitora), wydaje nam się, że wszystkie te obiekty, które moglibyśmy zobaczyć, gdybyśmy bezpośrednio obserwowali tę samą scenę w życiu, są tam bezpośrednio obecne. Tymczasem wszystko, co faktycznie jest nam dane na dwuwymiarowym obrazie, jest widoczne pole, czyli tylko niektóre funkcja rozkładu jasnościlub zabarwieniena dwuwymiarowej płaszczyźnie: fa(x, y) gdzie xi y- Współrzędne kartezjańskie opisujące płaszczyznę obrazu.
Co więcej, jeśli zbliżysz się do ekranu monitora komputera, zobaczysz, że obraz na ekranie w rzeczywistości nie jest gładki i ciągły, ale jest dyskretną „mozaiką” składającą się z oddzielnych kolorowych prostokątów ułożonych w regularną prostokątną matrycę. To jest to obraz cyfrowy... Z matematycznego punktu widzenia obraz cyfrowyjest dwuwymiarową macierzą Im o rozmiarze (DimXDimY), gdzie x jest liczbą całkowitą od 0 do DimX– 1, opisującą numer elementu w wierszu macierzy, y jest liczbą całkowitą od 0 do DimY– 1, opisującą numer wiersza macierzy, w której ten element się znajduje. W tym przypadku wywoływany jest element samego obrazu cyfrowego (komórka prostokątnej matrycy) piksel(piksel, element obrazu). W najprostszym przypadku każdy piksel Im ma skalarną wartość całkowitą proporcjonalną do wartości funkcji rozkładu jasności fa(x, y) w danym punkcie samolotu.
Na rys. 1.1.1 po lewej stronie znajduje się obraz twarzy kobiety przedstawionej jako obraz, a po prawej powiększony fragment obrazu tej samej twarzy (prawe oko), gdzie dla każdego elementu obrazu wskazana jest odpowiednia numeryczna wartość piksela. Jasne elementy obrazu odpowiadają b owyższe wartości matrycy, ciemne - niższe wartości. Obraz cyfrowy nie zawiera żadnych innych informacji.
@Figa. 1.1.1 Obraz cyfrowy jako dwuwymiarowa macierz intensywności
Rozpoczynając naukę widzenia maszynowego, konieczne jest jasne zrozumienie, że tylko i wyłącznie dwuwymiarowa tablica liczb w takim czy innym formacie jest przechowywana w komputerze jako obraz cyfrowy. Wszelkie inne dane, które chcielibyśmy wyodrębnić z obrazu (kształty, linie, obiekty, wymiary, zawartość wyświetlanego tekstu itp.) - możemy uzyskać tylko w wyniku zastosowania szeregu procedur przetwarzania i analizy obrazu, które musimy albo sami zaprogramować, albo skorzystać z gotowych procedur dostępnych w dobrze znanych pakietach oprogramowania do analizy obrazu. Jednocześnie do rozwiązywania prostych zadań wizji komputerowej zapewne w standardowych bibliotekach procedur przetwarzania obrazu znajdą się gotowe narzędzia, do rozwiązywania bardziej skomplikowanych zadań konieczne będzie łączenie pewnych gotowych procedur, a dla wielu zupełnie „zwyczajnych” zadań, jakie „biologiczne” ludzkie widzenie mogłoby się wydawać , rozwiązuje się łatwo i zabawnie, wizja komputerowa wciąż nie ma rozwiązań i nadal ich szuka. W końcu, korzystając ze swojego naturalnego wzroku, człowiek może z łatwością poruszać się w dowolnym środowisku, rozpoznawać przedmioty, wybierać ścieżkę, prowadzić samochód i wiele, wiele więcej. Dlaczego komputer odbierający obraz z kamery nie jest w stanie tego wszystkiego zrobić? Może to budowa ludzkiego oka?
W rzeczywistości ludzkie oko, podobnie jak kamera wideo, tworzy jedynie „widzialne pole” podobne do obrazu cyfrowego. W tym przypadku układ optyczny, składający się ze źrenicy i soczewki, rzutuje dwuwymiarowy obraz na siatkówkę oka, gdzie światłoczułe komórki („pręciki” i „czopki”) przekształcają powstały obraz w impulsy nerwowe. Dopiero potem złożony mechanizm przetwarzania otrzymanych informacji, funkcjonujący w odpowiedniej części naszego mózgu, interpretuje te impulsy jako obraz widzialnej sceny, którą rozumiemy. Tak więc u ludzi funkcję „widzenia” pełni nie tylko oko, ale system „oko + mózg” („czujnik + komputer”). To algorytmy przetwarzania informacji wbudowane w mózg pozwalają osobie zrozumieć, co widzi. Rolę tych wbudowanych algorytmów można zilustrować na poniższym przykładzie.
Kiedy w połowie XX wieku chirurdzy okuliści nauczyli się wykonywać operacje na soczewce oka, wiele osób niewidomych od urodzenia miało techniczną możliwość zobaczenia ich światła. Oznacza to, że po takiej operacji u osoby, która do tej pory była niewidoma (światło po prostu nie przechodziło przez soczewkę), obraz na siatkówce zaczął się formować, a odpowiednie sygnały zaczęły docierać do mózgu dokładnie w taki sam sposób, jak u osób zdrowych. Niestety w tym przypadku „widzenie światła” nie oznaczało „zaczynać widzieć”. Jak pokazała dalsza historia, większość dorosłych pacjentów „oświeconych technicznie” nigdy nie była w stanie osiągnąć bardziej znaczących wyników w polu widzenia niż rozpoznawanie prostych kształtów geometrycznych - a nawet to wymagało od nich poważnych, świadomych wysiłków. Rozpoznawanie ludzi po ich twarzach i orientacja w przestrzeni pozostaje dla nich przytłaczającym zadaniem. Faktem jest, że te wbudowane mechanizmy „automatycznej” analizy wizualnej, które rozwijają się u ludzi we wczesnym dzieciństwie, nie zostały opracowane u tych pacjentów w odpowiednim czasie i znaleźli się oni w pozycji komputera z urządzeniem do wprowadzania obrazów, ale brakowało im niezbędnego oprogramowania jego analiza.
Aby ostatecznie przekonać się o złożoności zadania, jakie przed nami stoi analiza obrazu będącego dwuwymiarową tablicą danych liczbowych, spróbujmy postawić się w miejscu programu komputerowego zajmującego się liczbami abstrakcyjnymi. W tym celu zmienimy mentalnie modalność percepcji obrazu - przeniesiemy ją z domeny wizualnej na dotykową. Wyobraźmy sobie dwuwymiarową tablicę wartości intensywności jako szachownicę, której rozmiar jest równy rozmiarowi obrazu (DimXDimY), a na środku każdej komórki utknęła kolumna, której wysokość jest proporcjonalna do wartości odpowiedniego piksela w obrazie. Innymi słowy, rozważmy dwuwymiarowy obraz jako rodzaj konwencjonalnej trójwymiarowej powierzchni. Na rys. 1.1.2 po lewej stronie fragment twarzy kobiety jest przedstawiony jako obraz, a po prawej jako pseudo-trójwymiarowy relief.
@Figa. 1.1.2. Obraz cyfrowy jako pseudotrójwymiarowy relief
A teraz wyobraź sobie, że bez patrzenia na obraz musisz poczuć odpowiednią „ulgę” i spróbować określić, co dokładnie przedstawia ta „relief” - dom, pies czy ludzkie oko? Eksperymenty pokazują, że przeciętny człowiek nie jest w stanie poradzić sobie z takim zadaniem. Nawet rozpoznanie najprostszych geometrycznych kształtów w takim „reliefowym” przedstawieniu będzie wiązało się ze znacznym wysiłkiem i będzie wymagało świadomego rozwoju specjalnej umiejętności, strategii i algorytmów odczuwania. Na tym polega, pomimo pozornej prostoty obiektu „obrazu cyfrowego”, prawdziwa złożoność zadań komputerowego i maszynowego widzenia.
UDC 004932: 621.396
T.M. VLASOV, V.G. KALMYKOV
ALGORYTM I PROGRAM ROZPOZNAWANIA ZARYSÓW OBRAZU JAKO SEKWENCJA CYFROWYCH INTERWAŁÓW LINII
Streszczenie: W pracy rozważono algorytm rozpoznawania cyfrowego odcinka linii prostej w konturach obrazów binarnych oraz implementację oprogramowania algorytmu. Wykorzystanie tego algorytmu do przetwarzania obrazów spowoduje bardziej naturalny i ekonomiczny opis w porównaniu ze znanymi sposobami opisu obrazów. Rozważany algorytm i implementacja oprogramowania mogą być wykorzystane również do opisu konturów podczas przetwarzania obrazów półtonowych i kolorowych.
Słowa kluczowe: obraz, kontur, cyfrowe odcinki proste, algorytm, program.
Streszczenie: Na podstawie danych robota indukowany jest algorytm tworzenia obrazów w cyfrowych liniach prostych na konturach obrazów binarnych, a także oprogramowanie do implementacji algorytmu. Algorytm przetwarzania obrazu produktu przed opisem zdjęcia będzie bardziej naturalny i ekonomiczny, w zależności od sposobu przetwarzania obrazu. Zastrzeżony algorytm i implementacja oprogramowania mogą być używane do kodowania konturów w przypadku dopracowanych i kolorowych obrazów. Słowa kluczowe: obraz, kontur, cyfrowe napędy bezpośrednie, algorytm, program.
Streszczenie: W artykule rozważono algorytm rozpoznawania odcinków linii cyfrowych w konturach obrazów binarnych oraz implementację oprogramowania algorytmu. Zastosowanie tego algorytmu w przetwarzaniu obrazu doprowadzi do bardziej naturalnego i ekonomicznego opisu obrazów w porównaniu ze znanymi metodami. Rozważany algorytm i implementacja oprogramowania mogą być również wykorzystywane do opisywania konturów podczas przetwarzania obrazów w skali szarości i kolorowych. Słowa kluczowe: obraz, kontur, odcinki linii cyfrowych, algorytm, program.
1. Wstęp
Analiza strukturalna konturów obrazu jako ciągów odcinków linii i łuków krzywych jest jednym z głównych zadań w przetwarzaniu obrazu w celu ich interpretacji w systemach sztucznej inteligencji.
W większości przypadków obraz można oglądać jako część płaszczyzny, podzieloną na obszary o stałych lub zmiennych parametrach, na przykład gęstość optyczną, kolor, teksturę, definiowanie tła i obiekty obrazu. Integralną właściwością każdego z tych obszarów jest jego granica, czyli kontur jest po prostu połączoną sekwencją składającą się z odcinków linii i łuków krzywych. Podczas przetwarzania bitmapa zarys obiektów jest zwykle podświetlony. Kontury obiektów, przedstawione jako zbiór pojedynczych, granicznych pikseli, nie nadają się jednak do dalszej obróbki, gdyż nie oddają dostatecznie jego istoty geometrycznej.
Rozpoznawanie konturów obrazu w postaci ciągu odcinków prostych można uznać za jedno z głównych zadań w procesie przetwarzania obrazu rastrowego. Rozwiązanie problemu odwzorowania konturu w postaci ciągu odcinków prostych pozwala na uzyskanie opisu obrazu w postaci zwartej, naturalnej dla ludzkiej percepcji, niezmiennej względem przekształceń afinicznych, dogodnej zwłaszcza do przetwarzania przez sieci neuronowe. Segmenty liniowe są głównymi elementami konturu. Łuk krzywej jest również często zastępowany wpisaną w niego linią przerywaną, zarówno w podstawach analizy matematycznej, jak iw wielu praktycznych zastosowaniach.
Znane metody i algorytmy, aw szczególności te zaproponowane w pracy, pozwalają na uzyskanie przybliżonego rozwiązania, które jest nie do przyjęcia dla wszystkich zastosowań.
W artykule rozważymy rozpoznanie konturu obrazu binarnego jako ciąg segmentów linii cyfrowych bez utraty informacji.
2. Kontur jako ciąg odcinków cyfrowych linii prostych
W w tej sekcji Analiza strukturalna konturów obrazu jest traktowana jako sekwencja odcinków cyfrowych linii prostych, które są danymi wyjściowymi do segmentacji konturu na łuki cyfrowych krzywych i odcinki cyfrowych linii prostych.
Ograniczmy się do rozważenia obrazów binarnych, których obiekty są całkowicie określone przez kontury ograniczające. Łuki cyfrowych krzywych, jak również odcinki cyfrowych linii, powstają podczas dyskretyzacji obrazów zawierających kontury utworzone przez odcinki linii i łuki krzywych.
Podczas transformacji tracone są charakterystyczne cechy odcinków linii i łuków krzywych. Biorąc pod uwagę próbkowany obraz przy wystarczającym powiększeniu, często trudno jest rozpoznać poszczególne odcinki linii i łuki krzywych w sekwencji
pionowe i poziome segmenty linii. Dodatkowe trudności powstają podczas przetwarzania, ponieważ kontury - linie matematyczne bez grubości - są wyświetlane na ekranie monitora przez połączone sekwencje pikseli, czyli linie wizualne o grubości.
Aby wykluczyć wynikające z tego problemy, rozważymy obraz uzyskany z oryginału w wyniku próbkowania jako dwuwymiarowy kompleks komórek. W tym przypadku
piksele to dwuwymiarowe elementy tego kompleksu komórkowego. Oprócz pikseli są pęknięcia i kropki. Cracky jest
boki pikseli, które są elementami jednowymiarowymi. Punkty to punkty końcowe pęknięć i narożniki pikseli. Punkty są elementami zerowymiarowymi. Więc
zatem w rozpatrywanym przypadku kontur obiektu jest połączonym zamkniętym ciągiem pęknięć konturu graniczących między pikselami obiektu a tłem. Kontur można opisać jako sekwencję współrzędnych punktów całkowitych,
ograniczające pęknięcia konturowe. Jak pokazano na rysunku, przedstawiający płaszczyznę obrazu jako
kompleks komórek oferuje wiele korzyści. W szczególności granica regionu staje się cienką krzywą o zerowej powierzchni.
Na rys. 1 przedstawia przykład pierwotnego konturu obiektu utworzonego przez łuk krzywej i odcinek prostej, a także jego cyfrowy odpowiednik w postaci ciągu pęknięć. Punkty są ponumerowane, które należą do pęknięć w różnych kierunkach. Podobnie jak w pracach, przez element L rozumiemy połączoną sekwencję pęknięć w tym samym kierunku, wychodzących z określonego punktu i kończących się pęknięciem o tym samym lub prostopadłym kierunku. Na rys. 1 przedstawia jeden z możliwych podziałów konturu na elementy L, które są utworzone przez pęknięcia pomiędzy punktami: (0-2), (2-4), (4-6), (6-8), (8-9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25), (25-27) ), (27-0). Każdy element L charakteryzuje się następującymi parametrami: kierunek względem jego punktu początkowego g (przyjmowany g \u003d 0 - w kierunku do góry, 1 - w prawo, 2 - w dół, 3 - w lewo); l - liczba pęknięć w kierunku g (! \u003d 1,2, ...); kierunek ostatniego pęknięcia q względem kierunku g poprzednich pęknięć (q \u003d -1 - ostatnia rysa skierowana jest w lewo względem kierunku g, +1 - w prawo, 0 - pokrywa się z kierunkiem g). Liczba pęknięć l będzie umownie nazywana „długością” elementu b. Dla elementu b (0-2) g \u003d 0 ,! \u003d 3, q \u200b\u200b\u003d + 1. Dla elementu b (27-0) g \u003d 3, \u003d 1, q \u003d 0.
Metoda selekcji odcinków linii cyfrowych w konturze wykorzystuje następującą właściwość ciągu elementów L tworzących odcinek. Taka sekwencja zawiera L-elementy o tych samych wartościach g, q; ich długości przyjmują wartości! +1. Ponadto
przemienność b -elementów długości! + 1 jest określana przez ułamek ciągły uzyskany przez podzielenie liczb całkowitych n \u003d Ax \u003d | x1 - x2 | i m \u003d Ay \u003d | y1 - y2 \\, gdzie (x13y1), (x2, y2) to współrzędne początkowego
i punkty końcowe odcinka linii: lub
Załóżmy dla pewności, że n\u003e m. Jak wynika ze wzoru (1), l - część całkowita z dzielenia n przez m - odpowiada w odcinku prostej cyfrowej liczbie l kolejnych pęknięć w jednym kierunku. Wraz z sąsiednim prostopadłym pęknięciem tworzą element L długości! k1 kolejne b -elementy o długości l i jeden b -element długości! +1 (lub k1 kolejnych b -elementów długości +1 i jeden b -element długości!) tworzą K1 -element o "długości" k1 (analogicznie do "długości" „Element B). Element b, który różni się długością o 1 od kolejnych elementów b, będzie nazywany zmodyfikowanym elementem b tego elementu K1. Podobnie k2 kolejne elementy K1 o „długości” k1 i jeden element K1 o „długości” k1 +1 (lub k2 kolejne elementy K1 o „długości” k1 +1 i jeden element K1 o „długości” k1) od K2- element „długości” k1. Więc
k + k 2 + k z + ... + kg
dalej, aż członkowie kontynuowanej frakcji zostaną wyczerpani. Element K1 (generalnie element K-1), który różni się długością o 1 od kolejnych elementów K1 (element Kg-1), zmodyfikowany element K1 (element Kg-1) tego elementu K2 (Kg -element). Tak więc wszyscy
cyfrowy odcinek prostej odpowiada ciągłemu ułamkowi, którego elementy określają strukturę tego odcinka.
W konturze na ryc. 1 można wybrać następujące odcinki cyfrowych linii prostych: 0-3, 3-9, 910, 10-17, 17-0.
3. Selekcja odcinków linii cyfrowej w konturze
Podczas przetwarzania konturów obrazów, w szczególności obrazów binarnych, w sekwencji pęknięć tworzących kontur, konieczne jest wybranie części ciągu tworzących odcinki linii. Zagadnienie to można rozpatrywać jako problem wyznaczania elementów ułamka ciągłego przez kolejność elementów L konturu. To zadanie jest odwrotna w stosunku do problemu wyznaczenia struktury odcinka prostej z ciągu wyrazów ułamka ciągłego, otrzymanego jako stosunek różnic między współrzędnymi początku i końca odcinka.
Metoda selekcji odcinków cyfrowej linii prostej polega na sekwencyjnym wykonywaniu następujących czynności.
1. Wyodrębnienie ciągu elementów L w ciągu pęknięć. Ta akcja spełnia definicję całej części! kontynuowana frakcja (1).
2. Wyodrębnienie ciągu elementów Kr o r \u003d 1 w ciągu elementów L i jeden z elementów L każdego elementu K1 musi zawierać 1 pęknięcie więcej lub mniej niż pozostałe. To działanie odpowiada definicji k1 -tego elementu ułamka ciągłego (1). Po jego wykonaniu wartość r należy zwiększyć o 1.
3. Izolacja ciągu elementów Kg w ciągu elementów Kg-1,
ponadto, jeden z elementów Kg-1 każdego elementu Kg musi zawierać jeden element K-2 więcej lub mniej niż pozostałe. Akcja ta odpowiada definicji k (to-ty element ułamka ciągłego (1). Po jej wykonaniu wartość r należy zwiększyć o 1.
4. Paragraf 3 powtarza się tak długo, aż będzie to możliwe z kolejnych elementów Kg
z elementu Km.
5. Określ punkty graniczne między dwoma sąsiednimi elementami L, które nie są zawarte w tym samym elemencie Kr. Te punkty są punktami końcowymi cyfrowych odcinków linii, które tworzą kontur.
Rozważmy algorytm rozdzielania segmentów linii w sekwencji L-elementów
Niech [b5 (fs, gs, qs)); 5 \u003d 0,1, ..., t jest ciągiem elementów L tworzących kontur; x5, y5- współrzędne początku e-tego elementu b; [xy, yy); y \u003d; r \u003d 0,1, ...,!; !< £ - множество
punkty przerwania konturu. Punkty przerwania definiują punkty końcowe segmentów linii, które tworzą kontur. Znajdowanie punktów przerwania oznacza definiowanie odcinków linii tworzących kontur.
Każdy rozpatrywany segment charakteryzuje się elementem Kr, a także łańcuchem
frakcja. W początkowym momencie rozpoznania odcinka linii prostej elementy odpowiadającego ułamka ciągłego są równe 0. Segment można uznać za rozpoznany, jeśli rozpoznane zostaną parametry elementu Kr, w tym jego rząd r oraz wartości elementów odpowiadającego ułamka kontynuowanego.
1. Warunki początkowe.
Podano sekwencje [b5 (f5, gs, qs)) i (x5, y5).
Konieczne jest znalezienie współrzędnych punktów przerwania | x;., Y,).
k0p: \u003d 0, k1p: \u003d 0, k2p: \u003d 0, ..., kr: \u003d 0 są wartościami roboczymi kontynuowanych elementów ułamkowych.
Weźmy punkt 5 \u003d 0 jako punkt początkowy pierwszego odcinka; i \u003d 0; i \u003d 0.
2. Weź pierwszy element b w sekwencji jako początek pierwszego segmentu linii. Jego punkt początkowy to x5, y. Długość / \u003d / 0 jest również wartością pierwszego elementu ułamka ciągłego.
5: \u003d 5 + 1; k1p: \u003d k1p + 1.
3. Sprawdź następny element L, czy tworzy się razem z poprzednim elementem K0.
3.1. Jeśli ((q3 \u003d\u003d q3-1) && (q3 \u003d\u003d 73-1) && (4 \u003d\u003d / 3-1)), to kontynuacja elementu Kg k0p: \u003d k0p +1; 5: \u003d 5 + 1; i kontynuacja odcinka linii. Przejdź do kroku 3.
3.2. Jeśli ((q3 qd3-1) || (q3 qp 73-1) 11 (| / e - / є-1!\u003e 1)), to koniec odcinka linii. Przejdź do kroku 5.
3.3. Jeśli ((& \u003d\u003d 9s + 1) && (% \u003d\u003d 7s + 1) && ((/ 3 + 1 \u003d\u003d / 3 + 1) 1! (/ 3 - 1 \u003d\u003d / 3 + 1))), następnie uzupełnienie elementu K0; Ї \u003d Ї + 1.
4. Sprawdzenie kontynuacji / zakończenia K (-element.
4.1. Jeśli (k \u003d\u003d 0), to k ^ \u003d k ^; cr: \u003d 0; k ^ 1p: \u003d k1 + 1p + 1; 5: \u003d 5 +1; początek elementu Km.
Przejdź do kroku 3.
4.2. Jeśli ((k іΦ 0) && (k \u003d\u003d k ^)), to k ^ 1p: \u003d k ^ 1p + 1; 5: \u003d 5 + 1; kontynuacja elementu Ki + 1. Przejdź do kroku 3.
4.3. Jeśli ((k (Ф 0) && ((k + 1 \u003d\u003d k1p) 11 (k1-1 \u003d\u003d k ^))), to Ї: \u003d +1; koniec elementu Km.
Przejdź do kroku 4.
4.4. Jeśli ((^ φ0) && (| k - k1p |\u003e 1)), to koniec segmentu jest prostą do kroku 5.
5. Koniec segmentu.
X] \u003d Xs; y \u003d Uz; k1p: \u003d 0, k2p: \u003d 0,., kir: \u003d 0; k: \u003d 0, k2: \u003d 0,., k: \u003d 0.
Jeśli (s< S), то s:= s +1; переход к п. 2.
W przeciwnym razie koniec ciągu elementów L. Koniec algorytmu.
W rzeczywistości zaproponowany algorytm wyszukuje elementy ułamka ciągłego i dla każdego otrzymanego elementu Kt i sprawdza, czy ułamek kontynuowany nowo skonstruowanego elementu Kt jest odpowiedni dla już zbudowanego.
4. Program do selekcji odcinków linii cyfrowej
Jak widać z opisu algorytmu, zawiera on znaczną liczbę skoków warunkowych, których użycie jest sprzeczne z zaleceniami programowanie strukturalne ze względu na trudności napotkane podczas debugowania programów. Ponadto liczba parametrów Kt z góry
nie można tego określić, ponieważ zmienna t nie jest z góry ograniczona. Ogranicz wartość t
Oznacza to wcześniejsze ograniczenie rozmiaru obrazu. Implementacja oprogramowania, a zwłaszcza debugowanie proponowanego algorytmu trywialnymi środkami, ze wskazanych powodów, jest znacznie utrudnione. Możliwe jest zmniejszenie trudności związanych z tworzeniem i debugowaniem implementacji oprogramowania, jeśli używasz nowoczesnych narzędzi programowania obiektowego.
Zaproponowany algorytm zaimplementowany jest w postaci programu LINESEGM będącego częścią laboratorium pakiet oprogramowania na temat przetwarzania obrazu w środowisku Visual C ++.
Jako informację początkową program LINESEGM wykorzystuje sekwencje elementów L skonstruowane dla każdego z konturów przetwarzanego obrazu.
Rezultatem programu jest połączona sekwencja cyfrowych odcinków prostych zbudowanych dla każdego konturu, reprezentowana przez współrzędne punktów końcowych odcinków.
Jak widać z algorytmu, operacje konstruowania elementów Kt z elementów Kt-l
są takie same dla wszystkich wartości t. Zwróć na to uwagę wartość początkowa t \u003d 0 iw trakcie działania algorytmu jest każdorazowo zwiększany o 1. Specjalna klasa CKForLn zawiera metody odpowiadające działaniom algorytmu. W procesie uruchamiania programu, który implementuje algorytm dla każdego wzrostu t o 1, tworzony jest nowy obiekt zawierający funkcje wykonujące operacje algorytmu dla każdej wartości t.
Biorąc pod uwagę, że na poziomie zerowym elementy K0 powstają nie z elementów K, ale z L -
elementów, aby zaimplementować algorytm na poziomie zerowym, stworzono specjalną modyfikację klasy CKForLn - klasę Cmini.
Zasada działania programu polega na tym, że dla każdej wartości t w programie zaimplementowany jest obiekt klasy CKForLn t-tego poziomu, zawierający funkcje określające parametry elementu Kt. Początkowe parametry elementu Kt są już parametrami
ukończony element Kt-l, którego parametry zostały określone przez obiekt klasy CKForLn t-1
Poziom wow.
Obiekty klasy CKForLn są implementowane w miarę pojawiania się warunków, a mianowicie: konieczności zbudowania elementu K następnego poziomu, - i gromadzenia w specjalnej tablicy dynamicznej. Obiekt zerowego poziomu jest tworzony natychmiast po uruchomieniu programu.
Implementacja obiektów w tablicy dynamicznej wraz ze wzrostem t pozwala nie nakładać ograniczeń na rozmiar obrazu. Ograniczenia rozmiaru obrazu są określane wyłącznie przez zasoby używanego komputera.
Przy opisie działania programu posłużymy się pojęciem zakończonego Kt -
element. Każdy ukończony element Kt zawiera elementy kt Kt-l i jeden zmodyfikowany element Kt-l zawierający elementy kt-l ± 1 Kt-2, w przeciwieństwie do niekompletnego elementu Kt, który nie zawiera niekompletnego elementu Kt.
Klasa CKForLn zawiera następujące metody.
1. Metoda DK (), (zdefiniuj element K) - zdefiniuj element K.
Określenie elementu Kt-1 oznacza określenie liczby elementów Kt-1, które tworzą dany element Sf.
2. Metoda VK§, (weryfikacja elementu K) - w celu sprawdzenia tożsamości rozpatrywanego elementu K z elementem K o tym samym poziomie, określonym wcześniej funkcją metody DK ().
3. Metoda DEO, (określ koniec elementu K) - określ koniec elementu K, czyli przy definiowaniu elementu Kt znajdź jego zmieniony element Sg-1. Funkcja metody DE () na poziomie t-1 jest wywoływana przez funkcję metody DK () na poziomie t.
4. Metoda VE (), (zweryfikuj koniec elementu K) - sprawdź tożsamość końca rozważanego elementu K przez zmieniony element K, uprzednio określony funkcją metody DE ().
Klasa Cmini zawiera te same metody, które różnią się od metod klasy CKForLn tym, że metody klasy Cmini działają z elementami L i określają lub sprawdzają elementy K0.
Metody klasy Cmini
Metody klasy Cmini wykorzystują jako dane początkowe ciągi elementów L zbudowane dla każdego z konturów przetwarzanego obrazu, począwszy od aktualnego numeru elementu L w momencie wywołania funkcji metody.
Funkcja metody DK () klasy Cmini porównuje parametry każdego następnego elementu L z parametrami początkowego elementu L, o ile są one zgodne. Jeśli parametry nie pasują, funkcja DK () sprawdza, czy element K0 jest zakończony i kończy się
praca. Za zakończony uznaje się element K0 zakończony zmodyfikowanym elementem L, którego długość różni się od pozostałych elementów L elementu K0 o 1 (operacja 3.1 na początku odcinka - t \u003d 0).
Funkcja metody VK () sprawdza, czy parametry kolejnych k0 L -elementów pokrywają się z parametrami L -elementów K0 -elementu z góry określonych funkcją DK ()
na tym samym poziomie. Jeśli parametry obecnego elementu K0 pokrywają się z parametrami wstępnymi
zdefiniowana funkcja VK () stanowi znak kontynuacji segmentu i kończy pracę (operacja 3.1 dla kontynuacji segmentu - t\u003e 0).
W przeciwnym razie funkcja VK () generuje znak końca segmentu i kończy
Funkcja metody DE () porównuje parametry bieżącego elementu Kci z parametrami elementu K0 poprzednio zdefiniowanymi przez funkcję DK () w celu określenia, czy bieżący element K0 jest modyfikowany. Jeśli inne parametry są równe, liczba elementów L k0
zmodyfikowany element K0 w porównaniu z wcześniej ustalonym elementem K0
funkcja DK (), musi różnić się o 1 (operacje 3.2, 3.3 w celu określenia zakończenia
początkowy element K0 segmentu - t \u003d 0). Wynik - parametry zmodyfikowanego elementu K0
są używane w metodzie VE () klasy Cmini.
Funkcja metody VE () porównuje parametry bieżącego elementu K0 z parametrami zmodyfikowanego elementu K0 poprzednio zdefiniowanego przez funkcję DE () w celu ustalenia
czy pokrywają się (operacja 3.2, 3.3 dla kontynuacji odcinka - t\u003e 0). Wynik - znak koincydencji lub nieprzypadku - jest używany w metodzie VК () klasy CKForLn.
Metody klasy CKForLn
Metody wykorzystują parametry elementów K zbudowanych dla najniższego poziomu jako dane wejściowe. To znaczy, aby określić parametry elementu Kt, parametry
już skonstruowane elementy Kt-l.
Funkcja metody DK () poziomu t klasy CKForLn, definiując parametry elementu ^, wywołuje funkcję VK () poziomu t-1 klasy CKForLn, która sprawdza, czy już zdefiniowany element Kt-l następuje po elemencie Kt-l o tych samych parametrach. Jeśli tak, wywołanie funkcji VK () jest powtarzane. W tym przypadku zliczana jest liczba powtórzeń, czyli określa się parametr kt.
W przeciwnym razie funkcja DK () poziomu t wywołuje funkcję DE () z poziomu t-1 w celu określenia zmienionego elementu Kt-l i kończy działanie. Na końcu pracy funkcja DK () poziomu t klasy CKForLn określa parametry i tworzy znaki ukończonego lub niekompletnego elementu Kt (operacje 4.1, 4.2 przy aktualnej maksymalnej wartości t).
Funkcja metody VK () poziomu t klasy CKForLn sprawdza, czy parametry kolejnych elementów kt Kt pokrywają się z parametrami wcześniej zdefiniowanego elementu Kt
funkcja metody DK () na tym samym poziomie. Jeśli parametry obecnego elementu Kt pokrywają się z
przez z góry określoną funkcję DK () Kt - element tego samego poziomu, funkcja VK ()
generuje znak kontynuacji segmentu i wychodzi.
W przeciwnym razie funkcja VK () generuje znak końca segmentu i kończy pracę (operacja 4.1, 4.2 z aktualną wartością t mniejszą od maksymalnej).
Kt -element Funkcja metody DE0 poziomu t klasy CKForLn podczas wyznaczania parametrów elementu Kt porównuje parametry bieżącego elementu Kt z parametrami elementu Kt zdefiniowanego wcześniej przez funkcję DK () w celu określenia, czy aktualny element Kt jest modyfikowany. Jeśli inne parametry są równe, ich wartości kt-1 muszą różnić się o 1. Jeśli ten warunek jest spełniony, funkcja DE () tworzy znak zmienionego elementu Kt i
wyjścia (operacja 4.3, 4.4 przy aktualnej maksymalnej wartości t).
Funkcja metody VE () poziomu t klasy CKForLn porównuje parametry bieżącego elementu Kt z parametrami zmodyfikowanego elementu Kt, przydzielonego wcześniej przez funkcję DE (), w celu określenia, czy wartości ich parametrów są takie same.
Jeśli wartości parametrów bieżącego elementu Kt pokrywają się z wartościami wstępnymi
zdefiniowana przez funkcję DK () na tym samym poziomie, funkcja VK () tworzy znak zbieżności wartości parametrów i kończy pracę (operacja 4.3,4.4 przy aktualnej wartości t mniejszej od maksymalnej).
Wykres czasowy (rys. 2) ilustruje działanie programu LINESEGM na przykładzie rozpoznania odcinka prostej. Dolna część rysunku przedstawia część linia cyfrowaskładający się z elementów L o tych samych głównych i pomocniczych kierunkach i różnych długościach.
W kroku 0 tworzony jest obiekt klasy Stypi, który definiuje parametry elementu K0.
W kroku 10 kończy się określanie parametrów elementu K0 i tworzony jest obiekt 1 klasy CKPrbn, który wykorzystuje funkcje wcześniej utworzonego obiektu do określenia parametrów elementu K1. W kroku 19 kończy się wyznaczanie parametrów elementu K1 i tworzony jest obiekt 2 klasy CKPorbn, który wykorzystuje funkcje wcześniej utworzonych obiektów do wyznaczenia parametrów elementu K2. W kroku 49 kończy się określanie parametrów elementu K2 i tworzony jest obiekt 3 klasy CKPorbn, który wykorzystuje funkcje wcześniej utworzonych obiektów do określenia parametrów elementu K3. Krok 79 zostanie wykonany
warunek zakończenia segmentu. Działanie programu zostało szczegółowo opisane w załączniku.
W odcinku 0-6 dwa elementy L tworzą niekompletny element K0. Jest oczywiste, że b -
element 3-6 o długości 3 zamyka odcinek linii, gdyż b -element 6-7 o długości 1 nie może być jego kontynuacją. Tak więc element b 6-7 jest początkiem cyfrowego odcinka linii.
Na rys. 3 przedstawia przykład programu. Kontur binarnego obrazu kręconej strzałki jest podzielony kwadratami na segmenty linii. Wynik programu - sekwencja odcinków linii - posłużył do wyselekcjonowania łuków krzywych cyfrowych. Duże kwadraty pokazują granice łuków krzywych cyfrowych.
Praca programu została przetestowana na znacznej liczbie (ponad 2000) przykładów i służy do badania analizy strukturalnej obrazów rastrowych.
5. Obsługa programu do rozpoznawania odcinków linii
Rozważmy działanie programu UEEBSM na przykładzie z rys. 4. W dolnej części rysunku pokazano fragment linii cyfrowej, składający się z elementów L o tych samych kierunkach głównych i pomocniczych oraz o różnych długościach. W sekcji 0-6 dwa elementy L tworzą niepełny K0-
Postać: 3. Przykład programu do analizy strukturalnej konturu - segmentacja konturu odcinkami cyfrowych linii prostych
element. Oczywiście b-element 3-6 o długości 3 zamyka odcinek linii, ponieważ b -element 6-7 o długości 1 nie może być jego kontynuacją. Tak więc element b 6-7 jest początkiem cyfrowego odcinka linii.
Praca programu w celu wyznaczenia kolejnego odcinka prostej rozpoczyna się od funkcji OK () poziomu zerowego, która wyznacza ukończony element K0 6-10 składający się z L-elementów
długości 1,1,2; k0 \u003d 2. Ten element K0 jest początkiem elementu K1. Program tworzy obiekt pierwszego poziomu i przekazuje sterowanie do funkcji OK () tego obiektu. Funkcja OK () poziomu 1 wywołuje funkcję VKQ poziomu 0. Funkcja VKQ porównuje parametry elementów L elementu K0 6-10 z kolejnymi elementami L i potwierdza obecność elementu K0 10-14,
identyczny z elementem K0 6-10. Kontynuując pracę, funkcja VKQ wykrywa, że \u200b\u200bnastępujące elementy L nie tworzą tego samego elementu K0, kończy swoją pracę i przekazuje sterowanie do funkcji OK () poziomu 1. Funkcja OK () poziomu 1 wywołuje funkcję OE () poziomu 0. Ta ostatnia, rozpoczynając z b -elementem 6-7 określa obecność zmodyfikowanego K0 -elementu 14-19, składającego się z b -elementów o długościach 1,1,1,2; k0 \u003d 3, kończy i przekazuje sterowanie do funkcji OK () poziomu 1. Ta funkcja określa obecność kompletnego elementu K1 6-19, składającego się z dwóch K0 -
elementy 1,1,2, (k1 \u003d 2) i jeden zmodyfikowany 1,1,1,2 (k0 \u003d 3). Program tworzy obiekt drugiego poziomu i przekazuje sterowanie do funkcji OK () tego obiektu. Funkcja OK () poziomu 2 wywołuje funkcję VKQ poziomu 1, która z kolei wywołuje funkcję VKQ poziomu 0. Funkcja VKQ porównuje parametry b-elementów elementu K0 6-10 z kolejnymi b -
elementów i potwierdza obecność elementów K0 19-23, 23-27, identycznych jak element K0 6-10, czyli taką samą liczbę takich elementów K0 zawartych w elemencie K1 6-19. Ponadto funkcja VKQ poziomu 0 zwraca sterowanie ze znakiem kontynuacji segmentu funkcji VKQ poziomu 1. Funkcja VKQ wywołuje funkcję VE0 poziomu 0, która określa obecność zmienionego K0 -
element 27-32, identyczny z elementem K0 14-19. Zatem zdefiniowano element K1 19-32,
identyczny z elementem K1 6-19. Ponadto funkcja VKQ poziomu 1 nie określa następnego elementu K1 identycznego z elementem K1 6-19, ponieważ funkcja VE0 poziomu 0 nie określa zmienionego elementu K1 identycznego jak element K1 6-19, zaczynając od elementu b 40-41 i przywraca sterowanie do poziomu OK () 2. Funkcja OK () poziomu 2 wywołuje funkcję OE () poziomu 1, która określa obecność zmodyfikowanego elementu K1 32-49, składającego się z elementów K0 32-36, 36- 40,
40-44, 44-49. Następnie wyznaczany jest element K2 6-49, tworzony jest obiekt poziomu 3, określany jest zmodyfikowany element K2 49-79. Te dwa elementy K2 tworzą element K3 6-79. Na tym kończy się budowa segmentu, gdyż kolejne elementy L 79-81 i 81-83 nie tworzą elementu K0,
identyczny z K0 -elementem 6-10, a funkcja poziomu 0 VKQ nie tworzy znaku kontynuacji
człon. W sekwencji elementów L zaznaczony jest odcinek cyfrowej linii prostej 6-79. Program rozpoczyna definiowanie kolejnego segmentu, zaczynając od elementu b 80-82.
b. wnioski
1. Proponowane nowy algorytm dobór odcinków linii w konturach obrazu oraz nietrywialna implementacja programowa algorytmu, które pozwalają uzyskać dokładne rozwiązanie problemu rozpoznawania konturów obrazu jako ciągów odcinków linii.
2. Programowa implementacja algorytmu doboru odcinków prostych w konturach obrazów została wykonana przy użyciu nowoczesnych środków programowania obiektowego, które pozwoliły nie narzucać jednoznacznych ograniczeń co do wielkości przetwarzanego obrazu przy maksymalnym wykorzystaniu zasobów wykorzystywanego komputera.
3. Na podstawie zaproponowanego algorytmu i jego implementacji programowej uzyskano rozwiązanie teoretyczne i przeprowadzono eksperymenty rozpoznawania łuków cyfrowych krzywych oraz segmentacji konturu obrazów binarnych na odcinku cyfrowych linii prostych i łuku cyfrowych krzywych.
LISTA ODNIESIEŃ
1. Kovalevsky V.A. Applications of Digital Straight Segments to Economical Image Encoding, In Proceedings of the 7th International Workshop, DGCI "97, Montpellier. - Francja, 1997. - 3-5 grudnia. - Str. 51-62.
2. Kalmykov V.G. Strukturalna metoda opisywania i rozpoznawania segmentów cyfrowych linii prostych w konturach obrazów binarnych // Piece іntelekt. - 2002. - nr 4. - C. 450-457.
3. Kalmykov V.G., Vishnevsky V.V. Analiza konturów obiektów na obrazach binarnych // Maszyny i systemy matematyczne. - 1997 r. - nr 2. - str. 68 - 71.
4. Kalmikov V.G. Łuk krzywej cyfrowej to wartość i mocowanie // Przetwarzanie sygnałów i obrazu oraz generowanie obrazów. Pratsi somoi Ogólnoukraińska konferencja międzynarodowa. - Kijów. - 2004. - 11-15 zhovten.
Od dawna chciałem napisać ogólny artykuł zawierający podstawy Rozpoznawania Obrazu, przewodnik po podstawowych metodach, podpowiadający, kiedy ich używać, jakie zadania rozwiązują, co można zrobić wieczorem na kolanach, a o czym lepiej nie myśleć bez zespołu ludzi w 20.
Od dłuższego czasu piszę artykuły na temat rozpoznawania optycznego, więc piszą do mnie kilka razy w miesiącu różni ludzie z pytaniami na ten temat. Czasami masz wrażenie, że żyjesz z nimi w różnych światach. Z jednej strony rozumiesz, że osoba jest najprawdopodobniej profesjonalistą w pokrewnym temacie, ale niewiele wie o metodach rozpoznawania optycznego. A najbardziej obraźliwe jest to, że próbuje zastosować metodę z pobliskiego obszaru wiedzy, co jest logiczne, ale nie działa w pełni w Rozpoznawaniu obrazu, ale tego nie rozumie i jest bardzo urażony, jeśli zaczyna mówić coś od podstaw. A biorąc pod uwagę, że opowiadanie od podstaw to dużo czasu, a często go nie ma, staje się jeszcze smutniejsze.
Ten artykuł jest pomyślany tak, aby osoba, która nigdy nie miała do czynienia z metodami rozpoznawania obrazów, mogła w ciągu 10-15 minut stworzyć w głowie pewien podstawowy obraz świata odpowiadający tematowi i zrozumieć, w jakim kierunku należy kopać. Wiele z opisanych tutaj technik ma zastosowanie do radaru i przetwarzania dźwięku.
Zacznę od kilku zasad, o których zawsze zaczynamy mówić potencjalnemu klientowi lub osobie, która chce rozpocząć rozpoznawanie optyczne:
- Rozwiązując problem, zawsze idź od najprostszych. O wiele łatwiej jest zawiesić pomarańczową etykietę na osobie niż podążać za osobą, podkreślając ją kaskadami. O wiele łatwiej jest wziąć aparat o wyższej rozdzielczości niż opracować algorytm super rozdzielczości.
- Ścisłe sformułowanie problemu w metodach rozpoznawania optycznego jest o rząd wielkości ważniejsze niż w problemach z programowaniem systemu: jedno dodatkowe słowo w specyfikacji technicznej może dodać 50% pracy.
- Nie ma uniwersalnych rozwiązań problemów z rozpoznawaniem. Nie możesz stworzyć algorytmu, który po prostu „rozpozna dowolny napis”. Znak na ulicy i kartka tekstu to zasadniczo różne przedmioty. Zapewne da się zrobić ogólny algorytm (tu dobry przykład z Google), ale będzie to wymagało sporo pracy dużego zespołu i składało się z kilkudziesięciu różnych procedur.
- OpenCV to biblia, która ma wiele metod i za pomocą której można rozwiązać 50% objętości prawie każdego problemu, ale OpenCV to tylko niewielka część tego, co faktycznie możesz zrobić. W jednym z badań sformułowano wniosek: „Problem nie jest rozwiązany metodami OpenCV, a zatem jest nierozwiązywalny”. Staraj się tego unikać, nie bądź leniwy i trzeźwo oceniaj bieżące zadanie za każdym razem od zera, bez korzystania z szablonów OpenCV.
Podana tutaj lista metod nie jest kompletna. Sugeruję dodanie metod krytycznych, których nie napisałem w komentarzach i przypisanie każdemu z nich 2-3 słów towarzyszących.
Część 1. Filtracja
W tej grupie umieściłem metody, które pozwalają na wyróżnienie obszarów zainteresowania na obrazach bez ich analizy. Większość z tych metod stosuje pewnego rodzaju jednolitą transformację do wszystkich pikseli obrazu. Na poziomie filtrowania obraz nie jest analizowany, ale przefiltrowane punkty można uznać za obszary o specjalnych właściwościach.Binaryzacja przez próg, wybór obszaru histogramu
Najprostsza transformacja to progowa binaryzacja obrazu. W przypadku obrazów RGB i obrazów w skali szarości progiem jest wartość koloru. Są zadania idealne, w których taka transformacja jest wystarczająca. Załóżmy, że chcesz automatycznie zaznaczyć obiekty na białej kartce papieru:
Wybór progu, przy którym następuje binaryzacja, w dużej mierze determinuje sam proces binaryzacji. W tym przypadku obraz został zbinaryzowany przez średni kolor. Zwykle binaryzację przeprowadza się za pomocą algorytmu, który adaptacyjnie wybiera próg. Ten algorytm może być wyborem oczekiwań lub trybu. Możesz wybrać największy szczyt histogramu.
Binaryzacja może dać bardzo ciekawe rezultaty podczas pracy z histogramami, także w sytuacji, gdy rozważamy obraz nie w RGB, ale w HSV. Na przykład podziel wybrane kolory na segmenty. Zasada ta może być wykorzystana do budowy zarówno detektora tagów, jak i detektora ludzkiej skóry.
Klasyczne filtrowanie: Fouriera, LPF, HPF
Klasyczne metody filtrowania z radaru i przetwarzania sygnału można z powodzeniem stosować w różnych zadaniach rozpoznawania wzorców. Tradycyjną metodą stosowaną w radarach, która prawie nigdy nie jest stosowana w czystych obrazach, jest transformata Fouriera (a dokładniej FFT). Jednym z nielicznych wyjątków, od których stosowana jest jednowymiarowa transformata Fouriera, jest kompresja obrazu. W przypadku analizy obrazu transformacja jednowymiarowa zwykle nie wystarcza; należy użyć znacznie bardziej wymagającej zasobów transformacji dwuwymiarowej.
Niewiele osób faktycznie to oblicza, zazwyczaj splot obszaru zainteresowania jest dużo szybszy i łatwiejszy z gotowym filtrem wyostrzonym na wysokie (HPF) lub niskie (LPF) częstotliwości. Taka metoda oczywiście nie pozwala na analizę widma, ale w konkretnym zadaniu przetwarzania wideo zwykle nie jest potrzebna analiza, ale wynik.
Najprostsze przykłady filtrów, które implementują podkreślenie niskie częstotliwości (Filtr Gaussa) i górnoprzepustowy (filtr Gabora).
Dla każdego punktu obrazu zaznaczane jest okno i mnożone przez filtr o tej samej wielkości. Wynikiem tego splotu jest nowa wartość punktowa. Podczas implementacji filtra dolnoprzepustowego i górnoprzepustowego uzyskuje się obrazy następującego typu:
Wavelets
Ale co, jeśli użyjemy jakiejś arbitralnej funkcji charakterystycznej dla splotu z sygnałem? Wtedy będzie się nazywał „Transformacja falkowa”. Ta definicja falek nie jest poprawna, ale tradycyjnie rozwinęło się, że w wielu poleceniach analiza falek polega na poszukiwaniu dowolnego wzoru na obrazie przy użyciu splotu z modelem tego wzoru. Istnieje zestaw klasycznych funkcji wykorzystywanych w analizie falkowej. Należą do nich falka Haar, falka Morleta, falka meksykańskiego kapelusza itp. Prymitywy Haara, o których było kilka moich poprzednich artykułów (,), odnoszą się do takich funkcji dla przestrzeni dwuwymiarowej.
Powyżej 4 przykłady klasycznych falek. Falka 3-D Haar, falka 2-D Meyera, falka Mexican Hat, falka Daubechies. Dobry przykład Użycie rozszerzonej interpretacji falek to problem znalezienia rozbłysku w oku, dla którego sama flara jest falką:
Klasyczne falki są zwykle używane do kompresji obrazów lub ich klasyfikacji (opisane poniżej).
Korelacja
Po takiej swobodnej interpretacji falek z mojej strony warto wspomnieć o faktycznej korelacji leżącej u ich podstaw. To niezastąpione narzędzie przy filtrowaniu zdjęć. Klasyczną aplikacją jest korelacja strumienia wideo w celu znalezienia przesunięć lub strumieni optycznych. Najprostszy detektor przesunięcia jest również w pewnym sensie korelatorem różnic. Tam, gdzie obrazy nie korelują, był ruch.
Funkcje filtrujące
Ciekawą klasą filtrów jest filtrowanie funkcji. Są to filtry czysto matematyczne, które pozwalają wykryć w obrazie prostą funkcję matematyczną (linia, parabola, koło). Budowany jest kumulacyjny obraz, w którym dla każdego punktu obrazu źródłowego rysowany jest zestaw funkcji generujących go. Najbardziej klasyczną transformacją jest transformacja Hougha dla linii. W tej transformacji dla każdego punktu (x; y) rysowany jest zbiór punktów (a; b) linii prostej y \u003d ax + b, dla których równość jest prawdą. Uzyskano piękne zdjęcia:
(pierwszy plus to ten, kto pierwszy znajdzie haczyk na obrazku i taką definicję i to wyjaśni, drugi plus temu, kto pierwszy powie to, co tu pokazano)
Transformacja Hougha pozwala znaleźć dowolne funkcje z możliwością parametryzacji. Na przykład koła. Istnieje zmodyfikowana transformacja, która umożliwia wyszukiwanie dowolnych kształtów. Ta przemiana strasznie lubi matematyków. Ale podczas przetwarzania obrazów niestety nie zawsze działa. Bardzo mała prędkość, bardzo duża wrażliwość na jakość binaryzacji. Nawet w idealnych sytuacjach wolałem radzić sobie innymi metodami.
Analogiem transformaty Hougha dla linii jest transformata Radona. Jest obliczany za pomocą FFT, co daje wzrost wydajności w sytuacji, gdy jest dużo punktów. Ponadto można go zastosować do obrazu niezbinaryzowanego.
Filtrowanie konturów
Osobną klasą filtrów jest filtrowanie obramowań i konturów. Kontury są bardzo przydatne, gdy chcemy przejść od pracy z obrazem do pracy z obiektami na tym obrazie. Kiedy obiekt jest wystarczająco złożony, ale dobrze zdefiniowany, często jedynym sposobem pracy z nim jest wybranie jego konturów. Istnieje wiele algorytmów, które rozwiązują problem filtrowania konturów:Najczęściej używany jest Canny, który działa dobrze i którego implementacja jest w OpenCV (Sobel też tam jest, ale na konturach wygląda gorzej).
Inne filtry
Powyżej znajdują się filtry, których modyfikacje pomagają rozwiązać 80-90% problemów. Ale oprócz nich istnieją rzadsze filtry używane w zadaniach lokalnych. Takich filtrów jest kilkadziesiąt, nie wymienię wszystkich. Interesujące są filtry iteracyjne (na przykład aktywny model wyglądu), a także transformacje rypsowe i krzywiznowe, które są stopem klasycznego filtrowania i analizy falkowej w polu transformaty radonowej. Transformacja wiązki działa pięknie na granicy transformacji falkowej i analizy logicznej, umożliwiając podkreślenie konturów:
Ale te transformacje są bardzo specyficzne i dostosowane do rzadkich zadań.
Część 2. Logiczne przetwarzanie wyników filtrowania
Filtrowanie zapewnia zestaw danych odpowiednich do przetwarzania. Ale często nie można po prostu pobrać i wykorzystać tych danych bez ich przetwarzania. W tej sekcji będzie kilka klasycznych metod, które pozwalają przejść od obrazu do właściwości obiektów lub do samych obiektów.Morfologia
Moim zdaniem przejście od filtrowania do logiki to metody morfologii matematycznej (,,). W rzeczywistości są to najprostsze operacje tworzenia i erodowania obrazów binarnych. Te metody pozwalają usunąć szum z obrazu binarnego poprzez zwiększenie lub zmniejszenie istniejących elementów. Istnieją algorytmy konturowania oparte na morfologii matematycznej, ale zwykle używają one pewnego rodzaju algorytmów hybrydowych lub algorytmów w połączeniu.
Analiza konturu
Algorytmy uzyskiwania granic zostały już wspomniane w sekcji dotyczącej filtrowania. Wynikowe granice można łatwo przekształcić w kontury. W przypadku algorytmu Canny'ego dzieje się to automatycznie; w przypadku innych algorytmów wymagana jest dodatkowa binaryzacja. Możesz uzyskać kontur dla algorytmu binarnego, na przykład za pomocą algorytmu chrząszcza.Obrys jest unikalną cechą obiektu. To często umożliwia identyfikację obiektu wzdłuż konturu. Istnieje potężny aparat matematyczny, który pozwala to zrobić. Aparat nazywa się analizą konturu (,).
Szczerze mówiąc, nigdy nie udało mi się zastosować analizy konturu w rzeczywistych problemach. Wymagane są zbyt idealne warunki. Albo nie ma granicy, albo jest za dużo hałasu. Ale jeśli chcesz rozpoznać coś w idealnych warunkach, analiza konturu jest świetną opcją. Działa bardzo szybko, ma piękną matematykę i przejrzystą logikę.
Punkty specjalne
Punkty osobliwe to unikalne cechy obiektu, które umożliwiają skojarzenie obiektu z samym sobą lub z podobnymi klasami obiektów. Sposobów na podkreślenie takich punktów jest kilkadziesiąt. Niektóre metody wyróżniają specjalne punkty w sąsiednich klatkach, niektóre po długim czasie i przy zmianie oświetlenia, inne pozwalają znaleźć specjalne punkty, które pozostają takie nawet po obróceniu obiektu. Zacznijmy od metod, które pozwalają nam znaleźć punkty osobliwe, które nie są tak stabilne, ale są szybko obliczane, a następnie przejdźmy do rosnącej złożoności:Pierwsza klasa. Pojedyncze punkty, które są stabilne przez kilka sekund. Takie punkty służą do prowadzenia obiektu między sąsiednimi klatkami wideo lub do łączenia obrazów z sąsiednich kamer. Punkty te obejmują lokalne maksima obrazu, kąty obrazu (najlepszy z detektorów, być może detektor Harisa), punkty, w których osiągane są maksima dyspersji, określone gradienty itp.
Druga klasa. Specjalne punkty, które są stabilne przy zmianach światła i małych ruchach obiektów. Takie punkty służą przede wszystkim do treningu i późniejszej klasyfikacji typów obiektów. Na przykład klasyfikator pieszych lub klasyfikator twarzy jest produktem systemu zbudowanego wokół takich punktów. Bazą dla takich punktów mogą być niektóre z wcześniej wspomnianych falek. Na przykład prymitywy Haar, wyszukiwanie blasku, wyszukiwanie innych określonych funkcji. Punkty te obejmują punkty znalezione metodą histogramu gradientu kierunkowego (HOG).
Trzecia klasa. Stabilne punkty. Wiem tylko o dwóch metodach dających pełną stabilność oraz o ich modyfikacjach. Są to SURF i SIFT. Pozwalają znaleźć specjalne punkty nawet podczas obracania obrazu. Obliczenie takich punktów trwa dłużej niż innymi metodami, ale wystarczy ograniczony czas... Niestety metody te są opatentowane. Chociaż w Rosji algorytmy nie są opatentowane, używaj ich na rynku krajowym.
Część 3. Szkolenie
Trzecia część opowieści zostanie poświęcona metodom, które nie działają bezpośrednio na obraz, ale pozwalają na podejmowanie decyzji. Są to głównie różne metody uczenia maszynowego i podejmowania decyzji. Niedawno Yandyks opublikował kurs na ten temat na Habr, jest bardzo dobry wybór. Tutaj jest w wersji tekstowej. W celu poważnego przestudiowania tematu gorąco polecam ich obejrzenie. Tutaj spróbuję zarysować kilka podstawowych metod stosowanych w rozpoznawaniu wzorców.W 80% sytuacji istota uczenia się w problemie rozpoznawania jest następująca:
Istnieje zestaw testowy zawierający kilka klas obiektów. Niech będzie to obecność / nieobecność osoby na zdjęciu. Każdy obraz ma zestaw cech, które zostały wyróżnione przez jakąś cechę, czy to Haar, HOG, SURF lub jakiś rodzaj falki. Algorytm uczący się musi zbudować taki model, zgodnie z którym będzie mógł przeanalizować nowy obraz i zdecydować, który z obiektów jest na obrazie.
Jak to jest zrobione? Każdy z obrazów testowych jest punktem w przestrzeni cech. Jego współrzędne to waga każdego elementu obrazu. Niech naszymi znakami będą: „Obecność oczu”, „Obecność nosa”, „Obecność dwóch rąk”, „Obecność uszu” itp. ... Wszystkie te znaki podkreślimy naszymi istniejącymi detektorami, które są trenowane na częściach ciała podobnych do człowiek. Dla osoby w takiej przestrzeni punkt będzie słuszny. W przypadku małpy chodzi o konia. Klasyfikator jest szkolony na próbce przykładów. Ale nie wszystkie zdjęcia pokazywały ręce, inne nie mają oczu, a na trzecim małpa ma ludzki nos z powodu błędu w klasyfikatorze. Wyszkolony klasyfikator ludzki automatycznie dzieli przestrzeń cech w taki sposób, aby powiedzieć: jeśli pierwsza cecha leży w zakresie 0,5
Istnieje wiele klasyfikatorów. Każdy z nich lepiej radzi sobie z jakimś własnym zadaniem. Zadanie doboru klasyfikatora do konkretnego zadania jest pod wieloma względami sztuką. Oto kilka pięknych zdjęć na ten temat.
Prosta obudowa, jednowymiarowa separacja
Przeanalizujmy na przykładzie najprostszy przypadek klasyfikacji, w którym przestrzeń cech jest jednowymiarowa i musimy podzielić 2 klasy. Sytuacja jest bardziej powszechna niż można by sobie wyobrazić: na przykład, gdy trzeba rozróżnić dwa sygnały lub porównać wzór z próbką. Powiedzmy, że mamy próbkę treningową. W tym przypadku uzyskuje się obraz, na którym oś X będzie miarą podobieństwa, a oś Y to liczba zdarzeń z taką miarą. Kiedy obiekt, którego szukasz, wygląda jak sam, otrzymasz lewy Gaussian. Kiedy nie lubisz - dobrze. Wartość X \u003d 0,4 dzieli próbki tak, że błędna decyzja minimalizuje prawdopodobieństwo podjęcia błędnej decyzji. Poszukiwanie takiego separatora jest problemem klasyfikacyjnym.
Mała uwaga. Kryterium minimalizujące błąd nie zawsze będzie optymalne. Następny wykres to wykres rzeczywistego systemu rozpoznawania tęczówki. W przypadku takiego systemu kryterium dobiera się tak, aby zminimalizować prawdopodobieństwo fałszywego wpuszczenia do obiektu osoby nieuprawnionej. Prawdopodobieństwo to nazywa się „błędem pierwszego rodzaju”, „prawdopodobieństwem fałszywego alarmu”, „fałszywie dodatnim”. W literaturze anglojęzycznej „False Access Rate”.
) AdaBusta jest jednym z najpopularniejszych klasyfikatorów. Na przykład zbudowana jest na nim kaskada Haar. Zwykle są używane, gdy potrzebna jest klasyfikacja binarna, ale nic nie stoi na przeszkodzie, aby uczyć dla większej liczby klas.
SVM (,,,) Jeden z najpotężniejszych klasyfikatorów z wieloma implementacjami. Zasadniczo, w przypadku zadań edukacyjnych, z którymi miałem do czynienia, działało podobnie jak adabusta. Uważa się, że jest wystarczająco szybki, ale jego szkolenie jest trudniejsze niż w przypadku Adabusty i wymagany jest wybór odpowiedniego rdzenia.
Istnieją również sieci neuronowe i regresja. Ale aby pokrótce je sklasyfikować i pokazać, czym się różnią, artykuł jest potrzebny znacznie bardziej niż ten.
________________________________________________
Mam nadzieję, że udało mi się dokonać szybkiego przeglądu stosowanych metod bez zagłębiania się w matematykę i opisy. Może to komuś pomoże. Chociaż, oczywiście, artykuł jest niekompletny i nie ma ani słowa o pracy z obrazami stereo, ani o OLS z filtrem Kalmana, ani o adaptacyjnym podejściu bayesowskim.
Jeśli podoba Ci się ten artykuł, postaram się zrobić drugą część z wyborem przykładów rozwiązania istniejących zadań ImageRecognition.
I w końcu
Co czytać1) Kiedyś bardzo podobała mi się książka „Cyfrowe przetwarzanie obrazu” B. Yane'a, która jest napisana prosto i przejrzyście, ale jednocześnie prawie cała matematyka jest przedstawiona. Dobre do zapoznania się z istniejącymi metodami.
2) Klasykami gatunku są R. Gonzalez, R. Woods „Digital Image Processing”. Z jakiegoś powodu było to dla mnie trudniejsze niż pierwsze. Dużo mniej matematyki, ale więcej metod i obrazków.
3) „Przetwarzanie i analiza obrazu w zadaniach widzenia maszynowego” - napisane na podstawie zajęć prowadzonych na jednym z wydziałów PhysTech. Istnieje wiele metod i ich szczegółowe opisy. Ale moim zdaniem książka ma dwie duże wady: książka jest mocno skoncentrowana na dołączonym do niej pakiecie oprogramowania, w książce zbyt często opis prostej metody zamienia się w matematyczną dżunglę, z której trudno jest zrobić strukturalny diagram metody. Ale autorzy stworzyli wygodną stronę internetową, na której prezentowana jest prawie cała zawartość - wiki.technicalvision.ru
4) Z jakiegoś powodu wydaje mi się, że dobrą książką, która porządkuje i łączy obraz świata, który powstaje podczas studiowania Rozpoznawania obrazu i uczenia maszynowego, jest „About Intelligence” Jeffa Hawkinsa. Nie ma metod bezpośrednich, ale trzeba pomyśleć o tym, skąd pochodzą bezpośrednie metody przetwarzania obrazu. Po dokładnym przeczytaniu zdasz sobie sprawę, że znasz już metody ludzkiego mózgu, ale w zadaniach przetwarzania wideo.
Sformułowanie problemu zdeterminowany celem i możliwościami jego realizacji.
Cel, powód. Opracuj program klasyfikacji części prostokątnych na części o wysokiej jakości i wadliwe.
Szanse na realizację zadania określane przez możliwości komputera. Komputer może przetwarzać informacje liczbowe w kolejności algorytmicznej. Aby wykorzystać możliwości komputera, konieczna jest symulacja rozwiązywanego problemu.
Symulacja z wykorzystaniem komputera oznacza przejście od rzeczywistego obiektu (świata) do zakodowanego opisu jego właściwości przy użyciu danych i operacji na nich. Takie przejście z reguły odbywa się w kilku etapach:
Abstrakcja - wybór najistotniejszych cech obiektu z punktu widzenia wykonywanego zadania.
Konieczne jest przeprowadzenie badań, które pozwolą przejść od przedmiotu modelowania do przedmiotu modelowania, odrzucając wszystkie niepotrzebne zgodnie z celem w zadaniu
Czym różni się prostokąt od innych czworoboków?
- Równość przeciwnych stron.
- Równoległość przeciwnych stron.
- Równość przekątnych.
- Wszystkie rogi są proste.
Jakie jest minimum znaków potrzebne do jednoznacznego rozwiązania problemu?
- Równość 2 przeciwległych boków + równość przekątnych.
- Równoległość 2 przeciwległych boków + równość przekątnych.
- Trzy rogi są proste.
Tak więc dzięki abstrakcji otrzymaliśmy werbalny model informacji. Ale nadal jest niezrozumiały dla komputera. Rozumie model matematyczny przedstawiony jako algorytm i zaimplementowany w oprogramowaniu.
Metodyka realizacji zadania.
Rysunek części wysokiej jakości (prostokąt) lub części wadliwej (czworokąt) jest tworzony z segmentów (polecenie LINIA) w systemie graficznym AutoCAD i eksportowany do. Program kntrs.lsp () odczytuje dane segmentu (współrzędne wierzchołków) z pliku DXF i zapisuje je do pliku tekstowego vrtks.txt w kołowej kolejności przechodzenia przez wierzchołki.
Plik tekstowy vrtks.txt można utworzyć ręcznie, pobierając współrzędne wierzchołków bezpośrednio z rysunku.
Opracowany program rct.lsp powinien odczytywać dane z pliku vrtks.txt, analizować je i wyprowadzać zapis zgodności części z wymaganiami (prostokąt lub nie) do pliku result.txt.
Formalizacja cech
Równość długości odcinków (boków lub przekątnych): Długość każdego odcinka jest określana jako przeciwprostokątna prostokąta (zgodnie z twierdzeniem Pitagorasa) poprzez różnicę współrzędnych odcinków:
(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Równoległość linii: K2 \u003d K1gdzie DO - nachylenie w linii prostej K \u003d (Y2-Y1) / (X2-X1)
Jak sformalizować pojęcie „Kąt prosty”? W ramach wykonywanego zadania obecność „kąta prostego” można określić na podstawie znaku prostopadłości segmentów: K2 \u003d -1 / K1gdzie DO To nachylenie prostej. K \u003d (Y-Y0) / (X-X0).
Wyświetlanie modelu na komputerze
Wszelkie informacje są ostatecznie wyświetlane w komputerze za pomocą liczb binarnych (kodów) w modelu wewnątrz maszyny. Wcześniej kodowanie było wykonywane przez programistę. Obecnie większość programów jest napisana w językach algorytmicznych.
