Beeldkwantiseringsmethode. Overgang van continue signalen en transformaties naar discrete signalen

Trekt de aandacht

Het goede oude GIF-formaat gebruikt bijvoorbeeld een palet van maximaal 256 kleuren. Als je een reeks van je selfies wilt opslaan als GIF-animatie (wat maakt het uit), dan is het eerste wat je moet doen preciezer het programma, die u hiervoor gaat gebruiken, moet u doen: een palet maken. U kunt een statisch palet gebruiken, bijvoorbeeld webveilige kleuren. Het kwantiseringsalgoritme zal heel eenvoudig en snel blijken te zijn, maar het resultaat zal niet erg goed zijn. U kunt een optimaal palet maken op basis van de kleuren in de afbeelding, waardoor een resultaat ontstaat dat visueel het meest lijkt op het origineel.

Er zijn verschillende algoritmen voor het creëren van een optimaal palet, elk met zijn eigen voor- en nadelen. Ik zal de lezer niet lastig vallen met vervelende theorieën en formules, ten eerste ben ik lui, en ten tweede zijn de meeste mensen hier niet in geïnteresseerd - ze scrollen gewoon door het artikel en kijken naar de afbeeldingen.

Vervolgens zul je een saai en onbegrijpelijk verhaal vinden over de mediaansectiemethode, het Floyd-Steinberg-foutverspreidingsalgoritme (kwantiseringsruis) (en niet alleen), de eigenaardigheden van de kleurwaarneming van het menselijk oog, evenals wat code-shit.

Achtergrond

Lang geleden, toen Nokia nog warm was en tube de smartphonemarkt domineerde, en smartphonebezitters zichzelf trots 'smartphonemensen' noemden, schreef ik in die oudheid eenvoudige programma's in Python voor de serie60. Ik kwam er laatst eentje tegen toen ik door de archieven aan het graven was. GifTool is een programma voor het maken van GIF-animaties van een reeks afbeeldingen. Daarin implementeerde ik kwantisering met behulp van de mediaansectiemethode, het LZW-compressie-algoritme, de volledige bestandsstructuur werd onafhankelijk gemaakt en transparantie werd gebruikt voor pixels die niet veranderden op de volgende dia om de uiteindelijke bestandsgrootte te verkleinen. Ik wilde mijn geheugen opfrissen en zien hoe het werkte. Ik opende de code en... Dat gevoel als je je waardeloze code van tien jaar geleden niet meer kunt achterhalen. Ik kende toen nog niets van PEP8, dus de leesbaarheid van de code was iets minder dan onbestaande (destijds hield ik van minimalisme, zoals veel beginnende programmeurs). Ik liet een paar tranen vallen, spuugde, herwerkte het in PyCharm, ontdekte hoe ik de mediaansectiemethode moest implementeren en creëerde snel een 'vies' script. Werken! Het palet is gemaakt, het uitvoerbeeld is acceptabel. En toen begon ik me af te vragen of ik dat wel zou kunnen bereiken beste resultaten zodat de afbeelding visueel zo dicht mogelijk bij het origineel komt.

Een paar foto's zijn bijna on-topic, voor de duidelijkheid

Nu hebben we een optimaal palet, niet ideaal natuurlijk (ik weet dat het nog verder verbeterd kan worden), maar goed genoeg. De volgende stap is het indexeren van de kleuren van de afbeelding. De eenvoudigste optie is in welk segment de kleur zich bevindt, en dat geldt ook voor de index. Snel en gemakkelijk. Maar er is één maar, en niet eens één, dus deze stap we komen weer terug.

Er is een andere manier om de kwaliteit van het resulterende beeld te verbeteren: foutspreiding. Ook hier is alles vrij eenvoudig: we trekken de overeenkomstige kleur van het palet af van de geïndexeerde kleur, krijgen een fout, verspreiden deze over aangrenzende pixels in overeenstemming met een bepaalde formule(sjabloon), de bekendste Floyd-Steinberg-formule, ik heb deze gebruikt. Wanneer fouten diffuus zijn, worden scherpe overgangen tussen kleuren wazig en lijkt het beeld visueel meer schakeringen (kleuren) te bevatten. Als u geïnteresseerd bent, kunt u gedetailleerd en interessant lezen over foutspreiding. Ik besloot ook om dit algoritme te voltooien, door de fout met dezelfde coëfficiënten te vermenigvuldigen, zoals later bleek, dit was een heel goed idee - aangezien er minder secties in het blauwe bereik waren, werd er een significante fout in verkregen, en zonder de correctie te corrigeren fout door coëfficiënten, verstrooiing introduceerde veel “ruis” "

Nu kunt u weer terugkeren naar het indexeren. Door fouten te verspreiden, veranderen we de kleuren van de pixels en krijgen we de kleuren die niet in onze RGB-kubus zitten (laat me je eraan herinneren dat deze uitsluitend uit beeldkleuren bestaat). Nu kunt u niet alleen kijken naar welk segment een kleur zich bevindt om een ​​index toe te wijzen. De oplossing werd onmiddellijk gevonden: zoeken naar de dichtstbijzijnde kleur in het palet. IN deze formule Ik heb dezelfde coëfficiënten vervangen. Bij het vergelijken van de resultaten van het selecteren van een paletkleur op basis van de index van het segment dat de originele kleur bevat, en de resultaten van het zoeken naar de dichtstbijzijnde kleur, zag ik duidelijk dat de dichtstbijzijnde kleur vaak in het aangrenzende segment terechtkomt. Als de bronkleur dichter bij het midden van het segment ligt, komt de segmentindex overeen met de kleurindex in het palet, maar hoe dichter de bronkleur bij de randen van het segment ligt, hoe waarschijnlijker het is dat de dichtstbijzijnde kleur zich in het aangrenzende segment bevinden. Over het algemeen de enige de juiste manier indexering – zoek naar de dichtstbijzijnde kleur in het palet. Maar zoeken heeft een nadeel: het is langzaam, heel langzaam. Het schrijven van een getallenbreker in Python is een slecht idee.

Nou, ik wilde het in een notendop uitleggen, maar het bleek een heleboel onbegrijpelijke teksten te zijn. Ik hoop dat ik betere code schrijf dan ik uitleg, dus hier is een link naar github. De code werd verschillende keren herschreven, eerst werd het algoritme verbeterd, totdat het resultaat mij tevreden stelde, daarna bleek dat het te veel RAM in beslag nam bij het verwerken van foto's (eerst testte ik het op kleine foto's), ik moest de RGB overbrengen kubus, mediaansectie en pixelkaart naar de database (sqlite). Het script werkt erg langzaam, maar het resultaat is beter dan kwantisering met PIL/Pillow en GIMP (hierin wordt deze bewerking indexering genoemd).

Visuele demonstratie:

Origineel

Kwantiseringsresultaat in GIMP, optimaal palet van 256 kleuren + Floyd-Stenberg kleurvervaging (normaal)

Kwantiseringsresultaat PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, kleuren=256)

Resultaat van kwantisering door mijn code

Waar u op moet letten: de foutspreiding van GIMP is erg luidruchtig, PIL/Pillow creëert een niet erg optimaal palet en verdrijft praktisch geen fouten (scherpe overgangen tussen kleuren).
Als je het verschil niet ziet, kijk dan naar andere voorbeelden op github.

4.2.2. Beeldbemonstering en kwantisering

Het gegenereerde en opgenomen beeld moet worden omgezet in een daarvoor geschikte vorm digitale verwerking. Als beelden foto-elektronisch worden vastgelegd, is dit meestal geen probleem, aangezien de scannende fotocel ontvangt elektrische stroom, geschikt voor bemonstering en kwantisering. Dit geval kan dus worden beschouwd als een uitbreiding van de overeenkomstige digitale signaalverwerkingsmethoden van eendimensionale signalen naar tweedimensionale signalen. In dit geval kan met kwantiseringsfouten rekening worden gehouden door een extra ruisbron in het blokdiagram te introduceren. De afstand tussen monsters moet aan de stelling voldoen
Nyquist voor tweedimensionale oscillaties.

Apparaten voor het bemonsteren en kwantiseren van beelden zijn gebaseerd op microdensitometrietechnieken. In dergelijke systemen wordt een lichtstraal met intensiteit I1 op de film geprojecteerd. Intensiteit I2 van licht dat door de film wordt doorgelaten
(of daardoor gereflecteerd) wordt gemeten door een fotomultiplier. Door transmissie

(4.16) Met behulp van relatie (4.5) kan men de optische dichtheid berekenen. Hierna kan de lichtvlek op de film abrupt worden verschoven en zo beeldmonsters worden verkregen. Wiskundig wordt dit proces beschreven door de relatie

g1(x, y) = (4,17)

waarbij g het beeld op de film is; ha helderheidsverdeling in de dwarsdoorsnede van de straal die de film verlicht; g1 is het equivalente beeld waaruit monsters worden genomen (dat wil zeggen, op discrete punten x = jx, y = ky meet de scannende fotodetector precies g1). Voorbeeldmatrix g1 (jx, ky
) is een bemonsterde of digitale afbeelding.

Uit gelijkheid (4.17) (die ook geldt voor het bemonsteren van beelden verkregen met foto-elektronische middelen) wordt duidelijk dat tijdens het bemonsteringsproces het opgenomen beeld onderhevig is aan vervorming. Door de ha-verdeling en de afstand tussen de monsters goed te kiezen, kan het beeld tijdens het monsternameproces worden gefilterd. Filtering die verband houdt met het bemonsteringsproces [zoals gedefinieerd in vergelijking (4.17)] kan worden gebruikt om aliasing-effecten te onderdrukken die ontstaan ​​omdat de spectrale breedte van het beeld doorgaans onbeperkt is (als gevolg van filmkorrelruis en andere hoogfrequente componenten). Transmissiebemonstering is equivalent aan bemonstering van luminantiebeelden, en dichtheidsbemonstering is equivalent aan bemonstering van dichtheidsbeelden. Je hoort vaak dat het de voorkeur verdient om de dichtheid te kwantiseren, omdat de logaritmische afhankelijkheid leidt tot een afname van het dynamische bereik. Een dergelijke vereenvoudigde redenering kan echter tot fouten leiden.

4.2.3. Restauratie en tentoonstelling digitale afbeeldingen
Bij de digitale verwerking van eendimensionale signalen wordt de reconstructie van een analoog signaal uit een reeks getallen bereikt door laagdoorlaatfiltering, wat theoretisch gerechtvaardigd wordt door de interpolatiestelling voor oscillaties met een beperkt spectrum. Idealiter zou voor een dergelijke interpolatie een functie van de vorm sin moeten worden gebruikt. Deze functie heeft echter geen tweedimensionale optie die kan worden gebruikt om te herstellen analoge beelden, aangezien de impulsresponsie van een ideaal laagdoorlaatfilter, dat de vorm sin heeft, negatieve waarden aanneemt, en dit de eis naar voren brengt van het verkrijgen van negatief licht, wat onmogelijk is bij het herstellen van beelden.

Het analoge beeld kan worden gereconstrueerd met behulp van een apparaat dat vergelijkbaar is met het apparaat dat wordt gebruikt bij beeldbemonstering. Op de blanco film wordt een lichtstraal geprojecteerd en de intensiteit van deze opnamestraal wordt gemoduleerd volgens de numerieke waarden van het beeld. Ook te gebruiken als lichtbron en voor directe weergave van beelden. kathodestraalbuizen(CRT). De lichtvlek beweegt langs het oppervlak van de film volgens het rasterraster. Het is gemakkelijk in te zien dat het beeldherstelproces wordt beschreven door de relatie

g2(x, y) = (4,18)

waarbij hd de helderheidsverdeling van de opnamevlek is, g1 de bemonsteringsmatrix van functie (4.17), hier weergegeven door een reeks gewogen pulsen op afstanden (x, y) van elkaar, en g2 het gereconstrueerde continue beeld. De helderheidsverdeling van de opnamevlek is de impulsresponsie van een interpolatiefilter, vergelijkbaar met die gebruikt bij de reconstructie van eendimensionale analoge signalen. In bijna alle beeldherstelsystemen heeft de opnamevlek een eenvoudige helderheidsverdeling (bijvoorbeeld Gaussiaans). Om deze reden is het niet mogelijk om het beeld nauwkeurig te reconstrueren, aangezien eenvoudige verdelingen het niet mogelijk maken om hoogfrequente kopieën van het beeldspectrum die tijdens het bemonsteren ontstaan ​​volledig te onderdrukken. Gelukkig levert dit meestal geen noemenswaardige problemen op, en eenvoudige systemen leveren goede beelden op.

Uit het bovenstaande blijkt dat bij het bemonsteren en weergeven van beelden spectrumvervormingen optreden. Dergelijke vervormingen kunnen worden gecorrigeerd tijdens het digitaal filteren van gekwantiseerde beelden.
.
Continue beeldreconstructie brengt een ander probleem met zich mee, namelijk het probleem van de beeldgetrouwheid. Als een getal in het geheugen van de machine de waarde vertegenwoordigt optische dichtheid afbeeldingen op een specifiek punt, en dan absoluut getrouwe reproductie het komt uit als de voor demonstratie bestemde film exact dezelfde optische dichtheid heeft als vastgelegd in het computergeheugen. (Vergelijkbare eisen kunnen worden geformuleerd voor de filmtransmissie om het foto-elektronische systeem te karakteriseren). Gelijkaardig apparaat
Rijst. 4.4. a - end-to-end kenmerken van een ideaal displaysysteem; b - end-to-end kenmerken van een typisch voorbeeld echt systeem weergave.

Het display moet end-to-end-karakteristieken hebben die samenvallen met die getoond in Fig. 4.4, een. Dergelijke ideale kenmerken zijn echter zeldzaam. De kenmerken van echte weergaveapparaten lijken meer op die getoond in Fig. 4.4, b, waar er een significante afwijking is van de ideale rechte lijn met een helling van 45°. Een goede benadering van de ideale respons kan worden verkregen door de respons van het weergaveapparaat te lineariseren. Om dit te doen, moet u het volgende doen:

1. Genereer een reeks vaste waarden van transmissie of optische dichtheid, verzend deze naar het weergaveapparaat en meet de daadwerkelijke reactie op elk van de waarden van transmissie of optische dichtheid.
2. De metingen verkregen in stap 1 geven de karakteristiek van het weergaveapparaat d0 = f (di). De gelineariseerde karakteristiek wordt beschreven door de relatie di = f- -1(d0). Deze inverse transformatie kan empirisch worden gevonden en gepresenteerd in de vorm van een tabel of een polynoom berekend met de kleinste kwadratenmethode.

3. Voordat de afbeelding wordt weergegeven, moeten de numerieke gegevens worden geconverteerd volgens de f -1-functie. Als gevolg hiervan zal er pre-emphasis in worden geïntroduceerd en zullen de helderheidswaarden die in de machine zijn vastgelegd, foutloos op het scherm worden weergegeven.
De methode voor het lineariseren van de kenmerken van weergaveapparaten is bij velen met succes toegepast onderzoeksinstituten. Exacte linearisatie is uiteraard onmogelijk vanwege de vorm niet-lineaire karakteristiek varieert afhankelijk van de filmontwikkelingskenmerken, chemische zuiverheid en veroudering
(of schade) aan de fosfor van een CRT, enz. Met enige moeite is het echter mogelijk om het weergaveapparaat zo te lineariseren dat afwijkingen van de lineariteit niet groter zijn dan ±5% maximale waarde. Opgemerkt moet worden dat de linearisatie van de karakteristiek van het weergaveapparaat een bewerking is die wordt gebruikt bij analoge beeldreconstructie; bij het verwerken van eendimensionale signalen met lineair elektronische circuits het wordt meestal niet gebruikt.

4.2.4. Eigenschappen van het menselijk zichtsysteem

Heel vaak wordt de uiteindelijke beoordeling van een beeld door een mens gemaakt. Als het menselijk gezichtsvermogen ideaal zou zijn en met absolute nauwkeurigheid en perfecte lineariteit op licht zou reageren, zou het niet worden bestudeerd. Het menselijke zichtsysteem heeft echter een niet-lineair kenmerk en de reactie ervan is niet absoluut correct. Het belang van deze voorzieningen voor het verkrijgen van beelden wordt al lang onderkend, maar wordt bij de beeldverwerking nog niet ten volle benut.
Een van de kenmerken van het menselijk zichtsysteem is het vermogen om de helderheid van licht waar te nemen. Experimenten om te bepalen hoe mensen minimaal onderscheidbare gradaties waarnemen in de helderheid van licht afkomstig van een gekalibreerde bron hebben aangetoond dat de helderheid van licht niet-lineair door het oog wordt waargenomen. Als u een grafiek tekent van de afhankelijkheid van de waarde van deze minimaal te onderscheiden helderheidsgradatie van de referentiehelderheid, dan heeft deze grafiek, wanneer de helderheid binnen verschillende ordes van grootte verandert, een logaritmisch karakter
. Dergelijke subjectieve experimentele resultaten komen overeen met objectieve gegevens verkregen bij dierproeven, waarin werd aangetoond dat de lichtgevoelige cellen van het netvlies en de oogzenuw worden geëxciteerd met een frequentie die evenredig is met de logaritme van de intensiteit van het licht dat eraan wordt toegevoerd. Om voor de hand liggende redenen zijn dergelijke objectieve metingen niet bij mensen uitgevoerd. Objectieve gegevens voor dieren en subjectieve gegevens voor mensen ondersteunen echter meer dan overtuigend de conclusie dat de helderheid van licht

Rijst. 4.5. a - dwarsdoorsnede van de (asymmetrische) hardwarefunctie van het menselijk oog; b - doorsnede (asymmetrisch) frequentierespons menselijke ogen.

waargenomen volgens de logaritmische wet. Dit is in wezen een niet-lineaire wet.
Een ander onderscheidend kenmerk van het menselijk zichtsysteem is de ruimtelijke frequentierespons. De impulsrespons van het oog, beschouwd als een tweedimensionaal lineair systeem (dat wil zeggen lineair na een initiële logaritmische transformatie van de intensiteit van het waargenomen licht), is geen Dirac-functie. De reactie van het oog op het binnenkomende lichtveld wordt beschreven door een hardwarefunctie, waarvan de dwarsdoorsnede wordt getoond in Fig. 4,5, een
. De scherpe centrale piek en negatieve zijlobben van de impulsrespons van het oog geven aan dat het oog ruimtelijke frequenties op dezelfde manier verwerkt als een hoogdoorlaatfilter. De precieze vorm van de frequentierespons van het oog is onderzocht door middel van een reeks psychovisuele experimenten; Er is aangetoond dat het oog lage ruimtelijke frequenties onderdrukt en hoge ruimtelijke frequenties verzwakt. In ruwe benadering heeft de ruimtelijke frequentierespons van het oog een banddoorlaatkarakter. Een soortgelijk kenmerk (Fig. 4.5,b) werd bijvoorbeeld verkregen in een aantal experimenten uitgevoerd door Mannos en Sakrison.
Ten slotte is een kenmerk van het menselijk zicht het vermogen om te verzadigen, d.w.z. om de respons bij zeer hoge of zeer lage intensiteiten van het waargenomene te beperken lichtstroom. De opgesomde eigenschappen van het visiesysteem kunnen worden beschreven door een model dat wordt gepresenteerd in de vorm van een blokdiagram in Fig. 4.6. Dit model weerspiegelt echter helemaal niet andere bekende eigenschappen van het visiesysteem. Er zijn bijvoorbeeld aanwijzingen dat sommige aspecten van het proces van beeldperceptie alleen kunnen worden verklaard door de aanwezigheid van meer dan één, zoals in figuur 1. 4.6, en meerdere lineaire systemen, parallel geschakeld, d.w.z. in het kader van een model met frequentiekanalen. Andere visuele verschijnselen (zoals de illusie van gelijktijdig contrast) geven aan dat de logaritmische transformatie geïntroduceerd in het stroomdiagram van Fig. 4.6 is een te grote vereenvoudiging. Maar ondanks de bekende tekortkomingen is het model gepresenteerd in Fig. 4.6 is nuttig omdat het

Rijst. 4.6. Blokdiagram van het menselijk zichtsysteem.

2) geeft aan dat het visiesysteem enkele elementen van het informatieverwerkingssysteem bevat. In het bijzonder lijkt het menselijke visiesysteem enkele homomorfe uit te voeren.

Het is nuttig om de logaritmische transformatie van een beeld die door het oog wordt uitgevoerd in verband te brengen met de eerder besproken kwestie van dichtheids- (en luminantie-)beelden. Er kan worden opgemerkt dat, aangezien de luminantie van licht het oog beïnvloedt volgens een logaritmische wet, het oog waarneemt een beeld dat net zo compact is, zelfs als het (door middel van een weergaveapparaat) wordt gepresenteerd in de vorm van een helderheidsbeeld.
Het lijkt logisch om bij analyses modellen van het menselijk gezichtssysteem te gebruiken mogelijke toepassingen digitale beeldverwerking. Dit moet echter zorgvuldig gebeuren, omdat het menselijke zichtsysteem zo complex is dat het onredelijke gebruik van vereenvoudigde zichtmodellen meer kwaad dan goed kan doen. Mannoe en Sakrison bewezen de toepasbaarheid van het visiemodel om de kwestie van het verminderen van beeldredundantie te onderzoeken. Alle gebieden van mogelijke toepassingen van visiemodellen zijn echter nog niet geïdentificeerd.

4. 3. Gebruik van digitale verwerking om beeldredundantie te verminderen
Het verminderen van beeldredundantie is de eerste toepassing van digitale beeldverwerking die hier wordt besproken.
Intensieve ontwikkeling digitale methoden beïnvloedde alle takken van de technologie voor het verzenden en opslaan van informatie vanwege de inherente voordelen van digitale systemen op het gebied van ruisimmuniteit, het vermogen om fouten te corrigeren, flexibiliteit bij het schakelen van berichten, voortdurend dalende kosten en toenemende betrouwbaarheid. Gelijktijdig met de implementatie digitale technologie het gebruik van afbeeldingen in verschillende gebieden wetenschap en technologie, bijvoorbeeld in de geneeskunde, experimentele natuurkunde, contactloze detectie van fouten, onderzoek natuurlijke hulpbronnen. Deze parallelle ontwikkeling van digitale technologie en de uitbreiding van het toepassingsgebied van beelden leidden tot een natuurlijk resultaat, namelijk intensief onderzoek op het gebied van de overdracht en opname van beelden met behulp van digitale methoden.

Een typisch beeld bevat veel overbodige informatie, die zelfs bij een snelle blik op de meeste afbeeldingen opvalt. Deze overtolligheid leidt tot economische verliezen. De frequentiebandbreedte die nodig is om een ​​beeld in digitale vorm te verzenden, hangt af van het aantal beeldmonsters, de bitdiepte van de monsters, de tijd die is toegewezen voor verzending en het vermogen van de zender. Naarmate de bandbreedte toeneemt, nemen het benodigde zendvermogen en de kosten toe. Geld en energie zijn geen probleem, maar het elektromagnetische spectrum is extreem druk. Daarom is het verminderen van redundantie bij beeldoverdracht een zeer belangrijke taak. Het is net zo belangrijk voor het opslaan van afbeeldingen in digitale vorm.
Als u slechts één afbeelding hoeft op te slaan, hoeft u zich hier geen zorgen over te maken. Wel in veel bestaande en geplande systemen, zoals de NASA ERTS (Earth Resources Technology) exploratiesatelliet
Satelliet), zo blijkt groot aantal afbeeldingen die geschikt zijn om in digitale vorm te ontvangen en op te slaan. Hoewel digitale opslagapparaten goedkoper worden, neemt het aantal vastgelegde beelden zo sterk toe dat het terugdringen van beeldredundantie een topprioriteit is.

4.3.1. Enkele opmerkingen over het verminderen van beeldredundantie

De redundantie van video-informatie kan worden beschreven door de correlatiefunctie tussen beeldmonsters; het manifesteert zich in een hoge mate van wederzijdse statistische voorspelbaarheid van nabijgelegen metingen uit het beeld. Het uiteindelijke doel van de videocompressiebewerking is het elimineren van deze statistische voorspelbaarheid (d.w.z. het is noodzakelijk om de correlatie van monsters tot de maximaal mogelijke mate te beperken). In het blokschema Afb. Figuur 4.7 toont de belangrijkste handelingen die door het videocompressiesysteem worden uitgevoerd. Eerst wordt een bewerking uitgevoerd om de correlatie van beeldmonsters te minimaliseren. De monsters moeten vervolgens dienovereenkomstig worden gekwantiseerd. De gekwantiseerde monsters worden gecodeerd in een vorm die gunstig is voor verzending (en uiteraard kan foutdetectie of correctie mogelijk zijn).

Kwantisering en codering worden uitgevoerd rekening houdend met algemene regels, onafhankelijk van de kenmerken van het decorrelatieschema dat is gekozen voor de eerste verwerkingsfase.
Daarom verschillen videocompressiesystemen in het type circuit dat bewerkingen uitvoert die verband houden met de eerste fase. Daarom zijn de methoden voor het implementeren van het eerste blok van het circuit in Fig. 4.7 zal hier meer aandacht worden besteed dan aan vragen
Rijst. 4.7. Blokschema van een systeem voor het verminderen van redundantie van video-informatie.

bouw van het tweede en derde blok. Deze benadering komt volledig overeen met de bedoeling van dit boek, dat hieraan is opgedragen technische toepassingen digitale signaalverwerking, d.w.z. taken die voornamelijk verband houden met het eerste blok.

Bij het ontwikkelen van de implementatieprincipes van het eerste blok van het diagram in Fig. 4.7 Er zijn een aantal overwegingen waarmee rekening moet worden gehouden. Laten we eerst eens kijken naar de statistische eigenschappen van afbeeldingen. Als de beeldmonsters een raster van punten met de grootte NN vormen en elk monster wordt weergegeven door een dubbel P-bit-getal, dan zijn bij het opnemen en verzenden van een beeld met behulp van conventionele pulscodemodulatie (PCM) N2P binaire cijfers vereist. Zoals hierboven opgemerkt, heeft een typisch beeld echter veel redundantie. Eén manier om deze redundantie te meten en te vergelijken met het nominale aantal N2P-bits is door een histogram van de beeldhelderheid uit te zetten en de overeenkomstige entropie te berekenen. Met behulp van P-bit-getallen kan men de kwantisering in 2p-niveaus beschrijven. Om dit te doen, moet u alle N2-monsters analyseren en tellen hoe vaak elk kwantiseringsniveau voorkomt.
Vervolgens moet u een histogram van de helderheid van het beeld maken, d.w.z. Geef voor elk kwantiseringsniveau het aantal keren aan dat het in de afbeelding voorkomt. Door deze getallen te delen door het totale aantal punten N2 kunnen we een benadering verkrijgen van de waarschijnlijkheidsdichtheid van het proces dat het beeld genereert. Als we de genormaliseerde frequenties aangeven met pi (i = 1, 2, ..., 2p), dan wordt entropie per definitie uitgedrukt door de som h = __ (4,19) en is gelijk aan de gemiddelde informatie (gemeten door de aantal bits per beeldelement) in elk element van de afbeelding. Uit beeldanalyse bleek dat de typische waarde van h veel kleiner is dan het aantal cijfers
P vereist voor standaard PCM-weergave. In het werk werd opgemerkt dat entropie in de orde van grootte van 1 bit/punt ligt. Dit betekent dat de bitdiepte van de array die het beeld beschrijft (althans theoretisch) kan worden teruggebracht zonder verlies van informatie tot gemiddeld 1 bit/punt.

Entropie biedt een maatstaf voor statistische redundantie, maar geeft geen informatie over de oorsprong ervan. De bron van overtolligheid is, zoals zijn visie de waarnemer vertelt, dat wel hoge graad beelduniformiteit in kleine gebieden. Deze ruimtelijke redundantie kan worden bepaald met behulp van de beeldcovariantiematrix. Eerst wordt de matrix van NN-beeldmonsters lexicogetransformeerd in een N2-componentvector [d.w.z. elementen van de eerste rij (of kolom) van de matrix g(j, k) worden componenten van de vector met getallen van 1 tot N, elementen van de tweede rij (kolom)
- componenten met nummers van N+1 tot 2 N, etc.]. Vervolgens wordt de covariantiematrix van het beeld berekend

[ Cg ] = E ( (g - E(g))(g - E(g))T ) ,

(4.20) waarbij E de gemiddelde waarde van het ensemble is, en g een vector is die is opgebouwd uit beeldmonsters. In de praktijk is het zelden mogelijk om ensemblemiddeling uit te voeren en wordt de covariantiematrix verkregen door het schatten van de ruimtelijke correlatie.

Covariantiestructuren, zoals de [Cg]-matrix, hebben geen één-op-één-relatie met het originele beeld. Cole toonde aan dat veel ongelijksoortige afbeeldingen qua covariantie sterk op elkaar kunnen lijken
(of spectraal) gevoel. Er zijn dus redenen om een ​​complexe matrixstructuur te vervangen door een eenvoudigere. In het bijzonder werd de toepassing van een model met een autoregressief Markov-proces van de n-de orde, waarbij n gewoonlijk klein is, overwogen (zie bijvoorbeeld werk)
(bijvoorbeeld n = 3). Het feit dat dergelijke modellen correct blijken te zijn en dat het gebruik ervan gerechtvaardigd is bij het analyseren van informatiecompressiemethoden, zoals differentiële pulscodemodulatie (DICM), duidt op een hoge mate van onderlinge verbinding tussen aangrenzende beeldgebieden.
Bij het comprimeren van video-informatie is het, naast de statistische eigenschappen van de afbeelding, erg belangrijk om rekening te houden met de kenmerken van de ontvanger van de afbeelding. Menselijke visie heeft handicaps en wordt gekenmerkt door enkele bekende (deels) onderscheidende kenmerken. Het gebruik van specifieke kenmerken van het gezichtsvermogen om beeldredundantie te verminderen, wordt psychofysische verwerking genoemd. Het is bijvoorbeeld bekend dat het visuele systeem zich bij het waarnemen van de helderheid van licht dat het oog binnenkomt, gedraagt ​​als een niet-lineair systeem met een logaritmische karakteristiek. Bovendien is het menselijke visuele systeem niet gevoelig voor zeer hoge of zeer lage ruimtelijke frequenties, en gedraagt ​​het zich in het middenfrequentiegebied bijna als een banddoorlaatfilter, wat te wijten is aan de remming van retinale zenuwcellen. De niet-lineariteit en frequentieafhankelijkheid van de gevoeligheid van het visuele systeem maakten het mogelijk om optimale compressiesystemen voor video-informatie te creëren. Om een ​​grotere weerstand te bieden tegen fouten die optreden tijdens het coderen en verzenden, wordt het beeld in deze systemen op ongeveer dezelfde manier verwerkt als in het menselijke visuele systeem. Dit voorstel werd als eerste gedaan
Stockham.
Het verminderen van informatieredundantie wordt wiskundig strikt gerechtvaardigd door de bepalingen van de coderingstheorie met een bepaald nauwkeurigheidscriterium. Zoals Mannos en Sakrison opmerkten, was het niet mogelijk om effectieve stellingen van de coderingstheorie toe te passen voor een bepaald nauwkeurigheidscriterium bij problemen met de compressie van video-informatie. De belangrijkste reden hiervoor was de moeilijkheid om een ​​criterium voor de toelaatbare omvang van fouten te kiezen dat consistent is met de eigenschappen van het menselijk zichtsysteem. Mannoe en Sakrison konden aantonen dat het mogelijk is een criterium te gebruiken dat verband houdt met de niet-lineaire en ruimtelijke frequentie-eigenschappen van het gezichtsvermogen. Hun werk is van groot belang voor de verdere ontwikkeling van methoden om beeldredundantie te verminderen. De introductie van geschikte voorverwerking in alle schema's die hieronder zullen worden besproken, kan de kwaliteit van videocompressiesystemen aanzienlijk verbeteren.

