2011美赛重庆大学特等奖题名论文

2014 Mathematical Contest in Modeling (MCM) Summary Sheet

Team Control Number

For office use only

T1 ________________

T2 ________________

T3 ________________

T4 ________________ 201401 Problem Chosen For office use only F1 ________________ F2 ________________ F3 ________________

F4 ________________ B

Summary

As is known to all, splicing of paper scraps is a complex issue, which exerts a important role in judicial evidence recovery, restoration of historical documents and access to military intelligence. This paper focuses on splicing problem of paper scraps, establishing shredding distance model and restoration TSP model.At same time,we design one-dimensional and multi-dimensional pieces restoration algorithm and then solves it by using MATLAB.

For question one, we extract information from the Appendix 1 and 2,designing to recover the one-dimensional shredding algorithms,which is characterized by a text character size, line spacing structure. And then we can transfor the shredding problem into recovery TSP problem, thus obtaining the correct recovery graphics and sequences.

For question two, we firstly standardize shredding pictures from the Appendix 1 and 2, and then extract the normalized image-level features. For that pictures can not be classified via machine,we use the developed programs of GUI to improve the efficiency of labor.

For question three, three-dimensional design shredding restoration algorithm, a first surface and the surface of Annex 5 b integrate pictures, get 416 pieces of shredding pictures, the picture also standardized level feature extraction, classification and other operations, will reduced dimensions of the one-dimensional problem and solved to obtain the correct recovery images and sequences of positive and negative Annex 5. Taking into account the problem of quantitative evaluation algorithm, this paper presents minimal intervention model to improve the algorithm in place, that is, through the computer to recognize the order and sequence in reverse order to recover the number of manual intervention to achieve a minimum number of advantages and disadvantages of the algorithm is portrayed.

Keywords:Reconstruct documents；TSP ；Shredding Distance Model；Shredding Restoration Algorithm

Content

I Introduction ............................................................................................................... 2

II Symbol Definitions ................................................................................................... 2

III Assumptions and Notations ................................................................................... 2

Ⅳ For question one ..................................................................................................... 3

4.1 Image Preprocessing .......................................................................................... 3

4.2 Shredding Feature Extraction ........................................................................ 3

4.3 Recognition Sequence Based on Text Features .......................................... 4

4.4 The Definition of Shredding Distance ........................................................ 5

4.5 Recovery of TSP .................................................................................................. 5

4.6 Simulate Anneal(SA) Algorithm ...................................................................... 5

4.7 One-Dimensional Shredding Restoration Algorithm .................................. 6

4.8 The Solution of Model ...................................................................................... 6

Ⅴ For question two ..................................................................................................... 7

5.1 Shredding Standardization And Level Feature Extraction ..................... 7

5.2 The Classification of Level Feature ......................................................... 8

5.3 Two—Dimensional Shredding Restoration Algorithm ................................ 8

5.4 The Solution of Model ...................................................................................... 9

Ⅵ For question three ................................................................................................ 10

6.1 Dimensionality Reduction .............................................................................. 10

6.2 Three—Dimensional Shredding Restoration Algorithm ........................... 11

6.3 The Solution of Model .................................................................................... 11

Ⅶ Strengths and Weaknesses ................................................................................... 12

7.1 Strengths ............................................................................................................ 12

7.2 Weaknesses .......................................................................................................... 12

Ⅷ The Refinement of our Model ............................................................................. 13

8.1 Improved Apply for Colorful Images .......................................................... 13

8.2 Minimal Intervention Degree Algorithm .................................................... 13

Reference..................................................................................................................... 13

AppendixⅠ ................................................................................................................. 15

AppendixⅡ ............................................................................................................... 16

AppendixⅢ .............................................................................. …… 此处隐藏：20305字，全部文档内容请下载后查看。喜欢就下载吧 ……