FI92272C - Kuvansiirtojärjestelmän tiivistyskoodausmenetelmä - Google Patents

Description

ς ο ·'· Γΐ ο j L- / £.

KUVANSIIRTOJÅRJESTELMAN TIIVISTYSKOODAUSMENETELMA

Keksinnon kohteena on patenttivaatimuksen 1 johdanto-osassa maåritelty kuvansiirtojarjestelmån 5 tiivistyskoodausmenetelma erityisesti tiivistyskoodauk-sen suorittamiseksi digitaalisessa kuvansiirtojarjes-telmassa.

Ennestaan tunnetaan vektorikvantisointi-menetelma (vector quantization, VQ) kuvan tiivistyskoo-10 daamiseksi. Vektorikvantisointimenetelmaå on kåsitelty laajasti viitejulkaisussa /1/. Vektorikvantisointi-menetelmåssa lahetettavå kuva jaetaan lohkoihin ja jokaiselle lohkolle etsitaan vektorikirjastosta sita lohkoa parhaiten vastaava esitysvektori. Taman esitys-15 vektorin vektori-indeksi eli paikka vektorikirjastossa lahetetåan siirtotielle. Vastaanottajapåassa esitysvek-torin vektori-indeksin perusteella poimitaan vastaavan-laisesta vektorikirjastosta asianomainen vektori. Lahe-tetty kuva rekonstruoidaan lohko lohkolta naiden esi-20 tysvektoreiden avulla. Vektorikirjasto muodostetaan etukateen harjoituskuvien avulla kåyttåen sopivaa vektorikir jaston muodostusalgoritmia. Harjoituskuvat on vastaavalla tavalla pilkottu kaytettyyn lohkokokoon vektorikirjastoa muodostettaessa.

25 Vektorikvantisointimenetelman haittana on ra- joitettu lohkokoko. Menetelman tehokkuus perustuu sii-hen tosiasiaan, etta kaikki tilastolliset riippuvuudet lohkon sisalla otetaan huomioon. Lohkorajojen ylittåvat riippuvuudet eivat tule huomioonotetuksi. Tavanomaises-30 sa vektorikvantisointimenetelmåsså ison mittakaavan riippuvuuksia voidaan hyodyntaa suuren kuvainformaation tiivistymisasteen saavuttamiseksi vain kåyttciinållå suurta lohkokokoa. Lohkokoon suurentaminen vuorostaan johtaa vektorikirjaston eksponentiaaliseen kasvuun, 35 mikali kuvan laatu pidetåan vakiona. Samalla kasvaa myos tehtavien vertailujen lukumåara parhaan esitysvek-torin loytamiseksi vektorikirjastosta. Nåin olien vek- 2

Q 9 r 7 O

y £ / δ.

torikvantisointimenetelmå muodostuu helposti epåkåy-tånnolliseksi ja laskenta-aikaa vaativaksi, kun kåytetåån suuria lohkokokoja. Tavallisesti lohkon koko on rajoitettu korkeintaan 4x4 pikseliin, jolloin suuri 5 osa lohkojen vålisistå tilastollisista riippuvuuksista jåå tallå menetelmållå hyodyntåmåttå.

Lohkojen koko-ongelma vektorikvantisoinnissa on kaksitahoinen. Toisaalta vektorikirjaston suuri koko itsessåån aiheuttaa ongelmia tallennuskapasiteetin 10 suhteen. Toisaalta tietojenkåsittelyaika lohkoa vastaa-van esitysvektorin loytåmiseksi kasvaa helposti liian pitkåksi. Useita vektorikvantisointimenetelmien muun-noksia on kehitetty nåiden ongelmien ratkaisemiseksi.

Erååsså modifioidussa vektorikvantisointimene-15 telmåsså, ns. puuhakuvektorikvantisointimenetelmåsså (tree search VQ) kåytetåån binååristå hakumenettelyå parhaan esitysvektorin loytåmiseksi ja nåin pyritåån pienentåmåån esitysvektorin hakuaikaa. Kuvan laadun kannalta tållå menetelmållå ei pååstå aivan niin hyviin 20 tuloksiin kuin tavanomaisella vektorikvantisointimene- telmållå.

Erååsså toisessa modifioidussa vektorikvan-tisointimenetelmåsså ns. kaskadivektorikvantisointi-menetelmåsså kåydåån kåsiksi suoraan tavanomaisen vek-25 torikvantisointimenetelmån pååongelmaan eli lohkoko- • koon. Tåsså menetelmåsså kåytetåån suhteellisen suurta lohkokokoa suuren mittakaavan korrelaatioiden hyodyntå-miseksi. Vektorikirjastot ovat kuitenkin kohtuullisen kokoisia ja nåin ne ovat helposti kåsiteltåviå. Tåstå 30 johtuvaa huonoa kuvan tarkkuutta pyritåån kompensoimaan siten, ettå menetelmåsså kåytetåån peråttåisiå koodaus-vaiheita. Kussakin myohemmåsså vaiheessa aikaisemman vaiheen koodivirhe kvantisoidaan. Epåkohtana on, ettå peråttåisten esitysvektorien vålillå mahdollisesti ovat 35 korrelaatiot menetetåån.

Erååsså kolmannessa modifioidussa vektorikvan-tisointimenetelmåsså, joka on edellå esitetystå kaska- 3 O r-70 J /L. ^ ! £_ divektorikvantisointimenetelmåstå kehitetty muunnos, lohkokokoa muutetaan ensimmåisestå koodausvaiheesta toiseen siirryttåesså. Koodivirhe, joka sisåltåå kuvan yksityiskohtia, koodataan kåyttaen hyvaksi osalohkoja.

5 Tallå menetelmållå vektorikirjaston niiden esitysvekto-rien lukumååråå, jotka tarvitaan pienten yksityiskoh-tien esittåmiseen, voidaan merkittåvåsti pienentåå, kun kåsitellåån pieniå lohkoja.

