PatentDe  


Dokumentenidentifikation DE69835739T2 23.08.2007
EP-Veröffentlichungsnummer 0000975146
Titel Bestimmung der Lage und Orientierung einer Vielzahl von Objekten mittels einer intelligenten Bildeingangsplatte
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Venable, Dennis L., Marion, New York 14505, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, 80538 München
DE-Aktenzeichen 69835739
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 24.07.1998
EP-Aktenzeichen 983059189
EP-Offenlegungsdatum 26.01.2000
EP date of grant 30.08.2006
Veröffentlichungstag im Patentblatt 23.08.2007
IPC-Hauptklasse H04N 1/387(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]

Diese Erfindung bezieht sich allgemein auf ein Bildeingabesystem und insbesondere auf die automatische Charakterisierung und Bearbeitung einer Vielzahl von Bildobjekten, die auf der Auflageplatte eines Bildeingabe-Geräts platziert sind.

Um die Effizienz von Abtastsystemen und Digitalkopierern zu verbessern, ist es wünschenswert, ein einzeln abgetastetes Bild zu erzeugen, das aus verschiedenen getrennten Objekten (z. B. Fotografien) besteht, die nebeneinander gelegt werden, aber sich auf der Auflageplatte des Eingabescanners vorzugsweise nicht berühren. Um die automatisierte Bearbeitung der Objekte zu ermöglichen, ist es erforderlich die Position, die Form und den Drehwinkel jedes Objekts zu identifizieren. Eine solche Fähigkeit kann die Produktivität fördern, indem die erforderliche Zeit für das Abtasten mehrerer Objekte abnimmt, und indem elementare Bearbeitungsabläufe automatisiert werden.

Bis jetzt hat eine Anzahl von Patenten und Veröffentlichungen hierzu eine Bildaufteilung und gegliederte Bilder offengelegt, deren maßgebliche Abschnitte kurz folgendermaßen zusammengefasst werden können:

US-A-5.485.568, erteilt an Venable und Andere legt ein Verfahren und eine Vorrichtung zur Darstellung eines komplexen Farb-Raster-Bilds als eine Ansammlung von Objekten in einem gegliederten Bildformat – in einem hierarchischen, geräteunabhängigen Format – offen. Ein gegliedertes Bilddokument, erzeugt unter Verwendung der von Venable beschriebenen Techniken, ist eine Darstellung von Daten, die berechnet und als ein Rasterbild wiedergegeben werden können. Die Daten beinhalten ebenso einfache Rasterbilder wie eine hierarchische Ansammlung von Unterobjekten und Rasterverarbeitungsabläufen. Die möglichen Datentypen für Objekte in dem gegliederten Bild beinhalten ein Rasterbild, einen Text, Grafiken, eine Bildverarbeitungsbeschreibung, und Dateien, die mehrere Bilddarstellungen enthalten. US '568 beschreibt, wie mehrere Fotos abgetastet werden können und wie gegliederte Bilder erzeugt werden, die jedes Foto definieren. Ein Drucker kann diese dann für die Platzierung auf einer Druckseite einrichten.

In „MANAGING UND REPRESENTING IMAGE WORKFLOW IN PREPRESS APPLICATIONS", Technical Association of the Graphic Arts (TAGA), Band 1, 1995, Berichte S. 373–385, lehren Venable und Andere die Nutzung von gegliederten Bildern, um den Druckvorstufen-Ablauf einzurichten. Ein Arbeitsablauf, wie z. B. ein Gruppen-Abtasten, wird beschrieben als ein Gerät für das Erfassen verschiedener Fotografien, die für das Erfassen auf einer Scanner-Auflageplatte grob ausgerichtet sind.

Nach der vorliegenden Erfindung ist hier eine Abbildungsvorrichtung bereitgestellt, die folgendes beinhaltet:

ein Bildeingabegerät, wobei das Bildeingabegerät ein digitalisiertes Bild erzeugt, das Darstellungen von jedem Objekt aus einer Vielzahl von Objekten enthält, die durch das Gerät abgebildet werden; und

einen programmierbaren Computer, der in der Lage ist, das digitalisierte Bild zu verarbeiten, wobei der Computer einen ersten Speicher zum Speichern wenigstens eines Teils des digitalisierten Bilds und einen Programmspeicher zum Speichern eines ausführbarem Codes enthält, der sich dazu eignet, den Computer zu veranlassen, Bildverarbeitungsvorgänge an

dem digitalisierten Bild auszuführen, dadurch gekennzeichnet, dass:

der Computer gemäß vorprogrammierter Befehle die Vielzahl von Objekten innerhalb des digitalisierten Eingangsbilds identifiziert, Formen moduliert, die Grenzen jedes Objektes aus der Vielzahl von Objekten darstellt, und jedes Objektes aus der Vielzahl von Objekten durch Parameter charakterisiert, die Form, Position und Ausrichtung einschließen; und

der Computer automatisch ein Ausgabedokument zusammenstellt, das eine Darstellung wenigstens eines Objektes aus der Vielzahl von Objekten enthält

Nach einem weiteren Gesichtspunkt der vorliegenden Erfindung, ist hier ein digitales Kopiergerät bereitgestellt, die Folgendes umfasst:

ein Bildeingabegerät, die eine transparente Auflageplatte aufweist, wobei das Bildeingabegerät ein digitalisieries Bild erzeugt, das Darstellungen jedes Objektes aus einer Vielzahl von Objekten enthält, die auf der Auflageplatte platziert sind;

einen programmierbaren Computer, der in der Lage ist, die Funktion der digitalen Kopiervorrichtung zu steuern und das digitalisierte Bild zu verarbeiten;

eine Benutzerschnittstelle, wobei die Benutzerschnittstelle ein Display zum Anzeigen des Ausgabedokumentes sowie einer Vielzahl durch den Benutzer auswählbarer Optionen umfasst, wobei der Computer des Weiteren vorprogrammierte Befehle zum Aktualisieren des Displays gemäß einer Auswahl der durch Benutzer auswählbaren Optionen enthält; und ein Druckgerät, um gemäß des Ausgabedokuments ein Substrat zu erzeugen, das Zeichen gemäß der in dem Ausgabedokument enthaltenen Darstellungen hervorbringt, dadurch gekennzeichnet, dass der Computer einen ersten Speicher zum Speichern wenigstens eines Teils des digitalisierten Bilds und einen Programmspeicher für die Speicherung eines ausführbares Code enthält, der sich dazu eignet, den Computer zu veranlassen, Bildverarbeitungsvorgänge an dem digitalisierten Bild auszuführen, wobei der Computer gemäß der vorprogrammierten Befehle die Vielzahl von Objekten innerhalb des digitalisierten Eingabebilds identifiziert, Formen moduliert, die Grenzen jedes Objektes aus der Vielzahl von Objekten darstellt, und jedes Objektes aus der Vielzahl von Objekten durch Parameter charakterisiert, die Form, Position und Ausrichtung einschließen, und der Computer automatisch ein Ausgabedokument zusammensetzt, das eine Darstellung wenigstens eines Objekts aus der Vielzahl von Objekten enthält.

Die vorliegende Erfindung bezieht sich auf ein System, das dafür vorgesehen ist, die automatische Bestimmung unabhängiger Bereiche oder Segmente für Objekte innerhalb eines abgetasteten Bilds durchzuführen. Die Erfindung stellt ferner eine Benutzerschnittstelle und Dokumentvorlagen bereit, um die automatische Platzierung der Vielzahl von Objekten an Positionen innerhalb eines digitalen Dokuments so zu ermöglichen, dass das Dokument berechnet und ausgegeben, gespeichert oder übertragen werden kann. Deshalb kombiniert die vorliegende Erfindung zur Produktivitätssteigerung eine Anzahl von Grafiken und Bildverarbeitungstechniken in einer automatischen benutzerfreundlichen Anwendung. Die Anwendung kann die Produktivität steigern, indem die Zeit verringert wird, die erforderlich ist, um mehrere Bilder abzutasten, indem Korrekturen für die Ausrichtung mehrere Bilder automatisiert werden und sogar automatisch mehrere Bilder in der Dokumentenvorlage platziert werden.

Die vorliegende Erfindung erreicht diese Ziele durch:

  • 1.) Lokalisieren einer Vielzahl von unabhängigen Objekten innerhalb des Bilds;
  • 2.) Modellierung der Form der identifizierten Objekte (z. B. rechtwinklig);
  • 3.) Erzeugen einer gegliederten Bildbeschreibung, die die Stehe, die Form und die Ausrichtung jedes Objekts innerhalb des Bilds identifiziert.

