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

25.04.2010 - Łukasz Milewski
TrudnośćTrudność

Skalowanie obrazu - pomniejszanie

W tym momencie mamy wszystkie operacje potrzebne do usunięcia szwu. Aby zmniejszyć szerokość obrazu o k pikseli musimy k razy wykonać następujące operacje:

  1. Znajdź szew o najmniejszej energii
  2. Usuń znaleziony szew
Można to zrobić np. przy pomocy poniższej funkcji:

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void retarget(Image* image, int dest_width, int dest_height) {
    int dx = dest_width - image->width;
 
    // pomniejszaj obraz tak dlugo az osiagnie wymagany rozmiar
    while (dx < 0) {
        if (dx < 0) { // pomniejszanie w poziomie
            std::vector<int> vseam;
            find_minimal_vertical_seam(*image, &vseam);
            remove_vertical_seam(image, vseam);
            ++dx;
        }
    }
}    
  

Skalowanie obrazu - powiększanie

Jak już wspomnieliśmy wcześniej, aby powiększyć obraz nie wystarczy postępować tak samo jak w przypadku pomniejszania. Wszystkie duplikowane szwy musimy znaleźć jednocześnie - na samym początku. Mając k szwów o najmniejszych energiach możemy je wszystkie zduplikować, otrzymując obraz szerszy o k pikseli. W rzeczywistości znajdowanie k szwów jest bardzo podobne do znajdywania jednego szwu, jednak nie wystarczy wykonać tej operacji k razy. Musimy zadbać o to, aby szwy nie nachodziły na siebie. W tym celu definiujemy stałą c_seam_energy, która oznacza bardzo dużą energię. Dzięki temu gwarantujemy, że optymalne szwy nigdy nie będą przechodziły przez piksel należący do innych szwów. Zauważmy, że po obliczeniu jednego szwu jesteśmy zmuszeni od nowa policzyć całą tablicę z energiami, gdyż znaleziony szew mógł w znaczący sposób wpływać na obliczone energie. Poniższy kod wykonuje tę operację

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int c_seam_energy = 1<<21;
 
void find_many_minimal_vertical_seams(Image img, 
                 std::vector<std::vector<int> >* result, int k) {
    // image_seams: true = w tym miejscu przebiega szew
    std::vector<std::vector<bool> > image_seams; 
 
    image_seams.resize(img.height);
    for (int y = 0; y < img.height; ++y) {
        image_seams.at(y).resize(img.width);
    }
 
    result->clear();
    result->resize(k);
    int seams_count = 0;
    for (int i = 0; i < k; ++i) {
        std::vector<std::vector<int> > cumulated_energy;
        compute_vertical_cumulated_energy(img, &cumulated_energy);
 
        // znajdz pierwszy punkt, ktory moze byc koncem szwu
        int min_x = 0;
        while (min_x < img.width 
              && image_seams.at(img.height-1).at(min_x)) {
            min_x++;
        }
 
        if (min_x >= img.width) {
            return; // nie ma już szwów do usunięcia
        }
 
        // znajdz koniec optymalnego szwu
        for (int x = 1; x < img.width-1; ++x) {
            if (!image_seams.at(img.height-1).at(x)) {
                if (cumulated_energy.at(img.height-1).at(x) 
                    < cumulated_energy.at(img.height-1).at(min_x)) {
                    min_x = x;
                }
            }
        }
 
        // znajdz szew
        int x = min_x;
        result->at(i).push_back(x);
        image_seams.at(img.height-1).at(x) = true;
        img.energy.at(img.height-1).at(x) = c_seam_energy;
        for (int y = img.height-2; y >= 0; --y) {
            int new_x = x;
            if (x > 0 
                && cumulated_energy.at(y).at(x-1) 
                     < 
                   cumulated_energy.at(y).at(new_x)) {
                new_x = x-1;
            }
            if (x < img.width-1 
                && cumulated_energy.at(y).at(x+1)  
                     < 
                   cumulated_energy.at(y).at(new_x)) {
                new_x = x+1;
            }
 
            x = new_x;
 
            if (image_seams.at(y).at(x)) {
                result->resize(seams_count);
                return;
            }
 
            result->at(i).push_back(x);
            image_seams.at(y).at(x) = true;
            img.energy.at(y).at(x) = c_seam_energy;
        }
 
        seams_count++;
        std::reverse(result->at(i).begin(), result->at(i).end());
    }
}
  

