Üç boyutlu çözüm ağları için K-means kümeleme tabanlı şekil araması

Üç boyutlu çözüm ağları, makine mühendisliği, tıp bilimi ve bilgisayar bilimleri gibi çeşitli alanlarda kullanılmaktadır. Şekil veritabanlarının büyüklüğü nedeniyle şekil koleksiyonlarının araştırılması ve taranması zor olmaktadır. İstenilen modelleri etkin ve sağlam bir şekilde aramak gerekiyor. 3B model araması için birçok yöntem önerilmiştir. Şekil arama yöntemleri üç temel gruba ayrılabilir: Özellik-tabanlı teknikler, grafik-tabanlı teknikler ve görünüm-tanımlı teknikler. 3B şekil eşleştirme 3B şekillerin geometrik ve topolojik özellikleri kullanarak yapılabilir. Böylece, 3B şekillerin özellikleri ölçülerek ve karşılaştırılarak ayırt edilebilir. Özellik-tabanlı teknikler ağırlıklı olarak 3B modellerin topolojisi ve geometrisine odaklanmıştır. Küresel dağılım ile benzerlik tekniği ve sektör / kabuk tabanlı dağılım histogramları, en popüler özellik tabanlı tekniklerdir. Özellik-tabanlı teknikler ağırlıklı olarak modelin geometrisinin sınıflandırılmasına odaklanmaktadır. Fakat genellikle topolojik bilgilere gerekli önemi vermemektedir. Bu yaklaşımlar, topolojik bilgileri nesnenin şekil tanımlayıcısına entegre etmeye odaklanmaktadırlar. Buna karşılık, grafik-tabanlı yaklaşımlar, 3B nesnelerin topolojisini ve geometrisini ortaya çıkarmakta, nesne bileşenleri arasındaki topolojik ilişkilere odaklanmakta ve bu ilişkileri temsil etmek için grafikleri kullanmaktadır. En popüler grafik-tabanlı yöntemler reeb grafikleri ve iskelet-tabanlı tekniklerdir. Görünüm-tabanlı teknikler, daha önce bahsedilen diğer iki teknikten tamamen farklı bir yaklaşım kullanmaktadırlar. Bu yaklaşım üç boyutlu bir modelin iki boyutlu uzayda gösterilmesini temel almaktadır. Bu yaklaşımın arkasındaki temel fikir, iki 3B model benzer olduğunda, aynı bakış açılarından elde edilen görüntülerin de benzer olmasıdır. Bu düşünceden yola çıkarak, birçok araştırmacı 3B şekillerin, görüntü eşleştirme ile karşılaştırılması sorununu azaltma da bu yöntemden faydalanmıştır. Daha önce belirtildiği gibi, üç boyutlu modeller geniş bir alan aralığında yararlıdır. Bu uygulama çeşitliliği, birçok farklı model gösterim formuyla alana özel koleksiyonların oluşmasına yol açar. Bununla birlikte, bu farklı gösterimler her zaman sınıflandırma ve bulup getirme algoritmaları tarafından yorumlanabilen çokgen bir mesh gibi daha genel bir karaktere dönüştürülebilir veya yaklaştırılabilir. Bu algoritmalar genellikle hem modelleri hem de sorguları tanımlamak için sayısal bir gösterime dayanır. 3B şekiller için en yaygın sayısal gösterim, özellik vektörleridir. Bu özellik vektörleri, modelleri ve sorguları çok boyutlu bir alanda noktalar olarak göstermeye izin verir. Böylece, benzer nesneleri aramak, nesneleri doğrudan karşılaştırmak yerine unsur-vektör uzayında bir aramaya indirgenir. Aslında, özellik vektörlerinin kullanımı çoğul ortamların bulunup getirilmesi için standart yaklaşımdır. Genellikle, tanımlayıcı ya da nesnenin imzası olarak da ifade edilen bir özellik vektörü, bir çoğul ortam nesnesinden elde edilen, özellik vektörünü yüksek boyutlu bir uzayda sayısal olarak tanımlayan değerler kümesidir. Herhangi bir 3B şekil tanımlaması yaklaşımının önemli bir amacı, mümkün olan daha düşük boyutlarda bir özellik vektörü üzerindeki maksimum şekil bilgisini korumaktır. Nitekim, bir şeklin bu gibi hesaplamalı olarak bulunması, şekil-tabanlı bir arama sisteminin oluşturulmasında birincil zorluk olarak kabul edilir. Daha önce de belirttiğimiz gibi, 3B şekil tanımlayıcı hesaplaması, şekil-tabanlı arama sistemi için çok önemlidir. Bu olgu, bu konuda geliştirilen çalışmaların çokluğunu açıklıyor. Bununla birlikte, yetkin şekil gösterimi, 3B model bulup getirme sistemleri geliştirilirken üstesinden gelinen tek zorluk değildir. Herhangi bir içerik tabanlı arama sisteminde olduğu gibi, bir 3B şekil araması çözümünün bir diğer önemli kısmı, sorgu ve eşleme süreçleridir. Nesnelerden çıkarılan tanımlayıcılar genellikle çok boyutlu bir uzayda unsur vektörleri olarak temsil edilir. Bu yalnızca 3B modeller için değil, aynı zamanda görüntü veya müzik gibi diğer veri türleri için de geçerlidir. Çok boyutlu uzaylarda endekslenen bilgilerin etkili bir şekilde içerik tabanlı olarak alınması, büyük ölçüde sorgu ve eşleme tekniklerine bağlıdır. Şekil arama motorunda, sorgu adı verilen bir girdi modeli seçilir ve model veritabanındaki modeller arasından sorguya benzer modeller listelenir. Veritabanındaki 3B modellerde direkt olarak şekil arama algoritmasını kullanmak zaman alıcıdır. Bu nedenle, sorgu ve veri kümeleri için tanımlayıcıların hesaplandığı çevrimdışı adım adında bir önişleme aşaması kullanılır. Ardından, sorgu tanımlayıcısı ile veri kümelerinin modelleri için tanımlayıcılar arasındaki karşılaştırma çevrimiçi basamakta yapılır. Arama motoru, önceden hesaplanmış tanımlayıcıları kullanarak sorguya benzer modelleri listeler. Bu yazıda önerilen tanımlayıcı ise farklı model görüntülerine duyarsızdır ve model döndürülürken, çevrilirken veya ölçeklendirildiğinde değişmez. Şekil arama sisteminin amaç ve kapsamına bağlı olarak, bazı şekil tanımlayıcıları diğerlerinden daha iyi performans gösterebilir. Nitekim, her anlamda diğerlerinden daha iyi bir şekil tanımlayıcı yoktur. Bu arama motorları duruma bağlı olarak, bir grup üç boyutlu model için veya arama sisteminin özel ihtiyaçları için en uygun arama algoritması olmaktadır. Bazı durumlarda en önemli husus şekil tanımlayıcısının yeterliliğidir. Bazı durumlarda ise en önemli faktör şekil tanımlama tekniklerinin performansı olabilir. Bir şekil tanımlayıcısının yeterliliği, temsil edebileceği şekil bilgisinin miktarını gösterir. Yeterliliği fazla olan şekil tanımlayıcıları şekle ilişkin daha fazla bilgi depolar. Öte yandan, bir şekil tanımlama tekniğinin performansı, elde edilen özellik vektörünün depolanması için gerekli olan zaman ve depolamak için gerekli olan alan ile ilgilidir. Daha büyük ve daha karmaşık şekil tanımlayıcıları genellikle daha yavaş sınıflandırmaya ve aramaya yol açar. Önceki çalışmalar rijid 3B modellerin edinilmesine odaklanmıştır. Dolayısıyla rijid olmayan şekillerin yeterli ve performanslı bir şekilde nasıl karşılaştırılacağı, içerik tabanlı 3B nesnelerin aranması alanında hala problem olmaktadır. Bildiğimiz gibi, rijid olmayan nesneler çevremizde sıklıkla görülür. Örneğin, bir insan modeli oldukça farklı açılarda ve pozisyonlarda görünebilir ancak geleneksel rijit şekil analiz teknikleri kullanılarak farklı objeler olarak tanımlanabilirler. Şimdiye kadar, bu soruna hitap eden sadece birkaç yöntem geliştirilmiştir. Rijid olmayan modellerin aranması, üzerinde hala daha fazla çalışılması gereken zorlu bir alandır. Rijid olmayan modeller için, tasarlanan tanımlayıcılar farklı pozlara duyarsız olmalıdır. Rijid olmayan model aranması için, bir modeli jeodezik mesafe metriğini "geodesic distance metric" kullanarak kümelere bölen ve daha sonra bu kümeleri kullanarak tanımlayıcıyı hesaplayan yeni bir yöntem önerilmiştir. Mesh segmentasyon, bir iskelet tabanlı K-ortalama kümeleme yöntemi kullanılarak gerçekleştirilir. K-ortalama kümelemesinin zayıf noktası, seçilen başlangıç sınıflandırma noktalarına duyarlılığıdır. Bu sorunu çözmek için, K-ortalama algoritmasının hızını arttırmak için K-en uzak noktalar kümelemesi 3B modelin iskeleti vasıtasıyla hesaplanır. Ek olarak, K-ortalama algoritmasını daha doğru hale getirmek için modelin en uzak iki noktası ilk iki sınıf olarak seçilmiştir. Sonraki sınıflandırma noktalarının seçimi için Greedy bir yaklaşım seçilir. Ayrıca, Euclidean uzaklığı yerine Jeodezik mesafenin uygulanması, iskelet-tabanlı K-ortalama yöntemini farklı açılara ve pozisyonlara duyarsız kılmaktadır. Modelin iskelet tabanlı K-ortalama yaklaşımı ile kümelenmesinden sonra, çevrimdışı bir adımda veritabanındaki tüm modeller için alan tabanlı bir tanımlayıcı oluşturulur. Bu durumda ise kullanılan tanımlayıcı, ölçek ve oryantasyon açısından değişmez. Tanımlayıcı, kümeler için sıralanmış normalleştirilmiş alanı gösteren vektör formundadır. Sonuç olarak, seçilen giriş modeline benzeyen nesneler bulunup getirilir. İki model arasındaki benzerlik oranı iki tanımlayıcı arasındaki Euclidean uzaklığına dayanarak hesaplanır. Önerilen şekil arama algoritmasının doğrulanması için, 56 3B modelden oluşan bir test modeli hazırlandı. Bu modeller Princeton Shape Benchmark ve SHREC'11 Benchmark'tan alınmıştır. Bu çalışmanın deneyleri için kullanılan model veritabanında, insandan hayvanlara mafsallı nesneler bulunmaktadır.