I 1111111111111111 11111 1111111111 11111 lllll 111111111111111 111111111111111111
`
`US009736484B2
`
`c12) United States Patent
`Jeong et al.
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 9,736,484 B2
`* Aug. 15, 2017
`
`(72)
`
`(54) APPARATUS FOR ENCODING AND
`DECODING IMAGE USING ADAPTIVE DCT
`COEFFICIENT SCANNING BASED ON
`PIXEL SIMILARITY AND METHOD
`THEREFOR
`(71) Applicants:Electronics and Telecommunications
`Research Institute, Daejeon (KR);
`Kwangwoon University Research
`Institute for Industry Cooperation,
`Seoul (KR); Industry-Academia
`Cooperation Group of Sejong
`University, Seoul (KR)
`Inventors: Se-Yoon Jeong, Daejeon (KR);
`Hae-Chui Choi, Daejeon (KR);
`Jeong-II Seo, Daejeon (KR);
`Seung-Kwon Beack, Seoul (KR);
`In-Seon Jang, Gunpo-si (KR); Jae-Gon
`Kim, Daejeon (KR); Kyung-Ae Moon,
`Daejeon (KR); Dae-Young Jang,
`Daejeon (KR); Jin-Woo Hong, Daejeon
`(KR); Jin-Woong Kim, Daejeon (KR);
`Yung-Lyul Lee, Seoul (KR);
`Dong-Gyu Sim, Seoul (KR);
`Seoung-Jun Oh, Seongnam-si (KR);
`Chang-Beom Ahn, Seoul (KR);
`Dae-Yeon Kim, Seoul (KR);
`Dong-Kyun Kim, Seoul (KR)
`(73) Assignees: Electronics and Telecommunications
`Research Institute, Daejeon (KR);
`Kwangwoon University Research
`Institute For Industry Cooperation,
`Seoul (KR); Industry-Academia
`Cooperation Group of Sejong
`University, Seoul (KR)
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`This patent is subject to a terminal dis(cid:173)
`claimer.
`(21) Appl. No.: 14/823,273
`Aug. 11, 2015
`(22) Filed:
`Prior Publication Data
`(65)
`
`( *) Notice:
`
`US 2015/0350658 Al
`Dec. 3, 2015
`Related U.S. Application Data
`
`(63)
`
`Continuation of application No. 13/975,251, filed on
`Aug. 23, 2013, now Pat. No. 9,225,982, which is a
`(Continued)
`
`(30)
`
`Foreign Application Priority Data
`
`Aug. 17, 2006
`Jan. 26, 2007
`
`(KR) ........................ 10-2006-0077851
`(KR) ........................ 10-2007-0008247
`
`(51)
`
`Int. Cl.
`G06F 21100
`H04L 29106
`
`(2013.01)
`(2006.01)
`(Continued)
`
`(52) U.S. Cl.
`CPC ................................ H04N 191159 (2014.11);
`(Continued)
`(58) Field of Classification Search
`CPC ...... H04N 19/159; H04N 19/18; H04N 19/13;
`(Continued)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,821,119 A *
`
`4/1989 Gharavi
`
`H04N 19/129
`375/240
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`CN
`
`WO 2013181979 Al * 12/2013
`(Continued)
`
`............. H04N 19/44
`
`OTHER PUBLICATIONS
`
`Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, Ming-Jiun Wang,
`Wen-Hsiao Peng, Tihao Chiang, Gwo-Giun Lee; "A unified systolic
`architecture for combined inter and intra predictions in H.264/ AVC
`decoder"; Jul. 2006; IWCMC '06: Proceedings of the 2006 inter(cid:173)
`national conference on Wireless communications and mobile com(cid:173)
`puting; Publisher: ACM; pp. 73-78.*
`(Continued)
`
`Primary Examiner - Shewaye Gelagay
`Assistant Examiner - Courtney Fields
`(74) Attorney, Agent, or Firm - NSIP Law
`
`ABSTRACT
`(57)
`The present invention discloses an encoding apparatus using
`a Discrete Cosine Transform (DCT) scanning, which
`includes a mode selection means for selecting an optimal
`mode for intra prediction; an intra prediction means for
`performing intra prediction onto video inputted based on the
`mode selected in the mode selection means; a DCT and
`quantization means for performing DCT and quantization
`(Continued)
`
`B(HORlZONTAL_UP)
`
`6(HOR!ZONTALDOWN)
`
`(DIAGONAL_DOWN_LEFT)3
`
`(VERTICAL_LEFT)7
`
`O(VERTICAL)
`
`S(VERTIC,AL_RIGHD
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 1
`
`

`

