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

25.04.2010 - Łukasz Milewski
TrudnośćTrudność

Podstawowe struktury, energia

Aby móc łatwo manipulować obrazami, potrzebujemy następujących struktur i funkcji:

  • Klasę reprezentującą kolor r,g,b
  • Klasę reprezentującą obraz
  • Funkcję uśredniającą dwa kolory
  • Funkcje do wczytywania i zapisywania obrazu
Wykorzystamy klasy std::vector oraz biblioteki SDL. Kolor będziemy reprezentować jako trzy składowe: czerwoną, zieloną i niebieską. Z obrazem będziemy pamiętali dwuwymiarowy wektor pikseli (kolorów), dwuwymiarowy wektor liczb całkowitych oznaczających wartość energii w danym punkcie, szerokość, wysokość oraz liczbę pikseli o negatywnej energii (to pole przyda się przy usuwaniu obiektów z obrazu). Implementacja tych struktur i funkcji może wyglądać następująco:

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
86
87
88
89
90
91
92
93
94
95
96
97
98
struct Color {
    Uint8 r;
    Uint8 g;
    Uint8 b;
 
    bool operator== (const Color& rhs) const {
        return r == rhs.r && g == rhs.g && b == rhs.b;
    }
};
 
Color mix_colors(const Color& c1, const Color& c2) {
    Color result;
    result.r = (c1.r + c2.r)/2;
    result.g = (c1.g + c2.g)/2;
    result.b = (c1.b + c2.b)/2;
    return result;
}
 
struct Image {
    std::vector<std::vector<Color> > data;
    std::vector<std::vector<int> > energy;
    int width;
    int height;
    size_t negative_energy_count; // liczba pikseli o ujemnej energii
};
 
void flip_image_vertically(Image* img) {
    for (int y = 0; y < img->height/2; ++y) {
        img->data.at(y).swap(img->data.at(img->height-y-1));;
    }
}
 
bool load_image(Image* result, const std::string& fname) {
    SDL_Surface* img = SDL_LoadBMP(fname.c_str());
    if (!img) {
        return false;
    }
 
    result->negative_energy_count = 0;
    result->width = img->w;
    result->height = img->h;
 
    result->data.resize(result->height);
    Uint8* pixels = reinterpret_cast<Uint8*>(img->pixels);
 
    for (int y = 0; y < result->height; ++y) {
        result->data.at(y).resize(result->width);
        for (int x = 0; x < result->width; ++x) {
            int current_pix = y * img->pitch + x * img->format->BytesPerPixel;
            Color c;
 
            c.b = pixels[current_pix+0];
            c.g = pixels[current_pix+1];
            c.r = pixels[current_pix+2];
 
            result->data.at(y).at(x) = c;
        }
    };
 
    SDL_FreeSurface(img);
    flip_image_vertically(result);
    return true;
}
 
bool store_image(Image img, const std::string& fname) {
    flip_image_vertically(&img);
    const int bpp = 3;
    SDL_Surface* output = SDL_CreateRGBSurface(SDL_SWSURFACE, img.width, img.height,
                                               bpp*8, 
                                               0xFF0000, 0x00FF00, 0x0000FF, 0);
    if (!output) {
        std::cerr << "Can not create output SDL_Surface";
        return false;
    }
 
    Uint8* pixels = reinterpret_cast<Uint8*>(output->pixels);
    for (int y = 0; y < img.height; ++y) {
        for (int x = 0; x < img.width; ++x) {
            int current_pix = y * output->pitch + x * output->format->BytesPerPixel;
            Color c = img.data.at(y).at(x);
            pixels[current_pix+2] = c.r;
            pixels[current_pix+1] = c.g;
            pixels[current_pix+0] = c.b;
        }
    }
 
    size_t last_dot = fname.find_last_of(".");
    if (last_dot == std::string::npos) {
        std::cerr << "Can not find extension of " << fname << "\n";
        return false;
    }
    std::string out_fname = fname.substr(0, last_dot) + ".png";
    SDL_SaveBMP(output, out_fname.c_str());
 
    SDL_FreeSurface(output);
    return true;
}
  

Wspomnieliśmy wcześniej, że powinniśmy usuwać te szwy, które wnoszą najmniej informacji do obrazu. Aby określić, co jest tą informacją, zdefiniujemy funkcję energii na naszym obrazie. Każdy piksel ma przypisaną energię, a energia szwu to suma energii pikseli należących do niego.

