技术宅拯救世界

@ 五月 7, 2012

原文首发于《兵马俑BBS》,感谢各位技术强人的原创分享!】

背景新闻:5月3日清晨6点,四川成都市民林兆强抱着5万百元钞碎片,从成都金堂赶到中国银行四川省分行,寻求帮助。5月1日,林兆强妻子突然发病,将5万元救命钱撕成碎片。面对数千块钞票碎片,12名银行工作人员分拣、拼接了6小时,才艰难拼出一张百元钞票。剩下的钱一旦拼接不出来,就面临作废的无奈。因为这笔钱是准备用来给妻子治精神病的,林兆强表示不会放弃。

这一新闻在交大BBS上引起一阵“学术讨论”潮,交大的技术宅们动用科学知识,试图解决这类大规模组合求解问题。下面是部分同学们的精彩讨论:

wangsong:我先抛砖引玉,个人觉得应该首先将完整纸币分成8个(或者其他)小格,然后将碎片编号,并根据每块碎片的大小和在纸币中所占“大致”位置判断所占的小格。如果某一格被大部分占据(只能估计,病人没有这么精准的撕纸手法),那么这一格的状态记为“1”,没有被占的格子状态即为“0”。

因此,每一片具有固定编号的碎片都可以用一个八位的二进制数进行表示,最后通过编程进行循环试凑,找到能凑齐八位”1“的组合,那么这几张碎片就可以组成一张完整纸币了。

该方法太过理想化具有一些漏洞:

  1. 计算量太大,可能应该首先进行分类,然后分别计算求解。
  2. 编码全靠人眼识别判断,具有一定的模糊性。
  3. 不一定非得凑够100%完整纸币,凑够80%就差不多了。这样应该能降低计算复杂度。

碎钞

cdnicc|:白背景,正面平铺拍照,用图像处理软件拼一下应该可以吧?

linglanluo:数字图像处理课的一些东西或许能用上。

解决方案如下:题设的5万元有4000个碎片,编号为1到4000号。分为10组,每组400个,按照20×20摆放。用相机给每组碎片拍照,背景最好为纯色,这样便于处理。然后进行图像分割、标记(分割标记课本上都有很多现成的算法),然后对每个标记的碎片计算出边界,通过对这4000个碎片进行边界拟合并计算误差,误差最小的那几个就可以认为是同一张纸币上的了。

可能有几个碎片轮廓比较像的会算错,但是如果计算机算出来的误差相近的话,人眼应该也看不出来,银行会给换的。还有,上述算法肯定会用到很多迭代算法,计算量估计会很大,个人电脑估计得算几天,交大很多实验室都有大型机,借用一下下,一会会就算出来了。

chengjun:将所有残片编号扫描进入电脑,然后通过专业的程序系统自动配对识别,就可以了。

wwww:我的想法是,首先对这一堆残片进行分堆处理,也就是按照残片所在的位置分为8堆,然后再利用图像处理技术进行拼接,即相邻位置的可以拼接,其他位置不可拼接,这样这样上下两堆可以拼成一堆,得到4堆,再由四堆进行拼接,得到两堆,最后拼接完成,我觉得这样可以大大减小误差和拼接所需的时间。

xiaochisheng:找个挨踢公司,捐五万,然后买下这堆碎片,扫成图片,作为人工智能算法的挑战题。如果谁有好的方法解决,再奖励五万,产生的算法的价值,以及给企业带来的效能应该大于五万。

各位技术宅,你有什么好办法吗?

[课外阅读]果壳网:碎纸复原,真的能做到!

《技术宅拯救世界》二维码网址相关阅读
无法控制的删除
都学到屁眼里去了
一起来做五毛党
挑颗扣子做胸针


7个 群众围观在“技术宅拯救世界”旁边

  1. CCTV 说:

    我认为xiaochisheng的最后一个建议很靠谱,更有意义

  2. 匿名 说:

    买过来弄个挑战杯题目吧

  3. lycoo 说:

    1、验证所有碎片都是真币(如果需要的话,这个应该是所有方法必须做的)
    2、找一块足够大的场地
    3、拼成一个尽量不重叠,缝隙最小的正方形,算出面积,除以一张面额的纸币面积,所得即为实际百元钞票数量

  4. Daisy 说:

    一张新100元纸钞的重量是1克,称一下碎钞的重量可以估出大概的张数。但是这种方法不能把所有碎钞全拼起来,最后的结果可能还是作废。只是路过的,不要拍砖啊~

  5. lilan 说:

    抛砖:
    1,假设每张被撕成4片;
    2,毛主席向上,从左边完整部分由窄向宽排列,然后取第二部分向上凑,
    3,为了提到效率,建议每片先扫描编号。
    其程序就和电脑比对指纹一样。指纹比对也是细分X,Y轴,再按小格对比。

  6. a.o.e 说:

    牛人呐

  7. ant 说:

    这个讨论不错,也可以给相关人提供实在的帮助,如果有公司能考虑xiaochisheng的建议,趁此机会顺便做个小广告估计很不错的,呵呵。

    个人想法,需要每张碎片进行编号,同时进行拍照,方向垂直纸币,全部采用正面,然后将其图像抠出,放入一个百元纸币大小的模板中定位,这样得到全部碎片的数字图,包含了碎片的边界,位置,所占的区域,模板需事先用一个百元钞得到,这样估计要得到5000个以上各不相同的图像。接下来,可以用人工依次对每个图像进行比对,当有边界吻合的情况即可将其编号定位在同一张钞票。也可以用程序进行处理,不过那又需要时间人力来做,又要花时间。总之,工作量还是很大。但相信可以完成,希望这位兄弟好运。

    刚才又看了链接里的介绍有一句让人绝望的话:在被手撕掉的钱中,最大碎条也只有打火机那么大,被剪刀剪过的钞票更让人绝望,大部分碎片比泡过的茶叶还小。 神啊…

注意:评论也是“话语权”,请用好每个行使权利的机会。

为防止“网评员”污染,您需要获得帐户注册邀请之后方可留言。