SE511669C2 - Sätt att optimera valet av färger när en bild skall presenteras - Google Patents

Description

511 669 2 10 15 20 25 30 35 användas med en GIF-bild, utan den kan också minska antalet färgeri andra tillämpningar och ger därvid ett mycket bra resultat.

Vid uppfinningen löses de uppställda problemen genom att den får den utformning som framgår av det efterföljande självständiga patentkravet. Lämpliga utförings- former av uppfinningen framgår av övriga patentkrav.

Uppfinningen kommeri det följande att beskrivas närmare under hänvisning till bifogade ritning, där fig. 1 visar ett exempel på ett histogram över röda färger, fig. 2 visar en färgkub, ett tredimensionellt histogram, fig. 3 visar en färgkub med två färgblock, fig. 4 visar trimning av färgblock, fig. 5 visar delning av färgblock, fig. 6 visar hur oturlig delning kan ge upphov till små närliggande block, fig. 7 visar sammanslagning av små närliggande block och fig. 8 visar hur sammanslagning kan leda till överlappning.

Först måste olika begrepp som kommertill användning vid uppfinningen definieras. lndata äri den utföringsforrn av uppfinningen som kommer att beskrivas närmare nedan en True Color-bild, dvs. en rektangel med pixlar där varje pixel består av 24 bitar. Andra bildformat som läses in kan först omvandlas till en sådan bild. Altema- tivt kan uppfinningen få verka direkt på andra bildformat på ett motsvarande sätt.

Palettoptimeringen enligt uppfinningen kan användas så fort antalet färger i indata överstiger antalet färger som skall presenteras i utbilden.

I exemplet är varje pixel RGB kodad. Andra format kan omvandlas intemt till RGB.

Det betyder att de 24 bitama delas upp på 8 bitar röd nivå, 8 bitar grön och 8 bitar blå nivå. Nivån för en enskild färg kan då variera mellan O och 255. 0 betyder släckt och 255 motsvarar full intensitet. l andra tillämpningar av uppfinningen kan man utnyttja andra uppdelningar i tre färger.

Utdata är en bild med en indexerad färgpalett. Utbilden har samma bredd och höjd som inbilden, och fungerar allt som det ska ser den ungefär likadan ut, samtidigt som antalet färger väsentligt minskat. 10 15 20 25 30 35 3 511 669 I indata finns hela färgkoden för en pixel lagrad i pixeln själv. Det finns därför inget behov av någon palett. I utdata finns en tabell med 2 till 256 färgkoder (i exemplet med 24 bitars RGB). En adress, ett index, till en kod i denna tabell består av 1 till 8 bitar. Färgkodtabellen kallas palett, och en pixel i utbilden består av ett index till paletten.

Föreliggande uppfinning är väsentligen ett program för att optimera paletten, dvs. fylla paletten med 24 bitars RGB koder som är så väl valda som möjligt. För en bild av en skog kommer ddet_t.ex. att finnas många olika gröna nyanser i paletten.

Dessutom skall det skapas en utbild där pixlama är index till paletten, men det är en enklare uppgift.

Uppfinningen arbetar med ett tre-dimensionellt histogram över färger. Det sanna histogrammet är en tredimensionell färgkub med, i exemplet, röd, grön och blå nivå längs var sin axel. Ofta ser man histogram över en färgnivå i taget, t.ex. den röda nivån, se fig. 1. Att ange histogram för de röda, gröna och blå nivåema var för sig är emellertid en förenkling. l fig. 2 visas en färgkub - ett äkta 3D histogram.

För varje 24 bitars färg finns en cell i färgkuben, och i den cellen lagras antalet pixlar i indata-bilden som harjust den färgen. Man kan tänka sig att färgkuben innehåller ett "pixelmoln", med varierande täthet.

Den färgkub som beskrivs ovan har 256 * 256 * 256 = 16 777 216 celler och varje cell kan vara ett 32 bitars heltal. Fârgkuben lägger då beslag på drygt 67 Megabyte RAM-minne. För en teoretisk matematiker och/eller superdatorinnehavare är detta inget problem alls, men i praktisk användning i bildbehandling är det det. Om där- emot 24-bitarsfärgen reduceras 18 bitar erhålls en kub om 64 * 64 ' 64 = 262 144 celler. Det går då åt drygt enïflagabyte, om varje cell har 32 bitar, och drygt en halv Megabyte för celler med 16 bitar. Denna storlek är fullt rimlig. 18 bitars färg är bättre än Hi Color och är egentligen onödigt bra för den aktuella tillämpningen.