Ein Gesichtspunkt der Erfindung behandelt ein grundlegendes Problem bei der digitalen Bildverarbeitung, dass der Identifizierung mehrerer Objekte innerhalb eines digitalisierten Bilds. Die Lösung dieses Problems wird dann so wirksam eingesetzt, dass die automatische Erkennung und Platzierung von Objekten ermöglicht wird, um ein digitales Dokument zusammenzusetzen. Die hierin beschriebenen Techniken ermöglichen einem Benutzer, eine Vielzahl von verschiedenen Dokumenten oder Objekten zweckmäßigerweise in einem einzigen Abtastablauf abzutasten, diese Objekte automatisch zu trennen, indem sie als unabhängige Objekte innerhalb des digitalisierten Bilds erkannt werden, und indem ein digitales Dokument, unter Verwendung von einem oder mehreren erkannten Objekten, wieder zusammengesetzt wird. Ein weiterer Gesichtspunkt der vorliegenden Erfindung ermöglicht die automatische Erzeugung einer gegliederten Bilddarstellung des digitalisieren Bilds, so dass die Bildobjekte leicht extrahiert und unabhängig weiter verarbeitet werden können.

Die oben beschriebenen Techniken sind günstig, da sie die Wirksamkeit des Abtastprozesses verbessern, was das Abtasten mehrerer Originaldokumente gleichzeitig ermöglicht, ebenso wie, unter Verwendung einer vorbestimmten Vorlage, den Dokument-Zusammensetzungsprozess durch Wiederzusammensetzen der Dokumente in ein einziges Dokument. Zusätzlich ermöglichen die Techniken ohne Eingreifen des Benutzers eine automatische Charakterisierung der physischen Attribute (Z. B. Lage, Form und Ausrichtung) der Objekte.

Eine Ausführungsform der vorliegenden Erfindung wird nun mit Bezug auf die beiliegenden Zeichnungen beschrieben, in denen Folgendes gilt:

1 ist eine Darstellung der Anlage, die ein Bildverarbeitungssystem bildet, das als eine Ausführungsform für die vorliegende Erfindung dient;

2 ist ein Blockdiagramm verschiedener Komponenten, die das System van 1 umfassen;

3 ist ein Ablaufdiagramm, das die allgemeinen Verarbeitungsschritte darstellt, die in dem System von 1 und 2 nach der vorliegenden Erfindung ausgeführt werden;

47 sind ausführliche Ablaufdiagramme, die die Verarbeitungsschritte darstellen, die nach verschiedenen Ausführungsformen der vorliegenden Erfindung ausgeführt werden;

8 ist ein darstellendes Beispiel eines Teils eines digitalen Dokuments;

9 ist eine Darstellung der Ausgabe des Systems von 1, während ein Eingabebild nach der vorliegenden Erfindung verarbeitet wird;

10 ist ein beispielhafter Benutzerschnittstellen-Bildschirm, der zu einer Ausführungsform der vorliegenden Erfindung gehört;

11 ist ein Beispiel eines Bilds, das mehrere Objekte enthält, die durch einen Abtastvorgang erzielt wurden; und

12 ist eine Vergleichsdarstellung von Entzerr- und Rückdreh-Vorgängen, wie sie auf ein Bildsegment angewendet werden.

Für ein allgemeines Verständnis der vorliegenden Erfindung wird auf die Zeichnungen Bezug genommen. In den Zeichnungen wurden gleiche Bezugszeichen durchweg verwendet, um identische Elemente zu bezeichnen. Beim Erläutern der vorliegenden Erfindung wurden die folgenden Begriffe in der Beschreibung verwendet.

Der Begriff "Daten" bezieht sich hierin auf physische Signale, die Informationen anzeigen oder beinhalten. Sobald ein Datenelement eine Alternative aus einer Anzahl von möglichen Alternativen anzeigen kann, weist das Datenelement einen "Wert" aus einer Anzahl von Werten auf. Zum Beispiel weist ein binäres Datenelement, das auch als ein „Bit" bezeichnet wird, einen von zwei Werten auf, und wird abwechselnd als "1" und "0" oder „eingeschaltet" und „ausgeschaltet" oder „hoch" und „niedrig" bezeichnet. Ein Bit ist eine "Umkehrung" eines anderen Bits, wenn die zwei Bits unterschiedliche Werte aufweisen. Ein N-Bit-Datenelement weist einen von 2N-Werten auf. Ein "Multi-Bit"-Datenelement ist ein Datenelement, das mehr als ein Bit beinhaltet.

„Speicherschaltung" oder „Speicher" ist eins Schaltung, die Daten speichern kann, und die lokale oder entfernte Speicher- und Eingabe-/Ausgabe-Geräte beinhalten kann. Beispiele beinhalten Halbleiter-ROMs, -RAMs und Speichermedium-Zugangsgeräte mit Datenspeichermedien, auf die sie zugreifen können. Eine „Speicherzelle" ist eine Speicherschaltung, die eine einzelne Dateneinheit, wie z. B. ein Bit oder eine andere n-stellige Zahl oder einen analogen Wert, speichern kann.

Ein Signal „zeigt an" oder „wählt aus" eine Alternative aus einer Gruppe von Alternativen, wenn das Signal bewirkt, dass die Angezeigte aus der Gruppe der Alternativen auftritt. Zum Beispiel kann ein Signal eine Bitgruppen in einer Reihe von Bitgruppen anzeigen, die in einem Arbeitsablauf verwendet werden sollen, wobei in dem Fall das Signal bewirkt, dass die angezeigte Bitgruppe in dem Arbeitsablauf verwendet wird.

Ein „Bild" ist ein Bild aus physikalischem Licht. Ein Bild kann Buchstaben, Wörter und Text ebenso wie weitere äußere Erscheinungen, wie z. B. Grafiken, beinhalten. Ein Text kann in einer Gruppe von einer oder mehreren Bilder enthalten sein, wie z. B. in Bildern der Seiten eines Dokuments. Ein Bild kann so verarbeitet werden, dass bestimmte „Objekte" innerhalb des Bilds identifiziert werden, von denen jedes selbst ein Bild ist. Ein Objekt kann einen beliebigen Umfang und eine beliebige Form aufweisen und „physische Attribute" oder Eigenschaften, die Position, Form und Ausrichtung einschließen, aber nicht darauf beschränkt sind.

Ein Datenelement „definiert" ein Bild, wenn das Datenelement ausreichende Informationen beinhaltet, um das Bild zu erzeugen. Zum Beispiel kann eins zweidimensionale Gruppierung alle Teile oder einen beliebigen Teil eines Bilds definieren, wobei jedes Datenelement in der Gruppierung einen Wert bereitstellt, der die Farbe einer entsprechenden Stelle des Bilds anzeigt.

Ein Datenelement „definiert" eine Bildgruppe, wenn das Datenelement ausreichende Informationen beinhaltet, um alle Bilder in der Gruppe zu erzeugen.

Jede Stelle in einem Bild kann ein „Pixel" genannt werden. In einer Gruppierung, die ein Bild definiert, in der jedes Datenelement einen Wert bereitstellt, kann jeder Wert, der die Farbe einer Stelle anzeigt, ein „Pixelwert" genannt werden. Jeder Pixelwert ist ein Bit in einer „binären Form" eines Bilds, ein Graustufen-Wert in einer „Graustufen-Form" eines Bilds oder einer Gruppe von Farb-Raumkoordinaten in einer „Farb-Koordinaten-Form" eines Bilds, wobei die binäre Form, die Graustufen-Form und die Farb-Koordinaten-Form jeweils eine zweidimensionale Gruppierung sind, die ein Bild definieren.

Ein Arbeitsablauf führt die „Bildverarbeitung" durch, wenn er auf ein Datenelement einwirkt, das zu einem Teil des Bilds gehört.

Pixel sind „Nachbarn" oder „benachbart" innerhalb eines Bilds, wenn es keine anderen Pixel zwischen ihnen gibt, und sie erfüllen ein zutreffendes Nachbarschafts-Kriterium. Wenn die Pixel rechtwinklig sind und in Zeilen oder Spalten innerhalb eines zweidimensionalen Bilds auftreten, kann jedes Pixel, abhängig von dem verwendeten Kriterium, 4 oder 8 benachbarte Pixel aufweisen.

Ein „Rand" tritt in einem Bild auf, wenn zwei benachbarte Pixel ausreichende Pixelwerte aufweisen, die einem zutreffenden Kriterium für das Auftreten eines Randes zwischen ihnen entsprechen. Der Begriff „Randpixel" oder „Grenzpixel" kann auf eines oder auf beide der benachbarten Pixel angewendet werden, zwischen denen ein Rand auftritt.

Eine „Bildcharakteristik" oder „Charakteristik" ist ein messbares Attribut eines Bilds. Ein Arbeitsablauf kann eine Charakteristik „messen", indem Daten erzeugt werden, die unter Verwendung von Daten, die ein Bild definieren, die Charakterstik anzeigen. Eine Charakteristik wird „ für ein Bild" gemessen, wenn die Charakterstik in einer Art gemessen wird, die wahrscheinlich jedes Mal annähernd dasselbe Ergebnis ergibt

Ein „Version" eines ersten Bilds ist eine zweites Bild, die unter Verwendung von Datenelementen, die das erste Bild definieren, erzeugt wird. Das zweite Bild kann identisch mit dem ersten Bild sein, oder sie kann verändert sein durch Auflösungsverlust, durch Verändern der Daten, die das erste Bild definieren oder durch andere Prozesse, die Pixelwerte des ersten Bilds modifizieren.

