Methods of selecting an encoding mode
View Patent ↗Information needed to generate an encoded version of a matrix of j transform coefficients c0 . . . cj−1 representing a block of digital video data is determined by forming a numerical signature σ of the matrix and looking up a value for the information needed in an array employing the signature σ as an index to the array.
1. A method of employing a mode selection function J for selecting a coding mode from a plurality of coding modes for a matrix of j transform coefficients c 0 . . . c j−1 representing a block of digital video data, the method comprising:
a) receiving, by a computing machine, the matrix of j transform coefficients c 0 . . . c j−1 representing the block of digital video data;
b) forming, by the computing machine, a numerical signature σ of the matrix,
c) determining, by the computing machine, at least one value of a parameter R based on an array using σ as an index to the array, wherein J is a function of R and each value of R equals the size, in bits, of an encoded version of the matrix encoded with one of the plurality of coding modes,
d) inputting, by the computing machine, each value of R as an input to an algorithm to determine a corresponding value of J,
e) selecting, by the computing machine, the coding mode corresponding to a minimum value of J, and
f) encoding, by the computing machine, the matrix of j transform coefficients c 0 . . . c j−1 based on the selecting.
2. A method according to claim 1 , comprising calculating σ using a group of the coefficients in accordance with a procedure that returns a unique value of σ for each unique set of coefficient values and wherein step a comprises:
a1) linearly ordering the coefficients c 0 , c 1 , . . ., c j−1 ,
a2) selecting a group of m sequentially ordered coefficients c u through c v where u is less than v and v equals u+m−1,
a3) mapping each coefficient c i in the group to an unsigned integer representation r i ,
a4) weighting each integer representation r i to form a weighted representation w i , and
a5) combining the weighted representations w u . . . w v to form σ.
3. A method according to claim 1 , wherein prior to step b, the method comprises calculating a σ value and a value of R for each of the plurality of coding modes for every matrix in which the value of each coefficient falls within a predetermined range.
4. A method according to claim 3 , wherein for every unique combination of σ and coding mode there is a single R value, and the method comprises, prior to step b, creating at least one table in which each calculated R value is stored, and creating the array, wherein the array includes said at least one table.
5. A method according to claim 1 , comprising performing step a in parallel with calculating transform coefficients c 0 . . . c j−1 .
6. A computing machine for receiving a matrix of j transform coefficients c 0 . . . c j− , the coefficients representing a block of digital video data, the machine being programmed to operate on the coefficients c 0 . . . c j−1 to determine information needed to generate an encoded version of the matrix by performing a procedure comprising the steps:
a) receiving, by the computing machine, the matrix of j transform coefficients c 0 . . . c j−1 ,
b) determining, by the computing machine, whether the matrix complies with a validity test,
c) forming, by the computing machine, a numerical signature σ of the matrix when it is determined that the matrix complies with the validity test, and
d) generating, by the computing machine, the encoded version of the matrix by looking up a value for the information needed for generating the encoded version in an array employing the signature σ as an index to the array.
7. A computing machine according to claim 6 wherein the programmed procedure comprises calculating σ using a group of the coefficients in accordance with a function that returns a unique value of σ for each unique set of coefficient values.
8. A computing machine according to claim 6 , wherein step a of the programmed procedure comprises:
a1) linearly ordering the coefficients c 0 , c 1 , . . ., c j−1 ,
a2) selecting a group of m sequentially ordered coefficients c u through c v where u is less than v and v equals u+m−1,
a3) mapping each coefficient c i in the group to an unsigned integer representation r i ,
a4) weighting each integer representation r i to form a weighted representation w i , and
a5) combining the weighted representations w u . . . w v to form σ.
9. A computing machine according to claim 8 , wherein step a1 of the programmed procedure comprises ordering the coefficients according to a zig-zag scan.
10. A computing machine according to claim 8 , wherein step a1 of the programmed procedure comprises ordering the coefficients according to a left-to-right-top-to-bottom scan.
11. A computing machine according to claim 8 , wherein each coefficient c i in the group is limited to a predefined range of possible values and the predefined range of possible values for coefficient c i is greater than the predefined range of possible values for coefficient c i+1 .
12. A computing machine according to claim 8 , wherein coefficients c v+1 . . . c j−1 equal zero.
13. A computing machine according to claim 8 , wherein c i is represented by a maximum number of bits b i and step a3 of the programmed procedure comprises:
calculating r i for each coefficient c i in the group according to the equation:
r i =c i +2 bi-1 −1.
14. A computing machine according to claim 8 , wherein step a4 of the programmed procedure comprises:
calculating w i for each coefficient c i in the group according to the equation:
w
k
=
2
tk
r
k
,
where
t
k
=
0
for
k
=
u
and
t
k
=
∑
i
=
0
k
-
1
b
i
for
k
>
u
.
15. A computing machine according to claim 8 , wherein step a5 of the programmed procedure comprises summing the weighted representations w u . . . w v to calculate σ.
16. A computing machine according to claim 8 , wherein step a of the programmed procedure further comprises:
receiving an identifier associated with the matrix, and, after step a5,
storing σ in a holding table using the matrix's identifier as an index.
17. A computing machine according to claim 16 , wherein the array comprises a plurality of data tables and the programmed procedure further comprises, between step a and step b:
receiving a communication from a requestor indicating a data table, and
receiving the identifier from the requestor,
step b further comprises:
using the identifier as an index to the holding table to retrieve σ, and
reading a value of the information needed from the indicated data table,
and, after step b, the programmed procedure further comprises:
returning the value of the information needed to the requestor.
18. A computing machine according to claim 6 , wherein the array comprises multiple data tables and step b of the programmed procedure comprises:
receiving a communication from a requestor indicating a data table,
reading the value of the information needed from the indicated data table, and
returning the value of the information needed to the requestor.
19. A computing machine according to claim 6 , wherein, prior to step b, the programmed procedure comprises calculating σ and the information needed for every matrix in which the value of each coefficient falls within a predetermined range.
20. A computing machine according to claim 19 , wherein, prior to step b, the programmed procedure comprises creating the array, wherein the array contains the calculated values of the information needed indexed by the calculated σ values.
21. A computing machine according to claim 6 , wherein the programmed procedure comprises performing step a in parallel with calculating transform coefficients c 0 . . . c j−1 .
22. A computing machine according to claim 6 , wherein the information needed is a number of bits R equivalent to the length of the encoded version of the matrix.
23. A computing machine according to claim 6 , wherein the information needed is a sequence of bits S that is equivalent to an encoded version of the matrix of transform coefficients.
24. A non-transitory computer readable storage medium upon which is stored instructions defining a procedure for operating on a matrix of j transform coefficients c 0 . . . c j−1 representing a block of digital video data to determine information needed to generate an encoded version of the matrix, the procedure comprising the steps:
a) receiving the matrix of j transform coefficients c 0 . . . c j−1 ,
b) determining whether the matrix complies with a validity test,
c) forming a numerical signature σ of the matrix when it is determined that the matrix complies with the validity test, and
d) generating the encoded version of the matrix by looking up a value for the information needed for generating the encoded version in an array employing the signature σ as an index to the array.
25. A computer readable medium according to claim 24 , wherein the procedure comprises calculating σ using a group of the coefficients in accordance with a function that returns a unique value of σ for each unique set of coefficient values.
26. A computer readable medium according to claim 24 , wherein step a of the procedure comprises:
a1) linearly ordering the coefficients c 0 , c 1 , . . ., c −1 ,
a2) selecting a group of m sequentially ordered coefficients c u through c v where u is less than v and v equals u+m−1,
a3) mapping each coefficient c i in the group to an unsigned integer representation r i ,
a4) weighting each integer representation r i to form a weighted representation w i , and
a5) combining the weighted representations w u . . . w v to form σ.
27. A computer readable medium according to claim 26 , wherein step a1 of the programmed procedure comprises ordering the coefficients according to a zig-zag scan.
28. A computer readable medium according to claim 26 , wherein step a1 of the programmed procedure comprises ordering the coefficients according to a left-to-right-top-to-bottom scan.
29. A computer readable medium according to claim 26 , wherein each coefficient c i in the group is limited to a predefined range of possible values and the predefined range of possible values for coefficient c i is greater than the predefined range of possible values for coefficient c i+1 .
30. A computer readable medium according to claim 26 , wherein coefficients c v+1 . . . c j−1 equal zero.
31. A computer readable medium according to claim 26 , wherein c i is represented by a maximum number of bits b i and step a3 of the procedure comprises:
calculating r i for each coefficient c i in the group according to the equation:
r i =c i +2 bi-1 −1.
32. A computer readable medium according to claim 26 , wherein step a4 of the procedure comprises:
calculating w k for each coefficient c k in the group according to the equation:
w
k
=
2
tk
r
k
,
where
t
k
=
0
for
k
=
u
and
t
k
=
∑
i
=
0
k
-
1
b
i
for
k
>
u
.
33. A computer readable medium according to claim 26 , wherein step a5 of the procedure comprises summing the weighted representations w u . . . w v to calculate σ.
34. A computer readable medium according to claim 26 , wherein step a of the procedure comprises:
receiving an identifier associated with the matrix, and, after step a5,
storing σ in a holding table using the matrix's identifier as an index.
35. A computer readable medium according to claim 34 , wherein the array comprises a plurality of data tables and the procedure further comprises, between step a and step b:
receiving a communication from a requestor indicating a data table, and
receiving the identifier from the requestor,
step b of the procedure further comprises:
using the identifier as an index to the holding table to retrieve σ, and
reading a value of the information needed from the indicated data table,
and, after step b, the procedure further comprises:
returning the value of the information needed to the requestor.
36. A computer readable medium according to claim 24 , wherein the array comprises multiple data tables and step b of the procedure comprises:
receiving a communication from a requestor indicating a data table,
reading the value of the information needed from the indicated data table, and
returning the value of the information needed to the requestor.
37. A computer readable medium according to claim 24 , wherein prior to step b, the procedure comprises calculating σ and the value of the information needed for every matrix in which the value of each coefficient falls within a predetermined range.
38. A computer readable medium according to claim 37 , wherein prior to step b, the procedure comprises creating the array, wherein the array contains the calculated values of the information needed indexed by the calculated σ values.
39. A computer readable medium according to claim 24 , wherein the procedure comprises performing step a in parallel with calculating integer transform coefficients c 0 . . . c j−1 .
40. A computer readable medium according to claim 24 , wherein the information needed is a number of bits R equivalent to the length of the encoded version of the matrix.
41. A computer readable medium according to claim 24 , wherein the information needed is a sequence of bits S that is equivalent to an encoded version of the matrix of transform coefficients.