1.21 ΑΛΓΟΡΙΘΜΟΣ ΣΥΜΠΙΕΣΗΣ "CCITT GROUP 3"


Ο αλγόριθμος αυτός είναι μία τροποποιημένη έκδοση του αντίστoιχου αλγόριθμου που χρησιμοποιείται στα FAX. Ο αλγόριθμος αυτός ονομάζεται και αλγόριθμος "RUN LENGTH". Οταν χρησιμοποιείται αυτή η μέθοδος συμπίεσης, η ετικέτα "ΣΥΜΠΙΕΣΗ ΔΕΔΟΜΕΝΩΝ" πρέπει να έχει τιμή "2". Χρειάζεται προσοχή όταν χρησιμοποιούμε τον αλγόριθμο αυτό, γιατί υπάρχουν αρκετοί άλλοι αλγόριθμοι που του μοιάζουν ( GROUP 3 απλός, GROUP 4 κλπ). Σκοπός του αλγόριθμου αυτού είναι να αντικαταστήσει ομάδες από συνεχόμενα ΒΙΤ, με τιμή "0" ή "1", με κωδικούς (σειρές από BIT) που θα έχουν μικρότερο μήκος. Ο αλγόριθμος αυτός χρησιμοποιείται κυρίως για την συμπίεση μονόχρωμων εικόνων. Στις εικόνες με αποχρώσεις του γκρι και στις έγχρωμες εικόνες, ο πιο πάνω αλγόριθμος δεν έχει μεγάλη επιτυχία και η χρήση του αποφεύγεται.

Η συμπίεση με τον αλγόριθμο αυτό γίνεται ως εξής. Κάθε σειρά της εικόνας αντικαθίσταται από μία σειρά από κωδικούς μεταβλητού μήκους. Ο κάθε κωδικός αντιπροσωπεύει μία συνεχή σείρα από BIT με την ίδια τιμή ("0" ή "1"). Ο πρώτος κωδικός που διαβάζουμε αναφέρεται πάντα σε BIT με τιμή "1", ο δεύτερος σε BIT με τιμή "0", ο τρίτος σε BIT με τιμή "1" κ.ο.κ. Για να διατηρήσουμε αυτήν τη σείρα και για λόγους συμβατότητας, αν μία εικόνα αρχίζει με BIT που έχει τιμή "0", τότε τά δεδομένα της συμπιεσμένης γραμμής θα ξεκινούν από τον κωδικό που αντιπροσωπεύει μηδέν αριθμό από συνεχόμενα BIT με τιμή "1".

Στην πραγματικότητα, κάθε σειρά από BIT με την ίδια τιμή, ανάλογα με το μήκος της, αντικαθίσταται από ένα, δύο ή και περισσότερους κωδικούς. Εχουμε δύο ειδών κωδικούς, τους κωδικούς Make Up και τους κωδικούς τερματισμού (TERMINATION CODES). Κάθε σείρα από BIT με την ίδια τιμή, αντικαθίσταται από κανέναν, έναν ή περισσότερους κωδικούς Make Up και ΕΝΑ κωδικό τερματισμού. Σειρές από BIT, με την ίδια τιμή, που έχουν μήκος έως 63 BIT αντικαθίστανται μόνο με τον κωδικό τερματισμού (κατάλογοι με τους κώδικες υπάρχουν στη συνέχεια του κειμένου).

Σειρές από BIT με την ίδια τιμή και με μήκος από 64 έως 2623 BIT κωδικοποιούνται ως εξής. Πρώτα έχουμε έναν κωδικό Make Up, που αντικαθιστά το μέγιστο δυνατό αριθμό BIT (χωρίς να ξεπερνά το μήκος της σειράς) και ακολουθεί ένας κωδικός τερματισμού που αντικαθιστά τα υπόλοιπα BIT. Για παράδειγμα, έαν θέλουμε να κωδικοποιήσουμε μία σειρά από 200 συνεχόμενα BIT με τιμή "1", η κωδικοποίηση θα γίνει ως εξής: Ο κωδικός Make Up, που αντικαθιστά το μεγαλύτερο αριθμό από BIT, είναι ο "010111" και αντικαθιστά 192 BIT. Ο κωδικός τερματισμού πρέπει να αντικαταστήσει 200 - 192 = 8 BIT. Αρα ο κωδικός τερματισμού θα είναι ο "10011". Αρα η σειρά με τα 200 συνεχόμενα BIT με τιμή "1" θα αντικατασταθεί από τη σειρά "01011110011".

