Page 16 - 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. 16
nikov, s ˇcimer doseˇzemo prekrivanje trikotnikov in s tem visˇinaSlike sˇirinaSlike xi∗,j R − xi,j R
dobimo veliko razliˇcnih barv, ki sestavljajo sliko. i=1 j=1
Mnoˇzico barvnih trikotnikov, ki sestavljajo sliko, kodiramo
v vektor na naslednji naˇcin: vektor x = (T1, T2, T3, ..., Tmax)
predstavlja mnoˇzico trikotnikov Ti, ∀i ∈ {1, ..., max}, kjer
max doloˇca ˇstevilo trikotnikov, ki sestavljajo sliko. Vsak od 255 · visˇinaSlike · sˇirinaSlike
teh trikotnikov je kodiran v vektor Ti = (x1, y1, x2, y2, x3, y3,
R, G, B, A), ki je sestavljen iz celih ˇstevil, kjer pari xi, yi, ∀i ∈
{1, 2, 3} predstavljajo koordinatne toˇcke ogliˇsˇc trikotnika, visˇinaSlike sˇirinaSlike
skalarji R, G, B barvo in A prosojnost trikotnika.
Slika 1 prikazuje mnoˇzico prekrivajoˇcih barvnih trikotnikov xi∗,j G − xi,j G
na ˇcrnem ozadju v zgodnji fazi delovanja optimizacijskih al-
goritmov. f (x) = 100% · 1 − (1)
i=1 j=1
Slika 1: Osnovni prikaz slike s trikotniki. +
255 · visˇinaSlike · sˇirinaSlike
visˇinaSlike sˇirinaSlike
xi∗,j B − xi,j B
i=1 j=1
+ 255 · visˇinaSlike · sˇirinaSlike
3. DIFERENCIALNA EVOLUCIJA
Diferencialna evolucija (angl. Differential Evolution, krajˇse
DE) reˇsuje optimizacijski problem z izboljˇsevanjem posame-
znih reˇsitev iz populacije. Iz obstojeˇcih reˇsitev tvori posku-
sne reˇsitve (angl. candidate solution) z dodajanjem razlike
nakljuˇcno izbranih vektorjev (mutacijska strategija), te pa
je potrebno vrednotiti. Vrednosti elementov vektorjev po-
skusne reˇsitve, ki so izven definiranih obmoˇcij popravimo
na zgornje ali spodnje meje v operaciji popravljanja. Cˇ e je
poskusna reˇsitev boljˇsa od obstojeˇce, ta reˇsitev zamenja ob-
stojeˇco v populaciji. Ta postopek ponavljamo za vsakega po-
sameznika v populaciji reˇsitev v vsaki generaciji algoritma,
dokler ni izpolnjen pogoj zaustavljanja [10]. Model diferen-
cialne evolucije je prikazan na sliki 2.
2.1 Optimizacijski problem in Slika 2: Model diferencialne evolucije
kriterijska funkcija
Optimizacija je postopek iskanja najboljˇsih vhodnih para-
metrov pri znanem modelu in znanih izhodnih parametrih [6,
4]. Optimizacijski problem P definiramo kot ˇcetvorko
P = I, S, f, cilj ,
kjer pomenijo: I mnoˇzico vseh nalog, S mnoˇzico dopu-
stnih reˇsitev problema, f kriterijsko funkcijo (angl. objec-
tive function), s katero ocenjujemo kakovost reˇsitve, in cilj,
s katerim povemo ali kriterijsko funkcijo maksimiziramo ali
minimiziramo. Vrednosti kriterijske funkcije so lahko ska-
larji ali v primeru veˇc-kriterijskih problemov vektorji [9, 12].
Kriterijska funkcija v naˇsem primeru primerja vsako isto le-
ˇzeˇco slikovno piko generirane slike s slikovno piko na origi-
nalni sliki. Vsako slikovno piko primerjamo po vseh treh
barvnih komponentah R, G, B. Vsoto razlik isto leˇzeˇcih sli-
kovnih pik pri vsaki od treh komponent delimo s produktom
med viˇsino in ˇsirino slike ter z vsemi moˇznimi odtenki vsake
od barv RGB. Z rezultatom dobimo vrednost razliˇcnosti slik,
ki ga odˇstejemo od ena in dobimo podobnost med slikama.
To pomnoˇzimo s 100 % in ta vrednost potem predstavlja po-
dobnost najdene slike v primerjavi z originalno v odstotkih.
Naˇs cilj je, da je podobnost ˇcim veˇcja in zato moramo naˇso
kriterijsko funkcijo maksimizirati.
Naˇsa kriterijska funkcija f (x) je opisana z enaˇcbo 1, kjer x∗
predstavlja originalno, referenˇcno sliko, x pa stisnjeno, gene-
rirano sliko. Indeksa xi, ∀i ∈ {1, ...visˇinaSlike} in yj, ∀j ∈
{1, ...sˇirinaSlike} doloˇcata trenutni poloˇzaj opazovane sli-
kovne pike. Oznake R, G in B pa definirajo, v kateri kompo-
nenti barve RGB se nahajamo. Konstanta 255 doloˇca ˇstevilo
razliˇcnih odtenkov barve.
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 16
Ljubljana, Slovenia, 12 October
dobimo veliko razliˇcnih barv, ki sestavljajo sliko. i=1 j=1
Mnoˇzico barvnih trikotnikov, ki sestavljajo sliko, kodiramo
v vektor na naslednji naˇcin: vektor x = (T1, T2, T3, ..., Tmax)
predstavlja mnoˇzico trikotnikov Ti, ∀i ∈ {1, ..., max}, kjer
max doloˇca ˇstevilo trikotnikov, ki sestavljajo sliko. Vsak od 255 · visˇinaSlike · sˇirinaSlike
teh trikotnikov je kodiran v vektor Ti = (x1, y1, x2, y2, x3, y3,
R, G, B, A), ki je sestavljen iz celih ˇstevil, kjer pari xi, yi, ∀i ∈
{1, 2, 3} predstavljajo koordinatne toˇcke ogliˇsˇc trikotnika, visˇinaSlike sˇirinaSlike
skalarji R, G, B barvo in A prosojnost trikotnika.
Slika 1 prikazuje mnoˇzico prekrivajoˇcih barvnih trikotnikov xi∗,j G − xi,j G
na ˇcrnem ozadju v zgodnji fazi delovanja optimizacijskih al-
goritmov. f (x) = 100% · 1 − (1)
i=1 j=1
Slika 1: Osnovni prikaz slike s trikotniki. +
255 · visˇinaSlike · sˇirinaSlike
visˇinaSlike sˇirinaSlike
xi∗,j B − xi,j B
i=1 j=1
+ 255 · visˇinaSlike · sˇirinaSlike
3. DIFERENCIALNA EVOLUCIJA
Diferencialna evolucija (angl. Differential Evolution, krajˇse
DE) reˇsuje optimizacijski problem z izboljˇsevanjem posame-
znih reˇsitev iz populacije. Iz obstojeˇcih reˇsitev tvori posku-
sne reˇsitve (angl. candidate solution) z dodajanjem razlike
nakljuˇcno izbranih vektorjev (mutacijska strategija), te pa
je potrebno vrednotiti. Vrednosti elementov vektorjev po-
skusne reˇsitve, ki so izven definiranih obmoˇcij popravimo
na zgornje ali spodnje meje v operaciji popravljanja. Cˇ e je
poskusna reˇsitev boljˇsa od obstojeˇce, ta reˇsitev zamenja ob-
stojeˇco v populaciji. Ta postopek ponavljamo za vsakega po-
sameznika v populaciji reˇsitev v vsaki generaciji algoritma,
dokler ni izpolnjen pogoj zaustavljanja [10]. Model diferen-
cialne evolucije je prikazan na sliki 2.
2.1 Optimizacijski problem in Slika 2: Model diferencialne evolucije
kriterijska funkcija
Optimizacija je postopek iskanja najboljˇsih vhodnih para-
metrov pri znanem modelu in znanih izhodnih parametrih [6,
4]. Optimizacijski problem P definiramo kot ˇcetvorko
P = I, S, f, cilj ,
kjer pomenijo: I mnoˇzico vseh nalog, S mnoˇzico dopu-
stnih reˇsitev problema, f kriterijsko funkcijo (angl. objec-
tive function), s katero ocenjujemo kakovost reˇsitve, in cilj,
s katerim povemo ali kriterijsko funkcijo maksimiziramo ali
minimiziramo. Vrednosti kriterijske funkcije so lahko ska-
larji ali v primeru veˇc-kriterijskih problemov vektorji [9, 12].
Kriterijska funkcija v naˇsem primeru primerja vsako isto le-
ˇzeˇco slikovno piko generirane slike s slikovno piko na origi-
nalni sliki. Vsako slikovno piko primerjamo po vseh treh
barvnih komponentah R, G, B. Vsoto razlik isto leˇzeˇcih sli-
kovnih pik pri vsaki od treh komponent delimo s produktom
med viˇsino in ˇsirino slike ter z vsemi moˇznimi odtenki vsake
od barv RGB. Z rezultatom dobimo vrednost razliˇcnosti slik,
ki ga odˇstejemo od ena in dobimo podobnost med slikama.
To pomnoˇzimo s 100 % in ta vrednost potem predstavlja po-
dobnost najdene slike v primerjavi z originalno v odstotkih.
Naˇs cilj je, da je podobnost ˇcim veˇcja in zato moramo naˇso
kriterijsko funkcijo maksimizirati.
Naˇsa kriterijska funkcija f (x) je opisana z enaˇcbo 1, kjer x∗
predstavlja originalno, referenˇcno sliko, x pa stisnjeno, gene-
rirano sliko. Indeksa xi, ∀i ∈ {1, ...visˇinaSlike} in yj, ∀j ∈
{1, ...sˇirinaSlike} doloˇcata trenutni poloˇzaj opazovane sli-
kovne pike. Oznake R, G in B pa definirajo, v kateri kompo-
nenti barve RGB se nahajamo. Konstanta 255 doloˇca ˇstevilo
razliˇcnih odtenkov barve.
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 16
Ljubljana, Slovenia, 12 October
