ABSTRACT
There is an abundance of algorithms developed in the field of image processing and computer vision ranging from simple algorithms that manipulate binary images based on local point operations to complex algorithms for the interpretation of the symbolic information extracted from the images. Here we concentrate on algorithms for three central problems in image processing and computer
vision that are representative of different types of algorithmsdeveloped in this area. Thefirst problem, connectivity analysis, has been studied since the early days of binary images. It consists of separating the objects from the background by assigning different labels to the connected components of an image.The algorithms to identify connected components inbinary images are rather straightforward: the first one is an iterative algorithm that performs several scans of the image and uses only local operations; the next two algorithms consist of only two scans of the image and use global information in the form of an equivalence table. The second problem is that of grouping features extracted from the image (for instance, edge
points) into parametric curves such as straight lines and circles. An algorithm to detect lines, based on the Hough transform, is described that maps the image data into a parameter space that is quantized into an accumulator array. TheHough transform is a robust technique since it is relatively insensitive to noise in the sensory data and to small gaps in a line. The last problem is that of identifying and locating objects known a priori in an image, a
problem that is generally called model-based object recognition. Our discussion will focus on the matching task, that is, finding correspondences between the image and model descriptions. This correspondence can be used to solve the localization problem, i.e., the determination of a
geometrical transformation that maps the model into the observed object. Finding correspondences is difficult, due to the combinatorial nature of the problem and to noise and uncertainty in the data. We deal mainly with the case of planar objects undergoing rigid transformations in 3D space followed by scaled orthographic projections. We first assume that both the model and the image data are represented in terms of sets of feature points and describe two approaches (alignment and geometric hashing) to solve the point set matching problem. Then we consider model and image representations in terms of object boundary descriptions. We review dynamic programming algorithms for matching two sequences of boundary segments, which resemble the algorithm for the string editing problem. For multiresolution boundary representations, a tree dynamic programming algorithm is discussed. Extensions of the indexing techniques and of the algorithms based on the hypothesis-and-test paradigm to take advantage of the richer boundary descriptions are also described.
