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".