Med 16 bitar per cell finns en liten risk att delar av färgkuben "mättas", dvs. att några celler slår i taket, eftersom 2" -1 inte är mer än 65 535. Detta innebär inte någon nämnvärd olägenhet. Som än lämplig storlek på färgkuben föreslås i det aktuella fallet 64 " 64 " 64 celler och ett sextonbitars heltal utan tecken för varje cell.

I andra tillämpningar kan det vara lämpligt att använda altemativa färgkuber med andra storlekar. Om t.ex. utdata-bilden endast skall innehålla färger från standard 511 669 4 10 15 20 25 30 35 Netscape-paletten så blir en lämplig storlek på kuben 6 ' 6 * 6 = 216 celler (och cellema kan då ha 32 bitar eftersom varje cell innehåller fler pixlar när det finns färre celler).

Det tredimensionella histogrammet måste kunna nollställas. Det skall därför finnas en funktion som sätter samtliga celleri färgkuben till noll. När man sedan skall lägga till en bild till histogrammet utför man i stora drag följande för samtliga pixlari bilden (indata): - Ta reda på röd, grön och blå nivå för den aktuella pixeln.

- Omvandla färgnivåerna till lämpliga index i färgkuben, t.ex. avmnda 8 bitar till 6 bitar.

- Den cell som utpekas av de tre indexen inkrementeras med ett, såvida den inte är mättad.

- Fortsätt med nästa pixel.

Genom att tillåta att flera bilder läggs till histogrammet kan det bli möjligt att opti- mera en gemensam palett för dem. Det kan vara bra vid arbete med animationer.

Det måste naturligtvis finnas en funktion för att läsa celleri färgkuben. Funktionen tar tre index (inte färgnivåer) som argument, och ger antalet pixlar i den utpekade cellen.

Uppfinningen kan vidare innefatta ett antal mindre viktiga funktioner. Exempel på sådana funktioner är. - ignorera nästan tomma celler Det kan finnas en funktion för att nollställa de celler i färgkuben som bara innehåller några enstaka pixlar, säg 1 till 10 stycken. Funktionen skall vara valbar. Om in- databilden innehåller enstaka ströpixlar med udda färger så kan man undvika att dessa i onödan tar upp värdefull plats i den färdiga paletten, förutsatt att strö- pixlama är ointressanta.

Om man optimerar en liten bild med jämn färgfördelning får man se upp så att man inte nollställer hela färgkuben eller en stor del av den. 10 15 20 25 30 35 511 669 - Valbar mättnad Om cellema består av 16 bitar införs en automatisk mättnadsnivå om 65 535 pixlar per cell. Användaren kan tillåtas sätta en egen mättnadsnivå på säg 1000 till 65 535 pixlar. Man kan då undvika att stora enfärgade ytor blir alltför dominerande vid tilldelningen av palettfärger.

- Färgkub statistik Färgkuben kan också besvara några statistiska frågor, t.ex. hur många pixlar den innehåller totalt, hur många celler som har något innehåll osv. Omfattande statistik är dock inte nödvändig här. Sådana saker som min-, max-, medelvärde och stan- dardavvikelse för rött, grönt och blått handhas av de färgblock, som beskrivs i det följande.

Ett färgblock är en rektangulär delvolym av färgkuben. För varje färgkub (det finns bara en) finns det mellan 1 och 256 färgblock, se fig. 3. Största storlek för ett färg- block är lika med hela färgkuben och minsta storlek är en enda cell i färgkuben.

Varje färgblock motsvarar exakt en färg i paletten och tvärtom. Listan med 1 till 256 färgblock är arbetsredskapet i palettoptimeringsfunktionen enligt uppfinningen. volymen av ett färgblock kan t.ex. beskrivas av sex variabler, som är index till färg- kuben: röd_min, röd_max, grön_min, grön_max, blá_min och blá_max.

