You will be presented with the full text of a science research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
bag - of - words ( bow ) was originally proposed for document retrieval . in recent years , the method has been successfully applied to image retrieval tasks in computer vision community @xcite .
the method is attractive because of its efficient image representation and retrieval .
bow represents an image as a sparse vector of visual words , and thus images can be searched efficiently using an inverted index file system .
other major application areas of the bow method are appearance - based mobile robot localization and slam problems .
the fundamental issue involved with the appearance - based approach to both visual slam and global localization is the place recognition .
robot should be able to recognize the places it has visited before to localise itself or refine the map of the environment .
this task is performed by matching the current view of the robot to the existing map that contains the images of the previously visited locations . in this paper
we consider the problem of appearance - based localization in which the map is known _ a priori_.    in large - scale environments maps contain too many images to match .
the image search in such a large map is still a challenging and open problem .
matching images by comparing the local features of each image directly to the local features of all other images in the map is not practical .
bag - of - words proposes a more efficient approach ; first , rather than matching with a pool of million visual features extracted from many thousands of images , the local features are mapped to a smaller number of vocabulary words that are built in an offline phase . this process is called vector - quantization .
once the visual words are identified in the query image , they are used as indices into the image database , to directly retrieve the images that share the same words .
when the vocabulary is large , the vector - quantization process can be a computationally expensive task in real - time localization .
considerable research has been done to speed up the search ; some papers @xcite do approximate nearest - neighbor search using structures like vocabulary trees @xcite ; some methods reduce the number of local image features by selecting only a fraction of features that are highly discriminative @xcite ; another group makes use of more compact feature descriptors like @xcite . in this paper , we first show that some image retrieval tasks are _ easier _ for bow method .
the hardness criteria , defined later , concerns how distinctive the image query is among all images in the dataset . given this criteria ,
we show that the bow search can be terminated earlier for easier queries .
this means , in such queries , mapping only a portion of features can be sufficient to yield a relatively good result .
the stopping rule saves considerable amount of computational resources .
the intuition behind this is that when there are many similar images to the query image , in terms of the number of common words they share , the search becomes more difficult as more processing is required to find the closest match candidate .
whereas when the query image has only a few match candidates , i.e. , it shares its visual words with only a few images , the search becomes easy as vector - quantizing only a small number of features is sufficient to find the closest match to the query . by exploiting this fact
, we can stop the vector - quantization when the search is easy and the nearest neighbor to the query is easy to find .
our method acts as an approximate image search algorithm .
our experimental results show that the accuracy decreases only slightly while the computational cost decreases dramatically
.    our approach can be best compared with the approach of cummins and newman @xcite who use concentration inequalities ( bennett s inequality in their case ) for early bail - out in multi - hypothesis testing that excludes unlikely location hypotheses from further evaluation .
however , we use a different bail - out strategy for the process of vector - quantization . in the next section ,
we briefly review the image representation and the inverted - index search algorithm used in bow framework .
this is followed by a review of the localization algorithms that employ bow for the image search .
our proposed method to improve the efficiency of bow is described in section  [ sec : method ] .
section  [ sec : results ] presents the experimental results and the evaluation criteria , and the result of our comparisons .
finally , we conclude the paper in section  [ sec : conclud ] .
bag - of - words is a popular model that has been used in image classification , objection recognition , and appearance - based navigation . because of its simplicity and search efficiency
it has been used as a successful method in web search engines for large - scale image and document retrieval @xcite .
bag - of - words model represents an image by a sparse vector of visual words .
image features , e.g. , sifts @xcite , are sampled and clustered ( e.g. , using k - means ) in order to quantize the space into a discrete set of visual words .
the centroids of clusters are then considered as visual words which form the visual vocabulary .
once a new image arrives , its local features are extracted and vector - quantized into the visual words .
each word might be weighed by some score which is either the word frequency in the image ( i.e. , _ tf _ ) or the `` term frequency - inverse document frequency '' or _
tf - idf _ @xcite .
a histogram of weighted visual words , which is typically sparse , is then built and used to represent the image .
an inverted index file , used in the bow framework , is an efficient image search tool in which the visual words are mapped to the database images .
each visual word serves as a table index and points to the indices of the database images in which the word occurs .
since not every image contains every word and also each word does not occur in every image , the retrieval through inverted - index file is fast .
bag - of - words model has been extensively used as the basis of the image search in appearance - based localization or slam algorithms @xcite .
cummins and newman @xcite propose a probabilistic framework over the bag - of - words representation of locations , for the appearance - based place recognition . along with the visual vocabulary they also learn the chow liu tree to capture the co - occurrences of visual words .
similarly , angeli _ et al . _
@xcite develop a probabilistic approach for place recognition in slam .
they build two visual vocabularies incrementally and use two bow representations as an input of a bayesian filtering framework to estimate the likelihood of loop closures .    assuming each image has hundreds of sift features , mapping the features to the visual words , using a linear search method , is computationally expensive and not practical for real - time localization .
researchers have tackled this problem with different approaches that speeds up the search but at the expense of accuracy .
a number of papers have employed compact feature descriptors that speeds up the search .
glvez - lpez and tards in @xcite propose to use fast @xcite and breif @xcite binary features and introduce a bow model that descritizes a binary space .
similarly , @xcite use surf @xcite to have a more compact feature descriptor .
another approach is to use approximate nearest neighbor search algorithms , like hierarchical k - means @xcite , kd - trees @xcite or graph - based search methods @xcite and @xcite , to speed up the quantization process .
achar _ et al .
_ @xcite and zhang @xcite propose reducing the number of features in each image , thereby reducing ( removing ) the vector - quantization process .
they keep track of the features that are repeatable over time . however , these approaches are more specific to the navigation problems where the data is sequential and there exists considerable overlaps between consecutive images .
our approach is more similar to this group as we also reduce the amount of feature mapping .
however rather than only selecting a small set of features , we use all features but we stop the mapping process when necessary . our approach is also more general as it does not depend on the sequential property of the data .
vector - quantization ( vq ) is an expensive process when the bow - based image retrieval is performed in large - scale environments , in which hundreds of features extracted from an image need to be matched against hundreds of thousands of visual words .
the question is if we really need to vector - quantize all features ?
depending on the difficulty level of the search , the number of features to be converted to visual words may vary .
we call a search difficult when there are many similar images to the query and thus finding the nearest neighbor among all those candidates requires more computations
. whereas in an easy search , the query image is similar to only a few images in the database and it can find its true match after processing only a small percentage of features .
figure  [ diff_search ] and figure  [ easy_search ] show examples of easy and difficult searches .
the histograms show the similarity of each database image to the query based on the _ tf - idf _ score .
the difficult search needs to process at least @xmath0 of features to find the closest match to the query ( indicated by the peak of the histogram ) , however the easy search can stop the search after processing only @xmath1 of features as the peak does not change until the end of the search . comparing the distance between the peak and average of the histograms , it can be seen that in difficult search this distance is smaller than that in easy search , which is expected .
initially each image starts with no vote . in original bow
, image features are converted to visual words one by one and the histogram ( of images scores ) is built incrementally .
each bin of the histogram corresponds to one of the database images and indicates the score of that image .
each visual word will cast a distance - weighted vote for multiple images , i.e. , histogram bins .
this process continues until all words cast their votes and then the peak of the histogram ( the bin with the highest score ) determines the nearest neighbor to the query .    [
cols="^,^ " , ]     the experimental results shown in tables [ exp1:city1 ] to [ exp1:newcol2 ] have been performed by rule 1 .
figures  [ fig : rules ] and [ fig : rules2 ] show the result of applying different rules to the bow search on the new college ( right - side sequence ) and city center ( right - side sequence ) datasets , respectively .
the graphs have been generated by varying the stopping thresholds . as can be seen ,
stopping rules # 1 and # 3 generate better results . by reducing the number of processed features to half the accuracy only decreases slightly .    figure  [ fig : feat_im ] shows another experiment that validates our proposed stopping method .
figure shows the relation between the number of images and the percentage of features they need to process to obtain the same result as that of the original bow .
the experiment has been done on city center dataset ( left - side sequence ) with the stopping rule # 1 used .
we set the threshold to @xmath2 to get exactly the same accuracy of original bow .
as can be seen , only @xmath3 images need to process @xmath4@xmath5 of their features , another @xmath6 only need to vector - quantize smaller percentages of features .
we observed that the computational requirements of the bow method can be significantly reduced by allocating less computations to easier search queries .
deciding when to terminate the search is treated as a stopping problem .
we proposed several stopping rules and showed their effectiveness on an appearance - based localization problem .
a. angeli , d. filliat , s. doncieux , and j .- a .
meyer , `` a fast and incremental method for loop - closure detection using bags of visual words '' , _ ieee transactions on robotics , special issue on visual slam _ , pp .
1027 - 1037 , 2008 .
k. hajebi , y. abbasi - yadkori , h. shahbazi , and h. zhang , `` fast approximate nearest - neighbor search with k - nearest neighbor graph '' , in _ proc .
of the twenty - second international joint conference on artificial intelligence ( ijcai ) _ , vol .
2 , pp . 1312 - 1317 , 2011 .
r. i. hartley and a. zisserman , _ multiple view geometry in computer vision .
_ , cambridge university press , second edition , 2004
. w. hoeffding , `` probability inequalities for sums of bounded random variables '' , _ journal of the american statistical association _ , vol .
13 - 30 , 1963 .
f. li and j. kosecka , `` probabilistic location recognition using reduced feature set '' , in _ proc . of the ieee international conference on robotics and automation ( icra ) _ , 2006 .
o. maron and a. w. moore , `` hoeffding races : accelerating model selection search for classification and function approximation '' , in _ advances in neural information processing systems ( nips ) _ , vol .
59 - 66 , 1993 .
d. nister and h. stewenius , `` scalable recognition with a vocabulary tree '' , in _ proc . of the ieee international conference on computer vision and pattern recognition ( cvpr )
2 , pp . 2161 - 2168 , 2006 .
j. philbin , o. chum , m. isard , j. sivic , and a. zisserman , `` object retrieval with large vocabularies and fast spatial matching '' , in _ proc . of the ieee international conference on computer vision and pattern recognition ( cvpr ) _ , pp . 1 - 8 , 2007 .
h. shahbazi and h. zhang , `` application of locality sensitive hashing to real - time loop closure detection '' , in _ proc . of the ieee / rsj international conference on intelligent robots and systems ( iros ) _ , 2011 .
j. sivic and a. zisserman , `` video google : efficient visual search of videos : toward category - level object recognition '' , in _ proc . of the ieee international conference on computer vision and pattern recognition ( iccv )
_ , pp . 1470 - 1477 , 2003 .
we propose a technique to improve the search efficiency of the bag - of - words method for image retrieval . 
 we introduce a notion of difficulty for the image matching problems and propose methods that reduce the amount of computations required for the feature vector - quantization task in bow by exploiting the fact that easier queries need less computational resources . measuring the difficulty of a query and stopping the search accordingly is formulated as a stopping problem . 
 we introduce stopping rules that terminate the image search depending on the difficulty of each query , thereby significantly reducing the computational cost . 
 our experimental results show the effectiveness of our approach when it is applied to appearance - based localization problem .