USOO6614845B1
`
`
`
`
`
`
`
`
`US 6,614,845 B1
`(10) Patent N0.:
`(12) Unlted States Patent
`
`
`
`
`
`
`Azadegan
`*Sep. 2, 2003
`(45) Date of Patent:
`
`
`
`
`
`
`
`
`
`
`
`(54) METHOD AND APPARATUS FOR
`DIFFERENTIAL MACROBLOCK CODING
`
`
`
`FOR INTRA-FRAME DATA IN VIDEO
`
`
`
`
`CONFERENCING SYSTEMS
`
`
`
`(75)
`
`
`
`
`
`
`
`
`Inventor: Faramarz Azadegan, San Diego, CA
`
`(US)
`
`
`
`
`
`
`(73) Assignee: Verizon Laboratories Inc., Waltham,
`
`MA (US)
`
`
`
`
`(*) Notice:
`
`
`
`
`
`
`
`
`
`This patent issued on a continued pros-
`
`
`
`
`
`ecution application filed under 37 CFR
`
`
`
`
`
`
`1.53(d), and is subject to the twenty year
`
`
`
`
`
`
`term provisions of 35 U.S.C.
`patent
`
`154(a)(2).
`
`
`
`
`
`
`
`Subject to any disclaimer, the term of this
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`
`U.S.C. 154(b) by 635 days.
`
`
`
`
`
`(21) Appl. NO': 08/941’785
`
`
`
`
`Filed:
`Sep. 30, 1997
`(22)
`
`
`
`(60)
`
`
`
`
`
`
`
`Related US. Application Data
`
`
`
`
`
`
`
`Provisional application No. 60/033,426, filed on Dec. 24,
`
`1996'
`
`
`
`
`
`(51)
`Int. Cl.7 .................................................. H04N 7/12
`
`
`
`
`(52) us. Cl.
`.................................................. 375/240.13
`
`
`
`
`(58) Field of Search ................................. 348/384, 390,
`
`
`
`
`
`348/400, 401, 402, 409, 415, 416, 420,
`
`
`
`
`421; 382/232, 233’ 236, 238; 375/24001,
`
`
`
`
`240.12, 240.13, 240.24; H04N 7/12
`
`
`
`
`
`
`
`
`
`
`(56)
`
`
`
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`7/1981 Mounts ...................... 348/401
`
`
`
`
`4,281,344 A *
`
`
`
`
`
`4,704,628 A * 11/1987 Chen .......................... 348/400
`4,930,013 A *
`5/1990 Leaning
`..... 348/422
`
`
`
`
`
`5,226,093 A *
`7/1993 Iwase ..........
`.. 348/416.1
`
`
`
`
`
`5,262,878 A * 11/1993 Esserman
`..... 358/430
`
`
`
`
`
`5,294,974 A *
`3/1994 Naimpally .................. 348/405
`
`
`
`
`
`
`
`
`
`5,386,248 A *
`1/1995 De Haan .................... 348/699
`
`
`
`
`
`5,684,534 A * 11/1997 Harney ............. 348/390
`
`5,815,636 A *
`9/1998 Fujii ............ 386/116
`
`
`
`
`
`
`
`
`5,883,823 A *
`3/1999 Ding .......................... 708/402
`
`
`
`
`5,905,535 A *
`5/1999 Kerdranvat
`................. 348/416
`5,933,571 A *
`8/1999 Bannai
`....................... 386/112
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`* cited by examiner
`
`
`
`
`
`
`
`Primary Examiner—Young Lee
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—Leonard Charles Suchyta;
`
`
`James K. Weixel
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`
`A process for reducing spatial redundancy and thereby
`
`
`
`
`
`
`
`increasing the efficiency of video compression techniques
`
`
`
`
`
`
`
`for video conferencing. A process for improving video
`
`
`
`
`
`
`
`coding by differential macroblock coding. One video coding
`
`
`
`
`
`
`
`process involves differential formation for the coding of
`
`
`
`
`
`
`
`
`each macroblock in comparison to at least one other mac-
`
`
`
`
`
`
`
`
`roblock Within each video picture. Another video coding
`
`
`
`
`
`
`
`process inV01VeS differential formation for macroblock God-
`
`
`
`
`
`
`
`ing by comparison to tWO maerobloeks, including the mac-
`
`
`
`
`
`
`
`
`rebloek immediately to the left of the coding maerobloek
`
`
`
`
`
`
`
`
`and the macroblock immediately above the coding macrob-
`
`
`
`
`
`
`
`lock. These processes involve improvements to the H.263
`
`
`
`
`
`
`
`video coding standard as well as improvements to the H.324
`
`
`
`
`
`
`
`video conferencing standard. These processes also involve
`
`
`
`
`
`
`
`improvements to the MPEG-2 and MPEG-4 video stan-
`dards.
`
`
`
`
`
`
`
`66 Claims, 15 Drawing Sheets
`
`
`
`
`
`
`
`
`
`312-,l
`
`
`
`
`
`
`
`
`
`r """"‘ """""""""""""""""""""""""""" 350"“:
`
`
`
`INTER/INTRA FLAG $492:
`I
`
`
`THANSMITTED OR NOT
`I
`i
`
`
`QUANTIZEFI INDICATION i
`I
`
`
`
`I
`494
`1
`
`l VIDEO IN
`E
`Q'LEVEL
`:
`496
`I
`l
`I
`'
`I
`'
`I
`l
`I
`|
`I
`|
`I
`|
`I
`I
`I
`I
`I
`|
`I
`I
`I
`'
`I
`'
`I
`I
`I
`l
`I
`|
`l
`l
`I
`I
`I
`I
`I
`
`:
`I
`498
`I
`E
`MOTION VECTOR
`
`
`L
`____________________________________________________________J
`
`
`
`
`
`
`
`
`Page 1 0f 28
`
`GOOGLE EXHIBIT 1018
`
`GOOGLE EXHIBIT 1018
`
`Page 1 of 28
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheet 1 0f 15
`
`US 6,614,845 B1
`
`4<mekxm
`
`mmkam—zoo
`
`
`
`omk<05moIMIFOm0
`
`P.9...
`
`._<z_s_mm._.
`
`I20.20;;<55'm0_>m0
`
`Page 2 of 28
`
`Page 2 of 28
`
`

