DE19615211A1

DE19615211A1 - Reconstruction of time information in hand written character identification

Info

Publication number: DE19615211A1
Application number: DE19615211A
Authority: DE
Inventors: Stefan Jaeger
Original assignee: Daimler Benz AG
Current assignee: Siemens AG
Priority date: 1996-04-18
Filing date: 1996-04-18
Publication date: 1997-10-23

Abstract

The automatic identification of hand written characters uses a time based reconstruction process that is based upon data obtained by optical scanning. The data is processed to obtain a digital line image that is defined in terms of line segments with end and crossing points. Crossing points between segments and the direction of the segments are used to assign weightings that are used in a learning process

Description

Die Erfindung betrifft ein Verfahren zur Rekonstruktion der Zeitinformation einer Handschriftvorlage.The invention relates to a method for reconstruction the time information of a manuscript template.

Für die automatische Erkennung handschriftlicher Zeichen oder Zeichenfolgen ist es bekannt, daß die Kenntnis des zeitlichen Verlaufs des Schriftzugs die Erkennungsleistung wesentlich fördert. Oft ist aber nur ein statisches Bild einer Handschriftvorlage verfügbar (Off-line-Erkennung). Es sind daher schon verschiedene Ansätze zur Rekonstruk tion der Zeitinformation der Handschriftvorlage, d. h. des vermutlichen zeitlichen Verlaufs des Schriftzugs aus dein statischen Bild gemacht worden. For the automatic recognition of handwritten characters or strings it is known that knowledge of the recognition over time significantly promotes. But often it's just a static picture a handwriting template available (off-line recognition). There are therefore different approaches to reconstruction tion of the time information of the manuscript template, d. H. of presumed chronological progression of the lettering from your static picture has been taken.

In [1] ist ein Verfahren beschrieben, welches die einzel nen Kreuzungspunkte einer Liniendarstellung des Schrift bildes, insbesondere einer Polygonapproximation, nach vor gegebenen Kriterien auflöst in durchgehende Linien. Ein wesentliches Kriterium ist der zwischen zwei Liniensegmen ten an einem Kreuzungspunkt eingeschlossene Richtungswin kel. Das Verfahren birgt vor allem Unsicherheiten bei Ver zweigungspunkten ohne klar dominierende durchgehende Linie und berücksichtigt kaum die bei Handschrift häufige dop pelte Liniendurchfahrung und Richtungsumkehr.In [1] a method is described, which the individual crossing points of a line representation of the font image, especially a polygon approximation, before given criteria resolves into solid lines. On the essential criterion is that between two line segments directional winds enclosed at a crossing point kel. The process harbors uncertainties in Ver branching points without a clearly dominating solid line and hardly takes into account the dop that is common in handwriting line crossing and reversal of direction.

Bei dem in [2] beschriebenen Verfahren wird ebenfalls auf der Basis einer Polygonapproximation ein Weg durch den Schriftzug bestimmt, der jeden Linienabschnitt mindestens einmal durchschreitet und bezüglich der Gesamtweglänge ein Minimum gegenüber anderen Weglängen aufweist (sogenanntes Chinese Postman Problem). Zu offen endenden Seitenlinien können für die formale mathematische Beschreibung paral lele Hilfslinien eingeführt werden. Eine Reihe zusätzli cher Kriterien sind bei der Durchschreitung des Schrift zugs zu beachten. Dieses Vorgehen ist auf Besonderheiten der arabischen Schrift abgestellt und führt bei anderen Handschriften nicht zu zufriedenstellenden Ergebnissen.The method described in [2] is also based on a path through the base of a polygon approximation Lettering determines the minimum of each line section passes through once and with regard to the total path length Minimum compared to other path lengths (so-called Chinese Postman problem). To open side lines can paral for the formal mathematical description All guidelines are introduced. A number of additional The criteria are when walking through the script train. This procedure is based on peculiarities turned off the Arabic script and leads to others Manuscripts did not produce satisfactory results.

Das in [3] beschriebene Verfahren sieht die Zerlegung der Liniendarstellung des Schriftbilds in eine Vielzahl von Grundelementen (primitives) vor, deren Aufeinanderfolge wiederum durch eine Reihe von Regeln bestimmbar sein soll. Die Vorgabe von Grundelementen und Regeln ist problema tisch und die Problemlösung kaum mathematisch formulier bar. The procedure described in [3] provides for the decomposition of the Line representation of the typeface in a variety of Basic elements (primitives), their sequence in turn should be determinable by a number of rules. The specification of basic elements and rules is problematic table and the problem solving hardly formulated mathematically bar.

Ebenfalls mathematisch schwer formulierbar ist ein Ansatz aus (4), bei welchem aus einer Vielzahl von Einzelheiten des Pixelbilds nach globalen, regionalen und lokalen Re geln der Zeitverlauf des Schriftzugs rekonstruiert werden soll. Die lokal anzuwendenden Regeln dominieren den Ent scheidungsprozeß.One approach is also difficult to formulate mathematically from (4), in which from a variety of details the pixel image according to global, regional and local re the time course of the lettering can be reconstructed should. The locally applicable rules dominate the Ent divorce process.

