Toggle search
Toggle menu
5.1K
5.9K
229
50.3K
VR & AR Wiki
Toggle preferences menu
Toggle personal menu
Not logged in
Your IP address will be publicly visible if you make any edits.

Bag of visual words

From VR & AR Wiki
More actions

The bag of visual words model (also called bag of features, bag of keypoints or BoVW) is a computer vision technique that describes an image by how often it contains each of a fixed set of "visual words", while ignoring where in the image they appear. The visual words come from a vocabulary built by clustering local feature descriptors, such as SIFT or ORB descriptors, taken from training images. Each new descriptor is assigned to its nearest word, and the image becomes a histogram, or a weighted vector, of word occurrences.[1][2] The idea is borrowed from the bag-of-words model of text retrieval and language processing, in which a document is represented by the frequencies of the words it contains rather than by their order.[1][3]

The model was introduced for object retrieval in video and for image categorization in 2003 and 2004. Robotics researchers then adopted it for visual place recognition, the problem of deciding whether a camera is looking at a place it has seen before. In simultaneous localization and mapping (SLAM) it is a common way to find candidate images for loop closure and for relocalization after tracking is lost.[4][5] The open-source DBoW2 library, which builds vocabularies of binary descriptors, provides this function in ORB-SLAM and VINS-Mono, and RTAB-Map is built around its own bag-of-words loop closure detector.[6][7][8][9] The 3GPP technical report on 5G glass-type augmented reality devices gives bag-of-visual-words keyframe retrieval as its example of how an AR device can speed up relocalization against a stored spatial map.[10]

Reviewed 12 October 2026. Every statement checked against the full text of the cited papers (Sivic and Zisserman, Csurka et al., Nistér and Stewénius, Philbin et al., Lazebnik et al., FAB-MAP, DBoW2, RTAB-Map 2013, ORB-SLAM, ORB-SLAM3, VINS-Mono, Cadena et al., Tsintotas et al., NetVLAD), their DOIs via Crossref, the DBoW2 and ORB-SLAM2 READMEs, the RTAB-Map project page and ETSI TR 126 998 V19.0.0 clause 4.4.7.3. About review dates.

How it works

Local features

The pipeline starts with local features. A detector finds distinctive points or regions in an image (see Feature detection) and a descriptor summarizes the appearance around each one as a vector. Video Google computed two kinds of viewpoint covariant regions in each frame and described each with a 128-dimensional SIFT descriptor.[1] FAB-MAP and the 2013 RTAB-Map detector used SURF descriptors,[11][4] while DBoW2 and the systems built on it use binary descriptors such as BRIEF and ORB, which are fast to compute and are compared with the Hamming distance.[6]

Building the vocabulary

A vocabulary is learned by clustering a large set of training descriptors. Each cluster center becomes one visual word. Sivic and Zisserman used k-means on about 200,000 averaged descriptors from 48 shots of the film Run Lola Run and ended up with about 6,000 words for one region type and about 10,000 for the other. The same vocabulary was then used unchanged to search the film Groundhog Day.[1] Csurka and colleagues also used k-means and found that a vocabulary of 1,000 words was a good trade-off between accuracy and speed for their categorization task. They noted that visual words do not necessarily carry a repeatable meaning such as "eyes" or "car wheels".[2]

Flat k-means becomes slow for large vocabularies, which led to faster clustering schemes. The vocabulary tree of David Nistér and Henrik Stewénius applies k-means hierarchically, so that each descriptor is quantized by walking down a tree with a fixed branch factor.[12] James Philbin and colleagues at Oxford instead replaced the exact nearest-neighbor step of k-means with a forest of eight randomized k-d trees, a method they called approximate k-means, and built vocabularies with as many as one million words.[13] For binary descriptors, DBoW2 clusters with k-medians and k-means++ seeding; the vocabulary used in its experiments had 10 branches and 6 levels, which gives one million words.[6]

The vocabulary is typically trained offline on images that are separate from those processed later. Some build it incrementally while the robot moves, so that it adapts to the environment and needs no training step.[3][4]

Weighting and indexing

After quantization, an image is a vector with one entry per word. Video Google borrowed several steps from text retrieval. Words are weighted by term frequency-inverse document frequency (tf-idf), so that words common across the whole collection count for less. A stop list removes the most and least frequent words; Sivic and Zisserman stopped the top 5% and bottom 10%. An inverted file lists, for each word, the images in which it occurs.[1] With an inverted file, a query only has to be compared with images that share at least one word with it, which makes search over large collections fast.[6] DBoW2 also keeps a direct index that stores each image's features grouped by vocabulary node; it uses this index to find feature correspondences quickly during geometric verification.[6]

