SEMINARSKA NALOGA pri RPK

 

4.16 Raztros črnobelih odtenkov
 Mitja Laharnar 3.l. - KGS
23. avgust 1998
 
 
ABSTRACT
 
Following program filters PPM format (ASCII form) color picture or PGM format (ASCII form) grey scale picture by using ERROR DIFFUSION method and FLOYD and STEINBERG algorithm. Color depth in color picture can be decreased to 2, 5, 8, 27 or 64 basic colors. Color depth in grey scale picture is decreased to 2 colors. This program is applicable for preparing pictures for printing  on  two colors  printers (black and white printers) or for printing on four colors  printers (usual color ink-jet printers).
 
 
 

KAZALO:
 

   

 

 

1. DEFINICIJA NALOGE
 

Z metodo difuzije napake (error diffusion) in uporabo Floyd - Steinberg algoritma lahko na črnobelih tiskalnikih in zaslonih ustvarimo učinek sivin, tako da variramo gostoto pojavljanja črnih pik. Izdelati je potrebno program, ki prebere rastrsko datoteko s sivimi odtenki in z metodo difuzije napake ustvari črnobelo sliko enake ločljivosti.

 
 

2. TEORETIČNE OSNOVE
 

2.1 ERROR DIFFUSION

Metoda error diffusion razprši in prišteje napako trenutnega piksla (ali dela piksla: R ali G ali B) na okoliške desne in spodnje piksle, po določenem algoritmu (error filter). Prvo se primerja velikost svetlosti trenutnega piksela IN(j) z izbranim pragom velikosti svetlosti (treshold). Če je piksel večji od praga dobi vrednost maksimuma velikosti svetlosti (OUT(j)=255), če pa je piksel manjši od praga pa dobi vrednost minimuma velikosti svetlosti (OUT(j)=0). Napaka piksla ali dela piksla je razlika med velikostjo svetlosti trenutnega piksla IN(j) in max. oziroma min. velikostjo svetlosti OUT(j). Napako pomnožimo z Floyd in Steinbergovim algoritmom ter prištejemo okoliškemu pikslu. To naredimo za vse okoliške piksle, ki so okoli trenutnega piksla IN(j).

Blok shema načina delovanja metode error diffusion je prikazana na Sliki 1.

 

Slika 1. Blok shema metode error diffusion

 

Prvi algoritem (error filter) za metodo difuzije (razpršitve) napake sta predstavila Floyd in Steinberg leta 1975 in se glasi:
 

 
· 
7/16
3/16
5/16
1/16
 

Kjer "· " predstavlja napako trenutnega piksla in se le ta pomnoži z parametri napisanimi v tabeli.

Algoritem ponovimo za vse piksle neke slike.

Algoritem (error filter), ki porazdeli napako trenutnega piksla na okoliške mora zadostiti naslednjemu pogoju:

Kjer so a , b , g , d parametri algoritma (npr. za Floyd in Steinberg: a =7/16, b =1/16, g =5/16, d =3/16)

 

 

2.2 Grafična formata PPM in PGM

    PPM - Portable PixMap
    PGM - Portable GreyMap

Oba grafična formata imata zelo enostavno zgradbo. Vsak se začne z glavo kateri sledijo podatki o pikslih. Glava je vedno napisana v obliki ASCII, podatki o pikslih pa so lahko napisani v ASCII ali binarni obliki in so ločeni z praznimi prostori. Rastrska slika se začne sestavljati v zgornjem levem kotu in se nadaljuje po vrstnem redu Slovenskega branja.

 
ASCII oblika formata PPM

Primer rastrske slike:

Slika 2. Primer rastrske slike formata PPM v obliki ASCII

 
Datoteka zgornje slike je naslednja:

P3
# Created by Paint Shop Pro
5 4
255
201 169 128 187 171 122 134 142 119 78 105 116 21 67 82 194 177 151 189 177 117
159 156 113 114 118 119 41 41 65 170 167 152 181 172 103 181 167 104 158 136 125
93 80 90 146 154 143 174 168 92 200 178 103 193 155 136 132 138 124
 
