NL9201415A - Werkwijze en inrichting voor het coderen en decoderen van digitale beeldgegevens. - Google Patents

Description

Werkwijze en inrichting voor het coderen en decoderen van digitalebeeldgegevens

De uitvinding betreft een werkwijze voor het coderen van digitale beeldgegevensomvattende opeenvolgende blokken van binnen de blokken op opeenvolgende positiesgelegen gegevensgroepen met als inhoud binaire waarden van steeds een gelijk aantalpixels van een afbeelding, in welke werkwijze een reeks van opeenvolgendegegevensgroepen binnen een te coderen blok, die elk dezelfde inhoud hebben als degegevensgroep op dezelfde positie in een referentieblok, wordt vervangen door eencode. De uitvinding betreft tevens een inrichting waarin deze werkwijze wordt toegepast

Het coderen van beeldgegevens vindt zijn toepassing in systemen voor het digitaliseren van beelden, zoals documenten, door middel van lijnsgewijs aftasten meteen lichtgevoelige opnemer, bewerken, in een geheugen opslaan en/of verzenden vande aftastsignalen, en het afdrukken ervan op bijvoorbeeld papier. Om een beeld metvoldoende kwaliteit te digitaliseren is het noodzakelijk om zeer veel gegevens daarvan op te nemen en verder te verwerken, en het is daarom wenselijk om deze gegevens te kunnen comprimeren, vooral ten behoeve van opslag en verzending. Een eerste vormvan compressie bestaat uit het overgaan van de veelwaardige aftastgegevens(grijswaarden) naar tweewaardige signalen (wit of zwart), zodat elk signaal met slechtseen bit kan worden gerepresenteerd, maar ook dan blijven er nog veel beeldgegevensover. Wanneer men uitgaat van de in de vakwereld veel gebruikte resolutie van 300 dotsper inch, bevat elke vierkante cm van het beeld ongeveer 14000 beeldelementen, pixelsgenoemd, zodat voor een A4 document al bijna 1 miljoen bits nodig zijn.

Een werkwijze als beschreven in de aanhef is bekend uit de Nederlandseoctrooiaanvrage nr. 9100225 van aanvraagster. In de bekende werkwijze wordtrunlengtecodering toegepast op reeksen opeenvolgende gegevensgroepen waarin elkegegevensgroep dezelfde inhoud heeft als de gegevensgroep op dezelfde positie in hetreferentieblok. De code bevat bijgevolg het aantal gegegevensgroepen in de reeks.

Het komt echter niet zelden voor, dat zulke reeksen zeer veel gegevensgroepenbevatten, zoals bijvoorbeeld in geheel witte gebieden aan de boven- en onderzijde vaneen document. Maar ook in gedeelten van een origineelbeeld, die wel beeldinformatiebevatten, kunnen opeenvolgende beeldlijnen plaatselijk gelijke informatie bevatten,bijvoorbeeld wanneer zich op het origineelbeeld evenwijdige lijnen loodrecht op deaftastrichting bevinden.

In dergelijke gevallen bevat de runlengtecode een lang getal en wordt bijgevolg decode langer. Afgezien van het evidente bezwaar van meer ruimtebeslag door de code is dit bezwaarlijk, omdat hierdoor de lengte van het codewoord variabel wordt, wat hetdecoderen lastiger maakt. Weliswaar zijn er methoden om dit bezwaar te ondervangen,maar die maken de codewoorden weer langer en verminderen daardoor de haalbarecompressiefaktor.

De uitvinding heeft tot doel om aan de bovengenoemde bezwaren tegemoet tekomen en daardoor de bereikbare compressiefaktor van de werkwijze volgens de aanhefte vergroten.

Dit doel wordt bereikt, doordat in de genoemde code niet het aantalgegevensgroepen in de gecodeerde reeks, maar de positie van het einde van de reeksgespecificeerd wordt ten opzichte van een overgang in pixelwaarde in hetreferentieblok. Een dergelijke code is daardoor niet afhankelijk van de lengte van dereeks, en wanneer er voor de positieaanduiding slechts een klein repertoire vanmogelijkheden beschikbaar wordt gesteld, kan de code zeer kort worden gehouden, ookals zeer lange reeksen worden gecodeerd.

Volgens een uitvoeringsvorm van de werkwijze volgens de uitvinding wordt in degenoemde code tevens de gegevensgroep geïdentificeerd, waarin de overgang inpixelwaarde, ten opzichte waarvan de positie van het einde van de reeks isgespecificeerd, is gelegen.

Aangezien de codering volgens de uitvinding altijd wordt uitgevoerd voor gehelegegevensgroepen tegelijk, is het ook voldoende om in de code aan te geven, in welkegegevensgroep van het referentieblok zich de bewuste overgang in pixelwaardebevindt In een verdere uitvoeringsvorm van de werkwijze volgens de uitvinding wordtin de genoemde code het volgnummer, geteld vanaf de positie van het begin van dereeks, verwerkt van de gegevensgroep metten minste een overgang in pixelwaarde,waarin de overgang in pixelwaarde, ten opzichte waarvan de positie van het einde vande reeks is gespecificeerd, is gelegen.

Bevindt zich in een gegevensgroep meer dan een overgang, zowel in het te coderenals in het referentieblok, dan telt dit voor de code toch maar als een overgang. Hierdoorwordt de afstand die de code kan overbruggen groter. Het aantal te kiezen volgnummerswordt bij voorkeur klein gehouden, omdat anders een langere code nodig is.

