5.26. Wyszukiwanie linii i segmentów

Niektóre cechy sceny nie są spójnymi obszarami koloru, lecz zorientowanymi prostymi krawędziami: namalowana linia na podłodze, szew między dwiema powierzchniami, bok wydrukowanego prostokąta, krawędź framugi drzwi. Proszenie detektora plam o ich znalezienie to złe pytanie – krawędź ma szerokość jednego piksela, algorytm plam chce powierzchni-z-kolorem, a odpowiedź wraca pusta lub zaszumiona.

Właściwym detektorem zorientowanych krawędzi jest transformata liniowa Hougha. Moduł image udostępnia ją w dwóch odmianach: find_lines() zwraca linie nieskończone (każda linia rozciąga się przez cały obraz); find_line_segments() zwraca segmenty skończone (każda linia ma punkty końcowe wewnątrz ramki). To, której z nich potrzebuje aplikacja, zależy od tego, czy interesujące krawędzie są ciągłe przez całą ramkę, czy obejmują tylko jej część.

5.26.1. Jak działa transformata Hougha

Oba detektory dzielą tę samą podstawową ideę, więc warto raz ją zrozumieć. Moduł image najpierw uruchamia filtr krawędziowy w stylu Sobela na wejściu, aby ocenić każdy piksel pod kątem prawdopodobieństwa, że leży on na zorientowanej krawędzi. Każdy taki piksel krawędzi następnie głosuje na wszystkie linie, na których mógłby leżeć. Wygrywają linie, które zbiorą najwięcej głosów.

Linia jest parametryzowana w przestrzeni Hougha za pomocą dwóch liczb: theta, kąta linii (0 – 179 stopni) oraz rho, prostopadłej odległości od początku obrazu do linii (ze znakiem, w pikselach). Każda linia, którą zawiera obraz, jest jednym punktem w przestrzeni (theta, rho). Każdy piksel krawędzi na wejściu wnosi jeden głos do każdej kombinacji (theta, rho) zgodnej z jego pozycją – koncepcyjnie krzywą przez przestrzeń Hougha. Tam, gdzie wiele takich krzywych się przecina, wiele pikseli krawędzi zgadza się co do tej samej linii i to przecięcie jest wykryciem.

Detektor zwraca lokalne maksima w przestrzeni Hougha, których sumy głosów przekraczają próg. Każda zwrócona Line niesie obie reprezentacje: x1, y1, x2, y2 dla postaci z punktami końcowymi (przyciętej do granic obrazu w przypadku nieskończonym), theta, rho dla postaci Hougha oraz length i magnitude odpowiednio dla rozmiaru i liczby głosów.

5.26.2. Linie nieskończone

find_lines() uruchamia transformatę Hougha i zwraca najsilniejsze linie, każdą rozciągniętą przez cały obraz:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold to minimalna suma głosów wymagana, aby linia została zaakceptowana. Suma głosów sumuje wielkości krawędzi Sobela każdego współtworzącego piksela, więc większe wartości threshold wymagają dłuższych lub silniejszych krawędzi, aby przejść – co sprawia, że właściwa wartość zależy zarówno od rozdzielczości obrazu (dłuższa linia przy wyższej rozdzielczości gromadzi więcej głosów), jak i od sceny, więc musi być dostrojona do konkretnej aplikacji. Jako przybliżone punkty wyjścia do dostrajania: 1000 dla skromnej linii na czystym obrazie, 500 lub mniej dla słabego kontrastu lub krótkich linii, 2000 lub więcej dla zatłoczonych scen, gdzie fałszywe linie powstają przez skupiska szumu krawędziowego.

theta_margin i rho_margin kontrolują łączenie pobliskich maksimów. Pojedyncza fizyczna krawędź wytwarza mały klaster komórek o wysokiej liczbie głosów wokół swojego rzeczywistego (theta, rho), a detektor zwija każdy klaster do jego szczytu przed zwróceniem. theta_margin=25 (stopni) łączy wszelkie szczyty w obrębie 25 stopni orientacji; rho_margin=25 (pikseli) łączy szczyty w obrębie 25 pikseli odległości. Wartości domyślne są rozsądne; ich podniesienie zwraca mniej, bardziej odrębnych linii, a obniżenie zwraca więcej, czasem zduplikowanych linii.

