Method and apparatus for alignment of images for template elimination

• US 5,793,887 A
• Filed: 06/30/1995
• Issued: 08/11/1998
• Est. Priority Date: 11/16/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zlotnick, Aviad
• Primary Examiner(s): CHANG, JON CARLTON
• Assistant Examiner(s): Nguyen, Ha Tran
• Application Number:
  US08/481,309
• Time in Patent Office: 1,138 Days
• Field of Search: 382/174, 382/294, 382/209, 382/217, 382/218, 382/216, 382/221, 382/151, 382/295, 382/306
• US Class Current: 382/209
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 1/4115 involving the recognition of specific patterns, e.g. by symbol matching

Abstract

The present application concerns an improved method and apparatus for fine alignment for template elimination. This method involves the steps of dividing a filled-in template image and a reference template image into vertical bands of a given number w of columns of picture elements, employing the OCS algorithm to correlate lines in the vertical bands of the filled-in form, herein referred to as vertical input bands, to lines in the corresponding bands of the reference template image, and constructing a new input image in which each line is moved into its new position--this new image being used as input image, e.g. for template elimination.

Claims

1. A method of aligning a reference template image with a filled-in template image comprising the steps of:

a) correlating lines in said reference template image to lines in said filled-in template image by finding corresponding pairs of projections in a first direction of said lines;

b) determining a displacement of the two projections of lines of each of said corresponding pairs in a second direction perpendicular to said first direction and evaluating the number of picture elements each line of said filled-in template image has to be shifted to achieve a match between said pairs of projections, said step of determining including using f(a,b)=1+MIN(a,b), where a represents picture elements in each of said lines in said reference template and b picture elements in each of said lines in said filled-in template, as a matching function to evaluate quality of said match; and

c) generating a new input image by shifting the picture elements of lines of said filled-in template image perpendicular to said first direction using the determined displacement.

2. The method according to claim 1 wherein either f(a,b)=|w-(a-b)| or f(a,b)=|h-(a-b)| is used as said matching function, a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates.

3. The method according to claim 2, further comprising the steps of:

a) correlating lines in said reference template image to lines in said new input image by finding corresponding pairs of projections of said lines in said reference template image and said new input image in said second direction;

b) determining a displacement of the two projections of lines of each said pair in said first direction and evaluating the number of picture elements each line of said new input image has to be shifted to achieve a match between said pairs of projections; and

c) generating a new input image by shifting the picture elements of lines of said filled-in template image in said first direction using the determined displacement.

4. The method according to claim 3, wherein said reference template image is divided into reference bands having a plurality of rows of picture elements, and said new input image is divided into corresponding input bands having a plurality of rows of picture elements, prior to carrying out steps a)-c) of claim 2, these steps being carried out separately for each reference band and its corresponding input band.

5. The method according to claim 4 wherein projections of lines in a direction parallel to said rows are determined by summing the number of black picture elements of each row of the respective image or band, and wherein projections of lines in a direction parallel to said columns are determined by summing the number of black picture elements of each column of the respective image or band.

6. The method according to claim 2, wherein said reference template image is divided into reference bands having a plurality of columns of picture elements, and said filled-in template image is divided into corresponding input bands having a plurality of columns of picture elements, prior to carrying out steps a)-c) of claim 1, these steps being carried out separately for each reference band and its corresponding input band.

7. The method according to claim 2 wherein said new input image and said reference template are taken as input for template elimination to separate the lines of said reference template from the contents of said filled-in template.

8. An apparatus for the alignment of a reference template image and a filled-in template image having a processor and a storage for storing said reference template image and said filled-in template image, said apparatus comprising:

means for correlating lines in said reference template image by finding corresponding pairs of projections in a first direction of said lines;

means for determining the displacement of the two projections of lines of each said corresponding pair in a second direction, said second direction being perpendicular to said first direction and means for evaluating the number of picture elements of each line said filled-in template image has to be shifted to achieve a match between pairs of projections, said determining means including means for using f(a,b)=1+MIN(a,b), where a represents picture elements in each of said lines in said reference template and b picture elements in each of said lines in said filled-in template, as a matching function to evaluate quality of said match; and

