(12) United States Patent
`Nishi et al.
`
`USOO6426975B1
`(10) Patent No.:
`US 6,426,975 B1
`(45) Date of Patent:
`Jul. 30, 2002
`
`(54) IMAGE PROCESSING METHOD, IMAGE
`PROCESSINGAPPARATUS AND DATA
`RECORDING MEDIUM
`
`(75) Inventors: Takahiro Nishi, Neyagawashi; Toshiya
`Takahashi, Ibarakishi; Choong Seng
`Boon, Moriguchishi; Shinya Kadono,
`Kobeshi, all of (JP)
`(73) Assignee: Matsushita Electric Industrial Co.,
`Ltd. (JP)
`Subj
`y disclai
`h
`f thi
`ubject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`* Y Not
`Otice:
`
`(21) Appl. No.: 09/118,991
`(22) Filed:
`Jul. 20, 1998
`(30)
`Foreign Application Priority Data
`Jul. 25, 1997
`(JP) ............................................. 9-200499
`Sep. 18, 1997
`(JP) ............................................. 9-253765
`May 22, 1998
`(JP) ........................................... 10-141919
`(51) Int. Cl." .................................................. H04B 7/66
`(52) U.S. Cl. .................................................. 375/240.13
`(58) Field of Search ...
`... 375/240.13, 240.01,
`375/240.02, 240.15, 240.16, 240.17, 240.2,
`240.21, 240.28; 348/405.1, 406.1, 409. 1,
`416.1, 423, 426, 845, 845.1, 845.3; 382/232,
`230; 34.5/58; 708/402; H04B 7/66
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,920,353 A * 7/1999 Diaz et al. .................. 348/402
`6,002,801 A * 12/1999 Strongin et al. ............ 382/233
`6,151,075 A 11/2000 Shin et al. .................. 348/459
`6,233,280 B1 * 5/2001 Kim et al. ............. 375/240.21
`
`* cited by examiner
`
`Primary Examiner-Chris Kelley
`Assistant Examiner Tung Vo
`(74) Attorney, Agent, or Firm-Parkhurst & Wendel, L.L.P.
`(57)
`ABSTRACT
`An image processing method for dividing a digital image
`Signal into plural image Signals corresponding to plural
`blocks constituting a single display Screen, and performing
`block-by-block coding of the image Signals of the respective
`blocks, comprises transforming an image Signal of a coding
`target block to be Subjected to coding into frequency com
`ponents by frame-by-frame frequency transformation on a
`frame basis or field-by-field frequency transformation on a
`field basis, Setting a processing order for coding the fre
`quency components corresponding to the image Signal of the
`coding target block, according as the image Signal of the
`coding target block has been Subjected to the frame-by
`frame frequency transformation or the field-by-field fre
`quency transformation; and Successively coding the fre
`quency components corresponding to the image Signal of the
`coding target block according to the order which has been
`Set. Therefore, in coding of an interlaced image or a specific
`progressive image in which frame DCT blocks and field
`DCT blocks coexist, a run length is increased, thereby
`improving coding efficiency.
`
`5,510,840 A 4/1996 Yonemitsu et al. ......... 348/402
`
`5 Claims, 37 Drawing Sheets
`
`
`
`108
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 1
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`800 ||
`
`
`
`|(61-)
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 2
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 2 of 37
`
`US 6,426,975 B1
`
`114
`
`116
`
`
`
`
`
`decision
`unit
`
`506
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 3
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 3 of 37
`
`US 6,426,975 B1
`
`Fig.3
`
`601
`
`Decide
`DCT type of coding
`target block
`
`
`
`field
`
`
`
`frame 602
`
`
`
`603
`
`Output signal for
`selecting scanner 1
`
`Output signal for
`Selecting scanner 2
`
`
`
`Completion
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 4
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 4 of 37
`
`US 6,426,975 B1
`
`/0/
`
`
`
`90/ 3UUBJ?
`
`90/
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 5
`
`

`

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

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`
`
`
`
`O
`O
`9
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 7
`
`

`

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

`

