Tez No	İndirme	Tez Künye	Durumu
467100		A K-means clustering-based shape retrieval technique for 3D mesh models / Üç boyutlu çözüm ağları için K-means kümeleme tabanlı şekil araması Yazar:MOHAMMADHASSAN REZAEI Danışman: YRD. DOÇ. DR. ERKAN GÜNPINAR Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Makine Mühendisliği Ana Bilim Dalı / Konstrüksiyon Bilim Dalı Konu:Makine Mühendisliği = Mechanical Engineering Dizin:	Onaylandı Yüksek Lisans İngilizce 2017 71 s.
Üç 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.
3D mesh models are used in various applications in mechanical engineering, medical science and computer science and so on. Due to the large size of shape databases, searching and browsing of the shape collections is a challenging task. There is a need to retrieve desired models effectively and robustly. Many methods have been suggested for this purpose Shape retrieval methods can be divided into three main groups: Feature-based techniques, graph-based techniques and view-based techniques. Feature-based techniques mainly focus on topology and geometry of the 3D models. Global feature distribution based technique and sector/shell-based distribution histograms are the most popular feature-based techniques. Graph-based techniques represent topology of the model by connecting the meaningful parts of the 3D shapes. The most popular graph-based methods are reeb graphs and skeleton-based techniques. View-based techniques utilize completely different approach from other two pre-mentioned techniques. In this approach, two models are similar if they look same from all viewpoints. Researchers mainly focus on finding descriptors, which is suitable for rigid models. Retrieval of non-rigid models is a still challenging field that needs to be studied more. For non-rigid models, descriptors that are designed should be insensitive to different poses. For non-rigid model retrieval, a new method is proposed, which first divides a model into clusters using geodesic distance metric and then computes the descriptor using these clusters. Mesh segmentation is performed using a skeleton-based K-means clustering method. Weak point of K-means clustering is its sensitivity to the selected initial seed points. To solve this problem, K-furthest seeds are calculated by means of 3D model skeleton to increase the speed of the K-means algorithm. Additionally, two furthest points of model are selected as initial two seeds to make K-means algorithm more accurate. For the selection of next seed points, a greedy approach is chosen. Moreover, implementing Geodesic distance instead of Euclidean distance makes skeleton-based K-means method insensitive to different poses. After clustering the model via skeleton-based K-means approach, an area-based descriptor is computed for all models in database in an off-line step. The descriptor used is invariant to scale and orientation. The descriptor is in the vector form, which denotes the sorted normalized area for clusters. Finally, similar objects for the selected input model are retrieved. Similarity rate between two models are computed based on Euclidean distance between two descriptors. For the validation of the proposed retrieval algorithm, we prepared a testing model, which consists of 56 3D models. These models are taken from Princeton shape benchmark and SHREC'11 benchmark. Articulated objects from human to animals exist in the model database that are used for this study's experiments.