Efficient encoding of video frames in a distributed video coding environment

• US 8,451,905 B1
• Filed: 02/25/2011
• Issued: 05/28/2013
• Est. Priority Date: 02/25/2011
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Rajagopalan, Shyam Sundar, Pai, Deepak, Revankar, Shriram V., Sood, Arsh, Chaitanya, Parimi Krishna
• Primary Examiner(s): Czekaj, David
• Assistant Examiner(s): Beck, Leron
• Application Number:
  US13/035,223
• Publication Number:
  US 20130128962A1
• Time in Patent Office: 823 Days
• Field of Search: 37524001-24029
• US Class Current: 375/240.24
• CPC Class Codes: H04N 19/127 Prioritisation of hardware or computational resources
• CPC Class Codes: H04N 19/157 Assigned coding mode, i.e. the coding mode being predefined or preselected to be further used for selection of another element or parameter
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field

Abstract

Systems and methods are presented for processing sequences of video frames in a distributed video coding environment. Video frames chosen as key video frames are encoded in their entirety on a sending device, and the encodings are forwarded to a receiving device. Non-key video frames are partitioned into blocks of pixels which are individually processed at the sending device. Some pixel blocks are designated for reconstruction at the receiving device using a similar corresponding pixel block from a previous video frame, and the sending device does not encode those pixel blocks. Other pixel blocks are compressed at the sending device into representations that are sent to the receiving device to facilitate reconstruction of the other pixel blocks at the receiving device. Exceptional efficiency and accuracy may be achieved by employing spatiograms and singular value decompositions in processing pixel blocks of the non-key video frames at the sending device.

Claims

1. A method, comprising:

processing a sequence of video frames by a computing device, in which at least some of the video frames are determined as key video frames and others of the video frames are determined as non-key video frames, said processing comprises, for video frames of the sequence of video frames;

determining whether the video frame is a key video frame or a non-key video frame;

if the video frame is determined to be a key video frame, encoding of the key video frame for reception by a receiving device; and

if the video frame is determined to be a non-key video frame;

for a particular pixel block of one or more pixel blocks of the non-key video frame, determining whether the particular pixel block is within a threshold of similarity to a corresponding previous pixel block of a previous video frame in the sequence of video frames;

in response to said determining that the particular pixel block is within the threshold of similarity to the corresponding previous pixel block, generating an indication usable by the receiving device to reconstruct the particular pixel block of the non-key video frame via the corresponding previous pixel block of the previous video frame; and

in response to said determining that the particular pixel block of the non-key video frame is not within the threshold of similarity to the corresponding previous pixel block, encoding the particular pixel block of the non-key video frame based at least in part on on contents of the non-key video frame that contains the particular pixel block and not on contents of the previous key video frame, nor on contents of any other video frame positioned between the previous key video frame and the nonkey video frame in the sequence of video frames.

2. The method of claim 1, wherein said determining whether the particular pixel block is within a threshold of similarity to the corresponding previous pixel block of the previous video frame in the sequence of video frames comprises:

determining a difference between a spatiogram of the particular pixel block and a spatiogram of the corresponding previous pixel block of the previous video frame; and

comparing the difference with the threshold of similarity;

wherein the spatiogram of the particular pixel block preserves spatial information of the particular pixel block, and the spatiogram of the corresponding previous pixel block of the previous video frame preserves spatial information of the corresponding previous pixel block.

3. The method of claim 1, wherein the encoding of the particular pixel block of the non-key video frame is based on a singular value decomposition of a matrix of pixel values for the particular pixel block.

4. The method of claim 3, further comprising determining an approximation matrix that approximates the matrix of pixel values for the particular pixel block, wherein said determining the approximation matrix is based on discarding one or more non-zero singular values obtained in the singular value decomposition, wherein the rank of the approximation matrix is less than the rank of the matrix of pixel values for the particular pixel block.

5. The method of claim 4, further comprising setting a global matrix rank limit, to be applied during said processing of each non-key video frame of the sequence of video frames, so that, for each said approximation matrix, the rank of said approximation matrix does not exceed the global matrix rank limit.

6. The method of claim 4, wherein said calculating the encoding of the particular pixel block of the non-key video frame comprises encoding a singular value decomposition of the approximation matrix, and said encoding the singular value decomposition of the approximation matrix requires fewer bits than encoding the singular value decomposition of the matrix of pixel values for the particular pixel block.

7. The method of claim 1, wherein said processing a sequence of video frames is performed on a mobile computing device.

8. The method of claim 1, wherein said processing the sequence of video frames is performed concurrently with capturing the sequence of video frames in real time.

9. A system, comprising:

a processor; and

a memory coupled to the processor, wherein the memory stores program instructions for;

processing a sequence of video frames in which at least some of the video frames are determined as key video frames and others of the video frames are determined as non-key video frames, said processing comprises, for video frames of the sequence of video frames;

determining whether the video frame is a key video frame or a non-key video frame;

if the video frame is determined to be a key video frame, encoding the key video frame; and

if the video frame is determined to be a non-key video frame;

for a particular pixel block of one or more pixel blocks of the non-key video frame, determining whether the particular pixel block is within a threshold of similarity to a corresponding previous pixel block of a previous video frame in the sequence of video frames;

