Najlepsze algorytmy to takie, które korzystają z
prostych idei i jednocześnie mają bardzo ciekawe
zastosowania. Niewątpliwie jednym z nich jest SeamCarving - algorytm opracowany w 2007
roku. Skaluje obrazy, biorąc pod uwagę ich
zawartość. Jednym z jego najbardziej praktycznych zastosowań jest usuwanie
obiektów ze zdjęć.
Czego się nauczymy?
Znamy wiele metod zmiany rozmiarów obrazów. Prawie żadna z nich nie
bierze pod uwagę zawartości obrazu. Może to powodować pojawianie się
artefaktów po zastosowaniu takiego algorytmu. Np. jeżeli powiększymy
zdjęcie w poziomie, wszystkie obiekty na przeskalowanym zdjęciu
będą "grubsze" niż w rzeczywistości - stosunek ich szerokości do
wysokości nie zostanie zachowany. Opisany efeket widać doskonale na
poniższych obrazkach.
Jeżeli użyjemy programu do obróbki grafiki (np. Gimp), uzyskamy taki efekt:
Używając algorytmu SeamCarving do skalowania obrazu, zachowamy proporcje ciała kota:
Nie ma wątpliwości, że algorytm SeamCarving daje w tym przypadku
znacznie lepsze wyniki. Nauczymy się, jak zaimplementować ten sposób
skalowania.
Poznamy także inne zastosowanie SeamCarving - można przy jego
pomocy np. "wzmacniać" obrazy, czyli wyciągać na pierwszy plan
najważniejsze elementy. W naszym przypadku kot jest ważniejszy niż
tło. Algorytm automatycznie to wykrywa. Popatrzmy na poniższe
porównanie.
Pierwszy obraz to obraz początkowy, drugi to ten sam obraz, lecz już po wzmocnieniu w poziomie.
Ostatnie zastosowanie, jakie poznamy to usuwanie obiektów z
obrazu. To, co chcemy osiągnąć, widać świetnie na poniższych
obrazkach. Pierwszy to zdjęcie, z którego usuniemy obiekt. Na drugim
obrazie zaznaczamy obszar do usunięcia. Trzeci obrazek to samo
zaznaczenie. Ostatni obraz jest już wynikiem działania algorytmu SeamCarving.
Razem zaimplementujemy wszystkie powyższe zastosowania algorytmu
SeamCarving - w przedstawionej kolejności. Do artykułu jest
dołączony kod źródłowy programu (link znajduje się na końcu artykułu), który
posłużył do wygenerowania wszystkich obrazów pokazanych w tej publikacji.
Skupimy się na operacjach skalowania w poziomie. Operacje dla
skalowania w pionie są analogiczne. Kod dołączony do artykułu
zawiera implementację obu typów skalowania.
Kluczowe operacje - pomniejszanie i powiększanie
Alogrytm SeamCarving składa się z dwóch prostych operacji -
powiększania i pomniejszania obrazu. Odpowiednio je składając,
uzyskuje się kolejne zastosowania algorytmu. Popatrzmy, jak ogólnie
wyglądają te operacje, abyśmy mogli szybko przejść do szczegółów.
Pomniejszanie
Aby zmniejszyć szerokość obrazu o k pikseli, wystarczy k razy
zmniejszyć ją o jeden piksel. Z kolei, aby zmniejszyć szerokość o
jeden, wystarczy z każdego wiersza usunąć jeden piksel. Można to
zrobić na różne sposoby. Pierwszy poznamy za chwilę, dwa inne są
dobrym materiałem na ćwiczenia.
Sąsiedztwem piksela będziemy nazywali wszystkie te piksele, z którymi
sasiaduje w pionie, w poziomie i po skosach. Na poniższym obrazku
widać zielony piksel i jego sąsiedztwo (zaznaczone na czerwono).
Jeżeli zaznaczymy piksel na górze obrazka i będziemy wybierali w
każdym kolejnym wierszu jeden piksel, który sąsiaduje z poprzednio
wybranym, otrzymamy tak zwany szew. Szwy są podstawowym pojęciem
w algorytmie SeamCarving. Poniższy obrazek przedstawie przykładowy
szew.
Jeżeli usuwalibyśmy losowe szwy, moglibyśmy spodziewać się losowo
poszarpanego obrazu po zakończeniu usuwania. Zamiast tego będziemy
usuwali takie szwy, które naszym zdaniem wnoszą najmniej treści do
obrazu.
Zobaczmy, jak działa w praktyce pomniejszanie obrazka. Pierwszy z
poniższych obrazków przedstawia góry. Drugi jest animacją, która
pokazuje, jak są usuwane kolejne optymalne szwy. Animacja jest
zbudowana tak, że zawsze najpierw na obrazku zaznaczamy szew w
postaci czerwonej łamanej, a w następnej klatce usuwamy go. Dzięki
temu możemy dokładnie zobaczyć, jak działa algorytm pomniejszania.
Pokaż/ukryj animację
Powiększanie
Nietrudno się domyślić, że aby poszerzyć obrazek o jeden piksel,
wystarczy w każdym wierszu dodać jeden piksel. Zatem operacja
poszerzania jest analogiczna do pomniejszania. Różnica jest taka, że
zamiast usuwać znaleziony szew, duplikujemy go. Kolor nowego piksela
to średnia kolorów jego dwóch sąsiadów (lewego i prawego).
Jest jednak drobna pułapka! Zauważmy, że jeżeli będziemy postępować
tak, jak poprzednio - generujemy szew, duplikujemy, generujemy szew,
duplikujemy itd., będziemy ciągle duplikować ten sam szew (lub jego
okolice), co spowoduje pojawienie się artefaktów na obrazie. Jest to
pokazane na poniższej ilustracji. Po lewej stronie widzimy, do czego
prowadzi proste duplikowanie szwów (widoczny jest pas po lewej
stronie, który wygląda bardzo nierealistycznie). Po prawej stronie
widzimy powiększony do takich samych rozmiarów obraz wejściowy. W
tym przypadku najpierw generujemy szwy do duplikacji i duplikujemy
wszystkie jednocześnie. Musimy jedynie zadbać o to, aby wygenerowane
szwy nie przecinały się.
Na poniższych obrazkach widzimy ponownie kota w śniegu. Kolejny
obraz to ten sam kot po dodaniu 25 szwów. Na ostatnim obrazie
widzimy opisany powyżej efekt zduplikowania szwów.