From Wikipedia, the free encyclopedia
Ääretuvastus (ehk servatuvastus) on matemaatiliste meetodite kogum, mille eesmärk on tuvastada digitaalsel kujutisel punkte, kus kujutise heledus muutub järsult. Need punktid on tavaliselt koondatud kõverjoontena segmentidesse, mida nimetatakse äärteks. Sarnast probleemi pidevusetuse leidmisel ühemõõtmelistes signaalides tuntakse astmetuvastusena ning signaali pidevusetuse ajas uurimist muutuse tuvastamisena. Ääretuvastus on peamine tööriist pilditöötluses ning masin- ja raalnägemises, eriti nendel aladel, mis on seotud omaduste tuvastamise ja eraldamisega.
Kujutise heleduses esinevate järskude muutuste tuvastamise eesmärk on tabada olulisi momente ja muutusi kujutatava maailma omadustes. Muutused kujutise heleduses viitavad enamasti järgnevale:[1][2]
Ideaaljuhul on kujutisele ääretuvastuse rakendamise tulemuseks kogum ühendatud kõveraid, mis kajastavad objektide piirjooni ning muutusi pindade suunas. Seega võib ääretuvastuse algoritmi rakendamine märkimisväärselt vähendada töödeldava info hulka ning sõeluda välja vähemolulist infot, säilitades samas kujutise olulised struktuursed omadused. Kui ääretuvastuse etapp on edukas, muudab see järgneva kujutise info interpreteerimise tunduvalt lihtsamaks. Siiski ei ole alati võimalik keskmise keerukusega päriselu kujutavate piltide puhul sellist ideaalolukorda saavutada.
Keerukamate kujutiste puhul on eraldatavad ääred sageli killustatud, mis tähendab, et äärekõverad ei ole omavahel ühendatud, mistõttu on äärte info puudulik ning esile võivad olla tõstetud valed ääred. See raskendab tuntavalt kujutise edasist tõlgendamist.[3]
Ääretuvastus on üks olulisemaid etappe pilditöötluses, kujutiste analüüsimisel ja mustrite tuvastamisel ning raalnägemise tehnoloogiates.
Kolmedimensioonilise pildi kahedimensioonilisest kujutisest eraldatud ääri võib jagada vaatepunktist sõltuvateks ja sõltumatuteks. Vaatepunktist sõltumatu äär kajastab enamasti kolmedimensioonilise objekti loomupäraseid omadusi, näiteks pinna kuju. Vaatepunktist sõltuv äär võib muutuda vastavalt vaatepunkti muutumisele ning kajastab enamasti pildi geomeetriat, näiteks objektide suhestumist teineteisega.
Tüüpiline äär võib olla näiteks piir punast värvi kogumi ja kollast värvi kogumi vahel. Joon seevastu võib olla aga väikesearvuline eri värvi pikslite kogum üldiselt muutumatul taustal. Seega võib kummalgi pool joont esineda üks äär.[4]
Ajalooliselt on mitmed koolkonnad tegelenud n-ö ideaalsete, üheastmelise reljeefiga äärte tuvastamise uurimisega. Praktilises kasutuses ei ole säärase reljeefiga ääred levinud, kuna nii sisendandmed kui ka uuritavad esemed ise ei ole ideaalsed. Sisendandmed võivad olla ebatäpsed mitmel põhjusel:
Mitmed uurijad on antud ebatäpsuste mõju vähendamiseks kasutanud Gaussi kõverana modelleeritud ääre reljeefi, kuna katsed on tõestanud, et antud mudel vastab päris maailmale paremini kui varem uuritud ideaalse Heaviside’i astmefunktsiooni sarnane mudel.[3][5] Gaussi kõvera baasil konstrueeritud mudelis võib vaadelda ühemõõtmelises pildis abstsissil asuvat üksikut äärt kui:
Sealjuures Gaussi kõvera parameeter peaks ideaalsetel oludel vastama keskmisele ääre hägususele, vältimaks täiendava ebatäpsuse teket, ent reaalselt pole tihti antud muutuja täpsus väga oluline, kuna tekkiv viga on marginaalne.
Selleks, et illustreerida ääretuvastuse keerukust, võib vaadelda äärte tuvastamist järgnevas ühedimensioonilises signaalis. Siinkohal võib vaistlikult öelda, et äär peaks paiknema 4. ja 5. piksli vahel.
5 | 7 | 6 | 4 | 152 | 148 | 149 |
Kui intensiivsuse erinevused 4. ja 5. piksli vahel oleks väiksemad ning erinevused nendega külgnevate pikslite vahel oleks suuremad, ei oleks samavõrd lihtne järeldada, et äär peaks asuma vastavas regioonis. Pealegi võib antud olukorras väita, et esineb mitmeid ääri.
5 | 7 | 6 | 41 | 113 | 148 | 149 |
Seega ei ole alati lihtne määrata kindlat lävendit kahe kõrvutioleva piksli erinevuseks, mis võimaldaks tuvastada ääre olemasolu.[3] See on kahtlemata üks põhjustest, mis muudab ääretuvastuse protsessi keerukaks, välja arvatud juhul, kui objektid pildil on väga lihtsad ning valgustatuse tingimused kergesti kontrollitavad (näiteks nagu ülaltoodud tüdrukut kujutaval pildil eraldatud ääred).
Ääretuvastuseks kasutatakse mitmeid erinevaid meetodeid, millest enamik jagunevad kahte kategooriasse: otsingupõhised ning nullkohapõhised meetodid. Otsingupõhised meetodid tuvastavad ääri, arvutades sisendi tuletise ning otsides seejärel lokaalseid maksimume, määrates nii üheselt ära nii ääre asukoha kui ka ääre reljeefi suuna. Nullkohapõhised meetodid kasutavad sisendi teist järku tuletisega seotud valemeid, otsides seejärel tulemist nulliga ristumise kohti. Tavaliselt on nullkohapõhiste meetodite keskseks valemiks Laplace’i operaator või mõni muu sarnane diferentsiaalvõrrand. Enne ääretuvastuse algoritmi kasutamist rakendatakse sisendile peaaegu eranditult mõnd hägustamisfiltrit, vähendamaks mürast tingitud ebatäpsuste mõju väljundile. Üldlevinud lahendustes on kasutusel arvutuslikult odav Gaussi filter.[2]
Viimastel kümnenditel levinumad ääre tuvastamise meetodid erinevadki suuremalt jaolt erinevate ühtlustavate filtrite parameetrite ning tuletiste ja reljeefide määratlemise mooduste poolest. Ääre suuna tuvastus on tihti ääre asukoha määramisega samaväärselt tähtis ning suuna määramise meetodite erinevused tulenevad suuresti eelnevalt kirjeldatud erinevustest.[4][6]
John Canny lähenes ääretuvastusele kui rangelt parametriseeritavale matemaatilisele probleemile, seades lahenduse edukuse mõõtmiseks kolm kriteeriumi:[7]
Canny tõestas, et matemaatiliselt vastab antud kriteeriumitele kõige paremini neljanda astme eksponentsiaalvõrrand, kuid väga hea lähenduse saab ka kasutades Gaussi filtrite esimesi tuletisi, mida on oluliselt lihtsam arvutada. Canny tõi kasutusele ka tänapäeval üldlevinud madalate väärtuste summutamise meetodi: ääre tuvastamisel leitakse lokaalsed maksimumid, mis ühtivad viimati leitud maksimumi suunaga, sealjuures kõrvalised väärtused loetakse nulliks. Canny ääretuvastuse algoritmi lõplikus variandis kasutatakse kahte künnist: kõrgem künnis, mis määrab üksiku ääre tuvastamiseks vajaliku taseme, ja madalam künnis, mis määrab eelneva äärega ühendatud ääre tuvastamiseks vajaliku taseme. Antud lähenemine võimaldab oluliselt vähendada müra mõju väljundile, samas tagades, et iga edukalt leitud äär märgitakse väljundis maksimumväärtusega.
Tänu arvutuslikule odavusele ja väga suurele täpsusele on Canny ääretuvastuse algoritm tänapäeval levinuim üldkasutatav ääretuvastuse algoritm.[8]
Ääre õhendamiseks nimetatakse tehnikat, mille käigus eemaldatakse kujutise äärest soovimatud ja/või valeinfot sisaldavad punktid. Seda tehnikat kasutatakse pärast seda, kui kujutist on esmalt filtreeritud müra suhtes, seejärel teostatud ääre tuvastamine ning kui ääred on sobiva künnisega tasandatud. Õhendamine aitab kõrvaldada kõik ebavajalikud punktid ning eduka õhendamise tulemuseks on ühe piksli laiused ääreelemendid.
Õhendatud äärtel on mitmeid eeliseid:[9]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.