Multi-bit information hiding using overlapping subsets
View Patent ↗Methods and devices for reconstructing coefficient levels from a bitstream of encoded video data for a coefficient group in a transform unit. Sign bits are hidden in the parity of partially overlapping subsets of a set of coefficients. This enables the hiding of multiple sign bits per coefficient group. Other information bits may be hidden instead of sign bits in some cases.
1. A method of decoding a bitstream of encoded video to reconstruct a set of coefficients in a video decoder, the bitstream including encoded sign bits for each non-zero coefficient in the set except at least two of the non-zero coefficients, wherein respective sign bits for the at least two non-zero coefficients are hidden sign bits, the method comprising:
for each of the at least two non-zero coefficients, reconstructing the respective hidden sign bit for that non-zero coefficient by:
summing an absolute value of coefficients within a subset of coefficients corresponding to that respective hidden sign bit to obtain a parity value; and
assigning a sign to that non-zero coefficient based on whether the parity value is even or odd,
wherein the subsets are partially overlapping subsets of the set of coefficients,
wherein there are two subsets, and there are two hidden sign bits for the set of coefficients reconstructed based on the parity values of two subsets of the coefficients,
wherein the set of coefficients comprises a coefficient group of at least sixteen coefficients, and
wherein the two subsets meet the condition that the two subsets contain at least one coefficient in common, and each of the two subsets has at least on coefficient that is not in the other subset.
2. The method claimed in claim 1 , further comprising first determining that the respective sign bits for the at least two non-zero coefficients are hidden and not encoded in the bitstream.
3. The method claimed in claim 2 , wherein the determining comprises conducting a test based on the position of the last non-zero coefficient in the set and the position of the second-last non-zero coefficient in the set.
4. The method claimed in claim 1 , wherein the two subsets contain at least four coefficients in common and wherein each of the two subsets has at least four coefficients that are not in the other subset.
5. The method claimed in claim 4 , wherein each of the two subsets includes eleven coefficients from the coefficient group, and wherein six of the coefficients are common to both subsets.
6. The method claimed in claim 5 , wherein one subset includes coefficients x 0 to x 10 , and wherein the other subset includes coefficients x 5 to x 15 .
7. The method claimed in claim 5 , wherein one subset includes coefficients x 0 , x 1 , x 3 , x 4 , x 6 , x 7 , x 9 , x 10 , x 12 , x 13 , and x 15 , and wherein the other subset includes coefficients x 0 , x 2 , x 3 , x 5 , x 6 , x 8 , x 9 , x 11 , x 12 , x 14 , and x 15 .
8. The method claimed in claim 1 , wherein there are exactly three subsets and exactly three hidden sign bits for the set of coefficients reconstructed based on the parity values of the three subsets of the coefficients.
9. The method claimed in claim 8 , wherein each of the three subsets contains at least four coefficients from the coefficient group, wherein each subset has at least one coefficient that is not in the other subsets, and wherein each pair of subsets has at least one coefficient that is not in the other subset.
10. The method claimed in claim 1 , wherein there are exactly four subsets and exactly four hidden sign bits for the set of coefficients reconstructed based on the parity values of the four subsets of the coefficients.
11. The method claimed in claim 10 , wherein each of the four subsets contains at least eight coefficients from the coefficient group, wherein each subsets has at least one coefficient that is not in any of the other three subsets, wherein each pair of subsets has at least one coefficient that is not in either of the other two subsets, and wherein each triple of subsets has at least one coefficient that is not in the other one subset.
12. A method of encoding video in a video encoder to output a bitstream of encoded data, the video including a set of quantized transform domain coefficients, each non-zero coefficient in the set having a sign bit, the method comprising:
summing a first absolute value of coefficients within a first subset of coefficients to obtain a first parity value;
summing a second absolute value of coefficients within a second subset of coefficients to obtain a second parity value, wherein the first subset and second subset are partially overlapping subsets of the set of coefficients;
determining whether the first parity value matches the sign of a selected non-zero coefficient in the set and whether the second parity value matches the sign of a second selected non-zero coefficient in the set and, if not, then adjusting the value of one non-zero coefficient so as to match the parity values to the signs of the respective selected non-zero coefficients; and
encoding the signs of the non-zero coefficients excluding the signs of the selected non-zero coefficients,
whereby there is a first hidden sign bit for the first subset of coefficients and a second hidden sign bit for the second subset of coefficients,
wherein the set of quantized transform domain coefficients comprises a coefficient group of at least sixteen coefficients, and
wherein the first and second subset contain at least on coefficient in common, and the first and second subset each have at least on efficient that is not in the other subset.
13. A decoder for decoding a bitstream of encoded video to reconstruct a set of coefficients in a video decoder, the bitstream including encoded sign bits for each non-zero coefficient in the set except at least two of the non-zero coefficients, wherein respective sign bits for the at least two non-zero coefficients are hidden sign bits, the decoder comprising:
a processor;
a memory; and
a decoding application stored in memory and containing instructions for configuring the processor to:
for each of the at least two non-zero coefficients, reconstruct the respective hidden sign bit for that non-zero coefficient by:
summing an absolute value of coefficients within a subset of coefficients corresponding to that respective hidden sign bit to obtain a parity value; and
assigning a sign to that non-zero coefficient based on whether the parity value is even or odd,
wherein the subsets are partially overlapping subsets of the set of coefficients,
wherein there are two subsets, and there are two hidden sign bits for the set of coefficients reconstructed based on the parity values of the two subsets of the coefficients,
wherein the set of coefficients comprises a coefficient group of at least sixteen coefficients, and
wherein the two subsets meet the condition that the two subsets contain at least one coefficient in common, and each of the two subsets has at least one coefficient that is not in the other subset.
14. The decoder claimed in claim 13 , wherein the decoder is configured to first determine that the respective sign bits for the at least two non-zero coefficients are hidden and not encoded in the bitstream.
15. The decoder claimed in claim 14 , wherein the decoder is configured to determine by conducting a test based on the position of the last non-zero coefficient in the set and the position of the second-last non-zero coefficient in the set.
16. The decoder claimed in claim 13 , wherein the two subsets contain at least four coefficients in common and wherein each of the two subsets has at least four coefficients that are not in the other subset.
17. The decoder claimed in claim 16 , wherein each of the two subsets includes eleven coefficients from the coefficient group, and wherein six of the coefficients are common to both subsets.
18. The decoder claimed in claim 17 , wherein one subset includes coefficients x 0 to x 10 , and wherein the other subset includes coefficients x 5 to x 15 .
19. The decoder claimed in claim 17 , wherein one subset includes coefficients x 0 , x 1 , x 3 , x 4 , x 6 , x 7 , x 9 , x 10 , x 12 , x 13 , and x 15 , and wherein the other subset includes coefficients x 0 , x 2 , x 3 , x 5 , x 6 , x 8 , x 9 , x 11 , x 12 , x 14 , and x 15 .
20. The decoder claimed in claim 13 , wherein there are exactly three subsets and exactly three hidden sign bits for the set of coefficients reconstructed based on the parity values of the three subsets of the coefficients.
21. The decoder claimed in claim 20 , wherein each of the three subsets contains at least four coefficients from the coefficient group, wherein each subset has at least one coefficient that is not in the other subsets, and wherein each pair of subsets has at least one coefficient that is not in the other subset.
22. The decoder claimed in claim 13 , wherein there are exactly four subsets and exactly four hidden sign bits for the set of coefficients reconstructed based on the parity values of the four subsets of the coefficients.
23. The decoder claimed in claim 22 , wherein each of the four subsets contains at least eight coefficients from the coefficient group, wherein each subsets has at least one coefficient that is not in any of the other three subsets, wherein each pair of subsets has at least one coefficient that is not in either of the other two subsets, and wherein each triple of subsets has at least one coefficient that is not in the other one subset.
24. A non-transitory processor-readable medium storing processor-executable instructions which, when executed, configures one or more processors to perform the method claimed in claim 1 .