Mein Format Decodieren

Die Umwandlung eines DSO/TRN in ein BMP-Bild 

1.0 Einleitung

Die Umwandlung des TRN- bzw. DSO- Formates war eine sehr schwierige Sache, da hier der Hauptteil meiner Arbeit lag. Die Umwandlung sollte in "Echtzeit" geschehen, dh. innnerhalb einer Sekunde sollten die Bilder bei einer Größe von 384x384 auf dem Bildschirm dargestellt werden. Zu dieser Zeit war ein 486'iger noch ein Standardrechner. Ein Bild mit 384x384 sollte auf einem 486iger mit etwa 50Mhz innerhalb einer Sekunde dargestellt werden. Diese Anforderung ist sehr hoch, da allein eine Darstellung eines BMP-Bildes in dieser Größe schon eine halbe Sekunde benötigt. Schuld daran sind die langsamen Grafiktreiber. Enttäuschend von der Firma war, daß ich einen 386iger zum Programmieren zur Verfügung gestellt bekam. Das war für mich unzumutbar. Erstens programmierte ich unter Windows. Und zweitens konnte ich somit nicht das interne Cacheverhalten der CPU's austesten, denn darauf beruhen meine Programmroutinen. Ich habe also meine eigene CPU mitbringen müssen, mehr möchte ich nicht dazu sagen. Zu dieser Zeit wahr schon abzusehen, daß die CPU's wesentlich schneller laufen, als der externe Cache. Somit war es von wichtiger Bedeutung, daß meine Routinen sehr klein werden mußten. Ich habe aus diesem Grund viele Tests durchführen müssen.

2.0 Die schrittweise Umwandlung von BMP nach DSO

Die Umwandlung des DSO- bzw. TRN- Formates geschieht schrittweise. Die Schritte der Decodierung sind natürlich genau anders herum, als die der Codierung. Die Unterteilung der Schritte ist hier kurz dargestellt.

2.1 Der 1.Schritt Lesen des Headers

Eine DSO- oder TRN- Datei hat eine 8Byte langen Header
Byte
Typ
Format
Beschreibung 
0 ..1
word
intel
 Erkennung immer "DS"
2 ..3
word
intel
 X ... Pixels per Row
4 ..5
word
intel
 Y ... Lines
6
byte
intel
 Quantisierung für Y-Matrix
7
byte
intel
 Quantisierung der Farben
 
Der Header ist ziemlich klein gehalten. Aus den X, Y- Werten wird der Rest errechnet, z.B. MCU-Anzahl, Bildgröße, ect. Wie man sieht wird eine getrennte Qualtäten für Farbe und Helligkeit gespeichert. Der Aufbau von Bildblöcken geschieht MCU- orientiert. Bei der Codierung werden die MCU's nullgepackt und dann in einen Block geschrieben, der 8Kb nicht überschreiten darf, Dies ist der maximale Bildblock. Danach wird dieser Block Huffmanncodiert, so entsteht ein Bildblock. Vor jedem Block stehen zwei Wordzahlen. Die erste Zahl gibt Auskunft über die Größe des Bildblocks. Die zweite Zahl sagt wie groß der Block nach der Huffmandecodierung ist. Das hat programmtechnische Hintergründe.

2.2 und 2.3 Die Huffmandecodierung und die Nulldecodierung

Die Huffmandecodierung erfolgt äquivalent zur Huffmancodierung durch die selbst erstellten festen Tabellen. Der ganze Bildblock wird decodiert und in einen großen 8kb- Puffer überspielt. Nun werden aus dem 8Kb Block die MCU's stückweise ausgelesen. Dies geschieht so,
  1. Lesen eines WORD's
  2. Auspacken der Nullen in einen MCU-Vektor
  3. So lange bis der MCU-Vektor voll ist, ansonsten gehe zu 1.
Nun steht immer eine MCU zur Verfügung.

Schritt 4 und Schritt 5 Dequantisieren und ZigZag- Rescanning

