Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1998-02-17
2003-05-13
Lee, Thomas D. (Department: 2624)
Image analysis
Pattern recognition
Template matching
C382S218000, C382S318000
Reexamination Certificate
active
06563951
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and a device for matching two images, each consisting of a plurality of pixels and having partially overlapping contents, the degree of correspondence between the images being determined for different displacement positions which represent different overlappings of the images.
BACKGROUND OF THE INVENTION
The applicant has developed a pen by means of which text can be recorded by the pen being passed over the text which is to be recorded. The pen, which includes, inter alia, a two-dimensional light-sensitive sensor and a signal-processing unit, records images of the text with partially overlapping contents. Subsequently, the images are put together to form a larger image, which does not contain any redundant information. The characters in the image are identified with the aid of OCR software and are stored in character-coded form in the pen. The pen is described in the applicant's Swedish Patent Application No. 9604008-4, which had not been published when the present application was filed.
In order to reduce the memory requirement of the pen, it is desirable that it be possible to put together a recorded image with the previous image before the next image is recorded. A desired image-recording frequency for the pen is about 50 Hz, which thus means that it shall be possible to put together two images in about 20 ms. The most time-consuming operation when putting the images together is the matching of the images, i.e. determining the relative position in which the best possible correspondence between the contents of the images is obtained.
A possible method for matching two images is to examine all possible overlap positions between the images and, for each overlap position, to examine every pair of overlapping pixels, to determine a score for each pair of overlapping pixels, the score depending on how well the values of the pixels correspond, and to then determine which overlap position provides the best match on the basis of the total of the scores for the overlapping pixels in each position. However, this procedure is too slow for the application indicated above.
SUMMARY OF THE INVENTION
In the light of the above, one object of the present invention is thus to provide a new method for automatic matching of two images, which method permits faster matching of two images with a given processor than the method described above.
A further object is to provide a device for the implementation of the method.
The objects are achieved by a method according to claim
1
and a device according to claims
18
and
19
. Preferred embodiments are stated in the subclaims.
Like the method described above, the invention is based on determining the degree of correspondence between two images, which each consists of a plurality of pixels and which have partially overlapping contents, for different displacement positions representing different overlappings of the images. However, the comparison of the contents of the images is effected in a more efficient manner. More specifically, a plurality of numbers are determined for each one of a plurality of displacement positions, each number being formed with the aid of pixel values from both images. The numbers are used to retrieve predefined overlap assessment values for at least two displacement positions simultaneously. These overlap assessment values are subsequently used in determining the degree of correspondence between the contents of the images.
By this method, the different displacement positions can be examined with a certain degree of parallelism, making it possible to examine the images more quickly than if all the displacement positions are examined sequentially. This parallelism is achieved with the aid of the numbers, which are used to examine at least two displacement positions simultaneously. Since the numbers are based on the contents of each image, it is possible to calculate in advance the overlap assessment values in the cases where the pixel values which make up the numbers overlap completely or partially. Naturally, the efficiency of the method increases the more pixels are included in each number since this increases the parallelism.
Thus, the overlap assessment values are predefined. What this means is that if a pixel in one of the images has a first given value and the corresponding overlapping pixel in the other image has a second given value, a certain predetermined overlap value is always obtained. The same applies when the overlap assessment values relate to several overlapping pixels. The different overlap assessment values which are obtained for different combinations of pixel values can be determined optionally. They can be defined with the aid of one or more formulae, or tables, or in some other suitable manner.
In this connection, it should be pointed out that, of course, the images are not physically displaced in relation to each other when the method is being implemented, but rather the comparison between the images is carried out for hypothetical displacements.
In a preferred embodiment, the method furthermore comprises the steps of adding up the overlap assessment values for each of said displacement positions, and of using the totals obtained in this manner to determine which of the displacement positions provides the best possible match between the contents of the images. The overlap assessment values which are added together for a certain displacement position preferably reflect the degree of correspondence between all overlapping pixels for that displacement position.
In order further to increase the matching speed, the overlap assessment values are suitably added up in parallel for several displacement positions. The adding-up becomes particularly advantageous if it is carried out in parallel for the overlap assessment values which are retrieved simultaneously with the aid of a number.
Each overlap assessment value can relate to one or more overlapping pixels. In the latter case, a matching speed increase is achieved by the fact that it is not necessary to add up the assessment values for each overlapping pixel for a certain displacement position, but rather overlap assessment values which have already been added up for two or more overlapping pixels can be retrieved directly.
When the displacement position which provides the best match between the contents of the images has been determined, the images can be put together in this relative position. The putting-together can be effected by the overlapping pixel values in one of the images being rejected or, preferably, by a combined weighting of the pixel values for each overlapping pixel.
The plurality of displacement positions for which numbers are determined can suitably constitute rough displacement positions, and said at least two displacement positions for which the overlap assessment values are retrieved can suitably comprise at least one fine displacement position, representing a smaller displacement from a rough displacement position than the displacement between two rough displacement positions. The second overlap assessment value retrieved can relate to the rough displacement position in question or to another fine displacement position.
In the simplest embodiment of the method, the contents of the images are displaced in relation to each other in one direction only. However, the method can also be employed when the images are displaced in two different, preferably perpendicular, directions in relation to each other. In this case, in order to arrive at the position in which the correspondence between the contents of the images is at a maximum, it is suitable to let the rough displacement positions represent different overlappings of the images in the first direction, for example horizontally, and to repeat the method for different overlappings of the images in the other direction, for example vertically.
The rough displacement positions, which thus constitute a subset of the displacement positions examined, are preferably determined by the images being divided into a plurality of r
Ericson Petter
Fåhraeus Christer
Hugosson Ola
C Technologies AB
Cooper & Dunham LLP
Lee Thomas D.
LandOfFree
Method and a device for matching images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and a device for matching images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and a device for matching images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3011036