A multiresolution chain coding scheme for contours is developed based on 4-connected chain codes at progressively more refined grid sizes. By taking advantage of a specific set of possible paths a contour can travel, the algorithm presented generates a multiresolution representation of a contour, with the final refinement representing the original contour with the same accuracy as conventional 4-connected chain coding. The technique described requires only a small overhead in comparison to 4-connected chain coding, so has the advantage of providing a hierarchical representation of a contour at little cost. The generation of a multi-scale representation allows the algorithm to perform well in the presence of storage or transmission limitations, as only a fraction of the data is required to obtain a detailed representation of the entire contour.>

Examines the localization criterion for edge detection and determine the probability density function describing the edge location error. Canny (1986) defines the measure of localization as the reciprocal of the root-mean-square edge location error and formulates an expression of this measure for local maximum detectors. However, Tagare and deFigueiredo (1990) point out that an incorrect assumption is made in the calculation. The same procedure is used by Sarkar and Boyer (1991) for their localization measure for zero-crossing detectors. We modify the analysis and obtain a closed-form solution of the probability density function of the edge location error. Examination of the density function indicates the variance of the edge location error does not exist, and hence cannot be used directly as a measure of localization.>

Binary images of objects are digitized by coloring a pixel cell black if more than half of its area is within the interior of the object. For simplicity, the digitization is often modified by looking only at the center point of a cell to determine its pixel value. The digitized boundary curve consists of a sequence of 4-directional links, sometimes called a "crack" code since it follows the cracks or edges of the pixel cells. Of interest here is the entropy of digitized binary objects or planar curves on an m/spl times/m integer grid. Let D(m) denote the number of digital convex polygons which can be inscribed into an integer grid of size m/spl times/m. The asymptotic estimation of log D(m) is of interest in determining the entropy of digitized convex shapes. It is shown that log D(m) is of the order m/sup 2/3/.>

A differential chain code implementation of the basic eight-directional and N-ring chain code for the encoding of line drawings is considered. Several distortion and rate criteria are considered, and they are evaluated for the special case of encoding infinite straight lines. These results indicate that the differential code outperforms ring codes and the ring delta code. Using a linear decoding filter for reconstructing a smoothed approximation to the original line is also considered. Optimal reconstruction filters for infinite straight lines at various angles are derived. An angle-invariant reconstruction filter that minimizes the expected square distortion taken over all angles is derived. The overall performance using this filter is close to that of the optimum filter. Furthermore, the impulse response of the angle-invariant filter is approximately rectangular, which can lead to simple hardware implementations.>

A 1:1 correspondence is established between digital straight lines which start at a fixed point and a simple set of quadruples of integer parameters. Such a representation by parameters is useful for enumeration, First, the authors show a 1:1 correspondence between point pairs in a planar set of points and the linear dichotomies of this set. Then, from the equivalence between digital lines and linear dichotomies of points on the digitization grid, they prove a 1:1 and 'onto' correspondence between digital straight lines starting at a fixed point and a well-defined set of pairs of grid points. It follows that four parameters uniquely represent any given digital line with a fixed starting point. An O(N) algorithm is given for determining the parameters from the digital line, as well as O(log N) algorithms for transforming between these parameters and the parameters suggested by L. Dorst and A.W.M. Smeulders (1984).>

The number of digital straight lines on an N*N grid is shown. A digital straight line is equivalent to a linear dichotomy of points on a square grid. The result is obtained by determining a way of counting the number of linearly separable dichotomies of points on the plane that are not necessarily in general position. The analysis is easily modified to provide a simple solution to a similar problem considered by C. Berenstein and D. Lavine (1988) on the number of digital straight lines from a fixed starting point.>

Measurement of perimeters of planar shapes from their digitized images is an important task of computer vision systems. A general methodology for the design of simple and accurate parameter estimation algorithms is described. It is based on minimizing the maximum estimation error for digitized straight edges over all orientations. Two perimeter estimators are derived and their performance is tested and digitized circles using computer simulations. The experimental results may be used to predict the performance of the algorithm on shapes with arbitrary contours of continuous curvature. The simulations also show that fast and accurate perimeter estimation is possible, even for objects that are small relative to pixel size.>

