Image Retargeting

图像缩略图、图像重定向

前言

这篇文章主要对比DL出现之前的几种上古算法，为了作为DL方法的引子而存在，顺便博客也该更新点新内容上来了，这篇博文就是介绍了我最近在玩什么。

本文方法

传统的方法主要有三种：Resize（拉伸、收缩）、Crop（裁剪）和Seam Carving（接缝裁剪）。

其中接缝裁剪这个算法挺好玩的，论文参见 Seam Carving，截止本篇博文，被引用次数是1914次，可以说是很经典的文章了。

该论文实现的效果图：

本文用到的python库

三种算法的对比由python实现，python版本为python3.8，对应下列依赖库版本为conda直接安装，不同版本请注意自己改动部分接口。

opencv 用于图像处理
scipy 用于图像卷积
notebook 提供环境
matplotlib 用于图像显示
tqdm 用于进度显示（可不用 主要是因为SC算法太慢了 会让人觉得程序卡了
numpy 用于辅助opencv

具体引用代码如下：

import cv2
import matplotlib.pyplot as plt
import numpy as np
from scipy.ndimage.filters import convolve
from tqdm import trange

图像的读入

都有opencv了，还用问么？

img = cv2.imread('test1.jpg')
imshow(img)
img.shape

图像的显示

其中imshow()函数是自己定义的，用于显示处理结果和处理过程的中间图像，这样就方便在notebook中查看了，需要注意的是opencv存储图像的格式和PIL不太一样，为bgr，需要转换。

def imshow(img):
    if (len(img.shape) == 2) :
        plt.imshow(img)
        plt.show()
        return
    b,g,r = cv2.split(img) 
    img_rgb = cv2.merge([r,g,b]) 
    plt.imshow(img_rgb)
    plt.show()

方法一：裁剪（Crop）

裁剪配合numpy的花式索引（别笑，这是正式名称）即可实现，本质上就是对数组的划分。

假如限定屏幕宽度为900像素（因为一般用在手机、iPad等终端上，所以不限制高度），Resize的结果如下：

左侧裁剪：

width = 900
height = img.shape[0]
crop = img[:height, :width]
imshow(crop)

居中裁剪：

