# A Solution to Reconstruct Cross-Cut Shredded Text Documents Based on Character Recognition and Genetic Algorithm

Authors: Hedong Xu; Jing Zheng; Ziwei Zhuang; Suohai Fan
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The reconstruction of destroyed paper documents is of more interest during the last years. This topic is relevant to the fields of forensics, investigative sciences, and archeology. Previous research and analysis on the reconstruction of cross-cut shredded text document (RCCSTD) are mainly based on the likelihood and the traditional heuristic algorithm. In this paper, a feature-matching algorithm based on the character recognition via establishing the database of the letters is presented, reconstructing the shredded document by row clustering, intrarow splicing, and interrow splicing. Row clustering is executed through the clustering algorithm according to the clustering vectors of the fragments. Intrarow splicing regarded as the travelling salesman problem is solved by the improved genetic algorithm. Finally, the document is reconstructed by the interrow splicing according to the line spacing and the proximity of the fragments. Computational experiments suggest that the presented algorithm is of high precision and efficiency, and that the algorithm may be useful for the different size of cross-cut shredded text document.


---

## Body

## 1. Introduction

The reconstruction technology of the shredded document is usually used for obtaining the judicial exhibit, repairing the relics and acquiring military intelligence. It plays an important role in judicial investment to repair the sensitive document damaged on purpose and archaeological research to recognize the cultural relics. Generally, the documents which are single sided or double sided are cut into pieces by hand or paper machine. Schauer et al. [1] thought the shredded document can be considered to be a variation from typical jigsaw puzzles. They define that there were three types of the fragments: the manually torn documents, the cross-cut shredded documents, and the strip shredded documents [1] (see Figure 1).The document shredded by hand (a) and by paper shredder ((b), (c)).
(a)
The manually torn document
(b)
The cross-cut shredded document
(c)
The strip shredded documentRecombining the document is tedious and time-consuming due to the tremendous number of the fragments and the missing information of the fragment. The efficient way is to reconstruct the shredded document by the automatic system. The approaches to reconstruct these two kinds of documents are different. The reconstruction of the paper with irregular boundaries shredded manually is based on the similarity of the boundary feature. Nevertheless, the fragments shredded by the paper shredder have smooth boundary, so the reconstruction method for irregular boundaries is not valid. For the smooth boundary, the key to reconstruct the document depends on the characters on the paper edges.Most of the existing literatures investigate the reconstructing of the fragments shredded manually. Justino et al. [2] used a polyapproximation to simplify the complex contours of fragments and reconstruct the pieces of manually torn document by matching the feature of the polygon. Such method could only reconstruct the document on a small scale. Kesarkar et al. [3] joined the torn pieces of papers with the semiautomatic technique which is comparing edge length and angles, and Richter et al. [4] introduced an algorithmic framework for the automatic assembly of shredded documents based on shape- and content-based information.Some literature focuses on the reconstruction of the strip shredded documents. Because the information in the boundary of the strip shredded documents is adequate, it is easy to calculate the correlation of two fragments and splice them if their proximity is high. Lin and Fan-Chiang [5] presented an algorithm based on image feature matching through the graph-based sorting scheme to reassemble the pieces of the shredded document. They merged the fragments with the average word length and the highest correlation of the binary codes. Also, some researchers made use of the character features to match two fragments. Perl et al. [6] proposed an optical character recognition (OCR) algorithm to match two fragments’ contours through the probability histograms of the characters in the border region. If the lines of the text decrease, the precision of the paper reconstruction drops. Diem and Sablatnig [7] proposed an optical character recognition (OCR) to recognize the characters in the ancient manuscripts.For the cross-cut shreds, the reconstruction of cross-cut shredded text documents (RCCSTD) problem proved to be NP-complete by Prandtstetter [8]. Biesinger et al. [9] investigated this problem with an improved genetic algorithm without using any pattern recognition technique. Schauer et al. [1] used a cost function to determine whether two shreds are adjacent according to the likelihood of the gray value of the pixels along the shreds edges through the memetic algorithm. The ant colony optimization and a variable neighborhood search were developed for RCCSTD by Prandtstetter and Raidl [10]. Sleit et al. [11] put up with a different approach for RCCSTD based on iteratively building clusters of shreds. A cross-cut shredded document is shown, for example, in Figure 2, including its correct reconstruction.The cross-cut shredded text document (a) and the fully reconstructed document (b).
(a)
(b)The reconstruction of cross-cut shredded text documents (RCCSTD) problem is defined as an injective mapΠ:S→D2, where the set of the fragments S={1,…,m×n} belongs to one single-side printed document and m×n is the number of grid-shaped images. In this mapping, each fragment s=(x,y)∈D2, where x∈{1,…,n} and y∈{1,…,m}, is assigned to one position in the two-dimensional (Euclidean) space D2={(x,y)∣x=1,…,n;y=1,…,m}, such that the virtual fragments are represented by the white rectangles in Figure 3, and each virtual fragment is allowed to be used once [9, 12]. Furthermore, assume that the orientation of the fragment is consistent and there is no character adhesion in the text.Figure 3
The explanation of RCCSTD problem [9, 12].The reconstruction of these fragments will be studied in this paper. First of all, statistic features of the English letters (capital and lowercase) including the letter size and the space between the letter and the ruled lines are measured, and we set a database of 52 letters (26 lowercase and 26 capital letters) of different fonts in the numeric way. The letter database is built for the character recognition, which can recognize the characters in the fragments and reconstruct the document in the row clustering and the intrarow splicing. Afterwards, since the ruled line of the characters in the common row is the same, cluster the fragments by the clustering algorithm with the help of the ruled line position determined by the identified characters in the fragments. The ruled lines in this paper are similar to the top lines and the based lines of the text [13]. Later, sort the fragments of each row concurrently. Splice some fragments according to identifiability of the characters on the joint of the boundaries at first. Then the combined fragments are regarded as the new fragments or vertices and their edges are the Euclidean distance between the border matrices of two new fragments. The TSP model and genetic algorithm are adopted to sort the fragments in the second stage. Finally, reconstruct the whole document using the fixed line spacing and the proximity of the fragment strings. Our methodology in detail is shown in Figure 4.Figure 4
The flowchart of our methodology.This paper is organized as follows. Section2 introduces how to establish the letter database for the character recognition system. In Section 3, the procedure of character recognition is introduced. The algorithm of row clustering based on the database is proposed in Section 4 while the process of intrarow splicing is shown in Section 5. Section 6 wraps up the work by interrow splicing. The simulation is given in Section 7. Finally, in Section 8, we conclude this paper and present some ideas in the future work.


