Mam taki problem. Chciałbym w obrazie (wielu obrazach) wydajnie znaleŹć pewien wzorzec. Jak najszybciej w obrazie znaleŹĆ np. biały punkt (mogą występować bardziej złożone wzorce) i wyznaczyc jego położenie( może byc mniejwiecej ) ?
0
0
Zainteresuj się wielorozdzielczościową reprezentacją obrazu. Konkretniej to piramidy Gaussowskie.
0
bardzo by mi się przydała taka funkcja w delphi
odnajdowanie obrazka w obrazku i zwrócenie pozycji
Z góry dziękuje
0
Ale czego Ty od nas oczekujesz?
0
To ją napisz ;-)
0
no właśnie chodzi o to że napisałem - porównuje wzorzec z pixelami całej bitmapy pixel po pixelu i działa to strasznie wolno - a na scanline się nie znam - tzn nie potrafię tego użyć = dodam że wzorzec to wycinek tej oryginalnej bitmapy i nie chodzi o szukanie podobieństwa tylko konkretnego miejsca
Nie mam pomysłów - może któremuś z szanownych grupowiczów chodzi coś po głowie i chciałby się podzielić?
0
Masz IMO conajmniej 2 drogi. O jednej już pisałem (piramidy, ogólnie reprezentacje wielorozdzielczościowe - zjedziesz do niskich czasów). Rozumiem, że nie wchodzi w grę.
Popatrzmy nieco inaczej.
Naiwna metoda wygląda tak:
Dla każdego piksela z obrazu
Dla każdego piksela z wzorca porównaj go z odpowiednio przesuniętym pikselem z obrazu.
Jest to wolne, ale można łatwo przyspieszyć w średnim przypadku (patrz algorytmy tekstowe). Postaram się to opisać (mam nadzieję, że wyjdzie ;-P).
Niech wzorzec to będzie liczba. Załóżmy, że jest to obraz 10x10 (może być dowolny). Wtedy jest 100 pikseli. Każdy ma 3 składowe, czyli 300 liczb. Każda z zakreso 0..255.
Potraktuj to jako zapis liczby w systemie o podstawie 256 ;-) Możesz obliczyć tę liczbę (oczywiście modulo jakaś rozsądnie duża liczba pierwsza). W ten sposób otrzymujesz jakąś liczbę (generalnie dużą - trzymaj np. w long long). Obliczasz np. tak:
suma=0
for x - kolejne liczba
suma = (255 * suma + x) % 255
Dobra po co ten cyrk? Teraz masz liczbę, która reprezentuje twój obraz (oczywiście funkcja nie jest różnowartościowa - taka liczba reprezentuje wiele obrazów).
Teraz robisz tak:
Dla każdego piksela obrazu wylicz odpowiednią liczbę tak samo. Ta odpowiednia liczba to liczba odpowiadająca kawałkowi obrazu, w którym potencjalnie znajduje się wzorzec.
Jeżeli liczby są takie same to porównaj piksel po pikselu. Jeżeli jest to samo to masz wzorzec.
Gdzie jest przyspieszenie?
Nie ma.
Ale będzie. Chodzi o to, że liczbę liczy się bardzo szybko. Jeżeli masz już policzoną dla jakiegoś kawałka, to aby policzyć dla następnego (który jest np. o piksel w prawo) wystarczy odjąć skrajnie lewą kolumnę i dodać nową prawą ;-D.
Jak ktoś coś z tego rozumie to brawo!! (trochę źle się czują, więc może być mało zrozumiałe).
Dobra. Znalazłem nieco lepszy opis niż mój :-)
http://pl.wikipedia.org/wiki/Algorytm_Karpa-Rabina
0
dziękuje za odpowiedź i zainteresowanie.
w sieci nie znalazłem żadnej próby użycia algorytmu Karpa Rabina do grafik :( a sam sobie nie poradzę - sądząć po nieudanych (moich) próbach implementacji tego.
0
Jest tak późno że nie chce mi się przerabiać kodu dla C - http://pastebin.4programmers.net/2935
Program w 125ms znajduje ikonkę gadulca z tray w bitmapie 1280x768, a szuka zwykłymi pętlami.
GetPixel czyta bezpośrednio z pamięci.
Ciepłe słowa na paypal [email protected] :)
0
Ludzie, jak dajecie jakiś kod na pastebin, który potem użyjecie na forum to ustawcie wygasanie:nigdy, bo potem za dwa dni już nikt go nie zobaczy.
Tak jak tutaj: http://pastebin.4programmers.net/2937
0
Ciekawe co się stało z pytaniodawcą? Czy mój kod zrobił coś złego, czy waćpan ma Problem z translacją?
0
nie złego nie :) - nie użyłem go - bo nie zabrałem się za translację - ale ...
w końcu sobie poradziłem - na moim kompie (2.6 sempron) porównywanie/
szukanie 145 wzorców z bitmapą 1016/760 wynosiło dobre kilka min,
po zastosowaniu pixel[] z gr32 wynosiło już 30sek, a w połączeniu z
konwersją bitmap naplik tekstowy i wpierwej szukaniu pierwszej linii
tekstu i wykluczanie niepasujących funkcją pos(..) (zaraz przed
detekcją samego obrazka) wynosi już ... 5-9 sek - o to mi chodziło