Palettoptimeringen enligt uppfinningen påbörjas utgående från ett enda färgblock med samma storlek som hela färgkuben. Därpå utförs ett antal steg avseende trimning, klyvning och sammanslagning för att optimera en palett.

Trimning utgår från att ett färgblock aldrig skall tillåtas innehålla några tomma kanter. En sida som endast innehåller nollställda celler skalas därför bort, se flg. 4 beträffande sådan trimning. Varje block har sex sidor som kan skalas bort om de är tomma, vid behov i flera steg. Om ett block är helt tomt så kommer det vid trimning att krympa till nollstorlek och tas bort. (Helt tomma block skall egentligen aldrig före- komma.) lgnorerade pixlar, se ovan, kan vid trimning komma att hamna utanför alla block.

När dessa pixlar senare skall tilldghs en färg i paletten får man ta den som råkar ligga närmast. 511 669 10 15 20 25 30 35 Efter trimningen är följande statistikvariabler redan kända: röd_min, röd_max, grön_min, grön_max, blá_min och blà_max. Det är samma variabler som beskriver blockets storlek.

Dessutom beräknas: pixlar diagonal färg_mitt röd_mitt grön_mitt blå_mitt färg_storlek röd_storlek grön_storlek blà_storlek färg_medel röd_medel grön_medel blá_medel färg_awikelse röd_awikelse grön_avvikelse blâ_awikelse Totala antalet pixlar i blocket. Detta är ett av de två måtten pâ blockets storlek.

Längden på blockets rymddiagonal. Detta är det andra måttet på blockets storlek och är ett mått på hur dísparata färger blocket innehåller. (Blockets volym används inte som mått, eftersom ett Iångsmalt block kan vara mycket stort längs en axel och ändå ha liten volym.) Resp. sidas mittpunkt hos blocket. röd_mitt = (röd_min + röd_max) /2 Längden på blockets resp. sidor. röd_storlek = (röd_max + 1) - röd_min "Medelpunkten". färg_medel är medelvärdet av resp. färgnivå i blocket.

Standardavvikelse för respektive färgnivå.

Då den lokala statistiken samlats för alla block beräknas lite global statistik: pixlar_medel Medelvärdet av antalet pixlar i blocken. (Totala antalet pixlar i kuben dividerat med antalet block.) 10 15 20 25 30 35 511 669 diagonal_medel Medelvärdet av blockens diagonaler.

Man kan nu beräkna lite ytterligare lokal statistik för varje block: = pixlar/ pixlar_medel Blockets pixelstorlek i förhållande till de andra blocken. pixlar_relativ = diagonal I diagonaI_medel Blockets diagonal, eller "färgstorlek", iförhållande till de andra blocken. diagonal_relativ Blockets diagonal- och pixelstorlek är två mått som inte utan vidare är jämförbara med varandra, och dessutom varierar de på olika sätt när blockets volym ändras.

Syftet med att ta fram relativa storlekar är att de två måtten lättare skall kunna vägas mot varandra. Sådan jämförelse är nödvändig, eftersom uppfinningen inne- fattar momentet klyvning av fârgblock, dvs. att det största färgblocket i någon utvald mening väljs ut och delas upp itvå mindre.

Ett block har som anförts två mått på sin storlek i förhållande till de andra blocken: pixlar_re|ativ och diagonal_relativ.

Det är användaren av programmet som avgör vilket mått som skall gälla och det kan vara möjligt att välja en kompromiss. Om man t.ex. väljer 60% prioritet på att minimera blockens diagonaler och 40% på pixlama, så gäller för varje block: vägd_storlek = 0.6 * diagonaljilativ + 0.4 * pixlar_relativ Om det är viktigt med en jämn fördelning av färgema i paletten så väljer man en hög prioritet för diagonalstorleken (färgmåttet). Om det är mer viktigt med bra färg- upplösning för areor som är storsj-Hailden, väljer man högre prioritet för pixelmåttet.

Blocket med den största vägda sßfleken väljs ut för klyvning. Ett block som består av bara en cell är odelbart och får aldrig väljas för klyvning. Om det bara finns en- celliga block så måste palettoptimeringen avbrytas i förtid.

