Topological Spatial Verification for Instance Search

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

19 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Article number7117400
Pages (from-to)1236-1247
Journal / PublicationIEEE Transactions on Multimedia
Issue number8
Online published3 Jun 2015
Publication statusPublished - 1 Aug 2015


This paper proposes an elastic spatial verification method for Instance Search, particularly for dealing with non-planar and non-rigid queries exhibiting complex spatial transformations. Different from existing models that map keypoints between images based on a linear transformation (e.g., affine, homography), our model exploits the topological arrangement of keypoints to address the non-linear spatial transformations that are extremely common in real life situations. In particular, we propose a novel technique to elastically verify the topological spatial consistency with the triangulated graph through a "sketch-and-match" scheme. The spatial topology configuration, emphasizing relative positioning rather than absolute coordinates, is first sketched by a triangulated graph, whose edges essentially capture the topological layout of the corresponding keypoints. Next, the spatial consistency is efficiently estimated as the number of common edges between the triangulated graphs. Compared to the existing methods, our technique is much more effective in modeling the complex spatial transformations of non-planar and non-rigid instances, while being compatible to instances with simple linear transformations. Moreover, our method is by nature more robust in spatial verification by considering the locations, rather than the local geometry of keypoints, which are sensitive to motions and viewpoint changes. We evaluate our method extensively on three years of TRECVID datasets, as well as our own dataset MQA, showing large improvement over other methods for the task of Instance Search.

Research Area(s)

  • Instance search, non-planar and non-rigid objects, spatial verification, triangulated graph

Citation Format(s)

Topological Spatial Verification for Instance Search. / Zhang, Wei; Ngo, Chong-Wah.

In: IEEE Transactions on Multimedia, Vol. 17, No. 8, 7117400, 01.08.2015, p. 1236-1247.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review