`B00n et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,995,654 B2
`Aug. 9, 2011
`
`US007995654B2
`
`(54) IMAGE PREDICTIVE CODING METHOD
`(75) Inventors: Choong Seng Boon, Moriguchi (JP);
`Sheng Mei Shen, Singapore (SG);
`Thiow Keng Tan, Singapore (SG)
`Assignee: Panasonic Corporation, Osaka (JP)
`Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1297 days.
`Appl. No.: 11/601,728
`
`(73)
`(*)
`
`(21)
`(22)
`(65)
`
`Filed:
`
`Nov. 20, 2006
`
`Prior Publication Data
`US 2007/OO65O28A1
`Mar. 22, 2007
`
`Related U.S. Application Data
`Division of application No. 10/781,616, filed on Feb.
`20, 2004, now Pat. No. 7,394.941, which is a division
`of application No. 10/229,151, filed on Aug. 28, 2002,
`now Pat. No. 6,859,559, which is a division of
`application No. 09/513,198, filed on Feb. 25, 2000,
`now Pat. No. 6,532,306, which is a division of
`application No. 08/983,640, filed as application No.
`PCT/JP97/01800 on May 28, 1997, now Pat. No.
`6,148,109.
`Foreign Application Priority Data
`
`(62)
`
`(30)
`
`May 28, 1996
`Jul. 5, 1996
`Sep. 26, 1996
`
`(JP) ..................................... P8-132970
`(JP) ..................................... P8-176426
`(JP) ..................................... P8-254677
`
`(51)
`
`(52)
`(58)
`
`Int. C.
`(2006.01)
`H04N 7/2
`(2006.01)
`G06K 9/36
`U.S. Cl. ................................... 375/240.12;382/238
`Field of Classification Search .................. 358/.447,
`358/463,448; 348/405, 403: 382/263,266,
`382/275,232,248; 375/240.12
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,155,097 A
`5, 1979 Lux
`(Continued)
`
`EP
`
`FOREIGN PATENT DOCUMENTS
`O 422.404
`4f1991
`(Continued)
`OTHER PUBLICATIONS
`"Codebook adaptation algorithm for a scene adaptive video coder;
`Hartung: IEEE 95 vol. 4 pp. 2591-2594 (1995).
`(Continued)
`Primary Examiner — Jerome Grant, II
`(74) Attorney, Agent, or Firm — Wenderoth, Lind & Ponack,
`LLP.
`
`ABSTRACT
`(57)
`When dividing inputted image data to be coded into image
`data of a plurality of small regions which are adjacent to each
`other and coding the image data of an objective Small region
`to be processed among the image data of the plurality of
`divided Small regions which are adjacent to each other, recon
`structed image data of a reproduction Small region adjacent to
`the image data of the objective Small region to be processed is
`used as image data of an intra-frame prediction Small region
`of the objective Small region to be processed, the image data
`of the intra-frame prediction Small region is used as image
`data of an optimum prediction Small region and image data of
`a difference small region which are differences between the
`image data of the objective Small region to be processed and
`the image data of the optimum prediction Small region is
`generated. Then, the generated image data of the difference
`Small region is coded and outputted, and then the coded image
`data of the difference small region is decoded, so that the
`reconstructed image data of the reproduction Small region is
`generated by adding the decoded image data of the difference
`Small region to the image data of the optimum prediction
`Small region.
`
`4 Claims, 26 Drawing Sheets
`
`First Preferred Erodiment
`image Predictive
`Coding Apparatus
`
`102
`
`
`
`103
`104.
`105
`few wery as - was - - - - - a - :
`
`
`
`Prediction
`Signal
`Generator 130
`2
`
`11
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.1
`
`
`
`US 7,995,654 B2
`Page 2
`
`
`
`*
`*
`ck
`
`U.S. PATENT DOCUMENTS
`5, 1989 Ozeki et al.
`4,833,535
`9, 1989 Gonzales et al.
`4,870,695
`12, 1995 Kim ......................... 375,240.03
`5,473,377
`1/1996 Yonemitsu et al.
`5,485,279
`... 375,240.03
`2, 1997 Kim .....
`5,606,372
`... 375,240.04
`8, 1997 Ohtsuki ...
`5,654,760
`8/1998 Guissin ......................... 382,254
`5,799,111
`9/1999 Jang et al.
`5,959,674
`10, 1999 Mochizuki
`5,970,172
`10/1999 Eifriget al.
`5,974, 184
`12, 1999 Haskell
`6,005,622
`11/2000 Boon
`6,148,109
`1/2001 Cho et al.
`6,173,080 B1
`9, 2001 Shen et al.
`6,292.588 B1
`1/2002 Haskell et al.
`6,341,144 B1
`3, 2002 Shen et al.
`6,360,016 B1
`4/2002 Boon et al.
`6,366,703 B1
`4/2002 Shen et al.
`6,377,708 B1
`3f2007 Boon et al. .................... 382,238
`2007/0065028 A1
`
`EP
`EP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`
`FOREIGN PATENT DOCUMENTS
`O 549 813
`7, 1993
`O863673
`9, 1998
`60-143O88
`7, 1985
`61-201570
`9, 1986
`62-065.583
`3, 1987
`2-65583
`3, 1990
`4-306095
`10, 1992
`5-37786
`2, 1993
`5-336382
`12/1993
`7-231445
`8, 1995
`8-23536
`1, 1996
`10-304364
`3, 1998
`10-304364
`11, 1998
`
`OTHER PUBLICATIONS
`Video coding for mobile communications MPEG4 perspective; Kit
`tler Mobile Multimedia Comm. Dec. 1996 pp. 311-319.
`A 60mW MPEG4 video coder using clustered voltage scaling with
`variable Supply voltage scheme: Takahashi et al.; IEEE Journal of
`
`Solid State Circuits pp. 1772-1780 Nov. 1998 vol. 33 Issue 11 ISSN:
`OO18-920O.
`Puri, A., et al. “Improvements in DCT Based Video Coding”. Pro
`ceedings of the SPIE, Feb. 12, 1997.
`Wallace, G. K. “The JPEG Still Picture Compression Standard”.
`Communications of the Association for Computing Machinery, vol.
`34, No. 4, Apr. 1, 1991, pp. 30-44.
`C-T et al., “Efficient Encoding of DC Coefficients in Transform
`Coding of Images. Using JPEG Scheme'. Signal Image and Video
`Processing, Singapore, Jun.
`11-14, 1991, pp. 404-407.
`XPOOO384794.
`Netravali et al., “Picture Coding: A Review'. Proceedings of the
`IEEE, IEEE, New York, vol. 68, No. 3, Mar. 1, 1980, pp. 366-407.
`XPOO2O28499
`Ad Hoc Group on MPEG-4 Video VM Editing: “MPEG-4 Video
`Verification Model 5.0, Nov. 1996, pp.55-60, XP002240954.
`European Search Report issued Sep. 4, 2007 in European Application
`No. 071098.719-1522.
`European Search Report issued Sep. 4, 2007 in European Application
`No. 071098.933-1522.
`European Search Report issued Sep. 4, 2007 in European Application
`No. 07109900.6-1522.
`“MPEG-4 Video Verification Model Version 5.0”37 MPEG Meeting,
`Nov. 18, 1996-Nov. 22, 1996, Maceio, (Motion Picture Expert Group
`or ISO/IEC JTC1/SC29/WG 11), International Organization for
`Standardization (ISO), 1, CH. De La Voie-Creuse, Case Postale
`56 CH-1211 Geneva 20, Switzerland, Nov. 18, 1996.
`A. Puri et al., “Description and Results of Coding Efficiency Modi
`fied Experiment T16 in MPEG-4 Video', ISO/IEC JTC 1/SC29/
`WG11, vol. MPEG97, No. 1703, Feb. 1997, pp. 1-22.
`G. Sullivan, “Draft text of H.263+” ITU SG15, LBC Experts Group,
`Feb. 28, 1997, pp. 1-92.
`Office Action issued Jan. 17, 2008 in U.S. Appl. No. 10/781,616.
`Office Action issued Feb. 22, 2008 in U.S. Appl. No. 1 1/601,623.
`Office Action issued Mar. 6, 2008 in U.S. Appl. No. 1 1/601,796.
`Office Action issued Feb. 22, 2008 in U.S. Appl. No. 1 1/601,794.
`European Office Action issued Sep. 29, 2010 in European Applica
`tion No. 07 109 871.9.
`* cited by examiner
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.2
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 1 of 26
`
`US 7,995,654 B2
`
`
`
`
`
`| | |
`
`Z || ||
`
`| 0 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.3
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 2 of 26
`
`US 7,995,654 B2
`
`Fig.2
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.4
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 3 of 26
`
`US 7,995,654 B2
`
`
`
`N
`M
`Y
`W
`4 - - - - - - - - - - - - - -N
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.5
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.6
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 5 of 26
`
`US 7,995,654 B2
`
`
`
`| | |
`
`9:61-7
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.7
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 6 of 26
`
`US 7,995,654 B2
`
`0 | 9JOJ JE
`
`---------------------------?-----------------------------
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.8
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 7 of 26
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`?pOW
`
`uunuu??dO
`
`| 0 ||
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.9
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 8 of 26
`
`US 7,995,654 B2
`
`Fig.9
`
`800
`
`8O1
`
`6
`b7
`
`8O2
`
`Inside Object Region
`
`803
`
`
`
`Fig. 10
`
`8O7
`
`
`
`Inside Object Region
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.10
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 9 of 26
`
`US 7,995,654 B2
`
`/06
`
`/ 16
`
`
`
`
`
`6 | 6
`
`2 || 6
`
`uÐduJOO
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.11
`
`
`
`U.S. Patent
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.12
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 11 of 26
`
`US 7,995,654 B2
`
`Fig.14 PRIOR ART
`Image Predictive
`Coding ApparatuS
`
`Input Frame
`
`Block
`Sampling
`
`Motion
`Detection
`
`
`
`
`
`
`
`Motion
`Compensation
`
`10
`
`
`
`
`
`1010
`
`
`
`Reference
`Frame Memory
`
`
`
`Local Decoding
`Frame Memory
`
`O09
`
`Inverse DCT
`
`
`
`
`
`
`
`1008
`
`nverse
`Guantizing
`
`
`
`Rate
`Controller
`
`Bit Stream
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.13
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 12 of 26
`
`US 7,995,654 B2
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.14
`
`
`
`U.S. Patent
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.15
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.16
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.17
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 16 of 26
`
`US 7,995,654 B2
`
`
`
`NNNNNNNNNÇ
`
`Macro Block
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.18
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 17 of 26
`
`US 7,995,654 B2
`
`
`
`
`
`690 ||
`
`0
`
`LOC
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.19
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 18 of 26
`
`US 7,995,654 B2
`
`Fig.21
`
`1059
`
`Bit Stream
`
`Code Indication
`Bit from Bit Stream
`
`1 O60
`Flag="O"?
`(only DC Compo
`-nent?)
`
`1 O62
`Flag="10"?
`(from Right-hand
`Side?)
`
`1064
`Flag="11"?
`(from Upper
`Side?)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`O61
`
`Extract DC Component
`from a Plurality of
`Adjacent Blocks
`
`Extract Left Column
`from Block to be
`Processed to the Left
`
`Extract Top Row from
`Above Block
`
`O66
`
`
`
`Add DCT Coefficients
`Extracted for
`Reconstruction to
`Current Block
`
`End
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.20
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 19 of 26
`
`US 7,995,654 B2
`
`9002
`9002
`
`
`
`
`
`
`
`
`
`LHV HO|Hc] ©?'êt-|
`
`
`
`Þ002 c062 3003| 002
`
`
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.21
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 20 of 26
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`
`
`G303
`
`?7202£3032003| 202
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.22
`
`
`
`U.S. Patent
`
`US 7,995,654 B2
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.23
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 22 of 26
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`/ 903 9900ZGOZ
`
`€GOZ
`
`1900
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.24
`
`
`
`U.S. Patent
`
`US 7,995,654 B2
`
`
`
`
`
`
`
`
`
`
`º EEEEEEEF2EE
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.25
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.26
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 25 of 26
`
`US 7,995,654 B2
`
`Fig. 30
`Mode Determining Process
`Input of Current Block
`
`2O62
`
`Subtract DCT Coefficients Data
`from Adjacent DCT Block
`
`
`
`
`
`
`
`
`
`
`
`
`Leftward
`Upward
`Upward Leftward
`DC Model DC Model OC/AC Mode DC/AC Mode
`
`2O63
`
`2O64
`
`
`
`
`
`
`
`ZigZag
`ZigZag
`Scannina SCannino
`
`Horizontal
`SCannino
`
`Vertical
`SCanninC
`
`Entropy Coding
`
`
`
`
`
`Compare Bits Used for
`Different Prediction Blocks
`
`
`
`Predict DCT Blocks Based on Least Bit
`Use Rule and Output Predicted Block
`with Prediction Mode
`
`Bit Stream
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.27
`
`
`
`U.S. Patent
`
`Aug. 9, 2011
`
`Sheet 26 of 26
`
`US 7,995,654 B2
`
`Fig. 31
`
`
`
`A Plurality of
`Adjacent Blocks
`Serving as Base in
`Prediction Mode
`
`Current Block
`is Predicted
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.28
`
`
`
`1.
`IMAGE PREDICTIVE CODNG METHOD
`
`This is a divisional application of Ser. No. 10/781,616, filed
`Feb. 20, 2004 now U.S. Pat. No. 7,394,941 which is a divi
`sional application of Ser. No. 10/229,151, filed Aug. 28, 2002,
`now U.S. Pat. No. 6,859.559, which is a divisional application
`of Ser. No. 09/513,198, filed Feb. 25, 2000, now U.S. Pat. No.
`6,532.306, which is a divisional application of Ser. No.
`08/983,640, filed Jan. 28, 1998, now U.S. Pat. No. 6,148,109,
`which is the National Stage of International Application No.
`PCT/JP97/01800, filed May 28, 1997.
`
`TECHNICAL FIELD
`
`The present invention relates to an image predictive coding
`apparatus and method, image predictive decoding apparatus
`and method and recording medium. The present invention
`relates, in particular, to an image predictive coding apparatus
`and method as well as image predictive decoding apparatus
`and method for storing digital image data of an image which
`is a static image or a dynamic image into a recording medium
`Such as an optical disk or for transmitting the data through a
`communication line. The present invention also relates to a
`recording medium in which a program including the steps of
`the image predictive coding method is recorded as well as a
`recording medium in which a program including the steps of
`the image predictive decoding method is recorded.
`
`BACKGROUND ART
`
`For the purpose of efficiently storing or transmitting a
`digital image, the image is required to be coded in a compres
`sion coding manner. As a method for coding a digital image in
`a compression coding manner, there is a waveform coding
`method of sub-band coding, wavelet coding, fractal coding or
`the like other than discrete cosine transform (referred to as a
`DCT transform hereinafter) represented by JPEG (Joint Pho
`tographic Experts Group) and MPEG (Motion Picture
`Experts Group). For the purpose of removing a redundant
`signal between images, an inter-image prediction with a
`motion compensation is executed, thereby Subjecting a dif
`ferential signal to waveform coding.
`According to the MPEG system, an input image is pro
`cessed while being divided into a plurality of 16x16 macro
`blocks. One macro block is further divided into 8x8 blocks
`and quantized after undergoing 8x8 DCT transform. This is
`called an intra-frame coding.
`On the other hand, according to a motion detection method
`inclusive of block matching, a prediction macro block having
`the minimum error with respect to the objective macro block
`is detected from other frames adjacent in time, the detected
`prediction macro block is subtracted from the target macrob
`lock thereby forming a differential macro block, and this
`macro block is quantized after undergoing 8x8 DCT trans
`form. This is called an inter-frame coding, and the prediction
`macro block is called a prediction signal of the time domain.
`A normal image has spatially similar regions, and an image
`can be approximated to a spatial region by utilizing this
`characteristic. In a mariner similar to that of the prediction
`signal of the time region, a prediction signal can also be
`obtained from an identical frame. This is called a spatial
`prediction signal.
`Since spatially adjacent two pixel values are close to each
`other, the prediction signal of the spatial region is generally
`located close to the target signal. On the other hand, on the
`receiving side or the reproducing side, a signal which has
`been coded and reproduced in the past is required to be used
`
`2
`as the prediction signal since the original image is absent.
`From these two factors, the prediction signal of the spatial
`region is required to be generated at high speed. This is
`because the signal used for the generation of a prediction
`signal has to be decoded and reproduced.
`Therefore, the prediction signal of the spatial region is
`required to be generated in a simple manner, as well as, in
`high accuracy. Furthermore, a quickly operable construction
`is required in a coding apparatus and a decoding apparatus.
`The coding of image data has been widely used in many
`international standards such as JPEG, MPEG1, H.261,
`MPEG2 and H.263. Each of the latter standards has a more
`improved coding efficiency. That is, much effort has been
`devoted to further reducing the number of bits than in the
`conventional standards in expressing the same image quality.
`Coding of image data of moving images is comprised of
`intra-frame coding and prediction frame coding. In a repre
`sentative hybrid coding system such as MPEG1 Standard,
`consecutive frames can be classified into the following three
`different types:
`(a) intra-frame (referred to as an “I-frame' hereinafter);
`(b) prediction frame (referred to as a “P-frame hereinaf
`ter); and
`(c) bidirectional prediction frame (referred to as a
`“B-frame” hereinafter).
`An I-frame is coded independently of the other frames, i.e.,
`the I-frame is compressed without referring to the other
`frames. A P-frame is coded through motion detection and
`compensation by using the preceding frame for predicting the
`contents of a coded frame (it is a P-frame). A B-frame is coded
`through motion detection and compensation by using infor
`mation from the preceding frame and information from the
`Subsequent frame for predicting the data of the contents of the
`B-frame. The preceding frame and the Subsequent frames
`could be an I-frame or a P-frame. The I-frame is coded in
`intra-modes. The P-frame and the B-frame are coded in intra
`and prediction mode.
`As the characteristics of the coding of the I-frame, P-frame
`and B-frame are different from one another, the compressing
`methods thereof differ from one another. The I-frame uses no
`temporal prediction for the purpose of reducing the redun
`dancy, and therefore, it requires more bits than those of the
`P-frame and the B-frame.
`A description will be herein made taking MPEG2 as an
`example. It is assumed that the bit rate is 4 Mbits/sec and an
`image having 30frames/sec is used. In general, the ratio of the
`number of bits used for the I- P- and B-frames is 6:3:1.
`Therefore, the I-frame uses about 420 kbits/s, and the
`B-frame uses about 70 kbits/s. This is because the B-frame is
`sufficiently predicted from both directions.
`FIG. 14 is a block diagram showing a construction of a
`prior art image predictive coding apparatus. Since a DCT
`transform is executed on a block basis, the recent image
`coding methods are all based on the division of an image into
`Smallerblocks. According to the intra-frame coding, an input
`ted digital image signal is first of all Subjected to a block
`sampling process 1001 as shown in FIG. 14. Next, the blocks
`obtained after the block sampling process 1001 are subjected
`to a DCT transform process 1004 and thereafter subjected to
`a quantizing process 1005 and a run length Huffman variable
`length coding (VLC: Variable Length Coding; entropy cod
`ing) process 1006. On the other hand, according to the pre
`diction frame coding, an inputted digital image is Subjected to
`a motion compensating process 1003, and the motion-com
`pensated block (i.e., the predicted block) is subjected to the
`DCT transform process 1004. Next, the quantizing process
`
`US 7,995,654 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.29
`
`
`
`3
`1005 and the run length Huffman VLC coding (entropy cod
`ing) process 1006 are executed.
`The fact that the block-based DCT transform process 1004
`removes or reduces a spatial redundancy inside the target
`block to be processed and the fact that the motion detecting
`and compensating processes 1002 and 1003 remove or reduce
`a temporal redundancy between adjacent frames are known
`from the conventional image coding techniques. Further, the
`run length Huffman VLC coding or other entropy coding
`processes 1006 executed after the DCT transform process
`1004 and the quantizing process 1005 removes statistical
`redundancy between quantized DCT transform coefficients.
`However, the process is executed only on the blocks within an
`image.
`A digital image has a spatially great redundancy as an
`inherent characteristic. This redundancy exists not only in the
`blocks inside a frame but also between blocks over blocks.
`However, the fact that no actual method uses a process for
`removing the redundancy between blocks of an image is
`apparent from the above description.
`According to the existing image coding method, the DCT
`transform process 1004 or another transform process is
`executed on the block basis due to restrictive conditions in
`terms of hardware formation and calculation.
`Although the spatial redundancy is reduced through the
`block-based transform process, it is restricted to the inside of
`one block. The redundancy between adjacent two blocks is
`not satisfactorily considered. The redundancy, however, can
`be further reduced when the intra-frame coding which con
`sistently consumes a great number of bits.
`Furthermore, the fact that the block-based DCT transform
`process removes or reduces the spatial redundancy inside the
`target block to be processed and the fact that the motion
`predicting and compensating processes remove or reduce the
`temporal redundancy between adjacent two frames are
`known from the existing image coding techniques. A ZigZag.
`scan and the run length Huffman VLC coding or another
`entropy coding process, which are executed after the DCT
`transform process and the quantizing process, remove the
`statistical redundancy in quantized DCT transform coeffi
`cients, however, they are still restricted to the inside of one
`block.
`A digital image inherently includes a great spatial redun
`dancy. This redundancy exists not only inside a block but also
`between blocks over blocks of an image. There is no existing
`method uses the process for removing the redundancy
`between blocks of one image at all except for the DC coeffi
`cient prediction of JPEG, MPEG1 and MPEG2.
`According to MPEG1 and MPEG2, the DC coefficient
`prediction is executed by subtracting the DC value of the
`preceding coded block from the currently coded block. This is
`a simple predicting method which does not have an adaptive
`ness or mode Switching when the prediction is inappropriate.
`Further, it merely includes DC coefficients.
`According to the current state of the concerned technical
`field, the ZigZag scan is used for all blocks prior to the run
`length coding. No attempt at making scan adaptive on the
`basis of the data of the contents of the block has been made.
`FIG. 22 is a block diagram showing a construction of a
`prior art image predictive coding apparatus. In FIG. 22, the
`prior art image predictive coding apparatus is provided with a
`block sampling unit 2001, a DCT transform unit 2003, a
`quantizing unit 2004, a ZigZag scan unit 2005 and an entropy
`coding unit 2006. In this specification, the term “unit device
`a circuit device.
`According to the intra-frame coding (i.e., coding inside a
`frame), an inputted image signal is subjected to a block Sam
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,995,654 B2
`
`10
`
`15
`
`4
`pling process 2001 and thereafter subjected directly to a DCT
`transform process 2003. Then, a quantizing process 2004, a
`ZigZag scan process 2005 and an entropy coding process 2006
`are sequentially executed. On the other hand, according to the
`inter-frame coding (i.e., coding between frames, i.e., predic
`tion frame coding), a motion detecting and compensating
`process is executed in a unit 2011 after the block sampling
`process 2001, and then a prediction error is obtained from an
`adder 2002 by subtracting a detection value obtained from the
`unit 2011 from the image data obtained from the block sam
`pling 2001. Further, this prediction error is subjected to the
`DCT transform process 2003 and then to the quantizing pro
`cess 2004, ZigZag scan process 2005 and entropy coding
`process 2006 similar to the intra-frame coding.
`In a local decoder provided in the image predictive coding
`apparatus shown in FIG. 22, an inverse quantizing process
`and an inverse DCT transform process are executed in units
`2007 and 2008. According to the inter/frame coding, a pre
`diction value obtained through motion detection and compen
`sation is added by an adder 2009 to the prediction error
`reconstructed by the units 2007 and 2008, and the addition
`value device locally decoded image data. The decoded image
`data is stored into a frame memory 2010 of the local decoder.
`Finally, a bit stream is outputted from the entropy coding unit
`2010 and transmitted to the image predictive decoding appa
`ratus of the other party.
`FIG. 23 is a block diagram showing a construction of a
`prior art image predictive decoding apparatus. The bit stream
`is decoded by a variable length decoder (VLD: Variable
`Length Decoding) unit (or an entropy decoding unit) 2021,
`and the decoded image data is then Subjected to an inverse
`quantizing process and an inverse DCT transform process in
`units 2023 and 2024. According to the inter-frame coding, a
`prediction value which is obtained through motion detection
`and compensation and formed by a unit 2027 is added by an
`adder 2025 to the prediction error reconstructed, thereby
`forming locally decoded image data. The locally decoded
`image data is stored into a frame memory 1026 of the local
`decoder.
`According to the existing image coding techniques, the
`DCT transform process or other transform process is
`executed on the block basis due to the restrictive conditions in
`terms of hardware formation and calculation. The spatial
`redundancy will be reduced through the block-based trans
`form. However, it is restricted to the inside of a block. The
`redundancy between adjacent blocks is not satisfactorily con
`sidered. In particular, the intra-frame coding which consis
`tently consumes a great amount of bits is not satisfactorily
`considered.
`
`SUMMARY OF THE INVENTION
`
`A first object of the present invention is to provide an image
`predictive coding apparatus and method as well as image
`predictive decoding apparatus and method capable of simply
`generating prediction image data of the spatial region at high
`speed with high accuracy.
`A second object of the present invention is to provide an
`image predictive coding apparatus and method as well as
`image predictive decoding apparatus and method capable of
`removing the redundancy in a block further than in the prior
`art image predictive coding apparatus and image predictive
`decoding apparatus and more efficiently coding or decoding
`image data.
`Further, a third object of the present invention is to provide
`an image predictive coding apparatus and method as well as
`image predictive decoding apparatus and method capable of
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et. al.
`
`Ex. 1008, p.30
`
`
`
`US 7,995,654 B2
`
`5
`improving the efficiency of an entropy coding process by
`Solving the problem that important transform coefficients are
`concentrated on different regions of a block depending on the
`internal properties of image data and by determining the
`correct scan method for the block.
`Furthermore, a fourth object of the present invention is to
`provide a recording medium in which the steps of the image
`predictive coding method or the image predictive decoding
`method are recorded.
`According to the first aspect of the present invention, there
`is provided an image predictive coding apparatus comprising:
`dividing device operable to divide inputted image data to
`be coded into image data of a plurality of small regions which
`are adjacent to one another,
`first generating device operable, when code the image data
`of a target Small region to be processed among the image data
`of the plurality of small regions which are divided by the
`dividing device and adjacent to one another, to use image data
`of a reconstructed Small region adjacent to the image data of
`the target Small region to be processed as image data of an
`intra-frame prediction Small region of the target Small region
`to be processed, to use the image data of the intra-frame
`prediction Small region as image data of an optimum predic
`tion Small region and to generate image data of a difference
`Small region which are differences between the image data of
`the objective Small region to be processed and the image data
`of the optimum prediction Small region;
`coding device operable to code the image data of the dif
`ference Small region generated by the generating device;
`decoding device operable to decode the image data of the
`difference small region coded by the coding device; and
`second generating device operable to generate image data
`of a reproduced reproduction Small region by adding the
`image data of the difference small region decoded by the
`decoding device to the image data of the optimum prediction
`Small region.
`Also, according to the second aspect of the present inven
`tion, there is provided an image predictive coding apparatus
`comprising:
`dividing device operable to divide inputted image data to
`be coded into image data of a plurality of small regions which
`are adjacent to one another,
`first generating device operable, when coding an objective
`Small region to be processed among a plurality of Small
`regions which are divided by the dividing device and adjacent
`to one another, to use only significant image data indicated by
`an inputted significance signal representing whether or not
`the coded image data is significant as image data of an intra
`frame prediction Small region of the objective Small region to
`be processed among image data of a reproduced reproduction
`Small region adjacent to the image data of the objective Small
`region to be processed, to use the image data of the intra
`frame prediction Small region as image data of an optimum
`prediction Small region and to generate image data of a dif
`ference small region which are differences between the image
`data of the objective Small region to be processed and the
`image data of the optimum prediction Small region;
`coding device operable to code the image data of the dif
`ference Small region generated by the first generating device;
`decoding device operable to decode the image data of the
`difference Small region coded by the coding device; and
`second generating device operable to generate image data
`of a reproduced reproduction Small region by adding the
`image data of the difference small region decoded by the
`decoding device to the image data of the optimum prediction
`Small region.
`
`40
`
`45
`
`6
`Further, according to the third aspect of the present inven
`tion, there is provided an image predictive decoding appara
`tus comprising:
`analyzing device operable to analyze an inputted coded
`image data series and outputting an image difference signal;
`decoding device operable to decode image data of a repro
`duction difference Small region from the image difference
`signal outputted from the analyzing device;
`a line memory for storing therein image data for generating
`image data of a predetermined intra-frame prediction Small
`region;
`generating device operable to execute a prediction signal
`generating process on the image data from the line memory to
`thereby use reconstructed image data adjacent to the image
`data of the reproduction difference Small region as image data
`of an intra-frame prediction Small region and outputting the
`image data of the intra-frame prediction Small region as
`image data of an optimum prediction Small region; and
`adding device operable to add the image data of the repro
`duction difference Small region from the decoding device to
`the image data of the optimum prediction Small region from
`the generating device, outputting image data for generating
`image data of an intra-frame prediction Small region of the
`result of addition and storing th