Polygon block matching method

• US 5,796,855 A
• Filed: 06/04/1996
• Issued: 08/18/1998
• Est. Priority Date: 10/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/657,274
• Time in Patent Office: 805 Days
• Field of Search: 382/107, 382/236, 348/409, 348/415, 348/416, 348/699
• US Class Current: 382/107
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/563 Motion estimation with padding, i.e. with filling of non-object values in an arbitrarily shaped picture block or region for estimation purposes
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments

Abstract

A polygon block matching method includes defining a preliminary quadrilateral reference pixel block of multiple pixels about a selected reference pixel in an image object of a video image frame. The pixels of the preliminary quadrilateral pixel block not in the interior of the image object are identified and omitted to establish a reference pixel block that conforms to the image object. If it encompasses the perimeter of the image object, the reference pixel block frequently is of a non-quadrilateral polygonal configuration. A search or sample pixel block of multiple sample pixels is defined in another video image frame and represents a region over which a selected sample pixel corresponding to the selected reference pixel is sought. The search includes determining and storing for the pixels in the sample pixel block correlations to the pixels in the reference pixel block, and identifying from the correlations the selected sample pixel corresponding to the selected reference pixel.

Claims

1. A block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, comprising:

defining a reference pixel block of multiple pixels relative to a first reference pixel in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the reference pixel block being a quadrilateral array of pixels;

determining and storing for the pixels in the sample pixel block correlations to the pixels in the reference pixel block, including using shape of an arbitrary image feature to exclude pixels in the reference pixel block located outside the arbitrary image feature from correlation determinations; and

identifying from the correlations a first sample pixel corresponding to the first reference pixel.

2. The method of claim 1 in which the first reference pixel and the first sample pixel are included in arbitrary first and second image features in the first and second video image frames, respectively, the arbitrary first image feature having an interior that is bounded by an image feature perimeter and the reference pixel block including a pixel block perimeter that conforms to the image feature perimeter.

3. The method of claim 2 in which the arbitrary first image feature includes plural image feature pixels, the method further comprising:

defining a reference pixel block of multiple pixels relative to each image feature pixel in the first video image frame and defining a corresponding sample pixel block of multiple sample pixels in the second video image frame, at least one of the reference pixel blocks being a non-quadrilateral polygonal array of pixels;

determining and storing for the pixels in the sample pixel block correlations to the image feature pixel relative to which the corresponding reference pixel block is defined; and

identifying from the correlations selected sample pixels in correlation with the image feature pixels relative to which the corresponding reference pixel blocks are defined.

4. The method of claim 1 in which determining correlations includes determining summed absolute errors between pixels of the sample pixel block and the reference pixel block.

5. The method of claim 4 in which the first sample pixel corresponding to the first reference pixel is the sample pixel for which the summed absolute error between the sample pixel block and the reference pixel block is minimal.

6. The method of claim 4 in which each of the reference and sample pixels is represented by three color component values and the summed absolute errors E are determined as:

##EQU4## in which r_ij, g_ij, and b_ij correspond to the color component values representing the reference pixels and r_ij '"'"', g_ij '"'"', and b_ij '"'"' correspond to the color component values representing the sample pixels.

7. The method of claim 6 in which the three color component values correspond to red, green, and blue color components.

8. The method of claim 1 in which the first video image frame precedes the second video image frame.

9. The method of claim 1 in which the reference pixel block is defined about the first reference pixel.

10. A block matching motion estimation method for estimating motion of pixels between first and second video image frames that include an arbitrary first image feature of plural image feature pixels, comprising:

identifying the arbitrary first image feature in the first video image frame;

defining a reference pixel block of multiple pixels relative to each image feature pixel in the first video image frame and a corresponding sample pixel block of multiple sample pixels in the second video image frame;

identifying for each reference pixel block in the first video image frame the pixels of the arbitrary first image feature; and

identifying from the sample pixels in the sample pixel block first sample pixels corresponding to the image feature pixels, including using shape of the arbitrary first image feature to exclude pixels in the reference pixel block located outside the arbitrary image feature from use in identifying the corresponding first sample pixels.

11. The method of claim 10 in which the reference pixel block is a non-quadrilateral polygonal array of pixels.

12. The method of claim 10 in which identifying the first sample pixel includes determining and storing for the sample pixels in the sample pixel block correlations to the image feature pixels the reference pixel block.

13. The method of claim 12 in which determining correlations includes determining summed absolute errors between pixels of the sample pixel block and the reference pixel block.

14. The method of claim 13 in which the first sample pixel corresponding to each image feature pixel is the sample pixel for which the summed absolute errors between pixel of the sample pixel block and the reference pixel block is minimal.

15. The method of claim 13 in which the reference and sample pixels is represented by three color component values and the summed absolute errors E are determined as:

##EQU5## in which r_ij, g_ij, and b_ij correspond to the color component values representing the reference pixels and r_ij '"'"', g_ij '"'"', and b_ij '"'"' correspond to the color component values representing the sample pixels.

