`US006614845B1
`
`
`
`
`
`
`
`
`United States Patent
`US 6,614,845 B1
`(10) Patent No.:
`
`
`
`
`
`
`*Sep. 2, 2003
`(45) Date of Patent:
`Azadegan
`
`
`(12)
`
`
`
`
`
`
`
`
`(54) METHOD AND APPARATUS FOR
`
`
`
`DIFFERENTIAL MACROBLOCK CODING
`
`
`
`
`FOR INTRA-FRAMEDATAIN VIDEO
`
`
`CONFERENCING SYSTEMS
`
`(75)
`
`
`
`
`
`
`
`
`Inventor: Faramarz Azadegan, San Diego, CA
`
`(US)
`
`
`
`
`(*) Notice:
`
`
`
`
`
`
`
`
`(73) Assignee: Verizon Laboratories Inc., Waltham,
`
`MA (US)
`
`
`
`
`
`
`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)
`
`
`
`
`
`
`
`4,704,628 A * 11/1987 Chen ...... cee 348/400
`
`
`
`
`4,930,013 A *
`5/1990 Leaning wesc: 348/422
`
`
`
`
`
`5,226,093 A *
`7/1993 Iwase .........
`. 348/416.1
`
`
`
`
`
`
`5,262,878 A * 11/1993 Esserman ou... 358/430
`
`
`
`
`5,294,974 A *
`3/1994 Naimpally ........0..00. 348/405
`
`
`
`
`
`5,386,248 A *
`1/1995 De Haan veces 348/699
`
`
`
`
`5,684,534 A * 11/1997 Harney «0.0.0...
`eee 348/390
`
`
`
`
`
`
`5,815,636 A *
`9/1998 FUjii
`.... ee
`eeeee 386/116
`
`
`
`
`5,883,823 A *
`3/1999 Ding oo... eee eee 708/402
`
`
`
`
`5,905,535 A *
`5/1999 Kerdranvat oo... 348/416
`
`
`
`
`5,933,571 A *
`8/1999 Bannai ......... eee 386/112
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`* cited by examiner
`
`
`
`
`
`
`
`
`
`Primary Examiner—Young Lee
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—Leonard Charles Suchyta;
`
`
`James K. Weixel
`
`
`ABSTRACT
`67)
`
`
`
`
`
`
`
`
`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
`Related U.S. Application Data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`each macroblock in comparison to at least one other mac-
`Provisional application No. 60/033,426, filed on Dec. 24,
`
`
`
`
`
`
`
`
`
`1996.
`roblock within each video picture. Another video coding
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(SL) Tints C0oe eeccceeccseeeeesseeeeseeeeeesnneeennes HO4N 7/12_process involvesdifferential formation for macroblock cod-
`
`
`
`
`
`
`
`
`
`
`
`
`(52) US. CM.
`ceeeecceceessssescssstesssseeessseesesneeeennes 375/240.13
`ing by comparison to two macroblocks, including the mac-
`
`
`
`
`
`
`
`
`
`
`
`
`
`(58) Field of Search .........ccc.cccccccscccccses 348/384, 390,
` toblock immediately to the left of the coding macroblock
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`348/400, 401, 402, 409, 415, 416, 420,
`and the macroblock immediately above the coding macrob-
`
`
`
`
`
`
`
`
`
`
`
`
`421; 382/232, 233, 236, 238; 375/240.01,
`lock. These processes involve improvements to the H.263
`
`
`
`
`
`
`
`
`
`
`
`
`240.12, 240.13, 240.24; HO4N 7/12
`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.
`
`
`(60)
`
`
`
`(56)
`
`
`
`
`
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`7/1981 Mounts... eee 348/401
`
`
`
`
`4,281,344 A *
`
`
`
`
`
`
`66 Claims, 15 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`312-,i
`
`posseei079
`
`
`
`
`INTERINTRA FLAG¢492|
`
`
`TRANSMITTED OR NOT
`!
`
`QUANTIZER INDICATION |
`
`
`
`40g!
`
`
`
`t
`'
`(
`1
`1
`'
`1
`i
`1
`l
`I
`'
`'
`i)
`{
`1
`'
`(
`'
`|
`
`
`
`| VIDEO IN
`{
`1
`1
`t
`1
`1
`1
`I
`I
`1
`1
`1
`1
`1
`{
`t
`1
`1
`1
`
`
`
`
`
`
`Q-LEVEL
`496
`
`
`
`498
`
`MOTION VECTOR
`
`
`Lenene nenaeeej
`
`Page 1 of 28
`
`GOOGLE EXHIBIT 1018
`
`GOOGLE EXHIBIT 1018
`
`Page 1 of 28
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 1 of 15
`
`WNealxsa
`
`US 6,614,845 B1
`
`LOld
`
`WNIWYSL
`
`||NOLLVOMddvVivaooSIAR
`
`G3LV9Ida0HAHLOHO
`YS.LNAdWOO
`
`Page 2 of 28
`
`Page 2 of 28
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 2 of 15
`
`US 6,614,845 B1
`
`seeeeeeeeeehwhwnesoeecmeeoecreeetSeSTetfeeneeemmhYe4
`
`we oe ee ee eeeeerr
`
`JOYLNOOD
`
`IXNW
`
`XNWAG
`
`
`
`$1000LO¥dVLVO
`
`Vit
`
`
`
`WALSASVIGSWILINW
`
`TOHLNOSD
`
`Obb
`
`Oz!chk
`
`03009O3dIA
`
`AV140HLVd
`
`
`
`SAIZ03Y03009O10NV
`
`LoweLE en we eeee
`
`Page 3 of 28
`
`Page 3 of 28
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`iole-eeeeeq---------!
`
`
`
`Page 4 of 28
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 3 of 15
`
`
`
`US 6,614,845 B1
`
`€‘Sig
`
`
`
`
`
`
`
`
`eemememetmemms7!!IaTy|WVAaYLSLIS¥3544N8
`OSAIA!!I1Pteeeeeee’eeSeezeso|oze-"
`|!Permamman7I||1WV3UYLSLidY3IINg430090“WNDIS;|qgqdoo
`
`
`
` |i|1|!jI|!|1t1lI|I|Iot,ot{t!!|beegnannnnaannnnnnnnnoononnnnnnnnnnnnnnnnnnnnnennnnnnnnaan
`
`
`ONIAIOSYXSIdILINWOSCIASa9DYNOS4350003dW3Sq0d00S0TvNOIS!|!qg3q090
`
`
`
`NOISSINSNVYLXSIdILINWOSCIAOSQGIA!
`
`
`Page 4 of 28
`
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 4 of 15
`
`{pL
`
`eeef!!HO.LOSA
`NOLLOWSoa|!!ser!og!'!i)|!I!!I
`t|({{!I!fo|ObOly!
`
`qaAaT08|a|NIOSGIA|ver|NOLLVOIONIHAZLLNYNO.!|
`I'LONHOGSLLINSNVHL
`ONIGOD!|eroyVULNISLNITORLNOD!J8Moneeeeee!
`
`US 6,614,845 B1
`
`y‘Sls
`
`96r
`
`Page 5 of 28
`
`Page 5 of 28
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 5 of 15
`
`
`
`US 6,614,845 B1
`
`ftstaxid7
`
`S‘Old
`
`
`
`Page 6 of 28
`
`
`—|
`k ox
`
`
`SYNLOId +}—~ssuiniomaodNoOuwd——||Oror
`“TTOOUUUU
`
`JONANDASOXIA
`+
`
`”u
`
`QQ
`
`WOOTOYOVN
`
`osot
`
`oc0l
`
`
`
`
`
`090}HOO18
`
`
`
`
`
`
`
`
`Page 6 of 28
`
`

`

`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 6 of 15
`
`
`US 6,614,845 B1
`
`
`
`
`
`FIG.6
`
`Seeenevseensoseeseese
`
`
`exeseeeeseeseoeseeren
`
`oO Seen eseeeeeeoeeosese
`
`~ RERSHHOSSSHOSCESHOOHOFE
`
`A
`i
`_—
`
`FIG.12
`Luma
`
`
`
`
`
`Page 7 of 28
`
`Page 7 of 28
`
`

`

`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 7 of 15
`
`
`
`US 6,614,845 B1
`
`400198
`
`VLVd
`
`
`
`
`gdqAw
`
`09S
`
`
`
`sss
`
`
`
`
`
`YSAVTXO018
`
`Lewvnoa
`
`
`
`vOAW
`
`oss
`
`
`
`Ses
`
`Ors
`
`
`SGAW
`son
`[omses
`
`LNVNOG
`Add
`
`8‘Did 2‘Sld
`
`oes
`
`Ses
`
`
`
`
`
`€add9
`
`oes
`
`SIS
`
`gqow
`OdaoOW
`
`005 xe90S-
`
`O1S
`
`
`
`
`
`
`
`Page 8 of 28
`
`Page 8 of 28
`
`
`

`

`
`
`US 6,614,845 B1
`
`Ob‘Sid
`
`
`
`LINVNODG
`
`
`Sheet 8 of 15
`
` iYAAV1HOO18.
`
`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`
`iY3AV1
`
`
`400187
`
`6‘Sis
`
`
`
`
`
`Page 9 of 28
`
`Page 9 of 28
`
`

`

`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 9 of 15
`
`
`
`US 6,614,845 B1
`
`
`
`
`
`
`490718
`viva
`gQAWw
`re
`SGAW
`
`caAW
`om
`LNVYNOG
`dodo
`€ia9
`
`
`
`
`
`LtOld
`
`QdON|OddOw
`
`
`
`=i
`
`w
`
`
`
`Page 10 of 28
`
`Page 10 of 28
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 10 of 15
`
`US 6,614,845 B1
`
`2Q
`
`O
`vt7
`
` FIG.14
`
`O
`
`occNecccecccceoseseceees
`
`SHHSHOHRSATHHSSHEHSSHSSHSHHSCESCHOHESHE
`SHSHCHHSOCHOSOKDHSSHEHOOHEHOSH HOSE HO
`SSCHSSHEHAISHOHSSEOCHRSSHSHSSSEHSHEHHSEOEH OS
`SCHOHSHSHHHSHHOSSTOHESSCOEHSSSHOTOHRESEHH HE
`SHOSHOHSHOHSSHHOHLSOOCHOSESSSEHSEHSECHEBEESD
`SSSSOSSEHRAESSSHESHSSOHSSOSHOSHSSESSSESES
`COSSHHEEEHOLEELSCHOHHHSEHHHEESHHBAEEES
`SSSSHSSSSHHSHESSSCHEHSSOH SESE EHEEBSE
`SSSCHOHSSSHSSSEHESSHOSSVEHDSESSOCEOSEE OSE
`SHSSSOSTOHSS SESS SHEHHSSCHSEHSESEHHOOEHS
`SOCEHHTEECCHEHECEE FHS HHHESCHFOHHHEEEHE
`SHRAACAHDESHTSSSSSSEHSHOTOOSHSESEOCE
`eonseenocasasvoossaeseeseooesessae
`SOHHOSSSEHHASHHOCATERSHHHOHHHHEOE OS
`SCeeSeSKOeesaoseasseeseseeseseeesse
`.
`exeeoceveoeoesneees
`eeeeoseenecenese
`soocenseseoacseogee
`soeesecoenosenee
`eceeeveoonsonese
`eserves ecoeseseee
`SOSH HOO BAOCOO HE
`esvosaesensoeone
`DOCH TOSEESSSH OE
`OOF O029ERBOOOO LE
`eocaeeseocerenaoeee
`evnecoceesseovece ee
`e8e00080980000000
`eeeocoecneoecece
`eeeoecaaosesesec
`eeeeeonengnonoeeoe oe
`
`FIG,13
`
`ma
`
`Page 11 of 28
`
`Page 11 of 28
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 11 of 15
`
`US 6,614,845 B1
`
`ooo0o0o00ce
`
`eoocoo0e
`
`"Oo0oo00000
`
`rooo0ooooe
`
`Nooo0000
`
`o7rooo00o
`Succco0e
`
`°a
`
`ry
`oo000000
`oooo0o00co090
`
`"Qooo0o0o0o
`
`ro0coo0oso
`
`Yoooo000o0
`MNOOCOCCEO
`Cm-coo0000
`
`oqooo00000s
`
`eOo0o000000
`
`Yoooooo°o
`
`rooocooo°os
`
`Noaoccco0o
`
`o7Too0o0o0o0o
`Sucooc0°o
`
`@a
`
`rTeeCOCoO
`C0000000
`eCoo00CCOoO
`
`“Oo0oo0o0o0o0o
`
`rOO00000O
`
`Noooco00
`
`MNDDOO0O
`Cam-o00000
`foi)
`aPuUDcC000
`
`FIG.15
`
`oooooo00°o
`
`ooo0o0000°o0
`
`“ooooooo
`
`-OO0C0000
`
`Yanooooo0o
`
`
`
`
`
`
`
`aTeooo0oeo
`Succc0ee
`
`B®uccD00acesseestecatesith00AAODTSsetSOSNDsahSnNGSSAEA)HHFOEDASEldSatuiktlhSSSmHYSMHHHP>ORDtrmhKYSHMETNhheyoNceArmeTceemeemthesmeermmSom
`
`
`
`
`
`
`MONDOOOCS
`oO
`Berreceoo
`On—-Puaoroo0o0
`
`
`
`oooocooco°o
`
`oo0eoocoo0cso
`
`~OQOoo0o0o0o0°o
`
`wr OO00000
`
`Noooo0c0c0eo
`
`oT ooo0o00o
`Fuoco e0°o
`BS TOGOCCO
`ecoece6o
`eooo0ooo00c0°o
`
`“"oOooooo0o0o
`
`roooo0coce
`
`Nooo0000
`
`MONOSODOCOCO
`
`tTHMHrOOCCCO
`
`oocooooSe
`
`oooo0o00°0°o
`
`eooo0o0o00°do
`
`ooo0o0ooco0°o
`
`TecCoOCOoOCO
`
`Tooooo0oo
`
`-O000000
`
`-OO000000
`
`VYoooo0000
`
`NYoooo0o00o0
`
`mTOCOOO0O
`
`=ENCOCOOO
`
`oT oo000so
`~nNoOoeOCO
`
`C0000000
`eoo000090o
`
`COO000000
`oo00000O0
`
`TOo0o0o0o00o0
`
`"oooo0oo0o
`
`roo00ooco
`
`rQO000000
`
`NYoonooo0c00o
`
`Yooo000do
`
`MNOCBCCO
`
`OnNr-COCOO
`© @HPNDOCOCTCSO
`
`MNOOCOOO
`Sm-co0000
`N oa'ynooondoae
`
`Page 12 of 28
`
`Page 12 of 28
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 12 of 15
`
`US 6,614,845 B1
`
`oooooo0o0°0
`
`ooooo00co
`
`ecooocoecoo
`
`ceoooceco
`
`cCocooCoCooSe
`
`ooooooc$dce
`
`cooco0oeo0nd
`
`ooooooe°ce
`
`ooooo0oeo
`
`oooooo0o°ce
`
`COCD0000
`
`ooooo0coeo0o
`
`eo0000c0cDo
`
`oooooo0°e
`
`PaocecocoOo
`OOO00000
`
`PaoDDOOCO”SO.
`
`ooo00000°0
`
`oo000000c00
`
`o0000000
`
`CoD0D000C0O
`
`OCOC0CD0000
`
`oo000000
`
`OD0000000
`
`oCO0000090
`
`eocoo0000N0
`
`eooco0co00Oo
`
`eCoo000000
`
`IN9r- OOCOOCS
`
`OOoD00000
`
`~7.ToOo0oco0oco
`
`MoaDOOCOCO0O
`
`FIG.16B
`
`FIG.16A
`
`oooocoooo
`
`C0000 CO0CSO
`
`CO000000
`
`Co0000CCOO
`
`CO000000
`
`eoo000000
`
`o2cccoceeo
`
`PaDeCD000
`COOOO0000
`
`COOC0C0O00O
`
`COO000000
`
`CODCC0CO
`
`Qoo000000
`
`eooc00000
`
`ooooooce
`
`nNnoocoo00co
`
`oooo0ecooo
`
`ooocoeo°o°o
`
`oo0ooo00°o
`
`eooo0oo0°]e
`
`ooooo0o9ceo
`
`“@C0000000
`
`wTooo00oeteetanepeeStHnehtelyAAAEDGDSEERANDONGETTGOTUESeSanMARDOWGUNDMRDGUEseeeeHenMaemGEDEDcoGEDOYtneGIPHONEem
`
`ecooo0c”dese
`
`~oaccccn
`©0000000
`
`oooo0ceo0oo
`
`ooooc”ooo
`
`oooo0o00°eo
`
`ooooo00°e
`
`ooooo°o00o°o
`
`wer OCOO0CS
`
`Page 13 of 28
`
`Page 13 of 28
`
`

`

`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 13 of 15
`
`
`
`US 6,614,845 B1
`
`
`
`rsfofetafufolelel-fs|=[*lelzlo| eases
`
`81‘Sid
`
`
`
`
`
`
`|s22]072]see]rooloseleee
`posesiprvioelecaleoedierolPelafelofelalalo
`
`
`
`266]3a)vee]evslac]ereve)veelwi]
`resoeee]
`
`JeyyBneg
`
`
`
`Zt‘Sid
`
`
`
`
`
`
`
`
`
`
`
`yuedled
`
`sBulaes
`
`Page 14 of 28
`
`Page 14 of 28
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 14 of 15
`
`US 6,614,845 B1
`
`0¢StOLSs
`
`
`
`T3A31NOLLVZILNYNO
`
`61‘Sis
`
`NVWS31VS
`
`
`
`NVWSYHOSYSHLOW
`
`YSLHONVGONY
`
`AINOHdYVO
`
`
`
`VOIHAWVSSIW
`
`ONIAVS%
`
`SLINI
`
`Page 15 of 28
`
`Page 15 of 28
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Sep. 2, 2003
`
`
`
`
`Sheet 15 of 15
`
`US 6,614,845 B1
`
`
`
`
`
`aguYVNS1LSVO9O
`
`
`
`AASNOILVZILNYND
`
`02
`
`clOlSs
`
`02‘Old
`
`
`
`YSNIVLNOO02ONIAYS%
`
`
`AIGNI
`
`Page 16 of 28
`
`Page 16 of 28
`
`
`
`

`

