Adaptive color coding based on spatial/temporal features

Walter Bender

Massachusetts Institute of Technology Media Laboratory
20 Ames Street, Cambridge, Massachusetts 02139
(To be presented at SPSE Electronic Imaging Devices and Systems Symposium, Los Angeles, January 1988)

This work has been supported in part by International Business Machines.

Suom. Timo Kinnunen 10.3.1989
Pelastettu 3.5 Levykkeeltä NU.EXE Ohjelmalla 12.4.1989 T. Kinnunen

ABSTRACT

Tehokkaan tietokonenäyttöön tulostuvien värikuvien adaptiiviseen koodaukseen liittyviä ongelmia tutkitaan parhaillaan. Onkin luotu nykyisin käytössä olevien algoritmien modifikaatioita, joilla voidaan esittää paikantuvuuteen liittyviä kuvan karakteristikoita. Spatiaalisia,- temporaalisia, ja semanttisia piirteitä on käytetty luotaessa maskeja, jotka ilmaisevat virhepoikkeamaa (error masks). Näitä maskeja on vuorostaan käytetty korjaamaan vektorikvantisoijan käyttämiä tilastollisia histogrammeja.

1. INTRODUCTION

Tavallisin arkkitehtuuri tietokonenäytöissä rakentuu kuvaruutumuistista, jolla on yhteys grafiikkakontrollipiiriin, joka tuottaa värivalikon. Näytön kuvan laatu on suorassa suhteessa värivalikon laajuuteen, ja jokaiseen valittavana olevaan väriin liittyvään bittimäärään, kuten esimerkiksi 256 väriä 16 -miljoonan bitin paletista. Kahdeksan bitin intensiteettikontrollia primaaria kohden käytetään usein värinäytöissä, vaikka se vaatiikin 24 bittiä kuvaelementtiä kohden, jotta voitaisiin tuottaa sävyjatkuvuudeltaan yhtenäinen kuva. Monet värivalokuvat voidaan kompressoida 256:sta 1024:aan väriin ilman, että kuvan laatu juurikaan heikkenisi [1,2]. Alkuperäisten kuvaoriginaalien värirunsauden toistettavuutta ajatellen on selvää, että käytettävä pienemmän värien määrä käyttö vaatii tihennystä (dithering) tai virhe-erottelua (error diffusion), jotta vältettäisiin virheellisyyksiä väripintojen rajakohdissa (contours), ja siten rajakohdat onkin korvattava korkeafrekvessisellä kohinalla [3,4]. Nykyinen tutkimuksen suunta liittyy adaptiivisen värikuvien koodauksen yleiseen problematiikkaan tietokonenäyttöä ajatellen. Useita nykyisten algoritmien modifikaatioita on ehdotettu, jotka sallivat paikantuvien kuvakarakteristikoiden tuoton näyttöön. Kaikki kompressiotekniikat joko hyödyntävät tilastollisia signaalin redundansseja, tai observoijan psykofysiologisia ominaisuuksia. Kumpaa tahansa lähestymistapaa käytettäessä enkoodauksessa, jätetään signaalin käsittelyllisesti tarpeettomat komponentit huomiotta. Kuitenkaan nämä tekniikat eivät ole erityisen tehokkaita. Adaptiivisen värikooderin toiminta, olipa se tilastollinen tai psykofyysinen, soveltaa kuvan alempiin elementteihinsä jaoittamista (subsampling) koodauksessa. Kolmiulotteinen avaruus, jonka akselit useimmiten edustavat punaista, vihreää ja sinistä, populoidaan otosarvojen (sample values) histogrammijakaumaan. Enkooderi muodostaa sitten väriavaruuden alajakaumat halutunlaajuisella värikoodimäärällä. Tätä monidimensionaalisen avaruuden alijaoittumista (subdivision) tutkitaan runsaasti vektorikvantisoinnin -nimellä tunnetulla koodaustekniikalla. Gray [5] mm. tutkii erilaisia alijaoittamisen sääntöjä. Jokaista originaalikuvan elementtiä verrataan tämän jälkeen sitä lähinnä olevaan vastaavaan koodiin [2]. On hyödyllistä ajatella enkoodauksen ongelmaa maskivaikutuksena (in terms of masking). Enkooderin tuotoksen ja kuvaoriginaalin eroa tarkastellaan tuottamalla eroa ilmaiseva virhekuva. Tehokasta koodausta voidaan siten tarkastella siten ongelmana, kuinka tehokkaimmin voidaan häivyttää (mask) virhekuvaa. Etuna maskivaikutuksen tutkimisen lähestymistavalla koodausongelmaan on siinä, että se johtaa lukuisiin ratkaisumalleihin, joita ei voida tavoittaa sellaisin menetelmin, joissa kuva jaoitetaan huomioimatta sitä, mistä kohden kuvaa otokset siitä löytyivät. Tämä raportti keskittyy nimenomaan maskivaikutukseen. Kaikki tekniikat hyödyntävät jotakin tietoa kuvasta itsestään, jotta voidaan jäsentää ja modifioida kuvan tiheyksiä kuvaavia otoksia, painottaen otoshistogrammia käytetyn tietämyksen mukaisesti. Eräs tekniikoista keskittyy kuvan spatiaalisiin piirteisiin. Tällöin tekniikassa korostuu se, MISSÄ kohden kuvaa virheitä esiintyy. Toiset tekniikat nojaavat kuvan semanttisiin sisältöihin l. MITKÄ KUVAN OSISTA OVAT OBSERVOIJAN HAVAINNOINNIN KANNALTA KESKEISIÄ. Alustava tutkimustyö tällä alueella on hyödyntänyt kuvan temporaalista analyysia [18], kuten myös syvyysinformaation osoittamista (depth keying) [19]. Toiset analyyttisista, tai ei-analyyttisista kuvan tärkeiden piirteiden mittauksista voidaan lisätä malliin, jotta enkooderia voitaisiin edelleen optimoida.

