Tracking Edges, Corners and Vertices in an Image

Abstract.  In a range of imaging problems, particularly those where the images are of man-made objects, edges join at points which comprise three or more distinct boundaries between textures. In such cases the set of edges in the plane forms what a mathematician would call a planar graph. Smooth edges in the graph meet one another at junctions, called 'vertices', the 'degrees' of which denote the respective numbers of edges that join there. Conventional image reconstruction methods do not always draw clear distinctions among different degrees of junction, however. In such cases the algorithm is, in a sense, too locally adaptive; it inserts junctions without checking more globally to determine whether another configuration might be more suitable. In this paper we suggest an alternative approach to edge reconstruction, which combines a junction classification step with an edge-tracking routine. The algorithm still makes its decisions locally, so that the method retains an adaptive character. However, the fact that it focuses specifically on estimating the degree of a junction means that it is relatively unlikely to insert multiple low-degree junctions when evidence in the data supports the existence of a single high-degree junction. Numerical and theoretical properties of the method are explored, and theoretical optimality is discussed. The technique is based on local least-squares, or local likelihood in the case of Gaussian data. This feature, and the fact that the algorithm takes a tracking approach which does not require analysis of the full spatial data set, mean that it is relatively simple to implement.