(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2005/0265447 A1
`(43) Pub. Date:
`Dec. 1, 2005
`Park
`
`US 200502654.47A1
`
`(54) PREDICTION ENCODER/DECODER,
`PREDICTION ENCODING/DECODING
`METHOD, AND COMPUTER READABLE
`RECORDING MEDIUM HAVING RECORDED
`THEREON PROGRAM FOR
`IMPLEMENTING THE PREDICTION
`ENCODING/DECODING METHOD
`(75) Inventor: Gwang-hoon Park, Scongnam-si (KR)
`Correspondence Address:
`SUGHRUE MION, PLLC
`2100 PENNSYLVANIAAVENUE, N.W.
`SUTE 800
`WASHINGTON, DC 20037 (US)
`(73) Assignees: INDUSTRY ACADEMIC COOPERA
`TION FOUNDATION KYUNGHEE
`UNIV.; SAMSUNG ELECTRONICS
`CO., LTD.
`(21) Appl. No.:
`11/111,915
`(22) Filed:
`Apr. 22, 2005
`
`(30)
`
`Foreign Application Priority Data
`
`May 25, 2004 (KR)............................ 10-2004-00375.42
`
`Publication Classification
`
`(51) Int. Cl." ....................................................... H04N 7/12
`(52) U.S. Cl. ........ 375/240.03; 375/240.12; 375/240.24;
`375/240.2; 375/240.23
`ABSTRACT
`(57)
`A prediction encoder/decoder, a prediction encoding/decod
`ing method, and a computer readable recording medium
`having a program for the prediction encoding/decoding
`method recorded thereon. The prediction encoder includes a
`prediction encoding unit that Starts prediction at an origin
`macroblock of an area of interest of a Video frame, continues
`prediction in an outward Spiral in the shape of Square rings
`composed of macroblockS Surrounding the origin macrob
`lock, and encodes Video by performing intra-prediction
`using information about a macroblock that has just been
`coded in a Square ring including a macroblock to be coded
`and a macroblock in a previous Square ring and adjacent to
`the macroblock.
`
`
`
`
`
`F
`(CURRENT)
`
`
`
`
`
`
`
`F
`(REFERENCE)
`(1 OR 2 PREVIOUSLY
`ENCODER FRAMES)
`
`
`
`
`
`
`F.
`(RECONSTRUCTED)
`
`
`
`MOTON
`ESTMATON
`UNIT
`
`MOTION
`COMPENSATION
`UNIT
`
`INTRA-PREDICTION
`MODE SELECTION
`UNIT
`
`NTRA
`PREDICTION
`UNIT
`
`13
`
`FILTER
`
`7
`QUANIZATION
`UNIT
`
`
`
`RPPLE
`SCANNING
`UNIT
`
`ENTROPY
`ENCODING
`UNI
`
`NAL
`
`INTRA-PREDCTIONMODE
`NFORMATION
`
`
`
`INVERSE
`OUANTIZATION
`UNIT
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 1
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 1 of 20
`
`US 2005/0265447 A1
`
`FIG. 1 (PRIOR ART)
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 2
`
`

`

`Patent Application Publication Dec. 1, 2005
`
`Sheet 2 of 20
`
`US 2005/0265447 A1
`
`FIG. 2 (PRIOR ART)
`
`
`
`PX-1, x
`
`--
`
`0, ...
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 3
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 3 of 20
`
`US 2005/0265447 A1
`
`FIG. 3A (PRIOR ART)
`
`FIG. 3B (PRIOR ART)
`
`----------- ...."
`
`----------- ...
`
`MODEO . VERTICAL MODE
`
`MODE1 : HORIZONTAL MODE
`
`FIG. 3C (PRIOR ART) FIG. 3D (PRIOR ART)
`
`
`
`
`
`E.
`l
`t
`..
`..
`.
`.
`
`----------- :
`MODE2: DC MODE
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 4
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 4 of 20
`
`US 2005/0265447 A1
`
`
`
`
`
`0 dnOH0 3OITS
`
`
`
`
`
`{{#7 “?IH
`
`
`
`Wý "?INH
`
`ESIMX|OOTO-HEIN[\OO
`
`ESIMOOTO
`
`Z
`
`--EEEEE##2
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 5
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 5 of 20
`
`US 2005/0265447 A1
`
`FIG. 5
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 6
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 6 of 20
`
`US 2005/0265447 A1
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 7
`
`

`

`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 8
`
`

`

`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 9
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 9 of 20
`
`US 2005/0265447 A1
`
`FIG. 9G
`
`FIG. 9H
`
`-----------
`
`
`
`
`
`X WWWWNWWW w Mwww.www.www.
`x www.W.W WWWW www.www.wwww.
`NWWWW www.www.www.www.www.
`rawwwa akaww.wawww.www.W. M. www.
`MWW www WWWW www.www.wwww.
`WWWWWW www.www.M.W. W. M. wwww.
`RX w. X W X Wawww.www.www.www.
`MWWWWWwww.www.www.www.www.www.ww.
`
`-----------
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 10
`
`

`

`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 11
`
`

`

`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 12
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 12 of 20
`
`US 2005/0265447 A1
`
`FIG. 14
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`r
`
`.
`* ... ."
`
`... .
`
`.
`
`.
`
`.
`
`''. . . . .'''
`* *
`*
`
`.
`. .
`.
`'A', '' ...'. ''
`''''''''
`A 'l','....'
`**t
`... ."
`
`
`
`..
`
`''A'. '''''''''.
`''''''''''
`''''''''' . . . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`***''''''''''
`'%' ...''''''ll''''''''
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 13
`
`

`

`Patent Application Publication
`
`Dec. 1, 2005 Sheet 13 of 20
`
`US 2005/0265447 A1
`
`
`
`9] 'OIGH
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Z |
`
`8 |
`
`(LNBHHTO)
`
`|-!)
`
`(BONEHEHEB)
`
`
`
`(SEWW.HE HECJOONE
`
`ÅTS^OIABHd Z HO |)
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 14
`
`

`

`Patent Application Publication
`
`Dec. 1, 2005 Sheet 14 of 20
`
`US 2005/0265447 A1
`
`TWN
`
`LINT
`
`ESHEAN||
`
`||N?I 100
`
`9] ^ 0IH
`
`
`
`|----
`
`(BONBBBBB}})
`
`
`
`(SEWWH-] HBOJOONE
`
`ÅTSTOIABHd Z HO ||)
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 15
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 15 of 20
`
`US 2005/0265447 A1
`
`
`
`2. I ’0IJI
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 16
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 16 of 20
`
`US 2005/0265447 A1
`
`FIG. 18
`
`ENCOOING START
`
`FROM RECEIVE MACROBLOCK
`FROM CENTER OF FRAME
`
`110
`
`INTRA-PREDICTION
`
`DETERMINE INTRA-PREDICTION MODE - 121
`
`PERFORMINTRA-PREDICTION
`
`122
`
`PERFORM DCT
`
`130
`
`PERFORM OUANTIZATION
`
`40
`
`PERFORMRIPPLE SCANNING
`FROM CENTER OF FRAME
`
`150
`
`PERFORMENTROPY ENCODING
`
`160
`
`END
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 17
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 17 of 20
`
`US 2005/0265447 A1
`
`FIG. 19
`
`
`
`SEARCH FOR REFERENCE
`MACROBLOCKS IN SAME SOUARE-201
`RING AND PREVIOUS SQUARE RING
`
`DETERMINE LOCATIONS OF
`REFERENCE MACROBLOCKS
`(A, A+D, A+B+D)
`
`202
`
`
`
`NO
`
`
`
`DO ALL THE
`REFERENCE MACROBLOCKS
`A, B, AND DEXIST?
`
`YES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PERFORMINTRA-PREDICTION
`USING INFORMATION
`ABOUT MACROBLOCKA
`
`OBTAIN PREDICTED
`MACROBLOCKS FOR
`FOR MACROBLOCKE USING
`MODES O AND 1
`
`
`
`CALCULATE SADS BETWEEN
`MACROBLOCKE AND
`PREDICTED MACROBLOCKS
`
`DETERMINE MODE HAVING
`SMALLER SAD TO BE
`PREDICTION MODE
`
`
`
`PERFORM INTRA-PREDICTION
`USING INFORMATION ABOUT
`ALL OF REFERENCE
`MACROBLOCKS A, B, AND D
`
`OBTAIN PREDICTED
`MACROBLOCK OF
`MACROBLOCKE USING
`MODES 2, 3, 4, AND 5
`
`
`
`CALCULATE SADS BETWEEN
`MACROBLOCKE AND
`PREDICTED MACROBLOCKS
`
`DETERMINE MODE HAVING
`THE SMALLEST SAD TO BE
`PREDICTION MODE
`
`PERFORMINTRA-PREDCTION IN
`DETERMINED PREDICTION MODE
`
`212
`
`END
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 18
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 18 of 20
`
`US 2005/0265447 A1
`
`FIG. 20
`
`DECODING START
`
`PERFORMENTROPY DECODING
`
`310
`
`PERFORMRPPLE SCANNING
`FROM CENTER OF FRAME
`
`320
`
`PERFORMINVERSE QUANTIZATION
`
`330
`
`PERFORMINVERSE DCT
`
`340
`
`INTRA-PREDICTION
`
`DETERMINE INTRA-PREDICTION MODE - 35
`
`PERFORM INTRA-PREDCTION
`
`RECONSTRUCT FRAME
`
`END
`
`352
`
`360
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 19
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 19 of 20
`
`US 2005/0265447 A1
`
`FIG. 21A
`
`SEARCH FOR REFERENCE
`MACROBLOCKS IN SAME SOUARE - 401
`RING AND PREVIOUS SQUARE RING
`
`DETERMINE LOCATIONS OF
`REFERENCE MACROBLOCKS
`(A, A+D, A+B+D)
`
`CHECK INFORMATION ABOUT
`INTRA-PREDICTION MODE
`
`402
`
`403
`
`ce
`
`ce
`
`404
`
`406
`
`MAP PXEL VALUES OF
`LNER OF MACROBLOCK A
`
`405
`
`
`
`MAP MEAN OF PIXEL
`VALUES OF LINER OF
`MACROBLOCK A
`
`407
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 20
`
`

`

`Patent Application Publication Dec. 1, 2005 Sheet 20 of 20
`
`US 2005/0265447 A1
`
`FIG 21B
`
`08
`
`10
`4
`
`o
`
`MAP MEAN OF PIXEL VALUES OF
`LINER OF MACROBLOCKA
`AND PXEL VAESOFINEL
`OF MACROBLOCK B
`
`09
`
`4
`MEASURE SIMILARITY BETWEEN
`MACROBLOCKSA, B, AND D
`
`BAND D
`ARE
`SMILAR
`
`A AND D
`ARE
`SIMILAR
`43
`412
`MAP MEAN OF PIXEL VALUES
`MAP MEAN OF PIXEL VALUES
`OF LINER OF MACROBLOCK A OF LINE L OF MACROBLOCK B
`
`414
`
`BAND D
`ARE
`SIMLAR
`
`MEASURE SIMILARITY BETWEEN
`MACROBLOCKS A, B, AND D
`
`A AND D
`ARE
`SMILAR
`417
`MAP PIXEL VALUES OF LINEL
`OF MACROBLOCK B
`
`416
`MAP PIXEL VALUES OF LINER
`OF MACROBLOCKA
`
`
`
`PERFORM PLANE FITTING
`USING LINER OF
`MACROBLOCK A AND
`LINE L OF MACROBLOCK B
`
`418
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 21
`
`

`

`US 2005/0265447 A1
`
`Dec. 1, 2005
`
`PREDICTION ENCODER/DECODER, PREDICTION
`ENCODING/DECODING METHOD, AND
`COMPUTER READABLE RECORDING MEDIUM
`HAVING RECORDED THEREON PROGRAM FOR
`IMPLEMENTING THE PREDICTION
`ENCODING/DECODING METHOD
`0001. This application claims priority from Korean
`Patent Application No. 10-2004-0037542, filed on May 25,
`2004, in the Korean Intellectual Property Office, the disclo
`Sure of which is incorporated herein in its entirety by
`reference.
`
`BACKGROUND OF THE INVENTION
`0002) 1. Field of the Invention
`0003. The present invention relates to a prediction
`encoder/decoder, a prediction encoding/decoding method,
`and a computer readable recording medium having recorded
`thereon a program for implementing the prediction encod
`ing/decoding method, for coding moving pictures.
`0004 2. Description of the Related Art
`0005 New standards called Motion Picture Experts
`Group (MPEG)-4 part 10 AVC (advanced video coding) or
`International Telecommunication Union Telecommunica
`tion Standardization Sector (ITU-T) H.264 emerged in 2003
`in the field of Video compression. Fueling the emergence
`was a change from conventional circuit Switching to packet
`Switching and a need for coexistence of various communi
`cation infrastructures, along with the rapid spread of new
`communication channels. Such as mobile networkS.
`0006. In AVC/H.264, spatial estimation encoding meth
`ods such as MPEG-1, MPEG-2, and MPEG-4 part 2 visual
`that differ from conventional international standards for
`moving picture encoding are used. In conventional moving
`picture encoding, coefficients transformed in a discrete
`cosine transform (DCT) domain are intra-predicted to
`improve encoding efficiency, resulting in degradation of
`Subjective quality at low-pass band transmission bit rates.
`On the other hand, in AVC/H.264, spatial intra-prediction is
`performed in a Spatial domain instead of in a transform
`domain.
`0007 Conventional spatial intra-prediction encoding is
`performed in Such a way that information about a block to
`be encoded is predicted using information about a block that
`has already been encoded and reproduced and only differ
`ence information indicating a difference between informa
`tion about an actual block to be encoded and the predicted
`block is encoded and transmitted to a decoder. At this time,
`a parameter required for prediction may be transmitted to the
`decoder or prediction may be performed by Synchronizing
`the encoder and the decoder. Information about a block to be
`decoded is predicted using information about an adjacent
`block that has already been decoded and reproduced, a Sum
`of the predicted information and the difference information
`transmitted from the encoder is calculated, and desired
`Structure information is reproduced. At this time, if a param
`eter required for prediction is received from the encoder, it
`is also decoded for use.
`0008 Intra-prediction used in conventional block-based
`or macroblock-based Video encoding uses information about
`blocks A, B, C, and D that are adjacent to a block E to be
`
`coded in a traditional raster Scan direction, as shown in FIG.
`1. Information about blocks marked with X in FIG. 1 is to
`be processed after completion of encoding of the block E,
`and is therefore not available for encoding processing. A
`block marked with O can be used when a predicted value is
`calculated, but it is spatially far from the block E. As a result,
`the block marked with O does not have a high correlation
`with the block E and is hardly used.
`0009. As such, most conventional intra-prediction uses
`part of the information about the blocks D, B, and C that are
`adjacent to the block E to be coded among blocks in a line
`immediately above a line including the block E and infor
`mation about the block A that has been encoded just before
`encoding the block E. In the case of MPEG-4-part 2, a DC
`(Discrete Coefficient) value of the block E is predicted using
`differences between DC values of the blocks A, D, and B in
`an 8x8 DCT domain. Also, in the case of AVC/H.264, a
`frame is divided into 4x4 blocks or 16x16 macroblocks and
`pixel values in a Spatial domain, instead of in a DCT domain,
`are predicted.
`0010 Hereinafter, 16x16 spatial intra-prediction of AVC/
`H.264 will be briefly described.
`0011 FIGS. 3A-3D show four modes of conventional
`16x16 spatial intra-prediction.
`0012 Macroblocks to be coded are indicated by E in
`FIGS. 3A-3D. Spatial intra-prediction is carried out using
`macroblocks A and B that are adjacent to the macroblock E.
`In FIGS. 3A-3D, a group of pixels used for spatial intra
`prediction includes 16 pixels that are located in the right
`most line of the macroblock A, which are indicated by V, and
`16 pixels that are located in the bottom-most line of the
`macroblock B, which are indicated by H.16x16 spatial
`intra-prediction is performed using the four modes, each of
`which will now be described.
`0013 A pixel value used in each mode is defined as
`shown in FIG. 2.
`0014 Assuming that a pixel value of the macroblock E to
`be intra-predicted is Pxy(x=0 ... 15 and y=0 ... 15), the
`line H of the macroblock B can be expressed as PX-1
`(x=0 .
`. . 15) and the line V of the macroblock A can be
`expressed as P-1y (y=0 . . . 15).
`0.015. In FIG.3A, a mode 0 (vertical mode) is illustrated.
`0016 Referring to FIG. 3A, by using the 16 pixels in the
`line H of the macroblock B, spatial intra-prediction is
`performed by Setting the values of all the pixels of a column
`in the macroblock E equal to the values of the pixels in the
`line H directly above the column.
`0017. That is, in mode 0, when Pxy is defined as an
`intra-predicted value of the actual pixel value Pxy and all
`16 pixels (PIX-1, x=0 .
`. . 15) of the line H of the
`macroblock B exist, extrapolation is performed on a pixel
`by-pixel basis using
`Pxy=Px-1, x=0 ... 15, y=0 . . . 15
`0.018. In FIG. 3B, a mode 1 (horizontal mode) is illus
`trated.
`0019 Referring to FIG.3B, by using the 16 pixels in the
`line V of the macroblock A, Spatial intra-prediction is
`performed by Setting the values of all the pixels of a column
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 22
`
`

`

`US 2005/0265447 A1
`
`Dec. 1, 2005
`
`in the macroblock E equal to the values of the pixels in the
`line V directly to the left of the column.
`0020 Namely, in mode 1, when Pxy is defined as the
`intra-predicted value of the actual pixel value Pxy and all
`16 pixels of the line V (P-1Iy), y=0 . . . 15) of the
`macroblock A exist, extrapolation is performed on a pixel
`by-pixel basis using
`Pxy=P-1y, x=0 ... 15, y=0 . . . 15
`0021. In FIG. 3C, a mode 2 (DC mode) is illustrated.
`0022 Referring to FIG. 3C, values defined by mean
`values (Sumx=0 . . . 15PXI-1+Sumy=0 . . . 15P-1Iy+
`16)/32) are mapped to all of the pixel values of the mac
`roblock E. The mean values are defined as follows.
`0023. When all the 16 pixels of the line V and all the 16
`pixels of the line H exist,
`Pxy=(Sumix=0 ... 15Px-1+Sumy=0 ... 15P
`1y+16)>>5, x=0 ... 15, y=0 ... 15
`0024. When only all the 16 pixels of the line V of the
`macroblock A exist,
`Pxy=(Sumix=0 ... 15Px-1+8)>>4, x=0 ... 15,
`y=0 ... 15
`0025. When only all the 16 pixels of the line H of the
`macroblock B exist,
`Pxy=(Sumy=0 ... 15P-1y-8)>>4, x=0 ... 15,
`y=0 ... 15
`0026. Also, when neither all 16 pixels of the line V of the
`macroblock
`0027) A nor all 16 pixels of the line H of the macroblock
`B exist,
`Pxy=128, x=0 ... 15, y=0 ... 15
`0028. In FIG. 3D, a mode 3 (plane Mode) is illustrated.
`0029) Referring to FIG. 3D, mode 3 only operates when
`both all 16 pixels of the line V of the macroblock A exist and
`all 16 pixels of the line H of the macroblock B exist and
`mapping is performed using the following Equation.
`
`0030 Mode 3 is appropriate for prediction of pixel values
`of an image that Slowly changes.
`0031. As such, conventionally, there is a total of four
`modes in 16x16 macroblock spatial intra-prediction. Thus,
`encoding and decoding are performed using 2-bit fixed
`length encoding (FLC) or variable length encoding (VLC)
`according to probability distribution.
`0032. After predicted pixel values of a block to be coded
`is obtained in each of the four modes, the predicted pixel
`values that are most similar to the actual pixel values of the
`block to be coded is transmitted to the decoder. At this time,
`to obtain a group (block) of the pixel values that are most
`Similar to the actual pixel values, a Sum of absolute differ
`ences (SAD) is calculated and a mode having the minimum
`SAD is selected. When Pxy is the actual pixel value of an
`image and PXy is the predicted pixel value determined in
`each mode, the SAD is given by
`
`SADMode=Sumix=0 ... 15.y=0 ... 15PyLy-Pix
`y
`0033) Once the selected intra-prediction mode is received
`and decoding is completed in the intra-prediction mode, the
`decoder createS predicted values of a corresponding mac
`roblock on a pixel-by-pixel basis in the same way as the
`encoder in the same intra-prediction mode.
`0034 AVC/H.264 video encoding is designed to have
`high network friendliness, which is an important require
`ment for Video encoding-related international Standardiza
`tion. To this end, AVC/H.264 employs slice-based indepen
`dent encoding as one of its major functions. This is because
`data that undergoes compression encoding becomes very
`Sensitive to transmission errors, which results in a very high
`probability that a part of a bit stream will be lost and such
`a loSS has a great influence on not only a portion of the bit
`Stream having the loSS but also restoration of an image that
`refers to the corresponding image, resulting in a failure to
`obtain flawless restoration. In particular, when using packet
`based transmission, which is widely used for Internet or
`mobile communications, if a packet error occurs during
`transmission, data following the damaged packet cannot be
`used for restoration of an image frame. Moreover, if a packet
`having header information is damaged, the entire data of the
`image frame cannot be restored, resulting in Significant
`degradation of image quality. To Solve Such a problem,
`AVC/H.264 determines a slice that is Smaller than a frame
`unit to be the Smallest unit of data that can be independently
`decoded. More Specifically, the Slices are determined Such
`that each Slice can be perfectly decoded regardless of data
`corresponding to other Slices that precede or follow the Slice.
`Therefore, even when data of Several Slices is damaged,
`there is a high probability of restoration or concealment of
`a damaged portion of an image using image data of Slices
`that are decoded without an error, which can minimize
`degradation of image quality.
`0035 AVC/H.264 is designed to support not only a slice
`Structure composed of groups of macroblockS in the raster
`Scan direction, but also a new slice Structure defined by
`flexible macroblock ordering (FMO). The new slice struc
`ture is adopted as an essential algorithm for a baseline profile
`and an extended profile. In particular, FMO mode 3 box-out
`Scanning has modes in which Scanning is performed in the
`clockwise direction and in the counter-clockwise direction,
`as shown in FIG. 4.
`0036 Scanning, Such as box-out Scanning, employed in
`AVC/H.264 is very useful for encoding a region of interest
`(ROI). Such scanning, as shown in FIG. 4, begins in the
`center of an ROI or the center of an image and then
`continues outward and around the already Scanned pixels,
`blocks, or macroblockS in the shape of Square rings. In other
`words, Scanning begins in a start region and continues Such
`that a Square ring is layered onto another Square ring that is
`processed before the current Square ring. When using ROI
`oriented Scanning, conventional intra-prediction designed
`for raster Scanning cannot be used.
`0037 AVC/H.264 carefully considers error resiliency and
`network friendliness to keep up with the rapidly changing
`wireleSS environment and Internet environment. In particu
`lar, box-out Scanning is designed for ROI encoding. The
`box-out Scanning makes it possible to improve compression
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 23
`
`

`

`US 2005/0265447 A1
`
`Dec. 1, 2005
`
`efficiency based on human Visual characteristics or to per
`form improved error protection and most preferentially
`perform ROI processing.
`0.038 However, since conventional video encoding such
`as AVC/H.264 employs intra-prediction encoding based on
`traditional raster Scanning which is very different from
`ROI-oriented Scanning, it cannot be used when a technique
`for improving encoding efficiency is applied to Video encod
`ing that is based on ROI-oriented Scanning.
`
`SUMMARY OF THE INVENTION
`0.039 The present invention provides a prediction
`encoder/decoder, a prediction encoding/decoding method,
`and a computer-readable recording medium having recorded
`thereon a program for implementing the prediction encod
`ing/decoding method, which are used for encoding/decoding
`an ROI.
`0040 According to one aspect of the present invention,
`there is provided a prediction encoder comprising a predic
`tion encoding unit. The prediction encoding unit Starts
`prediction at an origin macroblock of an area of interest of
`a Video frame, continues prediction in an outward Spiral in
`the shape of Square rings composed of macroblockS Sur
`rounding the origin macroblock, and encodes video by
`performing intra-prediction using information about a mac
`roblock that has just been coded in a Square ring including
`a macroblock to be coded and a macroblock in a previous
`Square ring and adjacent to the macroblock.
`0041. In an exemplary embodiment, the prediction
`encoder comprises an intra-prediction mode Selection unit
`and an intra-prediction unit. The intra-prediction mode
`Selection unit Selects a prediction mode that is most Suitable
`for the macroblock to be coded using the information about
`the macroblock that has just been coded in the Square ring
`including the macroblock to be coded and the macroblock in
`the previous Square ring and adjacent to the macroblock to
`be coded. The intra-prediction unit generates a predicted
`macroblock for the macroblock to be coded using the
`Selected prediction mode.
`0042. In an exemplary embodiment, the intra-prediction
`mode Selection unit comprises a reference macroblock
`Search unit, a reference macroblock location determining
`unit, and an intra-prediction mode determining unit. The
`reference macroblock Search unit Searches for a reference
`macroblock included in the Square ring including the mac
`roblock to be coded and a reference macroblock that is
`included in the previous Square ring and adjacent to the
`macroblock to be coded. The reference macroblock location
`determining unit determines the origin macroblock to be A
`if only the origin macroblock exists, determines a macrob
`lock included in the same Square ring to be A and a
`macroblock included in the previous Square ring to be D if
`Such macroblocks exist, and determines a macroblock that is
`included in the same Square ring and has just been coded to
`be A, a macroblock that is in the previous Square ring and
`adjacent to the macroblock to be coded to be B, and a
`macroblock that is adjacent to the macroblockSA and B and
`is included in the previous Square ring to be D, if a
`macroblock coded just before the macroblock to be coded is
`included in the Square ring and at least two macroblocks are
`included in the previous Square ring. The intra-prediction
`mode determining unit calculates SADS between the pre
`
`dicted macroblockS obtained using the prediction modes and
`the determined macroblockSA, B, and D and determines an
`intra-prediction mode having the Smallest SAD to be an
`intra-prediction mode.
`0043. In an exemplary embodiment, if only the macrob
`lock A exists as a reference macroblock or only the mac
`roblockS A and D exist as reference macroblocks, the
`intra-prediction mode determining unit determines which
`ever of mode 0 and mode 1 has the Smallest SAD to be an
`intra-prediction mode in mode 0, pixel values of a bottom
`most line of the macroblock A that is adjacent to the
`macroblock to be coded are extrapolated and then mapped to
`pixel values of the macroblock to be coded using only using
`information about the macroblock A, and, in mode 1, a mean
`of pixel values of the bottom-most line of the macroblock A
`that is adjacent to the macroblock to be coded is mapped to
`the pixel values of the macroblock to be coded using only
`the information about the macroblock A.
`0044) In an exemplary embodiment, if the macroblocks
`A, B, and D exist as reference macroblocks, the intra
`prediction mode determining unit determines whichever of
`mode 2, mode 3, mode 4, and mode 5 having the Smallest
`SAD to be an intra-prediction mode.
`0045. In mode 2, a mean of pixel values of the bottom
`most line of the macroblock A that is adjacent to the
`macroblock to be coded and the bottom-most line of the
`macroblock B is mapped to pixel values of the macroblock
`to be coded.
`0046. In mode 3, similarity among the macroblocks A, B,
`and D is measured and, if the macroblockS A and D are
`Similar to each other, a mean of pixel values of the bottom
`most line of the macroblock B that is adjacent to the
`macroblock to be coded is mapped to the pixel values of the
`macroblock to be coded or, if the macroblocks B and D are
`Similar to each other, a mean of pixel values of the bottom
`most line of the macroblock A that is adjacent to the
`macroblock to be coded is mapped to the pixel values of the
`macroblock to be coded.
`0047. In mode 4, similarity among the macroblocks A, B,
`and D is measured and, if the macroblockS A and D are
`Similar to each other, pixel values of the bottom-most line of
`the macroblock B that is adjacent to the macroblock to be
`coded are extrapolated and then mapped to the pixel values
`of the macroblock to be coded or, if the macroblocks B and
`D are similar to each other, pixel values of the bottom-most
`line of the macroblock A that is adjacent to the macroblock
`to be coded are extrapolated and then mapped to the pixel
`values of the macroblock to be coded.
`0048 Mode 5 is used when video characteristics of the
`macroblock to be coded gradually change from the macrob
`lock A to the macroblock B.
`0049. In an exemplary embodiment, the prediction
`encoder comprises a discrete cosine transform (DCT) unit,
`a quantization unit, a ripple Scanning unit, and an entropy
`encoding unit. The DCT unit performs DCT on a difference
`between the intra-predicted macroblock and the macroblock
`to be coded. The quantization unit quantizes transformed
`DCT coefficients. The ripple Scanning unit starts Scanning
`from the origin macroblock of a frame composed of the
`quantized DCT coefficients and continues to Scan macrob
`lockS in an outward Spiral in the shape of Square rings. The
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1034, p. 24
`
`

`

`US 2005/0265447 A1
`
`Dec. 1, 2005
`
`entropy encoding unit entropy encodes ripple Scanned data
`Samples and intra-prediction mode information Selected by
`the intra-prediction mode Selection unit.
`0050. According to another aspect of the present inven
`tion, there is provided a prediction decoder comprising a
`prediction decoding unit. The prediction decoding unit starts
`prediction at an origin macroblock of an area of interest of
`a Video frame, continues prediction in an outward Spiral in
`the shape of Square rings composed of macroblockS Sur
`rounding the origin macroblock, and decodes video by
`performing intra-prediction using information about a mac
`roblock that has just been decoded in a Square ring including
`a macroblock to be decoded and a macroblock in a previous
`Square ring and adjacent to the macroblock to be decoded in
`a previous Square ring.
`0051. In an exemplary embodiment, the prediction
`decoder comprises an intra-prediction mode Selection unit
`and an intra-prediction unit. The intra-prediction mode
`Selection unit Selects an intra-prediction mode that is most
`suitable for the macroblock to be decoded using the infor
`mation about the macroblock that has just been decoded in
`the Square ring including the macroblock to be decoded and
`the macroblock in the previous Square ring and adjacent to
`the macroblock to be decoded. The intra-prediction unit
`generates a predicted macroblock for the macroblock to be
`decoded using the Selected prediction mode.
`0.052
`In an exemplary embodiment, the intra-prediction
`mode selection unit comprises a reference macroblock
`Search unit, a reference macroblock location determining
`unit, and an intra-prediction mode determining unit. The
`reference macroblock Search unit Searches for a reference
`macroblock included in the Square ring including the mac
`roblock to be decoded and a reference macroblock that is
`included in the previous Square ring and adjacent to the
`macroblock to be decoded. The reference macroblock loca
`tion determining unit determines the origin macroblock to be
`A if only the origin macroblock exists, determines a mac
`roblock included in the same Square ring to be A and a
`macroblock included in the previous Square ring to be D if
`Such macroblocks exist, and determines a macroblock that is
`included in the Same Square ring and has just been decoded
`to be A, a macroblock that is in the previous Square ring and
`adjacent to the macroblock to be decoded to be B, and a
`macroblock that is adjacent to the macroblockSA and B and
`is included in the previous Square ring to be D, if a
`macroblock coded just before the macroblock to be coded is
`included in the Square ring and at least two macroblocks are
`included in the previous Square ring. The intra-prediction
`mode determining unit calculates SADS between the pre
`dicted macroblockS obtained using the prediction modes and
`the determined macroblockSA, B, and D and determines an
`intra-prediction mode having the Smallest SAD to be an
`intra-prediction mode.
`0053. In an exemplary embodiment, if received intra
`prediction mode information indicates mode 0, the intra
`prediction unit extrapolates pixel values of a bottom-most
`line of the macroblock A that is adjacent to the macroblock
`to be decoded and maps the extrapolated pixel values to
`pixel values of the macroblock to be decoded using only
`information about the macroblock A.
`0054.
`In an exemplary embodiment, if received intra
`prediction mode information indicates mode 1, the intra
`
`prediction unit maps a mean of pixel values of the bottom
`most line of the macroblock A that is adjacent to the
`macroblock to be decoded to the pixel values of the mac
`roblock to be decoded using only the information about the
`macroblock A.
`0055. In an exemplary embodiment, if received intra
`prediction mode information indicates mode 2, the intra
`prediction unit maps a mean of pixel values of the bottom
`most line of the macroblock A that is adjacent to the
`macroblock to be decoded and the bottom-most line of the
`macroblock B to pixel values of the macroblock to be
`decoded.
`0056. In an exemplary embodiment, if received intra
`prediction mode information indicates mode 3, the intra
`prediction unit measures Similarity among the macroblockS
`A, B, and D; and if the macroblocks A and D are similar to
`each other, the intra-prediction unit maps a mean of pixel
`values of the bottom-most line of the macroblock B that is
`adjacent to the macroblock to be decoded to the pixel values
`of the macroblock