4.3.2. Reductieschema's voor beeldredundantie met ruimtelijke domeinverwerking
In een van mogelijke opties schema voor het verminderen van redundantie van video-informatie in het eerste blok (diagram in figuur 4.7), wordt de identiteitsbewerking uitgevoerd, d.w.z. het originele beeld wordt op geen enkele manier gewijzigd en alle compressie wordt bereikt door middel van kwantisering en codering. Informatiecompressie kan echter niet worden uitgevoerd zonder criteria te gebruiken die rekening houden met de kenmerken van de waarnemer en de eigenschappen van de verzonden gegevens. Als een waarnemer bijvoorbeeld een nauwkeurigheid van 1/1000 nodig heeft, wordt het vereiste aantal kwantiseringsniveaus verkregen door gebruik te maken van binaire getallen van 10 bits; als nauwkeurigheid acceptabel is
1/8, dan is het voldoende om getallen van 3 cijfers te nemen. Bijgevolg speelt kwantisering een beperkte rol bij informatiecompressie. Het verminderen van de redundantie kan echter worden bereikt tijdens het coderen, en een van de hoofdtaken na het maken
Shannons informatietheorie was de constructie van codes die optimaal waren vanuit het oogpunt van het verminderen van redundantie van informatie. Shannon bewees dat er een code bestaat waarvan de transmissiesnelheid samenvalt met de snelheid waarmee de bron informatie creëert. Voor beelden met een entropie in de orde van grootte van 1 bit/punt bestaan ​​er dus coderingsschema's die het mogelijk maken codes te construeren met een gemiddelde lengte van 1 bit/punt. Helaas is het loutere bestaan ​​van dergelijke codes nutteloos als er geen algoritmen zijn voor de constructie ervan. Er zijn algoritmen bekend voor het construeren van codes die de optimale codes benaderen. Huffman-codering is bijvoorbeeld een efficiënte procedure om de code af te stemmen op de statistieken van de informatiebron en maakt kortere signaallengten mogelijk dan standaard PCM. Dergelijke codes hebben echter een variabel aantal tekens (dat wil zeggen dat bij het verzenden van berichten de codewoorden bestaan ​​uit: verschillende nummers karakters); het coderen en decoderen vereist complexe algoritmen die verband houden met het opnemen, synchroniseren en aanvullende accumulatie van informatie. Bovendien hangt het uiterlijk van dergelijke codes in grote mate af van de waarschijnlijkheid dat de bron de symbolen heeft gemaakt, en elke verandering in de waarschijnlijkheid kan leiden tot een verslechtering van de kenmerken van de code (in sommige gevallen zeer significant). Bijgevolg kan kwantiseringscodering slechts in een beperkt aantal gevallen dienen als het belangrijkste middel voor videocompressie, dus is het noodzakelijk om naar andere methoden te zoeken.

Als een methode voor het comprimeren van video-informatie in het vlak van ruimtelijke coördinaten, uitgevoerd in het eerste blok van het diagram in Fig. 4.7, het meest gebruikte differentieel pulscodemodulatie(DICM). De structuur van DPCM-schema's is vergelijkbaar met lineaire voorspellingscodering (LPC)-schema's die worden gebruikt bij compressie van de spraakbandbreedte, en daarom worden DPCM-beeldschema's soms voorspellende compressieschema's genoemd. Het DPCM-blokdiagram wordt getoond in Fig. 4.8. Deze methode maakt gebruik van de statistische relatie tussen de helderheid van individuele beeldpunten en voor elk punt wordt een helderheidsschatting gevormd in de vorm van een lineaire combinatie van de helderheid van voorgaande punten. Met voorafgaande punten bedoelen we punten die zich vóór het betreffende punt bevinden wanneer het beeld van boven naar beneden en van links naar rechts wordt gescand (zoals bij televisie), waardoor een zeer specifieke volgorde van beeldpunten ontstaat. Een soortgelijk schema zal uiteraard van toepassing zijn, zelfs als de afbeelding al is "uitgevouwen" door te scannen. Het verschil tussen de werkelijke helderheidswaarde en de schatting ervan wordt vervolgens berekend en gekwantiseerd.
Het gekwantiseerde verschil wordt gecodeerd en via het kanaal verzonden. Aan de ontvangende kant worden de symbolen gedecodeerd en wordt de informatie gereconstrueerd met behulp van een lineair voorspellingscircuit van de n-de orde (uiteraard identiek aan het corresponderende circuit bij de zender), dat luminantieschattingen genereert die worden opgeteld bij de ontvangen verschillen over de zender. kanaal.

De voorspellingsschema's getoond in Fig. 4.8 worden achterwaarts voorspellende circuits genoemd vanwege de signaalkwantisering

Rijst. 4.8. Blokschema van een DPCM-compressiesysteem met een voorspeller van de n-de orde.

gebeurt binnen de lus feedback, en wanneer het signaal is hersteld, wordt de voorspelde waarde teruggekoppeld via het circuit. Er kunnen circuits worden ontworpen
DPCM, waarin de voorspelde signaalwaarden worden doorgegeven, en creëren ook DPCM-circuits, waarbij de kwantiseerder zich buiten de feedbacklus bevindt. Dergelijke systemen produceren echter een gereconstrueerd beeld met grote fouten. Er is een achterwaarts voorspellend circuit in de ontvanger nodig omdat de symbolen opeenvolgend arriveren. Als een soortgelijk achterwaarts voorspellingscircuit in de zender zou worden gebruikt, zou het, bij afwezigheid van kwantiseringsfouten, mogelijk zijn om het beeld met absolute nauwkeurigheid te reconstrueren. Als het kwantiseringscircuit is opgenomen in de lus van het voorspellende circuit van de zender, zullen zowel de ontvanger als de zender voorspellen op basis van dezelfde gekwantiseerde monsters, wat reconstructiefouten zal verminderen.

Compressie in DPCM-circuits wordt bereikt door signalen af ​​te trekken, aangezien de verschillen een veel kleiner dynamisch bereik hebben. Stel bijvoorbeeld dat het originele beeld wordt verzonden via de PCM-methode en dat er getallen van 0 tot 255 nodig zijn om de helderheid van de punten weer te geven. Als de toegestane fout dan gelijk is aan de minst significante, dan wordt de kwantisering in 8- uitgevoerd. bitnummers zijn noodzakelijk. De waarden van de helderheidsverschillen van aangrenzende punten zullen echter veel kleiner zijn; als de verschillen (op dezelfde schaal) variëren van 0 tot 7, om een ​​fout te verkrijgen, gelijk aan één minst significante cijfers, kwantisering in getallen van 3 bits is voldoende.

(4.21) voor alle k, аi

Dit is een bekend probleem, en als het proces g(k) stationair is, heeft de oplossing de vorm

, (4.22) waarbij r (j - i) = E [ g (k - j) g (k -i) ]

gewoonlijk de autocorrelatiefunctie van proces g genoemd. De coëfficiënten ai worden verkregen door het oplossen van het stelsel vergelijkingen (4.22).

De optimale waarden van de voorspellingscoëfficiënten zijn afhankelijk van de relaties tussen de beeldpunten die worden beschreven door de autocorrelatiefunctie. Uit de definitie
(4.20) het is duidelijk dat in het geval van stationaire gegevens de autocorrelatiefunctie verschilt van de bovenstaande functie door constante waarde. Voor niet-stationaire gegevens is de functie r (in vergelijking (4.23)) afhankelijk van ruimtelijke variabelen en moeten de optimale voorspellingscoëfficiënten variëren afhankelijk van de ruimtelijke coördinaten. Gelukkig kunnen de niet-stationaire statistische kenmerken van afbeeldingen dat wel zijn meestal vrij goed worden benaderd door stationaire functies, zodat het niet-stationaire lineaire voorspellingsapparaat behoorlijk wat oplevert goede resultaten. Bij het comprimeren van video-informatie met behulp van de DPCM-methode verschijnen er meestal fouten aan de grenzen van afgebeelde objecten, waar in de minste mate aan de aanname van stationariteit wordt voldaan, en in het gereconstrueerde beeld worden ze visueel waargenomen als abnormaal lichte of donkere punten.

