Mechanism for video encoding based on estimates of statistically-popular motion vectors in frame

A video encoding system for encoding video data including a frame sequence, the video encoding system comprising:

• a processing agent;
• and
• memory storing program instructions, wherein the program instructions, when executed by the processing agent, cause the processing agent to:
• encode a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• (a) for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the one or more vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• and (b) select a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein the bit cost value R(v,p,C) is determined by:
• computing a baseline bit cost value R0(v,p) that represents a bit cost for encoding a difference vector d=v−p;
• computing a bias value ΔR(v,C) based on a bias function ΔR that has a local minimum at each of the vectors c1, c2, . . . , cn, wherein the bias function ΔR is identically zero in a neighborhood of the prediction vector p;
• and
• adding the baseline bit cost value R0(v,p) and the bias value ΔR(v,C) to obtain the bit cost value R(v,p,C).

A non-transitory computer-readable memory medium for encoding video data including a frame sequence, wherein the memory medium stores program instructions that are executable by a computer, wherein the program instructions, when executed by the computer, cause the computer to:

• encode a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the one or more vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein the bit cost value R(v,p,C) is determined by:
• computing a baseline bit cost value R0(v,p) that represents a bit cost for encoding a difference vector d=v−p;
• computing a bias value ΔR(v,C) based on a bias function ΔR that has a local minimum at each of the vectors c1, c2, . . . , cn, wherein the bias function ΔR is identically zero in a neighborhood of the prediction vector p;
• and
• adding the baseline bit cost value R0(v,p) and the bias value ΔR(v,C) to obtain the bit cost value R(v,p,C).

A non-transitory computer-readable memory medium for encoding video data including a frame sequence, wherein the memory medium stores program instructions that are executable by a computer, wherein the program instructions, when executed by the computer, cause the computer to:

• encode a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the one or more vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein n equals one, wherein the bit cost value R(v,p,C) is determined by computing a minimum of a first value and a second value, wherein the first value is determined by evaluating a standard rate function R0 at the vector v, wherein the standard rate function R0 has a minimum at the prediction vector p, wherein the second value is determined by evaluating a function R1 at the vector v, wherein the function R1 has a minimum at the vector c1, wherein a minimum value of the function R1 is greater than a minimum value of the standard rate function R0.

A method for encoding video data including a frame sequence, the method comprising:

• encoding a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block Bv in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein n equals one, wherein the bit cost value R(v,p,C) is determined by:
• computing a baseline bit cost value R0(v,p) that represents a bit cost for encoding a difference vector d=v−p;
• and
• computing a minimum of the baseline bit cost value R0(v,p) and a predetermined constant value, wherein the minimum is the bit cost value R(v,p,C).

A method for encoding video data including a frame sequence, the method comprising:

• encoding a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block Bv in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein n equals one, wherein the bit cost value R(v,p,C) is determined by computing a minimum of a first value and a second value, wherein the first value is determined by evaluating a standard rate function R0 at the vector v, wherein the standard rate function R0 has a minimum at the prediction vector p, wherein the second value is determined by evaluating a function R1 at the vector v, wherein the function R1 has a minimum at the vector c1, wherein a minimum value of the function R1 is greater than a minimum value of the standard rate function R0.

A method for encoding video data including a frame sequence, the method comprising:

• encoding a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block Bv in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• encoding a second frame of the frame sequence with respect to in reference frames of the frame sequence, wherein in is greater than one, wherein said encoding the second frame includes sequentially processing a plurality of blocks of the second frame according to an ordering of the blocks, wherein processing a given block of the second frame includes performing a motion vector search for the block over a search space of m-tuples (v1, v2, . . . , vm), wherein each vector vk, k=1, 2, . . . , m, of the m-tuple (v1, v2, . . . , vm) is a candidate motion vector for the block with respect to a kth one of the reference frames:
• for each m-tuple of the search space, computing a bit cost value R(vk,p,E) for each vector vk in the m-tuple, wherein the bit cost value R(vk,p,E) depends on vector vk, a prediction vector p for the block, and a vector set E, wherein the vector set E includes one or more vectors from a set of vectors {e1, e2, . . . , eL}, wherein the vectors e1, e2, . . . , eL are estimates of the L most statistically-popular motion vectors of the second frame.

A method for encoding video data including a frame sequence, the method comprising:

• encoding a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block Bv in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• selecting a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• encoding a second frame of the frame sequence with respect to in reference frames of the frame sequence, wherein in is greater than one, wherein said encoding the second frame includes sequentially processing a plurality of blocks of the second frame according to an ordering of those blocks, wherein processing a given block of the second frame includes performing a motion vector search for the block over a search space of m-tuples (v1, v2, . . . , vm), wherein each vector vk, k=1, 2, . . . , m, of the m-tuple (v1, v2, . . . , vm) is a candidate motion vector for the block with respect to a kth one of the reference frames, wherein the motion vector search includes:
• for each m-tuple of the search space, (a) computing a rate distortion value J(vk)=Dk(vk)+λR(vk,p,E) for each vector vk in the m-tuple, wherein Dk(vk) is a distortion value of the block based on the 10 reference frame and the vector vk, wherein R(vk,p,E) is a bit cost value that depends on vector vk, a prediction vector p for the block, and a vector set E, wherein the vector set E includes one or more vectors from a set of vectors {e1, e2, . . . , eL}, wherein the vectors e1, e2, . . . , eL are estimates of the L most statistically-popular motion vectors of the second frame, wherein L is greater than or equal to one, and (b) determining the index kmin of the vector vkmin in the m-tuple that gives the minimum value M of the distortion values J(vk);
• determining an m-tuple T* of the search space that gives a minimum value M* of M, wherein the vector vkmin corresponding to the m-tuple T* is selected as a motion vector for the block.

A video encoding system for encoding video data including a frame sequence, the video encoding system comprising:

• a processing agent;
• and
• memory storing program instructions, wherein the program instructions, when executed by the processing agent, cause the processing agent to:
• encode a current frame of the frame sequence with respect to a reference frame of the frame sequence, wherein said encoding the current frame includes sequentially processing a plurality of blocks of the current frame according to an ordering of the blocks, wherein processing a current block includes performing a motion vector search for the current block over a plurality of test vector positions, wherein said performing the motion vector search includes:
• (a) for each test vector position v of the plurality of test vector positions, computing a rate distortion value J(v) based on a linear combination of a distortion value D(v) and a bit cost value R(v,p,C), wherein the distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block in the reference frame, wherein the corresponding block Bv has a position in the reference frame that is defined by the test vector position v and a position of the current block in the current frame, wherein the bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn, wherein the one or more vectors c1, c2, . . . , cn are estimates of statistically popular motion vectors for the current frame;
• and (b) select a test vector position v* from said plurality of test vector positions that gives a minimum rate-distortion value,
• wherein n equals one, wherein the bit cost value R(v,p,C) is determined by computing a minimum of a first value and a second value, wherein the first value is determined by evaluating a standard rate function R0 at the vector v, wherein the standard rate function R0 has a minimum at the prediction vector p, wherein the second value is determined by evaluating a function R1 at the vector v, wherein the function R1 has a minimum at the vector c1, wherein a minimum value of the function R1 is greater than a minimum value of the standard rate function R0.