Aufgabe der vorliegenden Erfindung ist es, ein weiteres Verfahren zur Rekonstruktion der Zeitinformation einer Handschriftvorlage anzugeben. Insbesondere ist auch ein Verfahren angestrebt, das mathematisch gut formulierbar ist.The object of the present invention is another Process for the reconstruction of the time information of a Specify handwriting template. In particular is also a Aimed for procedures that can be formulated well mathematically is.

Die Erfindung ist im Patentanspruch 1 beschrieben. Die Un teransprüche enthalten vorteilhafte Ausgestaltungen und Weiterbildungen der Erfindung.The invention is described in claim 1. The Un Claims contain advantageous refinements and Developments of the invention.

Das erfindungsgemäße Verfahren behandelt die Rekonstruk tion der Zeitinformation als für den gesamten betrachteten Schriftzug globales Optimierungsproblem und kann auf lo kale Interpretationsregeln verzichten. An einem Kreu zungspunkt wird nicht eine Einzelentscheidung über den weiteren Verlauf getroffen, sondern alle möglichen Über gänge auf ein anderes Segment sind zulässig und werden mit im Regelfall unterschiedlichen Kostengewichten belastet. Die Entscheidung über einen einzelnen Kreuzungspunkt wird im Rahmen der globalen Optimierung gefällt. Wesentlich ist, daß die Übergänge zwischen Segmenten bewertet werden. In einer bevorzugten Ausführungsform wird die Rekonstruk tion der Zeitinformation formal auf ein graphentheoreti sches Standardproblem, daß sogenannte Travelling Salesman Problem (TSP) zurückgeführt.The method according to the invention deals with the reconstruction tion of the time information as for the entire considered Lettering global optimization problem and can be lo no rules of interpretation. On a cross The point of reference will not be an individual decision on the further course hit, but all possible over Moves to another segment are permitted and are included in the usually charged different cost weights. The decision on a single crossing point is made as part of global optimization. Essential is that the transitions between segments are evaluated. In a preferred embodiment, the reconstruction tion of the time information formally on a graph theory Standard problem, the so-called traveling salesman Problem (TSP) attributed.

Die Erfindung ist nachfolgend anhand von Beispielen unter Bezugnahme auf die Abbildungen noch eingehend veranschau licht. Dabei zeigt:The invention is based on examples below Reference to the pictures in detail light. It shows:

Fig. 1 ein Pixelbild eines handgeschriebenen Buchstabens Fig. 1 is a pixel image of a handwritten letter

Fig. 2 eine Skelettdarstellung der Fig. 1 FIG. 2 shows a skeleton representation of FIG. 1

Fig. 3 die Fig. 2 mit einem zugehörigen Line-Graphen Fig. 3 shows Fig. 2 with an associated line graph

Fig. 4 den Line-Graphen der Fig. 3 allein Fig. 4 shows the line graph of Fig. 3 alone

Fig. 5A den mit Kostengewichten versehenen Line-Graphen Fig. 5A provided with the cost weights line graphs

Fig. 5B den vervollständigten Line-Graphen Fig. 5B the completed line-graph

Fig. 5C den um einen Hilfsknoten erweiterten vollständigen Line-Graphen Fig. 5C to an auxiliary node complete line graphs extended

Fig. 6 ein Beispiel für eine Winkelbewertung Fig. 6 shows an example of an angle evaluation

Fig. 7 die Zerlegung eines längeren Schriftzugs in Teil probleme Fig. 7 the decomposition of a longer lettering in part problems

Fig. 8A-C ein weiteres Beispiel einer handgeschriebenen Buchstabens und dessen Line-Graphen. FIGS. 8A-C another example of a handwritten character and the line graph.

Das Pixelbild der Fig. 1 stellt ein rechtwinkliges Schwarz-Weiß Punktraster eines handgeschriebenen Buchsta bens "s" dar. Das erfindungsgemäße Verfahren geht vorzugs weise von einer Liniendarstellung wie in Fig. 2 aus, die aus dem Pixelbild der Fig. 1 durch eines von mehreren be kannten Verfahren zur sogenannten Skelettierung von Schriftbildern (z. B. [5], [6]) abgeleitet ist. Der Schriftzug kann unterteilt werden in mehrere Linienseg mente, die Eckpunkte, z. B. A, D, F in Fig. 2 und Kreuzungs punkte, in denen drei oder mehr Segmente zusammenlaufen, z. B. B, C, E in Fig. 2, verbinden.The pixel image of FIG. 1 represents a right-angled black and white dot matrix of a handwritten letter "s". The method according to the invention is preferably based on a line representation as in FIG. 2, which is derived from the pixel image of FIG. 1 by one of several known processes for the so-called skeletonization of typefaces (e.g. [5], [6]) is derived. The lettering can be divided into several line segments, the corner points, e.g. B. A, D, F in Fig. 2 and crossing points in which three or more segments converge, for. B. B, C, E in Fig. 2, connect.

