Retargeting:经典动态规划问题的一个出人意料的应用

    计算机的图片处理技术已经越来越牛B了,很多看似不可能的东西现在都已经有了比较成熟的算法,比如无锯齿放大、抠图、智能抹除等等。但你相信吗,现在竟然有这样一种算法,它可以改变图片的长宽比,同时保持画面内容的长宽比不变!
    我们经常遇到这样一个问题:源图片的长宽比与目标长宽不合,把图片剪裁一部分会觉得可惜,而拉伸图片后画面内容就变形了。此时,一种叫做Retargeting的技术或许可以帮助你:当图片长宽比改变后,它能压缩图片中不重要的部分,保持画面主体内容长宽比不变,让人看不出这个图片是被拉伸过的。
    算法的原理来自这篇名为Seam Carving for Content – Aware Image Resizing的论文,它第一次出现在今年8月份举行的SIGGRAPH大会上。下面一段视频简单地介绍了这个算法,看后你会发现其实质非常简单。

YouTube链接:http://www.youtube.com/watch?v=qadw0BRKeMk

    你会在视频中听到一个OIer特别熟悉的词。“从最上面一排的某个像素出发,每次只能向左下、右下和正下方三个方向移动,求出到达最底端的路径中权值和最小的一条”,这是每个OIer学习动态规划的必修课程,它甚至还出现在了前几天的某次NOIp模拟赛中(记得好像是第三题)。
    最近cnBeta的一篇文章提到,这个技术已经用于实践,一个叫做rsizr的Flash网站可以实现上述算法,感兴趣的同学可以去试试。

18 条评论

发表评论