Poisson Image Editing

The images are fused incvThe field has a wide range of uses,其中2003年的论文 Poisson Image Editing - 2003 Because of its pioneering and outstanding effect, it has become a classic in related fields.Moreover, the algorithm is outstanding in the traditional image fusion algorithm,profound impact on the field.

简介

Poisson image editing is fully automatic“无缝融合”Two-image technique,由Microsoft Research UK的Patrick Perez,Michel Gangnet, and Andrew Blake在论文“Poisson Image Editing”中首次提出.

• Poisson editing mainly solves the seamless fusion of signals from two different sources（seamless cloning）问题
• The purpose is to convert the source imageg的一部分内容\Omegafused to the target imagef*on the same size area,And make it a natural blend transition

左上：目标图像f*,区域\Omegais the part replaced by the content of the source image; 左下：源图像g,区域\OmegaThe content inside needs to be pasted to the target image 右上：Paste the source image information directly there will be inconsistent edge transitions 右下：Change the signal of the source to the target image boundary according to the original gradient relationship,A seamless fusion effect is achieved

• The goal of Poisson editing is to naturally fuse images from different sources
• Paste the source image onto the destination image
• To keep the transition smooth,The gradient information of the pasted region of the source image and the edge information of the target image are considered
• Solving the system of equations combined with the known information yields the result of the Poisson-edited image

理论介绍

符号定义

如上图所示：

• Image fusion is to combine the source imageg的指定区域\Omegafused to the target imageS中,The edge area is \partial \Omega ,Source image area functionf^*,Target image area functionf.
• 这里面g,\Omega,S, \partial \Omega ,f^*都是已知量,需要求的是f

理论

The purpose of Poisson image editing is to preserve the texture of the source image,Blends seamlessly into new images. The idea of ​​implementation is to preserve the gradient of the source image,Applied to the bounds of the target image,Solve equations that satisfy both gradient and edge constraints,Get the target area pixels.

• ∇f 指的是图像函数 f 的梯度

\nabla .=\left[\frac{\partial_{.}}{\partial x}, \frac{\partial}{\partial y}\right]

• v 在原论文中是指一个引导向量场（guidance field）,当用于图像合成时,它指的就是源图像的梯度.
• 这意味着上面的变分方程是指在Ω 的区域内,f的梯度和源图像的梯度一致,而在Ω 的边缘处f的值则和源图像f^*的值一致.这个变分方程的解是如下泊松方程在Dirichlet边界条件时的解,这也是为什么我们的融合方式叫做泊松融合.

Several keys and symbols are explained

• 梯度 Gradient：

\mathbf{v}=(u, v)=\nabla g

• 拉普拉斯算子 Laplacian

• 散度 Divergence

核心

• 也就是f^*和fThe divergences are correspondingly equal
• 同时保证f^*和fThe boundaries correspond to equal

\Delta f=\Delta f^* \text{ over } \Omega , \text{ with } \left.f\right|_{\partial \Omega}=f^{*} \mid \partial \Omega

求解方程

• Express the Poisson equation in linear vector form Af=b

• 等号的右边是图像g中每一个像素的拉普拉斯滤波结果∆gp,这很容易理解.未知函数f的每个元素构成了等号左边的列向量.而系数矩阵A则描述了最关键的f的拉普拉斯滤波算子.
• Once the equations are listed, the system of equations is solved,A是稀疏矩阵,No more than one element per line5个,可以用 f = b / A计算得到

参考代码

• A reference is madegithub上星星最多的Poisson image editing code,改成了python3And encapsulate it as a class method,供大家参考.

The core class function is channel_process,The input image is single channel,mask为0-1的浮点数

"""
Poisson Image Editing
William Emmanuel
[email protected]
CS 6745 Final Project Fall 2017
"""

import numpy as np
from scipy.sparse import linalg as linalg
from scipy.sparse import lil_matrix as lil_matrix

import cv2


