关于人工智能:接缝雕刻算法一种看似不可能的图像大小调整方法

作者 |Samarendra Chandan Bindu Dash
编译 |Flin
起源 |analyticsvidhya

介绍

在本文中，咱们将深入研究一种乏味的算法，称为“接缝雕刻”。调整图像的大小而不裁剪或扭曲其内容仿佛是不可能实现的工作。咱们将逐渐构建，从头开始实现接缝雕刻算法，同时查看其背地的一些乏味的数学原理。

微积分方面的常识将有助于后续学习，但不是必须的。咱们开始吧。

（本文的灵感来自麻省理工学院的格兰特·桑德森的演讲。）

问题

让咱们看一下这张图片。

萨尔瓦多·达利（Salvador Dali）实现的这幅画被命名为“记忆的永恒”。咱们对绘画的内容更感兴趣，而不是其艺术价值。咱们要通过减小图片的宽度来调整图片的大小。咱们能够想到的两个无效过程是裁剪图片或压缩宽度。

然而，正如咱们所看到的，裁剪会删除许多对象，挤压又会扭曲图片。咱们心愿两者兼有，即在不裁剪任何对象或不扭曲对象的状况下减小宽度。

咱们能够看到，除了对象之外，图片中还有很多空白。咱们要在此处实现的工作是以某种形式删除对象之间的空白区域，以便保留图像中乏味的局部，同时抛弃不必要的空间。

这的确是一个辣手的问题，很容易迷失。因而，将问题合成为更小，更易于治理的局部始终是一个好主见。咱们能够将这个问题分为两个局部。

1. 辨认图片中乏味的局部（即对象）。
2. 标识能够去除而不会扭曲图片的像素门路。

辨认对象

在持续之前，咱们须要将图片转换为灰度图像。这将对咱们稍后进行的操作很有帮忙。这是一个将 RGB 像素转换为灰度值的简略公式

def rgbToGrey(arr):
    greyVal = np.dot(arr[...,:3], [0.2989, 0.5870, 0.1140])
    return np.round(greyVal).astype(np.int32)

为了辨认对象，咱们能够制订策略。如果咱们能以某种形式辨认图片中的所有边缘呢？而后，咱们能够要求接缝雕刻算法采纳不通过边缘的像素门路，因而，通过扩大，不会碰触任何由边缘关闭的区域。

然而，咱们如何辨认边缘呢？咱们能够看到的一个察看后果是，每当两个相邻像素之间的色彩产生急剧变动时，最有可能就是物体的边缘。咱们能够将这种立刻的色彩变动合理化，作为从该像素开始的新对象的开始。

咱们必须解决的下一个问题是如何辨认像素值的急剧变动。当初，让咱们思考一个简略的状况，即一行像素。假如咱们将此值数组示意为 x。

咱们能够取像素 x [i + 1]，x [i]之间的差。它会显示以后像素从右侧变动了多少。或者咱们也能够取 x [i]和 x [i-1]之差，这将在左侧产生变动。为了示意总变动，咱们可能要取两者的平均值，得出

