1.19 ΑΛΓΟΡΙΘΜΟΣ ΣΥΜΠΙΕΣΗΣ "PACK BITS" 





Σε  κάθε  αρχείο TIFF  που  υπάρχει  εικόνα συμπιεσμένη  με  τον

αλγόριθμο αυτό,  πρέπει η  ετικέτα "ΣΥΜΠΙΕΣΗ ΔΕΔΟΜΕΝΩΝ"  να έχει

την τιμή 32773  ($8005). Ο  αλγόριθμος αυτός είναι  από τους πιο

απλούς  που υπάρχουν.  Αυτό  όμως, δεν  σημαίνει  ότι δεν  είναι

αποτελεσματικός.  Ο αλγόριθμος  αυτός χρησιμοποιείται  κυρίως σε

μικρές εικόνες  (εικόνες δύο  χρωμάτων, εικόνες  από σχεδιαστικά

προγράμματα κ.λ.π).  Υπάρχουν αρκετές παραλλαγές  του αλγόριθμου

αυτού,  όμως εμείς  θα  ασχοληθούμε μόνο  με  την παραλλαγή  που

χρησιμοποιείται συχνότερα.





Η  επιτυχία   του  αλγόριθμου  αυτού  βασίζεται   στο  ότι  στις

περισσότερες γραμμές μίας  εικόνας υπάρχουν συνεχόμενες περιοχές

με το ίδιο  BYTE. Αρα (κατά την  συμπίεση, αποσυμπίεση) θεωρούμε

ότι τα δεδομένα της εικόνας  είναι BYTE ανεξάρτητα από την μορφή

της εικόνας.  Για να  αποσυμπιέσουμε μία εικόνα,  συμπιεσμένη με

τον αλγόριθμο PackBits, εκτελούμε τα εξής βήματα:





ΒΗΜΑ 1 : Διαβάζουμε  το επόμενο BYTE δεδομένων (της συμπιεσμένης

         εικόνας)  και  δίνουμε  στη  μεταβλητή Ν  την τιμή  του

         BYTE.





ΒΗΜΑ 2 : Αν 0 <= Ν <= 127, τότε διαβάζουμε τα  επόμενα Ν+1  BYTE

         από το αρχείο και τα θεωρούμε δεδομένα της εικόνας.





ΒΗΜΑ 3 : Αν -127 <= Ν <= -1, τότε  διαβάζουμε  ΕΝΑ  BYTE  από το

         αρχείο και θεωρούμε  σαν δεδομένα της εικόνας μία ομάδα

         από  -Ν+1  συνεχόμενα  όμοια  BYTE   με  την  τιμή  που

         διαβάσαμε.





ΒΗΜΑ 4 : Αν Ν = 128 τότε δεν κάνουμε τίποτα.





ΒΗΜΑ 5 : Επαναλαμβάνουμε  τα  βήματα 1,  2,  3  και 4  έως ότου

         διαβάσουμε όλα τα δεδομένα της εικόνας.





Ακολουθεί μία υπορουτίνα σε  Pascal, που αποσυμπιέζει μία εικόνα

συμπιεσμένη με τον αλγόριθμο PackBits.








procedure show_mono_image_compr_8005

        (image_start :word ; image_length,image_width : word);

var

  image_data : shortint;  { EMΦΑΝΙΖΕΙ ΕΙΚΟΝΕΣ ΜΟΝΟΧΡΩΜΕΣ  }

  i,k,m,j,l  : word;  { ΠΟΥ ΕΧΟΥΝ ΣΥΜΠΙΕΣΤΗ ΜΕ ΤΗΝ ΜΕΘΟΔΟ 8005 }

  data       : byte;

  d1,d2      : char;

begin

  graphdriver := cga ; graphmode := cgahi;

  initgraph(graphdriver,graphmode,'');

  seek(tiff_file,image_start);

  for i := 1 to (image_length ) do

  begin

  k := 0;

    repeat

      read(tiff_file,data);

      image_data := data ;inc(counter_byte);

      if (image_data >= 0) and (image_data <= 127) then

      begin

        for m := 1 to image_data + 1 do

        begin

          read(tiff_file,data);inc(counter_byte);

          inc(k);show_mono_byte(data,i,k);

        end;

      end

        else if (image_data <= -1) and (image_data >= -127) then

      begin

        read(tiff_file,data);inc(counter_byte);

        for m := 1 to (-(image_data)+1) do

        begin

          inc(k);show_mono_byte(data,i,k);

        end;

      end;

    until k = (image_width + 7) div 8;

  end;

  xar := readkey;closegraph;

end;





Η  πιο πάνω  ρουτίνα αποσυμπιέζει  και στέλνει  για εμφάνιση  τα

δεδομένα μίας μονόχρωμης εικόνας, η οποία έχει συμπιεστεί με τον

αλγόριθμο   PackBits.  Στις   πρώτες  γραμμές   της  υπορουτίνας

μπαίνουμε σε κατάσταση γραφικών. Πρέπει να σημειώσουμε ακόμα ότι

το  αρχείο tiff_file  έχει προετοιμαστεί  για ανάγνωση  από άλλη

