Content–Aware Image Resizing (dle článku Shaie Avidana a Ariela Shamira)
Václav Vlček (1. roč. NMgr., Teoretická informatika)
6.12.2007 1
O co jde? ■
Změna rozměrů obrázku se zachováním „významu“
Klasická změna rozměrů
Změna popisovanou technikou
2
K čemu je to dobré? ■
Různé velikosti displejů (počítač vs. PDA)
■ ■
Nutnost přizpůsobovat obrázky (např. webové stránky pro různé platformy, velikosti okna prohlížeče):
Náhledy v programech na správu obrázků Uvedené techniky lze použít i pro retuš 3
Základní myšlenka ■
Začneme se zkrácením obrazku o jeden pixel
■
Odebereme jeden pixel v každém řádku, ale který? Pixely s co nejmenší změnou vůči sousedům? Ve výsledném obrázku se mohou rozpadat hrany 4
Základní myšlenka (pokračování)
Sloupec pixelů s celkově nejmenší změnou?
Vede k podobným deformacím, jako klasické zmenšení, dokonce vypadá hůře (hrany).
8–souvislá spojnice shora dolů!
„Souvislá cesta která z obrázku odebere nejméně informace“
5
Formalismus a terminologie ■
Označme I: {1, ..., n}x{1, ..., m} → C obrázek velikosti n x m
■
Potřebujeme porovnávat kolik informace z obrázku ubylo Zavedeme si proto funkci e: I → R (energy function), která
změří množství informace (energie) v obrázku Zde budeme uvažovat pouze následující variantu:
∣
∣∣
∣
∂ ∂ e1 I x , y= I x , y I x , y ∂x ∂y (rozdíl od sousedů vlevo a vpravo)
■
(rozdíl od sousedů nahoře a dole)
8-souvislé cestě v obrázku shora dolů budeme říkat svislý šev (seam) m s x={siy }i=1 ={ xi ,i}mi=1 tak, že ∀ j∣x j−x j−1∣1 (8-souvislost) x: {1, …, m} → {1, ..., n} (na každém řádku vybereme pixel)
6
Formalismus a terminologie (pokr.) ■
K tomu, aby v obrázku zůstalo co nejvíce informace, musí jí odstraňovaný šev obsahovat co nejméně (mít co nejnižší energii)
Energie švu (součet energií jeho pixelů) m
E s=E I S =∑ e I si i=1
Chceme šev s minimální energií s* m
s∗=min s E s=min s ∑ e I si i=1
7
Jak hledat švy s minimální energií ■
Pomocí dynamického programování M i , j =ei , j minM i−1, j−1 , M i−1, j , M i−1, j1 e(i, j).......Energie pixelu M(i, j)......Váha minimální 8-souvislé cesty shora do pixelu (i, j)
■
Příklad: Váhy pixelů e 3 1 2 1 2 3 1 4 1 2 1 2
M(i, 0) = e(i, 0)
3 1 2 1
3 1 2 1 3 4 2 5
3 1 2 1 3 4 2 5 4 4 3 4
3 1 2 1 3 4 2 5 4 4 3 4 Minimum
8
Zúžení o pixel (shrnutí) 1.Najdi šev s nejměnší energií 2.Odeber jemu odpovídající pixely z obrázku a spoj obě části k sobě 3 1 2 1 2 3 1 4 1 2 1 2
3 2 1 2 3 4 1 2 2
3 2 1 2 3 4 1 2 2
9
Zobecňování ■
Zmenšení o pixel v obou směrech
■
Zmenšení o více pixelů
■
Odebereme svislý i vodorovný šev. Ale v jakém pořadí? V tom, které zachová více informace. Nejlepší pořadí lze najít pomocí dynam. progr. (další slajd)
Lze kombinovat tento přístup s běžným zmenšováním (zmenšit, aby souhlasila jedna hrana a pak odebírat švy)
Vhodný postup závisí na požadovaném výsledku
10
Optimální pořadí odebírání ■
Může být nalezeno opět pomocí technik dynamického programování
Vytváříme tabulku energií T(s, v), která bude udávat s jakou nejmenší ztrátou energie lze odebrat s svislých a v vodorovných švů (tj. zúžit obrázek o s a snížit o v) T(0, 0) = 0 – neodebrali jsme nic, žádná energie se neztratí x ➔ T(s, v) = min{ T(s – 1, v) + E(s (I )), Odebrání svislého (n–(s–1))x(m–v) T(s, v – 1) + E(sy(I(n–s)x(m–(v–1))))} Odebrání vodorovného ➔
Nejmenší možná ztracená energie obrázku, ze kterého bylo odebráno o šev méně ➔
Energie nejmenšího švu z většího obrázku
Při výpočtu si pamatujeme, které minimum se použilo a kterému švu odpovídalo (svislý vs. vodorovný). Když se dopočátáme k požadovanému zúžení, zpětným postupem vyčteme optim. pořadí. 11
Zvětšování obrázku ■
Postupujeme pozpátku
Najdeme šev s nejmenší energií, v tomto místě obrázek „roztrhneme“ a vložíme jeden pixel (spočítaný z pixelu vlevo a vpravo) – přidáme nejméně informace ➔
Pokud bychom obrázek zase zmenšovali, bude to pravděpodobně právě přidaný, který bude odstraněn. Není to však zaručeno.
Pro zvětšení o více pixelů si nejdříve spočteme, které švy bychom odebrali a v takovém pořadí, v jakém bychom je odebírali je zdvojujeme (případně cyklicky).
Musíme si je předpočítat předem. Jinak by se stále přidávalo do stejného místa (právě přidaný má nejmenší energii). ➔ Pokud chceme obrázek zvětšovat o mnoho, je pro zachování obsahu dobré postupovat v krocích (vždy spočítat švy pro zvětšení např. o 25 %, zvětšit a znovu spočítat), jinak se algoritmus chová jako klasické natažení. ➔
12
Předem neurčený rozměr ■
Není těžké si uvědomit, že šev lze nalézt v lineárním čase vzhledem k velikosti obrázku
■
Při hledání minimálního švu se v každém pixelu porovnají hodnoty v nejvýše třech nad ním
Celkem je tedy potřeba pro každý odebíraný šev vykonat lineární práci
To může být problém, pokud bychom chtěli algoritmus použít například na serveru Pro každý pixel předem spočítáme, v kolikátém kroku by byl odebrán ➔ Při zmenšování na požadovanou velikost odebereme všechny (až do čísla odpovídajícímu rozdílu velikostí) najednou ➔ Uvedená metoda však nefunguje pokud chceme provádět změnu v obou rozměrech ➔
13
Co když metoda selhává? ■
Lze použít jinou míru informace obsažené v obrázku
■
Použít umělou inteligenci (metody analýzy obrazu)
■
Některé možnosti jsou uvedeny a porovnány v článku Vyhledávání objektů (obličejů, …)
Použít přirozenou inteligenci
Dát uživateli možnost zvýšit nebo snížit energetickou funkci v některých oblastech obrázku To lze používat k retuši (snížíme energii těm pixelům, které chceme odstranit a obrázek zmenšíme)
14
Co lze udělat jinak? ■
Jiná energetická funkce (funkce pro porovnávání změn)
■
Místo 8-souvilslosti použít zobecnění s x={s yj }mj=1={ xi ,i}mj=1 tak, že ∀ j∣x j−x j−1∣k
Pro k = 0 je to svislá čára Pro k = 1 je to 8-souvislost Pro k > 1 je šev nesouvislý
15
Literatura a odkazy ■
Původní článek Shaie Avidana a Ariela Shamira
„Seam Carving for Content–Aware Image Resizing“
(http://www.faculty.idc.ac.il/arik/imret.pdf) ■
Implementace ve Flashi (http://rsizr.com/)
■
Článek na Grafice online – nevysvětluje princip, ale lze v něm nalézt odkazy na další Flashové implementace a pluginy pro Adobe Photoshop, GIMP, … (http://www.grafika.cz/art/sw/seamcarving.html) 16
