On the effectiveness of various techniques of searching in 3D mesh objects in databases

• Autorzy: Kowalski P.

Warianty tytułu

PL

O efektywności algorytmów wyszukiwania siatek 3D w bazie danych

• Języki publikacji: EN

Abstrakty

EN

The article compares some algorithm for object comparison, that can be used for searching 3D objects in database. There are tested: basic D2, TH, and EGI algorithms. The algorithms use histograms as descriptors of 3D shape. The techniques were tested using cultural heritage objects and objects from Shape Princeton Benchmark. Additional test use the same object represented with different accuracy. The tests give us conclusions about the restricted usefulness of the algorithms and suggest the important parameters for searching in database.

PL

Artykuł prezentuje wyniki trzech serii testów, które przeprowadzono dla sprawdzenia możliwości wykorzystania algorytmów D2, TH i EGI w zastosowaniu do rozpoznawania przestrzennych modeli obiektów dziedzictwa kulturowego w bazie danych takich obiektów. Algorytm D2 opiera się na porównywaniu histogramów długości połączeń między punktami na powierzchni obiektów. Dla każdego obiektu, po jego przeskalowaniu (sprowadzeniu do wspólnych wymiarów) wyznaczamy zadaną liczbę punktów na powierzchni. Punkty są wyznaczane losowo, przy czym zakładamy stałą gęstość rozkładu. Histogram długości tworzony jest dla wszystkich par punktów. W pierwszej serii testów wykorzystano także wariant algorytmu D2, który opiera się na histogramie odległości punktów powierzchniowych od środka ciężkości obiektu. Algorytm TH (ang. thickness histogram) stanowi wariant algorytmu D2 i opiera się na histogramie iloczynów wektorowych odcinków łączących punkty powierzchniowe (wyznaczane jak w przypadku algorytmu D2), oraz normalnych do odpowiadających im powierzchni. W przypadku EGI (ang. Extended Gaussian Image) wyznacza się powierzchnię obiektu odpowiadającą danej orientacji - stanowi to odpowiednik histogramu dla określonej liczby orientacji (wektorów normalnych, wyznaczonych na sferze gaussowskiej). We wszystkich wariantach algorytmów porównanie histogramów wykonywane jest za pomocą metody EMD (ang. Earth Mover's Distance), której zaletą jest odporność na drobne błędy w przeskalowaniu obiektów (dla algorytmów D2 i TH). W przypadku pierwszej serii testów porównano także inne techniki wyznaczania odległości między histogramami (odległość euklidesową, zsumowaną euklidesową, oraz Manhattan) - odległości euklidesowa i zsumowana euklidesowa nie wykazały jednak znacząco lepszych wyników pracy niż EMD, która powinna cechować się większą odpornością na błędy przeskalowania obiektów, odległość zaś Manhattan okazała się miarą znacząco gorszą. W pierwszej serii testów przeanalizowano odległości wyznaczone dla trzech koralików pochodzących z naszyjnika będącego znaleziskiem archeologicznym, pochodzą-cym z kręgu kultury łużyckiej. Testy wykazały, że wszystkie trzy warianty algorytmu D2 pozwalają poprawnie rozpoznać rozpoznawać obiekty, przy czym wykorzystanie odległości od środka ciężkości prowadzi do ograniczeń dokładności (co częściowo rekompensuje niższą złożonością obliczeniową, rosnącą liniowo wraz z liczbą punktów). Wyniki testów algorytmu TH sugerowały możliwość wykorzystania go dla realizacji zadania klasyfikacji. Testy wykazały także, że jakość odpowiedzi (tj. różnica między najgorszymi spasowaniami obiektu ze swoimi kopiami i z obiektami innymi, pozwalająca na określenie wartości progowej dla rozpoznania obiektu) rośnie wraz z liczbą wykorzystanych punktów powierzchniowych. W przypadku algorytmu EGI nie osiągnięto podobnych wyników - wszystkie rodzaje koralików różniły się w podobnym stopniu. Drugą serię testów przeprowadzono na danych pochodzących z bazy Shape Princeton Benchmark, a ich celem było sprawdzenie możliwości wykorzystania algorytmu TH dla podziału bazy danych na klasy. Uzyskane wyniki nie potwierdziły takiej możliwości, choć przeglądy bazy (rys. 8-10) wskazały na pewne rozróżnienie grup obiektów. Należy jednak zauważyć, że ze względu na rozmiar bazy (1815 obiektów) i jej zróżnicowanie (złożoność od 16 do 316498 trójkątów) ograniczono liczbę wykorzystanych punktów do maksymalnie 6000. Analiza możliwości klasyfikacji przy wykorzystaniu technik TH i D2 wymaga więc dalszych prac. Podobne wyniki uzyskano przy pomocy algorytmu EGI, przy czym listy najbardziej podobnych obiektów różniły się w przypadku algorytmu EGI i D2, co może sugerować wykorzystanie złożenia obu algorytmów do stworzenia bardziej złożonego deskryptora. Celem trzeciej serii testów była weryfikacja wpływu jakości reprezentacji siatki na uzyskane wyniki. Testy potwierdziły, że algorytmy D2 i EGI poprawnie radzą sobie z różnicami między różnymi reprezentacjami tego samego obiektu (różniącymi się liczbą trójkątów, a co za tym idzie także cechującymi się pewnym zróżnicowaniem kształtu), podczas gdy algorytm TH okazał się wrażliwy na takie zmiany, co przy testowej liczbie punktów (maksymalnie 12000) czyni go nieprzydatnym dla porównań. Przypuszczalnym powodem takiego zróżnicowania jest większy, w przypadku algorytmu TH, wpływ nachylenia trójkątów powierzchni na uzyskane rezultaty. Artykuł kończy podsumowanie, ukazujące jednocześnie kierunki dalszych potencjalnych prac - analizy technik klasyfikacji przy wykorzystaniu większej liczby punktów dla utworzenia histogramu oraz do testów porównań fragmentów powierzchni z kompletnymi obiektami.

Słowa kluczowe

EN

3D mesh; 3D representation; database; object comparison; cultural heritage

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2011
• Tom: Vol. 23, No. 3-4
• Strony: 245--261
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Kowalski P.

• Institute of Theoretical and Applied Informatics Polish Academy of Science ul. Bałtycka 5, Gliwice, Poland,

Bibliografia

• 1. R. Osada, T. Funkhouser, B. Chazelle, D. Dobkin: Matching 3D models with shape distribution, In Proc. Shape Modeling International. pages 154-166, Genua, may 2001, IEEE Press.
• 2. Seminar on Shape Analysis and Retrieval: http://www.cs.jhu.edu/%7Emisha/Fall04/09-14-04.ppt
• 3. P. Shilane, P. Min, M. Kazhdan, T. Funkhouser: The Princeton Shape Benchmark, Shape Modeling International, Genova, Italy, June 2004.
• 4. P. Papadakis, I. Pratikakis, S. Perantonis, T. Theoharis: Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation, Patter Recognition 40 (2007), pp. 2437-2452.
• 5. A. Baxansky, N. Kiryati: Calculating geometric properties of three-dimensional objects from the spherical harmonic representation, Pattern Recognition 40 (2007), pp. 756-770.
• 6. K.P. Zhu, Y.S. Wong, W.F. Lu, J.Y.H. Fuh: A diffusion wavelet approach for 3-D model matching, Computer-Aided Design 41 (2009), pp. 28-36.
• 7. B. Horn: Extended Gaussian images, Proc. of the IEEE. 72(12):1671-1686, Dec. 1984.
• 8. S. Kang, K. Ikeuchi: Determining 3-D object pose using the complex extended Gaussian image, In CVPR, Pp. 580-585, June 1991.
• 9. D. Saupe, D.V. Vrenic: 3D model retrival with spherical harmonics and moments, In B. Rading and S. Florczyk. ed., DAGM 2001, pp. 392-397, Sept. 2001.
• 10. D.V. Vranic: An improvement of rotatrion invariant 3D shape description based on functions on concentric spheres, In IEEE International Conference on Image Processing (ICIP 2003), vol. 3, pp. 757-760, Sept. 2003.
• 11. M. Kazhdan, T. Funkhouser, S. Rusinkiewicz: Rotation invariant spherical harmonic representation of 3D shape descriptors, In Symposium on Geometry Processing, June 2003.
• 12. Cybervision: google project. http://code.google.com/p/cybervision/
• 13. D.E.R. Clark, J.R. Corney, F. Mill, H.J. Rea, A. Sherlock, N.K. Taylor: Benchmarking shape signatures against human perceptions of geometric similarity, Computer-Aided Design 38 (2006) pp. 1038-1051.
• 14. Y. Liu, J. Pu, H. Zha, W. Luy, Y. Uehara: Thickness histogram and statistical harmonic representation for 3D model retrieval, In; 2nd international symposium on 3D data processing. visualization and transmission, Thessaloniki, Greece: IEEE Computer Society; 2004.
• 15. D. Wang, J. Zhang, H.-S. Wong, Y. Li: 3D Model Retrieval Based on Multi-Shell Extended Gaussian Image, Advances in Visual Information Systems (Lecture Notes in Computer Science), pp. 426-437, vol. 4781/2007.
• 16. M.-H. Mousa, R. Chaine, S. Akkouche, E. Galin: Toward an efficient triangle-based spherical harmonics representation of 3D objects, Computer-Aided Design 28 (2008), pp. 561-575.
• 17. S. B. Kang, K. Ikeuchi: The Complex EGI: A New Representation for 3-D Pose Determination, IEEE PAMI, vol. 15, no, 7, July 1993, pp. 707-721.
• 18. S. Philipp-Foliguet, M. Jordan, L. Najman, J. Cousty: Artwork 3D model database indexing and classification, Pattern Recognition, vol. 44, 2011, pp. 588-597.
• 19.K.P. Horn: Extended gaussian images, Proceedings of IEEE, vol. 72, no. 2, 1984, pp.1671-1686