DE19803127A1

DE19803127A1 - Document reassembly method for shredded document sheet

Info

Publication number: DE19803127A1
Application number: DE19803127A
Authority: DE
Inventors: Gerd Stanke; Frank Ksciuk; Christian Feist
Original assignee: FOERDERUNG ANGEWANDTER INFORMA
Current assignee: FOERDERUNG ANGEWANDTER INFORMA
Priority date: 1998-01-28
Filing date: 1998-01-28
Publication date: 1999-08-05

Abstract

The document assembly device allows the original document sheet to be reassembled from the shredded strips obtained from a document shredder, using image detection and image processing for identifying information contained within the document, with evaluation of partial printed characters along the strip edges, for matching up the corresponding strips. An Independent claim for a shredded document sheet reassembly device is also included.

Description

Die vorliegende Erfindung betrifft ein Verfahren und eine Vorrichtung zum Zusam menfügen, d. h. virtuellen Wiederherstellen von durch Aktenvernichter in Streifen zerlegten Dokumenten.The present invention relates to a method and an apparatus for together add, d. H. Virtual restore from shredders to strips disassembled documents.

Die Erfindung liegt im Bereich des Zusammenfügens, Wiederherstellens von irrtümlich oder absichtlich durch Aktenvernichter in Streifen geschnittenen Dokumenten. Dieser Prozeß tritt z. B. bei Schreibtischaufräumungsarbeiten auf, wobei häufig größere Anzahlen von Dokumentenseiten gleichzeitig vernichtet werden, so daß im Vernichter ein unübersichtlicher Wust von Streifen entsteht, der nicht oder aber nur mit extremem Aufwand wieder geordnet werden kann. Das erfindungsgemäße Verfahren und die Vorrichtung lassen die Automatisierung dieses Prozesses zu.The invention is in the field of assembling, restoring erroneously or deliberately cut into strips by shredders Documents. This process occurs e.g. B. on desk clearing up, often large numbers of document pages are destroyed at the same time are so that in the annihilator there is a confusing mess of stripes, the cannot be arranged again or only with extreme effort. The The inventive method and the device allow automation of this Process too.

Im Stand der Technik ist bekannt, daß per Hand versucht werden kann, Dokumente, die in Streifen zerlegt sind, wieder zusammenzufügen. Dies ist ein aufwendiger Prozeß. Die Deutsche Patentanmeldung (DE 44 04 795 A1) befaßt sich für den Bereich der Archäologie mit dem Zusammenpuzzeln von unregelmäßig geformten Scherben, wobei dafür die Information über den Kantenverlauf genutzt wird. Die Veröffentlichungen Lit. [1]: Freemann, H. "Computer methods for the processing, classifying, and matching of profiles and other irregular curves" aus "Computers and their potential applications in Museums", Arno Press, New York, 1968, Seiten 237- 258; und Lit [2]: Freemann, H: "Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition", IEEE Trans. on Electronic Computers, Vol. EC- 13, 2, April 1964, Seiten 118-127 beschreiben eine Kodierung, die erlaubt, den Kantenverlauf z. B. von Scherben, in Bildern eindeutig zu charakterisieren. Allgemeine Verfahren zur Wiedererkennung, nicht aber zur Wiederherstellung von streifig zerlegten Dokumenten, werden z. B. in US-PS 5142 590 und EP-PS 04222 45 A1 beschrieben. Für das Aufnehmen und Abspeichern von räumlich auch in der dritten Dimension ausgedehnten Scherben ist in Lit. [3]: R. Slabatnig, Ch. Menard "Stereo and Structured Light as Acquisition Methods in the Field of Achaeology", Informatik aktuell/Mustererkennung 1992, Springer Verlag Seiten 398-404 ein Verfahren beschrieben. Im Stand der Technik sind kommerzielle OCR-Systeme (Optical Character Recognition-Systeme; Textbridge von Xerox; Recognita u.v.a.) zu berücksichtigen, die mit beachtlicher Leistungsfähigkeit in der Lage sind, bildlich vorliegende Textinformation in symbolische Textinformation zu überführen.It is known in the prior art that documents, which are broken down into stripes. This is an expensive one Process. The German patent application (DE 44 04 795 A1) deals with the Area of archeology with the piecing together of irregularly shaped Shards, whereby the information about the edge course is used for this. The Publications Ref. [1]: Freemann, H. "Computer methods for the processing, classifying, and matching of profiles and other irregular curves "from" Computers and their potential applications in Museums ", Arno Press, New York, 1968, pages 237- 258; and Lit [2]: Freemann, H: "Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition ", IEEE Trans. on Electronic Computers, Vol. EC- 13, 2, April 1964, pages 118-127 describe a coding which allows the Edge course z. B. of broken glass, to clearly characterize in pictures. General procedures for recognizing, but not for restoring stripped documents, z. B. in US-PS 5142 590 and EP-PS 04222 45 A1 described. For the recording and storage of space also in the The third dimension of extended shards is in Ref. [3]: R. Slabatnig, Ch. Menard "Stereo and Structured Light as Acquisition Methods in the Field of Archeology", Computer Science Current / Pattern Recognition 1992, Springer Verlag pages 398-404 Procedure described. Commercial OCR systems are in the prior art (Optical Character Recognition Systems; Textbridge from Xerox; Recognita and many more) to be taken into account, who are capable of remarkable performance, figuratively convert existing text information into symbolic text information.

