Neoweb.nl
Neoweb wetenschapsforum. Duurzame technologie en innovatieve wetenschappelijke onderwerpen. => Informatie Technologie, Telecommunicatie (ICT) en Electronica (Alles over de Digitale Revolutie) => Topic started by: Digihans on January 17, 2007, 09:37:55 AM
-
Sudoku-Compressie, Sudocompressie
Hallo, ik heb een nieuwe vorm van compressie van digitale bestanden bedacht.
Het is echter te complex om goed door te rekenen. Dus ik weet niet of het echt werkt.
Mijn idee is als volgt:
Stel je hebt een afbeelding van 100 x 100 pixels (dat is een redelijk klein plaatje)
Je geeft alle kleuren een bepaalde waarde
Per horizontale rij tel je de kleurwaardes bijelkaar op (totaal 100 kleuren)
Ook per verticale kolom tel je de kleuren bijelkaar op (totaal 100 kleuren)
Eventueel kun je ook diagonalen optellen. (in de hoeken dus 1 kleur, midden in weer 10 kleuren)
Als je deze informatie hebt, zou je de afbeelding weer moeten kunnen reconstrueren.
Het werkt dan als een soort 'sudoku' puzzel die de ontbrekende pixel met bijbehorende kleurwaarde invult.
Eventueel kun je met 'sleutel' waardes de puzzel vereenvoudigen. Bijvoorbeeld door de kleur informatie van iedere 50e pixel hard op te slaan.
Een bijpassende naam vind ik wel op z'n plaats: Sudoku-compressie (of sudocompressie)
Wie kan hier iets zinnigs over melden?
-
Dat gaat denk ik niet werken.
als je diagonaal erbij doet dan is er weinig compressie, maar als je alleen verticaal en horizontaal doet kan je volgens mij niet uitrekenen wat de kleur van elke pixel wordt.
Ik geef je ff een voorbeeldje van 5 bij 5 pixels zodat je kan kijken of je het zelf wel kan uitrekenen.
Kan je programmeren? Of weet je hoe de kleur van een pixel in 1 getal wordt weergegeven?
Zonee, dan leg ik het ff uit. Een pixel-kleur is opgebouwd uit 3 getallen die van 0 tot 255 gaan. Rood, Groen en Blauw. Daar wordt 1 getal van gemaakt op de volgende manier:
(ik kort de rode, groene en blauwe kleur-waarde ff af met r, g en b)
Kleur = r + (g * 256) + (b * 256^2)
Nu heb ik een plaatje gemaakt van 5 bij 5 pixels. De kleuren heb ik geheel willekeurig gekozen. ik zal je de uitkomsten geven van de pixels opgeteld van elke verticale en horizontale rij en dan mag jij kijken of jij kan uitrekenen welke pixel welke kleur is.
uitkomsten van de horizontale lijnen:
17528309, 21102974, 42008958, 25297088, 46773749
uitkomsten van de verticale lijnen:
16842750, 25231615, 42123007, 33604096, 34909610
dat zou er dus ongeveer zo uitzien:
? ? ? ? ? = 17528309
? ? ? ? ? = 21102974
? ? ? ? ? = 42008958
? ? ? ? ? = 25297088
? ? ? ? ? = 46773749
= = = = =
1 2 4 3 3
6 5 2 3 4
8 2 1 6 9
4 3 2 0 0
2 1 3 4 9
7 6 0 0 6
5 1 0 9 1
0 5 7 6 0
Die vraagtekens staan dus voor pixel-waardes
Probeer jij maar eens erachter te komen wat de kleur-waardes van die pixels zijn.
-
Dit kan lukken --> maar dan moet je ze VERMENIGVULDIGEN ipv sommeren ;D
(anders krijg je onbepaalde stelsels)
indien je alle diagonaal producten erbij krijgt (bovenlinks --> rechsonder en bovenrechts --> linksonder) en van elke rij en elke kolom, DAN IS DIT MOGELIJK!
toch moet je rekening houden met een paar zaken dan...
1) als je al de waarden vermenigvuldigd van een rij, dan kan het product een zodanig groot getal zijn dat het waarschijnlijk niet meer in een integer of zelfs een double waarde kan --> je hebt dan terug meerder opslaglaatsen nodig.
2) om je afbeelding terug te construeren moet je grote stelsel kunnen oplossen. --> matrixen bieden hiervoor een oplossing. --> veel geheugen nodig.
3)stel n gelijk aan het aantal pixels je wilt comprimeren... bij een afbeelding van 3*3pixels is dit bvb 9, dan is je compressietechniek pas efficient als 6*vierkantswortel(n) <n, dus moet n>36 of vanaf een afbeelding van 6*6 pixels. En dit ervan uitgaande dat ieder product terug in één interger/double past (wat geen realiteit zal zijn)
het is dus mogelijk, maar omdat je ze moet vermenigvuldigen en omdat het product te groot zal zijn om efficient bij te houden, ligt het compressieratio te laag.
grtjs,
Philippe
-
Je kan de optelsom per rij natuurlijk ook weer vereenvoudigen door de samenstellende factoren op te slaan.
of alle getallen een fixed length geven en met patroonherkenning weer de getallen vereenvoudigen.
Bijvoorbeeld alle getallen die de string "4289" bevatten vervangen door a.
Uiteindelijk krijg je een bijzonder krachtige compressie, die wel 'moeilijk' is uit te rekenen.
Maar voor langdurige opslag van data, die niet vaak gebruikt wordt, is dit misschien een interessante oplossing.
-
Ik heb nog een nieuwe compressie-methode in gedachte voor bijvoorbeeld digitale films.
1. golfpatroon intersectie in tijd per pixel
Stel je hebt een film. het beeld bestaat uit een raster van beeldpuntjes.
Ieder beeldpuntje zal in de loop van de tijd veranderen in één van de volgende 'kleuren' (rood groen blauw zwart (wit))
Met een aantal complexe golfpatronen zou je het gedrag van één pixel gedurende een hele film kunnen simuleren.
Je hebt eerst een standaard golf patroon die zich beweegt tussen rood groen en blauw.
Speel je dit af, dan zie je dus iedere frame een andere kleur in de pixel.
Om de pixel op een bepaald moment een andere kleur te laten worden, introduceer je een 2e golf.
In een pixel zullen meerdere herhalende rgb-patronen zitten, die je met verschillende golffrequenties en samengestelde golven kunt triggeren.
-
Een variant hierop is een enorm virtueel 3 dimensionaal blok, waarbij ieder videobeeldje achter elkaar staat.
Door golflengtes van verschillende hoeken hier in te schieten, kun je alle pixelpunten triggeren.
Het enige dat je dan op hoeft te slaan is een (enorme reeks) van golflengtes, bijbehorende invalshoeken en start coordinaten.
-
Even een brainstorm:
Toekenning waardes aan individuele kleuren
RGBZW (red, green, blue, zwart wit)
0 1 2 4 8
Neem een willekeurige reeks kleuren
bijvoorbeeld:
RBGZGBBGGZZWWBZGRWRBWZZB (=25 pixels)
Vervang de kleuren door de getallen, dan ontstaat de volgende primaire reeks
021412211448824108028442
In deze reeks komen een aantal 'paren' steeds terug:
02 - 14 - 12 - 21 - 14
(Op een grotere reeks komen trioparen of quadparen vaker terug.)
Stel je vereenvoudigt de bovenstaande primare reeks weer met de volgende duo-paren sleutel tabel:
00 0 0
01 1 1
02 2 2
04 4 3
08 8 4
10 16 5
11 32 6
12 64 7
14 128 8
18 256 9
20 512 A0
21 1024 A1
22 2048 A2
24 4096 A3
28 8192 A4
40 16384 A5
41 32768 A6
42 64536 A7
44 131072 A8
48 262144 A9
80 524288 B0
81 1048576 B1
82 2097152 B2
84 4194304 B3
88 8388608 B4
De primaire reeks kan dan worden vervangen door:
2 8 7 A1 8 A8 B1 A6 4 2 B2 A7 (18 karakters) (72% compressie)
Wanneer je de trio-paren neemt kun je de data nog verder vereenvoudigen.
Maar binnen de secundaire reeks kunnen ook herhalende duo-paren (of trio-paren) worden ontdekt.
287A18A8B1A642B2A7 (deze reeks is helaas te kort om dat aan te tonen, maar in een film van 90 minuten is dat zeker het geval)
Het moeilijke hieraan is onze 'telling' .
Een reeks met 5 mogelijke waardes (rgbzw) wordt eerst omgezet naar iets numeriekst door introductie van 0 1 2 4 8 (die wij als getallen kennen)
Hieraan worden patronen een bepaalde waarde meegegeven. Echter refereert ons telsysteem slechts aan 10 cijfers. Daarna krijg je getallen die niet meer op zichzelf uniek zijn. (12 kan ook 1,2 zijn en een ander voorbeeld: 111, is dat nu 1,1,1 of 11,1 of 1,11 of toch 111?) Daarom introduceren we extra 'data referenties' zoals A en B)
Om de secundaire reeks te vereenvoudigen heb je dus een sleuteltabel nodig, waarin alle paren van 0-9 en A & B zitten.
Het aantal combinaties stijgt dan naar zo'n 121 combinaties, waarmee je weer een nieuwe sleuteltabel nodig hebt die nog 10 extra unieke datareferenties heeft (A=10, B=20, C=30, D=40, E=50, F=60, G=70, H=80, I=90, J=100)
De sleuteltabel van deze reeks bestaat dan uit 212 combinaties = 441.
Om dit te halen heb je extra data referenties nodig: K=200, L=300 en M=400 ...
Weer 3 extra combinatie.
dus 242 = 576
Daarvooer heb je weer O=500 nodig
Dus 1 extra combinatie = 25
252 = 625
weer een extra referentie nodig P=600
262 = 676
Hier stopt de groei van datareferenties (in dit voorbeeld)
Uiteindelijk kun je alle data van de orginele reeks dus beschrijven met 3 posities
bijvoorbeeld PA2 (612) Maar zit je nog steeds op 12% van je orginele data
-
Klinkt op zich interessant, het is alleen dan nog maar wel de vraag of het constant berekenen van dit soort toch redelijk ingewikkelde formules per frame er niet voor zorgt dat de framerate tot onder het kijkbare daalt. Maar mss als er met vaste tabellen wordt gewerkt die een vastgesteld resultaat beschrijven dat het nog wel te programmeren valt.
Houd je er trouwens wel rekening mee dat een pixel behalve rgbwz ook geel (rood plus groen) en lichtblauw (groen plus blauw) en paars (rood plus blauw) hebben. Dat zijn dus totaal 8 verschillende kleuren die een pixel kan bevatten.