Vid klyvning av ett block, se fig. 5, ökar det totala antalet block med ett. Blocket som klyvs skärs mitt itu med ett som är vinkelrätt antingen mot den röda, gröna eller blå axeln. Den axel som är störst väljs för delning. Här kan storleken återigen mätas på två sätt, sidans längd (Weller) eller motsvarande färgniväs standard- 511 669 8 10 15 20 25 30 35 avvikelse. Ett vägt medelvärde kan beräknas på samma sätt som för vägd_storlek ovan. röd_vägd_storlek = prioritet * (röd_storlek/ medelstorlek) + (1 - prioritet) * (röd_awike|se I medelawikelse), där medelstorlek och medelawikelse gäller lokalt för blocket.

Ett enklare och kanske mer robust mått är röd_vägd_storlek = prioritet * röd_storlek + (1 - prioritet) * röd_awikelse.

Eller ännu mer robust: röd_vägd_storlek = röd_storlek + (1 - prioritet) * röd_awikelse När en axel, röd, grön eller blå, har valts för delning skall läget för delningen bestämmas. Det kan vara axelns mittpunkt eller färgnivåns medelvärde eller en kombination av de två, t.ex: röd_klyv = prioritet ' röd_mitt + (1 - prioritet) * röd_mede| Samma prioritetsvärde bör kunna användas såväl för val av största block, val av klyvaxel som för val av klyvkoordinat. Klyvkoordlnaten avrundas naturligtvis till ett helt antal celler innan delning sker. De två nya blocken trimmas och statistik- behandlas. Sedan väljs ett nytt största block för klyvning.

Om prioriteten för blockens pixelinnehåll är noll, tar algoritmen endast hänsyn till blockens cellstorlek. Programmet kan då snabbas upp, eftersom inhämtande av detaljerad pixelstatistik blir onödig.

När antalet block har uppnått ett förutbestämt antal, mellan 2 och 256, så är palett- optimeringens första steg avslutat. Efter detta kan man övergå till att skapa palet- ten, se vidare längre fram i beskrivningen.

I många fall är det dock lämpligt att även utföra ett andra steg avseende samman- slagning av små block innan paletten skapas. Har man nämligen otur vid block- klyvningen, kan av en slump två små block ligga nära varandra, när det önskade antalet block har uppnåtts, se fig. 6. Detta är inte optimalt.

Genom att slå ihop de två små blocken till ett, som fortfarande är ganska litet, kan klyvningsprocessen fortsätta ett steg till, och det tillgängliga utrymmet i paletten 10 15 20 25 30 35 9 511 669 bättre tas tillvara. Denna procedur kan upprepas så länge som det finns två block som kan slås samman, utan att det sammanslagna blocket blir det största, se fig. 7.

Funktionen är lite kombinatoriskt besvärlig, men inte omöjlig att genomföra. Den ambitiöse användaren väljer vid varje tillfälle ut det par av block som efter sam- manslagning ger den allra minsta storleken. Vid sammanslagning av block finns en viss risk att det uppstår överlappande block, se fig. 8. Sådan överlappning kan antingen tillåtas eller förbjudas.

Pixeldensiteten för färgkuben definieras som det totala antalet pixlar dividerad med hela färgkubens volym. Detta täthetsmått kan räknas ut en gång för alla och är sedan konstant under palettoptimeringens gång. Man kan på liknande sätt definiera pixeldensiteten för ett färgblock, men det måttet kan komma att ändras något när blocket trimmas, klyvs eller slås samman.

Ett blocks pixeldensitet kan normeras genom att den divideras med pixeldensiteten för hela färgkuben. Den normerade eller relativa pixeldensiteten, pixeldensitet_re|ativ, är större än ett (>1) om blocket är tätare än färgkuben i genomsnitt, och mindre än ett (<1) om blocket är glesare än så. Måttet ändras inte när andra block ändrar form.

Det innebär vissa nackdelar med att använda sig av blockens relativa diagonal och pixelinnehåll. Så fort någonting händer med ett enda block, kan dessa relativa storlekar ändras för samtliga block.