In een bijzondere uitvoeringsvorm van de werkwijze volgens de uitvinding is debeschreven coderingsmethode met verwijzing naar een referentieblok gekombineerdmet normale runlengtecodering. In deze uitvoeringsvorm wordt; beginnende bij eenstartpositie in een te coderen blok, onderzocht, of codering met verwijzing naar eenreferentieblok en runlengtecodering mogelijk zijn en wat hun resultaat is. Vervolgenswordt die coderingswijze gekozen, die de meest efficiënte code oplevert, dat wil zeggen,het kortste codewoord. Het zal duidelijk zijn, dat, wanneer beide coderingswijzendezelfde reeks opleveren, de verwijzingscodering snel de voorkeur zal krijgen, zeker voor lange reeksen. In praktijk kan de code voor de verwijzingscodering zo kort wordengehouden, dat deze coderingsmethode altijd de voorkeur heeft.

Als referentieblok wordt bij voorkeur het blok gekozen, dat direkt voorafgaat aan hette coderen blok. Bij deze keuze is immers de grootste kans op coïncidentie vanpixelwaarden te verwachten.

Niet in alle gevallen is codering in reeksvorm mogelijk. In dit geval kan wordenteruggevallen op de bekende coderingsmethode, waarin inhoud van de eerstvolgendete coderen gegevensgroep geheel in de code wordt opgenomen, voorzien van eencode-prefix die aangeeft dat de code de gegevensgroep zelf bevat. Deze oplossing isook in de reeds eerder vermelde octrooiaanvrage toegepast en is daarin"kopie-codering" genoemd. Het behoeft geen betoog, dat deze coderingswijze zeerongunstig is, omdat er door de toevoeging van de prefix data-expansie in plaats van-compressie optreedt. Niettemin is gebruik van deze coderingswijze onontkoombaar.

Het is gebleken, dat na een reekscodering vrijwel altijd een gegevensgroep volgt dieniet het begin is van een nieuwe reeks, en die dus kopie-codering vereist. Daarom wordtin een uitvoeringsvorm van de coderingswijze volgens de uitvinding een reekscoderingin de meeste, door een selektieregel bepaalde, gevallen automatisch gevolgd door eenkopie-codering van bijzondere vorm, namelijk zonder een code-prefix. Aangezien bij dedecodering deze selektieregel bekend is, is steeds duidelijk wanneer een kopie-codevolgt, zodat de prefix overbodig is. Hierdoor wordt in deze gevallen data-expansievoorkomen.

De uitvinding heeft tevens betrekking op een werkwijze en een inrichting voor hetdecoderen van een codestroom, die is ontstaan door het coderen van digitalebeeldgegevens volgens de werkwijze van de uitvinding. De opbouw van de werkwijzeen inrichting voor het decoderen vormen het spiegelbeeld van de werkwijze eninrichting voor het coderen.

De uitvinding zal nu uitvoerig worden beschreven aan de hand van de bijgevoegdetekeningen. Hierin zijn

Fig. 1A en 1B stroomschema's van de procedure voor het onderzoeken vanopeenvolgende pixelwaarden;

Fig.2A en 2B stroomschema's van de procedure voor het vormen van een code; enFig.3A, 3B, 3C en 3D stroomschema's van de procedure voor het vormen van een codevoor een uit het referentieblok over te nemen reeks pixelwaarden.

De codeermethode volgens de uitvinding zal nu eerst globaal worden beschreven.

In het beschreven uitvoeringsvoorbeeld zijn de te coderen gegevens beschikbaar inde vorm van groepen van 4 bits, zogenaamde nibbles. Andere aantallen bits per groepzijn echter, met voor de hand liggende aanpassing van de methode, op dezelfde wijzecodeerbaar. Voorbeelden van andere aantallen zijn 1 en 8 bits per groep. Een vast aantal groepen vormt steeds een blok. Een blok is bijvoorbeeld een beeldlijn, terwijl degenoemde bits overeenkomen met de waarden van de pixels op die beeldlijn. Een aantalblokken (beeldlijnen) komen tezamen overeen met een afbeelding van een document,waarvan de beeldgegevens moeten worden gecodeerd ten behoeve van opslag in eengeheugen of van transmissie naar ander apparaat.

De te coderen gegevens worden ook steeds in eenheden ter grootte van degenoemde groepen (nibbles) gecodeerd. In het algemeen worden, uitgaande van eenstartpositie in een blok een of meer groepen bits vervangen door een code, waarna heteerstvolgende niet gecodeerde bit (dit is dus altijd een eerste bit van een groep) alsvolgende startpositie wordt aangewezen.

De methode omvat vier verschillende basis-codeerwijzen waaruit, afhankelijk van deinhoud van de te coderen bits, er een wordt geselekteerd, namelijk: - runlengtecodering (aanduiding: m1) - overname uit de vorige lijn (aanduiding: m2) - overname uit de huidige lijn (aanduiding: m3) - codeloze overname uit de huidige lijn (aanduiding: m4)

Runlengtecodering (m1)

Bij de runlengtecodering wordt een reeks nibbles in het te coderen blok, waarin debits alle dezelfde waarde hebben geteld en door een code vervangen. De vorm van decode is: 01cxxxxx

