deadlime

Kezdek beállni erre a havi egy bejegyzésre. Ez nem feltétlen egy jó dolog, de legalább valami rendszeresség már van benne. Azért nem ártana letornászni ezt legalább heti egyre, de addig is, jöjjön a "januári bejegyzés". Remélem sikerül valami érdekeset hoznom az év első deadlime-os bejegyzésével.

A téma ismét a képekkel és a GD könyvtárral lesz kapcsolatos, bár a régi adatrejtéses bitbűvészkedésnél kicsit tovább merészkedünk a képfeldolgozás és a mintafelismerés irányába. A feladat roppant egyszerű lesz, egy adott képen szeretnénk megtalálni - lehetőleg - az összes hármas számot (azért pont a hármast, mert az kellően hasonlít a nagy b betűre, valamint a nyolcas számra is, így nehezítve a dolgunkat). Ehhez adott maga a kép, amin keresünk (egy kis zajjal nehezítettem a keresést, különben elég egyszerű lenne...), valamint egy minta, hogy mit is szeretnénk megtalálni. Vessük is rögtön bele magunkat a hogyanokba.

Több fajta módszer is létezik annak megállapítására, hogy egy kép bizonyos része és egy minta mennyire hasonlít egymásra. A módszerek lényegében abból állnak, hogy vesszük a mintát, ráillesztjük a kép bal felső sarkára, egy megfelelő képlet segítségével kiszámítjuk, hogy ott mennyire illeszkedik (vagy épp nem illeszkedik), az értéket eltároljuk, majd a mintát eltoljuk egy pixellel balra. Ha elértünk a sor végére, akkor egy pixellel lejjebb toljuk a mintát és visszaugrunk a sor elejére. Innentől már csak az adott képletben fogunk eltérni. Nézzük is az elsőt, ami az SSD nevet kapta, és elsőre talán egy picit ijesztőnek tűnhet:

A képletben látható W a minta lokális koordinátáinak halmaza (tehát függetlenek attól, hogy a képen belül hol járunk éppen), az F pedig a kép koordinátáinak halmaza. Az adatrejtéses bejegyzés óta megtartottam azt a jó szokásomat, hogy továbbra is szürkeárnyalatos képekkel dolgozok, tehát az f és a w függvények olyanok, hogy a kép- illetve a minta koordinátihoz rendelnek egy 0 és 255 közötti számot. Jöjjön egy példa is, hogy egy kicsit leegyszerűsített helyzetben ez hogyan is működik:

A szám, amit a végén megkapunk az "Eredmény" részben lévő pixelek értékeinek összege, azaz nyolc lesz. Mint az látszik, ez a módszer azt adja meg, hogy a képnek ez a része mennyire különbözik a mintától, vagyis minél közelebb van a visszatérési érték a nullához, annál jobb nekünk. A teszteléseim során az SSD elég szép eredményeket ért el a zaj nélküli, fekete-fehér képek esetén (gyakorlatilag az összes hármast megtalálta, mivel egy ilyen mintához érve a képlet visszatérési értéke nulla volt), de a zajjal nem tudott mit kezdeni.

Így jött a képbe az SSD_SC, amivel a kép és a minta közti intenzitás-különbséget próbáljuk korrigálni. Az új képlet lényegét muszáj leszek szavakban elmagyarázni, mivel szélességében meghaladja a design befogadóképességét, tehát: lényegében az f(x+x',y+y') függvényértékből levonunk egy f₂(x,y) függvényértéket és a w(x',y') értékből is egy w₂ értéket. Majd még az így kapott értékeket is kivonjuk egymásból és az egészet négyzetre emeljük (mint azt tettük a sima SSD esetében is). Már csak azt kellene tudni, hogy ez az f₂ és a w₂ hogyan is jön ki. Az f₂ a kép minta által borított pixeleinek átlagértéke (az összes pixel értékének az összege osztva a pixelek számával), a w₂ pedig a minta pixeleinek az átlagértéke (hasonlóan számolva). Tulajdonképpen azt fejezik ki, hogy a minta és a minta által fedett képterület mennyire sötétek illetve világosak.
Magam is meglepődtem a módszer eredményességén, megfelelő hibahatár mellett az összes hármast sikerült megtalálnia a zajos képen (hibahatár alatt értem azt, hogy mekkora különbséget engedek meg a kép adott része és a minta között, hogy az még találatnak számítson).