`
`
`US 6,614,845 B1
`
`
`1
`METHOD AND APPARATUS FOR
`
`
`
`
`DIFFERENTIAL MACROBLOCK CODING
`
`
`
`FOR INTRA-FRAMEDATAIN VIDEO
`
`
`
`
`CONFERENCING SYSTEMS
`
`
`
`
`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-4stan-
`
`
`
`
`
`
`
`dard will also incorporate the H.324/H.263 standard.
`
`
`
`
`
`
`All of these standards, however, focus more on temporal
`
`
`
`
`
`
`
`compression than spatial compression, mostlikely 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 techniquesfor 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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SUMMARYOF 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 improvementof
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`
`
`
`
`
`
`
`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 transmissionefficiency in theart of
`
`
`
`
`
`
`video conferencing. In the context of digital transmissions
`
`
`
`
`
`
`
`particularly, quality and efficiency issues are frequently
`
`
`
`
`
`
`
`
`intertwined. Over the years, the most commonsolution 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 methodsto
`
`
`
`
`
`
`
`
`reduce the redundancyof 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
`
`
`
`
`
`
`
`DCTto 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
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 17 of 28
`
`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
`
`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`Still another aspect of the invention includes a method of
`
`
`
`
`
`
`
`decoding. This method comprises a storing componentcon-
`
`
`
`
`
`
`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.
`
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`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 methodsuse 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 improvementin I-frame coding, an imple-
`
`
`
`
`
`
`
`mentation consistent with the invention provides for com-
`
`
`
`
`
`
`paring a coding macroblockto 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 componentto indicate the
`
`
`
`
`
`
`location of the reference macroblock. Alternatively, when
`
`
`
`
`
`
`
`there is an insubstantial difference between the coding
`
`
`
`
`
`
`macroblock and the reference macroblock, the methodis not
`
`
`
`
`
`
`
`used, and the difference componentindicates 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 (orslices 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 decodesthe video, audio, and data, and then
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`The accompanying drawings illustrate a preferred
`
`
`
`
`embodimentof 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
`
`
`
`
`
`
`arrangementof 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
`DCTvalues 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 exampleof the efficiency
`
`
`
`
`
`
`improvement gained by the claimed macroblock coding
`
`technique;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 18 of 28
`
`Page 18 of 28
`
`

