SeamCarving: Jak usunąć obiekt z obrazu przy pomocy skalowania?

25.04.2010 - Łukasz Milewski
TrudnośćTrudność

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.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com