Für die Rekonstruktion der Zeitinformation des Schriftzugs wird ein Weg durch das Linienbild bestimmt, welcher jedes Liniensegment mindestens einmal durchläuft. Eine Rich tungseinschränkung braucht dabei nicht vorgenommen werden, ergibt sich aber zum Teil implizit durch die Annahme, daß bei einem längeren Schriftzug mit mehreren Zeichen diese in einer Schreibrichtung, z. B. von links nach rechts fortlaufend aufeinanderfolgen. Es ist weiter als zulässig betrachtet, daß durch Richtungsumkehr ein Segment unmittelbar nacheinander in entgegengesetzten Richtungen durchlaufen wird.For the reconstruction of the time information of the lettering a path through the line image is determined, which each Line segment runs through at least once. A rich there is no need to restrict the but is implicit in part by the assumption that with a longer lettering with several characters this in a writing direction, e.g. B. from left to right consecutively. It is further than allowed considered that by reversing direction a segment immediately one after the other in opposite directions is going through.

Das Überwechseln von einem Segment auf ein anderes Segment durch Durchqueren eines gemeinsamen Kreuzungspunkt sei als Übergang bezeichnet. Durch die a priori uneingeschränkten Übergangsmöglichkeiten ergibt sich in der Problemstellung eine Mehrzahl von Wegen, welche die Bedingung, jedes Seg ment mindestens einmal zu durchlaufen, erfüllen. Die Ent scheidung, welcher der möglichen Wege vermutlich derjenige ist, der zu dem untersuchten Schriftbild geführt hat, wird als globale Optimierungsaufgabe behandelt, indem erfin dungsgemäß jedem Übergang von einem Segment auf ein an deres ein Kostengewicht zugewiesen wird und der Weg be stimmt wird, dessen Kostengewichtssumme gegenüber anderen Wegen ein Minimum einnimmt. Die Kostengewichte werden vor zugsweise von bei einem Übergang erfolgenden Richtungsän derung abhängig zugewiesen.The transition from one segment to another segment by crossing a common crossing point as Referred to transition. Through the a priori unrestricted Transition options arise in the problem a variety of ways that meet the condition of each seg ment to go through at least once. The Ent divorce, which of the possible paths is probably the one which led to the examined typeface treated as a global optimization task by inventing According to each transition from one segment to one to which a cost weight is assigned and the route is true, its cost weight sum compared to others Because of a minimum. The cost weights are before preferably from direction changes occurring during a transition assigned dependent.

Die Bestimmung der Richtungsabweichung zweier Segmente an einem gemeinsamen Kreuzungspunkt kann nach an sich bekann ten Verfahren erfolgen, z. B. wie in [1], wo auch eine Be wertungsfunktion für die Richtungsänderung angegeben ist, die aber nur zur lokalen Entscheidungsfindung dient. Eine solche Abhängigkeit zugewiesener Kostengewichte von einer Richtungsänderung der Schriftzugslinie soll die Gewohnhei ten beim Schreiben berücksichtigen. Hierbei kann insbeson dere eine Abhängigkeit vorgegeben werden, bei welcher die Kostengewichte von einem Maximum für eine 90-Grad-Rich tungsänderung nach Null Grad und nach 180 Grad hin jeweils monoton fallen. Die Abhängigkeit der Kostengewichte von der Richtungsänderung kann auch vorteilhaft aus Trainings-Schriftproben, deren originale Zeitinformation bekannt ist, abgeleitet werden, z. B. indem häufiger auftretenden Richtungsänderungswinkeln geringere Kostengewichte zugewiesen werden als weniger häufig auftretenden, oder indem die Kostengewichtszuweisung auf maximale Rekonstruk tionsleistung bei Anwendung auf die Trainings-Schriftpro ben abgestimmt wird.The determination of the directional deviation of two segments a common crossing point can be known per se ten procedures take place, for. B. as in [1], where a Be evaluation function for the change of direction is specified, which only serves for local decision making. A such dependency of assigned cost weights on one Change of direction of the lettering line is said to be the habit Take into account when writing. Here, in particular a dependency is specified, in which the Cost weights of a maximum for a 90 degree rich change after zero degrees and after 180 degrees each fall monotonously. The dependence of the cost weights on the change of direction can also be advantageous from training script samples, whose original time information is known is derived, e.g. B. by occurring more frequently Direction change angles lower cost weights be assigned as less common, or by assigning the cost weight to maximum reconstruction performance when applied to the training font pro ben is voted.

