Keskustelu: Yleinen keskustelu: Hahmon tunnistusta

Ajattelin pureutua seuraavaksi tällaiseen ongelmaan.. tarkoituksena on siis tehdä algoritmi, joka kertoo, että nmontako kulmaa on kuvassa olevalla monikulmiolla. Ihmiselle tämä tietysti on melko triviaali tehtävä, mutta järkevä algoritmi osoittautui aika hankalaksi.

http://msdos464.no-ip.com/php/gdlib/selvitys/

Huom: muuttelen tuota viimeistään huomenna iltapäivällä, joten voi ilmentyä virheitä jne :)

Ohjelmalla ei ole ongelmaa löytää kuvioiden rajalta nuo (tällä hetkellä) sinisellä korostetut neliöt. Ohjelma käsittelee siis jokaista tuollaista neliötä yhtenä pisteenä (keksipiste). Taustalla näkyy musta alkuperäinen kuvio.

Kannattaisiko noihin pisteisiin sovittaa aina tietyn pisteen kauta suora siten, että löytyisi esim. pienin neliösumma? Todennäköisesti tarvittaisiin isompaa potenssia, että se asettuisi pakosti tuollaista sivua pitkin..

Mielessä oli myös laskea kulmakertoimia kaikkien pisteiden välillä, ja siitä katsoa fregvenssejä. Tässä tulee kuitenkin ongelmaa, jos on useita sivuja, joilla on sama kulmakerroin.

3. mahdollisuus olisi, että aluksi laskisi noista reunapisteistä keskiarvon, jolloin saisi arvauksen siitä, että missä kuvion keskipiste likimain on. Tästä sitten lähtisi laskemaan tuon pisteen etäisyyttä reunasta eri kulmilla, jolloin siihen tulisi niin monta maksimia, kuin on kulmia. Tässä pitäisi kuitenkin olettaa, että kulmat eivät ole kovin suuria (yli 120 astetta), ja asettaa muutenkin rajoituksia.

Mitä tekniikkaa tuossa siis mahdollisesti kannattaisi käyttää? Aluksi riittää, että erottaa neliön kolmiosta :) Kiva olisi, että saisi ympyröityä löydetyt kulmat (eli pelkkä kulmien määrä ei ihan riittäisi).

Tässä tulee herkästi vastaan kysymys, mikä on kulma, kun kuvio koostuu pienistä neliöistä. Kuinka pienikokoinen ympyrä eroaa pienikokoisesta kahdeksankulmiosta?

Yksi ajatus olisi lähteä jostakin reunan pisteestä (kuvioon kuuluvasta) ja tutkia sen välitöntä ympäristöä: moniko piste ympäröivistä kahdeksasta on kuviota? Jos vain kolme tai kaksi (vierekkäistä), kyseessä on selvä terävä kulma. Kuvioon kuuluvien pisteiden sijaintien mukaan voidaan laskea suurpiirteinen arvo, minne päin sivu kulkee. Näistä arvoista voisi pitää joltakin matkalta kirjaa ja vaikka laskea keskiarvoa, ja jos esimerkiksi neljän seuraavan suuntakeskiarvo on aivan eri kuin neljän edellisen, on löytynyt kulma. Käytännön toteutukseen en ota enempää kantaa ja tarkempia arvioita toimivuudesta en esitä, kun en juuri nyt kuitenkaan itse ala tuollaista tehdä.

Toinen mieleeni tullut ratkaisu olisi lähteä kuvan reunalta etenemään eri suuntaisin suorin, ja laskea joka kohdasta, montako pistettä kuviosta suora leikkaa. Näin siis vaikkapa sopivasta kolmiosta voitaisiin ylhäältä lähestyessä havaita, että ensin leikataan yksi piste, sitten kolme, sitten viisi jne. Altaahta taas tulisi ehkä vastaan heti alkuun sata, jolloin tarkistuksen voisi lopettaa. Sivuilta tai sopivasta suunnasta kulmittain lähestyen löytyisivät toisetkin kulmat. Koverien kulmien kanssa voisi mahdollisesti edetä niin, että kun kaikki kuperat ovat ensin löytyneet, vedettäisiin niistä toisiinsa viivat ("monikulmion kupera peite"), ja kun ulkopuoli sitten täytettäisiin osaksi kuviota, jäisi jäljelle uusia, kuvioon kuulumattomia alueita, joiden kulmat (alkuperäisen kuvion koverat kulmat siis) voisi ehkä edelleen selvittää samaan tapaan.

