在巨量資料中進行以樣本為基礎的物件搜尋

Abstract

隨著行動通訊和數位攝影技術的發展和普及,使用者貢獻越來越大量的相片。因此如何能夠有效並且快速的,在這樣巨量的相片資料庫中,讓使用者能藉由相片搜尋,提供給使用者需要的資訊,變成一個很重要的議題。近年來,藉由特徵點或是視覺文字相片搜尋,其效能會受到兩個重要的因素影響:(1)有效率的空間關係驗證;(2)如何有效的表示相片中的物件。因此,在這個研究中,將會探討以樣本為基礎的物件搜尋中,此兩個重要的議題。在第一個議題中,首先我們會探討如何有效率的進行空間關係驗證。在傳統的方法中,此步驟通常都很耗費時間,然而我們觀察到在大規模的影像搜尋中,正確的特徵點比對,通常會集中在搜尋影像的某些區域,這些區域在我們的研究中被稱為熱門區域點。因此,我們提出了對位置區域敏銳的抽樣一致的方法,嘗試去找出對於空間關係驗證中,可靠並且正確的特徵點區域,並且提出一個更新此熱門區域點的有效方法,來加速空間關係驗證的步驟,我們也將此技術應用在以樣本為基礎的嶄新廣告媒合上,以加速並提高其比對的正確性。第二個議題是如何有效的表示相片中的物件,因為影像中常常會有多個物件或是背景,為了克服這樣的問題,我們提出了一個嶄新的擬似物件的概念,也就是影像的特徵點在空間中有鄰近關係的特徵子集合,用以近似影像中的真實物件。經由實驗在真實的相片資料庫中,可以看出我們提出的方法,對於以樣本為基礎的物件搜尋,比起傳統的方式在正確性和效率都會提升很多。

Due to the exponential growth of image collections, there arise the needs for efficient and effective example-based image search. Recently, image search by matching bags of feature points or visual words has shown an important paradigm, where the search quality is assured by the representation of objects in photos and spatial verification. In this thesis, we aim to investigate two important topics in example-based object retrieval. The first one is efficient spatial verification, which exploits geometry model between matching candidates for rejecting false positives and entailing further applications. The traditional methods for spatial verification are time-consuming to estimate model parameters iteratively from a set of (noisy) observed data. Instead, we observe that the image matching for large-scale image retrieval often corresponds to certain regions in the query image – the hot spots. Therefore, the aim of the proposed novel approach – Locality Sensitive Sample Consensus (LOCSAC), attempts to explore ”good matches” for accurate geometry model estimation. In addition, an online framework is devised for adaptively updating hot spot regions. The second one is the representation of objects in photos. Due to a database image representation generally carries mixed information of the entire image which may contain multiple objects and background. To tackle this problem, we propose a novel representation of objects, pseudo-objects – a subset of proximate feature points with its own feature vector to represent a local area, to approximate candidate objects in database images. Experimenting over consumer photo benchmarks, we will show that the proposed spatial verification method can bring (on the average) 20 folds speed-up over the conventional methods and assure the same or better quality. Besides, we confirm that the proposed pseudo-object can significantly benefit for object retrieval both in accuracy and efficiency.