`

`S”U
`
`2
`
`US 6,614,845 B1
`
`
`
`>58TEE"mMEMOMEOwDOO0.091nxasmo"as:
`
`._oEzoom.552855538.2.52:"uo:mMum980.5%<50"e_%v:_
`
`
`
`_.
`
`t.a.P,8
`
`9_2_w.8..m:_su
`
`omo_>"tnmr..................we......................................1---€.L
`
`_omooo
`
`Page 3 of 28
`
`Page 3 of 28
`
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 3 0f 15
`
`
`
`US 6,614,845 B1
`
`_
`
`_
`
`___
`
`
`
`
`
`
`
`.u"255m._._mmummsmmmooowo$5080.2205n_"omooo
`
`
`
`
`oz_>_w0wmxw._n:.53_2Own=>momnomOmD_>"n
`
`_.-J...................m.Nm-----------..--wmm...........Nmm.........n"ownun
`
`
`.nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...___n"2<mm._.mtmmmuEDm$000
`
`
`
`.2205u_"omooozo_ww.2mz<m._.Xm._n=._..Ss_Omo_>OmQS“n
`
`
`
`
`
`
`
` ___________.____,._u..u4.nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn.o5\uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuA:xsx|u:u|__
`
`_un_
`
`
`
`lo:
`
`Page 4 of 28
`
`Page 4 of 28
`
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheet 4 0f 15
`
`US 6,614,845 B1
`
`8L05¢<EzEmkz.
`.62moomEzmz<E
`
`
`
` vm¢dZO_._.<O_DZ_mwNFZ<DO
`
`mmclm
`
`4m>w._.0
`
`8L
`
`
`
`m0P0m>20:.0—2
`
`omv
`
`o;
`
`z_Owo_>
`
`Page 5 of 28
`
`Page 5 of 28
`
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 5 0f 15
`
`
`
`US 6,614,845 B1
`
`
`
`_a
`
`wOZMDOmmOw0_>
`llilli
`
`
`
`Page 6 of 28
`
`gnomeIv—
`
`000?100.5
`
`
`
`
`
`
`
`
`
`
`m59855.2
`
`
`
`mmDPOE
`
`
`
`omo_.
`
`
`
`SEBDDDDD
`DIED... Tlmmmaomumw
`
`Page 6 of 28
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 6 0f 15
`
`
`
`US 6,614,845 B1
`
`COCOOOCCOCIIOOOCOOOO
`IOOODOIOOOOIOOOOCOOO
`
`
`IIOOOUOCOCOCOOOOOOO.
`
`IIOIDOOOOOOO0.0IOOOO
`
`
`
`
`
`FIG.12
`
`w wk
`
`@
`
`
`
`1210
`
`
`
`Luma
`
`FIG.6
`
`Page 7 of 28
`
`Page 7 of 28
`
`

`

