- Tytuł:
-
On the effectiveness of various techniques of searching in 3D mesh objects in databases
O efektywności algorytmów wyszukiwania siatek 3D w bazie danych - Autorzy:
- Kowalski, P.
- Tematy:
-
3D mesh
3D representation
database
object comparison
cultural heritage - Pokaż więcej
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Powiązania:
- https://bibliotekanauki.pl/articles/375738.pdf Link otwiera się w nowym oknie
- Opis:
-
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.
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. - Dostawca treści:
- Biblioteka Nauki
Artykuł