Method and apparatus for contour motion estimating a binary image by using a weighted block match algorithm

• US 5,969,766 A
• Filed: 08/25/1997
• Issued: 10/19/1999
• Est. Priority Date: 07/19/1997
• Status: Expired due to Fees

• Current Assignee: Daewoo Electronics Company Limited (Dayou Holdings Co.,Ltd.)
• Original Assignee: Daewoo Electronics Company Limited (Dayou Holdings Co.,Ltd.)
• Inventors: Kim, Jin-Hun
• Primary Examiner(s): Lee, Richard
• Assistant Examiner(s): Vo, Tung T.
• Application Number:
  US08/918,040
• Time in Patent Office: 785 Days
• Field of Search: 348/402, 348/405, 348/413, 348/416, 348/411, 348/699, 348/700, 348/407, 348/420, 382/236, 382/239, 358/105
• US Class Current: 375/240.14
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/543 using regions

Abstract

A motion estimating method, for use in a motion estimation between a current and a previous frames of a binary video image, wherein the current frame is divided into a plurality of equal sized search blocks, forms a search region corresponding to each search block within the previous frame and a plurality of candidate blocks within the search region, each of the candidate blocks having a same size as the search block, to thereby provide a displacement of each candidate block from the search block as a displacement vector of each candidate block. Thereafter, the method overlaps the search block with each candidate block to thereby determine an unmatched region, a boundary of a matched region and a boundary of the search block and assigns a weight to each of the pixels within the unmatched region on a predetermined basis, wherein the weight may vary from pixel to pixel. Then, the method calculates a weighted error of each candidate block by using the weights and selects a displacement vector which has a minimum error as an optimum motion vector.

Claims

1. A method for motion estimating between a current and a previous frames of a binary image signal, wherein the current frame is divided into a plurality of equal sized search blocks, the method comprising the steps of:

(a) forming a multiplicity of search regions within the previous frame, wherein each search region corresponds to each search block;

(b) forming a plurality of candidate blocks within each search region, each of the candidate blocks having a same size as the search block, to thereby provide a displacement of each candidate block from the search block as a displacement vector of said each candidate block;

(c) overlapping the search block with each candidate block to thereby determine an unmatched region, a boundary of a matched region and a boundary of the search block;

(d) assigning a weight to each of the pixels within the unmatched region;

(e) calculating a weighted error of each candidate block by using the weights assigned to the pixels within the unmatched region in step (d);

(f) comparing the weighted errors with each other to thereby select a minimum weighted error, and providing a selection signal, wherein the selection signal indicates which displacement vector corresponds to the minimum weighted error; and

(g) selecting the displacement vector corresponding to the minimum weighted error in response to the selection signal and providing it as an optimum motion vector.

2. The method according to claim 1, wherein said step (c) includes the steps of:

(c1) overlapping the search block with each of the candidate blocks;

(c2) comparing each pixel value of the search block with a corresponding pixel value of the candidate block, wherein the corresponding pixel value of the candidate block is a value of a pixel located at a same position of a pixel in the search block which is being compared with; and

(c3) determining the unmatched region, the boundary of the matched region, and the boundary of the search block, wherein the unmatched region within the search block is comprised of pixels whose corresponding pixels within the corresponding candidate block have different pixel values therefrom, the boundary of the matched region within the search block is comprised of pixels whose pixel values are 1 and adjacent to the unmatched region or adjacent to pixels whose pixel values are 0, and the boundary of the search block is comprised of pixels whose pixel values are 1 and adjacent to pixels whose pixel values are 0.

3. The method according to claim 2, wherein said step (e) calculates the weighted error by summing up all of the weights assigned to the pixels within the unmatched region.

4. The method according to claim 3, wherein said step (d) assigns a weight to each pixel within the unmatched region on the basis of its proximity to the boundary of the matched region so that, a smaller weight is assigned to a pixel closer to the boundary of the matched region, and a larger weight is assigned to a pixel located farther from the boundary of the matched region.

5. The method according to claim 3, wherein said step (d) assigns a weight to each pixel within the unmatched region on the basis of its proximity to the boundary of the search block so that a smaller weight is assigned to a pixel located at the boundary of the search block, and a larger weight to a pixel apart located from the boundary of the search block.

6. An apparatus for motion estimating between a current and a previous frames of a binary image signal, wherein the current frame is divided into a plurality of equal sized search blocks, the method comprising:

a search region formation means for forming a multiplicity of search regions within the previous frame, wherein each search region corresponds to each search block;

a candidate block formation means for forming a plurality of candidate blocks within each search region, each of the candidate blocks having a same size as the search block, to thereby provide a displacement of each candidate block from the search block as a displacement vector of said each candidate block;

a block matching means for overlapping the search block with each candidate block to thereby determine an unmatched region, a boundary of a matched region and a boundary of the search block;

a weight assignment means for assigning a weight to each of the pixels within the unmatched region;

a weighted error calculating means for calculating a weighted error of each candidate block by using the weights assigned to the pixels within the unmatched region at the weight assignment means;

a comparing means for comparing the weighted errors with each other to thereby select a minimum weighted error, and providing a selection signal, wherein the selection signal indicates which displacement vector corresponds to the minimum weighted error; and

a multiplexing means for selecting the displacement vector corresponding to the minimum weighted error in response to the selection signal and providing it as an optimum motion vector.

7. The apparatus according to claim 6, wherein said block matching means includes:

an overlapping means for overlapping the search block with each of the candidate blocks;

a matching means for comparing each pixel value of the search block with a corresponding pixel value of the candidate block, wherein the corresponding pixel value of the candidate block is a value of a pixel located at a same position of a pixel in the search block which is being compared with; and

a determining means for determining the unmatched region, the boundary of the matched region, and the boundary of the search block, wherein the unmatched region within the search block is comprised of pixels whose corresponding pixels within the corresponding candidate block have different pixel values therefrom, the boundary of the matched region within the search block is comprised of pixels whose pixel values are 1 and adjacent to the unmatched region or adjacent to pixels whose pixel values are 0, and the boundary of the search block is comprised of pixels whose pixel values are 1 and adjacent to pixels whose pixel values are 0.

8. The apparatus according to claim 7, wherein said weighted error calculating means calculates the weighted error by summing up all of the weights assigned to the pixels within the unmatched region.

9. The apparatus according to claim 8, wherein said weight assignment means assigns a weight to each pixel within the unmatched region on the basis of its proximity to the boundary of the matched region so that, a smaller weight is assigned to a pixel closer to the boundary of the matched region, and a larger weight is assigned to a pixel located farther from the boundary of the matched region.

10. The apparatus according to claim 8, wherein said weight assignment means assigns a weight to each pixel within the unmatched region on the basis of its proximity to the boundary of the search block so that a smaller weight is assigned to a pixel located at the boundary of the search block, and a larger weight to a pixel apart located from the boundary of the search block.