Yerel öznitelikler kullanarak görüntü indeksleme ve eşleme
Image indexing and matching using local features
Yazar: ONUR ÇALIKUŞ
Danışman: PROF. DR. BİLGE GÜNSEL KALYONCU
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Haberleşme Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Bu tez çalışmasında, yüksek başarım oranına sahip ve hesaplama karmaşıklığı düşük bir mobil görüntü arama, eşleme ve getirme sistemi geliştirilmesi amaçlanmaktadır. Bu amaç doğrultusunda çeşitli görüntü getirme ve eşleme metotları değerlendirilmiş ve farklı metodolojilerin farklı koşullar altındaki başarımını belirlemek için bu metotların performansları karşılaştırılmış ve yeni bir arama eşleme yöntemi önerilmiştir. 
Görüntü öznitelikleri kullanılarak büyük ölçekli görüntü getirme, özellikle görüntü arama olmak üzere bir çok yeni gelişen uygulamalar sayesinde ilgi çekici araştırma alanlarından biridir. Görüntü getirme algoritmaları iki kategoriden oluşmaktadır. Bu kategoriler, ayrıt edici yerel öznitelikler ve kompak hash kodları ile indekslenen global özniteliklerdir. Bu tez çalışmasında, mobil arama amacıyla bir görsel görüntü getirme algoritması önerilmektedir. Bu tip uygulamlarda sorgu görüntüsü, mobil cihazın kamerası ile çekilmiş görüntüde yer alan yerel bir paterndir. Yerel özniteliklerin bölgesel görüntü paternlerini temsil edebilmesi sayesinde benzer görüntülerin veya bölgelerin  ayırt edilmesinde güçlü bir yöntem olan SIFT öznitelikler ile sözcük ağacı indekleme yöntemi tarif edilmiştir. 
Literatürde, sözcük ağacı indeksleme ve getirme alanında bir çok yöntem mevcuttur. Sözcük ağacı ile görüntü eşleme alanındaki öncü çalışma Nister'in çalışmasında bahsi geçen sözcük ağacı ile ölçeklenebilir eşleme isimli yöntem olarak kabul edilebilir (Nister, 2006). Bu çalışmadan esinlenerek Philbin (Philbin, 2007) sözcük ağacı yaklaşımını daha da geliştirerek, getirilen görüntülerin SIFT özniteliklerinin sorgu görüntüsüne benzerliğinin RANSAC ile kontrol edilmesini önermiştir. Chen'in çalışmasında (Chan, 2010) getirme hızının arttırılması ve sözcük ağacı indekslemesinde bellek ihtiyacının azaltılması amacıyla Nister'in (Nister, 2006) çalışmasında tanıtılan ters indeks (inverted indeks) kullanılarak yaprak düğümlerin ayırt edici özelliği, skorlamaya bir normalizasyon faktörü olarak eklenmektedir. Yerel özniteliklerin ayrıt ediciliğini arttırmak amacıyla Wang'ın çalışmasında (Wang, 2011), her özniteliğin katkısını adaptif olarak kontrol eden yeni bir ağırlıklandırma önerilmiştir. Adaptif kontrol edilerek, öznitelik ve uzamsal (spatial) yönteminin sıkılaştırılması önerilmiştir. Whan'ın çalışmasında yerel özniteliklerin bağlamsal ağırlıklandırılması ile sözcük ağacı kullanılarak getirme yaklaşımı güçlendirilmiştir (Wang, 2011). Thai'nin çalışmasında, sözcük ağacına entegre bir geometrik yeniden skorlama metodu sunulmakta ve geometrik skorlama hesaplama zamanını azaltılırken eşleme performansı arttırılmaktadır (Tsai, 2010). Zhang (Zhang, 2010), sözcük gruplama (Bag of words) yöntemindeki başarımı arttırmak için geometrik görüntü ifadelerini koruyacak şekilde yerel öznitelikleri uzamsal öğelere indirgemektedir.   
Nister (Nister, 2006) ve Lowe'den (Lowe, 2004) esinlenerek, sözcük ağacındaki yaprak düğümlerin, daha üstteki düğümlere göre ayırt ediciliğinin fazla olması, bu tez çalışmasında eşleme başarımını arttırmak ve hesaplama karmaşıklığını azaltmak için yaprak düğümlere odaklanmamızı sağlamıştır. Yaprak düğümleri kullanarak ayırt ediciliği arttırmak için geniş ölçekli görüntü veritabanlarında arama ve getirme amacıyla bir eşleme skorlama yöntemi önerilmiştir. Görüntüye has ayrıt edici bağlamsal bilginin, sorgu ve veritabanı görüntüleri tarafından paylaşılan yaprak düğümlerde olduğu düşünülmektedir. Nister (Nister, 2006) gibi tüm düğümlerde veya Chen (Chen, 2010) gibi sorgu görüntüsünün ziyaret ettiği tüm düğümlerde, eşleme skorlamasını hesaplamak yerine, sorgu görüntüsünün sözcük ağacına yayılmış yaprak düğümlerinde kümülatif toplam hesaplayan yeni bir ağırlıklandırma formüle edilmiştir. Stanford'ın mobil görsel arama veri seti kullanılarak elde edilen sayısal sonuçlar, önerilen eşleme kriterinin eşleme performansını arttıran ve hesaplama karmaşıklığını azaltan yeni bir ayırt edici ölçüm yöntemi olduğunu göstermiştir. 
Bu tez çalışması kapsamında ise bahsettiğimiz dört metod gerçeklenerek performans Stanford mobil görsel veri seti üzerinde denemiş ve sonuçlar karşılaştırmalı olarak raporlanmıştır.  Yapılan çalışma kapsamında farklı mobil cihazlarla çekilmiş farklı kategorideki 100 referans görüntüsü için dört yöntemin de ilk 15 eşlemedeki başarımına bakılmıştır. Ortalama eşleme değerlerine bakılarak ilk eşleme başarımına bakıldığında sözcük ağacı ile uzaklık eşleme başarımı %43 iken ters indeks ile %45, bağlamsal ağırlıklandırma ile %47 ve önerilen yöntem ile  %72 doğru eşleme oranına ulaşıldığı görülmektedir. İlk 5 eşlemeye bakıldığında, ters indeks ve önerilen arama/eşleme yönteminin %86, sözcük ağacının %66, bağlamsal ağırlıklandırmanın ise %76 başarım oranı olduğu görülmektedir. En son olarak ilk 15 eşleme başarımına bakıldığında ise tüm yöntemlerin  %90, %99 seviyelerinde eşleme başarıma ulaştığı görülmektedir.
Sonuç olarak, farklı mobil cihazlardan elde edilen farklı kategorilerdeki görüntüler üzerinde yürütülen deneylerde, eşleme başarımı sonuçlarını karşılaştırmak için tüm cihazlar ve kategoriler için sabit olan girdiler tespit edilerek test koşulları oluşturulmuştur. Örneğin, kategorik bir karşılaştırma yapılması için dört farklı kategori için de ortak ve sabit olan Droid telefonu seçilmiştir. Droid en yüksek sonuca %94 başarımla kitap kapaklarında ulaşırken, en düşük başarımı tablolar üzerinde elde etmektedir. Bunun yanı sıra, iPhone cihazın tüm cihazlar arasında %98 sonuçla, en yüksek ilk seferde eşleme başarımına sahip olan telefon olduğu tespit edilmiştir.

