Die vorliegende Erfindung betrifft ein auf einem Papierformat basierendes Schema für Computerbenutzerschnittstellen für Dokumentverarbeitungsanwendungen.

Viele Menschen haben keinerlei Probleme bei der Bearbeitung von Dokumenten im ausgedruckten Format. Im Allgemeinen sind Dokumente im ausgedruckten Format leichter zu lesen, zu bearbeiten und zu speichern als Dokumente, die in digitaler Form vorliegen. Dafür werden keine besonderen Fachkenntnisse benötigt.

Im Allgemeinen ist es jedoch weitaus einfacher, Dokumente im digitalen Format zu bearbeiten. Text kann indexiert, durchsucht, neu formatiert, extrahiert und auf andere Weise verändert werden. Gespeicherte Dokumente können auf einfache Weise und ohne einen Qualitätsverlust kopiert und von einer Person zu einer anderen Person (beispielsweise über E-Mail) gesendet werden. Und, was ganz besonders wichtig ist, kann all dies ohne die Verwendung von Papier erreicht werden. Darüber hinaus werden digitale Kopierer und Scanner mehr und mehr sowohl in Büros als auch in Haushalten eingesetzt.

Das Bearbeiten von Dokumenten im digitalen Format erfordert jedoch typischerweise einen Zugang zu einem Computersystem oder einem Computernetzwerk. Wenn der Benutzer des Computersystems nicht über die grundlegendsten Kenntnisse oder Fähigkeiten für die Benutzung des Systems verfügt, geht dies möglicherweise zu Lasten der Produktivität. Dies stellt eine ernsthafte Hürde bei der Umsetzung eines „papierlosen Büros" dar, in dem die Dokumente im digitalen Format den vorherrschenden Dokumententyp darstellen.

Dementsprechend besteht ein Bedarf an der Fähigkeit, Dokumente in digitalem Format auf effektive Weise zu bearbeiten, und ebenso besteht ein Bedarf daran, die Umwandlung von Dokumenten in Papierform zu Dokumenten im digitalen Format zu vereinfachen.

Bisherige Versuche zum Vereinfachen der Bearbeitung digitaler Dokumente griffen oftmals auf herkömmliche Benutzerschnittstellen-Paradigmen zurück. Wenn beispielsweise ein Dokument in Papierform gescannt und in einen Dokumentenspeicher eingegeben werden soll, werden zunächst einmal Befehle dafür in einen Computer oder in eine Scannvorrichtung eingegeben, die anschließend den gewünschten Dienst an dem Dokument durchführen. Eine ähnliche Abfolge von Schritten wird durchgeführt, wenn der Ausdruck gescannt und gefaxt werden soll, gescannt und über E-Mail verschickt werden soll, gescannt und erkannt werden soll (über eine Erkennungssoftware für optische Zeichen), oder wenn eine Vielzahl von anderen möglichen Aktionen durchgeführt werden soll. Obgleich die Eingabe von Befehlen über benutzerfreundliche Software oder selbsterklärende Befehle erleichtert werden kann, sind diese zusätzlichen Schritte immer noch umständlich und erfordern möglicherweise ein bestimmtes Niveau an Fachkenntnissen. Darüber hinaus kann, wenn die Operation erst einmal durchgeführt worden ist, die Abfolge von eingegebenen Befehlen verloren gehen, und selbst bei erfahrenen Benutzern treten möglicherweise Fehler auf.

Eine weitere Möglichkeit besteht darin, ein Deckblatt zu verwenden, das ein Formular für das Spezifizieren von Befehlen enthält. Das Deckblatt wird gemäß den Wünschen des Benutzers ausgefüllt (zum Beispiel, entweder durch das handschriftliche Verfassen von Befehlen oder durch das Markieren von Auswahlfeldern), und der Scanner übersetzt die Befehle auf dem Deckblatt und bearbeitet dementsprechend das folgende Dokument. Auch diese Arbeitsweise kann sich als umständlich und relativ uneffizient erweisen, da für jede Aufgabe, die durchgeführt wird, ein spezielles Deckblatt verwendet werden muss. Es erweist sich jedoch möglicherweise als unpraktisch, einen Vorrat an geeigneten Deckblättern zu halten.

Es sind verschiedene ein- und zweidimensionale Datencodes für die Verwendung beim Speichern von digitalen Daten auf Dokumenten in Papierform bekannt und verfügbar. So sind beispielsweise verschiedene Typen von Strichcodes (zum Beispiel das bekannte UPC-Symbol, das als Symbol für Einzelhandelsprodukte verwendet wird) sehr gut bekannt und auf robuste Weise dekodierbar. Andere Beispiele von linearen Strichcodes sind unter den Bezeichnungen Code 39, Code 128, Interleaved 2 of 5 und Postnet bekannt. Das Französische Patent FR-A-2393484 offenbart ebenfalls die Verwendung von Strichcodes zum Kodieren von Faxinformationen auf Dokumenten. Zweidimensionale Codes, wie beispielsweise der PDF417-Code und der UPS MaxiCode, die von dem United Parcel Service (UPS) beispielsweise zum Aufsuchen von Paketen verwendet werden, werden immer mehr und häufiger eingesetzt.

