Image registration

• US 5,129,014 A
• Filed: 12/08/1989
• Issued: 07/07/1992
• Est. Priority Date: 12/08/1989
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bloomberg, Dan S.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US02/349,203
• Time in Patent Office: 942 Days
• Field of Search: 382/41, 382/49, 382/48, 382/9, 382/8, 382/27, 358/101, 358/106, 358/107, 356/401, 356/375
• US Class Current: 382/287
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A technique for rapidly and efficiently registering binary images, contemplates incorporating one or more reference features, referred to as fiducials, into the binary image at a known displacement from a feature of interest in the image, subjecting the image to an operation (typically a morphological operation and possibly a thresholded reduction) that projects out the fiducial(s), determining the position of the fiducial(s), and thereby determining the position of the feature of interest. The fiducial(s) must have at least one characteristic that is absent from the remaining (or at least from neighboring) portions of the image. In one set of embodiments, each fiducial includes horizontal and vertical line segments that are longer than any line segments expected to be found in the binary image. Projecting out the fiducial entails erosions using hit-miss structuring elements. In another embodiment, each fiducial is a small finely textured region.

Claims

1. A method of determining the position of a feature of interest in a binary input image comprising the steps of:

providing as a part of the input image a fiducial at a known displacement from the feature of interest, the fiducial having at least one characteristic that is absent from neighboring portions of the input image;

eroding at least a portion of the input image containing the fiducial with a hit-miss structuring element that shares the characteristic with the fiducial so as to provide a resultant image having a number of ON pixels only in the vicinity of the fiducial;

determining a reference position representative of the position of the number of ON pixels; and

combining the reference position with the known displacement to provide the position of the feature of interest.

2. The method of claim 1, and further comprising the step, carried out after said subjecting step, of filling the number of ON pixels to the smallest enclosing rectangle.

3. The method of claim 2 wherein said determining step comprises the step of determining the coordinate of at least one corner of the enclosing rectangle.

4. The method of claim 2 wherein said determining step comprises the step of thinning the rectangle to a single ON pixel.

5. The method of claim 1 wherein the fiducial comprises a pair of intersecting straight lines and wherein the structuring element includes two rows of hits arranged in a cruciform pattern and a plurality of misses surrounding but spaced outwardly from the center of the cruciform pattern.

6. The method of claim 1 wherein the fiducial comprises a pair of straight lines that meet at respective endpoints and wherein the structuring element includes two rows of hits arranged in a corner pattern and a miss along each line beyond the corner but spaced from the corner.

7. A method of determining the position of a feature of interest in a binary input image comprising the steps of:

providing as a part of the input image a fiducial at a known displacement from the feature of interest, the fiducial being in the form of a finely textured region;

subjecting at least a portion of the input image containing the fiducial to a first set of operations that eliminates OFF pixels that are near ON pixels to produce a resulting image with a solid region corresponding to the textured fiducial in the input image;

subjecting the resulting image to a second set of operations that eliminates ON pixels that are near OFF pixels to produce a further resulting image with a solid region corresponding to the textured fiducial in the input image and regions substantially devoid of ON pixels corresponding to other regions in the input image;

determining a reference position representative of the position of the solid region; and

combining the reference position with the known displacement to provide the position of the feature of interest.

8. The method of claim 7, and further comprising the step, carried out after said subjecting steps, of filling the number of ON pixels to the smallest enclosing rectangle.

9. The method of claim 8 wherein said determining step comprises the step of determining the coordinate of at least one corner of the enclosing rectangle.

10. The method of claim 8 wherein said determining step comprises the step of thinning the rectangle to a single ON pixel.