Die MCU's werden nun dequantisiert. Dazu werden die Integerzahlen mit einem bestimmten Faktor multipliziert. Danach werden die Werte aus dem Vektor an eine bestimmte Stelle in den vorgesehenen Matrizen gespeichert. Nun stehen die 4 Frequenz- Y- Matrizen und die 2 Farbmatrizen zur Verfügung. Jetzt kann die inverse Cosinustransformation durchgeführt werden. Hier ein kleines  Beispiel für die Umwandlung des Vektors in die Matrix;
M[0][0] := V[ 0];
M[1][0] := V[ 2];
M[4][2] := V[23];
M[7][7] := V[64];
64'iger Vektor mit Elementen aus 8 * 8 Matrix
 
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
0x
OO
01
10
20
11
02
03
12
21
30
1x
40
31
22
13
04
05
14
23
32
41
2x
50
60
51
42
33
24
15
06
07
16
3x
25
34
43
52
61
70
71
62
53
44
4x
35
26
17
27
36
45
54
63
72
73
5x
64
55
46
37
47
56
65
74
75
66
6x
57
67
76
77
 
 
 
 
 
 
 
 ===>
Lage Vektorelemente in 8 * 8 Matrix
  xO x1 x2 x3 x4 x5 x6 x7
0x  
1x  
2x  
3x  
4x  
5x  
6x  
7x 
00 01 05 06 14 15 27 28 
02 04 07 13 16 26 29 42 
03 08 12 17 25 30 41 43 
09 11 18 24 31 40 44 53 
10 19 23 32 39 45 52 54 
20 22 33 38 46 51 55 60 
21 34 37 47 50 56 59 61 
35 36 48 49 57 58 62 63 
 