`

`
`
`US 6,614,845 B1
`
`
`6
`
`
`
`
`
`
`
`
`pixelsper line, dy lines per picture in an orthogonalarrange-
`
`
`
`
`
`
`
`
`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.
`
`
`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
`
`
`
`
`
`
`
`
`
`Number of|Numberof Number of Number of
`
`
`
`
`
`
`
`
`
`
`common embodiment as a multimedia telephone terminal,
`pixels for
`lines for
`pixels for
`lines for
`
`
`
`
`
`
`
`
`luminance
`luminance
`chrominance
`chrominance
`
`
`
`
`
`
`
`
`terminal 30 provides for the transmission andreceiptof real,
`
`
`
`
`
`
`
`
`
`(dx)
`(dy)
`(dx2)
`(dy/2)
`live-time video, audio, or data, or any combination thereof,
`
`
`
`
`
`
`
`
`
`
`along with the necessary control codes.
`128
`96
`64
`48
`
`
`
`
`
`
`176
`144
`88
`72
`Each component of terminal 30 preferably implements
`352
`288
`176
`144
`
`
`
`
`
`
`
`
`certain functions dictated by the H.324 standard. Video
`704
`576
`352
`288
`
`
`
`
`
`
`
`
`
`codec 110, using either the H.263 or H.261 standard, carries
`1408
`1152
`704
`576
`
`
`
`
`
`
`
`
`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 whichis 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 andIP, 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 V.34 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 synchronousbit stream that is sent to
`
`
`
`
`
`
`the Multiplex/Demultiplex protocol unit. Modem control
`
`
`
`
`
`
`
`
`145, using the V.25 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 c