Sequential Detection of Linear Features in Two-Dimensional R and om Fields (Edge, Image Processing, Line).
Paul H. Eichel · Deep Blue (University of Michigan) · 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 computer vision, pattern recognition, and image processing. Many current approaches to this problem involve a two step process: feature enhancement followed by detection. The detection step is generally accomplished in parallel over the image by imposing a decision threshold on some attribute of the local data. The specification of a decision threshold, however, is a problematical tradeoff between detectability and false positive rejection. Such enhancement/threshold detectors therefore often produce results in which features are only partially detected. In this thesis, we consider the use of a sequential tree searching approach to this problem. Linear features are modeled as paths through a two-dimensional r and om field. A log-likelihood statistic is derived that reflects the probability that a given path coincides with a true feature. Exploiting the connectivity of such features, the most probable paths are sequentially extended by a tree searching algorithm. The final classification decision is deferred until many observations along the paths are considered, greatly easing the problem of selecting a decision threshold. The nature of the search statistic derived here allows an analytical treatment of some key elements of the method. First, the statistic itself is shown to be unbiased and to possess a necessary asymptotic conditional mean. Second, bounds on the distribution of computational effort are determined. Since the tree search is sequential, the total searching effort is variable, depending on image quality. A generalized Chebychev bound relating conditional distributions on the r and om field to the distribution of computation is derived. Third, we find a bound on the probability that segments of detected contours are in error. Finally, a particular Markov r and om field model is proposed, allowing the data along search paths to be decorrelated with a one step predictive Wiener filter. This has an appreciable effect on the computational effort by decreasing the amount of searching along incorrect paths. Application to some real image processing tasks is demonstrated.