基于Seam Carving实现图像的重定位-计算机图像与图形技术大作业

# SeamCarving 实现图像的重定位 ## 一、引言 第 34 届 SIGGRAPH 数字图形学年会于 2007 年举行，在会中，ShaiAvida 教授和 ArielShamir 教授展示了他们的学术成果，一种能够保持图像中的“关键区域”不变，仅在图像中“不重要的区域”进行修改的图像放缩算法。该算法能够改变图像的整体宽高比，但是却能很好地维持“重要区域”完整性，不会发生扭曲变形或比例失调。这样的特性使得算法能够在很多实际情形下得以应用，例如，当图像由计算机屏幕迁移到手机屏幕，保持图像全屏显示的同时（改变了宽高比），也能够正常的显示图像的主体内容。或是将普通相机拍摄的照片经过算法处理起到广角相机的拍摄效果。算法在经过简单的改进之后，甚至可以通过简单地人工标注，实现“物体删除”的效果。 本次实验报告主要分为五个部分，第一部分介绍算法以及文章的整体结构。第二部分介绍算法的原理以及计算步骤。第三部分描述算法的实现过程和具体代码。第四部分详细地给出算法在两组图像中的实验结果，并做出分析。第五部分对原 SeamCarving 算法做出尝试性改进，观察改进后新的实验结果，并做出分析。 其中，实验部分包含以下的实验及结果： 1. 图像剪裁：将原图像剪裁为指定尺寸，并保持主体内容完整且比例正常。 2.图像重定向（Retarget）：将原图像重定向到指定尺寸，并保持主体内容完整且比例正常。 3. 内容去除：指定一个矩形的内容，将该矩形内容从原图像中删除，并且尽可能保持其余部分维持原有形状。 而第五部分则包含两个方面的实验尝试与结果： 1.结合其他算法重新评估像素重要性并生成能量图，观察图像剪裁结果。 2. 优化算法时间性能，一次性选择多条 Seam 进行剪裁，观察图像剪裁的结果。 ## 二、算法描述 相比于算法目标的复杂，算法步骤却异常的简单，下面具体介绍利用 SeamCarving 算法进行图像剪裁的步骤： 1.计算图像中每个像素的“重要程度”（能量），生成能量图。在绝大多数情况下，我们可以做出如下假设：像素值变化越剧烈的区域（如边界，角点），是人眼最容易捕捉到的区域，也是图像相对重要的区域。与此相反，像素变化较为平缓的区域，很多情况下使图像中的“背景区域”，是人们很少关注的区域。所以，算法给出一个简易假设：如果一个像素梯度绝对值较大，则该像素重要，算法倾向于保留。而某像素位置的梯度绝对值接近 0，则该像素不重要，算法倾向于删除。因此，某像素的“重要度”（能量）可由以下公式计算得出：  每个像素按照上述公式算出能量值后，构成能量图 E。 2. 从能量图中找到一条能量累积最小的纵向八连通路径，称之为 Seam。 通常在这个步骤中使用动态规划算法，能够使得算法的时间复杂度从 n3^n （暴力搜索）降低至 n^22。其核心步骤是构建能量累计图 M，其计算方式如下：  在此同时，记录每一个像素最小能量路径的前置像素。之后，从 M 最后一行找到能量累积最小的像素，从此像素开始，根据前置像素信息回溯到第一行，最终找到一条能量累积最小的纵向连通路径。 3.删除上一步骤中得到的连通路径。 4.重复 1 至 3 步骤，直到删除的列数符合剪裁要求。 5.将图像旋转 90°，重复 1-4 步骤，直到删除的行数符合剪裁要求。 6.将图像旋转回原图方向。对于图像重定向的任务，其核心思路是：首先通过其他方法对原有图像进行等比例放缩（例如双线性插值放大图像），之后在该图像上利用 SeamCarving 进行图像剪裁，即可起到图像重定向的效果。 而对于区域删除的任务，只需要将待删除像素的重要性（能量）特殊标注为 ∞，就能使生成的 Seam 通过待删除区域，不断删除 Seam 直到将目标区域完全删除。同理，对于不想误删的区域，可手动将其重要性（能量）标注为 +∞。 ## 三、算法实现 ### 1. 计算能量图 本次实现选取 Sobel 算子计算像素点的梯度，Sobel 算子形式如下：  该算子与原图像做卷积，可以得出图像每个像素点的梯度，这就构成了算法描述中提到的能量图，其代码实现如下图：  ### 2.计算能量累积图 生成能量累积图过程中值得注意的问题是，计算时需要时刻记录每个像素在其最小能量连通路径中的前置节点，这样方便在找到最小累积值对应的像素之后，回溯找到整条最小能量连通路径。其实现代码如下所示：  ### 3.找出最小能量连通路径并删除这部分 通过上一步骤中生成的前置节点信息 track，回溯找到最小能量的联通路径，最终对其进行删除，其实现代码如下所示：  ### 4.根据目标图片尺寸对原图进行剪裁。 其实现代码如下:  ### 5.图像重定向 实现代码图像的重定向主要针对目标尺寸比原图像尺寸大的情况（若重定向尺寸较原图小，可直接进行图像剪裁）。针对这种情况，首先根据目标尺寸的长宽，适当等比例放大原图像，针对放大后的图像再进行上述的图像剪裁操作，最终完成图像重定向的目标。  ### 6. 区域删除的实现 1)设定某矩形区域能量值为 ∞，并删除一条最小能量连通路径  2)多次删除连通路径，直到指定区域完全被删除   其中值得注意的是，第一个函数是将标定的矩形区域以纵向删除的方式进行去除（一次删除矩形中的一列），而后者则是以横向的方式对选定矩形区域删除（一次删除矩形中的一行）。根据选定目标的不同，两种删除方式得到的结果也有所不同。 ## 四、实验结果与分析 ### 1. 中间结果的可视化 1)原图像读取  2)能量图  3)能量累积图  4)找到最小能量连通路径左边图像中使用红色细线标注（中部偏右），右边图像使用绿色细线标注（靠左部分）。  ### 2.图像剪裁 ![](https://www