Zauważmy, że funkcja ta jako argument przyjmuje k - liczbę szwów do odnalezienia. Mimo to nie możemy zagwarantować, że uda się znaleźć tyle szwów (pierwszych kilka może zablokować wszystkie pozostałe. Dlatego nasza funkcja zwaraca liczbę odnalezionych szwów. Aby powiększyć obraz o k pikseli trzeba iterować wywołania powyższej funkcji tak długo, aż łącznie nie poszerzymy obrazu o k pikseli.

Podaną wcześniej funkcję retarget możemy zmodyfikować następująco, aby obslugiwała poszerzanie obrazów.

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void retarget(Image* image, int dest_width, int dest_height) {
    int dx = dest_width - image->width;
 
    // pomniejszaj obraz tak dlugo az osiagnie wymagany rozmiar
    while (dx < 0) {
        if (dx < 0) { // pomniejszanie w poziomie
            std::vector<int> vseam;
            find_minimal_vertical_seam(*image, &vseam);
            remove_vertical_seam(image, vseam);
            ++dx;
        }
    }
 
    // sprawdz czy trzeba powiekszyc obraz. Jezeli tak to zrob to
    while (dx > 0) {
        std::vector<std::vector<int > > vseams;
        find_many_minimal_vertical_seams(*image, &vseams, dx);
        add_vertical_seams(image, vseams);
        dx -= vseams.size();
    }
}    
  

Prosta sztuczka, czyli wzmacnianie zawartości obrazu

Potrafimy już powiększać i pomniejszać obrazy. Eksperymentowanie z różnymi obrazami jest fascynujące. Bawiąc się nimi można zauważyć pewną właściwość. Przy pomniejszaniu obiekty, które są istotne dla obrazu (mają dużą wartość energii) zazwyczaj nie zostają naruszone, podczas gdy inne elementy mogą znikać z obrazu lub zmniejszać się.

W pomniejszonym obrazie elementy z dużą wartością energii są takie same jak na obrazie pierwotnym - można zatem powiedzieć, że powiększyły się względem reszty obrazu. Zauważmy dodatkowo, że w pomniejszonym obrazie jest mniej szwów z małą energią niż w obrazie wejściowym. Wynika stąd, że jeżeli spróbujemy powiększyć nasz pomniejszony obraz to jako k szwów do duplikacji będziemy wybierali spośród tych o dużej energii.

Powyższe obserwacje prowadzą do wniosku, że jeżeli pomniejszymy obraz o k pikseli, a następnie wynik powiększymy o k pikseli to na obrazie wyjściowym elementy o dużej energi będą większe niż na obrazie wejściowym. Ten efekt nazywamy wzmocnieniem zawartości obrazu - elementy istotne stają się większe, przez co wydają się być jeszcze ważniejsze.

Poniższa funkcja wczytuje obraz, pomniejsza go, a następnie powiększa i zapisuje wynik do pliku "output.bmp".

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void amplify(const std::string& fname, int horizontal_amplification,
             int vertical_amplification) {
 
    // wczytaj obrazek
    Image image;
    if (!load_image(&image, fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }
 
    compute_image_energy(&image);
 
    // pomniejsz, a nastepnie powieksz obrazek
    int original_width = image.width;
    int original_height = image.height;
    int amplify_width = image.width * horizontal_amplification / 100;
 
    retarget(&image, amplify_width, original_height);
    retarget(&image, original_width, original_height);
 
    store_image(image, "output.bmp");
}

Coś, na co wszyscy czekamy - usuwanie obiektów

Okazuje się, że program implementujący algorytm SeamCarving bardzo łatwo jest rozszerzyć o możliwość usuwania obiektów z obrazu. Ogólne podejście jest takie jak przy wzmacnianiu - najpierw pomniejszamy obraz, a następnie przywracamy jego pierwotny rozmiar. Jednak dodatkowo dbamy o to, aby podczas usuwania, szwy przechodziły przez wybrany przez nas obszar. Będziemy pomniejszali obraz tak długo, jak długo będą istniały piksele z obszaru do usunięcia. Otrzymamy w ten sposób pomniejszony obraz bez nieinteresującago nas obszaru. Powiększenie do pierwotnego rozmiaru sprawi wrażenie, że obiekt został usunięty.

Pozostaje pytanie jak zmusić algorytm, żeby wybierał szwy przechodzące przez wybrany przez nas obszar. We wstępie widzieliśmy jak zaznaczamy fragment obrazu do usunięcia na zielono. Nie robiliśmy tego bez przyczyny. Otóż stworzymy dla algorytmu drugi obraz wejściowy - maskę. Następnie zmodyfikujemy obliczoną przez nas energię tak, że w miejscach, w których maska jest zielona ustawimy bardzo małą energię (ujemną), a w miejscach gdzie jest czerwona bardzo dużą. Pozostałych pikseli nie będziemy ruszali. Dzięki temu uzyskamy możliwość podpowiadania algorytmowi, które piksele nas nie interesują (zielona maska), a które są bardzo ważne (czerwona maska).

Działanie w praktyce już widzieliśmy, teraz zobaczmy jak może wyglądać implementacja. Funkcja add_energy Dodaje do policzonej już energii obrazu, energię pochodzącą z maski zapisanej jako obraz. Przeciążamy również funkcję compute_image_energy. Do implementacji, którą już widzieliśmy dodajemy nową, która najpierw wywołuje poprzednią, a następnie dodaje energię z maski przy użyciu add_energy

Jest jeden szczegół, na który warto zwrócić uwagę podczas implementacji. Może się zdarzyć tak, że zostanie jeden piksel z małą energią i przez wiele kolejnych iteracji nie zostanie usunięty. Wówczas obraz zostanie niepotrzebnie zniekształcony. Dlatego warto liczyć ile zostało pikseli z ujemną energią i jeżeli jest ich mało, a przez kilka ostatnich ruchów żadnego nie usunęliśmy, to kończymy działanie algorytmu tak, jakby ich nie było.

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const int c_negative_energy = -255;
 
void add_energy(Image* img, const Image& energy) {
    img->negative_energy_count = 0;
    for (int y = 0; y < img->height; ++y) {
        for (int x = 0; x < img->width; ++x) {
            if (energy.data.at(y).at(x).r == 255) { // czerwone chronimy
                img->energy.at(y).at(x) = 255;
            }
            else if (energy.data.at(y).at(x).g == 255) { // zielone usuwamy
                img->energy.at(y).at(x) = c_negative_energy;
                img->negative_energy_count++;
            }
        }
    }
}
 
void compute_image_energy(Image* img) {
    img->energy.resize(img->height);
    for (int y = 0; y < img->height; ++y) {
        img->energy.at(y).resize(img->width);
        for (int x = 0; x < img->width; ++x) {
            compute_pixel_energy(img, x, y);
        }
    }
}
 
void compute_image_energy(Image* img, const Image& energy) {
    compute_image_energy(img);
    add_energy(img, energy);
}
 
void remove_objects(const std::string& fname,
                    const std::string& energy_fname, int mode) {
    // wczytaj obrazek
    Image image;
    if (!load_image(&image, fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }
 
    // oblicz energię obrazka (uwzgledniajac plik z energia)
    Image energy;
    if (!load_image(&energy, energy_fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }
    compute_image_energy(&image, energy);
 
    // pomniejszaj obrazek az nie bedzie juz miejsc 'do usuniecia'
    int original_width = image.width;
    int original_height = image.height;
    int count = 0;
    int no_change_steps = 0; // przez ile krokow nie zmieniala
                              // sie negatywna energia
    while (image.negative_energy_count > 0) {
        ++count;
        size_t last_negative_energy = image.negative_energy_count;
 
        retarget(&image, image.width-1, image.height);
 
        ++no_change_steps;
        if (last_negative_energy != image.negative_energy_count) {
            no_change_steps = 0;
        }
        if (no_change_steps > 5 && image.negative_energy_count < 5) {
            break;
        }
    }
 
    // usun negatywna energie (nie moze przeszkadzac w powiekszaniu
    for (int y = 0; y < image.height; ++y) {
        for (int x = 0; x < image.width; ++x) {
            if (image.energy.at(y).at(x) == c_negative_energy) {
                compute_pixel_energy(&image, x, y);
            }
        }
    }
 
    // przywroc pierwotny rozmiar obrazka
    retarget(&image, original_width, original_height);
 
    store_image(image, "output.bmp");
}
  

Nie tak idealnie - artefakty

Jeżeli chcemy być uczciwi, to nie powinniśmy milczeć na temat pewnego drobiazgu. Algorytm SeamCarving nie jest idealny i nie każdy obraz daje się pomniejszyć tym algorytmem. Często powstają bardzo widoczne artefakty. Jest to jednen z powodów, dlaczego usuwania obiektów nie demonstrowaliśmy na obrazie z kotem. Sprawdzenie algorytmu na różnych obrazach pozwala dojść do pewnych wniosków kiedy warto użyć SeamCarving a kiedy nie. Przykładem moze być zbyt duże pomniejszenie obrazu - wówczas często uzyskujemy obrazy, które są mało realistyczne.

Nie powinniśmy traktować SeamCarving jako uniwersalnego narzędzia. Jest to raczej kolejne narzędzie w naszym warsztacie. Są sytuacje, w których daje dużo lepsze rezultaty niż wszystkie inne sposoby zmiany wymiarów obrazu. Można także znaleźć takie przykłady, gdzie zachowuje się znacznie gorzej. Nie zmienia to jednak faktu, że jest to algorytm, który przy pomocy prostych konstrukcji daje niesamowite efekty.

Co dalej?

SeamCarving to fascynujący algorytm. Jego konstrukcja udowadnia, że prosty pomysł może pozwalać na wykonywanie tak trudnych operacji, jak wycinanie fragmentu obrazu. Można łatwo rozszerzyć ten algorytm o możliwość skalowania obrazu w czasie rzeczywistym - wystarczy dla każdego piksela zapamiętać, w którym kroku algorytmu został usunięty. Kolejnym znanym uogólnieniem jest skalowanie filmów. Dokonali tego autorzy algorytmu SeamCarving rok po jego opublikowaniu. Na stronie poświęconej ulepszonej wersji algorytmu można obejrzeć krótki film, który pokazuje jak to zrobić. Wspomniana strona jest w języku angielskim.

Przykładowe aplikacje

Do artykułu jest załączona implementacja algorytmu SeamCarving w C++. Oprócz niej warto zainteresować się również wtyczką do programu Gimp.

Ćwiczenia

Główną operacją w algorytmie SeamCarving jest usuwanie po jedym pikselu w każdym wierszu. Można robić to na wiele sposobów. Wypróbujmy kilka prostych.

  1. Zmień program tak, aby zamiast usuwać szwy, usuwał piksel o najmniejszej energii w każdym wierszu
  2. Zmień program tak, aby zamiast usuwać szwy, usuwał całe kolumny o najmniejszej energii
  3. Zmień program tak, aby zamiast usuwać szwy, usuwał piksele wg Twojego pomysłu
  4. Czy któraś z tych metod daje satysfakcjonujące wyniki?

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com