DE69231049T2

DE69231049T2 - Bildverarbeitung

Info

Publication number: DE69231049T2
Application number: DE69231049T
Authority: DE
Inventors: Daniel P Huttenlocher; Peter C. Wayner
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1991-07-30
Filing date: 1992-07-30
Publication date: 2000-09-14
Anticipated expiration: 2012-07-31
Also published as: EP0526197B1; DE69231049D1; JP3346795B2; EP0526197A2; US5416851A; JPH05258058A; EP0526197A3

Description

Die vorliegende Erfindung betrifft die Bildverarbeitung.
Fischler, M.A. und Bolles, R.C. "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography," Communications of the ACM, Vol. 24, No. 6, June 1981, pp. 381-395 beschreiben ein Paradigma zum Anpassen eines Modells auf experimentelle Daten.
US-A-4,817,186 gibt Techniken zum Lokalisieren von einzelnen Bildern in einem Feld an. US-A-4,783,826 beschreibt Musterinspektionstechniken, während US-A-4,747, 1501/2 die Bildverarbeitungstechniken beschreibt.
Die vorliegende Erfindung gibt eine Bildverarbeitungstechnik an, die eine Eigenschaft eines Bildes durch das zufällige oder pseudozufällige Abtasten von das Bild definierenden Daten mißt. Anstatt die Bildeigenschaft relativ zu allen Bildpositionen zu messen, mißt die Technik die Bildeigenschaft relativ zu einem zufällig oder pseudozufällig ausgewählten Teilsatz der Bildpositionen. Die Ergebnisse werden kombiniert, um Meßdaten für die Bildeigenschaft des Bildes zu erhalten.
Ein Aspekt der vorliegenden Erfindung betrifft wie in Anspruch 1 definiert ein Grundproblem bei der Analyse eines Bildes. Herkömmliche Bildanalysetechniken teilen ein Bild in Pixel auf und operieren auf Daten, welche jedes Pixel des Bildes definieren. Ein typisches Bild umfaßt jedoch eine sehr große Anzahl von Pixeln, so daß dieser Ansatz einen hohen Rechenaufwand mit sich bringt.
Dieser Aspekt basiert weiterhin auf der Entdeckung einer Technik, welche dieses Problem vermindert. Die Technik tastet eine Anzahl von Positionen in einem Bild oder einem Segment eines Bildes zufällig oder pseudozufällig ab, wobei die abgetasteten Positionen hier als ein "Probesatz" bezeichnet werden. Deshalb kann die Technik eine Eigenschaft eines ganzen Bildes messen, ohne auf Daten zu operieren, die jede Position des Bildes definieren.
Die zufällige Auswahl vermeidet ein Aliasing, das aus einer nicht zufälligen Auswahl entstehen könnte. Wenn zum Beispiel Positionen in einem regelmäßigen oder gleichmäßigen Muster ausgewählt werden, kann ein regelmäßig oder gleichmäßig auftretendes Merkmal in einem Bild ignoriert oder falsch interpretiert werden, wenn es in einem Muster auftritt, so daß keine seiner Erscheinungen an einer Position in dem Probesatz auftritt oder so daß seine Erscheinungen an allen Positionen in dem Probesatz, aber an keinen anderen Positionen auftreten.
Die zufällige Abtasttechnik kann durch ein zufälliges oder pseudozufälliges Erzeugen einer Zahl, die eine Position in dem Bild angibt, und das darauffolgende Messen einer Eigenschaft für die angegebene Position implementiert werden. Dann kann eine andere Zahl erzeugt werden, und die Eigenschaft kann für eine andere Position gemessen werden usw. Die Messungen für die abgetasteten Positionen können kombiniert werden, um eine Messung der Eigenschaft für das Bild zu erhalten.
Die Messungen für jede Position können mit einer Operation vorgenommen werden, die Probeergebnisdaten für die Messung der Eigenschaft an der Position erzeugt. Die Probeergebnisdaten für jedes Position sind ein Satz von einem oder mehreren Datenelementen, welche Information für die Position angeben. Dieser Satz wird hier als "Ergebnissatz" bezeichnet. Zum Beispiel kann der Ergebnissatz ein Datenelement für jede aus einer Anzahl von Richtungen enthalten, die sich von der Position erstrecken, wobei das Datenelement für jede Richtung ein Wert ist, der die Distanz in dieser Richtung zu der nächsten Position angibt, an der das Bild ein Kriterium erfüllt.
Die Probeergebnisdaten für die Positionen in dem Probesatz können kombiniert werden, um kombinierte Ergebnisdaten für das Bild zu erhalten. Wenn zu Beispiele Ergebnissätze wie oben beschrieben erhalten werden, wobei jeder Ergebnissatz ein Datenelement für jede aus einer Anzahl von Richtungen enthält und wobei das Datenelement jeder Richtung die Distanz in dieser Richtung angibt, dann kann ein kombiniertes Datenelement für jede Richtung durch eine Durchschnittsbildung der Datenelemente für die Richtung erhalten werden.
Die vorliegende Erfindung wird im folgenden beispielhaft mit Bezug auf die beigefügten Zeichnungen beschrieben:
Fig. 1 ist eine schematische Zeichnung eines Teils eines Bildes, die zeigt, wie die Messung einer Eigenschaft in Beziehung zu einer Anzahl von nahen Positionen redundante Daten erzeugen kann,
Fig. 2 ist eine schematische Zeichnung eines Teils eines Bildes, die eine andere Möglichkeit zeigt, wie die Messung einer Eigenschaft in Beziehung zu einer Anzahl von nahen Positionen redundante Daten erzeugen kann,
Fig. 3 ist ein Flußdiagramm, das allgemeine Schritte zum Messen einer Eigenschaft eines Bildes durch das Abtasten von Positionen zeigt,
Fig. 4 ist ein Flußdiagramm, das allgemeine Schritte zum zufälligen Abtasten eines Bildes in einer seriellen Implementierung zeigt,
Fig. 5 ist ein Flußdiagramm, das allgemeine Schritte zum zufälligen Abtasten eines Bildes in einer parallelen Implementierung zeigt,
Fig. 6 ist ein Flußdiagramm, das allgemeine Schritte zum Segmentieren eines Bildes zeigt, so daß eine Eigenschaft für jedes Segment gemessen werden kann,
Fig. 7 ist ein schematisches Blockdiagramm, das Komponenten eines Systems zeigt, das eine Bildverarbeitung implementiert, in welcher eine Eigenschaft durch das zufällige Abtasten von Positionen gemessen wird,
Fig. 8 ist ein Flußdiagramm, das Schritte zum Messen einer Eigenschaft eines Bildes durch das Segmentieren des Bildes und das Messen der Eigenschaft für jedes Segment zeigt,
Fig. 9 ist ein Flußdiagramm, das Schritte zum Messen einer Eigenschaft eines Bildes durch das zufällige Abtasten von Positionen zeigt, die ein Kriterium erfüllen,
Fig. 10 ist ein Flußdiagramm, das Schritte zum Erhalten einer zufälligen Position innerhalb eines Bildes zeigt,
Fig. 11 ist ein Flußdiagramm, das Schritte zum Erhalten einer Annäherung an eine Schrägstellung durch das zufällige Abtasten und Messen der Distanzen zwischen den Kanten von verbundenen Komponenten zeigt,
Fig. 12 ist ein Flußdiagramm, das Schritte zum Erhalten einer präziseren Annäherung an eine Schrägstellung durch das zufällige Atasten und Erhalten einer Varianz der Zeichenpixelzählungen für Richtungen um eine Annäherung einer Schrägstellung herum zeigt,
Fig. 13 ist ein Flußdiagramm, das zeigt, wie die Techniken von Fig. 11 und 12 zusammen zum Messen der Schrägstellung verwendet werden können,
Fig. 14 ist ein Flußdiagramm, das Schritte zum Messen der dominanten Schriftart durch ein zufälliges Abtasten zeigt,
Fig. 15 ist ein Flußdiagramm, das Schritte zum Messen der Größe oder des Abstands von Zeichen oder Anschlägen durch ein zufälliges Abtasten zeigt,
Fig. 16 ist ein schematisches Blockdiagramm eines Systems, das einen parallelen Prozessor zum Messen einer Eigenschaft eines Bildes durch ein zufälliges Abtasten umfaßt, und
Fig. 17 ist ein schematisches Blockdiagramm eines Kopiergeräts, das ein Bildverarbeitungssystem enthält, welches eine Eigenschaft eines Bildes durch ein zufälliges Abtasten mißt.
Die allgemeinen Merkmale der vorliegenden Erfindung werden durch die Fig. 1 bis 6 verdeutlicht. Fig. 1 zeigt, wie nahe Positionen in einem Bild allgemein ähnliche Eigenschaften relativ zu einer nahen verbundenen Komponente aufweisen. Fig. 2 zeigt entsprechend, wie nahe Positionen in einer verbundenen Komponente in einem Bild ähnliche Eigenschaften relativ zu einer Kante der verbundenen Komponente aufweisen. Fig. 3 zeigt, wie Positionen eines Bildes abgetastet werden können, um eine Eigenschaft für das Bild zu messen. Fig. 4 zeigt die Messung einer Eigenschaft für Positionen in einem Probesatz auf einem seriellen Gerät, während Fig. 5 die Messung für Positionen in einem Probesatz auf einem parallelen Gerät zeigt. Fig. 6 zeigt, wie ein Bild in kleinere Bilder segmentiert werden kann, welche jeweils einen vorherrschenden Wert für eine gemessene Eigenschaft aufweisen.
Die Positionen 10, 12 und 14 in Fig. 1 sind nahe Positionen relativ zu welchen eine Bildeigenschaft gemessen werden kann. Die dargestellte Bildeigenschaft ist die Distanz in einer Richtung θ&sub1; über einen weißen Bereich zu der nächsten verbundenen Komponente. Wie gezeigt, ist die nächste verbundene Komponente in der Richtung θ&sub1; für alle drei Positionen 10, 12 und 14 die Komponente 20. Die Distanz von der Position 10 zu der Position 22 auf der Kante einer Komponente 20 ist d&sub1;, von der Position 12 zu der Position 24 d&sub2; und von der Position 14 zu der Position 26 d&sub3;. Obwohl d&sub1;, d&sub2; und d&sub3; alle jeweils verschieden sind, sind die Differenzen zwischen denselben relativ klein. Wenn nicht eine sehr kleine Maßeinheit verwendet wird, dann ist die Bildeigenschaft für die Positionen 10, 12 und 14 gleich. Deshalb erzeugt das Messen der Eigenschaft relativ zu allen drei Positionen redundante Daten.
Die Positionen 40, 42 und 44 in Fig. 2 sind entsprechend nahe Positionen in der verbundenen Komponente 50. Die dargestellte Bildeigenschaft ist eine Distanz in einer Richtung θ&sub2; über einen schwarzen Bereich zu der nächsten Kante der verbundenen Komponente 50. Die Distanz von der Position 40 zu der Position 52 auf der Kante der Komponente 50 ist d&sub4;, von der Position 42 zu der Position 54 d&sub5; und von der Position 44 zu der Position 56 d&sub5;. Obwohl d&sub4;, d&sub5; und d&sub5; sich jeweils voneinander unterscheiden, sind die Differenzen zwischen denselben wiederum relativ klein, so daß ein Messen der Eigenschaft relativ zu allen drei Positionen redundante Daten erzeugt.
Fig. 3 zeigt allgemeine Schritte zum Messen einer Eigenschaft eines Bildes durch das Messen der Eigenschaft für einen Probesatz von Positionen. Diese Technik kann verwendet werden, um wie in Fig. 1 und 2 gezeigte redundante Messungen zu reduzieren. Der Schritt in Kasten 70 mißt die Eigenschaft für den Probesatz von Positionen. Der Schritt in Kasten 72 kombiniert dann die Ergebnisse von Kasten 70, um ein Maß für die Eigenschaft des Bildes zu erhalten.
Die Schritte in Fig. 3 reduzieren die Redundanz des durch Fig. 1 und 2 dargestellten Typs, sind aber für ein Aliasing anfällig, wenn die Positionen des Probesatzes in einem regelmäßigen oder gleichmäßigen Muster ausgewählt werden. Ein regelmäßig oder gleichmäßig auftretendes Merkmal in einem Bild kann ignoriert oder falsch interpretiert werden, wenn es in einem Muster auftritt, so daß keine seiner Erscheinungen an einer Position in dem Probesatz auftritt oder so daß seine Erscheinungen an allen Positionen in dem Probesatz, aber an keiner anderen Position auftreten. Zum Beispiel kann ein regelmäßiges Abtasten von jeder n-ten Position in einem Aliasing resultieren, wenn ein Merkmal des Bildes mit Intervallen von n Positionen auftritt. Das Problem eines Aliasing kann vermieden werden, indem die Positionen des Probesatzes zufällig oder pseudozufällig abgetastet werden.
Fig. 4 zeigt ein Beispiel dafür, wie der Schritt in Kasten 70 von Fig. 3 mit einer zufälligen Auswahl auf einem seriellen Gerät implementiert werden kann. Der Schritt in Kasten 90 beginnt mit dem zufälligen Produzieren von Positionsdaten, die eine Position in dem abgetasteten Bild angeben. Der Schritt in Kasten 92 verzweigt dann auf der Basis davon, ob die angegebene Position ein Probesatzkriterium erfüllt. Wenn nicht, wird der Schritt in Kasten 90 nochmals durchgeführt. Wenn die angegebene Position jedoch das Kriterium erfüllt, dann mißt der Schritt in Kasten 94 eine Bildeigenschaft relativ zu der Position. Der Schritt in Kasten 96 verzweigt dann auf der Basis davon, ob genug Positionen abgetastet wurden, um die Eigenschaft für das Bild zu messen. Wenn nicht, wird der Schritt in Kasten 90 nochmals durchgeführt.
Fig. 5 zeigt, wie der Schritt in Kasten 70 von Fig. 3 mit einer zufälligen Auswahl auf einem parallelen Gerät implementiert werden kann, in dem jede Position des Bildes eines entsprechende Verarbeitungseinheit aufweist, die ein Datenelement für die Position im lokalen Speicher speichert. Der Schritt in Kasten 110 betreibt die Verarbeitungseinheiten parallel, so daß jede Verarbeitungseinheit Kriteriumsdaten erzeugt, welche angeben, ob die entsprechende Position ein Probesatzkriterium erfüllt, woraus Daten resultieren, welche das Ergebnis des Messens einer Bildeigenschaft relativ zu der entsprechenden Position angeben. Bei der Durchführung dieses Schrittes können die Verarbeitungseinheiten kommunizieren, um erforderliche Daten von anderen Verarbeitungseinheiten zu erhalten. Der Schritt in Kasten 112 wählt dann einen zufälligen Probesatz aus den Verarbeitungseinheiten aus, deren Kriteriumsdaten angeben, daß die entsprechenden Positionen das Kriterium erfüllen. Die Ergebnisdaten aus dem Probesatz werden in Kasten 114 erhalten.
Fig. 6 zeigt, wie ein Bild, das mehr als einen Teil umfaßt, welche jeweils einen vorherrschenden Wert für eine gemessene Eigenschaft aufweisen, in Segmente unterteilt werden kann, für welche jeweils die Eigenschaft gemessen werden kann. Der Schritt in Kasten 130 beginnt mit dem Aufteilen des Bildes in Startsegmente, wie etwa Zeilen oder Wörter, wenn es sich um ein Bild handelt, das Text enthält. Dies kann durch das Operieren auf den Bilddaten vorgenommen werden, um Segmentdaten zu erzeugen, welche jeweils die Startsegmente definieren. Der Schritt in Kasten 132 mißt dann die Eigenschaft in jedem Startsegment, was vorgenommen werden kann, indem Ergebnisdaten für eine Probe von Positionen in jedem Segment erhalten werden und die Ergebnisdaten kombiniert werden, um ein kombiniertes Ergebnis für das Segment zu erhalten. Dann gruppiert der Schritt in Kasten 134 die Startsegmente in größere Segmente auf der Basis der Messungen in Schritt 132, um Segmente zu erhalten, welche jeweils einen vorherrschenden Wert für die gemessene Eigenschaft aufweisen. Dies kann vorgenommen werden, indem die kombinierten Ergebnisse verwendet werden, um zu bestimmen, welche Startsegmente in eine Gruppe aufgenommen werden sollen, um gruppierte Segmentdaten zu erzeugen, welche ein größeres Segment definieren, das die Segmente in der Gruppe enthält.
In Übereinstimmung mit der statistischen Abtastungstheorie ist die Varianz der Verteilung umgekehrt proportional zu dem Quadrat der Anzahl von Abtastungen, die erforderlich sind, um eine bestimmte Stufe von statistischer Signifikanz beim Abtasten der Verteilung zu erhalten. Wenn also die Varianz bekannt ist oder analytisch aus Faktoren wie etwa den gemessenen Bildeigenschaften und der Anzahl von Positionen in dem Bild bestimmt werden kann, dann kann theoretisch die erforderliche Anzahl von Abtastungen durch Berechnungen bestimmt werden.
Praktisch ist die Varianz einer Bildeingenschaft jedoch häufig nicht zuvor bekannt und kann nicht analytisch bestimmt werden. Deshalb kann eine heuristische Anwendung der statistischen Abtastungstheorie verwendet werden, um die Anzahl von zu erhaltenden Abtastungen zu erhalten. Eine einfache Heuristik besteht darin, die anfängliche Anzahl von Abtastungen zu wählen und zwei Messungen unter Verwendung der gewählten Anzahl vorzunehmen; wenn zwei der Messungen identisch sind oder ungefähr gleich sind, dann ist die gewählte Anzahl ausreichend groß; wenn nicht, kann die gewählte Anzahl erhöht wer den, und es können zwei Messungen unter Verwendung der erhöhten Anzahl vorgenommen werden, usw.
Unter Verwendung dieser Heuristik hat sich herausgestellt, daß 1000 Abtastungen ausreichen, um die Distanz als eine Funktion der Richtung zu messen, um Information über die Schrägstellung oder die Schriftart zu erhalten, und daß 5000 Abtastungen ausreichen, um die horizontalen und vertikalen Distanzen über und zwischen verbundenen Komponenten zu erhalten, um Information über die Größe und den Abstand von Zeichen und Anschlägen zu erhalten, währen 24 Abtastungen ausreichen, um die Varianz in der Anzahl der Pixel einer bestimmten Farbe entlang von Zeilen in einer bestimmten Richtung zu messen, um Information über die Schrägstellung zu erhalten. Diese Ergebnisse können auf der Basis der Varianz der zugrundeliegenden Messung erklärt werden: die Distanzmessung, entweder als eine Funktion der Richtung oder in den horizontalen und vertikalen Richtungen weist eine relativ große Varianz auf, so daß sie eine relativ große Anzahl von Abtastungen erfordert. Die Varianz, selbst ein statistisches Maß, weist eine relativ kleine Varianz auf, so daß eine relativ kleine Anzahl von Abtastungen erforderlich ist, um dieselbe für ein Bild zu messen.
Die oben beschriebenen allgemeinen Merkmale können auf verschiedene Weise auf verschiedenen Geräten implementiert werden, um viele verschiedene Bildeigenschaften zu messen.
Fig. 7 zeigt eine Möglichkeit, wie die vorliegende Erfindung auf einem seriellen Gerät implementiert werden kann. Fig. 8 zeigt Schritte zum Segmentieren eines Bildes. Fig. 9 zeigt allgemeine Schritte, die zum Messen einer Eigenschaft durchgeführt werden. Fig. 10 zeigt insbesondere, wie Daten, die eine zufällige Position in einem Bild angeben, erhalten werden können.
Das System 160 in Fig. 7 umfaßt einen Prozessor 162, der verbunden ist, um Eingabedaten von einer Eingabeeinrichtung 164 zu erhalten und um Ausgabedaten zu einer Ausgabeeinrichtung 166 auszugeben. Der Prozessor 162 kann die CPU einer Workstation sein, und die Eingabeeinrichtung 164 und die Ausgabeeinrichtung 166 können E/A-Geräte sein. Zum Beispiel kann die Eingabeeinrichtung 164 eine Bildeingabeeinrichtung wie etwa ein Scanner oder eine digitale Bildquelle sein. Weiterhin kann die Eingabeeinrichtung 164 eine Verbindung zu einer peripheren Speichereinrichtung oder einem anderen Speicher- oder Übertragungsmedium vorsehen, von welchem Modellprofile, welche die Distanz als eine Funktion der Richtung angeben, empfangen werden können. Entsprechend kann die Ausgabe einrichtung 166 eine Einrichtung zum Ausgeben von durch den Prozessor 162 erhaltenen Daten sein, wie etwa von Daten, welche eine Bildeigenschaft angeben.
Während des Betriebs führt der Prozessor 162 Befehle aus einem Programmspeicher 168 durch und greift auf einen Datenspeicher 170 zu, um Daten zu lesen und zu schreiben. Der Programmspeicher 168 speichert Befehle zum Durchführen einer Anzahl von Operationen des Prozessors 162. Der Datenspeicher 170 speichert wie gezeigt Daten und kann auch temporär Zwischendaten speichern, die durch den Prozessor 162 zum Durchführen seiner Operationen verwendet werden.
Der Prozessor 162 kann eine Bildsegmentierungsoperation 172 durchführen, um eine Bildeigenschaft für Segmente eines Bildes zu messen. Der Aufruf für eine Bildsegmentierungsoperaiton 172 kann Daten umfassen, welche die zu messende Eigenschaft identifizieren. Wie weiter unten ausführlicher erläutert, kann die Bildsegmentierungsoperation 172 wiederum eine Kachelsegmentierungsoperation 174, eine Zeilensegmentierungsoperation 176, eine Wortsegmentierungsoperation 178, eine Schrägstellungsoperation 180 und andere Eigenschaftsoperationen 182 aufrufen, um das Bild in Segmente zu unterteilen, welche jeweils einen vorherrschenden Wert für die zu messende Eigenschaft aufweisen. Die Schrägstellungsoperation 180 und andere Eigenschaftsoperationen 182 können eine Zufallspositionsoperation 184 aufrufen, um Daten zu erhalten, welche eine abzutastende Position identifizieren.
Beim Durchführen der Bildsegmentierungsoperation 168, der Kachelsegmentierungsoperation 174, der Zeilensegmentierungsoperation 176, der Wortsegmentierungsoperation 178, der Schrägstellungsoperation 180 und anderer Eigenschaftsoperationen 182 kann der Prozessor 162 auf Bilddaten 186 im Datenspeicher 170 zugreifen, um Daten zu dem analysierten Bild zu erhalten und um Daten für eine bestimmte Position in dem Bild zu erhalten. Beim Durchführen der Schrägstellungsoperation 180 und anderer Eigenschaftsoperationen 182 kann der Prozessor 162 auf Signifikanzdaten 188 zugreifen, um Daten zu erhalten, welche die Anzahl oder die Proportion von Positionen angeben, die abgetastet werden müssen, um eine Eigenschaft mit einer gewünschten Stufe von statistischer Signifikanz zu messen; beim Durchführen dieser Operationen kann der Prozessor 162 auch Probeergebnisdaten 190 und Bildergebnisdaten 192 erzeugen und speichern.
Fig. 8 zeigt, wie die Bildsegmentierungsoperation 168 implementiert werden kann. Der Schritt in Kasten 210 beginnt mit dem Empfangen eines Aufrufs zum Messen einer beson deren Bildeigenschaft. Der Aufruf gibt auch die Quelle des zu analysierenden Bildes an. Der Schritt in Kasten 212 verzweigt in Abhängigkeit von der Bildquelle: wenn das Bild gescannt werden soll, empfängt der Schritt in Kasten 214 die Scanndaten aus der Eingabeeinrichtung 164, binarisiert dieselben und speichert sie in dem Datenspeicher 170. Dieser Schritt kann auch eine Vorverarbeitung der Bilddaten umfassen, um Rauschen zu reduzieren oder um andere irrelevante Daten zu beseitigen.
Der Schritt in Kasten 220 verzweigt in Abhängigkeit davon, ob die zu messende Eigenschaft eine Texteigenschaft wie zum Beispiel Schrägstellung, Schrift oder Zeichengröße-/abstand ist. Wenn nicht, mißt der Schritt in Kasten 222 die Eigenschaft mit Hilfe von anderen geeigneten Techniken.
Um eine Texteigenschaft zu messen, ist es allgemein erforderlich, die Schrägstellung zu bestimmen. Deshalb beginnt der Schritt in Kasten 224 damit, die Bilder in Kacheln wie etwa Rechtecke zu unterteilen, wobei ein entsprechender Aufruf der Kachelsegmentierungs-Subroutine 174 gemacht wird. Der Schritt in Kasten 226 mißt dann die Schrägstellung der Kacheln, macht entsprechende Aufrufe an die Schrägstellungs-Subroutine 180 und gruppiert dann die Kacheln auf der Basis der Schrägstellung zu Schrägstellungssegmenten. Dieser Schritt kann auch die Schrägstellung für alle Kacheln messen und dann die Kacheln in Übereinstimmung mit der Ähnlichkeit in Schrägstellungssegmente gruppieren, oder eine andere Strategie verwenden, die nicht erfordert, daß jede Kachel gemessen werden muß, indem etwa Schrägstellungssegmente vergrößert werden, wobei mit Ursprungskacheln begonnen wird. In jedem Fall sollten benachbarte Kacheln, deren Schrägstellung ausreichend verschieden ist, nicht in dasselbe Schrägstellungssegment aufgenommen werden.
Wenn Schrägstellungssegmente erhalten wurden, macht der Schritt in Kasten 228 wiederum Aufrufe an die Schrägstellungs-Subroutine 180, um dieses Mal die Schrägstellung jedes Schrägstellungssegment zu messen. Dann verzweigt der Schritt in Kasten 230 auf der Basis davon, ob die gemessene Eigenschaft eine Schrägstellung ist. Wenn ja, gibt der Schritt in Kasten 232 die Ergebnisse aus Kasten 228 aus, um die Messung der Schrägstellung abzuschließen.
Für andere Eigenschaften als die Schrägstellung beginnt der Schritt in Kasten 240 eine iterative Schleife, wobei jede Wiederholung derselben die Eigenschaft für eines der Schrägstellungssegmente mißt. Der Schritt in Kasten 242 beginnt eine iterative Schleife, um das nächste Schrägstellungssegment in Teilsegmente zu teilen. Dies kann durch Aufrufe an die Zeilensegmentierungsoperation 176 und die Wortsegmentierungsoperation 178 vorgenommen werden. Die Aufrufe an die Zeilensegmentierungsoperation 176 und die Wortsegmentierungsoperation 178 können die Schrägstellung enthalten, die für das zu teilende Schrägstellungssegment gemessen wurde. Die Zeilensegmentierungsoperation 176 kann leere Räume finden, die sich mit demselben Winkel wie die Schrägstellung über das Schrägstellungssegment erstrecken, und das Segment zwischen benachbarten leeren Räumen dann als Zeilensegment zu behandeln. Die Wortsegmentierungsoperation 178 kann leere Räume finden, die sich mit einem senkrechten Winkel zu der Schrägstellung über ein Zeilensegment erstrecken und eine Minimalbreite aufweisen, die größer ist als der wahrscheinliche Zeichenabstand innerhalb eines Wortes, und dann das Segment zwischen benachbarten leeren Räumen dann als Wortsegment behandeln.
Wenn ein Schrägstellungssegment in Teilsegmente unterteilt wurde, mißt der Schritt in Kasten 244 die Eigenschaft für Teilsegmente, so daß Teilsegmente, bei denen die Eigenschaft ungefähr gleich ist, zu Textsegmenten gruppiert werden können. In diesem Fall kann es erforderlich sein, die Eigenschaft für jedes Teilsegment zu messen, weil ein isoliertes Wort eine andere dominante Schriftart oder eine unterschiedliche Zeichengröße bzw. einen unterschiedlichen Zeichenabstand aufweisen kann.
Wenn alle Schrägstellungssegmente behandelt wurden, stellt der Schritt in Kasten 250 die für jedes Schrägstellungssegment erhaltenen Ergebnisse bereit. Wenn das Bild nur ein Schrägstellungssegment umfaßt, mißt das Ergebnis die Eigenschaft für das Bild als ganzes.
Obwohl die Technik von Fig. 8 automatisch Segmente findet, für welche jeweils eine Bildeigenschaft gemessen werden kann, können auch andere Ansätze verwendet werden. Ein zu analysierendes Bild kann auf der Basis von Information von einem menschlichen Bediener segmentiert werden, oder es kann angenommen werden, daß das Bild einen einzigen vorherrschenden Wert für die Eigenschaft aufweist, was in vielen Fällen wahr ist. Weiterhin können vor den Schritten in den Kästen 224 und 242 zusätzliche Tests durchgeführt werden, um zu bestimmen, ob das Bild einen einzigen vorherrschenden Wert aufzuweisen scheint, was die Segmentierung und Gruppierung unnötig macht. Wenn das Bild zum Beispiel eine einzelne dominante Schriftart aufweist, dann ist ein Segmentieren und Gruppieren nicht erforderlich, um die Schriftart zu bestimmen. Wenn entsprechend das Ergebnis der Schrägstellungsmessung für das Bild als ganzes wie weiter unten mit Bezug auf Fig. 11 beschrieben ein Minimum aufweist, das weniger als ein Drittel des Bereichs zwischen den niedrigsten und höchsten kombinierten Distanzwerten ist, dann weist das Bild eine vorherrschende Schrägstellung auf und braucht nicht in Schrägstellungssegmente geteilt werden; dieser Schwellwert basiert auf der Beobachtung, daß der Abstand zwischen Zeilen typischerweise wenigstens dreimal so groß ist wie der Abstand zwischen Zeichen.
Fig. 9 stellt allgemeine Schritte zum Implementieren der Meßoperationen in den Kästen 222, 226, 228 und 244 dar. Besondere Implementierungen von mehreren Meßoperationen werden weiter unten ausführlicher erläutert.
Der Schritt in Kasten 270 beginnt bei Empfang eines Aufrufs zum Messen einer bestimmten Eigenschaft. Dieser Aufruf umfaßt Parameter des Bildes, für das die Eigenschaft gemessen werden soll. Wie mit Bezug auf Fig. 8 beschrieben, kann das Bild ein Segment eines anderen Bildes wie etwa eine Kachel, ein Schrägstellungssegment, ein Wortsegment oder ein Textsegment sein. Die Bildparameter können Daten umfassen, welche die Startpositionen von Daten angeben, die das Bild im Speicher und seine Dimensionen angeben, welche zum Beispiel in Pixeln gemessen werden.
Auf der Basis der in Kasten 270 erhaltenen Daten bestimmt der Schritt in Kasten 272 die Anzahl der vorzunehmenden Abtastungen. Dieser Schritt ist optional, weil die Anzahl auch im voraus bestimmt werden kann, indem etwa eine globale Variable gesetzt wird oder indem eine Konstante gleich der Anzahl der vorzunehmenden Abtastungen eingefügt wird. Wie oben mit Bezug auf Fig. 7 beschrieben, können die Signifikanzdaten 188 Daten enthalten, welche eine Anzahl oder Proportion von Positionen in einem Bild angeben, das abgetastet werden muß, um einen gewünschten Grad von statistischer Signifikanz für eine bestimmte Eigenschaft vorzusehen. Unter Verwendung der Dimensionen des Bildes kann zum Beispiel die Anzahl der Pixel in dem Bild bestimmt und mit der Proportion multipliziert werden, die für die zu messende Eigenschaft abgetastet werden muß, um die Anzahl der vorzunehmenden Abtastungen zu erhalten.
Der Schritt in Kasten 280 beginnt eine iterative Schleife, die allgemein den Schritten von Fig. 4 folgt, um Abtastungen vorzunehmen, bis die Anzahl von Kasten 272 erreicht ist. Der Schritt in Kasten 282 ruft eine Zufallspositionsoperation 184 auf, um eine Zufallsposition innerhalb des zu messenden Bildes zu erhalten. Dieser Aufruf kann Parameter des Bildes aus Kasten 270 umfassen.
Der Schritt in Kasten 284 wendet das Probesatzkriterium für die zu messende Eigenschaft auf die in Kasten 282 erhaltene Position an. Wenn die Position das Kriterium nicht erfüllt, dann wird der Schritt in Kasten 282 wiederholt, um eine andere Position zu erhalten. Wenn eine Position erhalten wird, die das Kriterium erfüllt, dann führt der Schritt in Kasten 286 die Schritte durch, die erforderlich sind, um die Eigenschaft für die Position zu messen.
Wenn die Anzahl der Abtastungen von Kasten 272 erreicht wird, kombiniert der Schritt in Kasten 288 die in jeder Wiederholung von Kasten 286 vorgenommenen Messungen zu einer Messung der Eigenschaft für das Bild. Diese Messung wird an den Prozeß zurückgegeben, der den in Kasten 270 empfangenden Aufruf gemacht hat.
Wie weiter unten ausführlicher erläutert, können die Schritt in den Kästen 286 und 288 unterschiedlich zugeordnet werden. Zum Beispiel können alle Positionen erhalten und gespeichert werden, wobei der Schritt in Kasten 286 vollständig ausgelassen wird, wobei dann der Schritt in Kasten 288 die Eigenschaft für die Positionen messen und die Ergebnisse kombinieren kann. Oder der Schritt in Kasten 286 kann Operationen umfassen, welche jede erhaltene Messung mit vorhergehenden Messungen kombinieren, wobei in diesem Fall der Schritt in Kasten 288 nur endgültige Operationen durchführt, die erforderlich sind, um die Messungen zu kombinieren, bevor das kombinierte Ergebnis ausgegeben wird. Die Wahl, wie diese Schritte implementiert werden können, hängt von der Effizienz oder anderen praktischen Erwägungen ab.
Fig. 10 zeigt eine Implementierung einer Zufallspositionsoperation 184, die in Kasten 282 von Fig. 9 aufgerufen wird. Der Schritt in Kasten 300 beginnt bei Empfang eines Aufrufs zum Vorsehen einer Zufallsposition einschließlich von Bildparametern. Die Bildparameter können Daten enthalten, welche die Startposition von Daten, die das Bild im Speicher definieren, die in Pixeln gemessenen Abmessungen und die Gesamtzahl der Pixel angeben.
Der Schritt in Kasten 302 erzeugt eine Zufallszahl mit Hilfe von herkömmlichen Zufallszahl- oder Pseudozufallszahl-Erzeugungstechniken. Der Schritt in Kasten 304 mappt dann die Zufallszahl aus Kasten 302 auf das durch die Bildparameter von Kasten 300 definierte Bild, um eine Position im Bild zu finden. Zum Beispiel kann eine Zufallszahl zwischen null und der Gesamtzahl der Pixel in dem Bild erzeugt werden; die Zufallszahl kann dann durch die Anzahl der Reihen in dem Bild dividiert werden, wobei das ganzzahlige Ergebnis der Teilung die Reihe angibt, in welcher ein Pixel auftritt, und wobei der Rest die Position des Pixels in der Reihe angibt. Der Schritt in Kasten 306 gibt die in Kasten 304 erhaltene Position an den Prozeß aus, der die Zufallspositionsoperation 184 aufgerufen hat.
Die folgenden Abschnitte beschreiben Beispiele dafür, wie die allgemeine Technik in Fig. 9 implementiert werden kann, um Eigenschaften zu messen, welche Informationen zur Schrägstellung, der Schriftart, der Zeichengröße und den Abständen vorsehen.
Die Schritte in den Kästen 226 und 228 in Fig. 8 messen die Schrägstellung der Textzeilen in einem Bild. Fig. 11 stellt eine Technik zum Messen der Schrägstellung durch das Messen von Distanzen zwischen Kantenpixeln in einer großen Anzahl von Richtungen dar. Fig. 12 stellt eine Technik zum Messen der Schrägstellung durch das Messen der Anzahlen von schwarzen Pixeln in Linien in mehreren Richtungen dar, die einen Bereich abdecken. Die Techniken von Fig. 11 und 12 folgen allgemein den Schritten in Fig. 9, wobei sich jede derselben in verschiedenen Punkten von Fig. 9 unterscheidet. Fig. 13 stellt dar, wie die Techniken von Fig. 11 und 12 zusammen verwendet werden können, um die Schritte in den Kästen 226 und 228 in Fig. 8 durchzuführen.
Die Schritte in Fig. 11 nehmen an, daß die Anzahl der zum Messen der Schrägstellung zu erhaltenden Abtastungen im voraus bestimmt wurde und zum Beispiel in der Form einer globalen Variable verfügbar ist. Der Schritt in Kasten 320 von Fig. 11 beginnt mit dem Empfangen eines Aufrufs zum Messen der Schrägstellung zusammen mit Parametern des Bildes, für das die Schrägstellung gemessen werden soll. Der Schritt in Kasten 322 beginnt eine iterative Schleife, die Abtastungen erhält, bis die Anzahl der durch die globale Variable angegebenen Abtastungen erreicht ist. Der Schritt in Kasten 324 erhält eine zufällige Position innerhalb des zu messenden Bildes, indem er etwa die Zufallspositionsoperation 184 aufruft. Der Schritt in Kasten 326 greift dann auf das Pixeldatenelement der Zufallsposition aus Kasten 324 zu und greift außerdem auf die Pixeldatenelemente der benachbarten Positionen zu.
Der Schritt in Kasten 330 wendet ein Probesatzkriterium an, das bestimmt, ob die Pixeldaten der Zufallsposition eine entsprechende Farbe, entweder Schwarz oder Weiß angeben, und ob eine der benachbarten Positionen die entgegengesetzte Farbe angibt, so daß die Zufallsposition ein Kantenpixel ist. Wenn nicht, wird eine andere Zufallsposition in Kasten 324 erhalten.
Wenn ein Pixel gefunden wurde, welches das Probesatzkriterium erfüllt, mißt der Schritt in Kasten 332 die Distanz über die Hintergrundfarbe bis zur nächsten Kante in jeder von einer Vielzahl von Richtungen. Wenn das Bild zum Beispiel schwarze Zeichen auf einem weißen Hintergrund aufweist, dann kann die Distanz über weiße Pixel zum nächsten schwarzen Kantenpixel oder zum nächsten weißen Kantenpixel gemessen werden. Der Schritt in Kasten 334 addiert die in jeder Richtung erhaltene Distanz zu der Summe der zuvor erhaltenen Distanzen in dieser Richtung und führt also einen Teil der Operation zum Kombinieren der in jeder Richtung erhaltenen Distanzmessungen durch.
Wenn die Anzahl der Abtastungen erhalten wurde, kann der Schritt in Kasten 340 die Operation zum Kombinieren der Messungen durch das Teilen der Summe der Distanzen in jeder Richtung durch die Anzahl der erhaltenen Abtastungen abschließen, um eine durchschnittliche Distanz in jeder Richtung zu erhalten; dieser Schritt ist optional, weil die Schrägstellung ohne eine Durchschnittsbildung der Distanzen bestimmt werden kann. Die durchschnittlichen Distanzen bilden ein Profil, das dann analysiert wird, um in Kasten 342 die zwei tiefsten separaten Minima zu finden. Wenn mit anderen Worten die zwei tiefsten Minima in Richtungen liegen, die durch weniger als einen Minimalwinkel &epsi; getrennt sind, dann werden sie als Teil desselben Minimums und nicht als separate Minima behandelt. Der Schritt in Kasten 350 bestimmt dann, ob die tiefsten separaten Minima aus Kasten 342 ungefähr in entgegengesetzten Richtungen liegen. Das ist der Fall, wenn die Richtungen durch 180 ± &epsi; Grad getrennt sind. Wenn ja, dann erhält der Schritt in Kasten 352 die Richtung des tiefsten Minimums und gibt dieses an den Prozeß aus, der die Schrägstellungsmessung aufgerufen hat. Wenn nicht, dann gibt der Schritt in Kasten 354 einen Wert aus, der einen Fehler angibt, was typischerweise auftritt, wenn das analysierte Bild kein Textbild ist oder wenn der Text Zeilen enthält, die sich in verschiedenen Richtungen erstrecken, so daß keine Richtung vorherrschend ist.
Die Schritte in Fig. 12 nehmen an, daß die Anzahl der zum Messen der Schrägstellung zu erhaltenden Abtastungen im voraus bestimmt wurde und zum Beispiel in der Form einer Konstante verfügbar ist, die in einer Subroutine enthalten ist. Der Schritt in Kasten 370 von Fig. 12 beginnt mit dem Empfangen eines Aufrufs zum Messen einer Schrägstellung zusammen mit Parametern des Bildes, für das die Schrägstellung gemessen werden soll und mit einem ungefähren Schrägstellungswinkel. Der Schritt in Kasten 372 beginnt eine iterative Schleife, die Abtastungspositionen erhält, bis die durch die Konstante angegebene Anzahl der Abtastungspositionen erreicht ist. Der Schritt in Kasten 374 erhält eine Zufallsposition innerhalb des gemessenen Bildes, indem er etwa eine Zufallsposition-Subroutine 184 aufruft. Der Schritt in Kasten 376 greift dann auf das Pixeldatenelement der Zufallsposition aus Kasten 374 zu.
Der Schritt in Kasten 380 wendet ein Probesatzkriterium an, das bestimmt, ob das Pixeldatenelement der Zufallsposition die Farbe der Pixel innerhalb von Zeichen angibt, entweder Schwarz für schwarze Zeichen auf einem weißen Hintergrund oder Weiß für weiße Zeichen auf einem schwarzen Hintergrund. Wenn nicht, dann wird in Kasten 374 eine andere Zufallsposition erhalten.
Wenn ein Pixel gefunden wird, welches das Probesatzkriterium erfüllt, dann fügt der Schritt in Kasten 382 die Position des Pixels zu einer Matrix aus Probesatzpositionen hinzu. Wenn dann die Anzahl der Abtastungspositionen erhalten wurde, beginnt der Schritt in Kasten 390 eine iterative Schleife, welche die Positionen in der Matrix durchläuft. Für jede Position zählt der Schritt in Kasten 392 die Zeichenpixel in einer Linie durch die Position in jeder von einer Anzahl von Richtungen, welche einen Bereich um den in Kasten 370 empfangenen ungefähren Schrägstellungswinkel abdecken. Wenn jede Zählung erhalten wird, wird eine Operation wie etwa eine Quadratbildung durchgeführt und wird das Ergebnis zu der Summe der vorhergehenden Ergebnisse für dieselbe Richtung addiert, um eine Messung der Varianz in jeder Richtung zu erzeugen.
Wenn alle Positionen in der Matrix gehandhabt wurden, werden die Operationen zum Messen einer Eigenschaft und zum Kombinieren der Ergebnisse abgeschlossen. Der Schritt in Kasten 394 findet die Richtung mit der größten Ergebnissumme, was bedeutet, daß die Varianz zwischen den Zeilen in dieser Richtung am größten ist. Der Schritt in Kasten 394 gibt also die Richtung mit der größten Ergebnissumme als Schrägstellungswinkel aus.
Die Schritte in Fig. 13 stellen dar, wie die Techniken von Fig. 11 und 12 zusammen für die Feststellung der Schrägstellung verwendet werden können. Der Schritt in Kasten 400 beginnt mit dem Empfang eines Aufrufs zum Messen der Schrägstellung mit Parametern des Bildes, für das die Schrägstellung gemessen werden soll. Der Schritt in Kasten 402 nimmt eine Messung vor, um eine erste Annäherung der Schrägstellung zu erhalten, wobei er die Technik von Fig. 11 verwendet. Der Schritt in Kasten 404 verzweigt auf der Basis des ausgegebenen Ergebnisses. Wenn das Ergebnis einen Fehler angibt, gibt der Schritt in Kasten 406 eine Fehlermeldung an den Prozeß aus, von welchem der Aufruf in Kasten 400 erhalten wurde.
Wenn das Ergebnis der Technik von Fig. 11 ein Schrägstellungswinkel ist, dann verwendet der Schritt in Kasten 410 diesen Winkel als ungefähre Schrägstellung bei der Durchführung einer zweiten Messung, um eine präzisere Annäherung der Schrägstellung unter Verwen dung der Technik von Fig. 12 zu erhalten. Der Schritt in Kasten 412 gibt dann die präzisere Messung der Schrägstellung an den Prozeß aus, von welchem der Aufruf in Kasten 400 empfangen wurde.
Der Schritt in Kasten 244 von Fig. 8 kann die dominante Schriftart des Textes in einem Bild messen. Fig. 14 stellt eine Technik zum Messen der dominanten Schriftart dar, welche die Distanzen von einem Pixel innerhalb eines Zeichens zu Kantenpixeln in einer großen Anzahl von Richtungen mißt. Die Technik von Fig. 14 folgt allgemein den Schritten in Fig. 9, obwohl sie sich in verschiedenen Punkten von Fig. 9 unterscheidet.
Die Schritte in Fig. 14 nehmen an, daß die Anzahl der zum Messen der dominanten Schriftart zu erhaltenden Abtastungen im voraus bestimmt wurde und zum Beispiel in der Form einer globalen Variable verfügbar ist. Der Schritt in Kasten 430 von Fig. 14 beginnt mit dem Empfangen eines Aufrufs zum Messen der dominanten Schriftart zusammen mit Parametern des Bildes, für das die dominante Schriftart gemessen werden soll, und mit einer Anzahl von Richtungen, in welchen die Distanzmessungen vorgenommen werden sollen. Der Schritt in Kasten 432 beginnt eine iterative Schleife, die Abtastungen erhält, bis die durch die globale Variable angegebene Anzahl von Abtastungspositionen erreicht ist. Der Schritt in Kasten 434 erhält eine Zufallsposition innerhalb des gemessenen Bildes, indem sie etwa eine Zufallspositionsoperation 184 aufruft. Der Schritt in Kasten 436 greift dann auf das Pixeldatenelement der Zufallsposition aus Kasten 434 zu.
Der Schritt in Kasten 436 wendet ein Probesatzkriterium an, das bestimmt, ob das Pixeldatenelement der Zufallsposition eine entsprechende Farbe für ein Pixel innerhalb eines Zeichens angibt, entweder Schwarz oder Weiß, je nachdem ob das Bild schwarzen Text auf einem weißen Hintergrund oder weißen Text auf einem schwarzen Hintergrund enthält. Alternativ dazu kann das Kriterium bestimmen, ob die Zufallsposition ein Pixel an einer Kante eines Zeichens ist. Wenn das Pixel das Kriterium nicht erfüllt, dann wird in Kasten 434 eine andere Zufallsposition erhalten.
Wenn ein Pixel gefunden wird, welches das Probesatzkriterium erfüllt, dann mißt der Schritt in Kasten 438 die Distanz über die weiße Farbe zu der nächsten Kante in jeder von der Anzahl von Richtungen, die in Kasten 430 erhalten wurden. Wenn das Bild zum Beispiel schwarze Zeichen auf einem weißen Hintergrund aufweist, dann kann die Distanz über die schwarzen Pixel zu dem nächsten schwarzen Kantenpixel oder zu dem nächsten weißen Kantenpixel gemessen werden. Der Schritt in Kasten 440 addiert die erhaltene Distanz in jeder Richtung zu der Summe der zuvor erhaltenen Distanzen in dieser Richtung, um also einen Teil der Operation zum Kombinieren der in jeder Richtung erhaltenen Distanzmessungen durchzuführen.
Wenn die Anzahl der Abtastungen erhalten wird, schließt der Schritt in Kasten 442 die Operation zum Kombinieren der Messungen ab, indem er die Summe der Distanzen in jeder Richtung durch die Anzahl der erhaltenen Abtastungen dividiert, um eine durchschnittliche Distanz in jeder Richtung zu erhalten. Der Schritt in Kasten 444 vergleicht dann das durch die durchschnittlichen Distanzen gebildete Profil mit einer Anzahl von Modellprofilen, welche jeweils eine entsprechende Schriftart wiedergeben. Dieser Vergleich kann zum Beispiel vorgenommen werden, indem eine Distanzmessung wie etwa die Quadratwurzel der Summe der Differenzen an jedem von einer Anzahl von gepaarten Punkten auf zwei Profilen verglichen wird. Der Schritt in Kasten 446 gibt dann Daten aus, welche die Schriftart des Modellprofils angeben, das dem Profil von Kasten 442 am nächsten ist, um die Messung der dominanten Schriftart abzuschließen.
Die durch die Technik von Fig. 14 erzeugten Profile können auch in einer Klassifikationstechnik verwendet werden, die eine Anzahl von Profilen zu Äquivalenzgruppen clustert.
Der Vergleich in Kasten 444 muß in irgendeiner Form die Differenzen der Schrägstellung und der Skalierung kompensieren. Eine Möglichkeit zum Kompensieren der Schrägstellung in der Technik von Fig. 8 besteht darin, die Ergebnisse der Messung der Schrägstellung in Kasten 228 von Fig. 8 in jeder Richtung in Kasten 450 von Fig. 14 zu verwenden, indem etwa die erste Messung mit dem Schrägstellungswinkel vorgenommen wird. Eine Skalierung kann durch das Normalisieren der Profile vor dem Durchführen eines Vergleichs kompensiert werden.
Der Schritt in Kasten 244 von Fig. 8 kann Größen oder Abstände von Zeichen oder Anschlägen in dem Text eines Bildes messen. Fig. 15 stellt eine Technik zum Messen der Größe oder des Abstands von Zeichen oder Anschlägen dar, welche die Distanzen zwischen den Pixeln an den Kanten der verbundenen Komponenten in einer bestimmten Richtung mißt. Die Technik von Fig. 15 folgt allgemein den Schritten von Fig. 9, wobei sie sich jedoch in verschiedenen Punkten von Fig. 9 unterscheidet.
Die Schritte von Fig. 15 nehmen an, daß die Anzahl der zum Messen der Größen oder Abstände zu erhaltenden Abtastungen im voraus bestimmt wurde und zum Beispiel in der Form einer globalen Variable verfügbar ist. Der Schritt in Kasten 450 von Fig. 15 beginnt mit dem Empfangen eines Aufrufs zum Messen der Größe oder des Abstands von Zeichen zusammen mit Parametern des Bildes, für das die Größe oder der Abstand gemessen werden soll. In dem Aufruf ist eine Angabe der Richtung enthalten, in welcher die Größe oder der Abstand gemessen werden soll. Wenn eine Größe gemessen werden soll, dann werden die Messungen über die verbundenen Komponenten vorgenommen, wenn aber ein Abstand gemessen werden soll, dann werden die Messungen zwischen verbundenen Komponenten vorgenommen.
Der Schritt in Kasten 452 beginnt eine iterative Schleife, die Abtastungen erhält, bis die durch die globale Variable angegebene Anzahl von Abtastungen erreicht ist. Der Schritt in Kasten 454 erhält eine Zufallsposition innerhalb des gemessenen Bildes, indem er etwa die Zufallspositionsoperation 184 aufruft. Der Schritt in Kasten 456 greift dann auf das Pixeldatenelement der Zufallsposition von Kasten 454 zu.
Der Schritt in Kasten 460 wendet ein Probesatzkriterium an, das bestimmt, ob das Pixeldatenelement der Zufallsposition ein Kantenpixel ist, was vorgenommen werden kann, indem der entsprechende Wert mit den Werten der benachbarten Pixel verglichen wird. Wenn das Pixel das Kriterium nicht erfüllt, wird in Kasten 454 eine andere Zufallsposition erhalten.
Wenn ein Pixel gefunden wird, welches das Probesatzkriterium erfüllt, mißt der Schritt in Kasten 462 die Distanz über eine verbundene Komponente oder zwischen verbundenen Komponenten zu der nächsten Kante in der in Kasten 450 angegebenen Richtung. Wenn das Bild zum Beispiel schwarze Zeichen auf einem weißen Hintergrund aufweist, dann kann die Distanz über eine verbundene Komponente über schwarze Pixel zu dem nächsten Kantenpixel gemessen werden und kann die Distanz zwischen verbundenen Komponenten über weiße Pixel zu dem nächsten Kantenpixel gemessen werden. Der Schritt in Kasten 464 inkrementiert einen Wert für einen Bereich von Distanzen, der die gemessene Distanz in einer Histogrammdatenstruktur enthält.
Wenn die Anzahl der Abtastungen erhalten wurde, operiert der Schritt in Kasten 466 auf der Histogrammdatenstruktur, um die in Kasten 450 angegebene Messung der Größe oder des Abstands zu erhalten.
Die Technik in Fig. 15 muß in irgendeiner Form die Schrägstellung kompensieren. Eine Möglichkeit zum Kompensieren der Schrägstellung besteht darin, eine schrägstellungskom pensierte Richtung in Kasten 450 anzugeben, so daß der Schritt in Kasten 462 dieselbe Richtung, aber relativ zu der Schrägstellung in dem analysierten Bild angibt.
Die vorliegende Erfindung kann alternativ dazu auf einem parallelen Gerät implementiert werden, wie oben mit Bezug auf Fig. 5 beschrieben. Fig. 16 zeigt Komponenten eines parallelen Gerätes, auf welchem die vorliegende Erfindung implementiert werden kann.
Das System 470 in Fig. 16 ist dem System 160 in Fig. 7 ähnlich. Das System 470 umfaßt einen Hostprozessor 472, der verbunden ist, um Daten von einer Eingabeeinrichtung 474 zu erhalten und Daten zu einer Ausgabeeinrichtung 476 auszugeben. Der Hostprozessor 472 ist auch verbunden, um Daten mit einem parallelen Prozessor 480 auszutauschen, der zum Beispiel eine Connection Machine von Thinkings Machines Corporation sein kann. Der parallele Prozessor 480 umfaßt Verarbeitungseinheiten 482 mit jeweils einem lokalen Speicher 484. Die ein Bild definierenden Daten können im lokalen Speicher 484 gespeichert werden, so daß der Wert jedes Pixels in dem entsprechenden lokalen Speicher einer Verarbeitungseinheit gespeichert wird. Der Hostprozessor 472 führt Befehle aus einem Programmspeicher 490 aus und greift auf einen Datenspeicher 492 zu, um die Bildverarbeitung wie oben mit Bezug auf Fig. 7 beschrieben durchzuführen. Der Hostprozessor 472 führt Subroutinen aus, die das parallele Betreiben der Verarbeitungseinheit für jedes Pixel umfassen, um einen zufällig erhaltenen Probesatz von Verarbeitungseinheiten zu erhalten, aus dem Daten kombiniert werden können, um eine Eigenschaft für ein ganzes Bild zu messen. Das zufällige Abtasten ist auch für die parallele Implementierung vorteilhaft, weil es den Rechenaufwand reduziert, der zum Kombinieren von Daten aus den Verarbeitungseinheiten erforderlich ist, ohne dabei ein Aliasing einzuführen.
Die vorliegende Erfindung kann vielfältig angewendet werden, etwa für die Feststellung einer Schrägstellung, die Identifikation der dominanten Schriftart oder die Messung von Größen und Abständen von Zeichen und Anschlägen wie oben beschrieben. Fig. 17 stellt eine Kopieranwendung dar.
Das Kopiergerät 500 umfaßt einen Scanner 502, ein Bildverarbeitungssystem 504 und einen Drucker 506. Der Scanner 502 kann Daten erzeugen, welche ein Bild eines Ausgabedokuments definieren. Das Bildverarbeitungssystem 504 kann wie in Fig. 7 oder in Fig. 16 gezeigt implementiert werden, wobei es zusätzlich zu der Messung der Schrägstellung, der dominanten Schriftart und der Größe und des Abstandes von Zeichen auch optische Zeichenerkennungstechniken verwenden kann, um Zeichen in dem Dokument zu erkennen.
Das Bildverarbeitungssystem 504 kann auch Techniken anwenden, um Daten zu erzeugen, die ein korrigiertes Bild definieren, in welchem ein Zeichen in dem Eingabedokumentenbild durch eine korrekte Version desselben Zeichens aus der identifizierten Schriftart mit der richtigen Größe, Position und Schrägstellung ersetzt ist. Die Daten, die das korrigierte Bild definieren, können dann zu einem Drucker 506 ausgegeben werden, um ein Ausgabedokument zu drucken.
Die vorliegende Erfindung wurde mit Bezug auf bestimmte Texteigenschaften wie etwa die Schrägstellung, die dominante Schriftart und die Größen und Abstände der Zeichen und Anschläge beschrieben. Die vorliegende Erfindung kann jedoch auch für die Identifikation von Zeichen oder Wörtern angewendet werden. Weiterhin kann die vorliegende Erfindung auch auf Nicht-Texteigenschaften wie etwa graphische Merkmale angewendet werden.
Die vorliegende Erfindung wurde mit Bezug auf Implementierungen beschrieben, in denen Operationen auf ein Bild definierenden Daten durchgeführt werden, um eine Eigenschaft zu messen. Die vorliegende Erfindung kann auch mit einem spezialisierten Schaltungsaufbau implementiert werden, der mit Fotosensoren verbunden ist, um eine Bildeigenschaft direkt zu messen.
Die vorliegende Erfindung wurde mit Bezug auf Softwareimplementierungen beschrieben, wobei die vorliegende Erfindung jedoch auch durch spezialisierte Hardware implementiert werden kann.

