Final Report

Digits media today has the ability to support dynamic page layouts by changing the window or display size. We can change the layout of the documents. However, image is embedded in a document typically remain rigid in size and shape. Resizing is also important to fit images into different display devices. Image resizing has been widely used for image and video display, transmission, and analysis, etc. Several image resizing approaches such as scaling or cropping have been developed. However, standard image scaling is not sufficient because it uniformly change the image contents. Image cropping is also limited since the context information that may contain abundant information is abandoned during the operation. To address the issues associated with the traditional image resizing methods, Shai Avidan and Ariel Shamir proposed a seam carving method which supports content-aware image resizing for both reduction and expansion. The basic idea of this approach is to remove unimportant pixels. An image energy function is then used to define the importance of pixels. The seam is defined as a connected path of low energy pixels crossing the image from top to bottom, or from left to right. They calculated the seams and then carved out or inserted in one direction. By using these operators in both directions, they can reduce and enlarge the size of the an image. The approach also used to amplify and remove certain objects in the image. In this project, we will build on and extend the the Seam Carving method reported by Shaiu Avidan and Ariel Shamir.

One Dimension Seam Carving

• Generate original energy map of the image that will be used while dynamic programming
• With DP algorithm, remove one seam at a time until a pre-assigned amount.
• In each removal/insertion, change both image and energy map accordingly

Time Complexity : O((# of seams to remove) * (size of image)).

Two Dimension Seam Carving:

To find the optimal order to move h horizontal seams and v vertical seams:

• Generate a matrix M of size(h, v), M[i,j] represent for lowest cost to remove i horizontal seams and j vertical seams
• M[i, j] = min(M[i - 1, j] + E(removing a horizontal seam from it),
  M[i, j - 1] + E(removing a vertical seam from it)).
• Store whether to remove a vertical seam or horizontal seam along the way.
• Finally M[h, v] is our result, and backtrace to M[0, 0]

Time Complexity : O((# of vertical seams) * (# of horizontal seams) * (size of image)).

Content Amplification

• First do standard scaling to enlarge the image
• Do two dimension seam carving to get the original size image

Object Removal

• Change the weight of selected to be removed pixels to be very large negative numbers
• Get the smaller of the vertical or horizontal diameters, remove seams correspondingly
• Keep removing until the weight of the next to-be-removed seams becomes positive, meaning each selected pixel has been removed.
• Optionally insert seams to get original size

Edge-detection-based Energy Function

The basic idea of this approach is to remove the unimportant seams, we used a simple energy function to measure the importance of the image pixels according to this paper. energy function: e(i) = gradient(x) + gradient(y) as shown above.

Cython to fasten processing

In this project, we are implenting fine-grained operation to the data structures while as we know, Fine-grained manipulation is not fast enough in python(numpy or other library we found), it is a good idea to have dynamic libraries that can be linked at runtime. Thus we take advantage of Cython and makes the speed to remove a vertical/horizontal seam 10x faster.

Dynamic-prgramming-based Optimal Seam search

We then use dynamic programming algorithm to find the optimal seam. The first step is to traverse the image from the second row to the last row and compute the cumulative minimum energy M for all possible connected vertical seams for each entry(i, j). In particular, we compute the cumulative minimum energy for each entry(i, j) in M as follows:

Hence, after filling the matrix M, the minimum value of the last row in M will indicate the end of the minimal connected seam. The second step is to backtrack from this minimum entry on M to the find the path of the optimal seam.

Two Dimension Seam Carving

Now suppose we would like to reduce the size of an image from n × m to n′×m′, where m′ < m and n′ < n. The goal is to remove m-m’ vertical seams and n-n’ horizontal seams. The question is then becomes in what order should we remove the seams? Remove vertical seams first? Horizontal seams first? Or alternate between the two? Here we used another dynamic programming approach to find the optimal order. We use a transport map T which record the energy cost of each seam removal operation. In particular, we compute T using dynamic programming as the following formula:

where T(r, c) means the minimal cost needed to obtain an image of size n − r × m − c, In − r × m − c denotes an image of size n − r × m −c, E (s^x (I)) and E (s^y (I)) are the cost of the respective seam removal operation. Then traversing from T(0,0) to find the optimal order. We fill each entry (r, c) by choosing the minimum value of the two options - either removing a horizontal seam or removing a vertical seam.

Object Removal

We use Photoshop to marks the target object to be removed. Then we set the energy of the target object to a large negative number. In this case, the cost of any seams that cross the target object will be negative. Recall that our seam carving algorithm removes the seam with the lowest energy. Thus, the seams that we remove will definitely cross the target object. The seams will be removed from the image until all marked pixels are gone. The following figures show the results of object removal:

Animate Inserting/Removing process

• Object Removal :
  Example-1
  Example-2
  Example-3
• Remove vertical seams:
  Example-1