Algorytm deformacji

1 lip 2009 - pawel.salek

dodajdo.com

Wybór algorytmu:

Po dłuższym namyśle zapadła decyzja, aby docelowa aplikacja pozwalała na możliwie najłatwiejszą lokalną deformację. Innymi słowy – do zdeformowania pojedynczego fragmentu obrazu wymagane powinno być jak najmniej punktów kontrolnych (a konkretnie dwa: źródłowy i docelowy). Zadaniem algorytmu jest przesunięcie otoczenia punktu źródłowego w otoczenie punktu docelowego, z jednoczesnym zachowaniem ciągłości obrazu.

Założenia:

Informacją wejściową dla algorytmu deformującego są:

  • obraz wejściowy
  • punkt źródłowy (xs, ys)
  • punkt docelowy (xt, yt)
  • promień oddziaływania punktów (r), określający zasięg oddziaływania punktu źródłowego i docelowego
  • waga deformacji (Wi), określająca siłę, z jaką „okolica punktu źródłowego” zostanie „wypchnięta” w kierunku punktu docelowego

Opis algorytmu:

Etapy opracowanego algorytmu są następujące:

1. Ustalenie równania prostej przechodzącej przez punkt źródłowy i docelowy.

Algorytm deformacji - wyznaczenie prostej deformującej oraz właściwego punktu docelowego
Rys.1. Wyznaczenie prostej deformującej oraz właściwego punktu docelowego

2. Wyznaczenie wielkości przesunięcia na podstawie wagi deformacji (Wi). Na podstawie przesunięcia ustalany jest nowy, chwilowy (dla danej klatki animacji) punkt docelowy (xt’, yt’) (kolor czerwony na rys. 1)

3. Wyznaczenie ?obszaru zainteresowania”, na podstawie wagi deformacji (Wi) (czerwona ramka na rys. 2).
Dalsze operacje przeprowadzane będą wyłącznie na tym obszarze. Obszar zainteresowania określa fragment docelowego obrazu (obszar docelowy), na który będzie rzutowany odpowiadający fragment źródłowego obrazu (obszar źródłowy).

Rys.2. Obszar zainteresowania (czerwony) oraz obszar źródłowy (niebieski)

Rys.2. Obszar zainteresowania (czerwony) oraz obszar źródłowy (niebieski)

4. Wyznaczenie obszaru źródłowego (kolor niebieski na rys.2). Punkt z tego obszaru będą rzutowane na obszar docelowy.

5. Dla każdego z pikseli należących do obszaru docelowego (xj, yj) przeprowadzana jest następująca procedura:

  • Wyznaczenie wartości wagi podłużnej danego piksela (Wpj)
  • Wyznaczenie wartości wagi poprzecznej danego piksela (Wtj)
  • Wyznaczenie wartości wagi lokalnej (Wloc)
  • „Ważone rzutowanie” obszaru źródłowego na docelowy w następujący sposób:
  1. Wyznaczenie odległości (d) pomiędzy pikselem obszaru docelowego (rys.3. kolor błękitny) a odpowiadającym mu pikselem obszaru źródłowego (rys.3. kolor czarny).
  2. Wyliczenie wagi (W) jako iloczynu W = Wi*Wtj*Wpj.
  3. Wyznaczenie nowej wartości przesunięcia (rys. 3) – W*d.
  4. Rzutem punktu j jest piksel przesunięty od niego o odległość W*d.
Rys.3. Zasada ważonego rzutowania

Rys.3. Zasada ważonego rzutowania

Zasada działania:

Najpierw rozważmy brak wag przy operacji rzutowania. Wówczas prostokąt źródłowy zostałby rozciągnięty na obszar docelowy. Na krawędziach powstałaby nieciągłość informacji obrazowej, co wyraźnie rzucałoby się w oczy.

Z tego powodu wprowadzone zostały wagi poprzeczne i podłużne. Służą one zapewnieniu ciągłości obrazu na krawędziach obszaru zainteresowania, gdzie przyjmują wartość zerową. W miarę oddalania od krawędzi wartość tych wag rośnie do 1.

Waga lokalna (Wloc) służy zapewnieniu płynności rzutowania. W pobliżu punktu docelowego przyjmuje wartość 1. Im dalej od punktu docelowego – tym mniejsza jest wartość wagi lokalnej. Maleje do zera na krawędzi leżącej po drugiej stronie punktu źródłowego.

Rezultat:

Przykładowy rezultat działania algorytmu przedstawiają rysunek 4 oraz 5. Uzyskany efekt jest zbliżony do znanego z popularnego, komercyjnego zestawu do edycji zdjęć oraz montażu video.

Rys.4. Ilustracja działania algorytmu: punkt źródłowy (a), punkt docelowy oraz funkcja wagi (b), efekt końcowy (c)

Rys.4. Ilustracja działania algorytmu: punkt źródłowy (a), punkt docelowy oraz funkcja wagi (b), efekt końcowy (c)

Rys.5. Efekt działania algorytmu deformacji

Rys.5. Efekt działania algorytmu deformacji

Podsumowanie:

Poprawa rezultatów polega głównie na dobraniu odpowiednich funkcji wagi. W przedstawianym przykładzie użyte zostały możliwie najprostsze – odcinkami liniowe. Dobierając kształt funkcji poszczególnych wag można w stosunkowo prosty sposób zmieniać charakter działania i rodzaj deformacji.

Kategoria Morpher | Komentarze są wyłączone