Σειρές από BIT με μήκος μεγαλύτερο ή ίσο με 2624 αντικαθίστανται από δύο ή περισσότερους κωδικόυς Make Up και έναν κωδικό τερματισμού. Ολοι οι κωδικοί Make Up, εκτός από τον τελευταίο, αντικαθιστούν το μεγαλύτερο δυνατό αριθμό από BIT (δηλ. αντικαθιστούν 2560 BIT με τον κωδικό "000000011111"). Για παράδειγμα, εάν θέλουμε να συμπιέσουμε μία σειρά από 3000 συνεχόμενα BIT με τιμή "0", θα χρησιμοποιήσουμε τους κωδικούς "000000011111" (2560) + "00110111" (384) + "01011001" (56).

Η συμπίεση των εικόνων γίνεται πάντα ξεχωριστά για κάθε γραμμή της εικόνας. Αν κατά την αποσυμπίεση τα δεδομένα που διαβάζουμε για μία γραμμή είναι περισσότερα από ότι πρέπει, τότε Θεωρούμε ότι έχει γίνει λάθος που δεν μπορεί να αποκατασταθεί. Πρέπει ακόμα να προσέχουμε όταν χρησιμοποιούμε BIT συμπλήρωσης, γιατί τα BIT αυτά δεν πρέπει να συμπιεστούν. Για παράδειγμα, αν η γραμμή μίας εικόνας περιγράφεται από 10 BIT και χρησιμοποιούμε 2 BYTE για την αποθήκευση τους, τότε συμπιέζονται μόνο τα 10 BIT και όχι τα υπόλοιπα 6 BIT συμπλήρωσης. Αν τα συμπιεσμένα δεδομένα μίας γραμμής δεν τελειώνουν στα όρια ενός BYTE, τότε τα δεδομένα της επόμενης γραμμής θα ξεκινούν από την αρχή του επόμενου BYTE. Ακόμα πρέπει να προσθέσουμε, ότι στα TIFF δεν χρησιμοποιούνται χαρακτήρες EOL (τέλος γραμμής), σε αντίθεση με ότι συμβαίνει στα αρχεία FAX. Για μεγαλύτερη ταχύτητα, κατά την αποσυμπίεση συνίσταται ο χωρισμός της εικόνας σε λουρίδες.

**ΠΙΝΑΚΑΣ ΚΩΔΙΚΩΝ ΤΕΡΜΑΤΙΣΜΟΥ**

ΚΩΔΙΚΑΣ ΜΕΓΕΘΟΣ ΣΕΙΡΑΣ ΑΠΟ
ΤΕΡΜΑΤΙΣΜΟΥ ΒΙΤ ΜΕ ΤΙΜΗ "1"

00110101 0
000111 1
0111 2
1000 3
1011 4
1100 5
1110 6
1111 7
10011 8
10100 9
00111 10
01000 11
001000 12
000011 13
110100 14
110101 15
101010 16
101011 17
0100111 18
0001100 19
0001000 20
0010111 21
0000011 22
0000100 23
0101000 24
0101011 25
0010011 26
0100100 27
0011000 28
00000010 29
00000011 30
00011010 31
00011011 32
00010010 33
00010011 34
00010100 35
00010101 36
00010110 37
00010111 38
00101000 39
00101001 40
00101010 41
00101011 42
00101100 43
00101101 44
00000100 45
00000101 46
00001010 47
00001011 48
01010010 49
01010011 50
01010100 51
01010101 52
00100100 53
00100101 54
01011000 55
01011001 56
01011010 57
01011011 58
01001010 59
01001011 60
00110010 61
00110011 62
00110100 63

