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

morpher – postępy

19 maj 2009 - pawel.salek

dodajdo.com

Wybrane zostało środowisko, w którym realizowany będzie projekt.

Po przeglądzie dostępnych rozwiązań wybrane zostało środowisko QT na licencji LGPL, co oznacza, że źródła projektu zostaną udostępnione.

Zastosowanie QT jest dla nas nowym wyzwaniem. We wcześniejszych projektach realizowanych na własny użytek posługiwaliśmy się narzędziami wykorzystującymi SDL i podobne biblioteki graficzne. Dlatego QT w połączeniu z C++ jest znaczącym krokiem do przodu.

Aktualnie trwają prace w obszarach:

  • algorytmu deformacji obrazu
  • interfejsu graficznego

O dalszych postępach postaram się informować na bieżąco.

Kategoria Morpher | Komentarze są wyłączone

Morpher – założenia

10 maj 2009 - pawel.salek

dodajdo.com

Morpher ma być niezależną aplikacją realizującą morphing dwóch sekwencji obrazów.

Założenia wstępne:

- Dowolna ilość punktów bazujących

- Automatyczny tracking punktów bazujących, z możliwością manualnej korekty

Zastosowanie: efekty specjalne przy produkcji filmowej.

Możliwie prosty interfejs, bez zbędnych elementów. Aplikacja nie powinna być kombajnem montażowo-edycyjnym, lecz intuicyjnym narzędziem służącym wyłącznie do morphingu.

Aktualnie trwają prace nad wyborem środowiska i biblioteki graficznej. O dalszych postępach będę informował w tej kategorii.

Kategoria Morpher | Komentarze są wyłączone