Chapter 12. Additional Problems in Image Processing

In this chapter, we will discuss a few more advanced problems in image processing. We'll start with the seam carving problem and demonstrate a couple of applications, the first onebeing the content-aware image resizing, and the second one being object removal from images. Next, we'll discuss seamless cloning, which can be used to seamlessly copy one object from an image to another image. Then we'll discuss an inpainting algorithm that can be used to restore damaged pixels in an image. After that, we'll look at variational methods in image processing with an application in image denoising. Next, we'll discuss the image quilting algorithm and its applications in texture synthesis and the transfer of images. We shall end our discussion with a sophisticated face morphing algorithm.

 The topics to be covered in this chapter are as follows:

• Seam carving
• Seamless cloning and Poisson image editing
• Image inpainting
• Variational image processing
• Image quilting...

Seam carving

Seam carving is a content-aware image resizing technique where the image is reduced in size by one pixel in height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row. A horizontal seam is a path of pixels connected from the left to the right with one pixel in each column. Although the underlying algorithm is simple and elegant, it was not discovered until 2007.

 

Now it is now a core feature in Adobe Photoshop and other computer graphics applications. Unlike standard content-agnostic resizing techniques, such as cropping and scaling, seam carving preserves the most interesting features of the image, such as aspect ratio, set of objects present, and so on. Finding and removing a seam involves three parts:

1. Energy calculation: The first step is to calculate the energy of a pixel, which is a measure of its importance—the higher the energy, the less likely that the pixel will be included as part of a...

Seamless cloning and Poisson image editing

The goal of Poisson image editing is to perform seamless blending (cloning) of an object or a texture from a source image (captured by a mask image) to a target image. We want to create a photomontage by pasting an image region onto a new background using Poisson image editing. This idea is from the SIGGRAPH 2003 paper, Poisson Image Editing, by Perez et alia. The problem is first expressed in the continuous domain as a constrained variational optimization problem (the Euler-Lagrange equation is used to find a solution), and then can be solved using a discrete Poisson solver. The main task of the discrete Poisson solver is to solve a huge linear system. The central insight in the paper is that working with image gradients, instead of image intensities, can produce much more realistic results. After seamless cloning, the gradient of the output image in the masked region is the same as the gradient of the source region in the masked region. Additionally...

Image inpainting

Inpainting is the process of restoring damaged or missing parts of an image. Suppose we have a binary mask, D, that specifies the location of the damaged pixels in the input image, f, as shown here:

Once the damaged regions in the image are located with the mask, the lost/damaged pixels have to be reconstructed with some algorithm (for example, Total Variation Inpainting). The reconstruction is supposed to be performed fully automatically by exploiting the information presented in non-damaged regions. 

In this example, we shall demonstrate an image inpainting implementation with scikit-imagerestoration module's inpaint_biharmonic() function. Let's apply a mask to create a damaged image from the original Lena colored image. The following code block shows how the masked pixels in the damaged image get inpainted by the inpainting algorithm based on a biharmonic equation assumption:

import numpy as np
import matplotlib.pyplot as pylab
from skimage.io import imread, imsave
from...

Variational image processing

In this section, we shall very briefly discuss variational methods in image processing, with an example application in denoising. Image processing tasks can be viewed as function estimation (for example, segmentation can be thought of as finding a smooth closed curve between an object and the background). Calculus of variations can be used for minimization of the appropriately defined energy functionals (with the Euler-Langrange method) for a specific image processing task, and the gradient descent method is used to evolve towards the solution.

The following diagram describes the basic steps in an image processing task, represented as a variational optimization problem. First, we need to create an energy functional E that describes the quality of the input image u. Then, with the Euler-Lagrange equation, we need to calculate the first variation. Next, we need to set up a partial differentail equation (PDE) for the steepest descent minimization and discretize it...

Image quilting

