Video Google: A Text Retrieval Approach to Object Matching in Videos

“Video Google: A Text Retrieval Approach to Object Matching in Videos” by Josef Sivic and Andrew Zisserman of the University of Oxford was presented at the Ninth IEEE International Conference on Computer Vision (ICCV) in Nice in October 2003. It asked whether finding a particular object in a feature film could work the way a web search engine finds pages that contain particular words. The answer was a system in which the user outlines an object in one frame and receives, almost at once, a ranked list of the other frames that show it. Local region descriptors were vector-quantized into visual words, and the machinery of text retrieval was carried over to them: tf-idf weighting, a stop list of the most frequent words, an inverted file, and a re-ranking step that rewards words appearing close together. The paper established the bag of visual words for retrieval; that article describes the representation as it is used today, and image retrieval covers the systems that grew out of it. The authors published an extended version in IEEE Transactions on Pattern Analysis and Machine Intelligence in 2009, which this article compares with the conference paper. The 2003 paper received the ICCV Helmholtz Prize in 2017.

Problem

The paper opens by observing that identifying a specific object in a database of images, despite changes of viewpoint, lighting and partial occlusion, was reaching some maturity. Its introduction describes the standard recipe: detect overlapping regions with a controlled degree of invariance, describe each with a vector, match the vectors of two images by nearest-neighbor search, and remove wrong matches with local spatial coherence or a global constraint such as epipolar geometry. Schaffalitzky and Zisserman (2002) had applied this wide-baseline matching to films, matching key frames to find shots of the same 3D scene. The cost of such feature matching is the obstacle to search: every query must be compared with every frame at run time, and the journal version computes a worst case of $O(N R^2 D)$ for $N$ frames, $R$ regions per frame and descriptors of dimension $D$, whether the frames are searched one by one or pooled into one search space.

Text search engines avoid that cost because the matching is done in advance: documents are parsed into words, and an index lists, for each word, the documents that contain it. The paper’s premise is that vector quantization supplies the missing ingredient, a visual analogue of a word, so that two descriptors match when they fall in the same cluster. Matches are then precomputed, and any object in the film can be searched for, even one nobody thought about when the index was built. The authors also set themselves a test: the quantized system should not miss matches that nearest-neighbor matching would have found. Squire et al. (2000) had already used text retrieval’s weighting and inverted files for image databases, and the paper credits them; it claims to be, to the authors’ knowledge, the first systematic application of these ideas to object retrieval in video.

Contribution

• Visual words for object retrieval. Descriptors of affine covariant regions are clustered by k-means into a vocabulary, and each frame becomes a sparse vector of word frequencies, which turns object search into document retrieval.
• Text retrieval’s practices tested on images. The paper carried over tf-idf weighting, cosine ranking, a stop list and an inverted file, and compared weighting schemes on a ground-truth set, instead of treating quantization as only a speed-up.
• Video-specific stabilization. Regions are tracked through neighboring frames, and those that do not persist are discarded before indexing.
• Spatial re-ranking. The ranking from word frequencies is re-ordered by a cheap test of whether matched regions keep their neighbors, the visual analogue of rewarding query words that appear close together.

Method

The description below follows the 2003 paper; the table in the next section lists what the journal version changed.

Regions and descriptors. Each frame (720 × 576 pixels, converted to monochrome) yields two kinds of elliptical, affine covariant regions, the region type described in feature detection. Shape Adapted (SA) regions are grown around interest points by iteratively estimating the ellipse’s center, scale (from a Laplacian extremum across scale) and shape (by making the intensity gradients isotropic over the ellipse), using the implementations of Mikolajczyk and Schmid (2002) and of Schaffalitzky and Zisserman. Maximally Stable (MS) regions are the maximally stable extremal regions of Matas et al. (2002): areas of an intensity watershed segmentation whose size barely changes as the threshold varies. The paper uses both because they fire on different structures, SA regions on corner-like features and MS regions on blobs that contrast with their surroundings, such as a dark window on a grey wall. Each ellipse is enlarged to twice its detected size, to make its appearance more distinctive, and described by a 128-dimensional SIFT vector; the authors report that SIFT beat the other descriptors they tried on their ground-truth set and attribute this to its tolerance of small shifts in region position. A frame typically gave about 1,600 regions.

Tracking. Regions are tracked from frame to frame with a constant-velocity model and correlation. A region that does not survive more than three frames is rejected, each track’s descriptors are averaged into one, and the 10% of tracks with the largest diagonal covariance are discarded, leaving about 1,000 regions per frame. The authors report that averaging measurably improved the descriptors’ signal-to-noise ratio on their ground-truth tests.

Vocabulary. Clustering every descriptor of a film was out of reach, so the vocabulary was built from 48 shots of Run Lola Run, about 10,000 frames or 10% of the film, which still gave about 200,000 averaged track descriptors. Distances are Mahalanobis,