Zur Lösung der Optimierungsaufgabe wird vorteilhafterweise die Liniendarstellung der Fig. 2 des Schriftzugs überführt in eine sogenannte Line-Graph-Darstellung. Diese Transfor mation ist veranschaulicht in Fig. 3, wo die Linienseg mente jeweils durch Buchstabenpaare AB, BC, BE, . . . der durch die Segmente jeweils verbundenen beiden Eck und/oder Kreuzungspunkte A bis F bezeichnet sind. Für die Line-Graph-Darstellung werden die Segmente als Knoten des Line-Graphen behandelt. Knoten des Line-Graphen, deren zu gehörige Segmente der Liniendarstellung in einem Kreu zungspunkt zusammentreffen, sind im Line-Graph durch eine als Kante bezeichnete Linie unmittelbar verbunden. Den einzelnen Kanten des Line-Graphs kann daher jeweils genau ein zulässiger Segmentübergang der Liniendarstellung zuge ordnet und auch dessen jeweiliges Kostengewicht zugewiesen werden. In Fig. 4 ist der aus Fig. 2 gemäß Fig. 3 gebil dete Line-Graph allein und in Fig. 5A mit zugewiesenen Ko stengewichten C(ABC), C(BCD), etc. dargestellt. Für den Line-Graph der Fig. 5A ist die Optimierungsaufgabe in äquivalenter Weise so zu lösen, daß ein Weg durch den Line-Graphen bestimmt wird, der jeden Knoten mindestens einmal enthält und dessen Summe der Kostengewichte aller dabei durchlaufener Kanten ein Minimum einnimmt. Es muß nicht jede Kante durchlaufen werden und es können Kanten mehrfach, auch unmittelbar aufeinanderfolgend und in entgegengesetzten Richtungen durchlaufen werden. Die Kostengewichte mehrfach durchlaufener Kanten werden dabei (ebenso wie die Kostengewichte mehrfach erfolgter Über gänge bei der Liniendarstellung) mehrfach gezählt.To solve the optimization task, the line representation of FIG. 2 of the lettering is advantageously converted into a so-called line graph representation. This transformation is illustrated in FIG. 3, where the line segments are each represented by letter pairs AB, BC, BE,. . . of the two corner and / or crossing points A to F connected by the segments are designated. For the line graph display, the segments are treated as nodes of the line graph. Line graph nodes whose associated segments of the line representation meet at a crossing point are directly connected in the line graph by a line called an edge. The individual edges of the line graph can therefore be assigned exactly one permissible segment transition to the line representation and its respective cost weight can also be assigned. In Fig. 4, the line graph formed from FIG. 2 according to FIG. 3 is shown alone and in FIG. 5A with assigned cost weights C (ABC), C (BCD), etc. are shown. For the line graph of FIG. 5A, the optimization task is to be solved in an equivalent manner in such a way that a path through the line graph is determined which contains each node at least once and the sum of the cost weights of all edges traversed thereby takes a minimum. Not every edge has to be traversed, and edges can be traversed several times, also directly in succession and in opposite directions. The cost weights of multiple traversed edges are counted several times (as are the cost weights of multiple transitions in the line display).

Gemäß einem weiteren vorteilhaften Schritt wird der ur sprüngliche Line-Graph der Fig. 5A, dessen Kanten unmit telbare Übergänge zwischen zwei Segmenten des Schriftzugs repräsentieren, durch Ergänzungskanten zu einem vollstän digen Line-Graph, d. h. einem Line-Graph, bei welchem jeder Knoten mit jedem anderen Knoten unmittelbar durch eine Kante verbunden ist ergänzt. Die Ergänzungskanten reprä sentieren mittelbare Segmentwechsel in der Liniendarstel lung über mindestens ein weiteres Segment. Den Ergänzungs kanten werden wiederum Kostengewichte zugewiesen, die je weils als Kostensumme des kostengünstigsten Verbindungs wegs im ursprüngliche Line-Graphen bestimmt werden.According to a further advantageous step, the original line graph of FIG. 5A, the edges of which represent immediate transitions between two segments of the lettering, is made up of supplementary edges to form a complete line graph, ie a line graph in which each node is associated with every other node is directly connected by an edge. The supplementary edges represent indirect segment changes in the line representation over at least one further segment. The supplementary edges are again assigned cost weights, each of which is determined as the cost of the least expensive connection path in the original line graph.

