Deel dit artikel

vroeger was er vaak een tekort aan meetgegevens. de vooruitgang van sensor- en meettechnieken en de beschikbaarheid van recorders, scanners, hogedoorvoerapparatuur, microarrays en digitale camera’s zorgen nu voor een toevloed van digitale gegevens. het wordt bijna onmogelijk om al die gegevens op te slaan, laat staan ze te verwerken. nieuwe wiskundige technieken – aangepaste algoritmen van signaalverwerking – maken nu een substantiële compressie van meetgegevens mogelijk.

Gegevenscompressie van bij de bron

Joos Vandewalle

Om de toevloed van digitale gegevens te beheersen werden nieuwe wiskundige technieken gezocht en gevonden. Het vernieuwende karakter van deze compressiemethodes bestaat erin dat compressie gebeurt zo dicht mogelijk bij de sensor die gegevens meet. Een goede keuze van het referentiestelsel waarin de meetgegevens worden gemeten of omgezet, laat toe om een aangepaste voorstelling te maken met veel nullen. Alleen die bijdragen die niet nul zijn, moeten dan worden voorgesteld.

De waarden die door een meetinstrument of sensor worden weergegeven, kunnen zowel digitaal als analoog worden gemeten en getoond. Voorbeelden uit het dagelijkse leven zijn een horloge, een weegschaal, een snelheidsmeter of een verbruiksmeter van elektriciteit. Bij een analoge meting of registratie in een traditionele horloge geeft een wijzer op een schaalverdeling langsheen een cirkel het uur aan, een tweede wijzer geeft de minuten aan en een derde de seconden. Bij een digitaal uurwerk worden het uur, de minuten en de seconden met een reeks van drie getallen aangegeven. Een analoge uitlezing biedt het voordeel dat het mogelijk is om in één oogopslag een idee te krijgen van het tijdstip, terwijl de digitale uitlezing als voordeel heeft dat die erg precies kan zijn. Een belangrijk nadeel van een digitale meting is echter dat het getal in de uitlezing de valse indruk geeft van een volstrekte juistheid. Elk meetinstrument, zowel analoog als digitaal, heeft immers een beperkte nauwkeurigheid. Dit inzicht is van groot belang bij het ontwerpen van ICT-apparatuur.

Wanneer een analoog signaal in een digitaal signaal moet worden omgezet, moeten we een keuze maken voor het aantal niveaus dat wordt gebruikt voor deze conversie. Dit komt neer op het aantal decimale cijfers dat voorzien wordt voor de voorstelling van het analoge signaal. Hierbij moet de opsplitsing in niveaus natuurlijk niet fijner zijn dan de nauwkeurigheid van het meetinstrument. Vaak wordt de keuze van het aantal niveaus ook bepaald door de technische of budgettaire beperkingen, want het is technisch moeilijker en dus duurder om meer decimalen te voorzien. In de praktijk worden de signalen overigens niet met decimale getallen voorgesteld, maar met binaire getallen en dat aantal binaire eenheden noemen we ‘bits’. Een bit is de kleinste eenheid van digitale informatie. De wiskunde van de bits en ook de digitale technologie zijn beide veel eenvoudiger dan die van de decimale getallen. Computers en digitale elektronica maken overvloedig gebruik van bits, zowel bij de opslag als bij de verwerking van informatie. Zo wordt de intensiteit van muziek of spraak bij cd’s telkens met 16 bits voorgesteld: hiermee, kunnen we 216 = 65 536 niveaus onderscheiden. Met andere woorden, de dynamiek in het signaal, de verhouding tussen het sterkst mogelijke en het zwakst mogelijke signaal, is 216 = 65 536. In een digitale fotocamera is het aantal grijstinten van de beeldpunten of pixels dat kan worden onderscheiden gewoonlijk 28 = 256 niveaus. Deze pixels kunnen dus worden voorgesteld met 8 bits. Het aantal beeldpunten of pixels is begrensd tot enkele miljoenen (megapixels). Deze keuzes zijn een afweging tussen de menselijke perceptie van het beeld en de kostprijs van de sensoren en verwerking in de camera.

Naast het omzetten van analoge waarden naar digitale waarden – wat in een analoog-naar-digitaal-converter gebeurt – moet er voor signalen die veranderen in de tijd, zoals geluid, muziek of beelden, ook een bemonstering in de tijd gebeuren. Er moet dus op geregelde tijdstippen een waarde of een beeld worden genomen. Voor cd-opnames van geluid, muziek en spraak is afgesproken om 44 100 monsters per seconde (44,1 kHz) op te nemen. Technisch kan men veel sneller bemonsteren dan deze 44,1 kHz, maar het menselijke gehoor kan het verschil niet meer detecteren. Het bemonsteren van een signaal gebeurt technisch in een bemonsteraar (of sampler). Dit is opnieuw technisch moeilijker naarmate dit sneller moet gebeuren. Omwille van de kostprijs komt het er dus op aan om niet sneller te bemonsteren dan nodig is. Bovendien levert sneller bemonsteren niet altijd meer informatie op, omdat het signaal vaak een beperkte bandbreedte heeft, en dus niet snel kan variëren. In die context wordt vaak verwezen naar de bemonsteringsstelling van Nyquist en Shannon. Die garandeert dat als er voldoende snel bemonsterd wordt, het volledige signaal correct kan worden gereconstrueerd bij de weergave. In het geval van een cd-speler is dit dan een correcte weergave van het signaal voor de luisteraar. Bij videobeelden worden doorgaans vijftig stilstaande beelden per seconde opgenomen, en achtereenvolgens even snel weergegeven. Bij het bekijken van deze sequentie van stilstaande beelden zullen onze ogen de beelden op een vloeiende manier terug met elkaar verbinden en ons het gevoel geven bewegende beelden te zien, zoals dat ook in films gebeurt. Met andere woorden, onze ogen reconstrueren de beweging.