class Poission:
    # Helper enum
    OMEGA = 0
    DEL_OMEGA = 1
    OUTSIDE = 2

    # Determine if a given index is inside omega, on the boundary (del omega),
    # or outside the omega region
    @classmethod
    def point_location(cls, index, mask):
        if cls.in_omega(index, mask) == False:
            return cls.OUTSIDE
        if cls.edge(index, mask) == True:
            return cls.DEL_OMEGA
        return cls.OMEGA

    # Determine if a given index is either outside or inside omega
    @staticmethod
    def in_omega(index, mask):
        return mask[index] == 1

    # Deterimine if a given index is on del omega (boundary)
    @classmethod
    def edge(cls, index, mask):
        if cls.in_omega(index, mask) == False:
            return False
        for pt in cls.get_surrounding(index):
            # If the point is inside omega, and a surrounding point is not,
            # then we must be on an edge
            if cls.in_omega(pt, mask) == False:
                return True
        return False

    # Apply the Laplacian operator at a given index
    @staticmethod
    def lapl_at_index(source, index):

        i, j = index
        edge_num = 0
        minus_data = 0

        try:
            temp = source[i+1, j]
            edge_num += 1
            minus_data += temp
        except Exception as e:
            pass

        try:
            temp = source[i-1, j]
            edge_num += 1
            minus_data += temp
        except Exception as e:
            pass

        try:
            temp = source[i, j+1]
            edge_num += 1
            minus_data += temp
        except Exception as e:
            pass

        try:
            temp = source[i, j-1]
            edge_num += 1
            minus_data += temp
        except Exception as e:
            pass

        val = source[i, j] * edge_num - minus_data

        # val = (4 * source[i, j])    \
        #     - (1 * source[i+1, j]) \
        #     - (1 * source[i-1, j]) \
        #     - (1 * source[i, j+1]) \
        #     - (1 * source[i, j-1])
        return val

    # Find the indicies of omega, or where the mask is 1
    @staticmethod
    def mask_indicies(mask):
        nonzero = np.nonzero(mask)
        return nonzero[0], nonzero[1]

    # Get indicies above, below, to the left and right
    @staticmethod
    def get_surrounding(index):
        i, j = index
        return [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]

    # Create the A sparse matrix
    @classmethod
    def poisson_sparse_matrix(cls, rows, cols):
        # N = number of points in mask
        N = len(list(rows))
        A = lil_matrix((N, N))
        # Set up row for each point in mask

        points = list(zip(rows, cols))
        for i, index in enumerate(points):
            # Should have 4's diagonal
            A[i, i] = 4
            # Get all surrounding points
            for x in cls.get_surrounding(index):
                # If a surrounding point is in the mask, add -1 to index's
                # row at correct position
                if x not in points:
                    continue
                j = points.index(x)
                A[i, j] = -1
        return A

    # Main method
    # Does Poisson image editing on one channel given a source, target, and mask
    @classmethod
    def channel_process(cls, source, target, mask):
        rows, cols = cls.mask_indicies(mask)

        assert len(rows) == len(cols)
        N = len(rows)
        # Create poisson A matrix. Contains mostly 0's, some 4's and -1's
        A = cls.poisson_sparse_matrix(rows, cols)
        # Create B matrix
        b = np.zeros(N)
        points = list(zip(rows, cols))
        for i, index in enumerate(points):
            # Start with left hand side of discrete equation
            b[i] = cls.lapl_at_index(source, index)
            # If on boundry, add in target intensity
            # Creates constraint lapl source = target at boundary
            if cls.point_location(index, mask) == cls.DEL_OMEGA:
                for pt in cls.get_surrounding(index):
                    if cls.in_omega(pt, mask) == False:
                        b[i] += target[pt]

        # Solve for x, unknown intensities
        x = linalg.cg(A, b)
        # Copy target photo, make sure as int
        composite = np.copy(target).astype(int)
        # Place new intensity on target at given index
        for i, index in enumerate(points):
            composite[index] = x[0][i]

        composite = np.clip(composite, 0, 255)
        return composite.astype('uint8')

    @staticmethod
    def gray_channel_3_image(image):
        assert image.ndim == 3
        if (image[:, :, 0] == image[:, :, 1]).all() and (image[:, :, 0] == image[:, :, 2]).all():
            return True
        else:
            return False

    @staticmethod
    def image_resize(img_source, shape=None, factor=None):
        image_H, image_W = img_source.shape[:2]
        if shape is not None:
            return cv2.resize(img_source, shape)

        if factor is not None:
            resized_H = int(round(image_H * factor))
            resized_W = int(round(image_W * factor))
            return cv2.resize(img_source, [resized_W, resized_H])

        else:
            return img_source

复制

效果示例

The specified area of ​​the source image is fused into the target image,纵享丝滑.

参考资料

• https://github.com/willemmanuel/poisson-image-editing
• Poisson Image Editing - 2003
• https://blog.csdn.net/zhaoyin214/article/details/88196575
• https://zhuanlan.zhihu.com/p/58867397