siis onko tuo kummallisen näköinen kuvio se mitä ohjelmalle annetaan ja sen pitäisi sitten selvittää siitä jotain? Varmaan jos ne on aina tuollaisia niin voisi todeta että tausta on valkoinen ja kuvio musta ja pyrkiä siistimään nuo roskat (vihreät ja siniset neliöt) pois. Ainakin nuo siniset romut häiritsevät elämää kun ne aiheuttavat reunoihin lisäkulmia. Sen jälkeen pitäisi olla aika triviaalia.

Jos taas yleisemmin pitäisi tunnistaa hahmoja (sotkettuja monikulmioita) kuvasta ilman että voi tehdä oletuksia esimerkiksi väreistä, niin menee selkeästi hankalammaksi.

Tietysti jos mitä lyhyempiä viivoja kuviossa voi olla, niin sitä epävarmemmaksi menee. Tosin tuottaa se ihmisellekin hankaluuksia. Esim. jos kolmion kärjestä katkaistaan pieni pala pois niin siitä tulee nelikulmio. Jos pala on riittävän pieni, niin sitä voi olla vaikea havaita.

Outoa... luulin vastanneeni tänne, mutta unohdin näköjään kiireessä painaa lähetä-nappia.

Ohjelma saa siis syötteenä ihan sotkemattoman mustavalkokuvan, tuossa tapauksessa se on http://msdos464.no-ip.com/php/gdlib/selvitys/kuva.png. Vihreät pisteet ovat niitä, jotka ohjelma tulkitsee olevan kuvion sisällä, ja sinisellä korostetut pisteet ovat reunapisteitä. Näillä näkymin algoritmi käyttää hyväkseen ainoastaan noita löydettyjä reunapisteitä.

Taisin keksiä, miten ainakin sellaiset monikulmiot saa ratkaistua, missä yksikään kulma ei ole liian suuri (ei ainakaan yli 180 astetta). Valitaan mikä tahansa piste P_0. Käydään kaikki muut pisteet läpi, ja valitaan se, joka on pisteestä P_0 kauimpana. Tämä on piste P_1, joka on (oletettavasti) ensimmäinen löydetty kulma. Seuraavaksi etsitään piste P_2, joka on kauimpana pisteestä P_0. Tästä eteenpäin seuraava piste P_n etsitään siten, että laskettava S(P_n) on suurin löydetty. S(P_n) tarkoittaa siis summaa, mikä tulee, kun lasketaan etäisyyksien summa tuosta pisteestä tähän mennessä löydettyihin pisteissin. Tätä jatketaan niin kauan, että S(P_n) < S(P_k), jossa P_k on tähän mennessä löydettyjen pisteiden massakeskipiste.

Algoritmista tulisi kuitenkin melkolailla aikaa vievä, kannattaisi ehkä ensiksi laksea etäisyydet kaikkien (reunapisteiden (siis niiden korostettujen)) välillä. Sitten ne voisi taulukosta katsoa sen nopeasti.

Toivottavasti saitte selvää :) Paperilla tuota pyörittelin, ja pitäisi toimia aika hyvin, vaikka olisi yli 6 kulmaa. Tuon "verkon" kokoa voi sitten tihentää tarpeen mukaan.. Jollain tähtikuviolla tulisi ongelmia, kun siinä keskellä olisi niitä kulmia paljon vierekkäin (tulisi pieni etäisyys summa).

Tietysti jos nopeusoptimointi on keskeistä, niin tämä muutuu astetta haastavammaksi.

Mutta itse tekisin niin, että etsisin mustan ja valkoisen rajan ja lähtisin seuraamaan sitä. Sitten jos kulmakerroin muuttuu enemmän kuin pikselin edestä kesken matkaa niin siinä on kulma. Ongelmaa tuottaisivat erittäin tylpät kulmat, joiden jommalla kummalla puolella on lyhyt matka seuraavaan kulmaan. Mutta nämä nyt ovat ongelmallisia millä tahansa algoritmilla ja jopa ihmiselle.

Grez kirjoitti:

Mutta nämä nyt ovat ongelmallisia millä tahansa algoritmilla ja jopa ihmiselle.