Hierin vormt "01" de code-prefix die aangeeft, dat het een runlengtecode betreft, V'geeft de waarde (0 of 1) van de bits weer, en xxxxx geeft in binaire vorm het aantalnibbles in de gecodeerde reeks weer. Voor grotere aantallen nibbles dan met een binairgetal van vijf bits kan worden weergegeven wordt een extra codewoord toegevoegd,geheel bestaande uit de aantalscode. De waarde "00000" van xxxxx (die om voor dehand liggende redenen niet gebruikt wordt) wordt nu gebruikt als escape-code om ditaan de decoder te melden.

Bij het decoderen wordt elke code weer geexpandeerd tot het gespecificeerdeaantal nibbles van bits met de waarde c.

Overname uit de vorige lijn (m2)

In deze coderingswijze wordt een reeks nibbles binnen het te coderen blok, waarinde bits elk dezelfde waarde hebben als het bit op dezelfde plaats in het referentieblok(normaal het voorgaande blok), vervangen door een code die het einde van de reeksrelateert aan een waarde-omslag in het referentieblok, dat wil zeggen aan een bit in hetreferentieblok, dat een waarde heeft die tegengesteld is aan de waarde van hetonmiddellijk daaraan voorafgaande bit in het referentieblok. De code specificeert tevens,welke waarde-omslag in het referentieblok bedoeld wordt, geteld vanaf de startpositie.

Hierbij worden de volgende codes gebruikt. Achter elke code wordt de in dezebeschrijving gehanteerde aanduiding vermeld en de betekenis van de code voor dedecoder.

000 (aanduiding: m21): neem de inhoud van het referentieblok over vanaf de positie die overeenkomt met de startpositie tot aanhet begin van de eerste nibble in het referentieblok, waarineen waarde-omslag voorkomt 00100 (aanduiding: m22): neem de inhoud van het referentieblok over vanaf de positie die overeenkomt met de startpositie tot en met het eindevan de eerste nibble in het referentieblok, waarin eenwaarde-omslag voorkomt.

00101 (aanduiding: m23): neem de inhoud van het referentieblok over vanaf de positie die overeenkomt met de startpositie tot aan het begin vande tweede nibble in het referentieblok, waarin eenwaarde-omslag voorkomt.

00110 (aanduiding: m24): neem de inhoud van het referentieblok over vanaf de positie die overeenkomt met de startpositie tot en met het eindevan de tweede nibble in het referentieblok, waarin eenwaarde-omslag voorkomt.

00111 (aanduiding: m25): neem de inhoud van het referentieblok over vanaf de positie die overeenkomt met de startpositie tot aan het begin vande tweede nibble in het referentieblok, waarin eenwaarde-omslag voorkomt.

Voor de bovenstaande codes maakt het niet uit of er in een nibble meer dan eenwaarde-omslag voorkomt of precies een: beide gevallen gelden als "eenwaarde-omslag".

Overname uit de huidige lijn (m3)

In deze codeerwijze wordt de eerstvolgende te coderen nibble geheel opgenomenin de code. Deze heeft de vorm: 1 bbbb waarin bbbb de waarden van de bits van de bewuste nibble zijn. Deze codeerwijze zalslechts gebruikt worden, indien geen der andere codeerwijzen bruikbaar is.

Bij het decoderen wordt de inhoud van het gedeelte bbbb van de code aan dedatastroom toegevoegd.

Codeloze overname uit de huidige lijn (m4)

Deze codeerwijze is gelijk aan de voorgaande, maar heeft geen codeprefix. Hijwordt automatisch volgens een regel, die zowel bij de coder als de decoder bekend is, alof niet uitgevoerd na een van de andere codering. In veel gevallen namelijk is een codering van de nibbles direkt voorafgaande aan de te coderen nibble volgens een derandere codeerwijzen beëindigd, doordat in de volgende, dus de nu te coderen nibbleeen onregelmatigheid in het bitpatroon voorkomt. Het is dan voordelig, om die volgendenibble dan ook maar klakkeloos over te nemen in de code. Ingeval de voorafgaandecode een m22- of een m24-code is, volgt geen m4-code, omdat dan de onregelmatigenibble al in de voorafgaande code is opgenomen. In alle andere gevallen wordt steedseen m4-code toegevoegd. Het codewoord heeft de vorm:bbbb hetgeen gelijk is aan de inhoud van de betreffende nibble.

Aangezien de decoder over dezelfde selektieregel beschikt, is daar bekend wanneerdeze code gebruikt wordt, zodat de situatie eenduidig blijft ondanks het ontbreken vande codeprefix. De decoder voegt de waarde bbbb toe aan de gedecodeerde datastroom.

Door de keuze van de codewoorden is het decoderen zeer snel en eenvoudig uit tevoeren. Wanneer de decoder als eerste codebit een " 1" ziet, wordt meteen dem3-decodeerwijze geselekteerd, ingeval het eerste codebit een "0" is, wordt verdergekeken naar het tweede codebit. Is dit een " 1", dan worden de daaropvolgende zescodebits als een runlengtecode geïnterpreteerd (ml), en als deze zes codebits deescape-code cOOOOO bevatten, wordt de volgende byte mede gedecodeerd als extrarunlengtecode.