width = 900
height = img.shape[0]
crop = img[:height, (img.shape[1] - width) // 2 : (img.shape[1] + width) // 2]
imshow(crop)

可以看出，裁剪方法完全没有考虑图像的细节，简单的裁剪带来内容的严重丢失，优点是速度极快，几乎不消耗资源。

方法二：缩放（Resize）

缩放也是使用opencv内置函数实现。

opencv提供了五种Resize方法：

INTER_NEAREST - 最邻近插值
INTER_LINEAR - 双线性插值 默认
INTER_AREA - resampling using pixel area relation.
INTER_CUBIC - 4x4像素邻域内的双立方插值
INTER_LANCZOS4 - 8x8像素邻域内的Lanczos插值

width = 900
height = 600
resize = cv2.resize(img, (width,height))
imshow(resize)

可以看出，缩放方法造成了图像的失真，而且是严重失真，其优点也是速度极快，几乎不消耗资源。

方法三：接缝裁剪（Seam Carving）

这是本文重点介绍的算法，主要思想是图像总有一些不重要的列，将其删除比删除随机的列或者重新填充要更保留图像的细节部分，同时确保图像整体不严重失真（这里的列不是数组意义上的列，是图像中八联通的一条线，即一条接缝）。

步骤一：获取图像的能量图：

能量图就是图像的边缘啦，相当于图像的细节，这里使用偷懒的卷积实现。

卷积核是这两个：

def cal_energy(img):
    filter_du = np.array([
        [1.0, 2.0, 1.0],
        [0.0, 0.0, 0.0],
        [-1.0, -2.0, -1.0],
    ])

    filter_du = np.stack([filter_du] * 3, axis=2)

    filter_dv = np.array([
        [1.0, 0.0, -1.0],
        [2.0, 0.0, -2.0],
        [1.0, 0.0, -1.0],
    ])

    filter_dv = np.stack([filter_dv] * 3, axis=2)

    img = img.astype('float32')

    convolved = np.absolute(convolve(img, filter_du)) + np.absolute(convolve(img, filter_dv))

    energy_map = convolved.sum(axis=2)
    
    return energy_map

energy_map = cal_energy(img)
print(energy_map.shape)
imshow(energy_map)

卷积核是两个，分别从行和列上进行卷积操作。

这里是用了偷懒的卷积操作，对图像所有像素点做卷积运算，相当于如下C艹代码：

Mat compute_score_matrix(Mat energy_matrix)
{
    Mat score_matrix = Mat::zeros(energy_matrix.size(), CV_32F);
    score_matrix.row(0) = energy_matrix.row(0);

    for (int i = 1; i < score_matrix.rows; i++)
    {
        for (int j = 0; j < score_matrix.cols; j++)
        {
            float min_score = 0;

            // Handle the edge cases
            if (j - 1 < 0)
            {
                std::vector<float> scores(2);
                scores[0] = score_matrix.at<float>(i - 1, j);
                scores[1] = score_matrix.at<float>(i - 1, j + 1);
                min_score = *std::min_element(std::begin(scores), std::end(scores));
            }
            else if (j + 1 >= score_matrix.cols)
            {
                std::vector<float> scores(2);
                scores[0] = score_matrix.at<float>(i - 1, j - 1);
                scores[1] = score_matrix.at<float>(i - 1, j);
                min_score = *std::min_element(std::begin(scores), std::end(scores));
            }   
            else
            {
                std::vector<float> scores(3);
                scores[0] = score_matrix.at<float>(i - 1, j - 1);
                scores[1] = score_matrix.at<float>(i - 1, j);
                scores[2] = score_matrix.at<float>(i - 1, j + 1);
                min_score = *std::min_element(std::begin(scores), std::end(scores));
            }
                        
            score_matrix.at<float>(i, j) = energy_matrix.at<float>(i, j) + min_score;
        }
    }

    return score_matrix;
}

卷积之后的图像即为愿图像的能量图，代表了图像的细节部分，即更锋利的边缘，该算法认为平坦的部分能量更低，自己实验一下就能明白，一方面有效保留了图像中的细节部分，另一方面可能造成算法错误的删除了图像的重要部分，如雪白平坦的胸部等。

步骤二：获取图像接缝

图像的接缝就是一个八联通的线，每行有且只能选取一个像素，这里使用动态规划，回溯法求解，dp转移方程如下：

M(i, j) = e(i, j) + min{M(i - 1, j - 1), M(i - 1, j), M(i - 1, j + 1)}

def minimum_seam(img):
    r, c, _ = img.shape
    energy_map = cal_energy(img)

    M = energy_map.copy()
    backtrack = np.zeros_like(M, dtype=np.int)

    for i in range(1, r):
        for j in range(c):
            if j == 0:
                idx = np.argmin(M[i - 1, j:j + 2])
                backtrack[i, j] = idx + j
                min_energy = M[i - 1, idx + j]
            else:
                idx = np.argmin(M[i - 1, j - 1:j + 2])
                backtrack[i, j] = idx + j - 1
                min_energy = M[i - 1, idx + j - 1]

            M[i, j] += min_energy
    return M, backtrack
M, backtrack = minimum_seam(img)
imshow(M)

图像的接缝由dp求出，可以看出这个算法是十分慢的，同时因为损失最小的接缝被删掉后，该接缝涉及到的左右两侧的损失不能直接复用，必须重新计算，进一步减慢了算法的执行速度。

步骤三：裁剪一列

接缝都求出来了，很明显裁剪的那一列就应该是损失最小的接缝，删除方法使用numpy的黑科技argmin()。

def carve_column(img):
    r, c, _ = img.shape

    M, backtrack = minimum_seam(img)

    mask = np.ones((r, c), dtype=np.bool)

    j = np.argmin(M[-1])

    for i in reversed(range(r)):
        mask[i, j] = False
        j = backtrack[i, j]

    mask = np.stack([mask] * 3, axis=2)

    img = img[mask].reshape((r, c - 1, 3))

    return img
for i in trange(100):
    one = carve_column(img)
imshow(one)

这里模拟删除图像中100列之后的情况。

最终步骤：按需裁剪图像

这里把函数参数改为缩放倍数，其实也可以写为删除列数，都一样，符合人类直觉即可。

def crop_c(img, scale_c):
    r, c, _ = img.shape
    new_c = int(scale_c * c)

    for i in trange(c - new_c):
        img = carve_column(img)

    return img
crop = crop_c(img, 0.8)
imshow(crop)

注意这张图没使用原尺寸进行运算，6小时实在难等。

可以看到，原图像在被接缝裁剪后，保留了本身的细节，未引入大面积失真，缺点是慢！慢！慢！测试图像是一个4K的图像，运算删除一列需要30s，删除20%的列就是768列，总计用时6小时！这样处理图片的速度估计没人可以接受吧。

拓展：裁剪图像的行

很明确了，翻转一下行不就变成列了，复用一下就ok。

def crop_r(img, scale_r):
    img = np.rot90(img, 1, (0, 1))
    img = crop_c(img, scale_r)
    img = np.rot90(img, 3, (0, 1))
    return img
crop = crop_r(img, 0.8)
imshow(crop)

至于图像效果，此处就不运行了，这个算法忒慢了。

拓展：目标移除

理解了原算法之后这就很容易理解了，将能量图中需要重点保留的东西能量加高，需要删除的东西能量减低，利用蒙版（mask）即可快速实现目标移除的效果，这里直接贴原论文的效果图喽。

后言

根据保密协定，DL部分代码暂不贴出，我才不会说我还没看懂呢（

引用

Image-Processing-OpenCV
Implementing Seam Carving with Python
Seam carving--让图片比例随心缩放