On Detecting Spatial Regularity in Noisy Images

Detecting spatial regularity in images arises in computer vision, scene analysis, military applications, and other areas. In this paper we present an O(n 5 2 ) algorithm that reports all maximal equally-spaced collinear subsets. The algorithm is robust in that it can tolerate noise or imprecision that may be inherent in the measuring process, where the error threshold is a user-specified parameter. Our method also generalizes to higher dimensions. Keywords: Algorithms, combinatorial problems, computational geometry, pattern recognition. 1 Introduction Spatial regularity detection is an important problem in a number of domains such as computer vision, scene analysis, and landmine detection from infrared terrain images [5]. This paper addresses the problem of recognizing equally-spaced collinear subsets of a given pointset, where there may be imprecision in the input data. Kahng and Robins [5] gave an optimal O(n 2 )-time algorithm for the exact version of this problem (i.e., where n..