## 2. Letter Database

Initially, the database of the letters is needed. We obtain the gray image matrices of the 26 English capital letters and 26 lowercase letters. And then we get the binary gray image matrix of each letter through setting the threshold at 205, which means the pixels whose gray value is over the threshold are indicated by 0, and other pixels are indicated by 1. The letter database will be used later to recognize the characters of the fragments during the reconstruction.


### 2.1. Letter Extraction

Character recognition is the key to document reconstruction. Importantly, all the given fragments should be transferred into the binary image matrix the same as the process for the letter mentioned above.We adopt the approach to extract the letter from Zhang et al. [14].For a letter binary matrixL=(lij)p×q, where p×q is the scale of the letter matrix. The leftmost side of the letter is min⁡{j∣lij=1,i=1,…,p;j=1,…,q}. The rightmost side of the letter is max⁡{j∣lij=1,i=1,…,p;j=1,…,q}. The top edge of the letter is min⁡{i∣lij=1,i=1,…,p;j=1,…,q}. The bottom edge of the letter is max⁡{i∣lij=1,i=1,…,p;j=1,…,q} (see Figure 5).Figure 5
The approach to extract the certain letter.


### 2.2. Size Feature Extraction

We obtain the height and width of a letter, which is the so-called size feature of a letter, through the approach in Section2.1. The space between the top edge and the bottom edge of a letter is defined as the height of a letter. The space between the leftmost side and the rightmost side of a letter is defined as the width of a letter. The size feature of letters is one crucial aspect of the letter database.


### 2.3. Ruled Line Space Extraction

Lu et al. [13] used the local maxima of the horizontal projection histogram in order to identify the top lines and the base lines of the text lines. Similarly, we locate the ruled lines using the horizontal projection of the binary image of the whole alphabet. If the ruled lines are found, the space between the letter and the overline or underline will be measured (shown as Figure 6). We set the overline as the uppermost line of the horizontal histogram and the underline as the bottom of the horizontal histogram. As for different letters, the space between the letter and the ruled lines (the overline and the underline) is the important feature of letters, playing the vital roles in the letter database. In other words, once certain letter in a fragment is recognizable, the exact ruled lines are found based on the space between the letter and the ruled lines (Figure 6).Figure 6
The space between the letter and the ruled lines.


## 2.1. Letter Extraction

Character recognition is the key to document reconstruction. Importantly, all the given fragments should be transferred into the binary image matrix the same as the process for the letter mentioned above.We adopt the approach to extract the letter from Zhang et al. [14].For a letter binary matrixL=(lij)p×q, where p×q is the scale of the letter matrix. The leftmost side of the letter is min⁡{j∣lij=1,i=1,…,p;j=1,…,q}. The rightmost side of the letter is max⁡{j∣lij=1,i=1,…,p;j=1,…,q}. The top edge of the letter is min⁡{i∣lij=1,i=1,…,p;j=1,…,q}. The bottom edge of the letter is max⁡{i∣lij=1,i=1,…,p;j=1,…,q} (see Figure 5).Figure 5
The approach to extract the certain letter.


## 2.2. Size Feature Extraction

We obtain the height and width of a letter, which is the so-called size feature of a letter, through the approach in Section2.1. The space between the top edge and the bottom edge of a letter is defined as the height of a letter. The space between the leftmost side and the rightmost side of a letter is defined as the width of a letter. The size feature of letters is one crucial aspect of the letter database.


