By Rean Neil Luces
Pasowanie wzorców jest ważnym tematem w dziedzinie sztucznej inteligencji (AI), ponieważ jest jednym z podejść do podstawowego problemu przetwarzania obrazów, jakim jest lokalizowanie regionu zainteresowania. Znajduje miejsce, w którym znajduje się dany obiekt na danym obrazie. Ma szeroki wachlarz zastosowań, takich jak wykrywanie obiektów, śledzenie, nadzór, obrazowanie medyczne, i image stitching.
Template dopasowanie również składa się z dwóch głównych elementów: obraz źródłowy i obraz szablonu lub łaty. Obraz źródłowy jest obrazem, w którym spodziewamy się znaleźć dopasowanie do obrazu szablonu, podczas gdy obraz szablonu jest obrazem łaty, który będzie porównywany z podobraziem obrazu źródłowego.
Dwie ogólne klasyfikacje szablonu lub dopasowania obrazu są oparte na szablonie i oparte na cechach. Podejście oparte na szablonach, znane również jako podejście oparte na obszarach, działa bardzo dobrze, gdy szablony nie mają silnych cech z obrazem, ponieważ działają one bezpośrednio na wartości pikseli. Dopasowania są mierzone przy użyciu wartości intensywności zarówno obrazu, jak i szablonu. Z drugiej strony, podejście oparte na cechach jest stosowane, gdy zarówno obraz źródłowy, jak i szablon zawierają więcej zgodności w odniesieniu do cech i punktów kontrolnych. W tym przypadku cechy obejmują punkty, krzywe lub model powierzchni w celu wykonania dopasowania szablonu.
Podejście oparte na szablonach
Podejście oparte na szablonach jest łatwiejsze do wdrożenia niż podejście oparte na cechach. Proste dopasowanie szablonu polega na porównywaniu obrazu szablonu z obrazem źródłowym poprzez jego przesuwanie. Obraz szablonu jest przesuwany o jeden piksel od lewej do prawej lub od góry do dołu, aby umożliwić obliczenie liczbowej miary podobieństwa do fragmentu, na który się nakłada. Oba obrazy są konwertowane na obrazy binarne lub czarno-białe, a następnie stosowane są techniki dopasowywania szablonów, takie jak znormalizowana korelacja krzyżowa, korelacja krzyżowa i suma kwadratów różnic.
Jednym z wyzwań podejścia opartego na szablonach jest niezmienniczość skali. Zmiany w rozmiarze obrazu źródłowego lub obrazu szablonu będą miały wpływ na działanie algorytmu. Prostym sposobem na rozwiązanie tego problemu jest zmiana rozmiaru obrazu szablonu do wielu skal, a następnie porównanie go z obrazem źródłowym. Po zapętleniu wszystkich rozmiarów, weź region z największym współczynnikiem korelacji i użyj go jako „dopasowany” region. Jednakże, niezmienność rotacji jest trudna do rozwiązania za pomocą tego podejścia. W związku z tym Kim, Hae & Araújo, Sidnei (2007) opracował algorytm Ciratefi, aby rozwiązać problem rotacji poprzez ulepszenie algorytmu brute force, który wymaga obracania obrazu szablonu pod każdym kątem. Algorytm Ciratefi jest 400 razy szybszy niż algorytm brute force i uzyskuje takie same wyniki.
Podejście oparte na cechach
Cechy obrazu, takie jak krawędzie i punkty zainteresowania, dostarczają bogatych informacji o zawartości obrazu. Cechy lokalne i ich deskryptory są podstawą wielu algorytmów widzenia komputerowego. Ich zastosowania obejmują rejestrację obrazów, wykrywanie i klasyfikację obiektów, śledzenie i estymację ruchu. Cechy te są specyficzne dla każdego obrazu i dlatego pomagają w identyfikacji pomiędzy obrazami. Cechy obrazu pozostaną nawet w przypadku zmiany rozmiaru i orientacji, więc podejście może okazać się jeszcze bardziej przydatne, jeśli dopasowanie w wyszukiwanym obrazie jest przekształcane w jakiś sposób. To podejście jest również bardziej wydajne w użyciu, jeśli obraz ma dużą rozdzielczość. Przesuwanie obrazu szablonu w dużym obrazie źródłowym po jednym pikselu na raz i powtarzanie tego w różnych skalach będzie kosztowne obliczeniowo.
Pasowanie szablonów oparte na cechach obejmuje cztery główne kroki. Pierwsze dwa kroki to wykrywanie cech i ekstrakcja cech. SIFT (Scale Invariant Feature Transform) i SURF (Speeded Up Robust Feature) są najbardziej przydatne do wykrywania i dopasowywania cech, ponieważ są one niezmienne dla skali, rotacji, translacji, oświetlenia i rozmycia. Po detekcji i ekstrakcji cech, kolejnym krokiem jest dopasowanie cech przy użyciu Fast Library for Approximate Nearest Neighbors (FLANN). Zawiera ona zbiór algorytmów zoptymalizowanych pod kątem szybkiego wyszukiwania najbliższych sąsiadów w dużych zbiorach danych i cechach wielowymiarowych. Spośród dopasowanych cech zebranych przez FLANN matcher, na podstawie testu współczynnika Lowe’a, wybierane są dobre dopasowania. Po odfiltrowaniu punktów cech, kolejnym krokiem jest obliczenie homografii za pomocą algorytmu RANSAC (RANdom SAmple Consensus).
Podejście to nie może być jednak wykorzystane, gdy obrazy mają mniej cech lub różne obiekty mają te same cechy, ponieważ algorytm nie znajdzie wzorca w obrazie źródłowym.