introduce

Big brother, help me P a picture is busy, not busy very simple, you see is this picture it is a little wide, put on the page people are squeezed flat, help narrow a little bit better then you cut the picture a little bit, don't cut the person can not see all ok, send me email to help you do itCopy the code

We often need to resize images for better display, and photoshop is not very skilled. After reading this article, you won’t have to ask a designer to photocopy your images

Seam carving algorithm is an interesting image scaling algorithm. Different from common frame trimming or geometric stretching, the algorithm can sense the image content, distinguish the main objects, and deform on the basis of avoiding these subjects, for example:

It can be seen that although the width of Figure 2 is reduced, there is no obvious deformation of the people and the building in figure 3, while the people and the building in Figure 3 have been flattened, and the building in Figure 4 is incomplete. As the main elements in the picture, people and buildings are perceived by the algorithm and preserved as much as possible in the processing.

Of course, the algorithm can also be applied to the vertical direction, or to both horizontal and vertical directions, for example:

You can even mark an object in an image and remove it in a directional manner, almost as good as professional Photoshop. Let’s see which shoe is missing down there

If you don't find it, don't worry, the article provides reference answers at the endCopy the code

The principle of

background

Seam Carving algorithm was first proposed by Shai Avidan and Ariel Shamir in their book “Seam Carving for Content-Aware Image Resizing” published in 2007. According to the article, the Image layout is characterized by various forms. And a picture often need a lot of different sizes to fit different scenarios and equipment, but merely frame cut or simple geometric scaling effect is not very good, so I need an elegant way to dynamically adjust the size of the picture, and the transformation of this size and need to be able to keep good image to express information, This is the Seam carving algorithm.

The theory of

The article describes unnoticeable pixels that blend with their surroundings so that the viewer is likely to see the image so that it looks more natural to the viewer. The concept of an energy function is defined here, and the energy function is given as follows:


The higher the energy is, the more information is contained, and the pixels with higher energy should be avoided as much as possible during image transformation

The logic of the algorithm goes like this. Suppose you need to crop the width of the image from 600 to 400. Find a vertical crack and remove the crack from the image. Reduce the width from 600 to 599. Repeat 200 times to get a new image of 400 width.

The vertical seam mentioned above has the following requirements:

  • There is only one pixel per line of the image
  • The pixel coordinates between adjacent rows.

In order to find a Seam with the minimum energy, list all possible Seam routes from the top line down, and finally find the one with the minimum energy loss, where the energy loss at (I, j) coordinates is defined as follows:


After finding the cracks, remove the cracks, and the width of the picture -=1; Then continue to calculate the energy and energy loss in the new image, find the next gap with the least loss, and keep reducing the image width until the image width meets the requirements

The sample

The specific process of cutting pictures is shown below:

  • Figure 1 below is the image to be processed
  • According to theCalculate the energy and get Figure 2
  • Calculate the energy loss from the top down, and the result is shown in Figure 3
  • Find a crack with minimum energy loss, and the crack path is shown in the red line in Figure 4
  • After the crack is removed, go back to Step 2 and continue looking for the next crack

The tensile

Similar to cropping, image stretching is to operate on the pixel with the lowest energy, find the crack with the lowest energy loss, copy the crack and insert it into the original position, and repeat repeatedly to achieve image stretching. It should be noted that, unlike the cutting operation, which operates a crack in each cycle, the stretching operation needs to find all the cracks to be inserted at one time (take the energy loss from small to large before the size strip) and insert the cracks in batches as a whole, otherwise the same crack will be found in each cycle and repeatedly inserted.

The object to remove

To remove objects in the image in a directional manner, simply manually lower the energy value of the object’s corresponding pixel after energy_Function calculates, so that the gaps found will naturally pass through the object. After a few cycles, the object to be removed will be removed from the image. Then use the stretch operation to pull the image back to its original size, and the object removal operation is complete

Energy function

Here’s another question, why is the energy function gradientDistance.

The thoughtful author explains:

We have tested both and of the gradient, saliency measure [Itti et al. 1999], and Harris-corners measure [Harris and Stephens 1988]. We also used eye gaze measurement [DeCarlo and Santella 2002], and the output of face detectors.

After comparing them, it was concluded that no one fit all, but in general,These two are doing well, one of themThe definition is as follows:


3, implementation,

To optimize the

Since each crack requires recalculation of energy and energy loss, the computation of this algorithm is relatively large. The above picture is clipped from 640 to 400, and the average execution on my laptop is about 6s. Considering that the energy of other parts will not change after the crack is removed, in fact, it only needs to update the energy value near the removal. According to this idea, the calculation time of about 0.5s is reduced after optimization, but the whole calculation time is still too long.

Because Java is relatively easy to use, I used Java again, the processing time of the same picture was reduced to about 1s, the efficiency is not very ideal, I hope to find a way to optimize the efficiency again later.

code

Finally, the complete Python code is attached, where:

The Reduce (Image, size) method provides clipping of images

The enlarge(image, size) method provides stretching of the image

The remove_object(image, mask) method provides object removal

Energy_function (image) implements, interested friends can try other energy functions

Python 3.7.3

import numpy as np
import matplotlib.pyplot as plt
from skimage import color, io, util
from time import time

