Algorithms for 3D isometric shape correspondence

Abstract

Sayısal dünyada, aralarında herhangi bir karşılaştırma, aktarım, veya analiz yapabilmek için ilişkilendirilmesi gereken çok sayıda nesne modeli vardır. Şekil eşleme algoritmaları, buprobleme çözüm olarak verili iki nesne modeli arasında benzer veya anlamsal olarak denk yüzey noktalarını eşleştirmeyi hedeflerler.Bu çalışmada anlamsal olarak yakın ve yüzeyleri tamamen veya kısmi olarak örtüşen iki 3B şeklin öznitelik noktaları veya tüm noktaları arasında eşleştirme hesaplama problemineodaklanıyoruz. Bu örtüşmenin izometrik, yani uzaklık-koruyan, deformasyonlara ve ölçeklemeye karşı değişimsiz olduğunu varsayıyoruz. Bir başka deyişle, bizim geliştirdiğimizizometrik şekil eşleme algoritmaları şekil eşleme probleminin, şekiller arasındaki benzerlik miktarı, örtüşmenin kısmi ya da tam olması, istenilen eşlemenin çözünürlüğü gibi çeşitlietkenlere bağlı olarak ayrışan birçok farklı durumun üstesinden gelirler.Verilen iki şekil arasında çoğu zaman tatmin edici 3B eşlemeler bulabilen yöntemler olsa da bu yöntemlerin yüksek hesap yükü, hem kısmi hem yoğun eşleme yapamama, yaklaşıklık ve gömme hataları, simetrik parçaların karıştırılması gibi çeşitli sorunları vardır. Mevcut yöntemler şekil eşleme problemi için sağlam bir temel ve iyi bir başlangıç noktası oluştururken, bu çalışmada, verilen senaryoya göre tasarlanan yeni çözümler bu temel problemin ele alınmasında belirgin gelişmeler ve katkılar sağlamaktadır.3B şekil eşleme problemini tam ve kısmi eşleme olarak iki ana grupta inceliyoruz, ve ilk grubu çıktı çözünürlüğüne göre kaba ve yoğun eşlemeler olarak kendi içinde ikiye ayırıyoruz.Kaba çözünürlükteki tam eşleme problemi için, eşit uzaklıklarla ayrılan öznitelik noktalarını iki şekil yüzeyi üzerinden ortaklaşa örnekledikten sonra, problemi kaynak ve hedefşekillerdeki örnekler arasında olası tüm gönderimler üzerinden tanımlanan bir kombinatoryal eniyileme olarak formule ediyoruz ve bunu, olasılıksal bir yaklaşımla EM algoritmasi kullanarak çözebileceğimiz bir olasılıksal çatı içindeki log-olabilirlik enbüyütme problemine dönüştürüyoruz. Bu yöntem yüksek hesap yükü nedeniyle ancak kaba çözünürlükte görece az sayıda nokta arasında eşleme yapabilir. Tez çalışmasının bir sonraki aşamasında, şekil modellerindeki bütün noktalar arasında yoğun eşleme yapabilen hızlı, kabadan-inceye (çoklu çözünürlüklü), ve simetrik flip problemini de dikkate alan yeni bir algoritma tasarlıyoruz. Ölçek-değişimsiz ölçütümüz üzerine dayalı şekil ölçek düzgeleme yöntemimiz, diğer yandan, kısmi eşleme probleminin özel ve kısıtlı bir halinin üstesinden gelirken, diz-oyla-ve-birleştir (RAVAC) algoritmamız en genel kısmi eşleme durumunu ele alır. Bu iki yöntem de hem kısmi hem yoğun eşlemeler üretir.Bu çalışmada geliştirdiğimiz bütün yöntemleri, gerçek ve sentetik veriye dayalı çeşitli 3B şekil vertabanları üzerinde, literatürde mevcut diğer yöntemlerle karşılaştırmalı olaraksınıyoruz.

There are many pairs of objects in the digital world that need to be related before performing any comparison, transfer, or analysis in between. The shape correspondence algorithms essentially address this problem by taking two shapes as input with the aim of finding a mapping that couples similar or semantically equivalent surface points of the given shapes.We focus on computing correspondences between some featured or all present points of two semantically similar 3D shapes whose surfaces overlap completely or partially up to isometric, i.e., distance-preserving, deformations and scaling. Differently put, our isometric shape correspondence algorithms handle several different cases for the shape correspondence problem that can be differentiated based on how similar the shape pairs are, whether they are partially overlapped, the resolution of the desired mapping, etc.Although there exist methods that can, in most cases, satisfactorily establish 3D correspondences between two given shapes, these methods commonly suffer from certain drawbacks such as high computational load, incapability of establishing a correspondence which is partial and dense at the same time, approximation and embedding errors, and confusion of symmetricalparts of the shapes. While the existing methods constitute a solid foundation and a good starting point for the shape correspondence problem, our novel solutions designed for a given scenario achieve significant improvements as well as contributions.We specifically explore the 3D shape correspondence problem under two categories as complete and partial correspondences where the former is categorized further according to the output resolution as coarse and dense correspondences. For complete correspondence at coarse resolution, after jointly sampling evenly-spaced feature vertices on shapes, we formulate the problem as combinatorial optimization over the domain of all possible mappings between source and target features, which then reduces within a probabilistic framework to a log-likelihood maximization problem that we solve via EM (Expectation Maximization) algorithm. Due to computational limitations of this approach, we design a fast coarse-to-fine algorithm to achieve dense correspondence between all vertices of complete models with specific care on the symmetric flip issue. Our scale normalization method based on a novel scale-invariant isometric distortion measure, on the other hand, handles a particular and rather restricted setting of partial matching whereas our rank-and-vote-and-combine (RAVAC) algorithm deals with the most general matching setting, where both two solutions produce correspondences that are partial and dense at the same time.In comparison with many state-of-the-art methods, our algorithms are tested by a variety of two-manifold meshes representing 3D shape models based on real and synthetic data.