Decimated sliding windows for multi-reference prediction in video coding

1. A method for encoding a video stream having a plurality of frames, comprising:

allocating a first plurality of buffers, each buffer of the first plurality of buffers configured to store one frame of the plurality of frames;

allocating a second plurality of buffers, each buffer of the second plurality of buffers configured to store one frame of the plurality of frames;

selecting a reference frame for encoding at least one of the plurality of frames;

assigning a picture ID number to the reference frame;

if the first plurality of buffers is full of reference frames:

A) determining a first least recently used reference frame from the first plurality of buffers;

B) determining, based on the picture ID number of the first least recently used reference frame and a first decimation factor, if the first least recently used reference frame is to be stored at a buffer of the second plurality of buffers;

C) storing the first least recently used reference frame at the buffer of the second plurality of buffers if it is determined that the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers; and

D) removing the first least recently used reference frame from the first plurality of buffers;

storing the reference frame at a buffer of the first plurality of buffers;

encoding the at least one of the plurality of frames using the reference frame into an encoded video bitstream; and

including the picture ID number of the reference frame and the first decimation factor in the encoded video bitstream.

2. The method of claim 1 wherein storing the first least recently used reference frame at the buffer of the second plurality of buffers comprises:

if the plurality of second buffers is full of reference frames:

determining a second least recently used reference frame from the second plurality of buffers; and

removing the second least recently used reference frame from the second plurality of buffers.

3. The method of claim 2 , further comprising:

allocating a third plurality of buffers, each buffer of the third plurality of buffers configured to store one frame of the plurality of frames;

determining, based on the picture ID number of the second least recently used reference frame and a second decimation factor, if the second least recently used reference frame is to be stored at a buffer of the third plurality of buffers; and

storing the second least recently used reference frame at the buffer of the third plurality of buffers if it is determined that the second least recently used reference frame is to be stored at the buffer of the third plurality of buffers.

4. The method of claim 3 wherein the first decimation factor is equal to the second decimation factor.

5. The method of claim 1 wherein determining if the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers comprises:

determining if the picture ID number of the first least recently used reference frame is evenly divisible by the first decimation factor, wherein the first decimation factor is an integer.

6. The method of claim 1 wherein encoding the at least one of the plurality of frames using the reference frame comprises performing motion prediction for the at least one of the plurality of frames using the reference frame.

7. The method of claim 1 wherein the first plurality of buffers and the second plurality of buffers are each organized as a first-in-first-out stack.

8. The method of claim 1 , further comprising:

defining an array index for the first plurality of buffers; and

defining a linked list that keeps track of an order in which reference frames are stored in the first plurality of buffers; wherein

storing the reference frame at the buffer of the first plurality of buffers comprises:

inserting the picture ID number of the reference frame in an index of the array index, the index associated with the buffer of the first plurality of buffers; and

updating the linked list.

9. The method of claim 8 wherein removing the first least recently used frame comprises:

setting an index of the array index that is associated with a buffer of the first plurality of buffers storing the first least recently used reference frame to a value indicating that the buffer storing the first least recently used reference frame is unused before storing the reference frame at the first plurality of buffers; and

updating the linked list to indicate a new least recently used reference frame.

10. A method for decoding an encoded video stream having a plurality of frames, comprising:

receiving the encoded video stream, the encoded video stream including a picture ID number assigned to a reference frame used to encode at least one of the plurality of frames and a decimation factor;

allocating a first plurality of buffers, each buffer of the first plurality of buffers configured to store one frame of the plurality of frames;

allocating a second plurality of buffers, each buffer of the second plurality of buffers configured to store one frame of the plurality of frames;

decoding the reference frame;

if the first plurality of buffers is full of reference frames:

A) determining a first least recently used reference frame from the first plurality of buffers;

B) determining, based on the picture ID number of the first least recently used reference frame and a first decimation factor, if the first least recently used reference frame is to be stored at a buffer of the second plurality of buffers;

C) storing the first least recently used reference frame at the buffer of the second plurality of buffers if it is determined that the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers; and

D) removing the first least recently used reference frame from the first plurality of buffers;

storing the reference frame at a buffer of the first plurality of buffers; and

decoding the at least one of the plurality of frames using the reference frame.

11. The method of claim 10 wherein determining if the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers comprises:

determining if the picture ID number of the first least recently used reference frame is evenly divisible by the first decimation factor, wherein the first decimation factor is an integer.

12. The method of claim 10 wherein storing the first least recently used reference frame at the buffer of the second plurality of buffers comprises:

if the plurality of second buffers is full of reference frames:

determining a second least recently used reference frame from the second plurality of buffers; and

removing the second least recently used reference frame from the second plurality of buffers.

13. The method of claim 12 , further comprising:

allocating a third plurality of buffers, each buffer of the third plurality of buffers configured to store one frame of the plurality of frames;

determining, based on the picture ID number of the second least recently used reference frame and a second decimation factor, if the second least recently used reference frame is to be stored at a buffer of the third plurality of buffers; and

storing the second least recently used reference frame at the buffer of the third plurality of buffers if it is determined that the second least recently used reference frame is to be stored at the buffer of the third plurality of buffers.

14. The method of claim 10 wherein decoding the at least one of the plurality of frames using the reference frame comprises performing motion prediction for the at least one of the plurality of frames using the reference frame.

15. The method of claim 14 wherein the first plurality of buffers and the second plurality of buffers are each organized as a first-in-first-out stack.

16. An apparatus for encoding a video stream having a plurality of frames, comprising:

a memory; and

a processor configured to execute instructions stored in the memory to:

allocate a first plurality of buffers, each buffer of the first plurality of buffers configured to store one frame of the plurality of frames;

allocate a second plurality of buffers, each buffer of the second plurality of buffers configured to store one frame of the plurality of frames;

select a reference frame for encoding at least one of the plurality of frames;

assign a picture ID number to the reference frame;

if the first plurality of buffers is full of reference frames:

A) determine a first least recently used reference frame from the first plurality of buffers;

B) determine, based on the picture ID number of the first least recently used reference frame and a first decimation factor, if the first least recently used reference frame is to be stored at a buffer of the second plurality of buffers;

C) store the first least recently used reference frame at the buffer of the second plurality of buffers if it is determined that the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers; and

D) remove the first least recently used reference frame from the first plurality of buffers;

store the reference frame at a buffer of the first plurality of buffers;

encode the at least one of the plurality of frames using the reference frame into an encoded video bitstream; and

include the picture ID number of the reference frame and the first decimation factor in the encoded video bitstream.

17. The apparatus of claim 16 wherein the first plurality of buffers and the second plurality of buffers are allocated in the memory and are each organized as a first-in-first-out stack.

18. The apparatus of claim 16 wherein the processor is configured to:

determine that the first least recently used reference frame is to be stored at the buffer of the second plurality of buffers when the picture ID number of the first least recently used reference frame is evenly divisible by the first decimation factor.

19. The apparatus of claim 18 wherein the processor is configured to:

if the plurality of second buffers is full of reference frames:

determine a second least recently used reference frame from the second plurality of buffers; and

remove the second least recently used reference frame from the second plurality of buffers.

20. The apparatus of claim 19 wherein the processor is configured to:

allocate a third plurality of buffers, each buffer of the third plurality of buffers configured to store one frame of the plurality of frames;

determine that the second least recently used reference frame is to be stored at a buffer of the third plurality of buffers when the picture ID number of the second least recently used reference frame is evenly divisible by a second decimation factor; and

store the second least recently used reference frame at the buffer of the third plurality of buffers if it is determined that the second least recently used reference frame is to be stored at the buffer of the third plurality of buffers.