Ein „Bildeingabe-Gerät" ist ein Gerät, die ein Bild empfangen und ein Datenelement bereitstellen kann, das eine Version des Bilds definiert. Ein „Scanner" ist ein Bildeingabe-Gerät, die ein Bild durch einen Abtastvorgang, wie z. B. abtasten eines Dokuments, empfängt. Ein Scanner kann eine transparente Fläche (Auflageplatte) oder eine gleichwertige Einrichtung aufweisen, um das Dokument während des Abtastens zu tragen. Weitere wohl bekannte Bildeingabe-Geräte beinhalten Digitalkameras, Faxgeräte und Videorekorder, die die Fähigkeit aufweisen, durch Darstellen der Intensität des Lichts, das von einer Objektfläche reflektiert wird, auf die das Gerät sich richtet, Datensignale zu speichern.

Ein „Bildausgabe-Gerät" ist ein Gerät, die ein Datenelement empfangen kann, das ein Bild definiert, und das Bild als eine Ausgabe bereitstellen oder berechnen und wiedergeben kann. Ein „Display" ist ein Bildausgabe-Gerät, die das Ausgabebild in einer für den Menschen sichtbaren Form bereitstellt, und ein „Drucker" ist ein Bildausgabe-Gerät, die das Ausgabebild in einer für den Menschen sichtbaren Papierausgabe-Form berechnet und wiedergibt.

Bezüglich 1 und 2 wird dann nun ein elegantes Auflageplatten-System 20 dargestellt, in dem die vorliegende Erfindung besondere Verwendung findet. Das System 20 beinhaltet einen Computer 22, der digitale Daten empfangen kann, die ein Bild eines Originaldokuments 24 darstellen, das auf einer Auflageplatte des Scanners 26 platziert wird. Der Computer 22 speichert anfangs die digitalen Eingabedaten von Scanner 26 in dem Speicher 52 (z. B. einem RAM- oder einem Magnetplatten-Speicher), wo auf das Bild anschließend zugegriffen werden kann. Zusätzlich zu den digitalen Daten, kann der Speicher 52 auch einen Programmspeicher für die Speicherung eines Objektcodes enthaften, der geeignet ist, den Prozessor anzuleiten, Bildverarbeitungs-Abläufe nach der hierin beschriebenen Erfindung auszuführen. Mit dem Computer 22 ist eine Benutzer-Schnittstelle (U/I) 28 verbunden, die ein oder mehrere Benutzer-Eingabegeräte 30, wie z. B. eine Tastatur, ein Tastenfeld, eine Maus, einen Trackball, einen Eingabestift oder ein gleichwertiges Zeigegerät etc. beinhaltet.

Ein Bildausgabe-Gerät, wie z. B. ein Drucker 34, der eine lasergesteurte xerografische Druckmaschine beinhalten kann, wie sie in einer Vielzahl von handelsüblichen Druckern zu finden ist, ist ebenfalls Teil des Systems 20. In einer bevorzugten Ausführungsform wird das System 20 verwendet, um die digitalen Bilddaten zu verarbeiten, die als Eingabe von einem Scanner 26 empfangen werden, wobei eine Bildverarbeitungs-Software verwendet wird, die in dem Prozessor 50 arbeitet, um so eine Ausgabedatei zu erzeugen, die durch einen Drucker 34 berechnet und wiedergegeben, in dem Speicher 50 gespeichert und/oder über ein Netzwerk 40 zu einem weiteren Gerät übertragen werden kann.

Obwohl das System 20 als eine Vielzahl von miteinander verbundenen Einheiten dargestellt ist, wird es begrüßt, dass das System auch das umfasst, was allgemein als ein „Digitalkopierer" bezeichnet wird. In einer solchen Ausführungsform sind die Komponenten des Systems 20 in ein gebräuchliches Gehäuse integriert, und die Benutzerschnittstelle (einschließlich Display und Eingabegeräte) kann sehr unterschiedliche Erscheinungsbilder aufweisen. Ein Beispiel eines solchen digitalen Farb-Kopiersystems, in dem die vorliegende Erfindung besondere Anwendung finden kann, ist der Xerox 5775 Digital-Farbkopierer, der über einen Touchscreen-Farb-Videomonitor gesteuert wird, der den Fortschritt der Arbeitsabläufe anzeigt. Es wird begrüßt, dass das Dokument, das auf der Scanner-Auflageplatte in dem System 20 platziert wird, vorzugsweise eine Vielzahl von Fotografien und anderen Objekten beinhaltet, die durch Zeichen auf einer Substratoberfläche dargestellt werden, so dass solche Objekte durch einen einzigen Abtastvorgang abgetastet werden können. Zum Beispiel ist eine besondere Ausführungsform, auf die sich die folgende Beschreibung richtet, ein einzeln abgetastetes Bild, die mehrere verschiedene Fotografien darstellt, die nebeneinander auf die Auflageplatte des Scanners 26 gelegt werden, sich aber nicht berühren oder überdecken. Nach der vorliegenden Erfindung ist es wünschenswert, dass automatisch die Lage, die Form und der Drehungswinkel jeder Originalfotografie identifiziert werden.

Angesichts eines Eingabebilds, das durch Abtasten mehrere verschiedener Fotografien erzeugt wird, die nebeneinander auf die Scanner-Auflageplatte gelegt werden, identifiziert die vorliegende Erfindung mindestens die Position, die Form und den Ausrichtungswinkel jeder Fotografie. Wie in dem Ablaufdiagramm von 3 gezeigt, beinhaltet der Prozess, der während der Verarbeitung des Eingabebilds durch den Computer 22 ausgeführt wird, drei Hauptschritte. Zuerst werden in Schritt 100 die Objekte innerhalb des Bilds lokalisiert und die Grenzen des Objektes werden im Allgemeinen identifiziert Sobald die Objekte lokalisiert sind, wird die Form der Objekte in Schritt 200 modelliert. Nachdem die Objekte lokalisiert sind und ihre Form modelliert ist, kann ein gegliedertes Bild, das das Bild und die Objekte darin darstellt, erzeugt werden, wie es durch Schritt 300 dargestellt wird. Das gegliederte Bild beinhaltet vorzugsweise Daten, die nicht nur die Bilddaten selbst darstellen, sondern die Daten stellen die Lage, Form oder Ausrichtung jedes Objekts oder einer Kombination davon dar. Alternativ kann die Ausgabe in einem Seiten-Beschreibungssprache-Format oder in gleichwertigen Formaten erfolgen, die für das Speichern der Bildinformationen in einer wiederauffindbaren Form geeignet sind.

In einer bevorzugten Ausführungsform der vorliegenden Erfindung wird das abgetastete Eingabebild (oder eine Version davon mit einer niedrigeren Auflösung) in einen Bildspeicher (RAM) geladen, wo es gemäß der zuvor beschriebenen Schritte analysiert wird. Für die Einsatzzwecke der folgenden ausführlichen Beschreibung wird angenommen, dass Objekte einander nicht überdecken, und dass der Hintergrund des Bilds angrenzend ist. Diese vereinfachenden Annahmen sind nur zum Zweck der Erläuterung und nicht als Einschränkungen der Erfindung gedacht. Ein Fachmann wird es begrüßen, dass die hierin beschriebene Erfindung so erweiterbar ist, dass kein Betrieb nur innerhalb der Grenzen dieser Annahmen vorausgesetzt wird.

Wie durch das Ablaufdiagramm von 4 dargestellt, wird der Objekt-Lokalisierungsschritt 100 durchgeführt, indem zunächst der Hintergrundbereich des Eingabebilds 102 identifiziert wird, der Hintergrundbereich 104 charakterisiert wird und dann, unter Verwendung der Charakteristik des Hintergrundbereichs als Ausgangszahlen, alle Pixel des Hintergrundbereichs identifiziert werden, die den Hintergrundbereich mit einem lernfähigen mit Ausgangszahlen gefüllten Algorithmus 106 darstellen. Hintergrundpixel sind Pixel, die nicht zu irgendwelchen Objekten gehören, oder einfacher, es sind Pixel, die diese Bereiche darstellen, die außerhalb der Objekte liegen, deren Werte durch den „Hintergrund" gesteuert werden, an dem die Objekte während des Abtastens platziert werden (z. B. die Unterseite der Auflageplatten-Klappe). Eine Ausführungsform wendet die durchschnittliche Farbsättigung eines kleinen Bereichs in der oberen linken Ecke des abgetasteten Bilds als eine Vorabschätzung der Hintergrundfarbe an. Alternativ können andere Abfrageabläufe angewendet werden, um die Hintergrundfarbe zu bestimmen, wie es zum Beispiel in US-A-5.282.091 für eine programmierbare Vorrichtung zur Bestimmung des Hintergrundpegels eines Dokuments von Farrell, beschrieben wird.