ΚΩΔΙΚΑΣ ΜΕΓΕΘΟΣ ΣΕΙΡΑΣ ΑΠΟ
ΤΕΡΜΑΤΙΣΜΟΥ ΒΙΤ ΜΕ ΤΙΜΗ "0"

0000110111 0
010 1
11 2
10 3
011 4
0011 5
0010 6
00011 7
000101 8
000100 9
0000100 10
0000101 11
0000111 12
00000100 13
00000111 14
000011000 15
0000010111 16
0000011000 17
0000001000 18
00001100111 19
00001101000 20
00001101100 21
00000110111 22
00000101000 23
00000010111 24
00000011000 25
000011001010 26
000011001011 27
000011001100 28
000011001101 29
000001101000 30
000001101001 31
000001101010 32
000001101011 33
000011010010 34
000011010011 35
000011010100 36
000011010101 37
000011010110 38
000011010111 39
000001101100 40
000001101101 41
000011011010 42
000011011011 43
000001010100 44
000001010101 45
000001010110 46
000001010111 47
000001100100 48
000001100101 49
000001010010 50
000001010011 51
000000100100 52
000000110111 53
000000111000 54
000000100111 55
000000101000 56
000001011000 57
000001011001 58
000000101011 59
000000101100 60
000001011010 61
000001100110 62
000001100111 63

**ΠΙΝΑΚΑΣ ΚΩΔΙΚΩΝ MAKE UP**

ΚΩΔΙΚΑΣ ΜΕΓΕΘΟΣ ΣΕΙΡΑΣ ΑΠΟ
MAKE UP BIT ΜΕ ΤΙΜΗ "1"

11011 64
10010 128
010111 192
0110111 256
00110110 320
00110111 384
01100100 448
01100101 512
01101000 576
01100111 640
011001100 704
011001101 768
011010010 832
011010011 896
011010100 960
011010101 1024
011010110 1088
011010111 1152
011011000 1216
011011001 1280
011011010 1344
011011011 1408
010011000 1472
010011001 1536
010011010 1600
011000 1664
010011011 1728

ΚΩΔΙΚΑΣ ΜΕΓΕΘΟΣ ΣΕΙΡΑΣ ΑΠΟ
MAKE UP BIT ME TIMH "0"

0000001111 64
000011001000 128
000011001001 192
000001011011 256
000000110011 320
000000110100 384
000000110101 448
0000001101100 512
0000001101101 576
0000001001010 640
0000001001011 704
0000001001100 768
0000001001101 832
0000001110010 896
0000001110011 960
0000001110100 1024
0000001110101 1088
0000001110110 1152
0000001110111 1216
0000001010010 1280
0000001010011 1344
0000001010100 1408
0000001010101 1472
0000001011010 1536
0000001011011 1600
0000001100100 1664
0000001100101 1728

**ΠΙΝΑΚΑΣ ΕΠΙΠΛΕΩΝ ΚΩΔΙΚΩΝ MAKE UP**

ΚΩΔΙΚΑΣ ΜΕΓΕΘΟΣ ΣΕΙΡΑΣ ΑΠΟ
MAKE UP ΟΜΟΙΑ ΒΙΤ

00000001000 1792
00000001100 1856
00000001101 1920
000000010010 1984
000000010011 2048
000000010100 2112
000000010101 2176
000000010110 2240
000000010111 2304
000000011100 2368
000000011101 2432
000000011110 2496
000000011111 2560

Πρέπει να σημειώσουμε ότι οι επιπλέον κωδικοί Make Up είναι ίδιοι, ανεξάρτητα από το αν η σειρά από όμοια ΒΙΤ αποτελείται από ΒΙΤ με τιμή "0" ή "1".

Ο κωδικός EOL είναι ο "000000000001".