A geometric approach to subpixel registration accuracy

COMPUTER VISION, GRAPHICS, AND IMAGE PROCESSING 4 0 , 3 3 4 - 3 6 0

(1987)

A Geometric Approach to Subpixel Registration Accuracy CARLOS A. BERENSTEIN,* LAVEEN N . KANAL,* DAVID LAVINE, AND ERIC C. OLSON L. N. K. Corporation, Suite 306, 6811 Kenilworth Ave., Riverdale, MD 20737

Received November 11, 1984; accepted March 5, 1987 A method for estimating the translation offset between a pair of images to subpixel accuracy is described and analyzed. This method assumes the extraction of a digital edge representing a straight line in the image and then computes the best real line which could have given rise to the digital line. The key difference between this method and other approaches to subpixel fitting is that our method uses subpixel line location to estimate a digital model such as the digital line and then fits the digital model to the image while other approaches directly fit a continuous model to the image or an image related object such as a cross correlation matrix. The present paper lays a theoretical foundation for this digital approach. This technique can be applied in a variety of remote sensing and industrial vision problems requiring subpixel registration accuracy. 9 1987 Academic Press, Inc. 1. INTRODUCTION TO GEOMETRIC REGISTRATION Matching edges in sensed and reference images can be used for registration. The degree to which the position of a real-world edge, such as a field boundary, can be located in imagery depends heavily upon one's knowledge of the scene and the sensors. Edge detectors can be used to locate reasonable candidates for edge points and then an edge can be more precisely fit using these points. Alternatively, an estimate of subpixel edge location can be formed directly from the grey levels [5]. H y b r i d approaches may also be adapted. We study the accuracy attainable using the first of these approaches, which we call the geometric accuracy approach. Before launching into a description of our model for geometric accuracy, it is useful to consider those aspects of the registration problem we wish to capture in our model. The heart of our approach is to estimate the position of an image edge to subpixel accuracy and use this information to define a translation between the sensed a n d the reference image. In the ideal case, the grey levels on each side of the edge are constant off the edge pixels and the edge pixel grey levels are a simple weighted average o f these two grey levels. If all grey levels are possible and the edge pixels are all known then the position of the edge can be exactly determined b y solving a system of linear equations expressing the observed grey levels as a function of the edge parameters. Such a situation is clearly unrealistic but it serves as a starting point for approximation. Most current methods for attaining subpixel accuracy employ some type of interpolation of the correlation function. If such a method is to achieve subpixel accuracy, the digital correlation function must be able to achieve pixel accuracy. In *University of Maryland; partially supported by NSF grants. 334 0734-189X/87 $3.00 Copyright 9 1987 by Academic Press, Inc. All rights of reproduction in any form reserved.

SUBPIXEL REGISTRATION ACCURACY

335