The image quilting algorithm is an algorithm used for texture synthesis and transfer in images, described in the SIGGRAPH 2001 paper by Efros and Freeman. In this section, we shall touch upon the main idea behind the quilting algorithms for implementing texture synthesis and transfer, and show a couple of results obtained with an implementation of the algorithm. The code is left for the reader to implement (refer to https://sandipanweb.wordpress.com/2017/10/24/some-computational-photography-image-quilting-texture-synthesis-with-dynamic-programming-and-texture-transfer-in-python/ for more information).

Texture synthesis

Texture synthesis refers to the creation of a larger texture image from a small sample. For texture synthesis, the main idea is to sample patches and lay them down in overlapping patterns, such that the overlapping regions are similar. The overlapping regions may not match exactly, which will result in noticeable artifacts around the edges. To fix this, we need...

Face morphing

In Chapter 1, Getting Started with Image Processing, we discussed a naive face morphing technique based on simple α-blending, which looks terrible if the faces to be morphed are not aligned.

 

Let's conclude the last chapter by discussing a sophisticated face morphing technique, namely Beier-Neely morphing, which visually looks way smoother and better than α-blending for non-aligned faces. Here is the algorithm:

1. Read in two image files, A and B.
2. Specify the correspondence between source image and destination image interactively (by computing facial key points with PyStasm) using a set of line segment pairs. Save the line segment pair to lines file.
3. Read the lines file. The lines file contains the line segment pairs S_i^A, S_i^B. 
4. Compute destination line segments by linearly interpolating between S_i^A and S_i^B by warp fraction. These line segments define the destination shape.
5. Warp image A to its destination shape, computing a new image A'. 
6. Warp picture B to its destination shape, computing...

Summary

In this chapter, we discussed a few advanced image processing problems. We started with the seam carving algorithm and demonstrated a couple of applications of the algorithm in context-aware image resizing and object or artifact removal from images with the scikit-image library.

Next, we discussed seamless cloning with an application to copy one object from one image to another using Python and OpenCV. Then we discussed the biharmonic inpainting algorithm and applied it to restore damaged pixels in an image using the scikit-image library. After that, we discussed variational methods in image processing with an application in image denoising with scikit-image again. Next, we discussed the image quilting algorithm and its application in texture synthesis and transfer of images. Finally, we ended this chapter with a discussion on an advanced face morphing algorithm. By the end of this chapter, the reader should be able to write Python codes for all these tasks.

Questions

1. Use MIXED_CLONE as the clone type argument for seamless cloning with python-opencv. How does the output differ from the one obtained with NORMAL_CLONE? 
2. Implement total variation inpainting with variational optimization using gradient descent (hint: refer to https://sandipanweb.wordpress.com/2017/10/08/some-more-variational-image-processing-diffusiontv-denoising-image-inpainting/).
3. Apply total variation denoising on an RGB image.

Further reading

• Shai Avidan and Ariel Shamir: Seam Carving for Content-Aware Image Resizing - http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Avidan07.pdf
• Patrick Perez, Michel Gangnet and Andrew Blake: Poisson Image Editing - http://www.irisa.fr/vista/Papers/2003_siggraph_perez.pdf
• Quilting for Texture Synthesis and Transfer: http://www.merl.com/publications/docs/TR2001-17.pdf
• Image inpainting by biharmonic functions: https://arxiv.org/pdf/1707.06567.pdf
• Feature-Based Image Metamorphosis: https://www.cs.toronto.edu/~mangas/teaching/320/assignments/a4/Beier-SIG92.pdf
• https://sandipanweb.wordpress.com/2017/10/14/seam-carving-using-dynamic-programming-to-implement-context-aware-image-resizing-in-python/
• https://sandipanweb.wordpress.com/2017/10/03/some-variational-image-processing-possion-image-editing-and-its-applications/
• https://sandipanweb.wordpress.com/2017/10/08/some-more-variational-image-processing-diffusiontv-denoising-image-inpainting/