# US 7,746,249 B2 · Method and apparatus for encoding and decoding key data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,746,249 B2
- Document ID: US7746249B2
- Status: Granted
- Kind: B2
- Application number: 11/390,337
- Filed: 2006-03-28
- Published: 2006-08-03
- Granted: 2010-06-29
- Earliest claimed: 2002-10-19
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: Shin-jun Lee; Seok-yoon Jung; Euee-seon Jang; Sang-oak Woo; Mahn-jin Han; Do-kyoon Kim; Gyeong-ja Jang
- Web page: https://patentgrep.com/patent/US7746249B2

## CPC

- H04N 19/587: involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
- H04N 19/103: Selection of coding mode or of prediction mode
- H04N 19/12: Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
- H04N 19/124: Quantisation
- H04N 19/126: Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
- H04N 19/136: Incoming video signal characteristics or properties
- H04N 19/14: Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence)
- H04N 19/192: the adaptation method, adaptation tool or adaptation type being iterative or recursive
- H04N 19/25: with scene description coding, e.g. binary format for scenes [BIFS] compression
- H04N 19/46: Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence)
- H04N 19/50: using predictive coding (H04N19/61 takes precedence)
- H04N 19/70: characterised by syntax aspects related to video coding, e.g. related to compression standards
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

An apparatus and a method for encoding and decoding key data are provided. An apparatus for encoding DPCMed differential data of key data includes a DND operator which performs on input differential data a predetermined number of times a DND operation, in which a divide operation is performed on the input differential data so as to divide differential data belonging to a positive number region into halves and so as to convert one half of the differential data belonging to an upper range than the other half into negative values, and either a divide-up operation or a divide-down operation is selectively performed on the results of the divide operation depending on the range of the results of the divide operation so as to reduce the range of differential data belonging to a negative number region or the positive number region, respectively, a shift-up operator which performs a shift-up operation on the results of the DND operation so as to transfer the differential data having been through the DND operation to either the positive or negative number region, a differential data selector which selectively outputs either the differential data having been through the DND operation or the differential data having been through the shift-up operation, and an entropy encoder which entropy-encodes the differential data selected by the differential data selector.

## Claims

### Claim 1

A method of decoding a bitstream into which a coordinate interpolator that comprises key data and a key header comprising information regarding the key data is encoded, the key data representing the position of a key frame on a time axis, the method comprising:
(a) decoding the key header; and
(b) decoding the key data according to the result of the decoding performed in (a).

### Claim 2 (depends on 1)

The method of claim 1, wherein (b) comprises decoding the key data by performing entropy decoding, inverse shift, inverse differential pulse code modulation (DPCM), inverse quantization, and linear key synthesis.

### Claim 3 (depends on 2)

The method of claim 2, wherein the key header comprises:
a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;
a key data quantity (nNumberOfKey) which indicates the number of the key data;
a key data digit number (nKeyDigit) which indicates the number of digits of the key data;
a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;
beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;
a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;
an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform inverse quantization;
a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;
(nQIntraKey) indicates a size of first quantized intra data and is used as a base for recovering other quantized key data;
key data sign bits (nQIntraKeySign) represents a sign of (nQIntraKey);
a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;
a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;
a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);
a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;
at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);
a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);
an invert-down flag (nKeyInvertDownFlag) which indicates whether to invert down DND results;
an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and
an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,
wherein the linear key region is a region where the key data linearly increases.

### Claim 4 (depends on 3)

The method of claim 3, wherein (b) comprises:
performing entropy-decoding on the encoded key data by performing inverse signed AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the signed AAC method and performing inverse unsigned AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the unsigned AAC method;
performing inverse DND on the result of the entropy decoding if the DND order (nDNDOrder) is set to a value of 1 or greater;
performing inverse fold on the result of the entropy decoding if the DND order (nDNDOrder) is set to a value other than −1;
inversely shifting the result of the inverse fold by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value other than −1, and inversely shifting the result of the entropy decoding by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value of −1;
performing inverse DPCM on the result of the inversely shifting according to the DPCM order (nKDPCMOrder);
adjusting the result of the inverse DPCM if the maximum and minimum key data have been adjusted, and performing inverse quantization on the result of the adjusting according to the quantization bit size (nKeyQBit); and
if the decoded key header comprises the linear key region, decoding the key data of the linear key region using the beginning/ending key data (IKey), and performing linear key synthesis on the result of the decoding and the result of the inverse quantization.

