Sequential Detection of Linear Features in Two-Dimensional Random Fields (1985)

The detection of edges, lines, and other linear features in two-dimensional discrete images is a low level processing step of fundamental importance in the automatic processing of such data. Many subsequent tasks in computer vision, pattern recognition, and image processing depend on the successful execution of this step. In this thesis, we will address one class of techniques for performing this task: sequential detection. Our aims are fourfold. First, we would like to discuss the use of sequential techniques as an attractive alternative to the somewhat better known methods of approaching this problem. Although several researchers have obtained significant results with sequential type algorithms, the inherent benefits of a sequential approach would appear to have gone largely unappreciated. Secondly, the sequential techniques reported to date appear somewhat lacking with respect to a theoretical foundation. Furthermore, the theory that is advanced incorporates rather severe restrictions on the types of images to which it applies, thus imposing a significant limitation to the generality of the method(s). We seek to advance a more general theory with minimal assumptions regarding the input image. A third goal is to utilize this newly developed theory to obtain quantitative assessments of the performance of the method. This important step, which depends on a computational theory, can answer such vital questions as: Are assumptions about the qualitative behavior of the method justified? How does signal-to-noise ratio impact its behavior? How fast is it? How accurate? The state of theoretical development of present techniques does not allow for this type of analysis. Finally, a fourth aim is to' extend the earlier results to include correlated image data. Present sequential methods as well as many non-sequential methods assume that the image data is uncorrelated and cannot therefore make use of the mutual information between pixels in real-world images. We would like to extend the theory to incorporate correlated images and demonstrate the advantages incurred by the use of the existing mutual information. The topics to be discussed are organized in the following manner. We will first provide a rather general discussion of the problem of detecting intensity edges in images. The edge detection problem will serve as the prototypical problem of linear feature extraction for much of this thesis. It will later be shown that the detection of lines, ramp edges, texture edges, etc. can be handled in similar fashion to intensity edges, the only difference being the nature of the preprocessing operator used. The class of sequential techniques will then be introduced, with a view to emphasize the particular advantages and disadvantages exhibited by the class. This Chapter will conclude with a more detailed treatment of the various sequential algorithms proposed in the literature. Chapter 2 then develops the algorithm proposed by the author, Sequential Edge Linking or SEL. It begins with some definitions, follows with a derivation of the critical path branch metric and some of its properties, and concludes with a discussion of algorithms. The third Chapter is devoted exclusively to an analysis of the dynamical behavior and performance of the method. ' Chapter 4 then deals with the case of correlated random fields. In that Chapter, a model is proposed for which paths searched by the SEL algorithm are shown to possess a well-known autocorrelation function. This allows the use of a simple linear filter to decorrelate the raw image data. Finally, Chapter 5 presents a number of experimental results and corroboration of the theoretical conclusions of earlier Chapters. Some concluding remarks are also included in Chapter 5.