Sobald die Hintergrundfarbe in Schritt 104 gekennzeichnet ist, wird vorzugsweise ein lernfähiger Algorithmus angewendet, um die Hintergrundfarbe zu überwachen, und um die Objekte genau zu identifizieren. Ein Beispiel für einen mit Ausgangszahlen gefüllten Algorithmus, der für die Verwendung bei der vorliegenden Erfindung geeignet ist, wird in Graphics Gems I, A. Glassner Ed., Academic Press, 1990, S. 275–277 beschrieben. Ein lernfähiger Algorithmus ist erforderlich, weil die Hintergrundpixel erhebliche Farbabweichungen aufweisen können, die sich durch eine Beleuchtungsänderung über dem Auflageplattenbereich ergeben. Der lernfähige mit Ausgangszahlen gefüllte Algorithmus wird auf die abgetasteten Farbbilddaten angewendet, indem ein anfänglicher Ausgangszahlen-Punkt verwendet wird, der durch den Hintergrund charakterisiert wird, zum Beispiel die obere linke Ecke des Bilds. Im Allgemeinen füllt der lernfähige mit Ausgangszahlen gefüllte Algorithmus einen binären Bildspeicher mit einer Maske, die alle angrenzenden Pixel anzeigt, die als Hintergrundpixel identifiziert sind. In einer einfachen Ausführungsform, die durch Schritt 112 dargestellt wird, wird ein Pixel als Hintergrundpixel betrachtet, wenn seine Farbe in einen kleinen Zwischenraum &egr; des aktuellen durchschnittlichen Hintergrundpixel-Wertes fällt. Dieser Zwischenraum wird als eine euklidische Metrik in einem roten, grünen, blauen (RGB) Farbraum berechnet. d = SQRT ((Pr – AdAvgr)2 + (Pg – AdAvgg)2 + (Pb – AdAvgb)2), wobei Pk, AdAdvgk jeweils die RGB-Komponenten des Prüfpixels und der durchschnittliche Hintergrundwert sind, und d ist die Zwischenraum-Messung. Der Wert von &egr; ist festgelegt und wird empirisch in einer Ausführungsform bestimmt. Die Prüfung, die in Schritt 112 durchgeführt wird, ist Folgende:

wenn d < &egr;, dann ist das Pixel P ein Hintergrundpixel, andernfalls ist das Pixel P ein Vordergrundpixel.

Die durchschnittliche Hintergrundfarbsättigung wird in Schritt 114 anpassungsfähig modifiziert, indem der Durchschnittswert der letzten N Pixel verwendet wird, die als Hintergrundpixel eingeordnet wurden. Für die Leistungsfähigkeit berechnet das System vorzugsweise den anpassungsfähigen Durchschnitt unter Verwendung der Gleichung: AdAvg' = (N·AdAvg – AdAvg + LastVal)/N, wobei AdAvg' der modifizierte Durchschnitt ist, AdAvg der vorherige angepasste Durchschnitt ist, LastVal der Wert des letzten als Hintergrund identifizierten Pixels ist und N das Mittelungsfenster ist. Das ist eindeutig keine Rundlauf-Mittelung, aber sie verfolgt die Laut mittelung in geeigneter Weise und ist günstiger zu rechnen als eine peinlich genau funktionierende Durchschnittsberechnung. Alternativ kann der Wert von &egr; anpassend modifiziert werden. Zum Beispiel könnte &egr; auf der Standardabweichung der letzten einzelnen Pixel basieren, die als Hintergrund identifiziert wurden etc.

Es wird begrüßt, dass alternative Verfahren zur Ermittlung der Hintergrundbereiche verwendet werden können, und dass der Prozess der Erzielung einer binären Abbildung, die die Objekte von dem Hintergrund unterscheidet, unter Verwendung einer vereinfachten Schwellenwertoperation, basierend auf der Hintergrundfarbe, ausgeführt wird. In einer bevorzugten Ausführungsform kann die Hintergrundfarbe eine Funktion der Farbe der Auflageplatte, wie z. B. einer weißen Abdeckung, sein. Als ein weiteres Beispiel verwendet der digitale Farbkopierer 5775 eine spektral reflektierende Auflageplattenabdeckung, die zu einer bläulichen Hintergrundfarbe führt, die ermittelt und von den Objekten unterschieden werden kann.

Nachdem alle Hintergrundpixel identifiziert und eine binäre Maske erzeugt ist, die stellvertretend für die Hintergrundbereiche ist, wird der Prozess in Schritt 120 ausgeführt, um, unter Verwendung einer morphologischen Filterung, Rauschränder in der Hintergrundmaske zu glätten. Insbesondere wird vorzugsweise ein morphologischer Abschlussfilter auf die Hintergrundmaske angewendet, um einzelne Rauschpixel zu entfernen, und um Objektränder zu glätten. Anschließend werden in Schritt 122 angrenzende Vordergrundbereiche lokalisiert, wodurch die Objekte identifiziert werden. Die Objekte werden identifiziert, indem die Hintergrundmaske abgetastet wird, die durch den lernfähigen Ausgangszahlen-Füllablauf erzeugt wird (Schritt 106). Beginnend mit dem oberen linken Pixel wird die Maske in einer Zeilenabtast-Art nach einem Pixel abgesucht, das in der Maske nicht als ein Hintergrundpixel klassifiziert ist, wodurch die Pixel identifiziert werden, die zu einem Vordergrundobjekt gehören. Die Verwendung des Ausgangszahlen-Füllalgorithmus zur Identifizierung des Hintergrunds gewährleistet, dass Vordergrundobjekte ausgeschlossen werden, oder mit anderen Worten, die vollständige Begrenzung um die Eingrenzung des Objekts herum wird ausgebildet.

In Schritt 124 wird die Begrenzung eines Objekts identifiziert, indem sein Rand nachgezeichnet wird. Die Begrenzung des Vordergrundobjekts wird, unter Verwendung eines einfachen 8-connected-Randtraversals, nachgezeichnet, das eine geordnete Gruppe von Punkten bereitstellt, die den Rand des Objekts nachzeichnen. Ein solcher Randtraversal-Ablauf verwendet einen Umriss-Nachzeichnungs-Ablauf, um in einer Weise einen Kettencode zu erzeugen, die Word oder auf Zeichen basierenden Erkennungssystemen gleicht. Ein 8-connected-Prozess wird zum Beispiel von R. Bozinovic und Anderen in „Off-Line Cursive Script Word Recognation", IEEE Transactions on Pattern Analysis and Machine Intelligence, Band 11, Nr. 1 (Januar 1989) beschrieben. Sobald der Rand nachgezeichnet ist, werden alle Pixel, die zu dem Objekt in der Maske gehören, als Hintergrund markiert, damit sie nicht zum zweiten Mal verarbeitet werden, das Objekt wird zu der Vordergrundobjektliste hinzugefügt, und dann wird das Abtasten von Schritt 122, wie in dem Prüfschritt 126 bezeichnet, fortgeführt. Um das Vordergrund-Abtasten zur Identifizierung aller Objekte abzuschließen, kann anschließend eine Rückschau der identifizierten Objekte, wie durch Schritt 130 dargestellt, abgeschlossen werden. In vielen Fällen kann das abgetastete Bild unerwünschte Vordergrundobjekte enthalten; solche Objekte können in diesem Schritt aus der Objektliste entfernt werden. In einer Ausführungsform kann die Rückschau der Objektliste einfach kleine Objekte als unerwünschte Bilder entfernen. Zum Beispiel soll beim Abtasten einer Jahrbuchseite jedes Bild, mit dem eine Textüberschrift verbunden ist, nicht als Bilddaten klassifiziert werden. Solche Überschriften bestehen aus vielen Objekten mit kleinen Eingrenzungen, so dass es durch Messen der Eingrenzungslänge der nachgezeichneten Ränder möglich ist, Objekte zu entfernen, die eine Eingrenzung aufweisen, die kleiner als eine festgelegte Länge ist, wobei die Schwellenwertlänge empirisch bestimmt werden kann.

Sobald die Objekte lokalisiert wurden, wie es mit Bezug auf Schritt 100 beschrieben wird, ist der nächtse Hauptschritt, Schritt 200, das Modellieren der Form des Objekts. Aus Gründen der Vereinfachung behandelt die folgende Beschreibung rechtwinklige Objekte, es wird jedoch begrüßt, dass die Beschreibung auf andere Vielecke und selbst auf Formen ausgedehnt werden kann, die Abschnitte aufweisen, die durch Kurven (z. B. kreisförmige oder elliptische Objekte) dargestellt werden. Das Ergebnis oder die Ausgabe von Schritt 100 ist vorzugsweise eine Gruppe von Randspuren in der Form von verbundenen Listen, die Begrenzungspixel um jedes Objekt innerhalb des abgetasteten Bilds, identifizieren. Diese Spuren können verwendet werden, um jedes Objekt zu extrahieren, die Ausrichtung ist jedoch noch nicht bestimmt. Um die Qualität der Objektextrahierung zu verbessern, werden die Objektspuren einer Modellform angepasst Ausrichtungsinformationen etc. können dann von den angepassten Parametern extrahiert werden. In der beschriebenen Ausführungsform werden die Objektspuren an ein rechtwinkliges Modell angepasst, es sind jedoch auch andere Formen möglich.