Is het tweede codebit een "0”, dan wordt gekeken naar het daaropvolgende bit. Isdit een "0", dan is de code een m21 -code en vormt het volgende code-bit het eerste vanhet volgende codewoord. Is het derde codebit een " 1", dan bepalen de tweedaaropvolgende bits de aard van de code, m22, m23, m24 of m25. De decodeerwijzevan deze codes is boven reeds beschreven. Na een m21-, m23- en m25-code volgt altijdeen m4-code, dat wil zeggen, dat de vier eerstvolgende codebits als waarden van de bitsin de nibble worden overgenomen.

De gang van zaken tijdens het coderen van een datastroom, bijvoorbeeld binairepixelwaarden van een afbeelding, zal nu worden toegelicht aan de hand van de figuren.

De pixelwaarden (bits) worden toegevoerd in opeenvolgende beeldlijnen, waarvande lengte (II) in aantallen bits bekend is. Voorts worden in de figuren de volgendevariabelen gebruikt: pointer = lopende variabele, die steeds de positie in de lijn van de te coderenpixelwaarde aanwijst sp = de startpositie, het eerste te coderen bit volgend op het laatst gecodeerdebit pixc(i) = de waarde van pixel i van de te coderen lijn (0 of 1)pixr(i) = de waarde van pixel i van de referentielijn (0 of 1) WC = de beginpositie van de eerste nibble in de te coderen lijn, waarin een waarde-omslag is opgetreden WR = de beginpositie van de voor het coderen relevante nibble in de referentielijn,waarin een waarde-omslag is opgetreden nov = een toestandsvariabele, die aangeeft dat in de lopende cyclus de overnamevan nibbles uit de referentielijn niet meer mogelijk is; wordt gereset (0) bijhet definiëren van een nieuwe sp, en geset op het moment datgekonstateerd wordt dat pixc(pointer) en pixr(pointer) ongelijke waardenhebben nr = het aantal nibbles waarin een waarde-omslag voorkomt, in de referentielijn,gerekend vanaf de sp

Fig. 1A en 1B beschrijven het stuk voor stuk onderzoeken van de pixelwaarden in dete coderen lijn. Wanneer in deze lijn een waarde-omslag wordt gekonstateerd, wordtovergegaan naar een aparte routine voor het maken van een code, welke wordtbeschreven in Fig.2A en 2B. Blijkt in deze routine, dat op de positie van dewaarde-omslag ook in de referentielijn een waarde-omslag optreedt, dan wordtonderzocht, of met een m2-code een langere reeks is coderen. Dit wordt beschreven inFig.3A, 3B, 3C en 3D.

De procedure in Fig.lA vangt aan bij het begin van een nieuwe lijn of een nieuwecodereeks binnen de lopende lijn (A). In een initialisatieroutine wordt de waarde van depointer, WR en WC gelijk gemaakt aan de startpositie en wordt nov gereset. Vervolgenswordt onderzocht of de eerste pixelwaarde van de te coderen lijn gelijk is aan die van dereferentielijn. Is dit niet het geval, dan zijn alleen nog de codeerwijzen m1 en m3mogelijk, en de procedure gaat in dat geval verder met het tellen van gelijkepixelwaarden in de te coderen lijn, waarna wordt overgegaan naar een procedure voorhet vormen van de code in afhankelijkheid van de lengte van de bij het tellen gevondenreeks (Fig.2B). Tijdens heitellen wordt bijgehouden, of het einde van de lijn bereiktwordt, en als dit het geval is, dan wordt geforceerd overgegaan naar de procedure voorhet vormen van een code in Fig.2B.

In het geval dat de eerste pixelwaarden van de te coderen lijn en de referentielijn welgelijk zijn, wordt een lusroutine ingegaan, welke beschreven is in Fig. 1B. Hierin wordtsteeds voor een volgende pixelwaarde onderzocht, of de pixelwaarden op depointer-positie in de te coderen lijn en de referentielijn aan elkaar gelijk zijn en of ze elkgelijk zijn aan de pixelwaarde op de hun voorafgaande positie. Zijn de pixelwaarden opde pointer-positie in de te coderen lijn en de referentielijn niet aan elkaar gelijk, dan kaneen eventuele m2-codereeks in elk geval niet verder lopen dan tot de nibble, waarin depointer zich op dat moment bevindt. Dit wordt vastgelegd door de variabele nov dewaarde "1" te geven. Is op de pointer-positie in de referentielijn een waarde-omslagopgetreden, dan wordt, indien dit de eerste keer is na de startpositie, in WR de beginpositie van de lopende nibble opgeslagen.

Is op de pointer-positie in de te coderen lijn een waarde-omslag opgetreden, danwordt de lus van Fig. 1B verlaten en overgegaan naar de procedure voor het vormen vaneen code.

Verder wordt de lus van Fig. 1B verlaten, als het einde van de te coderen lijn bereiktwordt. Ook hier wordt dan het vormen van een code geforceerd door enkele variabeleneen andere waarde te geven.

De procedure voor het vormen van een code is weergegeven in Fig.2A en 2B. Dezeprocedure bestaat uit twee takken, een voor het vormen van een m2-code (Fig.2A) en deandere voor het vormen van een m1-, respektievelijk een m3-code (Fig.2B). Alvorenseen keus gemaakt wordt tussen een van deze twee takken, wordt onderzocht, of depointer zich nog in de eerste nibble na de startpositie bevindt. Is dit het geval, dan isalleen een m3-code mogelijk, en daartoe wordt dan onmiddellijk overgegaan naar dem1/m3tak.

