# Practical Challenge of Shredded Documents: Clustering of Chinese Homologous Pieces
## 1 Introduction  
Shredded document recovery is a complicated and challenging problem that has been studied by many researchers. Paper documents are separated into large numbers of pieces when they are shredded. These pieces are highly similar and present chaotic sequences, thereby increasing the difficulty of document recovery. Shredded document recovery has important research value, and the relevant findings can be extensively applied in several fields, such as information security [1], judicial investigations [2], and archaeological research [3]. Shredded document recovery is a complicated non-deterministic polynomial-hard problem [4]. The recovery task includes several steps, and piece clustering is one of the key steps [5]. As the number of pieces increases, the difficulty of document recovery also increases [6]. In clustering, a large number of pieces are grouped into several clusters, and the pieces in the cluster are processed together, thereby reducing the difficulty of piece searching and improving the accuracy of piece matching [7]. Because of the high similarity between shreds, piece clustering is difficult. Research on piece clustering can be divided into two categories. The first piece clustering category is based on a single-page document. [PERSON] et al. [8] considered piece clustering according to the distribution feature of a text line and assessed cluster validity by the matching proportion method. [PERSON] et al. [9] treated the clustering operation as a part of document reconstruction itself and used the cost function for piece matching and clustering. [PERSON] et al. [10] utilized multimodal features, including shape, context, etc., to combine clusters and assemble shreddeddocuments. [PERSON] [11] used line information to cluster pieces from the same line. Similarly, [PERSON] et al. [12] presented a row clustering method for shreds. The second piece clustering category is based on multi-page documents. [PERSON] et al. [5] employed a 12-dimension feature that included line spacing and paper/ink color. Based on the features, virtually shredded pieces from different files are clustered using hierarchical clustering. [PERSON] [13] used only the text line position as the feature to cluster pieces from multi-page documents, which have distinctly different page setups. [PERSON] et al. [14] used several methods (color analysis, paper type analysis, and classification of the text) to cluster pieces from different sources. [PERSON] et al. [15] employed clustering as a preprocessing step for piece forensics and analyzed paper color and background texture to achieve piece clustering from different files. [PERSON] et al. [16] proposed a spectral clustering algorithm that is based on the contour and color distribution of pieces, and several photos shredded by hand were clustered. [PERSON] et al. [17] applied the shape information of pieces as the matching feature, clustered the different pages shredded by hand and reassembled the pieces. Differing from the first study that focused on a few of pieces and used the clustering idea to achieve pieces matching and splicing. The second study must solve the problem of piece clustering, in which numerous pieces from different documents are mixed. Because of its highly applicable value, the second study is a hotspot in the current research of piece clustering. Although some achievements have been made in the second study, it focuses on the pieces that have distinct differences regarding page format (character size and lines spacing), appearance (paper color and piece shape), or content (writing style). These visual differences are very helpful for clustering. However, a real file usually has a unified document format, in which all pages of the document must present consistent paper color, character size, and text line spacing to satisfy people's reading habits [18]. When the file is shredded, the produced pieces are highly similar regarding page format, appearance, and content.