Vid eventuell sammanslagning avblock så skall ett ganska stort antal kombinato- riska möjligheter undersökas, för att man ska kunna utröna om det finns något par av block som tillsammans har en storlek som är mindre än det största enskilda blocket. Algoritmen blir besvärlígjorn samtliga block har olika storlek före och efter varje möjlig sammanslagning. i Det vore då bra om man i stället kunde använda ett storleksmått som är konstant för ett visst block, så länge som inte blocket själv ändras. Den absoluta diagonalen och det absoluta antalet pixlar är sådana konstanta mått, problemet är bara att kunna väga dem mot varandra. Diagonalen ökar linjärt med blockets storlek medan antalet pixlar ökar ungefär med kuben.

Pixeldensiteten (relativ eller absolut) år inte direkt beroende av blockets storlek.

Genom att multiplicera densíteten med diagonalen fås ett pixelmått som har samma 511 669 19 10 15 20 25 30 35 dimension som diagonalen. vägd_storlek = prioritet' diagonal + (1 - prioritet) * diagonal * pixe|densitet_relativ Lite försiktigare kan man i stället använda vägd_storlek = diagonal + (1 - prioritet) * diagonal " pixeldensitet_relativ Det kan vara en försiktighetsåtgärd att aldrig låta ett blocks storlek bli mindre än dess diagonal.

Efter trimning, klyvning och sammanslagning återstår skapandet av paletten. På ett idé-mässigt plan finns alltid en ett-till-ett relation mellan färgblocken och färgema i paletten. Färgen för ett visst block kan t.ex. vara röd_klyv, grön_klyv och blà_klyv enligt ovan. lnnan dessa nivåer förs in i palett-tabellen, måste de omvandlas till 8 bitar för vane nivå. En något lite bättre färgprecision kan ibland uppnås, om t.ex. röd_klyv inte avrundas till en hel cell innan den omvandlas till 8 bitar.

Till slut konstrueras en utdatabild, där pixlama består av index till paletten. För varje pixel hämtar man dess ursprungliga RGB-värde i indatabilden. RGB-värdet om- vandlas till index till en cell i färgkuben. Ett färgblock väljs, antingen ett block som innehåller cellen, eller annars det block som ligger närmast. Det index till paletten som motsvarar det valda blocket är korrekt utdata för aktuell pixel.

Som ett tillägg kan användaren använda en sk. dither-funktion vid konstruktion av utdatabilden Syftet är att åstadkomma skenbart flera färger genom rastrering. Hur detta går till är känt för fackmannen på området och beskrivs inte här.

Om indata består av flera bilder så kan utdata göra detsamma. Principema är de- samma som för en enda bild, med den enda skillnaden att pixlama läses från och skrivs till flera bildrektanglar istället för en. Ofta när man arbetar med GlF-animatio- ner så vill man optimera en gemensam palett för en serie bilder.

En något enklare variant av den här beskrivna algoritmen har implementerats i Common Lisp på en Texas Explorer ll Lisp-maskin. Bilder från ett Teragon- bildbehandlingssystem i 24 bitsfärg visades på Texas-maskinen, som kunde visa 8- bitsfärg. Experimentet var lyckat. Palettoptimeringen fungerade bra. Nya versioner av algoritmen kan förväntas bli utförda som Windows 95/NT applikationer eller möjligen en applikation i Java.

Claims (11)

10 15 20 25 30 35 511 669 1 1 Patentkrav:

1. Sätt att optimera valet av färger, ingående i den s.k. färgpaletten, när en bild presenteras med färre färger än de som finns i en ursprunglig form av bilden, varvid alla färger föreligger som en kombination av grundfärger, exempelvis röd, grön och blå (RGB), där man i den ursprungliga bilden fastställer den aktuella kombinationen av gnmdfärger i varje pixel och genererar ett flerdimensionellt histogram med nämnda grundfärger längs axlama, i vilket alla pixlars färger läggs in, så att för varje möjlig färg anges i histogrammet antalet pixlar med den färgen, k ä n n e t e c k n at av att man ursprungligen betraktar hela histogrammet som ett färgblock och utför operationema trimning av färgblock och delning av färgblock, varvid trimning innebär att blocksidor som endast innehåller nollställda celler skalas bort och delning att det i vaüe ögonblick största blocket, i en förutbestämd mening, delas med ett plan vinkelrätt mot den grundfärgsaxel som är parallell med den, i en förutbestämd mening, längsta blocksidan och vid en mittpunkt, i en förutbestämd mening, till sidan, varvid trimning utförs efter varje delning, och nämnda delning av block utförs till dess ett förutbestämt antal block föreligger, varefter man låter varje block representeras av en färg som är representativ för blocket och slutligen presenterar bilden med de så utvalda färgema.