Im skizzierten Beispiel der Fig. 5B, in welcher einige der Ergänzungskanten mit größerer Strichbreite eingezeichnet sind (der Übersichtlichkeit halber sind die Ergänzungskan ten BE-CD und BC-EF nicht eingezeichnet), wäre beispiels weise das Kostengewicht C(ABCD) der Ergänzungskante zwi schen Knoten AB und CD gleich der Summe der Kostengewichte C(ABC) und C(BCD) unter der Annahme, daß im ursprünglichen Line-Graphen der Fig. 5A der kostengünstigste Weg (d. h. der Weg mit der geringsten Kostengewichtssumme der durch laufenen Kanten) von AB über BC nach CD führt.In the sketched example of FIG. 5B, in which some of the supplementary edges are drawn with a larger stroke width (for the sake of clarity, the supplementary edges BE-CD and BC-EF are not shown), the cost weight C (ABCD) of the supplementary edge would be between, for example Nodes AB and CD are equal to the sum of the cost weights C (ABC) and C (BCD), assuming that in the original line graph of FIG. 5A, the most cost-effective route (ie the route with the lowest total cost weight of the through edges) of AB leads via BC to CD.

Für den vollständigen Line-Graph der in Fig. 5B skizzier ten Art stellt sich die Optimierungsaufgabe so, daß der Weg durch den Line-Graphen bestimmt wird, der jeden Knoten genau einmal enthält und ein Minimum der Kostengewichts summe der durchlaufenen Kanten aufweist. Bei einem solchen Weg wird keine Kante mehrfach durchlaufen.For the complete line graph of the type sketched in FIG. 5B, the optimization task arises in such a way that the path through the line graph is determined, which contains each node exactly once and has a minimum of the cost weight sum of the edges traversed. With such a path, no edge is run through multiple times.

Schließlich wird der vollständige Line-Graph der in Fig. 5B skizzierten Art noch vorteilhafterweise nach Art der Fig. 5C durch einen Hilfsknoten P erweitert der mit jedem Knoten des vollständigen Line-Graph über eine Hilfskante in unterbrochenen Linien verbunden ist. Der besondere Vor teil dieses Schrittes liegt darin, daß damit die Optimie rungsaufgabe mit der Suche nach einem jeden Knoten genau einmal enthaltenden geschlossenen Pfad (Rundweg) durch den erweiterten Line-Graph wiederum unter Minimierung der Ko stengewichtssumme auf eine besonders eingehend untersuchte Graphentheoretische Problemstellung des sogenannten "Tra velling Salesman Problems" gebracht ist und für die Lösung dieser Formulierung der Optimierungsaufgabe auf eine große Zahl von Lösungsansätzen zurückgegriffen werden kann, ohne die erfindungswesentliche Bewertung der Segmentübergänge aufgeben zu müssen. Die Rundreise im Travelling Salesman Problem ist äquivalent einem Hamilton-Zyklus mit minimalem Gewicht in einem vollständigen Graphen.Finally, the complete line graph of the type outlined in FIG. 5B is advantageously expanded in accordance with the type of FIG. 5C by an auxiliary node P which is connected to each node of the complete line graph via an auxiliary edge in broken lines. The special part of this step lies in the fact that the optimization task with the search for a closed path (circular path) containing each node exactly once through the extended line graph in turn minimizing the sum of the cost weights on a particularly thoroughly investigated graph theoretical problem of the so-called "Traveling salesman problems" and a large number of possible solutions can be used to solve this formulation of the optimization task without having to give up the evaluation of the segment transitions that is essential to the invention. The tour in the Traveling Salesman problem is equivalent to a Hamilton cycle with minimal weight in a complete graph.

Das Ergebnis der Optimierungsaufgabe in der letztgenannten Formulierung liefert einen Rundweg durch den erweiterten Line-Graphen. Die auf diesem Rundweg über je eine Hilfs kante mit dem Hilfsknoten P verbundenen Knoten des Line-Graph werden als Startknoten und als Schlußknoten eines nicht geschlossenen optimalen Weges durch den Line-Graph behandelt. Aus diesem Weg durch den Line-Graph läßt sich unmittelbar ein Weg durch die Liniendarstellung mit einem Startsegment und einem Schlußsegment ableiten. Die Seg mentfolge dieses Wegs enthält die gesuchte Zeitinformation des Schriftzugs. Aus der bis dahin symmetrischen Betrach tung wird im Regelfall eine eindeutige Variante durch die bei gegebener Schriftart vorgegebene Schreibrichtung, z. B. von links nach rechts in lateinischer Schrift, unter scheidbar sein. Bei Einzelzeichen können andere aus dem Stand der Technik bekannte Kriterien, z. B. typische Strichformen an Startpunkten und Schlußpunkten von Schriftzügen hilfsweise mit herangezogen oder beide symme trische Lösungen der Zeichenerkennung unterworfen werden.The result of the optimization task in the latter Formulation provides a circular route through the extended Line graphs. The one on this circular route via an auxiliary edge of the line graph connected to the auxiliary node P. are used as a start node and as a final node not closed optimal path through the line graph treated. This way through the line graph can be immediately a path through the line representation with a Derive the starting segment and a closing segment. The seg The sequence of this route contains the time information you are looking for the lettering. From the previously symmetrical view tion is usually a clear variant by the given writing direction given writing direction, e.g. B. from left to right in Latin script, below be divorced. In the case of single characters, others from the State-of-the-art criteria, e.g. B. typical Line shapes at start and end points of Letters used in the alternative or both symme trical solutions of character recognition are subjected.