Selbstsynchronisierende Glyphencodes, so wie beispielsweise Xerox DataGlyphs, sind für das Einbetten von maschinell lesbaren digitalen Informationen in Bildern unterschiedlichen Typs, einschließlich normalen Dokumenten in Papierform, erstrebenswert. Diese Codes weisen eine erhebliche Toleranz gegenüber Bildverzerrung und Bildrauschen auf, da die digitalen Informationen, die sie kodieren, vollständig in expliziten maschinell lesbaren Markierungen (das heißt, „Glyphen", ein Begriff, der hierin verwendet wird und von dem nicht beabsichtigt wird, dass er sich auf die Xerox DataGlyphs beschränkt, sondern beabsichtigterweise sämtliche maschinell lesbaren Markierungen einbezieht) eingebettet und durch sie definiert sind. Diese Glyphen kodieren nicht nur die Information, die in dem Code eingebettet ist, sondern definieren auch den Abtasttakt, der zum Extrahieren dieser Information aus dem Code verwendet wird, dementsprechend sind sie also für die „selbstsynchronisierende" Eigenschaft des Codes und auch für die Toleranz gegenüber Bildverzerrung und Bildrauschen verantwortlich.

Ein weiterer bekannter Vorteil der selbstsynchronisierenden Glyphencodes besteht darin, dass sie für gewöhnlich ein unauffälliges sichtbares Erscheinungsbild aufweisen. Dies ist insbesondere bei den Codes der Fall, die aus Glyphen gebildet sind, welche auf einem zweidimensionalen räumlich periodischem Muster an Mitten geschrieben sind, so wie beispielsweise ein regelmäßiges gitterähnliches Muster an Mitten, da der Code durch die räumliche Periodizität der Glyphen veranlasst wird, ein mehr oder weniger einheitlich texturiertes Erscheinungsbild aufzuweisen. So werden beispielsweise logisch geordnete digitale Einzelbit-Quanten typischerweise durch jeweilige längliche schrägstrichähnliche Glyphen kodiert, die auf ein zweidimensionales räumlich periodisches Muster an Mitten in Übereinstimmung mit einer vorgegebenen Regel für räumliches Formatieren geschrieben werden, wobei die einzelnen Glyphen zum Kodieren der logischen „0-en" und „1-en" um ungefähr +45° und –45° von der Vertikalen aus jeweils nach links oder nach rechts geneigt sind. Die wechselseitige Orthogonalität der Glyphenkodierungen für die zwei logischen Zustände dieser digitalen Einzelbit-Quanten verbessert die Unterscheidbarkeit des Codes ausreichend genug dafür, dass die eingebetteten Informationen wieder aufgerufen werden können, selbst dann, wenn das Codemuster auf einem ausreichend feingekörntem Muster der Mitte geschrieben wird, um das Codemuster zu veranlassen, ein allgemein einheitliches Graustufenerscheinungsbild aufzuweisen. Es sollte jedoch darauf hingewiesen werden, dass demonstriert worden ist, dass selbstsynchronisierende Glyphencodes auch so eingerichtet werden können, dass sie digitale Mehrbit-Quanten in den Glyphen kodieren können.

Das Europäische Patent Nr. EP-A-0469864 offenbart das Einbetten von selbstsynchronisierenden Glyphencodes in einem Dokument, um das Dokument zu befähigen, mit einem Dokumentenverarbeitungssystem zu interagieren, wenn das Dokument in das System eingescannt wird. Dieses Verfahren erweist sich jedoch als unflexibel und erfordert ein bestimmtes implizites Wissen von dem Benutzer.

In Anbetracht dessen wäre es wünschenswert, eine Lösung bereitzustellen, die die Verwendung von Dokumenten in digitalem Format und die Umwandlung von Dokumenten in Papierform zu Dokumenten in digitalem Format vereinfacht. Solch eine Lösung sollte einfach, effizient und nützlich sein und gar kein oder nur wenig Fachwissen von dem Benutzer erfordern.

In Übereinstimmung mit der vorliegenden Erfindung umfasst ein Verfahren für das Verarbeiten eines Dokumentes auf Basis von Informationen in einem Benutzerschnittstellen-Etikett die folgenden Schritte:

Spezifizieren eines Dienstes, der sich auf das Dokument bezieht;

Aufbringen des Benutzerschnittstellen-Etiketts auf dem Dokument, wobei das Benutzerschnittstellen-Etikett auf jeder Position auf dem Dokument an geordnet sein kann;

Abtasten des Dokumentes und des aufgebrachten Benutzerschnittstellen-Etiketts, um ein Bild zu erzeugen, das das Dokument und das Benutzerschnittstellen-Etikett darstellt;

Lokalisieren der Darstellung des Benutzerschnittstellen-Etiketts in dem Bild;

Dekodieren der in der Darstellung des Benutzerschnittstellen-Etiketts vorhandenen Daten;

Assoziieren der dekodierten Daten mit dem spezifizierten Dienst und

Durchführen des spezifizierten Dienstes.

Dementsprechend stellt die Erfindung ein auf Etiketten basierendes Benutzerschnittstellenschema zum Durchführen von Diensten an einem Dokument in Papierform je nach Benutzer- oder Dienstinformationen, die als gedruckte Daten auf einem Etikett gespeichert sind, das mit dem Dokument assoziiert ist, bereit.

Die vorliegende Erfindung verwendet ein Schema kodierter Etiketten, wie zum Beispiel selbstklebende Aufkleber oder Schildchen, die als die primäre Benutzerschnittstelle in einem Verarbeitungssystem für Dokumente in Papierformat fungieren. Mit solch ein System kann der Benutzer eine Aktion oder einen Dienst, die/der durchgeführt werden soll, sowie seine eigene Identität auf einfache Weise durch Aufbringen eines Aufklebers auf dem Dokument und durch Platzieren des Dokumentes in eine zu scannenden Ablage spezifizieren.

Die Aufkleber sind relativ klein und von unauffälligem Erscheinungsbild, und in einer Ausführungsform der vorliegenden Erfindung werden Xerox DataGlyphs zum Kodieren der Identität des Benutzers, eines gewünschten Dienstes und eines optionalen Argumentes für den Dienst verwendet. Der Benutzer hält einen Vorrat an Aufklebern, die einem bestimmten Dienst (zum Beispiel „Scannen und an mein persönliches E-Mail-Konto senden") entsprechen. Wenn der Benutzer wünscht, dass dieser bestimmte Dienst durchgeführt werden soll, bringt er einfach einen der passenden Aufkleber dem Dokument auf.

Ein Beispiel eines Computersystems, das die Erfindung ausführt, ist so eingerichtet, dass es zunächst eine Information über die Identität des Benutzers akzeptiert. Dies kann beispielsweise dadurch erreicht werden, dass eine der Visitenkarten des Benutzers gescannt und analysiert wird. Diese Informationen werden in einer Datenbank gespeichert und mit einer eindeutigen Benutzer-ID-Nummer versehen. Anschließend druckt das System einen maßgeschneiderten Satz an Etiketten aus, die die Benutzer-ID und den Dienst darstellen, aus.

Wenn der Benutzer anschließend wünscht, dass der durch seine Aufkleber spezifizierte Dienst durchgeführt werden soll, bringt er einfach einen der Aufkleber auf dem Dokument auf und platziert es in eine Warteschlange für das Scannen. Das Dokument wird gescannt, der Aufkleber wird identifiziert und dekodiert, er wird erneut mit den aus der Datenbank aufgerufenen Benutzerinformationen assoziiert, und der gewünschte Dienst wird ausgeführt.

Wie dies ersichtlich ist, kann dieses System so eingerichtet sein, dass es eine Vielzahl von Diensten und Aktionen ausführen kann, einschließlich, aber nicht beschränkt auf das einfache Scannen und Speichern des Dokumentes in einem Speicher, das Faxen des Dokumentes, das Umwandeln des Dokumentes in ein standardmäßiges elektronisches Format (wie beispielsweise ein Microsoft Word Format), sowie weitere.

Dementsprechend erweist sich die auf Aufklebern basierende Benutzerschnittstelle der vorliegenden Erfindung als praktisch und einfach, da sie es nicht erforderlich macht, dass der Benutzer Befehle in ein Computersystem eingeben muss, oder dass er für jedes Dokument, das verarbeitet werden soll, ein Deckblatt ausfüllen muss. Sie erweist sich dahingehend als effektiv, dass der Benutzer lediglich einen Vorrat an kleinen Aufklebern halten muss.

Im Folgenden werden in Bezug auf die beigefügten Zeichnungen einige Beispiele der Verfahren und Aufkleber in Übereinstimmung mit der Erfindung beschrieben. In den Zeichnungen ist:

1 ein exemplarischer Glyphen-Aufkleber;

2 ist ein exemplarisches Blockdiagramm, das eine Datenstruktur illustriert, die durch den in 1 gezeigten Glyphen-Aufkleber dargestellt wird;

3 ist ein Blockdiagramm des gesamtem Systems;

4 ist ein ausführlicher Funktionsablaufplan der Funktion des Aufklebererzeugens der Erfindung;

5 ist ein Funktionsablaufplan der Funktion der Aufkleberverarbeitung der Erfindung;

6 ist ein Ablaufplan, der die Abfolge der Schritte darstellt, die beim Lokalisieren des Aufklebers durchgeführt werden, so wie dies in 5 beschrieben ist;

7 ist ein Ablaufplan, der die Abfolge der Schritte darstellt, die beim Dekodieren des Aufkleber durchgeführt werden, so wie dies in 5 beschrieben ist;

8 illustriert einen Abschnitt eines exemplarischen Gitters von Glyphen mit assoziierten Glyphen-Bitmaps und Glyphen-Gittervektoren;

9 ist ein Ablaufplan, der die Abfolge der Schritte darstellt, die beim Bestimmen des Gitters von Glyphen durchgeführt werden, so wie dies in 7 beschrieben ist;

10 ist ein schematisches Diagramm, das die Suchrichtungen darstellt, die bei der Suche nach Glyphen verwendet werden, so wie dies in 7 dargestellt ist;

11 ist ein Ablaufplan, der die Abfolge von Schritten darstellt, die beim Suchen eines Ausgangsglyphen durchgeführt werden, so wie dies in 7 beschrieben ist;

12 ist ein schematisches Diagramm, das die Vorgehensweise darstellt, die für das Suchen sämtlicher Glyphen, so wie dies in 7 gezeigt ist, verwendet wird;

13 ist ein Ablaufplan, der die Abfolge der Schritte darstellt, die für das Suchen sämtlicher Glyphen in der Nähe des Ausgangsglyphen durchgeführt werden, so wie dies in 7 dargestellt ist; und

14 ist ein Ablaufplan, der die Schritte darstellt, die beim Dekodieren eines Glyphenmusters durchgeführt werden.

1 illustriert ein exemplarisches Muster eines Glyphen-Aufklebers 110, das in Übereinstimmung mit der Erfindung als ein Benutzerschnittstellen-Etikett in Papierform fungiert. Hierbei sollte beachtet werden, dass dieses Muster 110 nicht auf einen bestimmten Maßstab festgelegt ist; es wurde in Betracht gezogen, dass es in der Größenordnung von 1 Inch (2,5 cm) oder weniger in der vertikalen Richtung liegt; es wurde für diesen Fall im Sinne einer verständlichen Erklärung und für ein erleichtertes Identifizieren der Einzelheiten jedoch wesentlich vergrößert.

Während darüber hinaus das Benutzerschnittstellen-Etikett der Erfindung in 1 als ein selbstklebender Aufkleber dargestellt ist, der auf Dokumenten aufgebracht werden kann, sollte hierbei beachtet werden, dass das Muster 110 auch auf Formulare, Einschießbögen, Deckblätter, Visitenkarten, Ausweiskarten, Namensschilder und andere Objekte aufgebracht werden kann, die mit einem Objekt assoziiert werden können, und die darüber hinaus in der Lage sind, maschinell lesbare Informationen zu tragen. So können beispielsweise in einer alternativen Ausführungsform der Erfindung Reversnadeln, die das Muster 110 tragen, mit einem Dokument assoziiert werden, indem die Reversnadel genau zu dem Zeitpunkt, zu dem das Dokument gescannt und verarbeitet wird, gescannt wird (zum Beispiel mit einem tragbaren Laser-Scanner).

Wie dies dargestellt ist, enthält das Glyphen-Aufklebermuster 110 mehrere wichtige Eigenschaften. Eine im Wesentlichen rechteckige Umrandung 111 umgibt die verbleibenden Merkmale und ist selbst wiederum von weißem Raum 113 umgeben. Ein Glyphenfeld 112 enthält eine gedruckte Darstellung der digitalen Daten, die zum Durchführen der Ziele der Erfindung verwendet werden; die Struktur und die Inhalte des Glyphenfeldes 112 werden im Folgenden ausführlicher beschrieben. An dieser Stelle sollte beachtet werden, dass das in 1 dargestellte Glyphenfeld 112 mit der Verwendung von Xerox DataGlyphs dargestellt ist. Es wird jedoch noch offensichtlich werden, dass jegliche wiedergewinnbare gedruckte Darstellung von digitalen Informationen, einschließlich, jedoch nicht beschränkt auf Strichcodes, ein- und zweidimensionale Datenmuster und optisch erkennbare alphanumerische Zeichen, in alternativen Ausführungsformen der Erfindung ebenfalls und mit ähnlichem Effekt verwendet werden können.

Es können auch noch weitere identifizierende Elemente innerhalb des Glyphen-Aufklebermusters 110 vorhanden sein. So sind beispielsweise das „Digital X" 114 von Xerox und die eingetragene Marke „PaperWare^®" 116 vorhanden und werden aus Gründen der Ästhetik sowie als Markenzeichen verwendet. Darüber hinaus ist auch die Wortgruppe „The Person" 118 (Die Person) vorhanden; es wird in Betracht gezogen, dass dieses Feld für eine visuelle Identifizierung durch eine Anzeige des Namens des Benutzers oder durch andere Informationen ersetzt werden kann. Es ist auch ein Umrandungsabschnitt 120 vorhanden, der eine umgeknickte Seite darstellt. Dieser Umrandungsabschnitt 120 kann aus bloßen ästhetischen Gründen vorhanden sein, oder er kann durch die Erfindung mit dem Ziel verwendet werden, das Bestimmen der richtigen Ausrichtung des Glyphen-Aufklebermusters 110 zu vereinfachen. Dieser Aspekt der Erfindung wird im Folgenden ausführlicher beschrieben.

Im Folgenden wird in Bezug auf 2 eine durch das Glyphenfeld 112 ausgeführte exemplarische Datenstruktur 210, so wie diese dargestellt ist, beschrieben. Die Datenstruktur 210 enthält einen Dienstcode 212, der in einer Ausführungsform der Erfindung ein einzelnes Byte (acht binäre Bits) umfasst. Dementsprechend kann der Dienstcode 212 bis zu 256 mögliche unterschiedliche Aktionen, Umwandlungen und Dienste darstellen. Exemplarische Dienste können solche wie „in Dokumentenspeicher scannen", „scannen und über E-Mail senden", „scannen und faxen", „scannen und Kopien drucken" und so weiter umfassen, sie sind aber nicht auf die Genannten beschränkt. Ein angezeigter Dienst kann ohne Einschränkung eine Vielzahl von Aktionen (beispielsweise Scannen, anschließendes Erkennen der Zeichen, danach Senden des Textes per E-Mail) umfassen, und der Dienst kann auch die Umwandlung des Dokumentes von dem Papierformat in das elektronische Format und möglicherweise zurück in das Papierformat umfassen. Darüber hinaus können ein oder mehrere mögliche Schritte das Entfernen oder das Ändern des Glyphen-Aufklebermusters 110 auf dem digitalisierten Bild des Dokumentes umfassen, da sein Vorhandensein nicht länger erforderlich ist (und möglicherweise von dem Erscheinungsbild des Dokumentes ablenkt), wenn es erst einmal durch das System und das Verfahren der Erfindung bearbeitet worden ist.

Ein Dienstargument 214 stellt dem Dienstcode 212 ein codiertes Argument zur Verfügung. In einer Ausführungsform der Erfindung handelt es sich bei dem Argument 214 um ein zusätzliches Byte (acht Bits) an Informationen. So können beispielsweise bestimmte Dienste ein numerisches Argument erfordern (so werden zum Beispiel bei dem Dienst „scannen und Kopien drucken", an den sich ein Argument von „10" anschließt, 10 Kopien gedruckt). Andere Dienste können ein auf eine andere Weise codiertes Argument erfordern (zum Beispiel kann der Dienst „scannen und faxen", an den sich ein Argument von „2" anschließt, einen Befehl zum Faxen des Dokumentes zu der privaten Faxnummer des Benutzers im Gegensatz zu der geschäftlichen Faxnummer, oder vielleicht zu einer alternativen Faxnummer, darstellen, von denen beide unterschiedliche Argumentzahlen aufweisen). Es können auch viele andere Verwendungen des Dienstargumentes 214 in Betracht gezogen werden, ohne dass dabei von dem Umfang der Erfindung abgewichen wird.

Ein Identitätscode 216 macht den Großteil der verbleibenden Datenstruktur 210 aus. In einer Ausführungsform der Erfindung enthält der Identitätscode sechzehn Bytes an Identitätsinformationen (ausreichend zum Kodieren einer eindeutigen Identifikationsnummer für ein jedes Mitglied einer nahezu beliebig vorstellbaren Population) und acht Bytes an Sicherheitsinformationen, wobei durch die Letztgenannten der Identitätscode im Wesentlichen fälschungssicher gestaltet wird. Die Identitätsinformationen sind aus der Netzwerkadresse (entweder eine Ethernet-Adresse oder eine IP-Adresse) der Vorrichtung, die den Identitätscode ausstellt, einem Zeitstempel und einer Laufnummer gebildet. Obgleich nicht garantiert ist, dass eine Nummer, die auf diese Weise gebildet ist, unter allen Umständen (wenn zum Beispiel die Datenbank der Laufnummern verloren geht und derselbe Zeitstempel versehentlich zwei Mal verwendet wird) eindeutig ist, ist sie doch ziemlich robust und für die Zwecke der Erfindung in ausreichendem Maße eindeutig. Es sollte darüber hinaus beachtet werden, dass der Identitätscode mit einer beliebigen einer Vielzahl von anderen Möglichkeiten gebildet werden kann, von denen alle für die Verwendung der vorliegenden Erfindung akzeptabel sind.

Darüber hinaus enthält die Datenstruktur 210 auch Fehlerkorrektur- und Synchronisationsinformationen in den gesamten spezifizierten Datenfeldern auf eine Weise, die auf dem Gebiet der Technik gut bekannt ist und die in 2 nicht dargestellt ist.

3 stellt einen Überblick des Systems der Erfindung dar, bei dem das System in verschiedene funktionale Elemente, die ausführlicher dargestellt sind, aufgeteilt ist. Ein „Front-End-"Abschnitt 310 empfängt Informationen von einem Dateneingang 312. Der Dateneingang 312 kann eine Tastatur, ein Visitenkartenscanner, eine Spracherkennungseinrichtung oder eine beliebige andere Vorrichtung der Datenerfassung umfassen, die zum Empfangen von Daten, die die Identität des Benutzers darstellen, eingerichtet ist. Von dem Dateneingang 312 kann erwartet werden, dass dieser den Namen des Benutzers, seine Firma, den Titel, die Adresse, eine oder mehrere Telefonnummern, eine oder mehrere E-Mail-Adressen, ebenso wie andere mögliche Identifizierungsinformationen (so wie beispielsweise eine US-amerikanische Sozialversicherungsnummer [Social Security Number] oder eine Konferenz-ID-Nummer) empfängt. Diese Benutzerinformationen werden anschließend durch einen Identitätsprozessor 314 empfangen, der die Informationen als Eintrag in einer Datenbank speichert, die durch einen Datenbankserver 316 unterhalten wird. Zur gleichen Zeit werden die Benutzerinformationen durch den Identitätsprozessor 314 verarbeitet, um den Identitätscode 216 zu erzeugen (der die oben beschriebenen Identitäts- und Sicherheitsinformationen beinhaltet). Anschließend werden der Identitätscode 216 und ein beliebiger gewünschter optionaler Dienstcode 212 und ein Dienstargument 214 kodiert und durch einen Drucker 318 oder eine andere Papierausgabevorrichtung, die sich in Kommunikation mit dem Identitätsprozessor 314 befindet, gedruckt.

Wenn der Benutzer wünscht, dass ein Dokument verarbeitet werden soll, bringt er einen Glyphen-Aufkleber in Übereinstimmung mit der Erfindung auf dem Dokument auf und platziert das Dokument in einem Scanner 320, welcher Teil eines „Back-End"-Abschnittes 319 des Systems ist. Der Scanner ist vorzugsweise ein automatischer Scanner, der in der Lage ist, mehrere Aufgaben durchzuführen und aus mehreren Seiten bestehende Dokumente zu bearbeiten, ohne das dabei der Benutzer agieren muss. In dieser Anwendung kann jedoch auch ein beliebiger anderer Typ von Digitalisiervorrichtung (wie beispielsweise ein Flachbrettscanner, ein Digitalkopierer und ein tragbarer Scanner) verwendet werden. Der Scanner 320 liest das Dokument und formuliert ein Bitmap, das das Dokument (und den Glyphen-Aufkleber auf dem Dokument) darstellt.

Ein Aktionsprozessor 322 liest das von dem Scanner 320 empfangene Bitmap, identifiziert und kodiert den Glyphen-Aufkleber und greift auf den Datenbankserver 316 zu, um die Identität des Benutzers zu bestimmen. Der gewünschte Dienst kann anhand des Zugreifens auf eine Liste von möglichen Diensten, die lokal auf dem Aktionsprozessor 322 gespeichert ist, bekannt sein, oder er kann auch durch Zugreifen auf eine Dienst-Datenbank auf dem Datenbankserver 316 bestimmt werden, oder, alternativ dazu, kann er auch einfach anhand der Identität des Benutzers hergeleitet werden.

Auf Basis der Benutzeridentität und des gewünschten Dienstes veranlasst der Aktionsprozessor 322 anschließend, dass der gewünschte Dienst ausgeführt wird, was das Erzeugen eines umgewandelten Dokumentes durch ein Ausgabegerät 324 umfassen kann. Das Ausgabegerät 324 wird an dieser Stelle als ein allgemeines charakterisiert, es kann jedoch, wie dies voranstehend beschrieben wurde, einen Papierdrucker, eine Faksimilevorrichtung (oder ein Modem, das Faxe senden kann), eine Netzwerkverbindung für E-Mails, eine Verbindung zu einem Dokumentenspeicher, eine digitale Speichervorrichtung (wie beispielsweise ein Diskettenlaufwerk), oder eine Kombination aus einigen oder sämtlichen dieser Funktionen umfassen.

Während das System aus 3 auf eine Weise dargestellt ist, bei der es in mehrere funktionale Blöcke unterteilt ist, sollte beachtet werden, dass die dargestellten Funktionen auf einem einzigen Computersystem oder durch mehrere Computer, die über ein Kommunikationsnetzwerk miteinander verbunden sind, ausgeführt werden können. Als ein spezifisches Beispiel kann der Datenbankserver 316 lokal in dem Identitätsprozessor 314 oder dem Aktionsprozessor 322 angeordnet sein, oder es kann sich dabei um einen separaten Prozessor, der sich über ein Kommunikationsnetzwerk, wie beispielsweise dem Internet oder einem firmeneigenen Intranet in Kommunikation mit den anderen Elementen befindet, handeln.

Wie dies voranstehend durch 3 dargestellt wurde, findet die Front-End-Verarbeitung des Systems, nämlich das Erzeugen der Glyphen-Aufklebermuster 110 auf Basis der Benutzerinformationen und eines gewünschten Dienstes, als eine Folge von Schritten statt. Diese Schritte sind in dem in 4 dargestellten Ablaufplan illustriert.

Zunächst gibt der Benutzer (oder eine andere Person) Informationen in das System ein (Schritt 420), typischerweise über den Dateneingang 312 (3). Anschließend werden sämtliche der Informationen in der Datenbank auf dem Datenbankserver 316 gespeichert (Schritt 412). Anschließend wird ein Dienst ausgewählt (Schritt 414). Der Dienst kann aus einem „Menü" von möglichen Diensten ausgewählt werden, oder, in einer Ausführungsform der Erfindung, kann auch lediglich ein einziger Dienst eingerichtet sein. In dem letzteren Fall können der Dienstcode 212 und das Dienstargument 214 (2) optional von dem Glyphen-Aufklebermuster 110 weggelassen werden.

Anschließend werden der Benutzeridentitätscode 216, der Dienstcode 212 und das Dienstargument 214 kodiert und zu einem Glyphenfeld 112 gebildet, das die Informationen darstellt (Schritt 416). Das neu erzeugte maßgeschneiderte Glyphenfeld 112 wird anschließend als Glyphen-Aufklebermuster 110 eine beliebige Anzahl von Malen auf eine beliebige Anzahl von Aufklebern für eine spätere Verwendung durch den Benutzer gedruckt (Schritt 418).

5 ist ein Ablaufplan, der darstellt, was passiert, nachdem der Benutzer einen Aufkleber auf einem Dokument aufgebracht hat und es für das Scannen bereitgestellt hat. Zunächst wird das Dokument gescannt (Schritt 510), und das resultierende Bitmap wird für die Verarbeitung zurückbehalten. Das ursprüngliche Dokument in Papierform kann zu diesem Zeitpunkt zu dem Benutzer zurückgeführt werden, da es durch das System der Erfindung nicht länger benötigt wird.

Anschließend wird das Glyphen-Aufklebermuster 110 auf dem Dokument lokalisiert (Schritt 512). In einer bevorzugten Ausführungsform der Erfindung wird das Glyphen-Aufklebermuster mit Hilfe eines im späteren Verlauf im Zusammenhang mit 6 beschriebenen Verfahrens der Rechteckanpassung lokalisiert. In einer alternativen Ausführungsform der Erfindung wird der Benutzer dazu aufgefordert, den Glyphen-Aufkleber auf einer bestimmten Position auf dem Dokument (beispielsweise auf der oberen rechten Ecke der ersten Seite) zu platzieren, wodurch die Operationen vereinfacht werden, die erforderlich sind, um das Glyphen-Aufklebermuster 110 zu lokalisieren. In einer weiteren alternativen Ausführungsform kann das Aufklebermuster 110 auf einer beliebigen Position auf einem Dokument lokalisiert werden, indem das gescannte Dokumentenbitmap in Text- und Grafikabschnitte unterteilt wird, und indem in den Zeilengrafikabschnitten die Zeilen im rechten Winkel, die die Umrandung des Glyphen-Aufklebermusters 110 ausmachen, lokalisiert werden. Ein Verfahren, mit dessen Hilfe dies erzielt wird, wird auf ausführliche Weise in dem US-Patent Nr. 5.202.933 von Bloomberg, mit dem Titel „SEGMENTATION OF TEXT AND GRAPHICS", das durch Verweis ein Bestandteil der vorliegenden Beschreibung bildet, als ob es vollständig beschrieben wird, beschrieben. Um dies zu vereinfachen, können Bereiche mit Halbtönen und Bereiche fein texturierten Grafiken (wie beispielsweise lithographierte Photographien) mit Hilfe der Verfahren, die in den US-Patenten mit den Nummern 5.065.437 und 5.131.049 gelehrt werden, ebenfalls in Segmente (und von den Zeilengrafiken weg) unterteilt werden. Hierbei sollte beachtet werden, dass das Glyphen-Aufklebermuster 110 in nahezu jeder Ausrichtung vorhanden sein kann und dass das Verfahren zur Segmentierung dementsprechend so eingerichtet sein sollte, dass mehrere unterschiedliche Ausrichtungen geprüft werden (unter Verwendung von unterschiedlich geformten strukturierenden Elementen in den morphologischen Operationen, die in dem hierein verwiesenen Patentdokument '933 zum Identifizieren der horizontalen und der vertikalen Zeilen verwendet werden), bevor bestimmt wird, dass kein Aufkleber vorhanden ist. Schließlich kann auch ein auf dem Hausdorff-Abstand basierender Algorithmus verwendet werden; hierbei sollte beachtet werden, dass dieses Verfahren, ebenso wie das voranstehend beschriebene morphologische Verfahren, rotationssensitiv und demzufolge hinsichtlich des Rechenaufwandes relativ ineffektiv ist.

Wenn das Glyphen-Aufklebermuster 110 lokalisiert worden ist, werden anschließend die Daten innerhalb des Glyphenfeldes 112 dekodiert (Schritt 514). Dies wird durch Verfahren erzielt, die im weiteren Verlauf der Beschreibung im Zusammenhang mit den 7 bis 14 ausführlicher beschrieben werden. Anschließend werden die Daten mit den Benutzeridentifikationsinformationen (die von dem Datenbankserver 316 empfangen wurden) assoziiert (Schritt 516), und der Dienst wird durch Vorgehensweisen, die auf dem Gebiet der Technik bekannt sind und voranstehend erwähnt wurden, durchgeführt (Schritt 518).

In 6 ist ein vorliegend bevorzugtes Verfahren dargestellt, das verwendet wird, um Benutzerschnittstellen-Etiketten (beispielsweise das in 1 dargestellte Glyphen-Aufklebermuster 110) innerhalb eines digitalisierten Bildes zu lokalisieren. Dieses Verfahren kann zum Identifizieren und Lokalisieren von Objekten verwendet werden, die eine annähernd rechteckige Form aufweisen, so wie beispielsweise die bildhafte Darstellung einer Seite, bei der eine Ecke umgeknickt ist, so wie diese als Glyphen-Aufklebermuster 110 in einer Ausführungsform der Erfindung verwendet wird (siehe 1). Solche rechteckigen Objekte können durch eine Höhendimension und durch eine Breitendimension charakterisiert werden. Das Verfahren zur Identifizierung kann das gewünschte Muster in einer jeden beliebigen Ausrichtung und mit relativ geringen Maßstabsabweichungen (so wie jene, die in den Druck- und in den Digitalisierungsprozessen auftreten) identifizieren, selbst wenn Bildrauschen auftritt.

Das Verfahren funktioniert bei monochromatischen Bildern (das heißt, binären Bildern, die mit lediglich einem Bit pro Pixel dargestellt sind). Wenn das Bild in einem anderen Format vorliegt (so wie beispielsweise als Farb- oder Graustufenbild), sollte es zunächst, als eine Vorstufe zu dem in 6 beschriebenen Verfahren, in ein binäres Format umgewandelt werden, typischerweise mit Hilfe einer Schwellenwertfunktion oder durch Pixelschattierung.

Es wird davon ausgegangen, dass die Eigenschaften (zum Beispiel die Auflösung) der verwendeten Digitalisierungsvorrichtung bekannt sind. Dementsprechend kann, da die absolute Größe des Glyphen-Aufklebermusters 110 (1) bekannt ist, auch seine Bildgröße berechnet werden. Dementsprechend ist die erwartete Breite w und die erwartete Höhe h des Musters 110, in Pixeln, entweder bekannt, oder sie können auf einfache Weise berechnet werden. Mit der Höhen- und der Breitentoleranz (&Dgr;w beziehungsweise &Dgr;h), um geringfügige Abweichungen im Maßstab, wie voranstehend beschrieben, zu berücksichtigen, wäre eine minimale erwartete Breite w_min = (w – &Dgr;w), eine maximale erwartete Breite wäre w_max = (w + &Dgr;w), eine minimale erwartete Höhe wäre h_min = (h + &Dgr;h), und eine maximale erwartete Höhe wäre h_max = (h + &Dgr;h). In einer vorliegend bevorzugten Ausführungsform sind &Dgr;h = (0,1)h und &Dgr;w = (0,1)w, oder anders formuliert, betragen die Toleranzen 10% der jeweiligen Höhe und Breite. Hierbei sollte jedoch beachtet werden, dass auch andere Toleranzbereiche möglich sind, und dass für die Breitendimension und für die Höhendimension jeweils unterschiedliche Toleranzen verwendet werden können.

Dementsprechend und basierend auf den voranstehenden Ausführungen wären die minimalen und die maximalen erwarteten diagonalen Abessungen jeweils d_min = √(w – &Dgr;w)² + (h – &Dgr;h)² und d_max = √(w + &Dgr;w)² + (h + &Dgr;h)².

Nachdem ein geeignetes digitalisiertes Bild verfügbar ist, werden anfänglich sämtliche verbundenen Komponenten innerhalb des Bildes identifiziert (Schritt 610). Bei einer verbundenen Komponente handelt es sich um eine Gruppe von Pixeln eines einzigen Wertes (beispielsweise des Wertes, der Schwarz darstellt), in der es möglich ist, von jedem beliebigen Pixel der Gruppe zu jedem anderen beliebigen Pixel in der Gruppe einen Pfad zu bilden, ohne die Gruppe zu verlassen (indem beispielsweise lediglich die schwarzen Pixel durchquert werden). Im allgemeinen Sinne kann eine verbundene Komponente „mit 4 verbunden" oder „mit 8 verbunden" sein. In dem Fall, in dem die Komponente mit 4 verbunden ist, kann sich der Pfad lediglich in die horizontale Richtung und in die vertikale Richtung bewegen, dementsprechend gibt es vier mögliche Richtungen. Dementsprechend sind zwei diagonal aneinander angrenzende schwarze Pixel nicht mit 4 verbunden, es sei denn, es ist ein weiteres schwarzes Pixel horizontal oder vertikal angrenzend vorhanden und dient als Brücke zwischen den beiden. In dem Fall, in dem die Komponente mit 8 verbunden ist, kann der Pfad zwischen den Pixeln auch in diagonaler Richtung verlaufen. Eine vorliegend bevorzugte Ausführungsform der Erfindung verwendet Komponenten, die mit 8 verbunden sind, es hat sich jedoch herausgestellt, dass auch Komponenten, die mit 4 verbunden sind, identifiziert und verwendet werden können.

Da die Umrandung 111 des Glyphen-Aufklebermusters 110 (1) von einer einzelnen Gruppe von kontinuierlichen schwarzen Pixeln gebildet ist, sollte hierbei beachtet werden, dass die Umrandung 111 eine einzelne verbundene Komponente umfasst. In einer bevorzugten Ausführungsform der Erfindung ist der weiße Raum 113 um die Umrandung 111 herum ausreichend breit, um sicherzustellen, dass die Umrandung 111 nicht versehentlich mit einem anderen Abschnitt des Dokumentes in der Papierform verbunden ist, auf dem das Glyphen-Aufklebermuster 110 aufgebracht wird. Darüber hinaus ist die Umrandung 111 auch ausreichend dick, um sicherzustellen, dass sie nicht versehentlich durch Bildrauschen in einzelne Komponenten aufgeteilt wird.

Die verbundenen Komponenten innerhalb des Bildes werden durch eine auf dem Gebiet der Technik bekannte Vorgehensweise identifiziert (das heißt, indem mit einem einzelnen schwarzen Pixel innerhalb des Bildes angefangen wird, alle verbundenen Pixel rekursiv so lange lokalisiert werden, bis die verbundene Komponente vollständig definiert ist, und der Vorgang so lange wiederholt wird, bis sämtliche schwarze Pixel innerhalb des Bildes zu einer verbundenen Komponente gehören). Es können jedoch auch andere Vorgehensweisen des Identifizierens von verbundenen Komponenten mit einem ähnlichen Effekt angewendet werden.

Anschließend wird jede verbundene Komponente einzeln verarbeitet. Wenn irgendwelche verbundenen Komponenten für die Verarbeitung übrig bleiben (Schritt 611), wird das Verfahren auf die folgende Weise fortgesetzt. Wenn die verbundene Komponente zu klein ist (Schritt 612), das heißt, wenn seine Breite oder seine Höhe kleiner als ein minimaler erwarteter Wert ist, wird die verbundene Komponente verworfen (Schritt 614). In einer Ausführungsform der Erfindung ist der minimale erwartete Wert, der sowohl für die Höhe als auch für die Breite verwendet wird, der kleinere von h_min und w_min, womit eine mögliche Rotation des Musters 110 berücksichtigt wird. Die verbundene Komponente wird ähnliche Weise verworfen (Schritt 614), wenn sie zu groß ist (Schritt 616) und seine Breite oder seine Höhe den maximalen erwarteten Wert um ein erhebliches Maß übersteigt. In einer Ausführungsform der Erfindung ist der maximale erwartete Wert, der sowohl für die Höhe als auch für die Breite verwendet wird, wesentlich größer als der größere Wert von h_max und w_max, womit eine mögliche Rotation berücksichtigt wird. Wenn das Muster 110 (oder ein beliebiges Rechteck) in einem Winkel ausgerichtet ist, kann seine Breite und seine Höhe größer als erwartet erscheinen und sich dabei dem Wert von d_max annähern oder ihm entsprechen. Dementsprechend wird in die letztgenannte Markierung ein Puffer integriert.

Anschließend werden acht Extrempunkte, einen für jede der acht „Kompasspositionen" aus der Gruppe von Pixeln ausgewählt (Schritt 618), die die verbundene Komponente C ausmachen. Jeder Punkt hat eine Position, die durch ein Koordinatenpaar (x, y) dargestellt ist, und er stellt ein Pixel der verbundenen Komponente C dar, das sich innerhalb der Bildebene am weitesten in die ausgewählte Richtung (Nord, Nordost, Ost, Südost, Süd, Südwest, West oder Nordwest) ausdehnt. Jeder Extrempunkt wird auf die folgende Weise ausgewählt: N = (x_N, y_N) ∊ C|y_N ≤ y∀(x, y) ∊ C E = (x_E + y_E) ∊ C|x_E ≥ x∀(x, y) ∊ C S = (x_S, y_S) ∊ C|y_S ≥ y∀(x, y) ∊ C W = (x_W, y_W) ∊ C|x_W ≤ x∀(x, y) ∊ C NE = (x_NE, y_NE) ∊ C|(x_NE – y_NE) ≥ (x – y)∀(x, y) ∊ C SE = (x_SE, y_SE) ∊ C|(x_SE + y_SE) ≥ (x + y)∀(x, y) ∊ C SW = (x_SW, y_SW) ∊ C|(x_SW – y_SW) ≤ (x – y)∀(x, y) ∊ C NW = (x_NW, y_NW) ∊ C|(x_NW + y_NW) ≤ (x + y)∀(x, y) ∊ C

Hierbei sollte beachtet werden, dass beim Identifizieren der acht Extrempunkt verschiedene Optimierungen durchgeführt werden können. Wenn beispielsweise die verbundene Komponente C in horizontale Folgen von kontinuierlichen Pixeln aufgeteilt wird, muss lediglich das am weitesten links liegende Pixel in einer jeden Folge als ein Kandidat für die Extrempunkte NW [Nordwest], W [West] und SW [Südwest] in Betracht gezogen werden werden, und lediglich das am weitesten rechts liegende Pixel in einer jeden Folge muss als Kandidat für die Extrempunkte NE [Nordost], E [Ost] und SE [Südost] in Betracht gezogen werden. Wenn darüber hinaus die horizontalen Folgen in vertikaler Richtung angeordnet sind, müssen lediglich die Endpunkte der am weitesten oben liegenden und der am weitesten unten liegenden Folgen für die Extrempunkte N [Nord] und S [Süd] in Betracht gezogen werden. Darüber hinaus sollte beachtet werden, dass, wenn die Umrandung 111 (1) genau in einem beliebigen 45°-Intervall von oben rechts aus ausgerichtet ist, möglicherweise viele Pixel innerhalb der verbundenen Komponente vorhanden sind, die ein oder mehrere der oben beschriebenen Extremitätskriterien erfüllen. Dies stellt jedoch kein Problem dar; es kann ein jedes beliebiges zufriedenstellendes Pixel ausgewählt werden. So ist beispielsweise in der in 1 dargestellten Umrandung 111 kein einzelnes am weitesten südlich gelegenes Pixel vorhanden, und dementsprechend kann ein beliebiges Pixel entlang der Unterkante ausgewählt werden. Darüber hinaus stellt es kein Problem dar, wenn ein einzelnes Pixel als mehrere Extrempunkte verwendet wird. Unter erneuter Bezugnahme auf 1 kann beispielsweise ein Pixel der unteren rechten Ecke 122 als Extrempunkt S, SE und E verwendet werden, ohne dass es dabei zu irgendwelchen Auswirkungen aus das gewünschte Verfahren kommt.

Wenn die verbundene Komponente C die Umrandung 111 ist (sprich, ein Rechteck mit einer fehlenden Ecke), dann enthalten drei der Extrempunkte rechteckige Eckpunkte (die umgeknickte Ecke ist versetzt), und die anderen fünf Extrempunkte enthalten irrelevante Information. Das hierin beschriebene Verfahren hat jedoch noch nicht festgelegt, ob die verbundene Komponente C die Umrandung 111 ist, oder, wenn dies der Fall ist, welche Extrempunkte ihre Ecken darstellen; dies wird wie im Folgenden beschrieben, festgelegt.

Anschließend werden alle acht Extrempunkte in Betracht gezogen. Wenn der Abstand zwischen zwei beliebigen einander diametrisch gegenüberliegenden Extrempunkten die diagonalen Längenkriterien erfüllt (Schritt 620), handelt es sich bei der verbundenen Komponente um einen Umrandungskandidat. Das heißt, wenn d_min ≤ ∥N – S∥ ≤ d_max ist, oder wenn d_min ≤ ∥E – W∥ ≤ d_max ist, oder wenn d_min ≤ ∥NE – SW∥ ≤ d_max ist, oder wenn d_min ≤ ∥SE – NW∥ ≤ d_max ist, dann ist ein Umrandungskandidat gefunden worden. Anderenfalls wird die verbundene Komponente C verworfen (Schritt 614).

Auf Basis der Position der Diagonalen werden anschließend die anderen zwei möglichen Ecken der verbundenen Komponente identifiziert (Schritt 622) und in Betracht gezogen. Würde die Diagonale entweder zwischen den Extrempunkten N – S oder zwischen den Extrempunkten E – W gefunden, würden die Werte von N, E, S und W für p₁, p₂, p₃ und p₄ verwendet, welche die jeweiligen vier Eckpunkte des Umrandungskandidaten darstellen. Auf ähnliche Weise würden, wenn die Diagonale entweder zwischen den Extrempunkten NE – SW oder SE – NW gefunden würde, die Werte von NE, SE, SW und NW für p₁, p₂, P₃ und p₄, die jeweiligen vier Eckpunkte des Umrandungskandidaten, verwendet.

Anschließend werden die Beziehungen zwischen den vier Punkten p₁, p₂, p₃ und p₄ analysiert, um zu bestimmen, ob eine rechteckige Form vorhanden ist (Schritt 624). Insbesondere werden alle Abstände zwischen p₁ und p₂, zwischen p₂ und p₃, zwischen p₃ und p₄ und zwischen p₄ und p₁ betrachtet. Wenigstens ein Abstand (der vier möglichen Abstände) sollte annähernd der erwarteten Breite sein, und wenigstens ein angrenzend liegender Abstand (jedoch nicht der gegenüberliegende) sollte annähernd der erwarteten Höhe sein.

Das heißt, wenn entweder ((w_min ≤ ∥p₁ – p₂∥ ≤ w_max)oder(w_min ≤ ∥p₃ – p₄∥ ≤ w_max)) und ((h_min ≤ ∥p₂ – p₃∥ ≤ h_max)oder(h_min ≤ ∥p₄ – p₁∥ ≤ h_max)) oder ((h_min ≤ ∥p₁ – p₂∥ ≤ h_max)oder(h_min ≤ ∥p₃ – p₄∥ ≤ h_max)) ((w_min ≤ ∥p₂ – p₃∥ ≤ w_max)oder(w_min ≤ ∥p₄ – p₁∥ ≤ w_max)) wahr ist, handelt es sich bei der verbundenen Komponente C möglicherweise um die Umrandung 111, und sie wird zu einer Liste von möglichen Positionen hinzugefügt (Schritt 626). Anderenfalls wird die verbundene Komponente C erneut verworfen (Schritt 614).

Wie dies voranstehend beschrieben wurde, wird anhand von allen Umrandungskandidaten, die die voranstehenden Kriterien erfüllen, eine Liste mit möglichen Positionen erstellt. Anschließend wird die gesamte Liste zu dem Dekodierungsprozess weitergeleitet (Schritt 514 in 5). Es ist anzunehmen, dass lediglich ein Umrandungskandidat Daten gültiger Glyphen (oder andere Daten) enthält. Wenn mehr als ein Umrandungskandidat gültige Daten enthält, wird der verwendet, der zuerst gefunden wird.

Hierbei sollte beachtet werden, dass das voranstehend beschriebene Verfahren des Identifizierens und des Lokalisierens der im Wesentlichen rechteckigen Umrandung 111 des Glyphen-Aufklebermusters 110 in einer beliebigen Ausrichtung und mit geringfügigen Abweichungen im Maßstab auch in einer Vielzahl von verschiedenen anderen Bildverarbeitungsanwendungen angewendet werden kann und für diese vorteilhaft wäre. Es wird festgestellt, dass das in 6 dargestellte Verfahren, das voranstehend ausführlich beschrieben worden ist, verwendet werden kann, um nahezu ein jedes beliebige im Wesentlichen rechteckige Muster innerhalb eines digitalisierten Bildes zu identifizieren und zu lokalisieren, entweder als ein Teil oder getrennt von den anderen Leistungsmerkmalen und Fähigkeiten, die hierin beschrieben sind.

Es wird darüber hinaus offensichtlich sein, dass geringfügige Abänderungen an diesem Verfahren, die den Personen mit der gewöhnlichen Erfahrung auf dem Gebiet der Technik ohne Weiteres offensichtlich sein werden, ebenfalls zum Identifizieren und Lokalisieren von Parallel-, Rhombus-, Trapez-, und unregelmäßig viereckigen Mustern zusätzlich zu den Rechteckmustern und den rechteckähnlichen Mustern verwendet werden können. In diesen alternativen Ausführungsformen können entweder eine oder beide Diagonalen überprüft werden; wobei die zwei Diagonalen unterschiedliche erwartete Längen aufweisen können. Zusätzlich dazu kann das Verfahren dahingehend erweitert werden, dass es zum Identifizieren und Lokalisieren von n-seitigen Vielecken verwendet werden kann, indem Extrempunkte auf durch 2n gleichmäßig voneinander beabstandeten Kompasspositionen identifiziert werden und anschließend ein Prüfen auf Vorhandensein von Scheitelpunkten an alternierenden Extrempunkten durchgeführt wird. In den Fällen, in denen n eine ungerade Zahl ist, sollte beachtet werden, dass eine beliebige Diagonale, die gefunden wird, nicht diametrisch sein wird; es kann jedoch ein beliebiger erwarteter Abstand (oder Gruppe von erwarteten Abständen) zwischen angrenzenden oder nicht angrenzenden Scheitelpunkten in nahezu einem jeden beliebigen n-seitigen Vieleck in einem Verfahren in Übereinstimmung mit der Erfindung verwendet werden, um das Vieleck innerhalb eines Bildes zu identifizieren.

7 illustriert die Abfolge von Schritten, die beim Erkennen eines Glyphenfeldes 112 (1) und beim Umwandeln des Glyphenfeldes in binäre Daten durchgeführt werden. Zunächst wird das Gitter von Glyphen bestimmt (Schritt 710). Im Grunde genommen müssen dabei Glyphengittervektoren (8) zusammen mit Informationen zu Schräglauf und Maßstab bestimmt werden; diese Operation ist in 9 dargestellt und wird im Folgenden ausführlicher beschrieben. Als Zweites wird ein Ausgangsglyph gesucht (Schritt 712). Der Erkennungsprozess beginnt mit dem Suchen eines einzelnen „guten" Glyphen, dem Ausgangsglyphen; siehe 11. Als Drittes werden alle der Glyphen gesucht (Schritt 714), indem rekursiv die Nachbarn des Ausgangsglyphen überprüft werden (so wie dies in den 12 bis 13 dargestellt ist). Die Gittervektoren bestimmen die Suche und helfen beim Durchführen des Abbildens von Bildraum auf eine Matrix von Glyphenwerten. Wie dies im späteren Verlauf dargelegt wird, können diese Schritte allesamt ungeachtet der Rotation des Glyphenfeldes durchgeführt werden.

Wenn alle der Glyphen lokalisiert worden sind, wird die geeignete Rotation des Glyphenfeldes 112 bestimmt (Schritt 716). Wie dies anhand von 1 ersichtlich ist, umfasst die bevorzugte Glyphenkonfiguration „Schrägstrich"-Muster in Ausrichtungen von +45° und –45°. Dementsprechend kann das Glyphenfeld 112 anscheinend in Ausrichtungen von 0°, 90°, 180° und 270° gültig sein.

Dementsprechend werden die binären Muster, die durch das Glyphenfeld 112 dargestellt werden, verarbeitet, um die korrekte Rotation zu bestimmen. In einer Ausführungsform der vorliegenden Erfindung ist ein Synchronisationsmuster in das Glyphenfeld 112 eingebettet; und dieses Muster wird nur dann korrekt rekonstruiert, wenn sich das Glyphenfeld 112 in der richtigen Ausrichtung befindet. Für ein Verfahren des Vereindeutigens der Ausrichtung des Glyphenfeldes, wird auf die Spezifikation und Zeichnungen des US-Patentes Nr. 5.449.895 von Hecht und Stearns mit dem Titel „EXPLICIT SYNCHRONIZATION FOR SELF-CLOCKING GLYPH CODES" verwiesen, das durch Verweis ein Bestandteil der vorliegenden Beschreibung bildet, als ob es hierin vollständig beschrieben ist. Siehe insbesondere die Spalten 15 bis 16 des Patentes '895 für eine ausführliche Beschreibung des abwechselnden Vereindeutigens. Hierbei sollte beachtet werden, dass die Position der Ecke 120 (1) auch in einer alternativen Ausführungsform der Erfindung verwendet werden kann, um die korrekte Ausrichtung des Glyphenfeldes 112 zu bestimmen.

Wie dies in 8 dargestellt ist, kann ein Glyphenbild 810 durch zwei Gitter-Umwandlungsvektoren 812 und 814 und zwei (oder mehr) Bitmaps 816 und 818 definiert werden, die die Information spezifizieren, die an einem jeden Gitterort dargestellt werden soll. Diese Definition entspricht dem Definieren eines Kristalls in der Physik der festen Stoffe. Dieses Verfahren des Spezifizierens des Glyphenbildes lässt eine große Bandbreite von Strukturen zu, es stellt jedoch auch ein Schema zum Bearbeiten von beliebigen Rotationen, Maßstäben, Gittern und Bitmaps zur Verfügung. So entspricht beispielsweise die Rotation des Glyphenbildes 810 einfach einer Rotation der Gitter-Umwandlungsvektoren 812 und 814. Genau wie die Umwandlungsvektoren die Verschiebung von Glyphenmitte zu Glyphenmitte während der Erzeugung des Glyphenbildes definieren würden, definieren die Umwandlungsvektoren darüber hinaus auch die Verschiebung von Glyphenmitte zu Glyphenmitte während des Erkennungsprozesses. Das Betrachten des Glyphenbildes als ein Gitter ermöglicht es dem Erkennungsschema, eine große Bandbreite von verschiedenen Glyphenformatierungsschemen zu bearbeiten, während Rotations- und Maßstabsabweichungen bearbeitet werden.

Das Verfahren zum Bestimmen des Gitters von Glyphen basiert auf dem Aufbauen eines gemittelten Bildes aus dem, was die lokale Nachbarschaft des Glyphen ausmacht und auf dem Bestimmen der Gittervektoren anhand dieser Mittelung. In einer bevorzugten Ausführungsform der Erfindung wird dies auf die folgende Weise umgesetzt (so wie dies in 9 dargestellt ist).

In dem Glyphenbild (das heißt, dem Bereich innerhalb der Umrandung 111), wird eine gewisse Anzahl von Pixeln in dem Bild als Ausgangspixel für die Verarbeitung identifiziert (Schritt 910). Diese Ausgangspixel können beispielsweise in dem gesamten Bild auf einem Gitter von N × N Pixeln voneinander beabstandet sein, wobei N in der Größenordnung von 10 bis 50 liegt (der Abstand kann so gewählt werden, dass sich ungefähr 100 Ausgangspixel in dem gesamten Glyphenbild 810 befinden).

Anschließend wird, beginnend bei einem jeden Ausgangspixel, die minimale lokale Intensität in dem Bild, das sich zu diesem Ausgangspixel am nächsten befindet, gesucht (Schritt 912). Wenn kein lokales Minimum innerhalb eines geeigneten Abstandes des Ausgangspixels (beispielsweise 10 Pixel) gefunden wird, wird mit dem nächsten Ausgangspixel fortgefahren. Die lokalen Minima, das heißt, die dunkelsten Punkte in dem Bitmap, entsprechen typischerweise den Glyphen.

Wenn ein lokales Minimum gefunden ist, wird bestimmt, ob ein ausreichender Bildkontrast zwischen dem Bereich innerhalb von 1 bis 2 Pixeln des Minimums (das heißt, der Mitte) und dem Bereich 3 bis 4 Pixel von dem Minimum entfernt (das heißt, dem umliegenden Bereich) vorhanden ist (Schritt 914). Wenn der Kontrast verglichen mit der durchschnittlichen Bildintensität um das lokale Minimum herum zu klein ist, stellt das Verfahren weitere Berechnungen mit dem vorhandenen lokalen Minimum ein und fährt mit dem nächsten Ausgangspixel in dem Glyphenbild fort (falls welche vorhanden sind). Dieser Schritt, der, wenn dies gewünscht ist, weggelassen werden kann, wird durchgeführt, um unerwünschte lokale Minima in dem Bild, die durch Rauschen und anderes Nicht-Glyphen-Material entstehen, auszusondern.

Anderenfalls wird das Graustufenbild, das das lokale Minimum umgibt, zu einem zusammengesetzten Bild hinzugefügt (Schritt 916), das anfänglich mit Pixeln des Wertes Null gefüllt wird. Dieses zusammengesetzte Bild, das während der Verarbeitung aufgebaut wird, wird demzufolge zu einer Summe der Bitmapwerte um eine Anzahl von lokalen Minima in dem Glyphenbild herum. Das zusammengesetzte Bild liegt in seinen Abmessungen typischerweise in der Größenordnung von 20 × 20 Pixeln.

Wenn irgendwelche Ausgangspixel für die Verarbeitung übrig bleiben (Schritt 918), wird der Prozess wiederholt.

Nach dem Suchen der lokalen Minima, die mit sämtlichen der Ausgangspixel assoziiert sind, wird das zusammengesetzte Bild analysiert (Schritt 920), um die gemittelten Glyphenpositionen zu bestimmen. So ist beispielsweise die Mitte des zusammengesetzten Bildes notwendigerweise ein lokales Minimum, da sie aus mehreren Bildern gebildet ist, deren Mitten Minima waren. Anschließend entspricht das der Mitte in dem zusammengesetzten Bild am nächsten liegende lokale Minimum den gemittelten, den Glyphen in dem Glyphengitter am nächsten liegenden, Nachbarpositionen. Die Bestimmung dieser Minima in dem zusammengesetzten Bild resultiert dementsprechend in der Kenntnis über die Konfiguration des Glyphengitters; und die Gittervektoren 812 und 814 können anschließend hergeleitet werden.

Das im Zusammenhang mit 9 voranstehend beschriebene Verfahren ist aufgrund der Mittelungseigenschaften des Aufbauens des zusammengesetzten Bildes sehr robust. So wie dies in einer jeden beliebigen Signalverarbeitungsvorgehensweise der Fall ist, wird davon ausgegangen, dass in dem zusammengesetzten Bild die Pixel, die den Positionen der Glyphen entsprechen, eine kohärente Summe ergeben, während das für Bildrauschen nicht zutrifft. In der Praxis hat sich herausgestellt, dass die Mittel-Glyphengitterparameter eines Bildes unter Verwendung der voranstehend beschriebenen Vorgehensweise auf robuste Weise erhalten werden können, selbst wenn eine große Anzahl (> 50%) der Glyphen durch Bildrauschen oder Überschreiben undeutlich oder gelöscht ist. Zusätzlich dazu funktioniert die voranstehend beschriebene Vorgehensweise bei einem beliebigen Maß von Schrägverlauf im Bild.

Anhand der Gittervektoren 812 und 814 der Glyphen wird eine Suchrichtungs-Liste 1010 erstellt. Siehe dazu 10. Bei der Suchrichtungs-Liste handelt es sich um eine Liste von entsprechenden relativen Verschiebungen bei Bildraum 1012 und bei Datenraum 1014 für das Suchen von benachbarten Glyphen. Anhand eines bekannten Glyphen in dem Bildraum stellt die Suchrichtungs-Liste 1010 Information darüber bereit, wo die benachbarten Glyphen lokalisiert werden sollten. Und für eine jede Umwandlung in dem Bildraum (1016, 1018, 1030 und 1022) ist eine entsprechende relative Verschiebung in dem Datenraum (1024, 1026, 1028 und 1030) vorhanden. Dementsprechend können für eine bekannte Gitterstruktur, für die Rotation und für den Maßstab die relativen Verschiebungen in dem Bildraum spezifiziert werden, ohne dass dabei die entsprechende Bewegung in dem Datenraum verändert wird. Durch dieses Verfahren des Definierens der Suche kann der Prozess eine große Bandbreite an Glyphengittern, Rotationen und Maßstäben bearbeiten. Hierbei sollte beachtet werden, dass die Suchrichtungs-Liste auch so erweiterbar ist, dass nach Glyphen, die am zweitnächsten liegen oder nach rechtlinigen Suchmustern gesucht werden kann.

Im Folgenden werden die Operationen, die beim Suchen eines Ausgangsglyphen für den Erkennungsprozess durchgeführt werden, im Zusammenhang mit 11 beschrieben. Das Suchen eines guten Ausgangsglyphen ist äußerst wichtig. Wenn es sich bei dem Ausgangsglyphen tatsächlich um eine unerwünschte Mitte handelt, wird der Prozess sehr schnell scheitern. Vorzugsweise sucht der Prozess nach einem Ausgangsglyphen, der wenigstens vier benachbarte Glyphen besitzt. Dies gewährleistet eine gewisse Sicherheit dahingehend, dass der ausgewählte Ausgangsglyph nicht unerwünscht ist.

Der Ausgangsglyph wird durch in Betracht ziehen von beliebigen Positionen in den Bildern gesucht. An einer ausgewählten beliebigen Position (Schritt 1110) wird eine Gruppe von Korrelationsfiltern über einer 3 × 3-großen Nachbarschaft von Pixeln angewendet, die eingerichtet ist, um den Bereich eines einzelnen Glyphen abzudecken (Schritt 1112). Die 3 × 3-große Nachbarschaft fängt Bildrauschen und kleine Abweichungen in dem Glyphengitter ab. Die Korrelationsfilter, die angewendet werden, hängen von dem Schrägverlauf im Bild ab, der anhand des Suchens der Gittervektoren 812 und 814 bestimmt wird. Wenn sich der Schrägverlauf zwischen –22,5° und 22,5° bewegt, werden die folgenden Korrelationsfilterkernel angewendet:

Wenn sich der Schrägverlauf zwischen –45° und –22,5° bewegt, werden die folgenden Kernel angewendet:

Wenn sich der Schrägverlauf zwischen 45° und 22,5° bewegt, werden die folgenden Kernel angewendet:

Die zwei Korrelationskernel werden einzeln über der 3 × 3-großen Nachbarschaft angewendet, in der ein Glyph erwartet wird. Da die Glyphen typischerweise in schwarz erscheinen, wird der minimale Wert der zwei Korrelationen erfasst, und es wird die Differenz zwischen den zwei Korrelationen gebildet (Schritt 1114) und mit einem Schwellenwert verglichen (Schritt 1116): v = min(K₀ * 1_3×3) – min(K₁ * 1_3×3) wobei * die Korrelation bezeichnet. Wenn der absolute Wert von v kleiner als ein vorgegebener Schwellenwert ist (Schritt 1118), enthält die Position keinen Glyphen. Wenn v einen positiven Wert hat, weist der Glyph einen Wert von 0 auf, und wenn v einen negativen Wert hat, weist der Glyph einen Wert von 1 auf.

Wenn ein Glyph gefunden ist, sucht das Verfahren nach benachbarten Glyphen (Schritt 1120) unter Verwendung der voranstehend beschriebenen Suchrichtungs-Liste. Das Verfahren hört mit der Suche nach einem Ausgangsglyphen auf, sobald es einen Glyphen mit vier benachbarten Glyphen gefunden hat (Schritt 1122).

Der abschließende Schritt in dem Erkennungsprozess besteht darin, die Werte der einzelnen Glyphen zu bestimmen und diese Werte in eine Matrix zu platzieren. Die Erfindung verwendet die Suchrichtungs-Liste (10), um neue Glyphen zu suchen und um ihre Werte auf geeignete Weise in einer Matrix abzubilden. Der Prozess, der in 13 dargestellt ist, beginnt bei dem Ausgangsglyphen. Der Ausgangsglyph wird in eine dynamische Datenmatrix platziert, und die Position des Glyphen in dem Bildraum und in dem Datenraum werden auf einer Such-FIFO-(First-in-First-out)Liste platziert (Schritt 1310.

Die Such-FIFO-Liste steuert das Clustering. Wenn neue Glyphen gefunden werden, werden sie an das Ende der Such-FIFO-Liste gesetzt. Im Wesentlichen enthält die Such-FIFO-Liste die Positionen in dem Bild, die nach benachbarten Glyphen durchsucht werden müssen. Wenn die Such-FIFO-Liste leer ist, hält der Prozess an.

Beginnend mit dem Ausgangsglyphen, zieht das Verfahren, wenn irgendwelche Glyphen in der FIFO-Liste enthalten sind (Schritt 1312), eine Glyphenposition aus der FIFO-Liste heraus (Schritt 1314). Ihr Wert wird bestimmt (Schritt 1316) und in der Datenmatrix platziert. Der Wert des Glyphen wird unter Verwendung derselben Korrelationskernel bestimmt, die zum Suchen des Ausgangsglyphen verwendet werden. Das Verfahren führt anschließend eine Suche nach außen hin durch (Schritt 1318) und sucht unter Verwendung der Suchrichtungs-Liste (siehe 12(a)) nach benachbarten Glyphen; die benachbarten Glyphen werden in die FIFO-Liste platziert (Schritt 1320). Das Verfahren erzeugt ein Cluster von bekannten Glyphen, das nach außen hin größer wird, da es nach neuen Glyphen um den Umfang des Clusters herum sucht (12(b)). Das Ergebnis der Vorgehensweise ist eine Datenmatrix, die mit Datenwerten 1210 gefüllt ist (12(c)), die das Glyphenbild 810 darstellen.

Dieses Verfahren weist mehrere wünschenswerte Leistungsmerkmale auf. Zunächst kann es Gruppen von Glyphen mit beliebigen Umrandungen bearbeiten. Der Glyphenblock muss nicht notwendigerweise rechteckig sein. Zum Zweiten, wird ein sauberes Verfahren des Bearbeitens von Maßstabs- und Rotationsabweichungen bereitgestellt. Schließlich ist es Intensitätsgradienten und oberhalb der Glyphen platzierten Markierungen gegenüber tolerant. Hierbei sollte beachtet werden, dass, obgleich in der vorliegend bevorzugten Ausführungsform der Erfindung eine FIFO-Liste verwendet wird, auch andere Sucherverfahren, einschließlich jener, die einen LIFO-(Last-in-Last-out)Stapel oder -Liste auf Basis eines anderen Ordnungsschemas, wie zum Beispiel der Position innerhalb des Bildes verwenden, ebenfalls mit dem gleichen Effekt verwendet werden können.

Schließlich wird, wie dies voranstehend diskutiert wurde, die Datenmatrix, so wie dies in 14 dargestellt ist, verwendet. Zunächst wird die Datenmatrix abwechselnd vereindeutigt, so wie dies voranstehend beschrieben wurde (Schritt 1410). Die binären Werte in der Datenmatrix werden dementsprechend erneut abgebildet (Schritt 1412), was das erneute Ordnen der Matrix und das Umkehren der Datenwerte umfassen kann, so wie dies auf Basis der Rotation notwendig sein kann. Der Dienstcode wird ebenso wie der Benutzercode (Schritt 1416) von den resultierenden Daten extrahiert (Schritt 1414), und die Erfindung führt den Dienst, wie voranstehend im Zusammenhang mit 3 beschrieben, aus.