Geometric verification

Because the bag discards the positions of the features, two different scenes can produce similar histograms. Retrieval systems therefore check the top candidates geometrically. Video Google re-ranked results by requiring matched regions to be spatially consistent.[1] Philbin and colleagues fitted image transformations with a variant of RANSAC to re-rank their results. They found that this consistently improved search quality, though the gain was smaller with large vocabularies.[13] In SLAM, a candidate loop closure is usually accepted only after such a geometric check, often combined with a check that consecutive images agree (temporal consistency).[6][5]

History

Year Work Authors Contribution
2003 "Video Google", ICCV[1] Josef Sivic, Andrew Zisserman (Oxford) Recast object retrieval in video as text retrieval: quantized SIFT descriptors as visual words, tf-idf weighting, stop list, inverted file and spatial re-ranking. Demonstrated on the films Run Lola Run and Groundhog Day.
2004 "Visual Categorization with Bags of Keypoints", ECCV 2004 workshop[2] Gabriella Csurka and colleagues (Xerox Research Centre Europe) Used histograms of quantized keypoints as feature vectors for Naive Bayes and SVM classifiers on seven object categories.
2006 Vocabulary tree, CVPR[12] David Nistér, Henrik Stewénius (University of Kentucky) Hierarchical quantization that allows much larger vocabularies; retrieval tested on databases of up to 1 million images.
2006 Spatial pyramid matching, CVPR[14] Svetlana Lazebnik, Cordelia Schmid, Jean Ponce Added coarse spatial layout by computing histograms over increasingly fine sub-regions of the image.
2007 Large-vocabulary object retrieval, CVPR[13] James Philbin and colleagues (Oxford, Microsoft Research) Approximate k-means vocabularies of up to 1 million words; fast spatial verification; tests on more than 1 million Flickr images with Oxford landmarks as queries.
2008 FAB-MAP, IJRR[11] Mark Cummins, Paul Newman (Oxford) Probabilistic place recognition over bag-of-words observations, with a learned model of which words occur together.
2012 DBoW2, IEEE T-RO[6] Dorian Gálvez-López, Juan D. Tardós (University of Zaragoza) Vocabulary tree over a binary descriptor space (FAST keypoints with BRIEF descriptors), described by its authors as the first binary vocabulary used for loop detection.
2013 RTAB-Map loop closure detector, IEEE T-RO[4] Mathieu Labbé, François Michaud (Université de Sherbrooke) Incremental SURF vocabulary plus memory management for long-term, large-scale online operation.
2016 NetVLAD, CVPR[15] Relja Arandjelović and colleagues A trainable neural-network layer modeled on VLAD (vector of locally aggregated descriptors), trained for place recognition.

Retrieval and categorization

Sivic and Zisserman's 2003 paper, "Video Google: A Text Retrieval Approach to Object Matching in Videos", set out to retrieve the frames and shots of a film that contain a user-selected object "with the ease, speed and accuracy with which Google retrieves text documents". The authors acknowledged earlier image-retrieval work that had borrowed weighting and inverted files from text retrieval, and described their paper as the first systematic application of these ideas to object retrieval in videos. In a test that matched scene locations across 164 frames from 48 shots of Run Lola Run, tf-idf weighting gave a better mean rank than binary or plain term-frequency weights, although the authors noted that the differences averaged over the whole set were not very significant.[1]

Csurka and colleagues applied the same representation to generic visual categorization. Their in-house data set held 1,776 images in seven classes (faces, buildings, trees, cars, phones, bikes and books). With a 1,000-word vocabulary, a linear SVM reduced the overall error rate from 28% with Naive Bayes to 15%, without using any geometric information.[2]

Nistér and Stewénius showed that the vocabulary tree made much larger vocabularies practical, and that larger vocabularies greatly improved retrieval quality. Their implementation ran a live demonstration that recognized CD covers from a database of 40,000 images, and a query on a 50,000-image database took 25 ms.[12] Philbin and colleagues found that the choice of quantization had a major effect on retrieval quality.[13]

Place recognition in robotics

