回顾
第二周主要内容仍然是关于图的算法,主要内容为:
最小生成树
最短路径
- Dijkstra算法:适用无负权值边的图
- DAG最短路径算法:使用拓扑排序
- Bellman-Ford算法:适用含负权值边的图
编程作业是SeamCarver:原题地址
题目
SeamCarving是一种调整图像尺寸的算法:从一幅图像中选出最不重要的像素并删去,在尽可能保留图像内容的情况下改变图像的尺寸。
上图就是SeamCarving算法的应用,原图尺寸为505-by-287,变换后的图片尺寸为355-by-287。虽然尺寸变了,但是没有发生拉伸扭曲,保留了原图的特征。
算法步骤:
- 计算每个像素点的权重
- 找到水平(垂直)方向上的权重最小的像素序列,称为seam
- 移除seam
备注:
- 像素点的权重计算使用
dual-gradient energy function
,具体计算方法在原题中有。 - 从像素点
(i,j)
出发(假设垂直方向)只能连接到下一行的相邻三个像素(i-1,j+1)
,(i,j+1)
,(i+1,j+1)
- 坐标系与默认的不同:
(i,j)
表示第j
行,第i
列12345a 3-by-4 image(0, 0) (1, 0) (2, 0)(0, 1) (1, 1) (2, 1)(0, 2) (1, 2) (2, 2)(0, 3) (1, 3) (2, 3)
API:
解析
- 图像的表示使用alg4.jar中的Picture类。但是构造这个类的开销很大,在内部用一个二维数组作为类成员变量来表示图像中每个点,数组中存的值为此像素点
int
类型的rbg值。在实现算法的时候使用此二维数组,只在public Picture picture()
方法中生成Picture对象并返回。 核心算法是找到某一方向上的seam,下面一步步思考:
- 首先可以把图像抽象成一个有向图,顶点是每一个像素点,每个顶点有三条边指向下一行(列)的相邻顶点。
- seam即是一条最短路径,权值就是最短路径上所有像素点的权重。
- 这是一个无环有向图(DAG),从时间复杂度考虑应该使用无环有向图的最短路径算法,而不是Dijkstra算法。
- 因此需要得到拓扑顺序,在这里不需要使用深度优先搜索来计算。以垂直方向为例,自上而下,每一行的拓扑顺序先于下一行,而每一行中各个顶点的顺序无关紧要。
- 因此在最短路径算法中,可以直接for循环自上而下遍历所有顶点,进行松弛(relax)操作。
水平和垂直方向:两个不同方向的算法实质是一样的,只要先对表示图像的二维数组进行转置,就能够复用代码。
java中二维数组实际是由一维数组的每个元素表示其他各个一维数组,根据题意,垂直方向的像素作为第二层数组,方便用System.arraycopy()
来整体移动,因此我们实现removeHorizontalSeam(int[] seam)
方法:即水平方向上每行移除一个像素点,再整体移动剩余像素点;而对于removeVerticalSeam(int[] seam)
方法,只要转置二维数组、调用removeHorizontalSeam(int[] seam)
、再转置二维数组。
代码
成员变量:
构造方法:
|
|
width()
和height()
:
|
|
energy()
:使用dual-gradient energy function
来计算
|
|
findVerticalSeam()
- 先计算所有顶点的distTo值,即从第一行到此顶点的最短路径上所有顶点权值之和
- 找出最后一行中distTo值最小的顶点,此顶点属于seam
- 根据nodeTo,逐行逆向找到每个属于seam的顶点
|
|
findHorizontalSeam()
|
|
removeHorizontalSeam
|
|
removeVerticalSeam:转置后复用removeHorizontalSeam(int[] seam)
|
|
最后是转置方法:
|
|
成绩
|
|
完整代码和测试用例在GitHub上,欢迎讨论https://github.com/michael0905/SeamCarver