1

(dle článku Shaie Avidana a Ariela Shamira)

Content–Aware Image Resizing

Václav Vlček(1. roč. NMgr., Teoretická informatika)

6.12.2007

2

O co jde?

■ Změna rozměrů obrázku se zachováním „významu“

Klasická změna rozměrů Změna popisovanou technikou

3

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š

4

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

5

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“

6

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=∣ ∂∂ x

I x , y ∣∣ ∂∂ y

I x , y∣

sx={siy}i=1

m ={ x i , i }i=1m tak, že ∀ j∣x j −x j−1∣1

(8-souvislost)

(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)

x: {1, …, m} → {1, ..., n} (na každém řádku vybereme pixel)

7

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ů)

s∗=mins E s=mins∑i=1

m

e I si

Chceme šev s minimální energií s*

E s=E I S =∑i=1

m

e I si

8

Jak hledat švy s minimální energií

■ Pomocí dynamického programováníM i , j =e i , j min M i−1, j−1 , M i−1, j , M i−1, j1

e(i, j).......Energie pixeluM(i, j)......Váha minimální 8-souvislé cesty shora do pixelu (i, j)

■ Příklad:Váhy pixelů e

3 1 2 12 3 1 41 2 1 2

M(i, 0) = e(i, 0)

3 1 2 1 3 1 2 143 2 5

3 1 2 143 2 5

4 4 3 4

3 1 2 143 2 5

4 4 3 4

Minimum

9

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 12 3 1 41 2 1 2

3 2 12 3 41 2 2

3 2 12 3 41 2 2

10

Zobecňování

■ Zmenšení o pixel v obou směrech Odebereme svislý i vodorovný šev. Ale v jakém pořadí? V tom, které zachová více informace.

■ Zmenšení o více pixelů 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

11

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í➔ T(s, v) = min{ T(s – 1, v) + E(sx(I

(n–(s–1))x(m–v))),

T(s, v – 1) + E(sy(I(n–s)x(m–(v–1))

))}Odebrání svislého

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í.

12

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í.

13

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

14

Co když metoda selhává?

■ Lze použít jinou míru informace obsažené v obrázku Některé možnosti jsou uvedeny a porovnány v článku

■ Použít umělou inteligenci (metody analýzy obrazu) 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)

15

Co lze udělat jinak?

■ Jiná energetická funkce (funkce pro porovnávání změn)

■ Místo 8-souvilslosti použít zobecněnísx={s j

y}j=1m ={ x i , i }j=1

m 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ý

16

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)