def energy_function(image):
    gray_image = color.rgb2gray(image)
    gradient = np.gradient(gray_image)
    return np.absolute(gradient[0]) + np.absolute(gradient[1])

def compute_cost(image, energy, axis=1):
    energy = energy.copy()

    if axis == 0:
        energy = np.transpose(energy, (1.0))

    H, W = energy.shape

    cost = np.zeros((H, W))
    paths = np.zeros((H, W), dtype=np.int)

    # Initialization
    cost[0] = energy[0]
    paths[0] = 0

    for row in range(1, H):
        upL = np.insert(cost[row - 1.0:W - 1].0.1e10, axis=0)
        upM = cost[row - 1, :]
        upR = np.insert(cost[row - 1.1:W], W - 1.1e10, axis=0)
        upchoices = np.concatenate((upL, upM, upR), axis=0).reshape(3.- 1)

        # M(i, j) = e(i, j) + min(M(i -1 , j - 1), M(i - 1, j), M(i - 1, j + 1))
        cost[row] = energy[row] + np.min(upchoices, axis=0)

        # left = -1
        # middle = 0
        # right = 1
        paths[row] = np.argmin(upchoices, axis=0) - 1

    if axis == 0:
        cost = np.transpose(cost, (1.0))
        paths = np.transpose(paths, (1.0))

    return cost, paths

def backtrack_seam(paths, end):
    H, W = paths.shape
    seam = - np.ones(H, dtype=np.int)

    seam[H - 1] = end

    for h in range(H - 1.0.- 1):
        seam[h - 1] = seam[h] + paths[h, end]
        end += paths[h, end]

    return seam

def remove_seam(image, seam):
    if len(image.shape) == 2:
        image = np.expand_dims(image, axis=2)

    H, W, C = image.shape

    mask = np.ones_like(image, bool)
    for h in range(H):
        mask[h, seam[h]] = False
    out = image[mask].reshape(H, W - 1, C)
    out = np.squeeze(out)

    return out

def reduce(image, size, axis=1, efunc=energy_function, cfunc=compute_cost):
    out = np.copy(image)
    if axis == 0:
        out = np.transpose(out, (1.0.2))

    while out.shape[1] > size:
        energy = efunc(out)
        costs, paths = cfunc(out, energy)
        end = np.argmin(costs[- 1])
        seam = backtrack_seam(paths, end)
        out = remove_seam(out, seam)

    if axis == 0:
        out = np.transpose(out, (1.0.2))

    return out

def duplicate_seam(image, seam):
    if len(image.shape) == 2:
        image = np.expand_dims(image, axis=2)

    H, W, C = image.shape
    out = np.zeros((H, W + 1, C))

    for h in range(H):
        out[h] = np.vstack((image[h, :seam[h]], image[h, seam[h]], image[h, seam[h]:]))

    return out

def find_seams(image, k, axis=1, efunc=energy_function, cfunc=compute_cost):
    image = np.copy(image)
    if axis == 0:
        image = np.transpose(image, (1.0.2))

    H, W, C = image.shape
    indices = np.tile(range(W), (H, 1))
    seams = np.zeros((H, W), dtype=np.int)

    for i in range(k):
        # Get the current optimal seam
        energy = efunc(image)
        cost, paths = cfunc(image, energy)
        end = np.argmin(cost[H - 1])
        seam = backtrack_seam(paths, end)

        # Remove that seam from the image
        image = remove_seam(image, seam)

        # Store the new seam with value i+1 in the image
        seams[np.arange(H), indices[np.arange(H), seam]] = i + 1

        # Remove the indices used by the seam, so that `indices` keep the same shape as `image`
        indices = remove_seam(indices, seam)

    if axis == 0:
        seams = np.transpose(seams, (1.0))

    return seams

def enlarge(image, size, axis=1, efunc=energy_function, cfunc=compute_cost):
    out = np.copy(image)
    if axis == 0:
        out = np.transpose(out, (1.0.2))

    H, W, C = out.shape

    seams = find_seams(out, size - W)
    for i in range(size - W):
        seam = np.where(seams == i + 1) [1]
        out = duplicate_seam(out, seam)

    if axis == 0:
        out = np.transpose(out, (1.0.2))

    return out

def remove_object(image, mask):
    assert image.shape[:2] == mask.shape

    H, W, _ = image.shape
    out = np.copy(image)

    H,W,C = out.shape
    while not np.all(mask == 0):
        energy = energy_function(out)
        weighted_energy = energy + mask * (- 100.)
        cost, paths = compute_cost(out, weighted_energy)
        end = np.argmin(cost[- 1])

        seam = backtrack_seam(paths, end)
        out = remove_seam(out, seam)
        mask = remove_seam(mask,seam)

    return enlarge(out, W, axis=1)


tower = io.imread('imgs/tower_original.jpg')
tower = util.img_as_float(tower)
plt.subplot(1.2.1)
plt.imshow(tower)

out = reduce(tower, 400)
plt.subplot(1.2.2)
plt.imshow(out)

plt.show()
Copy the code

reference

Finally refer to the answer, the upper left corner is the original picture, the other three pictures remove a shoe respectively