(12) United States Patent
`Kimura et al.
`
`USOO6351569B1
`(10) Patent No.:
`US 6,351,569 B1
`(45) Date of Patent:
`Feb. 26, 2002
`
`(54) CODING METHOD, DECODING METHOD,
`CODING DEVICE AND DECODING DEVICE
`
`(*) Notice:
`
`(75) Inventors: Tomohiro Kimura; Masayuki
`Yoshida; Fumitaka Ono, all of Tokyo
`(JP)
`(73) Assignee: Mitsubishi Denki Kabushiki Kaisha,
`Tokyo (JP)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`(21) Appl. No.:
`09/155,166
`(22) PCT Filed:
`Jan. 14, 1998
`(86) PCT No.:
`PCT/JP98/00102
`S371 Date:
`Sep. 23, 1998
`S 102(e) Date: Sep. 23, 1998
`(87) PCT Pub. No.: WO98/33322
`PCT Pub. Date:Jul. 30, 1998
`Foreign Application Priority Data
`(30)
`Jan. 29, 1997 (JP) ............................................. 9-O15536
`(51) Int. Cl. .................................................. G06K 9/36
`(52) U.S. Cl. ........................................ 382/247; 382/233
`(58) Field of Search ................................. 382/238, 239,
`382/240, 241, 242, 243, 244, 245, 246,
`247, 248, 249; 348/415, 416, 417
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,191.974 A
`4,213,154 A
`
`3/1980 Ono et al.
`7/1980 Ono et al.
`
`4,542,411 A 9/1985 Imanaka et al.
`4,816,914 A
`3/1989 Ericsson ..................... 358/133
`4,849,810 A
`7/1989 Ericsson ..................... 358/133
`5,059.976 A 10/1991. Ono et al.
`5,297.220 A 3/1994 Nomizu
`5,307,062 A 4/1994 Ono et al.
`5,313.204 A 5/1994 Semasa et al.
`5,404,140 A 4/1995 Ono et al.
`5,828,411 A * 10/1998 Takizawa .................... 348/415
`5.960,116 A * 9/1999 Kajiwara .................... 382/238
`FOREIGN PATENT DOCUMENTS
`
`JP
`JP
`JP
`
`A638.048
`B2834433
`B22504316
`
`2/1994
`3/1996
`4/1996
`
`OTHER PUBLICATIONS
`Japanese abstract: JPA5–176171 Jul. 13, 1993.
`Japanese abstract: JPA4-122174 Apr. 22, 1992.
`Japanese abstract: JPA2–305225, Dec. 18, 1990.
`(List continued on next page.)
`Primary Examiner Phuoc Tran
`ASSistant Examiner Amir Alavi
`(57)
`ABSTRACT
`A prediction value is previously set in an MPS table corre
`sponding to a State number, a State number for an encoding
`pixel is obtained from a STATE table, the prediction value
`is determined based on the MPS table using the state
`number, a pixel-to-Symbol converter compares the predic
`tion value and the encoding pixel to obtain a Symbol, and an
`arithmetic encoder obtains an LPS interval from an LSZ
`table using the State number for the encoding pixel, and the
`arithmetic encoder implements encoding based on the Sym
`bol and the LPS interval.
`
`32 Claims, 56 Drawing Sheets
`
`
`
`
`
`VARTBL
`ST
`
`
`
`SYMBOL
`- - - - - OM ENC. SEC. - N - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`rty 7
`
`
`
`PIX-TO-SYM
`CONVERTER
`
`Unified Patents, Ex. 1006
`
`000001
`
`

`