`U.S. Patent
`
`US 6,426,975 B1
`
`C)
`O
`9
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 9
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 9 of 37
`
`US 6,426,975 B1
`
`| 08
`
`G08
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 10
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 10 Of 37
`
`US 6,426,975 B1
`
`| 06
`
`p[e]]
`
`906
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 11
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`s
`
`:
`
`g
`
`
`
`| 0 ||
`
`,000 ||
`
`
`
`^^^| 0,2 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 12
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`
`
`
`
`CN
`g
`
`^^^Q609
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 13
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 13 of 37
`
`US 6,426,975 B1
`
`| 0 ||
`
`902
`
`LOC]
`
`--T
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OCITA
`
`/09
`
`103 || 1 ( 7 || ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 14
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`O
`
`2
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 15
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 15 of 37
`
`US 6,426,975 B1
`
`
`
`107
`
`1801f1
`
`1802f
`
`evaluation
`function circuit
`
`function circuit 2
`
`1801 f2
`evaluation
`function circuit n
`
`1803
`
`1302
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 16
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 16 of 37
`
`US 6,426,975 B1
`
`Fig.16
`
`1601
`
`
`
`
`
`
`
`Decide
`whether scans for upper
`and left macroblocks are
`identical or not
`
`
`
`Decide
`which Scan the optumum
`Scan for upper and left
`macroblocks is
`
`
`
`
`
`
`
`1603
`
`
`
`Output signal for
`selecting scanner 1
`
`Output signal for
`Selecting Scanner 2
`
`Output signal for
`selecting scanner 3
`
`Completion
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 17
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`CD
`
``o-
`
`Tecoz,- - - - - - - -
`
`
`
`| 0 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 18
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`S
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 19
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`
`
`
`
`
`
`| 0:2 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 20
`
`

`

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

`

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

`

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

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 23 Of 37
`
`US 6,426,975 B1
`
`/0/ |
`
`N
`O
`
`80/ Þ
`
`90/ |
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Jo, Ieuô?s ?nd?nO
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 24
`
`

`

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

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 25 Of 37
`
`US 6,426,975 B1
`
`Fig.25
`
`
`
`102 103 104 105 106
`
`109
`
`112
`
`114
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 26
`
`

`

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

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 27 Of 37
`
`US 6,426,975 B1
`
`10||
`
`GOZ
`
`?suÐAu!
`
`O
`
`/0 ||
`
`ZOZ
`
`
`
`Jeuue0S ?SuÐAu!
`
`| 0:2
`| | |€ || ||
`
`CITA
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 28
`
`

`

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

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 29 Of 37
`
`US 6,426,975 B1
`
`Fig.30
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2------------E-O(Z)
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`| |
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`ET || | | | |
`|| |
`|
`| || | |
`|
`|
`|
`|
`| ROR1
`OHO(Z)
`3||||||3||||||
`%
`3| || ||
`1 || || ||
`%
`2
`H H
`2
`R2%
`X
`2
`|
`| | | | |
`
`%
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 30
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 30 Of 37
`
`US 6,426,975 B1
`
`O
`
`s 3.
`o &
`3 8
`g g C
`- CO N.
`O LD
`LO
`sesses
`w R
`
`or
`
`O
`CY)
`
`
`
`i w
`
`
`
`
`
`
`
`on 22 SR 88
`S
`&
`
`N
`
`O)
`
`O OO
`
`-
`
`a CN C.
`
`CN LD OO CN v
`- v- CN
`CO
`
`ry
`
`ye CN
`
`CO
`
`O N CO O
`y
`- CN C)
`
`CO
`
`O w
`
`v.
`
`2 gigggg
`g 9. 3 8
`s g &
`sessessic
`V R G o
`S.
`CO
`L)
`coole:3 sta
`enco? SSSIs
`- to Nass 38
`& G g S3
`oncos Sggs
`& 9 g S
`
`CN
`O
`
`O
`
`Y
`
`r
`
`S S. S. S3
`
`
`
`
`
`o 8
`
`
`
`t
`
`y
`
`O) & S.
`9
`o s s s g
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 31
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 32
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 32 of 37
`
`US 6,426,975 B1
`
`900!
`
`Z || ||
`
`OTA
`
`
`
`Q608. GOO!
`
`| 90OZ~~
`
`
`
`?00Z
`
`| 0 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 33
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 33 of 37
`
`US 6,426,975 B1
`
`
`
`
`
`5 3.
`
`
`
`| JeuueOS ºsuÐAu!
`
`
`
`z Jeuueos ºsuÐAu!
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 34
`
`

