By combining an image processing technique with English letter feature

we propose a new algorithm based on clustering and global optimization for double-sided shred restoration. The image processing technique is applied to eliminate the parts of letters at different height levels. The parameters (pixel difference) that describe the matching degree of adjacent shreds based on preprocessing images are obtained. The parameters (correlation coefficient) of the matching degree of shreds and the rows based on post-processing images are also obtained. The optimization problem is converted into two sub-problems by using these parameters. The first problem is to establish a global optimal clustering model that minimizes the maximum target of pixel difference. The second problem is to translate the problem of matching adjacent shreds in the same row into a traveling salesman problem (TSP). A global optimization model is developed to solve the TSP for each row. Our simulation result demonstrates that the proposed image processing technique considerably eliminates the negative influences of the letter parts in different levels. The two feature parameters can capture most information of the matching degree. Recovery accuracy reaches over 90%. This study presents an efficient algorithm for shred restoration based on clustering and global optimization. Experimental results show that the proposed algorithm can significantly reduce the complexity of the optimization problem with good restoration result. The proposed algorithm has practical significance in shred restoration for paper shredders.