Matrix67: My Blog » Blog Archive » Retargeting：经典动态规划问题的一个出人意料的应用

2007-10-14 20:23| icon3

16 Comments | 本文内容遵从CC版权协议转载请注明出自matrix67.com

    计算机的图片处理技术已经越来越牛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网站可以实现上述算法，感兴趣的同学可以去试试。

16 条回复

楼层: 沙发 | 2007-10-14 20:36 | qzben 说：
恩。看到那个“KISS”了。

您也上CB呀。
楼层: 板凳 | 2007-10-14 20:59 | yiyin 说：
不错~~
楼层: 地毯 | 2007-10-14 21:18 | 匿名龙神号说：
原来这么多人上CB啊.
楼层: 地板 | 2007-10-14 21:19 | deoxyz 说：
NB 以后可以PS和MM的KISS照片了
楼层: 地下室 | 2007-10-15 13:13 | axgle 说：
挺有意思
楼层: 地基 | 2007-10-15 18:37 | w4ppsxy 说：
太强了
楼层: 地壳 | 2007-10-15 20:02 | Kebe 说：
那么energy函数怎么定义呢？

回复：很多种定义方法，比如亮度、色相、饱和度等等
楼层: 地幔 | 2007-10-15 20:23 | Ben.MQ 说：
NB 以后可以PS和MM的KISS照片了

这是如此之现实～

另外。今天下午MATRIX67.COM怎么又挂了。。。难道我RP问题？五天三挂

回复：10月15日是一个非常和谐的日子
楼层: 地核 | 2007-10-15 23:38 | Ai.Freedom 说：
pdf下不下来啊..
楼层: 10楼 | 2007-10-16 12:43 | ConcreteVitamin 说：
话说是不是改 CSS 了?
字体突然变小了,不舒服,FireFox 浏览
楼层: 11楼 | 2007-10-16 12:44 | ConcreteVitamin 说：
靠...原来是自己不小心滚轮了 >.<
楼层: 12楼 | 2007-10-16 19:54 | arthas 说：
小人愚钝，没看出来怎么处理的
楼层: 12a楼 | 2007-10-16 20:28 | SubRaY 说：
这是每个OIer学习动态规划的必修课程，它甚至还出现在了前几天的某次NOIp模拟赛中（记得好像是第三题）。

难道指的是我的..

回复：正是
楼层: 14楼 | 2007-11-03 13:12 | fearlessxjdx 说：
太牛B了。。。
楼层: 15楼 | 2008-01-07 2:57 | ziliang 说：
很无敌啊...
楼层: 16楼 | 2008-07-16 2:55 | 逆铭说：
http://www.intuimage.com/
离线版的……

16 条回复

您也随便说几句吧：

Category

Subscribe

Control Panel

Random Articles

Recent Comments

Search

Blogroll

Support