Sauman veistos

Sauma kaiverrus , tai älykäs rajaus, on algoritmi varten kuvan koon kehittämä Shai Avidan Ariel Shamir vuonna 2007. Tämä algoritmi asteikot, ei asettamalla standardi asteikko ( interpolointi ) tai rajaus , mutta poistamalla tai lisäämällä ns alhainen -Energia pikselin polut (Englanti, vähän energiaa saumat ).

Pikselin energia mitataan yleensä sen kontrastilla lähimpiin naapureihin nähden, mutta muita tekniikoita, kuten muodon havaitsemista, voidaan käyttää. Lisäksi on mahdollista määrittää tai havaita automaattisesti suurenergiset alueet niiden suojaamiseksi poistolta. Vastaavasti voimme määritellä vähän energiaa olevat alueet, jotka ensin poistetaan. Näiden tietojen perusteella algoritmi laskee pienimmät energiapolut ja poistaa ne tai laskee lisättävät pikselireitit.

Yksi algoritmin sovelluksista on kuvien koon muuttaminen vääristymättä reagoiville verkkosivustoille .

Määritelmät

Polku (englanniksi sauma ) on jatkuva pikselisarja, joka kulkee joko kuvan ylhäältä alas tai vasemmalta oikealle.
Pikselin energia määritellään energiatoiminnolla, joka mittaa pikselin kontrastia (värieroa) suhteessa naapureihinsa.

Algoritmi

Vaiheiden kuvaus

Alla olevassa esimerkissä kuvataan saumanleikkausalgoritmi kuvan pienentämisen tapauksessa:

Vaihe	Kuva
1) Valitse kuvan koko.
2) Laske energia jokaisen pikselin, tässä päässä valon voimakkuuden gradientti . Muita menetelmiä voidaan käyttää, esimerkiksi perustuen silmäluomiin tai entropiaan (en) .
3) Laske tästä energiafunktiosta luettelo poluista, jotka on luokiteltu energiatason mukaan. Tämä voidaan tehdä useilla tavoilla: dynaamisessa ohjelmoinnissa (eniten käytetty menetelmä) Dijkstra-algoritmilla tai ahneella algoritmilla . Kuvassa punaisella olevat polut edustavat matalan energian polkuja, jotka on poistettava kuvasta.
4) Poista alemmat energiapolut niin paljon kuin on tarpeen halutun kuvakoon saavuttamiseksi. Jos päinvastoin haluat suurentaa kuvaa, tämä vaihe korvataan pienemmän energian polun kopiolla, sitten sen pikselien keskiarvon laskeminen naapureiden kanssa.
5) Käytä lopullista kuvaa.

Polkuenergian laskeminen dynaamisessa ohjelmoinnissa

Dynaaminen ohjelmointi on ratkaista ongelma se hajoaa osa-ongelmat ratkaistaan tallentamalla välitulokset. Saumojen veistämisen tapauksessa on kysymys siitä, lasketaanko kuvan ylärivin jokaiselle pikselille vähiten energiaa oleva (jatkuva) polku, joka laskee alarivin pikseliin.

Alla olevat kuvat esittävät dynaamisen ohjelmointiprosessin, jota käytetään optimaalisen ylhäältä alas -polun laskemiseen. Jokainen neliö edustaa pikseliä, kukin vasemmanpuoleinen arvo punaisella laatikossa edustaa vastaavan pikselin energiaa, ja kukin musta arvo edustaa kaikkien siihen pikseliin johtavan polun kaikkien pikselien energioiden summaa.

Alustus : Määritelmän mukaan ylemmällä viivalla ei ole viivaa sen yläpuolella, tämän viivan pikseliin johtavien energioiden summa (mustana) on siis yhtä suuri kuin kyseisen pikselin energia.
Polku : Jokaisen toisen viivan pikselin kohdalla sinne johtava vähimmäisenergia on yhtä suuri kuin pikselin energian ja kolmen yllä olevan pikselin energian summa. Tietylle viivalle lasketaan siten vähimmäisenergia tämän linjan jokaisen pikselin saavuttamiseksi. Riittää, että tämä algoritmi toistetaan jokaiselle riville, aina pohjaan asti, jotta saadaan mahdollisimman pieni energia, joka johtaa kuhunkin kuvan pikseliin.
Johtopäätös : Alareunassa saavutettu vähimmäisenergia (tässä esimerkissä 5) osoittaa vähiten energiaa kulkuvien polkujen kokonaisenergian. Sitten riittää mennä ylöspäin jokaisella polulla, valitsemalla joka kerta pienimmän energian pikseli kolmen mahdollisen joukosta, löytää pienimmän energian polut (piirretty tähän valkoisella), jotka voidaan siis poistaa.

Algoritmin monimutkaisuus

Joko kuvan rivien määrä (korkeus) ja pikselien määrä riviä kohden (leveys). Jokainen yllä kuvattu dynaaminen ohjelmointivaihe (joka laskee kaikkien rivin pikselien energiatasot) vaatii vakiomäärän operaatioita kullekin pikselille (pikselin energian summa siihen johtavien polkujen kolmen energian kanssa ja vertailu näistä kolmesta summasta) ja toteutuu siten ajoissa . Siksi koko algoritmi (kaikkien linjojen läpikulku) kestää . $ei$ $s$ ${\ displaystyle O (p)}$ ${\ displaystyle O (n \ kertaa p)}$