Abstract:
In this thesis, it is aimed to develop a mobile image search, matching and retrieval system which provides high accuracy while reducing the computational complexity. To achieve this various image retrieval and matching methods are evaluated  and their performance are compared in order to determine effectiveness of different methodologies under different attacks.
Large-scale image retrieval based on visual features has been a challenging research topic because of many emerging applications specifically the mobile image search. Most of the scalable image retrieval algorithms fall into two categories. They either employ discriminative floating-point local features indexed by a vocabulary tree (Nister, 2006) or holistic features indexed by compact hashing codes (Torralba, 2008). Methods to integrate these techniques are also introduced in Zhang's study (Zhang, 2015). In this thesis, we propose a visual image retrieval algorithm for mobile search. These type of applications the query is just a local pattern located in the image captured by the mobile device (Chandrasekhar, 2011). Size of the local pattern, its location and background pattern may vary from image to image depending on the type of mobile sensor and the environment.  We describe a SIFT descriptor based vocabulary tree indexing method which is powerful in identifying near-duplicate images or regions since local features are particularly capable of representing regional image patterns.      
In the literature there are several methods employing vocabulary tree based indexing and retrieval. The method proposed as scalable recognition with a vocabulary tree in Nister's study (Nister, 2006) can be considered as the pioneering work in vocabulary tree based image matching.  Inspired by this study, the vocabulary tree based approach has been further improved in Philbin's study (Philbin, 2007) that employs RANSAC as a post spatial verification to check whether the SIFT features of retrieved images to have a similar layout to the query. In Chen's study (Chan, 2010),  a compression scheme for the inverted index introduced in Nister's study (Niser, 2006) is proposed to minimize the memory requirements of a vocabulary tree based indexing and to speed up the retrieval. In Chen's study (Chan, 2010) also the discriminative property of the leaf nodes is used by including them into the matching score as a normalization factor. In order to enhance the discriminative power of individual local features, a new weighting score which adaptively controls the contribution of each descriptor is proposed in Wang's study (Wang, 2011). The vocabulary tree-based retrieval approach is improved by adaptively controlling the contextual weighting of in individual features in both descriptor and spatial domains (Wang, 2011). In Tsai's study (Tsai, 2010), a geometric re-ranking method that utilizes a vocabulary tree integrated with a location geometric scoring method is presented and it is shown that the geometric scoring reduces the computation time while increasing the recognition performance. Zhang et al. (Zhang, 2010) quantizes spatial offsets among local features through the geometry-preserving visual phrases to improve the accuracy of BoW (Bag of words).            
Inspiring from Nister (Nister, 2006) and Lowe (Lowe, 2004) which clearly state that the leaf nodes are more distinctive than the upper level nodes of vocabulary tree, we also focus on the leaf nodes in our matching scheme, to increase accuracy while reducing the computational complexity. In order to incorporate the leaf nodes effectively for search and retrieval on large-scale image databases we propose a novel matching score to boost their discriminative ability. We believe in that the discriminative contextual information pertinent to individual images can be reached at the leaf nodes shared by the query and database images. Instead of calculating the matching score  over all nodes of the vocabulary tree as Nister (Nister, 2010) or over all nodes visited by the query image as Chen (Chen, 2010), we formulate a novel weighting score calculated as cumulative sum of the contributions of the leaf nodes of the query image spread throughout the vocabulary tree. Numerical results obtained on Stanford's Mobile Visual Search data set demonstrate that the proposed matching criteria can be used as a new discriminative measure to improve the visual matching performance while reducing the retrieval complexity. 
Big data concept is a concept that traditional data processing is not sufficient for large and complex data sets. One of the most challenging part of the big data concept is that the data is mostly unstructured. Unstructured data is not created through a defined pattern and can include complex data sets in itself. We can see that the same situation can occur for visual image search large data sets. For each image there are different number of SIFT features. Then, the size of the value is different and complexity can be changeable.
In our implementation, we used hierarchical K-means clustering to perform BoW on SIFT descriptors extracted from the database images for building VT indexing of individual categories. We used 'db4o' which is an open source Java based object oriented database. The idea behind using an object oriented database rather than a relational or XML based database is db4o enables us creating nested objects i.e., cluster (node) object and keypoint (descriptor) object.
The developed system consists of a number of subsystems. First the local keypoints of reference images are extracted and feature vectors are created by SIFT in the development of mobile image matching system. Afterwards, vocabulary tree is created applying hierarchical k-means clustering on the local feature vectors corresponding to local key points. This vocabulary tree structure is saved in order to serve as a learning set during matching process. Training images including CD, DVD and Book covers and art paintings are gathered from Stanford mobile visual dataset. 