`US 6,351,569 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Japanese
`JPA6-164940, Jun. 10, 1994.
`abstract:
`Japanese
`JPA62–108663, May 19, 1987.
`abstract:
`Japanese
`JPA57–147346, Sep. 11, 1982.
`abstract:
`Japanese
`JPA58-94274, Jun. 4, 1983.
`abstract:
`Japanese
`JPA57–147325, Sep. 11, 1982.
`abstract:
`Japanese
`JPA6–181523 Jun. 28, 1994.
`abstract:
`Japanese
`JP53–98718, Aug. 29, 1978.
`abstract:
`Japanese
`JP53–98719, Aug. 29, 1978.
`abstract:
`Japanese
`JP53–98720, Aug. 29, 1978.
`abstract:
`Japanese
`JPA61–65573, Apr. 4, 1986.
`abstract:
`Japanese
`JPA58-94275, Jun. 4, 1983.
`abstract:
`
`Japanese abstract: JPA59–30366, Feb. 17, 1984.
`Japanese abstract: JPA59–30367, Feb. 17, 1984.
`Japanese abstract: JPA5–191770, Jul. 30, 1993.
`Japanese abstract: JPA5–91459, Apr. 9, 1993.
`Japanese abstract: JPA5–91460, Apr. 9, 1993.
`Run Length Encoding Method According To Start Patterns
`of Prediction Transformation Signals, Ryoichi et al., General
`National Assembly of the Institute of Electronics and Com
`munication Engineers held in 1977 pp. 1-4.
`ITU-T Recommendation T81 (In Japanese and English).
`ITU-T Recommendation T.82 pp. 26-45.
`* cited by examiner
`
`Unified Patents, Ex. 1006
`
`000002
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 1 of 56
`
`US 6,351,569 B1
`
`Fig.1
`
`
`
`O - - -
`
`0 1 1 - - -
`
`0 1 0 1 - - -
`
`01.01 - - -
`
`00 - - -
`
`0001 - - -
`
`OOOO - - -
`
`OOOOO .
`
`. .
`
`Unified Patents, Ex. 1006
`
`000003
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 2 of 56
`
`US 6,351,569 B1
`
`Fig.2
`
`SWITCH
`
`REGISTER
`
`Ai-1
`
`
`
`S
`
`MPS/LPS
`
`
`
`
`
`SWITCH
`
`CALCULATOR
`
`Unified Patents, Ex. 1006
`
`000004
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 3 of 56
`
`US 6,351,569 B1
`
`Fig.3
`EIGIOO
`
`
`
`<DIJLEIWNH, LIXIV
`
`YHOECIOCON@H
`
`
`
`
`
`XO
`
`XANHOWN@HWN
`{{DVWI | Îoywi
`
`
`
`
`
`+ – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –(~~~~Oºs ON, WO -----|
`
`TO{{WN?S | YISILN?GIANOO
`
`W?S-OL-XId
`
`4.
`
`Unified Patents, Ex. 1006
`
`000005
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 4 of 56
`
`US 6,351,569 B1
`
`Fig.4
`GHCHOO
`
`
`
`
`
`YHOEI, LYHEIANOCO
`
`8
`
`
`
`r– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –(~~~Oºs Oad wo -----|
`
`XId-OL-W?S
`
`|
`
`| Zsi
`
`
`
`
`
`
`
`
`
`XO
`
`Unified Patents, Ex. 1006
`
`000006
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 5 of 56
`
`US 6,351,569 B1
`
`Fig.5
`
`
`
`sk : ENCODING/DECODING PIXEL
`
`(B) 3–LINE MODEL TEMPLATE
`
`Unified Patents, Ex. 1006
`
`000007
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 6 of 56
`
`US 6,351,569 B1
`
`Fig.6
`
`
`
`Unified Patents, Ex. 1006
`
`000008
`
`

`

`Unified Patents, Ex. 1006
`
`000009
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 8 of 56
`
`US 6,351,569 B1
`
`Fig.8
`
`ENCODER
`
`S101
`
`CALL INITENC
`
`READ PIX, CX
`CALL ENCODE
`
`FINISHED
`STRIPE 2
`
`|
`
`
`
`
`
`YES
`
`S105
`
`CALL FLUSH
`
`Unified Patents, Ex. 1006
`
`000010
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 9 of 56
`
`US 6,351,569 B1
`
`Fig.9
`
`ENCODE
`
`
`
`
`
`S113
`
`CALL CODELPS
`
`
`
`CALL CODEMPS
`
`Unified Patents, Ex. 1006
`
`000011
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 10 0f 56
`
`US 6,351,569 B1
`
`Fig.10
`
`A=A-LSZSTCX
`
`S121
`
`<ggsgists
`
`S122
`
`C-C-A
`A=LSZSTCX
`
`stic
`
`S125 NO
`
`MPSCX)=1-MPSCX -
`
`STCX)=NLPSSTCX) / S127
`CALL RENORME
`S128
`
`Unified Patents, Ex. 1006
`
`000012
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 11 of 56
`
`US 6,351,569 B1
`
`Fig.11
`
`C O DE MP S
`
`A=A-LSZSTCX
`
`S131
`
`S132
`
`
`
`-C-C-A
`A=LSZSTCX
`
`STCX=NMPSSTCX
`CALL RENORME
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000013
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 12 of 56
`
`US 6,351,569 B1
`
`Fig.12
`
`R E N OR ME
`
`
`
`S141
`S142
`S143
`
`o
`
`S144. No
`
`YES
`
`S146
`YES
`
`NO
`
`Unified Patents, Ex. 1006
`
`000014
`
`

`

`Unified Patents, Ex. 1006
`
`000015
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 14 of 56
`
`US 6,351,569 B1
`
`Fig.14
`
`
`
`
`
`
`
`
`
`INITENC
`
`S171
`
`
`
`FIRST STRIPE OF
`THIS LAYER OR
`FORCED RESET 2
`
`FOR ALL CX
`STCX)=0
`MPSCX)=0
`
`
`
`FOR ALL CX SET STCX)
`AND MPSCX) TO THEIR
`VALUES AT THE END OF
`THE PREVIOUS STRIPE OF
`THIS LAYER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SC=0
`A=0x10000
`C-0
`CT=11
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000016
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 15 of 56
`
`US 6,351,569 B1
`
`Fig.15
`
`FLUSH
`
`
`
`
`
`
`
`CALL CLEARBITS
`CALL FINALWRITES
`| REMOVE THE FIRST BYTE OF THE CODE
`| IF DESIRED, REMOVE ANY 0x00 BYTES AT
`THE END OF THE CODE
`
`S181
`S182
`S183
`S184
`
`Unified Patents, Ex. 1006
`
`000017
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 16 of 56
`
`US 6,351,569 B1
`
`Fig.16
`
`
`
`
`
`C L E A R B I. T. S
`
`S191.
`TEMP= (A-1+C)&0xff ff0000
`
`
`
`C-TEMP--OX8000
`
`EN ID
`
`Unified Patents, Ex. 1006
`
`000018
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 17 of 56
`
`US 6,351,569 B1
`
`Fig.17
`
`F N A LWR. I. T E S
`
`
`
`WRITE BUFFER-I-1
`WRITE OX()() SC TIMES
`
`S207
`WRITE BUFFER
`WRITE 0xff SC TIMES/ S208
`
`
`
`WRITE (CD) 19)&OXff
`WRITE (CD)11)&OXff
`
`Unified Patents, Ex. 1006
`
`000019
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 18 of 56
`
`US 6,351,569 B1
`
`Fig.18
`
`S211
`
`DECODER
`
`CALL INITDEC
`
`READ CX
`CALL DECODE
`
`FINISHED
`STRIPE 2
`
`YES
`
`END
`
`|
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000020
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 19 of 56
`
`US 6,351,569 B1
`
`Fig.19
`
`
`
`Unified Patents, Ex. 1006
`
`000021
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 20 0f 56
`
`US 6,351,569 B1
`
`Fig.20
`
`
`
`
`
`
`BONVHOXETSÆTI TTVO 8ZZSCIW HONTH TTVO | ZZS,
`
`-CIW HONGIH TTVO
`
`
`
`EIONVHOXE SCHWI
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`º CI O O CH CI
`
`TITVO
`
`Unified Patents, Ex. 1006
`
`000022
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 21 of 56
`
`US 6,351,569 B1
`
`Fig.21
`
`L P S EXCHANGE
`
`
`
`
`
`CHIGH-CHIGH-A
`A-LSZSTCX
`PIX=MPSSTCX
`STCX=NMPSSTCX)
`
`
`
`
`
`CHIGH-CHIGH-A
`A=LSZSTCX
`PIX=1-MPSSTCX
`
`
`
`STCX=NLPSSTCX
`
`Unified Patents, Ex. 1006
`
`000023
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 22 of 56
`
`US 6,351,569 B1
`
`Fig.22
`
`MP S EXCHANGE
`
`YES - girlf NO
`
`M
`PIX=1-MPSCX
`
`S252
`
`S256
`PIX-MPSCX
`STCX=NMPSSTCX) / S257
`
`stic
`
`S253 NO
`
`MPSCX=ll-MPSCX
`
`S255
`
`STCX=NLPSSTCX
`
`END
`
`Unified Patents, Ex. 1006
`
`000024
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 23 of 56
`
`US 6,351,569 B1
`
`Fig.23
`
`RE NORMD
`
`o
`
`S261 NO
`
`
`
`S263
`S264
`S265
`
`S266
`YES
`
`S267 No
`
`NO
`
`YES
`
`Unified Patents, Ex. 1006
`
`000025
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 24 of 56
`
`US 6,351,569 B1
`
`Fig.24
`
`
`
`S272
`
`HAS ALL DATA
`BEEN READ FROM
`SCD 2
`
`S275
`
`S271
`
`BUFFER=0
`
`
`
`READ ONE BYTE FROM SCD
`SET BUFFER EOUAL TO IT
`
`C=C+(BUFFERzz8)
`CT-8
`
`
`
`Unified Patents, Ex. 1006
`
`000026
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 25 of 56
`
`US 6,351,569 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig.25
`
`INITDEC
`
`
`
`S281
`
`FIRST STRIPE OF
`THIS LAYER OR
`FORCED RESET 2
`
`FOR ALL CX SET STCX)
`AND MPSCX) TO THEIR
`VALUES AT THE END OF
`THE PREVIOUS STRIPE OF
`THIS LAYER
`
`
`
`FOR ALL CX
`STCX)=0
`MPSCX)=0
`
`
`
`
`
`
`
`
`
`
`
`
`
`CALL BYTEIN
`C=C-C8
`CALL BYTEIN
`C=C-C-C8
`CALL BYTEIN
`
`S285
`86
`S2
`S287
`S288
`
`Unified Patents, Ex. 1006
`
`000027
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 26 of 56
`
`US 6,351,569 B1
`
`Fig.26
`
`
`
`Unified Patents, Ex. 1006
`
`000028
`
`

`