Toisaalta, jos halutaan poistaa useita polkuja samanaikaisesti, algoritmin kolmas osa voi aiheuttaa polkuja, jotka leikkaavat. Tämän mahdollisuuden käsittelemiseksi välttäen kaikkien energioiden uudelleenlaskemista joka kerta, kun polku poistetaan, Avidan ehdottaa lisäämään taulukkoa, joka tallentaa jokaiselle pikselille polun vähimmäismäärän, jolla se sijaitsee: pikselit pienimmällä energiapolulla on numero , pikseleillä toisella vähiten energiapolulla on numero , ja niin edelleen. Sitten, kun polku poistetaan, tämä taulukko päivitetään vastaavasti. $1$ $2$

On myös mahdollista sivuuttaa tämä monimutkaisuus ja turvautua likiarvoon. Tätä varten voimme ensin suorittaa edellä kuvatun algoritmin kaksi ensimmäistä vaihetta, mikä mahdollistaa viimeisen rivin pikselien luokittelun lisäämällä energiatasoja. Sitten voimme tarkastella kutakin näistä pikseleistä kasvavan energian järjestyksessä ja suorittaa kolmannen polun etsintävaiheen päivittämättä energioita koskaan, mutta merkitsemällä käytetyt pikselit, jotta emme valitsisi niitä useita kertoja.

Sovellukset ja rajoitukset

Toteutukset

Adobe on hankkinut ei-yksinomaisen lisenssin saumanveistotekniikalle, joka on toteutettu Photoshop CS4: n ominaisuutena, nimellä Content Aware Scaling . Tätä ominaisuutta voidaan käyttää kuvan koon muuttamiseen interaktiivisesti, mikä on johtanut kaappauksiin meemien muodossa .

Muut tietokonegrafiikkasovellukset ovat siirtäneet tämän toiminnon, mukaan lukien GIMP , digiKam ja ImageMagick , erillisten sovellusten lisäksi, kuten iResizer, joka on julkaissut algoritmin ilmaiset ja avoimet lähdekoodiversiot .

Vuorovaikutteinen SVG-esittely saumanleikkauksesta ImageMagickin neste-uudelleen skaalaus -toiminnolla . Napsauttamalla yllä, voimme sitten viedä hiiren osoittimen päälle vertaillaksemme alkuperäistä kuvaa (ylhäällä), kokoa muutettua kuvaa saumanveistolla (keskellä), kokoa suurinta kuvaa klassisimmalla tavalla interpoloimalla (alhaalla).
Interaktiivinen SVG -saumanleikkauksen esittely ImageMagickin neste-uudelleen skaalaus -toiminnolla . Napsauttamalla yllä voimme viedä hiiren osoittimen vertaamaan näitä kolmea kuvaa: huomataan, että kasvot vaikuttavat vähemmän kuin muut.

Rajat

Algoritmi saattaa vaatia käyttäjän toimia virheiden välttämiseksi (esimerkiksi jos kuvissa on kasvoja, joita emme halua vääristää). Useat tämän algoritmin toteuttavat rajapinnat ehdottavat "maalattavan" säilytettävät alueet, mikä lisää niiden energiatasoa algoritmin suorituksessa. Kasvojen tapauksessa voidaan käyttää kasvojentunnistusalgoritmeja .

Poistamalla matalamman energiapolun algoritmi pyrkii toisinaan luomaan korkean energian polkuja (tuomalla pikselit, joilla on voimakas kontrasti niiden välillä). Tämän kuopan välttämiseksi on mahdollista simuloida polun poistamisen seurauksia ja laskea kokoonpanon energiaero nähdäksesi, kasvaako se. Jos näin on, voi olla parempi valita toinen poistettava polku

Huomautuksia ja viitteitä

(fr) Tämä artikkeli on osittain tai kokonaan otettu englanninkielisestä Wikipedia- artikkelista " Saumojen veistos " ( katso luettelo kirjoittajista ) .

(en) Shai Avidan ja Ariel Shamir, ” Saumanleikkaus sisällön tietoisen kuvan koon muuttamiseksi ” , SIGGRAPH ,Heinäkuu 2007( lue verkossa , tutustunut 17. heinäkuuta 2020 )
(in) Aditya Bist ja Vinay Palakkode, " Parallel Sauma Veistos " päälle cmu.edu , University Carnegie Mellon ,2016(käytetty 17. heinäkuuta 2020 )
(in) " Mitä uutta Adobe Photoshop CS4: ssä " on photoshopupport.com (avattu 17. heinäkuuta 2020 )
(in) " Content Aware Scaling " sivustolla knowyourmeme.com ,6. marraskuuta 2013(käytetty 17. heinäkuuta 2020 )
(en) Liquid Rescale GIMP -laajennus
(in) Uusi Liquid Rescale -työkalu rakenteilla ...
(in) Nestemäinen uudelleenmittaus - saumanleikkaus
(sisään) Smart Resizer - skaalaa valokuvat muuttamatta kohteen skaalausta!
(in) Michael Rubinstein, Ariel Shamir ja Shai Avidan, " arempi Sauman veistos Video uudelleenkohdistaminen " [PDF] , SIGGRAPH ,2008(käytetty 17. heinäkuuta 2020 )
(in) Michael Rubinstein, Ariel Shamir ja Shai Avidan, " Parempi Sauman Veistos Video uudelleenkohdistaminen " .

Katso myös

Aiheeseen liittyvät artikkelit

Maalaus