CN103679678B - A kind of semi-automatic splicing restored method of rectangle character features a scrap of paper - Google Patents

Abstract

The invention proposes a method for splicing and restoring rectangular shredded paper. According to the different cutting methods (longitudinal, horizontal and vertical), paper strip types (single-sided, double-sided) and text (Chinese, English), the splicing and restoration methods are divided into three parts from simple to difficult: longitudinal cutting of Chinese and English strips, Cross-cut Chinese and English paper strips, cross-cut double-sided English paper strips. Each part needs to first convert the read image into a grayscale image, and perform binarization and inversion operations, and then use algorithms such as left edge fragment detection, edge matching, and height detection to achieve the purpose of splicing and restoring shredded paper. In order to improve the accuracy of splicing restoration, manual intervention is added to the horizontal and vertical cutting methods, and morphological preprocessing operations are added to the horizontal and vertical cutting of English paper strips. The method provided by the invention has strong pertinence, simple operation, greatly improved efficiency compared with the manual splicing and restoration method, and significantly improved accuracy compared with fully automatic splicing and restoration, and has obvious advantages in the restoration of rectangular fragments cut by a shredder.

Description

A Semi-automatic Splicing and Restoration Method for Rectangular Text Feature Shredded Paper

technical field

The invention proposes a splicing and restoration method for shredded pieces of paper characterized by rectangular characters, which belongs to the technical field of image processing and pattern recognition in computer applications.

technical background

Automatic splicing of fragments can be approximately regarded as a puzzle problem [1], and has important applications in the fields of judicial evidence restoration, historical document restoration, art restoration, broken paper coin restoration, and military intelligence acquisition [2]. Traditionally, splicing and restoration work has to be done manually, with high accuracy but low efficiency. Especially when the number of fragments is huge, it is difficult for manual splicing to complete the task in a short time. Shredded paper can be seen everywhere in daily life, and it is a kind of debris. With the rapid development of computer technology, people try to develop the automatic splicing technology of shredded paper to improve the efficiency of splicing and restoration.

At present, researchers at home and abroad have done a lot of research on splicing and restoration of fragments. For paper fragments, they mainly process the shredded paper fragments shredded by hand. The key technology is the research on shape matching technology. For example, in literature [3] A mosaic method based on multi-scale two-dimensional fragments is proposed, and the curvature string of sampling points on the contour of the shredded paper is used for multi-scale analysis, and dynamic programming technology is used to refine each matching. Literature [4] proposes a fragment based on elastic matching For the automatic splicing method, literature [5] adopts a human-computer interaction semi-automatic splicing method, and literature [2] proposes a semi-automatic splicing shape matching method for shredded paper, which starts from extracting the outline of shredded paper and uses boundary criteria and area criteria to achieve matching. Document [6] proposes an edge detection algorithm for scraps of paper based on line segment scanning and so on. At present, these algorithms are all based on irregular shapes, and literature [7] proposes a semi-automatic fragment splicing algorithm based on fragmented text line features or table features for text document features, combining text line features and table features Taking line features into consideration, combined with manual methods, the accuracy has been greatly improved compared with pure machine stitching.

With the improvement of printing technology, handwriting has been gradually replaced by printing in document records, making the line features and table features of text tend to be more consistent. At the same time, shredders are becoming more and more popular in office applications, and the fragments of documents appear in two forms: horizontal and vertical, so algorithms based on shape features are becoming weaker and weaker in splicing and restoration. In response to this situation, we propose a restoration method for rectangular shreds of paper, which is spliced and restored through character handwriting features and left edge detection.

[1]Wolfson H, Schonberg E, Kalvin A, et al.Solving jigsaw puzzles by computer[J].Annals of Operations Research,1988,12(1):51-64.

[2] Jia Haiyan, Zhu Liangjia, Zhou Zongtan, et al. A shape matching method in automatic splicing of shredded paper [J]. Computer Simulation, 2006, 23(11): 180-183.

[3] da Gama HC, Stolfi JA multiscale method for the reassembly of two-dimensional fragmented objects[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002, 24(9): 1239-1251.

[4]Kong W,Kimia B B.On solving 2D and 3D puzzles using curve matching[C]//Computer Vision and Pattern Recognition,2001.CVPR 2001.Proceedings of the 2001IEEE Computer Society Conference on.IEEE,2001,2: II-583-II-590vol.2.

[5]De Smet P, De Bock J, Corluy E.Computer vision techniques for semi-automatic reconstruction of ripped-up documents[C]//AeroSense 2003.International Society for Optics and Photonics,2003:189-197.

[6] Luo Zhizhong. Research on edge detection algorithm of shredded paper based on line segment scanning [J]. Journal of Instrumentation, 2011,32(002):289-294.

[7] Luo Zhizhong. Semi-automatic splicing of document scraps based on text features [J]. Computer Engineering and Applications, 2012,48(5):207-210.

Contents of the invention

At present, most fragment splicing restoration technologies are based on fragment shape features, and some algorithms are highly complex and not very pertinent. However, with the development of technology, printing technology and the application of paper shredders in daily life, shredded paper fragments gradually present a regular rectangle, and the form features gradually fade away. In view of the deficiencies in the prior art, the present invention provides a rectangular text feature Method of splicing and restoring shredded paper. The recovery method of the present invention consists of processes such as preprocessing of shredded paper, detection of left edge shredded paper, and right matching of edge matching algorithm, assisted by manual processing, etc., and according to the splicing difficulty from low to high, the Chinese and English vertical Cut paper strips, Chinese and English horizontal and vertical cut paper strips, and English horizontal and vertical cut double-sided paper strips have been processed.

Technical scheme of the present invention is as follows:

A method for splicing and restoring pieces of paper with rectangular character features, including restoration methods for Chinese and English longitudinally cut pieces of paper, Chinese and English horizontally and vertically cut pieces of paper, and English horizontally and vertically cut double-sided paper pieces:

1. Chinese and English slitting pieces of paper

(1) Use a scanner to read in the digital image of text fragments, and convert the image into a grayscale image;

Since the fragments are relatively slender when there are only longitudinal fragments, it is more feasible to use the longitudinal edge vector as a comparison quantity, and the process is shown in Figure 1(a);

(2) The image is subjected to binarization processing, fragment left edge detection, edge matching and display splicing restoration image respectively:

(a) Binarize the image: serially number the fragments of paper strips, such as 00, 01, 02, ..., the computer reads in the fragmented images according to the number, and performs binarization and inversion to extract the left and right edge vectors of each fragment;

(b) Perform left edge detection on the fragments in step (a) in order to determine whether the fragments are the left edge of the original document: judge whether the left edge of the numbered fragments is blank, if it is blank, the numbered fragments are the left edge of the document ;

(c) Sorting the fragments according to the edge matching criterion: after determining the left edge of the original document through step (b), determine that the fragment corresponding to the left edge of the document is the first fragment, and display the first fragment and its number; The right edge vector of the first fragment is compared and matched with the left edge vectors of other fragments in order of number until the second fragment matching the right edge of the first fragment is found, and the second fragment and its Numbering;

(d) According to the edge matching criterion of step (c), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form the final restored original document;

(e) saving the sorting of the matching fragments and the corresponding numbering sorting described in step (c) and step (d).

Preferably according to the present invention, human eyes check the final restored original document in the step (d), and verify the restoration result;

2. Chinese and English horizontal and vertical cut paper pieces

Since there are cutting marks on the top, bottom, left, and right of the fragment, considering factors such as character spacing, line spacing, and paragraph indentation, there may be blanks on the edge of the fragment, which will cause large errors in edge vector matching. In this case, the judging standard of the character position (height) of each line is added, that is, the line matching is completed by the approximate position of each line of characters on the fragment.

Chinese is a square character with a relatively regular shape, so it is very feasible to use character height detection as a grouping standard; while English letters have different heights, so certain preprocessing is required to control the letters within a relatively consistent height range, and then determine the overall Relative position, thereby improving the recognition rate. Since Chinese and English characters have different characteristics, they cannot be processed using the same standard. The Chinese and English documents are analyzed separately below.

① Chinese horizontal and vertical fragments

The restoration process of Chinese horizontal and vertical fragments is shown in Figure 1(b):

First, read in the digital image information of the paper strip fragments cut horizontally and vertically in the document, convert the fragment image into a grayscale image, and perform binarization and inversion processing, and then extract the left and right edge vectors and upper and lower edge vectors of each fragment respectively ;

Secondly, the height of the debris will be detected; and the fragments on the left edge will be detected in the group to perform intra-group matching; finally, the horizontal paper strips will be matched up and down to restore:

i) Detect the height of the characters on the fragments: Since Chinese is a square character with a relatively regular shape, detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the fragments is a word or a blank, and the highest pixel where the characters appear in the first line Classify the point positions into groups, and number the fragments in each group; when classifying, in order to avoid the occurrence of special situations, carry out precise grouping, add manual intervention guidance, arrange the height of the text according to the size, and the height of adjacent values close The corresponding fragments are grouped together;