Robotics researchers adopted the model for appearance-based mapping. Cummins and Newman's FAB-MAP, published in 2008, was inspired by the retrieval systems of Sivic and Zisserman and of Nistér and Stewénius. It learns a generative model of which appearance words tend to occur together, because they are produced by the same objects, and approximates that distribution with a Chow-Liu tree. This lets it give a low match probability to images that look alike but are not distinctive, a problem known as perceptual aliasing. The paper demonstrated loop closure detection on a 2 km outdoor path.[11] According to Gálvez-López and Tardós, the follow-up FAB-MAP 2.0 detected loops with no false positives on trajectories of 70 km and 1,000 km, at recalls of 48.4% and 3.1%.[6]

DBoW2 was published in IEEE Transactions on Robotics in 2012; its authors described it as the first use of a binary vocabulary for loop detection. They reported no false positives on several public data sets with one vocabulary and one set of parameters, and an average of 22 ms per frame, including feature extraction, on a sequence of 26,300 images.[6] The library is written in C++, requires OpenCV, and ships with classes for ORB and BRIEF descriptors.[16]

Use in SLAM

Visual and visual-inertial odometry accumulate error over time (see Drift (tracking)). VINS-Mono, for example, uses loop detection and pose graph optimization to remove this drift once a revisited place is recognized.[8] The same methods can relocalize a device after tracking is lost, for example after sudden motion, occlusion or motion blur.[6] Comparing every new image with every stored feature quickly becomes impractical, and bag-of-words models avoid this by quantizing the feature space. The 2016 SLAM survey by Cadena and colleagues notes that such methods have shown reliable performance for loop closure detection within a single session.[5]

System Bag-of-words component Used for
ORB-SLAM (2015)[7] DBoW2 with an offline vocabulary of ORB descriptors Loop detection and relocalization
ORB-SLAM2[17] Modified DBoW2 (BSD licence), vocabulary file ORBvoc.txt Place recognition
ORB-SLAM3 (2021)[18] A single DBoW2 database of keyframes for all maps in its Atlas Relocalization, loop closing and map merging
VINS-Mono (2018)[8] DBoW2 with BRIEF descriptors Loop detection and relocalization
RTAB-Map (2013 onward)[4][9] Incremental vocabulary (SURF descriptors in the 2013 paper) Loop closure detection

ORB-SLAM builds its database incrementally as keyframes are added; an inverted index records the keyframes in which each word has been seen. Because neighboring keyframes overlap, the system groups keyframes that are connected in its covisibility graph and returns every keyframe match that scores higher than 75% of the best score. It also restricts brute-force descriptor matching to features that fall under the same node of the vocabulary tree, at the second of its six levels, to speed up matching.[7] ORB-SLAM3 changed the order of checks. Its authors wrote that DBoW2's requirement for three consecutive keyframes to match the same area before the geometric test raised precision at the cost of recall, making loop closing slow. ORB-SLAM3 instead verifies each candidate geometrically first and then checks it against three covisible keyframes.[18]

VINS-Mono, a visual-inertial estimator from the Hong Kong University of Science and Technology, detects 500 additional corners and describes them with BRIEF to improve the recall of DBoW2 loop detection. Because its inertial measurements make roll and pitch observable, it does not need rotation-invariant features such as ORB.[8] RTAB-Map's 2013 detector used SURF features extracted with OpenCV and built its vocabulary online, to avoid a training step for each new environment. A memory management scheme keeps recent and frequently seen locations in a working memory used for loop closure detection and moves others to long-term memory, so that processing stays within real-time limits.[4]

Applications in VR and AR

For camera-based tracking of AR devices (see also Inside-out tracking and Visual-inertial odometry), the 3GPP report on AR glasses describes visual features, keyframes and spatial maps as being used to map the real world, typically as part of a SLAM process, with a stored spatial map then used at runtime to relocalize the device.[10] In 3GPP TR 26.998 (published by ETSI as TR 126 998, version 19.0.0 of October 2025), which studies 5G glass-type AR and mixed reality devices, a spatial map can include metadata for keyframe retrieval. The report gives the bag-of-visual-words model as its example: the map stores the vocabulary and, for each keyframe, a vector of word occurrence counts. It states that, depending on the descriptor, the vocabulary is usually 10 to 100 MB and can be reused, and that the number of features per keyframe varies between 200 and 1,000. To relocalize, the device retrieves the closest keyframe with the bag-of-words model, matches features between the current frame and that keyframe, and then uses the keyframe's links to the map's 3D points to estimate the camera pose.[10]

