Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
2001-05-07
2004-10-26
Patel, Jayanti K. (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
C382S236000
Reexamination Certificate
active
06810134
ABSTRACT:
BACKGROUND OF THE INVENTION
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 relates to a method and 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 which is incorporated by reference herein. 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.
The method described above may be repeated a number of times to come to the best possible choice of the optimal candidate value. In the case where the depth in the image is determined, the depths are initially chosen at random. With each repetition the values of adjacent blocks are used then, which may differ from the previous repetition. The newly found value having the smallest matching error is subsequently used for calculating the matching error of other blocks. When the values do not change any longer, the final depth has been determined and the repetitions may be stopped. With each repetition, the current value for the optimal candidate value and the matching error are to be saved for each block.
It is common practice that a random motion vector or depth value is added to said set, or an already added value is added once again after a random value has been added thereto. This avoids that repeatedly executing the method only provides locally optimal candidate values.
A disadvantage of this method is that by adding a random value either or not based on a value that has already been added, it takes longer than necessary for the final depth or motion vector to be determined. Moreover, oscillations may occur around the final value, because the randomly chosen value negatively affects the process.
SUMMARY OF THE INVENTION
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 a variety of candidate values is determined, which candidate values are determined based on properties of the first image, and step (a) also includes the adding of a candidate value to the set which is chosen from said variety. Adding this candidate value provides a better choice for the optimal candidate value, because this candidate value better suits to the first image than a randomly chosen candidate value. Indeed, the variety is determined based on properties of the first image.
In an embodiment of the method the properties of the first image also include temporal changes of the value of previously chosen optimal candidate values for blocks from the first image. If, for example, the method is executed several times, previously obtained optimal candidate values are available. On the basis of these values, the variety may be formed so that it fits with the changes. If many large changes occur, the variety may be formed with many large candidate values, because this fits well with the first image.
In a further embodiment of the method, a histogram is made of said changes and the variety is determined in proportion to a distribution in the histogram. This embodiment is advantageous in that there may now be simply determined what kind of changes occur, for example, major, medium and minor, so that a variety may be formed that fits well with the first image.
In a further embodiment of the method, the properties of the first image also include a direction of temporal changes of the value of previously chosen optimal candidate values for blocks from the first image. This embodiment is advantageous in that with the aid of these properties there may be determined whether a repeated execution of the method leads to oscillation of the optimal candidate value chosen with each repetition around a certain point. In that case, the variety may be chosen such that oscillation is terminated.
It is also an object of the invention to provide a system of the type defined in the introductory part, with which a better choice for the optimal candidate value is made.
This object is achieved with the system in accordance with the invention in that the system is arranged for determining a variety of candidate values, which candidate values are determined based on properties of the first image, and the collector is also arranged for adding a candidate value to the set that is chosen from said variety.
The system determines said variety and renders it available to the collector, so that the latter can choose herefrom a candidate value and add it to the set.
In an embodiment of the system the properties of the first image also include temporal changes of the value of previously chosen optimal candidate values for blocks from the first image.
In a further embodiment of the system the system is arranged for making a histogram of said changes and for determining the variety in proportion to a distribution in the histogram.
In an embodiment of the system the properties of the first image also include a direction of temporal changes of the value of previously chosen optimal candidate values for blocks from the first image.
It is also an object of the invention to provide an apparatus of the type defined in the introductory part, with which a better processing of the video signal is provided.
This object is achieved with the apparatus in accordance with the invention, in that the apparatus comprises:
a system according to the invention 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 being arranged for choosing optimal candidate values for blocks fr
Op De Beeck Marc Joseph Rita
Wilinski Piotr
Koninklijke Philips Electronics , N.V.
Patel Jayanti K.
LandOfFree
Method, system and apparatus for choosing an optimal... 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 choosing an optimal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and apparatus for choosing an optimal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3328134