## 2.3. Ruled Line Space Extraction

Lu et al. [13] used the local maxima of the horizontal projection histogram in order to identify the top lines and the base lines of the text lines. Similarly, we locate the ruled lines using the horizontal projection of the binary image of the whole alphabet. If the ruled lines are found, the space between the letter and the overline or underline will be measured (shown as Figure 6). We set the overline as the uppermost line of the horizontal histogram and the underline as the bottom of the horizontal histogram. As for different letters, the space between the letter and the ruled lines (the overline and the underline) is the important feature of letters, playing the vital roles in the letter database. In other words, once certain letter in a fragment is recognizable, the exact ruled lines are found based on the space between the letter and the ruled lines (Figure 6).Figure 6
The space between the letter and the ruled lines.


## 3. Character Recognition

Initially, the character to be recognized is extracted in the rectangle as the method mentioned in Section2.1. If the character is cut by the boundary line, before extracting, the fragment should be merged with another fragment (Figure 7).Figure 7
The character to be recognized is extracted in the rectangle.After the character extraction, the character recognition begins. Character recognition consists of two steps: height-width ratio judgment and binary matrix judgment (Figure8).Figure 8
The flowchart of the character recognition.A character is thought to be recognized as a letter if it has the same height-width ratio and the similar binary matrix to a certain letter in the letter database. In order to measure the similarity of the binary matrix, we set a threshold rate. That is to say, a character is recognizable if it shares the same height-width ratio with the certain letter in the database and its shape is over the threshold rate similar to this letter. Moreover, once a character is identified, the ruled lines of the line containing the identified character can be found according to the space between the letter and the ruled lines in the database.


## 4. Row Clustering

### 4.1.  The Clustering Vector

We use the ruled line to cluster the fragments; however, the data of the gray image matrix is so enormous that we transform the data into the clustering vector to describe a fragment. The binary gray image matrix of each fragment can be described as a4×1 clustering vector through feature extraction. The clustering vector is defined as CV=(a1,a2,a3,a4)T, where a1 represents the lower position of the unidentified row on the top of the fragment and a4 represents the upper position of the unidentified row at the bottommost of the fragment. Meanwhile, a2 represents the position of the overline of the last identified row, and a3 represents the position of the underline of the last identified row.The steps of the feature extraction are as follows (see Figure9).S1.
If the border-top of binary image matrix is equal to 0, there is no unidentified row on the top of the fragment; leta1=0; if not, continue to the next step.S2.
If the upper part of the fragment is identified, there is no unidentified row on the top; leta1=0; if not, let a1=l1, where l1 is the lower position of the unidentified row.S3.
If the border-bottom of binary image matrix is equal to 0, there is no unidentified row at the bottom of the fragment; leta4=0; if not, continue to the fourth step.S4.
If the foot of the fragment is identifiable, leta4=0; if not, let a4=l2, where l2 is the upper position of the unidentified row.S5.
If there is any identified row in the fragment, identify one character in the identified row nearest to the border-bottom by the character matching algorithm. Leta2=la and a3=lb, where la is the overline position of the identified row and lb is the underline position of the identified line; if not, let a2=0,a3=0.S6.
Finally, we get the clustering vector of the fragmentv=(a1,a2,a3,a4)T.Figure 9
Example of feature extraction.


### 4.2. The Cluster Center

Define the first fragment in each row of the original document as the cluster center, which has the fixed and larger blank than the other fragments in the leftmost space. Therefore, we find the cluster centers of the fragments. According to the fact that the space before the document has the largest blank, the fragments of the first column as the cluster centers are easily found (Figure10).Figure 10
The cluster center of all the fragments.The steps of finding the cluster center are as follows.S1.
Initializet=1.S2.
Initialize the number of cluster centerp=0 and j=1.S3.
If the pixels, which mean the element in the gray image matrix of fragmentj, from 1 to tth column are equal to 0, let p=p+1.S4.
Ifj<m×n, j=j+1, return to S3.S5.
Ifp>m, t=t+1, return to S2. If p=m, we obtain m fragments, also called cluster centers. The pixels from 1 to tth column of their gray image matrices are equal to 0. Denote the cluster centers as the cluster centers C1,C2,…,Cm.


### 4.3. The Distance between Other Fragments and Cluster Center