x_stride i y_stride przechodzą przez piksele krawędzi podczas głosowania, tak samo jak przechodzą przez piksele w find_blobs(). Domyślne wartości 2 i 1 sprawdzają się w typowym przypadku; ich podniesienie przyspiesza wyszukiwanie kosztem rozdzielczości. roi ogranicza wyszukiwanie do obszaru ramki, co zarówno zawęża zwracane linie, jak i zmniejsza nakład pracy.

Każda zwrócona linia jest bezpośrednio rysowalna: obiekt Line przechodzi wprost do draw_line(), która odczytuje z jego początku pola punktów końcowych (x1, y1, x2, y2). l.theta to kąt w stopniach, który jednym porównaniem klasyfikuje linię jako poziomą, pionową lub ukośną. l.magnitude to suma głosów, która sortuje zwrócone linie od najsilniejszej do najsłabszej.

5.26.3. Segmenty linii

find_lines() jest właściwym detektorem dla krawędzi obejmujących całą ramkę, ale wiele rzeczywistych krawędzi – lewy bok wydrukowanego kodu kreskowego, górna krawędź etykiety, widoczny bok linijki – biegnie tylko przez część obrazu. find_line_segments() zwraca segmenty skończone, których punkty końcowe znajdują się wewnątrz ramki:

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Detektor segmentów śledzi bezpośrednio wzdłuż zorientowanych pikseli krawędzi, zamiast głosować w przestrzeni Hougha, a wynikiem jest zbiór krótkich prostych odcinków. merge_distance ustawia maksymalną przerwę w pikselach, którą dwa współliniowe krótkie odcinki mogą obejmować i nadal połączyć się w jeden zwracany segment; max_theta_difference ustawia, ile stopni różnicy orientacji łączący toleruje między sąsiednimi odcinkami. Hojne łączenie (merge_distance=10, max_theta_difference=15) zwraca niewielką liczbę długich segmentów kosztem czasem przerzucania mostów między rzeczywiście odrębnymi krawędziami; ścisłe łączenie (merge_distance=0, max_theta_difference=5) zwraca wiele krótkich segmentów i pozostawia aplikacji uporządkowanie ich w Pythonie.

Obiekty wynikowe są tego samego typu Line co te zwracane przez find_lines(), z tymi samymi właściwościami, więc potok może przetwarzać oba rodzaje wykryć tą samą ścieżką dalszego kodu. Jedyną praktyczną różnicą jest to, że punkty końcowe segmentów są rzeczywistymi końcami linii na obrazie, podczas gdy punkty końcowe linii nieskończonych są tam, gdzie linia przecina granicę obrazu.

5.26.4. Kiedy używać której

Wybór między dwiema metodami sprowadza się do jednego pytania: czy aplikacji zależy na tym, gdzie linia się kończy?

find_lines() jest właściwym narzędziem, gdy odpowiedź brzmi: nie. Robot podążający za linią musi wiedzieć, w którą stronę biegnie linia i gdzie przecina dół ramki; sama linia biegnie aż po horyzont i dalej. Detektor horyzontu chce najsilniejszej zorientowanej krawędzi na obrazie; nie musi wiedzieć, gdzie kończy się horyzont.

find_line_segments() jest właściwym narzędziem, gdy odpowiedź brzmi: tak. Zidentyfikowanie czterech boków wydrukowanego prostokąta wymaga czterech segmentów ze znanymi punktami końcowymi. Śledzenie palca wskazującego na wyświetlacz oznacza podążanie za krótkim segmentem, którego punktami końcowymi są czubek i podstawa palca. Pomiar długości widocznej rysy wymaga rzeczywistego rozciągłości segmentu w pikselach.

Oba detektory dzielą wspólne ograniczenie: potrzebują kontrastu. Filtr krawędziowy Sobela, na którym się opierają, reaguje na gradienty jasności; kolorowa krawędź na tle o równej jasności (czerwona linia na zielonej ścianie o tej samej luminancji) nie wytwarza gradientu ani wykrycia. Gdy ten przypadek pojawia się w praktyce, rozwiązaniem jest wyodrębnienie pojedynczego kanału LAB jako obrazu w skali szarości o właściwym kontraście przed wyszukiwaniem – to_grayscale() z wybranym kanałem b izoluje czerwień na tle zieleni tam, gdzie sam kanał luminancji jest płaski – i przekazanie tego obrazu kanału do detektora linii.