`

`U.S. Patent
`
`US 6,426,975 B1
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 35
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 35 0f 37
`
`US 6,426,975 B1
`
`/08 |
`
`908 ||
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 36
`
`

`

`U.S. Patent
`
`Jul. 30, 2002
`
`Sheet 36 of 37
`
`US 6,426,975 B1
`
`| 0 ||
`
`903
`
`Z00 ||
`
`
`
`goá v001 ( 708
`
`ZUu00||
`
`20
`
`9
`
`
`
`900 ||
`
`| 02
`
`900|
`
`G 10 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 37
`
`

`

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

`

`US 6,426,975 B1
`
`1
`IMAGE PROCESSING METHOD, IMAGE
`PROCESSINGAPPARATUS AND DATA
`RECORDING MEDIUM
`
`FIELD OF THE INVENTION
`The present invention relates to image processing
`methods, image processing apparatuses, and data recording
`media and, more particularly, to image processing methods,
`image processing apparatuses, and data recording media in
`which, in variable-length coding of frequency components
`of an interlaced image Signal, a Sequence of the frequency
`components is adaptively rearranged, thereby improving
`coding efficiency.
`
`15
`
`2
`processing. Therefore, when a Scan is performed So that
`coefficients of about the same size are consecutive, the
`efficiency of variable-length coding is improved.
`In coding an interlaced image Signal, when correlations
`between adjacent Scan lines are Strong, frame DCT
`processing, i.e., DCT using a frame as a unit, is carried out.
`When correlations between Scan lines in a field are strong,
`field DCT processing, i.e., DCT using a field as a unit, is
`carried out.
`More specifically, as shown in FIG. 27, in frame DCT
`processing of an interlaced image Signal, Scan lines of a first
`field and Scan lines of a Second field are alternately arranged
`to form one frame-Screen. This frame Screen is divided into
`plural macroblocks each comprising 16x16 pixels. Each
`macroblock is divided into four SubblockS-each comprising
`8x8 pixels. Thereby, the image signal is subjected to DCT
`processing Subblock by Subblock. Meanwhile, in field DCT
`processing of an interlaced image Signal, Each of macrob
`lockS constituting one frame Screen is formed by two first
`Subblocks comprising only Scan lines of a first field and two
`Second Subblocks comprising only Scan lines of a Second
`field. Thereby, the image signal is subjected to DCT pro
`cessing Subblock by Subblock.
`In MPEG, frame DCT or field DCT is adaptively selected
`for each macroblock. Accordingly, in order to perform
`accurate decoding to an input image signal, the blocking unit
`102 in the image coding apparatus 200a outputs DCT
`processing information 114 indicating a unit of DCT pro
`cessing for each macroblock (that is, information indicating
`whether each macroblock has been subjected to frame DCT
`or field DCT), together with the blocked image signal. Since
`a subblock which has been subjected to field DCT (a field
`DCT block) comprises only odd Scan lines or only even Scan
`lines among Scan lines constituting one frame Screen, a DCT
`coefficient group corresponding to the field DCT block
`includes more DCT coefficients indicating that the rate of
`change of pixel values in a vertical direction of a display
`Screen is higher, as compared with a DCT coefficient group
`corresponding to a Subblock which has been Subjected to
`frame DCT (a field DCT block).
`FIG. 28 is a block diagram illustrating a construction of
`an image decoding apparatus corresponding to the image
`coding apparatus shown in FIG. 26. In FIG. 28, reference
`numeral 200b designates an image processing apparatus
`(image decoding apparatus), which decodes the coded image
`Signal 113 which has been coded by the image coding
`apparatus 200a. This image decoding apparatus 200b con
`Sists of a variable-length decoding unit (hereinafter referred
`to as a VLD unit) 201 for performing variable-length decod
`ing to the coded image Signal 113, and an inverse Scanner
`202 for performing an inverse Scan to quantized values 111
`which are obtained by decoding so that the order of the
`quantized values 111 is returned to the order before rear
`rangement in coding. Further, the image decoding apparatus
`200b consists of an inverse quantization unit 203 for
`inverse-quantizing quantized values 107 which have been
`Subjected to inverse Scanning, to generate DCT coefficients
`(frequency components) 105 corresponding to a decoding
`target block to be Subjected to decoding, an inverse DCT
`unit 204 for performing inverse DCT processing to the DCT
`coefficients 105 to generate an image signal (pixel values)
`103 corresponding to the decoding target block, and an
`inverse blocking unit 205 for inverse-blocking the image
`signals 103 on the basis of the DCT processing information
`114 from the image coding apparatus 200a, thereby regen
`erating an image Signal 101 corresponding to one frame
`screen. Herein, the inverse quantization unit 203 and the
`
`25
`
`BACKGROUND OF THE INVENTION
`In recent years, discrete cosine transformation (DCT) has
`been widely utilized in image coding processing. In MPEG
`as a representative image coding method, an input image
`Signal is divided correspondingly to plural rectangular
`blocks constituting a single display Screen as units of DCT
`processing, and DCT processing is performed block by
`block to the blocked image Signal.
`A Specific description is given of image coding in MPEG.
`FIG. 26 is a block diagram illustrating a construction of
`a conventional image processing apparatus which performs
`the above-mentioned image coding. In FIG. 26, reference
`numeral 200a designates a conventional image processing
`apparatus (image coding apparatus), which performs coding
`including DCT processing to an image Signal. This image
`coding apparatus 200a consists of a blocking unit 102 for
`dividing an input image Signal 101 correspondingly to plural
`blocks constituting a single display Screen to generate an
`image signal (plural pixel values) 103 corresponding to each
`block, a DCT unit 104 for performing DCT processing to the
`image signal (pixel values) 103 to transform the image
`signal (pixel values) 103 into frequency components (DCT
`coefficients) 105, and a quantization unit 106 for quantizing
`the output 105 of the DCT unit 104 to generate quantized
`40
`values 107 corresponding to each block. Herein, the DCT
`unit 104 and the quantization unit 106 constitute an infor
`mation source coding unit 200a1.
`Further, the image coding apparatus 200a consists of a
`Scanner 109 for Setting the processing order for coding the
`quantized values 107, and a variable-length coding unit
`(hereinafter referred to as a VLC unit) 112 for performing
`variable-length coding to quantized values 111 to which the
`processing order has been Set, according to the Set order, to
`generate a bit stream 113 corresponding to the image Signal
`of each block.
`A description is given of the operation.
`Initially, the blocking unit 102 blocks an input image
`Signal 101 correspondingly to rectangular blocks each com
`prising 8x8 pixels, and outputs an image Signal (plural pixel
`55
`values) 103 corresponding to each block. The DCT unit 104
`transforms the image Signal (pixel values) 103 into plural
`frequency components (DCT coefficients) 105 by DCT. The
`quantization unit 106 converts the DCT coefficients 105 into
`quantized values 107 by quantization.
`Then, the scanner 109 performs rearrangement of the
`quantized values 107 So as to improve the efficiency of
`variable-length coding. That is, the scanner 109 sets the
`processing order for coding. Thereafter, the VLC unit 112
`performs variable-length coding to the quantized values
`which have been rearranged, according to the Set order. In
`addition, run length coding is used in variable-length coding
`
`35
`
`45
`
`50
`
`60
`
`65
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 39
`
`

`

`3
`inverse DCT unit 204 constitute an information Source
`decoding unit 200b1.
`In the image decoding apparatus 200b, inverse converting
`processes corresponding to the respective converting pro
`ceSSes in the image coding apparatus 200a are carried out to
`a coded image Signal, in the reverse order of the order in
`coding, thereby accurately decoding the coded image Signal.
`FIG. 29 is a block diagram illustrating a construction of
`another conventional image coding apparatus.
`In FIG. 29, reference numeral 200c designates an image
`processing apparatus (image coding apparatus), which per
`forms intra-frame predictive coding processing comprising
`generating predicted values of quantized values of a coding
`target block using information in a frame, and coding
`difference values between the predicted values and the
`quantized values of the coding target block.
`This image coding apparatus 200c includes the image
`coding apparatus 200a, a prediction unit 200c2 for gener
`ating predicted values, and a Scanning unit 200c1 for chang
`ing a Scan method using a parameter concerning generation
`of the predicted values. The prediction unit 200c2 consists of
`a predictor 305 for generating predicted values 303, and
`outputting first prediction information 309a and second
`prediction information 309b concerning generation of the
`predicted values, an adder 301 for subtracting the output
`(predicted values) 303 of the predictor 305 from the output
`107 of the quantization unit 106, and an adder 304 for adding
`the output 303 of the predictor 305 to an output 302 of the
`adder 301.
`The scanning unit 200c1 consists of three scanners
`109s 1-109s3 having different scan methods, for scanning
`the output 302 of the prediction unit 200c2, a first Switch
`108c for selecting one of the three scanners on the basis of
`a control signal 116 and supplying the output 302 of the
`prediction unit 200c2 to the selected Scanner, a second
`Switch 110c for selecting one of the three scanners on the
`basis of the control Signal 116 and Supplying an output of the
`Selected Scanner to the VLC unit 112, and a Scan control unit
`1401c for generating the control signal 116 on the basis of
`the first prediction information 309a. In addition, the second
`prediction information 309b is output from the image coding
`apparatus 200c.
`In the image coding apparatus 200c thus constructed, a
`Scan method is changed using the parameter concerning
`generation of predicted values (prediction information) 309,
`whereby the efficiency of variable-length coding is
`enhanced.
`A description is given of a method for generating pre
`dicted values with reference to FIG. 30.
`FIG. 30 shows a macroblock comprising 16x16 pixels.
`This macroblock comprises four Subblocks (hereinafter sim
`ply referred to as blocks) R0, R1,R2 and X each comprising
`8x8 pixels. The block X is a coding target block, and the
`blocks R0, R1 and R2 are already coded blocks which are
`adjacent to the coding target block X. Either block R1 or
`block R2 is referred in generating predicted values
`(quantized values) of the coding target block X. The block
`to be referred is decided using DC coefficients of the blocks
`R0, R1 and R2 (quantized values at the left upper ends of
`these blocks). Specifically, the absolute value of the differ
`ence between the DC coefficients of the blocks R0 and R1
`is compared with the absolute value of the difference
`between the DC coefficients of the blocks R0 and R2. When
`the absolute value of the difference between the DC coef
`ficients of the blocks R0 and R1 is larger, the block R1 is
`referred (reference in a vertical direction). When it is
`Smaller, the block R2 is referred (reference in a horizontal
`direction).
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,426,975 B1
`
`4
`When the block R1 is referred, the DC coefficient (the
`quantized value at the left upper end) of the block R1 and AC
`coefficients (quantized values at the uppermost line, except
`the DC coefficient) of the block R1 are used as predicted
`values of the coefficients of the block X at the same
`positions. When the block R2 is referred, the DC coefficient
`(the quantized value at the left upper end) of the block R2
`and AC coefficients (quantized values at the leftmost line,
`except the DC coefficient) of the block R2 are used as
`predicted values of the coefficients of the block X at the
`Same positions. In addition, in a case where the efficiency of
`variable-length coding is degraded by predicting AC
`coefficients, no AC prediction may be carried out.
`A scan method is changed according to ON/OFF of Ac
`prediction (whether AC prediction is performed or not) in
`intra-frame prediction. Further, when AC prediction is in the
`ON State, a Scan method is changed according to a reference
`direction of prediction. The first prediction information 309a
`supplied to the scan control unit 1401c includes ON/OFF
`information indicating ON/OFF of AC prediction, and pre
`diction direction information indicating a reference direction
`for AC prediction, and the Second prediction information
`309b includes only the ON/OFF information of AC predic
`tion.
`When Ac prediction is in the OFF state, a scan of
`quantized values is executed in the order shown in FIG.
`31(a). Thereby, the processing order for coding is set to the
`quantized values. In this case, in a group of quantized values
`corresponding to a Subblock, high-frequency components
`uniformly distribute in vertical and horizontal directions
`very often. Therefore, the quantized values are uniformly
`Scanned in the order from low-frequency components to
`high-frequency components. When AC prediction is per
`formed and a vertical direction is referred, a Scan of quan
`tized values is executed in the order shown in FIG.31(b). In
`this case, a group of quantized values corresponding to a
`Subblock has a distribution in which high-frequency com
`ponents in a horizontal direction are reduced by the predic
`tion. Therefore, the quantized values are Scanned with a
`priority given to a horizontal direction, thereby improving
`the efficiency of variable-length coding. When AC predic
`tion is performed and a horizontal direction is referred, a
`Scan of quantized values is executed in the order shown in
`FIG. 31(c). In this case, a group of quantized values corre
`sponding to a Subblock has a distribution in which high
`frequency components in a vertical direction are reduced by
`the prediction. Therefore, the quantized values are Scanned
`with a priority given to a vertical direction, thereby improv
`ing the efficiency of variable-length coding.
`FIG. 32 is a block diagram illustrating a construction of
`an image decoding apparatus corresponding to the image
`coding apparatus shown in FIG. 29. In FIG. 32, reference
`numeral 200d designates an image processing apparatus
`(image decoding apparatus), which decodes the coded image
`Signal 308 that has been coded in the image coding apparatus
`200c.
`This image decoding apparatus 200d has an inverse
`Scanning unit 200d1 for performing an inverse Scan to
`quantized values which are obtained by variable-length
`decoding of the coded image signal 308 so that the order of
`the quantized values is returned to the order before Scanning
`in coding, and changing an inverse Scan method on the basis
`of the prediction information (parameter) concerning gen
`eration of predicted values in the image coding apparatus
`200c, and a prediction unit 200d2 for adding quantized
`values (predicted values) of a decoding target block which
`are predicted from quantized values of an already decoded
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1014, p. 40
`
`

`

`S
`block in the vicinity of the decoding target block, to the
`quantized values corresponding to the decoding target block
`which have been Subjected to inverse Scanning.
`The inverse scanning unit 200d1 consists of three inverse
`scanners 202s1-202S3 having different inverse scan
`methods, for inverse-scanning the output of the VLD unit
`201, a first Switch 108d for selecting one of the three inverse
`Scanners on the basis of a control Signal 116 and Supplying
`the output of the VLD unit 201 to the selected inverse
`Scanner, a Second Switch 110d for Selecting one of the three
`inverse Scanners on the basis of the control signal 116 and
`Supplying the output of the Selected inverse Scanner to the
`prediction unit 200d2, and an inverse scan control unit
`1401d for generating the control signal 116 on the basis of
`the first prediction information 309a.
`In addition, the inverse scanner 202s1 performs an inverse
`scan corresponding to the scan by the scanner 109s 1 in the
`image coding apparatus 200c, the inverse Scanner 202s2
`performs an inverse Scan corresponding to the Scan by the
`scanner 109s2 in the image coding apparatus 200c, and the
`inverse Scanner 202S3 performs an inverse Scan correspond
`ing to the scan by the scanner 109s3 in the image coding
`apparatus 200c.
`The prediction unit 200d2 consists of a predictor 401 for
`generating predicted values 303 on the basis of the second
`prediction information 309b output from the image coding
`apparatus 200c and values 107d corresponding to the quan
`tized values 107 in the image coding apparatus 200c, and
`generating control prediction information 309a' correspond
`ing to the first prediction information 309a in the image
`coding apparatus 200c, and an adder 304 for adding the
`predicted values 303 to the output 302 of the inverse
`scanning unit 200d1. In addition, like the first prediction
`information 309a, the control prediction information 309a'
`includes ON/OFF information of AC prediction and predic
`tion direction information of AC prediction.
`In the image decoding apparatus 200d thus constructed,
`inverse converting processes corresponding to the respective
`converting processes in the image coding apparatus 200c
`shown in FIG. 29 are carried out to a coded image Signal, in
`the reverse order of the order in coding, thereby accurately
`decoding the coded image Signal.
`FIG. 33 is a block diagram illustrating a construction of
`Still another conventional image coding apparatus. In FIG.
`33, reference numeral 200e designates an image processing
`apparatus (image coding apparatus), which performs inter
`frame predictive coding processing comprising generating
`predicted values of an image signal (pixel values) of a
`coding target frame from another frame, and coding differ
`ence values between the image Signal (pixel values) of the
`coding target frame and the predicted values.
`This image coding apparatus 200e has an information
`Source coding unit 200e2 for performing information Source
`coding to difference values 1002 between an image Signal
`(pixel values) 103 obtained by blocking and predicted values
`1008 of the image signal 103, in place of the information
`Source coding unit 200a1 in the image coding apparatus
`200a shown in FIG. 26, which performs information source
`coding to the image Signal 103. Further, the image coding
`apparatus 200e has a Scanning unit 200e 1 for changing a
`Scan method, i.e., the processing order for coding, according
`to a parameter 1015 concerning generation of the predicted
`values 1008, in place of the scanner 109 in the image coding
`apparatus 200a.
`The information source coding unit 200e2 consists of an
`adder 1001, a DCT unit 104e, a quantization unit 106e, an
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,426,975 B1
`
`6
`inverse quantization unit 203e, an inverse DCT unit 204e, an
`adder 1010, a frame memory 1014, and a predictor 1012.
`The adder 1001 is for subtracting predicted values 1008
`from an image signal (pixel values) 103 corresponding to a
`coding target block. The DCT unit 104e is for transforming
`difference values 1002 between the image signal (pixel
`values) 103 and the predicted values 1008 into frequency
`components (DCT coefficients) 1003 by DCT. The quanti
`zation unit 106e is for quantizing the DCT coefficients 1003
`to generate quantized values 1004 corresponding to the
`coding target block.
`Further, the inverse quantization unit 203e is for inverse
`quantizing the quantized values 1004 output from the quan
`tization unit 106e to output DCT coefficients 1007 corre
`sponding to the DCT coefficients 1003. The inverse DCT
`unit 204e is for performing inverse DCT to the DCT
`coefficients 1007 to output difference signals 1009 corre
`sponding to the difference values 1002. The adder 1010 is
`for adding the predicted values 1008 to the difference signals
`1009 to output an already coded image signal 1011 corre
`sponding to the coding target block.
`Furthermore, the frame memory 1014 is for temporarily
`Storing already coded image Signals 1011 corresponding to
`one frame or corresponding to frames of a prescribed
`number. The predictor 1012 is for generating the predicted
`values 1008 on the basis of an already coded image signal
`1013 corresponding to a reference block in the memory
`1014 and the image signal 103 corresponding to the coding
`target block.
`The scanning unit 200e1 consists of two scanners 129s1
`and 129s2 having different Scan methods, for Scanning the
`output of the information source coding unit 200e2, a first
`Switch 108e for selecting one of the two scanners on the
`basis of a control signal 116e and supplying the output 1004
`of the information source coding unit 200e2 to the selected
`Scanner, a Second Switch 110e for Selecting one of the two
`Scanners on the basis of the control signal 116e and Supply
`ing an output of the Selected Scanner to the VLC unit 112,
`and a Scan control unit 1016e for generating the control
`signal 116e on the basis of a parameter 1015 from the
`predictor 1012.
`Herein, the Scanner 129S1 performs a Scan of quantized
`values in the order shown in FIG.31(a). The scanner 129s2
`is constituted by the respective elements 301, 304 and 305
`in the prediction unit 200c2 shown in FIG. 29, and the
`respective elements 108c, 110c, 109s 1-109s3 and 1401c in
`the scanning unit 200c1 shown in FIG. 29. That is, the
`scanner 129s2 performs intra-frame prediction to a block to
`which no inter-frame prediction has been performed in
`coding (hereinafter referred to as an intra-coded block) and
`selects one of the scanners 109s 1-109s3 constituting the
`scanner 129s2 on the basis of prediction information con
`cerning generation of predicted values. In addition, one of
`the scanners 109s 1-109s3 constituting the scanner 129s2
`performs a Scan of quantized values in the order shown in
`FIG. 31(a). The coding processing by the image coding
`apparatus 200e is fundamentally identical to that by the
`image coding apparatus 200c shown in FIG. 29, except that
`difference values between an image Signal which is obtained
`by blocking and predicted values of the image Signal are
`coded.
`That is, in inter-frame predictive coding by the image
`coding apparatus 200e, predicted values 1008 are set to 0
`when prediction efficiency is low, whereby an image Signal
`103 corresponding to a coding target block is Subjected to
`DCT processing as it is (intra-coding). Swit