One-Man Mathematical Modeling: Shredded Paper Reconstruction
suizhiji
I've never had much enthusiasm for participating in math competitions, mainly because I like to think deeply and continuously about a problem, without being constrained by competition time limits. I'm not a particularly quick-witted person, so it's hard for me to produce the "flash of insight" that competitions demand. About a week or so ago, the preliminary round of the National Undergraduate Mathematical Contest in Modeling began, and I followed it with some interest. I noticed that Problem B—an interesting problem about shredded paper reconstruction—caught my attention, and I started thinking about the algorithm. It must have been around noon on September 13th when I began my one-man modeling effort. By "one man," I don't mean that I alone formed a team; rather, I mean that I was freely and efficiently developing the algorithm and exploring the code all by myself—not for the sake of competing, but simply to reach the goal. That excitement lasted until three in the morning that night.more
To me, the perfect problem is one that is difficult, yet whose meaning is easy to grasp. Problem B was undoubtedly this kind of problem—its requirements couldn't be simpler: you take a piece of paper, shred it into small pieces, and then you're asked to reconstruct it. Of course, the modeling problem simplified things considerably by assuming the fragments were ideal rectangles, which greatly reduced the difficulty; otherwise we'd also have to extract the shapes of the fragments, which would be quite hard. Anyone wanting the full problem statement can refer to the attachment in this post.
My initial idea was to use an OCR system to convert the text on the fragments into editable text, but then I realized this probably wouldn't work, since many characters would have been cut apart. Then it occurred to me that if a character gets sliced across fragments, the edges of the fragments should match—and this could be used to determine which two fragments are adjacent. In fact, the whole algorithm boils down to just that: comparing the edges of the fragments. But turning this idea into code was still a long road. The first issue was how to extract edge information. The best approach, of course, was to convert the image into a matrix, but I had no prior experience with anything like this, so I cast a wide net searching online. I initially planned to use C++, but later found that Matlab was more straightforward—Matlab reads an image directly as a matrix, which is very convenient. Once that problem was solved, everything else was basically not difficult—just writing some loops and conditionals. My program is also included in the attachment.
One thing that struck me deeply: from noon on the 13th to 3 a.m. on the 14th, I went from knowing absolutely nothing about image-matrix processing to roughly finishing the program, all through constant Googling and Baidu-ing—interspersed with my two PE classes along the way. (I had just reinstalled my OS at the time, so my bookmarks folder was empty; but by the time I finished the program, it was already full.) Because of this, I feel that Problem B was probably the easiest problem in this year's contest. So I really can't understand why none of my classmates around me chose Problem B... ?? (You should know, not knowing how to code isn't the main obstacle—you can absolutely learn the necessary coding skills within a day or two; the key is the algorithm...)
I finished writing the complete code at around 3 a.m. the next day, and hurried off to sleep. The following day I had club activities to attend to in the morning, and only had time to keep tinkering at noon. Later I discussed it with Ziemou and found that he was also working on Problem B. We talked about the reconstruction of Attachments 3 and 4. In fact, the previous night I had only finished reconstructing Attachments 1 and 2, which were relatively simple, since the original sheet had only been cut vertically into rectangular strips; Attachments 3 and 4, however, had the paper cut into smaller rectangles, which made the matching much harder and required more manual intervention. For a while I couldn't think of a good approach; I fiddled with it again that evening but still didn't get particularly good results.
Another day passed, and Ziemou said he had cracked Attachment 3. Sure enough, pressure breeds motivation—I really admire him! So I quickly asked him about his approach. It was truly a clever idea—I knew manual intervention was needed, but I didn't know where to apply it—he told me you could manually identify the first column, and then do the matching for the rest! And with that, as far as I was concerned, this problem was resolved. This experience sparked another interest of mine—OCR recognition systems. I started wondering how converting text in images into editable text (like in Word) is actually implemented, and sketched out an algorithm in my head, only to find it quite complex—Matlab definitely wouldn't cut it (that night I concluded that Matlab's loops are too slow). Perhaps it's time to learn more C++ and see whether I can accomplish something in this area.
Regarding shredded paper reconstruction, there's also a more advanced competition abroad, for anyone interested:
"Shredded Paper Reconstruction—It Can Really Be Done!":
http://www.guokr.com/article/78259/
That competition is far more difficult!
The program is rather ugly and not particularly well-commented, so experts please excuse it~
Attachment: 2013 Mathematical Modeling Problem B.zip
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.