Piccolo image archive and implementation of search based on colour areas

Automaatiotekniikan laitos Graafisen tekniikan laboratorio

Petri Helin

Piccolo kuva-arkisto

ja haun toteuttaminen väritiedon perusteella

Diplomityö

Espoossa 16.2.1998

Valvoja: Professori Hannu Saarelma

Ohjaaja: TkL Kimmo Valkealahti

ALKUSANAT

Kiitos Professori Hannu Saarelmalle neuvoista ja opastuksesta.

Kiitos Kimmo Valkealahdelle oivallisesta diplomityön ohjaamisesta. Hänen koke­

muksestaan oli suurta apua sisällön hiomisessa ja rönsyilyjen karsimisessa.

Kiitos Tietopolulle ja Teppo Kurjelle sekä Janne Rajalalle siitä, että Piccolo on ole­

massa ja tämä diplomityön aihe oli mahdollinen.

Tämä diplomityö on syntynyt päivätyön ohella hiukan alle vuoden aikana. Lukemat­

tomat illat ja viikonloput kuluivat ennenkuin työ oli valmis. Sanna-Maria Takalalle kuuluu kiitos ymmärtäväisestä ja tukevasta asennoitumisesta.

Рспллсео 1 AO 1 QQÖ

Petri Helin

TEKNILLINEN KORKEAKOULU DIPLOMITYÖN TIIVISTELMÄ Tekijä: Petri Ilari Helin Työn nimi: Piccolo kuva-arkisto ja haun to-

teuttaminen väritiedon perusteella Päivämäärä: 16.2.1998 Sivumääärä: 43

Osasto: Tietotekniikan osasto Professuuri: Aut-75 Graafinen tekniikka Valvoja: Professori Hannu Saarelma Ohjaaja: TkL Kimmo Valkealahti

Digitaalinen kuva-arkisto on tietokoneelle organisoitu kuvatiedostojen tallennusjärjestel- mä. Kuvat tallennetaan digitaaliseen arkistoon skannattuna tai digitaalisella kameralla luotuina TIFF-, JPEG- tai EPS-tiedostomuotoihin. Kuviin liitetään arkistossa luokittelu- teksti, jonka avulla niitä voidaan hakea.

Kuvamäärän kasvaessa tekstimuotoinen luokittelutieto ei yksin riitä. Oikea kuva ei löydy tai kuvia löytyy liikaa. Luokitteluja haku visuaalisten ominaisuuksien perusteella on yksi ratkaisu haun ongelmiiin. Visuaalisia ominaisuuksia ovat väri, tekstuuri ja muoto. Visu­

aalisen ominaisuuksien avulla kuvia voidaan hakea esimerkkikuvan perusteella. Omi­

naisuuksien tallentaminen ja haku eroaa perinteisestä tietokantateknologiasta, minkä takia tarvitaan uudentyyppisiä indeksointitekniikoita, kuten R*- tai K-D-puu.

Diplomityön kokeellinen osuus perustuu Piccolon kuva-arkistosovellukselle, jonka diplo mityön tekijä on toteuttanut työskennellessään Tietopolku Oy:ssä. Piccolon visuaalisten ominaisuuksien laskenta toteutetaan erottamalla kuvista yhtenäisiä värialueita. Ominaisuu det tallennetaan tietokantaan, josta voidaan tehdä hakuja käyttäen esimerkkikuvasta lasket tuja piirteitä hakuehtoina.

Piccolon visuaalisten piirteiden laskennan toteutus onnistui. Kuvista saadaan erotettua merkittävät välialueet riittävällä tarkkuudella.

avainsanat: kuva-arkisto, kuvapankki, visuaalinen haku, välialueiden erottaminen, segmentointi, monidimensioinen indeksointi

2. KUVA-ARKISTO 7

2.1 Kuvientallennusarkistoon 7

2.1.1 Skannaus 7

2.1.2 Digitaaliset originaalit 8

2.1.3 Kuvien tallennusmuodot 8

2.1.4 Esikatselukuvat 10

2.1.5 Lukuoikeudet ja muutosoikeudet 10

2.1.6 Kuvien luokittelu 10

2.2 Tekstihaku arkistosta 11

2.2.1 Tekstihaku luokittelutiedosta 12

2.2.2 Aiheen mukainen haku 13

2.3 Kuva-arkistojentekniikkaa 13

2.3.1 Toteutusperiaate 13

2.3.2 Resurssien käyttö 14

2.3.3 Suorituskyky 14

3. VISUAALINEN SISÄLTÖHAKU 16

3.1 Visuaalisetominaisuudet 16

3.1.1 Matalan tason ominaisuudet 17

3.1.2 Korkean tason ominaisuudet 17

3.1.3 Kuvan sisältö: objektit ja tausta 18

3.2 VÄRI 18

3.2.1 Väriominaisuuksien erottaminen kuvasta 18

3.2.2 Haku väriominaisuuksilla 19

3.3 Tekstuuri 20

3.3.1 Menetelmiä tekstuuriominaisuuksien erottamiseksi 20

3.4 Muoto 20

3.5 Muutominaisuudet 21

3.5.1 Liike 21

3.5.2 Hahmotelma 21

3.6 Haku 21

3.6.1 Haun toteutus 22

3.6.2 Haun käyttöliittymät 22

3.6.3 Visuaalinen haku tekstin perusteella 23

3.7 Segmentointi 24

3.8 Ominaisuuksientallennus 24

3.8.1 Tietorakenteet 24

3.9 Evaluointi 25

4. VISUAALISEN SISÄLTÖHAUN TOTEUTUS 26

4.1 Yleistä Piccolosta 26

4.2 Visuaalinenluokittelu 29

4.2.1 Kuvan skaalaus 30

4.2.2 Väriavaruusmuunokset RGB-HSV ja HSV-RGB 31

4.2.3 Kvantisointi 166 väriin 32

4.2.4 Väritys mediaanisuodattimella 32

4.2.5 Kuvan segmentointi 33

4.2.6 Piirrevektorin muodostaminen 34

4.3 Haku 35

4.3.1 Käytetyn menetelmän arviointi 39

5. YHTEENVETO 40

Käytetyt lyhenteet

CIE Commission Internationale d"Eclairage CMY Cyan Magenta Yellow

CMYK Cyan Magenta Yellow Black CGI Common Gateway Interface HLS Hue, Lightness, and Saturation HSV Hue, Saturation, and Value

IPTC International Press and Telecom Counsil JFIF Joint Photographic Interchange Format JPEG Joint Photographic Expert Group LZW Lempel Ziv Welch

РАЮ Redundant array of inexpensive disks RGB Red Green Blue

SQL Structured query language TIFF Tagged Image File Format

1. Johdanto

Digitaalisten kuva-arkistojen käyttö ja hyödyntäminen on lisääntynyt voimakkaasti 1990-luvulla /1/. Tämä johtuu yleisestä tarpeesta hyödyntää kuvia uudestaan, tallen- nevälineiden hintojen laskusta sekä siitä, että graafisen alan tuotantomenetelmät ovat laajasti digitalisoituneet. Kun lehdentekoprosessi on saatu toimimaan uudella tek­

niikalla, on seuraava vaihe kuva- ja tekstiarkistojen saattaminen osaksi lehdentekojär- jestelmää.

Kuva-arkistojen luokittelu ja haku on perinteisesti perustunut tekstuaaliseen luokitte­

lutietoon. Jokaiseen kuvaan on liitetty sisällöstä kertovia avainsanoja sekä kuvailevaa tekstiä. Yksinomaan tekstitiedon käyttö kuvien luokitteluun voi aiheuttaa useita ongel­

mia. Luokittelun suorittavan henkilön tulee tuntea kuvien yhteys, jotta luokittelu on­

nistuisi. Yhteys tarkoittaa tässä tapauksessa kuvan sisältöä, kuvaushetkeä ja kuvaan liittyviä siinä näkymättömiä asioita.

Hakujen tekeminen arkistosta vaatii myös kuvien yhteyden ja käytetyn sanaston tunte­

mista. Kun kuvamäärä kasvaa, vaikeutuu oikeiden kuvien löytäminen perinteisestä kuva-arkistosta. Avainsanojen ja kuvailevan tekstin perusteella löytyy liian paljon ja vääränlaisia kuvia.

Kuvien luokitteluja haku visuaalisen sisällön perusteella on yksi ratkaisu osaan kuva- arkistojen ongelmista. Visuaalisia ominaisuuksia ovat mm. väri, tekstuuri ja muoto.

Visuaalisen ominaisuuksien avulla voidaan kuvia hakea esimerkin perusteella. Haku tapahtuu etäisyysfunktiolla, joka kertoo kahden kuvan "samanlaisuuden". Hakua varten kuvista erotetaan visuaaliset ominaisuudet. Piirteiden tallentaminen ja etäisyys- funktioiden laskeminen eroaa perinteisestä tietokantateknologiasta, minkä takia tarvi­

taan uudenlaisia ratkaisuja tallennukseen ja hakuun. Perinteisellä В-puuhun perustu­

valla indeksoinnilla ei pystytä tallentamaan moniuloitteisia ominaisuuksia, vaan tarvi­

taan esimerkiksi R*- tai K-D-puun tyyppisiä algoritmeja.

Tämän työn tarkoituksena on käsitellä visuaalisten ominaisuuksien käyttöä kuva-ar­

kistoissa ja soveltaa väripiirteiden avulla tapahtuvaa visuaalista hakua Piccolo-ohjel­

mistossa. Piccolo on Macintoshissa toimiva kaupallinen kuva-arkistosovellus, jonka diplomityön tekijä on toteuttanut työskennellessään Tietopolku Oy:ssä vuodesta 1993 alkaen. Piccolo on käytössä n. 40 yrityksessä Suomessa ja Ruotsissa. Sillä voidaan arkistoida kuvia ja tekstiä sekä helpottaa dtp-prosessia, jossa lehti tehdään ilman toi- mitusjärjestelmää.

Piccolon visuaalinen ominaisuuksien laskenta toteutetaan erottamalla kuvasta yhtenäi­