`
`US. Patent
`
`
`
`
`Sep.2,2003
`
`
`
`
`Sheet 7 0f 15
`
`
`
`US 6,614,845 B1
`
`xOOJm
`
`owm
`
`
`
`
`
`<F<Q
`
`
`
`
`
`_mw><4¥004m__
`
`_E— 0.0:;
`
`mo>2
`
`vo2).
`
`
`
`mo>s.
`_mm$$—
`_—mm———
`FZ<DOD
`
`
`
`h.9“.
`
`
`
`
`mmm
`
`omm
`
`
`
`3m
`
`ovm
`
`mmm
`
`
`
`0mm
`
`mum
`
`
`
`omm
`
`mvm
`
`
`
`can
`
`Page 8 of 28
`
`>mm0
`
`
`mmmo
`
`mDOE
`
`UmmOE
`
`_mmm—
`
`
`
`own
`
`
`
`mom.
`
`
`
`Page 8 of 28
`
`
`
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 8 0f 15
`
`
`
`US 6,614,845 B1
`
`
`
`
`
`-Im><4v.00._m—-._.Z<DOn_
`
`
`
`
`
`
`
`XOOJM—-
`
` -mm><n_
`
`m.GE
`
`
`
`Page 9 of 28
`
`
`
`Page 9 of 28
`
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet9 0f15
`
`
`
`US 6,614,845 B1
`
`XOOJm
`
`
`
`<P<D
`
`
`
`mo>2
`
`mo>2
`
`
`
` _mm$—
`
`
`
`
`
`
`No>2
`_mm——
`HZ<DOD
`momo
`
`2..0E
`
`mumo
`
`
`
`
`
`mmozOmmOE
`
`
`
`—mmm—
`—¢m——
`
`
`
`Pagel()0f28
`
`Page 10 of 28
`
`
`
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheet 10 0f 15
`
`US 6,614,845 B1
`
`O0¢,
`
`—
`
`FIG.14
`
`FIG.13
`
`m
`
`<
`
`O
`
`och-oocogooccooootooogooocool...
`
`0.00000300000-ova-0.00.00.00.00.
`0000000000000000000000.000000000
`0000000000000000.000000000000000
`0.0.0.0000...-Coo-oooooosooooooo
`0000000000000000.000000000000000
`0000000000000000000...0.0.0.0000
`0000000000000000.000000000000000
`not...a...no...acuooooolouoo.lo.
`0000000.000000000000000000000000
`coo-oo-ooooooo000.000.000.000...
`000000000000000000000000.0000000
`00000000000000000000.00000000000
`0000000000000000.000000000000000
`000000000000000000000000.0000...
`000000000000000000000000.0000...
`'
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000...
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0000000000000000
`0.00000000000000
`0000000 00000000
`
`Page 11 of28
`
`Page 11 of 28
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheetll 0f15
`
`US 6,614,845 B1
`
`00000000
`
`00000000
`
`Yooooooo
`
`rooooooo
`
`Wooooooo
`
`mToooooc
`
`Swooéooo
`
`33333333
`oooooooo
`
`Tooooooo
`
`Fooooooo
`
`Wooboooo
`mmoooooo
`
`0v
`
`-mv-00000
`
`00000000
`
`00000000
`
`70000000
`
`Fooooooo
`
`wooooooo
`
`«Toooooo
`
`Or
`
`woooooo
`
`oooooooo
`
`00000000
`
`70000000
`
`Foooocoo
`
`”cocoooo
`
`nmoooooo
`
`Smwooooo
`
`mm
`
`WNooooo
`
`F015
`
`-_.---———-—--———————-—-—-—-————-—————_—_-———_—_——-—-———-——_——_-——-——————-___—.
`
`oooooooo
`
`00000000
`
`70000000
`
`wooooooo
`
`§ooooooo
`
`mToooooo
`
`gmoooooo
`
`
`
`
`
`
`
`
`
`33333333
`oooooooo
`
`Tooooooo
`
`Fooooooo
`
`90000000
`
`061000000
`
`0F
`
`OGV-00000
`
`00000000
`
`00000000
`
`70000000
`
`30000000
`
`”0000000
`
`mToooooo
`
`emoooooo
`
`33333333
`00000000
`
`70000000
`
`Fooooooo
`
`Wooooooo
`
`mmoooooo
`
`¢Mvooooo
`
`ngooooo
`
`
`
`oooooooo
`
`00000000
`
`oooooooo
`
`00000000
`
`Tooooooo
`
`70000000
`
`Fooooooo
`
`wooooooo
`
`Wooooooo
`
`fiooooooo
`
`mToooooo
`
`mToooooo
`
`gmoooooo
`
`gmoooooo
`
`33333333
`00000000
`
`33333333
`oooooooo
`
`Tooooooo
`
`Tooooooo
`
`vooooooo
`
`rooooooo
`
`¢ooooooo
`
`Wooooooo
`
`0N000000
`
`0P
`
`OOv-OOCOC}
`
`Na0) INOOOOO
`
`mmoooooo
`
`mwwooooo
`mmm.~ooooo
`
`Page 12 of28
`
`Page 12 of 28
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheet12 0f15
`
`US 6,614,845 B1
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`0000'0000
`
`00000000
`
`00000000
`
`33333333
`
`33333333
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`lav-000000
`
`00000000
`
`57000000
`
`Wooooooo
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`'oooooooo
`
`00000000
`
`33333333
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`v-v-000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`@ooooooo
`
`00000000
`
`00000000
`
`00000000
`
`00000000
`
`0.0000000
`
`00000000
`
`00000000
`
`—_-——u—-—--—-—-———-—-————-——-——-—n—-——o
`
`mToocooo
`
`030000000
`
`FGJWB
`
`HGJGA
`
`Page 13 0f28
`
`Page 13 of 28
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 13 0f 15
`
`
`
`US 6,614,845 B1
`
`
`
`
`
`.2880aa5522:2was.$290“.Eu95:98559:8
`
`
`
`EEEEEEEEEEEEEEEE
`
`EEEEEEEEEEEEE'IE
`EEHEEEHEE-flflflaafla
`
`
`
`
`
`9.01.
`
`
`
`.2..GE
`
`
`
`
`
`E029".
`
`353w
`
`
`
`
`
`
`
`
`
`Page 14 of28
`
`Page 14 of 28
`
`
`
`
`