Eraasså neljånnesså modifioidussa vektorikvan-10 tisointimenetelmåsså ns. luokitellussa vektorikvan-tisointimenetelmåsså (classified VQ), lohkot luokitel-laan ennen koodausta. Luokittelu perustuu kuvan paikal-lisiin piirteisiin. Tåmå parantaa erityisesti reunavii-vojen esittåmistå, minka on havaittu toteutuvan suh-15 teellisen huonosti tavanomaisessa vektorikvantisointi-menetelmåsså. Kullekin lohkoluokalle on olemassa eril-linen vektorikirjasto. Suhteellisen pieni vektorikir-jasto riittåå, koska lohkot ovat luonteeltaan enemmån tai våhemmån samankaltaisia kussakin luokassa. Lohkojen 20 vålisiå korrelaatioita voidaan jonkin verran hyodyntåa, jos luokitteluprosessissa ei rajoituta lohkon alueelle.

Eraasså viidennesså modifioidussa vektorikvan-tisointimenetelmåsså, ns. åårellisten tilojen vektori-kvantisointimenetemåsså (finite state VQ) lohkojen 25 vålisiå korrelaatioita voidaan hyodyntåå edellå mainit-tuun luokitteluun perustuen. Tålloin lohkon luokka mååritellåån lohkokokoa isomman kuva-alueen sisållon avulla. Kuva-alueeseen kuuluu joukko toistensa låhellå olevia lohkoja, jotka on jo koodattu ja låhetetty.

30 Epåkohtana on, ettå luokitteluvirheet saattavat heiken-tåå kuvassa esiintyvien reunaviivojen koodaustulosta.

Eraasså kuudennessa modifioidussa vektorikvan-tisointimenetelmåsså ns. osoitevektorikvantisointi-menetelmåsså, (address VQ) kåytetåån hyvåksi lohkoryh-35 mien vektori-indeksien yhteisjakautumaa. Erityiset esitysvektorit, jotka on talletettu ns. osoitevektori-kirjastoon, on varattu vektori-indeksien todennåkoisim- 4 Q O ·':· 7 o S t- t- / £- mille yhdistelmille. Kaikilla muilla kombinaatioilla vektori-indeksit låhetetaån erikseen. Osoitevektorikir-jastoa paivitettaesså kåytetaan hyvåksi rinnakkaisten lohkojen vektori-indeksien eri yhdistelmien havaittuja 5 esiintymistodennåkoisyyksiå. Osoitevektorikirjasto muo- dostetaan vååristymåttomånå jålkikoodaustapahtumana tavanomaisen vektorikvantisointikoodauksen paaile ja tulokseksi saadaan samanlainen kuvanlaatu normaalia vektorikvantisointia alhaisemmilla bittinopeuksilla.

10 Keksinnon tarkoituksena on tuoda julki uusi kuvans iirtojarjestelman tiivistyskoodausmenetelmå, jolla tavanomaista vektorikvantisointimenetelmåå hait-taava rajoitetun lohkon ongelma voidaan ainakin osit-tain valttåå. Keksinnon tarkoituksena on edelleen saada 15 aikaan uusi tiivistyskoodausmenetelma, jonka avulla pyritaan valttamåan modifioituihin vektorikvantisointi-menetelmiin liittyvia ongelmia.

Keksinnon mukaiselle menetelmålle on tun-nusomaista se, mita on esitetty patenttivaatimuksessa 20 1.

Keksinnon mukaisessa kuvansiirtojarjestelmån tiivistyskoodausmenetelmåssa, erityisesti tiivistyskoo-dauksen suorittamiseksi digitaalisessa kuvansiirtojår-jestelmassa, kaytetaan hyvaksi vektorikvantisointi-25 menetelmåa, jossa kuva jaetaan lohkoihin lahetyspaåsså * ja jokaiselle lohkolle etsitåån vektorikirjastosta sitå lohkoa parhaiten vastaava esitysvektori, jonka vektori-indeksi eli paikka vektorikirjastossa låhetetaån vas-taanottopååhån, jossa indeksin perusteella poimitaan 30 identtisestå vektorikirjastosta asianomainen esitysvek tori ja kuva rekonstruoidaan lohko lohkolta esitysvek-torien avulla, joka vektorikirjasto muodostetaan etukå-teen harjoituskuvien avulla, jotka kuvat on vastaavalla tavalla jaettu kåytetyn lohkokoon mukaisiin lohkoihin.

35 Keksinnon mukaisesti menetelmåsså: - låhetyspååsså koodattava lohko jaetaan neljånnesloh-koihin eli osalohkoihin; 5 w V ' / o S £. <- t - kullekin osalohkolle suoritetaan vektorikvantisointi, jossa kåytetåån luokiteltua vektorikirjastoa, jonka luokka mååråytyy alkuperåisen lohkon vektori-indeksin ja osalohkon paikkaindeksin perusteella; 5 - osalohkon vektori-indeksi tamån luokltellun vektori kir jaston suhteen låhetetåån vastaanottopååhån; - vastaanottopååssa kaytetåan luokiteltua vektorikir-jastoa, joka valitaan siirretyn alkuperåisen lohkon vektori-indeksin ja osalohkon paikkaindeksin perus- 10 teella; - vastaanottopååsså valitusta luokitellusta vektorikir-jastosta, joka on identtinen låhetyspååsså luokitel-lun vektorikirjaston kanssa, asianomainen esitysvek-tori poimitaan låhetetyn osalohkon vektori-indeksin 15 perusteella, jolloin osalohkolle saadaan rekonstruk- tio; ja jossa menetelmåsså kutakin luokiteltua vektorikirjastoa muodostettaessa harjoituskuva-aineistona kåytetåån asianomaiseen luokkaan kuuluvaa osaa alkuperåisestå 20 harjoituskuva-aineistosta eli niitå neljånneslohkon kokoisia harjoituskuvajoukon osalohkoja, jotka saavat kirjaston luokkaa vastaavan luokitteluindeksin, kun edellå esitettyå menetelmåå sovelletaan harjoituskuva-joukkoon itseenså.

