Wydajność OpenCV przy dopasowywaniu szablonów

Question

Próbuję zrobić dopasowanie do szablonu w zasadzie na java. Użyłem prostego algorytmu, aby znaleźć dopasowanie. Oto kod:

minSAD = VALUE_MAX; 
// loop through the search image 
for (int x = 0; x <= S_rows - T_rows; x++) { 
    for (int y = 0; y <= S_cols - T_cols; y++) { 
     SAD = 0.0; 

     // loop through the template image 
     for (int i = 0; i < T_rows; i++) 
      for (int j = 0; j < T_cols; j++) { 

       pixel p_SearchIMG = S[x+i][y+j]; 

       pixel p_TemplateIMG = T[i][j]; 

       SAD += abs(p_SearchIMG.Grey - p_TemplateIMG.Grey); 
      } 
    } 

    // save the best found position 
    if (minSAD > SAD) { 
     minSAD = SAD; 
     // give me VALUE_MAX 
     position.bestRow = x; 
     position.bestCol = y; 
     position.bestSAD = SAD; 
    } 
} 

Ale to bardzo powolne podejście. Przetestowałem 2 obrazy (768 × 1280) i subimage (384 x 640). Trwa to przez wieki. Czy openCV wykonuje szablon dopasowywania znacznie szybciej, czy nie z gotową funkcją cvMatchTemplate()?

Answer 1

Znajdziesz openCV cvMatchTemplate() jest o wiele bardziej szybki niż metoda, którą zaimplementowałeś. To, co stworzyłeś, to metoda porównywania szablonów statystycznych. Jest to najczęstszy i najłatwiejszy do wdrożenia, ale jest bardzo wolny na dużych obrazach. Przyjrzyjmy się podstawowym matematycznym obrazom 768x1280, w którym przechodzisz przez każdy z tych pikseli minus krawędź, ponieważ jest to szablon, który ogranicza (768 - 384) x (1280 - 640), że 384 x 640 = 245 ' 760 operacji, w których przechodzisz przez każdy piksel twojego szablonu (kolejne 245'760 operacji), dlatego zanim dodasz matematykę w swojej pętli, masz już operacje (245'760 x 245'760) 60'397'977'600. Ponad 60 miliardów operacji po to, aby przeglądać Twój obraz To zaskakujące, jak szybkie maszyny mogą to zrobić.

Pamiętaj jednak o jego 245'760 x (245'760 x działach matematycznych), więc jest o wiele więcej operacji.

Teraz cvMatchTemplate() faktycznie używa operacji dopasowania szablonu analizy Fouriera. Działa to poprzez zastosowanie Szybkiej transformaty Fouriera (FFT) na obrazie, w którym sygnały, które składają się na intensywność pikseli, są dzielone na segmenty dla każdej z odpowiednich form fal. Metoda jest trudna do wytłumaczenia, ale obraz przekształca się w reprezentację sygnału liczb zespolonych. Jeśli chcesz dowiedzieć się więcej, wyszukaj hasło na gogle fast fourier transform. Teraz ta sama operacja jest wykonywana na szablonie, a sygnały tworzące szablon są używane do odfiltrowania wszelkich innych sygnałów z twojego obrazu.

W prosty sposób pomija wszystkie funkcje w obrazie, które nie mają tych samych funkcji co szablon. Obraz jest następnie przekształcany z powrotem za pomocą odwrotnej szybkiej transformaty Fouriera w celu uzyskania obrazów, w których wysokie wartości oznaczają dopasowanie, a niskie wartości oznaczają przeciwieństwo. Ten obraz jest często znormalizowany, więc 1 reprezentuje dopasowanie, a zero lub tam oznacza, że ​​obiekt nie znajduje się w pobliżu.

Należy pamiętać, że jeśli obiekt nie znajduje się na obrazie i zostanie znormalizowany, wykryje fałszywe wykrywanie, ponieważ najwyższa obliczona wartość będzie traktowana jako dopasowanie. Mógłbym przejść przez wieki o tym, jak działa ta metoda i jakie są jej zalety lub problemy, ale ...

Powód, dla którego ta metoda jest tak szybka, to: 1) opencv jest wysoce zoptymalizowanym kodem C++. 2) Funkcja fft jest łatwa do obsługi przez procesor, ponieważ większość z nich ma możliwość wykonania tej operacji w sprzęcie. Karty graficzne GPU są zaprojektowane do wykonywania milionów operacji fft w każdej sekundzie, ponieważ te obliczenia są tak samo ważne w wysokiej jakości grafice do gier lub kodowaniu wideo. 3) Ilość wymaganych operacji jest znacznie mniejsza.

W letniej statystycznej metodzie porównywania szablonów jest wolna i trwa wieki, podczas gdy opencv FFT lub cvMatchTemplate() jest szybka i wysoce zoptymalizowana.

