Bitmap registration by gradient descent

• US 5,631,981 A
• Filed: 03/12/1996
• Issued: 05/20/1997
• Est. Priority Date: 01/13/1994
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Rao, Arun
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/614,446
• Time in Patent Office: 434 Days
• Field of Search: 382/201, 382/209, 382/276, 382/205, 382/278, 382/295, 382/141, 382/218, 382/197, 324/309
• US Class Current: 382/278
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A template useful in registering an incoming bitmapped image with a master bitmapped image is created by convolving the master with a Gaussian function and computing the gradient of the resulting scalar field. According to the invention, the incoming image is iteratively moved with respect to the template in response to the gradient of the scalar field formed by the convolution operation, i.e., the direction of adjustment is a function of the gradient of the scalar field formed by the convolution operation used to create the template. According to one embodiment of the invention, the registration process is terminated when the error between the master and the image is below a predefined threshold.

Claims

1. A method for registering bitmapped images utilizing an image processing system, comprising the steps of:

(a) inputting a master bitmapped image to said image processing system;

(b) creating a template from said master by convolving said master with a Gaussian function and computing the gradient of the resulting scalar field;

(c) inputting an image to be registered with respect to said master into said image processing system; and

(d) iteratively shifting the entire position of said entire image to be registered, with respect to said template, and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system are included in the shifting, where the direction of adjustment is a function of the gradient of the scalar field formed by the convolution operation used to create said template.

2. A method as set forth in claim 1 further comprising the step of terminating the registration process whenever the alignment error between said master and image to be registered is below a predetermined threshold.

3. A method as set forth in claim 1 further comprising the step of terminating the registration process whenever the number of iterations performed at said step of iteratively shifting exceeds a predetermined threshold value.

4. A method as set forth in claim 1 further comprising the step of terminating the registration process whenever the same point is visited twice as a result of performing said step of iteratively shifting.

5. A method for registering bitmapped images with corresponding master bitmapped images, comprising the steps of:

(a) constructing a registration gradient template from a master bitmapped image by applying a convolution and gradient operation thereto;

(b) computing the vector sum of all vectors in said gradient template at each black pixel on the image to be registered with said master; and

(c) shifting the entire position of said entire image to be registered by one pixel in the direction of the vector sum computed at step (b) and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system are included in the shifting.

6. A method as set forth in claim 5 further comprising the step of iteratively performing said step of shifting until the alignment error between the image to be registered and said master is below a predetermined threshold.

7. A method as set forth in claim 5 further comprising the step of terminating the registration process wherever the number of iterations performed at said step of shifting exceeds a predetermined threshold value.

8. A method as set forth in claim 5 further comprising the step of terminating the registration process whenever the same point is visited twice as a result of performing said step of iteratively shifting.

9. A method as set forth in claim 5 wherein said master bitmapped image is convolved with a Gaussian function given by:

space="preserve" listing-type="equation">f(x,y)=(-e).sup.(x.spsp.2.sup.+y.spsp.2.sup.)/(sigma).spsp.2.

where sigma is the standard deviation of the Gaussian.

10. A method as set forth in claim 9 wherein said registration gradient template comprises the gradient of the scalar field resulting when said master is convolved with said Gaussian function given by:

space="preserve" listing-type="equation">f(x,y)=(-e).sup.(x.spsp.2.sup.+y.spsp.2.sup.)/(sigma).spsp.2.

11. A method as set forth in claim 5 wherein said step of computing further comprises the step of evaluating the equation:

##EQU2## where T is the mean vector, N is the number of black pixels in said second bitmapped image, G is the gradient vector field and u is a scalar matrix containing 1 for all black pixels in said image to be registered and 0 elsewhere, with the direction of vector T, defined as T=t_x i+t_y j, given by;

space="preserve" listing-type="equation">θ

=atan(t.sub.y /t.sub.x).

12.

12. Apparatus for registering, with the aid of a digital computer, an incoming bitmapped image with a master bitmapped image, using a template created from said master by convolving said master with a Gaussian function and computing the gradient of the resulting scalar field, comprising:

(a) means for providing said incoming bitmapped image to said computer; and

(b) means for iteratively shifting the entire position of said entire incoming bitmapped image, with respect to said template, and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system are included in the shifting, where the direction of adjustment is a function of the gradient of the scalar field formed by the convolution operation used to create said template.

13. Apparatus as set forth in claim 12 further comprising means for terminating the registration process whenever the alignment error between the incoming bitmapped image and said master is below a predetermined threshold.

14. Apparatus as set forth in claim 12 further comprising means for terminating the registration process whenever the number of iterations performed by said means for iteratively adjusting exceeds a predetermined threshold value.

15. Apparatus as set forth in claim 12 further comprising means for terminating the registration process whenever the same point is visited twice by said means for iteratively adjusting.

16. An image processing system for aligning an incoming bitmapped image with a master bitmapped image, comprising:

(a) registration means including;

(a1) means for creating a registration gradient template from said master by applying a convolution and gradient operation thereto;

(a2) means for computing the vector sum of all vectors in said registration gradient template at each black pixel on said incoming bitmapped image; and

(a3) means for shifting the entire position of said entire incoming bitmapped image by one pixel in the direction of the vector sum computed by said means for computing and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system are included in the shifting; and

(b) means for terminating the registration process.

17. A character recognition system operative to align an incoming bitmapped image representing a character with a master bitmapped image representing said character, comprising:

(a) registration means including;

(a1) means for creating a registration gradient template from said master by applying a convolution and gradient operation thereto;

(a2) means for computing the vector sum of all vectors in said registration gradient template at each black pixel on said incoming bitmapped image; and

(a3) means for shifting the entire position of said entire incoming bitmapped image by one pixel in the direction of the vector sum computed by said means for computing and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system are included in the shifting; and

(b) means for terminating the registration process.

18. An position adjustment system for aligning an incoming bitmapped representation of an object with a master bitmapped representation of said object, comprising:

(a) registration means including;

(a1) means for creating a registration gradient template from said master by applying a convolution and gradient operation thereto;

(a2) means for computing the vector sum of all vectors in said registration gradient template at each black pixel on said incoming bitmapped representation of an object; and

(a3) means for shifting the entire position of said entire incoming bitmapped representation of an object by one pixel in the direction of the vector sum computed by said means for computing and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system is included in the shifting; and

(b) means for terminating the registration process.

19. A method for registering bitmapped images utilizing a digital computer comprises the steps of:

(a) providing said computer with a template created from a master bitmapped image utilizing a convolution operation; and

(b) utilizing said computer to iteratively shift the entire position of an entire image to be registered, with respect to the template, and said entire image to be registered is shifted so that all portions of said entire image as originally inputted to the image processing system is included in the shifting, where the direction of adjustment is a function of the gradient of the scalar field formed by the convolution operation used to create the template.