Prve štiri vrstice datoteke predstavljajo glavo grafičnega formata PPM. Prva vrstica ima magični znak P3, ki je potreben za razpoznavo tipa datoteke. P3 pomeni da je to datoteka formata PPM v obliki ASCII. V drugi vrstici je označba 5 točk široke slike in 4 točke visoke slike. Tretja vrstica vsebuje število 255, ki predstavlja maksimalno velikost svetlosti in je v razponu od 0 do 255. Vrednost 0 pomeni, da je barva izklopljena, vrednost 255 pa pomeni, da je barva maksimalno prisotna. Glavi datoteke sledijo podatki o pikslih. Ker je format PPM namenjen za barvne slike vsebuje vsaka točka (piksel) troje števil. Prvo število je svetlost rdeče, drugo je svetlost zelene, tretje pa je svetlost modre (RGB). Črna barva ima vrednost (0 0 0 ), bela pa (255 255 255).

   
ASCII oblika formata PGM

Primer rastrske slike:

Slika 3. Primer rastrske slike formata PGM v obliki ASCII

 
Datoteka zgornje slike je naslednja:

P2
# Created by Paint Shop Pro
5 4
255
174 170 137 98 54 179 174 152 116 43 166 167 164 141 85 150 161 176 164
134
 
Prve štiri vrstice datoteke predstavljajo glavo grafičnega formata PPM. Prva vrstica ima magični znak P2, ki je potreben za razpoznavo tipa datoteke. P2 pomeni da je to datoteka formata PGM v obliki ASCII. V drugi vrstici je označba 5 točk široke slike in 4 točke visoke slike. Tretja vrstica vsebuje število 255, ki predstavlja maksimalno velikost svetlosti in je v razponu od 0 do 255. Vrednost 0 pomeni, da je barva izklopljena, vrednost 255 pa pomeni, da je barva maksimalno prisotna. Glavi datoteke sledijo podatki o pikslih. Ker je format PGM namenjen za sivinske slike vsebuje vsaka točka (piksel) eno število. Število je svetlost črne barve. Črna barva ima vrednost 0, bela pa 255.

 
 

 

3. OPIS PROGRAMIRANJA
 

Programiral sem z programskim jezikom Fortran PowerStation 4.0. Program je narejen tako, da uporabi Floyd in Steinbergov algoritem za pretvorbo rastrskih slik formata PPM oblike ASCII ali PGM oblike ASCII. Program barvni sliki zmanjša število barv na 2, 5, 8, 27 ali 64 osnovnih barv, sivinsko sliko pa pretvori v črnobelo (dve barvi).
 

 
Branje poljubno velike matrike:

Največji problem predstavlja branje poljubno velike matrike podatkov o pikslih. Ta problem sem rešil na sledeč način:

PARAMETER (n=100)
INTEGER*2 IN(n)
OPEN (1,FILE='Ime vhodne datoteke.ppm')
READ (1,*,END=70) (IN(i), i=1,n)
70   CONTINUE
OPEN (2,FILE='Ime izhodne datoteke.ppm')
WRITE (2,*) (IN(j), j=1,i-1)
END
 

Floyd in Steinbergov algoritem metode Error diffusion se glasi:

1) Za barvno sliko formata PPM v obliki ASCII:

DO j=1,i-1

IF (IN(j)<=127) THEN
OUT(j)=0
END IF

IF (IN(j)>127) THEN
OUT(j)=255
END IF
 
ERR=IN(j)-OUT(j)                                       ! Določitev napake (error)
 
IN(j+3)=IN(j+3)+(7./16.)*ERR                                       ! Floyd and Steinberg algoritem
IN(j+(3*G3)+3)=IN(j+(3*G3)+3)+(1./16.)*ERR            ! za barvno sliko, ki ima v enem
IN(j+(3*G3))=IN(j+(3*G3))+(5./16.)*ERR                     ! pikslu še tri številke (RGB).
IN(j+(3*G3)-3)=IN(j+(3*G3)-3)+(3./16.)*ERR              !

END DO
 

 
2) Za sivinsko sliko formata PGM v obliki ASCII: DO j=1,i-1

IF (IN(j)<=127) THEN
OUT(j)=0
END IF

IF (IN(j)>127) THEN
OUT(j)=255
END IF

ERR=IN(j)-OUT(j)                            ! Določitev napake (error)
 