Coding schemes for the quantization of line drawings that outperform basic chain codes are investigated. First, subpixel accuracy reconstruction is obtained by a simple linear filtering of the chain code points, which achieves a factor-of-three to-four reduction in average reconstruction distortion for smooth curves. Second, the basic chain encoding schemes are generalized to a multipath-tree-searched encoding scheme. A variation of the (M,L)-algorithm is used to maintain M contending chain code paths in storage and choose the best path from these. Over a wide variety of source curves, tree-searched chain coding results in nearly an order of magnitude reduction in average reconstruction distortion over smoother chain codes. The performance improvement for curves is obtained with only a slight increase in bit rate over basic chain codes.>

The number of different digital straight lines on an N*N square pixel array is studied. The problem is equivalent to finding the number of linear dichotomies of a planar set of N/sup 2/ points of an N*N grid. For any planar set of points, adjacent pairs are defined to be pairs of points from the set such that no other point from the set lie on the line segment between them. A one-to-one correspondence between linear dichotomies and adjacent pairs is proved. Then, the adjacent pairs of points of an N*N grid are counted, and the number of linear dichotomies, as well as the number of digital straight lines, follows. An asymptotic evaluation is proved and an efficient algorithm for finding L(N) for any particular N is given.>

A robust algorithm is presented for smoothing and achieving subpixel accuracy in the reconstruction of chain coded line drawings. The algorithm does not remove sharp corners and does not need a priori knowledge of curvature statistics. A fast on-line implementation can be achieved using a table look-up. A simplified algorithm can be used for reconstructing digitized polygons.

A circular Gaussian autoregressive (CGAR) source is used as a model for closed planar curves. A class of suboptimal encoding schemes is considered which separately quantize the Fourier coefficients of the boundary. Application of rate-distortion theoretic techniques leads to parametric equations describing the optimal encoding bound. Interpretation of these equations establishes a sampling criterion and a computationally efficient transform encoding scheme for the suboptimal class. Several variants of this transform encoding scheme are suggested and compared to the encoding bound.

It is shown that, asymptotically, as the dimensionality of the space increases, the usual sample editing becomes independent. This makes an accurate calculation of performance in a high-dimensional space straightforward. Thus, with high dimensionality, the grouping given by J. Koplowitz and T.A. Brown (1981) is not necessary for determining the risk, and, similarly, the results presented by D.L. Wilson (1972) become very close to exact.

A class of quantization schemes is presented which generalizes various existing chain coding methods. For the general case, simple expressions are derived for the probabilities of the directional elements from which we can determine the number of curve points and the length of the quantized curve. These results allow for the comparison of performance of the various encoding schemes.

A general class of editing schemes is examined which allows for the relabeling as well as the deletion of samples. It is shown that there is a trade-off between asymptotic performance and sample deletion which can adversely affect the finite sample performance. A kk′ rule is proposed to minimize the proportion of deleted samples. A slight modification of the rule is introduced which allows for an exact analysis in any dimension.

The nearest neighbor rule is considered for data samples obtained by selectingN_{i}independent samples with the conditional distribution corresponding to classC_{i}. It is shown that a weighted distance rule can The nearest neighbor nde is considered for data samples obtained by selectingN_{i}independent samples with the conditional distribution corresponding to classC_{i}. It is shown that a weighted distance rule can improve the performance when the ratio ofN_{i}to the total sample size differs substantially from the{\sl a priori}probability of classC_{i}.

Letx_{1}, x_{2}, \ldotsbe a sequence of dependent random variables drawn from a probability measureP. Consider the hypothesis testH_{o}: P= P_{o} \versus H_{1}: P= P_{1}. It is shown that for a class of discrete valued processes, including Markov processes the hypothesis test can be resolved with a three-state memory. The result is generalized tom-hypothesis tests which requirem\( + 1\) states.

LetX_1,X_2, \cdotsbe a sequence of independent identically distributed Bernoulli random variables with Pr\{X_i = 1 \} = p. Consider them-hypothesis testH_1 : p < p_1, H_2 : p_1 < p < p_ 2, \cdotsversusH_m: p_{m-1} < p < p_m. It is shown that, for a time-varying finite memory,m + 1states are necessary and sufficient to resolve the correct hypothesis with a zero-limiting probability of error.

A procedure is given for optimizing the sequential estimation of a random variable in the mean-square sense, with the constraint that the data must be summarized by a finite-valued statistic. This finite-valued statistic can be considered to be the memory of the processor. The estimate is constrained to be a function of the contents of the memory and the time of the estimate. An example is given to illustrate the results.