`

`US. Patent
`
`Sep. 2, 2003
`
`Sheet 14 0f 15
`
`M
`
`1B
`
`W,mp.07..
`
`
`
`
`
`M,._m>mj20.29530mcm22m
`
`Z<_2mm._<w
`
`232me5:52
`
`$5623oz<
`
`mZOImm<0
`
`
`
`(OF—ms?wm=2
`
`on
`
`mm
`
`ON
`
`2.
`
`0—.
`
`02_><w.x.
`
`mtmz_
`
`Page 15 0f28
`
`Page 15 of 28
`
`
`
`
`
`
`

`

`
`US. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 15 0f 15
`
`M
`
`1
`
`
`
`
`
`“a4m>w._ZO_._.<N_.—.Z<DCmcmm_.or
`
`B.W,ON0.....—
`
`
`
`om<DGP9100
`
`mwz_<._.zOO
`
`
`
`on
`
`0..
`
`cmwz.><mo\°
`
`
`mtm2.
`
`Page 16 0f28
`
`Page 16 of 28
`
`
`
`

`

`
`
`US 6,614,845 B1
`
`
`1
`METHOD AND APPARATUS FOR
`
`
`
`
`DIFFERENTIAL MACROBLOCK CODING
`
`
`
`FOR INTRA-FRAME DATA IN VIDEO
`
`
`
`
`CONFERENCING SYSTEMS
`
`
`
`
`
`
`
`
`
`
`
`
`
`This application claims the benefit of provisional appli-
`cation Ser. No. 60/033,426 filed Dec. 24, 1996.
`
`
`
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`1. Field of the Invention
`
`
`
`
`
`
`
`
`
`
`
`The present invention relates generally to data compres-
`
`
`
`
`
`
`
`
`
`sion for
`the coding of video image signals. More
`
`
`
`
`
`
`
`particularly, the invention relates to a method for coding a
`
`
`
`
`
`
`
`macroblock for intra-frame data representing the digital
`
`
`
`
`
`
`embodiment of video image signals in video conferencing
`systems.
`
`
`
`
`
`
`2. Description of the Related Art
`
`
`
`
`
`
`
`The electronic transmission of video pictures, either ana-
`
`
`
`
`
`
`
`
`
`log or digital, has presented various problems of both
`
`
`
`
`
`
`
`transmission quality and transmission efficiency in the art of
`
`
`
`
`
`
`video conferencing. In the context of digital transmissions
`
`
`
`
`
`
`
`particularly, quality and efficiency issues are frequently
`
`
`
`
`
`
`
`
`intertwined. Over the years, the most common solution to
`
`
`
`
`
`
`
`
`these issues has involved various types of video compres-
`sion.
`
`
`
`
`
`
`
`
`
`There are two types of video compression, spatial com-
`
`
`
`
`
`
`pression and temporal compression. Spatial compression
`strives to achieve a reduction in the information content of
`
`
`
`
`
`
`
`
`
`
`
`
`the video transmission by applying mathematical methods to
`
`
`
`
`
`
`
`
`reduce the redundancy of the contents of one video frame in
`
`
`
`
`
`
`comparison to another (thus, to reduce spatial redundancy).
`
`
`
`
`
`
`
`
`
`For video conferencing systems (that is, low bit rate coding
`
`
`
`
`
`
`applications),
`this problem is even more pronounced
`
`
`
`
`
`
`
`
`because such video scenes generally contain a highly cor-
`
`
`
`
`
`
`related background and a foreground with a small
`to
`medium amount of motion. One of the most common
`
`
`
`
`
`
`
`
`
`
`
`
`
`mathematical methods for reducing spatial redundancy is
`
`
`
`
`
`
`
`discrete cosine transform (DCT), as used by the Joint Picture
`
`
`
`
`
`
`
`Experts Group (JPEG) standard. In particular,
`television
`
`
`
`
`
`
`
`video signals, for example, are frequently compressed by
`
`
`
`
`
`
`
`DCT to reduce spatial redundancy pursuant to the Motion-
`
`
`
`JPEG (M-JPEG) standard.
`
`
`
`
`
`
`In contrast to-spatial compression, temporal compression
`
`
`
`
`
`
`
`
`
`is frequently used for video signals other than television
`
`
`
`
`
`
`
`video signals. Video conferencing, for example, frequently
`
`
`
`
`
`
`
`applies temporal compression for purposes of video
`
`
`
`
`
`
`
`compression, pursuant to the Motion Picture Experts Group
`
`
`
`
`
`
`
`(MPEG) standard. One of the fundamental elements of
`
`
`
`
`
`
`
`temporal compression involves the reduction of data rates,
`
`
`
`
`
`
`
`
`and a common method for reducing data rates in temporal
`
`
`
`
`
`compression is motion compensation. Motion compensation
`
`
`
`
`
`
`
`
`is a method of predicting one frame based upon an earlier
`
`
`
`
`
`
`frame. For example, in motion compensation, a predicted
`
`
`
`
`
`
`frame (P-frame) is based on an intra-coded frame (I-frame,
`
`
`
`
`
`
`
`
`
`
`that is, a frame that has only been spatially coded). In this
`
`
`
`
`
`
`
`manner, using temporal compression, the P-frame is coded
`based on the I-frame. Thus,
`if there is little difference
`
`
`
`
`
`
`
`
`
`between Alto the P-frame and the I-frame, motion compen-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sation may result
`in a significant reduction of the data
`
`
`
`
`
`
`
`
`needed to represent the content of the video using temporal
`
`compression.
`
`
`
`
`
`
`
`
`Various standards have been proposed for using both
`
`
`
`
`
`
`
`
`spatial and temporal compression for the purposes of video
`compression. The International Telecommunication Union
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(ITU), for example, has established the H.324 standard for
`the transmission of low bit-rate multimedia over general
`
`
`
`
`
`
`
`
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 17 of28
`
`
`2
`
`
`
`
`
`
`
`switched telephone networks, which includes video confer-
`
`
`
`
`
`
`
`encing. The H.324 video conferencing standard generally
`
`
`
`
`
`
`
`
`
`utilizes the H.263 video coding system. H.324 also plans to
`
`
`
`
`
`
`incorporate a proposed improvement for H.263, namely,
`
`
`
`
`
`
`
`H.263+ as well as H.263++. Currently, however, H.263
`
`
`
`
`
`
`
`represents the most recognized form of video compression
`
`
`
`
`
`
`
`for video conferencing,
`including the various MPEG
`standards, such as MPEG-1 and MPEG-2, which use the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`H.324/H.263 standard. Indeed, the proposed MPEG-4 stan-
`
`
`
`
`
`
`
`dard will also incorporate the H.324/H.263 standard.
`
`
`
`
`
`
`All of these standards, however, focus more on temporal
`
`
`
`
`
`
`
`compression than spatial compression, most likely due to the
`
`
`
`
`
`
`focus on compression for video conferencing. Indeed, most
`
`
`
`
`
`
`of these standards utilize some form of block-matching,
`
`
`
`
`motion-estimation compensation technique to accomplish
`
`
`
`
`
`temporal compression, generally by inter-frame (or P-frame)
`
`
`
`
`
`
`coding. As a result, the focus on temporal compression has
`
`
`
`
`
`resulted in a lack of attention to spatial compression. Also,
`
`
`
`
`
`
`
`the use of inter-frame (P-frame)
`temporal coding has
`
`
`
`
`
`resulted in little development of intra-frame (I-frame) cod-
`
`
`
`
`
`
`
`ing techniques. Moreover, even the known I-frame coding
`
`
`
`
`
`
`
`
`techniques do not take full advantage of the inter-block
`
`
`
`
`
`correlation present in typical pictures of video conferencing
`systems.
`
`
`
`
`
`
`
`This inattention in video compression to I-frame spatial
`
`
`
`
`
`
`
`
`coding gives rise to inefficiencies and other diminutions in
`
`
`
`
`
`
`quality that could be achieved by further development of
`
`
`
`
`
`
`
`
`compression techniques for I-frame spatial coding. Thus, the
`
`
`
`
`
`
`
`current video coding techniques reflect an unsatisfactory
`
`
`
`
`
`development of methods to diminish spatial redundancy in
`
`
`
`
`
`
`
`
`I-frame coding to provide better efficiency and better quality
`
`
`
`
`
`
`
`for video compression, particularly for video conferencing
`
`applications.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SUMMARY OF INVENTION
`
`
`
`
`
`
`
`Accordingly, the present invention is directed to a method
`
`
`
`
`
`
`
`that substantially obviates one or more of the problems due
`
`
`
`
`
`
`to the limitations, shortcomings, and disadvantages of the
`related art.
`
`
`
`
`
`
`
`
`
`One advantage of the invention is greater efficiency in
`
`
`
`
`
`video compression by reducing spatial redundancy through
`
`
`
`improvements in intra-frame coding.
`
`
`
`
`
`Another advantage of the invention is the improvement of
`
`
`
`
`
`
`
`
`the standard coding protocols, such as the H.263 video
`
`
`
`
`
`
`
`coding standard and the H.324 video conferencing standard,
`
`
`
`
`which ensures forward compatibility.
`
`
`
`
`
`
`
`
`
`To achieve these and other advantages, one aspect of the
`
`
`
`
`
`
`invention includes a method of data compression. This
`
`
`
`
`
`
`method comprises receiving a plurality of macroblocks;
`
`
`
`
`
`
`selecting one of the macroblocks; determining a difference
`between the selected macroblock and at least one other
`
`
`
`
`
`
`
`
`macroblock; and encoding the selected macroblock based on
`
`
`
`
`
`
`the difference.
`
`
`A further aspect of the invention includes a method of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`coding and decoding. This method comprises encoding a
`coding macroblock based on a difference between the cod-
`
`
`
`
`
`
`
`ing macroblock and a reference macroblock; and decoding
`
`
`
`
`
`
`
`the coding macroblock based on the difference between the
`
`
`
`
`
`
`
`
`coding macroblock and the reference macroblock.
`
`
`
`
`
`
`Another aspect of the invention includes a method of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`coding. This method comprises a storing component con-
`
`
`
`
`
`
`figured to store a reference macroblock; a receiving com-
`
`
`
`
`
`
`ponent configured to receive a coding macroblock to be
`
`
`
`
`
`coded; a determining component configured to determine a
`difference between the coding macroblock and the reference
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`macroblock; and an encoding component configured to
`encode the coding macroblock based on the difference.
`
`
`
`
`
`
`
`
`Page 17 of 28
`
`

`

