-
Notifications
You must be signed in to change notification settings - Fork 4
/
graphcut.cpp
321 lines (279 loc) · 12.4 KB
/
graphcut.cpp
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
#include "config.h"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
extern "C" {
#include "compter.h"
#include "main.h"
#include "texturize.h"
}
#include "graph.h"
#define MAX_CAPACITY 16383 // Half of the largest short, (captype is short in graph.h)
#define REMPLI 1
#define CUT_NORTH 2
#define CUT_WEST 4
#define HAS_CUT_NORTH(r) (r) & CUT_NORTH
#define HAS_CUT_WEST(r) (r) & CUT_WEST
// ||pixel1 - pixel2||^2
// From experience, squares seem to work better than another type of norm.
inline Graph::captype cost (guchar * pixel1, guchar * pixel2, int channels) {
int diff, result = 0;
for (int c = 0; c < channels; c++){
diff = pixel1[c] - pixel2[c];
result += diff*diff;
}
return (result/24);
// We need to divide at least by 24, or we might return more than
// MAX_CAPACITY.
}
inline Graph::captype gradient (guchar * pixel1, guchar * pixel2, int channels) {
int diff, result = 0;
for (int c = 0; c < channels; c++){
diff = pixel1[c] - pixel2[c];
result += diff*diff;
}
return ((Graph::captype) sqrt(result));
}
// When we write the four arguments to edge_weight on two lines of code,
// we try to always align things (pixel VS image) so that it makes sense.
inline Graph::captype edge_weight (int channels,
guchar * im1_pix1, guchar * im2_pix1,
guchar * im1_pix2, guchar * im2_pix2) {
return ((cost(im1_pix1,im2_pix1,channels) + (cost(im1_pix2,im2_pix2,channels)))
/ (gradient(im1_pix1,im1_pix2,channels) + gradient(im2_pix1,im2_pix2,channels) +1));
}
inline void paste_patch_pixel_to_image(int width_i, int height_i, int width_p, int height_p,
int x_i, int y_i, int x_p, int y_p,
int channels,
guchar * image, guchar * patch) {
int k;
for (k = 0; k < channels; k++) {
image[(y_i * width_i + x_i) * channels + k] = patch[(y_p * width_p + x_p) * channels + k];
/*
Might become useful again if we start taking old cuts into account again.
if (y_i < height_i - 1 && y_p < height_p - 1){
for(k = 0; k < channels; k++)
coupe_v_here[((y_i + 1) * width_i + x_i) * channels + k] = patch[((y_p + 1) * width_p + x_p) * channels + k];
}
if (x_i < width_i - 1 && x_p < width_p - 1) {
for(k = 0; k < channels; k++)
coupe_h_here[(y_i * width_i + x_i + 1) * channels + k] = patch[(y_p * width_p + x_p + 1) * channels + k];
}
*/
}
}
void decoupe_graphe (int* patch_posn,
int width_i, int height_i, int width_p, int height_p,
int channels,
guchar **rempli,
guchar *image, guchar * patch,
guchar *coupe_h_here, guchar * coupe_h_west,
guchar *coupe_v_here, guchar * coupe_v_north,
gboolean make_tileable, gboolean invert) {
////////////////////////////////////////////////////////////////////////////////
// Variable declaration.
gint k, x_p, y_p, x_i, y_i;// nb_sommets, sommet_courant; // Compteurs
gint real_x_i, real_y_i;
gint x_inf, y_inf, x_sup, y_sup;
Graph * graphe = new Graph(); // Le graphe à couper
Graph::node_id *node_of_pixel = (void **) calloc (width_p * height_p, sizeof (Graph::node_id)); // Le noeud du graph auquel correspond un pointeur.
for (k=0; k<width_p * height_p; k++) node_of_pixel[k] = NULL;
Graph::captype poids; // Pour calculer le poids d'un arc avant de le déclarer à Graph:add_edge
Graph::node_id first_node = NULL, node_sommet_courant;
guchar r;
////////////////////////////////////////////////////////////////////////////////
// Graph creation.
// Let's define how much space we need to visit, depending on whether we want
// a tileable texture.
if (make_tileable) {
x_inf = patch_posn[0];
y_inf = patch_posn[1];
x_sup = patch_posn[0] + width_p;
y_sup = patch_posn[1] + height_p;
} else {
x_inf = MAX (0, patch_posn[0]);
y_inf = MAX (0, patch_posn[1]);
x_sup = MIN (width_i, patch_posn[0] + width_p);
y_sup = MIN (height_i, patch_posn[1] + height_p);
}
/* Remarque sur la convention "real" :
*
* ______________________
* | |
* | |
* |<------- x_i ------>|
* | |
* | |
* <--------------|--------- real_x_i--|--------------->
* | |
* | |
* ______________________
*/
// We count the number of nodes by visiting the intersection between the
// patch and the filled in image.
// nb_sommets = 0;
// for (real_x_i = x_inf; real_x_i < x_sup; real_x_i++) {
// for (real_y_i = y_inf; real_y_i < y_sup; real_y_i++) {
// x_i = modulo (real_x_i, width_i);
// y_i = modulo (real_y_i, height_i);
// r = rempli[x_i][y_i];
// if (r) {
// nb_sommets++;
// We'll uncomment this when we start taking previous cuts into account again.
// if (HAS_CUT_NORTH(r)) nb_sommets++;
// if (HAS_CUT_WEST(r)) nb_sommets++;
// }
// }
// }
// Start by visiting the whole patch to create nodes and create links in
// node_of_pixel.
for (real_x_i = x_inf;
real_x_i < x_sup;
real_x_i++) {
x_p = real_x_i - patch_posn[0];
x_i = modulo (real_x_i, width_i);
for (real_y_i = y_inf;
real_y_i < y_sup;
real_y_i++) {
y_p = real_y_i - patch_posn[1];
y_i = modulo (real_y_i, height_i);
// Si le pixel de l'image n'est pas rempli, on ne fait rien et on passe au suivant
if (rempli[x_i][y_i]) {
node_of_pixel[x_p * height_p + y_p] = graphe->add_node ();
if (first_node == NULL) first_node = node_of_pixel[x_p * height_p + y_p];
}
}
}
// Create the edges.
/*
We link to the source the pixels that are at the same time filled and also
on the edges of the patch (and, for a non tileable texture, that are also
not on the edge of the image).
We link to the sink the pixels that have at least one neighbor that isn't
filled yet.
**********************************************
Loop summary:
For each x of the patch (intersection with the image if !make_tileable).
For each y of the patch (same note)
If I am already filled
Create the edges with my North and West neighbord (if they exist in the
patch) (later we'll need to take previous cuts into account)
If I am on the edge of the patch (i.e. there's no other pixel in the patch
to the North OR South OR East OR West)
And in the !make_tileable case, if I am also not on the edge of the image
(1)
Then link me to the source
If one of my neighbords (North, South, East, West) exists (in the patch
AND in the image) and hasn't been filled yet
Then link me to the sink
If I haven't been filled yet
Don't do anything.
// The test (1) above might cause the source to not be linked to any pixel.
// The following line fixes that problem.
If !make_tileable, link the top left pixel of the intersection (the first one
that was created) to the source.
*/
for (real_x_i = x_inf;
real_x_i < x_sup;
real_x_i++) {
x_p = real_x_i - patch_posn[0];
x_i = modulo (real_x_i, width_i);
for (real_y_i = y_inf;
real_y_i < y_sup;
real_y_i++) {
y_p = real_y_i - patch_posn[1];
y_i = modulo (real_y_i, height_i);
// If the pixel in the image hasn't been filled, we do nothing and skip
// to the next one.
if (!rempli[x_i][y_i]) {
continue;
} else {
// Create the nodes and edges.
node_sommet_courant = node_of_pixel[x_p * height_p + y_p];
// If the neighbord exists in the patch and if the pixel to the North
// is filled in the image, create a link to it.
if ((!make_tileable && y_p != 0 && y_i != 0 && rempli[x_i][y_i - 1])
|| (make_tileable && y_p != 0 && rempli[x_i][modulo (y_i - 1, height_i)])) {
poids = edge_weight (channels,
image + ((y_i * width_i + x_i) * channels),
patch + ((y_p * width_p + x_p) * channels),
image + (((modulo (y_i - 1, height_i)) * width_i + x_i) * channels),
patch + (((y_p - 1) * width_p + x_p) * channels));
graphe->add_edge (node_sommet_courant,
node_of_pixel[x_p * height_p + y_p - 1],
poids, poids);
}
// If the West neighbor exists in the patch and if the West pixel is
// filled in the image, we create a link to it.
if ((!make_tileable && x_p != 0 && x_i != 0 && rempli[x_i - 1][y_i])
|| (make_tileable && x_p != 0 && rempli[modulo (x_i - 1, width_i)][y_i])) {
poids = edge_weight (channels,
image + ((y_i * width_i + x_i) * channels),
patch + ((y_p * width_p + x_p) * channels),
image + ((y_i * width_i + (modulo (x_i, width_i) - 1)) * channels),
patch + ((y_p * width_p + (x_p - 1)) * channels));
graphe->add_edge (node_sommet_courant,
node_of_pixel[(x_p - 1) * height_p + y_p],
poids, poids);
}
// If I am on the edge of the patch and, if !make_tileable, I am not on
// the edge of the image, link me to the source.
if ( (make_tileable && (x_p == 0 || y_p == 0 || x_p == width_p - 1 || y_p == height_p - 1))
|| (!make_tileable && (x_p == 0 || y_p == 0 || x_p == width_p - 1 || y_p == height_p - 1)
&& x_i != 0 && y_i != 0 && x_i != width_i - 1 && y_i != height_i - 1)) {
graphe->add_tweights (node_sommet_courant, MAX_CAPACITY, 0);
}
// If one of my neighbords exists and isn't filled, link me to the sink.
if (((!make_tileable)
&& ( (y_p != 0 && y_i != 0 && !rempli[x_i][y_i - 1]) // North
|| (y_p != height_p - 1 && y_i != height_i - 1 && !rempli[x_i][y_i + 1]) // South
|| (x_p != width_p - 1 && x_i != width_i - 1 && !rempli[x_i + 1][y_i]) // East
|| (x_p != 0 && x_i != 0 && !rempli[x_i - 1][y_i]))) // West
|| ((make_tileable)
&& ( (y_p != 0 && !rempli[x_i][modulo (y_i - 1, height_i)]) // North
|| (y_p != height_p - 1 && !rempli[x_i][modulo (y_i + 1, height_i)]) // South
|| (x_p != width_p - 1 && !rempli[modulo (x_i + 1, width_i)][y_i]) // East
|| (x_p != 0 && !rempli[modulo (x_i - 1, width_i)][y_i])))) { // West
graphe->add_tweights (node_sommet_courant, 0, MAX_CAPACITY);
}
}
}
}
// If !make_tileable, link the top left pixel in patch \cap image to the
// source.
if (!make_tileable) {
graphe->add_tweights (first_node, MAX_CAPACITY, 0);
}
////////////////////////////////////////////////////////////////////////////////
// Compute the cut.
graphe->maxflow();
////////////////////////////////////////////////////////////////////////////////
// Update the image.
for (real_x_i = x_inf; real_x_i < x_sup; real_x_i++) {
x_p = real_x_i - patch_posn[0];
x_i = modulo (real_x_i, width_i);
for (real_y_i = y_inf; real_y_i < y_sup; real_y_i++) {
y_p = real_y_i - patch_posn[1];
y_i = modulo (real_y_i, height_i);
r = rempli[x_i][y_i];
if (r) {
if (graphe->what_segment(node_of_pixel[x_p * height_p + y_p]) == Graph::SINK) {
paste_patch_pixel_to_image (width_i, height_i, width_p, height_p, x_i, y_i, x_p, y_p,
channels, image, patch); //,
//coupe_h_here, coupe_v_here);
}
} else { // (!rempli[x_i][y_i])
paste_patch_pixel_to_image (width_i, height_i, width_p, height_p, x_i, y_i, x_p, y_p,
channels, image, patch); //,
//coupe_h_here, coupe_v_here);
rempli[x_i][y_i] = REMPLI;
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Clean up.
delete graphe;
free (node_of_pixel);
return;
}