Søm udskæring
Den søm udskæring , eller smart beskæring, er et algoritme til tilpasning af billedstørrelse udviklet af Shai Avidan og Ariel Shamir i 2007. Denne algoritme skalaer, ikke ved at sætte standarden skala ( interpolation ) eller beskæring , men fjernelse eller tilsætning af såkaldt lav -Energi pixel stier (på engelsk, lavenergi sømme ).
En pixels energi måles normalt ved sin kontrast til dens nærmeste naboer, men andre teknikker, såsom formdetektion, kan bruges. Derudover er det muligt automatisk at definere eller detektere områder med høj energi for at beskytte dem mod at blive fjernet. Omvendt kan vi definere områder med lav energi, der skal fjernes først. Ud fra disse oplysninger beregner algoritmen de laveste energibaner og fjerner dem eller beregner de pixelstier, der kan tilføjes.
En af applikationerne med algoritmen er at ændre størrelsen på billeder uden forvrængning for responsive websteder .
Definitioner
- En sti (på engelsk, søm ) er en kontinuerlig række af pixels, der går enten fra toppen til bunden af billedet eller fra venstre til højre.
- En pixels energi defineres af en energifunktion, der måler kontrasten (forskellen i farve) for en pixel i forhold til dens naboer.
Algoritme
Beskrivelse af trin
Eksemplet nedenfor beskriver sømudskæringsalgoritmen i tilfælde af billedreduktion:
| Trin | Billede |
|---|---|
| 1) Vælg det billede, der skal ændres. | |
| 2) Beregn energien af hver pixel, her fra den lysintensitet gradient . Andre fremgangsmåder kan anvendes, for eksempel baseret på salience eller entropi (en) . | |
| 3) Fra denne energifunktion beregner du en liste over stier klassificeret efter energiniveau. Dette kan gøres på flere måder: i dynamisk programmering (den mest anvendte metode) med Dijkstra-algoritmen eller en grådig algoritme . På billedet repræsenterer stierne i rødt stier med lav energi, der skal fjernes fra billedet. | |
| 4) Fjern de lavere energibaner så meget som nødvendigt for at opnå den ønskede billedstørrelse. Hvis du tværtimod vil forstørre billedet, erstattes dette trin af en kopi af en sti med lavere energi, så beregningen af gennemsnittet af dets pixels med sine naboer. | |
| 5) Brug det endelige billede. |
Beregning af stienergi i dynamisk programmering
Den dynamiske programmering er at løse et problem ved at opdele det i delproblemer løses ved at gemme mellemresultater. I tilfælde af sømudskæring involverer dette beregning for hver pixel i billedets øverste række den (kontinuerlige) sti med mindst energi, der går ned til en pixel i nederste række.
Illustrationer nedenfor viser den dynamiske programmeringsproces, der bruges til at beregne en optimal top-til-bund-sti. Hver firkant repræsenterer en pixel, hver værdi til venstre i rødt i en boks repræsenterer energien for den tilsvarende pixel, og hver værdi i sort repræsenterer summen af energierne af alle pixel på stien, der fører til den medfølgende pixel.
-
Initialisering : Per definition har den øverste linje ingen linje over sig, summen af energierne, der fører til en pixel på denne linje (i sort), er derfor lig med den pågældende pixels energi.
-
Sti : For hver pixel på en anden linje er minimumsenergien, der fører der, lig med summen af pixelens energi og minimumsenergien af de tre pixels ovenfor. For en given linje beregnes således minimumsenergien til at nå hver pixel af denne linje. Gentag bare denne algoritme for hver linje helt ned for at få den mindste energi, der fører til hver pixel i billedet.
-
Konklusion : Den mindste energi, der er nået i bunden (5 i dette eksempel) angiver den samlede energi på stierne med mindst energi. Det er så tilstrækkeligt at gå op ad hver sti ved at vælge hver gang pixlen med mindst mulig energi blandt de tre mulige for at finde stierne med mindst energi (tegnet med hvidt her), som derfor kan slettes.
Kompleksiteten af algoritmen
Enten antallet af linjer i billedet (højde) og antallet af pixels pr. Linje (bredde). Hvert dynamisk programmeringstrin beskrevet ovenfor (som beregner energiniveauerne for alle pixels i en række) kræver et konstant antal operationer for hver pixel (summen af pixelens energi med de tre energier af stierne, der fører til den, og sammenligning af disse tre summer) og realiseres derfor i tide . Hele algoritmen (gennemkørsel af alle linjer) tager derfor .
På den anden side, hvis man ønsker at slette flere stier samtidigt, kan den tredje del af algoritmen give anledning til stier, der krydser hinanden. For at håndtere denne eventualitet, mens man undgår at genberegne alle energierne hver gang en sti slettes, foreslår Avidan at tilføje en matrix, der for hver pixel gemmer det mindste antal af den sti, hvor den er placeret: pixlerne på den mindste energibane vil have antallet , pixels på den næstmindste energibane vil have tallet osv. Derefter, hver gang en sti slettes, opdateres denne tabel i overensstemmelse hermed.
Det er også muligt at ignorere denne kompleksitet og ty til en tilnærmelse. For at gøre dette kan vi først udføre de to første trin i algoritmen beskrevet ovenfor, hvilket gør det muligt at klassificere pixels i den sidste række ved at øge energiniveauerne. Derefter kan vi overveje hver af disse pixels i stigende rækkefølge af energi og udføre det tredje stisøgningstrin uden nogensinde at opdatere energierne, men ved at markere de anvendte pixels for ikke at vælge dem flere gange.
Ansøgninger og begrænsninger
Implementeringer
Adobe har erhvervet en ikke-eksklusiv licens til sømudskæringsteknologien, implementeret som en funktion i Photoshop CS4, under navnet Content Aware Scaling . Denne funktion kan bruges til at ændre størrelsen på et billede interaktivt, hvilket har resulteret i kapringer i form af memer .
Andre computergrafikapplikationer har overtaget denne funktionalitet, herunder GIMP , digiKam og ImageMagick , ud over dedikerede applikationer som iResizer, der har frigivet gratis og open source- versioner af algoritmen.
-
Interaktiv SVG-demonstration af sømudskæring ved hjælp af ImageMagicks væske-skaleringsfunktion . Ved at klikke ovenfor kan du derefter svæve over for at sammenligne det originale billede (øverst), det ændrede billede med sømudskæring (i midten), billedet ændres på den mest klassiske måde ved interpolering (nederst).
-
Interaktiv SVG-demonstration af sømudskæring ved hjælp af ImageMagicks væske-skaleringsfunktion . Ved at klikke ovenfor kan vi svæve over for at sammenligne de tre billeder: vi bemærker, at ansigterne er mindre påvirket end resten.
Grænser
Algoritmen kan kræve brugerintervention for at undgå fejl (for eksempel i tilfælde, hvor billederne indeholder ansigter, som vi ikke ønsker at forvrænge). Flere grænseflader, der implementerer denne algoritme, foreslår at "male" de områder, der skal bevares, hvilket har den effekt, at de øger deres energiniveau i udførelsen af algoritmen. I tilfælde af ansigter kan ansigtsgenkendelsesalgoritmer bruges.
Ved at fjerne en lavere energibane har algoritmen undertiden tendens til at skabe høje energibaner (ved at bringe pixels, der har en stærk kontrast imellem dem, tættere på hinanden). For at undgå denne faldgrube er det muligt at simulere konsekvenserne af at fjerne en sti og beregne enhedens energiforskel for at se, om den stiger. I så fald kan det være bedre at vælge en anden sti, der skal slettes
Noter og referencer
- (fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen " Seam carving " ( se forfatterlisten ) .
- (da) Shai Avidan og Ariel Shamir, " Seam carving for content-aware image resizing " , SIGGRAPH ,Juli 2007( læs online , hørt den 17. juli 2020 )
- (i) Aditya Bist og Vinay Palakkode, " Parallel Seam Carving " på cmu.edu , University Carnegie Mellon ,2016(adgang til 17. juli 2020 )
- (in) " Hvad er nyt i Adobe Photoshop CS4 " på photoshopsupport.com (adgang til 17. juli 2020 )
- (in) " Content Aware Scaling " på knowyourmeme.com ,6. november 2013(adgang til 17. juli 2020 )
- (da) Liquid Rescale GIMP plugin
- (i) Ny Flydende rescale værktøj under opførelse ...
- (in) Flydende skalering - sømudskæring
- (in) Smart Resizer - Skalér fotos uden at skalere motivet!
- (i) Michael Rubinstein, Ariel Shamir og Shai Avidan, " mproved Seam Carving til video Retargeting " [PDF] , SIGGRAPH ,2008(adgang til 17. juli 2020 )
- (i) Michael Rubinstein, Ariel Shamir og Shai Avidan, " Forbedret Seam Carving til video Retargeting " .