Methods and systems for estimation of document skew in an image

Aspects of the present invention are related to systems and methods for determining a skew angle associated with a document image. According to a first aspect of the present invention, a rotation vector may be estimated for at least one layer in a vertical-edge buffer and a horizontal-edge buffer. According to a second aspect of the present invention, a rotation vector may be estimated directly from the vertical-edge buffer and the horizontal-edge buffer using a fixed-sized, progressively constrained histogram.

RELATED REFERENCES

U.S. Pat. No. 6,987,880, entitled “Efficient Document Boundary Determination,” is hereby incorporated by reference herein in its entirety.

FIELD OF THE INVENTION

Embodiments of the present invention relate generally to image processing and, in particular, to methods and systems for determination of document skew in an image.

BACKGROUND

When a document is placed on a scanner platen, the document may be placed at an angle relative to the direction of the scan. In this situation, the document content may be skewed, also considered rotated, in the scanned document page, also considered the document image or the image. Document-content skew may also arise when a document is scanned using an automatic document feeder. Additionally, content in an image may appear skewed relative to the image boundaries due to document layout attributes. That is, content may be rotated relative to an image boundary for stylistic or other reasons.

An accurate estimate of a skew angle associated with a document image may be required for many reasons. For example, some image-processing techniques may require accurately determined content boundaries for which knowledge of the document skew angle may be necessary. Furthermore, a scanning system that supports automatic skew detection and skew-angle determination may be desirable since they may be crucial to the scanning system's ability to automatically handle an arbitrarily placed document. Efficient skew estimation may be desirable for devices with limited computational resources.

SUMMARY

Some embodiments of the present invention comprise methods and systems for determining a rotation vector associated with a skew angle, of a scanned document, relative to the direction of the scan.

Some embodiments of the present invention may comprise a skew-determination system, wherein edge buffers may be generated from a normalized input image and the edge buffers may be processed by a layer processor for determination of a rotation vector associated with each layer in a layer set.

Alternative embodiments of the present invention may comprise a skew-determination system, wherein edge buffers may be generated from a normalized input image and the edge buffers may be processed directly by a constrained-histogram generator to determine a rotation vector.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description.

It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention, but it is merely representative of the presently preferred embodiments of the invention.

Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention.

When a document is placed on a scanner platen, the document may be placed at an angle relative to the direction of the scan. In this situation, the document content may be skewed, also considered rotated, in the scanned document page, also considered the document image or the image. Document-content skew may also arise when a document is scanned using an automatic document feeder. Additionally, content in an image may appear skewed relative to the image boundaries due to document layout attributes. That is, content may be rotated relative to an image boundary for stylistic or other reasons.

An accurate estimate of a skew angle associated with a document image may be required for many reasons. For example, some image-processing techniques may require accurately determined content boundaries for which knowledge of the document skew angle may be necessary. Furthermore, a scanning system that supports automatic skew detection and skew-angle determination may be desirable since they may be crucial to the scanning system's ability to automatically handle an arbitrarily placed document. Efficient skew estimation may be desirable for devices with limited computational resources.

Embodiments of the present invention comprise methods and systems for skew-angle determination, also referred to as skew determination, by page-content analysis.

Referring toFIG. 1, in some embodiments of the present invention, an input image5may be made available to a skew-determination system2for skew-angle determination. In some embodiments of the present invention, the skew-determination system2may reside in an imaging device, for example, a scanner, a multifunction peripheral (MFP), a copier or other imaging device. In alternative embodiments, the skew-determination system2may reside in a computing device. In yet alternative embodiments, the skew-determination system2may comprise multiple devices, which may, or may not, be located proximate to each other. In some embodiments of the present invention, the skew-determination system2may comprise a computer program product stored on a computer-readable storage device and a computer processor for processing the computer program product.

The input image5may be received at an image receiver4in the skew-determination system2. The image receiver4may make the input image5available to an image preprocessor6, which may preprocess the input image5to a normalized form. In alternative embodiments of the present invention, a normalized image may be received directly in a skew-determination system. The normalized image7may be made available to an edge-buffer generator8, which may generate a horizontal-strip edge buffer and a vertical-strip edge buffer9. The edge buffers9may be made available to a layer processor10, which may estimate a rotation vector11for at least one layer associated with the edge buffers9. The estimated rotation vectors11may be made available to a rotation-estimate selector12, which may select a rotation vector13from the estimated rotation vectors11, which may be referred to as a group of estimated rotation vectors or a group of rotation vectors, associated with the, at least one, layers. The selected rotation vector13may be made available to additional processes or systems by the skew-determination system2.