means for generating a new input image by shifting the picture elements of lines of said filled-in template image in said second direction as determined by said determining means.

9. The apparatus of claim 8 wherein f(a,b)=|w-(a-b)| or f(a,b)=|h-(a-b)|, a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates, is used as said matching function.

10. The apparatus according to claim 9 further comprising:

means for correlating lines in said reference template image to lines in said new input image by finding corresponding pairs of projections of said lines in said reference template image and said new input image in said second direction;

means for determining the displacement of the two projections of lines of each said pair in said first direction and means for evaluating the number of lines the picture elements of said new input image has to be shifted to achieve a match between said pairs of projections; and

means for generating a new input image by shifting the picture elements of said filled-in template image in said first direction as determined by said determining means.

11. The apparatus according to claim 10 further comprising means for dividing said reference template image into reference bands having a plurality of rows of picture elements, and for dividing said new input image into corresponding input bands having a plurality of rows of picture elements.

12. The apparatus according to claim 9 further comprising means for dividing said reference template image into reference bands having a plurality of columns of picture elements, and for dividing said filled-in template image into corresponding input bands having a plurality of columns of picture elements.

13. A method of aligning a filled-in template image with a reference template image, said filled-in and said reference template image each having a plurality of rows and columns of pixel elements, said method comprising the steps of:

matching each row of said filled-in template image to a corresponding row of said reference template image;

determining whether there exists an offset between each row of a pair of matched rows, said step of determining including the step of using f(a,b)=1+MIN(a,b), where a represents picture elements in each of said lines in said reference template and b picture elements in each of said lines in said filled-in template, as a matching function to evaluate quality of said match; and

adjusting said row of said filled-in template to eliminate said offset if said offset exists.

14. The method according to claim 13 wherein f(a,b)=|w-(a-b)| or f(a,b)=|h-(a-b)|, a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates, is used as said matching function.

15. The method of claim 14 further comprising the steps of:

matching each column of said adjusted filled-in image to a corresponding column of said reference template image;

determining whether there exists an offset between each column of a pair of matched columns; and

adjusting said column of said filled-in template to eliminate said offset if said offset exists.

16. The method of claim 15 further comprising the step of using one of two matching functions to evaluate quality of the column matches between the reference template image and the filled-in image:

space="preserve" listing-type="equation">f(a,b)=1+MIN(a,b),

or

space="preserve" listing-type="equation">f(a,b)=|w-(a-b)|

and

space="preserve" listing-type="equation">f(a,b)=|h-(a-b),

a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates.

17. An apparatus for aligning a filled-in template image with a reference template image, said filled-in and said reference template image each having a plurality of rows and columns of picture elements, said apparatus comprising:

means for matching each row of said filled-in template image to a corresponding row of said reference template image;

means for determining whether there exists an offset between each row of a pair of matched rows, said step of determining including the step of using f(a,b)=1+MIN(a,b), where a represents picture elements in each of said lines in said reference template and b picture elements in each of said lines in said filled-in template, as a matching function to evaluate quality of said match; and

means for adjusting said row of said filled-in template to eliminate said offset if said offset exists.

18. The apparatus of claim 17 wherein f(a,b)=|w-(a-b)| or f(a,b)=|h-(a-b)|, a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates, is used as said matching function.

19. The apparatus of claim 18 further comprising:

means for matching each column of said adjusted filled-in image to a corresponding column of said reference template image;

means for determining whether there exists an offset between each column of a pair of matched columns; and

means for adjusting said column of said filled-in template to eliminate said offset if said offset exists.

20. The apparatus of claim 17 further comprising means for using one of two matching functions to evaluate quality of column matches between the reference template image and the filled-in image:

space="preserve" listing-type="equation">f(a,b)=1+MIN(a,b),

or

space="preserve" listing-type="equation">f(a,b)=|w-(a-b)|

and

space="preserve" listing-type="equation">f(a,b)=|h-(a-b)|,

a representing picture elements in each of said lines in said reference template, b representing picture elements in each of said lines in said filled-in template, w and h being the width and height, respectively, of said reference and said filled-in templates.