16. The method of claim 15 in which the three color component values correspond to red, green, and blue color component and the terms r_ij, g_ij, and b_ij and r_ij '"'"', g_ij '"'"', and b_ij '"'"' correspond.

17. The method or claim 10 in which the first video image frame precedes the second video image frame.

18. A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames, the medium comprising:

programming for defining a reference pixel block of multiple pixels relative to a first reference pixel in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the reference pixel block being an array of pixels at least partially overlapping an arbitrary image feature in the first video image frame;

programming for determining and storing for the pixels in the sample pixel block correlations to the reference pixel block and the first reference pixel, including using shape of an arbitrary image feature to exclude pixels in the reference pixel block located outside the arbitrary image feature from correlation determinations; and

programming for identifying from the correlations a first sample pixel corresponding to the first reference pixel.

19. The medium of claim 18 in which the first reference pixel and the first sample pixel are included in arbitrary first and second image features in the first and second video image frames, respectively, the arbitrary first image feature having plural image feature pixels in an interior that is bounded by an image feature perimeter, the reference pixel block including a pixel block perimeter that conforms to the image feature perimeter, the medium further comprising:

programming for defining a reference pixel block of multiple pixels relative to each image feature pixel in the first video image frame and defining a corresponding sample pixel block of multiple sample pixels in the second video image frame, at least one of the reference pixel blocks being a non-quadrilateral polygonal array of pixels;

programming for determining and storing for the pixels in the sample pixel block a correlation to the image feature pixel relative to which the corresponding reference pixel block is defined; and

programming for identifying from the correlations a selected sample pixel in correlation with the image feature pixel relation to which the corresponding reference pixel block is defined.

20. A block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, comprising:

defining a reference pixel block of multiple pixels relative to a first reference pixel in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the reference pixel block being a non-quadrilateral polygonal arrays of pixels;

defining relative to the first reference pixel a preliminary quadrilateral reference pixel block of plural pixels;

identifying the pixels of the preliminary quadrilateral pixel block as to whether they are in the interior of the arbitrary first image feature, at least one of the pixels in the preliminary quadrilateral pixel block not being in the interior of the arbitrary first image feature; and

establishing as the reference pixel block the pixels of the preliminary quadrilateral pixel block in the interior of the arbitrary first image feature;

determining and storing for the pixels in the sample pixel block correlations to the pixels in the reference pixel block; and

identifying from the correlations a first sample pixel corresponding to the first reference pixel;

wherein the first reference pixel and the first sample pixel are included in arbitrary first and second image features in the first and second video image frames, respectively, the arbitrary first image feature having an interior that is bounded by an image feature perimeter and the reference pixel block including a pixel block perimeter that conforms to the image feature perimeter.

21. A block matching motion estimation method for estimating motion of pixels between first and second video image frames that include an arbitrary first image feature of plural image feature pixels, comprising:

identifying the arbitrary first image feature in the first video image frame, the arbitrary first image feature having an interior that is bounded by an image feature perimeter;

defining a reference pixel block of multiple pixels relative to each image feature pixel in the first video image frame and a corresponding sample pixel block of multiple sample pixels in the second video image frame;

identifying for each reference pixel block in the first video image frame the pixels of the arbitrary first image feature;

defining relative to each image feature pixel a preliminary quadrilateral reference pixel block of plural pixels;

identifying the pixels of the preliminary quadrilateral reference pixel block as to whether they are in the interior of the arbitrary first image feature;

establishing as the reference pixel block the pixels of the preliminary quadrilateral reference pixel block in the interior of the arbitrary first image feature; and

identifying from the sample pixels in the sample pixel block first sample pixels corresponding to the image feature pixels.

22. The method of claim 21 in which at least one of the pixels in the preliminary quadrilateral pixel block is not in the interior of the arbitrary first image feature and the reference pixel block is defined to include a pixel block perimeter that conforms to the image feature perimeter.

23. A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames, the medium comprising:

programming for defining a reference pixel block of multiple pixels relative to a first reference pixel in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the reference pixel block being a non-quadrilateral polygonal array of pixels, and the first reference pixel and the first sample pixel being included in arbitrary first and second image features in the first and second video image frames, respectively, the arbitrary first image feature having an interior that is bounded by an image feature perimeter and the reference pixel block including a pixel block perimeter that conforms to the image feature perimeter;

programming for defining relative to the first reference pixel a preliminary quadrilateral reference pixel block of plural pixels;

programming for identifying the pixels of the preliminary quadrilateral pixel block as to whether they are in the interior of the arbitrary first image feature, at least one of the pixels in the preliminary quadrilateral pixel block not being in the interior of the arbitrary first image feature;

programming for establishing as the reference pixel block the pixels of the preliminary quadrilateral pixel block in the interior of the arbitrary first image feature;

programming for determining and storing for the pixels in the sample pixel block correlations to the reference pixel block and the first reference pixel; and

programming for identifying from the correlations a first sample pixel corresponding to the first reference pixel.