介绍

动态规划是如此的有用，然而只盯着尽人皆知的LIS，LCS，背包，矩阵连乘之类是相当没劲的。挖掘一些在视觉方面的应用让事情变得有意思。它在改变图像分辨率和图像融合方面扮演了重要角色。

改变图像分辨率之Seam carving

Seam carving是一种方法，它可以智能的改变图像分辨率（保留重要的，干掉次要的，孰轻孰重取决于能量函数）。也可以强调图像内容（content amplification），还可以删除特定的对象。让我先用几张图来说明这几个意思。

• 改变图像分辨率（content aware image retarget）

• 强调图像内容（content amplification）

• 删除特定对象（object remove）

Seam carving是如何做到这些的，顾名思义它要在图像中找到一条最优的缝隙，这条缝隙上面的像素是最不重要的，或者说这条缝隙所经历像素的能量累加和是最小的。这条缝隙可以是垂直的从上贯穿到下，并且宽度为一个像素。也可以从左贯穿到右，高度为一个像素。先来看看这条神奇的线。

因为这条线上所经历的像素最不重要，删除它是最合理的。如果删掉一条垂直缝，那么图像就窄了一个像素，在缩小的图像上再找，再把它删了，不断这样做直到你满意。下面的图显示了在处理过程中所找到的最优缝隙。

不禁要问，怎样找到些最不重要的像素。就是用动态规划，像素的重要性由能量函数衡量，这个能量函数可以是图像的梯度（人对边缘比较敏感），或者是Harris角点量度，或者是梯度直方图（HOG）。梯度作为能量函数非常简单也非常有效。

针对垂直最优线，重新描述下这个问题。求一张图像所有的从上贯穿至下的线中的最少像素代价。值得注意的是对缝隙上的像素有约束条件，从第1行开始每次只能能向左下，下，右下三个方向行走。

借由动态规划三部曲，抽象出子问题，由子问题分析状态转移方程，之后自底向上的实现。用M[i][j]表示经历到第i行第j个像素的最小代价。那么因为缝隙的约束，它前面的状态只能是M[i-1][j-1]，是M[i-1][j]，M[i-1][j+1]。显然M[i][j]应该是从他们中最小的那一位置过来的，这样累加和才会最小。最终的状态转移方程如下。

实现Seam carving的基本功能也比较简单，源码在https://github.com/tpys/seam-carving

图像融合

意思就是两张重叠的图像融合成新的没有人工痕迹的新图，图像融合有两方面含义：1是在重叠的区域的什么位置进行融合。2是使用什么方法融合。和seam carving类似，这里也是用动态规划确定融合的位置，确定最优的缝隙。只是不再用梯度作为能量函数，而是用重叠区域的两图像素平方差。