$$d(\bar{x}_1, \bar{x}_2) = \sqrt{(\bar{x}_1 - \bar{x}_2)^\top \Sigma^{-1} (\bar{x}_1 - \bar{x}_2)} ,$$

with a single covariance $\Sigma$ assumed common to all tracks and estimated from the descriptors along the tracks of the 48 shots, so that the noisier components of SIFT count less and the (slightly correlated) components are decorrelated. Transforming descriptor space by $\Sigma^{-1/2}$ turns this into the Euclidean distance that k-means needs. SA and MS descriptors were clustered separately, into about 6,000 and 10,000 words, in roughly the ratio of the two region counts; the paper compares the two sets to separate vocabularies for a building’s architecture and for its state of repair. Vocabulary sizes were chosen to maximize results on the ground-truth set, and k-means was run several times from random initial centers, keeping the best result.

Weighting and ranking. A frame is a document. With $n_{id}$ occurrences of word $i$ in frame $d$, $n_d$ words in the frame and $N$ frames in the database, word $i$ gets the weight

$$t_i = \frac{n_{id}}{n_d} \log \frac{N}{n_i} ,$$

and frames are ranked by the cosine of the angle between their weighted vectors and that of the query region. The conference text defines $n_i$ as the number of occurrences of word $i$ in the whole database; the journal version defines the corresponding $N_i$ as the number of documents that contain the word, the usual inverse document frequency. Bag of visual words covers tf-idf, cosine ranking and the inverted file in general.

Object search. For a whole film, the system uses one keyframe per second, averaging each stable region’s descriptor over two frames on either side, and assigns the descriptors to the vocabulary learned from the ground-truth shots, so most indexed frames contain objects and scenes the clustering never saw. The stop list removes the most frequent 5% of words, which came from clusters of over 3,000 points and caused mismatches all over an image, and also the rarest 10%; the limits were set by hand to reduce mismatches and the size of the inverted file while keeping enough vocabulary. The spatial consistency step takes the frames retrieved by the weighted vectors and re-ranks them. Each match defines a search area by its 15 nearest neighboring matches; every other region that also matches inside this area casts a vote for the frame, matches with no support are discarded, and the vote total gives the new rank. The authors placed this test deliberately between a loose requirement (neighbors in the query lie somewhere nearby in the retrieved frame) and a strict one (neighbors keep the same layout under the affine map that each pair of matched ellipses defines), and found the middle worked best. They noted that measures using the affine mapping might sometimes be needed, at greater computational cost.

Results

Scene matching. The vocabulary and weighting were evaluated on 164 frames from 48 shots of Run Lola Run, taken at 19 locations with four to nine frames each; the example frames of a location shown in its Fig. 3 come from different shots far apart in time, with significant viewpoint changes. Each frame in turn was used as a whole-frame query, and performance was summarized by the average normalized rank of the relevant frames, a measure from Müller et al. that the paper cites,

$$\widetilde{\mathrm{Rank}} = \frac{1}{N N_{\mathrm{rel}}} \left( \sum_{i=1}^{N_{\mathrm{rel}}} R_i - \frac{N_{\mathrm{rel}} (N_{\mathrm{rel}} + 1)}{2} \right),$$

where $R_i$ is the rank of the $i$-th of the query’s $N_{\mathrm{rel}}$ relevant frames among the $N$ frames. It is 0 when all relevant frames come first and 0.5 for random ordering. With tf-idf weighting, ranking was perfect for 17 of the 19 locations. The two failures were not missed matches but low-ranked ones, and the paper traces them to too few regions in the overlapping part of the scene: in one pair, only two of 564 and 533 detected regions corresponded. The combination of SA and MS regions beat either alone, each type winning on different frames.

Weighting	SA	MS	SA + MS
Binary	0.0265	0.0237	0.0165
Term frequency	0.0275	0.0208	0.0153
tf-idf	0.0209	0.0196	0.0132

Mean normalized rank over the 164 ground-truth frames (lower is better), 2003 paper, Table 1.

tf-idf gave the lowest mean rank for each region type and for their combination, but the authors called the differences over the whole set not very significant, adding that for particular frames the gap reached 0.1. Between the two simpler schemes, term frequencies were worse than binary weights for SA regions and better for MS regions and for the combination. The paper states that the same ground-truth set was used to choose the number of clusters, the minimum track length and the fraction of unstable tracks to reject; it follows that these figures are not a held-out test. On this set the authors concluded that quantization lost nothing against nearest-neighbor matching, citing Schaffalitzky and Zisserman’s earlier matching, though the paper prints no side-by-side comparison.

