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 codeWe 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 codeThe 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 the
Calculate 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 gradient
The thoughtful author explains:
We have tested both 
After comparing them, it was concluded that no one fit all, but in general,
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
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 codereference
Finally refer to the answer, the upper left corner is the original picture, the other three pictures remove a shoe respectively
