Transcript
Polska Akademia Nauk Oddział w Gdańsku Komisja Informatyki Metody Informatyki Stosowanej Nr 1/29 (18) Szczecin 29 Metody Informatyki Stosowanej Kwartalnik Komisji Informatyki Polskiej Akademii Nauk Oddział w Gdańsku Komitet Naukowy: Przewodniczący: prof. dr hab. inż. Henryk Krawczyk, czł. koresp. PAN, Politechnika Gdańska Członkowie: prof. dr hab. inż. Michał Białko, czł. rzecz. PAN, Politechnika Koszalińska prof. dr hab. inż. Ludosław Drelichowski, Uniwersytet Technologiczno-Przyrodniczy w Bydgoszczy prof. dr hab. inż. Janusz Kacprzyk, czł. koresp. PAN, Instytut Badań Systemowych PAN prof. dr hab. Jan Madey, Uniwersytet Warszawski prof. dr hab. inż. Leszek Rutkowski, czł. koresp. PAN, Politechnika Częstochowska prof. dr hab. inż. Piotr Sienkiewicz, Akademia Obrony Narodowej prof. dr inż. Jerzy Sołdek, Politechnika Szczecińska prof. dr hab. inż. Andrzej Straszak, Instytut Badań Systemowych PAN prof. dr hab. Maciej M. Sysło, Uniwersytet Wrocławski Recenzenci współpracujący z redakcją: Marian Adamski, Zbigniew Banaszak, Alexander Barkalov, Włodzimierz Bielecki, Piotr Bubacz, Ryszard Budziński, Henryk Budzisz, Andrzej Czyżewski, Ludosław Drelichowski, Witold Dzwinel, Imed El Frey, Mykhaylo Fedorov, Paweł Forczmański, Dariusz Frejlichowski, Krzysztof Giaro, Larysa Globa, Zbigniew Gmyrek, Janusz Górski, Stanisław Grzegórski, Volodymyr Harbarchuk, Volodymyr Hrytsyk, Wojciech Jędruch, Aleksander Katkow, Przemysław Klęsk, Shinya Kobayashi, Leonid Kompanets, Józef Korbicz, Marcin Korzeń, Georgy Kukharev, Mieczysław Kula, Eugeniusz Kuriata, Emma Kusztina, Małgorzata Łatuszyńska, Wiesław Madej, Oleg Mashkov, Oleg Maslennikow, Karol Myszkowski, Evgeny Ochin, Krzysztof Okarma, Piotr Pechmann, Jerzy Pejaś, Andrzej Pieczyński, Andrzej Piegat, Jacek Pomykała, Orest Popov, Remigiusz Rak, Valeriy Rogoza, Khalid Saeed, Jerzy Sołdek, Boris Sovetov, Marek Stabrowski, Andrzej Stateczny, Janusz Stokłosa, Alexander Ţariov, Leszek Trybus, Zenon Ulman, Anrzej Walczak, Jarosław Wątróbski, Sławomir Wiak, Antoni Wiliński, Waldemar Wolski, Waldemar Wójcik, Oleg Zaikin, Zenon Zwierzewicz Redaktor Naczelny: Antoni Wiliński Sekretarz redakcji: Piotr Czapiewski ISSN Wydawnictwo: Polska Akademia Nauk Oddział w Gdańsku, Komisja Informatyki Adres kontaktowy: ul. Żołnierska 49 p. 14, Szczecin, Druk: Pracownia Poligraficzna Wydziału Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie Nakład 51 egz. Spis treści Dariusz Frejlichowski ANALIZA OGÓLNEGO KSZTAŁTU OBIEKTÓW WYDOBYTYCH Z OBRAZÓW CYFROWYCH ROZPOZNAWANYCH Z UŻYCIEM DESKRYPTORA PDH... 5 Sławomir Gryś PROPOZYCJA METODY MNOŻENIA LICZB ZE ZNAKIEM Wojciech Horzelski ANALIZA ALGORYTMU SEKWENCYJNEGO DLA ZADANIA PAKOWANIA Jerzy Korostil INFORMATION TECHNOLOGY SECURITY ISSUES Krzysztof Kraska ZASTOSOWANIE INTEL VTUNE PERFORMANCE ANALYZER DO BADANIA LOKALNOŚCI DANYCH APLIKACJI RÓWNOLEGŁYCH OPARTYCH NA TWORZENIU NIEZALEŻNYCH WĄTKÓW OBLICZEŃ Georgy Kukharev, Andrzej Tujaka METHOD OF CLONES GENERATION FROM THE DIGITAL IMAGES Remigiusz Olejnik PRZEGLĄD ROZWIĄZAŃ SPRZĘTOWO-PROGRAMOWYCH POZWALAJĄCYCH NA BUDOWĘ BEZPRZEWODOWYCH SIECI O TOPOLOGII KRATOWEJ Marcin Radziewicz GENERACJA RÓWNAŃ BOOLOWSKICH DLA INSTRUKCJI SEKWENCYJNYCH JĘZYKA VHDL Dominik Strzałka, Franciszek Grabowski WYBRANE WŁAŚCIWOŚCI STATYSTYCZNE DYNAMIKI PROCESU SORTOWANIA PRZEZ WSTAWIANIE Piotr S. Sulikowski WSTĘPNE PRZETWARZANIE DANYCH RZECZYWISTYCH NA PRZYKŁADZIE ANALIZY REZYGNACJI Jakub Swacha, Przemysław Skibiński DYNAMIC, SEMI-DYNAMIC AND STATIC WORD-BASED COMPRESSION: A COMPARISON OF EFFECTIVENESS Galina Ţariova, Alexandr Ţariov ASPEKTY ALGORYTMICZNE WYZNACZANIA WSPÓŁCZYNNIKÓW WIELOMIANU REEDA-MULLERA NA PODSTAWIE TRÓJKĄTA PASCALA Grzegorz Ulacha ZASTOSOWANIE ADAPTACYJNEJ PREDYKCJI LINIOWEJ Z PRZEŁĄCZANIEM KONTEKSTÓW DO BEZSTRATNEJ KOMPRESJI OBRAZÓW Tomasz Wierciński USAGE OF C/C++ LANGUAGES WITH OPENMP DIRECTIVES TO EMBEDDED SYSTEMS DESIGN. 139 Tomasz Wiśniewski, Przemysław Korytkowski ANALIZA WŁAŚCIWOŚCI MODELI ANALITYCZNYCH I SYMULACYJNYCH SYSTEMÓW KLASY MONTAŻ NA ZAMÓWIENIE Analiza ogólnego kształtu obiektów wydobytych z obrazów cyfrowych rozpoznawanych z użyciem deskryptora PDH Dariusz Frejlichowski Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki Abstract: The paper presents experimental results of employing the Point Distance Histogram shape descriptor to the problem of finding the most similar general shape to the particular one. The template matching approach is used. However, unlike the typical recognition approach, here it is assumed that the test object is out of the template base. One of the general shapes, e.g. square, triangle, circle, ellipse, star, is indicated as the most similar to the test one. Three experiments were performed, using 5 various shapes. Keywords: general shape analysis, shape descriptor, polar coordinates 1. Wprowadzenie Analiza i rozpoznawanie obiektów znajdujących się na obrazie cyfrowym opiera się zazwyczaj na jednej z cech reprezentujących dany obiekt, takich jak np. kształt. Nie dość, że sam proces lokalizacji i wydobycia obiektu z obrazu jest złożony, to w jego trakcie pojawiają się różnego rodzaju utrudnienia, deformacje i inne problemy znacznie komplikujące rozpoznawanie. Dodatkowo, sam obraz może być w różny sposób zakłócony lub zdeformowany, np. w wyniku utrudnień podczas jego akwizycji, transmisji, itp. Sposób reprezentowania obiektu musi uwzględniać powyższe utrudnienia. W przypadku wspomnianego kształtu jego deskryptor powinien być niezależny od jak największej liczby deformacji. Dotyczy to oczywiście zadania rozpoznawania obiektu, czyli przydzielania go do jednej z predefiniowanych klas. W niniejszym artykule zaprezentowane zostaną wyniki badania analizy kształtu na nieco ogólniejszym poziomie niż w typowym systemie rozpoznawania. Zazwyczaj identyfikacja odbywa się na dużym poziomie szczegółowości, najczęściej w ramach jednej szeroko rozumianej klasy, np. system rozpoznaje litery wydobyte z tablic rejestracyjnych ([1]), kształty erytrocytów ([2]), sylwetki człowieka ([3]), tekst ([4]), kształt dłoni ([5]), samoloty ([6]), znaki firmowe ([7]). Rzadziej spotkać można przydzielanie identyfikowanego obiektu do ogólniej rozumianej klasy, np. dla powyższych przykładów mówilibyśmy ogólnie, że dany obiekt jest literą, komórką, człowiekiem, tekstem pisanym, dłonią, samolotem, znakiem firmowym. Tego typu zadania najczęściej kojarzone są z problem przeszukiwania dużych graficznych baz danych ([8]) lub analizy obrazów na podstawie ich zawartości CBIR, Content Based Image Retrieval ([9]). W niniejszym artykule analiza jest wykonywana na jeszcze wyższym poziomie. Określać ona będzie, do jakiego podstawowego kształtu, np. okręgu, elipsy, kwadratu, krzyża, Metody Informatyki Stosowanej, nr 1/29 (18), s ISSN Polska Akademia Nauk Oddział w Gdańsku, Komisja Informatyki 6 Dariusz Frejlichowski jest najbardziej zbliżony identyfikowany obiekt. Problem ten jest rzadziej spotykany w analizie obiektów w zadaniach rozpoznawania. Może mieć jednak zastosowanie w różnych miejscach, zazwyczaj jako wstępny etap przed późniejszą dokładniejszą analizą, mający na przykład na celu odrzucenie obiektów, co do których nie ma wątpliwości, że nie należą do zbioru obiektów poszukiwanych. Rysunek 1. Ilustracja rozpatrywanego problemu: do jakiego ogólnego kształtu najbardziej zbliżony jest rozpoznawany obiekt? Do ogólnej analizy kształtów wykorzystany zostanie deskryptor PDH (Point Distance Histogram). Algorytm ten został zaproponowany w [1]. Jest połączeniem dwóch powszechnie stosowanych w przetwarzaniu i rozpoznawaniu obrazów rozwiązań: przekształcenia do układu biegunowego oraz histogramu. Najważniejszą jego cechą dla rozpatrywanego problemu jest zdolność analizy kształtów na bardzo ogólnym poziomie. Pozostała część artykułu jest zorganizowana następująco. W następnym rozdziale opisany zostanie algorytm konstrukcji deskryptora PDH. W kolejnym zaprezentowane zostaną wyniki eksperymentów, badających możliwość wskazywania ogólnych kształtów podobnych do zadanego. Ostatni rozdział podsumuje niniejszą publikację. 2. Opis algorytmu PDH Deskryptor PDH wyznaczany jest dla konturowej reprezentacji kształtu. Dlatego przed jego obliczeniem, jeżeli pracujemy na obiektach wypełnionych, musimy najpierw wydobyć kontur zewnętrzny. Praca z reprezentacją konturową kształtu jest zazwyczaj znacznie szybsza niż w przypadku obiektu wypełnionego. Jest to jedna z zalet deskryptora PDH w porównaniu z innymi podobnymi rozwiązaniami: DH Distance Histogram ([11]) oraz PH Polar Histogram ([12]), które pracują na kształcie wypełnionym. Najważniejsze cechy deskryptora PDH to: niezależność od obrotu i problemu wyznaczania punktu startowego, dzięki zastosowaniu histogramu, niezależność od skalowania, dzięki normalizacji uzyskanej reprezentacji, niezależność od przesunięcia w płaszczyźnie obrazu, dzięki obliczaniu współrzędnych biegunowych względem określonego punktu, możliwość arbitralnego, dostosowanego do badanego problemu, wyboru punktu, względem którego dokonywana jest transformacja. Najczęściej stosowanym punktem, względem którego obliczamy transformację do układu biegunowego jest centroid. Taki punkt będzie stosowany tutaj. Zgodnie z założeniami deskryptora PDH ([1]) nazwę sposobu wyznaczania omawianego punktu należy umieścić w nazwie końcowego deskryptora. Dlatego też opisywany poniżej algorytm możemy określić jako centroid-pdh. Pierwszym etapem będzie więc wyznaczenie centroidu ([1]): 1 1 O ( O, O ) ( x, y ), n n x y i i n i1 n i1 (1) Analiza ogólnego kształtu obiektów wydobytych z obrazów cyfrowych 7 gdzie: n liczba punktów w konturze, x i, y i współrzędne kartezjańskie i-tego punktu w konturze. Kolejnym krokiem jest obliczenie współrzędnych biegunowych z uwzględnieniem obliczonego punktu O. Współrzędne zostaną zapisane w wektorach: Θ i dla kątów i Ρ i dla promieni ([1]): x O 2 y O 2, (2) i i x i y yi Oy i a tan, xi Ox (3) Wartości w wektorze Θ i zaokrąglamy do najbliższych całkowitych ([1]): i, gdy i i.5 i, i, gdy i i.5 (4) Następnie porządkujemy wartości w wektorach Θ i i Ρ i, zgodnie z rosnącymi wartościami wektora Θ i. Uzyskane nowe wektory oznaczamy jako Θ j, Ρ j. Dokonujemy selekcji elementów w wektorze Θ j w ten sposób, że w przypadku równych wartości pozostawiamy tylko tą z największą odpowiadającą jej wartością w wektorze Ρ j. W rezultacie otrzymujemy wektor, który zawiera maksymalnie 36 elementów (po jednym dla każdej całkowitej wartości kąta w stopniach). Uzyskany wektor oznaczamy jako Ρ k, gdzie k = 1,2,...,m i m (mniejsze lub równe 36) oznacza ilość elementów w wektorze. Do dalszej pracy potrzebny jest jedynie wektor promieni Ρ k. Następnym krokiem jest normalizacja składników wektora Ρ k względem największej wartości ([1]): k M max k, k. (5) k M Znormalizowane wartości przypisujemy do poszczególnych binów w histogramie (ρ k do l k ) ([1]): l k r, if k 1 rk, if k 1, (6) gdzie r oznacza założoną z góry liczbę składników histogramu. Na koniec należy znormalizować wartości w histogramie względem największej spośród nich ([1]): lk S max lk, lk. (7) k S Ostatecznie, histogram reprezentujący nasz kształt możemy zapisać formalnie jako funkcję h(l k ) ([1]): m bkl hl k,, (8) k 1 k 8 Dariusz Frejlichowski gdzie ([1]): 1, if k lk bkl (, k )., if k lk (9) Do porównywania uzyskanych reprezentacji wybrano miarę L 2 ([13]): L h, h h( i) h ( i) 2, (1) i h 1, h 2 dwie porównywane reprezentacje PDH, i = 1... r. 3. Rezultaty eksperymentów W celu eksperymentalnego zbadania omawianego w artykule problemu przygotowano bazę pięćdziesięciu różnego rodzaju obiektów, zapisanych w postaci obrazów binarnych. Stworzono kilka klas, gdzie najpierw skupiono się na najbardziej podstawowych kształtach, takich jak: koło, kwadrat, prostokąt, trójkąt itp., a następnie na coraz bardziej szczegółowych i skomplikowanych obiektach. Wykorzystane w eksperymentach obiekty przedstawione zostały na rys.2. Możemy na nim także zauważyć podział na podstawowe grupy obiektów, ze względu na ich stopień skomplikowania oraz kategoryzację. Rysunek 2. Kształty wykorzystane w eksperymentach, podzielone na 8 podstawowych grup Z użyciem opisanych powyżej obiektów wykonano trzy różne eksperymenty. Niestety nie było możliwości użycia miarodajnego sposobu zweryfikowania skuteczności badanej metody, ponieważ nie mieliśmy tu do czynienia z klasycznym problemem rozpoznawania, gdzie rozpoznawany obiekt należy prawdopodobnie do jednej z klas w bazie. W omawianych eksperymentach wskazywano bowiem obiekt bazowy najbardziej podobny do zadanego, ale nie należący na pewno do tej samej klasy. Dlatego, w kolejnych podrozdziałach obrazowo zostaną przedstawione wskazane kształty bazowe dla każdego obiektu testowego. Za każdym razem zaprezentowany zostanie zastosowany podział na dane bazowe i testowe. Analiza ogólnego kształtu obiektów wydobytych z obrazów cyfrowych Eksperyment z małą liczbą obiektów bazowych W pierwszym eksperymencie zastosowano znacznie zredukowaną liczbę obiektów wzorcowych wykorzystano zaledwie dziesięć najbardziej ogólnych kształtów. Natomiast pozostałe czterdzieści kształtów było użyte w charakterze obiektów testowych. Ze względu na małą liczbę tych pierwszych, w eksperymencie wybierano tylko trzy najbliższe w sensie miary dopasowania obiekty w bazie. Podział obiektów na dwie grupy ilustruje rys. 3. Natomiast wyniki przedstawiono na rys.4. Rysunek 3. Podział obiektów w pierwszym eksperymencie na 1 bazowych i 4 testowych Rysunek 4. Wyniki pierwszego eksperymentu po trzy najbliższe wskazane obiekty wzorcowe 1 Dariusz Frejlichowski 3.2. Eksperyment z większą bazą wzorców W drugim eksperymencie przyjęto większą liczbę obiektów bazowych, dzięki czemu mogły one być bardziej zróżnicowane. Tym razem w bazie wzorców znalazło się dwadzieścia kształtów, natomiast do testów użyto trzydziestu. Ponieważ obiektów bazowych było więcej, sensowne było wskazanie większej liczby wybranych na podstawie miary podobieństwa wzorców w trakcie eksperymentu tym razem było to pięć obiektów. Podział obiektów na bazowe i testowe ilustruje rys. 5. Natomiast wyniki przedstawiono graficznie na rys. 6. Rysunek 5. Podział obiektów w drugim eksperymencie na 2 bazowych i 3 testowych 3.3. Porównanie wszystkich obiektów Ostatni test porównywał wszystkie obiekty ze wszystkimi. Ponieważ oczywistym jest, że jako pierwszy (najbliższy) wskazywany był obiekt wzorcowy odpowiadający testowemu, nie brano go pod uwagę. Można więc uznać, że w każdym pojedynczym teście mieliśmy do czynienia z jednym obiektem testowym i czterdziestoma dziewięcioma wzorcami. Tym razem warto było zaprezentować więcej wybieranych obiektów, by sprawdzić które z nich są na bazie algorytmu PDH najbardziej podobne do badanego. Wybierano więc dziesięć wzorców. Wyniki przedstawiono na rys. 7. Analiza ogólnego kształtu obiektów wydobytych z obrazów cyfrowych 11 Rysunek 6. Wyniki drugiego eksperymentu po pięć najbliższych wskazanych obiektów wzorcowych 4. Podsumowanie i wnioski W artykule zaprezentowano problem znajdowania ogólnego kształtu (np. kwadrat, koło, trójkąt) najbardziej podobnego do zadanego. Wyróżnia się on innym spojrzeniem na problem rozpoznawania kształtów. Dotąd zakładaliśmy poszukiwanie obiektu bazowego należącego do tej samej klasy co rozpoznawany. Jeżeli dla określonego obiektu nie udało się znaleźć odpowiedniego wzorca (np. gdy miara podobieństwa była zbyt niska) uznawaliśmy to za porażkę (wyjątkiem była sytuacja poprawnego odrzucenia wyników rozpoznawania, 12 Dariusz Frejlichowski gdy odpowiedniej klasy po prostu nie ma w bazie). Tym razem z góry zakładamy, że badanego obiektu nie ma w bazie, a szukamy takiego wzorca, który jest do niego najbardziej podobny. Dzięki temu możemy określić jak bardzo okrągły czy kwadratowy jest dany kształt. Problem ten znaleźć może zastosowanie w wielu różnych dziedzinach, szczególnie na etapie wstępnej analizy kształtu, gdy najpierw chcemy go przydzielić do pewnej większej klasy, a dopiero potem w jej ramach szczegółowo badać. Rysunek 7. Wyniki trzeciego eksperymentu dziesięć najbliższych obiektów do zadanego (poza nim) spośród wszystkich obiektów testowych W ramach wstępnych badań, zaprezentowanych w artykule, przeprowadzono trzy testy. W pierwszym zastosowano znacznie zredukowaną bazę wzorców. Wykorzystano tylko 1 obiektów bazowych (prostokąt, kwadrat, trapez, pięciokąt, sześciokąt, trójkąt, koło, elipsa, krzyż, gwiazda), natomiast pozostałe obiekty badawcze posłużyły jako dane testowe. Wyniki zaprezentowano na rys. 4. W drugim eksperymencie użyto bazy złożonej z 2 obiektów, a jako dane testowe zastosowano 3 kształtów. Rezultaty możemy zobaczyć na rys. 6. Wreszcie, w ostatnim eksperymencie porównywano dany kształt z wszystkimi pozostałymi (rys. 7). Wyniki należy uznać za interesujące, ponieważ w wielu przypadkach można zauważyć, że dany kształt faktycznie jest podobny do wskazanego jako najbliższy wzorca. Analiza ogólnego kształtu obiektów wydobytych z obrazów cyfrowych 13 W wielu przypadkach kolejne wskazania (z malejącymi wynikami podobieństwa) również należy uznać za zgodne z oczekiwaniami sześciokąt jest najbardziej podobny do ośmiokąta, ale w następnej kolejności do okręgu; pionowa strzałka jest ogólnie rzecz biorąc podobna do podłużnych kształtów, itd. Do badań wykorzystano deskryptor PDH, jako metodę skutecznie wcześniej wykorzystywaną do analizy kształtu, m.in. erytrocytów i znaków firmowych. W dalszych pracach przewiduje się użycie większej liczby różnych metod, w celu porównania ich skuteczności i wskazania najlepszej w opisywanym problemie. Większy nacisk będzie położony na deskryptory kształtu wypełnionego. Zauważono bowiem w trakcie pracy z reprezentacją konturową, że w niektórych przypadkach niesie ona mniej informacji. Bibliografia [1] Frejlichowski D. License Plate Recognition with Significantly Distorted Characters, Polish Journal of Environmental Studies, vol. 15, no. 4C, 26, pp [2] Luengo-Oroz M. A., Angulo J., Flandrin G., Klossa J. Mathematical Morphology in Polar-Logarithmic Coordinates. Application to Erythrocyte Shape Analysis. LNCS, vol. 3523, 25, pp [3] Yasser E., Maher A., Wegdan A., Siu-Cheung C. Shape representation and description using the Hilbert curve, Pattern Recognition Letters, vol. 3, Iss. 4, 29, pp [4] Al-Muhtaseb H. A., Mahmoud S. A., Qahwaji R. S. Recognition of off-line printed Arabic text using Hidden Markov Models, Signal Processing vol. 88, iss. 12, 28, pp [5] Ramamoorthy A., Vaswani N., Chaudhury S., Banerjee S. Recognition of dynamic hand gestures, Pattern Recognition vol. 36, iss. 9, 23, pp [6] Xu D., Xu W. Description and recognition of object contours using arc length and tangent orientation, Pattern Recognition Letters vol. 26, iss. 7, 25, pp [7] Wei C.-H. L., Yue C. W.-Y., Li C.-T. Trademark image retrieval using synthetic features for describing global shape and interior structure, Pattern Recognition vol. 42, iss. 3, 29, pp [8] Frejlichowski D. Przeszukiwanie graficznych baz danych - wybrane problemy i możliwości, Problemy Społeczeństwa Informacyjnego, 27, ss [9] Yadav R. B., Nishchal N. K., Gupta A. K., Rastogi V. K. Retrieval and classification of shape-based objects using Fourier, generic Fourier, and wavelet-fourier descriptors technique: A comparative study, Optics and Lasers in Engineering vol. 45, iss. 6, 27, pp [1] Frejlichowski D. Shape Representation Using Point Distance Histogram, Polish Journal of Environmental Studies, vol. 16, no. 4A, 27, pp [11] Saykol E., Gudukbay U., Ulusoy O. A histogram-based approach for object-based query-by-shape-and-color in image and video databases, Image and Vision Computing, vol. 23, 25, pp [12] Suau P. Robust artificial landmark recognition using polar histograms, Lecture Notes in Artificial Intelligence, vol. 388: 12th Portuguese Conference on Artificial Intelligence, EPIA 25, pp [13] Mikłasz M., Aleksiun P., Rytwiński T., Sinkiewicz P. Image Recognition Using the Histogram Analyser, Computing, Multimedia and Intelligent Techniques, vol.1 no.1, 25, pp Propozycja me
