Method for segmenting 3D objects from compressed videos

• US 7,142,602 B2
• Filed: 05/21/2003
• Issued: 11/28/2006
• Est. Priority Date: 05/21/2003
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Porikli, Fatih M., Sun, Huifang, Divakaran, Ajay
• Primary Examiner(s): VO, TUNG T
• Application Number:
  US10/442,417
• Publication Number:
  US 20040233987A1
• Time in Patent Office: 1,287 Days
• Field of Search: 375/240.01, 375/240.12, 375/240.16, 375/240.19, 382/173, 382/291, 345/419
• US Class Current: 375/240.16
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20048 Transform domain processing
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• 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/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression

Abstract

A method segments a video into objects, without user assistance. An MPEG compressed video is converted to a structure called a pseudo spatial/temporal data using DCT coefficients and motion vectors. The compressed video is first parsed and the pseudo spatial/temporal data are formed. Seeds macro-blocks are identified using, e.g., the DCT coefficients and changes in the motion vector of macro-blocks.

A video volume is “grown” around each seed macro-block using the DCT coefficients and motion distance criteria. Self-descriptors are assigned to the volume, and mutual descriptors are assigned to pairs of similar volumes. These descriptors capture motion and spatial information of the volumes. Similarity scores are determined for each possible pair-wise combination of volumes. The pair of volumes that gives the largest score is combined iteratively. In the combining stage, volumes are classified and represented in a multi-resolution coarse-to-fine hierarchy of video objects.

Claims

1. A method for segmenting a three dimensional object from a compressed video, the compressed video including a plurality of frames separated in time, and each frame including a plurality of macro-blocks separated in space, comprising:

parsing transformed coefficients for each macro block;

determining a spatial/temporal gradient for each macro-block based on the transformed coefficients;

selecting a particular macro-block with a minimum spatial/temporal gradient magnitude as a seed macro-block;

measuring distances between the seed macro-block and spatially and temporally adjacent macro-blocks based on the transformed coefficients; and

growing a volume around the seed macro-block using the adjacent macro-blocks having distances less than a predetermined threshold.

2. The method of claim 1 wherein the plurality of frames are a single shot.

3. The method of claim 1 wherein the plurality of frames include I-frames having DCT coefficients.

4. The method of claim 3 wherein the plurality of frames include P-frames including motion vectors.

5. The method of claim 1 wherein the transformed coefficients are wavelets.

6. The method of claim 1 wherein the transformed coefficients are fast Fourier transform coefficients.

7. The method of claim 1 wherein there is a set of transformed coefficients for each color channel of the compressed video.

8. The method of claim 2 wherein the single shot is detected from the transformed coefficients.

9. The method of claim 4 wherein the transformed coefficients of each macro-block are represented as spatial/temporal data P(m, n, t, k), where (m,n) represents a macro-block index within a particular frame t, and represents a particular set of transformed coefficients within the macro-block.

10. The method of claim 9 wherein the spatial/temporal gradient magnitude is determined as

$$

∇

P ⁡

( m , n , t , k ) 

= ∑

k ⁢

w ⁡

( k ) ⁡

[ α

m ⁢



P ⁡

( m + h , n , t , k ) - P ⁡

( m - h , n , t , k ) 

+ α

n ⁢



P ⁡

( m , n + h , t , k ) - P ⁡

( m , n - h , t , k ) 

+ α

t ⁢



P ⁡

( m , n , t + h , k ) - P ⁡

( m , n , t - h , k ) 

] ,

where w(k) is a weight of a corresponding set of transformed coefficients, α

_m and α

_n are weights of the DCT coefficients, α

_t is a weight of the motion vector, and h is a derivative step size.

11. The method of claim 10 wherein the minimum spatial/temporal gradient magnitude is min|∇

VP(m, n, t, k)|.

12. The method of claim 1 wherein the selecting, measuring, and growing are repeated until no macro-blocks remain to generate a plurality of volumes.

13. The method of claim 9 wherein the distance between the seed macro-block v and a particular adjacent macro-block q is

d(v, q)=∥

P(q)−

v∥

=∥

P(m, n, t)−

v∥

, where ∥

•

∥

is a particular distance function.

14. The method of claim 13 further comprising:

updating a feature vector v for the seed macro-block while growing the volume as

$d\le <br><br>\mathrm{\lambda <br><br>}\Rightarrow <br><br>\{\begin{array}{cc}\mathrm{true}& v=\frac{N<br><br><br><br>v+P<br><br>\left(m,n,t\right)}{N+1}\\ \mathrm{false}& N=N+1\end{array},$

where d is the measured distance, λ

is the threshold, and N is a next adjacent macro-block.

15. The method of claim 12 further comprising:

subsuming individual macro-blocks of a particular volume smaller than a predetermined size into larger similar ones of the plurality of volumes.

16. The method of claim 1 further comprising:

assigning a set of self descriptors to the volume.

17. The method of claim 16 wherein the self descriptors include an average of the transformed coefficients of the macro-blocks in the volume, a number of macro-blocks in the volume, a number of macro-blocks on a surface of the volume, a compactness ratio of the volume, a trajectory of the volume, a length of the trajectory, and averaged coordinates of the macro-blocks of the volume.

18. The method of claim 12 further comprising:

assigning a set of mutual descriptors to each possible pair of volumes.

19. The method of claim 18 wherein the mutual descriptors include an average distance between trajectories of the pair of volumes, a variance of the distance of the trajectories, a maximum distance between the trajectories, an average change in the distance between the trajectories, an accumulated distance change of the trajectories, a compactness of the pair of volumes, a color difference between the pair of volumes, a number of frames where the pair of volumes coexists.

20. The method of claim 12 further comprising:

assigning a set of self descriptors to the volume; and

assigning a set of mutual descriptors to each possible pair of volumes.

21. The method of claim 20 further comprising:

merging the plurality of volumes according to the set of self descriptors and the set of mutual descriptors to segment the compressed video into a multi-resolution 3D video objects.

22. The method of claim 21 wherein the merging is pair-wise.

23. The method of claim 21 wherein the merged volumes are maintained in a video object tree.