siä välialueita, jotka ovat pinta-alaltaan vähintään 10 % kuvan kokonaispinta-alasta.

Yksittäisten aluiden lisäksi erotetaan kahden värin yhdistelmäalueet, joiden yhteenlas­

kettu pinta-ala on yli 15 %. Ominaisuudet tallennetaan tietokantaan, josta voidaan teh­

dä hakuja käyttäen esimerkkikuvasta laskettuja piirteitä hakuehtoina. Diplomityön lo­

pussa esitellään toteutetulla menetelmällä saavutettuja hakutuloksia sekä arvoidaan vi­

suaalisen haun käyttökelpoisuutta käytännön tilanteissa.

2. Kuva-arkisto

Kuva-arkiston tarkoituksena on tallentaa kuva myöhempää käyttöä varten. Kuva- arkisto-ohjelmiston tarkoituksena on se, että haluttu kuva löytyy arkistosta nopeasti.

Kuva-arkistoja käytetään nykyään hyvin erilaisissa ympäristöissä. Tyypillisiä käyt­

täjiä ovat aikakausi- ja sanomalehdet, museot ja oppilaitokset. Kuvien käytön ja ja­

lostuksen siirtyminen digitaaliseksi on luonut tarpeen hoitaa myös kuvien arkistointi tietokoneilla.

Kuva-arkistojen käyttö voidaan jakaa kahteen osaan: tiedon tallennukseen ja tiedon hyödyntämiseen. Tallennus on kuvien syöttöä arkistoon ja niiden luokittelua. Hyö­

dyntäminen käsittää kuvien hakua arkistosta ja niiden jatkokäsittelyä esimerkiksi ku­

vankäsittelyohjelmissa.

2.1 Kuvien tallennus arkistoon

2.1.1 Skannaus

Kuvien tulee olla digitaalisessa muodossa, jotta ne voidaan arkistoida digitaaliseen arkistoon. Lehdissä tuotantoprosessi on pääsääntöisesti nykyään tietokoneilla hoi­

dettu, joten kuvat ovat arkistointia varten valmiiksi skannattuja. Useat muut kuva- arkistojen käyttäjät joutuvat lukemaan kuvat sisään nimenomaan arkistointia varten.

Kuvan skannaus voidaan jakaa seuraaviin työvaiheisiin:

• Originaaliko van valmistelu

• Skannaus

• Skannatun kuvan rajaus, kierron poistoja värien korjailu

• Kuvan tallennus

Skannattavan kuvan koko ja skannausresoluutio vaihtelevat käyttötarkoituksen mu­

kaan. Esimerkiksi 6x7 tuuman laakadiasta sanomalehdelle riittää 7 megatavun, aika- kausilehdelle 20 megatavun ja korkealaatuiselle painotuotteelle 40 megatavun ko­

koinen kuva. Usein arkistoon tehdään huomattavasti edellämainittuja pienempi ku­

va, koska originaaliin ei ole tekijänoikeuksia ja digitaalinen kuva täytyy tallentaa sellaisena, ettei sitä voida painaa.

Värikorjailua ja -korostusta kannattaa arkistointia varten välttää. Kun arkiston kuvaa hyödynnetään myöhemmin, voivat vaatimukset värien sävyistä olla hyvin erilaiset kuin kuvaa skannatessa.

Skannauksen työvaiheita voidaan automatisoida sopivilla ohjelmistoilla, joita ovat esimerkiksi Binuscan /2/ tai Logoscan /3/. Ohjelmisto suorittaa skannauksen, ra­

jauksen ja värien korjailun automaattisesti haluttuun resoluutioon. Kun arkisto on luotava alusta alkaen, voi automatisointi nostaa tuottavuutta huomattavasti.

2.1.2 Digitaaliset originaalit

PhotoCD:n käyttö helpottaa kuvien tallennusta arkistoon /1/. PhotoCD on Kodakin kehittämä kuvien digitalisointimenetelmä, jossa filminegatiivi skannataan erityisellä Kodakin valmistamalla laitteistolla CD-ROM -muotoon. Näitä laitteistoja on suu­

rimmilla kuvavalmistajilla. Kuvat on tallennettu PhotoCD-levylle erityiseen Pho- toCD-tallennusmuotoon ja PhotoYCC-väriavaruuteen. Kuvan koko on normaalissa PhotoCD-muodossa enintään 2000 x 3000 pikseliä ja Pro PhotoCD-muodossa 4096 x 6144 pikseliä. Pro PhotoCD-muodossa saavutetaan riittävän korkea laatutaso kor- keatasoiseenkin painotyöhön.

Digitaaliset kamerat ovat nousemassa kilpailijaksi perinteiselle filmille. Niiden tark­

kuus ja värintoisto-ominaisuudet eivät vielä yllä filmin tasolle, mutta esimerkiksi sa­

nomalehti- ja World Wide Web -ympäristössä digitaalikameroiden laatu riit­

tää. Seuraavassa taulukossa on esitetty hintaluokittain digitaalikameroilla saavutetta­

vat kuvakoot pikseleissä /4/.

Taulukko 1. Eri digitaalikameroiden suorituskyky ja hinta kesällä 1997

Kamera Kuvan koko Hinta (mk)

Kodak DC-25 493x373 3.500

Minolta Dimage V 640x480 4.000

Canon PowerS hot 600 832x608 6.500

Olympus Camedia 800L 1024x768 7.000

Fujix DS-300 1260x1000 20.000

Agfa ActionCam 1528x1146 39.000

Kodak DCS460 3060x2036 170.000

Dicomed BigShot (kameraperä) 4096x4096 370.000

2.1.3 Kuvien tallennusmuodot

Kuva-arkistoon tallennettavien kuvien tiedostomuoto riippuu kuvien käyttötar­

koituksesta ja käytettävissä olevasta tallennuskapasiteetista. Jos kuvilta ei vaadita kaikkein korkeinta laatua (kuten sanomalehtipainatuksessa), on alkuperäisten kuvien pakkaus JPEG-menetelmällä /5/ suositeltavaa. JPEG-pakkauksen avulla päästään yleensä 1:20 pakkaussuhteeseen tai parempaan.

Kun taas halutaan korkeaa laatua, ja tallennuskapasiteettia on runsaasti, on TIFF /5/

suositeltava tiedostomuoto. TIFF on hyvin monipuolinen tiedostomuoto, jolle löy­

tyy useimmista ohjelmistoista tuki. Se sisältää suuren määrän erilaisia tiedon esitys­

muotoja, väriavaruuksia ja pakkaustapoja. Tyypillinen TIFF-tiedosto on täysväri RGB/ CMYK/CIELab-väriavaruudessa tallennettu kuva, joka on pakattu LZW-al- goritmilla.