ii) Intra-group matching: perform intra-group matching on the fragments classified in step (i):

(a) carry out left edge detection to all fragments successively, to determine whether described fragment is the left edge fragment of original document: judge whether the left edge of fragment is blank, if it is blank then fragment is the left edge of document;

(b) Sorting the fragments according to the edge matching criterion: if the detected left edge fragment exists in the group divided in the process of step i), then use the left edge fragment as the starting point to perform right edge matching on the corresponding grouped fragments ; After determining the left edge of the original document by step (a), determine that the fragment corresponding to the left edge of the document is the first fragment, and display the first fragment and its number; the right edge vector of the first fragment is sequentially connected with The left edge vectors of other fragments are compared and matched until the second fragment matching the right edge of the first fragment is found, and the second fragment and its number are displayed on the right side of the first fragment;

If the left edge fragment does not belong to any group, put the fragment on hold until other groups are matched, and then match into the document according to the upper and lower edge vectors of the left edge fragment of the original document;

(c) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe file;

(d) saving the sorting of matching fragments and the corresponding numbering sorting described in step (b) and step (c).

Preferably, according to the present invention, human eyes check the restored original horizontal stripe document in the step (c), and verify the restoration result. Due to the low pixel size of fragments, each group must participate in manual screening during the matching process. When encountering wrong matches, they should be eliminated and corrected again or continue to match after inserting correct fragments;

iii) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Finally get the horizontal note;

iv) Horizontal paper strips match up and down:

Extract the upper and lower edge vectors of the horizontal paper strips for comparison and matching,

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably according to the present invention, the original horizontal bar document is restored in step (c) in step iv) by human eyes, and the restoration result is approved; due to the existence of line spacing, upper and lower margin blanks may appear after the matching within the group, which cannot be performed The upper and lower edge vectors are compared, so manual inspection is performed after the horizontal paper strips are matched up and down to check whether the context of the document content is reasonable. If there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters;

② English horizontal and vertical fragments

Due to the morphological characteristics of English letters, it is inaccurate to only detect the highest and lowest positions of letters in the first line. The positioning method of four lines and three grids in Lenovo English homework paper, as shown in Figure 2, chooses to use the positioning line to complete the line matching. According to the position and duty cycle of the standard four lines and three grids, the letters are divided into four heights in advance: occupying the middle grid (such as a, e, etc.), occupying the upper two grids (such as h, l, etc.), and occupying the lower two grids ( Such as y, g, etc.), occupying three grids (j). Before grouping, it is necessary to calculate the heights of different types of letters, and based on this, process the heights of English letters and then group them.

According to the characteristics of the four-line grid of English letters, each letter has content in the middle grid, and only some letters have content in the upper and lower two grids. Therefore, finding the second and third lines of the four-line grid can accurately locate the row where the letter is located.

Considering that the content occupying the upper case has obvious morphological characteristics in the vertical direction, with proper processing, except for the upper case occupied by capital letters, other letters can eliminate the content occupied by the upper case.

In addition, considering that the proportion of capital letters and letters occupying the lower cells is relatively small, in a processed fragment, it is almost always possible to find at least one row with only the middle cell. Once such a row is found, it can be calculated according to the Calculate the position of the second and third lines of other rows based on the spacing and height data, so as to achieve height grouping.

First, read in the digital image of the fragments of paper strips, convert them into grayscale images, and perform binarization and inversion processing to highlight the text; then extract the left and right edge vectors and upper and lower edge vectors of each fragment respectively;

Secondly, the height of the debris will be detected; and the fragments on the left edge will be detected in the group to perform intra-group matching; finally, the horizontal paper strips will be matched up and down to restore:

Then, process according to the steps shown in Figure 1(b), determine the position of the second and third lines of the fragments, and group them according to the height of the text; match within the group, and finally match up and down the horizontal paper strips to recover:

i) Fragment preprocessing: In order to determine the position of the letters in each row and offset the height matching error caused by the difference in letter occupancy to the greatest extent, the letters must first be morphologically processed, and the letter parts occupying the upper grid should be eliminated as much as possible, so as to determine The position of the second and third lines.

ii) Determine the position of the second and third lines in the fragments, and group them according to height: firstly, find a line occupying only the middle grid in the processed fragments, and then calculate the position of the second and third lines of the previous line until it exceeds the upper edge. Take the height of the first second line that appears in each fragment as the characteristic height of the fragment, and group based on this, and detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the fragment is a word or a blank, and the first line of characters The position of the highest pixel point appearing at the height of the second line in the fragments is classified into groups, and the fragments in each group are numbered; when classifying, in order to avoid the occurrence of special situations, accurate grouping is carried out, and manual intervention guidance is added to divide the height of the text according to The size is arranged, and the fragments corresponding to the heights with close adjacent values are grouped together.

iii) Intra-group matching: perform intra-group matching on the fragments classified in step (ii):

(a) carry out left edge detection to all fragments successively, to determine whether described fragment is the left edge fragment of original document: judge whether the left edge of fragment is blank, if it is blank then fragment is the left edge of document;

(b) Sorting the fragments according to the edge matching criterion: if the detected left edge fragment exists in the group divided in the process of step i), then use the left edge fragment as the starting point to perform right edge matching on the corresponding grouped fragments ; After determining the left edge of the original document by step (a), determine that the fragment corresponding to the left edge of the document is the first fragment, and display the first fragment and its number; the right edge vector of the first fragment is sequentially connected with The left edge vectors of other fragments are compared and matched until the second fragment matching the right edge of the first fragment is found, and the second fragment and its number are displayed on the right side of the first fragment;

If the left edge fragment does not belong to any group, put the fragment on hold until other groups are matched, and then match into the document according to the upper and lower edge vectors of the left edge fragment of the original document;

(c) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe document;

(d) storing the sorting and corresponding numbering of the matching fragments described in step (b) and step (c);

Preferably, according to the present invention, human eyes check the restored original horizontal stripe document in the step (c) of step iii) to verify the restoration result. Due to the low pixel size of fragments, each group must participate in manual screening during the matching process. When encountering wrong matches, they should be eliminated and corrected again or continue to match after inserting correct fragments;

iv) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Finally get the horizontal note;