De keuze van het aantal kwantiseringsniveaus en de locatie van kwantiseringsdrempels is deels kwantitatief en deels kwalitatief.
De locatie van de kwantiseringsdrempels kan worden gevonden door kwantitatieve berekeningen. Het werk van Max was het eerste dat rekening hield met niet-uniforme kwantisering, die afhangt van de distributiefunctie van het gekwantiseerde signaal en de wortelgemiddelde kwadratische waarde minimaliseert van de fout die wordt veroorzaakt door het beperkte aantal kwantiseringsniveaus. Met het algoritme van Max kun je de optimale locatie van overgangspunten vinden voor een bepaald aantal kwantiseringsniveaus. Het aantal kwantiseringsniveaus wordt echter gekozen op basis van subjectieve kwalitatieve overwegingen.

Het minimumaantal kwantiseringsniveaus is twee (getallen van één cijfer) en komt overeen met een dergelijke kwantisering van beelden waarbij het helderheidsverschil een vaste (positieve of negatieve) waarde aanneemt. Deze methode wordt gewoonlijk deltamodulatie genoemd; het DPCM-circuit (Fig. 4.8) kan worden vereenvoudigd door de kwantiseerder te vervangen door een begrenzer, en de voorspeller van de n-de orde door een integrator. Bij het verminderen van beeldredundantie met behulp van de deltamodulatiemethode worden dezelfde nadelen waargenomen als bij deltamodulatie van andere signalen, zoals spraak, namelijk de verlenging van randen en fragmentatievervormingen. Als de bemonsteringssnelheid van de afbeelding echter veel wordt gekozen meer frequentie Echter, compressie met behulp van de deltamodulatiemethode leidt tot kleine (subjectief waarneembare) fouten. Als de bemonsteringsfrequentie de Nyquist-frequentie benadert, vertoont het beeld meer sleepbewegingen (aan de randen van de afbeeldingen) en verpletterende vervorming (in gebieden met constante helderheid). Net als bij spraakcompressie kan adaptieve deltamodulatie deze fouten verminderen. Over het algemeen bleek deltamodulatie bij het verzenden van beelden echter minder effectief te zijn dan bij het verzenden van spraak.

Kwantisering met een aantal niveaus groter dan twee maakt het mogelijk om beelden van meer niveaus te verkrijgen hoge kwaliteit. Een DPCM-compressiesysteem met 8-niveaus (3-bit) kwantisering produceert, wanneer optimaal geplaatst op drempels, beelden van dezelfde kwaliteit als een PCM-systeem met een bitdiepte van 6 tot 8, met uitzondering van fouten in de buurt van helderheidslijnen.

Het signaal van de uitgang van de kwantiseringsinrichting moet uiteraard gecodeerd zijn, aangezien de waarschijnlijkheidsverdeling van de gekwantiseerde verschillen niet uniform is. Met een succesvolle codekeuze (bijvoorbeeld Shannon - Fano-code of
Huffman) slaagt erin de algehele snelheid van informatiecreatie verder te verlagen. Pratt wijst erop dat het bij gebruik van de Huffman-code mogelijk is om de informatiecreatiesnelheid terug te brengen tot 2,5 bits/punt. Deze extra snelheidsvermindering moet worden afgewogen tegen de toegenomen kosten en complexiteit van het geheugen, de synchronisatoren en de hulpgeheugenregisters die nodig zijn om Huffman-codes uit te voeren.

De kwesties van beeldcompressie met behulp van DPCM bij het selecteren van elementen per lijn zijn hierboven besproken (dat wil zeggen, punten die op de huidige scanlijn liggen, werden genomen voor voorspelling). Vanwege de tweedimensionale aard van afbeeldingen is het mogelijk (en raadzaam) om de DPCM-methode uit te breiden, zodat de voorspelling rekening houdt met de helderheid op punten die niet alleen op de huidige, maar ook op eerdere scanlijnen liggen. DPCM-compressieschema's met dergelijke tweedimensionale voorspelling zijn gebaseerd op dezelfde principes als die voor eendimensionale voorspelling. Omdat afbeeldingen worden gekenmerkt door tweedimensionale statistische relaties, kan men hopen dat tweedimensionale voorspelling betere resultaten zal opleveren bij beeldcompressie, aangezien beelddecorrelatie met behulp van voorspellings- en aftrekbewerkingen langs twee coördinaten zal worden uitgevoerd. Apparaten met ruimtelijke voorspelling produceren inderdaad betere beelden. Habibi toonde aan dat met behulp van een tweedimensionaal voorspellend apparaat van de derde orde met kwantisering op 8 niveaus (3-bits) beelden werden verkregen die niet visueel konden worden onderscheiden van originele foto's, verwerkt door PCM met 11-bits getallen.

Voor beelden die uit opeenvolgende frames bestaan, zoals televisie, kunnen de ideeën van voorspelling en aftrekking geassocieerd met DPCM worden uitgebreid naar het tijdsdomein. In dergelijke afbeeldingen verandert de helderheid van veel punten niet van frame tot frame of verandert deze langzaam.
Daarom is het mogelijk om een ​​DPCM-compressiesysteem te construeren waarin de helderheid van het volgende punt wordt voorspeld op basis van de helderheid van een tweedimensionale reeks punten van het huidige frame en de overeenkomstige punten van voorgaande frames. In de praktijk kan de volgorde van de temporele voorspelling niet hoog zijn, omdat het voor elke temporele term noodzakelijk is om een ​​opslagapparaat te hebben waar het hele frame zou worden opgeslagen. Simulaties met een derde-orde voorspeller, waarbij punten in de huidige (en voorgaande frames) links van en boven het betreffende punt werden gebruikt voor voorspelling, lieten zien dat er zeer goede beelden kunnen worden verkregen met een gemiddelde bitdiepte van 1 beetje/punt.

4.3.3. Schema's voor het verminderen van beeldredundantie bij verwerking in het transformatiedomein

Om de belangrijkste bewerkingen uit te leggen die worden uitgevoerd door het videocompressiesysteem met verwerking in het transformatiedomein, gaan we naar de covariantiematrix gedefinieerd door relatie (4.20). De matrix beschrijft de correlatie van beeldmonsters in het (x, y)-vlak, dat het coördinatenvlak van het beeld is. Een belangrijke methode voor multivariate statistische analyse is de studie van een data-array, niet alleen in hun natuurlijke coördinaten, maar ook in coördinatensystemen met handiger eigenschappen. Met name coördinatensystemen gebaseerd op eigenwaarden en eigenvectoren van de covariantiematrix zijn zeer nuttig gebleken

[ Cg ] = [ Ф ] [ ] [ Ф ]T = ,

(4.24) waarbij [Ф] een matrix is ​​die is samengesteld uit orthogonale eigenvectorkolommen Фi en [] een diagonale matrix van eigenwaarden is.

De coördinatentransformatie, gedefinieerd door de matrix van eigenvectoren [Ф], heeft de eigenschap dat deze een gegeven reeks getallen omzet in een andere met niet-gecorreleerde elementen, en dat de resulterende componenten afnemende varianties hebben. Laat de eigenwaarden van de matrix
gerangschikt in aflopende volgorde en zo genummerd

, (4.25) en laat de bijbehorende eigenvectoren in dezelfde volgorde rangschikken. Dan heeft de matrix van eigenvectoren [Ф] de eigenschap dat vermenigvuldiging met de beeldvector g (gevormd door de lexicografische rangschikking) de vector oplevert

(4.26) met niet-gecorreleerde componenten, en de componenten van de vector G blijken te zijn gerangschikt in afnemende volgorde van hun varianties, wat een eigenschap is van de discrete versie van de Karhunen-Loeve-expansie, feitelijk beschreven door relaties (4.24) - ( 4.26).
Het nut van de Karhunen-Loeve (KL, of covariantie) transformatie voor het verminderen van beeldredundantie ligt voor de hand. De reeks beeldmonsters wordt vervangen door een reeks variabelen met verschillende statistische gewichten.
Verdichting kan worden bereikt door variabelen met een laag statistisch gewicht weg te laten en de rest te behouden. Als we bijvoorbeeld M

Annotatie: Invoering. Algoritme voor uniforme verdeling van de kleurruimte. Algoritme voor het partitioneren op frequentie van voorkomen: idee van het algoritme, methode voor het partitioneren van een kleurenkubus - lokaal gesorteerde zoekopdracht. Mediaan cut-algoritme. Clustermethoden voor beeldkwantisering: K-means-methode, grafiekconnectiviteitsmethode, hiërarchische methode, gegeneraliseerde K-means-methode of dynamische condensatiemethode. Conclusie.