Für einfache Schleifen innerhalb des Schriftzugs wie in Fig. 6 dargestellt ergibt sich bei der Zuweisung eines Ko stengewichts für den Übergang zwischen dem Schleifenseg ment L und einem am Kreuzungspunkt K zusammentreffenden normalen Liniensegment S die Situation, daß prinzipiell zwei Übergänge (Pfeillinien in Fig. 6) geometrisch unter scheidbar sind und wegen unterschiedlicher Richtungsände rungen verschiedene Kostengewichte c(SL)₁ und c(SL)₂ zuzu weisen wären, was der formale Lösungsweg aber nicht vor sieht. Eine bevorzugte Ausführungsform sieht hierzu vor, daß für den Übergang zwischen dem normalen Liniensegment und dem Schleifensegment das kleinere dieser beiden Ko stengewichte zugewiesen wird, c(SL) = Min (c(SL)₁, c(SL)₂). Gemäß einer anderen Ausführungsform kann das Schleifensegment durch einen fiktiven Trennpunkt in zwei Teilsegmente (z. B. L₁, L₂) aufgespalten werden, denen dann die beiden für das Schleifensegment in Frage kommenden Ko stengewichte eindeutig zuweisbar sind. Das Kostengewicht für den Übergang zwischen den Teilsegmenten ist niedrig, vorzugsweise gleich Null zu setzen. Vorzugsweise wird zur Bestimmung der Winkel eine approximierte Liniendarstellung mit aus Geradenstücken zusammengesetztem Schriftzug wie in Fig. 6 verwandt.For simple loops within the lettering as shown in FIG. 6, the assignment of a cost weight for the transition between the loop segment L and a normal line segment S meeting at the crossing point K results in the situation that in principle two transitions (arrow lines in FIG. 6 ) are geometrically distinguishable and different cost weights c (SL) ₁ and c (SL) ₂ would have to be assigned due to different changes in direction, but the formal solution does not provide for this. A preferred embodiment provides that for the transition between the normal line segment and the loop segment the smaller of these two Ko weight weights is assigned, c (SL) = Min (c (SL) ₁, c (SL) ₂). According to another embodiment, the loop segment can be split by a fictitious separating point into two sub-segments (z. B. L₁, L₂), which then the two possible Ko weight weights for the loop segment can be clearly assigned. The cost weight for the transition between the subsegments is low, preferably zero. An approximated line representation with a lettering composed of straight lines as in FIG. 6 is preferably used to determine the angles.

Bei der Darstellung der Optimierungsaufgabe mit einem Hilfsknoten nach Art der Fig. 5C sind den Hilfskanten zur formalen Problemlösung ebenfalls Kostengewichte zuzuwei sen. Hierfür werden vorteilhafterweise zwei Situationen unterschieden, die anhand der Fig. 7 erläutert werden.In the representation of the optimization task with an auxiliary node of the type shown in FIG. 5C, the auxiliary edges for formal problem solving must also be assigned cost weights. For this purpose, two situations are advantageously distinguished, which are explained with reference to FIG. 7.