v) Horizontal paper strips match up and down:

Extract the upper and lower edge vectors of the horizontal paper strips for comparison and matching,

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably according to the present invention, the original horizontal bar document is restored in step (c) in step iv) by human eyes, and the restoration result is approved; due to the existence of line spacing, upper and lower margin blanks may appear after the matching within the group, which cannot be performed The upper and lower edge vectors are compared, so manual inspection is performed after the horizontal paper strips are matched up and down to check whether the context of the document content is reasonable. If there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters;

3. Double-sided English horizontal and vertical cut paper fragments

Since the front and back of the fragments are inconsistent, there will be twice the different fragment information of the single-sided note. However, since the front and back of the fragments correspond, as long as one side is matched, the result expression can be obtained. For the difficulty of single-sided : The amount of data is doubled. In the process of high grouping, the number of each group will increase greatly. At the same time, due to the increase of edge blank fragments, the edge matching error rate increases, which increases the workload of manual error correction. For the comparison of Chinese and English fragments, it can be seen from the 2 solutions that the splicing and restoration of English is much more difficult than that of Chinese. Therefore, we choose to process the fragments of double-sided English horizontal and vertical paper strips. For Chinese double-sided paper strips, please refer to Part 2 is the splicing and restoration method of Chinese horizontal and vertical cut paper fragments, and the third part is the two-part content of the double-sided English horizontal and vertical splicing and restoration method.

For the fragments of double-sided paper strips, the solution is as follows: Find all the fragments on the left edge. Manually match the left edge fragments first, then the left edge of each side can be obtained. In the same group, if it contains two left-edge fragments, they will be used as the beginning to match to the right. If an error occurs during the matching process due to blank margins, manual intervention is required to correct the error, and the process will not be repeated; if only one left-edge fragment is included , and the number of fragments in the group is large, it will be used as the beginning of the match; if the number of fragments in the group is small, after other groups are matched, the fragments will be added to the result expression in the form of manual error correction filling.

The splicing and restoration process of double-sided English horizontal and vertical fragments is shown in Figure 1(c):

First, read the front and back digital image information obtained from the scraps of paper strips, convert the image into a grayscale image, and perform binarization and inversion operations on the grayscale image to highlight the text;

Secondly, carry out height detection, manual assisted grouping; front and back edge detection within the group, matching within the group and manual inspection; vertical matching of horizontal paper strips, splicing and restoration:

i) Fragment preprocessing: In order to obtain the position of each row of letters and offset the height matching error caused by the difference in letter occupancy to the greatest extent, by performing morphological processing on the letters in the fragments, try to eliminate the part of the letter occupying the upper grid, in order to determine the second , Prepare for the third-line position;

ii) Determine the position of the second and third lines in the fragments, and group them according to their heights: first find a line in the processed fragments that only occupies the middle grid, and then calculate the position of the second and third lines of the previous line until it exceeds the upper edge. Take the height of the first second line that appears in each fragment and define it as the characteristic height of the fragment; then detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the character is a word or a blank, and the highest second-line height of the character in the first line The positions of the pixels in the fragments are grouped, and the fragments in each group are numbered; when classifying, in order to avoid the occurrence of special situations, manual intervention guidance is added, and the fragments are arranged according to the height of the text, and the fragments with similar heights are grouped together ;

iii) Intra-group matching: perform intra-group matching on the fragments classified in step (ii):

(a) carry out left edge detection to fragment in each group, determine that the left edge in each group is the left edge of each line of original document: judge whether fragment in each group is blank, if it is blank, it is the left edge of fragment document;

(b) Match to the right according to the edge matching criterion: if the detected left-edge fragment exists in the divided group in step (ii), then start from the left-edge fragment of the fragment to the right of the corresponding fragment in the group Matching: compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence, until the second horizontal paper strip that matches the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) At this time, manual intervention is required to observe the matching results, take the redundant fragments to the fragment group that cannot be grouped, and search for the missing fragments in the fragment group that cannot be grouped. Since the height distribution is relatively concentrated, grouping is not difficult, only individual discontinuous fragments need to be considered. There are also two left-edge fragments in the fragments that cannot be grouped, which are matched separately, so that the fragments in one group are divided into two rows;

(d) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe file;

(e) saving the sorting of the matching fragments and the corresponding numbering sorting described in step (b) and step (c).

Preferably according to the present invention, human eyes check the restored original horizontal stripe document in the step (c) in the step iii) and check the restoration result. Due to the low pixel size of fragments, each group must participate in manual screening during the matching process. When encountering wrong matches, they should be eliminated and corrected again or continue to match after inserting correct fragments;

iv) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Finally get the horizontal note;

v) Up and down matching of horizontal paper strips: extracting the upper and lower edge vectors of horizontal paper strips for comparison and matching,

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably according to the present invention, the original horizontal bar document is restored in step (c) in step v) with human eyes, and the restoration result is approved; due to the existence of line spacing, upper and lower margins may appear after the matching within the group, and cannot be performed. The upper and lower edge vectors are compared, so manual inspection is performed after the horizontal paper strips are matched up and down to check whether the context of the document content is reasonable. If there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters;

vi) From step (v), all rows belonging to the same side can be found, and after matching one side of the document, the entire document can be restored.

The beneficial effects of the present invention are:

1. According to the present invention, the pulverized paper strips of the shredder present a rectangular shape, and the regular rectangular shape shredded paper is processed in a targeted manner;

2. According to the different cutting methods, the present invention performs special treatment on common different cutting methods such as single-sided longitudinal cutting, single-sided horizontal and longitudinal cutting, and double-sided horizontal and longitudinal cutting;

3. According to the differences between Chinese and English documents, the present invention performs targeted processing on splicing and restoration of two kinds of documents: Chinese document horizontal and vertical cut and English document horizontal and vertical cut;

4. The processing of different documents and cutting methods in the present invention greatly improves the efficiency and accuracy of splicing and restoration.

Description of drawings

Fig. 1 The splicing and restoration process of Chinese and English slitting paper strips;

Figure 2 Four-line layout of English letters;

Figure 3 is a picture of 19 pieces of Chinese paper strips cut longitudinally;

Figure 4 English paper strips cut longitudinally into 19 fragments;

Figure 5(a) The splicing and restoration results of longitudinally cut Chinese paper strip fragments;

Fig. 5(b) splicing and restoration results of longitudinally cut English paper fragments;

Figure 6: A picture of 209 fragments of Chinese paper strips cut horizontally and vertically;

Figure 7(a) is an example of the position where the margin of the debris appears;

Figure 7(b) is an example of where the fragment edge pixels appear;

Figure 8: An example of fragments in the fifth line of Chinese paper strips cut horizontally and vertically;

Fig. 9 The restoration results of the horizontal and vertical splicing of Chinese paper strips;

Figure 10 Schematic diagram of English letter marking and height measurement;

Fig. 11 Schematic diagram of English horizontal and vertical fragment image preprocessing;

Figure 12 The restoration results of horizontal and vertical splicing of English paper strips;

Fig. 13 (a) the fragments of side a of the double-sided English paper strip cut vertically and horizontally;

Fig. 13(b) The double-sided English paper strip is cut horizontally and vertically into the b-side fragments;

Fig. 14(a) is the side A of the splicing restoration diagram of double-sided English paper strips cut horizontally and vertically;

Fig. 14(b) is side B of the spliced restoration diagram of double-sided English paper strips cut horizontally and vertically.

detailed description:

The present invention will be described in detail below in conjunction with the accompanying drawings and examples, but is not limited thereto.

Embodiment 1,