IN(j+1)=IN(j+1)+(7./16.)*ERR                          ! Floyd and Steinberg algoritem
IN(j+G3+1)=IN(j+G3+1)+(1./16.)*ERR            ! za sivinsko sliko, ki ima za
IN(j+G3)=IN(j+G3)+(5./16.)*ERR                     ! en piksel samo eno številko.
IN(j+G3-1)=IN(j+G3-1)+(3./16.)*ERR              !

END DO
 

 
 

Popis oznak v programu LahiCon.txt:

 

G1 Prvi znak v glavi datoteke je: P3 ali P2
G2 Drugi znak v glavi datoteke je: #
G3 Tretji znak v glavi datoteke je število točk široke slike
G4 Četrti znak v glavi datoteke je število točk visoke slike
G5 Peti znak v glavi datoteke je max. velikost svetlosti
ODG Odgovor na vprašanje o izbiri možnosti
ODG1 Odgovor na vprašanje o pretvorbi v št. barv
ODG2 Odgovor na vprašanje o tipu pet barvne slike
INDAT Ime vhodne datoteke z končnico .ppm ali .pgm
OUTDAT Ime izhodne datoteke z končnico .ppm ali .pgm
IZH Odgovor na vprašanje če želiš pretvoriti še kakšno sliko
IZH1 Odgovor na vprašanje če želiš pretvoriti drugo sliko, ker te datoteke ni
IZH2 Odgovor na vprašanje če želiš napisati ime druge datoteke
IN Vhodni podatki
OUT Izhodni podatki
ERR Napaka piksla
ERR1, ERR2, ERR3 Napake rdeče, zelene in modre komponente barvnega piksla
n Največje število vhodnih podatkov
 
 
 

 


Down load:

Če želite si lahko presnamete programsko kodo na svoj računalnik: Down load code

Warning:         Feel free to use. But remember me!

                                  © Mitja Laharnar 1998



 

 

4. PRIMER DELOVANJA PROGRAMA (Slike)
 
 
 
Barvna slika formata PPM (ASCII oblike):

 
 
     Slika 4. Originalna slika formata PPM v obliki ASCII
 
 

     Slika 4a. Sfiltrirana slika na 2 barvi

 
 
 
     Slika 4b. Sfiltrirana slika na 5 barv - bolj zrnata slika
 
 
 
     Slika 4c. Sfiltrirana slika na 5 barv - manj zrnata slika
 
 
 
     Slika 4d. Sfiltrirana slika na 8 barv
 
 

     Slika 4e. Sfiltrirana slika na 27 barv
 

 
     Slika 4f. Sfiltrirana slika na 64 barv
 
 
 

 
 

Sivinska slika formata PGM (ASCII oblike):
 
 

     Slika 5. Originalna slika formata PGM v obliki ASCII
 
 
 
     Slika 7. Sfiltrirana slika na 2 barvi
 
 
 
 
 
 
 
 

5. NAPOTKI UPORABNIKU

 

Pregled in izdelava slik:

V okolju X-Windows (UNIX) lahko ustvarimo in gledamo slike formata PPM ali PGM z programom xv, v okolju MS-Windows pa s programom Paint Shop.
 

Opis programa:

Program pretvori (filtrira) barvno sliko formata PPM oblike ASCII ali sivinsko sliko formata PGM oblike ASCII po metodi Error diffusion z uporabo algoritma Floyd and Steinberg. Program barvni sliki zmanjša število barv na 2, 5, 8, 27 ali 64 barv, sivinsko sliko pa pretvori v črnobelo (dve barvi).
 

Zagon programa:

Program LahiCon.exe presnemite v nek direktorij na vašem trdem disku (npr. C:\TEMP). Pod isti direktorij presnemite poljubno sliko formata PPM oblike ASCII ali PGM oblike ASCII. Zaženite program LahiCon.exe in sledite vprašanjem, ki vam jih zastavlja.
 

Omejitve:

 



Down load: 

Tukaj si lahko presnamete program LahiCon.exe na svoj računalnik: Down load program

Če želite si lahko za začetek presnamete tudi vzorčne datoteke sample.zip, ki zasedejo 1,08 MB: Down load sample
 
Warning:         Feel free to use. But remember me!

                                © Mitja Laharnar 1998


 
Authors address:
Mitja Laharnar
Predstruge 18
1312 Videm-Dobrepolje
SLOVENIJA

tel: + 386 (0)61/788-159