In Fig. 7 liegt der Name "Duxbury" handschriftlich mit ei nem isolierten Anfangsbuchstaben "D" und einem mit durch gehender Linie geschriebenen Rest "uxbury" in Liniendar stellung vor. Eck- und Kreuzungspunkte sind eingetragen aber nicht näher bezeichnet. Für den längeren Wortteil ist zweifelsfrei das Vorliegen einer Zeichenfolge anzunehmen, für deren gesamten Schriftzug wegen der Schreibrichtung von links nach rechts der Startpunkt im linken Bereich und der Schlußpunkt im rechten Bereich zu suchen ist. Auf die ser Basis wäre die Zahl der möglichen Wege bereits einge schränkt. Die Zahl der Liniensegmente und damit der Knoten des Line-Graph wäre aber hoch und die formale Lösung der Optimierungsaufgabe damit sehr aufwendig. Es ist daher sinnvoll die Untersuchung des langen Schriftzugs in Tei laufgaben zu zerlegen. Hierfür wird der längere Schriftzug so in aufeinanderfolgende Abschnitte zerlegt, daß die Li nienführung von einem Abschnitt zum nächsten eindeutig ist. Die durch die senkrechten Linien markierten Schnitt stellen auf der Schriftlinie werden jeweils nur einmal von links nach rechts durchlaufen. Verfahren zu einer solchen Zerlegung sind an sich bekannt. Besonders vorteilhaft ist es, aus der vorgegebenen Schreibrichtung (z. B. von links nach rechts) einen Wortanfang und ein Wortende abzuleiten und Schnittstellen derart in Liniensegmente einzufügen, daß an der Schnittstelle auf beiden Seiten des Schriftzugs diesselbe Zusammenhangsgebiet (Kontur) vorliegt und von den beiden durch das durchschnittene Liniensegment verbun denen Kreuzungspunkten der eine näher am Wortanfang und der andere näher am Wortende liegt. Die mittleren Ab schnitte weisen dann ein eindeutiges Eingangssegment und ein eindeutiges Ausgangssegment auf und die Optimierungs aufgabe wird für jeden Abschnitt separat gelöst, wobei je weils Anfangssegment und Schlußsegment vorgegeben sind. Die links und rechts endständigen Abschnitte zeigen inso fern eine Besonderheit, als hierbei um dem Ergebnis der Rekonstruktionsoptimierung nicht vorzugreifen, eventuell mehrere Startsegmente bzw. Schlußsegmente vorgegeben und die daraus resultierenden mehreren Ergebnisse der Optimie rung nochmals untereinander verglichen werden können.In Fig. 7, the name "Duxbury" is handwritten with an isolated initial letter "D" and a remainder written with a continuous line "uxbury" in line representation. Corner and intersection points are entered but are not specified. For the longer part of the word, there is no doubt that a character string is available, for the entire writing of which, due to the writing direction from left to right, the starting point in the left area and the closing point in the right area must be found. On this basis, the number of possible routes would already be restricted. However, the number of line segments and thus the nodes of the line graph would be high and the formal solution to the optimization task would therefore be very complex. It is therefore sensible to break down the examination of the long lettering into subtasks. For this purpose, the longer lettering is broken down into successive sections so that the line guidance from one section to the next is clear. The intersections marked by the vertical lines on the text line are only run once from left to right. Methods for such a decomposition are known per se. It is particularly advantageous to derive a word beginning and a word end from the specified writing direction (e.g. from left to right) and to insert interfaces in line segments in such a way that the same context area (contour) is present at the interface on both sides of the lettering and from the both intersected by the intersected line segment where the intersection is one closer to the beginning of the word and the other closer to the end of the word. The middle sections then have a clear input segment and a clear exit segment, and the optimization task is solved separately for each section, with the start segment and the end segment being specified in each case. The left and right end sections show a peculiarity in that, in order not to prejudge the result of the reconstruction optimization, it is possible to specify several start segments or end segments and the resulting multiple results of the optimization can be compared again.

Die Abschnitte mit vorgegebenem Startsegment und Schluß segment stellen den einen der genannten beiden Fälle bei der Zuweisung von Kostengewichten zu den Hilfskanten dar. Da die Optimierungsaufgabe nicht zu einer Lösung führen soll, welche einen Weg mit anderem Start- und/oder Schluß segment als den vorgegebenen als Ergebnis liefern soll, werden in einer solchen Situation den Hilfskanten, die zu den dem vorgegebenen Start- bzw. Schlußsegment entspre chenden Knoten des Line Graph führen, geringe Kostenge wichte, vorzugsweise nicht höher als das niedrigste Ko stengewicht des vollständigen Line-Graphen (Fig. 5B) ins besondere gleich Null, und den übrigen Hilfskanten hohe Kostengewichte, insbesondere höher als das höchste Kosten gewicht des vollständigen Line-Graphen, zugewiesen.The sections with a given start segment and end segment represent one of the two cases mentioned when assigning cost weights to the auxiliary edges. Since the optimization task should not lead to a solution which involves a path with a different start and / or end segment than the specified one should deliver as a result, in such a situation, the auxiliary edges leading to the nodes of the line graph corresponding to the predetermined start or end segment are low cost weights, preferably not higher than the lowest cost weight of the complete line graph ( FIG . 5B) in particular zero, and the other auxiliary edge high cost weights, notably higher than the highest cost weight of the complete line graphs assigned.

Der andere der beiden Fälle bei der Zuweisung von Kosten gewichten zu den Hilfskanten ist typischerweise bei der Betrachtung von Einzelzeichen wie dem "D" in Fig. 7 gege ben, wo kein Anfangssegment und kein Schlußsegment sicher vorgebbar ist. Zu diesem Fall werden vorzugsweise allen Hilfskanten gleiche Kostengewichte, die auch gleich Null sein können, zugewiesen.The other of the two cases when assigning cost weights to the auxiliary edges is typically given when considering individual characters such as the "D" in FIG. 7, where no start segment and no end segment can be reliably specified. In this case, all auxiliary edges are preferably assigned the same cost weights, which can also be zero.

In Fig. 8A ist als weiteres Beispiel ein handschriftliche Buchstabe B im Pixelbild dargestellt. Fig. 8B zeigt die daraus abgeleitete Liniendarstellung (Skelett) mit Knoten und Kanten des Line-Graphen, der in Fig. 8C mit Ergän zungskanten (punktiert) vervollständigt und durch Hilfs knoten P und Hilfskanten (unterbrochene Linien) erweitert ist.In Fig. 8A, a handwritten letter B is displayed in the pixel image as another example. Fig. 8B shows the derived line representation (skeleton) with nodes and edges of the line graph, which is completed in Fig. 8C with supplementary edges (dotted) and extended by auxiliary nodes P and auxiliary edges (broken lines).