Nachteilig an den oben aufgeführten Verfahren (Lit. [1], Lit. [2], DE 44 04 795 A1) ist, daß sie originär auf der Erhebung einer charakteristischen Konturinformation aufbauen, diese aber für den hier beschriebenen Anwendungsbereich genau nicht relevant und nutzbar ist, da alle Streifen in einer bestimmten Auflösung eine identische Konturinformation (Länge/Breite; langgestrecktes Rechteck) tragen. Vorteilhaft an der Erfindung ist, daß die Fragmente der Symbole der Buchstaben erkannt werden, und diese Fragmente gemäß Inhalt und Position zu einem Kode gebildet werden können. Der Kode wiederum erlaubt zwischen einzelnen Streifen Ähnlichkeiten, die dem Wiederherstellungsprozeß dienen, zu berechnen. Nachteilig an den in (Lit. [3]) beschriebenen Verfahren ist, daß sie die dreidimensionale Reliefinformation aufnehmen, die für den erfindungsgemäß betrachteten Fall keine Rolle spielt. Die eingeführten OCR-Systeme arbeiten genau dann fehlerhaft, wenn die auf den Buchstaben bezogene Bildinformation, so wie in dem erfindungsgemäß angesprochenen Prozeß, unvollständig ist, das ist nachteilig.A disadvantage of the processes listed above (Ref. [1], Ref. [2], DE 44 04 795 A1) is that they were originally based on the collection of characteristic contour information build, but not exactly for the application described here is relevant and usable since all stripes have a certain resolution carry identical contour information (length / width; elongated rectangle). An advantage of the invention is that the fragments of the symbols of the letters are recognized, and these fragments according to content and position to a code can be formed. The code in turn allows between individual strips Calculate similarities that serve the recovery process. Disadvantageous of the methods described in (Lit. [3]) is that they are the three-dimensional Relief information that none for the case considered according to the invention Role play. The OCR systems that have been introduced are malfunctioning precisely when the image information related to the letters, as in the invention process mentioned, is incomplete, that is disadvantageous.

Es ist daher Aufgabe der vorliegenden Erfindung, ein Verfahren und eine Vorrichtung zu schaffen, die es gestatten, durch Aktenvernichter in Streifen zerlegte Dokumente automatisiert wiederherzustellen, d. h. virtuell zusammenzufügen.It is therefore an object of the present invention, a method and a To create a device that allows it to be cut into strips by shredders Automatically restore documents, d. H. put together virtually.

Die Lösung dieser Aufgabe erfolgt erfindungsgemäß durch ein Verfahren und eine Vorrichtung mit dem in Anspruch 1 bzw. 15 angegebenen Merkmalen.This object is achieved according to the invention by a method and a Device with the features specified in claim 1 or 15.

Vorteilhafte Ausgestaltungen der Erfindung ergeben sich aus den jeweiligen Unteransprüchen.Advantageous embodiments of the invention result from the respective Subclaims.

Weitere Einzelheiten und Vorteile von Ausführungsbeispielen der Erfindung ergeben sich aus der nachfolgen Beschreibung unter Verweis auf die angefügten Zeichnungen.Further details and advantages of exemplary embodiments of the invention result derive from the following description with reference to the attached Drawings.

Fig. 1 Teilweise vereinfachter Gesamtaufbau einer Ausführungsform einer erfindungsgemäßen Vorrichtung zum Zusammenfügen von in Streifen zer legten Seiten unter Nutzung einer Bilderfassung sowie Bildverarbeitung und Bildauswertung Fig. 1 Partially simplified overall structure of an embodiment of an apparatus according to the invention for assembling pages laid out in strips using an image capture as well as image processing and image evaluation