Jako energię piksela możemy przyjąć różne wartości. Jedna, która dobrze sprawdza się w praktyce, to suma różnic:

  • piksela i jego lewego sąsiada
  • piksela i jego górnego sąsiada
Czyli energia jest tam, gdzie są krawędzie na obrazie. Każdy obszar o jednolitym kolorze ma niską energię.

Odpowiada to spostrzeżeniu, że ludzkie oko bardzo dobrze rozpoznaje krawędzie, więc usunięcie czegoś z krawędzi spowoduje powstanie widocznego artefaktu. Z tego powodu przypisujemy im dużą energię - aby nie ruszać krawędzi bez powodu.

Tak zdefiniowana energia może zostać zaimplementowana następująco:

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
void compute_pixel_energy(Image* img, int x, int y) {
    if (x < 0 || x > static_cast<int>(img->data.at(0).size())-1) {
        return;
    }
    
    if (y < 0 || y > static_cast<int>(img->data.size())-1) {
        return;
    }
 
    const Color& c = img->data.at(y).at(x);
 
    int dy = 0;
    if (y > 0) {
        const Color& up = img->data.at(y-1).at(x);
        dy = abs(c.r - up.r) + abs(c.g - up.g) + abs(c.b - up.b);
    }
 
    int dx = 0;
    if (x > 0) {
        const Color& left = img->data.at(y).at(x-1);
        dx = abs(c.r - left.r) + abs(c.g - left.g) + abs(c.b - left.b);
    }
 
    img->energy.at(y).at(x) = abs(dx) + abs(dy);
}
  

Dodatkowo przydatana okaże się funkcja uaktualniająca wartość energii. Będzie się ona różniła od funkcji obliczającej energię piksela tym, że jeżeli w danym miejscu jest negatywna energia, to jej wartość nie ulegnie zmianie

Pokaż/ukryj kod
1
2
3
4
5
6
7
8
9
10
11
12
13
void update_pixel_energy(Image* img, int x, int y) {
    if (x < 0 || x > static_cast<int>(img->data.at(0).size())-1) {
        return;
    }
    if (y < 0 || y > static_cast<int>(img->data.size())-1) {
        return;
    }
    if (img->energy.at(y).at(x) == c_negative_energy) {
        return;
    }
    compute_pixel_energy(img, x, y);
}
  

Skoro mamy już funkcję obliczającą energię piksela, przyda się funckja obliczająca energię dla wszystkich pikseli w obrazie (pętla po wszystkich pikselach obrazu).

Jeżeli policzymy i wyświetlimy energię dla pokazanego już wcześniej obrazu ze zwierzętami, będzie to wyglądało tak (im cieplejsze kolory, tym większa energia):

Szwy o minimalnej energii

Do pełnej konstrukcji algorytmu SeamCarving brakuje nam już tylko sposobu wyznaczania szwu o minimalnej energii. Zastanówy się dokładniej, co chcemy zrobić. Mamy dany prostokąt, wypełniony liczbami. Te liczby oznaczają energię. Chcemy znaleźć taki szew, że jego energia będzie możliwie najmniejsza.

Odpowiednią ścieżkę możemy znaleźć bardzo łatwo. Tworzymy drugą, taką samą tablicę, ale wypełnioną zerami. Pierwszy krok to przepisanie pierwszego wiersza tablicy do nowej tablicy. Widać to na poniższym rysunku.

W drugim kroku wypełniamy drugi wiersz, tak, aby na każdym polu była najmniejsza energia szwu, który zaczyna sie w pierwszym wierszu i kończy na danym polu. Odpowiednia wartość to minimum wartości pól, z których można przejść na dane pole, powiększone o wartość samego pola. Pierwsze dwa elementy drugiego wiersza są policzone na poniższym obrazie. Pozostałe liczy się analogicznie.

Uzyskane wartości to 7 = 2 + min(8,5) oraz 6 = 1 + min(8, 5, 12).

Zastanówmy się teraz, jak policzyć trzeci wiersz. W dowolnym polu chcemy mieć energię szwu, który zaczyna się w pierwszym wierszu i kończy na danym polu. Mamy już policzone wartości dla pierwszego i drugiego wiersza. Oczywiście, jeżeli szew kończy się w trzecim wierszu, musi przechodzić przez drugi. Na każde z pól w trzecim wierszu można wejść z co najwyżej trzech pól wiersza drugiego, a dla nich mamy już policzone energie minimalnych szwów. Wystarczy zatem przedłużyć któryś z nich - ten o minimalnej energii. Na poniższym obrazie widzimy, jak ta operacja wygląda w praktyce. Otrzymujemy wartości 15 = 1 + min(68,24,14).