Is de pointer al voorbij de eerste nibble, dan worden de beginposities van de eerstenibbles waarin een waarde-omslag is opgetreden, in de te coderen lijn (WC) en dereferentielijn (WR), met elkaar vergeleken. Omdat naar deze procedure wordtovergegaan bij de eerste waarde-omslag in de te coderen lijn, is WC dus altijd debeginpositie van de lopende nibble. Is WR kleiner dan WC, dan is dus in de referentielijnal eerder dan in de te coderen lijn een waarde-omslag opgetreden, en wordtrunlengtecodering gekozen, omdat hiermee een langere reeks kan worden gecodeerd.Omdat een m2-code korter is dan een runlengtecode, zou ook nog voor m2-coderingkunnen worden gekozen, indien WR een klein aantal posities, bijvoorbeeld 4 (een nibble)kleiner is dan WC, maar dat is in dit voorbeeld niet uitgewerkt.

In het geval van runlengtecodering (Fig,2B) wordt eerst onderzocht of de te coderenreeks nibbles uit ten minste twee elementen (8 pixelwaarden) bestaat. Is dit het geval,dan wordt een m1 -code gevormd voor de nibbles vanaf de startpositie tot aan delopende nibble, met de waarde van de pixels in de aan de lopende nibble voorafgaandenibble als waarde voor de bit "c" in de code, gevolgd door een m4-code. Vervolgenswordt een nieuwe startpositie voor de volgende codecyclus bepaald en er wordt getest,of deze nieuwe startpositie voorbij het einde van de lijn reikt (dit is mogelijk door dem4-code), in welk geval alles gereed wordt gemaakt voor codering van de volgende lijn.De decoder is op de hoogte van de lengte van de lijnen, zodat de code niet hoeft teworden aangepast. Eventueel te veel gegenereerde pixelwaarden worden eenvoudiggenegeerd.

Indien het aantal te coderen nibbles kleiner of gelijk is aan twee, wordt een m3-codevoor de eerste te coderen nibble gevormd, gevolgd door een m4-code, zodat in elkgeval de gehele reeks gecodeerd is. Er volgt nu weer controle op het bereiken van het einde van de lijn.

Zijn WC en WR gelijk, dan wordt in de procedure voor het vormen van een code detak voor de m2-codes ingegaan. In dit geval is er een waarde-omslag opgetreden in de tecoderen lijn en in de referentielijn, en wel in dezelfde nibble. Er wordt nu onderzocht, ofer zich eerder in die nibble reeds een waarde-omslag heeft voorgedaan in dereferentielijn. Is dit het geval (nov = 1), dan is de te coderen lijn van de startpositie tot aande lopende nibble gelijk aan de referentielijn (codering geschiedt altijd in gehele nibbles)en kan dit gedeelte van de te coderen lijn worden gecodeerd met een m21-code,gevolgd door een m4-code. Vervolgens wordt een nieuwe startpositie voor de volgendecodecyclus bepaald en er wordt weer getest, of deze nieuwe startpositie voorbij heteinde van de lijn reikt.

Zijn WC en WR gelijk en is nov nog steeds gelijk aan nul, dan is de gevondenwaarde-omslag in de te coderen lijn blijkbaar gelegen op dezelfde positie als de eerstewaarde-omslag in de referentielijn, en zijn beide lijnen vanaf de startpositie tot en met delopende pixelwaarde gelijk. Er wordt nu onderzocht, of de codering met verwijzing naarde referentielijn kan worden verlengd tot een m22-, m23-, m24- of m25-codering. Ditwordt beschreven met verwijzing naar Fig.3A, 3B, 3C en 3D.

Deze procedure is erop gericht om, stappend langs de pixelwaarden van de tecoderen lijn, een reeks opeenvolgende posities te vinden, waarop de pixelwaarden inbeide lijnen twee-aan-twee gelijk zijn. Op het moment, dat dit niet meer het geval is, kande codering niet verder worden voortgezet en wordt een code gevormd. Deze coderelateert het einde van de reeks nibbles, die bij het decoderen uit de referentielijn moetworden gekopieerd uit de referentielijn, aan een bepaalde, met name genoemdewaarde-omslag in de referentielijn en zal er dus van afhangen, of de eerstewaarde-omslag die niet in beide lijnen tegelijk voorkomt in de te coderen lijn of in dereferentielijn is gelegen. Ligt deze waarde-omslag in de referentielijn, dan wordt eencode gekozen, die een reeks beschrijft van de startpositie tot aan de nibble waarin dewaarde-omslag is gelegen (m23 of m25). Een erop volgende m4-code codeertvervolgens de nibble met de waarde-omslag zelf. Ligt de betreffende waarde-omslag inde te coderen lijn, dan kan het einde van de door de code beschreven reeks zich nietverder uitstrekken dan tot en met de nibble waarin de laatste waarde-omslag in dereferentielijn is gelegen (m22 of m24). In dit geval is toevoeging van een m4-code nietzinvol, omdat vaak de erop volgende nibble geen waarde-omslag zal bevatten.

