Method for automatic registration of digitized multi-plane images

• US 5,251,271 A
• Filed: 10/21/1991
• Issued: 10/05/1993
• Est. Priority Date: 10/21/1991
• Status: Expired due to Fees

• Current Assignee: RR Donnelley & Sons Company
• Original Assignee: RR Donnelley & Sons Company
• Inventors: Fling, Russell T.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/780,009
• Time in Patent Office: 715 Days
• Field of Search: 382/44, 382/41, 382/54, 382/48, 382/45, 382/42, 358/105, 358/80, 356/2
• US Class Current: 382/162
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 3/153 using elastic snapping
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: H04N 1/58 Edge or detail enhancement; Noise or error suppression, e.g. colour misregistration correction H04N1/62 takes precedence

Abstract

A method is provided for registering digitized multi-plane color images. The method designates one plane as the reference plane and registers each of the other warped planes with the reference plane. Each plane comprises pixels representing luminosity values having scalar x and y coordinates representing positions in the horizontal and vertical directions, respectively, of the plane. The planes are divided into regions. Correlation values are calculated for regions within the divisional region of the reference plane with a plurality of regions offset from the corresponding warped divisional region. A warp error value is calculated for each pixel of each divisional region as a function of the scalar offset. The warp error values are interpolated and added to the current position of each pixel of the warped plane.

Claims

1. A method of measuring warp calculations for a plurality of regions of a digitized warped plane of an image relative to corresponding regions of a digitized reference plane of the same image, each of the planes comprising pixels representing luminosity values having scalar x and y coordinates representing positions in the horizontal and vertical directions, respectively, said method comprising the steps of:

(1) dividing said digitized reference plane into a plurality of reference regions;

(2) dividing said digitized warped plane into a plurality of corresponding regions;

(3) determining a central pixel of each said reference region of said digitized reference plane;

(4) determining a central pixel of each said corresponding region of said digitized warped plane;

(5) calculating a plurality of correlation values between each reference region centered on the central pixel thereof and a plurality of regions on the warped plane offset from said corresponding region of the warped plane centered on said central pixel thereof in a plurality of x and y directions, each of said correlation values being calculated as a function of gradient values for said warped plane region and said reference plane region, wherein each of said gradient values corresponds to the gradient of the plane at each of said pixel locations;

(6) comparing said plurality of correlation values to identify the offset region having a maximum correlation value with said reference region; and

(7) calculating warp error values in the x and y directions for said warped region as a function of a scalar offset value corresponding to the offset of the central pixel of said maximum correlation offset region.

2. The method of claim 1 wherein each of said gradient values at a pixel location is calculated as a function of a luminosity value for said pixel and luminosity values of pixels two positions over from said pixel.

3. The method of claim 1 wherein each of said correlation values is calculated by multiplying gradient values of said reference region with corresponding gradient values of said warped region;

and summing up the resulting products.

4. The method of claim 1 wherein each of said warp error values is calculated as a function of said maximum correlation value and correlation values for a plurality of offset regions neighboring said maximum correlation region.

5. The method of claim 4 wherein each of said warp error values is calculated as a function of a Gaussian distribution fitted to said correlation values for said neighboring offset regions.

6. The method of claim 1 further comprising the step of using a metric function to indicate the accuracy of said warp error values.

7. A registration method of registering pixels of a warped plane with pixels of a reference plane using the method of claim 1 to determine warp error calculations for a plurality of regions of the warped plane, said registration method comprising the steps of:

(1) determining a filtered warp value for each region of said warped plane by filtering said warp error values using a kernel; and

(2) adding said filtered warp values to each of said pixel positions.

8. The method of claim 7 further comprising the steps of:

(1) calculating warp error values for a plurality of phantom regions surrounding the warped plane, each of said phantom values being a function of neighboring region warp error values; and

(2) interpolating each pixel of said warped plane with neighboring pixels.

9. A method of measuring warp values between separate color planes of a digitized image, each of the planes comprising pixel values corresponding to the luminosity of a color at each location in the x and y directions, said method comprising the steps of:

(1) selecting one of said planes as a reference plane;

(2) calculating a gradient value for said planes at each of said pixels relative neighboring pixels;

(3) dividing the image into a plurality of regions;

(4) selecting another of said planes as a warped plane to be registered with said reference plane;

(5) for each of said divisional regions of said reference plane identifying a corresponding divisional region on said warped plane;

(6) identifying a plurality of correlation regions centered at central pixels of each of said divisional regions on said warped plane;

(7) calculating a plurality of correlation values between each of said reference correlation regions and offset regions on said warped plane centered at pixels offset from each of said corresponding central pixels;

(8) for each region of the warped plane, comparing said plurality of correlation values to determine a maximum correlation offset corresponding to the offset in the x and y direction of the offset central pixel for the region having the maximum correlation value from said regional central pixel; and

(9) calculating an x and y component of a warp error value for each of said pixels in each of said warped region as a function of said maximum correlation offset.

10. The method of claim 9 wherein said planes correspond to cyan, magenta, yellow and black color components of said image and the reference plane is said magenta plane.

11. The method of claim 9 wherein a plurality of pixels are removed from surrounding each of said planes.

12. The method of claim 9 wherein each of said gradient calculations for said planes is made by squaring the difference between the luminosity value at a given pixel and the luminosity value at a pixel two x positions over from said pixel and adding that value to the square of the difference between the luminosity value at said pixel and the luminosity value at a pixel two y positions over.

13. The method of claim 9 wherein said maximum correlation offset is determined from a range of offset regions corresponding to an error range for said warp error values.

14. The method of claim 9 wherein said correlation regions have a smaller area than said reference region.

15. The method of claim 9 wherein each of said correlation values is determined by multiplying each of said gradient values of said reference correlation region with a corresponding gradient value in the offset region;

and performing a plurality of summations for each of the resultant values.

16. The method of claim 15 wherein each of said correlation values is normalized by the number of summations performed to determine normalized correlation values.

17. A method of registering planes of an image using said warp calculations of claim 9 comprising the steps of:

(1) calculating warp error values for a plurality of phantom regions surrounding said warped plane as a function of a plurality of warp error values of bordering regions;

(2) filtering each of said warp error values using a region size rectangular kernel; and

(3) interpolating the x and y positions for each of said pixels of said warped plane using the filtered warp values.

18. A method for registering digitized planes of an image, said planes comprising a plurality of pixels, said method comprising the steps of:

(1) selecting one of said planes as a reference plane and the others of said planes as warped planes;

(2) dividing the image into divisional regions;

(3) calculating a plurality of gradient values for each of said planes at the location of each of said pixels;

(4) selecting one of said planes as a warped plane to be registered with said reference plane;

(5) correlating said gradients for each of said regions of said reference plane with each of said gradients of a plurality of offset regions of said warped planes;

(6) determining offsets for regions of said warped planes which provide the greatest correlations;

(7) interpolating said offsets to determine warp errors for each of said regions of each of said warped planes;

(8) determining warp error values for phantom regions along the borders of said warped planes;

(9) using a plurality of region sized kernels to filter each of said warp error values for each of said regions of said warped planes; and

(10) using said filtered warp error values to interpolate image plane pixel positions.

19. The method of claim 18 further comprising the step of determining a maximum error range, wherein said offset values are limited by said error range.

20. The method of claim 18 wherein said divisional regions are rectangular and of equal sizes.