Problem Review
It must be said that Problem B of the 2013 National Mathematical Modeling Contest is truly a rare gem in the history of mathematical modeling competitions: the problem is concise, rich in meaning, allows for diverse approaches, and has strong extensibility. I have been thinking about it ever since. Because of this problem, I have already written two articles on "Scientific Space," namely "Mathematical Modeling by One Person: Shredded Paper Restoration" and "A Year Late: Re-exploring Shredded Paper Restoration". When I first worked on this problem, I only had a basic knowledge of mathematical modeling. Since learning data mining, especially deep learning, I have always wanted to redo this problem, but I kept procrastinating. I finally implemented it these past few days.
For readers who are not familiar with the problem, you can refer to the previous two articles. There are five attachments in total, representing five types of "shredded paper fragments" with different granularities. Attachments 1 and 2 are not difficult; the difficulty is mainly concentrated in Attachments 3, 4, and 5, which are essentially of the same implementation difficulty. The most intuitive approach to this problem is a greedy algorithm: pick a fragment at random, find the fragment that matches it best, and then continue matching the next one. For the greedy algorithm to be effective, the key is to find a good distance function to determine whether two fragments are adjacent (horizontally adjacent; vertical adjacency is not considered here).
The previous two articles used the Euclidean distance of edge vectors and mentioned indicators like correlation coefficients. However, if applied to Attachments 3, 4, and 5, the results are poor because the fragments are not large and there is little edge information available. Therefore, relying solely on edges is insufficient; one must consider multiple factors, such as line spacing, average line position, etc. How should these be considered? It is difficult for a human to write a good function manually. In that case, why not leave it to a model? Just use a Convolutional Neural Network (CNN)!
Constructing Samples
Specifically, we can observe the characteristics of the fragments:
Size 44 SimHei (Bold) font;
For Attachment 3, the content is Chinese; for Attachment 4, it is English;
Fragments have a fixed size of 72x180 pixels.
With these features, we can take a bunch of text and, following these specifications, construct a large number of adjacent and non-adjacent samples with the same properties. By training a CNN, we can automatically obtain a "distance function." This is quite simple for those familiar with deep learning. I directly found some Chinese text and generated a batch of Chinese samples. The code is roughly as follows:
from PIL import Image, ImageFont, ImageDraw
import numpy as np
from scipy import misc
import pymongo
from tqdm import tqdm
texts = list(pymongo.MongoClient().weixin.text_articles.find().limit(1000))
text = texts[0]['text']
line_words = 30
font_size = 44
nb_columns = line_words*font_size/72+1
def gen_img(text):
n = len(text) / line_words + 1
size = (nb_columns*72, (n*font_size/180+1)*180)
im = Image.new('L', size, 255)
dr = ImageDraw.Draw(im)
font = ImageFont.truetype('simhei.ttf', font_size)
for i in range(n):
dr.text((0, 70*i), text[line_words*i: line_words*(i+1)], font=font)
im = np.array(im.getdata()).reshape((size[1], size[0]))
r = []
for j in range(size[1]/180):
for i in range(size[0]/72):
r.append(1-im[j*180:(j+1)*180, i*72:(i+1)*72].T/255.0)
return r
sample = []
for i in tqdm(iter(texts)):
sample.extend(gen_img(i['text']))
np.save('sample.npy', sample)
nb_samples = len(sample) - len(sample)/nb_columns
def data(sample, batch_size):
sample_shuffle_totally = sample[:]
sample_shuffle_in_line = sample[:]
while True:
np.random.shuffle(sample_shuffle_totally)
for i in range(0, len(sample_shuffle_in_line), nb_columns):
subsample = sample_shuffle_in_line[i: i+nb_columns]
np.random.shuffle(subsample)
sample_shuffle_in_line[i: i+nb_columns] = subsample
x = []
y = []
for i in range(0, len(sample), nb_columns):
subsample_1 = sample[i: i+nb_columns]
for j in range(0, nb_columns-1):
x.append(np.vstack((subsample_1[j], subsample_1[j+1])))
y.append([1])
subsample_2 = sample_shuffle_totally[i: i+nb_columns]
for j in range(0, nb_columns-1):
x.append(np.vstack((subsample_2[j], subsample_2[j+1])))
y.append([0])
subsample_3 = sample_shuffle_in_line[i: i+nb_columns]
for j in range(0, nb_columns-1):
x.append(np.vstack((subsample_3[j], subsample_3[j+1])))
y.append([0])
if len(y) >= batch_size:
yield np.array(x), np.array(y)
x = []
y = []
if y:
yield np.array(x), np.array(y)
x = []
y = []The process is as follows: I took 1,000 articles, each several
thousand words long, printed each article uniformly onto an image, and
then cropped them to obtain a batch of samples. The data
function is an iterator used to generate positive and negative samples.
Since loading everything into memory at once is impossible, an iterator
is necessary. However, I was still a bit lazy; even with this approach,
it consumed 18GB of RAM on my server.
sample_shuffle_totally generates arbitrary negative samples
by shuffling all samples; sample_shuffle_in_line shuffles
only within the same line, resulting in negative samples where line
spacing and positions are identical, but the content is different. I
shuffle once per iteration to improve data performance (data
augmentation), significantly increasing the number of negative samples
used in training.
It is important to note that while we consider horizontal adjacency, Python reads matrices from top to bottom, not left to right. Therefore, we need to transpose the image matrix. Additionally, the images are normalized from the 0–255 grayscale range to 0–1 to speed up convergence. Finally, I subtracted the image matrix from 1, effectively performing a color inversion: "black text on white background" becomes "white text on black background." When training the network, we want the input to have many zeros to speed up convergence. In color values, white is 255 and black is 0; thus, "white text on black background" converges faster than "black text on white background."
Training the Model
Next, I used these samples to train a CNN. This process is very standard, using a stack of three convolutional and pooling layers, followed by a sigmoid classifier (for binary classification).
Model structure:
_________________________________________________________________ Layer (type) Output Shape Param # ================================================================= input_2 (InputLayer) (None, 144, 180) 0 _________________________________________________________________ convolution1d_4 (Convolution1D) (None, 143, 32) 11552 _________________________________________________________________ maxpooling1d_4 (MaxPooling1D) (None, 71, 32) 0 _________________________________________________________________ convolution1d_5 (Convolution1D) (None, 70, 32) 2080 _________________________________________________________________ maxpooling1d_5 (MaxPooling1D) (None, 35, 32) 0 _________________________________________________________________ convolution1d_6 (Convolution1D) (None, 34, 32) 2080 _________________________________________________________________ maxpooling1d_6 (MaxPooling1D) (None, 17, 32) 0 _________________________________________________________________ flatten_2 (Flatten) (None, 544) 0 _________________________________________________________________ dense_3 (Dense) (None, 32) 17440 _________________________________________________________________ dense_4 (Dense) (None, 1) 33 ================================================================= Total params: 33,185 _________________________________________________________________
Code:
from keras.layers import Input, Convolution1D, MaxPooling1D, Flatten, Dense
from keras.models import Model
input = Input((144, 180))
cnn = Convolution1D(32, 2)(input)
cnn = MaxPooling1D(2)(cnn)
cnn = Convolution1D(32, 2)(cnn)
cnn = MaxPooling1D(2)(cnn)
cnn = Convolution1D(32, 2)(cnn)
cnn = MaxPooling1D(2)(cnn)
cnn = Flatten()(cnn)
dense = Dense(32, activation='relu')(cnn)
dense = Dense(1, activation='sigmoid')(dense)
model = Model(input=input, output=dense)
model.compile(loss='binary_crossentropy', optimizer='adam', metrics=['accuracy'])
model.summary()
model.fit_generator(data(sample, batch_size=1024),
nb_epoch=100,
samples_per_epoch=nb_samples*3
)
model.save_weights('2013_suizhifuyuan_cnn.model')In fact, an accuracy of 95% can be achieved after just 3 iterations;
nb_epoch=100 was chosen arbitrarily. If computational
resources are sufficient and you are not in a hurry, more iterations do
no harm. I eventually achieved 97.7% accuracy.
Stitching Results
Now we can test the performance of our trained "distance function."
import glob
img_names = glob.glob(u'Attachment 3/*')
images = {}
for i in img_names:
images[i] = 1 - misc.imread(i, flatten=True).T/255.0
def find_most_similar(img, images):
imgs_ = np.array([np.vstack((images[img], images[i])) for i in images if i != img])
img_names_ = [i for i in images if i != img]
sims = model.predict(imgs_).reshape(-1)
return img_names_[sims.argmax()]
img = img_names[14]
result = [img]
images_ = images.copy()
while len(images_) > 1:
print len(images_)
img_ = find_most_similar(img, images_)
result.append(img_)
del images_[img]
img = img_
images_ = [images[i].T for i in result]
compose = (1 - np.hstack(images_))*255
misc.imsave('result.png', compose)For Attachment 3, the result of a single-pass stitching is (zoom in to see the original image):
For comparison, the result of a single-pass stitching using Euclidean distance was:
It is clear that the improvement is significant. Although this model was trained on Chinese corpora, it also performs well when applied directly to Attachment 4:
Similarly, for comparison, the stitching result for Attachment 4 using Euclidean distance was:
Thus, we can see that the model we obtained is indeed effective and possesses strong generalization capabilities. Of course, the direct stitching of English text is not perfect; it would be better to include English corpora in the training to achieve even better results.
Conclusion
A good problem is inevitably rich in content and stands the test of time. This is already the third article I have written about the shredded paper restoration problem. Perhaps there will be a fourth or a fifth; every study is a step deeper...
When reposting, please include the original address: https://kexue.fm/archives/4100
For more details on reposting, please refer to: Scientific Space FAQ