`US 9,736,484 B2
`Page 2
`
`onto residual coefficients of a block outputted from the intra
`prediction means; and an entropy encoding means for per(cid:173)
`forming entropy encoding onto DCT coefficients acquired
`from the DCT and quantization by using a scanning mode
`decided based on pixel similarity of the residual coefficients.
`
`4 Claims, 6 Drawing Sheets
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`7,817,718 B2 * 10/2010 Wang.
`
`7,933,334 B2 *
`
`4/2011 Kanehara.
`
`7,995,654 B2 *
`
`8/2011 Boon
`
`8,107,532 B2 *
`
`1/2012 Gaedke .
`
`Related U.S. Application Data
`
`continuation of application No. 12/377,617, filed as
`application No. PCT/KR2007/001433 on Mar. 23,
`2007, now Pat. No. 8,548,060.
`
`8,199,819 B2
`8,548,060 B2
`2003/0007698 Al
`2003/0081850 Al*
`
`2005/0074062 Al*
`
`2006/0002466 Al *
`
`4/2005 Sung.
`
`1/2006 Park.
`
`H04N 19/105
`348/699
`H04N 19/197
`375/240.12
`H04N 19/619
`375/240.12
`H04N 19/105
`375/240.01
`
`6/2012 Seo et al.
`10/2013 Jeong et al.
`1/2003 Govindaswarny et al.
`5/2003 Karczewicz
`H04N 19/176
`382/247
`H04N 19/176
`375/240.2
`H04N 19/196
`375/240.03
`H04N 19/51
`375/240.12
`
`(51)
`
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2014.01)
`(2006.01)
`(2014.01)
`
`Int. Cl.
`H04N 191159
`H04N 19191
`H04N 191182
`H04N 19113
`H04N 19118
`H04N 191176
`H04N 191129
`H04N 19161
`H04N 19111
`H04N 191103
`H04N 191136
`H04N 7/50
`H04N 19/44
`(52) U.S. Cl.
`CPC ........... H04N 191103 (2014.11); H04N 19111
`(2014.11); H04N 191129 (2014.11); H04N
`19113 (2014.11); H04N 191136 (2014.11);
`H04N 191176 (2014.11); H04N 19118
`(2014.11); H04N 191182 (2014.11); H04N
`19161 (2014.11); H04N 19191 (2014.11)
`( 58) Field of Classification Search
`CPC .... H04N 19/91; H04N 19/182; H04N 19/129;
`H04N 19/61; H04N 19/136; H04N
`19/176; H04N 19/11; H04N 19/103
`See application file for complete search history.
`
`2007/0274385 Al* 11/2007 He
`
`2013/0343452 Al
`2014/0037000 Al
`
`12/2013 Jeong et al.
`2/2014 Jeong et al.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`JP
`JP
`KR
`KR
`KR
`WO
`
`0 230 632 A2
`2 207 359 A2
`2003-6643 A
`2004-348741 A
`10-0180173 Bl
`2002-0006149 A
`2002-0081342 A
`WO 2008/020672 Al
`
`8/1987
`7/2010
`1/2003
`12/2004
`5/1999
`1/2002
`10/2002
`2/2008
`
`OTHER PUBLICATIONS
`
`D.-k. Kim et al., "Adaptive Scanning Using Pixel Similarity for
`H.264/ AVC," Proceedings of the 2006 Korean Signal Processing
`Conference, vol. 19, No. 1, pp. 1-4, Sep. 23, 2006, Hanyang
`University Ansan Campus, Ansan, Republic of Korea (in Korean,
`including English abstract).
`International Search Report and Written Opinion of the Interna(cid:173)
`tional Searching Authority issued on Jun. 29, 2007, in counterpart
`International Application No. PCT/KR2007/001433.
`H. Zrida et al., "High Level H.264/ AVC Video Encoder Paralleliza(cid:173)
`tion for Multiprocessor Implementation"; Proceedings of the 2009
`Design, Automation & Test in Europe Conference & Exhibition
`(Date '09), pp. 940-945, conference held Apr. 20-24, 2009, Nice,
`France, ISBN 978-3-9810801-5-5.
`
`* cited by examiner
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 2
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 1 of 6
`
`US 9,736,484 B2
`
`FIG. 1
`
`8(HORIZONTAL_UP)
`
`6(HORIZONTAL_DOWN)
`
`4(DIAGONAL_DOWN_RIGHT)
`
`(VERTICAL_LEFT)7
`
`0(VERTICAL)
`
`S(VERTICAL_RIGHT)
`
`FIG. 2
`
`X
`
`A
`
`B C D E
`
`F G H
`
`201
`
`202
`
`203
`
`204
`
`200
`
`b
`
`f
`
`j
`
`n
`
`C
`
`g
`
`k
`
`0
`
`d
`
`h
`
`p
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 3
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 2 of 6
`
`US 9,736,484 B2
`
`FIG. 3
`
`206
`
`207
`
`208
`
`I
`
`I
`
`I
`
`IC
`
`D E I F I G I H I
`- -
`
`C
`
`g
`
`d
`h ~200
`
`205
`I
`A
`
`a
`
`e
`
`X
`
`I
`
`]
`
`B
`
`b
`
`f
`
`- _,... - - - I->-
`
`K
`
`i
`
`j
`
`L m n
`
`k
`
`0
`
`I
`
`p
`
`FIG. 4
`
`Mode
`selection unit
`
`10
`
`20
`
`30
`
`40
`
`Input video
`
`Intra
`prediction unit
`
`DCT&
`Quantization unit
`
`Entropy
`encoding unit
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 4
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 3 of 6
`
`US 9,736,484 B2
`
`FIG. 5
`
`FIG. 6
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 5
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 4 of 6
`
`US 9,736,484 B2
`
`FIG. 7
`
`FIG. 8
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 6
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 5 of 6
`
`US 9,736,484 B2
`
`FIG. 9
`
`Perform vertical
`intra prediction
`
`5601
`
`No
`
`Yes
`
`Perform horizontal
`scanning
`
`5603
`
`Perform zigzag
`scanning
`
`5604
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 7
`
`

`