25 Keksinnon mukaisessa menetelmåsså vektorikvan- • tisointia sovelletaan peråkkåin alkaen sopivasti vali tusta lohkokoosta ja edeten sen neljånneslohkoihin. Jålkimmåisesså vaiheessa suoritettu vektorikvantisointi hyodyntåå suuremmassa lohkokoossa jo koodattua infor-30 maatiota ns. luokittelun avulla. Luokan måårååvånå indeksinå kåytetåån ensimmåisen kvantisoinnin tuloksena saatua vektori-indeksiå sekå neljånneslohkon paikkain-deksiå.

Keksinnon erååsså sovellutuksessa neljånnes-35 lohko eli osalohko jaetaan edelleen neljånnesosalohkoi-hin ja nåmå edelleen samalla periaatteella yhå pienem-piin lohko-osiin, jossa kukin neljånnesosalohko ja 6 o o π o S / £.

lohko-osa koodataan luokitellulla vektorikirjastolla, jossa luokittelijoina ovat kyseisen neljannesosalohkon tai lohko-osan niiden kaikkien emolohkojen vektori-indeksit, joihin koodattava neljannesosalohko tai loh-5 ko-osa kuuluu ja kyseisen neljannesosalohkon tai lohko-osan sekå mainittujen emolohkojen paikkaindeksit ja jossa luokitellut vektorikirjastot muodostetaan etukå-teen edellå esitettyyn tapaan.

Edellå esitetyssa menetelmåsovellutuksessa 10 vektorikvantisointia sovelletaan edeten sopivasti vali-tusta lohkosta, so. lohkokoosta, sen neljånneslohkoi-hin, nåiden neljånneslohkoihin jne. haluttuun syvyyteen asti. Kullakin lohkotasolla suoritetaan vektorikvanti-sointi, jossa hyodynnetåan suuremmassa lohkokoossa jo 15 koodattua informaatiota luokittelun avulla, jossa luo-kan måaråavina indekseina kåytetaån aikaisempien kvan-tisointien tuloksina saatuja vektori-indekseja seka vastaavia paikkaindeksejå. Koodausta jatketaan haluttuun syvyyteen asti niin pitkalle kuin kåytettåvisså 20 oleva siirtokanavan bittinopeus sallii tai kun kuvan laatu muutoin on riittåvå. Keksinnon mukaisessa hierar-kisessa luokitellussa vektorikvantisointimenetelmasså kuva siis tarkentuu vaiheittain suhteellisen pienen lisåinformaation avulla.

25 Menetelman eraasså sovellutuksessa ennen kuta- * kin keksinnolle ominaista kuvalohkon neljånneslohkoja- koa suoritetaan kuvalohkon rekonstruointi siihen asti koodatun informaation perusteella ja muodostetaan kuvalohkon ja rekonstruoidun kuvalohkon vålinen erotus, 30 joka erolohko siis sisaltåa viimeksi suoritetun koo-dausvaiheen koodausvirheet, ja sovelletaan keksinnon mukaista menetelmaå kuvalohkon sijasta nåin muodostet-tuun erolohkoon. Erolohko jaetaan neljånneslohkoihin, jotka vektorikvantisoidaan hyodyntåmalla suuremmassa 35 lohkokoossa jo koodattua informaatiota luokittelun avulla. Luokitellut vektorikirjastot muodostetaan keksinnon mukaisen menetelman tavoin kayttamalla harjoi-

II

q o ·' 7 o J /-i- i ά.

tusaineistona niitå erolohkon osalohkoja, jotka saavat vastaavat luokitteluindeksit kuin koodattava erolohkon osalohko, kun menetelmåå sovelletaan harjoituskuvajouk-koon itseenså.

5 Edella esitetyn sovellutuksen etuna on, etta erosignaali on kompaktimpi eli erolohkon sisåltåmåt arvot vaihtelevat rajoitetummalla alueella kuin varsi-naiset kuvasignaalin arvot, mikå tehostaa koodausta. On kuitenkin todettava, etta suuremmassa lohkokoossa koo-10 dattu informaatio kuvaa huonommin erolohkon ominaisuuk-sia, minka vuoksi keksinnon mukaiselle menetelmålle ominaisen luokittelun hyoty ja koodauksen tehokkuus pienenevat. Erosignaalia koodaavan sovellutuksen toteu-tus on myos hieman monimutkaisempi.

15 Menetelman erååsså sovellutuksessa ensimmåi- sella lohkotasolla koodausta tehostetaan poistamalla ennen koodauksen suorittamista kuvan kunkin lohkon sisåltåmien kuvapisteiden harmaasåvyarvojen keskiarvo ja lahettåmållå keskiarvo erikseen låhetyspååsta vas-20 taanottopaahan.

Menetelman eraasså sovellutuksessa kuvalle suoritetaan låhetyspååsså alipååstosuodatus ja nåin suodatettu kuva låhetetåån erikseen vastaanottopååhån, ja vain kuvan suurtaajuuskomponenttiin eli alkuperåisen 25 kuvan ja alipååstdsuodatetun kuvan erokuvaan sovelletaan jotain edella esitettyå menetelmaa tai sen sovel-lutusta. Matalataajuuskomponentti sisåltåå kuvan tår-keimmån osan ja sen siirtåmiseksi tarvitaan våhån in-formaatiota ja våhån kanavakapasiteettia. Nåin kuvan 30 lohkoisuus våhenee erityisesti "sileillå" alueilla, so. alueilla, jotka sisåltåvåt våhån muutoksia.

Menetelmån erååsså sovellutuksessa osalohkojen ja mahdollisesti niitå pienempien lohko-osien koodaami-sessa kåytettyjen vektorikirjastojen kokoa vaihdellaan 35 tapauskohtaisesti koodatun lohkon kuvasisållon perus-teella siten, ettå våhån yksityiskohtia sisåltåvien lohkojen koodauksessa kåytetåån pienempiå vektorikir- 8 Ο Ο 7 ο s / 2.

jastoja kuin paljon yksityiskohtia sisåltavien lohkojen koodauksessa, jolloin tieto vektorikirjaston koosta låhetetåån lisåinformaationa.