Fig. 2 Beispiele von nacheinander oder gleichzeitig aufgenommenen Streifen, die in Symbolen, hier Buchstaben, aufgebrachte Informationen tragen Fig. 2 examples of successively or simultaneously recorded strips that carry information applied in symbols, here letters

Fig. 3 Zwischenresultat der Bildverarbeitung über den in der Fig. 2 gezeigten Beispielen, überlagert mit dem Originalbild und verdeutlichend die charakteristischen Schnittstellen der aufgebrachten Informationen an den Streifenrändern der Streifenabschnitte, weiß gekennzeichnet, Hervorhebung von die konkrete Streifensituation charakterisierenden Informationen, die zur Kodierung weiterverarbeitet werden. Fig. 3 Intermediate result of the image processing over the examples shown in Fig. 2, superimposed with the original image and clarifying the characteristic interfaces of the information applied to the stripe edges of the stripe sections, marked in white, highlighting information characterizing the specific stripe situation, which is further processed for coding .

Fig. 4 Eine Beispiel für die inhaltliche und damit verknüpfte ortsbezogene Kodierung für die Streifenelemente aus Fig. 2 mit beliebigem Anfangspunkt FIG. 4 shows an example of the content-related and associated location-based coding for the strip elements from FIG. 2 with any starting point

Fig. 5 Beispiel für ein Ergebnis der virtuellen Streifenzusammenführung, zur Verdeutlichung noch mit einem Abstand zwischen den einzelnen Streifen behaftet Fig. 5 example of a result of the virtual stripe merging, for clarification still with a distance between the individual strips

Fig. 6 Vorteilhafte Ausführungsform einer Vorrichtung mit bewegter Streifenzu führung Fig. 6 Advantageous embodiment of a device with moving Streifenzu leadership

Fig. 1 zeigt den Gesamtaufbau einer Ausführungsform einer erfindungsgemäßen Vorrichtung zum Zusammenfügen von in Streifen zerlegten Seiten unter Nutzung einer Aufnahmeeinrichtung (1) sowie Bildverarbeitung und Bildauswertung in einer nicht näher beschriebenen Auswerte- und Speichereinrichtung (3). Die Aufnahmeeinrichtung (1) nimmt ein Bild der Streifen (4) vor einem geeignet gestalteten, z. B. grauen Hintergrund (5), der auch fehlen kann, auf und leitet dieses Bild an eine hier nicht weiter ausgeführte Auswerte- und Speichereinheit (3), die ein Personalcomputer sein kann, weiter. Die Beleuchtungseinrichtung (2), die auch spektrale Besonderheiten aufweisen kann, unterstützt die Aufnahmeeinrichtung (1) bei der Gewinnung vorteilhaft auswertbarer Bilder. Fig. 1 shows the overall construction of an embodiment of an inventive apparatus for joining cut in stripes side by using a receiving device (1) as well as image processing and image evaluation in an unspecified evaluating and storing means (3). The recording device ( 1 ) takes a picture of the strips ( 4 ) in front of a suitably designed, for. B. gray background ( 5 ), which may also be missing, and forwards this image to an evaluation and storage unit ( 3 ), which may be a personal computer. The lighting device ( 2 ), which can also have special spectral characteristics, supports the recording device ( 1 ) in obtaining images that can be advantageously evaluated.

Eine typische Darstellung der durch die Aufnahmeeinrichtung (1) an die Auswerte- und Speichereinrichtung (3) weitergeleiteten Bilder zeigt die Fig. 2, wobei in dieser Abbildung eine Differenzierung in der bildlichen Informationsdarstellung der aufgebrachten Symbole, hier Buchstaben, Streifen und Hintergrund um den Streifen zu sehen ist. Diese Differenzierung in der Darstellung wird durch die Auswerte- und Speichereinrichtung (3) genutzt, um mit nicht weiter ausgeführten und bekannten Bildverarbeitungsoperationen eine Hervorhebung charakteristischer Stellen im Bild zu erhalten, vgl. Fig. 3, die ein Zwischenresultat, das in der weißen Überlagerung die Stellen enthält, die zur orts- und inhaltsbezogenen Kodierung verarbeitet werden können, darstellt.A typical representation of the images forwarded by the recording device ( 1 ) to the evaluation and storage device ( 3 ) is shown in FIG. 2, in which figure a differentiation in the pictorial information representation of the symbols applied, here letters, stripes and background around the stripe you can see. This differentiation in the representation is used by the evaluation and storage device ( 3 ) in order to obtain a highlighting of characteristic points in the image with known image processing operations which are not further developed, cf. Fig. 3, which shows an intermediate result, which contains in the white overlay the places that can be processed for location and content-related coding.