`Unified Patents, Ex. 1006
`
`000029
`
`

`

`U.S. Patent
`
`US 6,351,569 B1
`
`------TIO{{WXS
`YHOEHLYHEIANOO
`
`"I W KS-OL-XII
`
`I
`
`1- TAL'SNOO -
`
`
`
`XO
`
`
`
`r- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(~~~oºs DNA wo -----!
`
`L
`
`Unified Patents, Ex. 1006
`
`000030
`
`

`

`U.S. Patent
`
`US 6,351,569 B1
`
`
`
`
`
`| Zsi |
`
`
`
`“IVA CI/01
`
`| |
`
`Unified Patents, Ex. 1006
`
`000031
`
`

`

`U.S. Patent
`
`
`
`Feb. 26, 2002
`
`Sheet 30 of 56
`
`US 6,351,569 B1
`
`Unified Patents, Ex. 1006
`
`000032
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 31 of 56
`
`US 6,351,569 B1
`
`Fig.31
`
`ENCODER
`
`S301
`
`ST=STATECX)
`
`
`
`
`
`
`
`S113
`
`CALL CODELPS
`
`
`
`CALL CODEMPS
`
`Unified Patents, Ex. 1006
`
`000033
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 32 of 56
`
`US 6,351,569 B1
`
`Fig.32
`
`COD E L PS
`
`A-A-LSZST
`
`S3
`
`siggs is
`
`S312
`
`C-C-A
`A=LSZST
`
`STATELCX)=NLPSST /S314
`CALL RENORME
`S128
`
`Unified Patents, Ex. 1006
`
`000034
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 33 of 56
`
`US 6,351,569 B1
`
`Fig.33
`
`COD EMP S
`
`A-A-LSZST
`
`S321
`
`S132
`
`YES
`
`
`
`
`
`
`
`C-C-A
`A-LSZST
`
`STATELCX=NMPSLST)
`CALL RENORME
`
`
`
`Unified Patents, Ex. 1006
`
`000035
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 34 of 56
`
`US 6,351,569 B1
`
`Fig.34
`
`INITENC
`
`
`
`S171
`
`FIRST STRIPE OF
`THIS LAYER OR
`FORCED RESET 2
`
`FOR ALL CX
`STATECX)=0
`
`FOR ALL CX SET STATECX)
`TO TS VALUE AT THE END
`OF THE PREVIOUS STRIPE
`OF THIS LAYER
`
`
`
`
`
`SC=0
`A=0x10000
`C=O
`CT=11
`
`S175
`S176
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000036
`
`

`