Several research SLAM systems that use a bag-of-words index for place recognition have been evaluated for, or released on, AR-capable devices. The ORB-SLAM3 authors wrote that the room sequences of the TUM-VI data set, recorded with a hand-held stereo-inertial rig, can be representative of AR/VR applications in which a user moves a hand-held or head-mounted device in a small space. They reported an average accuracy of 9 mm for the system's stereo-inertial mode under quick hand-held motion in those rooms.[18] The VINS-Mono team ported their estimator to an iPhone 7 Plus as VINS-Mobile and demonstrated it with a simple AR application, comparing it with a Google Tango device.[8] RTAB-Map was released for Project Tango devices in 2016 and for iPhones and iPads with LiDAR in 2021.[9]

Limitations and successors

  • No spatial layout. Lazebnik, Schmid and Ponce wrote that because bag-of-features methods disregard all information about the spatial layout of the features, they cannot capture shape or separate an object from its background. Their spatial pyramid restored coarse layout by computing histograms over increasingly fine sub-regions of the image.[14]
  • Perceptual aliasing. Different places can share many visual words. FAB-MAP addresses this with a probabilistic model of word co-occurrence,[11] and SLAM systems add temporal and geometric checks before accepting a loop closure.[6] A survey of visual loop closure detection by Tsintotas, Bampis and Gasteratos notes that vector quantization throws away geometric information and so reduces discrimination when places look alike.[3]
  • Fixed vocabularies. A vocabulary trained in advance does not adapt to the environment where it is used, which led to incremental vocabularies built during navigation.[3]
  • Changing appearance. Cadena and colleagues note that bag-of-words methods cannot handle severe illumination changes, because visual words can no longer be matched.[5]

Other image representations keep more information per word. Fisher kernels fit a Gaussian mixture to the local features, and VLAD (vector of locally aggregated descriptors) records the difference between each descriptor and its nearest word.[3] As the NetVLAD authors put it, bag-of-visual-words aggregation keeps counts of visual words, while VLAD stores the sum of residuals for each word. NetVLAD turned VLAD into a layer that can be trained inside a convolutional neural network. It was trained for place recognition with images of the same places over time from the Google Street View Time Machine.[15]

