2013年國賽B題講評.ppt

2014年數(shù)學建模競賽湖南賽區(qū)研討會,2013B題“碎紙片拼接復原”評論,題 目,B題 碎紙片的拼接復原 破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復原效率。請討論以下問題： 1. 對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果以圖片形式及表格形式表達。,題 目,2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果表達要求同上。 3. 上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設計相應的碎紙片拼接復原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復原結(jié)果，結(jié)果表達要求同上。,目 錄,命題背景 解題思路 評閱要點 存在問題 幾點評價,命 題 背 景,有實際應用 難度適中 參考文獻少 一篇參考文獻：Reconstruction of shredded document based on image feature matching,解 題 思 路,總體思路 三步走：分行，行內(nèi)排序，行間排序 其他做法有： 全局生長算法 ：技術(shù)含量低，出錯概率大。 鄰近生長算法：同上,解 題 思 路,第一步：分行 行距信息 ：普遍做法，精度略差（尤其是英文），大約是80%左右，技術(shù)含量不足。 聚類算法：主流算法，技術(shù)含量較高，效果好。,圖1：英文文本行特征像素行和,解 題 思 路,第一步：分行聚類算法 計算Ai 的行和，得到180維向量ri。定義合適的向量相似度，對ri（i = 1;2;: : ; n）進行相似度計算，然后對所有碎片進行聚類，從而得到分行結(jié)果。,解 題 思 路,第一步：分行聚類算法 幾種相似性度量 歐氏距離倒數(shù)： 夾角余弦： 相關(guān)系數(shù)：,解 題 思 路,第一步：分行聚類算法,解 題 思 路,第一步：分行規(guī)劃算法 假設每一組最左邊一塊可以識別出來，記為 ，其他198塊碎片記為 ，相似度記為 ，則可以求解以下0-1線性規(guī)劃求得分組結(jié)果： s.t.,解 題 思 路,第二步：行內(nèi)排序距離定義 歐氏距離 夾角余弦 相關(guān)系數(shù),解 題 思 路,第二步：行內(nèi)排序距離定義 考慮斜率的距離： 考慮像素陣列分布的距離：,解 題 思 路,第二步：行內(nèi)排序排序算法 貪心算法1：從左到右逐步拼接 貪心算法2：從右到左逐步拼接 貪心算法3：所有鄰接距離中最小的兩片拼接 圖論+規(guī)劃方法：按鄰接距離定義有向權(quán)圖，將最佳排序問題轉(zhuǎn)化為TSP問題，再應用規(guī)劃軟件求解。,解 題 思 路,第二步：行內(nèi)排序排序算法 規(guī)劃方法：定義兩碎片i，j之間邊緣（有向）距離為rij，并規(guī)定ri0=r18，j=，求解以下規(guī)劃模型： 如果求解結(jié)果無子回路，則得到問題最優(yōu)解。,解 題 思 路,第二步：行內(nèi)排序排序算法 第三問雙面規(guī)劃方法： 如果求解結(jié)果無子回路，則得到問題最優(yōu)解。,解 題 思 路,第二步：行內(nèi)排序排序算法結(jié)果,說明：假設分行完全正確；括號中的數(shù)字是沒有完全復原的行數(shù)。,解 題 思 路,第三步：行間排序 根據(jù)行距排序，或者根據(jù)內(nèi)容排序。,評 閱 要 點,1. 看思路：是否有全局最優(yōu)的思想。 2. 看特征信息：分行時是否用到所有像素點信息？是否用到文字結(jié)構(gòu)信息？是否考慮多種信息，并從比較中選取合適信息？ 3. 看算法：看算法與模型是否一致，看算法描述。 4. 看人工干預：干預方式及干預時間節(jié)點是否明確表述？,評 閱 要 點,存 在 問 題,直觀想法建模比例之高超乎意料。 過于依賴人工拼接。 特征信息發(fā)掘不深、不廣。 計算能力不強。 模型、算法、程序、結(jié)果脫節(jié)，甚至有造假現(xiàn)象。 最普遍的缺陷是模型檢驗嚴重不足。,幾 點 評 價,過于重視結(jié)果的痼疾在競賽論文中充分暴露，在題目中直接給出結(jié)果也許能啟發(fā)學生更關(guān)注模型。 模型檢驗是建模過程的必要環(huán)節(jié)，甚至是重要環(huán)節(jié)，從此次論文來看，這還是一個較薄弱