Így a végére pedig jöjjön egy PHP-s megvalósítás az SSD_SC-ra:

$image = imagecreatefromgif('image.gif');
$template = imagecreatefromgif('template.gif');

$image_width = imagesx($image);
$image_height = imagesy($image);

$template_width = imagesx($template);
$template_height = imagesy($template);

for ($x=0;$x<$image_width;++$x) {
    for ($y=0;$y<$image_height;++$y) {
        $tmp = imagecolorsforindex($image, imagecolorat($image, $x, $y));
        $image_data[$x][$y] = $tmp['red'];
    }
}

$template_average = 0;
for ($x=0;$x<$template_width;++$x) {
    for ($y=0;$y<$template_height;++$y) {
        $tmp = imagecolorsforindex($template, imagecolorat($template, $x, $y));
        $template_data[$x][$y] = $tmp['red'];
        $template_average += $tmp['red'];
    }
}
$template_average = $template_average / ($template_width * $template_height);

imagedestroy($template);

$hibahatar = 100000;

$min = array();
$min_values = array();

Első körben még semmi komoly, betöltöm a két képet, meghatározom a méretüket, az összes pixelük színét eltárolom egy-egy tömbben (az $image_data és a $template_data tömbök) és meghatározom a w₂ értékét (ez lenne a $template_average, amit ugyebár elég egyszer kiszámolni, mivel nem függ a minta képen való elhelyezkedésétől). Most jön a neheze, a főciklus(ok):

for ($image_x=0;$image_x<($image_width - $template_width);++$image_x) {
    for ($image_y=0;$image_y<($image_height - $template_height);++$image_y) {
        $SSD[$image_x][$image_y] = 0;
        
        $image_average = 0;
        for ($template_x=0;$template_x<$template_width;++$template_x) {
            for ($template_y=0;$template_y<$template_height;++$template_y) {
                $image_average += $image_data[($image_x + $template_x)][($image_y +     $template_y)];
            }
        }
        $image_average = $image_average / ($template_width * $template_height);

        for ($template_x=0;$template_x<$template_width;++$template_x) {
            for ($template_y=0;$template_y<$template_height;++$template_y) {
                $SSD[$image_x][$image_y] += pow((
                    ($image_data[($image_x + $template_x)][($image_y + $template_y)] - $image_average) -
                    ($template_data[$template_x][$template_y] - $template_average)
                ), 2);
            }
        }
    }

    $min[$image_x] = min($SSD[$image_x]);
    foreach ($SSD[$image_x] as $k => $v) {
        if ($v <= ($min[$image_x] + $hibahatar)) {
            $min_values[$image_x][] = $k;
        }
    }
}

Mint az észrevehető, jó pár ciklus van egymásba ágyazva, ezért nem éppen várható el a scripttől, hogy másodpercek alatt lefusson, főleg ha nem éppen kis képekről van szó. Végül pedig bejelöljük a találatokat az eredeti képen egy zöld négyzettel és elmentjük az új képet:

$green = imagecolorallocate($image, 0, 255, 0);

$the_min = min($min);
foreach ($min as $k => $v) {
    if ($v <= ($the_min + $hibahatar)) {
        foreach ($min_values[$k] as $k2 => $v2) {
            imagerectangle($image, $k-1, $v2-1, $k+$template_width, $v2+$template_height, $green);
        }
    }
}

imagegif($image, 'image_new.gif');

imagedestroy($image);

A végére pedig jöjjön egy kép, hogy az SSD_SC nálam milyen eredménnyel járt a példakódban is használt 100000-es hibahatárt használva:

Remélem mindenkinek sikerült felkeltenem az érdeklődését. Igény esetén szót ejthetek még esetleg a CC, NCC, MNCC képletekről (ezek az SSD-vel ellentétben a hasonlóságok mérésére szolgálnak). Addig is, akit komolyabban is érdekel a téma, annak tudom ajánlani ezt a weboldalt.