2. PRECENDENTS

On useitakin hyvindokumentoituja havainnon ominaisuuksia, joita voidaan hyödyntää koodauksessa:

* Herkkyys epäjatkuvuuksille spatiaalisessa frekvessispektrissä.
* Herkkyyden väheneminen vastaanotettuun ärsykkeeseen läheisärsykkeen vuoksi, sekä spatiaalisen -että temporaalisen.
* Lisääntynyt herkkyys luminanssikohinalle kuvan tummilla alueilla.

Kuvanhäiriöiden mittaukset perustuvat johonkin, tai kaikkiin manituista havaittavuus-ominaisuuksista, joita ovat kuvanneet mm. Sakrison [6], Watson [7], Glenn [8], Limb [9], Lukas [10], Sharma [11], Legge [12], ja Stromeyer [13]. Häiriömittauksia käytetään usein visuaalisten eroavaisuuksien kvantisoinnissa; onhan se hyödylliseksi havaittu myöskin kuvien perseptuaalisessa koodauksessa, jossa soveltumaton informaatio siivilöityy pois, ja jossa sitten evaluoidaan resultanttikuvia. On tehty systemaattisia tutkimuksia häiriömittauksen hyödynnettävyydestä kuvankoodauksessa taajuusaluekompressiossa. Spatiaalisten luminanssimuutosten peittovaikutusta (masking) ovat tutkineet mm. Netravali ja Presada [14], sekä Ramaurthi ja Gersho [15]. Yamaguchi [16] on tutkinut nonlineaaristen trasformaatioiden koodausta puna-vihreä-sininen -väriavaruudessa. Swaszek ja Thomas [17] käyttävät nonlineaarisia funktioita kvantisoidakseen ja laajentaakseen luminanssisignaalia. Vektorikvantisoinnin käyttö kuvankoodauksen mekanismina näyttöön on lukuisia eroavaisuuksia koodattaessa kuvia tiedonsiirtoon, koska graafisen näytön resoluutio on kiinteä (yleisesti yhden suhde yhteen näyttömuistin ja kuvaelementtien välillä), kun taas tonaliteetin suhteen jää tietty vapaus. Ne mittaustavat, joissa hyödynnetään tonaliteetin riippumattomuutta sijainnista ovat hyödynnettävissä olemassaoleviin algoritmeihin käyttämällä häiriönmittausta ennen kvantisointia, sillä kooderit kvantisoivat luminanssia hienojakoisemmin kuin krominanssia. Heckbert [2] soveltaa "suuntautuneeseen toimintaan liittyvän raapustelun" (doodle) mekanismia, jossa "käsin piirrettyä" maskia käytettäisiin lisäotosten syöttöön otoshistogrammiin. "Suuntautuneeseen toimintaan liittyvällä raapustelulla" tuotetaan enemmän keskeisyyttä kuvan mm. pienille kasvojen yksityiskohdille, kuten esimerkiksi silmille ja suulle suoralla ihmisen väliintulolla. Visuaalisten mallien käyttöön ja kuvan semantiikkaan liittyvänä on tämä tekniikka saanut yleistävyyttä.