Ein Verfahren zur Anpassung der Objektspuren an eine rechtwinklige Form ist eine Annäherung mit Hilfe der Fehlerquadratmethode für die Anpassung an einen rechten Winkel. Um die Anpassung mit Hilfe der Fehlerquadratmethode durchzuführen, wird die Randspur zunächst in vier Punktgruppen zergliedert, von denen jede einer der vier Seiten des rechtwinkligen Objekts entspricht. Die Zergliederung in vier Punktgruppen kann, wie nachfolgend beschrieben, auf verschiedene Arten durchgeführt werden.

Das erste Verfahren weist zwei Hauptabschnitte auf, (a) Kategorisieren der Randpunkte in eine Gruppe von Binärdateien, die zu einer einzelnen Linie gehören, und (b) Durchführen der Erkennung durch die Binärdateien für gedrehte Formen. Bezüglich 5, wo das erste Zergliederungsverfahren ausführlich dargestellt ist, berechnet nun Schritt 204 den Richtungskoeffizienten jedes Punkts der Randspur. Schritt 204 führt vorzugsweise die Berechnung des Richtungskoeffizientenwinkels durch, idem eine lineare Regression in einem kleinen Fenster von benachbarten Randpunkten durchgeführt wird. Zum Beispiel für 2 Punkte die auf einer der beiden Seiten des Randpunktes liegen, für den der Richtungskoeffizient bestimmt ist. Der Winkel der Linie, die durch die Mitte jedes Punkts läuft, wird, unter Verwendung einer linearen Regression in einem kleinen mittigen Fenster jedes Punkts, bestimmt. Jede Regression erfordert 4 Additionen pro Punkt in dem Fenster, plus 2 Subtraktionen, 2 Multiplikationen und eine Arcustangens-Berechnung, der Regressionsalgorithmus kann jedoch weiter optimiert werden, um die meisten Additionsoperationen zu entfernen. In einer bevorzugten Ausführungsform, die die Berechnungskomplexität reduziert, wird eine Auswahl von Randpixeln für die Berechnungen des Richtungskoeffizientenwinkels und die Einsortierung verwendet, wodurch die Anzahl der Berechnungen, die für die Kategorisierung der Randpixel erforderlich sind, reduziert wird.

Als Nächstes erstellt der Prozess in Schritt 206 eine Liste von Richtungskoeffizientenkategorien oder binären Dateien. Die Richtungskoeffizientenkategorien werden durch Berechnen der Differenzgröße in dem Richtungskoeffizientenwinkel zwischen dem aktuellen Punkt entlang des Rands (z. B. Punkt B in 8) und dem vorhergehenden Punkt (z. B. Punkt A in 8) für jeden Randpunkt erstellt. Wenn die Differenz kleiner ist als der Wert TOLERANZ (in einer Ausführungsform mit ± 5 Grad empirisch festgelegt), dann wird der Punkt derselben Richtungskoeffizientenkategorie zugewiesen wie der vorhergehende Punkt, andernfalls wird eine neue Richtungskoeffizientenkategorie erzeugt und der Punkt wird ihr zugeordnet. Bezüglich 8 würde der oben beschriebene Prozess die Punkte A, B und C einer ersten Richtungskoeffizientenkategorie zuordnen, die Punkte D, E, F, G und H einer zweiten Richtungskoeffizientenkategorie und die Punkte I, J, ... einer weiteren Richtungskoeffizientenkategorie. Wenn die Richtungskoeffizientenkategorie für den letzten Punkt ungefähr denselben Richtungskoeffizientenwinkel aufweist wie die erste Richtungskoeffizientenkategorie, dann werden zuletzt alle Punkte innerhalb der ersten Richtungskoeffizientenkategorie und der letzten Richtungskoeffizientenkategorie in einer einzigen Richtungskoeffizientenkategorie zusammengefasst.

Sobald die Richtungskoeffizientenkategorien in Schritt 206 erstellt und in einer Datenstruktur gespeichert sind, werden sie sortiert und gemäß der Anzahl der Randpunkte, die jeder Kategorie zugeordnet sind, geordnet. Für rechtwinklige Objekte sollten die besten vier Richtungskoeffizientenkategorien, welche die meisten Punkte enthalten, den Punkten entlang der vier Ränder des Rechtecks entsprechen. Die besten Richtungskoeffizientenkategorien werden dann in Schritt 210 ausgewählt. Es wird begrüßt, dass man die besten sechs Kategorien für sechseckige Objekte und in ähnlicher Weise die besten drei Kategorien für dreieckige Objekte etc. verwenden würde.

Alternativ können die Schritte 208 und 210 durch einen Schritt ersetzt werden, der den Richtungskoeffizientenwinkel oder die binären Dateien verarbeitet durch eine einfache oder sogar statistische Entfernung, in der solche Kategorien entfernt werden, die wenige Einträge aufweisen. Zum Beispiel kann ein empirisch ermittelter Schwellenwert von 5 Pixeln so angewendet werden, dass nur binäre Dateien, die mehr als 5 Pixel aufweisen mit einem gemeinsamen Winkel behalten werden. Anschließend kann ein durchschnittlicher Winkel für eine Kategorie unter Verwendung einer linearen Regression aller Punkte, die einer bestimmten Kategorie zugeordnet sind, ermittelt werden. Mit dem ermittelten Durchschnittswinkel wäre eine weitere Verfeinerung der Kategorien möglich, indem die Kategorien kombiniert werden, die im Wesentlichen gemeinsame Winkel aufweisen. Insbesondere wird jede Kategorie überprüft, und wenn angrenzende Kategorien im Wesentlichen kollinear sind, werden die Kategorien zusammengefügt. Deshalb stellt jede der verbleibenden binären Dateien oder Kategorien eine Gruppe von kollinearen Punkten dar, die entlang eines Rands liegen. Die Randpunkte, die jeder verbleibenden Richtungskoeffizienten-Winkelkategorie zugeordnet werden, stellen die Randspur dar, die in die vier Seiten des Rechtecks zergliedert ist. Es wird begrüßt, dass diese Alternative allgemein auf den Prozess des „Filterns" oder Verfeinerns der Kategorien gerichtet ist, um die tatsächlichen Ränder des Objekts darzustellen. Dementsprechend werden äquivalente Verfahren zur Durchführung der Verfeinerung erwogen.

Das erste Verfahren zur Charakterisierung der Objektgrenzen ist infolge der Messung des Durchschnitts-Richtungskoeffizienten bei jedem Punkt rechenintensiv. Für eine erhöhte Geschwindigkeit können in der zuvor erwähnten alternativen Ausführungsform die Randspuren abgetastet werden, um die Gesamtzahl der Punkte zu reduzieren, die verarbeitet und kategorisiert werden müssen.

Es wird ferner begrüßt, dass es möglich ist, durch die Analyse der geordneten Kategorien die Form zu identifizieren. Zum Beispiel zeigt eine statistisch bedeutende Differenz in der Anzahl der Punkte zwischen der dritten und der vierten Kategorie oder das vollständige Fehlen einer vierten Kategorie ein dreieckiges Objekt an.

Bezüglich 6 ist darin das zweite Verfahren beschrieben, durch das die Objektformen modelliert werden können. Nach dem Abrufen der Randspur-Listendaten in Schritt 202, berechnet Schritt 252 den Massenmittelpunkt des Objekts. Obwohl es eine Anzahl bekannter Verfahren zur Berechnung des Massenmittelpunkts des Objekts gibt, würde in dem Fall eines rechteckigen Objekts eine geradlinige Näherung die (x, y) Koordinaten der Randpunkte mitteln. Als Nächstes würde in Schritt 254 der Randpunkt lokalisiert, der dem Massenmittelpunkt am nächsten ist. Der nächste Punkt wird der annähernde Mittelpunkt der langen Seite des Rechtecks sein. Wieder auf 8 bezogen, ist der Winkel &thgr; von dem Massenmittelpunkt (CofM) zu dem Mittelpunkt (La/2) der annähernde Drehwinkel (&thgr;) des Rechtecks.

