碎紙機產生的規則條狀碎片拼接，屬於**文檔圖像拼接**領域的經典問題，廣泛應用於司法鑒定、檔案修復、情報分析。本文梳理技術路線與核心難點。
問題分類與建模
| 切割模式 | 碎片特徵 | 拼接維度 | 核心難點 |
|---|
| 僅縱切 (條狀) | 寬度固定、高度等於頁高、邊緣平滑 | 1D 排序 (左右鄰域) | 文本行跨碎片連續性斷裂、字體/字符重複導致歧義 |
| 縱切 + 橫切 (碎屑) | 矩形小塊、邊緣齒狀/平滑、數量級增長 | 2D 拼圖 (四向鄰域) | 組合爆炸 (N!)、邊緣特徵微弱、旋轉/翻轉不確定、缺片/雜片 |
| 雙面打印 | 正反面文本重疊、透光干擾 | 2.5D (需分離正反面) | 正反面關聯、透光文本去除、雙面對齊 |
主流算法流程
- 預處理： 二值化、去噪、傾斜校正、碎片分割分離、邊緣增強 (Canny/Sobel)。
- 特徵提取：
- **幾何特徵：** 邊緣輪廓、角點、撕裂紋理 (僅手撕非碎紙機)。
- **文本特徵：** 字符/詞邊界投影剖面、行間距、字體簇、顏色直方圖。
- **深度特徵：** CNN 提取邊緣/文本語義嵌入 (Siamese Network 學習相似度)。
- 相似度計算： 邊緣互補度 (SSD/NCC)、文本連續性語言模型得分、深度嵌入餘弦相似度。
- 優化搜索：
- 1D：貪心鏈式拼接、動態規劃、TSP 求解器 (Concorde)。
- 2D：圖匹配 (鄰域圖)、拼圖求解器 (PaqPuzzle)、遺傳算法/模擬退火、Z3 SMT 求解器。
- 後處理驗證： OCR 識別拼接結果評分、人工複核關鍵斷點。
工具鏈推薦
- 開源庫： OpenCV (圖像處理)、Tesseract (OCR)、PyTorch/TensorFlow (深度模型)、NetworkX (圖優化)。
- 專用軟體： Unshredder (商業)、Document Reconstruction Toolkit (DRT) (學術)、PaqPuzzle (拼圖求解)。
- 數據集： DARPA Shredder Challenge 數據、NIST SD27、自製碎片生成器 (Python + imgaug)。
人工干預節點設計
- 預處理階段： 參數調優 (二值化閾值、去噪強度) — 專家經驗決定。
- 歧義消解： 算法輸出 Top-K 候選鄰域，專家選擇正確匹配 — 關鍵斷點。
- 最終驗收： 全頁 OCR 閱讀驗證邏輯通順 — 質量把關。
前沿趨勢
- **Transformer 視覺模型** 建模長距離文本依賴，解決字體重複導致的局部最優陷阱。
- **圖神經網絡 (GNN)** 編碼碎片拓撲結構，端到端學習拼接策略。
- **少樣本/零樣本學習** 適應未見字體/版面佈局。
碎紙片拼接本質是**約束滿足問題 (CSP)**，純算法難以達到 100% 自動化，**人機協作 (Human-in-the-loop)** 是工程落地常態。競賽題目 (如全國大學生數學建模) 禁止賽期外部求助，請遵守學術誠信，獨立完成建模論文。