12.1. Invoering

Conversieproces analoog signaal in digitale vorm bestaat uit drie fasen: sampling ("Sampling. Antialiasing. Geometrische transformaties van rasterafbeeldingen"), kwantisering en codering. Deze lezing bespreekt de tweede fase. Kwantisering- dit is de vervanging van een referentiewaarde door de dichtstbijzijnde waarde uit een reeks vaste waarden. Wanneer toegepast op afbeeldingen betekent dit het verminderen van het aantal attribuutwaarden voor elke pixel, of, eenvoudiger gezegd, het verminderen van het aantal kleuren in de afbeelding. Dit vereist dat de beeldkwaliteit zo min mogelijk achteruitgaat. De kwantiseringsoperatie wordt ook gebruikt op reeds gedigitaliseerd materiaal.

Kwantisering is nodig voor:

• geheugen opslaan;
• het verbeteren van de eigenschappen van sequenties voor compressie;
• voorbereiding voor daaropvolgende verwerking;
• effecten toevoegen.

Laten we deze punten in meer detail bespreken met betrekking tot afbeeldingen.

Geheugenbesparingen worden uiteraard bereikt door de kosten voor het opslaan van attribuutwaarden te verlagen. Veel beeldopslagformaten, zoals PNG en GIF, slaan referentienummers op in paletrijen, in plaats van attribuutwaarden op te slaan. Een palet is een tabel waarvan de rijen een vaste attribuutwaarde bevatten. Voorheen werd het paletmechanisme gebruikt om afbeeldingen te vormen en weer te geven, omdat de hoeveelheid videogeheugen vóór 1995 meestal desktopcomputer niet groter was dan één megabyte.

Het verbeteren van de eigenschappen van reeksen voor compressie wordt bereikt door het aantal mogelijke waarden te verminderen en daardoor het aantal herhalingen te vergroten.

Rijst. 12.1.

Voor sommige algoritmen is voorbereiding voor daaropvolgende verwerking noodzakelijk, waarvan de complexiteit in belangrijke mate afhangt van het aantal mogelijke attribuutwaarden. In dit geval verschilt het resultaat van de werking van het algoritme vaak niet of slechts in geringe mate.

Beeldkwantisering kan worden gebruikt om artistieke effecten toe te voegen en randen te accentueren.

Deze lezing gaat ervan uit dat de attribuutwaarden van de pixels van een afbeelding in de RGB-kleurruimte liggen ("Basisconcepten: Representing Color in Computer Graphics"). Voor het gemak zijn de pseudocodes van de algoritmen gegeven voor een 8-bits halftoonafbeelding (256 tinten) (zie figuur 12.1), de conversie wordt uitgevoerd naar een 4-bits afbeelding (16 tinten).

12.2. Algoritme voor uniforme verdeling van de kleurruimte

Laten we eens kijken naar het eenvoudigste kwantiseringsalgoritme: algoritme voor uniforme verdeling van de kleurruimte, ook wel genoemd lineaire kwantisering . Laten we het opsplitsen kleur ruimte in gelijke delen in elk van de hoofdrichtingen (voor RGB zijn er drie van dergelijke richtingen - afhankelijk van het aantal componenten). In de richting van de blauwe of groene as (zie figuur 1.5) verdelen we de kubus bijvoorbeeld in 8 delen, en in de richting van de rode as - in 4. We voeren de reeks waarden in die worden gevormd op de kruising van de partities in de tabel. In ons voorbeeld krijgen we 256 waarden, gelijkmatig verdeeld over de RGB-kubus. Vervolgens komt beeldconversie neer op het zoeken naar het overeenkomstige nummer in de tabel, zodat de afstand tussen de echte kleur en de vervanging ervan minimaal is. Met behulp van afronding kunt u dit snel doen.

// van de 256 grijstinten maken we er 16 // I(pixel) - pixelattribuut // Inew(pixel) nieuw attribuut - referentienummer in het palet // Palet - palet // aantal tinten in de originele afbeelding NOlColors = 256; // aantal elementen in het palet NNewColors = 16; // 1. Vul het palet voor(i = 0; i< NNewColors; i++) { Palette[i] = i * (NOldColors / NNewColors); } // 2. Вычиcляем новые значения атрибутов foreach(pixel in I) // для каждого пикселя { // округляем, отбрасывая fractioneel deel Inieuw(pixel) = I(pixel) / (NOlKleuren / NNieuwKleuren); ) Lijst 12.1.

Algoritme voor uniforme verdeling van de kleurruimte Als gevolg van de werkzaamheden (van dit algoritme zie afb. 12.2

Trekt de aandacht

Het goede oude GIF-formaat gebruikt bijvoorbeeld een palet van maximaal 256 kleuren. Als je een reeks van je selfies wilt opslaan als GIF-animatie (wie heeft dat nodig), dan is het eerste dat jij, of beter gezegd het programma dat je hiervoor gaat gebruiken, een palet moet maken. U kunt een statisch palet gebruiken, bijvoorbeeld webveilige kleuren. Het kwantiseringsalgoritme zal heel eenvoudig en snel blijken te zijn, maar het resultaat zal niet erg goed zijn. U kunt een optimaal palet maken op basis van de kleuren in de afbeelding, waardoor een resultaat ontstaat dat visueel het meest lijkt op het origineel.

Er zijn verschillende algoritmen voor het creëren van een optimaal palet, elk met zijn eigen voor- en nadelen. Ik zal de lezer niet lastig vallen met vervelende theorieën en formules, ten eerste ben ik lui, en ten tweede zijn de meeste mensen hier niet in geïnteresseerd - ze scrollen gewoon door het artikel en kijken naar de afbeeldingen.

Vervolgens zul je een saai en onbegrijpelijk verhaal vinden over de mediaansectiemethode, het Floyd-Steinberg-foutverspreidingsalgoritme (kwantiseringsruis) (en niet alleen), de eigenaardigheden van de kleurwaarneming van het menselijk oog, evenals wat code-shit.

Achtergrond

Lang geleden, toen Nokia nog warm was en tube de smartphonemarkt domineerde, en smartphonebezitters zichzelf trots 'smartphonemensen' noemden, schreef ik in die oudheid eenvoudige programma's in Python voor de serie60. Ik kwam er laatst eentje tegen toen ik door de archieven aan het graven was. GifTool is een programma voor het maken van GIF-animaties van een reeks afbeeldingen. Daarin implementeerde ik kwantisering met behulp van de mediaansectiemethode, het LZW-compressie-algoritme, de volledige bestandsstructuur werd onafhankelijk gemaakt en transparantie werd gebruikt voor pixels die niet veranderden op de volgende dia om de uiteindelijke bestandsgrootte te verkleinen. Ik wilde mijn geheugen opfrissen en zien hoe het werkte. Ik opende de code en... Dat gevoel als je je waardeloze code van tien jaar geleden niet meer kunt achterhalen. Ik kende toen nog niets van PEP8, dus de leesbaarheid van de code was iets minder dan onbestaande (destijds hield ik van minimalisme, zoals veel beginnende programmeurs). Ik liet een paar tranen vallen, spuugde, herwerkte het in PyCharm, ontdekte hoe ik de mediaansectiemethode moest implementeren en creëerde snel een 'vies' script. Werken! Het palet is gemaakt, het uitvoerbeeld is acceptabel. En toen vroeg ik me af of ik betere resultaten kon bereiken, zodat de foto visueel zo dicht mogelijk bij het origineel zou komen.

Een paar foto's zijn bijna on-topic, voor de duidelijkheid

Nu hebben we een optimaal palet, niet ideaal natuurlijk (ik weet dat het nog verder verbeterd kan worden), maar goed genoeg. De volgende stap is het indexeren van de kleuren van de afbeelding. De eenvoudigste optie is in welk segment de kleur zich bevindt, en dat geldt ook voor de index. Snel en gemakkelijk. Maar er is één maar, en niet eens één, dus op deze stap komen we later terug.

Er is een andere manier om de kwaliteit van het resulterende beeld te verbeteren: foutspreiding. Ook hier is alles vrij eenvoudig: we trekken de overeenkomstige kleur van het palet af van de geïndexeerde kleur, krijgen een fout, verspreiden deze over aangrenzende pixels volgens een bepaalde formule (sjabloon), de beroemdste Floyd-Steinberg-formule, die is wat ik gebruikte. Wanneer fouten diffuus zijn, worden scherpe overgangen tussen kleuren wazig en lijkt het beeld visueel meer schakeringen (kleuren) te bevatten. Als u geïnteresseerd bent, kunt u gedetailleerd en interessant lezen over foutspreiding. Ik besloot ook om dit algoritme te voltooien, door de fout met dezelfde coëfficiënten te vermenigvuldigen, zoals later bleek, dit was een heel goed idee - aangezien er minder secties in het blauwe bereik waren, werd er een significante fout in verkregen, en zonder de correctie te corrigeren fout door coëfficiënten, verstrooiing introduceerde veel “ruis” "

Nu kunt u weer terugkeren naar het indexeren. Door fouten te verspreiden, veranderen we de kleuren van de pixels en krijgen we de kleuren die niet in onze RGB-kubus zitten (laat me je eraan herinneren dat deze uitsluitend uit beeldkleuren bestaat). Nu kunt u niet alleen kijken naar welk segment een kleur zich bevindt om een ​​index toe te wijzen. De oplossing werd onmiddellijk gevonden: zoeken naar de dichtstbijzijnde kleur in het palet. Ik heb dezelfde coëfficiënten in deze formule vervangen. Bij het vergelijken van de resultaten van het selecteren van een paletkleur op basis van de index van het segment dat de originele kleur bevat, en de resultaten van het zoeken naar de dichtstbijzijnde kleur, zag ik duidelijk dat de dichtstbijzijnde kleur vaak in het aangrenzende segment terechtkomt. Als de bronkleur dichter bij het midden van het segment ligt, komt de segmentindex overeen met de kleurindex in het palet, maar hoe dichter de bronkleur bij de randen van het segment ligt, hoe waarschijnlijker het is dat de dichtstbijzijnde kleur zich in het aangrenzende segment bevinden. Over het algemeen is de enige juiste manier om te indexeren het zoeken naar de dichtstbijzijnde kleur in het palet. Maar zoeken heeft een nadeel: het is langzaam, heel langzaam. Het schrijven van een getallenbreker in Python is een slecht idee.

Nou, ik wilde het in een notendop uitleggen, maar het bleek een heleboel onbegrijpelijke teksten te zijn. Ik hoop dat ik betere code schrijf dan ik uitleg, dus hier is een link naar github. De code werd verschillende keren herschreven, eerst werd het algoritme verbeterd, totdat het resultaat mij tevreden stelde, daarna bleek dat het te veel RAM in beslag nam bij het verwerken van foto's (eerst testte ik het op kleine foto's), ik moest de RGB overbrengen kubus, mediaansectie en pixelkaart naar de database (sqlite). Het script werkt erg langzaam, maar het resultaat is beter dan kwantisering met PIL/Pillow en GIMP (hierin wordt deze bewerking indexering genoemd).