`U.S. Patent
`
`US 6,351,569 B1
`
`
`
`GH CI NI
`
`
`
`
`
`QH CIO O GH CI
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000037
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 36 of 56
`
`US 6,351,569 B1
`
`Fig.36
`
`L P S EXCHANGE
`
`
`
`
`
`
`
`CHIGHECHIGH-A
`A-LSZST
`PIX-MPSLST)
`STATECX=NMPSIST
`
`
`
`
`
`
`
`CHIGHFCHIGH-A
`A=LSZST
`PIX-LPSLST)
`STATECX)=NLPSST
`
`S236
`S355
`S356
`S357
`
`Unified Patents, Ex. 1006
`
`000038
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 37 of 56
`
`US 6,351,569 B1
`
`Fig.37
`
`MP S EXCHANGE
`
`PIX-LPSST
`STATECX=NLPSST
`
`
`
`
`
`PIX-MPSIST
`STATELCX=NMPSST
`
`S364
`S365
`
`Unified Patents, Ex. 1006
`
`000039
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 38 of 56
`
`US 6,351,569 B1
`
`Fig.38
`
`
`
`
`
`
`
`RE NORMID
`
`
`
`CALL BYTEIN
`
`s
`
`S266
`
`NO
`
`Unified Patents, Ex. 1006
`
`000040
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 39 of 56
`
`US 6,351,569 B1
`
`Fig.39
`
`INITENC
`
`
`
`S281
`
`FIRST STRIPE OF
`THIS LAYER OR
`FORCED RESET
`
`FOR ALL CX
`STATECX=0
`
`FOR ALL CX SET STATECX)
`TO TS VALUE AT THE END
`OF THE PREVIOUS STRIPE OF
`THIS LAYER
`
`
`
`
`
`
`
`
`
`CALL BYTEIN
`C-CC <8
`CALL BYTEIN
`C=CCC8
`CALL BYTEIN
`A=0x10000
`
`S285
`S 2 8 6
`
`S287
`S288
`S289
`
`
`
`
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000041
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`Sheet 40 of 56
`Fig. 40
`
`
`
`US 6,351,569 B1
`
`Unified Patents, Ex. 1006
`
`000042
`
`

`

`Unified Patents, Ex. 1006
`
`000043
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 42 of 56
`
`US 6,351,569 B1
`
`Fig. 43
`
`-1
`
`Fig. 44
`
`
`
`Unified Patents, Ex. 1006
`
`000044
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 43 of 56
`
`US 6,351,569 B1
`
`Fig.45
`
`
`
`Unified Patents, Ex. 1006
`
`000045
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 44 of 56
`
`US 6,351,569 B1
`
`Fig. 47
`
`Fig. 48
`
`
`
`Unified Patents, Ex. 1006
`
`000046
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 45 of 56
`
`US 6,351,569 B1
`
`Fig. 49
`
`cx
`
`47
`
`sTATE
`
`
`
`
`
`8bit
`
`Unified Patents, Ex. 1006
`
`000047
`
`

`