`U.S. Patent
`
`Aug. 15, 2017
`
`Sheet 6 of 6
`
`US 9,736,484 B2
`
`FIG. 10
`
`Perform horizontal
`intra prediction
`
`5701
`
`No
`
`Yes
`
`Perform vertical
`scanning
`
`S703
`
`Perform zigzag
`scanning
`
`S704
`
`FIG. 11
`
`Output video
`
`70
`
`Video
`recovery unit
`
`~--"'---,60
`scanning
`decision unit
`
`Mode
`Information
`
`50
`
`Entropy
`decoding unit
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 8
`
`

`

`US 9,736,484 B2
`
`1
`APPARATUS FOR ENCODING AND
`DECODING IMAGE USING ADAPTIVE DCT
`COEFFICIENT SCANNING BASED ON
`PIXEL SIMILARITY AND METHOD
`THEREFOR
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation Application of applica(cid:173)
`tion Ser. No. 13/975,251 filed on Aug. 23, 2013, which is a
`continuation application Ser. No. 12/377,617 filed on Feb.
`16, 2009, now U.S. Pat. No. 8,548,060, which is a U.S.
`National Stage application of International Application No.
`PCT/KR2007/001433 filed on Mar. 23, 2007, which claims 15
`the benefit of Korean Applications Nos. 10-2006-0077851
`filed on Aug. 17, 2006, and 10-2007-0008247 filed on Jan.
`26, 2007. The entire disclosures of application Ser. No.
`13/975,251, 12/377,617, International Application No. PCT/
`KR2007/001433, and Korean Application Nos. 10-2006-
`0077851 and 10-2007-0008247 are incorporated herein by
`reference for all purposes.
`
`TECHNICAL FIELD
`
`2
`As illustrated in FIG. 1, the 9 prediction modes used for
`intra prediction of 4x4 blocks include a vertical mode (mode
`0), a horizontal mode (mode 1), a direct current (DC) mode
`(mode 2), a diagonal_down_left mode (mode 3), a diagon-
`5 al_down_right mode (mode 4), a vertical_right mode (mode
`5), a horizontal_down mode (mode 6), a vertical_left mode
`(mode 7), and a horizontal_up mode (mode 8).
`Herein, in the DC mode (mode 2), intra prediction is
`performed using a mean value of adjacent pixels. The arrows
`10 indicate prediction directions.
`Meanwhile, intra 16x16 prediction encoding includes a
`total of four modes, which are a vertical mode, a horizontal
`mode, a DC mode, and a plane mode.
`Also, intra 8x8 prediction encoding includes a total of 9
`modes, just like the intra 4x4 prediction encoding. As for
`color difference signals, intra 8x8 prediction encoding is
`performed, and the intra 8x8 prediction encoding includes a
`DC mode, a vertical mode, a horizontal mode, and a plane
`20 mode and so on.
`Hereinafter, prediction methods in the vertical and hori(cid:173)
`zontal modes for intra prediction of 4x4 blocks will be
`described with reference to FIGS. 2 and 3.
`FIG. 2 exemplarily illustrates a pixel prediction method in
`25 a vertical direction in a 4x4 block 200.
`As shown in FIG. 2, pixel a 201, pixel e 202, pixel i 203,
`and pixel m 204 are predicted based on an adjacent pixel A
`in the vertical direction.
`Also, pixels b, f, j and b are predicted based on an adjacent
`pixel B in the vertical direction, and pixels c, g, k and o are
`predicted based on an adjacent pixel C in the vertical
`direction. Pixels d, h, 1 and p are predicted based on an
`adjacent pixel D in the vertical direction.
`FIG. 3 exemplarily illustrates a pixel prediction method in
`a horizontal direction in a 4x4 block 200.
`As illustrated in FIG. 3, pixel a 205, pixel b 206, pixel c
`207, and pixel d 208 are predicted based on an adjacent pixel
`1 in a horizontal direction.
`Also, pixels e, f, g and h are predicted based on an
`adjacent pixel Jin the horizontal direction, and pixels i, j, k
`and 1 are predicted based on an adjacent pixel K in the
`horizontal direction. Pixels m, n, o and p are predicted based
`on an adjacent pixel L in the horizontal direction.
`An encoder performs Discrete Cosine Transform (DCT)
`and quantization onto residual signals (which are of a pixel
`area) acquired by calculating differences between the pre(cid:173)
`dicted pixels and the current pixels. Subsequently, the
`encoder performs zigzag scarming and entropy encoding
`50 onto the transformed coefficients obtained from DCT and
`quantization.
`Herein, although the zigzag scanning takes advantage of
`an energy compaction characteristic of a transformed coef-
`55 ficient that energy converges into low frequency compo(cid:173)
`nents and energy appears little in high frequency compo(cid:173)
`nents, the energy compaction after intra prediction is not
`always effective.
`In short, the zigzag scanning is a method of scanning a
`transformed coefficient from low frequency components to
`high frequency components. When distribution of trans(cid:173)
`formed coefficients appears more in the low frequency
`components, the zigzag scarming is effective. However,
`when spatial prediction having directivity is used, the dis-
`65 tribution of transformed coefficients is influenced by the
`direction of prediction. Therefore, it is ineffective to apply
`the zigzag scanning to the prediction of all directions.
`
`The present invention relates to an encoding/decoding
`apparatus and method using an adaptive Discrete Cosine
`Transform (DCT) coefficient scanning based on pixel simi(cid:173)
`larity. More particularly, the present invention relates to an
`encoding/decoding apparatus and method which performs 30
`intra prediction onto input video, predicts pixel similarity
`based on pixel similarity information of coefficients to be
`encoded that is acquired from adjacent pixels in the intra(cid:173)
`predicted video, and performs a most effective scanning,
`e.g., Discrete Cosine Transform (DCT) coefficient scanning, 35
`according to the predicted pixel similarity.
`
`BACKGROUND ART
`
`45
`
`According to video compression standards for encoding/ 40
`decoding video data, a frame is divided into a plurality of
`macro blocks and a macro block may be divided into a
`plurality of sub-blocks. The encoding/decoding is performed
`on the basis of a macro block unit or a sub-block unit based
`on temporal prediction and spatial prediction.
`Herein, the temporal prediction is to predict motion of
`macro blocks or sub-blocks of a current frame by referring
`to blocks of adjacent frames.
`The spatial prediction is to predict motion of macro
`blocks or sub-blocks of a current frame to be encoded by
`using boundary pixels of already recovered adjacent blocks.
`The spatial prediction is also called intra prediction. The
`intra prediction takes advantage of a characteristic that when
`a pixel is predicted, pixels adjacent to it are highly likely to
`have similar values.
`H.264/Advanced Video Coding (AVC) standard technol(cid:173)
`ogy can compress video about twice as high as Moving
`Picture Experts Group 2 (MPEG-2) and about one and a half
`times as high as MPEG-4 by using such technique as intra
`prediction encoding, ¼-pixel based variable block motion 60
`prediction and compensation, Context-based Adaptive Vari(cid:173)
`able Length Coding (CAVLC), and Context-based Adaptive
`Binary Arithmetic Coding (CABAC).
`The H.264/AVC standard predicts pixel values of a cur(cid:173)
`rent block by using prediction modes of 9 directivities.
`FIG. 1 illustrates 9 prediction modes used for intra
`prediction of 4x4 blocks.
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 9
`
`

`

`US 9,736,484 B2
`
`3
`DISCLOSURE
`
`Technical Problem
`
`Advantageous Effects
`
`4
`nal_down_left mode, a diagonal_down_right mode, a ver(cid:173)
`tical_right mode, a horizontal_down mode, a vertical_left
`mode, and a horizontal_up mode, and an intra 16x16 lumi(cid:173)
`nance encoding mode of H.264/AVC, which includes a
`An embodiment of the present invention, which is devised 5 vertical mode, a horizontal mode, a plane mode, and a DC
`to overcome the above problems, is directed to providing an
`mode.
`encoding/decoding apparatus and method which performs
`Also, according to an embodiment of the present inven(cid:173)
`intra prediction onto input video, predicts pixel similarity
`tion, a chrominance block may go through an intra MxN
`based on pixel similarity information of coefficients to be
`chrominance encoding mode ofH.264/AVC, which includes
`encoded acquired from adjacent pixels in the intra-predicted 10
`a vertical mode, a horizontal mode, a plane mode and a DC
`video, and performs a most effective scanning, e.g., DCT
`mode.
`coefficient scanning, according to the predicted pixel simi(cid:173)
`larity.
`Other objects and advantages of the present invention can
`be understood by the following description, and become 15
`apparent with reference to the embodiments of the present
`invention. Also, it is obvious to those skilled in the art of the
`present invention that the objects and advantages of the
`present invention can be realized by the means as claimed
`and combinations thereof.
`
`As described above, the present invention can improve a
`compression rate of intra encoding by applying a most
`effective scanning method according to pixel similarity in
`order to encode/decode video.
`Also, the present invention can improve a video compres-
`20 sion rate by being applied to a video compression technol(cid:173)
`ogy using intra prediction, which will be developed in the
`future.
`Also, the present invention can reduce a need for an
`additional module by applying the same similarity informa-
`25 tion to both encoder and decoder.
`
`Technical Solution
`
`In accordance with an aspect of the present invention,
`there is provided an encoding apparatus using a Discrete
`Cosine Transform (DCT) scanning, which includes a mode
`selection means for selecting an optimal mode for intra
`prediction; an intra prediction means for performing intra
`prediction onto video inputted based on the mode selected in
`the mode selection means; a DCT and quantization means 30
`for performing DCT and quantization onto residual coeffi(cid:173)
`cients of a block outputted from the intra prediction means;
`and an entropy encoding means for performing entropy
`encoding onto DCT coefficients acquired from the DCT and
`quantization by using a scanning mode decided based on 35
`pixel similarity of the residual coefficients.
`In accordance with another aspect of the present inven(cid:173)
`tion, there is provided a decoding apparatus using a DCT
`scanning, which includes an entropy decoding means for
`performing entropy decoding onto encoded video; a scan- 40
`ning decision means for deciding a scanning mode for the
`video decoded in the entropy decoding means; and a video
`recovery means for recovering the video based on the
`scanning mode decided in the scanning decision means.
`In accordance with another aspect of the present inven- 45
`tion, there is provided an encoding method using a DCT
`scanning, which includes the steps of selecting an optimal
`mode for intra prediction; performing intra prediction onto
`video inputted based on the mode selected in the mode
`selection step; performing DCT and quantization onto 50
`residual coefficients of a block outputted from the intra
`prediction step; deciding pixel similarity of the residual
`coefficients; and performing entropy encoding onto DCT
`coefficients acquired from the DCT and quantization by
`using a scanning mode decided in the pixel similarity 55
`decision step.
`In accordance with an aspect of the present invention,
`there is provided a decoding method using a DCT scanning,
`which includes the steps of performing entropy decoding
`onto encoded video; deciding a scanning mode for the video 60
`decoded in the entropy decoding step; and recovering the
`video based on the scanning mode decided in the scanning
`decision step.
`According to an embodiment of the present invention, a
`luminance block may go through an intra 4x4 luminance 65
`encoding mode of H.264/Advanced Video Coding (AVC),
`which includes a vertical mode, a horizontal mode, a diago-
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates 9 prediction modes used for intra
`prediction of 4x4 blocks according to H.264/AVC.
`FIG. 2 exemplarily illustrates a pixel prediction method in
`a vertical direction.
`FIG. 3 exemplarily illustrates a pixel prediction method in
`a horizontal direction.
`FIG. 4 is a block view showing an encoding apparatus
`using an adaptive DCT coefficient scanning based on pixel
`similarity in accordance with an embodiment of the present
`invention.
`FIG. 5 exemplarily illustrates a zigzag scanning method
`used in the present invention.
`FIG. 6 exemplarily illustrates a horizontal scanning
`method used in the present invention.
`FIG. 7 exemplarily illustrates a vertical scanning method
`used in the present invention.
`FIG. 8 illustrates a method for predicting pixel similarity
`in vertical and horizontal directions in accordance with an
`embodiment of the present invention.
`FIG. 9 is a flowchart describing an adaptive scanning
`method based on pixel similarity in a vertical intra predic(cid:173)
`tion mode in accordance with an embodiment of the present
`invention.
`FIG. 10 is a flowchart describing an adaptive scanning
`method based on pixel similarity in a horizontal intra
`prediction mode in accordance with an embodiment of the
`present invention.
`FIG. 11 is a block view showing a decoding apparatus
`using an adaptive DCT coefficient scanning based on pixel
`similarity in accordance with an embodiment of the present
`invention.
`
`BEST MODE FOR THE INVENTION
`
`The advantages, features and aspects of the invention will
`become apparent from the following description of the
`embodiments with reference to the accompanying drawings,
`which is set forth hereinafter. When it is considered that
`detailed description on a related art may obscure a point of
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 10
`
`

`

`US 9,736,484 B2
`
`5
`the present invention, the description will not be provided
`herein. Hereinafter, specific embodiments of the present
`invention will be described in detail with reference to the
`accompanying drawings.
`FIG. 4 is a block view showing an encoding apparatus
`using an adaptive DCT coefficient scanning based on pixel
`similarity in accordance with an embodiment of the present
`invention.
`As illustrated in FIG. 4, the encoding apparatus based on
`DCT coefficient scanning adaptive to pixel similarity
`includes a mode selection unit 10, an intra prediction unit 20,
`a DCT and quantization unit 30, and an entropy encoding
`unit 40.
`The mode selection unit 10 selects an optimal mode
`among several available prediction modes for intra predic- 15
`tion. In other words, it selects one among a plurality of
`possible encoding modes when 4x4, 16x16, or 8x8 intra
`prediction is performed. Generally, the mode selection unit
`10 selects one mode according to a rate-distortion optimi(cid:173)
`zation method for reducing an amount of distortion at a
`given bit rate.
`The intra prediction unit 20 receives a video, and per(cid:173)
`forms 4x4 intra prediction for pixels of luminance blocks
`and 8x8 intra prediction for pixels of chrominance blocks
`based on a mode selected in the mode selection unit 10.
`The DCT and quantization unit 30 performs DCT and
`quantization onto difference values outputted from the mode
`selection unit 10, that is, onto residual coefficient blocks
`indicating differences between pixel values of macro blocks
`of a current frame to be encoded and predicted pixel values,
`and transmits resulting coefficients to the entropy encoding
`unit 40.
`The entropy encoding unit 40 arrays DCT coefficients
`obtained in the DCT and quantization unit 30 by using an
`adaptive DCT coefficient scanning based on pixel similarity, 35
`performs entropy encoding onto the arrayed DCT coeffi(cid:173)
`cients, and outputs an encoded video bitstream in accor(cid:173)
`dance with the result.
`Herein, the entropy encoding is an encoding technique for
`enhancing a compression rate by allocating a few bits to data
`highly likely to occur and many bits to data that are not
`likely to occur. Examples of the entropy encoding used in
`the present invention include Context-based Adaptive Vari(cid:173)
`able Length Coding (CAVLC) or Context-based Adaptive
`Binary Arithmetic Coding (CABAC).
`With reference to FIGS. 8 to 10, described hereafter are a
`method of predicting pixel similarity in vertical and hori(cid:173)
`zontal directions in the entropy encoding unit 40, and a
`scanning method in vertical and horizontal intra prediction
`modes.
`FIG. 5 exemplarily illustrates a typical zigzag scanning
`method used in the present invention. FIG. 6 exemplarily
`illustrates a typical horizontal scanning method used in the
`present invention. FIG. 7 exemplarily illustrates a typical
`vertical scanning method used in the present invention.
`As shown in FIG. 5, the zigzag scanning method used in
`the present invention is devised in consideration that low
`frequency components of transformed coefficients acquired
`from the DCT and quantization are highly likely to be
`positioned in the upper left part of a two-dimensional plane. 60
`It takes advantage of a transformed coefficient energy com(cid:173)
`paction characteristic that coefficients after DCT collectively
`appear in low frequencies, whereas coefficients after DCT
`less appear in high frequencies.
`The zigzag scanning method may be more efficient when 65
`pixel similarity in the horizontal direction is similar to the
`pixel similarity in the vertical direction.
`
`6
`However, when intra prediction encoding, particularly,
`vertical or horizontal intra prediction, is performed, the
`similarity of the residual coefficients in the vertical direction
`shows much difference from the similarity in the horizontal
`5 direction. Thus, the above-described coefficient distribution
`is not always effective. Therefore, it is inefficient to apply the
`zigzag scanning to prediction of all directions.
`To describe an example of the vertical prediction mode,
`the vertical prediction mode is selected as an optimal mode
`10 in a rate-distortion optimization process, when the pixel
`similarity in the vertical direction is high. Herein, significant
`coefficients are distributed in the first row. Therefore, the
`horizontal scanning shown in FIG. 6 is more efficient than
`the typical zigzag scanning.
`Meanwhile, to describe an example of the horizontal
`prediction mode, the horizontal prediction mode is selected
`as an optimal mode, when the pixel similarity in the hori(cid:173)
`zontal direction is high. Herein, significant coefficients are
`distributed in the first colunm. Therefore, the vertical scan-
`20 ning shown in FIG. 7 is more efficient.
`However, since the pixel similarity before intra prediction
`is different from pixel similarity of residual coefficients after
`the intra prediction, it is inefficient to simply use the
`scanning method of FIG. 6 or FIG. 7 according to the intra
`25 prediction mode.
`Therefore, if pixel similarities in the vertical and hori(cid:173)
`zontal directions of a block to be encoded are predicted
`based on similarity information among adjacent block
`boundary pixels which are already recovered and an adap-
`30 tive scanning method according to the prediction result is
`used, the encoding efficiency can be increased.
`FIG. 8 illustrates a method for predicting pixel similarity
`in vertical and horizontal directions in accordance with an
`embodiment of the present invention.
`As illustrated in FIG. 8, pixels A, B, C and D are
`positioned adjacent to the upper part of a current block to be
`encoded, whereas pixels E, F, G and H are positioned
`adjacent to the left part of the current block to be encoded.
`Herein, when vertical prediction encoding is performed,
`40 the vertical-directional pixel similarity of the pixels a, e, i
`and min the first colunm of the current block to be encoded
`is the same as the vertical-directional pixel similarity of
`residual coefficients a-A, e-A, i-A, and m-A after vertical
`prediction. This is because the residual coefficients a-A, e-A,
`45 i-A, and m-A are differentiated by the same prediction pixel
`A from the pixels a, e, i and m, and thus the correlation does
`not change.
`Also, the vertical-directional pixel similarity of the pixels
`in columns 2, 3 and 4 of the current block to be encoded is
`50 the same as the vertical-directional pixel similarity of
`residual coefficients after vertical prediction.
`However, the horizontal-directional pixel similarity of the
`pixels a, b, c and din the first row of the current block to be
`encoded is different from the horizontal-directional pixel
`55 similarity of residual coefficients a-A, b-B, c-C, and d-D
`after vertical prediction. Also, the horizontal-directional
`pixel similarity before vertical prediction is higher than the
`horizontal-directional pixel similarity after the vertical pre-
`diction. Thus, it becomes similar to or higher than the
`vertical-directional pixel similarity.
`Likewise, in the case of the horizontal prediction encod(cid:173)
`ing, the horizontal-directional pixel similarity of the pixels
`a, b, c and d in the first row of the current block to be
`encoded is the same as the horizontal-directional pixel
`similarity ofresidual coefficients a-E, b-E, c-E, and d-E after
`horizontal prediction. Also, the horizontal-directional pixel
`similarity of the pixels in rows 2, 3 and 4 of the current block
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1001, p. 11
`
`

`

`US 9,736,484 B2
`
`7
`to be encoded is the same as the horizontal-directional pixel
`similarity of the residual coefficients after horizontal pre(cid:173)
`diction.
`However, the vertical-directional pixel similarity of the
`pixels a, e, i and m in the first colunm of the current block 5
`to be encoded is different from the vertical-directional pixel
`similarity ofresidual coefficients a-E, e-F, i-G, andm-H after
`horizontal prediction. Also, the vertical-directional pixel
`similarity before horizontal prediction is higher than the
`vertical-directional pixel similarity after the horizontal pre- 10
`diction. Thus, it becomes similar to or higher than the
`horizontal-directional pixel similarity.
`As described above, when the pixel similarities in the
`vertical and horizontal directions are similar, a general
`zigzag scamiing method is more efficient than the horizontal 15
`and vertical scanning methods.
`Therefore, when the vertical intra prediction mode is
`performed and the vertical-directional pixel similarity of
`residual coefficients is high and their horizontal-directional
`pixel similarity is low, it is more efficient to use the hori- 20
`zontal scanning.
`Meanwhile, when the horizontal intra prediction mode is
`performed and the horizontal-directional pixel similarity of
`residual coefficients is high and their vertical-directional
`pixel similarity is low, it is more efficient to use the vertical 25
`scanning.
`When the vertical-directional pixel similarity of recov(cid:173)
`ered 8 pixels A, B, C, D, E, F, G and Hof FIG. 8 is referred
`to as S _ VER and their horizontal-directional pixel similarity
`is referred to as S_HOR, the pixel similarities for increasing
`the efficiency of 4x4 prediction encoding can be calculated
`using the following Equation 1.
`
`8
`Hereinafter, a method of selecting a scanning method in
`the vertical and horizontal intra prediction modes will be
`described in detail with reference to FIGS. 9 and 10.
`FIG. 9 is a flowchart describing an adaptive scanning
`method based on pixel similarity in a vertical intra predic(cid:173)
`tion mode in accordance with an embodiment of the present
`invention.
`In case of a vertical intra prediction mode in step S601, an
`S_ VER value and a value of axS_HOR are compared in step
`S602. When the S_ VER value is greater than the value of
`axS_HOR, a horizontal scanning method is used in step
`S603. When the S_ VER value is smaller than the value of
`axS_HOR, a zigzag scamiing method is used in step S604.
`Herein, when a vertical-directional pixel similarity of the
`current block to be encoded based on similarity of adjacent
`pixels is predicted higher than the horizontal-directional
`pixel similarity thereof, transformed coefficients obtained
`after DCT and quantization are highly likely to be distrib-
`uted in a direction horizontal to a first row of the block.
`Therefore, the horizontal scamiing method can bring about
`a high encoding efficiency.
`FIG. 10 is a flowchart describing an adaptive scanning
`method based on pixel similarity in a horizontal intra
`prediction mode in accordance with an embodiment of the
`present invention.
`In case of a horizontal intra prediction mode in step S7