Die Fig. 4 zeigt ein mögliches Kodierungsbeispiel im Ergebnis der Bildauswertung durch die Auswerte- und Speichereinrichtung (3) für das Bildbeispiel mit den Streifenabschnitten (6) in Fig. 2. Die Positionssymbole der Kodierung (9) "l", "m" und "r" können für Positionen, z. B. Zeilennummern, stehen, die addierten Zahlen, die hier im Beispiel ganzzahlig sind, allgemein aber reelle Zahlen sein können, geben eine relative Positionslängenzuwachs an, der für die hier nicht weiter ausgeführte Kodierungsvorschrift und damit Streifenkodierung genutzt werden kann. Aus den Symbolen (7), den Informationsinhalten und Positionen dieser Informations inhalte auf den Streifen ergeben sich ausreichend viele unterschiedliche Kombinationsmöglichkeiten, so daß der Ähnlichkeitsvergleich durch die Auswerte- und Speichereinrichtung (3) zu einer hinreichend eingeschränkten Antwortmenge führt. Werden z. B. im Mittel 20 verschiedene erkennbare Symbole (Informationsinhalte) angenommen und solche an 10 unterschiedlichen Positionen (Zeilen) gefunden, ergeben sich ca. 10×10¹² Kombinationen, das entspricht ca. 2×10¹⁰ Schreibmaschinenseiten, abhängig von der physisch vorliegenden Streifenbreite. Informationen, die sich aus den erkannten Schriftfonts, aus Grauwertprofilen oder gewonnenen spektralen Signalen ergeben, können als Kodierungsergänzung verwendet werden und damit eine weitere Einschränkung des Suchraumes ergeben. FIG. 4 shows a possible coding example as a result of the image evaluation by the evaluation and storage device ( 3 ) for the image example with the stripe sections ( 6 ) in FIG. 2. The position symbols of the coding ( 9 ) "l", "m" and "r" can be used for positions, e.g. B. line numbers, the added numbers, which in this example are integers, but can generally be real numbers, indicate a relative increase in position length, which can be used for the coding rule and thus strip coding not described here. The symbols ( 7 ), the information content and the positions of this information content on the strips result in a sufficient number of different possible combinations, so that the comparison of similarity by the evaluation and storage device ( 3 ) leads to a sufficiently restricted response set. Are z. Accepted as different in the means 20 identifiable symbols (information content), and those found at 10 different positions (lines), there are approximately 10 × 10 ¹² combinations, corresponding to about 2 x 10 ¹⁰ typewritten pages, depending on the physically present strip width. Information that results from the recognized fonts, from gray value profiles or obtained spectral signals can be used as a coding supplement and thus result in a further restriction of the search space.

Das Ergebnis einer virtuellen Zusammenführung der Streifenabschnitte (6) zeigt die Fig. 5. In dieser wird die Wiederverwertbarkeit, d. h. Lesbarkeit der Information der virtuell hergestellten Dokumente demonstriert.The result of a virtual merging of the strip sections ( 6 ) is shown in FIG. 5. This demonstrates the recyclability, ie readability, of the information of the virtually produced documents.

Die Fig. 6 zeigt eine vorteilhafte Ausführungsform der erfindungsgemäßen Vorrichtung, in der ergänzend zur Fig. 1 die Streifen (4) durch eine Bewegungs- und Zuführungseinrichtung (10) in das Blickfeld der Aufnahmeeinrichtung (1), die in diesem Falle vorteilhaft durch eine Zeilenkamera realisiert sein kann, geführt werden. Fig. 6 shows an advantageous embodiment of the device according to the invention, in addition to the Fig. 1, the strip (4) by a motor and supply means (10) in the field of view of the receiving device (1), which advantageously in this case by a line camera can be realized.

Reference list

11

Aufnahmeeinrichtung
Reception facility

22nd

Beleuchtungseinrichtung
Lighting device

33rd

Auswerte- und Speichereinrichtung
Evaluation and storage device

44th

Streifen
Stripes

55

Hintergrund
background

66

Streifenabschnitte
Strip sections