### Claim 5 (depends on 4)

The method of claim 4, wherein, in the performing of the inverse DND, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is not −1, an invert-down operation, which is an inverse operation of a shift-up operation performed during entropy encoding, is performed, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is −1, not performing the invert-down operation, and the performing of the inverse DND comprises performing the inverse DND a predetermined number of times corresponding to the DND order (nDNDOrder), wherein, if a current iteration of the inverse DND is not a final iteration of the inverse DND and the at least one (nKeyMax) is a positive value, the current iteration of the inverse DND is performed using an invert-divide-down method, if the current iteration of the inverse DND is not the final iteration of the inverse DND and the at least one (nKeyMax) is a negative value, the current iteration of the inverse DND is performed using an inverse-divide-up method, and if the current iteration of the inverse DND is the final iteration of the inverse DND, the current iteration of the inverse DND is performed using an inverse-divide-up method regardless of whether the at least one (nKeyMax) is a positive value or a negative value.

### Claim 6 (depends on 1)

The method of decoding of claim 1, wherein the key header comprises information about a number of key data and information about a number of digits of each of the key data.

### Claim 7

A method of encoding a coordinate interpolator that comprises key data and a key header comprising information regarding the key data, the key data representing the position of a key frame on a time axis, the method comprising:
(a) encoding the key header; and
(b) encoding the key data according to the result of the encoding performed in (a).

### Claim 8 (depends on 7)

The method of claim 7, wherein (b) comprises encoding the key data by performing quantization, differential pulse code modulation (DPCM), and entropy encoding.

### Claim 9 (depends on 8)

The method of claim 8, wherein the key header comprises:
a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;
a key data quantity (nNumberOfKey) which indicates the number of the key data;
a key data digit number (nKeyDigit) which indicates the number of digits of the key data;
a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;
beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;
a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;
an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform quantization;
a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;
(nQIntraKey) indicates a size of first quantized intra data and is used as a base for recovering other quantized key data;
key data sign bits (nQIntraKeySign) represents a sign of (nQIntraKey);
a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;
a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;
a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);
a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;
at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);
a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);
an invert-down flag (bKeyInvertDownFlag) which indicates whether to invert down DND results;
an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and
an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,
wherein the linear key region is a region where the key data linearly increases.

### Claim 10 (depends on 9)

The method of claim 9, wherein (b) comprises:
performing quantization on the key data according to the quantization bit size (nKeyQBit);
generating differential data by performing DPCM on the result of the quantization according to the DPCM order (nKDPCMOrder);
performing DND on the differential data so that a difference between a maximum and minimum of the differential data can be minimized; and
performing entropy encoding on the result of the DND.

### Claim 11 (depends on 7)

The method of encoding of claim 7, wherein the key header comprises information about a number of key data and information about a number of digits of each of the key data.

### Claim 12