Sobald der Drehwinkel ermittelt ist, wird er in Schritt 256 verwendet, um die annähernde Länge der kleinen Achse des Rechtecks in Schritt 258 zu ermitteln. Insbesondere wird der Abstand von dem Massenmittelpunkt bis zu der durchschnittlichen Position aller Randpunkte ermittelt, die in einem Winkelbereich von &thgr; – &Dgr;A bis &thgr; + &Dgr;A liegen. Dieser Abstand ist ein annäherndes Maß einer Hälfte der kleinen Achsenlänge Lp des Rechtecks. &Dgr;A ist ein empirisch ermittelter Wert in der Größenordnung von ca. 5 Grad. Schritt 260 nähert sich der Länge der großen Achse La auf ziemlich die gleiche Weise. Der Abstand von dem Massenmittelpunkt bis zu der durchschnittlichen Position (&thgr; + 90) + &Dgr;A ist ein annäherndes Maß einer Hälfte der großen Achsenlänge La des Rechtecks. Nachdem der annähernde Ausrichtungswinkel und die Längen der großen und der kleinen Achse angeglichen wurden, berechnet Schritt 264 einen Winkelbereich (der mit Bezug auf den Massenmittelpunkt gemessen wird) für jede Seite des Rechtecks, der nur die Randpunkte umfasst, die zu dieser Seite gehören:

  • a) &thgr;'b = atan2 (La, Lb) halbe Winkelbreite der großen Achse;

    &thgr;'a = 90 – &thgr;b halbe Winkelbreite der kleinen Achse;

    &thgr;b = &thgr;'b·TOL wobei TOL = 0,95, um Ecken zu vermeiden;

    &thgr;a = &thgr;'a·TOL wobei TOL = 0,95, um Ecken zu vermeiden;

    und
  • b) Bereich1: (&thgr; + &thgr;b) bis (&thgr; – &thgr;b)

    Bereich2: ((&thgr; + 90) + &thgr;a) bis ((&thgr; + 90) – &thgr;a)

    Bereich3: ((&thgr; + 180) + &thgr;b) bis ((&thgr; + 180) – &thgr;b)

    Bereich4: ((&thgr; + 270) + &thgr;a) bis ((&thgr; + 270) – &thgr;a)

Sobald der Winkelbereich ermittelt ist, findet Schritt 266 alle die Randpunkte, die innerhalb jedes der vier oben ermittelten Winkelbereiche liegen (relativ zu dem Massenmittelpunkt), wodurch die Randpunkte identifiziert werden, die jeder Seite des Rechtecks entsprechen.

Es wird begrüßt, dass diese Technik in Bezug auf Randrauschen nicht so empfindlich ist wie das erste Verfahren, das oben beschrieben ist.

Sobald die Randspur in vier Punktgruppen zergliedert ist, wobei jede Gruppe einer der vier Seiten des Rechtecks entspricht, wird in Schritt 280 eine Berechnung mit Hilfe der Fehlerquadratmethode zur Anpassung der Punkte an das Rechteck durchgeführt. Ein Rechteck kann als vier gegenseitige rechtwinklige Linien beschrieben werden, die durch folgende Gleichungen definiert sind: y = &agr;0 + &bgr;x,y = &agr;1 + Yx,y = &agr;2 + &bgr;x,y = &agr;3 + Yx, wobei &bgr;y = –1. Eine Anpassung mit Hilfe der Fehlerquadratmethode ergibt die angepassten Parameter:

wobei (xki, yki) der ite Randpunkt der kten Seite ist, und nk die Anzahl der Randpunkte ist, die der kten Seite zugeordnet ist. Sobald die Anpassung mit Hilfe der Fehlerquadratmethode die angepassten Parameter (&bgr;, &agr;0, &agr;1, &agr;2, &agr;3) ergeben hat, werden sie in Schritt 282 in vier Koordinatenpaare umgewandelt, die die Ecken des Rechtecks markieren. Darüber hinaus wird der Drehwinkel des rechtwinkligen Objekts durch den Richtungskoeffizienten-Parameter &bgr; exakt dargestellt.

Ein weiteres Verfahren zur Anpassung der Randspuren an eine Form ist ein Verfahren, das Binärmomente für die schnelle Bildeingrenzung verwendet. Unter Verwendung der binären Maske, die, wie unter Bezug auf Schritt 106 beschrieben, erzeugt wird (z. B. durch den lernfähigen Ausgangszahlen-Algorithmus) oder alternativ mit einer einfachen Schwellenwertoperation, wird das Bild in einer binären Bitmap-Form wiedergegeben, wo jeder Pixelwert eine 1 oder eine 0 ist und die Hintergrund- oder die Nicht-Hintergrund-Bereiche bezeichnet. Sobald unter Verwendung der binären Maske die Grenzen für ein Objekt ermittelt sind, verwendet die in 7 beschriebene alternative Ausführungsform Binärmomente zweiter Ordnung, um eine Form (z. B. ein Rechteck) dem Objekt anzupassen.

Bezüglich 7, ist darin ein verallgemeinertes Ablaufdiagramm beschrieben, das die Schritte der Binärmomentgrenzen-Findungstechnik darstellt. In Schritt 100 werden die Objektränder lokalisiert und, wie zuvor beschrieben, aufgezeichnet, wobei sie in Schritt 290 als eine Eingabe eine verbundene Liste der Grenz- oder Randpixel bereitstellen, die als eine Randspur bezeichnet werden. Unter Verwendung der Grenzliste werden die Momente zweiter Ordnung in einer wirkungsvollen Weise berechnet (Schritt 292) mit der Gleichung:

wobei p(i, j) der Bildpixelwert bei den Bildkoordinaten (i, j) ist und p1(i) das Moment 1ter Ordnung der iten Abtastlinie ist Weil die Objektgrenzpixel im Voraus ermittelt werden, kann der Prozess vereinfacht werden, und die am weitesten rechts und am weitesten links liegenden Grenzpixel für eine bestimmte Abtastlinie werden für die Berechnungen des (absoluten) Moments 1ter Ordnung verwendet.

Anschließend werden die (mittigen) Momente 2ter Ordnung (m00, m01, m10, m11, m20, und m02) unter der Verwendung der Momente 1ter Ordnung und der folgenden Gleichungen berechnet:

Nachdem die Momente 2ter Ordnung ermittelt sind, werden sie verwendet, um in Schritt 294 eine Ellipse zu charakterisieren, und durch die Ellipse den Rahmen um das Objekt herum zu charakterisieren. Insbesondere werden der Mittelpunkt der Ellipse (x, y), die Längen jeder Achse (a und b) und der Drehwinkel (&thgr;) ermittelt. Der Rahmen für das rechtwinklige Objekt wird als ein rechtwinklig zentriertes Objekt bei (x, y) mit Längenseiten 2a und 2b, gedreht um einen Winkel &thgr;, ermittelt. Während das einen Rahmen wiedergibt, der etwas größer ist als das Objekt, wird es so erledigt, dass ein Sicherheitsspielraum für die Berechnung bereitgestellt wird, und dass ein Abschneiden eines Teils des Objekts vermieden wird. Wenn ein engerer Rahmen gewünscht wird, würde das Rechteck mit Längenseiten 2&agr;a und 2&agr;b charakterisiert, wobei &agr; mit 3/2 oder einem etwas kleineren Wert gleichgesetzt wird, um das Randbeschneiden oder -abschneiden zu bewerkstelligen (z. B. in der Größenordnung von einem oder mehreren Pixeln).

Nachdem jedes Objekt als eine Form modelliert wurde (z. B. als ein Rechteck), wird ein gegliedertes Bild erzeugt, wie es zum Beispiel in US-A-5.485.568, erteilt an Venable und Andere beschrieben wird. Das gegliederte Bild besteht aus einem „teilgegliederten" Bild für jedes Objekt, das unter Verwendung eines der oben beschriebenen Verfahren ermittelt wird. Die Auflösung des gegliederten Bilds enthält Attribute, die festlegen, welches Rechteck des abgetasteten Bilds die Objektdaten enthält, und auch den Drehwinkel, der erforderlich ist, um einen Ausrichtungsversatz zu korrigieren. 9 ist ein Beispiel eines gegliederten Bilds, das gemäß der zuvor beschriebenen Prozesse erzeugt wurde, wobei das gegliederte Bild ein Paar rechtwinkliger Bildobjekte enthält.

In einer Ausführungsform der vorliegenden Erfindung, die in 10 beschrieben wird, ist das gegliederte Bild so aufgebaut, dass während des Wiedergebens alle Objekte zurückgedreht und in einem Gittermodus angeordnet werden. Insbesondere stellt 10 eine Benutzerschnittstelle 400 dar, die unter verschiedenen Gesichtspunkten des zuvor beschriebenen Objektform-Erkennungsverfahrens verwendet werden kann, um ein intelligentes oder „smartes" Auflageplatte-Abtastsystem bereitzustellen. Das Smart-Scan-System, das durch 10 dargestellt wird, stellt vorzugsweise ein Gerät bereit, durch die ein Benutzer mit einem Digitalisier-Scanner verbunden werden kann, um wirkungsvoll digitalisierte Darstellungen von Objekten zu erzielen, die auf der Auflageplatte 24 eines Scanners platziert sind.

Bezüglich 10 gemeinsam mit 1 kann zum Beispiel ein Benutzer eine Anzahl von Fotografien auf der Scanner-Auflageplatte platzieren. Sobald sie darauf platziert sind, kann der Benutzer dann einen Arbeitsablauf aus dem Bereich 410 von 10 auswählen, um zu bewirken, dass das Computersystem 22 das Abtasten durch den Scanner 26 initialisiert.