Kyllä jo 7 vuotias lapsi osaa laskea monikulmiosta kulmat, oli ne sitten tylppiä tai ei. Ongelmia tietty tuottaa rajatapaukset, eli esim. 179 asteen kulmat ja lyhytet sivut (kolmiosta pienellä leikkauksella neliöksi). Uskon, että tuolla "kauimman pisteen menetelmällä" tulee melko hyviä tuloksia.. myöhemmin tänään näkee, että tekeekö se ohjelma niinkuin olen sen päässä ajatellut tekevän :D

msdos464 kirjoitti:

Grez kirjoitti:

Mutta nämä nyt ovat ongelmallisia millä tahansa algoritmilla ja jopa ihmiselle.

Kyllä jo 7 vuotias lapsi osaa laskea monikulmiosta kulmat, oli ne sitten tylppiä tai ei. Ongelmia tietty tuottaa rajatapaukset, eli esim. 179 asteen kulmat ja lyhytet sivut.

Mitä ihmettä? Noista rajatapauksistahan juuri puhuin.

Olisit ottanut lainaukseen mukaan sen edellisenkin lauseen.

"Ongelmaa tuottaisivat erittäin tylpät kulmat, joiden jommalla kummalla puolella on lyhyt matka seuraavaan kulmaan. Mutta nämä nyt ovat ongelmallisia millä tahansa algoritmilla ja jopa ihmiselle."

Voin tehdä vaikka heti monikulmion tuollaisena mustavalkoisena kuvana, josta et tiedä montako kulmaa siinä on vaikka oletettavasti olet yli 7 -vuotias.

Oho.. tuli vähän mokattua. Hätäisesti lukiessani käsitin, että tarkoitit "erittäin tylpillä" kulmilla jotain selvästi yli 180 asteen kulmia.

Periaatteessa rasteri ympyrässäkin on mahdollisesti satoja kulmia.. Tässä tapauksessa olisi helpointa sanoa, ettei siinä ole kulmia ollenkaan :)

Joo, "erittäin tylppä" tosiaan tarkoittaa samaa kuin "erittäin lähellä 180°". kun se kasvaa suuremmaksi kuin 180°, niin se muuttuu terävämmäksi. Tai näin minä itse määrittelisin terävän ja tylpän kulman. Tietysti termistössämme saattaa olla merkityseroja.

Jos löydät reunoja mukailevia suoria helposti, pääset ehkä alkuun näin:

Kuvion reunat ovat näille suorille asettuvia janoja ja nurkat näiden suorien leikkauspisteissä. Välttämättä kaikissa leikkauspisteissä ei kuitenkaan ole nurkkaa.

Jokainen reuna yhdistää kaksi nurkkaa, ja jokaisesta nurkasta lähtee kaksi erisunntaista reunaa.

Tästä kai voisi johtaa algoritmin. En kuitenkaan näe kaikkia sudenkuoppia vain näin miettimällä.

http://msdos464.no-ip.com/php/gdlib/selvitys/tilanne1.png

Tuon se ratkaisi oikein, kuten monet muutkin kuviot. Jos monikulmiossa on kuitenkin joitakin sivuja, jotka ovat selvästi pidempiä kuin muut, niin tulee ongelmia:

http://msdos464.no-ip.com/php/gdlib/selvitys/tilanne2.png

Tylpät kulmat tuottavat myös ongelmia:

http://msdos464.no-ip.com/php/gdlib/selvitys/tilanne3.png

Aluksi siis tehdään arvaus likimain kuvion puolesta välistä (sinisen sävyinen neliö / ruutu)

Siitä etsitään kauimmainen piste (valkoinen viiva näyttää, että minne mentiin), tämä on P_1. Tästä eteenpäin etsitään aina sellainen piste, että etäisyyksien summat muihin löydettyihin pisteisiin olisi mahdollisimman pieni. Jos päädytään uudestaan jonkun löydetyn pisteen läheisyyteen, lopetetaan etsintä.

Tuo löytää vähän hankalammatkin kulmat, jos sen annetaan edetä pidemmälle:

http://msdos464.no-ip.com/php/gdlib/selvitys/tilanne4.png

Tällöin pitäisi kuitenkin filtteröidä summasta sellaiset pois, mitkä asettuivat jonkin jo valmiiksi löydetyn pisteen läheisyyteen.

edit: muutin sen jo siten, että hakee 20 pistettä. Keltaiset on pisteitä, jotka tulkittiin, että olivat jonkun jo-löydetyn pisteen lähellä. Joillakin syötteillä toimii, joillakin ei ;)