our work, we assume pixel accuracy is available either through correlation or other methods. Thus, in the simple case of a one-dimensional shift any real world point can be determined to fie within a 3 • 1 pixel strip. Our results can be improved drastically if we assume we know, from registration, we are in the correct pixel, but this is a highly unrealistic assumption. The analysis described in this paper pertains to the problem of one-dimensional translations. For long fines this is not particularly restrictive since the two-dimensional problem can be easily decomposed into one-dimensional shift estimates. In the line location estimation problem, we are trying to locate a real world line y = m x + b in the image. A shift (Ax, Ay) between real world and image coordinates yields a line y = m ( x - A x ) + b + A y in the image. This may be written as y = m x + b + ( A y - m Ax) which is the original fine shifted only in the y direction and by an amount y " m Ax, when the line is infinite. Our I - d estimation procedures enable us to estimate Ay - m Ax. Given two lines, we can solve (possibly using least squares) for Ax and Ay separately. From this point on, we will confine ourselves to 1 - d shifts. The models described here assume a set of pixels labelled edge pixels are provided by an edge detection procedure. Three cases can be considered. First, the set of edge pixels are exactly the digital edge corresponding to a fine in the real world. This model is unduly restrictive since an edge which comes very near a pixel boundary can show up in the next pixel due to noise. Second, one could consider a model in which the set of edge pixels given is a subset of the digital edge corresponding to the real edge. This approach is more realistic since it enables us t o discard some pixels whose classification as edge pixels is in doubt. Finally, we could give a model in which some pixels lying on the digitization of the real edge are given and some incorrect pixels are given. For the first model, in which a complete digital edge is available, a tight upper bound for the registration error as a function of the line parameters is given (Section 3). This allows us to give some probabilistic error estimates for the family of all digital lines (Section 7). This analysis provides the firm basis for the study of the second and third models, but since our results in these cases are not so complete yet, we leave them to future reports. We notice nevertheless that in many applications one only finds rather short digital fines, with information only on 10 to 20 pixels, and hence occasionally, e.g., if no analytic formulas are available, it might be perfectly justified to rely on computer-aided counting of possibilities when this counting is not too time consuming. As a first step in our analysis we parametrize the chain codes of digital fines see (Section 2 for definitions) by four parameters N, q, p, s as proposed by [2] and use some formulas from the same paper. We present alternate proofs in Appendix A. There is an excellent report [8] which seems to be generally unnoticed, and where there are several characterizations of those chain codes corresponding to digital lines among all possible strings of O's and l's. We do not use their results explicitly but they seem essential in the analytic study of the second and third models. We point out that both in [2, 8] as in other work in the literature, no attention is paid to the counting of all digital fines of finite length. It is not enough to count lines through the origin as done in [8] and since our probabilistic analyses require such count, we give an exact formula for the number of all fines in Section 6, which is not a straightforward generalization of the formula for fines through the origin. We also

336

BERENSTEIN ET AL.

provide asymptotic bounds for the number of lines of a given length as well as provide grounds for the reasonable conjecture that this number L ( N ) is of the form

L ( N ) = N3/~r 2 + O ( N Z l o g N ) . A proof of this conjecture will appear shortly. A brief outline of the notation used is found in Appendix B. 2. DIGITAL STRAIGHT LINE SEGMENT PARAMETER ESTIMATION Estimation of the location parameters of a real world edge giving rise to an image edge is discussed in this section. The ideas discussed are a summary of those parts of [2] which are useful for subpixel registration. Their basic result is a determination of all lines whose digitization is a specified chain code. In later sections, this set of lines will be used to derive error bounds on registration accuracy. Several line digitization procedures are commonly used in graphics and image processing. Given a line segment in the upper right-hand quadrant of the plane, with slope and y-intercept both between 0 and 1 and strictly less than 1, we define its digitization as follows: To each intersection (a, b) between the line and a line x = a, a an integer, we associate the pixel with lower left-hand comer (a, tbl) (see Fig. 2.1). The chain code of the sequence of pixels with lower left-hand coordinates (0, bo), (1, bx) . . . . , ( N, bN) is the sequence Cl,..., c N, where