Dopasowywanie szablonów statystycznych nie spowoduje błędów, jeśli obiekt nie jest dostępny, podczas gdy opencv FFT może zostać użyty, jeśli nie zostanie podjęta odpowiednia czynność.

Mam nadzieję, że da ci to podstawowe zrozumienie i odpowie na twoje pytanie.

Cheers

Chris

[EDIT]

Aby dodatkowo odpowiedzieć na Twoje pytania:

Hi

cvMatchTemplate może pracować z CCOEFF_NORMED i CCORR_NORMED i SQDIFF_NORMED tym nie- znormalizowana wersja tych. Here pokazuje rodzaj wyników, jakich można się spodziewać i podaje kod, na którym można grać.

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

Te trzy metody są dobrze cytowane i wiele dokumentów są dostępne za pośrednictwem Google scholar. Podałem kilka dokumentów poniżej. Każdy z nich po prostu używa innego równania, aby znaleźć korelację między sygnałami FFT, które tworzą szablon, a sygnałami FFT, które są obecne w obrazie. Współczynnik korelacji daje lepsze wyniki w moim doświadczeniu i jest łatwiejszy do znalezienia odniesień. Suma wartości Squared Difference to kolejna metoda, która może być używana z porównywalnymi wynikami. Mam nadzieję, że niektóre z tych pomocy:

Fast normalized cross correlation for defect detection Du-Ming Tsai; Chien-Ta Lin; Pattern Recognition Letters Volume 24, Issue 15, listopad 2003, strony 2625-2631

Template Matching using Fast Normalised Cross Correlation Kai Briechle; Uwe D. Hanebeck;

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference Friemel, B.H .; Bohs, L.N .; Trahey, G.E .; Sympozjum Ultrasonics, 1995. Proceedings., 1995 IEEE

A Class of Algorithms for Fast Digital Image Registration Barnea, Daniel I .; Silverman, Harvey F .;
Computers, IEEE Transactions on lutego 1972

Często jest preferowane użycie znormalizowanej wersji tych metod, jak wszystko, co równa się 1 jest mecz jednak jeśli obiekt nie jest obecna można dostać fałszywych alarmów. Metoda działa szybko po prostu ze względu na sposób, w jaki jest uruchamiany w języku komputerowym. Zastosowane operacje są idealne dla architektury procesora, co oznacza, że ​​można zakończyć każdą operację w kilku cyklach zegara, zamiast przesuwać pamięć i informacje w ciągu kilku cykli zegara. Procesory rozwiązują problemy FFT od wielu lat i wiem, jak powiedziałem, że do tego jest wbudowany sprzęt. Oparty na sprzęcie jest zawsze szybszy niż oprogramowanie, a metoda statystyczna dopasowania szablonów jest oparta na podstawowym oprogramowaniu.Dobra lektura dla sprzętu można znaleźć tutaj:

Digital signal processor Chociaż strona Wiki odniesienia są warte wyglądać efektywnie jest to sprzęt, który wykonuje obliczenia FFT

A new Approach to Pipeline FFT Processor Shousheng He; Mats Torkelson; Mój ulubiony, ponieważ pokazuje, co dzieje się wewnątrz procesora:

An Efficient Locally Pipelined FFT Processor Liang Yang; Kewei Zhang; Hongxia Liu; Jin Huang; Shitan Huang;

Dokumenty te pokazują, jak skomplikowana jest funkcja FFT po wdrożeniu, jednak metoda ta pozwala na wykonanie operacji w kilku cyklach zegara. To jest powód, dla którego systemy oparte na widzeniu w czasie rzeczywistym wykorzystują układ FPGA (w szczególności procesory projektowe, które można zaprojektować w celu wykonania określonego zadania), ponieważ mogą być projektowane w sposób wyjątkowo równoległy w architekturze, a układanie rur jest łatwiejsze do wdrożenia.

Chociaż muszę wspomnieć, że dla FFT obrazu używasz FFT2, który jest FFT z poziomej równiny i FFT z pionowej równiny, więc nie ma zamieszania, gdy znajdziesz odniesienie do niego. Nie mogę powiedzieć, że mam wiedzę ekspercką na temat wdrażania równań i wdrażania FFT. Próbowałem znaleźć dobre przewodniki, ale znalezienie dobrego przewodnika jest bardzo trudne, ale jeszcze go nie znalazłem (Nie mogę tego zrozumieć najmniej). Któregoś dnia mogę je zrozumieć, ale wiem, że dobrze rozumiem, jak działają i jakich rezultatów można się spodziewać.

Poza tym nie mogę ci więcej pomóc, jeśli chcesz zaimplementować własną wersję lub zrozumieć, jak to działa, czas na trafienie w bibliotekę, ale ostrzegam, że kod opencv jest tak dobrze zoptymalizowany, że będziesz miał trudności z podniesieniem jego wydajność jednak, kto wie, może znaleźć sposób, aby uzyskać lepsze wyniki, wszystkie najlepsze i powodzenia

Chris