如果這是拼圖你有什麼辦法快速拼好?

12-26

5月3日清晨6點，四川成都市民林兆強抱著5萬元百元鈔碎片，從成都金堂趕到中國銀行四川省分行，尋求幫助。5月1日，林兆強妻子突然發病，將5萬元救命錢撕成碎片。面對數千塊鈔票碎片，12名銀行工作人員分揀、拼接了6小時，才艱難拼出一張百元鈔票。剩下的錢一旦拼接不出來，就面臨作廢的無奈。因為這筆錢是準備用來給妻子治精神病的，林兆強表示不會放棄。

新聞鏈接:http://news.163.com/photoview/00AP0001/23170.html#p=80MF0I7700AP0001

技術宅們,拼圖一定有技巧的吧,你有什麼演算法能最快速度搞定.

如果能確定鈔票碎片沒有假幣，並且都為百元鈔的話，如果銀行肯變通，完全可以通過稱重的方式來驗證是不是共5萬元，換成等額新紙幣就可以了。

下面說拼圖思路：
1.先把碎片根據圖案讓同一面朝上，
2.編號，順序歸檔
3.掃描入電腦
4.根據碎片圖案確定碎片在和幣紙等大的矩形中的位置，處理成一個矩形中只有一個碎片，並把碎片處理成沒有圖案的黑色形狀塊
5.依次對齊疊加兩個帶有碎片的矩形判斷是否有一個邊拼合，這樣最終能得到一堆帶有拼合的了兩個碎片的矩形
6.用新得到的矩形反覆重複步驟5，直到得到帶有所有碎片的矩形
7.根據碎片編號把碎片實物拼合。

方法：
1) 把一個紙幣網格化，具體每個網格的大小根據碎幣來確定。
2) 根據紙幣在網格上面的位置，剪成一塊又一塊的網格；有兩種網格，一種是完整的，還有一種是不完整的。
3) 用完整的網格拼接出完整的紙幣。
4) 剩下不完整的網格繼續細化，一直迭代這個過程。

當然，這個需要用計算機+機械裝置來處理，成本不小。

找小100（一張錢上只有一個），找到幾個算幾張。如需驗證，就把所有的碎片放在一起稱重，看看是否與5萬元重量吻合。這樣銀行就可以補償很多了吧。

演算法：
第一步，類似曉野的方法，將正常紙幣網格化（例如：155*77）。
第二步，每個碎片，對應佔用的網格，轉化為數據存儲。（例如某紙片數據格式存為｛（2，3），（2，4），（3，3），（3，4）｝，就是一個2*2網格的小正方形）。按照一張紙紙幣被撕成20片，總紙片數為500*20=10000張。（只要有網格佔到，不分大小，既算覆蓋）
第三步，建模完畢，現實的問題已經轉化為一個數學問題，下面開始模擬演算法~
1，取出一個覆蓋點（1，1）的紙片，例如紙片A｛（1，1），（1，2），（1，3）...(1，j）（2，1），（2，2），（2，k），（3，4）……（33，21）），將紙片A存入棧。
2，搜索資料庫，找到某個紙片中覆蓋（1，j），但不覆蓋（1，j-1）；覆蓋（2，k）但不覆蓋（2，k-1）；覆蓋（3，l），但不覆蓋（3，l-1）……的紙片B。（即不打架的紙片）。最壞情況找到100張，但是由於網格較細，大部分情況是1，偶爾會有2或3張。將紙片B存入棧，
3，然後一次類推，尋找紙片C……
4，橫向結束後，從紙片A下一行開始。
……

演算法複雜度草估：
假設平均找下一張的時候，有2個候選結果（已經人品極差了），平均每張鈔票被撕成20片，那麼最難的第一張鈔票，運算次數=10000*（2的19次方）=5242880000次。這個數字還是可以接受的。

德國專門有拼圖的設備用來處理當年東德解體時用碎紙機銷毀的文件，不知道對這個管用不？

這個早就有電腦程序可以處理了。

前幾個月去了一次吳哥窟，那裡的廟宇殘骸以前靠人工，現在也是藉助電腦實現修復的，效率大大提高。那可是三維的啊，而且和拼人民幣不同，修復殘骸還不知道復原以後應該是什麼樣子呢。

當然估計真正的問題是我們這家銀行沒有這個程序，那就看他們是否真心愿意「為人民服務」。如果是，大家提到的稱重等方法都很靠譜。如果不是，那什麼方法都沒用。從報道看來是，我也真心希望是。

另外，不是有規定說只要殘破的人民幣大於一半就可以兌換新的嗎？何必一定要拼完整呢？

重要的一點，拼出3/4就能兌換全額了，而且3/4也能辨認真假了，所以一張一張湊3/4張就好了。

演算法：
1、把碎片理平按同一朝向拍照入庫
2、圖像匹配出每張所拍攝碎片在一張百元鈔中的位置
3、將一張百元鈔分為155*77的矩形點陣，若要精確還可細分
第五套人民幣100元尺寸155mm*77mm
參考http://zhidao.baidu.com/question/357137579.html
4、按照過半取點的規則，統計出所有碎片在所有點位中的出現次數
5、統計結果如果所有點的覆蓋頻率在500次左右，則情理上應該是5萬元無誤

演算法的誤差：
1、人民幣相對中間的點可能在統計中被忽略，因為一個像素可能被3張或以上碎片平分，則該點被忽略統計；而邊上的點相對誤差會偏小，因為不容易被多張碎片平分
2、人民幣紙張是有厚度的，因此紙張被撕碎並不是理想的2維平面分割，可能出現撕口邊緣被斜撕，撕口的紙張厚度變薄而總面積變大，此處的點被重複統計。
3、演算法（1）中理平的步驟，會產生很大誤差。

尋找帶有直角的碎片，直角數除以4就是可以估算出來。不過驗證假鈔還是很麻煩的。
按照描述，500張紙幣，以平均每張撕成6片的話總數在3000塊上下。設計一個演算法拚是可行的，就看有沒人願意幫忙了。

題外話：
儘管很悲慘，但是造成這個結果當事人也有保管不當的責任的。有問題不能老找銀行的茬。

如果是新錢，抽取部分碎片，記錄重量後，通過分析紙張，油墨的成分以及某防偽處的特徵判定真假，抽取的份額待擬。剩餘碎片稱重加上抽取碎片重量，與五萬元紙幣對比。拋磚引玉，理想狀況脫離實際。如果是5億的話這個方法認為可行，五萬可能偏差較大。