3. PROCEDURE

Tässä luvussa kuvataan kuvan kvantisoinnin proseduuria. Perusmuodossaan [2,3] on vektorikvantisoinnin algoritmilla kolme vaihetta:

* Analyysi, jossa värienjakauma kvantisoitavasta kuvasta esitetään histogrammina kuvan jokaista kanavaa koskien. Harjoituajosetti generoidaan koodattavaksi aiotun kuvan satunnaisjakaumasta.
* Koodikirjaa varten valitaan histogrammista edustava vektorien joukko (koodisanat), ja kd-puuta käytetään tietojenkäsittelyllisesti tehokkaana keinona koodikirjan generoinnissa.
* Kvantisoinnissa kuvan jokainen otos liitetään sitä lähinnä olevaan koodisanaan. Virhe-erottelun (error diffusion) tekniikoita käytetään prosessin tässä vaiheessa.

Tässä raportissa esiteltävä koodausalgoritmin modifikaatio on maskivaikutusfunktion inkluusio kuva-analyysissa. Maskivaikutusfunktiota käytetään kontrolloimaan laatutason vaihteluja alueelta toiselle poikkeuttamalla (biasing) kuvan otoksia. Generoidaan sellainen maskivaikutuskuva, joka suoraan vastaa kuvaoriginaalia. Se generoidaan liittyen kuvahistogrammin generoimiseen, jotta luotaisiin joustava testausalusta (test bed), eikä pyrkimyksenä ole niinkään luoda tietojenkäsittelyllisesti tehokasta ratkaisua. Maskikuvan arvo m(i,j) pisteessä (i,j) määrittää kaksiulotteisen otosalueen koon. Kaikki pisteet, jotka sisältyvät ympyrään, tai diametriin m(i,j), ja jotka ovat keskittyneet pisteen (i,j) ympärille, lisätään histogrammiin. Siitä johtuen poiminnan lopputuloksena on suuri maskiarvo saadaan suhteellisesti suuremmalta alueelta kuin pieni maskiarvo. Poiminta ei ole enää satunnaista, vaan on suuntautunut erityisiin kuvan komponentteihin. Saatu histogrammi ei siten pelkästään heijasta sitä, mitä värejä löydetään, vaan myös jossain määrin sitä, MISSÄ KOHDEN ne kuvaan poimittiin. Koodikirjan valinta liittyy otoksen edustavuuteen (representative of sampling), sillä kvantisointivirheet korreloituvat maskivaikutusfunktioon (katso fig. 1 ja 2.). Maskivaikutusfunktion ja kuva-analyysin välinen suhde määritellään kokeellisesti, mutta määrittelytapa ei ole mielivaltainen. Maskivaikutsfunktion vaihtelualue rajattiin 3 -bittiin. Resultanttiotosalueiden säde vaihteli 1-8 kuvaelementtiin. Kaikille otosalueille annettiin samanlainen painotusarvo. Lukuisat maskiarvofunktiot todettiin hyödyllisiksi. maskiarvofunktioita varioitiin niin, että niitä voitiin matemaattisesti seurata, sekä käyttää ad hoc -tekniikoita.

3.1. Spatial masking functions

