Segment based image registration method

• US 7,400,783 B2
• Filed: 09/30/2004
• Issued: 07/15/2008
• Est. Priority Date: 01/16/2004
• Status: Expired due to Fees

• Current Assignee: National Taiwan University of Science and Technology
• Original Assignee: National Taiwan University of Science and Technology
• Inventors: Sheu, Hsin-Teng
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): Torres; Jose M
• Application Number:
  US10/952,926
• Publication Number:
  US 20050157946A1
• Time in Patent Office: 1,384 Days
• Field of Search: 382/294
• US Class Current: 382/294
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

An examined image is segmented, where a segment thereof may correspond to an area scan image or a line scan image of which the size is defined by considering the performance of the servo mechanism. In the segment, vectors between feature points of the examined image and a standard image are compared, and based on the required tolerance, a Fibonacci search having a predetermined number of iterations is used for matching an optimal corresponding relationship between the examined image and the standard image.

Claims

1. A segment based image registration method for registering an examined image with a standard image, the method comprising:

dividing the standard image into at least one standard image segment, and dividing the examined image into at least one examined image segment, wherein the standard image segment has a plurality of standard feature points, and the examined image segment has a plurality of examined feature points;

selecting a standard reference point in the standard image segment, and selecting an examined reference point in the examined image segment, wherein the standard feature points and the standard reference point form a plurality of standard vectors, and the examined feature points and the examined reference point form a plurality of examined vectors;

comparing the examined vectors to the standard vectors to obtain at least one transformation matrix;

deriving a transformation parameter from the transformation matrix according to a Fibonacci search, wherein the Fibonacci search comprises;

setting a tolerance and an initial possible interval, wherein two ends of the initial possible interval are a maximum possible value and a minimum possible value;

obtaining a Fibonacci iteration number according to the tolerance;

dividing the initial possible interval into a first interval, a second interval and a third interval with a first experimental point and a second experimental point according to the Fibonacci iteration number;

counting numbers of elements of the transformation matrix falling into the first, second and third intervals;

comparing a sum of the numbers of the elements falling into the first and second intervals with a sum of the numbers of the elements falling into the second and third intervals, and keeping the two adjacent intervals having the greater sum of the numbers of the elements and removing the other interval; and

using the two remaining intervals as a new possible interval and repeating the foregoing iteration steps for the new possible interval until obtaining an ideal interval; and

adjusting the examined image segment with the transformation parameter.

2. The method of claim 1, wherein at least one transformation matrix comprises a scaling transformation matrix, a rotation transformation matrix, a first translation matrix and a second translation matrix.

3. The method of claim 1, wherein the transformation parameter is the experimental point at the maximum value of the ideal interval.

4. The method of claim 1, wherein the Fibonacci search further comprises:

dividing the initial possible interval into a former interval and a later interval with a midpoint of the first experimental point and the second experimental point, wherein the former interval comprises the first interval and one portion of the second interval, and the later interval comprises another portion of the second interval and the third interval;

comparing numbers of the elements falling into the former interval and the later interval;

removing the third interval when the number of the elements falling into the former interval is greater than the number of the elements falling into the later interval; and

removing the first interval when the number of the elements falling into the later interval is greater than the number of the elements falling into the former interval.

5. The method of claim 4, wherein the numbers of the elements are counted with an accumulator.

6. The method of claim 1, wherein the standard image segment is divided by a quantity of the standard feature points, and the examined image segment is divided by a quantity of the examined feature points.

7. The method of claim 1, wherein the standard image segment and the examined image segment are divided by distances.

8. The method of claim 1, wherein when the standard image has two standard position points and the examined image has two examined position points, a midpoint of a line connected between the two standard position points is defined as the standard reference point, and a midpoint of a line connected between the two examined position points is defined as the examined reference point.

9. The method of claim 1, wherein the standard image comprises a first standard image segment and a second standard image segment, and the examined image comprises a first examined image segment and a second examined image segment.

10. The method of claim 9, wherein the method further comprises:

deciding an initial boundary of the second standard image segment according to one of the standard feature points in the second standard image segment closest to the first standard image segment; and

deciding an initial boundary of the second examined image segment according to one of the examined feature points in the second examined image segment closest to the first examined image segment.

11. The method of claim 10, wherein when the standard image has two standard position points and the examined image has two examined position points, the initial boundary of the second standard image segment is parallel to a line connected between the two standard position points, and the initial boundary of the second examined image segment is parallel to a line connected between the two examined position points.

12. The method of claim 10, wherein the standard reference point of the second standard image segment is located on the initial boundary of the second standard image segment, and a line connected between the standard reference points of the first and second standard image segments is perpendicular to an initial boundary of the first standard image segment, and the examined reference point of the second examined image segment is located on the initial boundary of the second examined image segment, and a line connected between the examined reference points of the first and second examined image segments is perpendicular to an initial boundary of the first examined image segment.

13. The method of claim 9, wherein a first predetermined distance is between an initial boundary of the second standard image segment and a final boundary of the first standard image segment, and a second predetermined distance is between an initial boundary of the second examined image segment and a final boundary of the first examined image segment.

14. The method of claim 13, wherein when the standard image has two standard position points and the examined image has two examined position points, the initial boundary of the second standard image segment is parallel to a line connected between the two standard position points, and the initial boundary of the second examined image segment is parallel to a line connected between the two examined position points.

15. The method of claim 13, wherein the standard reference point of the second standard image segment is located on the initial boundary of the second standard image segment, and a line connected between the standard reference points of the first and second standard image segments is perpendicular to an initial boundary of the first standard image segment, and the examined reference point of the second examined image segment is located on the initial boundary of the second examined image segment, and a line connected between the examined reference points of the first and second examined image segments is perpendicular to an initial boundary of the first examined image segment.