I have always been reluctant to participate in mathematical competitions. The main reason is that I prefer to think deeply and continuously about a problem without being constrained by the time limits of a competition. I am not a particularly quick-witted person, so it is difficult for me to have the "flash of inspiration" required for such contests. About a week ago, the preliminary round of the National Mathematical Modeling Competition began. I followed it with interest and noticed Problem B, an intriguing topic: Shredded Paper Reconstruction. I then began to think about algorithms. It was around noon on September 13th when I started my "one-person mathematical modeling." By "one person," I don’t mean that I formed a team by myself, but rather that I was freely and efficiently conceiving algorithms and exploring code on my own. Not for the competition, but simply to achieve the goal. That excitement lasted until three o’clock the next morning.
In my mind, a perfect problem is one that is challenging yet has a very easy-to-understand premise. Problem B is undoubtedly such a case. Its requirement is as simple as it gets: take a piece of paper, tear it into tiny fragments, and then ask you to restore it. Of course, the modeling problem included significant simplifications; the fragments were all ideal rectangles. This greatly reduced the difficulty, as we otherwise would have had to obtain the shapes of the fragments, which would be much harder. For those who need a detailed understanding of the problem, please refer to the attachments of this article.
My initial idea was to use an OCR system to convert the text on the fragments into an editable text format, but I soon realized this was unlikely to work because many characters were cut into pieces. Then I thought that if characters are cut, the edges of the fragments should match. Based on this, one can determine which two fragments are adjacent. In fact, the overall algorithm is just that: comparing the edges of the fragments. However, translating this idea into code is a long journey. First, there is the issue of how to obtain edge information. The best way, of course, is to convert the images into matrices. At that time, I had never encountered anything similar. I searched extensively on the internet, initially planning to use C++, but later found that using Matlab was more direct. Matlab reads images and converts them directly into matrices, which is very convenient. Once this problem was solved, the rest was essentially straightforward, involving just some loops and conditional statements. My program is also included in the attachments.
One thing that left a deep impression on me was that from 12:00 PM on the 13th to 3:00 AM on the 14th, I started from knowing absolutely nothing about image matrix processing and, through constant searching on Google and Baidu, finally managed to write a rough program. This period also included two of my PE classes. (At that time, I had just reinstalled my system and my bookmarks were empty, but by the time I finished the program, the bookmarks were full.) Therefore, I feel that Problem B was probably the simplest problem in this mathematical modeling competition. I don’t understand why none of my classmates chose Problem B...?? (Keep in mind, not knowing how to code is not the main issue; one can definitely learn the necessary code within a day or two. The key is the algorithm...)
I finished writing the code completely at 3:00 AM the next day and quickly went to sleep. The next morning, I was busy with club activities and only had time to tinker with it again at noon. Later, I discussed it with Zimou and found that he was also working on Problem B. We talked about the reconstruction of Attachment 3 and Attachment 4. In fact, I had only completed the reconstruction of Attachment 1 and Attachment 2 the previous night. Those cases were relatively simple because the original paper was only cut vertically into rectangular strips. Attachment 3 and Attachment 4, however, involved cutting the paper into smaller rectangles, which increased the difficulty of judgment and required more manual intervention. For a while, I couldn’t think of a good solution. I spent some time on it that evening but still didn’t achieve particularly good results.
Another day passed, and Zimou said he had finished Attachment 3. Indeed, pressure provides motivation; I really admire him! I quickly asked him about his approach. It was a truly brilliant idea—I knew manual intervention was needed, but I didn’t know where to apply it—he told me that one could manually identify the first column and then perform matching for the rest! Thus, for me, this problem concluded there. This experience sparked another interest in me: OCR recognition systems. I am wondering how converting text on images into editable text (such as Word) is implemented. I have also conceived an algorithm for it, but found it to be very complex. Using Matlab definitely won’t work (Netizens commented that Matlab’s loops are very slow). I will study more C++ in the future and see if I can do something in this area.
Regarding shredded paper reconstruction, there is also a more advanced competition abroad. Interested friends can follow:
"Shredded Paper Reconstruction, It Can Really Be Done!"
This competition is much more difficult!
The program is rather ugly and does not have many comments; experts, please ignore it
Attachment: 2013 Mathematical Modeling B.zip
When reposting, please include the address of this article: https://kexue.fm/archives/2067
For more detailed reposting matters, please refer to: Scientific Space FAQ