See also

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Josef Sivic, Andrew Zisserman (2003). "Video Google: A Text Retrieval Approach to Object Matching in Videos". Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV 2003), vol. 2, pp. 1470-1477. IEEE. doi:10.1109/ICCV.2003.1238663. https://doi.org/10.1109/ICCV.2003.1238663. Retrieved 2026-10-12.
  2. ↑ 2.0 2.1 2.2 2.3 Gabriella Csurka, Christopher R. Dance, Lixin Fan, Jutta Willamowski, Cédric Bray (2004). "Visual Categorization with Bags of Keypoints". Workshop on Statistical Learning in Computer Vision, ECCV 2004. https://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/csurka-eccv-04.pdf. Retrieved 2026-10-12.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Konstantinos A. Tsintotas, Loukas Bampis, Antonios Gasteratos (2022-11). "The Revisiting Problem in Simultaneous Localization and Mapping: A Survey on Visual Loop Closure Detection". IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 11, pp. 19929-19953. doi:10.1109/TITS.2022.3175656. https://doi.org/10.1109/TITS.2022.3175656. Retrieved 2026-10-12.
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 Mathieu Labbé, François Michaud (2013-06). "Appearance-Based Loop Closure Detection for Online Large-Scale and Long-Term Operation". IEEE Transactions on Robotics, vol. 29, no. 3, pp. 734-745. doi:10.1109/TRO.2013.2242375. https://doi.org/10.1109/TRO.2013.2242375. Retrieved 2026-10-12.
  5. ↑ 5.0 5.1 5.2 5.3 Cesar Cadena, Luca Carlone, Henry Carrillo, Yasir Latif, Davide Scaramuzza, José Neira, Ian Reid, John J. Leonard (2016-12). "Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age". IEEE Transactions on Robotics, vol. 32, no. 6, pp. 1309-1332. doi:10.1109/TRO.2016.2624754. https://doi.org/10.1109/TRO.2016.2624754. Retrieved 2026-10-12.
  6. ↑ 6.00 6.01 6.02 6.03 6.04 6.05 6.06 6.07 6.08 6.09 6.10 Dorian Gálvez-López, Juan D. Tardós (2012-10). "Bags of Binary Words for Fast Place Recognition in Image Sequences". IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1188-1197. doi:10.1109/TRO.2012.2197158. https://doi.org/10.1109/TRO.2012.2197158. Retrieved 2026-10-12.
  7. ↑ 7.0 7.1 7.2 Raúl Mur-Artal, J. M. M. Montiel, Juan D. Tardós (2015-10). "ORB-SLAM: A Versatile and Accurate Monocular SLAM System". IEEE Transactions on Robotics, vol. 31, no. 5, pp. 1147-1163. doi:10.1109/TRO.2015.2463671. https://doi.org/10.1109/TRO.2015.2463671. Retrieved 2026-10-12.
  8. ↑ 8.0 8.1 8.2 8.3 8.4 Tong Qin, Peiliang Li, Shaojie Shen (2018-08). "VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator". IEEE Transactions on Robotics, vol. 34, no. 4, pp. 1004-1020. doi:10.1109/TRO.2018.2853729. https://doi.org/10.1109/TRO.2018.2853729. Retrieved 2026-10-12.
  9. ↑ 9.0 9.1 9.2 "RTAB-Map - Real-Time Appearance-Based Mapping". RTAB-Map project page. IntRoLab, Université de Sherbrooke. https://introlab.github.io/rtabmap/. Retrieved 2026-10-12.
  10. ↑ 10.0 10.1 10.2 "LTE; 5G; Support of 5G glass-type Augmented Reality / Mixed Reality (AR/MR) devices (3GPP TR 26.998 version 19.0.0 Release 19)". ETSI TR 126 998 V19.0.0, clause 4.4.7.3. ETSI. 2025-10. https://www.etsi.org/deliver/etsi_tr/126900_126999/126998/19.00.00_60/tr_126998v190000p.pdf. Retrieved 2026-10-12.
  11. ↑ 11.0 11.1 11.2 11.3 Mark Cummins, Paul Newman (2008-06). "FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance". The International Journal of Robotics Research, vol. 27, no. 6, pp. 647-665. doi:10.1177/0278364908090961. https://doi.org/10.1177/0278364908090961. Retrieved 2026-10-12.
  12. ↑ 12.0 12.1 12.2 David Nistér, Henrik Stewénius (2006). "Scalable Recognition with a Vocabulary Tree". 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), vol. 2, pp. 2161-2168. IEEE. doi:10.1109/CVPR.2006.264. https://doi.org/10.1109/CVPR.2006.264. Retrieved 2026-10-12.
  13. ↑ 13.0 13.1 13.2 13.3 James Philbin, Ondřej Chum, Michael Isard, Josef Sivic, Andrew Zisserman (2007-06). "Object retrieval with large vocabularies and fast spatial matching". 2007 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE. doi:10.1109/CVPR.2007.383172. https://doi.org/10.1109/CVPR.2007.383172. Retrieved 2026-10-12.
  14. ↑ 14.0 14.1 Svetlana Lazebnik, Cordelia Schmid, Jean Ponce (2006). "Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories". 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), vol. 2, pp. 2169-2178. IEEE. doi:10.1109/CVPR.2006.68. https://doi.org/10.1109/CVPR.2006.68. Retrieved 2026-10-12.
  15. ↑ 15.0 15.1 Relja Arandjelović, Petr Gronat, Akihiko Torii, Tomas Pajdla, Josef Sivic (2016-06). "NetVLAD: CNN Architecture for Weakly Supervised Place Recognition". 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5297-5307. IEEE. doi:10.1109/CVPR.2016.572. https://doi.org/10.1109/CVPR.2016.572. Retrieved 2026-10-12.
  16. ↑ Dorian Gálvez-López. "DBoW2". GitHub. https://github.com/dorian3d/DBoW2. Retrieved 2026-10-12.
  17. ↑ Raúl Mur-Artal, Juan D. Tardós, J. M. M. Montiel, Dorian Gálvez-López. "ORB-SLAM2". GitHub. https://github.com/raulmur/ORB_SLAM2. Retrieved 2026-10-12.
  18. ↑ 18.0 18.1 18.2 Carlos Campos, Richard Elvira, Juan J. Gómez Rodríguez, José M. M. Montiel, Juan D. Tardós (2021-12). "ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual-Inertial, and Multimap SLAM". IEEE Transactions on Robotics, vol. 37, no. 6, pp. 1874-1890. doi:10.1109/TRO.2021.3075644. https://doi.org/10.1109/TRO.2021.3075644. Retrieved 2026-10-12.
Retrieved from "https://vrarwiki.com/index.php?title=Bag_of_visual_words&oldid=49941"