77

aufgebrachte, im Bild sichtbare Symbole, Informationen
applied symbols, information visible in the picture

88th

hervorgehobene Bereiche der Symbole an den Streifengrenzen
highlighted areas of the symbols at the stripe boundaries

99

abstrakte Positionssymbole für Positionen auf dem Streifen
abstract position symbols for positions on the strip

1010th

Bewegungs- und Zuführungseinrichtung
Movement and feeding device

Claims

1. Process for assembling documents broken down into strips using an image capture as well as image processing and image evaluation with the further features that

- There is information on the document that visibly differs from the background of the document
- At least one gray-scale image is recorded per strip with the partial information located on it
- The recorded images are processed and evaluated in such a way that the applied and disturbed on the strip edges symbols, informa tion are highlighted, they are determined in their position so that they for the comparative search using a coding in a descriptive amount of all processed strips can serve.

2. The method according to claim 1 characterized, that the recorded image contains only two intensity levels, e.g. B. light stripe background and darkly applied symbols.

3. The method according to claim 1 characterized, that the captured image contains only three intensity levels, e.g. B. light stripe background, gray surroundings of the paper strip and dark on Striped symbols.

4. The method according to claim 1 characterized, that the information disturbed at the edges of the strip as symbol fragments be recognized as such a class of possible symbols are assigned, which in turn is a partner class of the likely to be added Owns symbol fragments.

5. The method according to claim 1 characterized, that the symbol fragments obtained according to claim 4 for all lines into one Code are summarized in which also the relative positions on the Stripes come along and that to a significant restriction of the search leads to the search for partner strips.

6. The method according to claim 1 characterized, that the lines of the symbols disturbed at the edges of the stripes for all lines recognized and determined in their position, so that from the determined Positions a location code can be formed, this location code contains on the Same or similar elements along the associated partner strip.

7. The method according to claim 1 characterized, that the gray scale profiles near the left and near the right outer Strip edge, if special information is contained (e.g. gray scale images), in encoding is included to narrow the search space (available yes / no) and all the more so with known methods (e.g. correlation) to make quick decisions about togetherness comparative strip to come.

8. The method according to claim 1 characterized, that a recognizable line feed is estimated in written documents, the can be used to restrict search space and accordingly as Code element is used.

9. The method according to claim 1 characterized, that special characteristics (e.g. font used, font characteristics) all completely existing symbols are included in the coding of the strips become.

10. The method according to claim 1 characterized, that for two strips of the symbol fragments and line ends the Symbol fragments that are recognized and determined in their position, and further coding information, a similarity measure is calculated.

11. The method according to claim 1 characterized, that images of similar stripes are positioned and displayed on a screen be compared visually and complemented in context can.

12. The method according to claim 1 characterized, that the stripes are recorded in several spectral channels and this information is also used for coding.

13. The method according to claim 1 characterized, that the strips are picked up on both sides and used for further processing become.

14. The method according to claim 1 characterized, that the images to be fed to the evaluation and storage unit different reception facilities arise.

15. Apparatus for assembling documents broken down by document shredders into strips using image capture and image processing and evaluation, with the further features that the strips ( 4 ) are positioned under a recording device ( 1 ) in such a way that an image or partial image of the Strip ( 6 ), in which the applied symbols ( 7 ) are visible, receives and forwards them to the evaluation and storage device ( 3 ), in which the applied symbols ( 7 ) are determined in their arrangement so that they act as a code for the Stripes ( 4 ) or the stripe areas can be stored and stored and a similarity or fit can be calculated between all these codes by the evaluation and storage device ( 3 ).

16. The apparatus according to claim 15, characterized in that the lighting ( 2 ) and the background ( 5 ) are designed so that exactly a two-level image in which the relevant information applied is visible can be recorded by the recording device ( 1 ).

17. The apparatus according to claim 15, characterized in that the lighting ( 2 ) and the background ( 5 ) are designed so that in the image recorded by the recording device ( 1 ) three separate levels of information arise, the stripes ( 4 ), symbols applied ( 7 ) and background ( 5 ) are allowed to be separated from each other.

18. The apparatus according to claim 15, characterized in that the strips ( 4 ) are placed and moved by a movement and feed device ( 10 ) and moved under a recording device ( 1 ), so that the recording device ( 1 ) optionally a surface or line camera , in which the second dimension can arise through movement in time.

19. The apparatus according to claim 15, characterized in that the receiving device ( 1 ) realizes spectral channels.