`
`
`US 6,614,845 B1
`
`
`4
`
`
`
`
`
`FIG. 19 is a graph depicting the efficiency improvement
`
`
`
`
`
`
`
`gained by the claimed macroblock coding technique; and
`
`
`
`
`
`
`
`FIG. 20 is another graph depicting the efficiency improve-
`
`
`
`
`
`
`
`ment gained by the claimed macroblock coding technique.
`DETAILED DESCRIPTION
`
`Introduction
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Methods consistent with the invention avoid the ineffi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ciencies of the prior art video compression techniques by
`
`
`
`
`
`
`diminishing spatial redundancy in current
`intra-frame
`
`
`
`
`
`
`
`
`(I-frame) coding. The methods use the structure of the H.324
`
`
`
`
`
`
`
`
`video conferencing standard as well as the structure of the
`
`
`
`
`
`
`
`H.263 video coding standard. The recommendation reports
`for these standards, as described in International Telecom-
`
`
`
`
`
`
`munication Union, Telecommunication Standardization
`
`
`
`
`Sector, Recommendation H.324, Terminal for Low Bit Rate
`
`
`
`
`
`
`
`
`
`
`
`
`
`Multimedia Communication (March 1996), and Interna-
`tional Telecommunication Union, Telecommunication Stan-
`
`
`
`
`
`
`
`
`
`
`
`dardization Sector, Recommendation H.263, Video Coding
`
`
`
`
`
`
`
`
`for Low Bit Rate Communication (March 1996), are hereby
`
`
`incorporated by reference.
`
`
`
`
`
`To achieve an improvement in I-frame coding, an imple-
`
`
`
`
`
`
`
`mentation consistent with the invention provides for com-
`
`
`
`
`
`
`paring a coding macroblock to at least one other reference
`
`
`
`
`
`macroblock in order to determine a difference. The coding
`
`
`
`
`
`
`
`macroblock is then encoded with the difference. One imple-
`mentation consistent with the invention also results in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`addition of two components to the protocol structure of the
`macroblock layer in the H.263 standard. Thus, when the
`
`
`
`
`
`
`
`
`
`
`
`
`method is used, a value is assigned to a difference compo-
`
`
`
`
`
`
`nent to indicate the encoding of the coding macroblock, and
`
`
`
`
`
`
`a value is assigned to a reference component to indicate the
`
`
`
`
`
`
`location of the reference macroblock. Alternatively, when
`there is an insubstantial difference between the coding
`
`
`
`
`
`
`
`macroblock and the reference macroblock, the method is not
`
`
`
`
`
`
`
`
`
`
`
`
`
`used, and the difference component indicates no coding, and
`the reference macroblock is not utilized.
`
`
`
`
`
`
`
`
`
`
`
`
`In the preferred implementation, the comparison of mac-
`
`
`
`
`
`
`
`roblocks occurs by comparing the coding macroblock
`
`
`
`
`
`
`
`
`the macroblock immediately left of the coding
`against
`
`
`
`
`
`
`
`macroblock and immediately above the coding macroblock,
`if a macroblock exists at either or both of these positions.
`
`
`
`
`
`
`
`
`
`
`
`
`
`However, the methods similarly operate in comparison to
`other macroblocks as reference macroblocks with similar
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`gains in efficiency. Additionally,
`the methods may also
`
`
`
`
`
`
`
`
`
`operate on other levels of the video sequence, including
`
`
`
`
`
`
`
`blocks and groups of blocks (or slices of video).
`
`
`
`Video Conferencing System
`
`
`
`
`
`
`FIG. 1 illustrates a video conferencing system according
`
`
`
`
`
`
`
`to the present invention. System 5 comprises an external
`
`
`
`
`
`
`
`
`computer or other dedicated device 10, data application 20,
`
`
`
`
`
`
`
`
`terminal 30, modem 40, and general switched telephone
`
`
`
`
`
`
`
`network (GSTN) 50. External computer 10 implements
`
`
`
`
`
`
`
`video conferencing with data application 20, transmitting
`the video, audio, and data. External computer 10 and data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`application 20 then interact with terminal 30. In a sending
`mode, terminal 30 encodes the video, audio, and data and
`
`
`
`
`
`
`
`
`
`then transmits the encoded information to modem 40, which
`
`
`
`
`
`
`
`
`
`
`
`
`transmits the information to GSTN 50. Correspondingly, in
`
`
`
`
`
`
`
`
`a receiving mode,
`the operation of system 5 in FIG. 1
`
`
`
`
`
`
`
`functions similarly, except that GSTN 50 initially receives
`the encoded information, provides the encoded information
`
`
`
`
`
`
`
`to modem 40, which transmits the information to terminal
`
`
`
`
`
`
`
`30, which then decodes the video, audio, and data, and then
`
`
`
`
`
`
`
`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`Still another aspect of the invention includes a method of
`
`
`
`
`
`
`
`decoding. This method comprises a storing component con-
`
`
`
`
`
`
`figured to store a reference macroblock; a receiving com-
`
`
`
`
`
`
`ponent configured to receive a coded macroblock, which
`was coded based on a difference with the reference mac-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`roblock; and a decoding component configured to decode
`the coded macroblock based on the difference.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Additional aspects of the invention are disclosed and
`
`
`
`
`
`
`defined by the appended claims. It is to be understood that
`
`
`
`
`
`
`
`
`both the foregoing general description and the following
`
`
`
`
`
`
`
`
`detained description are exemplary and explanatory and are
`
`
`
`
`
`
`intended to provide further explanation of the invention as
`claimed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`The accompanying drawings illustrate a preferred
`
`
`
`
`embodiment of the invention. The drawings are incorporated
`
`
`
`
`
`
`
`in and constitute a part of this specification. In the drawings,
`
`
`
`
`
`FIG. 1 is a block diagram of a video conferencing system;
`
`
`
`
`
`
`FIG. 2 is a block diagram of a terminal from the video
`
`
`
`conferencing system in FIG. 1;
`
`
`
`
`
`
`FIG. 3 is a block diagram of a codec utilizing the H.324
`
`
`
`
`
`
`
`video conferencing standard and the H.263 video coding
`standard from the terminal in FIG. 2;
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 4 is a block diagram of a source coder from the video
`codec in FIG. 3;
`
`
`
`
`
`
`
`
`FIG. 5 is a block diagram used to explain a sample video
`sequence;
`
`
`
`
`
`
`FIG. 6 is a diagram used to explain a sample of the blocks
`
`
`
`
`in a macroblock as depicted in FIG. 5;
`
`
`
`
`
`
`
`FIG. 7 is a diagram used to explain a sample of the
`structure of a macroblock layer using the H.263 standard;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 8 is a diagram used to explain the standard syntax for
`
`
`
`
`
`
`
`the macroblock layer utilizing the H.263 standard;
`
`
`
`
`
`
`FIG. 9 is a diagram used to explain the syntax for
`
`
`
`
`
`intra-frame coding of a macroblock utilizing the H.263
`standard;
`
`FIG. 10 is a block diagram of an embodiment of the
`
`
`
`
`
`
`
`
`
`
`
`
`improved syntax for coding a macroblock utilizing the
`H.263 standard;
`
`
`FIG. 11 is a block diagram of an embodiment of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`improved structure for the macroblock layer utilizing the
`H.263 standard;
`
`
`
`
`
`
`
`
`FIG. 12 is a-diagram used to explain a sample of the
`arrangement of blocks in a macroblock from a slice from the
`
`
`
`
`
`
`
`
`
`picture shown in FIG. 5;
`
`
`
`
`
`FIG. 13 is a diagram of three macroblocks arranged with
`one macroblock beside another macroblock and under
`
`
`
`
`
`
`another macroblock;
`
`
`
`
`
`
`
`
`
`FIG. 14 is a block diagram of the three comparison
`macroblocks of FIG. 13;
`
`
`
`
`
`
`
`
`
`FIG. 15 is a diagram of a sample representation of the
`DCT values contained within the three macroblocks of FIG.
`
`
`
`
`
`
`
`13;
`
`FIGS. 16A and 16B are diagrams of macroblocks after
`
`
`
`
`
`
`
`
`
`
`
`
`
`computation of a difference with the other macroblocks
`
`
`
`depicted in FIG. 15;
`
`
`
`
`
`
`FIG. 17 is a diagram of an example of the efficiency
`
`
`
`
`
`
`improvement gained by the claimed macroblock coding
`
`technique;
`
`
`
`
`FIG. 18 is another diagram of an example of the efficiency
`
`
`
`
`
`
`improvement gained by the claimed macroblock coding
`
`technique;
`
`
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 18 of28
`
`Page 18 of 28
`
`

`