in response to said determining that the particular pixel block is within the threshold of similarity to the corresponding previous pixel block, generating an indication that is usable by a receiving device to reconstruct the particular pixel block of the non-key video frame via the corresponding previous pixel block of the previous video frame; and

in response to said determining that the particular pixel block of the non-key video frame is not within the threshold of similarity to the corresponding previous pixel block, encoding the particular pixel block of the non-key video frame based at least in part on contents of the non key video frame that contains the particular pixel block and not on contents of the previous key video frame, nor on contents of any other video frame positioned between the previous key video frame and the nonkey video frame in the sequence of video frames.

10. The system of claim 9, wherein said determining whether the particular pixel block is within a threshold of similarity to the corresponding previous pixel block of the previous video frame in the sequence of video frames comprises:

determining a difference between a spatiogram of the particular pixel block and a spatiogram of the corresponding previous pixel block of the previous video frame; and

comparing the difference with the threshold of similarity;

wherein the spatiogram of the particular pixel block preserves spatial information of the particular pixel block, and the spatiogram of the corresponding previous pixel block of the previous video frame preserves spatial information of the corresponding previous pixel block.

11. The system of claim 9, wherein the encoding of the particular pixel block of the non-key video frame is based on a singular value decomposition of a matrix of pixel values for the particular pixel block.

12. The system of claim 11, wherein said processing further comprises determining an approximation matrix that approximates the matrix of pixel values for the particular pixel block, wherein said determining the approximation matrix is based on discarding one or more non-zero singular values obtained in the singular value decomposition, wherein the rank of the approximation matrix is less than the rank of the matrix of pixel values for the particular pixel block.

13. The system of claim 12, wherein said processing further comprises setting a global matrix rank limit, to be applied during said processing of each non-key video frame of the sequence of video frames, so that, for each said approximation matrix, the rank of said approximation matrix does not exceed the global matrix rank limit.

14. The system of claim 12, wherein said calculating the encoding of the particular pixel block of the non-key video frame comprises encoding a singular value decomposition of the approximation matrix, and said encoding the singular value decomposition of the approximation matrix requires fewer bits than encoding the singular value decomposition of the matrix of pixel values for the particular pixel block.

15. A tangible computer-readable storage device

comprising instructions stored thereon that, responsive to execution by a computing device, causes the computing device to perform operations comprising:

processing a sequence of video frames, in which at least some of the video frames are determined as key video frames and others of the video frames are determined as non-key video frames, said processing comprises, for video frames of the sequence of video frames;

determining whether the video frame is a key video frame or a non-key video frame;

if the video frame is determined to be a key video frame, sending an encoding of the key video frame for reception by a receiving device; and

if the video frame is determined to be a non-key video frame;

for a particular pixel block of one or more pixel blocks of the non-key video frame, determining whether the particular pixel block is within a threshold of similarity to a corresponding previous pixel block of a previous video frame in the sequence of video frames;

in response to said determining that the particular pixel block is within the threshold of similarity to the corresponding previous pixel block, generating an indication usable by the receiving device to reconstruct the particular pixel block of the non-key video frame via the corresponding previous pixel block of the previous video frame; and

in response to said determining that the particular pixel block of the non-key video frame is not within the threshold of similarity to the corresponding previous pixel block, encoding the particular pixel block of the non-key video frame based at least in part on contents of the non-key video frame that contains the particular pixel block and not on contents of the previous key video frame, nor on contents of any other video frame positioned between the previous key video frame and the nonkey video frame in the sequence of video frames.

16. The tangible computer-readable storage device of claim 15,

wherein said determining whether the particular pixel block is within a threshold of similarity to the corresponding previous pixel block of the previous video frame in the sequence of video frames comprises:

determining a difference between a spatiogram of the particular pixel block and a spatiogram of the corresponding previous pixel block of the previous video frame; and

comparing the difference with the threshold of similarity;

wherein the spatiogram of the particular pixel block preserves spatial information of the particular pixel block, and the spatiogram of the corresponding

previous pixel block of the previous video frame preserves spatial information of the corresponding previous pixel block.

17. The tangible computer-readable storage device of claim 15, wherein the encoding of the particular pixel block of the non-key video frame is based on a singular value decomposition of a matrix of pixel values for the particular pixel block.

18. The tangible computer-readable storage device of claim 17, wherein said processing further comprises determining an approximation matrix that approximates the matrix of pixel values for the particular pixel block, wherein said determining the approximation matrix is based on discarding one or more non-zero singular values obtained in the singular value decomposition, wherein the rank of the approximation matrix is less than the rank of the matrix of pixel values for the particular pixel block.

19. The tangible computer-readable storage device of claim 18, wherein said processing further comprises setting a global matrix rank limit, to be applied during said processing of each non-key video frame of the sequence of video frames, so that, for each said approximation matrix, the rank of said approximation matrix does not exceed the global matrix rank limit.

20. The tangible computer-readable storage device of claim 18, wherein said calculating the encoding of the particular pixel block of the non-key video frame comprises encoding a singular value decomposition of the approximation matrix, and said encoding the singular value decomposition of the approximation matrix requires fewer bits than encoding the singular value decomposition of the matrix of pixel values for the particular pixel block.