Robust Image Retargeting via Axis Aligned Deformation

Slide1Robust Image Retargeting viaAxis-Aligned Deformation Mateusz Bujalski Daniele Panozzo                Ofir Weber                   Olga Sorkine

Slide2O co chodzi?Szerokość zdjęcia powiększona dwukrotnie. Mapa „ważności” stworzona za pomocą filtra wykrywającego krawędzie, poprawiona kilkoma maźnięciami. Czas obliczeń: ok. 4ms Czas użytkownika: ok. 30s

Slide3O co chodzi?• Chcemy zmienić rozmiar zdjęcia – Bez zachowania aspect ratio – Bez obcinania fragmentów zdjęcia – I żeby było dość podobne do oryginalnego – Fajnie mieć: realtime

Slide4Sposoby• Większość metod okazuje się być jakąś modyfikacją poniższego schematu – Zdefiniuj funkcję, którą będziesz optymalizował a następnie zminimalizuj ją biorąc pod uwagę ograniczenia rozmiaru obrazu wyjściowego – Z reguły przekształcenia afiniczne + wagi (mapa ważności) + dodatki w celu wyeliminowania artefaktów (np. rozmywanie krawędzi) • Istnieje trochę innych, ale często wyspecjalizowanych metod – np. w przypadku tekstur, można „doklejać” pasujące łaty

Slide5Skupimy się na metodach opartych nawarpingu

Slide6ProblemLiczba zmiennych w takich problemach optymalizacyjnych jest kwadratowa względem wymiarów obrazu - O(MxN) No i usuwanie „niepotrzebnych” nie zawsze działa.

Slide7Problem

Slide8Spostrzeżenie• Autorzy analizując działanie istniejących algorytmów zauważyli, że „niedawne” (w znaczeniu lepsze) algorytmy prawie zawsze używają deformacji, które są wyrównane do osi • Brak miejscowych obrotów ma sens, ponieważ, jeśli się miejscami takie obroty różnią to dostajemy dziwne obrazki

Slide9Trochę wyolbrzymione

Slide10WniosekAutorzy uznali, że skoro większość algorytmów nie korzysta z obrotów mimo, że sformułowanie problemu na to pozwala, to przestrzeń „deformacji wyrównanych do osi” jest tą właściwą dla tej operacji

Slide11Zalety• w większości przypadków miejscowe obroty są nieporządane – poprzedni obrazek, dodatkowo czasem obrócony obiekt może kawałkiem wypaść poza zdjęcie (jak na drugim zdjęciu) • Złożoność problemu optymalizacyjnego względem liczby zmiennych maleje do O(M+N)

Slide12•Można sobie wyobrazić, że czasem (gdy np. tło jest jednolitego koloru) obrócenie kawałka zdjęcia mogłoby dać lepszy efekt, niż takie przekształcenia • Brak gwarancji, że linie proste nie wyrównane do osi pozostaną proste! Wady

Slide13•Wymiary obrazu:  W -szerokość,  H -wysokość • Nakładamy na obraz równomierną kratę  N kolumn i  M  wierszy, każda komórka ma rozmiar:  W/N  – szerokość,  H/M  - wysokość • Programowanie kwadratowe Algorytm

Slide14Minimalizujemywersja ogólna

Slide15Minimalizujemywersja ogólna s jest niewiadomą Q i b możemy ustawić jakie chcemy, ale jeśli F(s) jest „dodatnio określona” to możemy użyć standardowych QP solverów

Slide16Minimalizujemywersja ogólna L h , L w  – minimalne rozmiary wierszy i kolumn

Slide17Czemu Lw  i L h  są ważne?

Slide18Minimalizujemywersja ogólna H L  i W L  – oczekiwane rozmiary obrazu wyjściowego

Slide19Minimalizujemywersja ogólna

Slide20Przykładowe definicje F(s)• Autorzy proponują dwie „najczęściej spotykane” definicje energii • ASAP – na podstawie „mapy ważności” stara się, aby zaznaczone obszary były odwzorowane jak najbardziej podobnie (As Similar As Possible) – tylko translacje i równomierne („uniform”) skalowanie • ARAP – (As Rigid As Possible) – wszystko poza translacjami i rotacjami jest karane (w naszym przypadku zostają tylko translacje, bo rotacje nie są brane pod uwagę z założenia

Slide21Przykładowe definicje F(s)

Slide22ASAP – minimalizacjaniejednorodnych skalowań W przestrzeni deformacji wyrównanych do osi przekształcenia podobieństwa   ograniczają się do kombinacji jednorodnych skalowań   (takie same we wszystkich kierunkach) i  translacji , ponieważ rotacje nie są brane pod uwagę z definicji

Slide23ASAP – przekształcenie do QP

Slide24ASAP – przekształcenie do QPKs – wektor zawierający energie dla wierszy Q = K T K, b = 0 => mamy formułę w postaci QP Q jest dodatnio określona

Slide25ARAP – wszystko pozatranslacjami jest karane • Wzorki są mało istotne • Te dwie energie zostały wybrane tylko dlatego, że pojawiają się często w innych pracach i zwykle dają niezłe rezultaty • Podobno nic nie stoi na przeszkodzie, żeby podobnie jak pierwszą zdefiniować inne • Można tworzyć z tych energii kombinacje liniowe i dalej jest dobrze

Slide26Regularyzacja Laplace’adodatkowa energia, która karze za duże różnice w rozmiarach sąsiednich wierszy/kolumn – przydatne w ręcznie malowanych mapach ważności, które są z reguły mocno skoncentrowane

Slide27Rezultaty• Czas rzeczywisty dla zdjęć HD na laptopie sporo gorszym niż ten (używa 1 core CPU) • ASAP z reguły lepszy niż ARAP • Eksperymenty z automatycznym generowaniem „map ważności” – cała metoda jest niezależna od rodzaju mapy i można się bawić • Dobrze działa tryb pół automatyczny: najpierw metoda generuje nam mapę automatyczną, a potem ją troszkę poprawiamy zaznaczając naprawdę ważne fragmenty

Slide28Obrazki i działającyprogram na żywo!