`
`
`US 6,614,845 B1
`
`
`
`5
`
`terminal 30 transmits the video, audio, and data to external
`
`
`
`
`
`
`
`
`
`
`
`
`computer 10 and data application 20.
`
`
`
`
`
`
`
`As shown in FIG. 2, terminal 30 comprises video codec
`
`
`
`
`
`
`
`
`
`110, audio codec 112, data protocols 114, multimedia system
`
`
`
`
`
`
`
`control 116,
`receive path delay 120, multiplexer/
`
`
`
`
`
`
`
`
`demultiplexer 130, modem 140, and modem control 145.
`Terminal 30 transforms a video signal into a format suitable
`
`
`
`
`
`
`
`for transmission over-GSTN 50 via modem 40.
`In one
`
`
`
`
`
`
`
`
`
`
`
`
`
`common embodiment as a multimedia telephone terminal,
`
`
`
`
`
`
`
`
`terminal 30 provides for the transmission and receipt of real,
`live-time video, audio, or data, or any combination thereof,
`
`
`
`
`
`
`
`
`
`
`
`
`
`along with the necessary control codes.
`
`
`
`
`
`
`Each component of terminal 30 preferably implements
`certain functions dictated by the H.324 standard. Video
`
`
`
`
`
`
`
`
`codec 110, using either the H.263 or H.261 standard, carries
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`out redundancy reduction coding and decoding for video
`
`
`
`
`
`
`
`
`streams. Audio codec 112, using the G.723.1 standard,
`
`
`
`
`
`
`
`
`encodes the audio signal
`from the microphone for
`
`
`
`
`
`
`
`
`transmission, and decodes the audio code which is output to
`
`
`
`
`
`
`
`
`
`the speaker. Optional receive path delay 120 in the receiving
`
`
`
`
`
`
`
`
`audio path compensates for the video delay, so as to main-
`
`
`
`
`
`
`
`
`tain audio and video synchronization. Data protocols 114
`
`
`
`
`
`
`support data applications such as electronic Whiteboards,
`
`
`
`
`
`
`
`
`still image transfer, file exchange, database access, audio-
`
`
`
`
`
`
`
`graphics conferencing, remote device control, and network
`
`
`
`
`
`
`protocols. Standardized data applications include T120 for
`
`
`
`
`
`
`real-time audiographics conferencing, T84 simple point-
`
`
`
`
`
`
`
`
`
`point still image file transfer, T434 simple point-point file
`transfer, H.224/H.281 far-end camera control,
`IS/IEC
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TR9577 network protocols including PPP and IP, and trans-
`
`
`
`
`
`
`
`
`port of user data using buffered V.14 or LAPM/V.42. Other
`
`
`
`
`
`
`
`
`
`applications and protocols may also be used via H.245
`
`
`
`
`
`
`
`
`negotiation. Multimedia system control 116, using the H.245
`
`
`
`
`
`
`
`standard, provides end-to-end signaling for proper operation
`of the H.324 terminal, and signals all other end-to-end
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`system functions including reversion to analogue speech-
`
`
`
`
`
`
`
`only telephony mode. It provides for capability exchange,
`
`
`
`
`
`
`
`signaling of commands and indications, and messages to
`
`
`
`
`
`
`
`
`
`open and fully describe the content of logical channels.
`
`
`
`
`
`
`Multiplexer/Demultiplexer 130, using the H.223 standard,
`multiplexes transmitted video, audio, data and control
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`streams into a single bit stream, and demultiplexes a
`received bit stream into various multimedia streams. In
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`addition, it performs logical framing, sequence numbering,
`error detection, and error-correction by means of
`
`
`
`
`
`
`
`
`
`
`
`
`
`retransmission, as appropriate to each media type. Modem
`
`
`
`
`
`
`
`
`
`140, using the V34 standard, converts the H.223 synchro-
`
`
`
`
`
`
`
`
`
`nous multiplexed bit stream into an analogue signal that can
`be transmitted over the GSTN, and converts the received
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`analogue signal into a synchronous bit stream that is sent to
`
`
`
`
`
`
`the Multiplex/Demultiplex protocol unit. Modem control
`
`
`
`
`
`
`
`
`145, using the V25 standard, is used to provide control/
`sensing of the modem/network interface, when the modem
`
`
`
`
`
`
`with network signaling and V.8/V.8 bis functional elements
`
`
`
`
`
`
`
`
`
`
`
`
`is a separate physical item.
`
`
`
`
`
`
`
`Video codec 110 implements the H.263/H.261 video
`
`
`
`
`
`
`
`
`coding standards. Video codec 110 conducts the spatial
`
`
`
`
`
`
`
`redundancy reduction coding and decoding for video
`streams. The term “codec” refers to a coder decoder. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`H.263 and H.261 video coding standards are two separate
`
`
`
`
`
`
`coding/decoding techniques. The H.324 standard requires
`
`
`
`
`
`
`
`
`
`
`support for both the H.263 and the H.261 video coding
`
`
`
`
`
`
`
`standards. Accordingly, the H.324 standard recognizes and
`utilizes five standardized video image formats: 16CIF, 4CIF,
`
`
`
`
`
`
`
`
`CIF, QCIF, and SQCIF: H.261 employs CIF and QCIF, and
`
`
`
`
`
`
`
`
`
`
`H.263 employs 4CIF, 16CIF and SQCIF. For each of these
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`picture formats,
`the luminance sampling structure is dx
`
`Page 19 of28
`
`
`6
`
`
`
`
`
`
`
`
`pixels per line, dy lines per picture in an orthogonal arrange-
`
`
`
`
`
`
`
`
`ment. Sampling of each of the two color difference compo-
`
`
`
`
`
`
`
`
`
`
`nents is at dx/2 pixels per line, dy/2 lines per picture,
`
`
`
`
`
`
`
`
`
`
`orthogonal. The values of dx, dy, dx/2 and dy/2 are given in
`
`
`
`
`
`
`
`
`the following table for each of the picture formats.
`
`10
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Number of
`
`pixels for
`
`
`luminance
`
`(dx)
`
`128
`176
`352
`704
`1408
`
`
`
`
`
`
`
`Number of
`
`lines for
`
`
`luminance
`
`(dy)
`
`96
`144
`288
`576
`1152
`
`
`
`
`
`
`
`Picture
`
`Format
`
`sub-QCIF
`QCIF