Poisson Image Editing

This repository is an effective C++ implementation of Pérez et al. Poisson image editing and Sun et al. Poisson matting. We briefly describe our design of reproduction and implementation details.

Get Started

Dependencies of this project include:

Eigen
OpenCV
gflags
Boost
(optional) Intel MKL for accelerating sparse system solving.

Install dependence, on macOS it is recommended to using homebrew:
```
brew install cmake eigen opencv gflags boost
```
For intel MKL, go ahead to their official website to apply a community license;
Setup git-lfs before cloning this repository. Images in this repository are quite large thus all hold by git-lfs;

Compile the executable visualize:

mkdir build && cd build
cmake -DINTEL_ROOT=<path/to/intel_performance_library> ..
make
./visualize <args>

Arguments of visualize executable include:

visualize: C++ implementation of Poisson matting and clone.

  Flags from /Users/lirundong/Projects/poisson_editing/tools/visualize.cpp:
    -cfg (argument of specified task, separated by commas) type: string
      default: ""
    -dst (path to output image) type: string default: ""
    -mask (path to fore/back/unknown map image) type: string default: ""
    -src (path to source image) type: string default: ""
    -src_back (path to source background image) type: string default: ""
    -src_fore (path to source foreground image) type: string default: ""
    -task (task to perform: {clone, matting}) type: string default: "clone"

where configurations (the -cfg argument) are passed by a string of numbers, separated by commas or spaces. For each of the tasks, the configurations are:

For Poisson cloning: -cfg="<object_x1>, <object_y1>, <object_long_edge_size>";
For Poisson matting: -cfg="<trimap_value_for_foreground>, <for_background>, <for_unknown_region>, <max_number_of_solving_iterations>";

Visual Results

Seamless Poisson Cloning

Background	Object	Mask

Result:

Poisson Matting

Source Image	Trimap

Result after 10 iterations:

Implementation Details

The core of this implementation is building a (sparse) linear system from (4-neighbor) Laplacian matching, and specifying border conditions by specific tasks.

For Poisson cloning, the border condition is border of unknown region is consistent with background image; for Poisson matting, it's exterior border between unknown region and absolute foreground region have alpha value of 1, for background side the alpha value is 0.

To build Laplacian of unknown values f within mask (the Omega in paper):

The general case here is: at position i of Omega, and relevant spatial location (y, x) on source image, the Laplacian L_f of f is:
```
L_f[i] = 4 * f[i] - f[y + 1, x] - f[y - 1, x] - f[y, x + 1] - f[y, x - 1]
```
There are three points that we should take into consideration:
1. Build the mapping between plain index i and spatial index (y, x). This is simply done by scanning though the input binary mask, then recording the mappings to two vector:
```
vector<int> spatial2omega(obj_h * obj_w, -1), omega2spatial(obj_h * obj_w, -1);
```
2. Boundary conditions when i is on RoI edge, such that number of its neighborhoods are less than 4. This is handled in add_laplacian:
```
#define WITHIN(i, N) (0 <= (i) && (i) < (N)

auto add_laplacian = [&](int y, int x) {
  if (WITHIN(y, obj_h) && WITHIN(x, obj_w)) {
    n4_count++;
    // ...
  }
};
```
3. When i is on edge of Omega, the L_f should computed from both unknown neighborhoods and background pixels b on edge. Say, (y + 1, x) and (y, x + 1) are on edge:
```
L_f[i] = 4 * f[i] - b[y + 1, x] - f[y - 1, x] - b[y, x + 1] - f[y, x - 1]
```
To build Laplacian of guidance values g within mask (the Omega in paper):

Basically the g is drawn from forge-ground image, and no boundary conditions should be considered:
```
L_g[i] = 4 * g[i] - g[y + 1, x] - g[y - 1, x] - g[y, x + 1] - g[y, x - 1]
```
Build a linear system A.dot(f) = b, A and b are inferred from the Laplacian matching L_f == F_g. In our example the A is a 103183 * 103183 big sparse matrix. To speedup the building process we use the setFromTriplets methods provided by Eigen parse matrix.

To solve this sparse, positive-defined linear system, we use the SimplicialLDLT solver, as suggested by Eigen official document.

Performance

This implementation is able to fuse 800 * 600 sized RoI in about 2 seconds. We profiled this implementation: the major time consumptions reside in I/O: From the perspective of fusing function seamless_clone, major consumptions resides in Eigen API Eigen::SimplicialLDLT::solve and Eigen::SparseMatrix::setFromTriplets:

Thus (the core logic of) this implementation is effective enough. Linking against Intel MKL will further accelerate the solving process.

License

This work is licensed under Apache License 2.0. See LICENSE for details.

lirundong/Poisson-Editing