Claims

1. Bildverarbeitungsverfahren zum Verarbeiten von Bilddaten, die ein Bild definieren, wobei das Bild eine Bildcharakteristik relativ zu jeder einer Anzahl von Orten in dem Bild aufweist; wobei das Verfahren die Bildcharakteristik für das Bild mißt und umfaßt:

zufälliges oder pseudozufälliges Auswählen eines Probensatzes von Orten in dem Bild, wobei die Anzahl von Orten in dem Probensatz geringer als die Gesamtanzahl von Orten in dem Bild ist und Durchführen einer Messung der Bildcharakteristik relativ zu dem Ort für jeden Ort im Probensatz, um Probenergebnisdaten zu erhalten, die das Ergebnis der Messung angeben; und

Kombinieren der Probenergebnisdaten der Orte im Probensatz, um kombinierte Ergebnisdaten zu erhalten, wobei die kombinierten Ergebnisdaten eine Messung der Bildcharakteristik für das Bild angeben.

2. Bildverarbeitungsverfahren nach Anspruch 1, bei dem die Maßnahme des Auswählens des Probensatzes von Orten eine Folge von Schritten umfaßt, wobei jeder Schritt umfaßt:

zufälliges oder pseudozufälliges Erzeugen von Ortsdaten, die einen Ort angeben; und

Bestimmen, ob die Messung bezüglich des angegebenen Orts durchgeführt wird.

3. Bildverarbeitungsverfahren nach Anspruch 1 oder 2, in dem Maßnahme des Durchführens einer Messung bezüglich des Ortes umfaßt:

Durchführen einer Messung in einer Richtung, die sich von dem Ort erstreckt.