De procedure wordt nu in detail beschreven. Bij de aanvang wordt de variabele nr,waarin het aantal nibbles in de referentielijn metten minste een waarde-omslag wordtbijgehouden, op de waarde "Γ gebracht, omdat immers de eerste waarde-omslag al isgevonden. Vervolgens wordt een lusbewerking ingegaan, waarin steeds de pointer eenpixelwaarde verder wordt gezet en dan wordt getest of zich op de nieuwe pointerpositie een waarde-omslag heeft voorgedaan in de te coderen lijn en/of de referentielijn. Na eentest op het bereiken van het einde van de lijn keert de lus terug naar zijn begin.

Wordt een waarde-omslag gevonden in de te coderen lijn, dan volgt een subroutine(Fig.3B) waarin eerst wordt nagegaan, of op dezelfde positie in de referentielijneveneens een waarde-omslag is opgetreden. Is dit het geval, dan wordt onderzocht, ofin de lopende nibble al eerder een waarde-omslag in de referentielijn is gevonden. Dezetest wordt uitgevoerd door de beginpositie WR' van de nibble te bepalen en deze tevergelijken met de beginpositie WR van de nibble waarin de vorige waarde-omslag in dereferentielijn is gevonden. Zijn WR' en WR gelijk, dan ligt de laatstgevondenwaarde-omslag inderdaad in een nibble die al een andere waarde-omslag bevat en kandaarom verder genegeerd worden, omdat het aantal waarde-omslagen per nibble nietgebruikt wordt voor de codering, zolang ze maar in beide lijnen tegelijk optreden. IndienWR' en WR ongelijk zijn, is blijkbaar een nieuwe nibble gevonden met eenwaarde-omslag en dit wordt geadministreerd door de waarde van nr met 1 te verhogenen WR gelijkte maken aan die van WR'. De code kan tot maximaal 3 nibblesvooruitwijzen en daarom wordt nu getest, of het aantal gevonden nibbles vanaf destartpositie (nr) de waarde 3 heeft bereikt, in welk geval deze codecyclus wordtbeëindigd met het vormen van een m25-code, gevolgd door een m4-code, hetberekenen van een nieuwe startwaarde en de gebruikelijke test op het bereiken van heteinde van de lijn.

Indien de variabele nr de waarde 3 nog niet bereikt heeft, en ook indien WR' en WRgelijk zijn, wordt teruggesprongen naar de lus (Fig.3A) en de volgende pixelwaardeonderzocht.

Indien aan het begin van de subroutine van Fig.3B geen waarde-omslag in dereferentielijn is gekonstateerd, zodat er op de pointerpositie dus wel een waarde-omslagin de te coderen lijn en niet in de referentielijn is opgetreden, dan is het einde van decodeerbare reeks bereikt en wordt een code gevormd (Fig.3C) in afhankelijkheid van hetaantal (nr) inmiddels gevonden nibbles metten minste 1 waarde-omslag. Is dit er 1, danvolgt een m22-code, anders (nr = 2) een m24-code. Nu volgt geen m4-code. Vervolgenswordt een nieuwe startpositie bepaald en begonnen aan een nieuwe codeercyclus. Hieris geen test op het bereiken van het einde van de lijn nodig, omdat bij een m22- en eenm24-code het einde van de gecodeerde reeks teruggeplaatst is ten opzichte van depointerpositie.

Indien in de lus van Fig.3A geen waarde-omslag in de te coderen lijn wordtgekonstateerd, wordt binnen de lus onderzocht, of er wel een waarde-omslag in dereferentielijn heeft plaats gehad op de pointerpositie. Is dit evenmin het geval, dan zijnde beide lijnen gelijk en kan de volgende pixelwaarde onderzocht worden. Wordt er weleen waarde-omslag gekonstateerd, dan is het einde van de codeerbare reeks bereikten wordt een code (m23 of m25) gevormd in een subroutine, welke is weergegeven inFig.3D. In deze subroutine wordt eerst de beginpositie bepaald van de lopende nibbleten behoeve van de bepaling van de nieuwe startpositie. Afhankelijk van het reedsgevonden aantal nibbles metten minste 1 waarde-omslag (nr) wordt nu een m23-code(voor nr = 1) of een m25-code (voor n = 2) gevormd, in beide gevallen gevolgd dooreen m4-code. Vervolgens wordt een nieuwe startpositie bepaald, er wordt getest op hetbereiken van het einde van de lijn en dan wordt begonnen aan een nieuwe codecyclus.

Hiermede is de uitvoeringsvorm van de codering volgens de uitvinding geheelbeschreven. Er wordt echter op gewezen, dat ook andere uitvoeringsvormen van deuitvinding mogelijk zijn. Zo kan bijvoorbeeld ook steeds een gehele nibble tegelijkbehandeld worden. De werkwijze moet daarvoor enigszins aangepast worden, dochblijft daarbij binnen de reikwijdte van de conclusies.

Een inrichting voor het uitvoeren van de codering of de decodering volgens deuitvinding kan worden gerealiseerd door een algemene computer te programmerenvolgens de stroomdiagrammen in de figuren en behoeft daarom geen verdere uitleg.Ook kan een inrichting worden gebouwd die dezelfde bewerkingen uitvoert mettoegesneden hardwareschakelingen, of die bestaat uit een passend geprogrammeerdecomputer, uitgebreid met hardwareschakelingen voor specifieke funkties. Ook hier zijntal van varianten mogelijk binnen de reikwijdte van de conclusies.

Claims (17)

