介绍在本文中，我们将深入研究一种有趣的算法，称为“seam－carving”，它可以调整图像的大小而不裁剪或扭曲其内容。本文我们将逐步构建，从头开始实现接缝雕刻算法，同时查看其背后的一些有趣的数学原理。理解该算法需要一些微积分方面的知识，但也不是必需的。（本文的灵感来自麻省理工学院的格兰特·桑德森的演讲。）问题让我们看一下这张图片。萨尔瓦多·达利（Salvador Dali）的这幅画被命名为“记忆的永恒”。我们要通过减小图片的宽度来调整图片的大小。我们可以想到的两个有效调整方法是裁剪图片和压缩宽度。但是，正如我们所看到的，裁剪会删除许多对象，挤压又会扭曲图片。我们希望两者兼有，即在不裁剪任何对象和不扭曲对象的情况下减小宽度。我们可以看到，除了对象之外，图片中还有很多空白的区域。我们要在此处完成的任务是以某种方式删除对象之间的空白区域，以便保留图像中有信息的部分，同时丢弃不必要的空间。这是一个棘手的问题，因此，我们将问题分解为更小，更易于管理的小问题。我们可以将这个问题分为两个部分。识别图片中有用的部分（即对象）。标识可以去除而不会扭曲图片的像素路径。识别对象首先我们需要将图片转换为灰度图像，这将对我们稍后进行的操作很有帮助。这是一个将RGB像素转换为灰度值的简单公式

def rgbToGrey（arr）：
   greyVal ＝ np．dot（arr［．．．，：3］， ［0．2989， 0．5870， 0．1140］）
   return np．round（greyVal）．astype（np．int32）

为了识别对象，我们可以制定以下策略：首先我们能以某种方式识别图片中的所有边缘，然后使用seam－carving算法采用不通过边缘的像素路径，通过扩展，可以不碰触任何由边缘封闭的区域来实现调整图像大小的过程。但是，我们如何识别边缘呢？我们可以观察到，每当两个相邻像素之间的颜色发生急剧变化时，最有可能就是物体的边缘，所以我们可以将这种立即的颜色变化合理化，作为从该像素开始的新对象。我们必须解决的下一个问题是如何识别像素值的急剧变化。现在，让我们考虑一个简单的情况，即一行像素。假设我们将此值数组表示为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过滤器，过滤器如下所示，

当我们的过滤器计算沿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”，该函数获取一个像素并计算从那里到图片结尾的最小成本像素路径。在最底行（即i ＝ r－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个接缝雕刻操作。

我们可以看到画中的物体是如何彼此接近的。我们已经成功地使用接缝切割算法缩小了图像的大小，而不会对物体造成任何变形。我已经附上了完整代码链接，感兴趣的读者可以在这里看看。总的来说，seam－carving算法是一个有趣的算法，但是它也有缺点，如果提供的图像有太多的细节或太多的边缘，它会执行识别。