Menetelman erååsså sovellutuksessa osalohkojen 5 ja raahdollisesti niitå pienempien lohko-osien koodaami-sessa kaytettyjen vektorikirjastojen kokoa vaihdellaan koodatun lohkon kuvasisallon perusteella siten, etta våhån yksityiskohtia sisåltåvien lohkojen koodauksessa kåytetåån pienempiå vektorikirjastoja kuin paljon yksi-10 tyiskohtia sisåltavien lohkojen koodauksessa, ja vekto-rikirjaston koko mååritetåån kiinteåsti luokitteluin-deksin perusteella. Tålloin ei låhetetå lisåinformaa-tiota, vaan valinta tapahtuu automaattisesti.

Keksinnon eduista toteamme seuraavaa. Keksin-15 non mukaisessa menetelmåsså hyodynnetåån kuvassa esiin-tyviå suuren mittakaavan korrelaatioita. Tåmå perustuu sopivasti valittuun suureen aloituslohkokokoon. Mene-telmå on lisåksi tarkkuudeltaan muunneltavissa halutul-la tavalla, koska kuva koodataan useassa vaiheessa 20 alkaen suhteellisen suuresta lohkosta, joka peråttai-sesti jaetaan yhå pienempiin lohko-osiin. Mitå useampia lohko-osia koodataan sitå tarkemmaksi kuva tållå alu-eella saadaan. Edelleen keksinnon etuna on, etta se on erittåin tehokas ja tulokseksi saadaan subjektiivisesti 25 arvioituna laadultaan hyvå kuva. Edelleen keksinnon etuna on, etta menetelmåå on suhteellisen helppo sovel-taa ja sillå pååståån alhaisiin siirtonopeuksiin.

Seuraavassa keksintoå ja sen muita etuja se-lostetaan oheiseen piirustukseen viittaamalla, jossa 30 kuva 1 esittåå kaaviomaisesti vektorinkoodausmenetel-måå; j a kuvat 2a, 2b ja 2c esittåvåt kaaviomaisesti kuvan lohkon jakamista lohko-osiin keksinnon mukaisessa tiivis-tyskoodausmenetelmåsså; 35 kuva 3 esittåå lohkokaaviona eråstå keksinnon mukaisen tiivistyskoodausmenetelmån mukaista kooderia; kuva 4 esittåå vastaavasti dekooderia; ja

II

9 G O η η ο S £-<- / ά.

kuva 5 esittaa toista keksinnon mukaisen tiivistyskoo-dausmenetelmån mukaista kooderia.

Vektorikvantisoinnin periaatetta on havainnol-listettu kuvan 1 lohkokaaviolla. Kameralta, kuten vi-5 deokameralta, saatu kuva 1 tallennetaan kuvamuistiin 2. Kuva 1 on muodostettu n x m kuva-alkiosta eli pikselis-ta (n, m = kokonaisluku). Sopivan kasittely-yksikon 3 avulla kuvamuistiin 2 tallennettu kuva 1 jaetaan loh-koihin 4 eli vektoreihin. Tyypillinen lohkon 4 koko on 10 4x4 pikselia. Kukin pikseli sisaltaa harmaasavytiedon ennalta mååråtyllå harmaasavyasteikolla. Kåsittely-yksikossa 3 kullekin kuvan lohkolle 4 etsitaån sita parhaiten vastaava esitysvektori 7a vektorikirjasto-muistiin 5 tallennetusta vektorikirjastosta 6. Vektori-15 kirjasto 6 on laadittu etukateen harjoituskuvien avulla kåyttaen sopivaa vektorikirjaston muodostusalgoritmia esim. ns. LBG-algoritmia /2/. Esitysvektorin 7a jarjes-tysluku a vektorikirjastossa 6 eli vektori-indeksi låhetetåan siirtokanavan 8 kautta lahetysyksikostS A 20 vastaanottoyksikkoon B.

Kuva rekonstruoidaan vastaanottoyksikon B kuvamuistiin 9 hakemalla kuvankåsittely-yksikon 10 avulla vektori-indeksin a mukainen esitysvektori 7a vektorikirjaston muistiin 11 tallennetusta vektorikir-25 jastosta 12. Kun kaikki kuvaan 1' kuuluvat lohkot 4' on saatu koottua esitysvektoreina kuvamuistiin 9, se voi-daan esittaa monitorilla.

Keksinnon mukaisessa kuvansiirtojarjestelman tiivistyskoodausmenetelmåsså kåytetåan hyvåksi edellå 30 esitettyå vektorikvantisointimenetelmåå. Tatå on ha- vainnollistettu kuvan 3 lohkokaaviolla. Lohkon kooksi valitaan suurempi lohkokoko kuin tavanomaisessa vekto-rikvantisoinnissa. Tyypillisesti lohkon 13 (vrt. kuva 2a) koko on esim. 8x8 pikselia. Lohko koodataan en-35 simmaisessa vaiheessa ensimmaisessa osakooderissa 16 sellaisen ensimmaisen vektorikirjaston 17 avulla, jossa on suhteellisen pieni esitysvektorikanta. Ensimmaisia 10

G 9 ·' 7 O

S i- i L· esitysvektoreita 18 on esim. 64 kappaletta. Esitysvek-torin 18 koko vastaa lohkon 13 kokoa ja on esim. 8x8 pikselia. Tama merkitsee sita, ettå kuva voidaan hah-mottaa tåsså koodausvaiheessa ainoastaan karkeasti eli 5 ainoastaan kuvan pientaajuisten komponenttien sisaltå-måt peruspiirteet voidaan tunnistaa.

Lohkot 13 jaetaan seuraavassa vaiheessa nel-jånneslohkoihin 14 eli osalohkoihin 14A’, 14B', 14C ja 14D', kuten kuvassa 2b on havainnollisesti esitetty.