Visuele demonstratie:

Origineel

Kwantiseringsresultaat in GIMP, optimaal palet van 256 kleuren + Floyd-Stenberg kleurvervaging (normaal)

Kwantiseringsresultaat PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, kleuren=256)

Resultaat van kwantisering door mijn code

Waar u op moet letten: de foutspreiding van GIMP is erg luidruchtig, PIL/Pillow creëert een niet erg optimaal palet en verdrijft praktisch geen fouten (scherpe overgangen tussen kleuren).
Als je het verschil niet ziet, kijk dan naar andere voorbeelden op github.

Verbergmethoden in het ruimtelijke domein omvatten ook de methode beeldkwantisering, gebaseerd op interpixelafhankelijkheid, die door een bepaalde functie kan worden beschreven. In het eenvoudigste geval kan men het verschil tussen aangrenzende pixels berekenen; en (of en ) en stel het in als een functieparameter: , waarbij een discrete benadering is van het signaalverschil.

Sinds is een geheel getal, en echt verschil een reëel getal is, treden kwantiseringsfouten op. Voor sterk gecorreleerde signalen is deze fout bijna nul: .

Bij deze methode informatie wordt verborgen door het verschilsignaal aan te passen. Een stegan-sleutel is een tabel die aan elke mogelijke waarde een specifiek bit toekent, bijvoorbeeld:

Om het i-de bit van het bericht te verbergen, wordt het verschil berekend. Als in dit geval bi niet overeenkomt met het geheime bit dat verborgen moet worden, dan wordt de waarde vervangen door de dichtstbijzijnde waarde waarvoor aan een dergelijke voorwaarde is voldaan. In dit geval worden de intensiteitswaarden van de pixels waartussen het verschil werd berekend dienovereenkomstig aangepast.

Laten we een voorbeeld bekijken van een programma dat de beeldkwantiseringsmethode implementeert

De initiële gegevens zijn standaard.

Stap 2

We berekenen de gewatteerde sleutel met behulp van modules (M.28) en (M.29). In dit geval retourneert de module (M.28) alle mogelijke signaalverschillen (van -255 tot +255), en retourneert de module (M 29) de bitwaarden die overeenkomen met deze verschillen.

Waarden b ik in dit geval worden ze berekend op basis van de array van de rode kleurcomponent. Bovendien voor elke kolom van de array R De som wordt berekend modulo 2 van de samenstellende elementen, met een Booleaanse optelling van één bij het resultaat van de sommatie bij elk derde element. Aan het einde van de module de resulterende vector B breidt uit met de lengte van de vector. Dus de elementen van de array B zijn pseudo-willekeurig van aard. Fragmenten van de gevormde gewatteerde sleutel worden getoond in Fig. 5.15.

Rijst. 6.15. Gewatteerde sleutelfragmenten

Laten we de containerarray implementeren MET(array van blauwe kleurcomponent) in een vector met behulp van de module (M.16). Laten we de startindex van het element van de resulterende vector instellen, vanaf waar de bits en berichten zullen worden ingebed (bijvoorbeeld ).

Om de stapgrootte (pseudo-willekeurig interval) te berekenen, gebruiken we module (M.15). Laat het tegelijkertijd NAAR := 8.

Stap 4

Het inbeddingsalgoritme wordt geïmplementeerd door de module (M.30). De vorming van een vector van binaire gegevens uit een reeks karakters is vergelijkbaar met die gepresenteerd in (M.21) (in dit geval is het echter noodzakelijk om deze te vervangen door ).

Voor elke bit van het bericht wordt een index berekend z container vectorelement CV. Het verschil tussen aangrenzende pixels wordt berekend Cvz En C vz-1 De binnenste lus zoekt naar de overeenkomstige verschilwaarde in de vector. Indien gedetecteerd, krijgt de variabele de indexwaarde toegewezen i, wat overeenkomt met dit verschil in .

Als de waarde niet overeenkomt met het huidige bit van het verborgen bericht, wordt er gezocht naar de dichtstbijzijnde index waarop bi is gelijk aan de berichtbit. Er wordt naar beneden gezocht (L) en omhoog (H) van index.

Een voorlopige toewijzing van variabelen aan de waarde ±1000 zorgt ervoor dat het onmogelijk is om eerdere waarden te dupliceren als de beweging naar beneden of naar boven niet heeft geleid tot het vervullen van de gestelde voorwaarde (dit laatste is mogelijk wanneer de index te dicht bij de onder- of bovengrens van de vector B). Nadat de waarden zijn gevonden, wordt degene geselecteerd die het dichtst bij de initiële waarde ligt.

Pixelintensiteit van de container Sv z gelijk aan de intensiteit van de aangrenzende pixel, verhoogd met de hoeveelheid Sv z-1. Als deze stijging leidt ertoe dat de kleurintensiteitswaarde het bereik overschrijdt, en omgekeerd wordt aan de intensiteit van de aangrenzende pixel Sv z -1 de pixelintensiteitswaarde toegewezen Sv z, verminderd met het bedrag). Na het inbedden laatste stukje bericht, wordt de buitenste lus onderbroken.

We voeren de omgekeerde vouwing van de vector uit Sv in een matrix met de afmetingen van de primaire array MET(M.7). We krijgen een array S.