Image correspondence techniques using serial neighborhood processing

• US 4,590,607 A
• Filed: 07/16/1985
• Issued: 05/20/1986
• Est. Priority Date: 09/17/1982
• Status: Expired due to Fees

• Current Assignee: Environmental Research Institute Incorporated
• Original Assignee: Environmental Research Institute of Michigan
• Inventors: Kauth, Richard J.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US06/755,706
• Time in Patent Office: 308 Days
• Field of Search: 382/46, 382/41, 382/45, 382/44, 382/49, 382/23, 358/105, 358/107, 358/282, 358/284, 356/2
• US Class Current: 382/294
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A serial neighborhood processing system, preferably employing a pipeline of individually programmable stages, is used to detect image correspondence between multiple frames of image data. Similar features in each frame are extracted utilizing a series of dilation and erosion sequences. In particular, landmarks in each frame are condensed to single image points having exactly one corresponding point in the other frame surrounding it within a given mathematical distance. The second frame of pixel data is registered with the first frame as a function of the spatial relationship between these pairs of matched points in the two reduced frames. A comparison is made between the first frame and the registered second frame to detect differences therebetween. Motion detection, stereo projection, registration of multidate Landsat imagery and matching images of electrophoretic gels are examples of particular uses for the techniques disclosed.

Claims

1. A method of detecting correspondence between multiple frames of image data, each frame represented by a matrix of pixels, said method comprising the steps of:

transforming the matrix representing a first frame of image data in at least one serial neighborhood processing stage by a predetermined number of electronic erosion sequences thereby reducing the matrix to a plurality of discrete islands of pixels;

transforming the matrix representing a second frame of image data in at least one serial neighborhood processing stage by performing the predetermined number of electronic erosion sequences to reduce the matrix associated with the second frame to a plurality of discrete islands of pixels;

removing, from the matrix representing the first frame of image data, all discrete islands of pixels which consist of a plurality of pixels, to leave a first transformed matrix containing a first plurality of single points of nonconnected pixels;

removing, from the matrix representing the second frame of image data, all discrete islands of pixels which consist of a plurality of pixels, to leave a second transformed matrix containing a second plurality of single points of nonconnected pixels;

storing, for each of the two pluralities of single points, the coordinates of the single points; and

labeling each single point in a transformed matrix having exactly one single point in the other transformed matrix satisfying a predetermined spatial relationship with its location in the other transformed matrix,

whereby the correspondence between multiple frames of image data is detected.

2. The method of claim 1 wherein said islands are single points of nonconnected pixels.

3. A method of registering multiple frames of image data each represented by a matrix of pixels, said method comprising the steps of:

a. transforming a first pixel matrix associated with a first frame of image data by electronically eroding it in a first predetermined number of serially connected neighborhood processing stages to produce a first transformed matrix containing a first plurality of single points of nonconnected pixels;

b. transforming a second pixel matrix associated with a second frame of image data by electronically eroding it in a second predetermined number of serially connected neighborhood processing stages to produce a second transformed matrix containing a second plurality of single points of nonconnected pixels;

c. storing, for each of the two pluralities of single points, the coordinates of the single points;

d. labeling each nonconnected pixel in a transformed matrix having exactly one nonconnected pixel in the other transformed matrix satisfying a predetermined spatial relationship with its location in the other transformed matrix;

e. removing each unlabeled nonconnected pixel from its transformed matrix, thereby reducing the transformed matrices to a form where each nonconnected pixel in one reduced matrix has a corresponding nonconnected pixel in the other reduced matrix;

f. determining the spatial relationship between pairs of nonconnected pixels in the reduced matrices;

g. transforming one frame of pixel data into registration with the other frame as a function of the spatial relationship between corresponding pixels in the two reduced matrices; and

h. comparing the one frame and the transformed other frame to detect differences therebetween.

4. The method of claim 3, wherein steps a.-f. are repeated, using the nonconnected pixel matrices resulting from the last repetition, until a satisfactory registration of the nonconnected pixels is obtained.