10 Kunkin osalohkon 14 koko on talloin esim. 4x4 pikselia. Kukin osalohko 14 koodataan toisessa osakooderissa 19 toisen vektorikirjaston 20, joka muodostuu joukosta luokiteltuja vektorikirjastoja, avulla kåyttåen luokit-telijana alkuperaisen lohkon 13 vektori-indeksiå i ja 15 osalohkon 14 paikkaindeksia A', B', C, D' eli sijain-tia alkuperaisen lohkon 13 sisalla. Osalohkon 14 koo-daamiseen kåytetåan siis luokiteltujen vektorikirjasto-jen 20 joukosta sita, joka mååråytyy alkuperaisen lohkon 13 kunkin neljanneksen 14 paikkaindeksin ja kunkin 20 alkuperaisen lohkon 13 vektori-indeksin i perusteella. Alkuperaisen lohkon 13 avulla loydetty ensimmåinen esitysvektori 18 måårittelee kuvan karkeat piirteet sen kussakin lohkossa ja toiset esitysvektorit 21 toisista vektorikirjastoista 20 tarkentavat kuvaa osalohkojen 14 25 osalta. Toisen esitysvektorin 21 koko vastaa osalohkon * 14 kokoa ja on esim. 4x4 pikselia. Suhteellisen våhån lisainformaatiota tarvitaan nåin olien kuvan yksityis-kohtien koodaamiseen, silla luokitellussa vektorikir-jastossa 20 riittåå suhteellisen pieni lukumååra esi-30 tysvektoreita.

Keksinnon mukaista menetelmåa voidaan soveltaa edelleen ottamalla seuraavassa vaiheessa edella esite-tyssa koodausprosessissa saadut osalohkot 14A', 14B', 14C ja 14D' uudeksi alkulohkoksi ja toistamalla esi-35 tetty menettely kunkin osalohkon 14 neljHnneslohkoille 15A, 15B, 15C ja 15D (kuva 2c). Kukin nåistå uusista osalohkoista 15 sisåltaå talloin esim. 2x2 pikselia.

li 11 92172

Pienet lohko-osat 15 koodataan kolmannessa osakooderis-sa 22 vektorikvantisointimenetelmåå kåyttåen siten, etta kolmannesta vektorikirjastosta 23, joka muodostuu joukosta luokiteltuja vektorikirjastoja, etsitåan 5 sopiva kolmas esitysvektori 24. Alkuperåisen (esim. 8 x 8 pikselin) lohkon 13 ja sen (esim. 4x4 pikselin) osalohkon 14, johon uudet lohko-osat 15A, 15B, 15C ja 15D kuuluvat, vektori-indeksit i, j yhdesså lohko-osan 15 ja osalohkon 14 paikkaindeksien kanssa måårååvåt 10 mitå kyseisista kirjastoista 23 kaytetåan esitysvekto-rin 23 loytåmiseksi. Nåmå luokitteluindeksit sisåltåvåt kaiken sen informaation, joka on tåhån vaiheeseen men-nesså saatu eristetyksi lohkon kuvasisållostå. Kukin kolmas vektorikirjasto 23 sisåltåå suhteellisen pienen 15 lukumåårån esitysvektoreita, joiden lukumåårå on yleen-så rajoitetumpi kuin edellisesså koodaustasossa kåytet-tyjen vektorikirjastojen 17, 20 koko. Nåin saadaan to-teutetuksi hierarkinen koodausmenettely, jossa kuvan alkuperåiset suhteellisen suuret lohkot voidaan esittåå 20 vaiheittain kasvavalla tarkkuudella.

Låhetyspååsså koodattu ja edelleen siirtotiel-le låhetetty kuva kootaan vastaanottopååsså yksinker-taisella kåånteisellå dekoodausmenetelmållå, joka on esitetty lohkokaaviona kuvassa 4. Vastaanottopåån yh-25 distetty vektorikirjasto 24 sisåltåå identtiset låhe-tyspåån vektorikirjastoihin 17, 20, 22 nåhden identtiset vektorikirjastot. Kuvan varsinaiseen kokoamiseen kåytetåån alimman tason vektorikirjastojen 23 esitysvektoreita 23. Kuva kootaan lohko kerrallaan rekonst-30 ruointiyksikosså 25 ja siirretåån eteenpåin kuvan koko-amiseksi lohkoista kuvaksi sinånså tunnetulla tavalla. Kunkin esitysvektorin 23 mååråå tåysin sen oma vektori-indeksi k luokitteluvektori-indeksin j, i ilmaisemassa vektorikirjastossa. On huomattava, etta ainoastaan 35 hierarkiset vektori-indeksit i, j tåytyy låhettåå; neljånnesten tunnukset eli paikkaindeksit mååråytyvåt automaattisesti kooderin ja dekooderin vålisestå synk- 12

Q O r' 7 O 7 L

ronoinnista. Vektori-indeksi, joka låhetetåån tietyllå tasolla, on yhteinen sen neljålle osalohkolle ja kaik-ille niitå seuraaville lohko-osille.

Kuvissa 3 ja 4 esitetaån katkoviivoin merki-5 tyisså lohkoissa koodauksen ja dekoodauksen tehostamis-ta keskiarvoistamisen avulla. Låhetyspååsså (kuva 3) ensimmåisellå lohkotasolla esim. 8x8 pikselin alku-lohkojen keskiarvo m lasketaan keskiarvoistusyksikossa 26 ja se våhennetåån kustakin låhetettåvåstå lohkosta 10 erotusyksikosså 27. Keskiarvolla tarkoitetaan kunkin lohkon sisåltåmien kuvapisteiden harraaasåvyjen keskiar-voa. Keskiarvo in låhetetåån lukuarvona siirtotielle ja edelleen vastaanottopååhån. Lohkojen erotus eli jåån-noslohkot koodataan ja vastaavasti dekoodataan keksin-15 non mukaisella menetelmållå. Vastaanottopååsså (kuva 4) keskiarvon mukainen lohko rekonstruoidaan keskiarvoloh-kon rekonstruointiyksikosså 30 ja se summataan sum-mausyksikosså 29 dekoodattuna jåånnoslohkoon.

