(12) United States Patent
`Román et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,016,417 B1
`Mar. 21, 2006
`
`USOO7016417B1
`
`(54) GENERAL PURPOSE COMPRESSION FOR
`VIDEO IMAGES (RHN)
`
`(75) Inventors: Kendyl A. Román, 730 Bantry Ct.,
`Sunnyvale, CA (US) 94087-3402;
`Cyrus J. Hoomani, San Francisco, CA
`(US); Richard S. Neale, Sunnyvale, CA
`(US)
`
`(73) Assignee: Kendyl A. Roman, Sunnyvale, CA
`(US)
`s
`s
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`p issisted under 35
`a --
`y UdayS.
`(21) Appl. No.: 09/470,566
`1-1.
`(22) Filed:
`
`Dec. 22, 1999
`Related U.S. Application Data
`(60) Provisional application No. 60/113,276, filed on Dec.
`23, 1998.
`
`4,704,628 A 11/1987 Chen et al. ................. 358/136
`4,743,959 A 5/1988 Frederiksen
`5,014,710 A 5/1991 Maslak et al.
`5,047,853 A * 9/1991 Hoffert et al. ......... 375/240.01
`5,287.452 A 2/1994 Newman .................... 34.5/520
`5,309.232 A 5/1994 Hartung et al.
`5,416,602 A 5/1995 Inga et al.
`5,471.989 A 12/1995 Roundhill et al. ..... 128/660.04
`5,552,832 A
`9/1996 Astle
`5,581,613 A * 12/1996 Nagashima et al. ........ 380/201
`5,583,561. A 12/1996 Baker et al. .................. 725/93
`5,621,660 A 4/1997 Chaddha et al.
`5. A 3.C. With tal
`5,721,815 A
`2/1998 Ottesen et al. .............. 345/721
`5,754.820 A
`5/1998 Yamagami .................. 711/133
`5,812,119 A 9/1998 Tateyama
`5,812,788 A
`9/1998 Agarwal
`5,897,498 A 4/1999 Canfield, II et al. ........ 600/437
`5.959,639 A 9/1999 Wada ......................... 34.5/542
`Continued
`Ontinue
`(
`)
`FOREIGN PATENT DOCUMENTS
`
`OOC e a
`
`2
`
`as 2
`
`(56)
`
`(51) Int. Cl
`(2006.01)
`H04N 7/12
`(52) U.S. Cl. ................................................. 375/240.23
`(58) Field of Classification Search ............... 348/207,
`348/143,211,212,400, 407,384,413,385,
`348/415; 382/245, 232, 246,250, 239, 242;
`375/240.01, 240.16, 240,240.23
`See application file for complete Search history.
`References Cited
`U.S. PATENT DOCUMENTS
`4,301,469 A 11/1981 Modeen et al. ............... 358/75
`4,302.775. A 11/1981 Widergren et al. ......... 358/136
`4,385,363 A 5/1983 Widergren et al. ......... 364/725
`4,394,774 A 7/1983 Widergren et al. ........... 382/56
`4.410,916 A 10/1983 Pratt et al. .................. 358/263
`4,546,385 A 10/1985 Anastassiou.
`4.550,437 A 10/1985 Kobayashi et al. ......... 34.5/536
`4,646,356 A 2/1987 Anderson et al. ............. 382/56
`4,698,672 A 10/1987 Chen et al. ................. 358/136
`
`11/1999
`
`WO 99/59472
`WO
`Primary Examiner-Vu Le
`Assistant Examiner-Behrooz Senfi
`(57)
`ABSTRACT
`
`Methods, medium, and machines which compress, encode,
`enhance, transmit, decompress and display digital video
`images in real time. Real time compression is achieved by
`Sub-Sampling each frame of a Video signal, encoding and
`filtering the pixel values to codes, and run-length encoding
`the codes. Real time transmission is achieved due to high
`levels of effective compression. Real time decompression is
`achieved by decoding and decompressing the encoded data
`to display high quality images. High levels of effective
`compression also reduce the Storage Space requirement for
`recorded video.
`
`22 Claims, 19 Drawing Sheets
`
`202
`
`284
`
`206
`
`Receive pixelatafor
`Currett Pixed
`
`Cbtaia Line Nibef
`corresponding to Pixel Data
`
`
`
`Instacart, Ex. 1034
`
`1
`
`

`

`US 7,016,417 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5.999,655 A 12/1999 Kalker et al. ............... 382/234
`6,018,713 A
`1/2000 Coliet al. .................... 705/2
`6,025,854 A 2/2000 Hinz et al. .................. 34.5/538
`6,054,990 A 4/2000 Tran
`6,063,032 A
`5/2000 Grundwald
`6,064,324. A 5/2000 Shimizu et al.
`6,078,691 A
`6/2000 Luttmer ...................... 382/235
`6,091,777. A * 7/2000 Guetz et al. ......... 375/240.11
`6,115,485 A 9/2000 Dumoulin et al.
`6,144,392 A 11/2000 Rogers ....................... 34.5/537
`6,181,711 B1
`1/2001 Zhang et al. ............... 370/468
`
`4/2001 Pinder et al.
`6.219.358 B1
`11/2001 Zhou et al. ................... 710/26
`6,324,599 B1
`1/2002 Chen et al. ................. 382/261
`6,335,990 B1
`1/2002 Anderson et al. ............. 710/22
`6,338,119 B1
`6,339,616 B1* 1/2002 Kovalev ........
`375/240.16
`6,384.862 B1* 5/2002 Brusewitz et al. .......... 348/212
`6,571,392 B1
`5/2003 Zigmond et al. ........... 725/110
`6,592,629 B1
`7/2003 Cullen et al. ...
`709/232
`6,651,113 B1
`11/2003 Grimsrud ..................... 710/22
`2001/0021260 A1* 9/2001 Chung et al. ............... 382/100
`
`
`
`* cited by examiner
`
`2
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 1 of 19
`
`US 7,016,417 B1
`
`110
`Sub-sample
`Image
`
`120
`
`130
`Run-Length
`Encode
`
`
`
`
`
`
`
`Image
`Reconstitution
`
`140
`
`3
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21, 2006
`
`Sheet 2 of 19
`Sheet 2 of 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`
`
`208
`
`206
`
`204
`
`202
`
`
`
`Fig 2A [AimeJRed]Green]Bre]
`
`216
`
`214
`
`*
`
`200
`
`212
`
`4
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 3 of 19
`
`US 7,016,417 B1
`
`f 300
`
`unsigned char encode Table (
`
`) = {
`
`? 370
`
`?
`
`360
`
`7,
`
`3,
`
`0,
`0,
`0,
`0,
`0,
`1
`1,
`1,
`1,
`1,
`1
`1,
`1,
`2,
`2,
`2,
`2,
`2,
`2,
`2,
`2,
`3,
`3,
`3,
`3,
`3,
`3,
`3,
`3,
`4,
`4,
`4,
`4,
`4,
`4,
`4,
`4,
`5 ,
`5,
`5 ,
`5,
`5 ,
`5,
`5 ,
`5,
`6,
`6,
`6,
`6,
`6,
`6,
`6,
`6,
`7,
`7,
`7,
`7,
`7,
`7,
`7
`7,
`8,
`8,
`8,
`8,
`8,
`8,
`8,
`8,
`9,
`9,
`9,
`9,
`9,
`9,
`9,
`9,
`10, 10, 10, 10, 10, 10, 10, 10,
`11, 11, 11, 11, 11, 11, 11, 11, 11,
`12, 12, 12, 12, 12, 12, 12, 12
`13, 13, 13, 13, 13, 13, 13, 13,
`14, 14, 14, 14, 14, 14, 14, 14,
`15, 15, 15, 15, 15, 15, 15, 15, 15,
`16, 16, 16, 16, 16, 16, 16, 16,
`17, 17, 17, 17, 17, 17, 17, 17,
`18, 18, 18, 18, 18, 18, 18, 18,
`19, 19, 19, 19, 19, 19, 19, 19, 19,
`20, 20, 20, 20, 20, 20, 20, 20,
`21, 21, 21, 21, 2l 21, 21, 21,
`22, 22, 22, 22 22, 22, 22, 22,
`23, 23, 23, 23, 23, 23, 23, 23, 23,
`24, 24, 24, 24, 24, 24, 24, 24,
`25, 25, 25, 25, 25, 25, 25, 25,
`26, 26, 26, 26, 26, 26, 26, 26,
`27, 27, 27, 27, 27, 27, 27, 27, 27,
`28, 28, 28, 28, 28, 28, 28, 28,
`29, 29, 29, 29, 29, 29, 29, 29,
`30, 30, 30, 30, 30, 30, 30, 30,
`31, 31, 31, 31
`
`O
`A -->
`O -
`A/
`8
`2 -->
`5 -
`A /
`M/ 13 - 20 -> 16
`A / 2 - 29 -> 24
`// 30 - 37 -> 33
`A / 38 - 4 5 -> 41
`// 46 - 53 -> 49
`// 54 - 62 -> 57
`// 63 - 70 -> 66
`?/ 71 - 78 -> 74
`f / 79 - 86 -> 82
`// 87 - 95 -> 90
`A / 96 - O3 -> 99
`A / 1 O4 - 111 -> 1 O7
`// 11.2 - 119 -> 115
`// 120 - 128 -> 123
`?/ 129 - 13 6 --> 132
`A / 1.37 - 144 -> 14 O
`A / 1 4 5 - 152 -> 1. 48
`A / 53 - 161 -> 56
`// 162 - 169 -> 1.65
`W/ 17 O - 177 -> 173
`A / 178 - 185 -> 181
`// 186 - 194 -> 189
`f / 195 - 202 -> 198
`?/ 203 - 21 O -> 2O6
`// 211 - 218 -> 214
`// 219 - 227 -> 222
`A / 228 - 235 -> 231
`// 236 - 243 -> 239
`// 24 4 - 251 -> 2.47
`// 252 - 255 -> 255
`
`310
`
`320
`
`5
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 4 of 19
`
`US 7,016,417 B1
`
`350
`w
`
`
`
`37O 330
`v
`v
`O
`1
`2
`3
`4
`5
`6
`7
`8
`9
`
`Fig 3B
`
`6
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 5 of 19
`
`US 7,016,417 B1
`
`Fig. 4A
`
`P=0xFF (prior)
`C=0 (repeat count)
`L=0 (encoded length)
`Done=False
`
`428
`
`422
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Get eight-bit value V
`from pixel
`
`Use valueV to index
`into encode table to
`retrieve the five-bit
`encoded value E
`
`
`
`AL=0x80
`L=L-1
`AL=P
`L-L-1
`C=C-128
`
`
`
`AL=C& 0x80
`L=L-1
`AL=P
`
`C=1
`PEE
`
`
`
`
`
`
`
`(End of Data)
`| (End of Data
`&& Done)
`
`No
`
`418
`
`Done=True
`
`7
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21, 2006
`
`Sheet 6 of 19
`Sheet 6 of 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`
`
`
`
`Fig. 4B
`Fig 4B
`
`8
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 7 of 19
`
`US 7,016,417 B1
`
`510
`
`|
`
`|
`
`M 500
`
`|
`|
`|
`Fig 5A
`
`|
`
`|
`
`510
`
`M 520
`
`530
`
`|
`
`
`
`con
`Fig 5B
`
`M 550
`
`9
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 8 of 19
`
`US 7,016,417 B1
`
`610
`
`(1,1,1,1,1)
`
`N-N-1
`
`O
`65
`
`65
`2
`
`--S N
`looloolooxxolololoo
`653 oxxololoo
`
`N-- N--
`651
`
`654
`
`
`
`10
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 9 of 19
`
`US 7,016,417 B1
`
`int decode Table (
`) = {
`? 710
`
`Oxff Kg 24
`Oxff << 24
`Oxff K ( 24
`Oxff << 24
`Oxff K< 24
`Oxff << 24
`Oxff (< 24
`0xff << 24
`Oxff << 24
`Oxff (< 24
`Oxff << 24
`Oxff << 24
`0xff << 24
`Oxff (< 24
`Oxff << 24
`Oxff << 24
`Oxff << 24
`0xff << 24
`Oxff << 24
`Oxff << 24
`Oxff (< 24
`Oxff << 24
`0xff << 24
`Oxff << 24
`Oxff << 24
`Oxff << 24
`Oxff K< 24
`Oxff KC 24
`Oxff << 24
`Oxff << 24
`Oxff << 24
`Oxff << 24
`
`700
`
`?
`? 720
`
`O << 16
`8 << 16
`16 K-4 16
`24 << 16
`33 << 16
`41 << 16
`49 << 16
`57 << 16
`66 << 16
`74 << 16
`82 << 16
`90 << 16
`99 << 16
`107 << 16
`115 << 16
`123 << 16
`132 << 16
`140 << 16
`148 << 16
`156 << 16
`165 << 16
`173 << 16
`181 << 16
`189 << 16
`198 << 16
`206 << 16
`214 << 16
`222 << 16
`231 << 16
`239 << 16
`247 << 16
`255 << 16
`
`730 ? 740
`
`0,
`O << 8
`8,
`8 << 8
`16,
`16 K ( 8
`24,
`24 << 8
`33
`33 << 8
`41,
`41 << 8
`49,
`49 << 8
`57
`57 << 8
`66,
`66 << 8
`74,
`74 << 8
`82,
`82 << 8
`90,
`90 << 8
`99,
`99 << 8
`107,
`107 << 8
`115,
`115 KC 8
`123,
`123 << 8
`132,
`132 << 8
`140,
`140 Kg 8
`148,
`148 << 8
`156,
`156 << 8
`165,
`165 (< 8
`173,
`173 << 8
`181,
`181 << 8
`189,
`189 << 8
`198,
`198 << 8
`206,
`206 << 8
`214,
`214 << 8
`222,
`222 << 8
`231,
`231 << 8
`239,
`239 << 8
`247 KC 8 - 247,
`255 << 8
`255
`
`11
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21,2006
`
`Sheet 10 of 19
`Sheet 10 of 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`810
`
`812 814 816 818 - 820
`
`822
`
`824
`
`- 800
`
`
`
`
`
`
`
`840
`
`1
`
`- 830
`
`880
`
`Fig 8
`
`12
`
`12
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 11 of 19
`
`US 7,016,417 B1
`
`Fig 9
`
`
`
`
`
`
`
`900
`
`( sun Y
`
`C=1 (repeat counter)
`L (encoded length)
`I=0 (index)
`
`Use X to index into
`decode table to obtain
`pixel value V
`
`914
`
`
`
`<> I --
`
`Yes
`
`Place V in next
`location of image
`C = C - 1
`
`910
`
`13
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21, 2006
`
`Sheet 12 of 19
`Sheet 12 of 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`1000
`1000
`M
`K
`
`
`
`0 1 2 3 4 5 6 7 8 9 1
`
`O
`1
`2
`3.
`4.
`5
`6
`7
`8
`9
`
`4
`
`14
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 13 of 19
`
`US 7,016,417 B1
`
`unsigned char encode Table
`
`=
`
`Y 1010
`
`5,
`
`24, 24, 24, 24, 24,
`18, 18, 18, 18, 18, 18, 18, 18,
`25, 25, 25, 25, 25, 25, 25, 25,
`5,
`5,
`5,
`5,
`5 ,
`5,
`5,
`5,
`3,
`3,
`3,
`3,
`3,
`3,
`3,
`3,
`6,
`6,
`6,
`6,
`6,
`6,
`6,
`6,
`12, 12, 12, 12, 12, 12, 12, 12,
`30, 30, 30, 30, 30, 30, 30, 30, 30,
`21, 21, 21, 21, 21, 21, 21, 21,
`27, 27, 27, 27, 27, 27, 27, 27,
`1,
`l,
`1,
`l
`l
`1,
`l,
`1,
`16, 16, 16, 16, 16, 16, 16, 16, 16,
`31, 31, 31, 31, 31, 31, 31, 31,
`4,
`4,
`4,
`4,
`4,
`4,
`4,
`4,
`14, 14, 14, 14, 14, 14, 14, 14,
`20, 20, 20, 20, 20, 20, 20, 20, 20,
`10, 10, 10, 10, 10, 10, 10, 10,
`28, 28, 28, 28, 28, 28, 28, 28,
`23, 23, 23, 23, 23, 23, 23, 23,
`9,
`9,
`9,
`9,
`9,
`9,
`9,
`9,
`15, 15, 15, 15, 15, 15, 15, 15,
`22, 22, 22, 22, 22, 22, 22, 22,
`29, 29, 29, 29, 29, 29, 29, 29,
`13, 13, 13, 13, 13, 13, 13, 13, 13,
`19, 19, 19, 19, 19, 19, 19, 19,
`26, 26, 26, 26, 26, 26, 26, 26,
`2,
`2,
`2,
`2,
`2,
`2,
`2,
`2,
`17, 17, 17, 17, 17, 17, 17, 17, 17,
`0,
`0,
`0,
`0,
`0,
`0,
`0,
`0,
`8,
`8,
`8,
`8,
`8,
`8,
`8,
`8,
`11, 11, 11, 11, 11, 11, 11, 11,
`7,
`7,
`7,
`7
`
`9,
`
`Fig 10B
`
`O
`4 ->
`O -
`//
`8
`5 - 12 ->
`//
`// 13 - 20 -> 16
`// 21 - 29 -> 24
`// 30 - 37 --> 33
`// 38 - 4 5 -> 41
`A /
`A 6 - 53 -> 49
`// 54 - 62 -> 57
`W/ 63 - 70 -> 66
`// 71 - 78 -> 74
`A / T9 - 86 -> 82
`A / 87 - 95 -> 90
`// 96 - 103 -> 99
`A / 104 - 11 -> 1.07
`// 11.2 - 119 - > 115
`// 120 - 128 -> 123
`A / 129 - 136 -> 132
`A / .37 - 144 -> 14 O
`// 145 - 152 --> 148
`A / 153 - 161 --> 156
`// 162 - 169 -> 1.65
`A / 170 - 177 -> 173
`f / 178 - 85 -> 181
`// 86 - 194 -> 189
`// 195 - 2 O2 -> 198
`// 2O3 - 21 O -> 2O6
`A / 211 - 218 -> 214
`A / 219 - 227 -> 222
`A / 228 - 235 -> 231
`// 236 - 243 -> 239
`// 24 4 - 251 -> 2.47
`// 252 - 255 -> 255
`
`15
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 14 of 19
`
`US 7,016,417 B1
`
`int decode Table (
`
`)
`
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`Oxff
`
`{K
`<<
`<<
`<<
`<<
`{{
`CK
`{K
`gk.
`
`KK
`{{
`<<
`<<
`{{
`<<
`Kk
`g<
`
`{K
`kC
`<<
`<<
`<<
`{{
`CC
`Kg
`<<
`{K
`KK
`<<
`<<
`<<
`<<
`
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`24
`
`231
`82
`214
`33
`107
`24
`41
`255
`239
`15 6
`132
`247
`49
`189
`115
`1.65
`9 O
`222
`
`198
`123
`66
`17 3
`148
`
`16
`2O6
`74
`1 4 0
`181
`57
`99
`
`CK
`<<
`<<
`<<
`<<
`C C
`KK
`k<
`<<
`KC
`<<
`<<
`<<
`KK
`KC
`<<
`<g
`KC
`CC
`KC
`<<
`<<
`<<
`CC
`KC
`KC
`K43
`CK
`<<
`<<
`<<
`CC
`
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`16
`
`255
`239
`156
`132
`247
`49
`189
`115
`165
`90
`222
`
`198
`123
`66
`|
`| 173
`148
`
`231,
`82,
`214,
`33,
`107,
`24,
`41,
`255,
`239,
`156,
`132,
`247,
`49,
`189,
`115,
`165,
`90,
`222,
`
`198,
`123,
`66,
`173,
`148,
`
`16,
`206,
`74,
`140,
`181,
`57,
`99
`
`};
`
`16
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 15 of 19
`
`US 7,016,417 B1
`
`Video Source 101
`
`Transmitter
`1 103
`
`
`
`Recorded Video
`1104
`
`
`
`
`
`
`
`
`
`Computer Network
`1105
`
`
`
`
`
`Receiver
`1 106
`
`
`
`
`
`
`
`Receiver
`1106
`
`Receiver
`1106
`
`Fig 11
`
`17
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 16 of 19
`
`US 7,016,417 B1
`
`
`
`O2 12
`
`1204
`
`206
`
`Receive Pixel Data for
`Current Pixel
`
`Obtain Line Number
`Corresponding to Pixel Data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`208
`
`No
`
`1210
`
`
`
`
`
`Is Repeat
`Counter Equal
`to O
`
`
`
`No
`
`1214
`
`Transmit Current
`Line Number
`
`1220
`N
`O
`
`1222
`
`Transmit Repeat
`
`1224
`
`is line number
`same as previous
`line number
`
`Yes
`Increment Repeat
`Counter
`
`Is Repeat
`Counter Equal
`to O2
`
`Yes
`Transmit Repeat
`Counter Value
`
`O
`
`1216
`
`Additional
`Pixels
`
`No
`Is Repeat
`Counter Equal
`to O
`
`
`
`1218
`
`No
`
`
`
`
`
`
`
`Y e S au
`End
`
`1228
`
`226
`
`Transmit Repeat
`Counter Walue
`
`Fig 12
`
`18
`
`

`

`(i. f
`1320Ga . |E1330e
`l V
`4i'1i
`
`
`414'itt'1
`
`ti
`
`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21,2006
`
`Sheet 17 of 19
`Sheet 17 0f 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`1310
`1310
`
`1320
`
`1322
`
`1326
`
`1328
`
`1330
`
`1332
`
`'!ii
`ai
`
`
`
`w
`
`f
`
`y
`
`1351
`
`1353
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Mar. 21, 2006
`
`Sheet 18 of 19
`
`US 7,016,417 B1
`
`1400
`
`1402
`
`1404
`
`1406
`
`Yes
`
`Receive Next
`Data Structure
`
`Read Identification Bit
`of Data Structure
`
`No
`
`1st Bit a “O'” )
`
`Read Last Seven
`Bits for Count
`
`1412
`
`1414
`
`Read Last Five Bits
`For Line Number
`
`1408
`
`1410
`
`Form Pixel
`Illumination Intensity
`
`Form Pixel
`Illumination Intensity
`
`
`
`
`
`Yes
`
`1416
`
`1418
`
`
`
`Next Data
`Structure ?
`
`NO
`End
`
`Fig 14
`
`20
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 21, 2006
`Mar. 21, 2006
`
`Sheet 19 of 19
`Sheet 19 of 19
`
`US 7,016,417 B1
`US 7,016,417 B1
`
`1500
`1500
`
`s
`
`1506
`1506
`
`1508
`1508
`
`1510
`1510
`
`1512
`1512
`
`1514
`1514
`
`s f us
`is‘
`
`w
`
`
`
`
`
`f
`
`
`
`1502
`1502
`
`1504
`
`s |
`
`V
`V
`V
`V
`
`i!!i‘é'!!yii't4i‘‘‘H o
`
`1556*1558|1560E1562on
`l1552B1554
`eeeEee,
`S-N-1
`
`1550
`1550
`
`Fig 15
`Fig 15
`
`21
`
`21
`
`

`

`1
`GENERAL PURPOSE COMPRESSION FOR
`VIDEO IMAGES (RHN)
`
`US 7,016,417 B1
`
`2
`a rate of 30 frames per Second. This frame rate is considered
`full motion. A television Screen has a 4:3 aspect ratio.
`When an analog video signal is digitized, each of the 480
`lines is Sampled 640 times and each Sample is represented by
`a number. Each Sample point is called a picture element, or
`pixel. A two dimensional array is created that is 640 pixels
`wide and 480 pixels high. This 640x480 pixel array is a still
`graphical image that is considered to be full frame. The
`human eye can perceive 16.7 thousand colors. A pixel value
`comprised of 24 bits can represent each perceivable color. A
`graphical image made up of 24-bit pixels is considered to be
`full color. A Single Second-long full frame, full color Video
`requires over 220 millions bits of data.
`The transmission of 640x480 pixelsx24 bits per pixel
`times 30 frames requires the transmission of 221,184,000
`millions bits per Second. A T1 Internet connection can
`transfer up to 1.54 millions bits per second. A high speed (56
`Kb) modem can transfer data at a maximum rate of 56
`thousand bits per second. The transfer of full motion, full
`frame, full color digital video over a T1 Internet connection,
`or 56 Kb modem, will require an effective data compression
`of over 144:1, or 3949:1, respectively.
`
`BASIC RUN-LENGTHENCODING
`
`An early technique for data compression is run-length
`encoding where a repeated Series of items are replaced with
`one sample item and a count for the number of times the
`Sample repeats. Prior art ShowS run-length encoding of both
`individual bits and bytes. These simple approaches by
`themselves have failed to achieve the necessary compression
`ratioS.
`
`VARIABLE LENGTHENCODING
`
`In the late 1940s, Claude Shannon at Bell Labs and R. M.
`Fano at MIT pioneered the field of data compression. Their
`work resulted in a technique of using variable length codes
`where codes with low probabilities have more bits, and
`codes with higher probabilities have fewer bits. This
`approach requires multiple passes through the data to deter
`mine code probability and then to encode the data. This
`approach also has failed to achieve the necessary compres
`Sion ratioS.
`D. A. Huffman disclosed a more efficient approach of
`variable length encoding known as Huffman coding in a
`paper entitled “A Method for Construction of Minimum
`Redundancy Codes,” published in 1952. This approach also
`has failed to achieve the necessary compression ratioS.
`
`ARITHMETIC, FINITE CONTEXT, AND
`ADAPTIVE CODING
`
`In the 1980s, arithmetic, finite coding, and adaptive
`coding have provided a slight improvement over the earlier
`methods. These approaches require extensive computer pro
`cessing and have failed to achieve the necessary compres
`Sion ratioS.
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims priority under 35 U.S.C. S119(e)
`of the now abandoned U.S. provisional application Ser. No.
`60/113,276 filed on 1998 Dec. 23, and entitled “METHOD
`OF IMAGES ENHANCEMENT, COMPRESSION, AND
`ENCODING of GRAYSCALE IMAGES (ECHOCODEC)
`.” The provisional application Ser. No. 60/113,276 filed on
`1998 Dec. 23 and entitled “METHOD OF IMAGE
`ENHANCEMENT,COMPRESSION, AND ENCODING of
`GRAYSCALE IMAGES (ECHOCODEC)” is also hereby
`incorporated by reference.
`This application also claims priority under 35 U.S.C.
`$119(e) of our co-pending U.S. patent application Ser. No.
`09/312,922 filed on 1999 May 17, and entitled “SYSTEM
`FORTRANSMITTING VIDEO IMAGES OVER A COM
`PUTER NETWORK TO AREMOTE RECEIVER,” which
`describes an embodiment of the invention of this application
`in combination with our now abandoned U.S. provisional
`application Ser. No. 60/085,818 filed on 1998 May 18, and
`entitled “APPARATUS FOR TRANSMITTING LIVE
`VIDEO IMAGES OVER A COMPUTER NETWORK TO
`MULTIPLE REMOTE RECEIVERS.” U.S. patent applica
`tion Ser. No. 09/312,922 filed on 1999 May 17, and entitled
`“SYSTEM FOR TRANSMITTING VIDEO IMAGES
`OVER A COMPUTER NETWORK TO A REMOTE
`RECEIVER'' is also hereby incorporated by reference.
`
`15
`
`25
`
`BACKGROUND
`
`1. Field of the Invention
`This invention relates to data compression, Specifically to
`the compression and decompression of Video images.
`2. Description of Prior Art
`In the last few years, there have been tremendous
`advances in the Speed of computer processors and in the
`availability of bandwidth of worldwide computer networks
`Such as the Internet. These advances have led to a point
`where businesses and households now commonly have both
`the computing power and network connectivity necessary to
`have point-to-point digital communications of audio, rich
`graphical images, and Video. However the transmission of
`Video signals with the full resolution and quality of televi
`Sion is still out of reach. In order to achieve an acceptable
`level of Video quality, the Video Signal must be compressed
`Significantly without losing either spatial or temporal qual
`ity.
`A number of different approaches have been taken but
`each has resulted in less than acceptable results. These
`approaches and their disadvantages are disclosed by Mark
`Nelson in a book entitled The Data Compression Book,
`Second Edition, published by M & T Book in 1996. Mark
`Morrision also discusses the state of the art in a book entitled
`The Magic of Image Processing, published by Sams Pub
`lishing in 1993.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`DICTIONARYBASED COMPRESSION
`
`VIDEO SIGNALS
`
`Standard Video signals are analog in nature. In the United
`States, television signals contain 525 scan lines of which 480
`lines are visible on most televisions. The Video signal
`represents a continuous Stream of Still images, also known as
`frames, that are fully Scanned, transmitted and displayed at
`
`65
`
`Dictionary-based compression uses a completely different
`method to compress data. Variable length Strings of Symbols
`are encoded as Single tokens. The tokens form an indeX to a
`dictionary. In 1977, Abraham Lempel and Jacob Ziv pub
`lished a paper entitled. “A Universal Algorithm for Sequen
`tial Data Compression” in IEEE Transactions on Informa
`
`22
`
`

`

`US 7,016,417 B1
`
`4
`the previous or Subsequent identical block is encoded.
`MPEG suffers from the same blocking and smearing prob
`lems as JPEG.
`These approaches require extensive computer processing
`and have failed to achieve the necessary compression ratioS
`without unacceptable loSS of image quality and artificially
`induced distortion.
`
`5
`
`3
`tion Theory, which disclosed a compression technique
`commonly known as LZ77. The same authors published a
`1978 sequel entitled, “Compression of Individual Sequences
`via Variable-Rate Coding,” which disclosed a compression
`technique commonly known as LZ78 (see U.S. Pat. No.
`4,464,650). Terry Welch published an article entitled, “A
`Technique for High-Performance Data Compression,” in the
`June 1984 issue of IEEE Computer, which disclosed an
`algorithm commonly known as LZW, which is the basis for
`the GIF algorithm (see U.S. Pat. Nos. 4,558,302, 4,814,746,
`and 4,876,541). In 1989, Stack Electronics implemented a
`LZ77 based method called QIC-122 (see U.S. Pat. No.
`5.532,694, U.S. Pat. No. 5,506.580, and U.S. Pat. No.
`5,463,390). The output of a QIC-122 encoder consists of a
`Stream of data, which, in turn consists of tokens and Symbols
`freely intermixed. Each token or symbol is prefixed by a
`Single bit flag that indicates whether the following is a
`dictionary reference or a plain symbol. The definitions for
`these two Sequences are:
`(a) plaintext <1><eight-bit-symbold
`(b) dictionary reference: <0><window-offsetd-phrase
`length>
`Windows offsets are encoded as seven bits or eleven bits.
`These lossless (method where no data is lost) compression
`methods can achieve up to 10:1 compression ratioS on
`graphic images typical of a video image. While these
`dictionary-based algorithms are popular, these approaches
`require extensive computer processing and have failed to
`achieve the necessary compression ratios.
`
`15
`
`25
`
`JPEG AND MPEG
`
`Graphical images have an advantage over conventional
`computer data files: they can be slightly modified during the
`compression/decompression cycle without affecting the per
`ceived quality on the part of the viewer. By allowing Some
`loSS of data, compression ratios of 25:1 have been achieved
`without major degradation of the perceived image. The Joint
`Photographic Experts Group (JPEG) has developed a stan
`dard for graphical image compression. The JPEG lossy
`(method where Some data is lost) compression algorithm
`first divides the color image into three color planes and
`divides each plane into 8 by 8 blocks, and then the algorithm
`operates in three Successive Stages:
`(a) A mathematical transformation known as Discrete
`Cosine Transform (DCT) takes a set of points from the
`Spatial domain and transforms them into an identical
`representation in the frequency domain.
`(b) A lossy quantization is performed using a quantization
`matrix to reduce the precision of the coefficients.
`(c) The Zero values are encoded in a zig-zag sequence (See
`Nelson, pp. 341-342).
`JPEG can be Scaled to perform higher compression ratio
`by allowing more loSS in the quantization Stage of the
`compression. However this loSS results in certain blocks of
`the image being compressed Such that areas of the image
`have a blocky appearance and the edges of the 8 by 8 blockS
`become apparent because they no longer match the colors of
`their adjacent blocks. Another disadvantage of JPEG is
`Smearing. The true edges in an image get blurred due to the
`lossy compression method.
`The Moving Pictures Expert Group (MPEG) uses a com
`bination of JPEG based techniques combined with forward
`and reverse temporal differencing. MPEG compares adja
`cent frames and for those blocks that are identical to those
`in a previous or Subsequent frame and only a description of
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`QUICKTIME: CINEPAK, SORENSEN, H.263
`
`Apple Computer, Inc. released a component architecture
`for digital Video compression and decompression, named
`QuickTime. Any number of methods can be encoded into a
`QuickTime compressor/decompressor (codec). Some popu
`lar codes are CinePak, Sorensen, and H.263. CinePak and
`Sorensen both require extensive computer processing to
`prepare a digital Video Sequence for playback in real time;
`neither can be used for live compression. H.263 compresses
`in real time but does So by Sacrificing image quality resulting
`in Severe blocking and Smearing.
`
`FRACTAL AND WAVELET COMPRESSION
`
`Extremely high compression ratioS are achievable with
`fractal and wavelet compression algorithms. These
`approaches require extensive computer processing and gen
`erally cannot be completed in real time.
`
`SUMMARY OF THE INVENTION
`
`In accordance with the present invention a method of
`compression of a Video stream comprises steps of Sub
`Sampling a Video frame, determining a code for each pixel,
`run-length encoding the codes whereby the method can be
`executed in real time and the compressed representation of
`codes Saves Substantial Space on a Storage medium and
`require Substantially less time and bandwidth to be trans
`ported over a communication link. The present invention
`includes a corresponding method for decompressing the
`encoded data.
`
`OBJECTS AND ADVANTAGES
`
`Accordingly, beside the objects and advantages of the
`method described in our patent above, Some additional
`objects and advantages of the present invention are:
`(a) to provide a method of compressing and decompress
`ing video Signals So that the Video information can be
`transported across a digital communications channel in
`real time.
`(b) to provide a method of compressing and decompress
`ing Video signals. Such that compression can be accom
`plished with Software on commercially available com
`puters without the need for additional hardware for
`either compression or decompression.
`(c) to provide a high quality Video image without the
`blocking and Smearing defects associated with prior art
`lossy methods.
`(d) to provide a high quality video image that Suitable for
`use in medical applications.
`(e) to provide Some level of encryption So that images are
`not directly viewable from the data as contained in the
`transmission.
`(f) to provide a method of compression of Video signals
`Such that the compressed representation of the Video
`Signals is Substantially reduced in size for Storage on a
`Storage medium.
`
`23
`
`

`

`S
`(g) to enhance electronically generated images by filtering
`highs and lowS.
`
`US 7,016,417 B1
`
`6
`
`-continued
`
`DRAWING FIGURES
`
`In the drawings, closely related figures have the same
`number but different alphabetic suffixes.
`FIG. 1 shows the high level steps of compression and
`decompression of an image.
`FIGS. 2A to 2H show alternatives for selecting a pixel
`value for encoding.
`FIG. 3A shows the encode table of the preferred embodi
`ment.
`FIG. 3B shows a chart of values corresponding to the
`Sample encode table
`FIG. 4A shows a flowchart for the preferred embodiment
`of the compression method.
`FIG. 4B shows an image and a corresponding Stream of
`pixels.
`FIGS. 5A to 5C shows the formats for the run-length
`encoding.
`FIG. 6 shows a series of codes and the resulting encoded
`Stream.
`FIG. 7 shows a sample decode table.
`FIG. 8 shows an alternate method of selecting a five bit
`code.
`FIG. 9 shows the flow chart for the preferred embodiment
`of the decompression method.
`FIGS. 10A to 10C show an encryption key, an encryption
`table and a decryption table.
`FIG. 11 illustrates a block diagram of a network for video
`transmission.
`FIG. 12 illustrates a flow chart showing the steps involved
`in the compression proceSS within a compressor of an
`alternate embodiment.
`FIG. 13 illustrates a Sample data Stream representing
`Video pixels and a corresponding compressed data Stream.
`FIG. 14 illustrates a flow chart showing the steps involved
`during the decompression process of an alternate embodi
`ment.
`FIG. 15 illustrates an uncompressed data Stream, a cor
`responding compressed data Stream, and a corresponding
`converted data Stream of an alternate embodiment.
`
`Reference Numerals in Drawings
`100 compression steps
`110 sub-sampling step
`120 code lookup step
`130 run-length encoding step
`140 encoded data
`150 decompression steps
`160 run-length expansion step
`170 value lookup step
`180 image reconstitution step
`200 32 bit pixel value
`202 blue channel
`204 green channel
`206 red channel
`208 alpha channel
`210 24 bit pixel value
`212 blue component
`214 green component
`216 red component
`220 RGB averaging diagram
`222 blue value
`224 green value
`226 red value
`228 averaged value
`230 blue selection diagram
`232 blue instance
`234 green instance
`236 red instance
`240 selected blue value
`250 green selection diagram
`260 selected green value
`270 red selection diagram
`280 selected red value
`290 grayscale pixel
`292 grayscale blue
`294 grayscale green
`296 grayscale red
`298 selected grayscale value
`299 8 bit pixel value
`300 encode table
`310 codes
`330 minimum values
`360 stepped values
`
`320 line comments
`340 maximum values
`350 chart of values
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Reference Numerals in Drawings
`370 line numbers
`400 encode flowchart
`402 encode entry
`403 encode initialization step
`404 get pixel step
`405 get value step
`406 lookup encoded value step
`408 compare previous
`410 increment counter step
`412 check count overflow
`414 new code step
`416 check end of data
`418 set done
`420 counter overflow step
`422 check done
`428 encode exit
`430 image
`440 image width
`450 image height
`460 pixel stream
`500 code byte
`510 flag bit
`520 repeat code
`530 count
`550 data code
`565 data bit 6
`570 data bit 5
`575 data bit 4
`580 data bit 3
`585 data bit 2
`590 data bit 1
`595 data bit O
`610 decimal values
`620 first value
`622 second value
`624 third value
`626 fourth value
`628 fifth value
`630 sixth value
`632 seventh value
`640 binary code
`650 first byte
`651 repeat count
`652 second byte
`653 first code
`654 third byte
`655 second code
`656 fourth byte
`657 third code
`700 decode table
`710 alpha values
`720 red values
`730 green values
`740 blue values
`800 8 bit pixel
`810 pixel bit 7
`812 pixel bit 6
`814 pixel bit 5
`816 pixel bit 4
`818 pixel bit 3
`820 pixel bit 2
`822 pixel bit 1
`824 pixel bit 0
`830 5 bit sample
`832 sample bit 4
`834 sample bit 3
`836 sample bit 2
`838 sample bit 1
`840 sample bit 0
`850 ignored bits
`860 decompressed pixel
`880 3 low order bits
`900 decode entry
`901 decode initialize step
`902 get code step
`906 determine type
`908 decode lookup step
`909 check Zero count
`910 place pixel step
`912 assign counter step
`914 reset counter step
`916 check length
`918 decode exit
`1000 encryption key
`1010 encryption table
`1020 decryption table
`
`TERMINOLOGY CORRELATION
`
`Different terminology was used in the Specification of
`application Ser. No. 09/312,922, portions of which are now
`included in this specification. The two specifications were
`written by two different authors who described distinct
`embodiments of the subject invention with two distinct sets
`of terminology. The following table provides a partial cor
`relation between the two sets of terminology. Note that this
`correlation of terms does not necessarily mean the term are
`equivalent. This high level correlation is provided to aid in
`understanding Similarities and differences between the two
`Specifications. Also note that t