相熟微积分的任何人都能够疾速地将此表达式辨认为导数的定义。咱们须要计算 x 值的急剧变动，因而咱们正在计算它的导数。如果咱们定义一个过滤器 [-0.5,0,0.5]，而后用数组[x[i-1]，x[i]，x[i+1] 乘以它的元素，而后取它的和，它就会失去 x[i]的导数。

因为咱们的图片是 2D 的，因而咱们须要 2D 过滤器。我不会具体介绍，然而咱们过滤器的 2D 版本看起来像这样，

当咱们的过滤器计算沿 x 轴的每个像素的导数时，它将给出垂直边缘。同样，如果咱们沿 y 轴计算导数，则将具备程度边缘。过滤器如下。（与转置时用于 x 轴的过滤器雷同。）

这些过滤器也称为Sobel 过滤器。

所以，咱们有两个过滤器，须要在图片中流传。对于每个像素，用（3X3）子矩阵对其进行逐元素乘法，而后取其和。这种运算被称为卷积。

卷积：

数学上，卷积运算就是这样，

看看咱们如何对两个函数进行逐点乘法，而后对其进行积分。从数值上讲，这将与咱们之前所做的绝对应，即过滤器和图像的逐元素相乘，而后对其求和。

留神，对于 k 函数，它如何写为 k（t-τ）。因为卷积运算须要翻转其中一个信号。你能够直观地将其设想成这样：两列火车在一条直线的程度轨道上互相朝着一个不可避免的碰撞（不用放心，因为它们是叠加的，火车不会产生任何事件）。因而，火车头将彼此面对。当初，假如你正在从左到右扫描轨道。而后，对于左列火车，你将从尾部向头部扫描。

同样，计算机须要从右下角（2,2）角到左上角（0,0）而不是从左上角到右下角读取过滤器。因而，理论的 Sobel 过滤器如下所示，

在进行卷积运算之前，咱们先进行 180 度旋转。

咱们能够持续编写一个简略的实现来进行卷积运算。像这样：

def naiveConvolve(img,ker):
    
    res = np.zeros(img.shape)
    r,c = img.shape
    rK,cK = ker.shape
    halfHeight,halfWidth = rK//2,cK//2
    
    ker = np.rot90(ker,2)
    img = np.pad(img,((1,1),(1,1)),mode='constant')
    
    for i in range(1,r+1):
        for j in range(1,c+1):
            res[i-1,j-1] = np.sum(np.multiply(ker,img[i-halfHeight:i+halfHeight+1,j-halfWidth:j+halfWidth+1]))
    
    return res

这将很好地工作，然而将破费大量工夫来执行，因为它将进行近 9 r c 的乘法和加法运算以得出后果。然而咱们能够聪慧地应用数学中的更多概念来大大减少工夫复杂度。

疾速卷积：

卷积具备乏味的性质。时域中的卷积对应于频域上的乘法。即

，其中 F（w）示意频域中的函数。

咱们晓得傅立叶变换将时域的信号转换成其频域。因而，咱们能够做的是计算图像和滤波器的傅立叶变换，将它们相乘，而后进行傅立叶逆变换以取得卷积后果。

为此咱们能够应用 NumPy 库。

def fastConvolve(img,ker):
    imgF = np.fft.rfft2(img)
    kerF = np.fft.rfft2(ker,img.shape)
    return np.fft.irfft2(imgF*kerF)

（留神：在某些状况下，得进去的值可能与奢侈办法稍有不同，因为 fastConvolve 函数会计算圆形卷积。然而实际上，咱们能够轻松地应用疾速卷积，而不用放心这些较小的值差别。）

酷！当初，咱们有了一种无效的办法来计算程度边缘和垂直边缘，即 x 和 y 重量。因而，应用

def getEdge(greyImg):
    
    sX = np.array([[0.25,0.5,0.25],
                   [0,0,0],
                   [-0.25,-0.5,-0.25]])
    sY = np.array([[0.25,0,-0.25],
                   [0.5,0,-0.5],
                   [0.25,0,-0.25]])
    
    #edgeH = naiveConvolve(greyImg,sX)
    #edgeV = naiveConvolve(greyImg,sY)
    edgeH = fastConvolve(greyImg,sX)
    edgeV = fastConvolve(greyImg,sY)
    
    return np.sqrt(np.square(edgeH) + np.square(edgeV))

辨认像素门路：

对于间断门路，咱们能够定义一个规定，即每个像素仅连贯到它上面的 3 个最近的像素。这将使像素从上到下具备间断的门路。因而，咱们的子问题成为根本的寻路问题，咱们必须将老本降到最低。

因为边缘具备更高的幅度，如果咱们持续以最低的老本移除像素门路，它将避免出现边缘。

让咱们定义一个函数“cost”，该函数获取一个像素并计算从那里到图片结尾的最小老本像素门路。咱们有以下察看，

1. 在最底行（即 i = r-1）

1. 对于任何两头像素，

代码：

def findCostArr(edgeImg):
    r,c = edgeImg.shape
    cost = np.zeros(edgeImg.shape)
    cost[r-1,:] = edgeImg[r-1,:]
    
    for i in range(r-2,-1,-1):
        
        for j in range(c):
            c1,c2 = max(j-1,0),min(c,j+2)
            cost[i][j] = edgeImg[i][j] + cost[i+1,c1:c2].min()
                
    return cost

绘图：

咱们能够在图中看到三角形。它们示意不返回的点，也就是说，如果你达到那个像素，就没有一条门路不通过边缘达到底部。而这正是咱们试图防止的。

从老本矩阵中寻找像素门路能够很容易地用贪心算法实现。在最下面一行找到最小老本像素，而后向下挪动，在所有连贯到它的像素中抉择老本最低的像素。

def findSeam(cost):
    
    r,c = cost.shape
    
    path = []
    j = cost[0].argmin()
    path.append(j)
    
    for i in range(r-1):
        c1,c2 = max(j-1,0),min(c,j+2)
        j = max(j-1,0)+cost[i+1,c1:c2].argmin()
        path.append(j)

    return path

为了删除门路定义的接缝，咱们只须要遍历每一行并删除门路数组提到的列。

def removeSeam(img,path):
    r,c,_ = img.shape
    newImg = np.zeros((r,c,3))
    for i,j in enumerate(path):
        newImg[i,0:j,:] = img[i,0:j,:]
        newImg[i,j:c-1,:] = img[i,j+1:c,:]
    return newImg[:,:-1,:].astype(np.int32)

在这里，我曾经事后计算了 100 个接缝雕刻操作。

咱们能够看到画中的物体是如何彼此靠近的。咱们曾经胜利地应用接缝切割算法放大了图像的大小，而不会对物体造成任何变形。我曾经附上了残缺代码链接。感兴趣的读者能够在这里看看。

• https://github.com/Samarendra…

总的来说，接缝雕刻是一个乏味的算法。它有一些正告，因为如果提供的图像有太多的细节或太多的边缘，它将失败。

应用该算法对不同的图片进行批改以查看最终后果总是很乏味的。如果你有任何疑难或倡议，请给我留言。

感激你的浏览！

原文链接：https://www.analyticsvidhya.c…

欢送关注磐创 AI 博客站：
http://panchuang.net/

sklearn 机器学习中文官网文档：
http://sklearn123.com/

欢送关注磐创博客资源汇总站：
http://docs.panchuang.net/