Motion segmentation system with multi-frame hypothesis tracking

• US 7,088,773 B2
• Filed: 01/17/2002
• Issued: 08/08/2006
• Est. Priority Date: 01/17/2002
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Carrig, James J., Paniconi, Marco
• Primary Examiner(s): RAO, ANAND SHASHIKANT
• Application Number:
  US10/052,699
• Publication Number:
  US 20030133503A1
• Time in Patent Office: 1,664 Days
• Field of Search: 37524011-24029, 348143-162, 725105-109
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

In one embodiment, a video encoder encodes digital video using motion segmentation. According to one embodiment, motion segmentation is performed using multiple frames. The motion segmentation may operate by determining multiple classification hypotheses and by re-classifying poorly classified regions according to the multi-frame hypothesis tracking algorithm. This involves determining a similarity measure for each hypothesis class, and then assigning a classification to the region with the hypothesis class that is most similar or consistent with past or future data. This hypothesis tracking algorithm for re-classification can handle inherent problems like occlusion and ambiguous motion classification, that plague standard methods. In another embodiment, the motion segmentation algorithm may be integrated into a larger video encoding system. The system may incorporate motion estimation, motion classification, identification and selection of poor blocks, and re-classification of poor blocks using the multi-frame hypothesis tracking algorithm.

Claims

1. A method comprising:

identifying a plurality of motion classes for a frame of video data, each motion class having at least one region classified thereto, wherein a region is poorly classified if it is classified as belonging to an improper class;

determining a region to be a poorly classified region;

forming a set of class hypotheses for the poorly classified region, the set of class hypotheses containing at least one possible motion class;

determining a similarity measure for the poorly classified region with respect to a set of past and future video data, the similarity measure indicating a degree of consistency between a hypothesis for the motion of the poorly classified region and the motion of the corresponding regions in past and future frames; and

reclassifying the poorly classified region to one of the at least one possible motion classes according to the similarity measure.

2. The method of claim 1, wherein the set of past and future video data comprises:

at least one preceding frame of video data; and

at least one succeeding frame of video data.

3. The method of claim 1, wherein reclassifying according to the similarity measure includes:

determining which of the at least one possible motion classes are suitable for the poorly classified region using the similarity measure.

4. The method of claim 3 wherein reclassifying further includes:

assigning the poorly classified region to a motion class of the at least one possible motion class with an optimal similarity measure.

5. The method of claim 4, wherein the optimal similarity measure is a minimum similarity measure.

6. The method of claim 1, wherein determining a region to be a poorly classified region comprises:

measuring the distortion of a region;

comparing the measured distortion of the region to a distortion threshold; and

determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

7. The method of claim 1, wherein determining a region to be a poorly classified region comprises:

measuring the prediction error of a region;

comparing the measured prediction error of the region to a prediction error threshold; and

determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

8. The method of claim 1, wherein the reclassification of a poorly classified region in an image comprises finding the minimum of a measure over all class hypotheses according to the equations arg min_i(A(K_i)), where K_i is a class hypothesis, indexed by i,

$A$

( K i ) = min ⁡

( A past ⁡

( K i ) , A past ⁡

( K i ) ) , A past/future = 1 N ⁢

∑

t ⁢

∑

B ⁢

D ⁡

( K t p / f , K i ) ;

A_past/future is a measure of the consistency through the distortion quantity, D, between a hypothetical class K_i and its corresponding class K^p/f on past/future frames.

9. A computer-readable medium comprising computer program instructions which, when executed by a processor, cause the processor to perform a hypothesis algorithm comprising:

identifying a plurality of motion classes for a frame of video data, each motion class having at least one region classified thereto, wherein a region is poorly classified if it is classified as belonging to an improper class;

determining a region to be a poorly classified region;

forming a set of class hypotheses for the poorly classified region, the set of class hypotheses containing at least one possible motion class;

determining a similarity measure for the poorly classified region with respect to a set of past and future video data, the similarity measure indicating a degree of consistency between a hypothesis for the motion of the poorly classified region and the motion of the corresponding regions in past and future frames; and

reclassifying the poorly classified region to one of the at least one possible motion classes according to the similarity measure.

10. The computer-readable medium of claim 9, wherein the set of past and future video data comprises:

at least one preceding frame of video data; and

at least one succeeding frame of video data.

11. The computer-readable medium of claim 9, wherein determining a region to be a poorly classified region comprises:

measuring the distortion of a region;

comparing the measured distortion of the region to a distortion threshold; and

determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

12. The computer-readable medium of claim 9, wherein determining a region to be a poorly classified region comprises:

measuring the prediction error of a region;

comparing the measured prediction error of the region to a prediction error threshold; and

determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

13. A video device comprising:

means for forming a set of class hypotheses for a region of a frame of video data;

means for determining a similarity measure for the region with respect to a set of past and future video data; and

means for reclassifying the region according to the similarity measure if the region has been poorly classified as belonging to an improper class.

14. The video device of claim 13, wherein the set of past and future data comprises:

at least one preceding frame of video data; and

at least one succeeding frame of video data.

15. The video device of claim 13, further comprising:

means for determining a region to be poorly classified by a) measuring the distortion of a region, b) comparing the measured distortion of the region to a distortion threshold, and c) determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

16. The video device of claim 13, further comprising:

means for determining a region to be poorly classified by a) measuring the prediction error of a region, b) comparing the measured prediction error of the region to a prediction error threshold, and c) determining the region to be poorly classified if the measured prediction is greater than the prediction error threshold.

17. A video device comprising:

a motion compensation component configured to form a set of class hypotheses for a region of a frame of video data, to determine a similarity measure for the region with respect to a set of past and future data, and to reclassify the region according to the similarity measure if the region has been poorly classified as belonging to an improper class.

18. The video device of claim 17, wherein the set of past and future data comprises:

at least one preceding frame of video data; and

at least one succeeding frame of video data.

19. The video device of claim 17, wherein the region is reclassified by finding the minimum similarity measure and assigning the region to a class having the minimum similarity measure.

20. A method comprising:

performing motion estimation for a frame containing a plurality of motion classes, each motion class having at least one region classified thereto, wherein a region is poorly classified if it is identified as belonging to an improper class;

identifying at least one poorly classified region;

selecting a new motion class for each poorly classified region;

reclassifying the poorly classified region to the new motion class; and

re-estimating the poorly classified region based on a result of reclassifying the poorly classified region.

21. The method of claim 20 wherein reclassifying includes:

using a set of past and future data according to a hypothesis tracking algorithm.