Fast Convex Layers Algorithm for Near-Duplicate Image Detection

Article type: Research Article

Authors: Šinjur, Smiljan | Zazula, Damjan | Žalik, Borut

Affiliations: Facultaty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia, e-mail: smiljan.sinjur@uni-mb.si, zazula@uni-mb.si, zalik@uni-mb.si

Abstract: This paper builds on a novel, fast algorithm for generating the convex layers on grid points with linear time complexity. Convex layers are extracted from the binary image. The obtained convex hulls are characterized by the number of their vertices and used as representative image features. A computational geometric approach to near-duplicate image detection stems from these features. Similarity of feature vectors of given images is assessed by correlation coefficient. This way, all images with closely related structure and contents can be retrieved from large databases of images quickly and efficiently. The algorithm can be used in various applications such as video surveillance, image and video duplication search, or image alignment. Our approach is rather robust up to moderate signal-to-noise ratios, tolerates lossy image compression, and copes with translated, rotated and scaled image contents.

Keywords: near-duplicate image detection, feature extraction, geometric features, convex layers, similarity measure

Journal: Informatica, vol. 23, no. 4, pp. 645-663, 2012