1. Werkwijze voor het coderen van digitale beeldgegevens omvattendeopeenvolgende blokken van binnen de blokken op opeenvolgende posities gelegengegevensgroepen metals inhoud binaire waarden van steeds een gelijk aantal pixelsvan een afbeelding, in welke werkwijze een reeks van opeenvolgende gegevensgroepen binnen een tecoderen blok, die elk dezelfde inhoud hebben als de gegevensgroep op dezelfde positiein een referentieblok, wordt vervangen door een code,met het kenmerk, dat in de genoemde code de positie van het einde van de reeks gespecificeerd wordt tenopzichte van een overgang in pixelwaarde in het referentieblok.

2. Werkwijze volgens conclusie 1, met het kenmerk, dat in de genoemde code tevens de gegevensgroep geïdentificeerd wordt, waarin deovergang in pixelwaarde, ten opzichte waarvan de positie van het einde van de reeks isgespecificeerd, is gelegen.

3. Werkwijze volgens conclusie 2, met het kenmerk, dat in de genoemde code het volgnummer, geteld vanaf de positie van het begin van dereeks, wordt verwerkt van de gegevensgroep metten minste een overgang inpixelwaarde, waarin de overgang in pixelwaarde, ten opzichte waarvan de positie vanhet einde van de reeks is gespecificeerd, is gelegen.

4. Werkwijze volgens een der voorgaande conclusies, met het kenmerk, dat in de genoemde code tevens wordt aangegeven, of de gegevensgroep in het te coderenblok, gelegen op de positie van de gegevensgroep in het referentieblok, waarin deovergang in pixelwaarde, ten opzichte waarvan de positie van het einde van de reeks isgespecificeerd, is gelegen, nog tot de reeks behoort.

5. Werkwijze voor het coderen van digitale beeldgegevens omvattendeopeenvolgende blokken van binnen de blokken op opeenvolgende posities gelegengegevensgroepen met als inhoud de binaire waarden van pixels van een afbeelding,waarin, beginnende bij een beginpositie in een te coderen blok, en steeds voor eenvolgende positie binnen het blok, wordt onderzocht, of de op die positie gelegengegevensgroep dezelfde inhoud heeft als de gegevensgroep op dezelfde positie in hetreferentieblok, en voor de langste op deze wijze gevonden reeks van gegevensgroepenwaarvan de inhoud gelijk is aan de corresponderende gegevensgroep in hetreferentieblok een code wordt gevormd volgens een der voorafgaande conclusies; beginnende bij dezelfde beginpositie in het te coderen blok, en steeds voor eenvolgende positie binnen het blok, wordt onderzocht, of de inhouden van de op die positie gelegen gegevensgroep gelijk is aan de inhoud van de eraan voorafgaandegegevensgroep, en dat een runlengtecode wordt bepaald voor de langste op deze wijzegevonden reeks; en diegene van de twee genoemde langste reeksen, die de meest efficiënte code oplevert,wordt geselekteerd en vervangen door de betreffende code.

6. Werkwijze volgens een der voorgaande conclusies, met het kenmerk, dat als referentieblok het blok dat onmiddellijk voorafgaat aan het te coderen blok wordt gebruikt.

7. Werkwijze volgens een der voorgaande conclusies, waarbij na het vervangen van een reeks door een code de eerstvolgende nietgecodeerde gegevensgroep wordt gecodeerd met een code die geheel bestaat uit deinhoud van die gegevensgroep.

8. Werkwijze volgens een der voorgaande conclusies,waarin een gegevensgroep een groep van vier bits omvat.

9. Werkwijze voor het decoderen van gecodeerde digitale beeldgegevens, welkebeeldgegevens in ongecodeerde vorm opeenvolgende blokken van binnen de blokkenop opeenvolgende posities gelegen gegevensgroepen met als inhoud binaire waardenvan steeds een gelijk aantal pixels van een afbeelding omvatten, en in gecodeerde vormeen reeks codes omvatten, omvattende het steeds voor een volgende code van de codereeks vaststellen, aan de hand vaneen voorafbepaald gedeelte van de code, of deze verwijst naar een referentieblok vanongecodeerde beeldgegevens en, in het bevestigende geval, het selekteren, aan de hand van een tweede vooraf bepaald gedeelte van de code,van een gegevensgroep met ten minste een overgang in pixelwaarde in hetreferentieblok en het expanderen van de betreffende code in een reeks gegevensgroepen, die dezelfdeinhoud heeft als de reeks gegevensgroepen in het referentieblok, beginnend op depositie volgend op de positie van de laatste gegevensgroep die uit de voorafgaandecode is gevormd en eindigend bij de positie van de geselekteerde gegevensgroep in hetreferentieblok.

10. Werkwijze volgens conclusie 9, waarin bovendien uit een voorafbepaald gedeelte van de code wordt bepaald, of degenoemde geselekteerde gegevensgroep in het referentieblok al of niet tot de bij degenoemde expansie over te nemen gegevensgroepen behoort, enwaarin de genoemde geselekteerde gegevensgroep in het referentieblok in hetbevestigende geval wordt overgenomen als laatste element van de door de expansiegevormde reeks.

11. Werkwijze volgens conclusie 9 of 10, waarin als referentieblok het voorgaande gedecodeerde blok wordt gebruikt.

12. Werkwijze volgens conclusie 9, 10 of 11, waarin na het expanderen van een code, uit de eerstvolgende code een gegevensgroepwordt gevormd door de inhoud van die code onveranderd over te nemen.

