伴跟着研究生阶段课程的开始，也学习到了不少风趣的东西，这儿就介绍下跟着《核算机图形技术》课程中老师介绍的Seam Carving(也叫Content Aware即内容感知)算法，算法是由Shai Avidan, Ariel Shamir在2007年提出。这儿就以个人的了解来尽或许的详细解读这篇文章
算法用处
正如标题那样，Seam Carving算法主要是用于图片的缩放(裁剪、拉伸)，但其不同于传统算法，传统算法的处理是关于整张图片的，在处理图片时，关于图画中的每个像素点，均选用了同等的对待方式，因此经过拉伸之后(特别对错等比拉伸的情况下)，会呈现显着的形变。
以下图的为例
上为640×426像素的，咱们期望将其紧缩至300×426。
第一种处理方式便是裁剪，这儿选用的是居中裁剪，能够看出，经过裁剪之后，图片中的部分信息缺失了。
第二种是缩放，缩放是特别不等比缩放时会发生显着的形变
第三种便是content-aware，基于内容感知算法对图片进行处理，坚持了图片主要部分的相关特性。能够看到，其基本上坚持了时钟塔的巨细与比例，而且对底层部分进行了一定的紧缩。
那么这个算法究竟是怎么完成的呢?
算法原理-紧缩
1. 感知内容
图画在核算机中其实只是由像素组成的矩阵，其中每个像素由R、G、B别离为0-255的数字构成。经过屏幕的烘托，便将数据转化为了人眼能够分辨出的图画
问题也随之而来，核算机要怎么从像素矩阵中感知内容？
能量函数=>能量矩阵
这儿Seam-Carving奇妙的将感知内容部分抽象成了一个能够替换的接口部分并将其界说为了能量函数(Energy Function) 。此部分接口能够被自界说完成，然后影响算法后续的裁剪作用。
从接口层面的抽象来看，Seam-Carving算法会将，为经处理过的原图矩阵数据移交给接口，接口只需返回对应的图画能量矩阵。
能量矩阵其实代表了原图画矩阵中的某个像素点的重要程度，即该像素点在图中越重要，其对应方位的能量矩阵中的能量便会越高。
这儿我运用过如下几个能量核算函数:
自界说能量函数
这个函数是我自己想的，用于做测试的。其原理适当于是核算当时像素点别离与其上下左右像素点之间的差值绝对值的均值。
关于示例图，其终究核算能量矩阵的作用图下:
图中越亮堂的部分，其像素重要程度越高。
比照原图能够发现，自界说算法中对边际区域识别较为敏感，其赋予了边际区域较高的能量
Sabel算子(图画梯度)
Sabel算子法这儿不过多描绘了，主要是用于这儿核算图画中心点梯度走向(变化率趋势)。与自界说能量函数相比，其增加了方针像素点周围角上的像素影响。
关于示例图，其终究核算能量矩阵的作用图下:
比照原图与自界说能量函数能够看出，其算法关于边际识别更加显着。
Forward Energy
Forward Energy算法是于2008年提出的，这儿我并没有详细的去找到对应的算法详细实验原理。可是作为优化算法，这儿也把对应的作用图贴上了。
关于示例图，其终究核算能量矩阵的作用图下:
从图中看，显得稍微杂乱，此刻我也无法比较这种算法的优点。
到这儿，感知内容部分进程就现已结束了。而能量感知部分详细的方针是获取到能量矩阵。
2. 核算需求裁剪(增加)的像素点
当咱们经过第二部分得到详细能量矩阵的时分，咱们现已对图画的接下来的每个点的像素的重要程度有了一定的认知，接下来需求履行去除部分操作了。
在图画缩放的时分，通常咱们都会期望删去的是无关轻重的像素点，由于往往越重要的像素点关于图画的影响越大。
假设咱们要对图画处理进程中让图画从640×426变为639×426，即咱们要使图画变少一列。一起咱们又有了标志图画的重要性的能量矩阵，很容易能够想到，咱们只需求删去能量矩阵中每行能量最低的那个点的像素就行了。可是很不幸，这种简略的删去或许会导致画面的撕裂。那么怎么删去才能不发生撕裂感呢？
这儿也就引申出了 缝（Seam) 的概念，关于一个缝来说，其有必要是接连的线，在图画矩阵中，咱们以为某个像素点和其周围的8个像素点，是接连的。关于图画而言，删去缝的撕裂感更低。
这儿将上述的条件简化如下:
- 若要删去某个点，则接下来只能删去其临近上、下的三个点(这儿以图画缩放列为例)，终究删去的一切点组合成缝
- 咱们需求删去能量总和最低的那个缝
可是咱们又怎么去找到能量最低的那个缝呢？
动态规划
算法的重要性就体现出来了，缝的可选组合适当多，假如咱们要做暴力核算的话，一个640×426的图画想要缩放成639×426，其包括的缝的个数或许性约为3^426，咱们要从这么多或许里边去寻找最低的那个，显着是不现实的。而且该问题显着是能够经过迭代来缩小问题规模的，所以这儿运用动态规划来解决能够有效下降核算复杂度。
首先，咱们要去考虑，假设咱们现已确认了要删去图画中缝的当时点坐标为(i, j)，那么咱们一定会选择的缝为以其上边三个点为终点的缝的能量最低值的那个缝，此刻当时缝的能量为
E(i,j) = min(E(i - 1,j - 1), E(i - 1,j), E(i - 1,j + 1)) + e(i, j)
，由此递归表达式就得到了，咱们只需求运用空间记录好每个E(i, j)的能量值，即可获得一切缝的最低能量值。
这儿能够看到，经过核算后，能够得到缝的最低累积能量值矩阵。咱们想要详细获得缝，能够运用倒序，相同沿着能量最低矩阵的最低能量途径便可得到详细的缝的途径坐标。
接下来展现的是累积能量矩阵函数图
自界说能量函数
Sabel算子(图画梯度)
Forward Energy
在咱们有累积能量图之后，能够更直观的想到，咱们的途径其实只需从下往上去找最暗的那条缝就行了。
这儿将途径标回到原图中能够得到:
自界说能量函数
Sabel算子(图画梯度)
Forward Energy
其中红线部分为裁剪途径，能够看到，不同算法的裁剪途径均不相同。
3. 履行裁剪
接下来需求做的，便是把上述步骤中标红的点从图画中删去，即可完成一次Seam Carving缩放操作，接下来咱们只需求将裁剪后的图片递归进行操作1-3步，直到图片巨细达到要求。
这儿将运用gif图片展现详细裁剪进程
自界说能量函数
Sabel算子(图画梯度)
Forward Energy
比照能够看出，自界说算法在前期影响几乎相同。跟着图画的继续紧缩，作用下降比较显着。
这儿只演示了沿着竖轴删去行，若要延横轴进行删去的，能够采纳将图画进行90旋转，随后对旋转后的图画继续按竖轴进行缩放，即可满足要求。
算法原理-扩大
关于图画紧缩，Seam Carving的主要目的是删去能量值最低缝用以确保能量高的部分，即要点区域不受影响。关于图画扩大，其原理相同，即尽或许的确保能量高的区域在图画扩大进程中维持其原有结构不变化。所以咱们需求采纳的处理才做为，先选用紧缩算法，获取前k条缝(k为需求扩大后图画宽度-当时图画宽度)，随后咱们将图画依照缝的次序顺次拉伸，并选用传统拉伸算法对拉伸点进行像素填充，终究所得图画即为填充像素。
关于扩大作用，跟着扩大的比率的提高，扩大作用在逐渐变差(由于哪怕获取前k条缝，期望控制的方针区域也会跟着k的增大而发生形变)
自界说能量函数
Sabel算子(图画梯度)
Forward Energy
算法原理-方针区域删去(此处部分为个人猜想，并无实际代码支撑)
在论文中提到了能够关于用户指定的区域进行剔除。此处也能够等价的将其看做，图画或许需求删去包括特定区域的指定的缝。这儿个人了解依然能够对 能量函数(能量矩阵) 部分处做相关处理，即结合用户给定区域，对累积能量矩阵的相关方位的能量赋予较大的负值，用于招引动态规划部分，将此区域的缝设置为最小累积能量的缝。随后结合后续操作，即可在紧缩图画的一起完成删去特定区域。
算法总结
Seam Carving算法做为图画缩放算法，具有如下优点:
- 具有优异的扩展性，其
能量函数的引入使得后续算法裁剪步骤能够与前面的算法能量函数部分解耦，然后使咱们在对裁剪部分的规划时，能够更多的关怀能量函数的完成。 - 具有不错的作用
但一起其也具有显着缺陷即比照传统图画拉伸算法，因其处理步骤多，导致其算法效率低下
从规划角度出发Seam Carving算法展现出了杰出的规划能力，其规划模式契合了接口模式，又将动态规划交融到了途径核算中。
一起，上面这些技巧也是咱们在接下来能够借鉴并应用在其他范畴的办法。
上述算法支撑的相关代码在github