Obwohl nicht speziell gezeigt, wird es begrüßt, dass verschiedene Verfahren zur Initialisierung der Digitalisierung der Objekte verwendet werden können, einschließlich, aber nicht darauf beschränkt, Tastatureingabe, Touchscreen-Auswahl, Drücken eines Fernbedienungsschalters oder sogar Auslösen eines Auflageplatte-Sensors, indem ein Benutzer die Auflageplatte-Abdeckung schließt. Nachdem „Gruppieren & Bearbeiten" (412) oder eine gleichwertige Abtastauswahl getroffen wurde, tastet das System 20, wie in 10 beschrieben, die auf der Auflageplatte 24 platzierten Objekte ab, und speichert die Daten zeitweise in der Datei, die die Informationen verwendet, die in dem Bereich 420 des Benutzer-Schnittstellen-Bildschirms widergespiegelt werden. Zum Beispiel können die verschiedenen Bildobjekte (A, B, C und D) innerhalb eines Bilds gefunden werden, wie es in 11 dargestellt wird. Sobald das Bild abgetastet ist, wird es, wie oben beschrieben, analysiert, um die Bildobjekte zu identifizieren. Die Bildobjekte können dann durch das Smart-Scan-System verarbeitet werden, um die Bilder automatisch auszurichten und zu positionieren, zum Beispiel können sie automatisch in einer festgelegten Dokumentvorlage, wie der in Bereich 430 der Benutzerschnittstelle beschriebenen Darstellung, platziert und wiedergegeben werden. Es wird begrüßt, dass einem Benutzer bezüglich der Dokumentvorlage auch eine zusätzliche Verarbeitungsfähigkeit gegeben werden kann, um zum Beispiel Bildunterschriften den Objekten hinzuzufügen, oder um, wie dargestellt, Titel 432 oder Untertitel 434 einzufügen. Die Eingabe einer solchen auf Text basierenden Verarbeitung würde durch die Benutzerschnittstellen-Optionen bewerkstelligt, die in Bereich 440 beschrieben werden.

Es wird von Fachleuten begrüßt, dass durch das Festlegen der Begrenzungen der Objekte in einem Bild ein Rückdreh-Ablauf exakt verwendet werden kann, um das Objekt exakter zu entzerren. Zur weiteren Darstellung dieses Vorteils, kann Bezug genommen werden auf 12. Darin wird ein Objekt O innerhalb eines Bildsegments I beschrieben. In einem typischen Entzerr Arbeitsgang werden die orthogonalen Begrenzungen des Bilds bestimmt, wie es durch den Rahmen 500 dargestellt wird, und das Bild wird entzerrt, um das Bild zu erzeugen, das als 504 bezeichnet wird und das Objekt O' enthält. Es wird begrüßt, dass um das Bild zu entzerren, das nicht klar durch Begrenzungen definiert ist, der gesamte Bildbereich gedreht werden muss, was sowohl zu einem größeren entzerrten Bildbereich als auch zu der Notwendigkeit führt, Pixel zu erzeugen, die den Bereich 508 füllen. Durch exaktes Definieren der Begrenzungen und der Ausrichtung des Objekts, vermeidet die vorliegende Erfindung die Notwendigkeit, Bereiche einzubeziehen, die größer sind als das Objekt in dem Rückdreh-Ablauf. Deshalb sind die Pixel, die das Objekt selbst darstellen, die einzigen Pixel, die zurückgedreht werden, um das Ausgabebild O' herzustellen.

Außerdem würden durch das Smart-Scan-System Bildverarbeitungsfähigkeiten ermöglicht, wie sie in Bereich 450 der Benutzerschnittstelle dargestellt werden. Nachdem jedes Objekt innerhalb des Bilds identifiziert ist, ist es möglich, die Objekte zu isolieren, verschiedene Bilder davon zu erzeugen und dann die Bilder einzeln zu verarbeiten. Deshalb können die einzelnen Bildobjekte, die automatisch innerhalb der Dokumentvorlage des Bereichs 430 platziert werden, einzeln ausgewählt, verarbeitet, skaliert (Taste 452), gedreht (Taste 454) oder abgeschnitten (Taste 456) werden. Es wird begrüßt, dass die Skalier-, Dreh- und Abschneidearbeitsgänge zusätzlich zu denjenigen vorhanden sind, die vorzugsweise automatisch als das Ergebnis der zuvor beschriebenen Objekt-Erkennungsverfahren durch das System angewendet werden.

Zum Beispiel ermöglicht die Bild-Skaliertaste, die zur Beschreibung der Auswahl quer schraffiert dargestellt ist, dem Benutzer einen (nicht gezeigten) Cursor zu bewegen, um ein Objekt (z. B. Bildobjekt D) auszuwählen, und dann eine Seite oder Ecke des Objekts zu ziehen, um so das Bildobjekt zu skalieren. Um das Verarbeiten der Objekte zu erleichtern, können Steuerungspunkte, wie diejenigen, die um die Begrenzungen des Bildobjekts D (436) dargestellt sind, in einer Weise verwendet werden, die denjenigen, die Benutzerschnittstellen entwerten, gut bekannt ist.

Wie erwähnt, kann eine vorbestimmte Dokumentvorlage verwendet werden, um automatisch Bildobjekte an den jeweiligen Positionen in einem Dokument oder in einer Seite davon zu "platzieren". Es wird begrüßt, dass solche Dokumentvorlagen in der Form einer Auflösung eines gegliederten Bilds vorliegen können, so dass die Dokumentvorlage verwendet werden kann, um eine andere Anordnung für das gegliederte Bild, das erzeugt werden soll, zu spezifizieren. Deshalb kann eine Familie, die versucht ihre Fotografien in ein "digitales Fotoalbum" zu bringen, in der Lage sein eine Dokumentvorlage zu erzeugen, die eine Seite beschreibt, die der gleicht, die in Bereich 430 der Benutzerschnittstelle gezeigt wird. Die Dokumentvorlage würde dann verwendet, um automatisch einzelne Bilder oder mehrere Objekte innerhalb eines größeren Bilddokuments zu ordnen.

In einer bevorzugten Ausführungsform würde die Ausgabe des Smart-Scan-Systems ein gegliedertes Bilddokument-Format sein, wie es von Venable und Anderen in US-A-5.485.568 beschrieben wird. Ein wichtiges Merkmal gegliederter Bilder ist die Fähigkeit, Bildverarbeitungsabläufe bei ihrer Darstellung zu speichern. Das bedeutet, dass das gegliederte Bild andere Bildverarbeitungsabläufe als einfache Objekt-Entzerr-Attribute enthalten kann. Zum Beispiel können automatische Bildverbesserungsabläufe innerhalb des gegliederten Bilds so enthalten sein, dass die identifizierten Objekte einzeln verbessert werden können. Alternativ kann die Smart-Scan-System-Ausgabe die Form eines digitalen Dokuments in einer oder mehreren gut bekannten Seiten-Beschreibungssprachen annehmen.

Sobald die „Seite" in Fenster 430 in dem von dem Benutzer gewünschten Zustand aufgebaut ist, muss der Benutzer das Bild abspeichern, indem er die Taste „verarbeitetes Bild abspeichern" 460 wählt. Ein Benutzer kann dann die aufgebaute(n) Seite(n) ausdrucken oder anderweitig verteilen, was noch wichtiger ist.

Obwohl die verschiedenen Ausführungsformen der vorliegenden Erfindung unter Bezug auf das Smart-Scan-System beschrieben wurden, wird es begrüßt, dass die Erfassung von Bildern und das Drucken und Verteilen der aufgebauten Seiten über Netzwerke oder auf einem Walk-Up-Digitalkopierer bewerkstelligt werden können. Zum Beispiel kann ein Benutzer Fotografien haben, die automatisch durch einen Filmprozessor abgetastet werden, und ein digitalisiertes Kennzeichnungsblatt wird über ein Netzwerk zu dem Benutzer gesendet. Das Kennzeichnungsblatt, das im Format eines gegliederten Bilds vorliegt, könnte dann, unter Verwendung des Smart-Scan-Systems, verarbeitet werden, um Seiten eines digitalen Fotoalbums mit einem oder mehreren Objekten auf jeder Seite zu erzeugen.

In Rekapitulation ist die vorliegende Erfindung eine intelligente Abtastvorrichtung zur Verarbeitung eines digitalen Eingabebilds, um automatisch eine Vielzahl von darin enthaltenen Objekten zu charakterisieren, und um dann die Charakterisierung als die Grundlage für bruchstückhafte Bildverarbeitungsabläufe zu verwenden, um so ein digitales Dokument zu erzeugen. In dem digitalen Dokument werden die Objekte zurückgedreht, verschoben, abgeschnitten oder anderweitig in einer vorbestimmten Weise gemäß einer Dokumentvorlage ausgerichtet. Die Abtastvorrichtung der vorliegenden Erfindung ermöglicht nicht nur das Abtasten einer Vielzahl von Objekten sondern tut das auch in einer intelligenten Art und Weise, um so eine weitere Verarbeitung und Bearbeitung der Bilder, die zu den Objekten gehören, zu ermöglichen.


Anspruch[de]
Bilderzeugungsvorrichtung, die enthält:

eine Bildeingabeeinrichtung (26), wobei die Bildeingabeeinrichtung ein digitalisiertes Bild erzeugt, das Darstellungen jeder einer Vielzahl von Objekten enthält, die durch die Einrichtung abgebildet werden; und