2. Sätt enligt patentkravet 1, k å n n e t e c k n at av att man efter en delning kontrollerar om man kan finna två närliggande block som kan slås samman utan att det sammanslagna blocket blir det största blocket och om så är fallet slår samman dem, varefter delning sker, varpå följer en ny kontroll om det är möjligt att slå samman block o.s.v.

3. Sätt enligt patentkravet 2, k å n n e t e c k n at av att man tillåter att de block som slås samman delvis överlappar varandra.

4. Sätt enligt något av patentkraven 1-3, k ä n n e t e c k n a t av att blockens storlek, vägd_storlek, jämförs baserat på storleken på blockens rymddiagonal i förhållande till övriga block, diagonaLrelativ, eller blockens pixelstorleki förhållande till övriga block, pixlar_relativ, eller en förutbestämd kombination av dem.

5. Sätt enligt något av patentkravet! 1_-3, k ä n n e t e c k n at av att blockens storlek, vägd_storlek, jämförs baserat på storleken på blockens rymddiagonal, till l 511 10 15 20 25 30 35 669 12 diagonal, eller denna storhet multiplicerad med den relativa pixeldensiteten, pixeldensitet_relativ, för blocken eller en förutbestämd kombination av dem.

6. Sätt enligt något av patentkraven 1-5, k ä n n e t e c k n a t av att sidomas längd, färg_vägd_stor|ek, jämförs baserat på längden på resp. sida i ett block i förhållande till längden på motsvarande sida i genomsnitt, färg__storlek dividerat med medelstorlek, eller standardawikelsen för resp. färg i ett block i förhållande till motsvarande standardawikelse i genomsnitt, färg_awikelse dividerat med medelawikelse, eller en förutbestämd kombination av dem.

7. Sätt enligt något av patentkraven 1-5, k ä n n e t e c k n a t av att sidornas längd, färg_vägd_storlek, jämförs baserat på längden på resp. sida i ett block, färg_storlek, eller standardavvikelsen för resp. färg i ett block, färg_awíkelse, eller en förutbestämd kombination av dem.

8. Sätt enligt något av patentkraven 1-7, k ä n n e t e c k n at av att läget för delning av en sida, färg_klyv, bestäms baserat på sidans mittpunkt, färg_mitt, eller färgnivåns medelvärde, färg_medel, eller en förutbestämd kombination av dem.

9. Sätt enligt patentkravet 8, med beräkning av blockens storlek enligt patentkravet 4 eller 5, sidomas längd enligt patentkravet 6 eller 7 och läget för delning enligt patentkravet 8, k ä n n e t e c k n a t av att nämnda storheter beräknas som den i resp. krav angivna förutbestämda kombinationen av storheter och där samma förhållande mellan den aktuella förstnämnda storheten och den andra storheten används i de tre fallen.

10. Sätt enligt något av patentkraven 1-9, k ä n n e t e c k n at av att den färg som skall representera ett block utgörs av skämingspunkten mellan de tre plan som skulle användas om blocket skulle delas längs sina tre färgaxlar, färg1_klyv, färg2_klyv resp. färg3_klyv, vanligen röd_klyv, grön_klyv och blå_klyv.

11. Sätt enligt något av patentkraven 1-10, k ä n n e t e c k n at av att de celler i histogrammet som endast innehåller ett fåtal pixlar, företrädesvis högst 10 stycken, nollställs innan trimning och delning inleds och i de fall de hamnar utanför ett block under delningsförfarandet används vid den avslutande presentationen i resp. fall en färg som ligger närmast den urspmngliga färgen.