Als er voldoende snel bemonsterd wordt, kan het volledige signaal correct worden gereconstrueerd bij de weergave

De vooruitgang van de chiptechnologie en de sensortechnologie heeft een exponentiële groei in sensorgegevens veroorzaakt. Er zijn alsmaar meer sensoren beschikbaar, en ze produceren steeds grotere bitstromen. Sensoren voor digitale camera’s zijn in prijs gedaald tot rond de 1 euro per megapixel (= 106 pixels = miljoen pixels). Steeds grotere groepen consumenten kunnen nu foto’s en video opnemen, versturen en opslaan. Naast de miljoenen veiligheids- en bewakingscamera’s zijn ook satellietcamera’s, digitale radio-ontvangers en milieudetectoren wijdverspreid. Die grote hoeveelheden sensoren produceren een toevloed van gegevens. Terwijl vroeger het beperkte aantal en de kostprijs van de sensoren een flessenhals was, is er nu een beperking van de opslag bij de gegevens en de verwerking ervan.

In een recent rapport in Science werd gesteld dat er wereldwijd ieder jaar 58 procent meer gegevens beschikbaar worden, en dan vooral via sensoren. Er wordt geraamd dat de hele wereld in 2010 1 250 miljard gigabytes aan gegevens produceerde (1 gigabyte is 8×109 bits). Dit zijn meer bits dan er sterren zijn in het universum. De totale hoeveelheid opslagcapaciteit in termen van harde schijven, geheugenchips, USB-sticks of geheugenkaarten neemt daarentegen slechts toe met 40 procent per jaar. Een mijlpaal werd bereikt in 2007, toen evenveel nieuwe gegevens werden geproduceerd als er opslagcapaciteit was. In 2011 werden al twee keer zoveel bits geproduceerd als er opslagcapaciteit was. De discrepantie tussen de productie en de opslag van bits wordt steeds groter, en ook de verwerkingscapaciteit kan geen gelijke tred houden met de bitproductie.

De discrepantie tussen de productie en de opslag van bits wordt steeds groter, en ook de verwerkingscapaciteit kan geen gelijke tred houden

Deze toevloed aan gegevens vraagt om fundamentele vernieuwingen in de theorie en de praktijk van sensorontwerp, algoritmes voor signaalverwerking, breedbandtelecommunicatietechnieken, compressietechnieken en geheugenontwerp. De basisreden waarom compressie van bits mogelijk is, ligt in de eenvoudige observatie dat de meeste signalen, beelden en video zeer veel herhaling, dode zones of gelijke of homogene gebieden bevatten, waardoor vele bits in feite niet veel nieuws te vertellen hebben. Denken we maar aan bewegende beelden, waar er tussen twee opeenvolgende beelden weinig verschil is. Ook binnen één beeld zijn er vaak grote gebieden van bijvoorbeeld blauwe lucht waar de pixels niet veel van elkaar verschillen. Vele biomedische signalen, zoals elektrocardiogrammen, vertonen in één periode enkele pieken die interessant zijn, maar daartussen is er vaak een dode zone die niet belangrijk is. Ook in de muziek en de spraak zijn er heel wat overbodige bits, omdat er meestal slechts een beperkt aantal frequenties voorkomt in deze signalen. In spraak, beeld en video heeft men daarom nu al een sterke compressie van bits kunnen realiseren met aangepaste compressiemethodes zoals JPEG voor beelden, MPEG voor video en MP3 voor audio. Om een vlotte uitwisseling hiervan mogelijk te maken, werden die compressiemethodes gestandaardiseerd, met een grote populariteit tot gevolg.

‘Compressed sensing’ nu heeft de ambitie om nog veel verder te gaan in compressie, met name om de compressie al onmiddellijk uit te voeren dicht bij de sensor, zodat alle verdere activiteiten zoals opslag en verwerking nog veel efficiënter kunnen. De achterliggende redenering is dat de signalen en beelden niet willekeurig zijn, maar uit een zeer kleine deelverzameling komen van de grote verzameling van alle mogelijke signalen. Anders uitgedrukt, in het geheel van de mogelijke beelden die met de sensoren gecapteerd kunnen worden, zijn de realistische of nuttige beelden zeer dun bezaaid. Hiervoor wordt de Engelse term ‘sparse’ gebruikt. Het bemonsteringsproces kan dus speciaal worden afgestemd op het zoeken in deze kleine deelverzameling, en dat kan men met veel minder bits voorstellen. Hiervoor maakt men gebruik van de techniek ‘sparse sampling’ waarbij het aantal monsters of samples nog veel geringer is dan dat voorgeschreven door de Nyquist-Shannon-grens. We zullen dit nu zonder formules, maar toch in een wiskundige context formuleren. Het meten van een signaal of beeld kunnen we opvatten als het zoeken naar een punt of het lokaliseren van dat punt in de ruimte van de mogelijke signalen of beelden. We meten dus de coördinaten van dat punt zoals een landmeter dat doet voor het lokaliseren van een referentiepaal van een perceel.

In het geheel van de mogelijke beelden die met de sensoren gecapteerd kunnen worden, zijn de realistische of nuttige beelden zeer dun bezaaid

De wiskunde leert ons dat we van één coördinatenstelsel naar een ander coördinatenstelsel kunnen overstappen door het vermenigvuldigen met een passende matrix, of omgekeerd door een stelsel van vergelijkingen op te lossen. Het vinden van de passende sparse voorstelling van een beeld of een signaal bestaat er dan in een oplossing te zoeken van een stelsel van zo’n coördinatentransformatie die weinig van nul verschillende coördinaten heeft, en dus sparse is. Uiteraard moet ook een goede coördinatentransformatie worden gebruikt, waar een sparse oplossing te vinden is. Dit moet natuurlijk ook worden bekeken in de context van de beperkte nauwkeurigheid van de metingen, wat betekent dat we niet moeten zoeken naar een exacte sparse oplossing van het stelsel, maar een benaderende oplossing, die rekening houdt met de nauwkeurigheid van de metingen. Benaderende oplossingen van stelsels van vergelijkingen worden al vaak gebruikt in de techniek, de telecommunicatie en de automatisering. Meestal gebruikt men hierbij de methode van de kleinste kwadraten. Men gaat dan op zoek naar een benaderende oplossing waarbij de som van de kwadraten van alle gemaakte fouten zo klein mogelijk is. Die is vrij vlot te berekenen, maar heeft wel de eigenschap dat de oplossing meestal niet sparse is. Daarom gebruikt men bij ‘compressed sensing’ andere manieren om fouten te schatten. Men gaat bijvoorbeeld op zoek naar een benaderende oplossing waarbij de som van de absolute waarden van de gemaakte fouten zo klein mogelijk is. Men spreekt dan over de L1-norm. Of men zoekt de oplossing die zo sparse mogelijk is, dit wil zeggen die op zoveel mogelijk plekken nul is. Dan heeft men het over de L0-norm.

Als één van zijn recente activiteiten onderzocht Frontiers of Engineering een aantal van de bemoedigende methodieken voor ‘compressed sensing’. Eén veelbelovende richting is het ontwerp van nieuwe soorten data-acquisitiesystemen die conventionele sensoren vervangen door sensoren die het meten combineren met de compressie en gegevensverwerking in één globale handeling. Bij een andere veelbelovende denkrichting draaien de onderzoekers het probleem om als volgt. Stel dat men met een digitale camera een grote collectie van ongeorganiseerde beelden van één scène heeft opgenomen (bijvoorbeeld foto’s van de Notre Dame in Parijs), en dat elke foto automatisch het standpunt en een driedimensionaal model van de scène berekent. Eenmaal die gegevens berekend zijn, kan men elk van de originele foto’s reconstrueren aangezien we het standpunt van de fotograaf voor deze foto kennen en een volledige vergelijking van het object in drie dimensies.

Op lange termijn moeten we echter verwachten dat de overvloed aan meetgegevens niet zal verdwijnen zonder radicale superexponentiële vooruitgang in de computer-, communicatie- en opslagcapaciteit. De volgende generatie van sensorontwerpen en signaalverwerkingsmethodieken zal de overvloed van meetgegevens maximaal moeten benutten. Men kan zich hierbij wel een aantal conceptuele vragen stellen. Zoals: kan men de wetenschappelijke conclusies en de bewijslast van beelden in juridische situaties vertrouwen, als de ruwe experimentele gegevens verloren zijn gegaan en het decompressiealgoritme eventueel geïnfecteerd is door een computervirus? Of kunnen we de nieuwe wiskundige modellen met lage complexiteit en de nieuwe praktische meetmethodes ontwikkelen die nodig zijn om de relevante informatie te halen uit de overvloed aan bits? Het is duidelijk dat dit spannende tijden zijn voor het ontwerp van sensorsystemen.

Richard G. Baraniuk, ‘More Is Less: Signal Processing and the Data Deluge’, in: Science, 2011, 331, 717.
U.S. National Academy of Engineering and Royal Academy of Engineering, Frontiers of Engineering, EU-US Symposium. Cambridge, Verenigd Koninkrijk, van 31 augustus tot 3 september 2010. www.raeng.org.uk/international/activities/frontiers_engineering_symposium.htm.

Joos Vandewalle is als burgerlijk ingenieur elektrotechniek en wiskundige ingenieurstechnieken verbonden aan de KU Leuven.

Deel dit artikel
Gerelateerde artikelen