A kind of splicing recovery method of rectangular pieces of shredded paper is shown in Figure 1, including the restoration method for Chinese and English vertically cut paper strip fragments, Chinese and English horizontally and vertically cut paper strip fragments, and English horizontally and vertically cut double-sided paper strip fragments:

1. Chinese and English slitting pieces of paper

(1) Use a scanner to read in the digital image of the text fragments, and convert the image into a grayscale image. The Chinese paper fragments are shown in Figure 3, and the English paper fragments are shown in Figure 4, with a total of 19 fragments;

Since the fragments are relatively slender when there are only longitudinal fragments, it is more feasible to use the longitudinal edge vector as a comparison quantity, and the process is shown in Figure 1(a);

(2) The image is subjected to binarization processing, fragment left edge detection, edge matching and display splicing restoration image respectively:

(a) Perform binarization processing on the image: sequentially number the fragments of paper strips, such as 00, 01, 02, ... 18, and the computer reads in the fragment images according to the numbers, and performs binarization processing and inversion, Extract the left and right edge vectors of each patch;

(b) Perform left edge detection on the fragments in step (a) in order to determine whether the fragments are the left edge of the original document: determine whether the left edge of the fragment numbered 00 is blank, and if it is blank, then the fragment numbered 00 for the left edge of the document. Otherwise, compare the scrap of paper with the number 00 with other rectangular fragments of equal width and height according to the serial number, and detect the scrap of paper with a certain blank on the left edge, which is the left edge fragment of the original document;

(c) Sorting the fragments according to the edge matching criterion: after determining the left edge of the original document through step (b), determine that the fragment corresponding to the left edge of the document is the first fragment, and display the first fragment and its number; The right edge vector of the document is compared and matched with the left edge vectors of other fragments in sequence according to the numbering order, that is, starting from the first fragment of the document found by the left edge detection of the document, the right edge vector of the previous fragment and the left edge of other fragments are cyclically extracted Vectors are compared, and each time the two vectors have a different element, the comparison mark xx plus 1. After all comparisons are completed, take the fragment with the smallest xx value as the second fragment that matches the right edge of the first fragment, and display the second fragment and its number on the right side of the first fragment;

(d) According to the edge matching criterion of step (c), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display the respective numbers to form the final restored original document, and the numbering sequence of the Chinese longitudinal fragments is Table 1, and the English longitudinal fragmentation numbering sequence is Table 2;

Table 1 Number of Chinese longitudinal slices:

008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 017 000 006

Table 2 Numbers of longitudinally cut fragments in English:

003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004

(e) saving the sorting of the matching fragments and the corresponding numbering sorting described in step (c) and step (d).

Preferably according to the present invention, human eyes check the final restored original document in the step (d), and check and verify the restoration results, and the Chinese and English fragment restoration results are shown in Figure 5 (a), (b) respectively;

2. Chinese and English horizontal and vertical cut paper pieces

Since there are cutting marks on the top, bottom, left, and right of the fragment, considering factors such as character spacing, line spacing, and paragraph indentation, there may be blanks on the edge of the fragment, which will cause large errors in edge vector matching. In this case, the judging standard of the character position (height) of each line is added, that is, the line matching is completed by the approximate position of each line of characters on the fragment.

Chinese is a square character with a relatively regular shape, so it is very feasible to use character height detection as a grouping standard; while English letters have different heights, so certain preprocessing is required to control the letters within a relatively consistent height range, and then determine the overall Relative position, thereby improving the recognition rate. Since Chinese and English characters have different characteristics, they cannot be processed using the same standard. The Chinese and English documents are analyzed separately below.

① Chinese horizontal and vertical fragments

The restoration process of Chinese horizontal and vertical fragments is shown in Figure 1(b):

First, read in the digital image information of the paper strip fragments cut horizontally and vertically in the document, and convert the fragment image into a grayscale image. As shown in Figure 6, the paper strip is cut 10 times and the paper strip is cut 18 times, forming a total of 11*19 Block fragments, and perform binarization and inversion processing, and then extract the left and right edge vectors and upper and lower edge vectors of each fragment respectively;

Secondly, the height of the debris will be detected; and the fragments on the left edge will be detected in the group to perform intra-group matching; finally, the horizontal paper strips will be matched up and down to restore:

i) Detect the height of the characters on the fragments: Since Chinese is a square character with a relatively regular shape, detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the fragments is a word or a blank, and the highest pixel where the characters appear in the first line Classify the point positions, as shown in Figure 7(a) and (b), and number the fragments in each group; when classifying, in order to avoid the occurrence of special situations, carry out precise grouping, add manual intervention guidance, and set the text height Arranged according to the size, the fragments corresponding to the heights with close adjacent values are grouped together;

An example of the height grouping process of manual intervention: the extracted heights are arranged according to size, and the fragments corresponding to the heights with similar adjacent values are grouped together. The method is quite obvious. For example, the first 35 heights are:

It is obvious that the first three heights belong to singular points, and the corresponding fragments should be classified into groups that cannot be grouped. Starting from the third data 42, all the way to 38, a total of 19 data, the size is very similar, can be grouped together. From 28 to later, the heights are also very similar, and they are also grouped together (the data is not fully posted). The 33 in the middle also belongs to the singularity and is included in the group that cannot be grouped. The Chinese fragments given in Figure 6 are divided into 10 groups, except that there are 25 fragments that cannot be grouped (see Table 3, horizontal and vertical cut Chinese paper strip recovery labeling table, shown in bold), and each group of fragments has 17-19 pieces (disordered) , the grouping result is better;

ii) Intra-group matching: perform intra-group matching on the fragments classified in step (i):

(a) Perform left edge detection on all fragments in order to determine whether the fragment is the left edge fragment of the original document: judge whether the left edge of the fragment is blank, if it is blank, the fragment is the left edge of the document, use 72* in the example 10 matrix, detect all fragments, and get 11 fragments on the left edge (there is a blank space on the left edge of the original paper), so the matching initial fragments are determined in each divided height group;

(b) Sorting the fragments according to the edge matching criterion: if the detected left edge fragment exists in the group divided in the process of step i), then use the left edge fragment as the starting point to perform right edge matching on the corresponding grouped fragments ; After determining the left edge of the original document by step (a), determine that the fragment corresponding to the left edge of the document is the first fragment, and display the first fragment and its number; the right edge vector of the first fragment is sequentially connected with The left edge vectors of other fragments are compared and matched until the second fragment matching the right edge of the first fragment is found, and the second fragment and its number are displayed on the right side of the first fragment;

If the fragment at the left edge does not belong to any group, put the fragment on hold first (among the detected fragments at the left edge, 014, 029 and 071 do not exist in any height group), until other groups are matched, follow the original document The upper and lower edge vectors of the left edge fragments are matched into the document;

(c) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe file;

(d) saving the sorting of matching fragments and the corresponding numbering sorting described in step (b) and step (c).

Preferably according to the present invention, human eyes check the recovery of the original horizontal bar document in the step (c), check and verify the recovery result, and find that complete five lines have been matched (the relative vertical position of the specific line is uncertain); one line contains The 18 shards of are perfectly matched, and the last one is missing; there are two rows in the middle of which the match has a wrong match. At this time, manual intervention is required. Among the fragments that cannot be grouped, use the remaining three left-edge fragments to match the groups without left-edge fragments. If there is a match, the edge fragments belong to this group. This determines the grouping of fragments 014 and 029, thereby also determining the grouping of 071, and so on.