Object retrieval. Both films were indexed at about 4,000 keyframes each (3,768 for Run Lola Run), and the vocabulary learned on Run Lola Run was used unchanged for Groundhog Day. The paper reports three example queries rather than measured recall:

• a poster in Run Lola Run: 20 keyframes retrieved, six from the query’s own shot, all containing the poster;
• a second Run Lola Run object: 33 keyframes retrieved, 31 correct, with the two wrong ones ranked 29th and 30th;
• an object in Groundhog Day: 73 keyframes retrieved, 53 correct, the first error at rank 27.

The authors wrote that, as far as they could tell, no frame containing the object was missed. Querying 4,000 frames took about 0.1 s in a Matlab implementation on a 2 GHz Pentium.

Versions

Intermediate versions appeared as a 2006 book chapter, “Video Google: Efficient Visual Search of Videos”, and as “Efficient Visual Search for Objects in Videos” in Proceedings of the IEEE (2008); this article compares only the conference paper with the TPAMI paper, “Efficient Visual Search of Videos Cast as Text Retrieval” (submitted in January 2007 and published in the April 2009 issue), which describes itself as an extended version of the 2003 paper. The journal paper keeps the architecture and changes most numbers and the whole evaluation.

	ICCV 2003	TPAMI 2009
Films	Run Lola Run, Groundhog Day	Groundhog Day, Casablanca, Run Lola Run
Regions per frame	About 1,600 detected; about 1,000 after tracking and covariance filtering	About 1,200 detected; about 600 after the three-frame stability check
Vocabulary training	48 shots (about 10,000 frames), about 200,000 track-averaged descriptors	474 random frames, about 300,000 descriptors
Vocabulary	About 6,000 SA + 10,000 MS words; one vocabulary for both films	6,000 SA + 10,000 MS words; a new vocabulary per film
Document frequency	Occurrences of the word in the database	Documents containing the word
Stop list	Top 5% and bottom 10% of words	Top 10% (5% in some experiments)
Spatial consistency	15 nearest neighbors; vote count ranks frames; placed in the middle of the loose-to-strict range	15 nearest neighbors in both frames; votes plus cosine score, applied to the top 500 frames; no votes between matches of the same word; placed at the less constrained end of the range
Evaluation	164 frames, 19 locations; normalized rank	Six object queries over 5,640 keyframes (752 shots); shot-level average precision
Query time	About 0.1 s for 4,000 frames	0.82 s on average for 5,640 frames, with re-ranking

The journal’s spatial test was tightened against repeated structures, which the authors found responsible for many highly ranked false positives: matches with the same visual word may not vote for each other, and each match takes at most one vote per distinct word. It also derives the cost argument from the Problem section: with $M$ distinct words per frame, scoring all $N$ frames with sparse, prenormalized vectors costs at most $O(MN)$, a factor of $RD$ less than unquantized matching. The inverted file for Groundhog Day took about 66 MB for about 2 million word occurrences, against about 2 GB for the raw descriptors in double precision. Extracting and quantizing the regions took about 20 s per frame offline.

The journal’s evaluation answered questions the conference paper had left to examples. Six objects in Groundhog Day (a red clock, a black clock, a digital clock, two signs and a microphone, with 13 to 29 ground-truth shots each) were labeled in all 5,640 keyframes, and only about 12% of those ground-truth keyframes had been used to build the vocabulary. In its Fig. 9, mean average precision was 0.72 with tf-idf ranking and spatial re-ranking, 0.58 with tf-idf ranking alone, and 0.56 for a baseline that matched the query’s descriptors to every keyframe by thresholded nearest-neighbor search. The authors concluded that visual-word matching causes no significant loss against frame-to-frame matching, although the baseline scored higher on three of the six queries; re-ranking raised average precision on every query. The baseline took about 500 s per query, about 600 times longer. Further experiments in the journal paper:

• Vocabulary size (its Fig. 16): mean AP 0.49 with 1,600 words, 0.62 with 8,000, 0.72 with 16,000, 0.64 with 32,000 and 0.53 with 80,000. Too few words merge distinct patches; too many split one patch across words.
• Stop list (its Table 1, 16,000 words): 0.66 with no stop list or 1%, 0.71 with 5%, 0.72 with 10% and 0.65 with 20%. Stopping 10% removed 1,600 words but about 1.25 million of the 3.2 million word occurrences.
• Generalization (its Table 2): on Groundhog Day, a vocabulary built from Casablanca gave 0.31, against 0.71 for one built from Groundhog Day itself; concatenating the two vocabularies recovered 0.69 (all three with a 5% stop list, hence 0.71 rather than 0.72). This tempers the 2003 paper’s qualitative finding that one film’s vocabulary served another.
• Distractors (its Table 3): adding the 5,749 keyframes of Casablanca lowered mean AP from 0.72 to 0.63 with the Groundhog Day vocabulary; clustering both films jointly into 32,000 words gave 0.66.
• Weighting and similarity (its Fig. 17, without spatial re-ranking): tf-idf weights with the Bhattacharyya coefficient (see similarity and distance measures) scored best (0.61), KL-divergence variants and the standard tf-idf cosine followed (0.58–0.60), unweighted cosine scored 0.54, and χ² and ℓ1 ranking scored 0.26–0.40. The authors found that the ℓ1 and χ² scores ranked frames with only 10–50 words and one or two shared words too high, and noted that their poor ℓ1 result contrasts with Nistér and Stewénius’s (2006) results, which they attributed to different descriptor or data statistics: their queries were small objects in clutter, Nistér and Stewénius’s mostly whole images. With a 10% stop list instead of 5%, the methods without idf gained 0.035 on average, bringing the plain cosine and Bhattacharyya scores close to their tf-idf counterparts, which led the authors to describe idf as a “soft” stop list.

