主题：【原创】‘缝刻’ -- 卷心菜
很多人都有用电脑处理图片的经历。当我们要改变一张图片的大小时，通常有两种选择，一种是Scaling，将图片内容按指定的长宽比例压缩/放大，另一种是Cropping，裁切图片中的一部份，保持图中物件大小不变。下面我作个简单示范：
原图
Scaling
Cropping
好吧，上面的太简单了。让我们再来看看这幅图：
看出点什么了吗？这是PS作品？变形工具与人工剪贴的结果？另一张不同角度的照片？
都不是。
答案在这里：
2007年10月，芝加哥AdobeMAX会场
[FLASH]http://www.youtube.com/v/eGR-x9LX9XA&rel=0[/FLASH]
上面这段视频中演示的算法叫做Seam Carving，直译成中文就是‘缝刻’，由Shai Avidan与Ariel Shamir共同发表。它的原理在于找出图片中由单个‘背景像素’连接而成的一条条裂缝并加以填充或删除，以此达成改变图片大小的效果。这种效果有时被称为Retargeting，既能保持图中物件的比例与完整性，又可容许使用者自由改变图片大小与长宽比。
下面这个视频的解释更生动一些：
[FLASH]http://www.youtube.com/v/vIFCV2spKtg&rel=0[/FLASH]
Seam Carving的核心算法虽然只有二十行，却在一定程度上实现了对主体与背景的的分辨，因此它同样擅于不留痕地移除图片中的主体物件。在实践中，图片背景越是干净，越是由无固定形态的物体组成（如白云、土地、水面），缝刻的运算效果就越好；若是在复杂、对比度高而且规则的背景下（如都市），处理过的照片就容易被看出破绽来。
上面视频演示中使用的程序并没有公开，但算法是在他们论文里公开的，现在已有一些现成工具可用了。GIMP里有个叫做Liquid Rescale的插件是其一。不用GIMP的话，还有一些独立的程序可选，Liquid Resize是其中功能比较完善的一个，有Windows和Linux版本：
http://www.thegedanken.com/retarget/default.asp?lnk=3
试试看吧，在一些特定情况下真的很好用。
真是又前沿又通俗易懂的学术帖啊
也许西西河的截图比风景照片更能直观地体现‘缝刻’的效果。
(请点击图片看原图)
原图：
Resize:
Retarget:
恭喜：你意外获得【西西河通宝】一枚
鲜花已经成功送出。
此次送花为【有效送花赞扬，涨乐善、声望】
自动的对象提取可以有许多算法，edge detection比较多见。也可以用户干预。
前景物件大多有清晰的边界与特定的比例，只要边缘探测算法稍微有些不准确，对其进行缩放或移动就很容易被看出来，破坏图片观感，因此这种技术不易应用。
对背景中颜色变化最小处做手脚却完全不同，那是人们注意力最容易忽略的地方，因此被改过的图片看起来往往还是十分自然，没有修改的痕迹。
这种算法也可以说是edge detection的反面应用---它探测与改变的就是‘最没有edge’的地方。
比如背景是均匀的色阶渐变的情况，前景是等距条纹的情况
最想看到的是对像素舍弃规则的直观表现
比如主贴里的碧海蓝天滑翔机，继续缩的话，会不会出现岛屿上缘突破水天界限的情况？
我推荐的那个软件2MB而已，还有其他更小的（功能少些）。
如果seam只是取梯度的最小值，而不需要连续的话，似乎算法很简单。