In den folgenden Tabellen sind die Dequantisierungstabellen aufgelistet, die von meinem Programm verwendet werden. Jede Multiplikation wird mit SAL (Assembler Shift Arithmetik Left) ausgedrückt. Das SAL-Effektiv ist deshalb aufgeführt, da mit der SAL-Bewegung in meinem Programm die Werte gleichzeitig normiert werden. Das heißt, die Brüche (aus der FPU- Emulation) bestehen aus Zahl/2^5 (Zahl/32'igstel). Mit diesem SAL werden also 2 Fliegen mit einer Klappe geschlagen, Dequantisierung plus Normierung. SAL wird deswegen genommen, damit die negativen Zahlen erhalten bleiben.
1. Quantisierungstabelle 1-2%  sehr gute Qualität
Multiplikator Matrix
SAL-Matrix
SAL-Effektiv
01 02 02 02 04 08 08 08
02 02 02 08 08 08 08 08
02 04 04 08 08 08 08 08
02 04 08 08 08 08 08 08
04 08 08 08 08 08 08 08
08 08 08 08 08 08 08 08
08 08 08 08 08 08 08 08
08 08 08 08 08 08 08 08
0 1 1 1 2 3 3 3
1 1 1 3 3 3 3 3
1 2 2 3 3 3 3 3
1 2 3 3 3 3 3 3
2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
5 6 6 6 7 8 8 8
6 6 6 8 8 8 8 8
6 7 7 8 8 8 8 8
6 7 8 8 8 8 8 8
7 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
2. Quantisierungstabelle 15% gute Qualität
Multiplikator Matrix
SAL-Matrix
SAL-Effektiv
01 02 02 04 08 16 16 16
02 04 04 16 16 16 16 16
04 08 08 16 16 16 16 16
04 08 16 16 16 16 16 16
08 16 16 16 16 16 16 16
16 16 16 16 16 16 16 16
16 16 16 16 16 16 16 16
16 16 16 16 16 16 16 16
0 1 1 2 3 4 4 4
1 2 2 4 4 4 4 4
2 3 3 4 4 4 4 4
2 3 4 4 4 4 4 4
3 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4
5 6 6 7 8 9 9 9
6 7 7 9 9 9 9 9
7 8 8 9 9 9 9 9
7 8 9 9 9 9 9 9
8 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
3. Quantisierungstabelle 40%  ausreichende Qualität
Multiplikator Matrix
SAL-Matrix
SAL-Effektiv
01 08 08 08 16 16 32 32
08 08 08 32 32 32 32 32
08 16 16 32 32 32 32 32
08 16 32 32 32 32 32 32
16 32 32 32 32 32 32 32
32 32 32 32 32 32 32 32
32 32 32 32 32 32 32 32
32 32 32 32 32 32 32 32
0 3 3 3 4 4 5 5
3 3 3 5 5 5 5 5
3 4 4 5 5 5 5 5
3 4 5 5 5 5 5 5
4 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 8 8 8 9 9 A A
8 8 A A A A A A
8 9 9 A A A A A
8 9 A A A A A A
9 A A A A A A A
A A A A A A A A
A A A A A A A A
A A A A A A A A
4. Quantisierungstabelle 60% schlechte Qualität
Multiplikator Matrix
SAL-Matrix
SAL-Effektiv
01 16 16 16 32 32 64 64
16 16 16 64 64 64 64 64
16 32 32 64 64 64 64 64
16 32 64 64 64 64 64 64
32 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
0 4 4 4 5 5 6 6
4 4 4 6 6 6 6 6
4 4 4 6 6 6 6 6
4 5 6 6 6 6 6 6
5 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
5 9 9 9 A A B B
9 9 9 B B B B B
9 A A B B B B B
9 A B B B B B B
A B B B B B B B
B B B B B B B B
B B B B B B B B
B B B B B B B B

2.6 Aus einer 8 * 8 F-Matrix wird eine 8 * 8 Y bzw U oder V– Matrix

Die Berechnung der Y-Matrix aus der Frequenzmatrix geschieht durch die inverse Cosinustransformation. Dies ist eine sehr umständliche Formel und erfordert eine Menge Berechnungszeit. Es kann aus der Formel durch genaues Hinsehen eine Matrizenmultiplikation hergeleitet werden, die das Ganze beschleunigt und übersichtlich macht. Die Multiplikation sieht wie folgt aus:
Y = DCT' * F * DCT

Die Punkte der 8 * 8 F-Matrix, werden durch eine nur zweifache Matrizenmultiplikation berechnet. Es werden dazu 2 Koeffizientenmatrizen erstellt, die wie folgt berechnet werden (allgemeine Formel für N * N-Matrix).
DCT i,j = 1/N; wenn i (die Zeile) =0, sonst
DCT i,j = 1/N * cos[(2j+1)* i * PI / 2N], wenn i>0;
in diesem Fall ist N=8, dh: i, j "laufen" von 0..7
 
Dies ist ein Ausschnitt der DCT
DCT =   
.
 —    
—
 .
|
 +0.3535 +0.3535 ..... +0.3535 |
|
 +0.4904 +0.4157 -0.4904 |
|
:
:
:
:
 |
|
 +0.0975 -0.2777 ..... -0.0975 |
'
 —    
—
 ´
 

2.6.1 Das Pascalprogramm mit FPU- Lösung

Die Multiplikationen der Matrix habe ich in einer Assemblerlösung vollzogen, da eine FPU-Lösung viel zu langsam wäre, obwohl das schön kurz ist. Ich habe das Programm zum besseren Verständnis als Pascalprogramm aufgelistet.

var d:array[0..7,0..7] of real;  --- Die DCT – Matrix ---
    t:array[0..7,0..7] of real;  --- Die DCT'- Matrix ---
    Y:array[0..7,0..7] of byte;  --- Die Y   – Matrix ---
    e:array[0..7,0..7] of real;  --- ein zwischen Ergebnis
    f:array[0..7,0..7] of real;  --- Das Endergebnis
    1s,lz,tm:integer;            --- Ein paar Laufvariablen
begin
 for 1s:=0 to 7 do d[0][ls]:=1/sqrt(8);                --   0. Zeile der DCT
 for 1z:=1 to 7 do for 1s:=0 to 7 do                   -- 1-7. Zeile der DCT
   d[lz][ls]:=sqrt(2/8)*cos((2*ls+1)*lz*pi/(2*8));     -- Die Formel
 for 1z:=0 to 7 do for 1s:=0 to 7 do                   -- Die Transponierte
   t[lz][ls]:=d[ls][lz];                               -- Die DCT'
 for 1z: =0 to 7 do                                    -- Berechnung
   for 1s:=0 to 7 do                                   -- von DCT' * F
     for tm:=0 to 7 do                                 -- ZwischenErgebnis
       e[lz][ls]:=e[lz][ls]+t[lz][tm]*(f[tm][ls]);     -- in E-Matrix
 for 1z:=0 to 7 do                                     -- Berechnung
   for 1s:=0 to 7 do                                   -- (DCT' * F) * DCT
     for trn:=0 to 7 do                                -- FertigErgebnis in
       f[lz][ls]:=f[lz][ls]+e[lz)[tm]*d[tm][ls];       -- später Scale 128
end.


In meinem Assemblerprogramm wird mit Integerarithmetik die FPU emuliert die Realzahlen z.B. 1/8 = 0.35355 wurde mit Vielfachen von 2 multipliziet. so z.B. mit 16384, dh. 1/8 —> 5792. Bei einer zweifachen Matrixmultiplikation habe ich eine maximale Abweichung von ±0.75 erreicht und mit einer 92%-igen Sicherheit sind die Werte im richtigen Bereich gerundet.

2.6.2 Die Optimierung der Multiplikation

Aus Geschwindigkeitsgründen wird die Multiplikation noch einmal optimiert: Der Prozessor benötigt für eine Multiplikation recht viel Zeit. Bsp. ein MOV, ADD, SUB,...  benötigt einen Taktzyklus. Eine Multiplikation hingegen benötigt 26 Zyklen.
Weiterhin möchte ich noch folgendes in Erinnerung bringen. Ein Beispiel für  zeilen- bzw. spaltenorientierte Berechnung:

1. Beispiel. E:= (DCT' * F) spaltenorientierte Ermittlungsreihenfolge
E00
E01
. .
E07
E10
E11
. .
E17
:
:
. : .
:
E70
E71
. .
E77
 		  : = 
D00
D01
. .
D07
D10
D11
. .
D17
:
:
. : .
:
D70
D71
. .
D77
 
 *
 
F00
F01
. .
F07
F10
F11
. .
F17
:
:
. : .
:
F70
F71
. .
F77
 
1. E00:= (DCT'00 * F00) + (DCT'01 * F10) + ... + (DCT'07 * F70)
2. E01:= (DCT'00 * F01) + (DCT'01 * F11) + ... + (DCT'07 * F71)  


2. Beispiel.  E:= (DCT' * F) zeilenorientierte Ermittlungsreihenfolge
E00
E01
. .
E07
E10
E11
. .
E17
:
:
. : .
:
E70
E71
. .
E77
 		  : = 
D00
D01
. .
D07
D10
D11
. .
D17
:
:
. : .
:
D70
D71
. .
D77
 
 *
 
F00
F01
. .
F07
F10
F11
. .
F17
:
:
. : .
:
F70
F71
. .
F77
 
1. E00:= (DCT'00 * F00) + (DCT'01 * F10) + ... + (DCT'07 * F70)
2. E10:= (DCT'10 * F00) + (DCT'11 * F10) + ... + (DCT'17 * F70)  

Das Ergebnis der E- Matrix wird von der "Orientierung" natürlich nicht beeinflußt. Die Berechnung kann dadurch nur vereinfacht werden. Das geschieht folgendermaßen. DCT und DCT' verändern sich nie (Konstanten), nur die Elemente der F- Matrix. Multipliziere ich DCT' * F in einer zeilenorientierten Reihenfolge, dann kann ich feste Multiplikatoren bei der Berechnung der Matrix E einsetzen (Jedes Element der  DCT' wird  bei der Bestimmung einer Spalte von E benötigt). Gleiches geschieht, wenn ich Y:= E * DCT in spaltenorientierter Reihenfolge berechne. Nun kann ich mir die Multiplikatoren von DCT und DCT' genauer ansehen. Dabei stelle ich fest, daß es insgesamt 512 Multiplikationen je Matrizenoperation gibt. Davon können aber nur 64 mit unterschiedlichen Multiplikatoren sein. DCT und die DCT' sind mit gleichen Elementen bestückt. Es gibt in DCT bzw. in der DCT' genau 14 unterschiedliche Multiplikatoren, die  aus 7 verschiedenen Zahlen jeweils 7 positiven und 7 negativen zusammengesetz sind.
Nun bin ich am Ende mit theoretischen Überlegungen. Nun wird ausgezählt. Welches der 8 Elemente (entweder Spalten aus der F-Matrix oder Zeilenelemente aus der E-Matrix) wird mit welchem der DCT bzw. DCT' multipliziert und vor allem wie oft?
Die Multiplikatoren der folgenden Tabelle sind integernormierte Zahlen der DCT bzw. DCT'.(DCT* 2^15)
Multiplikator
X0
X1
X2
X3
X4
X5
X6
X7
Sum
16069 
-
1
-
1
-
1
-
1
4
-16069 
-
1
-
1
-
1
-
1
4
15137 
-
-
2
-
-
-
2
-
4
-15137 
-
-
2
-
-
-
2
-
4
13623 
-
1
-
1
-
1
-
1
4
-13623 
-
1
-
1
-
1
-
1
4
11585 
8
-
-
-
4
-
-
-
12
-11585 
-
-
-
-
4
-
-
-
4
9102 
-
1
-
1
-
1
-
1
4
-9102 
-
1
-
1
-
1
-
1
4
6270 
-
-
2
-
-
-
2
-
4
-6270 
-
-
2
-
-
-
2
-
4
3196 
-
1
-
1
-
1
-
1
4
-3196 
-
1
-
1
-
1
-
1
4
Summe
8
8
8
8
8
8
8
8
64
Es treten gerade 43 verschiedene Multiplikationen von 64 auf. Diese Multiplikatoren können auf 22 Verschiedene herabgesetzt werden, wenn ich das Vorzeichen nicht mitbetrachte. Produkte mit einem negativem Multiplikator werden vom enstehenden Element subtrahieren statt addiert. Bei der optimierten Matrizenmultiplikation werden bei jeder neuanfangenden Zeile bzw. Spalte die 22 verschiedenen Produkte berechnet.Die Ergebnisse werden in Variablen abgelegt. Nun werden diese fertigen
Produkte in der weitere Berechnung eingesetzt (addiert und subtrahiert). Ich brauche statt 64 nur noch 22 Multiplikationen zu berechnen. Das bedeutet einen fast dreifachen Zeitgewinn.

Die Optimierung mit Multiplikationstabellen, in denen feste Ergebnisse stehen, wäre noch möglich. Doch eine Anwendung wäre sehr speicherintensiv. Sieben Multiplikationstabellen mit 2048 Integerzahlen. dh.  7*4kb sind 28Kb je Multiplikationstabelle. Konstanten in dieser Größenordnung sind unter der 16bit-Programmierung sehr schlecht anzuwenden. Die Beschleunigung würde etwa 33%. betragen. Momentan liegt die Geschwindigkeit auf ein 486DX/33 bei 600ms, bei einem 486DX-2/80 bei 220ms (gemessen mit einem 24bit-Bild 384x384 Pixel). Weitere denkbare Zeiteinsparungen würden vielleicht nicht gehen, da eine DX2-CPU einen MiSS im internen Cache hart mit Zeitverlusten bestraft. Es hat sich allgemein die Kleinprogrammstrategie besser bewährt, als übermäßige Schleifenausprogrammierungen mit viel Quell- und Binärcode.

2.7 Der 7.Schritt YUV —> RGB

Hier möchte ich nicht allzuviel schreiben. Die Umwandlung geschieht äquivalent zur RGB —> YUV-Umwandlung. Der Assemblertext sollte hier Aufschluß geben. Die einzigste Veränderung ist eine Optimierung. Jegliche Multiplikationen wurden durch Multiplikationstabellen mit MOV ersetzt. Hier hat es sich angeboten, da nicht allzuviele Eingangswerte vorhanden sind (nur 256 verschiedene).
Blättern:
Mein Format Codieren     Dateien und Proceduren
Praktikum