果壳有意思
  • 注册
  • 下载客户端
  • 手机扫码下载
    全新果壳APP
925
需用时 01:51
24
81
碎纸复原,真的能做到!
/gkimage/jj/ch/tl/jjchtl.png

今年10月29日,美国国防部高级研究计划局(DARPA)宣布了一场碎纸复原挑战赛(Shredder Challenge),旨在寻找到高效有效的算法,对碎纸机处理后的碎纸屑进行复原。

据DARPA称,军方常常在战场上收集到撕碎的文件残片,恢复文件原样是一件望而生畏的艰巨任务,需要大量人手,进程十分缓慢。而有价值重要情报通常都是有时限的,过一段时间就会变得不值一文。目前学术界关于残片复原(reconstructing shredded documents)的问题有多种研究策略,全人工不可能,全自动也不可能,所以,主流解决方案是结合类似于拼图游戏的手工复原方法和进行匹配和搜寻的计算机算法。DARPA开启这场比赛的目的在于,一方面召集到计算机科学家、解谜爱好者或任何有天分的人,另一方面也能为寻找到最佳解决方案投石问路。同时,获胜者会获得50000美元的奖励。

其比赛规则设置得也很有意思。为了测试算法的有效性,赛事组委会挑选了五道智力题,写在五张纸上,再将这些纸分别投入碎纸机,形成碎片。参赛队伍不仅需要将这些纸张复原至能准确阅读其上的题目,还要做出正确的回答,才能获得相应的分数。根据纸张大小、破碎程度包括题目难度等因素,五道题目设置了不同的分数。

这注定是一场高智商人群的挑战赛,吸引了全美9000支参赛队伍参与角逐。令人始料未及的是,预计在12月5日结束的比赛,提前两天便落下了帷幕,其原因是,宣布获胜的队伍领先优势太过明显,赛事已无悬念。

这支参赛队伍的名字叫做“All Your Shreds Are Belong To U.S.”,由三名来自旧金山的程序员组成。其实这三个人的来头都不小,编写了iPhone上著名图片文字翻译软件WordLens的奥塔威奥·古德,长期专注于手机软件开发的卢克·阿朗索,和在洛克希德·马丁(航空航天军工企业)工作的肯思·沃克。

其解决方案是这样的。首先,该队伍设计出算法,基于纸张碎片的边缘性状等特征,能够自动搜寻到最可能匹配的纸张碎片对。接着,这三人号召众亲朋好友对这些可能的碎片对进行人工筛选。夜以继日的奋战之后,拼凑出了最后的结果。古德介绍说:“我们的算法基于计算机视觉、图形学,并且结合了传统的仿真软件,才能达到高效和有效。”

在被问及这个解决方法是否能够投入军方使用时,古德坚定地回答说:“当然不行!赛事提供的模拟问题要简单许多,每张纸的碎片都被分开了。而实际情况中,要面对的是被碎成一大箱碎片的一沓文件,所以实际问题要复杂的很多。所以,我们只是全力以赴赢了一场比赛,不必有人担心碎纸机的保密性。”

/gkimage/1x/8n/16/1x8n16.png/gkimage/tz/po/xd/tzpoxd.png/gkimage/km/9i/dd/km9idd.png/gkimage/4l/rk/44/4lrk44.png/gkimage/ii/il/io/iiilio.png

以上就是这五道题的原图和复原后的图,其中第五道题有三幅图,只取了第一幅

查看清晰大图可以点这个 PDF

另外别忘了,其实它们还是智力题,有兴趣的同学可以解一解。


图片和信息来源: newscientist & darpa

The End

发布于2011-12-09, 本文版权属于果壳网(guokr.com),禁止转载。如有需要,请联系果壳

我的评论

唯一

数字图像处理博士

pic