(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2006/0002466A1
`Park
`(43) Pub. Date:
`Jan. 5, 2006
`
`US 20060002466A1
`
`Publication Classification
`
`(51) Int. Cl.
`(2006.01)
`H04B I/66
`(2006.01)
`H04N II/02
`(2006.01)
`H04N II/04
`(2006.01)
`H04N 7/12
`(52) U.S. Cl. ........ 375/240.03; 375/240.12; 375/240.24;
`375/240.2; 375/240.23
`
`(54) PREDICTION ENCODER/DECODER AND
`PREDICTION ENCODING/DECODING
`METHOD
`(75) Inventor: Gwang-hoon Park, Seongnam-si (KR)
`Correspondence Address:
`STAAS & HALSEY LLP
`SUTE 700
`1201 NEW YORKAVENUE, N.W.
`ABSTRACT
`(57)
`WASHINGTON, DC 20005 (US)
`(73) Assignees: Samsung Electronics Co., LTD., A prediction encoder/decoder and a prediction encoding/
`decoding method. The prediction encoder includes a predic
`Suwon-si (KR); Industry Academic
`tion encoding unit starting prediction from a origin macrob
`Cooperation Foundation Kyunghee
`lock of an area of interest of a Video frame, continuing
`University, Youngin-Si (KR)
`prediction in a direction of ripple Scanning with respect to a
`Square ring that includes macroblocks and Surrounds the
`(21) Appl. No.:
`11/141,263
`origin macroblock, and encoding Video by performing intra
`(22) Filed:
`Jun. 1, 2005
`prediction in 8x8 block units using information about a
`macroblock that has been just coded in a Square ring
`(30)
`Foreign Application Priority Data
`including a macroblock to be coded and at least one of
`macroblocks that are adjacent to the macroblock to be coded
`in a Square ring that has been just coded.
`
`Jun. 1, 2004 (KR).................................. 2004-0O398O7
`
`(CURRNET)
`
`
`
`
`
`
`
`
`
`F-1
`(REFERENCE) Yi
`(1 OR2 PREVIOUSLY
`ENCODER FRAMS)
`
`
`
`
`
`F.
`(RECONSTRUCTED)
`
`COMPENSATION
`
`PREDICTION
`UNT
`
`5
`
`6
`
`Z 7
`OUANTIZATION
`UNT
`
`B
`
`REPPLE
`SCANNT
`
`9
`ENTROPY
`ENCODINGUNT
`
`NA
`
`- - - - - - - - - - - - - - - - - -
`
`NTRA-PREDICTION:
`MODE INFORMATION
`- - - - - - - - - - - - - -
`-
`
`
`
`INVERSE
`QUAETION
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.1
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 1 of 17
`
`US 2006/0002466A1
`
`FIG. 1 (PRIOR ART)
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.2
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 2 of 17
`
`US 2006/0002466A1
`
`
`
`
`
`(I—H 'L-M) ESIMXOOTO-HEINDOO
`
`
`
`
`
`0 d[\OH0 HOITS
`
`
`
`
`
`
`
`
`
`(LHV HOIHA) 88 º?ôIJ
`
`
`
`(LHV HOIHA) V8 ‘DIJ
`
`+ + I + + ? + + + + + I + + I + +
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.3
`
`

`

`Patent Application Publication Jan.5, 2006 Sheet 3 of 17
`
`US 2006/0002466A1
`
`FIG. 4
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.4
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 4 of 17
`
`US 2006/0002466A1
`
`FIG. 5A
`
`SCANNING ORDER
`F2-F4-Fi-F3
`
`SCANNING ORDER
`F2-F4-F3-F1
`
`
`
`SCANNING ORDER
`F-F3-F 2--F4
`
`SCANNING ORDER
`F-F3-F 4-F2
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.5
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 5 of 17
`
`US 2006/0002466A1
`
`FIG.
`
`6A
`
`
`
`(a1)
`
`(a2)
`
`FIG.
`
`(b1)
`
`(b2)
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.6
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 6 of 17
`
`US 2006/0002466A1
`
`FIG.
`
`
`
`(c1)
`
`FIG.
`
`6D
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.7
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 7 of 17
`
`US 2006/0002466A1
`
`FIG.
`
`7A
`
`
`
`a1)
`
`a2)
`
`FIG.
`
`(b1)
`
`(b2)
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.8
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 8 of 17
`
`US 2006/0002466A1
`
`FIG.
`
`
`
`(c1
`
`(C2)
`
`FIG.
`
`(d1
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.9
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 9 of 17
`
`US 2006/0002466A1
`
`
`
`FIG.
`
`FIG.
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.10
`
`

`

`Patent Application Publication Jan.5, 2006 Sheet 10 of 17
`
`US 2006/0002466A1
`
`
`
`FIG.
`
`FIG.
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.11
`
`

`

`Patent Applicat
`
`US 2006/0002466A1
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.12
`
`

`

`Patent Application Publ
`ication
`
`Jan. 5, 2006 Sheet 12 of 17
`
`2
`
`
`
`
`
`
`
`
`
`
`
`6 * 0IJI
`
`US 2006/0002466A1
`
`||NTU
`
`9NICJOOBO
`
`ÅdOHINE TWNHEITIH
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.13
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 13 of 17
`
`US 2006/0002466A1
`
`FIG 10
`
`------------------------------------------------------------ 4--------- -
`INTRA-PREDICTION MODE SELECTION UNIT
`15
`
`16
`
`
`
`14
`
`REFERENCE
`MACROBLOCK
`SEARCH UNIT
`
`REFERENCE
`MACROBLOCKLOCATION
`DETERMINING UNIT
`
`INTRA
`PREDICTION MODE
`DETERMINING UNIT
`
`INTRA-PREDICTION
`MODE INFORMATION
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.14
`
`

`

`Patent Application Publication Jan.5, 2006 Sheet 14 of 17
`
`US 2006/0002466A1
`
`FIG 11
`
`ENCODING START
`
`
`
`
`
`am
`
`m. m.
`
`am - -
`
`- urgs m. m. m. -, - s m arm - - - - - a -
`
`- - -
`
`INTRA-PREDICTION
`DETERMINE INTRA-PREDICTION
`MODE
`
`---------
`
`---------------
`
`- 121
`
`PERFORM DCT
`
`130
`
`PERFORM QUANTIZATION
`
`140
`
`PERFORMRIPPLE SCANNING
`FROM ORIGIN OF FRAME
`
`150
`
`PERFORMENTROPY ENCODING
`
`160
`
`END
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.15
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 15 of 17
`
`US 2006/0002466A1
`
`FIG. 12
`
`NTRA-PREDICTION START
`
`SEARCH FOR REFERENCE
`MACROBLOCKS IN THE SAME SOUARE
`RING AND PREVIOUS SQUARE RING
`
`201
`
`DETERMINE LOCATIONS OF
`REFERENCE MACROBLOCKS
`(A, A+D, A+B+D)
`
`202
`
`
`
`NO
`
`DO ALL THE
`REFERENCE MACROBLOCKS
`A, B, AND DEXIST2
`
`203
`
`YES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PERFORMINTRA-PREDICTION
`USING ONLY INFORMATION
`ABOUT MACROBLOCK A
`
`PERFORMINTRA-PREDICTION
`USING INFORMATION
`ABOUT ALL OF REFERENCE
`MACROBLOCKSA, B, AND D
`
`OBTAIN PREDICTED
`MACROBLOCK OF MACROBLOCK
`E USING MODES O AND 1
`
`OBTAIN PREDICTED MACROBLOCK
`OF MACROBLOCKE USING
`MODES 2 AND 3
`
`CALCULATE SAD BETWEEN
`MACROBLOCKE AND
`PREDICTED MACROBLOCK
`
`DETERMINE MODE HAVING
`THE SMALLER SAD TO BE
`PREDICTION MODE
`
`
`
`CALCULATE SAD BETWEEN
`MACROBLOCKE AND
`PREDICTED MACROBLOCK
`
`DETERMINE MODE HAVING
`THE SMALLERSAD TO BE
`PREDICTION MODE
`
`PERFORMINTRA-PREDICTION IN
`DETERMINED PREDICTION MODE
`
`212
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.16
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 16 of 17
`
`US 2006/0002466A1
`
`FIG. 13
`
`DECODING START
`
`PERFORMENTROPY DECODING
`
`31 O
`
`PERFORMRIPPLE SCANNING
`FROM ORIGIN OF FRAME
`
`320
`
`PERFORM INVERSE OUANTIZATION - 330
`
`PERFORMINVERSE DCT
`
`340
`
`PERFORMINTRA-PREDICTION
`
`350
`
`RECONSTRUCT FRAME
`
`360
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.17
`
`

`

`Patent Application Publication Jan. 5, 2006 Sheet 17 of 17
`
`US 2006/0002466A1
`
`FIG. 14
`
`SEARCH FOR REFERENCE
`MACROBLOCKS IN THE SAME
`SQUARE RING AND PREVIOUS
`SOUARE RING
`
`DETERMINE LOCATIONS OF
`REFERENCE MACROBLOCKS
`(A, A+D, A+B+D)
`
`401
`
`402
`
`CHECKINFORMATION ABOUT
`INTRA-PREDICTION MODE
`
`403
`
`Sood
`
`404
`
`AP DC VALUE OF MACROBLOCK
`AINN-SHAPE SCANNING ORDER
`WITH REFERENCE TO
`MACROBLOCK A
`
`405
`
`o
`
`406
`
`AP DC VALUE OF MACROBLOCK
`A IN C-SHAPE SCANNING ORDEF
`WITH REFERENCE TO
`
`407
`
`MODE 3
`
`MAP DC VALUES OF ADJACENT
`BLOCKS IN SCANNING ORDER
`OF EA-EB --Ec-ED WITH
`REFERENCE TO MACROBLOCKS
`A AND B
`
`409
`
`
`
`MAP DC VALUES OF ADJACENT
`BLOCKS IN SCANNING ORDER
`OF EA-Ec-EB-ED WITH
`REFERENCE TO MACROBLOCKS
`A AND B
`
`41 O
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.18
`
`

`

`US 2006/0002466 A1
`
`Jan. 5, 2006
`
`PREDICTION ENCODER/DECODER AND
`PREDICTION ENCODING/DECODING METHOD
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`0001. This application claims the priority of Korean
`Patent Application No. 10-2004-00398.07, filed on Jun. 1,
`2004, in the Korean Intellectual Property Office, the disclo
`Sure of which is incorporated herein by reference.
`
`BACKGROUND OF THE INVENTION
`0002) 1. Field of the Invention
`0003. The present invention relates to moving picture
`encoding, and more particularly, to a prediction encoder/
`decoder and a prediction encoding/decoding method for
`encoding of an area of interest.
`0004 2. Description of Related Art
`0005 New standards called MPEG-4 part 10 AVC
`(advanced video encoding) or ITU-T H.264 emerged in
`2003 in the field of video compression. Fueling the emer
`gence was a change from conventional circuit Switching to
`packet Switching and a need for coexistence of various
`communication 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 coding are used. In conventional moving
`picture coding, coefficients transformed in a discrete cosine
`transform (referred to as a DCT transform hereafter) domain
`are Subject to intra-prediction to improve encoding effi
`ciency, resulting in degradation of Subjective quality at
`low-pass band transmission bit rates. On the other hand, in
`AVC/H.264, Spatial intra-prediction in a spatial domain,
`instead of in a DCT transform domain, is adopted.
`0007 From the point of view of an encoder, traditional
`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 is already encoded and
`reproduced and difference information between information
`about an actual block to be encoded and the predicted block
`is only encoded and transmitted to a decoder Side. At this
`time, a parameter required for prediction may be transmitted
`to the decoder Side or prediction may be performed by
`Synchronizing the encoder and the decoder. From the decod
`er's point of view, information about a block to be decoded
`is predicted using information about an adjacent block that
`is already decoded and reproduced, a Sum of the predicted
`information and the difference information transmitted from
`the encoder Side is calculated, and desired Structure infor
`mation is reproduced. At this time, if a parameter required
`for prediction is received from the encoder Side, it is also
`decoded for use.
`0008 Intra-prediction of block-based or macroblock
`based Video encoding according to prior art entirely adopts
`prediction using information about blocks A, B, C, and D
`that are adjacent to a block E to be coded in a traditional
`raster Scanning 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 therefore,
`
`is not available in encoding processing. Ablock marked with
`O is available when a prediction value is calculated, but it is
`far from the block E on a spatial axis. As a result, the block
`marked with O does not have high correlation with the block
`E and is rarely used.
`0009. As such, most of conventional intra-prediction uses
`a part of information about the blocks D, B, and C that are
`adjacent to the block E to be coded among blocks in an upper
`line adjacent to a line including the block E and information
`about the block A that has been coded just before encoding
`of the block E. In the case of MPEG-4-part 2, a DC value of
`the block E is predicted using differences between DC
`values of the blocks A, D, and B in an 8x8 DCT transform
`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 transform domain, are
`predicted.
`0010 FIG. 2 is a view for explaining intra-prediction
`encoding using 8x8 DCT coefficients according to the
`conventional art.
`0011 Referring to FIG. 2, 16x16 macroblocks are pro
`cessed in 8x8 block units and a DC value is predicted for
`each block in a DCT transform domain.
`0012. In other words, in FIG. 2, four macroblocks D, B,
`A, and E are shown and each macroblock is divided into four
`blocks. In other words, the macroblock D is divided into
`blocks D1, D2, D3, and D4, the macroblock B is divided into
`blocks B1, B2, B3, and B4, the macroblock A is divided into
`blocks A1, A2, A3, and A4, and the macroblock E is divided
`into blocks E1, E2, E3, and E4. Ablack square at the top left
`corner of each 8x8 block indicates a DC value of the block.
`0013 Intra-prediction within a macroblock E to be coded
`is performed as follows.
`0014 (1) To perform intra-prediction in the macroblock
`E, it is checked whether the macroblocks A, B, and D exist.
`If some of the macroblocks A, B, and D exist outside a video
`object plane (VOP), a predicted DC value is determined to
`be 1024 (that is equal to 128 as a pixel value).
`0015 (2) To process the block E1, it is checked whether
`the blocks D4, B3, and A2 exist. If some of the blocks D4,
`B3, and A2 do not exist or are not intra-coded, a predicted
`value of the block E1 is determined to be 1024.
`0016 (3) If all of the blocks D4, B3, and A2 exist, an
`intra-predicted DC value of the block E1 is determined as
`follows. In other words, if a difference between a DC value
`of the block A2 and a DC value of the block D4 is Smaller
`than a difference between a DC value of the block D4 and
`a DC value of the block B3, it means that there is a high
`probability that a DC value of the block E1 is similar to that
`of the block B3. Thus, the DC value of the block E1 is
`predicted from the DC value of the block B3. If the
`difference between the DC value of the block A2 and the DC
`value of the block D4 is larger than the difference between
`the DC value of the block D4 and the DC value of the block
`B3, the DC value of the block E1 is predicted from a DC
`value of the block A2. Such prediction can be applied to both
`the encoder Side and the decoder Side, and therefore, it is
`possible to perform intra-prediction encoding without trans
`mitting a parameter for calculation of a predicted value. In
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.19
`
`

`

`US 2006/0002466 A1
`
`Jan. 5, 2006
`
`other words, in the decoder Side, a predicted value should be
`calculated in a manner Similar to that of the encoder Side.
`0017 Prediction of the block E1 can be arranged as
`follows.
`0018) If A2 DC-D4 DC-D4 DC-B3 DC, E1 DC
`B3 DC Else, E1-DC=A2 DC
`0019. To predict a DC value of the block E2, (1) through
`(3) are performed using blocks E1, B3, and B4 that are
`adjacent to the block E2. To predict a DC value of the block
`E3, (1) through (3) are performed using blocks A2, A4, and
`E1 that are adjacent to the block E3. To predict a DC value
`of the block E4, (1) through (3) are performed using blocks
`E1, E2, and E3 that are adjacent to the block E4. In other
`words, intra-prediction based on 8x8 block units of the
`macroblock E is performed in a raster Scanning direction in
`the form of Z.
`0020 AVC/H.264 video encoding is designed to have
`high network friendlineSS that will be important require
`ments 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
`that Since data that undergoes compression encoding
`becomes very Sensitive to a transmission error caused during
`transmission, there is a very high possibility that a part of
`corresponding bit Streams is lost upon the occurrence of the
`transmission error and Such a loSS has a great influence on
`not only a portion 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 that is widely used in an
`Internet or mobile communication network environment, 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 qual
`ity. 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,
`each slice is determined on the assumption that a 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 additionally damaged, there is
`a high possibility of restoration or concealment of an image
`of a damaged portion, using image data of Slices that are
`decoded without an error, which can minimize degradation
`of image quality.
`0021 AVC/H.264 is designed to support not only a slice
`Structure composed of groups of macroblocks in a raster
`Scanning direction according to the conventional art, but
`also a new slice Structure defined in flexible macroblock
`ordering (FMO). The new slice structure is adopted as an
`essential algorithm of a baseline profile and an extended
`profile. In particular, FMO mode 3 box-out scanning has
`modes, in each of which Scanning is performed in the
`clockwise direction and in the counter-clockwise direction,
`as shown in FIG. 3.
`0022 Scanning, Such as box-out Scanning, employed in
`AVC/H.264 is very useful for encoding of a region of
`interest (ROI). According to Such scanning, as shown in
`FIG.3, Scanning begins in the center of an ROI or the center
`
`of an image and then continues in Such a way that each onion
`skin-like group of pixels, blocks, or macroblockS is Sequen
`tially layered in the shape of a Square ring. In other words,
`Scanning begins in a start region and continues in a way that
`a Square ring is layered onto another Square ring that is
`processed just before the previous Square ring. When using
`ROI-centered Scanning, conventional intra-prediction that is
`designed to fit for raster Scanning cannot be used.
`0023 AVC/H.264 is methodology that carefully consid
`erS error resiliency and network friendliness to keep pace
`with the rapidly changing wireleSS environment and Internet
`environment. In particular, box-out Scanning is methodology
`for ROI encoding. The box-out Scanning makes it possible
`to improve compression efficiency based on human visual
`characteristics or to perform improved error protection and
`allows ROI processing with the highest priority.
`0024 However, since conventional video encoding such
`as AVC/H.264 employs intra-prediction encoding based on
`traditional raster scanning that is very different from ROI
`centered Scanning, it cannot be used when a technique for
`improving encoding efficiency is applied to Video encoding
`that is based on ROI-centered Scanning.
`
`BRIEF SUMMARY
`0025. An aspect of the present invention provides a
`prediction encoder/decoder and a prediction encoding/de
`coding method for encoding of an ROI.
`0026. According to one aspect of the present invention,
`there is provided a prediction encoder including a prediction
`encoding unit which starts prediction from an origin mac
`roblock of an area of interest of a Video frame, continues
`prediction in a direction of ripple Scanning with respect to a
`Square ring that includes macroblocks and Surrounds the
`origin macroblock, and encodes video by performing intra
`prediction in 8x8 block units using information about a
`macroblock that has been just coded in a present Square ring
`including a macroblock to be coded and at least one of
`macroblocks that are adjacent to the macroblock to be coded
`in a previous Square ring which is inner Square ring adjacent
`to the present Square ring.
`0027. The prediction encoding unit may predict a DCT
`coefficient of each block of the macroblock to be coded
`using a DCT coefficient of each block of the origin mac
`roblock or a DCT coefficient of each block of the macrob
`lock A, when the macroblock to be coded is a first macrob
`lock after completion of encoding of the origin macroblock
`or there exist two reference macroblocks of the macroblock
`to be coded, wherein the two reference macroblockS
`includes a macroblock A that is included in the present
`Square ring and has been just coded and a macroblock D that
`is included in the present Square ring and is adjacent to the
`macroblock to be coded.
`0028. The prediction encoding unit may predict the
`remaining blocks after the prediction encoding unit first
`predicts, among the blocks of the macroblock to be coded,
`a block that is adjacent to the origin macroblock or the
`macroblock A,
`0029. The prediction encoding unit may predict a DCT
`coefficient of each block of the macroblock to be coded
`using DCT coefficients of blocks of the macroblocks A, B,
`and D, when a macroblock A that is included in the present
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.20
`
`

`

`US 2006/0002466 A1
`
`Jan. 5, 2006
`
`Square ring and has been just coded, a macroblock B that is
`included in the previous Square ring and is adjacent to the
`macroblock to be coded, and a macroblock D that is
`included in the previous Square ring and is adjacent to the
`macroblockSA and B exist as reference macroblocks of the
`macroblock to be coded,
`0030 The prediction encoding unit first may predict,
`among the blocks of the macroblock to be coded, a block EA
`that is adjacent to the macroblockSA and B, a block E that
`is only adjacent to the macroblock A or a block E that is
`only adjacent to the macroblock B, and then a block E that
`is adjacent to the blockS E and E.
`0031. The prediction encoding unit may include a refer
`ence macroblock Search unit Searching for a reference
`macroblock included in the present Square ring and a refer
`ence macroblock that is included in the previous Square ring
`and is adjacent to the macroblock to be coded; a reference
`macroblock location determining unit determining the origin
`macroblock to be A if only the origin macroblock exists,
`determining a macroblock included in the present Square
`ring to be A and a macroblock included in the previous
`Square ring to be D if two macroblocks exist, each being
`included in the present Square ring and in the previous
`Square ring, and determining a macroblock that is included
`in the present Square ring and has been just coded to be A,
`a macroblock that is adjacent to the macroblock to be coded
`in the previous Square ring 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 is included in
`the present Square ring and at least two macroblocks are
`included in the previous Square ring, and an intra-prediction
`unit encoding the macroblock in a predetermined Scanning
`order of the blocks of the macroblock to be coded using the
`determined reference macroblocks A, B, and D.
`0.032 The prediction encoding unit may include an intra
`prediction mode determining unit determining a prediction
`mode having the minimum Sum of absolute differences
`between the macroblock to be coded and each predicted
`macroblock in an intra-prediction mode according to a
`Scanning order using the reference macroblockSA, B, and D
`that are determined to determine the Scanning order.
`0033. The prediction encoding unit may include a dis
`crete cosine transform (DCT) unit performing DCT on a
`difference between the intra-predicted macroblock and the
`macroblock to be coded; a quantization unit quantizing
`transformed DCT coefficients, a ripple Scan unit starting
`Scanning from the origin macroblock of a frame composed
`of the quantized DCT coefficients and continuing to Scan
`macroblocks of a next Square ring in a ripple Scanning
`direction; and an entropy encoding unit entropy encoding
`ripple Scanned data Samples.
`0034. According to another aspect of the present inven
`tion, there is provided a prediction decoder including a
`prediction decoding unit which Starts prediction from a
`origin macroblock of an area of interest of a Video frame,
`continues prediction in a direction of ripple Scanning with
`respect to a Square ring that includes macroblockS and
`Surrounds the origin macroblock, and decoding video by
`performing intra-prediction in 8x8 block units using infor
`mation about a macroblock that has been just decoded in a
`present Square ring including a macroblock to be decoded
`and at least one of macroblocks that are adjacent to the
`
`macroblock to be decoded in a previous Square ring which
`is inner Square ring adjacent to the present Square ring.
`0035. The prediction encoding unit may predict a DCT
`coefficient of each block of the macroblock to be decoded
`using a DCT coefficient of each block of the origin mac
`roblock or a DC coefficient of each block of the macroblock
`A, when the macroblock to be decoded is a first macroblock
`after completion of decoding of the origin macroblock or
`there exist two reference macroblocks of the macroblock to
`be decoded, wherein the two reference macroblocks include
`a macroblock A that is included in the present Square ring
`having the macroblock to be decoded and has been just
`decoded and a macroblock D that is included in the previous
`Square ring and is adjacent to the macroblock to be decoded.
`0036) The prediction encoding unit may predict the
`remaining blocks after the prediction decoding unit first
`predicts, among the blocks of the macroblock to be decoded,
`a block that is adjacent to the origin macroblock or the
`macroblock A.
`0037. The prediction encoding unit may predict a DCT
`coefficient of each block of the macroblock to be decoded
`using DCT coefficients of blocks of the macroblocks A, B,
`and D when a macroblock A that is included in the present
`Square ring and has been just decoded, a macroblock B that
`is included in the previous Square ring and is adjacent to the
`macroblock to be decoded, and a macroblock D that is
`included in the previous Square ring and is adjacent to the
`macroblocks A and B exist as reference macroblocks of the
`macroblock to be decoded.
`0038. The prediction decoding unit first may predict,
`among the blocks of the macroblock to be decoded, a block
`EA that is adjacent to the macroblocks A and B, a block E.
`that is only adjacent to the macroblock A or a block E that
`is only adjacent to the macroblock B, and then a block E.
`that is adjacent to the blockS E and E.
`0039 The prediction decoding unit may include a refer
`ence macroblock Search unit Searching for a reference
`macroblock included in the present Square ring and a refer
`ence macroblock that is included in the previous Square ring
`and is adjacent to the macroblock to be decoded; a reference
`macroblock location determining unit determining the origin
`macroblock to be A if only the origin macroblock exists,
`determining a macroblock included in the present Square
`ring to be A and a macroblock included in the previous
`Square ring to be D if two macroblocks exist, each being
`included in the present Square ring and in the previous
`Square ring, and determining a macroblock that is included
`in the present Square ring and has been just decoded to be A,
`a macroblock that is adjacent to the macroblock to be
`decoded in the previous Square ring to be B, and a macrob
`lock that is adjacent to the macroblockS A and B and is
`included in the previous Square ring to be D, if a macroblock
`is included in the present Square ring and at least two
`macroblocks are included in the previous Square ring, and an
`intra-prediction unit decoding the macroblock in a prede
`termined Scanning order of the blocks of the macroblock to
`be decoded using the determined reference macroblockSA,
`B, and D.
`0040. The prediction decoding unit may include an intra
`prediction mode determining unit determining a prediction
`mode having the minimum Sum of absolute differences
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1007, p.21
`
`

`

`US 2006/0002466 A1
`
`Jan. 5, 2006
`
`between the macroblock to be decoded and each predicted
`macroblock in an intra-prediction mode according to a
`Scanning order using the reference macroblockSA, B, and D
`that are determined to determine the Scanning order.
`0041. The prediction decoder may include an entropy
`decoding unit entropy decoding a bitstream received from a
`prediction encoder; a ripple Scan unit Starting Scanning from
`the origin macroblock of a frame composed of entropy
`decoded data Samples and continuing to Scan macroblockS
`of a neXt Square ring in a ripple Scanning direction; an
`inverse quantization unit inversely quantizing the ripple
`Scanned data Samples, an inverse discrete cosine transform
`(IDCT) unit performing IDCT on the inversely quantized
`data Samples, and an adder adding a macroblock composed
`of inversely-quantized and IDCTed coefficients to the pre
`dicted macroblock.
`0042. According to yet another aspect of the present
`invention, there is provided a prediction encoding method
`including prediction encoding by Starting prediction from a
`origin macroblock of an area of interest of a Video frame,
`continuing prediction in a direction of ripple Scanning with
`respect to a Square ring that includes macroblockS and
`Surrounds the origin macroblock, and encoding video by
`performing intra-prediction in 8x8 block units using infor
`mation about a macroblock that has been just coded in a
`present Square ring including a macroblock to be coded and
`at least one of macroblocks that are adjacent to the mac
`roblock to be coded in a previous Square ring which is inner
`Square ring adjacent to the present Square ring.
`0043. According to still another aspect of the present
`invention, there is provided a prediction decoding method
`including prediction decoding by Starting prediction from a
`origin macroblock of an area of interest of a Video frame,
`continuing prediction in a direction of ripple Scanning with
`respect to a Square ring that includes macroblockS and
`Surrounds the origin macroblock, and decoding video by
`performing intra-prediction in 8x8 block units using infor
`mation about a macroblock that has been just decoded in a
`present Square ring including a macroblock to be decoded
`and at least one of macroblocks that are adjacent to the
`macroblock to be decoded in a previous Square ring which
`is inner Square ring adjacent to the present Square ring.
`0044) Additional and/or other aspects and advantages of
`the present invention will be set forth in part in the descrip
`tion which follows and, in part, will be obvious from the
`description, or may be learned by practice of the invention.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`004.5 These and/or other aspects and advantages of the
`present invention will become apparent and more readily
`appreciated from the following detailed description, taken in
`conjunction with the accompanying drawings of which:
`0.046
`FIG. 1 shows reference blocks required for intra
`prediction encoding in the raster Scanning direction accord
`ing to the conventional art;
`0047 FIG. 2 is a view for explaining intra-prediction
`encoding using 8x8 DCT coefficients according to the
`conventional art;
`0048 FIGS. 3A and 3B are views for explaining FMO
`mode 3 box-out Scanning according to the conventional art;
`
`0049 FIG. 4 is a view for explaining locations of mac
`roblocks in a current Square ring to perform intra-prediction
`encoding according to an order that Scanning begins in the
`center of a Square and continues in the shape of a Square
`ring,
`0050 FIGS. 5A (parts (a1) and (a2)) and 5B (parts (b1)
`and (b2)) show a Scanning order of prediction coding on a
`block-by-block basis when a first block only exists after an
`origin block or a macroblock is coded according to an
`embodiment of the present invention;
`0051 FIGS. 6A through 6D (respective parts (a1)
`through (d2)) show a Scanning order of intra-prediction
`coding on a block-by-block basis when two reference mac
`roblocks only exist, in which the two reference macroblockS
`include a macroblock D of a Square ring that is immediately
`inwardly adjacent to a Square ring having a macroblock to be
`coded and a macroblock (A) that is included in the same
`Square ring having the macroblock to be coded, has been just
`coded, and can be referred to, ac