介绍
动态规划是如此的有用,然而只盯着尽人皆知的LIS,LCS,背包,矩阵连乘之类是相当没劲的。挖掘一些在视觉方面的应用让事情变得有意思。它在改变图像分辨率和图像融合方面扮演了重要角色。
改变图像分辨率之Seam carving
Seam carving是一种方法,它可以智能的改变图像分辨率(保留重要的,干掉次要的,孰轻孰重取决于能量函数)。也可以强调图像内容(content amplification),还可以删除特定的对象。让我先用几张图来说明这几个意思。
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类似,这里也是用动态规划确定融合的位置,确定最优的缝隙。只是不再用梯度作为能量函数,而是用重叠区域的两图像素平方差。
参考
http://www.win.tue.nl/~wstahw/edu/2IV05/seamcarving.pdf
http://www.statfe.com/projects/csc5280_project4/index.html
http://www.cs.stonybrook.edu/~svittayakorn/seamcarving.html
http://eric-yuan.me/seam-carving/
http://www.cis.upenn.edu/~cis110/12su/hw/hw07/dynprog.shtml
原文:http://www.cnblogs.com/tpys/p/3892660.html