这是我在掘金翻译计划中的译文。 译文链接:[译] 动态规划算法的实际应用:接缝裁剪
我们一直认为动态规划(dynamic programming)是一个在学校里学习的技术,并且只是用来通过软件公司的面试。实际上,这是因为大多数的开发者不会经常处理需要用到动态规划的问题。本质上,动态规划可以高效求解那些可以分解为高度重复子问题的问题,因此在很多场景下是很有用的。
在这篇文章中,我将会仔细分析动态规划的一个有趣的实际应用:接缝裁剪(seam carving)。Avidan 和 Shamir 的这篇文章 Seam Carving for Content-Aware Image Resizing 中详细讨论了这个问题以及提出的技术(搜索文章的标题可以免费获取)。
这篇文章是动态规划的系列文章中的一篇。如果你还不了解动态规划技术,请参阅我写的动态规划的图形化介绍。
环境敏感的图片大小调整
为了用动态规划解决实际问题,我们需要将问题建模为可以应用动态规划的形式。本节介绍了这个问题的必要的准备工作。
论文的原作者介绍了一种在智能考虑图片内容的情况下改变图片的宽度或高度的方法,叫做环境敏感的图片大小调整(content-aware image resizing)。后面会介绍论文的细节,但这里先做一个概述。假设你想调整下面这个冲浪者图片的大小。
论文中详细讨论了,有多种方法可以减少图片的宽度。我们最先想到的是裁剪和缩放,以及它们相关的缺点。删除图片中部的几列像素也是一种方法,但你也可以想象得到,这样会在图片中留下一条可见的分割线,左右的内容无法对齐。而且即使是这些方法全用上了,也只能删掉这么点图片: