SYSTEM AND METHOD FOR MOTION VECTOR COLLECTION BASED ON K-MEANS CLUSTERING FOR MOTION COMPENSATED INTERPOLATION OF DIGITAL VIDEO

• US 20090060042A1
• Filed: 08/28/2007
• Published: 03/05/2009
• Est. Priority Date: 08/28/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Yeong-Taeg, Lertrattanapanich, Surapong
• Granted Patent: US 8,861,603 B2
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence

Abstract

A system and method of collection motion vectors for motion compensated interpolation of digital video are disclosed. For example, one embodiment includes a method of identifying motion vectors for interpolating a portion of a digital video signal. The method comprises identifying a plurality of motion vectors indicative of differences between first and second frames of a digital video signal, assigning each of the plurality of motion vectors to one of a plurality of clusters, selecting at least one motion vector assigned to each of the plurality of clusters, and generating at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters. Other embodiments include a system and device configured to perform the method.

Claims

1. A method of identifying motion vectors for interpolating a portion of a digital video signal, the method comprising:

identifying a plurality of motion vectors indicative of differences between first and second frames of a digital video signal;

assigning each of the plurality of motion vectors to one of a plurality of clusters;

selecting at least one motion vector assigned to each of the plurality of clusters; and

generating at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters.

2. The method of claim 1, further comprising:

outputting the frames in an output digital video signal, wherein the third frame is output between the first and second frames, and

displaying the third frame between the first and second frames.

3. The method of claim 1, wherein identifying the plurality of motion vectors comprises identifying motion vectors associated with portions of the first frame that are spatially proximal to a portion of the first frame that corresponds to the generated portion of the third frame.

4. The method of claim 1, wherein assigning each of the plurality of motion vectors to one of the plurality of clusters comprises iteratively assigning each of the plurality of motion vectors to one of the plurality of clusters.

5. The method of claim 4, wherein iteratively assigning each of the plurality of motion vectors to one of the plurality of clusters comprises:

assigning each of the plurality of motion vectors to one of the clusters;

calculating the centroid of each of the clusters; and

determining whether the centroid of each cluster has changed from a prior iteration by less than a predetermined threshold.

6. The method of claim 5, wherein assigning each of the plurality of motion vectors to one of the clusters comprises assigning each of the plurality of motion vectors based on a distance to a centroid of each cluster.

7. The method of claim 1, wherein selecting the at least one motion vector assigned to each of the plurality of clusters comprises selecting the at least one motion vector closest to a centroid of each cluster.

8. The method of claim 1, wherein generating the at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters comprises generating a block of the third frame based on the at least one motion vector selected for each of the plurality of clusters.

9. The method of claim 8, wherein generating the at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters comprises generating the at least a portion of the third frame based on a number of motion vectors in each of the plurality of clusters.

10. The method of claim 8, wherein the block comprises a plurality of adjacent pixels of the frame.

11. A system for identifying motion vectors for interpolating a portion of a digital video signal, the device comprising:

a memory configured to store a plurality of motion vectors indicative of differences between first and second frames of a digital video signal; and

a processor configured to;

assign each of the plurality of motion vectors to one of a plurality of clusters;

select at least one motion vector assigned to each of the plurality of clusters; and

generate at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters.

12. The system of claim 11, further comprising:

a receiver configured to receive the first and second frames, and

a display configured to display the third frame between the first and second frames.

13. The system of claim 11, wherein the processor is configured to identify motion vectors associated with portions of the first frame that are spatially proximal to a portion of the first frame that corresponds to the generated portion of the third frame.

14. The system of claim 11, wherein the processor is configured to iteratively assign each of the plurality of motion vectors to one of the plurality of clusters.

15. The system of claim 14, wherein the processor is configured to:

assign each of the plurality of motion vectors to one of the clusters;

calculate the centroid of each of the clusters; and

determine whether the centroid of each cluster has changed from a prior iteration by less than a predetermined threshold.

16. The system of claim 15, wherein the processor is configured to:

assign each of the plurality of motion vectors based on a distance to a centroid of each cluster; and

select the at least one motion vector assigned to each of the plurality of clusters by selecting the at least one motion vector closest to a centroid of each cluster.

17. The system of claim 11, wherein the processor is configured to generate at least one block of the third frame based on the at least one motion vector selected for each of the plurality of clusters.

18. The system of claim 11, wherein the processor is configured to generate the at least a portion of the third frame based on a number of motion vectors in each of the plurality of clusters.

19. A system for identifying motion vectors for interpolating a portion of a digital video signal, the system comprising:

means for storing a plurality of motion vectors indicative of differences between first and second frames of a digital video signal; and

means for processing the digital video signal, the processing means being configured to;

assign each of the plurality of motion vectors to one of a plurality of clusters;

select at least one motion vector assigned to each of the plurality of clusters; and

generate at least a portion of a third frame based on the at least one motion vector selected for each of the plurality of clusters.

20. The system of claim 19, further comprising:

means for receiving the first and second frames, and

means for displaying the third frame between the first and second frames.

21. The system of claim 19, wherein the processing means is configured to identify motion vectors associated with portions of the first frame that are spatially proximal to a portion of the first frame that corresponds to the generated portion of the third frame.

22. The system of claim 19, wherein the processing means is configured to iteratively assign each of the plurality of motion vectors to one of the plurality of clusters.

23. The system of claim 22, wherein the processing means is configured to:

assign each of the plurality of motion vectors to one of the clusters;

calculate the centroid of each of the clusters; and

determine whether the centroid of each cluster has changed from a prior iteration by less than a predetermined threshold.

24. The system of claim 23, wherein the processing means is configured to:

assign each of the plurality of motion vectors based on a distance to a centroid of each cluster; and

select the at least one motion vector assigned to each of the plurality of clusters by selecting the at least one motion vector closest to the centroid of each cluster.

25. The system of claim 22, wherein the processing means is configured to generate at least one block of the third frame based on the at least one motion vector selected for each of the plurality of clusters.