`Unified Patents, Ex. 1006
`
`000048
`
`

`

`Sheet 47 of 56
`
`US 6,351,569 B1
`
`Feb. 26, 2002
`Fig.
`51
`LSZ NLPSINMPS MPS I LPS LST LSZIN
`LPSNMPS MPS LPS
`
`U.S. Patent
`
`ST
`
`
`
`
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000049
`
`

`

`U.S. Patent
`
`
`
`
`
`Feb. 26, 2002
`Sheet 48 of 56
`Fig.52
`
`47
`
`US 6,351,569 B1
`
`Fig.53
`
`CX
`
`()
`
`1
`
`2
`
`1023
`
`8bit
`
`STATE
`
`()
`
`129->142
`
`8bit
`
`Unified Patents, Ex. 1006
`
`000050
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 49 of 56
`
`US 6,351,569 B1
`
`Fig.54
`
`47
`
`STATE
`
`14 2->143
`
`
`
`
`
`
`
`1023
`
`
`
`o
`-N-1
`8bit
`
`Fig.55
`
`1()
`
`11
`
`47
`
`MPS
`
`STATE
`
`() x 128-- 0 ->
`
`1X 128-- 1
`
`- > 129
`
`1 x 128-14 - > 142
`
`1 x 128--15 - > 143
`
`Unified Patents, Ex. 1006
`
`000051
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 50 of 56
`
`US 6,351,569 B1
`
`Fig.56
`
`
`
`Unified Patents, Ex. 1006
`
`000052
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 51 of 56
`
`US 6,351,569 B1
`
`57
`
`
`
`
`
`
`
`(OILVH NOILO?IJACI HOLAAS) OILVH SATI
`NO
`
`XI? HO ‘ONU” SÆTI HO "ON=
`
`Fig
`
`€)----¬----------------
`
`TIIVIGHCI O NICHOONEI
`
`
`
`{{ZIS SHOVWI
`
`
`
`
`
`NOIJLOEILGICI HOJLAAS HO "ON
`
`
`
`/~TIVA "CI?TNIA HO ISHQANI HO ‘ON=
`
`
`
`
`"TVA "CIGH}{d (HO OILVYH NOISYHOEIANI
`
`
`
`
`
`Unified Patents, Ex. 1006
`
`000053
`
`

`

`Unified Patents, Ex. 1006
`
`000054
`
`

`

`Unified Patents, Ex. 1006
`
`000055
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 54 of 56
`
`US 6,351,569 B1
`
`Fig.60
`
`
`
`Unified Patents, Ex. 1006
`
`000056
`
`

`

`U.S. Patent
`
`US 6,351,569 B1
`
`
`
`XO
`
`TO8IVNXS | ?IGI LYIJANOO
`
`
`
`-W XS-O. L-XHA
`
`
`
`r- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(~~~oºs DNA wo -----|
`
`4.
`
`ÅRHOVNGIVN
`{{DVWI | Îoywi
`
`6
`
`Unified Patents, Ex. 1006
`
`000057
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 56 of 56
`
`US 6,351,569 B1
`
`Fig.62
`
`
`
`COI LOEIWNHILIYHV
`
`YHOEHCIOC){{CI
`
`
`
`|
`
`L -TAL'SNOO --
`zsi
`
`|
`
`Unified Patents, Ex. 1006
`
`000058
`
`

`

`US 6,351,569 B1
`
`1
`CODING METHOD, DECODING METHOD,
`CODING DEVICE AND DECODING DEVICE
`
`This application is the national phase under 35 U.S.C.
`$371 of prior PCT International Application No. PCT/JP98/
`00102 which has an International filing date of Jan. 14, 1998
`which designated the United States of America, the entire
`contents of which are hereby incorporated by reference.
`
`5
`
`TECHNICAL FIELD
`The present invention relates to implementation of encod
`ing and decoding image data.
`
`2
`precision is kept under a virtual decimal point by Virtually
`resetting a decimal point. In obtaining an actual codeword,
`the above Set of fixed values can be always used.
`Here, by approximating ra to S, each of the above
`expressions becomes each of the following:
`when the symbol value a is “0”,
`
`and
`when the symbol value a is “1”,
`
`The range (interval) A resulted from the previous
`Symbol, essentially becomes Smaller as mapping is continu
`ously repeated, thus, S should accordingly be reduced. This
`reduction can be performed by shifting operation into one
`n-th (n is power of 2). However, the reduction of S causes
`to increase a number of 0 aligning in the high order bits of
`S, which does not directly effect to the operation. On the
`contrary to the above operation, by multiplying A by
`power of 2 and by keeping A more than a minimum value
`(1/2), it is possible that S having the fixed value is used. The
`foregoing process is called renormalization.
`In the following explanation, a symbol is called MPS
`(more probable symbol: symbol having higher probability of
`occurrence) when the symbol a is “0”, and a symbol is
`called LPS (less probable symbol: symbol having lower
`probability of occurrence) when the symbol a, is “1”.
`Namely, a prediction conversion is previously performed
`and MPS showing a higher probability of occurrence or LPS
`showing a lower probability of occurrence is assigned to
`each Symbol. And when the Symbol a is “1”, the range
`
`becomes a range (interval) of the less probable symbol.
`FIG. 2 is a block diagram showing an example of an
`encoder of a conventional encoding apparatus. In the figure,
`reference numeral 1 shows a register for temporarily Storing
`a value of range (interval) assigned to the previous Symbol.
`Reference numeral 2 shows a Subtracter, 3 shows a Switch of
`range (interval), 4 shows a Switch of coordinates, 5 shows a
`Shifter for determining a Shifting amount for
`renormalization, and 6 shows a calculator for calculating
`encoded output.
`Next, an operation of the apparatus will be described
`referring to the figure.
`S (within a range (interval) of LPS), which is previously
`Selected from the states of Markov information Source based
`on the table specifying a plurality of values at a prediction
`estimator (not shown in the figure), is entered to the Sub
`tracter 2. The Subtracter 2 obtains and outputs a difference
`(A -S) from the range (interval) A for the previous
`Symbol Stored in the register 1.
`The Switch 3 receives the range (interval) (A -S)
`assigned to MPS and the range (interval) Sassigned to LPS,
`and the Switch 3 Switches the range according to whether the
`symbol is MPS or LPS. Namely, when the symbol is MPS,
`the range (interval) A assigned to the Symbol is determined
`and output as
`
`and when the Symbol is LPS, the range (interval) A assigned
`to the Symbol is determined and output as
`
`15
`
`BACKGROUND ART
`A number line encoding method (arithmetic encoding
`method) is also known as encoding method for Markov
`information Source, where a Symbol Sequence is mapped
`between 0.0 and 1.0 on the number line, and its coordinate
`is encoded into a codeword indicated by, for example, binary
`notation.
`FIG. 1 is a conceptual drawing of the above method. For
`simplifying an explanation, binary symbols “1” and “0” are
`Supplied at random out of a memoryleSS State, which is
`independent of past occurrence States. In this case, an
`occurrence probability of symbol “1” is defined as r and an
`occurrence probability of symbol “0” is expressed as 1-r. A
`range for the symbol “1” is placed at the bottom of the
`figure. The length of an output Sequence of memoryleSS
`source is assumed to be three, and coordinates for C(000)
`through C(111) shown in the right rows are respectively
`expressed by binary numbers. These binary numbers are cut
`off at digit, where the number can be identified, and the
`binary numbers are defined as respective codewords. By
`defining as above, the codewords can be decoded at a
`receiving Side by operating a proceSS Similar to a transmit
`ting Side.
`In the above case, a mapping range A for mapping on the
`number line of the Symbol Sequence at the i-th point,
`minimum coordinates C. of the mapping range A. are as
`follows where an initial value of the mapping range is
`A=1.0 and the minimum coordinates Co=0.0:
`when an occurring Symbol value at is “0”,
`Aji=(1-r)A 1
`
`25
`
`35
`
`40
`
`45
`
`C=C +PA ;
`
`and
`when the symbol value at is “1”,
`
`A=PA 1
`
`C=C
`As described in “An overview of the basic principles of
`the Q-coder Adaptive binary arithmetic coder” (IBMJournal
`of Research & Development Vol. 32 No. 6, November,
`1988), in order to reduce a number of operations Such as a
`multiplication with large operational load, instead of calcu
`lating rail, a set of fixed values S may be provided as a
`table. Encoding and decoding with finite precision is imple
`mented by Selecting a value corresponding to Markov Status
`out of the table.
`Accordingly, as mapping is continuously repeated, the
`range (interval) A becomes Smaller, renormalization is
`performed (e.g., A is multiplied by power of 2 to keep the
`value A more than a predefined value), and an operational
`
`50
`
`55
`
`60
`
`65
`
`Unified Patents, Ex. 1006
`
`000059
`
`

`

`US 6,351,569 B1
`
`3
`
`4
`interval by 16 bits. 13 denotes a next MPS state table (NMPS
`table) specifying a next state for MPS transition by 7 bits. 14
`denotes a next LPS state table (NLPS table) specifying a
`next state for LPS transition by 7 bits. 15 denotes a predic
`tion Switching table (SWTCH table) showing inversion of
`the prediction value of the MPS table 10 by one bit. 16
`denotes a pixel-to-Symbol converter inputting a prediction
`value of the MPS table 10 and a pixel PIX supplied from the
`image memory 9 and outputting a symbol. 17 and 18 denote
`update processors updating the values of the MPS table 10
`and the ST table 11. 19 denotes an arithmetic encoder.
`In this case, the above MPS table 10 and the ST table 11
`are variable tables. The above LSZ table 12, the NMPS table
`13, the NLPS table 14, and the SWTCH table 15 are constant
`tables (probability estimation tables). In the following, an
`operation of the encoding apparatus will be explained refer
`ring to FIG. 3.
`In FIG. 3, a QM encoding section 7 receives two inputs,
`one of which is a context and the other is an encoding pixel.
`The QM encoding section 7 outputs a code.
`The image memory 9 Stores an image and generates a
`context (10 bits, a total of 1024 patterns=2'), which is a
`reference pattern of 10 adjacent pixels, already encoded or
`decoded, indicated by Model Template for an encoding
`pixel. The image memory 9 also outputs the encoding pixel
`at the time of encoding. The QM-Coder is provided with
`2-line and 3-line Standard model templates for generating a
`context as shown in FIG. 5.
`In the QM-Coder, a prediction matching probability of
`pixel value is estimated for each context of each encoding
`pixel, and encoding is performed by learning the change of
`the prediction matching probability of pixel value. Learning
`is implemented by rewriting values of two variable tables
`having indexes of contexts as shown in FIGS. 40 and 41
`(namely, the MPS table 10 indicating a prediction value by
`one bit corresponding to the context, and the ST table 11
`indicating a State by Seven bits corresponding to the
`context).
`The QM-Coder includes a constant table (probability
`estimation table) for referring State number (state) on encod
`ing as an index as well as the variable tables. FIG. 42 shows
`values set in the constant table. A prefix such as “Ox’ of
`“0x08000” indicates hexadecimal number. In FIG. 42, the
`LSZ table 12 shows a size of LPS interval by LSZ value of
`16 bits, the NMPS table 13 shows a next state for MPS
`transition by NMPS value of seven bits, the NLPS table 14
`shows a next state for LPS transition by NLPS value of
`Seven bits, and an SWTCH table 15 shows an inversion of
`prediction value by SWTCH value of one bit. (These names
`expressed by capital alphabet letters for variable and con
`Stant tables will be used as array names in processing flow
`explained below.)
`The size of LPS interval of the LSZ table 12 is referred to
`by a calculator, which is not shown in the figure, of the
`arithmetic encoder 19 and is not directly related to learning
`of adaptive prediction. In the arithmetic encoder 19, a
`calculation is operated using the LSZ, and when an opera
`tion precision is reduced, the operation is renormalized.
`When the renormalization occurs, learning is performed at
`the same time.
`If the encoding symbol is MPS when renormalization
`occurs, the NMPS value of the NMPS table 13 is written in
`the ST table 11. If the encoding symbol is LPS, the NLPS
`value of the NLPS table 14 is written in the ST table 11 (this
`operation means the State corresponding to the context is
`rewritten). The State is thus moved. On encoding, the
`pixel-to-symbol converter 16 outputs the symbol to the
`arithmetic encoder 19 and the update processors 17 and 18.
`
`The Switch 4 selects one of the range (interval) S for LPS
`and a fixed value 0 according to whether received Symbol is
`MPS or LPS and outputs the selected value as AC, difference
`coordinates between the range (interval) assigned to the
`previous Symbol and the minimum coordinates C.
`Namely, when the received symbol is MPS placed in the
`high order bit, the difference coordinates AC is output as
`
`when the received symbol is LPS placed in the low order bit,
`the difference coordinates AC is output as
`
`The output A of the Switch 3 is supplied to the register 1
`and to the shifter 5.
`The range (interval) A assigned to the symbola, is stored
`in the register 1 and the range (interval) for a next symbol
`is calculated based on the data of A. The shifter 5 compares
`the range (interval) A with /2. When the range (interval) A
`is smaller than /2, the shifter 5 doubles the range (interval)
`A and compares the doubled result of the range (interval) A
`with /2 again. The shifter 5 repeats this doubling of the range
`(interval) A until the doubled result of the range (interval)
`A is greater than /2. The number 1 of the above doublings
`is obtained and output to the register 1 and the calculator 6
`as a shifting amount 1. Then, the calculator 6 calculates a
`codeword using the outputs Supplied from the Switch 4 and
`the shifter 5 and outputs the codeword. The calculator 6
`Stores difference coordinates accumulated from the past.
`Namely, this accumulated value equals to the minimum
`coordinates C.
`of the range (interval) assigned to the
`previous symbol. The input difference coordinates AC is
`added to the minimum coordinates C.
`of the previous
`Symbol to obtain the minimum coordinates C. of the range
`(interval) assigned to the present symbol. The minimum
`coordinates C, is shifted by the shifting amount 1 (bits).
`Then, it is checked whether one of the high order bits of the
`maximum coordinates within the effective range matches to
`any of the high order bits of the shifted minimum coordi
`nates C. If there exists a bit matched, the matched bit is
`determined and output as determined bit of coordinates, in
`other words, a codeword.
`Next, the general arithmetic encoder and the general
`arithmetic decoder will be explained in detail.
`The encoder and decoder using arithmetic encoding and
`decoding can be embodied using the table and the proceSS
`ing flow described in the International Standard Recommen
`dation T82 of ITU-T (International Telecommunication
`Union). In the following explanation, the arithmetic encoder
`is referred to as a OM-Coder, the encoder is as a OM
`encoding Section 7, and the decoder is as a QM decoding
`section 8. FIGS. 3 and 4 show general configurations of the
`encoder and the decoder. On the contrary to FIG. 1, in the
`QM-Coder, the range for LPS (symbol “1”) on the number
`line is placed in the upper part of the figure.
`In FIG. 3, a reference numeral 9 shows an image memory
`for Storing an input image and a reference numeral 10 shows
`a prediction value table (MPS table) storing a pixel value
`MPS (More Probable Symbol), which has a high probability
`of occurrence, as a prediction value of one bit. A reference
`numeral 11 shows a state table (ST table) storing a state
`number (0-112) of 7bits. This state number is for classifying
`the State of matching probability of the prediction value into
`a total of 113 states. A reference numeral 12 shows an LPS
`interval size table (LSZ table) specifying a size of an LPS
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Unified Patents, Ex. 1006
`
`000060
`
`

`

`S
`If the renormalization is due to the LPS, and when the
`prediction matching probability is less than around /2, the
`MPS value is inverted (operation “1-MPS) and the inverted
`value is written in the MPS table 10. Whether the prediction
`matching probability is less than /2 or not can be determined
`by the SWTCH value of the SWTCH table 15 as a flag.
`Namely, the SWTCH value of the SWTCH table 15 is set
`to “1” for the state where the prediction matching probabil
`ity is less than around /2 and the SWTCH value of the
`SWTCH table 15 other than the above case is set to “0”. By
`setting like above, the SWTCH value of the SWTCH table
`15 can indicate the prediction value as an inversion flag.
`As has been described, the ST table 11 and the MPS table
`10 should be updated and controlled, respectively. As shown
`in FIG. 3, the update processors 17 and 18 determine the
`updating values for the ST table 11 and the MPS table 10,
`respectively. The update processors 17 and 18 also respec
`tively rewrite the values of the tables with the above values.
`The updating proceSS has been thus performed.
`FIG. 6 shows a state transition diagram in the QM-Coder
`operated based on the table shown in FIG. 42 (since the
`number of the States is too large as 113 to show in the figure,
`only a part of the state transition is described). Each block
`shows one State and has a State number (a parenthesized
`number is hexadecimal notation) inside of the block. An
`arrow with “MPS” shows a state transition due to MPS (and
`accompanied with renormalization). An arrow with “LPS”
`shows a state transition due to LPS. Next states for the state
`transitions due to MPS and LPS are shown in the NMPS
`table 13 and the NLPS table 14, respectively. LPS state
`transition shown by underlined LPS means LPS state tran
`Sition accompanied by inversion of the prediction value,
`which is indicated in the SWTCH table 15 as the SWTCH
`value “1”.
`An example of the State transition will be explained. On
`Starting the encoding process, values are initialized for all
`contexts as “state=0, prediction value=0”, as shown in FIGS.
`43 and 44. To simplify the explanation, it is assumed that
`context CX for a plurality of Sequential pixels continuously
`takes the same value (e.g., CX=1). A State number and a
`prediction value for the context CX can be obtained as
`STCX) and as MPSCX) by referring to the variable table.
`When LPS occurs as a first symbol, the state STCX) is
`moved to 1 from 0. The next state for the LPS state transition
`is shown as:
`NLPSISTICXI(=0)=1
`and the value of STCX) of the ST table 11 is updated to:
`STCX)=1
`as shown in FIG. 45. At this time, the prediction value is
`Simultaneously updated Since:
`SWTCHISTICXI(=0)=1
`(this is also shown in the figure as underlined “LPS”).
`Namely, MPS CX) of the MPS table 10 becomes 1
`(inversion value) from 0 as shown in FIG. 46. When a
`second symbol occurs as LPS, the next state for the state
`transition is:
`NLPSISTICXI(=1)=14
`and the value of STCX) of the ST table 11 is updated as:
`STCX)=14
`as shown in FIG. 47. At this time, since:
`SWTCHISTICXI(=1)=0,
`the prediction value of the MPS table 10 does not need to be
`inverted. If a third symbol occurs as MPS, the state is moved
`to a neXt State only when the renormalization occurs. For
`explanation of the operation, it is assumed the State is
`moved, the next State is:
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,351,569 B1
`
`1O
`
`15
`
`25
`
`6
`NMPSISTICXI(=14)=15
`and the value of STCX) of the ST table 11 is updated to:
`STCX)=15
`as shown in FIG. 48.
`The state transition explained hereinbefore is indicated by
`***** in the figure. The state transition will be the same on
`decoding process.
`Before explaining an encoding processing flow, bit
`assignments of an encoding register 20 and an interval size
`register 21 included in the arithmetic encoder 19 are shown
`in FIG. 7.
`In the encoding register 20, a decimal point is placed
`between 15' bit and 16" bit, “x” (16 bits) shows a calcu
`lation part (Cx22) for the LSZ table 12. If the calculation
`results in carry-over, the bits of “X” is propagated to the high
`order bit. “s” (3 bits) shows a spacer bit part (Cs23), “b” (8
`bits) shows a bite output part (Cb24), and “c” (1 bit) shows
`a carry detector (CC25). In the encoding process, the value
`of the encoding register 20 is updated to the l