An apparatus for decoding a bitstream into which a coordinate interpolator that comprises key data and a key header comprising information regarding the key data is encoded, the key data representing the position of a key frame on a time axis, the apparatus comprising:
a key header decoding unit which decodes the key header; and
a key decoding unit which decodes the key data according to the result of the decoding performed by the key header decoding unit.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the key decoding unit decodes the key data by performing entropy decoding, inverse shift, inverse differential pulse code modulation (DPCM), inverse quantization, and linear key synthesis.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the key header comprises:
a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;
a key data quantity (nNumberOfKey) which indicates the number of the key data;
a key data digit number (nKeyDigit) which indicates the number of digits of the key data;
a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;
beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;
a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;
an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform inverse quantization;
a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;
(nQIntraKey) indicates a size of first quantized intra data and is used as a base for recovering other quantized key data;
key data sign bits (nQIntraKeySign) represents a sign of (nQIntraKey);
a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;
a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;
a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);
a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;
at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);
a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);
an invert-down flag (bKeyInvertDownFlag) which indicates whether to invert down DND results;
an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and
an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,
wherein the linear key region is a region where the key data linearly increases.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the key decoding unit comprises:
an entropy decoding unit which performs entropy-decoding on the encoded key data by performing inverse signed AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the signed MC method and performs inverse unsigned AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the unsigned AAC method;
an inverse DND unit which performs inverse DND on the result of the entropy decoding performed by the entropy decoding unit if the DND order (nDNDOrder) is set to a value of 1 or greater;
an inverse fold unit which performs inverse fold on the result of the entropy decoding performed by the entropy decoding unit if the DND order (nDNDOrder) is set to a value other than −1;
an inverse shift unit which inversely shifts the result of the inverse fold performed by the inverse fold unit by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value other than −1, and inversely shifts the result of the entropy decoding performed by the entropy decoding unit by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value of −1;
an inverse DPCM unit which performs inverse DPCM on the result of the inversely shifting performed by the inverse shift unit according to the DPCM order (nKDPCMOrder);
an inverse quantization unit which adjusts the result of the inverse DPCM performed by the inverse DPCM unit if the maximum and minimum key data have been adjusted, and performs inverse quantization on the result of the adjusting according to the quantization bit size (nKeyQBit); and
a linear key synthesis unit which, if the decoded key header comprises the linear key region, decodes the key data of the linear key region using the beginning/ending key data (IKey), and performs linear key synthesis on the result of the decoding and the result of the inverse quantization performed by the inverse quantization, unit.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is not −1, an invert-down operation, which is an inverse operation of a shift-up operation performed during entropy encoding, is performed, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is −1, the invert-down operation is not performed, and the inverse DND is performed a predetermined number of times corresponding to the DND order (nDNDOrder), wherein, if a current iteration of the inverse DND is not a final iteration of the inverse DND and the at least one (nKeyMax) is a positive value, the current iteration of the inverse DND is performed using an invert-divide-down method, if the current iteration of the inverse DND is not the final iteration of the inverse DND and the at least one (nKeyMax) is a negative value, the current iteration of the inverse DND is performed using an inverse-divide-up method, and if the current iteration of the inverse DND is the final iteration of the inverse DND, the current iteration of the inverse DND is performed using an inverse-divide-up method regardless of whether the at least one (nKeyMax) is a positive value or a negative value.

### Claim 17 (depends on 12)

The apparatus for decoding of claim 12, wherein the key header comprises information about a number of key data and information about a number of digits of each of the key data.

### Claim 18

An apparatus for encoding a coordinate interpolator that comprises key data and a key header comprising information regarding the key data is encoded, the key data representing the position of a key frame on a time axis, the apparatus comprising:
a key header encoding unit which encodes the key header; and
a key encoding unit which encodes the key data according to the result of the encoding performed by the key header encoding unit.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein the key encoding unit encodes the key data by performing quantization, differential pulse code modulation (DPCM) and entropy encoding.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the key header comprises:
a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;
a key data quantity (nNumberOfKey) which indicates the number of the key data;
a key data digit number (nKeyDigit) which indicates the number of digits of the key data;
a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;
beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;
a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;
an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform quantization;
a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;
(nQIntraKey) indicates a size of first quantized intra data and is used as a base for recovering other quantized key data;
key data sign bits (nQIntraKeySign) represents a sign of (nQIntraKey);
a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;
a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;
a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);
a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;
at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);
a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);
an invert-down flag (bKeyInvertDownFlag) which indicates whether to invert down DND results;
an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and
an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,
wherein the linear key region is a region where the key data linearly increases.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the key encoding unit comprises:
a quantization unit which performs quantization on the key data according to the quantization bit size (nKeyQBit);
a DPCM unit which generates differential data by performing DPCM on the result of the quantization performed by the quantization unit according to the DPCM order (nKDPCMOrder);
a DND unit which performs DND on the differential data so that a difference between a maximum and minimum of the differential data can be minimized; and
an entropy encoding unit which performs entropy encoding on the result of the DND performed by the DND unit.

### Claim 22 (depends on 18)

The apparatus for encoding of claim 18, wherein the key header comprises information about a number of key data and information about a number of digits of each of the key data.