υπορουτίνα.  Η  υπορουτίνα  Show_mono_byte  υπάρχει  σε  επόμενη

ενότητα   του κειμένου  και εμφανίζει  8 PIXEL   μίας μονόχρωμης

εικόνας στην κατάλληλη θέση.





Από  τα πιο  πάνω γίνεται  φανερό ότι  ακόμη και  στην χειρότερη

περίπτωση (όταν δέν έχουμε συμπίεση) ο αλγόριθμος προσθέτει μόνο

1 BYTE παραπάνω για κάθε 128 BYTE δεδομένων.





Οταν φτιάχνουμε  εφαρμογές που  υποστηρίζουν αυτό  τον αλγόριθμο

πρέπει να έχουμε υπόψη μας τους πιο κάτω κανόνες:





- Κάθε γραμμή εικόνας συμπιέζεται ξεχωριστά. 


- Το  πλήθος των  δεδομένων   που πρέπει να διαβάσουμε  για κάθε

  γραμμή εικόνας, δίνεται από   τον τύπο  ("ΕΥΡΟΣ ΕΙΚΟΝΑΣ"+7)/8.

  Αυτό ισχύει για μονόχρωμες εικόνες. 


- Εάν  η  ομάδα των  BYTE  που  θέλουμε να  κωδικοποιήσουμε έχει

  μήκος περισσότερο από 128, τότε  χωρίζουμε την ομάδα σε  δύο ή

  περισσότερες ανεξάρτητες ομάδες.





Υπορουτίνες  που  θα  συμπιέζουν  την εικόνα  με  τον  πιο  πάνω

αλγόριθμο  είναι  εύκολο να  γίνουν.  Ακολουθεί  μια ρουτίνα  σε

PASCAL, η οποία αναλαμβάνει να  συμπιέσει και να σώσει σε αρχείο

τα  δεδομένα  εικόνας  πού  βρίσκονται στην  μνήμη  ενός  IBM  ή

συμβατού υπολογιστή.











procedure save_in_pack_bits 

                  ( seg , offs , x_length , y_length : word;    

                    file_name                        : str_80;

                    cgacard                          : boolean  );

{

-----------------------------------------------------------------------------

   This procedure compresses an image with the pack bits algorithm and sends

  the output to a file ( The output appends the file ). The input  variables

  are the segment and the offset address of the image data  in  the  memory,

  the x, y length of the image ( the x  length  in BYTE  ), the  output file

  and the boolean variable cgacard, if this variable is true the image  must

  be  an cga screen ( interlace  mode  with  192  bytes gap between the two

  blocks. The file in whiche we send the output, must exist and must be closed  

----------------------------------------------------------------------------

}

var

 pointer1,pointer2,i          : word;

 counter,data                 : shortint;

 output                       : file of shortint;

 line_counter,row_counter     : word;

 exit                         : boolean;

 total_counter                : word;




begin

  assign(output , File_name );reset(output);seek(output , filesize(output));

  pointer1 := offs;pointer2 := offs;exit:=false;

  counter  := 0; line_counter := 0;row_counter:=0;

  total_counter :=0;

  repeat

    while (mem[seg:pointer2] <> mem[seg:pointer2+1])

          and (counter<128)

          and (line_counter < x_length)

          and not (total_counter >= x_length * y_length) do

      begin

        inc(counter);inc(pointer2);inc(line_counter);

      end;

    if pointer1 <> pointer2 then

    begin

      data := counter-1;

      write(output,data);

      for i := 0 to counter-1 do

      begin

        data := mem[seg:pointer1+i];

        write(output,data);

        inc(total_counter);

      end;










      if line_counter = x_length then

      begin

        line_counter := 0;inc(row_counter);

        if pointer2<>offs+(row_counter*x_length) then

                                       pointer2:=(row_counter*x_length)+offs;

        if ( row_counter >= 100 )

           and cgacard then pointer2 :=pointer2+193;

      end;

    end;

    counter := 0; pointer1 := pointer2;

    if mem[ seg : pointer2 ] = mem[seg:pointer2+1] then

    begin

      counter :=1;inc(pointer2);inc(line_counter);

    end;

    while (mem[ seg : pointer2-1 ] = mem[seg:pointer2])

           and (counter<128)

           and (line_counter < x_length+1) do

      begin

        inc(counter);inc(pointer2);inc(line_counter);

      end;


    if pointer1 <> pointer2 then

     begin

      if (line_counter-1= x_length) then dec(counter);

      data := -counter+1;

      total_counter := total_counter + counter;

      write(output,data);

      data := mem[seg : pointer1];

      write(output,data);

      if line_counter >= x_length then

      begin

        line_counter := 0;inc(row_counter);

        if pointer2<>offs+(row_counter*x_length) then

                                       pointer2:=(row_counter*x_length)+offs;

        if ( row_counter >= 100 )

            and ( cgacard = true )  then pointer2 :=pointer2+193;

      end;

    end;

    counter := 0; pointer1 := pointer2;

  until (total_counter >= x_length * y_length);

  close(output);

end; { save in pack bits }