iii) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Finally, horizontal paper strips are obtained; comprehensively observe the matching results, as shown in Table 3, it is found that the third group (only 18 fragments) does not match from the sixth fragment, and the seventh group (only 18 fragments) is the last The fragment doesn't match the previous one either. The group in which 014 is located has only 18 fragments, and mismatches appear from the seventh fragment. The group where 029 belongs to is a good match. And 071 just matched the other 18 fragments, so there are only four fragments that cannot be grouped. One of them is the last one in the second row, which the human eye can pick out. The other three are compared with the last correctly matched fragment in the group that does not match. After determining their respective positions, they are matched with the remaining fragments in the group to form a whole row of paper strips. Use the last generated sequential vector to display the picture, observe the recovery result, and the recovery of row fragments is complete.

Table 3 Corresponding labels of splicing and restoration of Chinese horizontal and vertical fragments (bold are fragments that cannot be grouped according to height):

iv) Horizontal paper strips match up and down:

Extract the upper and lower edge vectors of the horizontal paper strips for comparison and matching,

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably, according to the present invention, human eyes check the restored original horizontal bar document in the step (c), and verify the restoration result; due to the existence of line spacing, upper and lower edge blanks may appear after matching within the group, and the upper and lower edge vector comparisons cannot be performed. As shown in the fifth row of fragments in Figure 8, all the fragments in this row cannot be grouped together with other fragments according to their height, and after the matching is completed in the group, the edge comparison cannot be performed because the upper edge is blank. Therefore, after the horizontal paper strips are matched up and down with each other, it is necessary to manually check whether the context of the content is reasonable. If there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters. The final splicing repair result is shown in Figure 9;

② English horizontal and vertical fragments

Due to the morphological characteristics of English letters, it is inaccurate to only detect the highest and lowest positions of letters in the first line. The positioning method of four lines and three grids in Lenovo English homework paper, as shown in Figure 2, chooses to use the positioning line to complete the line matching. According to the position and duty cycle of the standard four lines and three grids, the letters are divided into four heights in advance: occupying the middle grid (such as a, e, etc.), occupying the upper two grids (such as h, l, etc.), and occupying the lower two grids ( Such as y, g, etc.), occupying three grids (j). Before grouping, it is necessary to calculate the heights of different types of letters, and based on this, process the heights of English letters and then group them.

As shown in Figure 10, the letter height is measured by detecting the position where the pixel appears and drawing a line and returning the height value. The returned two sets of line drawing height values are [1,52,90,116,154,180], [1,14,44,83,122,147,171,180]. The scale standard to be used by the algorithm is that the height of the letters occupying the middle grid (i.e. the second and third lines of the standard four lines and three grids) is 171-147=24 pixels, and the height of the letters accounting for the upper (lower) two grids is 90- 52=38 pixels.

According to the characteristics of the four-line grid of English letters, each letter has content in the middle grid, and only some letters have content in the upper and lower two grids. Therefore, finding the second and third lines of the four-line grid can accurately locate the row where the letter is located.

Considering that the content occupying the upper case has obvious morphological characteristics in the vertical direction, with proper processing, except for the upper case occupied by capital letters, other letters can eliminate the content occupied by the upper case.

In addition, considering that the proportion of capital letters and letters occupying the lower cells is relatively small, in a processed fragment, it is almost always possible to find at least one row with only the middle cell. Once such a row is found, it can be calculated according to the Calculate the position of the second and third lines of other rows based on the spacing and height data, so as to achieve height grouping.

First, read in the digital image of the fragments of paper strips, convert them into grayscale images, and perform binarization and inversion processing to highlight the text; then extract the left and right edge vectors and upper and lower edge vectors of each fragment respectively;

Secondly, the height of the debris will be detected; and the fragments on the left edge will be detected in the group to perform intra-group matching; finally, the horizontal paper strips will be matched up and down to restore:

Then, process according to the steps shown in Figure 1(b), determine the position of the second and third lines of the fragments, and group them according to the height of the text; match within the group, and finally match up and down the horizontal paper strips to recover:

i) Fragment preprocessing: In order to determine the position of the letters in each row and offset the height matching error caused by the difference in letter occupancy to the greatest extent, the letters must first be morphologically processed, and the letter parts occupying the upper grid should be eliminated as much as possible, so as to determine The positions of the second and third lines are preprocessed as shown in Figure 11(a-d). Figure 11(a) is after the original image is reversed, and Figure 11(b) is the result of opening operations on fragments using 27*1 structural elements , Figure 11(c) is the result of the subtraction of Figure 11(a) and Figure 11(b), and Figure 11(d) is the result of eliminating the region with a connected domain less than 50 pixels in Figure 11(c).

ii) Determine the position of the second and third lines in the fragments, and group them according to height: firstly, find a line occupying only the middle grid in the processed fragments, and then calculate the position of the second and third lines of the previous line until it exceeds the upper edge. Take the height of the first second line that appears in each fragment as the characteristic height of the fragment, and group based on this, and detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the fragment is a word or a blank, and the first line of characters The position of the highest pixel point appearing at the height of the second line in the fragments is classified into groups, and the fragments in each group are numbered; when classifying, in order to avoid the occurrence of special situations, accurate grouping is carried out, and manual intervention guidance is added to divide the height of the text according to The size is arranged, and the fragments corresponding to the heights with similar adjacent values are grouped together. The grouping results are shown in Table 4.

Table 4 Corresponding labels of splicing and restoration of English horizontal and vertical fragments (bold are fragments that cannot be grouped by height)

iii) Intra-group matching: perform intra-group matching on the fragments classified in step (ii):

(a) carry out left edge detection to fragment in each group, determine that the left edge in each group is the left edge of each line of original document: judge whether fragment in each group is blank, if it is blank, it is the left edge of fragment document;

(b) Match to the right according to the edge matching criterion: if the detected left-edge fragment exists in the divided group in step (ii), then start from the left-edge fragment of the fragment to the right of the corresponding fragment in the group Matching: compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence, until the second horizontal paper strip that matches the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) At this time, manual intervention is required to observe the matching results, take the redundant fragments to the fragment group that cannot be grouped, and search for the missing fragments in the fragment group that cannot be grouped. Since the height distribution is relatively concentrated, it is not difficult to group, and only need to consider individual discontinuous fragments. There are also two left-edge fragments in the fragments that cannot be grouped, which are matched separately, so that the fragments in one group are divided into two rows;

(d) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe file;

(e) saving the sorting of the matching fragments and the corresponding numbering sorting described in step (b) and step (c).

Preferably, according to the present invention, human eyes check the restored original horizontal stripe document in the step (c), and verify the restoration result. Due to the low pixel size of fragments, each group must participate in manual screening during the matching process. When encountering wrong matches, they should be eliminated and corrected again or continue to match after inserting correct fragments;

iv) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Obtain horizontal paper strip at last, obtain 11 horizontal paper strips among Fig. 6;

v) Horizontal paper strips match up and down:

The extracted upper and lower edge vectors of the 11 horizontal paper strips are compared and matched,

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably, according to the present invention, human eyes check the restored original horizontal bar document in the step (c), and verify the restoration result; due to the existence of line spacing, upper and lower edge blanks may appear after matching within the group, and the upper and lower edge vector comparisons cannot be performed. Therefore, after matching the top and bottom of the horizontal paper strips, manual inspection is performed to check whether the context of the document content is reasonable. If there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters. The matching results are shown in Figure 12;

3. Double-sided English horizontal and vertical cut paper fragments