13. Werkwijze voor het decoderen van volgens de werkwijze van een dervoorgaande conclusies gecodeerde digitale beeldgegevens,omvattende het steeds voor een volgende code van de codereeks vaststellen, aan de hand van eenvoorafbepaald gedeelte van de code, of deze verwijst naar een referentieblok vanongecodeerde beeldgegevens en, in het bevestigende geval, het selekteren, aan de hand van een tweede vooraf bepaald gedeelte van de code,van een gegevensgroep metten minste een overgang in pixelwaarde in hetreferentieblok en het expanderen van de betreffende code in een reeks gegevensgroepen, diedezelfde inhoud heeft als de reeks gegevensgroepen in het referentieblok, beginnend opde positie volgend op de positie van de laatste gegevensgroep die uit de voorafgaandecode is gevormd en eindigend bij de positie van de geselekteerde gegevensgroep in hetreferentieblok.

14. Werkwijze volgens conclusie 13, waarin bovendien uit een voorafbepaald gedeelte van de code wordt bepaald, of degenoemde geselekteerde gegevensgroep in het referentieblok al of niet tot de bij degenoemde expansie over te nemen gegevensgroepen behoort, enwaarin de genoemde geselekteerde gegevensgroep in het referentieblok in hetbevestigende geval wordt overgenomen als laatste element van de door de expansiegevormde reeks.

15. Inrichting voor het coderen van digitale beeldgegevens omvattendeopeenvolgende blokken van binnen de blokken op opeenvolgende posities gelegengegevensgroepen met als inhoud binaire waarden van steeds een gelijk aantal pixelsvan een afbeelding, omvattende toevoermiddelen voor het toevoeren van de pixelwaarden van een te coderen bloken die van een referentieblok middelen om vast te stellen, of zich in het te coderen blok een reeks vanopeenvolgende gegevensgroepen bevindt, die elk dezelfde inhoud hebben als degegevensgroep op dezelfde positie in het referentieblok en een codegenerator, die een code afgeeft voor de genoemde reeks,met het kenmerk, dat de codegenerator is voorzien van middelen om de positie van het einde van de reeks tenopzichte van een overgang in pixelwaarde in het referentieblok te bepalen en vanmiddelen voor het samenstellen van de genoemde code, die zijn ingericht om dezepositie in de code te beschrijven.

16. Inrichting volgens conclusie 15,met het kenmerk, dat de middelen om de positie van het einde van de reeks te bepalen tevens zijn ingerichtom de positie van de overgang in pixelwaarde in het referentieblok, ten opzichtewaarvan de positie van het einde van de reeks wordt beschreven, te bepalen en dat demiddelen voor het samenstellen van de code zijn ingericht om in de code eenidentificatie van de genoemde overgang in pixelwaarde op te nemen.

17. Inrichting volgens conclusie 16,met het kenmerk, dat de middelen voor het samenstellen van de code tevens zijn ingericht om in de code aante geven, of de gegevensgroep in het te coderen blok, gelegen op de positie van degegevensgroep in het referentieblok, waarin de overgang in pixelwaarde is gelegen, tenopzichte waarvan de positie van het einde van de reeks wordt beschreven, nog tot dereeks behoort.

18. Inrichting voor het decoderen van gecodeerde digitale beeldgegevens, welkebeeldgegevens in ongecodeerde vorm opeenvolgende blokken van binnen de blokkenop opeenvolgende posities gelegen gegevensgroepen met als inhoud binaire waardenvan steeds een gelijk aantal pixels van een afbeelding omvatten, en in gecodeerde vormeen reeks codes omvatten, omvattende middelen voor het ontvangen van de reeks codes; een geheugen voor het opslaan van een referentieblok van gegevensgroepen inongecodeerde vorm; eerste interpretatiemiddelen voor het steeds voor een volgende code van decodereeks, selekteren van een voorafbepaald gedeelte van de code, het interpreterenvan dat gedeelte, het op grond van die interpretatie bepalen van de lengte van de codeen vaststellen of deze code verwijst naar een referentieblok van ongecodeerdebeeldgegevens, en het, indien de laatstgenoemde test bevestigend is beantwoord,doorgeven van de code aan: tweede interpretatiemiddelen welke zijn ingericht voor het selekteren van een tweede vooraf bepaald gedeelte van de code, het interpreteren daarvan en het op grond van die interpretatie selekteren van een gegevensgroep metten minste een overgang inpixelwaarde in het referentieblok; expansiemiddelen voor het vormen van een reeks gegevensgroepen door de inhoud van opeenvolgende gegevensgroepen in het referentieblok, vanaf degegevensgroep op de positie volgend op die van de laatste gegevensgroep die uit devoorafgaande code is gevormd tot de positie van de door de tweedeinterpretatiemiddelen geselekteerde gegevensgroep, te kopiëren en de zo gevormdereeks toe te voegen aan de uit de voorafgaande codes gevormde gegevensgroepen.

17. Inrichting volgens conclusie 16, waarin de tweede interpretatiemiddelen zijn ingericht om op grond van de interpretatievan de code een keuzecommando af te geven en waarin de expansiemiddelen zijn ingericht om op grond van het keuzecommando,afgegeven door de tweede expansiemiddelen, de inhoud van de door de tweedeinterpretatiemiddelen geselekteerde gegevensgroep te kopiëren en de zo gevormdegegevensgroep aan de gevormde reeks toe te voegen als laatste element.