After construction of the reference database, the system extracts features of the query image and starts to search them in the vocabulary tree in order to find the proper match with reference images stored in the database. The matchingis declared between the reference and query images which have the most similar features. 
During the experiments, we have tested and evaluated different methods we have applied in this work. The first method is based-on determining similarity scores for query images by calculating Euclidian distance between features, which are indexed and weighted (Nister, 2006). The second method, which is based-on entropy in vocabulary tree using inverted index (Girod, 2011). The third method is the implementation of contextual weighting approach for mobile image matching (Wang, 2011). The final method is the proposed approach in this thesis, which suggests a different weighting technique based on the leaf nodes of the vocabulary tree. 
Performances of the image matching of mobile devices are dependent on resolution, density, position and the complexity of the reference image. In order to prevent this, we applied sequenced iterative sum approach during geometric verification. Furthermore, we have assigned weights for each feature, which are indexed on final leaf nodes of the vocabulary tree. The threshold score is calculated by summing each value for every reference.
We have evaluated four different approaches, which are presented in this thesis using Stanford Mobile Visual Dataset. A hundred reference images in different categories and captured from different mobile devices are used for training and testing of four models. We have compared four different approaches by collecting matching results of first 15 attempts. According to the experiment results, it is shown that proposed approach increase the accuracy of the mobile visual search and matching system besides vocabulary tree, the inverted indexing and contextual weighting methods. Especially, the outcome of the fourth case shows that the new proposed approach significantly improves the search performance and increases the matching accuracy . In the first case the average matching rate is 43% whereas it is reported as 45% for the second test case. The third case which applies the contextual weighting has %47 matching rate. On the other hand the fourth and the proposed search/retrieval approach has 72% average  succefully matching rate. For the first 5 attempts, inverted indeks and the proposed search/ retrieval  approach has %86, vocabulary tree based approach has % 66 and contextual weighting has %76 success rates. At last we can see that all the methods have %90 - %99 sucess rates for the first 15 attempts.  
In conclusion,  the experiments are performed on different image categories captured by different mobile devices by creating test cases after determining constant inputs for all devices and categories. For example, in order to make categorical comparison, Droid is selected because of the fact that is a common device for all four catogories. It achieves the highest accuracy on book covers which is 94% success rate and the lowest rate is reported on paintings which is 56%. Moreover, iPhone achieved the highest accuracy with 98% success rate on the first attempt during the comparison of the success rates of all devices.