Since the front and back of the fragments are inconsistent, there will be twice the different fragment information of the single-sided paper strip, and 418 different fragments will be produced according to the 2 cutting methods. However, due to the correspondence between the front and back of the fragments, as long as one side is matched, the result expression can be obtained. For one side, the difficulty is: the amount of data is doubled, and the number of each group will greatly increase in the process of highly grouping At the same time, due to the increase of edge blank fragments, the error rate of edge matching increases, which increases the workload of manual error correction. For the comparison of Chinese and English fragments, it can be seen from the 2 solutions that the splicing and restoration of English is much more difficult than Chinese. Therefore, this section chooses to process the fragments of double-sided English horizontal and vertical paper strips. For Chinese double-sided paper strips, it can be processed. Refer to the content of the two parts of the splicing and restoration method of the Chinese horizontal and vertical cut paper fragments in the second part and the splicing and restoration method of the double-sided English horizontal and vertical cuts in the third part.

For the fragments of double-sided paper strips, the solution is as follows: Find all the fragments on the left edge. Manually match the left edge fragments first, then the left edge of each side can be obtained. In the same group, if it contains two left-edge fragments, they will be used as the beginning to match to the right. If an error occurs during the matching process due to blank margins, manual intervention is required to correct the error, and the process will not be repeated; if only one left-edge fragment is included , and the number of fragments in the group is large, it will be used as the beginning of the match; if the number of fragments in the group is small, after other groups are matched, the fragments will be added to the result expression in the form of manual error correction filling.

The splicing and restoration process of double-sided English horizontal and vertical fragments is shown in Figure 1(c):

First, read in the digital image information on the front and back sides obtained from 418 pieces of paper strips. Each piece randomly stipulates that one side is the front side and the other side is the back side. a) and Figure 13(b). And the image is converted into a grayscale image, and the grayscale image is binarized and inverted to highlight the text;

Secondly, carry out height detection, manual assisted grouping; front and back edge detection within the group, matching within the group and manual inspection; vertical matching of horizontal paper strips, splicing and restoration:

i) Fragment preprocessing: In order to obtain the position of each row of letters and offset the height matching error caused by the difference in letter occupancy to the greatest extent, by performing morphological processing on the letters in the fragments, try to eliminate the part of the letter occupying the upper grid, in order to determine the second , Prepare for the third-line position.

ii) Determine the position of the second and third lines in the fragments, and group them according to their heights: first find a line in the processed fragments that only occupies the middle grid, and then calculate the position of the second and third lines of the previous line until it exceeds the upper edge. Take the height of the first second line that appears in each fragment and define it as the characteristic height of the fragment; then detect the position where the characters appear line by line for all fragments, according to whether the upper edge of the character is a word or a blank, and the highest second-line height of the character in the first line The positions of pixels in the fragments are grouped, and the fragments in each group are numbered. 10 groups can be divided, each group has 35-40 fragments, and more than 30 fragments are left in the end; when classifying, in order to avoid special cases occur, add manual intervention guidance, arrange according to the height and size of the text, and group the fragments with similar heights into one group.

iii) Intra-group matching: perform intra-group matching on the fragments classified in step (ii):

(a) Perform left edge detection on the fragments in each group, and determine that the left edge in each group is the left edge of each line of the original document: judge whether the fragments in each group are blank, if it is blank, it is the left edge of the fragment document, in Among the 10 divided groups, 20 starting fragments on the left edge can be determined;

(b) Match to the right according to the edge matching criterion: if the detected left-edge fragment exists in the divided group in step (ii), then start from the left-edge fragment of the fragment to the right of the corresponding fragment in the group Matching: compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence, until the second horizontal paper strip that matches the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) At this time, manual intervention is required to observe the matching results, take the redundant fragments to the fragment group that cannot be grouped, and search for the missing fragments in the fragment group that cannot be grouped. Since the height distribution is relatively concentrated, grouping is not difficult, only individual discontinuous fragments need to be considered. There are also two left-edge fragments in the fragments that cannot be grouped, which are matched separately, so that the fragments in one group are divided into two rows;

(d) According to the edge matching criterion of step (b), compare and match other fragments from left to right according to the numbering order, until the last fragment is matched, and display the matched fragments from left to right according to the matching order, And display their respective numbers to form a restored original horizontal stripe file;

(e) saving the sorting of the matching fragments and the corresponding numbering sorting described in step (b) and step (c).

Preferably, according to the present invention, human eyes check the restored original horizontal stripe document in the step (c), and verify the restoration result. Due to the low pixel size of fragments, each group must participate in manual screening during the matching process. When encountering wrong matches, they should be eliminated and corrected again or continue to match after inserting correct fragments;

iv) In-row adjustment: When matching, select the fragment with the smallest edge difference. If there is no next connected fragment in the group, the wrong fragment will be matched, which will affect the subsequent sorting. Therefore, the in-row adjustment is performed through manual intervention. Finally, 22 horizontal paper strips were obtained, and the matching results of paper A and B sides are shown in Table 5 and Table 6, respectively.

Fragment number corresponding to side A of Table 5

Table 6 side B corresponds to the fragment number

v) Up and down matching of horizontal paper strips: the upper and lower edge vectors of 22 horizontal paper strips obtained in extraction (iv) are compared and matched:

(a) Carry out upper edge detection and lower edge detection sequentially to all horizontal paper strips, to determine whether said horizontal paper strips are upper edge fragments or lower edge fragments of the original document: judge whether the upper edge or the lower edge of the horizontal paper strips are Blank, if it is blank, the horizontal paper strip is a fragment of the upper edge or lower edge of the document;

(b) Vertically sort the horizontal strips according to the edge matching criterion: After determining the upper edge of the original document through step (a), determine the fragment corresponding to the upper edge of the document as the first horizontal strip, and display the first horizontal strip and its Numbering; compare and match the lower edge vectors of the first horizontal paper strip with the upper edge vectors of other fragments in sequence according to the numbering order, until the second horizontal paper strip matching the right edge of the first horizontal paper strip is found. Add the second horizontal paper strip and its serial number to the lower side of the first horizontal paper strip mentioned above;

(c) According to the edge matching criterion of step (b), compare and match other horizontal paper strips from top to bottom according to the numbering order, until the last horizontal paper strip is matched, and the matched horizontal paper strips are sequentially selected according to the matching order Display from top to bottom, and display their respective numbers to form the restored original document;

(d) storing the sorting and corresponding numbering of the matching horizontal paper strips described in step (b) and step (c);

Preferably, according to the present invention, human eyes check the restored original horizontal bar document in the step (c), and verify the restoration result; due to the existence of line spacing, upper and lower edge blanks may appear after matching within the group, and the upper and lower edge vector comparisons cannot be performed. Therefore, after matching the top and bottom of the horizontal paper strips, manual inspection is performed to check whether the context of the document content is reasonable, and if there is any misalignment, appropriate adjustments should be made according to the content of the article and the position of the characters;

vi) From step (v), 11 lines belonging to the same side can be found, and after matching one side of the document, the entire document can be restored, as shown in FIG. 13 .

Claims (1)

1. the splicing restored method of a rectangle character features a scrap of paper, it is characterised in that this restored method bag Include that to cut two-sided paper slip for Chinese and English rip cutting paper slip fragment, Chinese and English transverse and longitudinal cut paper bar fragment and English transverse and longitudinal broken The restored method of sheet:

One, Chinese and English rip cutting paper slip fragment

(1) use scanner to read in Chinese and English rip cutting paper slip fragment digital picture, and image is changed into gray scale Image；

(2) described gray level image is carried out the most respectively binary conversion treatment, the detection of fragment left hand edge, edge matching With display splicing restored image:

A () carries out binary conversion treatment to gray level image: Chinese and English rip cutting paper slip fragment is carried out serial number, Gray level image is read in by computer according to numbering, and carries out binary conversion treatment and negate, and extracts each fragment Left and right edges vector；