Erås keksinnon mukainen tiivistyskoodaus-20 menetelmån sovellutus on esitetty kuvassa 5. Tåsså sovellutuksessa ennen kutakin keksinnolle ominaista kuvalohkon neljånneslohkojakoa (vert. kuvat 2a, 2b, 2c) suoritetaan kuvalohkon rekonstruointi osakooderissa 16, 19 siihen asti koodatun informaation perusteella. Kuva-25 lohkon ja rekonstruoidun kuvalohkon vålinen erotus eli erotuslohko muodostetaan erotusyksikosså 28, 29. Ero-lohko siis sisåltåå viimeksi suoritetun koodausvaiheen koodausvirheet. Erolohkoon sovelletaan keksinnon mu-kaista menetelmåå edellå esitetyllå tavalla kuvalohkon 30 sijasta. Kuvassa 5 kooderin eri yksikdistå on kåytetty samoja viitenumeroita kuin aiemmin kuvan 3 yhteydesså. Dekoodaaminen toteutetaan vastaanottopååsså periaat-teessa kåånteisenå toimenpiteenå koodausprosessiin nåhden.

35 Keskiarvoistamista voidaan soveltaa myos edel lå esitettyyn keksinnon mukaiseen menetelmåån, kuten : kuvasta 5 kåy ilmi. Keskiarvoistusyksikko 26 ja ero-

II

o O '' -7 o J Li- i 13 tusyksikko 27 on sovitettu koodausjarjestelyyn ennen varsinaista edella esitetyn menetelmån mukaista koodaus jar jestelya . Dekoodaus toteutetaan periaatteessa samalla tavalla kuin kuvan 4 sovellutuksessa.

5 Tavanomaisessa vektorikvantisointimenetelmåsså vektorikirjasto muodostetaan kåyttåmållå tilastollises-ti edustavien harjoituskuvien laajaa joukkoa. Yleisesti tunnettua LBG-algoritmia voidaan kåyttåå vektorikir-jastoa muodostettaessa. Keksinnon mukaisessa tiivistys-10 koodausmenetelmåsså vektorikirjastot 17, 20, 23 muodostetaan hierarkisesti etenemållå siten, ettå kutakin luokiteltua kirjastoa muodostettaessa harjoituskuva-aineistona kaytetåan kyseiseen luokkaan kuuluvaa osaa alkuperaisestå harjoituskuva-aineistosta.

15 Ensimmåinen vektorikirjasto 17 muodostetaan ylimmålle tasolle tavanomaisella tavalla kåyttaen alku-peråiseen lohkokokoon (esim. 8x8 pikselia) jaettujen harjoituskuvien lohkojen joukkoa. Kukin vektorikirjas-toista 20 muodostetaan seuraavalla tasolla kåyttåmållå 20 alkuperåisten harjoituskuvien lohkoja, jotka koodataan ensimmaista vektorikirjastoa kayttåmalla ja ryhmitel-låån eri joukkoihin tulokseksi saatujen vektori-indek-sien mukaisesti. Lohkot kussakin joukossa jaetaan tamån jålkeen neljaan neljannekseen (eli osalohkoihin kuten 4 25 x 4 pikselia) muodostamaan nelja erillistå osajoukkoa A’, B’, C, D*. Kullakin osajoukon A’-lohkon lohkolla on sama luokitteluvektori-indeksi ja paikkaindeksi. Nain saatuja osajoukkoja kaytetaån harjoitusaineistona kyseisille vektorikirjastoille 20.

30 Edella esitettyå vektorikirjastojen muodostus- menettelya voidaan jatkaa samalla tavalla jakamalla jo muodostetut harjoituskuvien osajoukot edelleen pienem-piin osajoukkoihin luokittelemalla ne viimeksi saatujen vektorikirjastojen avulla ja jakamalla neljanneslohkoi-35 hin. Kutakin uutta osajoukkoa kaytetåan uuden vektori-kirjaston harjoitusaineistona seuraavaksi alemmalla tasolla.

14 0 0 ' 70 S / L·

Keksinnon mukaista tiivistyskoodausmenetelmåå tarkastellaan seuraavassa analyyttisesti. Ensiksi måå-ritellåån, etta allimnan tason lohkoa kutsutaan perus-lohkoksi ja sen kooksi oletetaan N x N pikseliå. Lohko-5 jen hierarkiatasoja merkitaan indeksillå h. Tåmå indek-si h voi olla valilla 1 (alin taso) ja L (ylin taso). Tason h (h = 1,..., L) lohko kuuluu lohko-osana seuraa-vaksi ylemmån tason h + 1 lohkoon. Kyseessa olevaa neljånneslohkoa merkitaan tunnuksella ah, joka voi saada 10 minkå tahansa neljasta arvosta A’, B1, C ja D' (vert. kuva 2) .

