Low latency correlation

Details Low latency correlation Low latency correlation

2000-06-09

2002-04-16

Au, Amelia M. (Department: 2623)

Image analysis

Image transformation or preprocessing

Correlation

C382S304000, C382S209000

Reexamination Certificate

active

06373994

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
This invention relates generally to correlation of pixelated images in the digital domain, and more specifically to a correlator enabling low-latency image processing, advantageously in self-contained fashion on a digital signal processor (DSP) deployed on an integrated circuit chip.
BACKGROUND OF THE INVENTION
Devices having a tracking capability (such as a hand-held scanner) require navigation functionality in order to maintain awareness of the device's present position on a piece of work. The surface texture of the work can provide a frame of reference for navigation. A known effective technique for enabling such navigation is to shine light at an angle on the work, and to process the resulting reflection, which will include the surface texture shadow of the work. This technique enables navigation using, for example, the fiber texture on the surface of a piece of paper from which an image is being scanned.
Part of such a navigation technique is correlation. In a series of frames representing portions of the image captured during motion across the image, correlation produces a numerical representation of “how much the current frame looks like the previous frame.” Deriving this numerical representation is analogous to laying a photograph slide of a current image over a negative of a reference image, and then moving the slides around until the least amount of light gets through. The numerical representation sought in correlation corresponds actually to the amount of light that actually gets through at the nadir point and thus quantifies the “best fit” between the two images.
Correlation is typically performed in the digital domain in accordance with techniques described with reference to
FIGS. 1A-1D
. Reference image
101
on
FIG. 1A
comprises, for example, a 6×6 array of reference pixels R
0
-R
35
. Each reference pixel R
0
-R
35
will be understood to be a digital value representative of the information seen by that pixel when the image was captured. Compare image
102
on
FIG. 1A
comprises a 6×6 array of compare pixels C
0
-C
35
clipped for the purposes of correlation to a 4×4 array
103
. Referring now to FIG.
1
B), compare array
103
is overlayed “dead center”on reference image
101
, generating 16 calculations
104
as shown on FIG.
1
B. In
FIG. 1B
, exemplary use is made in calculations
104
of the function (R
x
-C
y
)
2
, although other functions of R and C may be used in correlation, such as |R
x
−C
y
|.
The aggregate sum of all 16 calculations
104
on
FIG. 1B
goes forward to form output value O
4
on result surface
105
depicted on FIG.
1
D. With further reference to
FIG. 10
, result surface is typically a 3×3 array of output values O
0
-O
8
.
Turning now to
FIG. 1C
, array
103
is now overlaid, for example, on reference image
101
one reference pixel to the right of dead center. The aggregate sum of calculations
104
on
FIG. 1B
corresponding to this overlay yields output value O
5
on result surface
105
on FIG.
1
D. With further reference to
FIG. 1C
, array
103
is now overlaid, for example on reference image
101
one pixel diagonally up and to right of dead center. The aggregate sum of calculations
104
on
FIG. 1B
corresponding to this overlay yields output value O
2
on result surface
105
on FIG.
1
D.
The result of the foregoing process is that result surface
105
on
FIG. 1D
comprises a series of output values O
0
-O
8
each representative of correlation between array
103
and the corresponding patch of reference image
101
when array
103
is “moved around” reference image
101
. The lowest value of O
0
-O
8
is the “best fit” and is the correlation value for reference image
101
and compare image
102
.
Although exemplary use in
FIGS. 1A-1D
has been made of a 6×6 reference image
101
and compare image
102
(the compare image clipped to 4×4 to facilitate “movement” over reference image
101
) in order to generate a 3×3 result surface, there is no limitation on these numbers to perform correlation according to the foregoing technique. Any size of reference image and compare image may be correlated, and the amount of “movement” enabled will dictate the size (and resolution) of the result surface.
Correlators of the current art using this technique typically store entire frames of digitized input pixel values in memory and then correlate the frames using an off-chip processor. Calculations are generally done serially for each output value over the result surface, calculations for the next output value not started until the previous output value has been determined. This results in a long latency from completion of the digitization of a frame until the result surface against the previous reference frame is calculated. There is also a high hardware overhead requiring at least two memory regions for the reference frame and the compare frame.
This type of batch processing causes slowdowns that could be remediated by more of a continuous and parallel processing of correlation calculations. It would also be advantageous to be able to perform correlation on-chip, which might become more feasible if the hardware requirements were optimized.
There is therefore a need in the art to perform correlation calculations in more of a “streaming” fashion, preferably on-chip.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a correlator in which indexed patches of pixels on the current and reference frames are presented to correlation cells for processing in a “streaming” fashion.
The inventive correlator derives its inventive concept from recognizing, in the current examples illustrated on
FIGS. 1A-1D
that the pixel values in compare array
103
(pixel values C
7-
C
10
, C
13-
C
16
, C
19 -
C
22
, and C
25
-C
28
on
FIG. 1A
) are each used once and only once, in every calculation of an output value O
0
-O
8
. Thus, for example, if architecture is used where pixel value C
7
is presented to nine calculators concurrently, and the appropriate reference pixel values are sent at the same time to the calculators, the nine calculators may individually execute a different calculation in unison, where each of the calculations is one of those required to determine a corresponding one of the output values. Therefore, C
7
is not needed again, all of the calculations requiring C
7
now having been made.
Repeating this process for a stream of compare pixel values C
7
-C
10
, C
13
-C
16
, C
19
-C
22
and C
25
-C
28
(as used in the example of
FIG. 1A
) enables all output values O
0
-O
8
to be determined simultaneously after 16 iterations of the concurrent process. This “streaming” process dramatically reduces the latency required to perform these calculations in comparison to corresponding “batch” systems of the prior art. The only difference over the prior art process described in the previous section is that according to the inventive correlator, none of the output values are known until the 16th and final iteration is complete, whereupon all output values O
0
-O
8
manifest themselves concurrently. In contrast, in the prior art, calculation of one output value is generally completed before the next is started. This difference is not disadvantageous, however, since the next step in analysis of output values is typically to identify the lowest one. It does not matter, therefore, if the values of output values manifest themselves serially or concurrently, since identification of the lowest value cannot be made until all output values are known.
While the inventive correlator is used for image processing (two dimensions) in a preferred embodiment, there is no reason why its principles will not apply to n-dimensional problems.
The architecture of the inventive correlator is, in a preferred embodiment, an array of correlation cells each containing a delay pipe, a math unit and an accumulator. An array of these correlation cells are tiled together to allow simultaneous processing by all cells. The array

Affiliated with

Also associated with

Rating

Low latency correlation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Low latency correlation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low latency correlation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2874377