All fragments are assigned to their closest cluster centers according to the similarity of their feature vectors. Assume that the feature vector of the cluster center isCV′=(a1′,a2′,a3′,a4′)T. It is easier to estimate the similarity of two fragments by comparing two clustering vectors. If there is an identified row in both lines and the ruled lines of these two fragments are in the same position, that is, a2=a2′,a3=a3′, these two fragments are likely to be in the same cluster. If two ruled lines are not in the same position, these two fragments are not adjacent. The distance vector Dj,Cp means the distance between the clustering vector CVj of the fragment j and the clustering vector CVCp of cluster center Cp, and it is defined as
(1)Dj,Cp={(0,0),a2=a2′≠0,a3=a3′≠0(Inf,Inf),a2≠a2′ora3≠a3′(|a1-a1′|,|a4-a4′|),a2=a2′=a3=a3′=0.The steps of the row clustering algorithm are as follows.S1.
Compute the distance vectorDj,Cp.S2.
If both the components of the vectorDj,Cp are no more than the threshold, it shows that the fragment j and the cluster center Cp are in the same cluster.S3.
Cluster all the fragments intom clusters, and find the number of the fragments of each cluster.


## 4.1.  The Clustering Vector

We use the ruled line to cluster the fragments; however, the data of the gray image matrix is so enormous that we transform the data into the clustering vector to describe a fragment. The binary gray image matrix of each fragment can be described as a4×1 clustering vector through feature extraction. The clustering vector is defined as CV=(a1,a2,a3,a4)T, where a1 represents the lower position of the unidentified row on the top of the fragment and a4 represents the upper position of the unidentified row at the bottommost of the fragment. Meanwhile, a2 represents the position of the overline of the last identified row, and a3 represents the position of the underline of the last identified row.The steps of the feature extraction are as follows (see Figure9).S1.
If the border-top of binary image matrix is equal to 0, there is no unidentified row on the top of the fragment; leta1=0; if not, continue to the next step.S2.
If the upper part of the fragment is identified, there is no unidentified row on the top; leta1=0; if not, let a1=l1, where l1 is the lower position of the unidentified row.S3.
If the border-bottom of binary image matrix is equal to 0, there is no unidentified row at the bottom of the fragment; leta4=0; if not, continue to the fourth step.S4.
If the foot of the fragment is identifiable, leta4=0; if not, let a4=l2, where l2 is the upper position of the unidentified row.S5.
If there is any identified row in the fragment, identify one character in the identified row nearest to the border-bottom by the character matching algorithm. Leta2=la and a3=lb, where la is the overline position of the identified row and lb is the underline position of the identified line; if not, let a2=0,a3=0.S6.
Finally, we get the clustering vector of the fragmentv=(a1,a2,a3,a4)T.Figure 9
Example of feature extraction.


## 4.2. The Cluster Center

Define the first fragment in each row of the original document as the cluster center, which has the fixed and larger blank than the other fragments in the leftmost space. Therefore, we find the cluster centers of the fragments. According to the fact that the space before the document has the largest blank, the fragments of the first column as the cluster centers are easily found (Figure10).Figure 10
The cluster center of all the fragments.The steps of finding the cluster center are as follows.S1.
Initializet=1.S2.
Initialize the number of cluster centerp=0 and j=1.S3.
If the pixels, which mean the element in the gray image matrix of fragmentj, from 1 to tth column are equal to 0, let p=p+1.S4.
Ifj<m×n, j=j+1, return to S3.S5.
Ifp>m, t=t+1, return to S2. If p=m, we obtain m fragments, also called cluster centers. The pixels from 1 to tth column of their gray image matrices are equal to 0. Denote the cluster centers as the cluster centers C1,C2,…,Cm.


## 4.3. The Distance between Other Fragments and Cluster Center

All fragments are assigned to their closest cluster centers according to the similarity of their feature vectors. Assume that the feature vector of the cluster center isCV′=(a1′,a2′,a3′,a4′)T. It is easier to estimate the similarity of two fragments by comparing two clustering vectors. If there is an identified row in both lines and the ruled lines of these two fragments are in the same position, that is, a2=a2′,a3=a3′, these two fragments are likely to be in the same cluster. If two ruled lines are not in the same position, these two fragments are not adjacent. The distance vector Dj,Cp means the distance between the clustering vector CVj of the fragment j and the clustering vector CVCp of cluster center Cp, and it is defined as
(1)Dj,Cp={(0,0),a2=a2′≠0,a3=a3′≠0(Inf,Inf),a2≠a2′ora3≠a3′(|a1-a1′|,|a4-a4′|),a2=a2′=a3=a3′=0.The steps of the row clustering algorithm are as follows.S1.
Compute the distance vectorDj,Cp.S2.
If both the components of the vectorDj,Cp are no more than the threshold, it shows that the fragment j and the cluster center Cp are in the same cluster.S3.
Cluster all the fragments intom clusters, and find the number of the fragments of each cluster.


## 5. Intrarow Splicing

After row clustering, the set of the fragments in the same row is supposed to be{j1,j2,…,jn}. Intrarow splicing can be modeled as the problem of finding the optimal path of the graph (also called the traveling salesman problem). The traveling salesman problem figures out the shortest path for the salesman to visit each city exactly and only once and finally return to the original starting point.As intrarow splicing can be regarded to be the travelling salesman problem, the solution to this problem is to find a shortest path in the undirected graph that visits each vertex exactly once. Each fragment is a vertex of the graph, and the adjacent correlations of the fragments are the edges of the vertices. The goal is to figure out the shortest path which connects the start vertex (the leftmost fragment) to the ending vertex (the rightmost fragment).The intrarow splicing contains three steps: constructing distance matrix, the first stage splicing based on the character recognition, and the second stage splicing.


### 5.1. Constructing Distance Matrix

There are two boundaries in a fragment (the left edge and the right edge) when splicing the fragments to the others. Calculate the edges correlation according to the ordinary Euclidean distance metric. Forn fragments in the set of fragments {j1,j2,…,jn}, we define an n×n correlation matrix to show the adjacency among the fragments. Let Xjp=(x1,x2,…,xn)T be the gray image matrix of the rightmost edge of fragment jp and let Yjq=(y1,y2,…,yn)T be the gray image matrix of the leftmost edge of fragment jq, where jp, jq represents the fragment jp and the fragment jq, respectively (p,q=1,2,…,n). Define the distance between the fragment jp and the fragment jq as
(2)D(jp,jq)={0,jp=jq-Inf,pjpjq=1,jp≠jqdjpjq,pjpjq=0,jp≠jq,
where
(3)djpjq=∑i=1n‍|xi-yi|.Andpjpjq represents whether the character on the joint of two adjacent fragments is identifiable or not:
(4)pjpjq={0,thecharacterisunidentifiable1,thecharacterisidentifiable.For example, in Figure11(a), the character on the joint boundary is identifiable because the feature of the character is almost the same as that of the letter “e” in the database. In Figure 11(b), the character on the joint boundary is unidentifiable because the feature of the character is different from that of any letters in the database.The character on the joint boundary is identifiable (a). The character on the joint boundary is unidentifiable (b).
(a)
(b)Therefore, we obtain the distance matrix of fragments in the same row.


### 5.2. The First Stage Splicing

The fragmentsjp and jq are possibly adjacent when their correlation D(jp,jq)=-Inf. Select the pairs of the adjacent fragments to verify whether they can be merged into each other. Two fragments are adjacent when one character on the joint of the two fragments is identifiable according to the character database. Figure 11 is an example to explain whether the characters on the boundaries are identifiable or not.In the first stage splicing, according to distance matrix, we denote the set of fragments{j1,j2,…,jn} as follows.(a)
For each givenk(k=1,2,3,…,n), if D(jp,jq)>-Inf,l=1,2,3,…,n, the fragment jk is denoted as (jk).(b)
If the following equations existD(jk1,jk2)=D(jk2,jk3)=D(jk3,jk4)=⋯=D(jkt-2,jkt-1)=D(jkt-1,jkt)=-Inf,1≤k1,k2,…,kt≤n, and k1,k2,…,kt are pairwise different, the fragments jk1,jk2,…,jkt-2,jkt-1,jkt are denoted as (jk1,jk2,…,jkt-2,jkt-1,jkt).Finally, the set of fragments{j1,j2,…,jn} can be rewritten as follows:
(5){(jk1(1),jk2(1),…,jkL1(1)),(jk1(2),jk2(2),…,jkL2(2)),…,(jk1(r),jk2(r),…,jkLr(r))},
where 1≤r,Lr≤n, ks(i)=1,2,…,n, s=1,2,…,Li, and i=1,2,…,r.Furthermore,{(jk1(1),jk2(1),…,jkL1(1)), (jk1(2),jk2(2),…,jkL2(2)),…,(jk1(r),jk2(r),…,jkLr(r))} can be denoted as {J1,J2,…,Jr}, where (jk1(i),jk2(i),…,jkLi(i)) is represented by Ji(i=1,2,…,r). After the first stage splicing, the set of fragments {j1,j2,…,jn} is represented by {J1,J2,…,Jr}.


### 5.3. The Second Stage Splicing

After the first stage splicing, the fragments in the same row are denoted by{J1,J2,…,Jr}. Calculate the distance D(Jk,Jl) as defined in the first stage splicing, where k,l=1,2,…,r.Suppose that the fragmentJ1 contains the clustering center of the row, so the goal of TSP in the intrarow splicing is transferred and modeled as
(6)min⁡{D(J1,Ji)+∑1<u,v≤r,u≠v‍D(Ju,Jv)}.In other words, we find the solution of the TSP problem withJ1 as the starting point. We apply the genetic algorithm to solve this problem.With the usual coding method, generate an1×r array randomly within the interval [0,1]. The r components in the array correspond to J1,J2,…,Jr, respectively. The sort in ascending order of the 1×r array represents the position of J1,J2,…,Jr. In addition, adopting the multiple point crossover method, select two random positions of the crossover point, and exchange the gene segments. Moreover, adopting the multiple point mutation method, select some random position of the mutation point and replace the value on the mutation point. The fitness function of the genetic algorithm is
(7)F=D(J1,Ji)+∑1<u,v≤r,u≠v‍D(Ju,Jv).The new genetic algorithm with multiple point crossover operators and multiple point mutation operators is applied in order to increase the diversity of the individual. In addition, as for the first stage splicing based on the character recognition, we can offer the optimal initial solution to the genetic algorithm. Therefore the algorithm can be converged quickly. The optimal sequence of the fragments in a row can be obtained through the genetic algorithm.


## 5.1. Constructing Distance Matrix

There are two boundaries in a fragment (the left edge and the right edge) when splicing the fragments to the others. Calculate the edges correlation according to the ordinary Euclidean distance metric. Forn fragments in the set of fragments {j1,j2,…,jn}, we define an n×n correlation matrix to show the adjacency among the fragments. Let Xjp=(x1,x2,…,xn)T be the gray image matrix of the rightmost edge of fragment jp and let Yjq=(y1,y2,…,yn)T be the gray image matrix of the leftmost edge of fragment jq, where jp, jq represents the fragment jp and the fragment jq, respectively (p,q=1,2,…,n). Define the distance between the fragment jp and the fragment jq as
(2)D(jp,jq)={0,jp=jq-Inf,pjpjq=1,jp≠jqdjpjq,pjpjq=0,jp≠jq,
where
(3)djpjq=∑i=1n‍|xi-yi|.Andpjpjq represents whether the character on the joint of two adjacent fragments is identifiable or not:
(4)pjpjq={0,thecharacterisunidentifiable1,thecharacterisidentifiable.For example, in Figure11(a), the character on the joint boundary is identifiable because the feature of the character is almost the same as that of the letter “e” in the database. In Figure 11(b), the character on the joint boundary is unidentifiable because the feature of the character is different from that of any letters in the database.The character on the joint boundary is identifiable (a). The character on the joint boundary is unidentifiable (b).
(a)
(b)Therefore, we obtain the distance matrix of fragments in the same row.


## 5.2. The First Stage Splicing

The fragmentsjp and jq are possibly adjacent when their correlation D(jp,jq)=-Inf. Select the pairs of the adjacent fragments to verify whether they can be merged into each other. Two fragments are adjacent when one character on the joint of the two fragments is identifiable according to the character database. Figure 11 is an example to explain whether the characters on the boundaries are identifiable or not.In the first stage splicing, according to distance matrix, we denote the set of fragments{j1,j2,…,jn} as follows.(a)
For each givenk(k=1,2,3,…,n), if D(jp,jq)>-Inf,l=1,2,3,…,n, the fragment jk is denoted as (jk).(b)
If the following equations existD(jk1,jk2)=D(jk2,jk3)=D(jk3,jk4)=⋯=D(jkt-2,jkt-1)=D(jkt-1,jkt)=-Inf,1≤k1,k2,…,kt≤n, and k1,k2,…,kt are pairwise different, the fragments jk1,jk2,…,jkt-2,jkt-1,jkt are denoted as (jk1,jk2,…,jkt-2,jkt-1,jkt).Finally, the set of fragments{j1,j2,…,jn} can be rewritten as follows:
(5){(jk1(1),jk2(1),…,jkL1(1)),(jk1(2),jk2(2),…,jkL2(2)),…,(jk1(r),jk2(r),…,jkLr(r))},
where 1≤r,Lr≤n, ks(i)=1,2,…,n, s=1,2,…,Li, and i=1,2,…,r.Furthermore,{(jk1(1),jk2(1),…,jkL1(1)), (jk1(2),jk2(2),…,jkL2(2)),…,(jk1(r),jk2(r),…,jkLr(r))} can be denoted as {J1,J2,…,Jr}, where (jk1(i),jk2(i),…,jkLi(i)) is represented by Ji(i=1,2,…,r). After the first stage splicing, the set of fragments {j1,j2,…,jn} is represented by {J1,J2,…,Jr}.


## 5.3. The Second Stage Splicing

After the first stage splicing, the fragments in the same row are denoted by{J1,J2,…,Jr}. Calculate the distance D(Jk,Jl) as defined in the first stage splicing, where k,l=1,2,…,r.Suppose that the fragmentJ1 contains the clustering center of the row, so the goal of TSP in the intrarow splicing is transferred and modeled as
(6)min⁡{D(J1,Ji)+∑1<u,v≤r,u≠v‍D(Ju,Jv)}.In other words, we find the solution of the TSP problem withJ1 as the starting point. We apply the genetic algorithm to solve this problem.With the usual coding method, generate an1×r array randomly within the interval [0,1]. The r components in the array correspond to J1,J2,…,Jr, respectively. The sort in ascending order of the 1×r array represents the position of J1,J2,…,Jr. In addition, adopting the multiple point crossover method, select two random positions of the crossover point, and exchange the gene segments. Moreover, adopting the multiple point mutation method, select some random position of the mutation point and replace the value on the mutation point. The fitness function of the genetic algorithm is
(7)F=D(J1,Ji)+∑1<u,v≤r,u≠v‍D(Ju,Jv).The new genetic algorithm with multiple point crossover operators and multiple point mutation operators is applied in order to increase the diversity of the individual. In addition, as for the first stage splicing based on the character recognition, we can offer the optimal initial solution to the genetic algorithm. Therefore the algorithm can be converged quickly. The optimal sequence of the fragments in a row can be obtained through the genetic algorithm.


## 6. Interrow Splicing

In the text document, suppose that the overline and the underline of linep(p=1,2,…,m) are denoted as lover(p) and lunder(p), respectively. The interrow space is defined as the space between lunder(p) and lover(p+1) (Figure 12). Moreover, all of the interrow spaces in the text document are consistent. Finally, we can splice the string of fragments according to the interrow space and the proximity of the fragments.Figure 12
The interrow space.


## 7. Simulation

The shredded document with New Times Roman and 20 fonts is simulated to test the efficiency of the model, which is shown in Figure2. As for the parameter, the threshold for character recognition is set to 0.83, and the threshold for row clustering is set to 232. In genetic algorithm, the population size is set to 100, the iteration is set to 50, and mutation rate is set to 0.6. We implemented our approach in MATLAB and performed all tests on a double core of an Intel core CPU with 2.10 GHz and 2 GB RAM.A document in Figure2 is shredded into different scales of fragments to test the algorithm. The scales of fragments are as in Table 1.Table 1
The fragment scale of the shredded document.
Scale (piece)
12
25
35
45
48
54
66
84
96
104
112
120
126
130
Row
4
5
7
9
8
9
11
14
12
13
14
15
14
13
Column
3
5
5
5
6
6
6
6
8
8
8
8
9
10Now, we cut the documents into13×10 fragments and use this as an example to illustrate the process of document reconstruction in detail. First of all, the database that fits for the document reconstruction is applied, which is shown in Table 2.Table 2
The feature information of letters with New Times Roman and 20 fonts in database.
LW
LH
OLS
ULS
LW
LH
OLS
ULS
A
28
27
1
10
a
16
19
10
9
B
24
26
2
10
b
18
28
1
9
C
24
28
1
9
c
15
19
10
9
D
27
26
2
10
d
19
28
1
9
E
23
26
2
10
e
16
19
10
9
F
20
26
2
10
f
16
27
1
10
G
27
28
1
9
g
18
27
10
1
H
28
26
2
10
h
20
27
1
10
I
11
26
2
10
i
9
27
1
10
J
14
27
2
9
j
11
36
1
1
K
29
26
2
10
k
20
27
1
10
L
23
26
2
10
l
9
27
1
10
M
34
26
2
10
m
30
18
10
10
N
29
27
2
9
n
20
18
10
10
O
26
28
1
9
o
17
19
10
9
P
21
26
2
10
p
18
27
10
1
Q
26
35
1
2
q
19
27
10
1
R
27
26
2
10
r
13
18
10
10
S
18
28
1
9
s
12
19
10
9
T
22
26
2
10
t
11
24
5
9
U
28
27
2
9
u
20
19
10
9
V
28
27
2
9
v
19
19
10
9
W
37
27
2
9
w
28
19
10
9
X
28
26
2
0
x
19
18
10
10
Y
28
26
2
10
y
19
27
10
1
Z
23
26
2
10
z
17
18
10
10
*LW, LH, OLS, ULS are short for the width of letter, the height of letter, the space between the letter and the overline, the space between the letter and the underline.Secondly, with the help of the database and the character recognition, the clustering vector of each fragment is given through the row clustering algorithm (shown in Table3).Table 3
Clustering vectors of 130 fragments.
Fnum
1
2
3
4
5
6
⋯
123
124
125
126
127
128
129
130
CV
0
0
0
0
0
0
⋯
0
0
0
0
0
0
0
0
89
89
89
89
89
89
⋯
25
25
25
25
25
25
25
25
126
126
126
126
126
126
⋯
62
62
62
62
62
62
62
62
0
0
0
0
0
0
⋯
0
0
0
0
0
0
0
0
*Fnum represents the fragment number, and CV represents the clustering vector of each fragment.Based on the algorithm of row clustering, 130 fragments are distributed into 13 rows according to their clustering vectors (Table4).Table 4
The result of row clustering.
Row 1
1
2
5
4
3
6
8
7
9
10
Row 2
11
14
13
12
15
17
16
18
19
20
Row 3
21
24
23
22
26
29
28
27
30
25
Row 4
31
35
36
32
33
37
38
39
40
34
Row 5
41
42
46
44
45
43
47
48
49
50
Row 6
51
52
54
55
57
58
59
56
60
53
Row 7
61
62
63
64
65
66
67
68
69
70
Row 8
71
74
73
72
75
76
77
79
80
78
Row 9
81
82
85
83
84
86
88
87
89
90
Row 10
91
93
92
94
95
97
96
99
98
100
Row 11
101
106
103
109
105
102
107
108
104
110
Row 12
111
114
113
115
112
116
119
118
117
120
Row 13
121
122
124
123
125
126
129
128
127
130
*The bold numbers are the clustering centers.After the row clustering, the intrarow splicing starts. We use Row 13, for example. The distance matrix is used as in Tables5 and 6.Row13:
{121122124123125126129128127130}→
{(121,122,123,124), (126,127), (128,129,130), (125)}→
{(121,122,123,124), (125), (126,127), (128,129,130)}→
{121,122,123,124,125,126,127,128,129,130}.Table 5
The distance matrix in first stage.
121
122
123
124
125
126
127
128
129
130
121
0
−Inf
3050
2234
3656
3657
2777
3647
2831
1681
122
833
0
−Inf
2584
834
833
5591
855
1801
3647
123
2467
2041
0
−Inf
2470
2467
4003
2447
2077
1773
124
0
4428
1031
0
3
0
6416
42
1154
3064
125
0
4428
1031
2451
0
0
6416
42
1154
3064
126
6086
1806
5063
3685
6083
0
−Inf
6072
4938
3090
127
65
4455
1068
2478
62
65
0
101
1187
3107
128
1125
3345
2100
2110
1126
1125
5315
0
−Inf
1993
129
3720
818
3875
1701
3721
3720
2744
3702
0
−Inf
130
0
4428
1031
2451
3
0
6416
42
1154
0Table 6
The distance matrix in second stage.
(121, 122, 123, 124)
125
(126, 127)
(128, 129, 130)
(121, 122, 123, 124)
0
3
0
42
125
0
3
0
42
(126, 127)
65
62
65
101
(128, 129, 130)
0
3
0
42
*(i, j, …) means fragment i and fragment j are splicing in the first stage.Splicing in the other rows is similar to Row 13.After intrarow splicing and interrow splicing, as the end of the reconstruction algorithm, the document is finally reconstructed. The reconstruction result is shown in Table7, corresponding to Figure 13(a).Table 7
The final result of the algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
18
19
15
16
17
20
21
22
23
24
26
27
28
25
29
30
31
32
33
35
36
37
38
39
40
34
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
57
58
59
56
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
84
85
86
87
88
89
90
83
82
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
*The bold numbers are in wrong position.The first reconstructed document (a) and the second reconstructed document (b).
(a)
(b)The correct order of the document is shown in Table8, corresponding to Figure 2(b).Table 8
The correct order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130The precision of the reconstruction is calculated by(8)Precision=1-thenumberoffragmentsinwrongpositionthetotalnumberoffragments=1-29130=0.7769.In our simulation, it is found that the effective information of the fragment and the precision of document reconstruction descend globally as the number of the fragments increases. But in the local, the precision of the reconstruction has three stages (see Figure14). When the number of the fragments is less than 55, the precision of this algorithm is 100%; when the number is from 55 to 100, the precision is above 90%; when the fragments are more than 100 pieces, the reconstruction precision fluctuates around 75% to 85%.Figure 14
The precision of reconstructing the document (Figure2) shredded into different pieces.Because the initial solution is optimized through combining the adjacent fragments in the first stage splicing, the complexity of genetic algorithm to find the optimal path is simplified. In addition, the fragment splicing algorithm for each cluster can operate in the same time which improves efficiency. Therefore, the total operating time of reconstructing the documents cut into13×10 fragments is 0.8276 seconds, which is much faster than restoring the fragments by naked eye.To test the adaptability of the algorithm, we choose another document to compute the precision of document reconstruction (Figure13(b)). The document is shredded in the same way as the one in the previous experiment, with New Times Roman and 20 fonts. On the one hand, compared with the result in Figure 15, we could find that they have the similar trend, indicating the robustness of the algorithm. On the other hand, the precision in Figure 14 is different from the one in Figure 15, indicating that the result of this algorithm will be influenced by the difference of documents.Figure 15
The precision of reconstructing another document shredded into different pieces.Document is reconstructed by the algorithm proposed in this paper without human intervention. As for the unsatisfied result, that is to say, the precision cannot reach 100%, human intervention is necessary. After all, the complete document is our goal.


## 8. Conclusion and Future Work

This paper studies the reconstruction of the shredded text document cross-cut by the paper shredder. With the construction of the letter database, the character recognition helps find out the accurate ruled line in row clustering. In addition, the character recognition shortens the convergence time by offering the better initial solution to genetic algorithm in intrarow splicing. Meanwhile from the simulation results, the document is reconstructed precisely in that short convergence time. Hence, the feature-matching algorithm based on the character recognition can splice the fragments through row clustering, intrarow splicing, and interrow splicing with high efficiency and high precision.As a solution for the reconstruction of cross-cut shredded text documents (RCCSTD) problem, the algorithm proposed in this paper can be improved in the future. More feature information of the characters in the same row would be considered to be extracted and used to improving the precision in the row clustering. Also, more advanced OCR technology may help solve the RCCSTD problem a lot. We will use it to splice a larger number of fragments from the cross-cut shredded text documents and keep the high precision which is the unique goal for RCCSTD problem.



---

*Source: 829602-2014-06-30.xml*