Seuraavassa taulukossa on esitetty kuvan pakkautumista eri pakkausmenetelmillä (kaikissa alkuperäisen kuvan dimensiot ovat 1536 x 1024 pikseliä. JPEG-pakkaus

on tehty Photoshop-ohjelmiston laatuasetuksella normaali, joka tarkoittaa 50 % laa­

tutasoa.

Taulukko 2. Kuvatiedoston koot eri pakkausmenetelmillä

Kuvatyyppi Alkuperäisen koko (kt) LZW TIFF koko (kt)

JPEG koko (kt)

CMYK 6159 3233 273

RGB 4623 2372 182

CIELab 4623 2007 ei mahdollinen

harmaasävy 1548 811 113

mustavalko 201 150 ei mahdollinen

RGB grafiikka 1119 193 151

Tiedostomuotoon liittyy läheisesti arkistoitavien kuvien väriavaruus. Väriavaruus tarkoittaa sitä värinmuodostuksen periaatetta, millä silmän havaitsema väri muodos­

tetaan. Väriavaruudet voidaan jakaa kahteen perustyyppiin, jotka ovat additiivinen ja substraktiivinen. Additiivinen värinmuodostus tapahtuu sekoittamalla punaisen, vih­

reän ja sinisen valon intensiteettejä siten, että niiden summasta syntyy eri värejä tai valkoista. Substraktiivisessä värinmuodostuksessa värejä (syaani, magenta, keltai­

nen, musta) käytetään suodattamaan heijastuvaa valkoista valoa, jolloin muodostuu eri värejä.

Arkistoinnin kannalta paras vaihtoehto kuville olisi laitteistoriippumaton väriava­

ruus, kuten esimerkiksi CIELab. CIELab on tristimulusarvoista XYZ matemaattisel­

la muokkauksella linearisoitu väriavaruus. Tristimulusarvot perustuvat malliin sil­

män tavasta havaita värejä. Koska CIELab on laitteistoriippumaton, ei se ole sidottu minkään laitteiston ominaisuuksiin ja näin se olisi ideaalinen pitkäaikaiseen arkis­

tointiin. CIELab-väriavaruuden käyttö on ollut hankalaa vähäisen kokemuksen ja osittain puuttuvan sovellustuen takia. Suurin osa ohjelmistoista ei pysty käyttämään CIELab-kuvia. Lisäksi CIELab-väriavaruuden käyttäminen vaatisi värinhallintaa, joka ei ole vielä levinnyt yleiseen käyttöön.

Käytännössä esimerkiksi sanomalehdissä skannaus tehdään värikuvien osalta CMYK-väriavaruuteen. Kun CMYK-kuvia arkistoidaan, voidaan myöhemmin esi­

merkiksi painokoneen vaihtuessa joutua ongelmiin kuvien värintoiston kanssa.

Kahden painokoneen värintoisto voi huomattavasti erota toisistaan, jolloin yhdelle optimoidut CMYK-kuvat eivät toistu oikein värien osalta toisessa painokoneessa.

Tämän takia CMYK-skannatuille kuville on suositeltavaa tehdä muunnos RGB- väriavaruuteen ja arkistoida kuvat sellaisenaan. RGB-CMYK-RGB muunnoksissa häviää kuvista tietoa, mutta kuvan hyödyntämisen ongelmat ovat RGB-väria- varuudessa vähäisempiä kuin CMYK-avaruudessa.

2.1.4 Esikatselukuvat

Kuva-arkistoon tallennetaan kuva alkuperäisen lisäksi yleensä kahdella pienemmällä kuvakoolla. Pienempi ns. peukalonpääkuva voi olla esimerkiksi 192x192 pikseliä, kun taas isompi ns. selailukuva on 500 x 500 pikseliä tai enemmän.

Peukalonpääkuvalla voidaan valita suuresta kuvajoukosta näytöllä haluttu kuva, jota sitten tarkastellaan tarkemmin selailukuvalla. Joissakin tapauksissa on perusteltua käyttää kuva-arkistossa vielä kolmatta esikatselukuvan tarkkuutta. Tämä on tarpeel­

lista silloin, kun alkuperäiset kuvat ovat talletettu hitaalle tallenteelle, kuten nauhalle, magneto-optiselle levylle tai CD-ROM-levylle.

Esikatselukuvat kannattaa pakata tilan säästämiseksi. Esimerkiksi 120x120 pikselin esikatselukuva pienenee 42 kilotavusta n. 10 kilotavuun pakkaamalla se JPEG- al­

goritmilla.

2.1.5 Lukuoikeudet ja muutosoikeudet

Eri käyttäjillä on erilaiset tarpeet kuva-arkiston käyttöoikeuksien suhteen. Kun ar­

kistoa rakennetaan, tarvitaan laajat oikeudet muokata arkiston hakusanarakennetta ja sisältöä. Päivittäisessä kuvien lisäyksessä tarvitaan oikeudet muokata kuvien haku­

sanoja eli luokituksia ja lisätä kuvia arkiston tietokantaan. Tällaiset oikeudet ovat tyypillisesti kuva-arkiston hoitajalla. Normaalit käyttäjät tarvitsevat oikeudet tehdä hakuja arkistoon. Tämän lisäksi voidaan tarpeen mukaan antaa käyttäjille oikeudet kopioida arkistosta alkuperäisiä kuvia muokkausta ja hyödyntämistä varten.

2.1.6 Kuvien luokittelu

Tärkeä tekijä kuva-arkistoissa kuvien hyödyntämisen kannalta on hyvä ja kattava luokittelu. Luokittelujärjestelmän tulee olla laaja ja järjestetty aihepiirien mukaan.

Kuva-arkiston luokittelussa käsitteet voidaan jakaa kokonaisuuksiin. Tälläiset koko­

naisuudet tallennetaan tietokannan sarakkeisiin ts. kenttiin. Kenttien arvot annetaan mahdollisuuksien mukaan valmiista sanastosta. Kaikkea kuvaan liittyvää tietoa ei voi kuitenkaan koodata kenttiin. Siksi tulee luokittelussa olla mahdollisuus syöttää kuvasta myös kuvailevaa tekstiä.

Seuraavassa kuvassa on esimerkkinä Kouvolan Sanomien arkistoissa käytetty kent­

tärakenne.

i Tuutti

Tiedosto: Alfa_Romeo_8C_2300.jpg Jäljellä: 0

Kohteet: 1 ▼ 1

Otsikko Alfa Romeo 8C 2300.jpg Alkuperä Desktop Folder

Tekijä Markkanen Petri

a

Luonti pvm 12.9.1994 Luontiaika 06:34

Jul kaisupvm 14.10.1997 I Sivu [S

Sijainti koti maa

Fl

Pääluokka 1 tiede ja tekniikka

M

Pääluokka 2 sekalaiset

H

Tarkennus liikenne

a

Pää hakusanat punainen auto vanha Käsittelijä Petri

Kuvauspvm 1.5.90 П Liittyy tekstiin

Sisältö '

Värillisyys 4-väri H-vl Suunta |vaaka

a

Leveys 2-3 palstaa

I

I

[ Seuraava |

Kumoa

Kuva 1. Kouvolan Sanomien arkistojen luokittelukentät

Kuva-arkiston luokittelussa tulisi voida käyttää yhteisesti sovittuja sanoja siten, ettei samoista käsitteistä käytetä eri sanoja. Yhtenäisyyden saavuttamiseksi voidaan käyt­

tää valmiita luokittelusanastoja, kuten Helsingin Yliopiston Yleistä Asiasanastoa /6/

tai Sanomalehtien Liiton asiasanastoa. Yleisten sanastojen lisäksi on olemassa tie­

tylle kapealle sektorille tehtyjä asiasanastoja, kuten esimerkiksi Taideteollisuuden asiasanasto. Valmiita sanastoja joutuu käytännössä laajentamaan käyttöalueen mu­

kaan esimerkiksi paikkakunta- ja asiakohtaisilla sanoilla.

Luokittelu muodostaa aikaavievimmän osuuden kuva-arkiston toteuttamisessa. Sii­

hen ei kiinnitetä riittävästi huomiota kuva-arkistoja suunniteltaessa1, vaan esimerkik­

si sanastojen annetaan kertyä ajan mittaan. Tämä voi johtaa suunnittelemattomaan lopputulokseen ja arkiston käyttökelpoisuuden heikkenemiseen materiaalin löyty­

misen kannalta. Arkiston luokittelusta löytyy hyvä esitys viitteessä /7/ sekä viittessä

/8/.

2.2 Tekstihaku arkistosta

Monipuoliset hakuominaisuudet ovat tärkeä osa kuva-arkistoa. Relaatiotietokanta- mainen kenttähaku ei enää yksin riitä, tarvitaan tekstihaun monipuolisia mahdolli­

1 Käytännön kokemukset Piccolon asiakkaiden parissa ovat osoittaneet, että yksi ihminen voi skannata ja luokitella laadukkaasti saman päivän aikana enintään 40 kuvaa.

suuksia. Haku luokittelutiedon mukaan voi tapahtua kahdella perustavalla: vapaalla tekstihaulla ja aiheen mukaisella haulla.

2.2.1 Tekstihaku luokittelutiedosta

Vapaa tekstihaku tarkoittaa luokiteltujen kuvien hakua siten, että mikä tahansa luo­

kittelussa esiintyvistä sanoista voi toimia hakusanana. Haettava sana voi siis olla esi­

merkiksi keskellä kuvatekstiä ja se voi esiintyä taivutetussa muodossa.

Pelkkä yhden sanan etsiminen ei riitä, vaan tarvitaan monipuolisempia hakuehtoja.

Useimmat kuva-arkistot tukevat jonkinlaisia hakulausekkeita, joilla hakuja voi moni­

puolistaa. Hakulauseke voi olla esimerkiksi seuraavanlainen: kissa* or koira*.

Edellisellä hakulausekkeella etsittäisiin kaikkia niitä kuvia, joiden luokittelussa esiintyy kissa- tai koira-sanalla alkava sana.

Hakulausekkeiden syntaksi ja syöttötapa vaihtelevat huomattavasti eri kuva-arkisto- ohjelmistojen välillä. Yhä useimissa Windows- ja Macintosh-ohjelmissa on mahdol­

lista syöttää hakulauseke graafisen käyttöliittymän kautta. Käytännössä pitempään arkistoja käyttäneet pitävät enemmän komentorivipohjaisesta hakulausekkeen syö­

töstä. Seuraavassa taulukossa on esitetty esimerkkinä Piccolo- ja Mopsi-kuva-arkis- tosovellusten hakulausekkeiden syntaksi /9/.

Taulukko 3. Esimerkki vapaan tekstihaun operaattoreista.

operaattori selite

+ ja

» tai

- ei

? mikä tahansa merkki

* mitä tahansa merkkejä

sarja kahden numeron välillä, esimerkiksi 10:50 antaa kaikki luvut väliltä 10-50

& fuzzy-haku, joko Levenstain-pohjainen muutosetäisyyshaku tai soun- dex-algoritmiin perustuva haku

« == » sanojen esiintymisen lukumäärään perustuva haku O sulut hakuehtojen loogiseen ryhmittelyyn

/,/ läheisyyshaku, jolla määritellään sanojen etäisyys toisistaan

Jotta vapaa tekstihaku toimisi tehokkaasti suomen kielen kanssa, tulee sen tukea tai­

vutusmuotoja. Taivutusmuotojen tuki tarkoittaa käytännössä sitä, että ohjelmisto muodostaa sanasta hakulausekkeen, joka sisältää sanan eri taivutusvartalot. Näin esimerkiksi sanan hallitus taivutusvartalot ovat hallituks ja hallitus. Taivutusvartaloa käytetään hakulausekkeen luomiseen. Sanan hallitus taivutusvartaloista luodaan seu­

raavanlainen hakulauseke: hallituks*,hallitus*. Toinen vaihtoehto taivutusmuotojen tuelle on sanojen tallentaminen arkistoon perusmuodossaan. Tällöin sanat muutetaan arkiston päivityksen yhteydessä perusmuotoonsa.

Taivutusvartaloiden luonti aiheuttaa ajoittain epätarkkuutta hakuihin. Varsinkin ly­

hyistä sanoista tulee lyhyitä taivutusvartaloita, joiden perusteella tulee helposti vääriä osumia. Väärät osumat voidaan suodattaa siten, että löydetty sana ja hakusana muunnetaan perusmuotoon ja niitä verrataan toisiinsa. Jos molemmat sanat ovat pe­

rusmuodossaan samat, hyväksytään osuma. Tämä käänteistarkistus vaatii tietysti paljon laskentatehoa haun suorittavalta tietokoneelta.

Vapaa tekstihaku vaatii perinteisestä relaatiotietokannasta poikkeavaa tietokantasys- teemiä ja hakualgoritmeja toimiakseen tehokkaasti. Tästä johtuen kaikissa kuva-ar- kistojärjestelmissä ei ole ollut vapaata tekstihakua, vaan haku on rajoittunut ko­

konaisten luokittelukenttien hakuun.

2.2.2 Aiheen mukainen haku

Yksinkertaisimmillaan aiheeseen perustuva haku on tietyn hakusanan etsimistä luo­

kittelutiedon avulla ja niiden kuvien näyttäminen, missä ko. hakusana esiintyi. Ai­

heen mukaista hakua voidaan tehdä myös aihehierarkian avulla. Tällöin laajemman käsitteen avulla voidaan etsiä kuvia, joissa esiintyy käsitteen alakäsitteitä. Esimerkki (Taideteollisuuden asiasanastosta):

tekstiilit

S T arvotekstiilit

kansanomaiset tekstiilit kirkkotekstiilit

kodintekstiilit sairaalatekstiilit sisustustekstiilit taidetekstiilit vaatetustekstiilit

RT kankaat

ST tarkoittaa suppeampaa termiä ja RT rinnakkaistermiä. Kun esimerkiksi tehdään aihehaku sanalla tekstiili, löydetään kaikki tekstiilit-käsitteen alakäsitteet. Tälläisissä hauissa on usein ongelmana se, että kuvia löytyy liikaa. Sopivalla hakulausekkeiden käytöllä voidaan aiheen mukaisia hakuja yhdistää ja pienentää löytyneiden kuvien määrää.

2.3 Kuva-arkistojen tekniikkaa

2.3.1 Toteutusperiaate

Kuva-arkiston tietokannan toteutusperiaate kuuluu johonkin seuraavista: relaatiotie­

tokanta, täysteksti tai hakemistopohjainen. Relaatiotietokanta on tietokanta, jossa ennalta määritetyt kentät tai sarakkeet on indeksoitu b-puu-tyyppisellä indeksillä.

Relaatiotietokannasta voi tehdä hakuja tyypillisesti SQL-kielen avulla. Relaatiotieto­

kanta sopii hyvin kenttämuotoisen tiedon tallennukseen.

Täystekstitietokanta on tietokanta, jossa jokaisen artikkelin jokainen sana voi toimia haun avaimena. Täystekstitietokannassa jokaisesta sanasta voidaan palauttaa artikke-

lit, joissa ne esiintyvät. Koska avaimia on hyvin suuri määrä, ovat täystekstitieto- kannan tekniset ratkaisut erilaisia verrattuna relaatiotietokantaan /10/. Täystekstitieto- kanta soveltuu parhaiten hakuihin, jossa etsitään tietyn sanan esiintymää.

Hakemistotietokanta on yksinkertainen tiedosto, johon on tallennettu kuvien luokit­

telut. Haku hakemistosta tapahtuu merkkijonohaulla, jossa koko tiedosto pitää käy­

dä läpi kaikkien esiintymien löytämiseksi.

Kuva-arkistot voidaan jakaa kahteen luokkaan sen mukaan, minkälaisia kuvia ne si­

sältävät. Uusia kuvia sisältävät arkistot ovat lähiarkistoja. Lähiarkistot tallennetaan nopeille tallenteille, kuten esimerkiksi kovalevyille ja RAID-jäijestelmään. Pitempi­

aikaiseen varastointiin käytetään kiinto- ja irtolevyjä, CD-ROM:a, optisia levyjä ja nauha-asemia. Usein kuvat tallennetaan ensin lähiarkistoon ja siirretään ajan kulues­

sa pitkäaikaisarkistoon.

2.3.2 Resurssien käyttö

Arkistoitavien kuvien koko riippuu paljon kuvilta vaaditusta laadusta ja käytetystä pakkausmenetelmästä. Taulukossa 2 on esitetty tuloksia kuvien pakkaamisesta.

Käytännössä yksi kuva vie arkistosta n. 0,1-20 megatavua. Alkuperäisen kuvan li­

säksi esikatselukuvat vievät tilaa arkiston tallenteilta. Niiden koko on luokkaa 10- 200 kilotavua pakattuna JPEG-pakkauksella.

2.3.3 Suorituskyky

Kuva-arkiston suorituskykyä voidaan arvioida kahden pääperiaatteen mukaan /7/.

Ensimmäinen arviointiperiaate on arkistoinnin suorituskyky. Luokittelussa tehok­

kuutta voidaan arvioida hakusanojen käytön luotettavuutena, luokittelun käyttöliit­

tymän tehokkuutena sekä kuvatiedostojen arkistoinnin tehokkuutena. Kuvatiedosto­

jen arkistoinnin tehokkuus tarkoittaa sitä, kuinka helposti skannattu kuva saadaa ar­

kistoitua lopulliseen sijoituspaikkaan.

Hakusanojen käytön tehokkuus riippuu paljolti sen käyttöliittymän tehokkuudesta, jolla hakusanoja luokitteluprosessissa käytetään. Oikea hakusana pitää löytyä hel­

posti ja intuitiolla. Seuraavassa kuvassa on esitetty Piccolon hakusanojen käyttö­

liittymä, jonka avulla sanastojen hierarkiaa voi selailla kätevästi.

Hakusana: tanssi

Laajemmat termit: Rinnakkaistermit: Suppeammat termit:

harrastukset taide ja kulttuuri urheilulajit

baletti diskotanssit jazztanssi kansantanssit kilpatanssi moderni tanssi

Käytä: taide ja kulttuuri

Lisää Kumoa I OK

Kuva 2. Piccolon hakusanojen käyttöliittymä

Toinen kuva-arkistojen suorituskyvyn arviointiperiaate on kuva-arkiston ohjelmis­

ton suorituskyky. Se voidaan jakaa edelleen kuva-arkiston tietokannan päivittämisen ja haun suorityskyvyiksi. Tietokannan suorituskyky riippuu paljolti palvelimen ja tietokantaohjelmiston suorituskyvystä. Samoista tekijöistä riippuu myös haun suo­

rituskyky, joskin käytetyillä algoritmeilla on myös suuri merkitys haun suoritus­

kyvyssä.

3. Visuaalinen sisältöhaku

Sisältöhaku on kuvan visuaalisten ominaisuuksien hyödyntämistä kuva-arkistojen hauissa. Kuvien tekstuaalisella luokittelulla ei pystytä kuvaamaan kuvan koko si­

sältöä. Esimerkiksi tekstuuria ja muotoa on vaikea esittää sanallisesti. Lisäksi luokit­

telun laatuja kuvissa olevien asioiden tärkeys vaihtelee luokittelijasta toiseen /11/.

Kun kuvien määrä kasvaa, tulee jokaista hakusanaa kohden paljon kuvia. Kun ha­

kusanalla löytyy liikaa kuvia, ei kuva-arkiston tekstimuotoinen haku täytä tehtävään­

sä. Kuvien sisältöhaulla on yritetty korjata tätä puutetta tuomalla hakuun mukaan kuvasta automaattisesti erotettavia visuaalisia piirteitä.

Visuaalisen sisältöhaun kokonaisuus voidaan esittää seuraavalla kuvalla.

Kuva Käyttäjä

Ominaisuuksien erotus Väri Tekstuuri Muoto

Haun käyttöliittymä Indeksit/suodatus

Visuaalisten ominaisuuksien vertaulu

Tulosten esittäminen

Käyttäjä

Kuva 3. Visuaalisen haun toimintaperiaate

Kuvista erotetaan visuaaliset ominaisuudet, jotka tallennetaan tietokantaan. Käyttäjä syöttää hakehtona toimivan kuvan, jonka ominaisuuksia vertaillaan tietokannassa sijaitseviin kuviin joko indeksoinnin avulla tai suodatuksella. Vertailun tulokset esi­

tetään käyttäjälle perustuen etäisyyten ominaisuuksien välillä.

3.1 Visuaaliset ominaisuudet

Visuaalisia ominaisuuksia ovat esimerkiksi väri, muoto ja tekstuuri. Kun näitä omi­

naisuuksia käytetään kuvien vertailuun, puhutaan visuaalisesta sisältöhausta. Omi­

naisuudet voivat olla joko paikallisia tai globaaleja. Paikalliset liittyvät tietylle alueel­

le rajautuviin ominaisuuksiin kun taas globaalit ominaisuudet ulottuvat koko kuvan alueelle. Visuaalisten ominaisuuksien tasot voidaan jaotella seuraavan kaaviokuvan mukaisesti.

korkea taso

lokaalit

globaalit

matala taso

Kuva 4. Visuaalisten ominaisuuksien tasot

Ominaisuudet voidaan jakaa kolmeen tasoon toteutuksen vaikeuden ja hyödyllisyy­

den mukaan: hahmoihin, piirteisiin ja olioihin /12/.

Visuaalisten ominaisuuksien tallennus voidaan tiivistää seuraavaan lainaukseen:

"Muutetaan tietorikas pikselidata kompaktiksi visuaalisesti merkittävien ominaisuuk­

sien esitykseksi" /13/.

3.1.1 Matalan tason ominaisuudet

Yksinkertaisimpia visuaalisia ominisuuksia ovat hahmot. Tyypillinen hahmon käyttö ominaisuutena on tietyn bittikartan etsiminen kuvasta. Koska asiat esiintyvät kuvissa hyvin erilaisissa orientaatioissa, ei hahmojen käytöllä pystytä saavuttamaan hyviä hakutuloksia.

Toinen ominaisuuksien taso on piirteet (stuff). Piirteet ovat paikallisia tai globaaleja ominaisuuksia, kuten esimerkiksi reuna, välialue tai värijakauma. Nykyiset visuaa­

liset hakujärjestelmät perustuvat pääasiassa piirteiden käyttöön.

Hahmot ja piirteet muodostavat konkreettisten ominaisuuksien ryhmän. Hahmojen käytöstä ei ole paljoakaan hyötyä visuaalisessa haussa, mutta piirteillä voidaan saa- daa kohtalaisen hyviä tuloksia aikaan.

3.1.2 Korkean tason ominaisuudet

Ylin taso ominaisuuksilla on oliot (things). Ne ovat korkean tason ominaisuuksia, kuten esimerkiksi käsite silinteripäisestä Kekkosesta. Olioita ei nykyisin menetelmin pystytä luotettavasti erottamaan. Joitain yksinkertaisia esimerkkejä on toteutettu, ku­

ten viitteessä /12/ esitetty hevosia kuvista tunnistava menetelmä.

Oliot ovat abstrakteja ominaisuuksia. Ihmiset ovat kiinnostuneita olioista, mutta ny­

kyiset tietokonesovellukset eivät pysty ominaisuuksien korkeamman tason käsitte­

lyyn. Koska oliot rakentuvat osittain piirteistä, voidaan piirteitä yhdistelemällä saada aikaiseksi rajoitettuja olioiden hakualgoritmeja /14/. Ominaisuuksien indeksointi vaatii käytännössä ihmisistä. Perinteinen luokittelu on kuvan ominaisuuksien tallen­

tamista.

-hahmot- - - piirteet — oliot —

3.1.3 Kuvan sisältö: objektit ja tausta

Kuvan sisältö voidaan karkeasti jakaa kahteen osaan: objekteihin ja taustaan.

Useimmiten käyttäjää kiinnostaa enemmän kuvassa esiintyvät objektit, ei niinkään tausta. Ominaisuuksien erottamisen kannalta objektien ja taustan erottaminen toisis­

taan parantaa visuaalisen sisältöhaun laatua. Rajatuilla kuvajoukoilla objektien erotus onnistuu käyttäen segmentointia (kts. sivu 24), mutta satunnaisilla reaalimaailman kuvilla objektien erotus vaatii ihmisen suorittamaan segmentointia. Erotuksessa voi­

daan käyttää apuvälineitä, kuten väritysalgoritmeja ja käärmealgoritmeja /14/, jotka löytävät objektin rajat kunhan riittävä määrä vihjeitä on annettu. Kun kuvasta tiede­

tään objektit, voidaan objektien ja taustan ominaisuudet erottaa toisistaan.

3.2 Väri

Kuvan vaikutelma syntyy aiheesta, rakenteesta ja väreistä. Tärkein tekijä niistä on väri /15/. Jos kuvassa on väriä, muodostuu vaikutelma muutaman hallitsevan väri- alueen perusteella. Ihmisen silmä näkee värit suhteellisesti paljon tarkemmin kuin yksityiskohdat.

Kuvan värit voidaan kuvata sekä paikallisesti että globaalisti histogrammin avulla.

Histogrammi määritellään harmaasävykuvasta laskemalla valitun alueen erillisten harmaasävyjen määrät. Värikuvasta voidaan laskea histogrammi kullekin osavärille erikseen tai jakamalla väriavaruus rajattuun määrään osia eli kvantisoimalla. Globaali histogrammi lasketaan koko kuvan alueelta kun taas paikallinen rajoitetulta kuvan alueelta. Histogrammia käytetään visuaalisessa haussa laskemalla vertailtavien ku­

vien histogrammien etäisyys.

Paikalliset väriominaisuudet voidaan laskea erottamalla merkittävät välialueet. Väri- alueilla voidaan kuvata melko hyvin kuvan rakenne ja käyttää niitä hyväksi visuaali­

sessa haussa. Myös paikallisten objektien haku on mahdollista toteuttaa välialueilla.

3.2.1 Väriominaisuuksien erottaminen kuvasta

Histogrammin muodostaminen kuvasta on melko yksinkertainen toimenpide /16/ ss.

144-149. Kuvasta valitun alueen pikselit käydään läpi kaikille osaväreille ja jokaisen pikselin arvon indeksoimaa taulukkoarvoa kasvatetaan yhdellä. Näin saadaan lasket­

tua kuvassa esiintyvien värien määrät eli todennäköisyydet tietyn värin esiintymiselle kuvassa. Histogrammien käytön ongelmat liittyvät lähinnä hakuun.

Paikallisesti värit voidaan kuvata välialueiden avulla. Välialue on yhtenäinen saman värin täyttämä alue kuvassa. Reaalimaailman kuvissa on usein jopa miljoonia värejä, mikä on värialuiden muodostamisen kannalta liikaa. Tämän vuoksi väriavaruutta su­

pistetaan voimakkaasti kvantisoimalla. Kvantisointia varten kuva muunnetaan RGB- väriavaruudesta helpommin käsiteltävissä olevaan väriavaruuteen kuten HSV /17/ tai Munsell /15/. Muunnetusta kuvasta etsitään segmentoinnin avulla yhtenäisiä alueita.

Segmentointi on yhtenäisten aluiden erottamista kuvasta, jossa alueet täyttävät tietyn

ominaisuuden. Luvussa 4. on esitetty tarkemmin erään paikalliseen väriin perustu­

van menetelmän toteutus.

3.2.2 Haku väriominaisuuksilla

Haku värialuiden perusteella voidaan toteuttaa helposti. Taulukossa sivulla 35 on esitetty Piccolon värialuiden tallentamisessa käyttetty piirre. Tämä piirre voidaan tallentaa esimerkiksi relaatiotietokantaan. Tietokannasta värialuiden piirrevektoreita voidaan hakea esimerkiksi SQL-lausekkeiden avulla.

Histogrammien avulla tapahtuva haku toteutetaan siten, että hakuehtona toimivan kuvan ja vertailtavan kuvan histogrammien välinen etäisyys lasketaan. Etäisyys määrittelee kahden kuvan värijakaumien samanlaisuuden. Se voidaan laskea esimer­

kiksi histogrammien erotuksen neliöiden summana. Neliösummaan perustuva etäi­

syys voidaan laskea seuraavalla kaavalla /18/.

\\Z\\ = ZTSZ (1)

Missä Z =X-Y, X on hakuhtona toimiva histogrammi, Y on arkistoidun kuvan his­

togrammi, S on symmetrinen värien samankaltaisuutta kuvaava matriisi, jonka ele­

mentti s(i,j) kuvaa värien / ja j samankaltaisuutta. S rakennetaan käsin.

Koska etäisyyden laskenta tapahtuu jokaiselle kuvalle erikseen, tulee isojen kuva- määrien yhteydessä ongelmaksi pitkät laskenta-ajat. Ongelman ratkaisemiseksi on kehitetty erilaisia menetelmiä. Yksi tapa on suodattaa kuvajoukosta potentiaaliset kuvat, joille lasketaan histogrammien etäisyyspiirre /19/. Suodatus voidaan toteuttaa laskemalla painotettu keskiarvo histogrammin väreistä, jossa keskiarvo on kolmi­

ulotteinen vektori. Kahden kuvan keskiarvovekotoreille voidaan laskea etäisyys (keskimääräinen värietäisyys), jonka avulla valitaan tarkempaan histogrammi- etäisyyslaskentaan otettavat kuvat /20/.

3.3 Tekstuuri

Tekstuuri on pinnan ominaisuus. Tekstuuri on ominaisuus, joka kuvaa harmaa- sävyjen spatiaalista jakautumista kuvan tai sen osan alueella. Kuvissa tekstuurit koostuvat pikseliarvoista jotka voivat toistua säännöllisesti, melkein säännöllisesti tai sattumanvaraisesti. Kuvan alueella on vakiotekstuuri jos kuvafunktion paikalliset ominaisuudet ovat vaikiot, hitaasti muuttuvat tai likimääräisesti toistuvat.

Tekstuurit ovat apuna, kun aivot määrittävät olioiden kolmiulotteisia ulottuvuuksia.

Tasaisessa valossa esitetystä tasaisesta pinnasta ilman tekstuuria on vaikea hahmot­

taa syvyyttä.

Tekstuuri on paikallinen ominaisuus. Vaikka kuvalla voi olla koko kuvan alan täyt­

tävä toistumaton tekstuuri, on tekstuuri yleensä jossain määrin toistuva ominaisuus kuvassa tai sen osassa.

Kuvasssa esiintyviä tekstuureja on vaikea määritellä tekstiin perustuvalla luokittelu­

järjestelmällä. Tästä syystä tekstuuriominaisuuksien luokittelu automaattisesti on hyvin houkutteleva ajatus.

3.3.1 Menetelmiä tekstuuriominaisuuksien erottamiseksi

Tekstuurien erottamiseen ja käyttämiseen visuaalisessa haussa liittyy kuvakulman ja valaistuksen ongelma. Koska kuvissa projisoidaan kolmiuloitteista avaruutta kaksi­

ulotteiseen kuvaan, muuttuvat samanlaiset tekstuurit eri kuvakulmista esitettynä.

Myös valaistusolosuhteet muuttavat tekstuurien ulkoasua.

Kuvan segmentointi tekstuurien avulla on vaikea ongelma, minkä vuoksi merkittävät tekstuuritalueet joudutaan osoittamaan kuvasta käsin. Kirjallisuudessa esitetyt me­

netelmät on kehitetty tekstuurien tunnistamiseen kuvista siten, että kuvassa esiintyy yhtä tekstuuria, joka on kuvattu samassa valaistuksessa samasta kuvakulmasta.

Tekstuuriominaisuuksien erottamismemetelmiä ovat mm. yhteismatriisit , Markovin satunnaiskenttä, fraktaalit ja spatiaalitaajuustekniikat /17/ /21/. Eri menetelmissä py­

ritään esittämään tekstuurien ominaisuudet siten, että niistä pystytään muodostamaan ominaisuusvektori.

3.4 Muoto

Muoto kuvaa kuvan rakennetta. Kuvassa esiintyvät reunat ja vastaavat rakenteet muodostavat yhtenäisiä ja epäyhtenäisiä muotoja. Muodoista on hankalampi erottaa ominaisuuksia kuin väristä ja tekstuurista, koska muoto on monimutkaisempi visu­

aalinen käsite kuin väri ja tekstuuri. Väriä ja tekstuuria varten tarvitaan muutamia tai kymmeniä piirteitä, kun taas muotoa varten tarvitaan jopa useita satoja esittäämään muodon ominaisuudet tarkasti /22/.

Muoto-ominaisuudet voidaan erottaa sekä tekstuuri- että geometristen ominaisuuk­

sien perusteella /23/. Geometrisia ominaisuuksia käytetään mustavalkokuvien muo­

to-ominaisuuksien luomiseen, kun taas tekstuuriominaisuuksien harmaasävy- sekä värikuvien yhteydessä. Yksi tapa laskea muodon ominaisuudet on Curvature Scale Shape, CSS /22/. Se perustuu kuvasta erotetun reunan ominaisuuksien koodaami­

seen kompaktiin esitykseen.

3.5 Muut ominaisuudet

3.5.1 Liike

Elokuva on visuaalisen haun kannalta pitkä sarja perättäisiä kuvia. Jokaisesta eloku­

van kuvasta ei ominaisuuksia kannata erottaa. Siksi elokuva jaetaan otoksiin, jotka sisältävät kukin yhden "tapahtuman" kokonaisuudesta /14/. Otokset voidaan erottaa toisistaan automaattisesti esimerkiksi globaalin värin tai spatiaalisiin ominaisuuksiin perustuen. Jokaisesta otoksesta valitaan yksi kuva, ns. r-frame edustamaan ko.

otosta. R-frame:lie lasketaan samat ominaisuudet, kuin yksittäisille kuvillekin.

Elokuvalle voidaan muodostaa myös sille ominaisia ominaisuuksia. Kiinnostavia ominaisuuksia on objektien liike kuvissa ja staattisten ominaisuuksien muutos otok­

sen sisällä. Kahden kuvan välille voidaan pikseleille laskea ns. optical flow field /23/, joka määrittelee gradientin pikselien liikkeestä kahden kuvan välillä.

3.5.2 Hahmotelma

Hahmotelma on voimakkaasti pienennetty versio kuvasta, joka on muutettu musta­

valkoiseksi. Tyypillisesti hahmotelman dimensiot ovat 64x64x1 bittiä /18/. Redusoi­

tu hahmotelma voidaan tallentaa sellaisenaan tietovarastoon, josta haut tehdään ver­

tailemalla käyttäjän piirtämää hakuehtoa tietovarastossa sijaitseviin kuviin.

3.6 Haku

Haku visuaalisten ominaisuuksien avulla tarkoittaa samankaltaisuuden määrittämistä kuvien välillä. Samankaltaisuutta mitataan suhteessa ominaisuuksiin, joista ollaan kiinnostuneita. Useimmiten samankaltaisuuden mittana kahden kuvan välillä käyte­

tään jotain muotoa Euklidisesta etäisyysfunktiosta /18/.

Visuaalinen haku voi tapahtua esimerkin tai hahmotelman perusteella. Esimerkki- haussa käytetään jo olemassa olevaa kuvaa esimerkkinä, jonka mukaan haku teh­

dään. Esimerkkikuvasta muodostetaan ominaisuudet, joita sitten verrataan arkistoi­

tujen kuvien ominaisuuksiin. Hahmotelman mukaan haettaessa käyttäjä luo erityisel­

lä kuvamuokkaimella hahmotelman, joka sisältää käytettäviä ominaisuuksia (väri- alueita, tekstuureja jne). Hahmotelmasta erotetaan ominaisuudet, joita verrataan ar­

kiston kuviin.

Visuaaliselle haulle tulee usein määrittää herkkyys, jolla haku tapahtuu. Herkkyys tarkoittaa sitä kynnystä, jolla vertailtavat kuvat katsotaan riittävän samankaltaisiksi.

Kynnys on tarpeellinen, koska hakutilanteen tarpeita ei voi ennakoida etukäteen. Jos arkistossa on suuri määrä kuvia pitää kynnyksen olla melko korkea.

3.6.1 Haun toteutus

Haun toteutus riippuu piirteiden tallennustavasta. Jos piirteet voidaan laskea etukä­

teen on haun toteutus indeksoinnin avulla usein mahdollista. Perinteinen B-puuhun perustuva indeksointi ei ole useinkaan riittävän tehokas moniuloitteisten ominai­

suuksien tallentamiseen /19/. Siksi käytetään mm. nelipuuta, K-D-puuta ja R*-puu- ta, joiden soveltuvat paremmin moniuloitteisen tiedon tallennukseen.

Jos piirre on riittävän moniuloitteinen, pitää haku tehdä vertailemalla hakuehtona toimivan kuvan ominaisuuksia arkistoitujen kuvien ominaisuuksiin yksi kerrallaan.

Suurissa kuva-arkistoissa vertailu voi olla hyvin hidasta. Siksi vertailussa käytetään apuna suodatusta, jolla sopivia kandidaatteja vodaan valita ennen ominaisuuksien täysimittaista vertailua /19/.

3.6.2 Haun käyttöliittymät

Visuaalisen haun hakuehtona toimii kuva. Tämä kuva tulee voida "syöttää" hakusys- teemiin riittävän helposti ja monipuolisesti. Haun syöttämiseen on kaksi perustapaa:

esimerkki ja hahmotelma.

Esimerkin avulla haku tapahtuu kuten "näytä samankaltaiset kuvat", jossa samankal­

taisuus on määriteltävä suure. Seuraavassa kuvassa on esitetty PhotoDisc, Inc.iin WWW-pohj ai sen kuva-arkiston esimerkkiin pohjautuva visuaalinen haku.

Basic Search ■ Power Search

Find Visual Matches

Search within keywords or leave keyword field blank to search entire collection.

LSO16588

Flamenco Dancer

Color matters

Composition matters Texture matters Structure matters

Some Lots

I

Tom last searched for tkese keymorls:

’dance'

Enter kefmords to limit this search:

Shorn me:

9 images per page

Kuva 5. Visuaalinen haku esimerkin avulla

Käytettävät samankaltaisuuden suureet tulee yleensä yksinkertaistaa muutamiin va­

lintoihin, jotta käyttäjät pystyvät tekemään valintoja niiden perusteella.

Toinen tapa hakuehtona toimivan kuvan syöttöön on hahmotelman luominen. Tähän tarvitaan erityinen muokkain (editori), jolla hakuehtona toimiva kuva luodaan.

Muokkain on useissa esimerkeissä (/13/, /14/, /17/) ollut yksinkertaistettu kuvan- muokkausmoduli, jossa on toteutettu käytettyihin ominaisuuksiin sopivat työkalut.

Seuraavassa kuvassa on esimerkkinä QBIC-jäijestelmän värieditori, jolla voidaan luoda hakuehtona toimiva histogrammi.

Kuva 6. Visuaalisen haun histogrammieditori

QBIC-projektissa käytetty hakujärjestelmä on jaettu kolmeen tasoon /24/. Korkeim­

pana tasona on kyselyikkuna (Query Window). Siinä esitetään hakuehdot koottuna siten, että yhtä hakuehtoa esittää yksi ikoni. Kyseyikkunaan voidaan kerätä useita eri hakuehtoja, joiden perusteella haku tehdään. Seuraavalla tasolla on piirreikkuna (Feature Window), jossa määritellään, mitkä ominaisuudet otetaan mukaan ja mikä ominaisuuksien painoarvot toisiinsa nähden ovat. Alimpana hierarkiassa on yksit­

täisten ominaisuuksien muokkausikkunat. Ominaisuudet voidaan määritellä joko ko­

ko kuvalle tai kuvasta erotetuille objekteille (kts. Kuvan sisältö: objektit ja tausta si­

vulla 18). Ominaisuudet voidaan määritellä joko esimerkin perusteella tai ominaisuu­

den sovitetulla muokkaimella.

3.6.3 Visuaalinen haku tekstin perusteella

Ominaisuuksien haku on järkevää myös tekstuaalisen kuvauksen perusteella. Jos kuvasta on tallennettu esimerkiksi globaalit väriominaisuudet, voi sopivalla värien koodauksella hakuehto "jonkin verran sinistä" olla käyttökelpoinen /25/ /14/. Myös paikalliseen väriin ja tekstuuriin pohjautuvat ominaisuudet ovat haettavissa tekstiku- vausten perusteella, esimerkiksi "keltaiset ympyrät" tai "vihreä puutekstuuri". Visu­

aalisten piirteiden tuominen tekstimuotoiseen hakuun täydentää hyvin perinteisiä tekstipohjaisia hakujärjestelmiä.

3.7 Segmentointi

Segmentointi liittyy useisiin visuaalisessa haussa käytettyihin algoritmeihin. Esi­

merkiksi QBIC-projektissa /14/ histogrammeihin perustuvassa väriluokittelussa merkittävät alueet segmentoidaan käsin. Segmentointi on hyvin keskeinen ongelma tietokonenäössä, jonka puitteissa sitä on tutkittu paljon.

Kuvan segmentoinnissa kuva jaetaan alueisiin, jotka kuuluvat johonkin luokkaan /26/. Segmentointia käytetään myös kun halutaan tunnistaa jokin kohde kuvasta.

Segmentointitavat voidaan jakaa kahteen luokkaan. Ensimmäinen luokka on globaa­

lisiin ominaisuuksiin kuten histogrammin mukaan tehtävä segmentointi. Toinen seg­

mentoi nti tapa on paikallisiin spatiaalisiin ominaisuuksiin perustuva segmentointi.

Useimmiten kuvan segmentointiin käytetään molempien luokkien yhdistelmää.

Segmentointi voidaan jakaa luokkiin myös sen mukaan, kuinka pitkälle se voidaan suorittaa automaattisesti. Esimerkiksi värialueitten mukaan tehtävä segmentointi voi­

daan toteuttaa täysin automaattisesti, mutta tekstuureihin perustuva segmentointi vaatii usein ihmisen avustusta

3.8 Ominaisuuksien tallennus

Jotta ominaisuudet voidaan tallentaa, kuvasta täytyy voidaan erottaa piirteet tai piir­

rettä kuvaavia suureita etukäteen. Ominaisuudet voidaan erottaa kuvasta automaatti­

sesti, puoliautomaattisesti tai käsin. Puoliautomaattisuus tarkoittaa ihmisen osallis­

tumista kuvien ominaisuuksien erottamiseen. Suurien kuvamäärien ollessa kyseessä tarvitaan täyttä automatiikkaa, mutta esimerkiksi tärkeimpien tekstuurialueiden osoittaminen käsin on nopea toimenpide perinpohjaiseen tekstiluokitteluun verrattu­

na.

3.8.1 Tietorakenteet

Ominaisuuksiin liittyy usein suuri dimensionaalisuus, joka vaikeuttaa niiden indek­

sointia. Tekstipohjaisen tiedon indeksoinnissa on käytetty В-puu ja sen johdannaiset (B - ja B+-puu) eivät sovellu hyvin moniulotteisen tiedon indeksointiin /27/. Tätä ongelmaa ratkaisemaan on kehitetty useita menetelmiä, joilla voidaan indeksoida laa­

joja tietorakenteita tehokkaasti.

Eräs tapa nopeuttaa moniulotteisen ominaisuuksien hakua on hajoittaa tieto siten, et­

tä perinteisiä indeksointimenetelmiä voidaan käyttää. Kuva voidaan muuntaa 2-ulot- teiseksi merkkijonoksi, joissa säilyy tieto kuvan objekteista. Toinen tapa on muun­

taa kuva käyttäen perinteisiä matriisilaskennan hajotelmia, kuten K-L-hajotelma /18/.

Moniulotteisella indeksointimenetelmällä voidaan nopeuttaa piirrevektoreihin perus­

tuvia hakuja. Näitä indeksointimenetelmiä ovat mm. k-d-puu, R-puu ja SS-puu.

Nelipuu on binääripuun laajennus, joka on käsittää useamman ulottuvuuden. Neli- puusta on edelleen kehitetty k-d-puu ja k-d-b-puu, jotka parantavat nelipuun ominai­

suuksia levytilankäytön ja algoritmisen tehokkuuden suhteen.

b-puuhun perustuvia laajennuksia ovat R-puu, R+-puu ja R-puu. R-puut ovat pui­

ta, joiden kaikki haarat ovat yhtä korkeita. R-puun lehtinä on rakenne, jossa on viit­

taus objektiin tietokannassa sekä objektin rajoittava suorakaide (bounding box). R- puun solmut sisältävät viittaukset alempiin puun osiin sekä rajoittavan suorakaiteen, joka sisältää alempien osien suorakaiteet. Seuraavassa kuvassa on esitetty R-puu ja alueet, joista se on luotu.

Kuva R-puu

4 A В

3 1 2 4 5 6

Kuva 7. R-puun muodostaminen

3.9 Evaluointi

Visuaalisen haun evaluointia ei voida tehdä täysin objektiivisesti, koska käsite visu­

aalinen samankaltaisuus on melko epämääräinen. Monilla visuaalisen haun mene­

telmät ovat toisensa poissulkevia tehokkuuden ja tarkkuuden välillä. Tämä tarkoittaa sitä, että jos halutaan vain “oikeita” osumia, jää tarkkuuden nimissä hyväksyttäviä kuvia pois löytyneiden joukosta. Jos taas halutaan “kaikki” mahdolliset kuvat mu­

kaan, tulee löytyneiden joukkoon väistämättä myös “vääriä” osumia/12/.

Hakualgoritmien evaluointi tehdään tutkimuksena, jossa usealta ihmiseltä kysytään samankaltaisuusindeksiä kuvaparien välillä. Tätä indeksiä verrataan sitten visuaa­

lisen haun tuodamiin tuloksiin. Jos ihmisen ja algoritmin tuottamat tulokset eivät poikkea olennaisesti toisistaan, voidaan algoritmin tuloksia kutsua hyviksi.

4. Visuaalisen sisältöhaun toteutus

Tämän diplomityön kokeellinen osuus käsittää visuaalisen sisältöhaun toteuttamisen Piccolo kuva-arkistoon. Toteutuksessa käytetään viitteessä /17/ esitettyä menetel­

mää, jossa erotetaan värialueita ja tekstuureja kuvista ja käytetään niistä muodostet­

tuja piirteitä kuvien hakuun.

4.1 Yleistä Piccolosta

Piccolo on diplomityön tekijän toteuttama dokumenttien hallintaan tarkoitettu ohjel­

misto, joka toimii Macintosh-ympäristössä. Piccoloa käytetään mm. kuva- ja teksti­

arkistona, dokumenttien hallintaohjelmana ja Internet-pohjaisena arkistona. Ohjel­

miston pääasiallinen käyttö on nykyään kuva- ja tekstiarkistoissa. Piccolo on saanut alkunsa vuonna 1993 Kouvolan Sanomille tehdyn asiakasprojektin tuloksena. Se on muuttunut vuosien varrella tuotteeksi, jota myydään Suomen lisäksi Ruotsissa ja Norjassa. Sitä käyttää noin 40 yritystä pääasiassa graafisessa teollisuudessa.

Piccolo koostuu kahdesta ohjelmasta, Tuutista ja Luupista. Tuutti on luokittelu- ohjelma, jonka avulla teksti- ja kuvatiedostoille syötetään avainsanat ja luokittelu- teksti. Luuppi on varsinainen arkisto-ohjelma, jolla ylläpidetään arkistoja ja tehdään hakuja. Piccolon toimintaperiaate on esitetty seuraavassa kuvassa.

Kuva.jpg

Tuutti

Kuva raahataan Tuutin päälle

Luuppi tallentaa luo­

kittelut ja esikatse- lukuvat arkistoon, joka sijaitsee tiedosto-

Kuva luokitellaan Tuutissa

Kuva kopioidaan tiedostopalvelimelle

Tiedostopalvelin

Luuppi hakee kuvat tiedostopalvelimelta, lukee niistä luokittelut sekä luo esikatseluku- vat

Käyttäjät tekevät hakuja arkistoon Luupilla.

Kjyá Luuppi

Haku WWW-selaimella Luupin Internet-liittymän kautta

Arkistoiva Luuppi

Kuva 8. Piccolon toimintaperiaate

Esimerkki Tuutin luokitteluikkunasta on esitetty sivulla 11. Tuutin luokkiteluikku- na voidaan muokata käyttötarvetta vastaavaksi. Luokittelussa voi käyttää apuna sa­

nastoja usealla eri tavalla. Jokaiselle kentälle voidaan määritellä putkahdusvalikko,

joka sisältää useimmin käytettävät luokittelusanat. Tämän lisäksi voidaan käyttää laajempia sanastoja. Piccoloon on toteutettu yleisen asiasanaston syntaksi sanasto- määrittelyille /6/.

Piccololla voi hallita tiedostoja niiden tyypistä riippumatta. Yksi ohjelmiston kantava idea on että ei oteta kantaa tiedostomuotoihin, vaan yritetään hyödyntää mahdolli­

simman paljon tiedostoista löytyvää informaatiota. Kuvatiedostoista (JPEG ja TIFF) luetaan niihin liitetyt kommentit. Photoshop-tiedostoista luetaan IPTC-kommentit, jotka sisältävät runsaasti tietoa kuvasta. Applen määrittelemät Macintosh-tiedostoihin

liitettävät standardikommentit luetaan.

Luupin arkistointi toimii siten, että arkistoon määritellään siihen kuuluvat hakemis­

tot. Indeksoinissa nämä hakemistot käydään läpi lukien tiedostoista niistä saatava in­

formaatio. Kuvatiedostoista pyritään muodostamaan esikatselukuvat sekä luetaan Tuutilla syötetyt sekä muut luokittelutiedot. Tekstitiedostoista pyritään lukemaan tekstisisältö, jolle tehdään oma indeksi. Myös tekstitiedostosta luetaan Tuutilla syö­

tetyt luokittelut.

Luupilla voi tehdä monipuolisia hakuja. Seuraavassa kuvassa on esimerkki rakentei- sesta hausta, jonka on tehty ikkunoidulla käyttöliittymällä.

Kuva 9. Esimerkki Piccolon rakenteisesta hausta

Haku voidaan tehdä myös hakulausekkeilla, joiden syntaksi on esitetty taulukossa sivulla 12. Indeksiin tallennettuja sanoja voi selailla haun yhteydessä. Hakutulokset esitetään ikkunassa, jossa hakuehtoa vastaavat dokumentit esitetään lista- tai ruuduk- komuotoisena luettelona. Seuraavassa kuvassa on esitetty esimerkki ruudukkomuo- toisesta hakutuloksesta.

Haun ••Kaikki" tulos 0B

Kohteita 30 Q Päivitetään | Ruudukko ▼ ) [ Päivitä out ifTätaa kuvat~)| Asetukset I Kenttä t : [ Tiedosto j Kenttä 2 : [ Kuvan selite ‘wJ Kenttä 3 : [ Kuvan avainsanat ^ J

16001.JPG

"Fell in Meine C. Meint

eastern scenic fall colo

16002.JPG

"Old Lobeter Buoy» C. f

eastern scenic fishi ngl

16003.JPG

"Boet Herbor in Meine

Scenic eastern Bar Her

16004.JPG

"Country Porch C. Mclr eastern scenic home ho

16005JPG

"Auguste Mai ne C. Mein eestern ece ni c river w<

1 6006.JPG 16007.JPG

"Signpost in Mai ne C. h "Yard in Mi note. Mcltf Scenic eastern tree» fel eastern ecenic fell colo

1600B.JPO

"Camden Mai ne C. Mein eastern ecenic town vil

Kuva 10. Esimerkki hakutuloksesta

Luupissa on useita jatkokäsittelymahdollisuuksia kuville. Usein tapahtuvia kopioin­

teja varten voidaan määritellä valmiiksi kohdehakemistoja. Dokumentit voidaan avata suoraan esimerkiksi Photoshop-ohjelmistolla. AppleScript-makrokielen avulla voidaan ohjelmoida uusia toimenpiteitä kuvien jatkokäsittelyyn.

Luupin Intemet-yhteys on toteutettu Luuppiin ns. cgi-tukena. Cgi-Luuppi toimii ha­

kukoneena Macintoshissa toimivalle WWW-palvelinohjelmistolle. Luuppi saa kyse­

lyt WWW-palvelijalta ja palauttaa sille hakutuloksen HTML-muodossa sekä JPEG- pakattuja esikatselukuvia. Dynaamisen HTML-määrittelyyn on Luupissa tehty ra­

porttigeneraattori, jolla voidaan määritellä palautettavan hakutuloksen ulkoasu.

Luuppi tukee myös WWW-palvelinten käyttöoikeusmekanismia, jolla saavutetaan kohtuullisen hyvä turvallisuustaso.

Macintosh Internet

Web-palvelin

Kysely Web-palvelimelta Hakutulos ja kuvat

Luuppi.cgi Kuva 11. Piccolon WWW-liittymän toimintaperitaate

Luupin arkisto on toteuttettu käyttäen New Generation Software Oy:n NDB:tä.

NDB on tietokanta, jossa strukturoidun tiedon lisäksi on tuki vapaalle tekstihaulle.

Tieto voidaan tallentaa NDB tietokantaan joko kenttämuotoisena tai vapaana teksti­

nä. NDB:n täysteksti-indeksointi perustuu muokatulle B+-puulle, jossa on muuttu­

van kokoiset avaimet /10/. Indeksointi tapahtuu aluksi keskusmuistissa josta avaimet

tallennetaan levylle, kun ennalta määritelty muistialue täyttyy. Tämän ansiosta in­

deksointi on nopeaa.

Luupin sisäisen toiminnan pääpiirteet on esitetty seuraavassa kuvassa.

Hahmotin

Visuaalinen haku

Kuvamuotokirjasto MacApp

Käyttöliittymän

käsittely Indeksointi Arkistot

Kuva 12. Piccolon Luupin sisäisen rakenteen periaate

Ohjelman runko perustuu Applen tekemään MacApp-luokkakirjastoon. Siinä on to­

teutettu Macintosh-ohjelman peruspiirteet, jolloin sovelluskehittäjän tulee luoda oh­

jelman tarvitsemat ainutlaatuiset piirteet. Luupin rakenne jakautuu kahteen osaan, arkistoon ja käyttöliittymän käsittelyyn. Arkisto käyttää kirjastoina NDB:tä, kuva- muotokirjastoa, visuaalisen haun kirjastoa sekä Hahmotinta. Kuvamuotokirjastossa on käytetty Internetissä vapaassa jakelussa löytyviä TIFF- ja JPEG-tiedostomuo- tojen kirjastoja. Hahmotin on Kielikone Oy:ltä lisensoitu kirjasto, jonka avulla on toteutettu suomen kielen taivutusmuotojen tuki.

4.2 Visuaalinen luokittelu

Valittaessa Piccoloon toteutettavaa visuaalista hakumenetelmää oli tavoitteena rat­

kaista seuraavat asiat:

• Hakutuloksen hyvä visuaalinen vastavuus hakuehtoon nähden (hakutuloksen hyvä laatu)

• Käyttökelpoisuus myös suurilla kuvamäärillä

• Nopeat ja tehokkaat algoritmit

• Toteutettavuus kohtuullisessa ajassa

• Mahdollisuus hyödyntää NDB:n hakuominaisuuksia

Käytettävissä olevasta julkaisuista nousi viitteessä/17/ esitetty menetelmä esille par­

haiten yllämainittuihin kriteereihin soveltuvana. Käytetty menetelmä perustuu väri- aluiden erottamiseen ja niistä muodostettavan piirrevektorin luokitteluun. Menetel­

män etu on tuotetun piirrevektorin pieni dimensionaalisuus. Tällöin voidaan päästä

tavoitteiden mukaiseen nopeaan hakuun käytetyllä perinteisellä indeksointimenetel- mällä.

Värialueiden erotus koostuu seuraavista operaatioista:

• Kuvan skaalaus vakiokokoon

• Väriavaruusmuunnos RGB-HSV

• Mediaan ¡suodatus HSV väriavaruudessa

• Värien kvantisointi 166 väriin

• Mediaanisuodatus HSV väriavaruudessa

• Väriavaruusmuunnos HSV-RGB

• Kuvan segmentointi RGB väriavaruudessa

• Piirre vektori n muodostaminen

Mediaanisuodatus tehdään kaksi kertaa, jotta JPEG-pakkauksen vaikutukset kuvaan minimoituvat (kts luku 4.3.1 Käytetyn menetelmän arviointi). Kuva muunnetaan ta­

kaisin RGB-väriavaruuteen kvantisoinnin jälkeen siksi, että välituloksia pystyy ar­

vioimaan visuaalisesti. Sinänsä segmentoinnin ja piirrevektorin voisi yhtä hyvin muodostaa HSV-väriavaruudessa.

Kunkin toimenpiteen vaikutus esimerkkikuvaan on näytetty toimenpiteen käsittelyn yhteydessä. Ne toimenpiteet, joissa kuva on ollut HSV-väriavaruudessa on esitetty HSV-RGB muunnoksen jälkeen. Seuraavassa kuvassa esimerkkikuva alkuperäise­

nä.

Kuva 13. Alkuperäinen esimerkkikuva

4.2.1 Kuvan skaalaus

Piirrevektorin laskentaa varten kuva pienennetään normaalisti 120x120 pikselin ko­

koon (koon voi valita). Tämä tehdään siksi että laskenta-ajat olisivat kohtuullisia ku­

vaa kohden. Pienennös tehdään keskiarvolaskennalla, jossa kunkin pienennetyn ku­

van pikselin arvoon vaikuttavat alkuperäisen kuvan ympäristön pikselit seuraavan kaavan mukaan:

p'(x'.y') = 2

pU - I, у- 1) + p(.t,y- 0 + р(лг- l,y)+ pU - l,y + l) + p(x.y) + p(x + 1,_y) + p(x,y + 1) + pU + l.y + l) + p(.r + l.y- 1)V 9

p(x,y) tarkoittaa pikselin arvoa koordinaateissa x,y ja p'(x',y') skaalatun ku­

van pikseliä.

Keskiarvonlaskenta pehmentää kuvaa poistaen siitä pieniä yksityiskohtia, mikä hel­

pottaa väripiirteiden laskentaa. Se myös parantaa kuvan visuaalista laatua. Seuraa- vassa kuvassa on esitetty kuva suoraan pienennettynä ja keskiarvolaskennalla skaa­

lattuna. Varsinkin vinot viivat toistuvat paremmin keskiarvolaskennalla skaalatussa kuvassa.

Kuva 14. Esimerkkikuva skaalattuna suoraan ja keskiarvolaskennalla

4.2.2 Väriavaruusmuunokset RGB-HSV ja HSV-RGB

Väriavaruusmuunnokset tehdään viitteessä /28/ esitetyillä algoritmeilla. Sävy h on ositettu r (-60°,60°), g (60°, 180°) ja b (180°,300°) hallitsemiin alueisiin seuraavan kuvan mukaisesti.

Kuva 15. Sävy HSV-väriavaruudessa

Määritellään seuraavat kaavat (r,g,b ja s,v saavat arvot väliltä Oja 1):

m = max(r,g,¿?)

i = min (r,g,b) (3)

Д = x-y

HSV:n v-parametri saa arvon m. Saturaatio (s) taas saa arvon s = Д/m. Jos maksimi on nolla on s = Oja h saa arvon "ei väriä". Tässä toteutuksessa "ei väriä" arvo on 0.

Sävyn h arvo lasketaan seuraavasti:

h = ■

sr,g-b ■

60--- , jos m = r m — i

b — r

180--- , jos m = g m — i

300-——, jos m — h m - i

(4)

4.2.3 Kvantisointi 166 väriin

Kvantisointi on piirteiden laskennassa tärkeä toimenpide, koska piirrevektorin koko on suoraan verrannollinen värien määrään. Kvantisoinnissa 32-bittisen kuvan mil­

joonat värit vähennetään 166 väriin. Nämä 166 väriä muodostuvat IB sävystä (h), kolmesta kylläisyyden (s), kolmesta voimakkuuden (v) arvosta, mustasta, valkoi­

sesta sekä neljästä harmaan sävystä.

Sävyn (h) arvot kvantisoidaan välille 0-256 kahdeksaantoista arvoon. Kylläisyyden (s) arvot ovat 60, 150 tai 245. Samalla tavoin voimakkuudella (v) voi olla arvot 60, 150 tai 245. Tämän lisäksi voimakkuus voi olla 0, jotta kvantisoituihin väreihin saa­

daan musta mukaan.

3000 kuvan testissä kuviin jäi kvantisoinnin jälkeen noin 10-30 eri väriä. Kuvat oli­

vat kuvatoimistomateriaalia.

Kuva 16. Kvantisoitu esimerkkikuva

4.2.4 Väritys mediaan ¡suodatti mella

Kvantisoinnin jälkeen kuvassa on vielä paljon pieniä yksityiskohtia, joista on vain haittaa piirteitä laskettaessa. Tämän vuoksi kvantisoidulle kuvalle tehdään epälineaa-

rinen mediaanisuodatus. Mediaansuodatuksessa on etuna se, että se hävittää pieniä ykstyiskohtia ja samalla säilyttää kuvassa esiintyvät reunat.

Piccolon mediaanisuodatuksessä käytetään 3x3 pikselin neliömäistä ikkunaa. Tut­

kittava pikseli on neliön keskustassa ja se saa arvonsa pikselin ympärillä sijaitsevan 8 pikselin sekä tutkittavan pikselin arvojen mediaanista. Seuraava kuva selventää pe­

riaatetta.

alkuperäinen kuva

5 9 3 1 7 4 2 3 6

med(5,9,3,1,7,4,2,3,6) = 4

pikseli korvattu mediaanilla

Kuva 17. Mediaanisuodattimen toimintaperiaate

Mediaanin laskennassa käytetään Paethin algoritmia /29/ /16/, joka on nopea medi- aanialgoritmi. Sen ideana on etsiä yhdeksän luvun mediaani jakamalla luvut kolmeen joukkoon. Ensimmäisessä joukossa on mediaania pienemmät ja yhtäsuuret luvut.

Toinen joukko koostuu mediaanista. Kolmas joukko sisältää mediaania suuremmat tai yhtäsuuret luvut. Luvut järjestetään kolmeen joukkoon ottamalla kerrallaan yh­

deksästä luvusta kaksi ja laittamalla ne suuruusjärjestykseen. Tämä toistetaan kai­

kille kahden luvun pareille. Sama tehdään 3,4,5 ja 6 luvun ryhmille jonka jälkeen keskimmäinen luvuista on mediaani.

Kuva 18. Mediaansuodatettu esimerkkikuva

4.2.5 Kuvan segmentointi

Piccolon segmentoinnissa ideana on etsiä ja nimetä kuvasta yhtenäiset välialueet.

Yksittäisten välialueiden lisäksi kuvasta etsitään tietyt ehdot täyttävät kahden vierek­

käisen värin alueet. Piccolon segmentoinnin toteutuksessa käytetään taulukko-