B () carries out left hand edge detection successively to fragment in step (a), to determine whether described fragment is original The left hand edge of document: judge whether the fragment left hand edge numbered is blank, if the fragment that blank is then numbered is literary composition Shelves left hand edge；

C () carries out fragment sequence according to edge matching criterion: determine original document left hand edge by step (b) After, determine that the fragment corresponding to document left hand edge is the 1st fragment, show the 1st fragment and numbering thereof；By described The right hand edge vector of the 1st fragment, according to number order, left hand edge vector with other fragment carries out contrast successively Joining, until looking for the 2nd fragment mated with the 1st fragment right hand edge, increasing display on the right side of described 1st fragment 2nd fragment and numbering thereof；

(d) according to the edge matching criterion of step (c) to other fragment according to number order successively by left-to-right Carry out contrast coupling, until matching last fragment, by fragment complete for coupling successively according to matching order Shown by left-to-right, and show respective numbering, form final recovery original document；

E () preserves and mates the sequence of fragment and the number sorting of correspondence described in step (c) and step (d)；

Human eye checks recovery original document final in described step (d), appraises and decides restoration result；

Two, Chinese and English transverse and longitudinal cut paper bar fragment

1. Chinese transverse and longitudinal fragment

First, read in the paper slip fragment digital image information that document transverse and longitudinal is cut, and fragment digital picture is converted into Gray level image, and carry out binaryzation, negate process, extract the most respectively each fragment left and right edges vector, Lower edges vector；

Secondly, fragment height is detected；And in group, detect left hand edge fragment, carry out organizing interior coupling；Finally carry out Laterally paper slip mates up and down, recovers:

I) height of word on fragment is detected: owing to Chinese is Chinese characters, font is the most regular, institute All fragments to be detected line by line the position that character occurs, it is word or blank according to fragment upper edge, Yi Ji The maximum pixel point position that a line character occurs is grouped, and is numbered by the fragment in often group；During packet, In order to avoid the generation of special circumstances, be accurately grouped, add manual intervention instruct, by word height according to Size arranges, and the fragment that the close height of adjacent values is corresponding is classified as one group；

Ii) coupling in group: carry out organizing interior coupling by being grouped complete fragment in step i):

A () carries out left hand edge detection, to determine whether described fragment is original literary composition successively to all fragments in group The left hand edge fragment of shelves: judge whether fragment left hand edge is blank, if blank then fragment is document left hand edge；

B () carries out fragment sequence according to edge matching criterion: if the left hand edge fragment detected is present in step I) in the group divided during, then the fragment of corresponding packet is carried out to the right with this left hand edge fragment for starting point Edge mates；After determining original document left hand edge by step (a), determine the fragment corresponding to document left hand edge It is the 1st fragment, shows the 1st fragment and numbering thereof；By the right hand edge vector of described 1st fragment, according to numbering Order carries out contrast successively and mates with the left hand edge vector of other fragment, mates until looking for the 1st fragment right hand edge The 2nd fragment, the right side of described 1st fragment increase display the 2nd fragment and numbering thereof；

If left hand edge fragment is not belonging to any one packet, the most first shelve this fragment, until having mated other packet After, according to the lower edges vector of the left hand edge fragment of original document, then carry out fitting into document；

(c) according to the edge matching criterion of step (b) to other fragment according to number order successively by left-to-right Carry out contrast coupling, until matching last fragment, by fragment complete for coupling successively according to matching order Shown by left-to-right, and show respective numbering, formed and recover original horizontal stripe document；

D () preserves and mates the sequence of fragment and the number sorting of correspondence described in step (b) and step (c)；

Human eye is checked and is recovered original horizontal stripe document in described step (c), appraises and decides restoration result；

Iii) adjust in row: during coupling, select the fragment that Edge difference is minimum, if next not being connected in group Individual fragment, then can match the fragment of mistake, and then the sequence after influencing whether, therefore pass through manual intervention Mode go interior adjustment, finally obtain horizontal paper slip；

Iv) laterally paper slip mates up and down:

The lower edges vector extracting horizontal paper slip contrasts and mates,

(a) all horizontal paper slips are carried out successively edge detection and lower limb detection, with determine described laterally Whether paper slip is top edge fragment or the lower limb fragment of original document: judge the top edge or below of horizontal paper slip Whether edge is blank, if blank then horizontal paper slip is document top edge fragment or lower limb fragment；

B () carries out the longitudinal direction sequence of horizontal paper slip according to edge matching criterion: determined original by step (a) After document top edge, determine that the fragment corresponding to document top edge is the 1st horizontal paper slip, show the 1st horizontal paper Bar and this paper slip corresponding fragment numbering；By the lower limb vector of the described 1st horizontal paper slip, according to number order Carrying out contrast successively to mate with the top edge vector of other fragment, mating with the 1st horizontal paper slip right hand edge until looking for The 2nd horizontal paper slip, the downside of the described 1st horizontal paper slip increase display the 2nd horizontal paper slip and numbering thereof；

(c) according to the edge matching criterion of step (b) to other horizontal paper slip according to number order successively by upper Contrast coupling is carried out, until matching last horizontal paper slip, by horizontal paper slip complete for coupling successively under to Show from top to bottom according to matching order, and show respective numbering, formed and recover original document；

D () preserves and mates the sequence of horizontal paper slip and the numbering of correspondence described in step (b) and step (c) Sequence；

Human eye checks described step iv) in (c) step recovers original horizontal stripe document, appraise and decide restoration result； 2. English transverse and longitudinal fragment

First, read in paper slip fragment digital picture, and be converted into gray level image, and carry out binaryzation, negate place Reason, highlights word；Extract the left and right edges vector of each fragment, lower edges vector the most respectively；

Secondly, will detection fragment height；And in group, detect left hand edge fragment, carry out organizing interior coupling；The most laggard The horizontal paper slip of row mates up and down, recovers；

Then, it is determined that two or three line positions of fragment, it is grouped according to word height；Mate in group, finally carry out horizontal stroke Mate up and down to paper slip, recover, comprise the following steps i)-v)

I) fragment pretreatment: want to determine often row character position, at utmost offsets because of letter occupy-place different band The matched error come, first to carry out Morphological scale-space to letter, be disappeared by the letter part occupying upper lattice as far as possible Remove, in order to determine the position of second and third line；

Ii) the two or three line position in fragment is determined, according to height packet: fragment the most after treatment is found Only account for a line of middle lattice, the most up calculate two or three line positions of lastrow, until beyond top edge；Take every First two wires height of one fragment appearance, as the feature height of this fragment, is grouped on this basis, All fragments are detected line by line the position that character occurs, is word or blank according to fragment upper edge, and first The maximum pixel point that line character two wires height occurs position in fragment is grouped, and by the fragment in often group It is numbered；During packet, in order to avoid the generation of special circumstances, accurately it is grouped, adds manual intervention and refer to Leading, arranged according to size by word height, the fragment that the close height of adjacent values is corresponding is classified as one group；

Iii) coupling in group: by step ii) in be grouped complete fragment and carry out organizing interior coupling:

A () carries out left hand edge detection, to determine whether described fragment is original literary composition successively to all fragments in group The left hand edge fragment of shelves: judge whether fragment left hand edge is blank, if blank then fragment is document left hand edge；