A rotation vector may be characteristic of a skew angle. In some embodiments of the present invention, a rotation vector may comprise a baseline value, which may be denoted β, and an associated delta, which may be denoted Δ, which may relate to a skew angle, which may be denoted θ, according to:

In some embodiments of the present invention, the image preprocessor6may comprise a down-sampler and a converter. The input image5may comprise a high-resolution image, for example, a 300 dpi (dots per inch) image, and the high-resolution, input image may be down-sampled to a lower resolution, for example, 75 dpi. The resolution to which the input image5may be down-sampled may be associated with, in some embodiments, the computational capability of the skew-determination system2. The down-sampled data may be converted to grayscale data, if necessary. For example, if the input image5is an RGB (red-green-blue) image, then an RGB-to-Y conversion, or other color-to-grayscale conversion known in the art, may be applied. In some embodiments, a ceiling on the grayscale values may be imposed. In some of these embodiments, all grayscale values greater than a threshold value may be clamped to the threshold value. An exemplary threshold value for 8-bit grayscale data may be 235. In alternative embodiments, an input image5may be converted to grayscale data first, and then down-sampled. The converted and down-sampled input image may be referred to as the normalized image7corresponding to the input image5.

The normalized image7may be made available from the image preprocessor6to an edge-buffer generator8. The edge-buffer generator8may generate a horizontal-strip edge buffer and a vertical-strip edge buffer, which may be collectively referred to as the edge buffers,9. In some embodiments described in relation toFIG. 2, the edge-buffer generator8may comprise a vertical-strip summary-measure calculator20and a horizontal-strip summary-measure calculator24, which may generate a vertical-strip buffer21and a horizontal-strip buffer25, respectively.

Referring toFIG. 3, a normalized image30may be partitioned into non-overlapping 1-by-k blocks, also considered horizontal strips, of pixels, for example, seven of which31-37are shown labeled inFIG. 3. A summary measure may be calculated for each horizontal strip by the horizontal-strip summary-measure calculator24. A horizontal-strip buffer40may be generated and the summary measures corresponding to each horizontal strip, for example,41-47corresponding to31-37, respectively, may be stored. Exemplary widths of the horizontal strips may be 8 pixels, 16 pixels and 32 pixels. In some embodiments of the present invention, the summary measure for a horizontal strip may be the mean value of the pixel values in the horizontal strip.

Similarly, referring toFIG. 4, a normalized image30may be partitioned into non-overlapping k-by-1 blocks, also considered vertical strips, of pixels, for example, five of which51-55are shown labeled inFIG. 4. A summary measure may be calculated for each vertical strip by the vertical-strip summary-measure calculator20. A vertical-strip buffer50may be generated and the summary measures corresponding to each vertical strip, for example,56-60corresponding to51-55, respectively, may be stored. Exemplary heights of the vertical strips may be 8 pixels, 16 pixels and 32 pixels. In some embodiments of the present invention, the summary measure for a vertical strip may be the mean value of the pixel values in the vertical strip.

Referring again toFIG. 2, a vertical-edge detector22and a horizontal-edge detector26may be applied to the vertical-strip buffer21and the horizontal-strip buffer25, respectively. In some embodiments of the present invention, the edge detectors22,26may comprise local differencing and thresholding. In an exemplary embodiment, the vertical-edge buffer23, which may be denoted Er,cV, may be generated according to:

Er,cV={1,Br,cV⊗DV>θV0,otherwise,
and the horizontal-edge buffer27, which may be denoted Er,cH, may be generated according to:

Er,cH={1,Br,cH⊗DH>θH0,otherwise,
where r, c designates the row and column position within a buffer, Br,cVand Br,cHdenote the vertical-strip buffer and the horizontal-strip buffer, respectively, Dvdenotes the vertical convolution kernel [−1 1], DHdenotes the horizontal convolution kernel [−1 1]T, θVand θHdenote a vertical-buffer threshold value and a horizontal-buffer threshold value, respectively, anddenotes convolution. In some embodiments, θV=θH, and in some of these embodiments, θV=θH=3.

Referring again toFIG. 1, the layer processor10may estimate a rotation vector for at least one layer. The first layer of a vertical-edge buffer is the location of the first non-zero entry, from the left and the right, in each row. If a row contains no edges, then a null-edge marker, indicating that the row contains no edges, may be associated with the row. The first layer of a horizontal-edge buffer is the location of the first non-zero entry, from the top and the bottom, in each column. A null-edge marker may be associated with any column that does not contain an edge. The first layer may be viewed as the outermost edges in each of the two orthogonal directions defining the image coordinates, that is, the top, bottom, left and right. A subsequent layer may be determined by replacing all locations corresponding to previous layers with a zero.

An exemplary layer processor may be described in relation toFIG. 5. In these embodiments, the layer processor may make, for each of M layers, λi, in a layer set which may be denoted Λ=[λ1, λ2, . . . , λM], the vertical-edge buffer70associated with the current layer available to a vertical-leading-and-trailing edge locator72and the horizontal-edge buffer71associated with the current layer available to a horizontal-leading-and-trailing edge locator76. The vertical leading and vertical trailing edges are the left and right edges, respectively, and the horizontal leading and horizontal trailing edges are the top and bottom edges, respectively. The vertical-leading-and-trailing edge locator72may determine the edge locations73of the leading and trailing edges in the current vertical-edge buffer70by examining the rows in the current vertical-edge buffer70independently, and the horizontal-leading-and-trailing edge locator76may determine the edge locations77of the leading and trailing edges in the current horizontal-edge buffer71by examining the columns in the current horizontal-edge buffer71independently.

A vertical-edge-list generator74may generate two lists: a left list containing the column indices of the first edge, from the left, in each row or the null-edge index if there is no edge in a row; and a right list containing the column indices of the last edge, from the left, in each row or the null-edge index when no edge is present in a row. The horizontal-edge-list generator78may generate two lists: a top list containing the row indices of the first edge, from the top, in each column or the null-edge index if there is no edge in a column; and a bottom list containing the row indices of the last edge, from the top, in each column or the null-edge index if there is no edge in a column The edge lists75,79generated by the vertical-edge-list generator74and the horizontal-edge-list generator78may be made available to a baseline processor80. The baseline processor80may be understood in relation toFIG. 6.

The baseline processor80may compute, for the current layer, a candidate rotation angle for each baseline, βi, in an estimating set of baselines which may be denoted B=[β1, β2, . . . , βN]. In an exemplary embodiment, the set of baselines may be B=[32,64,128,256,512,576], which allows for the resolution of angles as small as 0.1°. For each baseline, the baseline processor80may make available, to a folded-delta calculator90, the current-layer vertical-edge lists75(left, right), the current-layer horizontal-edge lists79(top, bottom) and the current baseline88. The folded-delta calculator90may compute “folded” deltas91for each current leading-trailing set. The term “folded” is used to indicate that the angle estimates are constrained to the interval [−45°, 45°]. The baseline may be considered the x component of a tangent vector associated with a rotation angle, and a measured delta may be considered the y component of the tangent. The delta may be the local displacement from the local baseline. The folded-delta calculator90may traverse an edge list, for example, a left-edge list, also referred to as a left list, a right-edge list, also referred to as a right list, a top-edge list, also referred to as a top list, and a bottom-edge list, also referred to as a bottom list, element-by-element using the current baseline value. When a non-null edge coordinate is encountered, the edge list may be checked at an offset of the current baseline value to determine if a valid edge is present at that position. If a valid edge is present at that position, the signed difference in the coordinates may be the local delta. The coordinate of the current position may be subtracted from the coordinate at the baseline offset where the valid edge is detected. When a null-edge index is encountered at either end of the baseline, no delta is calculated at that position.

FIG. 7illustrates the relationship for the delta determination.FIG. 7depicts a portion100of an exemplary horizontal-edge buffer. The non-edge pixels are indicated in gray, for example,101. The edge pixels are indicated in white, for example102. An edge list corresponding to the horizontal-edge buffer would list, for each column, the row in which the edge is positioned. For a current baseline length, as shown104,108, when the edge list entry corresponding to edge location103is examined, the edge list entry at an offset corresponding to the current baseline104is then examined to determine if a valid edge exists at that offset. The entry in the edge list at that offset will correspond to edge location105, and the delta106may be determined by examining the relative difference between the corresponding edge-list entries. Similarly, when the edge list entry corresponding to edge location107is examined, the edge list entry at an offset corresponding to the current baseline108may be then examined to determine if a valid edge exists at that offset. The entry in the edge list at that offset will correspond to edge location109, and the delta106may be determined by examining the relative difference between the corresponding edge-list entries

When a local delta is larger than the current baseline, the angle magnitude is greater than 45°, and a folding operation may be performed. The folding operation may be illustrated pictorially in relation toFIG. 8. The solid black line110represents (in image coordinates) edge locations in an edge buffer, in this example, a horizontal edge buffer. When the edge point at location112is examined, a determination may be made as to whether or not an edge point is present at an orthogonal offset to the current baseline113. In this example, an edge point114is located at an offset distance of Δ1115. Since Δ1115is less than the length of the current baseline113, the offset distance, Δ1115, is recorded.

However, considering the edge point at location116, the edge point118is located at an offset Δ2119from the baseline117. In this example, Δ2119is greater than the length of the current baseline117. Therefore, the cotangent is representative of the rotation angle constrained to the interval [45°, 45°]. In order to consistently associate the offset with the current baseline117, the offset Δ2119needs to be rescaled to the baseline length120so that the appropriate offset Δ2′121may be recorded. By exploiting similar triangles, it is readily seen that

Δ⁢⁢2′=-β2Δ2,
where β is the length of the current baseline. Flipping the sign of Δ2′121gives an offset123consistent with the other deltas associated with the current baseline. As seen inFIG. 8, this is, effectively, a folding of the point118which brings the rotation angle within the constraint.

Referring again toFIG. 6, the deltas91determined by processing each of the four edge lists may be accumulated by a delta-histogram generator92to form a delta histogram93. The delta histogram93may comprise 2βi+1 bins, where βiis the length of the current baseline and the bins may be mapped to the closed integer interval [−βi, βi].

The delta histogram93may be made available to a constrained-mode detector94which may determine, using any of the many know-in-the-art peak detection methods, the peak within a current envelope89expressing a lower-bound upper-bound pair of bin indices, which may be denoted [lbi, ubi]. This peak may be referred to as the constrained mode95and may be determined in some embodiments, by determining the bin index, within the current envelope89, that has maximum count. Initially, for the first baseline length, the envelope may encompass the entire histogram. Thereafter, it may be constrained by the current rotation estimate97projected to the scale of the next baseline.

The constrained mode95may be made available to a rotation-vector calculator96, which may determine a rotation vector97associated with the current baseline88. For a baseline iteration, i, and a mode index, denoted mdindexi, the rotation vector97may be given by [βi, Δi], where Δt=bincentersi(lbi+mdindexi−1) and bincentersimaps the histogram bin centers to displacement values. The calculated rotation vector97may be made available to an envelope calculator98that calculates the envelope for the next baseline iteration, and the rotation vector97may be recorded for the current baseline.

The envelope calculator98may compute the next envelope99for the next baseline iteration, i+1. The bin index of the center of the next envelope99, which may be denoted eci+1, may be computed by mapping the current delta estimate, Δi, into the histogram range of the next iteration according to:
eci+1=s·Δi+βi+1+1,
where

s=βi+1βi.
In some embodiments of the present invention, the envelope interval may be determined according:
lbi+1=max(eci+1−n,mnindi+1)
and
ubi+1=min(eci+1+n,mxindi+1),
where mnindi+1and mxindi+1are the first and list bins, respectively, of the histogram range for the next iteration, and the max and min functions constrain the envelope to a valid histogram range. In some embodiments of the present invention, n=2.

Referring again toFIG. 5, from the rotation-vector estimates for all baselines81at a given layer, a most-likely rotation vector83, also referred to as a candidate rotation vector corresponding to the current layer, may be selected for the current layer by a rotation-vector selector82. In some embodiments, the estimate that is most precise and most likely may be selected. In some embodiments, the rotation-vector selector82may scale the estimates for all baseline iterations to the maximum baseline for comparison. A mean of the scaled estimates may be computed, and if the difference between the mean and the final (most precise) estimate is less than threshold, then the final vector may be selected as the best estimate. Otherwise, the mean may be selected as the best estimate. In alternative embodiments, the final, most precise estimate may be selected by the rotation-vector selector82as the candidate rotation vector83corresponding to the current layer. In still alternative embodiments of the present invention, the rotation-vector selector82may select the mode of the scaled estimates as the candidate rotation vector83corresponding to the current layer. In yet alternative embodiments, a weighted average of the scaled estimates may be selected as the candidate rotation vector83corresponding to the current layer. In some of these embodiments, a weight associated with a scaled estimate may be based on the length of the associated baseline.

The current layer, and any intervening layers to the next layer in the layer set, may be nullified by a vertical-layer nullifier84and a horizontal-layer nullifier86. The vertical-edge buffer85for the next layer and the horizontal-edge buffer87for the next layer may be processed by the layer processor10.

Referring toFIG. 1, from the rotation-vector estimates11for all layers, a final rotation-vector estimate13may be determined by a rotation-estimate selector12. In some embodiments, a weighted mean of the rotation-vectors estimates11from the layers may be determined according to:

R=∑λ∈Λ⁢rλ⁢wλ∑λ∈Λ⁢wλ,
where wλ=e1/λand rλis a rotation vector associated with a layer λ in the layer set Λ.

In alternative embodiments of the present invention, a vertical-edge buffer and a horizontal-edge buffer may be processed directly. These embodiments may be understood in relation toFIG. 9. In some embodiments of the present invention, an input image141may be made available to a skew-determination system140for skew-angle determination. In some embodiments of the present invention, the skew-determination system140may reside in an imaging device, for example, a scanner, a multifunction peripheral (MFP), a copier or other imaging device. In alternative embodiments, the skew-determination system140may reside in a computing device. In yet alternative embodiments, the skew-determination system140may comprise multiple devices, which may, or may not, be located proximate to each other. In some embodiments of the present invention, the skew-determination system140may comprise a computer program product stored on a computer-readable storage device and a computer processor for processing the computer program product.

The input image141may be received at an image receiver142in the skew-determination system140. The image receiver142may make the input image141available to an image preprocessor144, which may preprocess the input image141to a normalized form. In alternative embodiments of the present invention, a normalized image may be received directly in a skew-determination system. The normalized image146may be made available to an edge-buffer generator148, which may generate a horizontal-strip edge buffer and a vertical-strip edge buffer, which may be referred to collectively as edge buffers,150. The edge buffers150may be made available to a constrained-histogram generator152, which may estimate a rotation vector154by computing entries, in progressively constrained histograms, for each edge point in the edge buffers150using a sequence of baselines. The estimated rotation vector154may be made available to additional processes or systems by the skew-determination system140.

A rotation vector may be characteristic of a skew angle. In some embodiments of the present invention, a rotation vector may comprise a baseline value, which may be denoted β, and an associated delta, which may be denoted Δ, which may relate to a skew angle, which may be denoted θ, according to:

In some embodiments of the present invention, the image preprocessor144may comprise a down-sampler and a converter. The input image141may comprise a high-resolution image, for example, a 300 dpi (dots per inch) image, and the high-resolution, input image may be down-sampled to a lower resolution, for example, 75 dpi. The resolution to which the input image141may be down-sampled may be associated with the computational capability of the skew-determination system140. The down-sampled data may be converted to grayscale data, if necessary. For example, if the input image141is an RGB (red-green-blue) image, then an RGB-to-Y conversion, or other color-to-grayscale conversion known in the art, may be applied. In some embodiments, a ceiling on the grayscale values may be imposed. In some of these embodiments, all grayscale values greater than a threshold value may be clamped to the threshold value. An exemplary threshold value for 8-bit grayscale data may be 235. In alternative embodiments, an input image141may be converted to grayscale data first, and then down-sampled. The converted and down-sampled input image may be referred to as the normalized image146corresponding to the input image141.

The normalized image146may be made available from the image preprocessor144to an edge-buffer generator148. The edge-buffer generator148may generate, as described in relation to the embodiments described in relation toFIG. 1, a horizontal-strip edge buffer and a vertical-strip edge buffer150. In some embodiments, the edge-buffer generator148may comprise, as described above, a vertical-strip summary-measure calculator and a horizontal-strip summary-measure calculator, which may generate a vertical-strip buffer and a horizontal-strip buffer, respectively.

The edge buffers150may be made available to the constrained-histogram generator152. Some embodiments of the constrained-histogram generator152may be understood in relation toFIG. 10. For each baseline length, also referred to as a baseline, βi, in an estimating set of baseline lengths B=[β1, β2, . . . , βN], a histogram, of delta values for each edge in an edge buffer, may be generated. In an exemplary embodiment of the present invention, the set of baselines may be B=[32,64,128,256,512,576], which allows for the resolution of angles as small as 0.1°.

A fixed histogram size may be selected and used for each baseline iteration. In some embodiments of the present invention, a common memory may be used for the fixed-size delta histogram for each baseline iteration. In some embodiments, the delta histogram may comprise 2β1+1 bins, where β1is the length of the shortest, or first, baseline and the bins may be mapped to the closed integer interval [−β1, β1]. In these embodiments, the first iteration may cover the estimation interval [−45°, 45°].

The histogram size may be initialized170, and a histogram-center offset may be initialized172to zero. A determination174may be made as to whether or not there are remaining baseline lengths to process. If all baselines in the baseline set have been processed175, then the constrained-histogram generation process may terminate176, and the most recent estimate of the rotation delta may be used to determine the rotation vector.

If there is a baseline in the baseline set that has not been processed177, then the histogram may be cleared178and a constrained histogram associated with the next baseline length, considered the current baseline, in the baseline set may be generated. Clearing178the histogram may comprise, in some embodiments, setting the accumulation count in each bin to zero.

A determination180may be made as to whether or not there are remaining edges, in the edge buffers, to process at the current baseline length. If there are181remaining edges, a delta value associated with the current baseline may be measured182. The delta value may be measured as described in relation to the embodiments described in relation toFIG. 1. The measured delta may be adjusted184based on the current histogram-center offset. Initially, the histogram center may be set to zero, thereby requiring no adjustment. After each baseline iteration, the histogram-center offset for the next baseline iteration may be updated190according the estimated rotation delta from the current iteration. Thus, an adjusted delta, which may be denoted Δadjustedmay be determined from a measured delta, which may be denoted Δmeasured, measured according to:
Δadjusted=Δmeasured−CenterOffset,
where CenterOffset denotes the current histogram-center offset value. Therefore, fixing the histogram size and adjusting the histogram center effectuates a constrained window of delta values with progressively increasing baseline lengths. The adjusted delta value is accumulated186in the delta histogram associated with the current baseline length, and a determination180is made as to whether or not there are remaining edges in the edge buffers to process.

When all edges in the edge buffers have been processed187at the current baseline, then a rotation delta may be estimated188for the current iteration. In some embodiments of the present invention, the rotation delta may be estimated by finding the global histogram mode, mapping the mode index through a list of bin centers and adjusting for the center offset. The histogram-center offset may be updated190, for the next iteration, to the estimated rotation delta. Thus, the rotation vector for the current iteration may be given by [βi, Δi], where Δi=bincentersi(lbi+mdindexi−1) and bincentersimaps the histogram bin centers to displacement values.

A determination174may then be made as to whether or not there are remaining baselines to process.

Embodiments of the present invention wherein a vertical-edge buffer and a horizontal-edge buffer may be processed directly may be further understood in relation to an example depicted inFIG. 11.FIG. 11depicts a fixed-size delta histogram210associated with a first baseline200of length β1=8. The delta histogram210has 17 bins211-227associated with delta values in the integer interval [−8, 8] and corresponding to rotation angles in the interval

[tan-1⁡(-88),tan-1⁡(88)]=[-45°,45°].
The precision of a rotation angle estimate at this iteration is less than 7.125°.FIG. 11shows an edge point208for illustration. At the first baseline iteration, a delta at the baseline offset β1=8 will be accumulated in the delta histogram210at the bin, for example, bin222, relative to the histogram-center offset, which is zero for the first iteration.

If the rotation delta estimate from the first baseline iteration is the rotation delta associated with bin222, then the delta histogram230associated with a second baseline202of length β2=16 is centered239around that delta offset determined from the first baseline iteration. Thus, the delta histogram230has 17 bins231-247associated with delta values in the integer interval [−2, 14] and corresponding to rotation angles in the interval

If the rotation delta estimate from the second baseline iteration is the rotation delta associated with bin241, then the delta histogram250associated with a third baseline204of length β3=32 is centered259around that delta offset determined from the second baseline iteration. Thus, the delta histogram250has 17 bins251-267associated with delta values in the integer interval [8, 24] and corresponding to rotation angles in the interval

If the rotation delta estimate from the third baseline iteration is the rotation delta associated with bin261, then the delta histogram270associated with a fourth baseline206of length β4=64 is centered279around that delta offset determined from the third baseline iteration. Thus, the delta histogram270has 17 bins271-287associated with the delta values in the integer interval [28, 44] and corresponding to rotation angles in the interval

If the fourth baseline is the last baseline in the baseline set and the rotation delta estimate from the fourth baseline iteration is the rotation delta associated with bin280, then the rotation vector is [64, 37] corresponding to a rotation angle of 30.0°.

Table 1 summarizes the constrained histogram bin mappings for this example.