efros_freeman  0.1
boundary_cut.c
Go to the documentation of this file.
1 /*
2  Copyright (c) 2016 Lara Raad <lara.raad@cmla.ens-cachan.fr>,
3  Bruno Galerne <bruno.galerne@parisdescartes.fr>
4 
5  Quilting is free software: you can redistribute it and/or modify
6  it under the terms of the GNU Affero General Public License as
7  published by the Free Software Foundation, either version 3 of the
8  License, or (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18 
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <math.h>
22 #include <assert.h>
23 #include <float.h>
24 
25 #include "boundary_cut.h"
26 #include "random_number.h"
27 
28 #define min(a,b) (a<=b)?(a):(b)
29 #define max(a,b) (a>b)?(a):(b)
30 #define abs(a) (a<0)?-(a):(a)
31 #define true 1
32 #define false 0
33 
34 /**
35 * This method computes the cumulative veritcal error in the overlap region
36 * and the corresponding patches to these errors.
37 * @author Lara Raad
38 * @param src_im The input texture sample
39 * @param out_im The synthesized texture
40 * @param E E is the cumulative error in the overlap
41 * @param paths paths saves the minimal path to each pixel
42 * of the overlap zone
43 * @param os Overlap size
44 * @param ps Patch size
45 * @param x X position of the location were to add
46 * the new patch in the output image
47 * @param y Y position of the location were to add
48 * the new patch in the output image
49 * @param patch_src Corner position of the patch to copy
50 * from the input texture sample
51 * @date 22/06/2014
52 */
53 int cumulative_vertical_error(Image *out_im, Image src_im, Image *E,
54  Image *paths, int ps, int os, int x, int y, Corner patch_src)
55 {
56  int ii,jj, kk, ll, mm, pos_o, pos_e, pos_s, posE_x, pos_P,
57  aux1, aux2, aux3, m1, m2, inc_o, inc_s;
58  Image e;// e is the error along the overlap region
59 
60  initialize_image(&e, ps, os,1);
61  inc_o = out_im->h*out_im->w; // number of pixels in 1 channel of output
62  inc_s = src_im.h*src_im.w; // number of pixels in 1 channel of source
63 
64  kk=0; ll=0; mm=0;
65 
66  for (ii=0; ii<ps; ii++)
67  {
68  kk = ps-1-ii;
69  ll = ps-1-(ii-1);
70  mm = ps-2-(ii-1);
71 
72  for (jj=0; jj<os; jj++)
73  {
74  pos_o = (kk + x)*out_im->w + (y + jj);
75  pos_e = kk*e.w + jj;
76  pos_s = (patch_src.x + kk)*src_im.w +(patch_src.y +jj);
77  posE_x = ll*e.w;
78  pos_P = (mm)*paths->w + jj;
79 
80  assert(pos_o<(int)(out_im->h*out_im->w));
81  assert(pos_e<(int)(e.h*e.w));
82 
83 
84  e.img[pos_e] = (out_im->img[pos_o] - src_im.img[pos_s]) *
85  (out_im->img[pos_o] - src_im.img[pos_s])
86  +
87  (out_im->img[pos_o+inc_o] - src_im.img[pos_s+inc_s]) *
88  (out_im->img[pos_o+inc_o] - src_im.img[pos_s+inc_s])
89  +
90  (out_im->img[pos_o+2*inc_o] - src_im.img[pos_s+2*inc_s]) *
91  (out_im->img[pos_o+2*inc_o] - src_im.img[pos_s+2*inc_s]);
92 
93  //build cumulative error image E
94  //in the first row of the vertical overlap zone the error
95  // image e and the cumulative error match
96  if (ii==0)
97  {
98  E->img[pos_e] = e.img[pos_e];
99  }
100  if (ii > 0)
101  {
102  assert(pos_s<(int)(src_im.h*src_im.w));
103  assert(pos_P<(int)(paths->w*paths->h));
104  assert(posE_x<=(int)((ps-1)*e.w));
105  assert(posE_x>=0);
106  assert(pos_P>=0);
107  aux2 = E->img[posE_x + jj];
108  if (jj==0)
109  {
110  //left edge of the vertical overlap zone
111  aux3 = E->img[posE_x + (jj+1)];
112  m1 = min(aux2,aux3);
113  E->img[pos_e] = e.img[pos_e] + m1;
114 
115  if ( m1 == aux2 )
116  paths->img[pos_P] = 0;
117  else if ( m1 == aux3 )
118  paths->img[pos_P] = 1;
119  }
120  else if (jj==(os-1))
121  {
122  //right edge of the vertical overlap zone
123  aux1 = E->img[posE_x + (jj-1)];
124  m1 = min(aux1,aux2);
125  E->img[pos_e] = e.img[pos_e] + m1;
126 
127  if ( m1 == aux1 )
128  paths->img[pos_P] = -1;
129  else if ( m1 == aux2 )
130  paths->img[pos_P] = 0;
131  }
132  else
133  {
134  //rest of pixels of the vertical overlap zone
135  aux1 = E->img[posE_x+ (jj-1)];
136  aux3 = E->img[posE_x + (jj+1)];
137  m1 = min(aux1,aux2);
138  m2 = min(m1,aux3);
139  E->img[pos_e] = e.img[pos_e] + m2;
140 
141  if ( m2 == aux1 )
142  paths->img[pos_P] = -1;
143  else if ( m2 == aux2 )
144  paths->img[pos_P] = 0;
145  else if ( m2 == aux3 )
146  paths->img[pos_P] = 1;
147  }
148 
149  }
150  }
151  }
152 
153  // release memory
154  free(e.img);
155 
156  return 0;
157 }
158 
159 /**
160 * This method computes the cumulative horizontal error in the overlap region
161 * and the corresponding patches to these errors.
162 * @author Lara Raad
163 * @param src_im The input texture sample
164 * @param out_im The synthesized texture
165 * @param E E is the cumulative error in the overlap
166 * @param paths paths saves the minimal path to each pixel of the
167 * overlap zone
168 * @param os Overlap size
169 * @param ps Patch size
170 * @param x X position of the location were to add
171 * the new patch in the output image
172 * @param y Y position of the location were to add
173 * the new patch in the output image
174 * @param patch_src Corner position of the patch to copy from
175 * the input texture sample
176 * @date 22/06/2014
177 */
178 
179 int cumulative_horizontal_error(Image *out_im, Image src_im, Image *E,
180  Image *paths, int ps, int os, int x, int y, Corner patch_src)
181 {
182  int ii, jj, kk, ll, mm, pos_o, pos_e, pos_s,
183  posE_y, pos_P, aux1, aux2, aux3, m1, m2;
184  Image e;
185 
186  initialize_image(&e, os, ps,1);
187  int inc_o = out_im->h*out_im->w;// number of pixels in 1 channel of output
188  int inc_s = src_im.h*src_im.w;// number of pixels in 1 channel of source
189 
190  kk=0; ll=0; mm=0;
191 
192  for (jj=0; jj<ps; jj++)
193  {
194  kk = ps-1-jj;
195  ll = ps - 1 - (jj-1);
196  mm = ps - 2 - (jj-1);
197 
198  for (ii=0; ii<os; ii++)
199  {
200  pos_o = (x + ii)*out_im->w + (y + kk);
201  pos_e = ii*e.w + kk;
202  pos_s = (patch_src.x + ii)*src_im.w +(patch_src.y +kk);
203  posE_y = ll;
204  pos_P = ii*paths->w + mm;
205 
206  assert(pos_o<(int)(out_im->h*out_im->w));
207  assert(pos_e<(int)(e.h*e.w));
208 
209 
210  e.img[pos_e] =
211  (out_im->img[pos_o] - src_im.img[pos_s]) *
212  (out_im->img[pos_o] - src_im.img[pos_s])
213  +
214  (out_im->img[pos_o+inc_o] - src_im.img[pos_s+inc_s]) *
215  (out_im->img[pos_o+inc_o] - src_im.img[pos_s+inc_s])
216  +
217  (out_im->img[pos_o+2*inc_o] - src_im.img[pos_s+2*inc_s]) *
218  (out_im->img[pos_o+2*inc_o] - src_im.img[pos_s+2*inc_s]);
219 
220  // build cumulative error image E
221  // in the first colmun of the horizontal overlap zone the error
222  // image e and the cumulative error match
223  if (jj==0)
224  E->img[pos_e] = e.img[pos_e];
225  if (jj > 0)
226  {
227  assert(pos_s<(int)(src_im.h*src_im.w));
228  assert(posE_y<(int)ps);
229  assert(pos_P<(int)(paths->w*paths->h));
230  assert(posE_y>=0);
231  assert(pos_P>=0);
232  aux2 = E->img[(ii)*E->w + posE_y];
233  if (ii==0)
234  {
235  //considering the top edge of the horizontal overlap zone
236  aux3 = E->img[(ii+1)*E->w + posE_y];
237  m1 = min(aux2,aux3);
238  E->img[pos_e] = e.img[pos_e] + m1;
239 
240  if ( m1 == aux2 )
241  paths->img[pos_P] = 0;
242  else if ( m1 == aux3 )
243  paths->img[pos_P] = 1;
244  }
245  else if (ii==(os-1))
246  {
247  //considering the bottom edge of the horizontal overlap zone
248  aux1 = E->img[(ii-1)*E->w + posE_y];
249  m1 = min(aux1,aux2);
250  E->img[pos_e] = e.img[pos_e] + m1;
251 
252  if ( m1 == aux1 )
253  paths->img[pos_P] = -1;
254  else if ( m1 == aux2 )
255  paths->img[pos_P] = 0;
256  }
257  else
258  {
259  //considering the rest of pixels of the horizontal overlap
260  aux1 = E->img[(ii-1)*E->w + posE_y];
261  aux3 = E->img[(ii+1)*E->w + posE_y];
262  m1 = min(aux1,aux2);
263  m2 = min(m1,aux3);
264  E->img[pos_e] = e.img[pos_e] + m2;
265 
266  if ( m2 == aux1 )
267  paths->img[pos_P] = -1;
268  else if ( m2 == aux2 )
269  paths->img[pos_P] = 0;
270  else if ( m2 == aux3 )
271  paths->img[pos_P] = 1;
272  }
273  }
274  }
275  }
276 
277  // Release memory
278  free(e.img);
279 
280  return 0;
281 }
282 
283 /**
284 * This method creates the boundary mask for the vertical overlap.
285 * @author Lara Raad
286 * @param E_V Cumulative error across the vertical overlap area
287 * @param paths_V Optimal paths to reach the positions of the last row
288 * @param ps Patch size
289 * @param os Overlap size
290 * @param boundary_mask Mask used to redefine the ragged edges of the patches
291 * in the blending step
292 * @date 24/06/2014
293 */
294 int create_vertical_mask(Image *E_V, int ps, int os, Image *boundary_mask,
295  Image paths_V)
296 {
297  int ymin, ii, jj, counter, num_rand;
298  int ys[os];
299  float minE;
300  ymin = 0;
301  assert((0)*E_V->w + ymin<E_V->w*E_V->h);
302  minE = E_V->img[(0)*E_V->w + ymin];
303  for (jj=1; jj<os; jj++)
304  {
305  assert((0)*E_V->w + jj < E_V->w*E_V->h);
306  if (E_V->img[(0)*E_V->w + jj] < minE)
307  {
308  minE = E_V->img[(0)*E_V->w + jj];
309  }
310  }
311 
312  counter = 0;
313  for (jj=0; jj<os; jj++)
314  {
315  if (E_V->img[(0)*E_V->w + jj]==minE)
316  {
317  ys[counter] = jj;
318  counter++;
319  }
320  }
321 
322  assert(counter>0);
323  assert(counter<=os);
324  num_rand = random_number(NULL) % counter;
325  assert(num_rand < counter);
326  assert(num_rand < os);
327  ymin = ys[num_rand];
328 
329  //* initialize vertical mask *//
330  for (jj=0; jj<=ymin; jj++)
331  {
332  assert((0)*boundary_mask->w + jj<boundary_mask->w*boundary_mask->h);
333  boundary_mask->img[(0)*boundary_mask->w + jj] = 1;
334  }
335 
336  //* complete vertical mask *//
337  for (ii=1; ii<ps; ii++)
338  {
339  assert((ii-1)*(int)paths_V.w + ymin < (int)(paths_V.w*paths_V.h));
340  ymin = ymin + paths_V.img[(ii-1)*(int)paths_V.w + ymin];
341  for (jj=0; jj<=ymin; jj++)
342  {
343  assert(ii*boundary_mask->w + jj <
344  boundary_mask->h*boundary_mask->w);
345  boundary_mask->img[ii*boundary_mask->w + jj] = 1;
346  }
347  }
348 
349  return 0;
350 }
351 
352 /**
353 * This method creates the boundary mask for the horizontal overlap.
354 * @author Lara Raad
355 * @param E_H The cumulative error across the horizontal
356 * overlap arear
357 * @param paths_H The optimal paths to reach the positions
358 * of the last column
359 * @param ps Patch size
360 * @param os Overlap size
361 * @param boundary_mask Mask used to redefine the ragged edges of
362 * the patches in the blending step
363 * @date 24/06/2014
364 */
365 int create_horizontal_mask(Image *E_H, int ps, int os, Image *boundary_mask,
366  Image paths_H)
367 {
368  int xmin, ii, jj, counter, num_rand;
369  int xs[os];
370  float minE;
371  xmin = 0;
372  assert(xmin*E_H->w + 0 < E_H->w*E_H->h);
373  minE = E_H->img[xmin*E_H->w + 0];
374  for (ii=1; ii<os; ii++)
375  {
376  assert(ii*E_H->w + 0 < E_H->w*E_H->h);
377  if (E_H->img[ii*E_H->w + 0] < minE)
378  {
379  minE = E_H->img[ii*E_H->w + 0];
380 
381  }
382  }
383 
384  counter = 0;
385  for (ii=0; ii<os; ii++)
386  {
387  if (E_H->img[ii*E_H->w + 0] == minE)
388  {
389  xs[counter] = ii;
390  counter++;
391  }
392  }
393 
394  assert(counter>0);
395  assert(counter<=os);
396  num_rand = random_number(NULL) % counter;
397  assert(num_rand<counter);
398  assert(num_rand<os);
399  xmin = xs[num_rand];
400 
401  //* initialize horizontal mask *//
402  for (ii=0; ii<=xmin; ii++)
403  {
404  assert(ii*boundary_mask->w + 0 < boundary_mask->w*boundary_mask->h);
405  boundary_mask->img[ii*boundary_mask->w + 0] = 1;
406  }
407 
408  //* complete horizontal boundary mask *//
409  for (jj=1; jj<=ps-1; jj++)
410  {
411  assert(xmin*(int)paths_H.w + (jj-1) < (int)(paths_H.w*paths_H.h));
412  xmin = xmin + paths_H.img[xmin*(int)paths_H.w + (jj-1)];
413  for (ii=0; ii<=xmin; ii++)
414  {
415  assert(ii*boundary_mask->w + jj <
416  boundary_mask->h*boundary_mask->w);
417  boundary_mask->img[ii*boundary_mask->w + jj] = 1;
418  }
419  }
420 
421  return 0;
422 }
423 
424 /**
425 * This method creates the boundary mask for the L-shape overlap.
426 * @author Lara Raad
427 * @param E_V Cumulative error across the vertical overlap area
428 * @param paths_V Optimal paths to reach the positions of the first row
429 * @param E_H Cumulative error across the horizontal overlap area
430 * @param paths_H Optimal paths to reach the positions of the first column
431 * @param ps Patch size
432 * @param os Overlap size
433 * @param boundary_mask Mask used to redefine the ragged edges of
434 * the patches in the blending step
435 * @date 24/06/2014
436 */
437 int create_Lshape_mask(Image *E_V, Image *E_H, int ps, int os,
438  Image *boundary_mask, Image paths_V, Image paths_H)
439 {
440  int xmin, ymin, x0, y0, ii, jj, counter, num_rand;
441  int diag[os];
442  float minE;
443  xmin = 0;
444  ymin = 0;
445  minE = E_V->img[0] + E_H->img[0];
446  for (ii=1; ii<os; ii++)
447  {
448  if (E_V->img[ii*E_V->w + ii] + E_H->img[ii*E_H->w + ii] < minE)
449  {
450  minE = E_V->img[ii*E_V->w + ii] + E_H->img[ii*E_H->w + ii];
451  }
452  }
453  counter = 0;
454  for (ii=0; ii<os; ii++)
455  {
456  if (E_V->img[ii*E_V->w + ii] + E_H->img[ii*E_H->w + ii] == minE)
457  {
458  diag[counter] = ii;
459  counter++;
460  }
461  }
462  assert(counter>0);
463  assert(counter<=os);
464  num_rand = random_number(NULL) % counter;
465  assert(num_rand<counter);
466  assert(num_rand<os);
467  xmin = diag[num_rand];
468  ymin = xmin;
469  x0 = xmin;
470  y0 = ymin;
471  //* initialize L-shape mask *//
472  for (ii=0; ii<=xmin; ii++)
473  for(jj=0; jj<=ymin; jj++)
474  {
475  boundary_mask->img[ii*boundary_mask->w + jj] = 1;
476  }
477 
478  //* complete L-shape boundary mask*//
479  for (ii=x0+1; ii<ps; ii++)
480  {
481  assert((ii-1)*(int)paths_V.w + ymin < (int)(paths_V.w*paths_V.h));
482  ymin = ymin + paths_V.img[(ii-1)*(int)paths_V.w + ymin];
483  for (jj=0; jj<=ymin; jj++)
484  {
485  assert(ii*boundary_mask->w + jj <
486  boundary_mask->h*boundary_mask->w);
487  boundary_mask->img[ii*boundary_mask->w + jj] = 1;
488  }
489  }
490  for (jj=y0+1; jj<ps; jj++)
491  {
492  assert(xmin*(int)paths_H.w + (jj-1) < (int)(paths_H.w*paths_H.h));
493  xmin = xmin + paths_H.img[xmin*(int)paths_H.w + (jj-1)];
494  for (ii=0; ii<=xmin; ii++)
495  {
496  assert(ii*boundary_mask->w + jj <
497  boundary_mask->h*boundary_mask->w);
498  boundary_mask->img[ii*boundary_mask->w + jj] = 1;
499  }
500  }
501  return 0;
502 }
503 
504 /**
505 * This method computes the boundary mask needed
506 * to then blend correctly the patch in the
507 * output texture.
508 * @author Lara Raad
509 * @param src_im The input texture sample
510 * @param out_im The synthesized texture
511 * @param os The size of the overlap area betwenn patches
512 * @param ps The size of the patches
513 * @param temp Left top corner position of the patch under
514 * construction in the output image
515 * @param patch_src Corner position of the patch to copy from the
516 * input texture sample
517 * @date 22/06/2014
518 */
519 int compute_boundary_mask(Image src_im, Image out_im, Image *boundary_mask,
520  int os, int ps, Corner * temp, Corner patch_src)
521 {
522  int x, y;
523  x = temp->x;
524  y = temp->y;
525 
526  if(os==1)
527  {
528  int i,j;
529  if (x > 0 && y > 0) //* L-shape overlap *//
530  {
531  for(i=0;i<ps;i++)
532  {
533  boundary_mask->img[i*boundary_mask->w] = 1;
534  }
535  }
536  else if (x == 0 && y > 0) //* vertical overlap *//
537  {
538  for(j=0;j<ps;j++)
539  {
540  boundary_mask->img[j] = 1;
541  }
542  }
543  else if (y == 0 && x > 0) //* horizontal overlap *//
544  {
545  boundary_mask->img[0] = 1;
546  for(i=1;i<ps;i++)
547  {
548  boundary_mask->img[i*boundary_mask->w] = 1;
549  }
550  for(j=1;j<ps;j++)
551  {
552  boundary_mask->img[j] = 1;
553  }
554  }
555  }
556  else
557  {
558  if (x > 0 && y > 0) //* L-shape overlap *//
559  {
560  Image E_V, E_H, paths_V, paths_H;
561  initialize_image(&paths_V, ps-1, os, 1);
562  initialize_image(&paths_H, os, ps-1, 1);
563  initialize_image(&E_V, ps, os, 1);
564  initialize_image(&E_H, os, ps, 1);
565  cumulative_vertical_error(&out_im, src_im, &E_V, &paths_V,
566  ps, os, x, y, patch_src);
567  cumulative_horizontal_error(&out_im, src_im, &E_H, &paths_H,
568  ps, os, x, y, patch_src);
569 
570  //* create L-shape blending mask *//
571  create_Lshape_mask(&E_V, &E_H, ps, os, boundary_mask,
572  paths_V, paths_H);
573 
574  //* release memory *//
575  free(E_V.img);
576  free(E_H.img);
577  free(paths_V.img);
578  free(paths_H.img);
579  }
580  else if (x == 0 && y > 0) //* vertical overlap *//
581  {
582  Image E_V, paths_V;
583  initialize_image(&paths_V, ps-1, os, 1);
584  initialize_image(&E_V, ps, os, 1);
585  cumulative_vertical_error(&out_im, src_im, &E_V, &paths_V, ps,
586  os, x, y, patch_src);
587 
588  //* create vertical blending mask *//
589  create_vertical_mask(&E_V, ps, os, boundary_mask, paths_V);
590 
591  //* release memory *//
592  free(E_V.img);
593  free(paths_V.img);
594  }
595  else if (y == 0 && x > 0) //* horizontal overlap *//
596  {
597  Image E_H, paths_H;
598  initialize_image(&paths_H, os, ps-1, 1);
599  initialize_image(&E_H, os, ps, 1);
600  cumulative_horizontal_error(&out_im, src_im, &E_H,
601  &paths_H, ps, os, x, y, patch_src);
602 
603  //* create horizontal blending mask *//
604  create_horizontal_mask(&E_H, ps, os, boundary_mask, paths_H);
605 
606  //* release memory *//
607  free(E_H.img);
608  free(paths_H.img);
609  }
610  }
611 
612  return 0;
613 }