c , = {01

if[bi]=[b'-l])otherwise.

(1)

The restrictions on the slope and y-intercept of the lines under consideration are made for simplicity of presentation. By symmetry the results can be extended to remove these conditions. To determine the lines with specified chain code, it is useful to have a parameterization of the set of all chain codes of digital line segments resulting from digitizing the class of lines specified above. In [2] the following parameterization is given. A digital line segment chain code (c I . . . . , CN) is given by a quadruple of integers (N,p,q,s).

J

0

v

--

~176

FIG. 2.1. Chaincode of a digitalline. The digitizationof the dark diagonalline has pixels with lower left-hand vertices (0, 0), (1,0), (2, 0), (3,1), (4, 1), (5,1). The resultingchain code indicatedby the arrows is 00100.

SUBPIXEL REGISTRATION ACCURACY

337

N is the length of the chain code, i.e., the number of O's and l's. We note that not every string of O's and l's is generated by a line segment. For a characterization of those that are, see [10]. Next q is defined to be the smallest integer such that there exists an extension cN+l, cN+2,..., with Cl, C2, c3,.., periodic with period q. Define p to be the number of ones in a period. The fourth parameter, s, provides a normalization of the chain code for one period. Geometrically, s may be interpreted as follows. Any chain code corresponds to a line segment with rational slope. Among all such segments, select the slope p / q with p A q = 1 which has the minimum q. This q is the period. The standard chain code corresponding to the first period of this chain code is the chain code of the digitization of the first q pixels of the line through the origin, y = ( p / q ) x . The ith element ci, of this chain code is given by ci = [i(p/q)]

[(i-

-

1)(p/q)],

i = 1,2 . . . . . N

The parameter s, of a code string of length N, is defined by the condition that the standard code string of p / q starts at the (s + 1)th element of the original chain code. Given the parameters N, q, p, s of a codestring, the ith element of the original code string can be obtained by ci

=

l(i

-

s)(p/q)l

-

t(i

-

s

-

1)(p/q)],

i = 1,2 . . . . . N

The parameters satisfy the constraints 0 < p < q < N and 0 < s < q - 1. A point which will be particularly important for the registration problem is that there are constraints on the parameters other than the above inequalities. These additional constraints are described in Appendix A. Our interest in these matters stems from the need to enumerate the digital lines satisfying various conditions. If it were not for these messy constraints, the enumeration problems would often be straightforward. Without these additional constraints for fixed N, we would obtain all digital line segments of length N by independently varying s, p, and q subject to the constraints0 Error

0.5000 0.2500 0.1666 0.1250 0.1000 0.0833 0.0714 0.0625 0.0555 0.5000 0.0000

0.0000 0.0147 0.0294 0.0735 0.1323 0.2794 0.3676 0.6323 0.7794 0.9412 1.0000

Note. Given an entry, a, in the first column, the corresponding entry in the second column is the percentage of digital lines of length ten whose maxim u m registration error exceeds a. Line length = 10.

354

BERENSTEIN ET AL.

which is, in fact, in tune with the upper and lower bounds obtained in Proposition 9, namely 0.72/N and 1.09/N, respectively. It would be very interesting to show that E ( N ) has the same asymptotic behavior as/~(N). We remark that though the asymptotic behavior of the expected value of the offset with respect to the invariant measure /~ is very hard to obtain due to the nature of the formulas from Section 5, for any concrete value of N it is perfectly possible to compute this expected value using the explicit nature of the formulas for the measure ~(fl) of the quadrilateral associated to any digital line. We have done this for N = 10 and obtained the error probabilities given in Table 3. CONCLUSIONS This paper is concerned with the accuracy of registration based on line matching given that the correct digital line is detected, i.e., there are no missing or extraneous pixels. An expected error of approximately 0.1 pixels in the estimation of the vertical offset of a line was derived. In this approach, a straight edge in a scene is represented as a digital line in a sensed image and a real line whose digitization is this digital line is selected. The real line is then matched to the corresponding line in the reference image. Since this paper was written, we have conducted simulation studies [1] on the accuracy of this approach. The approach was also extended to the case where not all pixels in the digitization were correct. In addition, those extensions made use of grey scale information. In that work, the average error in the vertical offset estimation was about 2~ of a pixel for digital lines of length ten. This approach to subpixel accuracy appears promising for problems in both image reigstration and high accuracy edge detection. Extensions of this approach to curved edges is a natural direction for further work. In the process of obtaining the error estimates for edge accuracy determination, we have obtained an exact formula for the number of digital lines of a given length. Up to now, only the count of the number of digital lines which are digitizations of real lines through the origin have been computed. A natural question that arises in this context is the counting of various other digital geometric objects. Since the formula counting all digital lines is complicated, we give heuristic reasons that support the conjecture that the asymptotic behavior of this number of lines is N3/rr 2. For N = 100, the exact formula and the conjectured asymptotic behavior differ only by 0.5%. We consider the problem of proving this conjecture an interesting mathematical problem. APPENDIXA Here we provide the proofs of the formulas (4)-(10) of Section 2. An alternate proof appears in [2]. We begin with an observation from [10] which remains valid for lines of finite length N due to the fact that all digital lines arise out of the digitization of lines of the form y = p / q x + m / q , 0