Koodausprosessia harjoitetaan hierarkisesti. Tasolla h aikaisempien kvantisointi-indeksien ja paik-kaindeksien koko ketju on: 15 (1) ch = (iL; α£,_!/ -ίχ,-χ/* · · ·; ja se muodostaa yhdistetyn luokitteluindeksin. Lohko-taso h vektorikvantisoidaan kåyttåen luokan ch mukaista vektorikirjastoa. Tulokseksi saatu indeksi ih yhdesså luokitteluindeksin ch kanssa maårittSa yhdistetyn vekto-20 ri-indeksin: (2) kh - (iL; Λχ,.χ/ Il-i' · · * ah> i-h) · joka tåysin mååraa taman tason koodaustuloksen. Tåmå osalohkon yhdistetty vektori-indeksi ja seuraavaksi alemman tason neljanneksen paikkaindeksi toimivat jal-25 leen luokittelijana c tålle alemman tason neljånnek-selle jne.

Oletetaan, ettå luokitellun vektorikirjaston koko tasolla h on I (so. i = 1,..., I ). Tålldin tarvi-taan b = log, (Ik) bittiå indeksin i_ arvon vålittåmi-30 seen låhetyspååstå siirtokanavan kautta vastaanotto-pååhån. Kuten edellå todettiin neljånneslohko-osien paikkaindekseja ei siirretå, koska ne tunnetaan låhe-

II

15 g o π ο 7 L· ^ / ζ.

tyspåån koodausyksikon ja vastaanottopåan dekoodausyk-sikon synkronoinnin perusteella. Lohkon vektori-indek-sin i arvo tasolla h on yhteinen sen alalohkoille ja kaikille sita seuraaville lohko-osille. Nåin olien koko 5 tiedonsiirtoprosessin bittinopeus alimmalle tasolle asti ilmaistuna bittien lukumåårånå peruslohkoa kohti (N x N pikseliå) on: (3) R = ^ + 4^2 + · · + —ThL = Σ —'

Koska vektori-indeksien ih kaikki arvot eivåt ole yhtå 10 todennåkoisia, todellista informaation siirtonopeutta voidaan edelleen pienentåå entropiakoodauksella. Entropia voidaan laskea olettamalla vektori-indeksin ih ilmaisemiseen tarvittavan koodisanan pituudeksi luokas-sa cw: n 15 (4) bh(kh) = -log2P(ih\ch) , jossa P(ijch) antaa (ehdollisen) todennåkoisyyden vek-tori-indeksille i, tasså luokassa. On huomattava, ettå kullakin tasolla lisåinformaatio, joka tarvitaan siir-tåmaån lohkon vektori-indeksi, riippuu sekå indeksista 20 itsestaan ettå lohkon luokasta so. tåmån lohkon koko yhdistetysta vektori-indeksistå kh-

Oletetaan, etta kx on eraan alimman tason lohkon yhdistetty vektori-indeksi. Tåman lohkon koko-naisinformaation måårå on tålloin: 25 (5) R.a,) = b.ik,) * |b2<Jc2> * ... * j-LbL(kL) = Σ jossa kh nyt merkitsee indeksiå k rajoitettuna tasolle h asti (vrt. kaava 2). Keskimååråinen kokonaisbit-tinopeus (entropia) on silloin (6) 16 00070 S L· L- i L·

Re = ΣΡ«ΐ'*Μ · ki

Alimman tason yhdistettyjen vektori-indeksien kx toden-nåkoisyysjakautuma P(kx) voidaan estimoida indekslen esiintymistodennåkoisyyksistå harjoituskuvajoukossa 5 talla menetelmållå koodattuna.

Keksinnon mukainen tiivistyskoodausmenetelmå voidaan ymmårtåå erityisena luokitteluprosessina alku-peraisen kuvalohkon (esim. 8x8 pikseliå) sisållå, johon prosessiin on yhdistetty varsinainen koodausvaihe 10 eli alimman tason lohko-osien (esim. 4x4 tai 2x2 piksel in lohko-osat) kvantisointi. Keksinnon mukaisessa tiivistyskoodausmenetelmåsså kåytetåån luontevasti hyvåksi aikaisemmin saatuja kvantisointituloksia. Tar-vetta ei ole etsiå mitåån erityisiå kriteerejå eri 15 luokkien valitsemiseksi.

Keksinnon mukaisella tiivistyskoodausmenetel-mållå ja puuhakuun perustuvalla vektorikvantisointi-menetelmållå (tree search VQ) on samankaltaisia piir-teitå. Puuhakuvektorikvantisointimenetelmåsså peråk-20 kåisten koodausten tulokset (puun oksat) måårååvåt seuraavassa vaiheessa kåytettåvån vektorikirjaston. Olennainen ero keksinnon mukaisen menetelmån ja maini-tun puuhakumenetelmån vålillå on, ettå puuhakumenetel-måsså lohkojen koko on kiinteå ja pysyy samana koko 25 koodausprosessin ajan, kun taas keksinnon mukaisessa menetelmåsså kussakin vaiheessa siirrytåån yhå pienem-piin lohko-osiin koodauksen edetesså.

Puuhakuvektorikvantisointimenetelmåsså pyri-tåån etupååsså pitåmåån koodausaika kohtuullisena, 30 mutta siinå tarvitaan hyvin laajaa vektorikirjastoa, kun kåytetåån suurta lohkokokoa ja pyritåån hyvåån lopputulokseen eli korkealaatuiseen kuvaan. Keksinnon mukaisen menetelmån etuna on nopeus, joka saavutetaan li 17 Q 9r: n o s w / z.

hierarkiatasoihin perustuvalla koodauksella. Edelleen etuna on, etta vektorikirjastojen esitysvektorien luku-raaårat voidaan pitaa kohtuullisena, mika johtuu kuvan yksityiskohtien koodaamisesta hierarkiatasoittain pie-5 nenevilla lohkokoilla. Toisaalta voidaan todeta, etta keksinnon mukaisessa tiivistyskoodausmenetelmåsså kay-tetåan hyvaksi hyvan lopputuloksen saamiseksi myos kuvassa esiintyvia suuren mittakaavan korrelaatioita aloittamalla koodaus suuresta lohkokoosta.

10 Edella keksintoa on selostettu låhinna vain sen yhteen edulliseen sovellutusmuotoon viittaamalla, mutta on selvaa, etta keksintoa voidaan monin tavoin muunnella oheisten patenttivaatimusten puitteissa.

15

Viitejulkaisuja: /1/ H. Abut, ed., "Vector Quantization", IEEE Press, 20 1990.

/2/ Y. Linde, A. Buzo, R.M. Gray, "An Algorithm for

Vector Quantization for Image Coding", IEEE Trans. Comm., vol. COM-28, pp. 2301-2304, 1991.

Claims (7)

18 g o r π η //Li. / /L

1. Kuvansiirtojårjestelmån tiivistyskoodaus-menetelmå erityisesti tiivistyskoodauksen suorittami-5 seksi digitaalisessa kuvansiirtojårjestelmåsså, jossa menetelmåsså kaytetaan hyvaksi vektorikvantisointimene-telmåå, jossa kuva jaetaan lahetyspaassa lohkoihin ja jokaiselle lohkolle etsitåan vektorikirjastosta sita lohkoa parhaiten vastaava esitysvektori, jonka vektori- 10 indeksi eli paikka vektorikirjastossa lahetetåan vas-taanottopååhån, jossa indeksin perusteella poimitaan identtisesta vektorikirjastosta asianomainen esitysvektori ja kuva rekonstruoidaan lohko lohkolta esitysvek-torien avulla, joka vektorikirjasto muodostetaan etukå- 15 teen harjoituskuvien avulla, jotka kuvat on vastaaval-la tavalla jaettu kåytetyn lohkokoon mukaisiin lohkoihin, tunnettu siita, etta menetelmasså: - lahetyspaassa koodattava lohko jaetaan neljannesloh-koihin eli osalohkoihin (14A', 14B', 14C ja 14D'); 20. kullekin osalohkolle suoritetaan vektorikvantisointi, jossa kaytetaan luokiteltua vektorikirjastoa (20), jonka luokka maaraytyy alkuperaisen lohkon vektori-indeksin (i) ja osalohkon paikkaindeksin (A', B', C, D') perusteella; 25. osalohkon vektori-indeksi (j) tamån luokitellun vek torikir jaston (20) suhteen lahetetåån vastaanottopåa-han; - vastaanottopaasså kaytetaan luokiteltua vektorikir-jastoa, joka valitaan siirretyn alkuperaisen lohkon 30 vektori-indeksin (i) ja osalohkon paikkaindeksin perusteella; - vastaanottopaasså valitusta luokitellusta vektorikir-jastosta (24), joka on identtinen lahetyspaassa luokitellun vektorikirjaston kanssa, asianomainen esi- 35 tysvektori poimitaan låhetetyn osalohkon vektori- indeksin perusteella, jolloin osalohkolle saadaan rekonstruktio; ja II G O n o -/ Δ. <_ / ^ 19 jossa menetelmåsså kutakin luokiteltua vektorikirjastoa muodostettaessa harjoituskuva-aineistona kåytetåån asianomaiseen luokkaan kuuluvaa osaa alkuperåisestå harjoituskuva-aineistosta eli niitå neljånneslohkon ko-5 koisia harjoituskuvajoukon osalohkoja, jotka saavat kirjaston luokkaa vastaavan luokitteluindeksin, kun edella esitettyå menetelmåå sovelletaan harjoituskuva-joukkoon itseensa.

2. Patenttivaatimuksen 1 mukainen menetelmå, 10 tunnettu siitå, ettå osalohkot jaetaan edelleen neljånnesosalohkoihin ja nåmå edelleen samalla periaat-teella yhå pienempiin lohko-osiin, jossa kukin neljån-nesosalohko ja lohko-osa koodataan luokitellulla vektorikir jastolla, jossa luokittelijoina ovat kyseisen 15 neljannesosalohkon tai lohko-osan niiden kaikkien emo-lohkojen vektori-indeksit, joihin koodattava neljan-nesosalohko tai lohko-osa kuuluu, ja kyseisen neljan-nesosalohkon tai lohko-osan sekå mainittujen emolohko-jen paikkaindeksit, ja jossa luokitellut vektorikirjas-20 tot muodostetaan etukåteen edella esitettyyn tapaan.

3. Patenttivaatimuksen 1 tai 2 mukainen mene-telmå, tunnettu siita, ettå ennen kutakin keksinnolle ominaista kuvalohkon neljånneslohkojakoa suoritetaan kuvalohkon rekonstruointi siihen asti koo- 25 datun informaation perusteella ja muodostetaan kuvalohkon ja rekonstruoidun kuvalohkon vålinen erotus, joka erolohko siis sisåltåå viimeksi suoritetun koodausvai-heen koodausvirheet, ja sovelletaan keksinnon mukaista menetelmaå kuvalohkon sijasta nåin muodostettuun ero-30 lohkoon.

4. Patenttivaatimuksen 1 tai 2 mukainen mene-telmå, tunnettu siitå, ettå ensimmåisellå lohkotasolla koodausta tehostetaan poistamalla ennen koodauksen suorittamista kuvan kunkin lohkon sisåltåmi- 35 en kuvapisteiden harmaasåvyarvojen keskiarvo ja låhet-tåmållå keskiarvo erikseen låhetyspååstå vastaanotto-pååhån. 20 92272

5. Patenttivaatimuksen 1, 2 tai 3 mukainen menetelmå, tunnettu siitå, ettå kuvalle suori-tetaan lahetyspaassa alipåastosuodatus ja nåin suoda-tettu kuva lahetetåån erikseen vastaanottopååhån, ja 5 ettå vain kuvan suurtaajuuskomponenttiin eli alkuperåi-sen kuvan ja alipååstosuodatetun kuvan erokuvaan sovel-letaan patenttivaatimusten 1, 2 tai 3 mukaista menetel-måå.

6. Jonkin edellå esitetyistå patenttivaatimuk-10 sista 1-5 mukainen menetelmå, tunnettu siitå, ettå osalohkojen ja mahdollisesti niitå pienempien lohko-osien koodaamisessa kåytettyjen vektorikirjasto-jen kokoa vaihdellaan tapauskohtaisesti kuvan sisållon perusteella siten, ettå våhån yksityiskohtia sisåltåvi-15 en lohkojen koodauksessa kåytetåån pienempiå kirjastoja kuin paljon yksityiskohtia sisåltåvien lohkojen koodauksessa, ja ettå kåytetyn vektorikirjaston koko låhe-tetåån lisåinformaationa.

7. Jonkin edellå esitetyistå patenttivaatimuk-20 sista 1-5 mukainen menetelmå, tunnettu siitå, ettå osalohkojen ja mahdollisesti niitå pienempien lohko-osien koodaamisessa kåytettyjen vektorikirjasto-jen kokoa vaihdellaan koodatun lohkon kuvasisållon perusteella siten, ettå våhån yksityiskohtia sisåltåvi-25 en lohkojen koodauksessa kåytetåån pienempiå vektori-kirjastoja kuin paljon yksityiskohtia sisåltåvien lohkojen koodauksessa, jolloin vektorikirjaston koko måå-ritellåån kiinteåsti luokitteluindeksin perusteella. §2272 21