Page 15 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 15
skanje slik z algoritmi po vzorih iz narave
Gregor Jurgec Iztok Fister
Univerza v Mariboru Univerza v Mariboru
Fakulteta za elektrotehniko, racˇunalništvo in Fakulteta za elektrotehniko, racˇunalništvo in
informatiko informatiko
Smetanova 17, Maribor Smetanova 17, Maribor
gregor.jurgec@gmail.com iztok.fister@um.si
POVZETEK (npr. ˇzivali ali ˇzuˇzelk), ki reˇsujejo vsakodnevne probleme po-
razdeljeno in kolektivno [1]. S kombinacijo znaˇcilnosti obeh
V ˇclanku predstavljamo postopek stiskanja slik na inova- druˇzin lahko razvijemo hibridne algoritme, ki so sposobni
tiven naˇcin s pomoˇcjo optimizacijskih algoritmov iz dveh reˇsevanja tudi kompleksnejˇsih optimizacijskih problemov. S
razliˇcnih druˇzin, tj. evolucijskih algoritmov in algoritmov hibridizacijo razliˇcnih delov algoritma dodamo osnovnemu
na osnovi inteligence rojev. V naˇsi raziskavi za reˇsevanje algoritmu domensko specifiˇcno znanje domene [4, 5].
problema stiskanja slik uporabljamo diferencialno evolucijo
in optimizacijo s kukaviˇcjim iskanjem. Osnovna algoritma V tem ˇclanku reˇsujemo problem stiskanja slik z izboljˇsanima
izboljˇsamo z adaptacijskimi in hibridizacijskimi metodami. optimizacijskima algoritmoma diferencialne evolucije [10] in
Stiskanje slik izvedemo s pomoˇcjo mnoˇzice primitivnih ge- kukaviˇcjega iskanja [11] sposobna generiranja slik, ki zase-
ometrijskih oblik trikotnikov. Razvita algoritma testiramo dajo manj prostora, ampak slabˇse kakovosti. Sliko predsta-
na realnih primerih stiskanja slik in kakovost rezultatov sti- vljamo s trikotniki narisanimi na platno, ki so doloˇceni s
skanja primerjamo med seboj. Z izboljˇsanima algoritmoma koordinatami ogliˇsˇc in barvo. Trikotniki so uˇcinkoviti za to
dobimo zelo dobre rezultate stisnjenih slik, saj podobnost nalogo saj pokrivajo veˇc slikovnih pik kot ena sama toˇcka in
teh slik v primerjavi z izvornimi slikami v najslabˇsem pri- omogoˇcajo prekrivanje in prosojnost barv v doloˇceni regiji.
meru presega 89,70 %, v najboljˇsem primeru pa doseˇzemo Naˇs cilj je, da bi bila izrisana slika ˇcim bolj podobna ori-
92,08 %. ginalni sliki. V tem ˇclanku se zgledujemo in nadgrajujemo
delo iz [13, 7], kjer s pomoˇcjo trikotnikov in samo adaptivne
Kjucˇne besede diferencialne evolucije oziroma genetskega algoritma posku-
ˇsajo zgraditi pribliˇzen model slike.
evolucijski algoritmi, inteligenca rojev, diferencialna evolu-
cija, kukaviˇcje iskanje, stiskanje slik S tem delom ˇzelimo pokazati, da lahko z izboljˇsanima algo-
ritmoma na osnovi obnaˇsanja kukavic in diferencialne evo-
1. UVOD lucije uspeˇsno stisnemo izvorno sliko. Pri tem lahko ugo-
tovimo, da sta oba algoritma primerna za stiskanje slik s
Z razvojem naprednih senzorjev za zajem slik visoke loˇclji- trikotniki, tj. na inovativen naˇcin in s pomoˇcjo novih algo-
vosti se poveˇcuje velikost zajetih posnetkov. Pri tem pri- ritmov, po vzoru iz narave. Tak naˇcin stiskanja slik lahko
demo do problema shranjevanja slik, saj nestisnjene slike postane dobra alternativa obstojeˇcim algoritmom stiskanja
zavzemajo ogromno prostora na spominskih medijih. Da slik. Seveda ti algoritmi potrebujejo ˇse dodatne izboljˇsave,
prihranimo prostor, uporabljamo razliˇcne optimizacijske al- vendar so se kot osnova izkazali zelo dobro, kar dokazujejo
goritme, ki stisnejo podatke na raˇcun izgube informacij o tudi rezultati v nadaljevanju.
sliki. Za te izgube seveda ˇzelimo, da so ˇcim manjˇse. Algo-
ritmi stiskanja slik iˇsˇcejo podobnosti v podatkih, oz. sku- Struktura ˇclanka v nadaljevanju je naslednja. Drugo po-
ˇsajo podatke, zajete s senzorji, spraviti v ˇcim kompaktnejˇso glavje se ukvarja s podanimi sploˇsnimi informacijami o ko-
obliko. diranju slik. V tretjem in ˇcetrtem poglavju predstavimo oba
izboljˇsana algoritma za stiskanje slik. Peto poglavje primerja
Glavna razlika med evolucijskimi algoritmi in algoritmi na rezultate stiskanja realnih slik z izboljˇsanima algoritmoma.
osnovi inteligence rojev je, da evolucijski algoritmi [4] pri op-
timizaciji simulirajo naravno evolucijo z operatorji mutacije, 2. KODIRANJE SLIKE
kriˇzanja in selekcije [3], medtem ko delovanje algoritmov na
osnovi inteligence rojev temelji na obnaˇsanju bioloˇskih vrst V naˇsem delu uporabljamo izgubni naˇcin stiskanja slik, ker
imajo naˇse stisnjene slike nepravilnosti in so popaˇcene. Naˇsa
slika je predstavljena z mnoˇzico barvnih trikotnikov, narisa-
nih na ˇcrno podlago, ki je iste velikosti kot originalna slika.
Mnoˇzica trikotnikov predstavlja sliko, podobno originalni.
Vsak trikotnik je sestavljen iz treh toˇck s koordinatami x,
y in barvo, s katero je obarvan, v barvnem prostoru rdeˇce-
zeleno-modro-alfa (angl. Red, Green, Blue, Alpha, krajˇse
RGBA). Zelo pomembno je, da uporabimo prosojnost tri-
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 15
Ljubljana, Slovenia, 12 October
Gregor Jurgec Iztok Fister
Univerza v Mariboru Univerza v Mariboru
Fakulteta za elektrotehniko, racˇunalništvo in Fakulteta za elektrotehniko, racˇunalništvo in
informatiko informatiko
Smetanova 17, Maribor Smetanova 17, Maribor
gregor.jurgec@gmail.com iztok.fister@um.si
POVZETEK (npr. ˇzivali ali ˇzuˇzelk), ki reˇsujejo vsakodnevne probleme po-
razdeljeno in kolektivno [1]. S kombinacijo znaˇcilnosti obeh
V ˇclanku predstavljamo postopek stiskanja slik na inova- druˇzin lahko razvijemo hibridne algoritme, ki so sposobni
tiven naˇcin s pomoˇcjo optimizacijskih algoritmov iz dveh reˇsevanja tudi kompleksnejˇsih optimizacijskih problemov. S
razliˇcnih druˇzin, tj. evolucijskih algoritmov in algoritmov hibridizacijo razliˇcnih delov algoritma dodamo osnovnemu
na osnovi inteligence rojev. V naˇsi raziskavi za reˇsevanje algoritmu domensko specifiˇcno znanje domene [4, 5].
problema stiskanja slik uporabljamo diferencialno evolucijo
in optimizacijo s kukaviˇcjim iskanjem. Osnovna algoritma V tem ˇclanku reˇsujemo problem stiskanja slik z izboljˇsanima
izboljˇsamo z adaptacijskimi in hibridizacijskimi metodami. optimizacijskima algoritmoma diferencialne evolucije [10] in
Stiskanje slik izvedemo s pomoˇcjo mnoˇzice primitivnih ge- kukaviˇcjega iskanja [11] sposobna generiranja slik, ki zase-
ometrijskih oblik trikotnikov. Razvita algoritma testiramo dajo manj prostora, ampak slabˇse kakovosti. Sliko predsta-
na realnih primerih stiskanja slik in kakovost rezultatov sti- vljamo s trikotniki narisanimi na platno, ki so doloˇceni s
skanja primerjamo med seboj. Z izboljˇsanima algoritmoma koordinatami ogliˇsˇc in barvo. Trikotniki so uˇcinkoviti za to
dobimo zelo dobre rezultate stisnjenih slik, saj podobnost nalogo saj pokrivajo veˇc slikovnih pik kot ena sama toˇcka in
teh slik v primerjavi z izvornimi slikami v najslabˇsem pri- omogoˇcajo prekrivanje in prosojnost barv v doloˇceni regiji.
meru presega 89,70 %, v najboljˇsem primeru pa doseˇzemo Naˇs cilj je, da bi bila izrisana slika ˇcim bolj podobna ori-
92,08 %. ginalni sliki. V tem ˇclanku se zgledujemo in nadgrajujemo
delo iz [13, 7], kjer s pomoˇcjo trikotnikov in samo adaptivne
Kjucˇne besede diferencialne evolucije oziroma genetskega algoritma posku-
ˇsajo zgraditi pribliˇzen model slike.
evolucijski algoritmi, inteligenca rojev, diferencialna evolu-
cija, kukaviˇcje iskanje, stiskanje slik S tem delom ˇzelimo pokazati, da lahko z izboljˇsanima algo-
ritmoma na osnovi obnaˇsanja kukavic in diferencialne evo-
1. UVOD lucije uspeˇsno stisnemo izvorno sliko. Pri tem lahko ugo-
tovimo, da sta oba algoritma primerna za stiskanje slik s
Z razvojem naprednih senzorjev za zajem slik visoke loˇclji- trikotniki, tj. na inovativen naˇcin in s pomoˇcjo novih algo-
vosti se poveˇcuje velikost zajetih posnetkov. Pri tem pri- ritmov, po vzoru iz narave. Tak naˇcin stiskanja slik lahko
demo do problema shranjevanja slik, saj nestisnjene slike postane dobra alternativa obstojeˇcim algoritmom stiskanja
zavzemajo ogromno prostora na spominskih medijih. Da slik. Seveda ti algoritmi potrebujejo ˇse dodatne izboljˇsave,
prihranimo prostor, uporabljamo razliˇcne optimizacijske al- vendar so se kot osnova izkazali zelo dobro, kar dokazujejo
goritme, ki stisnejo podatke na raˇcun izgube informacij o tudi rezultati v nadaljevanju.
sliki. Za te izgube seveda ˇzelimo, da so ˇcim manjˇse. Algo-
ritmi stiskanja slik iˇsˇcejo podobnosti v podatkih, oz. sku- Struktura ˇclanka v nadaljevanju je naslednja. Drugo po-
ˇsajo podatke, zajete s senzorji, spraviti v ˇcim kompaktnejˇso glavje se ukvarja s podanimi sploˇsnimi informacijami o ko-
obliko. diranju slik. V tretjem in ˇcetrtem poglavju predstavimo oba
izboljˇsana algoritma za stiskanje slik. Peto poglavje primerja
Glavna razlika med evolucijskimi algoritmi in algoritmi na rezultate stiskanja realnih slik z izboljˇsanima algoritmoma.
osnovi inteligence rojev je, da evolucijski algoritmi [4] pri op-
timizaciji simulirajo naravno evolucijo z operatorji mutacije, 2. KODIRANJE SLIKE
kriˇzanja in selekcije [3], medtem ko delovanje algoritmov na
osnovi inteligence rojev temelji na obnaˇsanju bioloˇskih vrst V naˇsem delu uporabljamo izgubni naˇcin stiskanja slik, ker
imajo naˇse stisnjene slike nepravilnosti in so popaˇcene. Naˇsa
slika je predstavljena z mnoˇzico barvnih trikotnikov, narisa-
nih na ˇcrno podlago, ki je iste velikosti kot originalna slika.
Mnoˇzica trikotnikov predstavlja sliko, podobno originalni.
Vsak trikotnik je sestavljen iz treh toˇck s koordinatami x,
y in barvo, s katero je obarvan, v barvnem prostoru rdeˇce-
zeleno-modro-alfa (angl. Red, Green, Blue, Alpha, krajˇse
RGBA). Zelo pomembno je, da uporabimo prosojnost tri-
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 15
Ljubljana, Slovenia, 12 October