einen programmierbaren Computer (20), der in der Lage ist, das digitalisierte Bild zu verarbeiten, wobei der Computer einen ersten Speicher (52) zum Speichern wenigstens eines Teils des digitalisierten Bildes und einen Programmspeicher (52) zum Speichern von ausführbarem Code enthält, der sich dazu eignet, den Computer zu veranlassen, Bildverarbeitungsvorgänge an dem digitalisierten Bild auszuführen, dadurch gekennzeichnet, dass:

der Computer entsprechend vorprogrammierten Befehlen die Vielzahl von Objekten innerhalb des digitalisierten Eingangsbildes identifiziert, Formen moduliert, die Grenzen jedes der Vielzahl von Objekten darstellen, und jedes der Vielzahl von Objekten durch Parameter charakterisiert, die Form, Position und Ausrichtung einschließen; und

der Computer automatisch ein Ausgabedokument zusammenstellt, das eine Darstellung wenigstens eines der Vielzahl von Objekten enthält.
Vorrichtung nach Anspruch 1, die des Weiteren eine Benutzerschnittstelle (34) zum Anzeigen einer Darstellung des Ausgabedokumentes enthält, das die Darstellung wenigstens eines der Vielzahl von Objekten einschließt, wobei einer der Parameter des wenigstens einen Objektes geändert worden ist. Vorrichtung nach Anspruch 1 oder Anspruch 2, wobei die Position der Darstellung des Objektes an eine vordefinierte Position in dem Ausgabedokument verschoben ist. Vorrichtung nach Anspruch 2, wobei nur die Darstellung des Objektes gedreht wird, um eine gedrehte Darstellung des Objektes in dem Ausgabedokument anzuordnen. Vorrichtung nach einem der vorangehenden Ansprüche, wobei die Bildeingabeeinrichtung eine Fläche (24) enthält, auf der die Vielzahl von Objekten zur Digitalisierung angeordnet werden. Vorrichtung nach einem der vorangehenden Ansprüche, wobei der erste Speicher ein Grafikspeicher (frame buffer) ist. Vorrichtung nach einem der vorangehenden Ansprüche, wobei der erste Speicher ein Datenspeichermedium ist, auf das der programmierbare Computer zugreifen kann. Vorrichtung nach einem der vorangehenden Ansprüche, die des weiteren einen Schablonenspeicher zum Speichern wenigstens einer Schablone zum Steuern der Position und der Ausrichtung der Darstellung des wenigstens einen Objektes während der Zusammenstellung des Ausgabedokumentes enthält. Vorrichtung nach Anspruch 8, wobei die wenigstens eine Schablone in Form eines strukturierten Bildes gespeichert ist. Vorrichtung nach einem der vorangehenden Ansprüche, die des Weiteren enthält:

eine Benutzerschnittstelle, wobei die Benutzerschnittstelle eine Benutzereingabeeinrichtung (30), die auf eine Benutzerauswahl anspricht, und eine Anzeigeeinrichtung (34) zum Darstellen des Ausgabedokumentes im Zusammenhang mit durch Benutzer auswählbaren Optionen umfasst;

wobei der Computer des Weiteren vorprogrammierte Befehle zum Aktualisieren der Anzeigeeinrichtung entsprechend einer Auswahl der durch Benutzer auswählbaren Optionen enthält.
Vorrichtung nach Anspruch 10, wobei der programmierbare Computer im Zusammenhang mit der Anzeigeeinrichtung durch Benutzer auswählbare Optionen bereitstellt, um:

wenigstens ein Objekt in dem Ausgabedokument auszuwählen;

wenigstens einen Parameter des ausgewählten Objektes zu ändern; und

in einem Speicher eine Version des Ausgabedokumentes zu speichern, nachdem ein Benutzer einen Parameter wenigstens eines Objektes geändert hat.
Vorrichtung nach Anspruch 10 oder 11, wobei die durch Benutzer auswählbaren Optionen aus der Gruppe ausgewählt werden, die besteht aus:

Einfügen von Textinhalt in das Ausgabedokument;

Definieren eines Speicherortes für das Ausgabedokument;

Speichern des Ausgabedokumentes;

Skalieren der Darstellung des wenigstens einen Objektes;

Drehen der Darstellung des wenigstens einen Objektes;

Beschneiden der Darstellung des wenigstens einen Objektes;

Ändern der Färbung der Darstellung des wenigstens einen Objektes; und

Verbessern der Darstellung des wenigstens einen Objektes.
Vorrichtung nach einem der vorangehenden Ansprüche, wobei die Bildeingabeeinrichtung eine Auflageplatte enthält und die Bildeingabeeinrichtung so eingerichtet ist, dass sie eine Vielzahl von Originalen auf der Auflageplatte abtastet und ein einzelnes digitalisiertes Bild erzeugt, das die Darstellungen jedes der Vielzahl von Originalen einschließt, die durch die Einrichtung abgebildet werden. Vorrichtung nach Anspruch 13, wobei der Computer so eingerichtet ist, dass er den Hintergrund des digitalisierten Bildes bestimmt und die Vielzahl der digitalisierten Originale auf Basis des bestimmten Hintergrundes als Objekte innerhalb des digitalisierten Eingabebildes identifiziert. Digitale Kopiervorrichtung, die enthält:

eine Bildeingabeeinrichtung (26), die eine transparente Auflageplatte (24) hat, wobei die Bildeingabeeinrichtung ein digitalisiertes Bild erzeugt, das Darstellungen jedes einer Vielzahl von auf der Auflageplatte angeordneten Objekten enthält;

einen programmierbaren Computer (20), der in der Lage ist, die Funktion der digitalen Kopiervorrichtung zu steuern und das digitalisierte Bild zu verarbeiten;

eine Benutzerschnittstelle, wobei die Benutzerschnittstelle eine Anzeigeeinrichtung (34) zum Anzeigen des Ausgabedokumentes sowie einer Vielzahl durch den Benutzer auswählbarer Optionen umfasst, und der Computer des Weiteren vorprogrammierte Befehle zum Aktualisieren der Anzeigeeinrichtung entsprechend einer Auswahl der durch Benutzer auswählbaren Optionen enthält; und

ein Druckgerät, das entsprechend dem Ausgabedokument einen Träger erzeugt, der Zeichen entsprechend in dem Ausgabedokument enthaltener Darstellungen trägt, dadurch gekennzeichnet, dass der Computer einen ersten Speicher (52) zum Speichern wenigstens eines Teils des digitalisierten Bildes und einen Programmspeicher (52) für die Speicherung von ausführbarem Code enthält, der sich dazu eignet, den Computer zu veranlassen, Bildverarbeitungsvorgänge an dem digitalisierten Bild auszuführen, wobei der Computer entsprechend vorprogrammierten Befehlen die Vielzahl von Objekten innerhalb des digitalisierten Eingabebildes identifiziert, Formen moduliert, die Grenzen jedes der Vielzahl von Objekten darstellen, und jedes der Vielzahl von Objekten durch Parameter charakterisiert, die Form, Position und Ausrichtung einschließen, und der Computer automatisch ein Ausgabedokument zusammensetzt, das eine Darstellung wenigstens eines der Vielzahl von Objekten enthält.
Digitale Kopiervorrichtung nach Anspruch 15, wobei das digitalisierte Bild ein Farbbild ist und die auf dem Substrat angeordneten Zeichen von wenigstens zwei unterschiedlichen Farben sind. Vorrichtung nach Anspruch 15 oder Anspruch 16, wobei die Benutzerschnittstelle eine Benutzereingabeeinrichtung (30), die auf eine Benutzerauswahl anspricht, und eine Anzeigeeinrichtung umfasst, die das Ausgabedokument im Zusammenhang mit durch Benutzer auswählbaren Optionen anzeigt; und wobei der programmierbare Computer des Weiteren vorprogrammierte Befehle zum Aktualisieren der Anzeigeeinrichtung entsprechend einer Auswahl der durch Benutzer auswählbaren Optionen enthält. Vorrichtung nach Anspruch 17, wobei der programmierbare Computer im Zusammenhang mit der Anzeigeeinrichtung durch Benutzer auswählbare Optionen bereitstellt, um:

wenigstens ein Objekt in dem Ausgabedokument auszuwählen;

wenigstens einen Parameter des ausgewählten Objektes zu ändern; und

in einem Speicher eine Version des Ausgabedokumentes zu speichern, nachdem ein Benutzer einen Parameter wenigstens eines Objektes geändert hat.
Vorrichtung nach Anspruch 17 oder 18, wobei die durch Benutzer auswählbaren Optionen aus der Gruppe ausgewählt werden, die besteht aus:

Einfügen von Textinhalt in das Ausgabedokument;

Definieren eines Speicherortes für das Ausgabedokument;

Speichern des Ausgabedokumentes;

Skalieren der Darstellung des wenigstens einen Objektes;

Drehen der Darstellung des wenigstens einen Objektes;

Beschneiden der Darstellung des wenigstens einen Objektes;

Ändern der Färbung der Darstellung des wenigstens einen Objektes; und

Verbessern der Darstellung des wenigstens einen Objektes.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com