2013年國(guó)賽B題講評(píng).ppt

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