Inne wartości w wierszu trzecim liczymy analogicznie.

Zauważmy, że podobne rozumowanie działa dla wiersza czwartego, piątego i każdego kolejnego. W ten sposób możemy zbudować całą tablicę. Następnie odnajdujemy w ostatnim wierszu minimalną wartość. Jest to koniec pewnego szwu, o minimalnej energii - na naszym obrazie odpowiednie pole zostało zaznaczone kolorem zielonym.

Szwu będziemy szukali od końca. Wiemy, że minimalny szew kończy się w polu o minimalnej wartości w ostatnim wierszu. Aby odgadnąć, przez które pole poprzedniego wiersza przychodzi, wystarczy rozważyć trzy pola, z których dany szew mógł zostać przedłużony podczas konstrukcji. Zawsze wybieraliśmy rozszerzenie wiersza o minimalnej energii, dlatego teraz wiemy, że wystarczy wybrać to pole, które ma minimalną energię. Mówiąc krótko, zawsze wybieramy spośród pól poprzedniego wiersza - takie, które sąsiaduje z aktualnym polem i ma minimalną wartość. Skonstruowany szew dla naszej tablicy jest zaznaczony zielonym kolorem na poniższym obrazie.

Pierwszą z opisanych operacji - znajdowanie tablicy z wartościami minimalnych szwów, wykonuje poniższa funkcja. Jako argumenty przekazujemy jej obraz oraz miejsce na wynik - dwuwymiarowy wektor.

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
void compute_vertical_cumulated_energy(const Image& img, 
                             std::vector<std::vector<int> >* result) {
    std::vector<std::vector<int> >& cumulated_energy = *result;
    cumulated_energy.resize(img.height);
 
    for (size_t y = 0; y < cumulated_energy.size(); ++y) {
        cumulated_energy.at(y).resize(img.width);
    }
    
    // wypelnij pierwszy wiersz
    for (int x = 0; x < img.width; ++x) {
        cumulated_energy.at(0).at(x) = img.energy.at(0).at(x);
    }
 
    // znajdz pozostale wartosc (alg. dynamiczny)
    for (int y = 1; y < img.height; ++y) {
        for (int x = 0; x < img.width; ++x) {
            int min = cumulated_energy.at(y-1).at(x);
            if (x > 0 && cumulated_energy.at(y-1).at(x-1) < min) {
                min = cumulated_energy.at(y-1).at(x-1);
            }
            if (x < img.width-1 && cumulated_energy.at(y-1).at(x+1) < min) {
                min = cumulated_energy.at(y-1).at(x+1);
            }
            cumulated_energy.at(y).at(x) = min + img.energy.at(y).at(x);
        }
    }
}
  

Aby znaleźć optymalny szew do usunięcia, należy posłużyć się powyższą funkcją, a następnie poszukać szwu w opisany wcześniej sposób. Tę operację wykonuje funkcja find_minimal_vertical_seam. Implementację dokonuje się wprost z podanego opisu - najpierw tworzymy tablicę energii, następnie znajdujemy koniec szwu, aby ostatecznie oddtworzyć wszystkie piksele szwu. Zauważmy, że szukamy tych pikseli od końca, dlatego musimy odwrócić uzyskany wynik.

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
void find_minimal_vertical_seam(const Image& img, std::vector<int>* result) {
    std::vector<std::vector<int> > cumulated_energy(img.height);
    compute_vertical_cumulated_energy(img, &cumulated_energy);
 
    // znajdz koniec optymalnego szwu
    int min_x = 0;
    for (int x = 1; x < img.width-1; ++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->push_back(x);
    for (int y = img.height-2; y >= 0; --y) {
        if (x > 0 && cumulated_energy.at(y).at(x-1) 
            < cumulated_energy.at(y).at(x)) {
            x = x-1;
        }
        if (x < img.width-1 && cumulated_energy.at(y).at(x+1) <
            cumulated_energy.at(y).at(x)) {
            x = x+1;
        }
        result->push_back(x);
    }
 
    std::reverse(result->begin(), result->end());
}
  
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com