Sculptură de cusătură
Sculptură cusătură , decuparea inteligentă, este un algoritm pentru Redimensionarea imaginii dezvoltat de Shai Avidan și Ariel Shamir în 2007. Acest algoritm cântare, nu prin setarea scală standard ( interpolare ) sau decuparea , dar eliminarea sau adăugarea de așa-numitele scăzut comustibil si energie pixel căi (în limba engleză, cusături-consum redus de energie ).
Energia unui pixel este de obicei măsurată prin contrastul său cu cei mai apropiați vecini, dar pot fi folosite și alte tehnici, cum ar fi detectarea formei. În plus, este posibilă definirea sau detectarea automată a zonelor cu energie ridicată, pentru a le proteja de îndepărtare. În schimb, putem defini zone cu consum redus de energie, care trebuie eliminate mai întâi. Din aceste informații, algoritmul calculează cele mai mici căi de energie și le elimină sau calculează căile de pixeli care pot fi adăugate.
Una dintre aplicațiile algoritmului este redimensionarea imaginilor fără distorsiuni pentru site-urile web responsive .
Definiții
- O cale (în engleză, seam ) este o serie continuă de pixeli care merg fie de sus în partea de jos a imaginii, fie de la stânga la dreapta.
- Energia unui pixel este definită de o funcție energetică care măsoară contrastul (diferența de culoare) a unui pixel în raport cu vecinii săi.
Algoritm
Descrierea pașilor
Exemplul de mai jos descrie algoritmul de sculptură a cusăturii , în cazul reducerii imaginii:
| Etapa | Imagine |
|---|---|
| 1) Alegeți imaginea de redimensionat. | |
| 2) Calculați energia fiecărui pixel, aici din gradientul de intensitate a luminii. Pot fi utilizate și alte metode, de exemplu bazate pe evidență sau entropie (en) . | |
| 3) Din această funcție de energie, calculați o listă de căi clasificate după nivelul de energie. Acest lucru se poate face în mai multe moduri: în programare dinamică (cea mai utilizată metodă), cu algoritmul Dijkstra sau cu un algoritm lacom . În imagine, căile în roșu reprezintă căile cu energie redusă, care trebuie eliminate din imagine. | |
| 4) Îndepărtați căile de energie inferioare atât cât este necesar pentru a atinge dimensiunea dorită a imaginii. Dacă, dimpotrivă, doriți să măriți imaginea, acest pas este înlocuit de copia unei căi cu energie mai mică, atunci calculul mediei pixelilor săi cu vecinii săi. | |
| 5) Folosiți imaginea finală. |
Calculul energiei traseului în programarea dinamică
Programarea dinamică este de a rezolva o problemă prin spargerea - l în sub-probleme sunt rezolvate prin stocarea rezultatelor intermediare. În cazul sculpturii cusăturii , aceasta implică calcularea, pentru fiecare pixel din rândul superior al imaginii, a căii (continue) cu cea mai mică energie care coboară la un pixel în rândul inferior.
Ilustrațiile de mai jos arată procesul de programare dinamică utilizat pentru a calcula o cale optimă de sus în jos. Fiecare pătrat reprezintă un pixel, fiecare valoare din stânga în roșu într-o casetă reprezintă energia pixelului corespunzător și fiecare valoare în negru reprezintă suma energiilor tuturor pixelilor din calea care duce la acel pixel inclus.
-
Inițializare : Prin definiție, linia superioară nu are nicio linie deasupra ei, suma energiilor care duc la un pixel al acestei linii (în negru) este, prin urmare, egală cu energia pixelului în cauză.
-
Calea : pentru fiecare pixel al unei alte linii, energia minimă care conduce acolo este egală cu suma energiei pixelului și energia minimă a celor trei pixeli de mai sus. Pentru o linie dată, se calculează astfel energia minimă pentru a atinge fiecare pixel al acestei linii. Doar repetați acest algoritm pentru fiecare linie, până la capăt, pentru a obține energia minimă care duce la fiecare pixel din imagine.
-
Concluzie : energia minimă atinsă în partea de jos (5 în acest exemplu) indică energia totală a căilor cu cea mai mică energie. Apoi este suficient să urcați pe fiecare cale, selectând de fiecare dată pixelul cu cea mai mică energie dintre cele trei posibile, pentru a găsi căile cu cea mai mică energie (desenate în alb aici), care, prin urmare, pot fi șterse.
Complexitatea algoritmului
Fie numărul de linii ale imaginii (înălțime) și numărul de pixeli pe linie (lățime). Fiecare etapă de programare dinamică descrisă mai sus (care calculează nivelurile de energie a tuturor pixelilor pe rând) necesită un număr constant de operații pentru fiecare pixel (suma energiei pixelului cu cele trei energii ale căilor care duc la acesta și comparație din aceste trei sume) și se realizează deci în timp . Prin urmare, întregul algoritm (traversarea tuturor liniilor) ia .
Pe de altă parte, dacă se dorește ștergerea mai multor căi simultan, a treia parte a algoritmului poate da naștere unor căi care se intersectează. Pentru a face față acestei eventualități, evitând în același timp recalcularea tuturor energiilor de fiecare dată când o cale este ștearsă, Avidan propune să adauge o matrice care stochează, pentru fiecare pixel, numărul minim al căii pe care se află: pixelii pe cea mai mică cale energetică va avea numărul , pixelii pe a doua cale cu cea mai mică energie vor avea numărul și așa mai departe. Apoi, de fiecare dată când o cale este ștearsă, acest tabel este actualizat în consecință.
De asemenea, este posibil să ignorăm această complexitate și să recurgem la o aproximare. Pentru a face acest lucru, putem efectua mai întâi primii doi pași ai algoritmului descris mai sus, ceea ce face posibilă clasificarea pixelilor din ultimul rând prin creșterea nivelurilor de energie. Apoi, putem lua în considerare fiecare dintre acești pixeli în ordinea creșterii energiei și putem efectua cea de-a treia etapă de căutare a căilor, fără a actualiza vreodată energiile, ci marcând pixelii utilizați pentru a nu le selecta de mai multe ori.
Aplicații și limitări
Implementări
Adobe a achiziționat o licență neexclusivă pentru tehnologia de sculptură a cusăturilor, implementată ca o caracteristică a Photoshop CS4, sub numele Content Aware Scaling . Această caracteristică poate fi utilizată pentru a redimensiona o imagine interactiv, ceea ce a dus la deturnări sub formă de meme .
Alte aplicații de grafică pe computer au preluat această funcționalitate, inclusiv GIMP , digiKam și ImageMagick , pe lângă aplicații dedicate precum iResizer care a lansat versiuni gratuite și open source ale algoritmului.
-
Demonstrație interactivă SVG a sculpturii cusăturilor, utilizând funcția de redimensionare a lichidului ImageMagick. Făcând clic deasupra, puteți trece cu mouse-ul pentru a compara imaginea originală (sus), imaginea redimensionată cu sculptura cusăturii (în mijloc), imaginea redimensionată în modul cel mai clasic, prin interpolare (jos).
-
Demonstrație interactivă SVG a sculpturii cusăturilor, utilizând funcția de redimensionare a lichidului ImageMagick. Făcând clic mai sus, putem trece cu mouse-ul pentru a compara cele trei imagini: observăm că fețele sunt mai puțin afectate decât restul.
Limite
Algoritmul poate necesita intervenția utilizatorului pentru a evita erorile (de exemplu, în cazul în care imaginile conțin fețe pe care nu vrem să le denaturăm). Mai multe interfețe care implementează acest algoritm propun să „picteze” zonele care trebuie păstrate, ceea ce are ca efect creșterea nivelului lor de energie în execuția algoritmului. În cazul fețelor, pot fi utilizați algoritmi de recunoaștere facială .
Prin eliminarea unei căi de energie mai mici, algoritmul uneori tinde să creeze căi de energie ridicată (prin apropierea pixelilor care au un contrast puternic între ei). Pentru a evita această capcană, este posibil să simulați consecințele eliminării unei căi și să calculați diferența de energie a ansamblului pentru a vedea dacă crește. Dacă da, poate fi mai bine să alegeți o altă cale de șters
Note și referințe
- (fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia engleză intitulat „ Seam carving ” (a se vedea lista autorilor ) .
- (ro) Shai Avidan și Ariel Shamir, „ Sculptură de cusătură pentru redimensionarea imaginii conștiente de conținut ” , SIGGRAPH ,Iulie 2007( citiți online , consultat la 17 iulie 2020 )
- (în) Aditya Bist și Vinay Palakkode, " Parallel Seam Carving " pe cmu.edu , Universitatea Carnegie Mellon ,2016(accesat la 17 iulie 2020 )
- (în) „ Ce este nou în Adobe Photoshop CS4 ” pe photoshopsupport.com (accesat la 17 iulie 2020 )
- (în) „ Scalare conștientă de conținut ” pe knowyourmeme.com ,6 noiembrie 2013(accesat la 17 iulie 2020 )
- (ro) Plugin GIMP Liquid Rescale
- (în) Nou instrument de redescalcare a lichidului în construcție ...
- (în) Rescale lichide - Sculptură de cusături
- (în) Smart Resizer - Redimensionarea fotografiilor fără redescalarea subiectului!
- (în) Michael Rubinstein, Ariel Shamir și Shai Avidan, „ Seam Carving îmbunătățit pentru retargeting video ” [PDF] , SIGGRAPH ,2008(accesat la 17 iulie 2020 )
- (în) Michael Rubinstein, Ariel Shamir și Shai Avidan, „ Îmbunătățire a cusăturii pentru retargeting video ” .