Seam carving 图像缩放

一、算法理论

   传统的图像缩放（opencv中的resize和crop）采用几何缩放和插值技术（线性插值和双线性插值）或者roi裁剪,这样有可能是图像失真。最近回过头去看比较经典的图像处理算法，看到《Seam Carving for Content-Aware Image Resizing》这篇关于图像缩放的比较有意思的算法，这是一种内容感知的缩放算法，在改变图像尺寸的同时充分保留图像内容特征。

   算法的核心思想是寻找某一维度（列或者行）的能量最小的裁剪线（seam），然后删除这条像素线，并且不断重复这个过程实现图像缩小；对于图像放大，则找到相应数量的最小能两线，然后在最小能量线处用邻近插值插入一条能量线。Seam的寻找是基于能量图实现的，初始能量图实际就是原始图像的梯度图，用普通sobel算子就可求得：

                                                                          

 

  算法具有内容感知，而能量图就是梯度图，不难想到实际就是要尽可能保住图像中梯度较大的区域（及边缘特征），求得最小能量线又是一种优化问题，作者定义竖直seam（连接方式）为：

                                                 

  n为行数，也就是相邻两行的连接线只能是当前行像素位置的八连通域子集，即列编号最多相隔一个像素，而非天马星空随便连接。同理，水平seam定义为：

                                               

  那么如何求得这样的最小能量线呢，作者将其看做是一种最优化问题，优化目标（最小能量线）定义如下 ：

                                        

  比如竖直能量线上的能量值之和最小则为我们要寻找的。基于之前对seam连接的定义，作者提到采用动态规划的方式求最小能量线，首先需要求得能量累积图(竖直线：从上到小，水平线：从左到右)，求解过程每一个像素会记录上行（列）的最小值的索引;

                                             

   然后能量累积图中在从最后一行的最小能量值开始回溯就能找到最小能量线，最后删除即可。

  上面说的是某一维度的裁剪算法，如果两个维度都有裁剪量，基于上面的理论，可能会想到两个维度分别裁剪。作者则认为这也是一种优化问题，每一步裁剪哪一个维度通过如下方式确定，

                                            

   其实简单就是每一步中选择能量较小的seam作为该步的裁剪。

二、算法实现

一）、算法流程

  1、单个维度的缩小（裁切）

    1）求初始能量图（sobel梯度）

    2）从第一行（列）到最后一行（列），求能量累积图。

    3）从最后一行（列）最小能量值回溯到第一行找到seam

    4）删除seam

    5）重复1）-4）直到满足设定的值。

 

   2、两个维度的缩小

    1）求初始能量图（sobel梯度）

    2）求得两个维度（行和列）的能量累积图

    3）求得两个维度的最小能量线sx和sy，取较小的能量线作为当前不删除线

    4）重复1）-3）知道两个维度的删除量满足设定值。

二）算法C++实现代码

Github: https://github.com/SyGoing/seam-carving

三）效果展示：