B () carries out fragment sequence according to edge matching criterion: if the left hand edge fragment detected is present in step Ii) in the group divided during, then the fragment of corresponding packet is carried out to the right with this left hand edge fragment for starting point Edge mates；After determining original document left hand edge by step (a), determine the fragment corresponding to document left hand edge It is the 1st fragment, shows the 1st fragment and numbering thereof；By the right hand edge vector of described 1st fragment, according to numbering Order carries out contrast successively and mates with the left hand edge vector of other fragment, mates until looking for the 1st fragment right hand edge The 2nd fragment, the right side of described 1st fragment increase display the 2nd fragment and numbering thereof；

If left hand edge fragment is not belonging to any one packet, the most first shelve this fragment, until having mated other packet After, according to the lower edges vector of the left hand edge fragment of original document, then carry out fitting into document；

(c) according to the edge matching criterion of step (b) to other fragment according to number order successively by left-to-right Carry out contrast coupling, until matching last fragment, by fragment complete for coupling successively according to matching order Shown by left-to-right, and show respective numbering, formed and recover original horizontal stripe document；

D () preserves and mates the sequence of fragment and the number sorting of correspondence described in step (b) and step (c)；

Human eye checks described step iii) (c) step recovers original horizontal stripe document, appraise and decide restoration result；

Iv) adjust in row: during coupling, select the fragment that Edge difference is minimum, if next not being connected in group Individual fragment, then can match the fragment of mistake, and then the sequence after influencing whether, therefore pass through manual intervention Mode go interior adjustment, finally obtain horizontal paper slip；

V) laterally paper slip mates up and down:

The lower edges vector extracting horizontal paper slip contrasts and mates,

(a) all horizontal paper slips are carried out successively edge detection and lower limb detection, with determine described laterally Whether paper slip is top edge fragment or the lower limb fragment of original document: judge the top edge or below of horizontal paper slip Whether edge is blank, if blank then horizontal paper slip is document top edge fragment or lower limb fragment；

B () carries out the longitudinal direction sequence of horizontal paper slip according to edge matching criterion: determined original by step (a) After document top edge, determine that the fragment corresponding to document top edge is the 1st horizontal paper slip, show the 1st horizontal paper The numbering of bar correspondence fragment；By the lower limb vector of the described 1st horizontal paper slip, according to number order successively with its The top edge vector of its fragment carries out contrast coupling, until looking for the 2nd mated with the 1st horizontal paper slip right hand edge Laterally paper slip, increases display the 2nd horizontal paper slip and numbering thereof in the downside of the described 1st horizontal paper slip；

(c) according to the edge matching criterion of step (b) to other horizontal paper slip according to number order successively by upper Contrast coupling is carried out, until matching last horizontal paper slip, by horizontal paper slip complete for coupling successively under to Show from top to bottom according to matching order, and show respective numbering, formed and recover original document；

D () preserves and mates the sequence of horizontal paper slip and the numbering of correspondence described in step (b) and step (c) Sequence；

Human eye is checked and is recovered original horizontal stripe document in described step v) in (c) step, appraises and decides restoration result；

Three, English transverse and longitudinal cuts two-sided paper slip fragment

First, the positive and negative digital image information obtained by paper slip fragment reads in, and image is converted into gray-scale map Picture, carries out binaryzation and inversion operation by gray level image, highlights word；

Secondly, carrying out height detection, human assistance is grouped；Positive and negative rim detection in group, coupling people in group Work checks；Laterally paper slip mates up and down, carries out splicing and restores:

I) fragment pretreatment: in order to obtain the position of often row letter, at utmost offset letter occupy-place different band The matched error come, occupies the letter of upper lattice by letter in fragment carries out Morphological scale-space elimination as far as possible Part, for determining that second and third line position is prepared；

Ii) the two or three line position in fragment is determined, according to being highly grouped: fragment the most after treatment is sought Look for a line only accounting for middle lattice, the most up calculate two or three line positions of lastrow, until beyond top edge；Take First two wires height that each fragment occurs is defined as the feature height of this fragment；Then to all fragments by The position that row detection character occurs, is word or blank according to character upper edge, and the first row character two wires is high The maximum pixel point that degree occurs position in fragment is grouped, and is numbered often organizing internal fragment；Packet Time, in order to avoid the generation of special circumstances, add manual intervention and instruct, arrange according to word height size, Fragment close for height is classified as one group；

Iii) coupling in group: by step ii) in be grouped complete fragment and carry out organizing interior coupling:

A () carries out left hand edge detection to often organizing internal fragment, determine that the left hand edge in every group is original document often row Left hand edge: judge often whether group internal fragment is blank, if blank is then the left hand edge of fragment document；

B () mates to the right according to edge matching criterion: if the left hand edge fragment detected is present in step ii) In the group divided, then fragment corresponding in this group is mated to the right with this fragment left hand edge fragment for starting point； By the lower limb vector of the 1st horizontal paper slip, according to number order, top edge vector with other fragment is carried out successively Contrast coupling, until look for the 2nd horizontal paper slip mated with the 1st horizontal paper slip right hand edge, described 1st horizontal The downside of paper slip increases display the 2nd horizontal paper slip and numbering thereof；

C () now needs manual intervention, observe matching result, unnecessary fragment is taken the fragment that cannot be grouped In Qun, the fragment lacked is found in the fragment group that cannot be grouped；Owing to concentration is compared in height distribution, so point Group difficulty is little, only need to consider indivedual discontinuous fragment；The fragment that cannot be grouped also there are two left hand edges broken Sheet, mates respectively, thus the fragment in a packet has separated two row respectively；

(d) according to step (b) edge matching criterion to other fragment according to number order successively by left-to-right enter Row contrast coupling, until match last fragment, by fragment complete for coupling successively according to matching order by Left-to-right show, and show respective numbering, formed and recover original horizontal stripe document；

E () preserves and mates the sequence of fragment and the number sorting of correspondence described in step (b) and step (c)；

Human eye checks described step iii) in (c) step recovers original horizontal stripe document, appraise and decide restoration result；

Iv) adjust in row: during coupling, select the fragment that Edge difference is minimum, if next not being connected in group Individual fragment, then can match the fragment of mistake, and then the sequence after influencing whether, therefore pass through manual intervention Mode go interior adjustment, finally obtain horizontal paper slip；

V) laterally paper slip mates up and down: the lower edges vector extracting horizontal paper slip contrasts and mates,

(a) all horizontal paper slips are carried out successively edge detection and lower limb detection, with determine described laterally Whether paper slip is top edge fragment or the lower limb fragment of original document: judge the top edge or below of horizontal paper slip Whether edge is blank, if blank then horizontal paper slip is document top edge fragment or lower limb fragment；

B () carries out the longitudinal direction sequence of horizontal paper slip according to edge matching criterion: determined original by step (a) After document top edge, determine that the fragment corresponding to document top edge is the 1st horizontal paper slip, show the 1st horizontal paper Bar and numbering thereof；By the lower limb vector of the described 1st horizontal paper slip, according to number order successively with other fragment Top edge vector carry out contrast coupling, until look for the 2nd horizontal paper slip mated with the 1st horizontal paper slip right hand edge, Display the 2nd horizontal paper slip and numbering thereof is increased in the downside of the described 1st horizontal paper slip；

(c) according to the edge matching criterion of step (b) to other horizontal paper slip according to number order successively by upper Contrast coupling is carried out, until matching last horizontal paper slip, by horizontal paper slip complete for coupling successively under to Show from top to bottom according to matching order, and show respective numbering, formed and recover original document；

D () preserves and mates the sequence of horizontal paper slip and the numbering of correspondence described in step (b) and step (c) Sequence；

Human eye is checked and is recovered original horizontal stripe document in described step v) in (c) step, appraises and decides restoration result；

Vi) can be found by step v) and belong to all of row of the same face, mate the one side of document, Restore whole document.