Die Erfindung ist nicht auf die beschriebenen Beispiele beschränkt und insbesondere mit weiteren Verfahren der Er kennung von handschriftlicher Information kombinierbar. The invention is not based on the examples described limited and in particular with other Er identification of handwritten information can be combined.

literature

[1] Boccignone, Chianese, Cardella, Marcelli: "Recove ring Dynamic Information From Static Handwriting" in Pattern Recognition, Vol. 26, No. 3, pp. 409-418, 1993
[2] Abuhaiba, Ahmed: "Restoration of Temporal Informa tion In Off-Line Arabic Handwriting" in Pattern Recognition, Vol. 26, No. 7, pp. 1009-1017, 1993
[3] Govindaraju, Wang, Srihari: "Using Temporal Infor mation In Off-Line Word Recognition" USPS Advanced Technology Conference, pp. 529-543, 1992
[4] Doermann, Rosenfeld: "Recovery Of Temporal Infor mation From Static Images on Handwriting", Procee dings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition 1992, pp. 162-168
[5] E. Mandler, M.F. Oberländer: "A Single Pass Algo rithm for Fast Contour Coding of Binary Images Proceedings of the 12th DAGM-Symposium, pp. 248-255, 1990 (in german)
[6] P. Kwok: "A Thinning Algorithm by Contour Genera tion", Communications of the ACM, Vol. 31, No. 11, pp. 1314-1324, 1988[1] Boccignone, Chianese, Cardella, Marcelli: "Recove ring Dynamic Information From Static Handwriting" in Pattern Recognition, Vol. 26, No. 3, pp. 409-418, 1993
[2] Abuhaiba, Ahmed: "Restoration of Temporal Information In Off-Line Arabic Handwriting" in Pattern Recognition, Vol. 26, No. 7 , pp. 1009-1017, 1993
[3] Govindaraju, Wang, Srihari: "Using Temporal Information In Off-Line Word Recognition" USPS Advanced Technology Conference, pp. 529-543, 1992
[4] Doermann, Rosenfeld: "Recovery Of Temporal Information From Static Images on Handwriting", Procee dings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition 1992, pp. 162-168
[5] E. Mandler, MF Oberländer: "A Single Pass Algo rithm for Fast Contour Coding of Binary Images Proceedings of the 12th DAGM-Symposium, pp. 248-255, 1990 (in German)
[6] P. Kwok: "A Thinning Algorithm by Contour Generation", Communications of the ACM, Vol. 31, No. 11, pp. 1314-1324, 1988

Claims

1. Method for the reconstruction of the time information of a manuscript template with the following features

- From the ge obtained by optical scanning of the original image endpoints and crossing points as well as these connecting line segments are determined within a coherent lettering
- A cost weight is assigned to all possible transitions between two segments over a common crossing point
- A path is determined by the lettering, which runs through each segment at least once and the cost-weight sum of all transitions made in this way takes a minimum compared to other paths.

2. The method according to claim 1, characterized in that the cost weights depending on the angle the segments involved in the transition at the cross include point of delivery.

3. The method according to claim 2, characterized in that the maximum cost weights for an angle of 90 degrees are and drop monotonically after 0 degrees and after 180 degrees.

4. The method according to claim 2, characterized in that the cost weights from learning samples with given time information mation can be determined.

5. The method according to any one of claims 1 to 4, characterized characterized in that the representation of the lettering with Line segments and crossing points in a line graph representation is transferred in which the line segment elements through nodes and the transitions between line segments elements through edges between the assigned nodes are presented, and that a way through the line graph is determined which contains each node at least once and its total cost weight in this way traversed edges a minimum compared to others Because of occupies.

5. The method according to claim 5, characterized in that the line graph with supplementary edges between originally Lich not directly connected nodes to a full constant graph is added, with the supplementary edges Cost weights are assigned that are equal to the sum of the Cost weights of the edges of the cheapest are indirect path in the original line graph, and that determines a path through the full line graph that contains each node exactly once and a mini mum of the cost weight sum.

7. The method according to claim 6, characterized in that an auxiliary node and auxiliary edges from this to all nodes of the full line graph are introduced and a closed circular route through the complete line graph with auxiliary nodes and auxiliary edges that each Ent nodes including the auxiliary node exactly once stops (traveling salesman problem).

8. The method according to claim 7, characterized in that All auxiliary edges are assigned the same cost weights the.

9. The method according to claim 7, characterized in that from the complete line graph a pair of nodes as Start node and be specified as the final node and the Auxiliary edges to these two nodes low cost weights that are not higher than the lowest cost importance of the line graph, and the other auxiliary edges high Cost weights that are higher than the highest cost importance of the full line graph.