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.