Řezání švů - Seam carving




Řezání švů (nebo změna měřítka kapaliny) je algoritmus pro sledování obsahu změna velikosti obrázku, vyvinutý společností Shai Avidan, z Mitsubishi Electric Research Laboratories (MERL) a Ariel Shamir, z Interdisciplinární centrum a MERL. Funguje stanovením řady švy (cesty nejméně důležité) v obrázku a automaticky odstraní švy, aby se zmenšila velikost obrázku, nebo vloží švy, aby se rozšířil. Řezání švů také umožňuje ručně definovat oblasti, ve kterých nemusí být pixely upravovány, a nabízí možnost odstranit z fotografií celé objekty.
Účelem algoritmu je retargeting obrazu, což je problém zobrazování obrázků bez zkreslení na médiích různých velikostí (mobilní telefony, projekční plátna) pomocí standardů dokumentů, jako je HTML, které již podporují dynamické změny v rozvržení stránky a textu, ale ne v obrazech .[1]
Image Retargeting vynalezli Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher a Bruce Gooch v roce 2005.[2] Práce Setlura a kol. získal v roce 2015 ocenění za 10letý dopad.
Švy
Švy mohou být svislé nebo vodorovné. Svislý šev je cesta obrazových bodů spojených shora dolů na obrázku s jedním pixelem v každém řádku.[1] Horizontální šev je podobný, s výjimkou připojení zleva doprava. Funkce důležitosti / energie hodnotí pixel měřením jeho kontrastu s jeho sousedními pixely.
Proces
Níže uvedený příklad popisuje proces vyřezávání švů:
Krok | obraz |
---|---|
1) Začněte s obrázkem. | ![]() |
2) Vypočítejte hmotnost / hustotu / energii každého pixelu. Toho lze dosáhnout pomocí různých algoritmů: velikost gradientu, entropie, vizuální charakteristika, pohyb očí.[1] Zde používáme gradientovou velikost. | ![]() |
3) Z energie vytvořte seznam švů. Švy jsou řazeny podle energie, přičemž švy s nízkou energií mají pro obsah obrázku nejméně důležitý význam. Švy lze vypočítat pomocí níže uvedeného přístupu dynamického programování. | ![]() |
4) Podle potřeby odstraňte nízkoenergetické švy. | ![]() |
5) Konečný obrázek. | ![]() |
Švy, které se mají odstranit, závisí pouze na rozměru (výšce nebo šířce), který chcete zmenšit. Je také možné invertovat krok 4, aby se algoritmus zvětšil v jedné dimenzi kopírováním nízkoenergetického švu a zprůměrováním jeho pixelů se svými sousedy.[1]
Výpočetní švy
Výpočet švu spočívá v nalezení cesty minimálních nákladů na energii z jednoho konce obrazu na druhý. To lze provést pomocí Dijkstrův algoritmus, dynamické programování, chamtivý algoritmus nebo řezy grafů mezi ostatními.[1]
Dynamické programování
Dynamické programování je programovací metoda, která ukládá výsledky dílčích výpočtů, aby se zjednodušil výpočet složitějšího výsledku. Dynamické programování lze použít k výpočtu švů. Pokud se pokoušíme vypočítat svislý šev (cestu) s nejnižší energií, pro každý pixel v řadě spočítáme energii aktuálního pixelu plus energii jednoho ze tří možných pixelů nad ním.
Na obrázcích níže je znázorněn proces DP k výpočtu jednoho optimálního švu.[1] Každý čtverec představuje pixel, přičemž hodnota vlevo nahoře v červené barvě představuje energetickou hodnotu uvedeného pixelu. Hodnota v černé barvě představuje kumulativní součet energií vedoucích k tomuto pixelu včetně.
Horní řada nemá nic nad sebou, takže energie jsou stejné jako zdrojový obraz.
Pro každý pixel ve zbytku řádků je energie jeho vlastní energií plus minimální ze tří výše uvedených energií. Opakujte, dokud nedosáhnete spodní části.
U nejnižších energií, které máme na konci, pracujte zpět na minimech, abyste obnovili šev s minimální energií.
Výpočet energie je u jednoduchých funkcí triviálně paralelizován. Výpočet pole DP lze také paralelizovat s nějakou meziprocesovou komunikací. Problém vytváření více švů současně je však těžší ze dvou důvodů: pro správnost je nutné regenerovat energii pro každé odstranění a pouhé zpětné vysledování více švů může vytvářet přesahy. Avidan 2007 spočítá všechny švy tak, že iterativně odstraní každý šev a uloží „indexovou mapu“, která zaznamená všechny generované švy. Mapa obsahuje číslo „n-tého švu“ pro každý pixel na obrázku a lze ji později použít k úpravě velikosti.[1]
Pokud však oba problémy ignorujete, je možné chamtivé přiblížení pro vyřezávání paralelních švů. Chcete-li tak učinit, jeden začíná pixelem s minimální energií na jednom konci a stále volí cestu minimální energie na druhý konec. Použité pixely jsou označeny tak, aby nebyly znovu vybrány.[3] Pro lepší přiblížení lze pro menší části obrazu paralelně vypočítat také místní švy.[4]
Problémy
- Algoritmus může potřebovat informace poskytnuté uživatelem, aby se snížily chyby. To může spočívat v malování oblastí, které mají být zachovány. U lidských tváří je možné použít detekci obličeje.
- Někdy může algoritmus odstraněním švu s nízkou energií neúmyslně vytvořit šev s vyšší energií. Řešením je simulovat odstranění švu a poté zkontrolovat energetickou deltu a zjistit, zda se energie zvyšuje. Pokud ano, upřednostněte místo toho jiné švy.[5]
Implementace
Adobe Systems získal nevýhradní licenci na technologii řezání švů od společnosti MERL,[6] a implementoval to jako funkci v Photoshop CS4, kde se nazývá Content Aware Scaling.[7]Jelikož je licence nevýhradní, patří mezi ně i další populární aplikace pro počítačovou grafiku GIMP, digiKam, ImageMagick, stejně jako některé samostatné programy, mezi které patří iResizer,[8] také mají implementace této techniky, z nichž některé jsou vydány jako bezplatný open source software.[9][10][11]
Vylepšení a rozšíření
- Lepší funkce energie a aplikace na video zavedením švů 2D (čas + 1 D).[5]
- Rychlejší implementace na GPU.[4]
- Multi-operator: Kombinujte s oříznutím a škálováním.[12]
- Mnohem rychlejší odstranění více švů[13]
Recenze osmi metod retargetingu v roce 2010 zjistila, že řezba švů přinesla výstup, který byl zařazen mezi nejhorší z testovaných algoritmů. Byla to však součást jednoho z nejvýše postavených algoritmů: výše zmíněné rozšíření pro více operátorů (v kombinaci s oříznutím a změnou měřítka).[14]
Viz také
Reference
- ^ A b C d E F G Avidan, Shai; Shamir, Ariel (červenec 2007). "Řezání švů pro změnu velikosti obrazu podle obsahu | Dokumenty ACM SIGGRAPH 2007". SIGGRAPH 2007: 10. doi:10.1145/1275808.1276390.
- ^ Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher a Bruce Gooch (prosinec 2005). „Automatické přesměrování obrázků“. MUM '05: Sborník ze 4. mezinárodní konference o mobilních a všudypřítomných multimédiích: 59–68. doi:10.1145/1149488.1149499. ISBN 0473106582.CS1 maint: používá parametr autoři (odkaz)
- ^ Bist; Palakkode (2016). „Paralelní řezba švů“. www.andrew.cmu.edu.
- ^ A b Chen-Kuo Chiang; Shu-Fan Wang; Yi-Ling Chen; Shang-Hong Lai (listopad 2009). „Rychlé zpracování videa na základě JND s akcelerací GPU pro přesměrování videa v reálném čase“. Transakce IEEE na obvodech a systémech pro videotechniku. 19 (11): 1588–1597. doi:10.1109 / TCSVT.2009.2031462.
- ^ A b Vylepšená řezba švů pro přesměrování videa. Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2008.
- ^ Tisková zpráva společnosti Mitsubishi Electric, Business Wire, 16. prosince 2008.
- ^ Seznam nových funkcí aplikace Adobe Photoshop CS4.
- ^ Software pro změnu velikosti obrazu iResizer od společnosti Teorex
- ^ Liquid Rescale, zásuvný modul pro vyřezávání švů pro GIMP
- ^ Oznámení o zařazení v digiKam
- ^ Součástí je možnost vyřezávání švů v ImageMagick
- ^ Přesměrování médií na více operátorů. Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2009.
- ^ Změna velikosti obrazu v reálném čase Science in China Series F: Information Sciences, 2009 SCIENCE IN CHINA PRESS. Archivováno 7. července 2011 na adrese Wayback Machine
- ^ Rubinstein, Michael; Gutierrez, Diego; Sorkine, Olga; Shamir, Ariel (2010). „Srovnávací studie retargetingu obrazu“ (PDF). Transakce ACM v grafice. 29 (5): 1–10. doi:10.1145/1882261.1866186. Viz také Benchmark RetargetMe.
externí odkazy
- Interaktivní ukázka vyřezávání švů
- Ukázková videa pro řezání švů:
- Na youtube
- na stránkách Ariel Shamir na webu Interdisciplinárního centra (vyšší rozlišení)
- Vysvětlení řezby švů (změna měřítka kapaliny) na ImageMagick webová stránka
- Výukový program pro vyřezávání švů