On hyödyllistä erottaa toisistaan matala- ja korkeafrekvenssiset alueet, koska kohina on heikommin erotettavissa korkean- kuin alhaisen frekvenssitason alueilla, ja siten kvantisointikohina on (visuaalisesti) havaittavampaa alhaisen kuin korkean spatiaalisen frekvenssin alueilla. Maskivaikutuskuva voidaan generoida vertaamalla toisiinsa alkuperäisen luminanssin kuvaa ja samaa kuvaa ajettuna alitaajuussuotimen kautta (low-pass filter). (Fig. 1b). Resultantti maskivaikutuskuva sisältää matalia arvoja niissä kohdin, missä alkuperäiskuvassa vierekkäisten kuva-alueiden ero on jyrkkä, ja korkeita arvoja siellä, missä siirtymät ovat loivia. Signaali-kohinasuhteessa (S/N) on vähän eroja verrattaessa kvantisoituja kuvia spatiaalisen maskin kanssa ja ilman sitä. Subjektiivinen kuvien analyysi viittaa sihen, että virhettä liittyisi kuitenkin vähemmän kuviin, jotka on kvantisoitu spatiaalisen maskin kanssa.

3.2. Semantic masking functions

Yritettäessä tuottaa maskikuvia siten, että huomioitiin kuvien semanttisesti "merkityksettömät" alueet sovellettiin lukuisia heuristiikkoja. Rekursiivista blokkienvertailun algoritmia sovellettiin kuvien sekvensseihin silloin kun haluttiin erottaa toisistaan ne kuvanosat, joissa oli liikettä niistä kuvan osista, jotka olivat kuvaavan kameran suhteen liikkumattomia. Tällainen algoritmi työskentelee etsimällä maksimaalisia spatiaalisen sijainnin korrelaatioita tietyn, valitun kuvaruudun ja sitä edeltävien ja seuraavien kuvien yksityiskohtien välille [18]. Maskivaikutuskuva luodaan liittämällä korkeita arvoja niihin kuvanosiin, joissa on havaittu liikettä (katso fig. 3). Kuten odotettuakin, on kvantisointikohinaa eniten kuvan taustassa. Syvyyskameran (range cameras) kuvia voidaan myös käyttää maskien luomiseen, joissa erotetaan kuvan etuosa sen taustasta. Kameraa lähellä oleviin objekteihin liitetään suurempia arvoja kuin kaemmaksi asettuviin objekteihin. Tulokset ovat samansuuntaisia kuin mitä on saavutettu blokkiensuhteutusalgoritmilla (block matching algorithm). Syvyysetäisyysmitaukset, joita käytetään syvyyskameran kuvissa [19] ovat soveltuvia fokusointimaskien generointiin (focus mask). Fokusoidut objektit painotetaan eri tavalla kuin sen ulkopuolella sijaitsevat objektit.

4. EVALUATION

One man's enchangement may be another man's noise [21]

Signaali-kohinasuhde jää kaikkein yleisimmäksi koodausskeemojen punnitsemiskriteeriksi. Tässä raportissa luonnehditut tekniikat vaihtelivat suurestikin S/N -suhteen huomioonottaen. Spatiaalisen maskin käytöllä oli S/N:aan vähäinen vaikutus. Testikuvassa (fig. 1.) S/N oli 16.2 db ilman maskia, ja 16.0 db sen kanssa. Tämä ei ole yllättävää, koska virhe on tasaisemmin jakautunut. Tausta huonontui etualalla olevien objektien hyväksi. Kvantitatiivinen ja kvalitatiivinen muutos virhejakaumassa viittaa siihen, että maskikuvan käytöllä on tiettyä potentiaalista etua.

5. CONCLUSION

Yksikään tarjolla olevista visuaalisista malleista ei ole adekvaatti yleiseksi työkaluksi kuvien evaluaatioon, mutta niitä malleja, joita meillä on käytettävissämme, voidaan soveltaa menestyksellä maskivaikutusongelmaa ratkaistaessa. Maskivaikutusvirheen (masking error) arviointi kuvansisällön perusteella on käyttökelpoinen tapa, mutta siihen liittyvät tekniikat eivät ole matemaattisesti jäljitettävissä, tai riittävästi yleistettävissä. Maskivaikutusfunktion tuottaminen vektorikvantisoinnin yhteyteen on ollut menestys siinä mielessä, että se tarjoaa vapausasteita koodausprosessiin. Kun uusia visuaalisia malleja kehitellään, esimerkkinä Adelsonin pyramidimalli [20], voidaan niitä soveltaa maskivaikutusongelman ratkaisuun edellä kuvatulla tavalla. Kun kuvien kontekstuaalinen ymmärtäminen kehittyy edelleen, voidaan sitä myös soveltaa värikuvien koodaukseen tietokonenäyttöjä varten.

6. ACKNOWLEDGEMENTS

Andrew Lippman, Pascal Chesnais ja Judith Donath saavat kiiroksen tämän raportin kirjoittajalta osallistumisestaan tutkimustyöhön. International Business Machines Inc. tuki osittain tätä työtä.

7. REFERENCES

[1] T. Boyle, Coding Color by Popularity, Architecture Machine Group Memo (1978).

[2] P. Heckbert, An Adaptive Color Encoding System for Computer Graphics, Computer Graphics, 16(3) (1982).

[3] G. Houle, Quantization des Images Coleurs Pour Appareils Graphiques, INRS-Télécommunications Technical Report no. 85-37 (1985).

[4] G. Braudaway, A Procedure for Optimum Choice of a Small Number of Colors From a Large Color Palette for Color Imaging, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, (UNDATED).

[5] R. Gray, Vector Quantization, IEEE ASSP Mag. (1984).

[6] D.J. Sarkinson, On the role of observer and a distortion measure in image transmission, IEEE Trans. Commun., 25(11):1251-1267 (1977).

[7] A. Watson, A. Ahumada,Jr, and J.E. Farrell, The window of visibility: a psychophysical theory of fidelity in time-sampled visual motion displays, NASA Technical Paper 2211 (1983).

[8] W.E. Glenn, K.G. Glenn, and C.J. Bastian, Imaging system design based on psychophysical data, SID Int. Sym. Digest of Tech. Papers, 15 (1984).

[9] J.O. Limb, Distortion criteria of the human viewer, IEEE Trans. Syst. Man & Cybern, 9(12):778-793 (1979).

[10] F.X.J. Lukas and Z.L. Budrikis, Picture quality predictions based on a visual model, IEEE Trans. Commun., 30(7):1679-1692 (1982).

[11] D.K. Sharma and A.N. Netravali, Design of quantizers for dpcm coding of picture signals, IEEE Trans. Commun., 25(11):1267-1274 (1977).

[12] G. Legge and J. Foley, Contrast Masking in human vision, J. Opt. Soc. Am., 70(12) (1980).

[13] C. Stromeyer III and B. Julesz, Spatial-frequency masking in vision: critical bands and spread of masking, J. Opt. Soc. Am., 62(10) (1972).

[14] A.N. Netravali and B. Presada, Adaptive quantization of picture signals usin spatial masking, Proc. IEEE, 65(4) (1977).

[15] B. Ramaurthi and A. Gersho, Image coding using segmented codebooks, Proc. Int. Picture Coding Sym. (1983).

[16] H. Yamaguchi, Vector quantization of differential luminance and chrominance signals, IEEE Trans. Commun., 33(5) (1985).

[17] P. Swaszek and J.B. Thomas, Design of quantizers from histograms, IEEE Trans. Commun., 32(3) (1984).

[18] E. Devlin, High Resolution Video Stills, (SB Thesis), MIT (1987).

[19] V.M. Bove, Pictorial applications for range-sensing cameras, SPIE Proc., 901 (1988).

[20] E.H. Adelson, C.H. Anderson, J.R. Bergen, P.J. Burt, and J.M. Ogden, Pyramidmethods in image processing, RCA Eng., 26(9) (1984).

[21] H. Andrews, comment in IEEE Tutorial on Digital Image Processing, IEEE (1978).