动态规划的思想及其在图像缩放中的应用

摘要：动态规划经常用于求解某些具有最优性质的问题。如今随着对动态规划算法的日渐深入的研究，动态规划被用在生产调度等各个方面。该文介绍了动态规划的基本思想，包括动态规划模型的基本要素，动态规划的特点及设计一个动态规划算法的基本步骤。同时，结合Seam Caving图像缩放方法[[1]]，具体介绍了动态规划算法在图像缩放方面的应用。

关键词：动态规划；图像缩放；接缝

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）20-4815-03

The Idea of Dynamic Programming and its Application in the Image Zooming

ZHOU Fen-qin，CAI Hai-chao，HUANG Lu-yao，PAN Hai-kuan，ZHU Bao

（College of Computer Science and Technology ，Southwest University for Nationalities ，Chengdu 610041，China）

Abstract： Dynamic programming is often used to solve some of the problems with optimal properties. With today's increasingly algorithm-depth study of dynamic programming ， it is used in all aspects such as production scheduling. This article describes the basic idea of dynamic programming， including the basic elements of dynamic programming model， the characteristics of dynamic programming and the basic steps to design a dynamic programming algorithm. Meanwhile， combined with Seam Caving image scaling method， specifically introduced the application of dynamic programming algorithm in terms of image scaling.

Key words： Dynamic Programming；Image scaling；Seam

动态规划的本质是为解决多阶段决策问题，是运筹学的一个分支。在20世纪50年代由美国数学家R.E Bellman等人提出。如今，动态规划的应用已经非常的广泛，例如用动态规划算法进行弱目标检测[[2]]，求解水库优化调度问题[[3]]，工程控制技术和最优控制等方面。

通过对大量动态规划实例的分析，简要介绍了动态规划的基本思想。结合实例，在图像缩放应用中用动态规划解决最优接缝的查找，使图像在缩放过程中尽可能保持图像本身的内容。

1 动态规划基本思想

1.1 动态规划模型的基本要素

动态规划模型一般由以下要素组成：

阶段：多决策问题通常有若干阶段，状态可以从前一个阶段转移到下一个阶段。

状态：各阶段开始时的客观条件叫做状态。状态时阶段的属性，一个阶段可以分成若干个状态。

决策：从一个阶段的某个状态到下一个阶段的某个状态所做的决定叫做决策。

状态转移：通过决策，从一个阶段的某状态转移到下一阶段的某状态的决策结果。

1.2 动态规划的特点

类似于贪心算法，动态规划也是一种递推算法，从局部最优推出全局最优。贪心是一种特殊的动态规划，要求每一步的最优解包含上一步的最优解。一般来说，用动态规划解决的问题具有以下两个特点：

1） 最优化原理。美国数学家R.Bellman曾提出：“作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。”[[4]]也就是说问题的最优解只取决于子问题中的最优解而与非最优解无关。例如下图，求起点A到终点E的最短路程，只与A到中间点D的最短路程有关。

2） 无后向性。如果当前决策影响到下一步的状态，从而使得问题没有得到最优决策，这就是后效性。用动态规划解决问题时是需要做到全局最优则局部最优，即第i个状态决定之后，无论第i+1个状态如何都不会改变第i个状态。例如下图在三角形中求从顶层到底层数字的最大和。

假设从局部最优求全局最优。则每次找下方最大的数字，得到最大和1+3+3+6=13，没有达到最优。

利用动态规划的思想全局最优求局部最优，找下方最大路径最大的方向去走，得到最大和为1+3+5+5=14。无后效性。

1.3 设计一个动态规划算法的基本步骤[[5]]

确定问题决策对象；正确划分阶段和选择阶段变量；确定状态和状态变量：

确定决策并写出状态转移方程：写出规划方程。

2 动态规划算法在图像缩放中的应用

在手机、电脑等设备上播放图像时，需要对其进行缩放或裁减以适应不同的尺寸或分辨率，标准的图像缩放容易失真。在2007年SIGGRAPH会议上Avidan等人提出了Seam Carving（接缝雕刻）技术，最大程度的保留图像原始信息。

在传统图像缩放的方程中，要尽可能保持原始图像，就需要消除混合周围环境的不引人注意的像素，这些像素称为低能量像素，

我们可以采用几种策略来删除低能量像素，例如

1） 为了保持高像素值，按升序排列的方式删除最低能量的像素。

缺点：会破坏图像的矩形形状，因为每一行删除的像素点数不一定相同。

2） 为了保留图像的原始形状，从每一行删除同等数量的低能量像素。

缺点：容易破坏图像的内容。

若既要保留图像原始形状，又要尽可能的保留图像的内容，Avidan等人提出图像接缝的策略。所谓接缝，就是由低能量像素组成低能量线，删除低能量线对图片整体的影响较小。对此，寻找最优接缝就成了关键，我们可以用动态规划的方法来解决。

设I 是n*m的图像，则其垂直接缝如下：

其中，x是一个映射：[1，…，n][1，…m]，接缝路径s，即垂直接缝是图像中的

像素从顶部到底部的8-连通路径，在图像的每一行中包含一个且只有一个像素，类似的，y也是一个映射：[1，…，m][1，…n]，它是横向接缝，如图5所示。

定义接缝路径s的像素为[Is]，则对于垂直接缝，[Is={I（si）}ni=1={（i，I（si））}ni=1]。

给定能量函数e，我们定义接缝的能量值为[E（s）=E（Is）=i=1ne（I（si））]，寻找最优接缝[s*]，即寻找能量值能小的接缝。[s*=minsE（s）=minsi=1ne（I（si））]。

最优接缝可由动态规划的方法得到，每一步从第二行到最后一行遍历图像。

设接缝的最小能量之和为M，则[M（i，j） = e（i，j） + max （ M（i-1，j-1） ， M（i-1，j） ， M（i-1，j+1） ）]

当此过程结束时，最后一行的最小值M即为垂直接缝的最小能量值，我们可以从这个最小值进行回溯，找到最优接缝的路径。

如图6右图所示，红色箭头表示垂直最优接缝路径，横向接缝类似。此时，可以通过删除或插入最后接缝来缩放图像，保持图像的真实性。

3 结论

本文的主要内容是动态规划的思想及其应用。利用动态规划可以解决贪心、搜索等等无法求解的复杂的问题。通过将问题分解成多个阶段，每个阶段作出正确的决策，从而找到全局的最优解。在图像缩放这一应用中，利用动态规划找到最优接缝，节省了时间，提高解决问题的效率。放眼未来，动态规划的应用范围必然会越来越广泛。

参考文献：

[1] Shai Avidan ，Ariel Shamir.Seam Carving for Content-Aware Image Resizing[J].ACM Trans on Graphics，2007，27（3）：10-18.

[2] 强勇，焦李成，保铮.动态规划算法进行弱目标检测的机理研究[J].电子与信息学报，2003（6）.

[3] 刘攀，郭生练等.求解水库优化调度问题的动态规划-遗传算法[A].武汉大学学报：工学版，2007，40（5）.

[4] 秦裕瑗.Bellman最优性原理――论动态规划[I].应用数学， 1994（3）.

[5] 张辰.动态规划的特点及其应用.I0I2000集训队，2000.