Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
2001-05-07
2004-05-18
Patel, Jayanti K. (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
C348S416100, C348S700000, C375S240160
Reexamination Certificate
active
06738497
ABSTRACT:
The invention relates to a method of choosing an optimal candidate value to be used for matching a block from a first image with an area from a second image, the method comprising:
(a) making a set of candidate values for determining an area to be matched from the second image,
(b) for each candidate value from the set, determining an area to be matched from the second image, based on said candidate value, matching the block from the first image with this area and calculating a matching error, and
(c) choosing the optimal candidate value from the set based on the calculated matching errors.
The invention likewise relates to a system for choosing an optimal candidate value to be used for matching a block from a first image with an area from a second image, the system comprising:
a collector, which is arranged for making a set of candidate values for determining an area to be matched from the second image,
a matcher, which is arranged for determining for each candidate value from the set based on said candidate value an area to be matched from the second image, matching the block from the first image with this area and calculating a matching area, and
a selector, which is arranged for choosing the optimal candidate value from the set based on the calculated matching errors.
The invention furthermore relates to an apparatus for processing a video signal that comprises a variety of images.
A method of the type defined in the opening paragraph is known from international patent application published under number WO 99/40726 (PHN 17.017) by the same applicants. With block-based techniques for determining motion and depth in an image, the image is divided into a number of blocks, for example, rectangles of equal size. The image may then be compared with another image by matching the individual blocks in the other image.
Matching a block with a second image is effected by choosing a number of candidate values for the motion vector or the depth and then determining for each candidate value in how far the block corresponds to an area in the second image. The degree of deviation in this match may be calculated. This deviation is called the matching error that belongs to the candidate value. The optimal candidate value is the candidate value that has a relatively small matching error. Suitable candidate values are, inter alia, the depths or the motion vectors of adjacent blocks from the first image, because they are likely to have approximately the same characteristics as the present block. Since a block comprises pixels, the matching error may be determined on the basis of the corresponding pixels in the block from the first image and in the area in the second image. A mathematical technique such as determining the mean square error (MSE) is suitable for this purpose.
When the chosen optimal candidate value lies between the minimum and the maximum of the set, there may be determined how close this candidate value lies to the real optimal value. For this purpose, the distance is determined between the two candidate values whose matching errors lie closest to the matching error of the optimal candidate value. The real optimal value must now lie in the interval determined by these two candidate values. The size of this interval may now be used as a measure for the accuracy of the chosen optimal candidate value. The larger the interval, the greater the chance of the real optimal value being remote from the chosen optimal candidate value.
A disadvantage of the known method is that when the optimal candidate value is an extreme value of the set, it is impossible to find out how much the matching error of this value comes close to the real smallest matching error. It is then highly likely that the value of the real minimum matching error lies remote from this candidate value. As a result, the approximation of the depth or the motion is not optimal with this method.
It is an object of the invention to provide a method of the type defined in the opening paragraph, in which a better choice for the optimal candidate value is made.
This object is achieved with the method according to the invention in that, when the chosen optimal candidate value is an extreme value of the set, the following steps are executed:
(d) extending the set by a first candidate value outside the interval determined by a minimum and a maximum of the set,
(e) determining, based on the first candidate value, an area to be matched from the second image, matching the block from the first image with this area and calculating a matching error, and
(f) choosing the optimal candidate value from the extended set based on the calculated matching errors.
If the optimal candidate value chosen with step (f) is the first candidate value, it has a smaller matching value than the candidate value chosen with step (c). This provides a better choice for the optimal candidate value. Otherwise, the optimal candidate value chosen with step (f) will be the candidate value chosen with step (c), because all the other candidate values are less optimal than the candidate values chosen with step (c). This candidate value then has the smallest matching error. At the same time, the accuracy of this matching error can be determined. This also provides a better choice for the optimal candidate value.
In an embodiment of the method, steps (d), (e) and (f) are repeated each time with a next candidate value, as long as the chosen optimal candidate value is an extreme value from the extended set. This embodiment is advantageous in that now always an optimal candidate value is chosen whose accuracy can be determined and that checks need only be made whether the optimal candidate value is the same as the first value to decide whether the set is to be extended further.
In a further embodiment of the method the first candidate value is determined by mirroring the value of a candidate value from the set relative to the chosen optimal candidate value. This embodiment is advantageous in that it is very simple to obtain a new value in this manner.
In a further embodiment of the method the next candidate value is determined by mirroring the value of a candidate value from the extended set relative to the chosen optimal candidate value.
It is also an object of the invention to provide a system of the type defined in the opening paragraph in which a better choice for the optimal candidate value is made.
This object is achieved with the system according to the invention in that the system is arranged for detecting when the chosen optimal candidate value is an extreme value from the set, and in that
the collector is arranged for extending the set in that case by a first candidate value outside the interval determined by a minimum and a maximum of the set,
the matcher is arranged for determining, based on the first value, in that case an area to be matched from the second image, matching the block from the first image with this area and calculating a matching error, and
the selector is arranged for choosing the optimal candidate value in that case from the extended set based on the calculated matching errors.
In an embodiment of the system
the collector is arranged for extending the extended set further by a next candidate value determined outside the interval by a minimum and a maximum of the extended set as long as the optimal candidate value is an extreme value of the extended set,
the matcher is arranged for determining in that case an area to be matched from the second image on the basis of the next candidate value, matching the block from the first image with this area and calculating a matching error, and
the selector is arranged for choosing in that case the optimal candidate value from the extended set based on the calculated matching errors.
This embodiment is advantageous in that it is easy to realize because the system now only needs to check whether the optimal candidate value is the same as the first value, to decide whether the set is to be extended any further.
In a further embodiment of the system, the collector is arranged for determining the first candida
Van Overveld Cornelius Wilhelmus Antonius Marie
Wilinski Piotr
Koninklijke Philips Electronics , N.V.
Patel Jayanti K.
LandOfFree
Method, system and apparatus for image block matching 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, system and apparatus for image block matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and apparatus for image block matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225361