The journal paper also searched with an image from outside the film, a photograph of a Berlin museum that appears as a bank in Run Lola Run, and analyzed failure cases (described under Limitations). The Visual Geometry Group’s website still hosts a Video Google demonstration page, on the films Charade and Dressed to Kill, as of October 2026.

Impact

The PAMI Technical Committee lists “Video Google: A text retrieval approach to object matching in videos” among the winners of the 2017 Helmholtz Prize (as of October 2026), a biennial prize presented at each ICCV that, in the committee’s description, recognizes ICCV papers from ten years ago with significant impact on computer vision research; the 2017 list covers papers from ICCV 2003 and ICCV 2005. It includes Sivic, Russell, Efros, Zisserman and Freeman’s ICCV 2005 paper “Discovering objects and their location in images”, which in our reading took up the 2003 paper’s closing suggestion of borrowing latent semantic indexing and automatic clustering from text retrieval: it applied probabilistic latent semantic analysis to images represented by visual words, treating object categories as topics, to discover categories without supervision.

The retrieval systems that followed state their debt directly. Nistér and Stewénius (2006) described their vocabulary tree as largely inspired by Sivic and Zisserman; Philbin et al. (2007) presented Video Google’s flat k-means as effective but hard to scale to large vocabularies, and scaled it with approximate k-means; Jégou, Douze and Schmid (2009) described most state-of-the-art image search approaches as building on Sivic and Zisserman’s “seminal paper”. These descendants are covered in bag of visual words, which also describes the parallel use of visual-word histograms for categorization by Csurka et al. (2004), and in image retrieval. Quantizing descriptors to make search cheap also connects the paper to approximate nearest-neighbor search, which later systems used to assign descriptors to much larger vocabularies.

Limitations

• Dependence on detected regions. The conference paper traces its low rankings to a lack of regions in some scene types, such as pavement texture, and the journal paper lists failure modes: queries on which no region is detected (a plain wall returns nothing), regions on object boundaries or specular highlights that change with viewpoint (a coffee pot), unstable regions on deformable objects (creases in a shirt), and textureless or thin, wiry objects.
• One view per query. A query covers the visual aspect of the object seen in one frame. The 2003 paper found a sub-part of one image sufficient for quasi-planar rigid objects and proposed defining the object over several frames, and the journal paper pointed to grouping aspects within a shot with temporal information.
• A vocabulary per collection. The authors did not claim their quantization was universal, and the journal’s generalization experiment measured the cost of using another film’s vocabulary.
• Loose geometry. The neighborhood vote does not fit a transformation. The journal suggested stricter, more expensive verification in successive stages, with care not to reject deformable objects.
• Small evaluations. In our assessment, the evidence is thin by later standards: one film’s 164 frames, also used for tuning, in 2003, and six queries in one film in 2009. Later work moved to public benchmarks with many queries, such as Oxford 5K, described in image retrieval.

What Came After

The scaling limits that Philbin et al. pointed to were addressed first. The vocabulary tree of Nistér and Stewénius (2006) and approximate k-means (Philbin et al., 2007) made million-word vocabularies practical; Nistér and Stewénius blocked very long inverted lists for efficiency but reported that in most cases they could not improve retrieval quality with stop lists. Philbin et al. (2007) also replaced the neighborhood vote with spatial verification, estimating a transformation between query and result with a RANSAC variant, and Chum et al. (2007) used verified results to expand the query, an extension the TPAMI paper already cites. Jégou, Douze and Schmid (2009) identified the burstiness of visual words, a word’s tendency to recur within an image, as a source of error in tf-idf scoring that idf does not take into account; in our reading it is closely related to the repeated structures that the journal version had stopped from voting for each other. Soft assignment, Hamming embedding and aggregated descriptors such as VLAD followed, and later learned global embeddings, as bag of visual words and image retrieval describe.