PatentDe  


Dokumentenidentifikation DE69737495T2 10.01.2008
EP-Veröffentlichungsnummer 0000873003
Titel Verfahren und Vorrichtung zur Bildabtastung
Anmelder Hewlett-Packard Development Company, L.P., Houston, Tex., US
Erfinder Kahn, Richard Oliver, Bradley Stoke, Bristol BS12 6AY, GB;
Pollard, Stephen Bernard, Nr. Dursley, Gloucestershire GL11 5SL, GB
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Aktenzeichen 69737495
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 14.04.1997
EP-Aktenzeichen 973025190
EP-Offenlegungsdatum 21.10.1998
EP date of grant 21.03.2007
Veröffentlichungstag im Patentblatt 10.01.2008
IPC-Hauptklasse H04N 1/047(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
TECHNISCHES GEBIET

Die vorliegende Erfindung bezieht sich allgemein auf Vorrichtungen und Verfahren zum Erzeugen gescannter bzw. abgetasteter oder anderweitig erfasster elektronischer Bilder von Originalen. Sie ist besonders relevant für Vorrichtungen oder Verfahren, in denen das Bild in einer willkürlichen Sequenz erfasst wird, insbesondere beim uneingeschränkten Hand-Scannen.

HINTERGRUNDTECHNIK

Scanner zum elektronischen Erzeugen eines Bilds eines Originals sind bekannt. Typischerweise ist das erfasste Bild, das durch einen Scanner bereitgestellt wird, ein Pixeldatenarray, das in einem digitalen Format in einem Speicher gespeichert wird. Ein verzerrungsfreies Bild erfordert eine getreue Abbildung des Originalbildes auf das Pixeldatenarray. Scanner umfassen typischerweise zumindest eine Einrichtung zum Auferlegen einer mechanischen Beschränkung während des Bilderfassungsvorgangs, um die Wahrscheinlichkeit einer getreuen Abbildung zu maximieren. Die vier Typen von Scannern, die in der Technik bekannt sind, sind Trommelscanner, Flachbettscanner, Scanner mit zweidimensionalem Array und Hand-Scanner.

Trommelscanner bringen das Original an der Oberfläche einer zylindrischen Trommel an, die sich mit einer im Wesentlichen festen Geschwindigkeit dreht. Während der Drehung der Trommel wird ein Bildsensor in einer Richtung parallel zu der Drehachse der Trommel bewegt. Die Kombination der Linearverschiebung des Bildsensors und der Drehung des Originals auf der Trommel erlaubt ein Scannen des gesamten Originals. Zu einem bestimmten Moment während des Bilderzeugungsvorgangs kann die gegenwärtige Position innerhalb des Pixeldatenarrays relativ zu dem Original durch Messen der Winkelposition der Trommel und der Verschiebungsposition des Sensors bestimmt werden. Die Position des Pixeldatenarrays in Bezug auf das Original ist fest, solange das Original ordnungsgemäß an der Trommel angebracht ist, die Trommeldrehung ordnungsgemäß gesteuert wird und der Sensor in seiner Verschiebung entlang des linearen Wegs ordnungsgemäß gesteuert wird.

Flachbettscanner umfassen einen Lineararraysensor, der relativ zu dem Original entlang einer Achse bewegt wird, die senkrecht zu der Achse des Arrays ist. So kann die Position des Sensors in einer Dimension bekannt sein, indem die relative Bewegung des Sensors verfolgt wird. Die Position des Sensors in der senkrechten Richtung wird implizit durch Adressieren eines bestimmten Arrayelements, an dem eine Intensität gemessen werden soll, fixiert. Bei einem Ausführungsbeispiel des Flachbettscanners ist das Original auf einer transparenten Auflage platziert und der Sensor ist gemeinsam mit einer Bildbeleuchtungsquelle auf einer Seite der Auflage gegenüber von dem Original platziert. Solange das Original relativ zu der Auflage nicht bewegt wird, ist das Pixeldatenarray in Bezug auf das zu erfassende Bild fixiert. Bei einem weiteren Ausführungsbeispiel wird das Original bewegt, und nicht der Sensor. Dieses zweite Ausführungsbeispiel ist typisch für Faxgeräte. Präzisionspapiertransporte stellen ein hohes Maß an Positionsgenauigkeit während des Bilderfassungsvorgangs bereit.

Vorteile der Trommel- und Flachbettscanner umfassen die Fähigkeit, Dokumente unterzubringen, die zumindest so groß wie A4-Papier oder Papier mit 8,5 Zoll × 11 Zoll sind. Ferner können einige dieser Scanner A1-Papier in einem einzelnen Aufbau handhaben. Die Scanner jedoch sind allgemein nicht tragbar, da sie einen Host-Computer zur Steuerung, Datenspeicherung und Bildmanipulation benötigen.

Scanner mit zweidimensionalem Array könnten in Abwesenheit mechanischer Codierungsbeschränkungen eingesetzt werden und machen es nur erforderlich, dass das Array und das Original während einer Belichtungsperiode bewegungsfrei gehalten werden. Ein zweidimensionales Array photoempfindlicher Elemente erzielt direkt die Abbildung des Bildes des Originals in ein Pixeldatenarray. Da jedoch eine einzelne 300dpi-Abbildung eines Originals mit 8,5 Zoll × 11 Zoll einen Bildsensor erfordert, der ein Array mit 2.500 × 3.300 Elementen aufweist, d. h. 8,25 Millionen Pixeln, sind diese Scanner in den meisten Anwendungen aus Kostengründen untragbar.

Herkömmliche Hand-Scanner machen es erforderlich, dass ein Benutzer ein Lineararray elektrooptischer Sensorelemente über ein Original bewegt. Die Bewegung geschieht durch Handmanipulation. Arraypositionsinformationen werden unter Verwendung von Verfahren bestimmt, wie z. B. denjenigen, die beim Betrieb einer Computer-"Maus" eingesetzt werden. Wenn ein Linearsensorarray bewegt wird, wird die Drehung von Rädern, Kugeln oder Rollen, die in Kontakt mit dem Original sind, erfasst und die Positionsinformationen werden aus den mechanischen Details der Drehung bestimmt. Allgemein weist die Oberfläche des mechanischen Elements, das in Kontakt mit dem Original ist, einen hohen Reibungskoeffizienten auf, z. B. Gummi, um so einem Rutschen und Gleiten zu widerstehen. Eine zylindrische Rolle oder zwei Räder, die durch eine starre Achse verbunden sind, könnten verwendet werden, um während des Scannvorgangs einen einzelnen Verschiebungsfreiheitsgrad durchzusetzen. Eine Halterung mit gerader Kante oder eine andere Halterung wird oft verwendet, um die Scannrichtung in Bezug auf das Original zu fixieren und ferner die Verschiebungsbeschränkung, die durch das Paar von Rädern oder Rollen bereitgestellt wird, durchzusetzen. Trotzdem ist der Positionscodiereransatz einer, der oft anfällig für Rutschen und Gleiten ist, so dass das Pixeldatenarray seine Entsprechung zu dem Bild auf dem Original verliert.

Hand-Scanner sind typischerweise mit einem separaten Computer zur Bilddatenspeicherung, -verarbeitung und -verwendung verbunden. Datenraten von dem Bildsensor neigen zu einer Einschränkung der Scanngeschwindigkeit. Die Scanner liefern Rückkopplung an den Benutzer, typischerweise mittels grüner oder roter Leuchtdioden, um die geeignete Geschwindigkeit für die erwünschte Bildauflösung beizubehalten. Einige Hand-Scanner verwenden elektromagnetische Bremsen, um zu verhindern, dass der Benutzer den Scanner zu schnell über das Bild zieht, wobei der mechanische Widerstand mit ansteigender Scanngeschwindigkeit zunimmt.

Hand-Scanner verwenden relativ kleine Bilderzeugungsarrays und können allgemein in einem einzelnen Durchlauf keine größeren Dokumente als A6 handhaben. Dies erfordert Zusammenheftalgorithmen zur Verbindung mehrerer Bänder eines größeren Dokuments miteinander. Ein Bandzusammenheften könnte in einer separaten Operation durch einen separaten Computer durchgeführt werden. Ein Abtasten eines mehrseitigen Geschäftsdokuments oder Berichts mit einem Hand-Scanner ist ein mühsamer Vorgang, der oft Ergebnisse von geringer Qualität ergibt. Techniken zum Zusammenheften von Bildbändern sind in der Scanntechnik bekannt. Diese Techniken erfordern typischerweise ein Paar vollständiger Bildbänder und erzeugen eine einzelne Globaltransformation, die die beiden Bänder in Ausrichtung bringt. Verbesserte Techniken sind in der internationalen Patenanmeldung mit der Veröffentlichungsnummer WO96/27257 gelehrt. Die GB-A-2288512 lehrt ein Verfahren zum Verbinden von Bildern ohne Verbindungszwischenräume durch Einstellen von Positionsfehlern und Auflösung.

Bei der Erzeugung eines abgetasteten elektronischen Bildes ist es nötig, Navigationsinformationen zu erfassen, die gemeinsam mit Bilddaten erfasst werden. Ein Hand-Scanner, in dem Navigationsinformationen ohne Kompromiss zur Erleichterung einer Verwendung des Scanners erhalten werden, ist in dem U.S.-Patent Nr. 5578813 beschrieben. Die Navigationsinformationen werden mittels zumindest eines Navigationssensors erfasst, der inhärente strukturbezogene Eigenschaften eines gerade gescannten Originals erfasst. Die Bewegung eines Bildsensors entlang des Originals wird durch Überwachen von Variationen der inhärenten strukturbezogenen Eigenschaften verfolgt, wenn der Bildsensor relativ zu dem Original bewegt wird. Die inhärenten strukturbezogenen Eigenschaften, die überwacht werden, sind inhärente Strukturmerkmale, wie z. B. Papierfasern oder andere Bestandteile des Originals. Eine Navigation kann alternativ auf Fleckenbasis sein, wobei eine Bewegung des Bildsensors entlang des Originals durch Überwachen von Variationen von Fleckenmustern verfolgt wird, die unter Verwendung kohärenter Beleuchtung zur Erfassung der Navigationsinformationen erzeugt werden.

„Inhärente strukturbezogene Eigenschaften" sind Eigenschaften des Originals, die Faktoren zuzuschreiben sind, die unabhängig von der Erzeugung von Bilddaten und/oder von systematischen Ausrichtungsdaten auf dem Original sind. Die Navigationsinformationen könnten durch Erzeugen eines Positionssignals, das auf die Erfassung inhärenter strukturbezogener Eigenschaften anspricht, gebildet werden, wie z. B. eines Positionssignals von Fleckeninformationen oder eines Positionssignals, das eine Verfolgung einzelner inhärenter Strukturmerkmale erlaubt. „Inhärente Strukturmerkmale" sind diejenigen Merkmale eines Originals, die charakteristisch für Vorgänge eines Erzeugens des Originals sind und unabhängig von der Erzeugung von Bilddaten und/oder systematischen Ausrichtungsdaten auf dem Original sind. Wenn z. B. das ursprüngliche Aufzeichnungsmedium ein Papierprodukt ist, könnten die inhärenten Strukturmerkmale von Interesse Papierfasern sein. Als weiteres Beispiel könnte eine Navigation des Bildsensors über ein Hochglanzoriginal oder eine Overhead-Transparenzfolie durch Verfolgen von Oberflächentexturvariationen, die Fleckenfelder beeinflussen, bestimmt werden. Typischerweise sind die inhärenten Strukturmerkmale mikroskopische, z. B. zwischen 10 und 40 &mgr;m, Merkmale der Oberflächentextur.

Die vorliegende Erfindung ist direkt anwendbar auf Hand Scanner, wie sie in der internationalen Patentanmeldung mit der Veröffentlichungsnummer WO96/27257 und dem U.S.-Patent Nr. 5578813 gelehrt werden, wobei diese beiden Anmeldungen beide durch Bezugnahme zu dem Ausmaß, das durch nationales Recht zulässig ist, aufgenommen sind.

Wie zuvor angemerkt wurde, wird ein bestimmter Typ von Halterung typischerweise mit einem Hand-Scanner verwendet. Ohne eine Halterung (wie dies der Fall für die meisten Ausführungsbeispiele in dem U.S.-Paten Nr. 5578813 ist) besteht eine Tendenz, eine bestimmte Drehung einzuführen, wenn der Hand-Scanner über ein Original bewegt wird. Wenn der Ellenbogen des Benutzers während einer Bewegung des Scanners auf einer flachen Oberfläche aufliegt, besitzt die Drehung wahrscheinlich einen Radius, der durch die Entfernung zwischen dem Scanner und dem Ellenbogen des Benutzers definiert ist. Als eine Folge ist das gescannte elektronische Bild verzerrt. Andere krummlinige Bewegungen während eines Bands des Scanners erzeugen ebenso Verzerrungen.

Die vorliegende Erfindung möchte eine Scann- bzw. Abtastvorrichtung und ein Verfahren bereitstellen, das eine qualitativ hochwertige verzerrungsfreie Reproduktion eines Originals selbst bei Vorliegen verzerrter Abtastwege erzeugt. Dies ermöglicht dem Benutzer größere Freiheit für das Scannen eines Dokuments von Hand und ermöglicht die Erzeugung eines zusammengesetzten Bildes aus dem durchgehenden Scannen überlappender Teile eines Originalbildes mit einem hohen Maß an Entsprechung zwischen dem Original und dem reproduzierten Bild.

Zusammenfassung der Erfindung

Gemäß der vorliegenden Erfindung stellen wir ein Verfahren zum Rekonstruieren eines Bildes, das als Bilddaten in einem Linearsensorarray und Positionsdaten in einer Navigationseinrichtung erfasst wird, bereit, wobei das Bild in der Form eines Stroms aufeinander folgender Sensorablesewerte erfasst wird, wobei jeder Sensorablesewert einen Ablesewert jedes Elements in dem Linearsensorarray aufweist, wobei Positionsdaten für jeden Sensorablesewert erfasst werden, wobei das Verfahren folgende Schritte aufweist: Definieren eines Pixelgitters für ein rekonstruiertes Bild; Identifizieren eines oder mehrerer Pixel in dem Pixelgitter, für die dieser Teil der Bilddaten relevant ist, aus einem Teil der Bilddaten durch Verwenden der Positionsdaten, das ein Definieren einer Region in dem Pixelgitter, die durch Abbilden von Positionen äußerer Elemente des Linearsensorarrays für zwei unterschiedliche Sensorablesewerte in dem Strom auf das Pixelgitter erhalten wird, aufweist, wobei die Positionen aus den Positionsdaten für die beiden unterschiedlichen Sensorablesewerte erhalten werden; und Auswählen einer Mehrzahl relevanter Bilddatenwerte aus diesem Teil der Bilddaten für ein Pixel des einen oder der mehreren Pixel in der Region des Pixelgitters; und Bestimmen der Intensität des Pixels unter Verwendung der relevanten Bilddatenwerte, die für dieses Pixel ausgewählt sind.

Dieses Verfahren ist besonders wirksam, wenn es auf die Rekonstruktion eines hand-gescannten Bildes angewendet wird, das als ein Strom aufeinander folgender Sensorablesewerte mit Positionsdaten für jeden Sensorablesewert erhalten wird. Die Abhängigkeit von einem einzelnen Sensorablesewert des Scanners wird reduziert und Daten aus sogar unregelmäßigem Scannen können mit relativ wenig Rechenaufwand zusammengefügt und verarbeitet werden.

Vorzugsweise weist der Schritt des Identifizierens eines oder mehrerer Pixel in dem Pixelgitter ein Definieren einer Region in dem Pixelgitter, die erhalten wird, indem auf das Pixelgitter Positionen äußerer Elemente des Linearsensorarrays für zwei unterschiedliche Sensorablesewerte in dem Strom abgebildet werden, auf, wobei die Positionen aus den Positionsdaten für die beiden unterschiedlichen Sensorablesewerte erhalten werden; und wobei die Schritte des Auswählens relevanter Bilddatenwerte und des Bestimmens der Intensität für Pixel innerhalb der Region durchgeführt werden. Die ausgewählten Sensorablesewerte könnten entweder zwei aufeinander folgende Ablesewerte in dem Strom sein oder könnten alternativ beliebige zwei Sensorablesewerte in dem Strom sein, wobei in diesem Fall beliebige Sensorablesewerte in dem Strom zwischen den Grenzsensorablesewerten ebenso als relevant für Pixel innerhalb der Region auswählbar sind, wobei die Grenzsensorablesewerte und alle Sensorablesewerte zwischen denselben in dem Strom einen Brocken aufweisen. Dieser "Brocken"-Ansatz opfert etwas Genauigkeit für einen wesentliche Reduzierung des Rechenaufwands.

Bei bevorzugten Ausführungsbeispielen weist der Schritt des Identifizierens einer Entsprechung zwischen Bilddaten und dem Pixelgitter ferner den Schritt eines Bestimmens, welche Pixel in dem Pixelgitter in diese Region fallen, die durch die Grenzsensorablesewerte definiert ist, auf. Vorzugsweise werden Pixel in dem Pixelgitter in einen Raum abgebildet, der durch die Grenzsensorablesewerte definiert ist, und die Gitterpixel, für die eine Intensität bestimmt ist, sind diejenigen, die innerhalb des definierten Raums abbilden.

Bei bestimmten Ausführungsbeispielen wird die Intensität eines Pixels durch Interpolation aus Sensorpixelwerten in jedem zweier aufeinander folgender Sensorablesewerte bestimmt, wobei die Sensorpixelwerte ausgewählt sind, um das Gitterpixel, das in den Raum abgebildet wird, zu überspannen. Vorzugsweise ist die Interpolation eine bilineare Interpolation aus zwei Sensorpixelwerten in jedem zweier aufeinander folgender Sensorablesewerte. Bei alternativen Ausführungsbeispielen wird der Schnittpunkt einer Linie in dem Pixelgitter mit Positionen nachfolgender Sensorablesewerte bestimmt, wobei ein Sensorpixelwert für den Schnittpunkt durch Interpolation zwischen den Sensorpixelwerten an beiden Seiten des Einfügungspunkts berechnet wird, und wobei die Pixelintensitätswerte für ein Gitterpixel entlang dieser Linie durch Interpolation zwischen Schnittpunktsensorwerten berechnet werden. In dem Fall, in dem die Linie in dem Pixelgitter eine Zeilen von Pixeln ist, wird ein besonders recheneffizientes Verfahren bereitgestellt.

Vorzugsweise ist der Sensor in einer Scann- bzw. Abtastvorrichtung beinhaltet, insbesondere einem Hand-Scanner. Bei einem weiteren Aspekt stellt die Erfindung eine Scannvorrichtung zum Implementieren eines Verfahrens, wie oben angezeigt wurde, bereit und stellt ferner eine Scannvorrichtung zum Sammeln von Bilddaten bereit, die zur Verbindung mit einem Computersystem zur Durchführung eines Verfahrens, wie oben angezeigt wurde, entworfen ist.

Navigationsinformationen könnten in einer Vielzahl von Weisen bereitgestellt werden, wie in dem U.S.-Patent Nr. 5578813 gelehrt ist. In dem breitesten Ansatz besteht keine Einschränkung bei den Quellen von Navigationsinformationen, die verwendet werden sollen, um Verzerrungsartefakte einer krummlinigen und Drehbewegung der Scannvorrichtung entlang eines Abtastwegs zu entfernen. Das Navigationssignal könnte deshalb in der Form eines Positionssignals vorliegen, das auf die Erfassung von Bilddaten über das Original (z. B. Identifizierung von Kanten von Textzeichen) anspricht, wobei das Positionssignal dann bei der Manipulation eines Bildsignals verwendet wird. Ein zweiter Ansatz ist einer, bei dem ein Positionssignal auf die Erfassung inhärent strukturbezogener Eigenschaften anspricht, wie z. B. die Eigenschaften, die Fleckenmuster bestimmen. Der dritte Ansatz besteht darin, eine Navigation der Abtastvorrichtung zu verfolgen, indem die Positionen einzelner inhärenter Strukturmerkmale (z. B. Papierfasern) über die Zeit überwacht werden.

In den zu beschreibenden Ausführungsbeispielen ist der Bildsensor ein lineares Array elektrooptischer Elemente, während der Navigationsansatz zumindest ein zweidimensionales Array von Navigationssensorelementen einsetzt. Durch Platzieren eines separaten zweidimensionalen Navigationsarrays an jedem Ende des Bildsensors werden dem Scanner drei Bewegungsfreiheitsgrade verliehen. Wenn das Original planar ist, sind zwei der Freiheitsgrade translatierend und sind senkrecht zueinander innerhalb der Ebene des Originals, während der dritte Freiheitsgrad drehmäßig um die Normale zu der Ebene des Originals ist. Die Genauigkeit einer Drehungsverfolgung wird durch die Verwendung zweier Navigationsarrays verbessert, wobei jedes Array ein kleineres Arrayausmaß aufweist als nötig wäre, wenn ein einzelnes Navigationsarray verwendet würde. Während das beschriebene Ausführungsbeispiel eines ist, bei dem ein Navigationssensor ein zweidimensionales Array ist, könnten auch lineare Arrays verwendet werden. Ferner könnten, wie unten detaillierter beschrieben ist, Navigationsinformationen zum Gleichrichten von Bilddaten möglicherweise durch Befestigen einer anderen Positionsverfolgungseinrichtung an der Abtastvorrichtung erfasst werden, einschließlich Codierrädern und -kugeln, Computermaus-Verfolgungskugeln, Ausrichtungsgitterdetektoren, Beschleunigungsmessern, mechanischen Verbindungen, berührungsfreien elektromagnetischen und elektrostatischen Verbindungen und Zeitverzögerungsintegrationssensorarrays. Bei vielen dieser alternativen Ausführungsbeispiele werden Navigationsinformationen zum Gleichrichten der Bilddaten in Weisen erfasst, die unabhängig von inhärenten strukturbezogenen Eigenschaften des Originals sind, da eine Positionsverfolgung keine Bilderfassung umfasst.

Die Navigationssensoren sind in einer bekannten Position relativ zu dem Bildsensor. Vorzugsweise sind die Navigationssensoren so nahe an den Endpunkten des Bilderzeugungssensors wie möglich, so dass die Navigationssensoren weniger anfällig für eine Bewegung über die Kante eines Originals hinaus sind, wenn das Bildarray bewegt wird. Der Bildsensor erzeugt ein Signal, das ein Bild von Interesse darstellt. Gleichzeitig bildet jeder Navigationssensor ein Signal, das die inhärenten strukturbezogenen Eigenschaften des Originals darstellt. Die Abtastvorrichtung könnte in einem freihändigen mäanderförmigen Muster bewegt werden, wie z. B. einer abwechselnden Links-nach-Rechts- und Rechts-nach-Links-Bewegung beim Abfahren entlang des Originals, wobei die Vorrichtung in Kontakt mit dem Original bleibt. Jedes der Seite-zu-Seite-Bänder sollte einen Abschnitt des vorherigen Bandes überlappen, so dass das Bild in Bezug auf eine Position manipuliert und entweder während oder nach dem Abtastvorgang zusammengeheftet werden kann. Die Manipulation des Bildsignals ist eine Gleichrichtung von Bilddaten, wobei die Gleichrichtung auf der relativen Bewegung zwischen dem Navigationssensor oder -sensoren und den inhärenten strukturbezogenen Eigenschaften, die durch die Navigationssensoren erfasst werden, basiert. Die Manipulation ist eine „Gleichrichtung" des Bildsignals, d. h. eine Operation eines Anordnens und Modifizierens erfasster Bilddaten basierend auf Navigationsdaten, um eine Übereinstimmung zwischen einem ursprünglichen und einem ausgegebenen Bild zu erzielen. Das Zusammenheften wird verwendet, um Bilddaten, die während aufeinander folgender Bänder erfasst werden, zu verbinden.

Jeder Navigationssensor könnte eine oder mehrere Lichtquellen umfassen, die entworfen sind, um einen Kontrast abhängig von den inhärenten strukturbezogenen Eigenschaften des Originals bereitzustellen. Emittiertes Licht könnte in dem sichtbaren Bereich sein, dies ist jedoch nicht notwendig. „Streifendes" Licht z. B., das große Einfallswinkel relativ zu der Oberflächennormalen aufweist, steht mit Papierfasern an oder nahe der Oberfläche eines Originals, das ein Papierprodukt ist, in Wechselwirkung, was unter den Fasern Kontrastverstärkungsschatten erzeugt. Andererseits erzeugt, wenn das Original eine Hochglanzoberfläche aufweist, wie z. B. einen Photographiedruck, ein kaolingestrichenes Papier oder eine Overhead-Transparenzfolie, normal einfallendes Licht ein Bild in dem Spiegelfeld, das Bildkontrastmerkmale besitzt, die ausreichend zu Zwecken einer Navigation sind. Optische Elemente, wie z. B. Filter und eine oder mehrere Bilderzeugungslinsen, verbessern eine Erfassung inhärenter strukturbezogener Eigenschaften weiter.

Ein Vorteil der beschriebenen Ausführungsbeispiele besteht darin, dass die Abtastvorrichtung und das Verfahren drei Bewegungsfreiheitsgrade der Abtastvorrichtung erlauben, während dennoch eine Qualitätsbilderfassung geboten wird. So könnte eine tragbare Abtastvorrichtung in Taschengröße ohne andere mechanische Beschränkungen hergestellt und verwendet werden als durch einen Kontakt mit der Oberfläche des Originals während des gesamten Bilderfassungsvorgangs geboten werden. Die Erfindung ist in einer Anwendung nicht auf Ausführungsbeispiele eingeschränkt, in denen die Abtastvorrichtung in Kontakt mit dem Original steht – mit geeigneten Navigationsinformationen ist eine Bildrekonstruktion aus Bildern, die in verschiedenen Umgebungen erfasst werden, möglich. Ein weiterer Vorteil besteht darin, dass, da die Abtastvorrichtung der beschriebenen Ausführungsbeispiele ein elektronisches Bild basierend auf einer Detektion inhärenter Strukturmerkmale erzeugt, große Bereiche eines „Weißraums" zwischen Bildmerkmalen des Originals erhalten bleiben und deshalb nicht dazu führen, dass Bildmerkmale während eines Zusammenheftschritts näher zusammenbewegt werden.

Kurze Beschreibung der Zeichnungen

1 ist eine perspektivische Ansicht einer Hand-Abtastvorrichtung, die einem mäanderförmigen Weg auf einem Original folgt.

2 ist eine Rückansicht von Bilderzeugungs- und Navigationssensoren der Abtastvorrichtung aus 1.

3 ist eine perspektivische Ansicht der Abtastvorrichtung aus 1, die mit freiliegenden Bilderzeugungs- und Navigationssensoren gezeigt ist.

4 ist eine schematische Seitenansicht eines Beleuchtungssystems für einen der Navigationssensoren aus 3.

5 ist eine schematische Seitenansicht einer Leuchtdiode und optischer Elemente zur Bereitstellung der Beleuchtung, die unter Bezugnahme auf 4 beschrieben ist.

6 ist eine konzeptionelle Ansicht der Bilderfassungsoperation der Abtastvorrichtung aus 1.

7 ist eine Funktionsansicht eines Ausführungsbeispiels der Navigationsverarbeitung der Abtastvorrichtung aus 1.

8 ist eine schematische Ansicht ausgewählter Schritte aus 7.

9a ist ein Blockdiagramm der Komponenten zur Ausführung der Schritte aus 8.

9b stellt eine Interpretation von Daten bei einer Navigationsverarbeitung dar.

10a ist eine Darstellung einer Inkrementierung eines mit Positionsetiketten versehenen Datenstroms, der typisch für die Ausgabe aus dem Navigationsprozess aus 9 ist.

10b ist eine Darstellung eines Zwischenspeichers bzw. Puffers, der eine Vielzahl von mit Positionsetiketten versehenen Dateninkrementen speichert.

11 zeigt einen Geradliniges-Bild-Puffer, der den Ort bzw. Lokus der Endpunkte der Abtastwerte aus dem Linearbildsensor zeigt.

12 ist eine Darstellung von Bändern, die durch die Abtastvorrichtung aus 1 gesammelt werden.

13 zeigt die Puffer, die bei einem Einphasenvorgang gemäß der vorliegenden Erfindung verwendet werden.

14 stellt Bänder dar, die gesammelt werden, wenn der Einphasenvorgang verwendet wird.

15 ist eine Darstellung einer Ausrichtungskachel, die verwendet werden könnte, um ein Zusammenheften aufeinander folgender Bänder zu erzielen.

16 zeigt die Puffer, die bei einem Zweiphasenvorgang zum Erzielen eines Zusammenheftens aufeinander folgender Bänder verwendet werden.

17 stellt Bänder dar, die gesammelt werden, wenn der Zweiphasenvorgang aus 16 verwendet wird.

18 zeigt einen Abschnitt eines Geradliniges-Pixel-Arrays, das das abgetastete Bild definiert, wobei zwei Linearbildsensorpositionen auf demselben abgebildet sind.

19 zeigt die Rückabbildung eines Pixels in dem geradlinigen Raum aus 18 auf einen Raum, der durch die beiden Linearbildsensorpositionen definiert ist.

20 zeigt die lineare Interpolation von Pixelwerten in den in 18 gezeigten Bildsensorpositionen.

21 zeigt eine weitere Form einer linearen Interpolation von Pixelwerten in den in 18 gezeigten Bildsensorpositionen.

22 zeigt einen Abschnitt eines Geradliniges-Pixel-Arrays, das das abgetastete Bild definiert, mit einer Serie von Linearbildsensorpositionen, die auf dasselbe abgebildet sind.

23 zeigt die Rückabbildung eines Pixels in dem geradlinigen Raum aus 21 auf einen Raum, der durch die Linearbildsensorpositionen definiert ist.

24 zeigt die Verwendung einer Hilfsabbildungstabelle zur Normierung eines Raums, der durch Linearbildsensorpositionen definiert ist.

Bester Modus zur Ausführung der Erfindung

Unter Bezugnahme auf 1 ist eine tragbare Hand-Abtastvorrichtung 10 als einem mäanderförmigen Weg 12 entlang eines Originals 14 folgend gezeigt. Das Original könnte ein Stück Papier, eine Overhead-Transparenzfolie oder eine weitere ein Bild tragende Oberfläche sein. Die inhärenten strukturbezogenen Eigenschaften des Originals könnten verwendet werden, um Positionsinformationen während einer Navigation entlang des mäanderförmigen Wegs bereitzustellen. Bei diesem Ansatz werden die Positionen der inhärenten Strukturmerkmale verfolgt und die Positionsinformationen werden verwendet, um Bilddaten gleichzurichten, andere Ausführungsbeispiele werden jedoch beschrieben. Die Abtastvorrichtung ist vorzugsweise unabhängig und batteriebetrieben, könnte jedoch eine Verbindung zu einer externen Leistungsquelle oder zu Datentoren von Computern oder Netzwerken umfassen.

Die Abtastvorrichtung 10 aus 1 umfasst eine Bildanzeige 16, um eine Betrachtung eines erfassten Bildes zu ermöglichen. Eine Anzeige ist für die Verwendung der Abtastvorrichtung jedoch nicht wesentlich.

Unter Bezugnahme auf die 13 umfasst die Vorwärtsseite 18 der Abtastvorrichtung 10 ein Schwenkbauteil 20, das eine Beibehaltung eines ordnungsgemäßen Kontaktes zwischen dem Original 14 und einem Bilderzeugungssensor 22 unterstützt. Der Bilderzeugungssensor 22 weist ein lineares Array von Bildsensorelementen auf. Navigationssensoren 24 und 26 befinden sich an den gegenüberliegenden Enden des Bilderzeugungssensors. Die Navigationssensoren 24, 26 sind an dem Schwenkbauteil befestigt und so sind die Navigationssensoren an einem festen Ort relativ zu dem Bilderzeugungssensor.

Die Abtastvorrichtung 10 ermöglicht drei Freiheitsgrade, wobei zwei in einer Translation sind und einer in einer Drehung. Der erste Grad ist die Seite-zu-Seite-Bewegung (X-Achsenbewegung) entlang des Originals 14. Der zweite Freiheitsgrad ist eine Bewegung nach oben und unten entlang des Originals (Y-Achsenbewegung). Der dritte Freiheitsgrad ist die Fähigkeit, die Vorrichtung mit einer Drehfehlausrichtung eines Bilderzeugungssensors 22 relativ zu einer Kante des Originals 14 zu betreiben. Dies bedeutet, dass der Bilderzeugungssensor 22 einen Angriffswinkel besitzen könnte, der nicht senkrecht zu der Richtung einer Vorrichtungstranslation ist.

Aus Gründen physischer Kompaktheit ist der Bilderzeugungssensor 22 vorzugsweise eine Kontaktbildvorrichtung, für Anwendungen jedoch, in denen eine Kompaktheit weniger von Belang ist oder ein kleineres Bild erwünscht wird, könnten Sensoren, die Projektionsoptiken einsetzen, verwendet werden, mit einer Vergrößerung von weniger als Eins. In derartigen Anwendungen sollten die Elemente des Bilderzeugungssensors 22 kleiner und dichter zusammengepackt sein. Kontaktbilderzeugungsvorrichtungen setzen typischerweise Linsen ein, die unter dem Markennamen SELFOC verkauft werden, was ein Markenname der Nippon Sheet Glass Company Limited ist. Weniger herkömmlich kann eine Kontaktbilderzeugung unter Verwendung verschachtelter Arrayelemente von Quellen und nahen Sensoren erhalten werden, ohne Bilderzeugungslinsen. Herkömmliche Bilderzeugungssensoren für Abtastanwendungen könnten verwendet werden. Der Bilderzeugungssensor könnte Teil einer Einheit sein, die auch eine Beleuchtungsquelle, Beleuchtungsoptiken und Bildübertragungsoptiken umfasst.

Der Bilderzeugungssensor 22 ist als ein lineares Array diskreter optisch empfindlicher Elemente gezeigt. Die Beabstandung der Elemente spielt eine Rolle bei der Bestimmung der räumlichen Auflösung des Scanners 10. Ein lineares Array mit einer Länge von 101,6 mm z. B. benötigt 1.200 Sensorelemente, um eine Auflösung von 300 dpi zu erzielen. Der Sensor könnte ein ladungsgekoppeltes Bauelement, ein Amorphes-Silizium-Photodiodenarray oder ein bestimmter anderer Typ von Lineararraysensor, der in der Technik bekannt ist, sein.

Eine Schlüsselüberlegung bei dem Entwurf der Bilderzeugungssensoreinheit ist Geschwindigkeit. Der Bilderzeugungssensor 22 ist vorzugsweise in der Lage, jedes Pixel mit etwa 10 tausend Abtastwerten pro Sekunde abzubilden. Linearbilderzeugungsarrays erzeugen allgemein einen seriellen Datenstrom, wobei Pixelwerte, d. h. Ladungen, in ein Schieberegister platziert und dann herausgeschoben werden. Ein Erzielen der erwünschten Geschwindigkeit erfordert entweder sehr schnelle serielle Übertragungsraten aus dem gesamten Bildarray heraus oder mehrere Abgriffe, so dass Pixelwerte durch weniger Zellen verschoben werden können. Dies führt Parallelität ein, was für eine digitale Verarbeitung von Vorteil ist.

Eine weitere Folge der Geschwindigkeitsanforderung ist die, dass die Produkte von Pixelbereichen an der Oberfläche des Originals und deren Raumwinkel emittierten Lichts, das gesammelt und zu jedem Arrayelement befördert wird, ausreichend groß sein sollten, um ein erfassbares Signal in Integrationszeiten in der Größenordnung von 100 Mikrosekunden zu erzeugen. Eine Verbesserungsoption besteht darin, ein optisches Element zu dem Sensor hinzuzufügen, um den wirksamen Bruchteil einer Sensorteilung zu erhöhen, für den jedes Leseelement anspricht. Da es üblicherweise in der Arraymatrix nicht verwendete Fläche gibt, erhöhen derartige Lichtsammeloptiken eine Empfindlichkeit.

Eine einfache Modifizierung des Bilderzeugungssensors 22 ermöglicht ein Lesen von Farbbildern. Drei lineare Arrays parallel zueinander, jedes mit zumindest einem eingebetteten Filterelement, das selektiv rote, grüne bzw. blaue Komponenten des einfallenden Lichts durchlässt, würden eine Farbbilderzeugung erlauben. Alternativ könnte ein einzelnes Array mit Breitbandempfindlichkeit nacheinander durch Rot-, Grün- und Blaulichtquellen beleuchtet werden.

Bezüglich einer Beleuchtung zum Verbessern des Betriebs des Bilderzeugungssensors 22 könnte ein lineares Array von Leuchtdioden mit hoher Intensität bei der Amber-Wellenlänge verwendet werden. Die Auswahl der bevorzugten Beleuchtungsquelle und möglicher optischer Elemente jedoch hängt von dem Medium des Originals ab. Die Wellenlänge des Lichts wird ausgewählt, um die Kontrastbilddaten, die während der Abtastung eines bestimmten Bereichs des Originals 14 erfasst werden, zu maximieren, wobei ungewollte Signale ignoriert werden. Beleuchtungsoptiken könnten aus LED-Kuppellinsen bestehen oder könnten einen Lichtleiter umfassen, der aus einem präzisionsgeformten optischen Element besteht, das die Beleuchtung mit minimaler Menge an Lichtverlust auf das Original kanalisiert. Ein derartiger Entwurf kann eine relativ einheitliche Beleuchtung eines Zielbereichs des Originals mit einem breiten Bereich von Winkeln bieten, blockiert jedoch normale einfallende Strahlen, um Spiegeloberflächenreflexionen zu vermeiden.

In 1 ist der mäanderförmige Weg 12 als vier Bänder und ein Bruchteilsband, d. h. Seite-zu-Seite-Durchläufe über das Original 14, aufweisend gezeigt. Ein nützlicher Bilderzeugungssensor 22 für die meisten in Frage kommenden Anwendungen weist eine Länge innerhalb des Bereichs von 25,4 mm und 101,6 mm auf. Wenn der Sensor 22 eine Länge von 63,5 mm aufweist, kann ein A4-Papier in vier oder fünf Bändern abgetastet werden. Wie unten vollständiger erläutert wird, sollten die Bänder Regionen einer Überlappung umfassen, so dass ein Zusammenheftvorgang verwendet werden kann, um eine getreue Reproduktion des ursprünglichen Bilds zu erzeugen.

Die Abtastvorrichtung 10 umfasst zumindest einen Navigationssensor 24 oder 26. Bei dem bevorzugten Ausführungsbeispiel umfasst die Vorrichtung ein Paar von Navigationssensoren, wobei die Sensoren an gegenüber liegenden Enden des Bilderzeugungssensors 22 liegen. Während ein eindimensionales Array optoelektronischer Elemente verwendet werden könnte, ist bei dem bevorzugten Ausführungsbeispiel jeder Navigationssensor ein zweidimensionales Array von Elementen. Die Navigationssensoren 24 und 26 werden verwendet, um einen Bewegung der Abtastvorrichtung 10 relativ zu dem Original 14 zu verfolgen.

Bei einer bevorzugten Verwendung erfasst jeder Navigationssensor 24 und 26 Bilder in Bezug auf inhärente strukturbezogene Eigenschaften des Originals, um Informationen bezüglich der Position der Abtastvorrichtung 10 zu erzeugen. Für die meisten Abtastvorrichtungen des Stands der Technik werden inhärente Strukturmerkmale aus Rauschen betrachtet. Für die Abtastvorrichtung 10 der 13 sind derartige Merkmale Rauschen hinsichtlich des Bilderzeugungssensors 22, könnten jedoch verwendet werden, um eine Basis für die Navigationssensoren 24 und 26 zur Erzeugung von Positionsinformationen bereitzustellen. Nützliche kontrastreiche Bilder einer Oberflächentextur können durch Erfassen von Strukturvariationen erzeugt werden, die für das Medium inhärent sind oder auf dem Medium gebildet sind, wie z. B. Text. Bilder könnten z. B. basierend auf dem Kontrast zwischen Schatten in Tälern und hellen Punkten an den Spitzen inhärenter Strukturmerkmale gebildet werden. Derartige Merkmale sind typischerweise mikroskopischer Natur und variieren oft in der Größe zwischen 10 &mgr;m und 40 &mgr;m auf üblichen Druckmedien. Als eine Alternative könnten Flecken verwendet werden, da eine Spiegelreflexion eines kohärenten Strahls ein Kontrastmuster heller und dunkler Bereiche erzeugt. Eine dritte Quelle von Kontrastinformationen ist Farbe. Ein Farbkontrast ist unabhängig von der Oberflächentextur. Selbst wenn die texturfreie Oberfläche mit Licht in dem sichtbaren Bereich beleuchtet wird, gibt es Farbkontrast zwischen Regionen unterschiedlicher Farben, Z. B. zwischen unterschiedlichen Grauschattierungen.

Es kommt jedoch in Frage, die Erfindung für Anwendungen zu verwenden, in denen Navigationsinformationen unabhängig von inhärenten strukturbezogenen Eigenschaften des Originals sind. Einer oder beide der Navigationssensoren 24 und 26 aus 2 Z. B. könnten verwendet werden, um aufeinander folgende Bilder eines Drucks auf dem Original zu erzeugen, wobei eine Korrelation der aufeinander folgenden Bilder verwendet wird, um die Position und die Ausrichtung des Bildsensors 22 entlang des Originals 14 zu bestimmen. Bei diesem Ausführungsbeispiel bilden alle drei Sensoren 22, 24 und 26 Text auf dem Original ab, jedoch nur das Signal von dem Sensor 22 wird zur Erfassung von Bilddaten verwendet. Die Signale von den Navigationssensoren 24 und 26 werden verwendet, um Navigationsinformationen auf Bildbasis zu erfassen.

Wie in dem U.S.-Patent Nr. 5578813 erläutert ist, können bilderzeugungslose Ansätze auch verwendet werden, um X-, Y- und Winkelpositionsinformationen zu erfassen und zu verarbeiten. Leider erlegen viele der alternativen Mittel verschiedene Einschränkungen auf Kompaktheit, Bequemlichkeit einer Verwendung, Geschwindigkeit, Bewegungsfreiheit, Leistungsverbrauch, Genauigkeit, Präzision und/oder Kosten auf. Eine bilderzeugungsunabhängige Alternative, die für die Erfassung von Positionsinformationen verfügbar ist, besteht darin, eines oder mehrere Codierungsräder anstelle der Navigationssensoren bereitzustellen. Ein weiterer bildfreier Ansatz für die Erfassung von Navigationsinformationen besteht darin, Rollkugeln zu verwenden, die denjenigen für eine Computermaus ähneln. Ein weiterer bildfreier Ansatz für die Erfassung von Positions- und Ausrichtungsinformationen ist die Bereitstellung eines Beschleunigungsmessers. Wiederum ein weiterer alternativer Ansatz bestünde darin, beliebige einer Vielzahl mechanischer Verbindungen zu verwenden, mit denen Position und Ausrichtung relativ zu Bezugskoordinaten, die in Bezug auf das gerade gescannte Medium fest sind, verfolgt werden. Ein berührungsloses Fernlesen könnte auch verwendet werden, um Position und Ausrichtung der Abtastvorrichtung relativ zu Referenzkoordinaten zu messen, die in Bezug auf das gescannte Original fest sind.

Die Navigationssensoren 24 und 26 aus 2 beobachten wirksam sich bewegende Fenster auf dem Bild des Originals 14 und erzeugen eine Anzeige der Verschiebung in zwei planaren Dimensionen zwischen aufeinander folgenden Beobachtungen. Wie unten vollständiger erläutert wird, werden Pixelwerte aus den Navigationssensoren verarbeitet, um eine ordnungsgemäße Abbildung von Bilddaten aus dem Bilderzeugungssensor 22 zu bestimmen. Werte eines bestimmten Pixels und seiner nächsten Nachbarn werden verwendet, um ein Array von Korrelationswerten an jedem Pixelort zu erzeugen. Die Korrelationswerte basieren auf Vergleichen zwischen einem gegenwärtigen Bild der Oberflächenstruktur und einem gespeicherten Bild, das eine bekannte Position inhärenter Strukturmerkmale darstellt, wobei das gespeicherte Bild als eine Positionsreferenz dient. Andere Operationen als der Korrelationsvorgang könnten jedoch bei der Manipulation der Eingangsbilddaten zur Erzeugung des Ausgangsbildes verwendet werden.

Bezug nehmend auf die 4 und 5 ist ein Navigationssensor 24 als Beleuchtungsoptiken wirksam zugeordnet gezeigt. Wenn das Original 14 ein Papierprodukt ist, für das Papierfasern durch den Navigationssensor 24 erfasst werden sollen, wird die Einführung von Licht in einem streifenden Einfallswinkel bevorzugt. Während dies nicht nötig ist, könnten eine oder mehrere Leuchtdioden (LEDs) 28 verwendet werden. Der Streifwinkel 30, der das Komplement des Einfallswinkels ist, liegt vorzugsweise in dem Bereich von Null Grad bis 15 Grad, wobei dies abhängig von den Eigenschaften des Originals 14 variieren könnte. In 5 ist die Quelle 28 mit Beleuchtungsoptiken 34 gezeigt. Diese Optiken könnten ein einzelnes Element oder eine Kombination aus Linsen, Filtern und/oder holographischen Elementen aufweisen, um eine geeignete kollimierte und allgemein einheitliche Beleuchtung der Zieloberfläche zu erzielen. Die Wellenlänge des Lichts, das durch die Quelle 28 emittiert wird, sollte ausgewählt sein, um die Raumfrequenzinformationen, die zur Navigation verfügbar sind, zu verbessern. Ein festes Strukturrauschen in dem Beleuchtungsfeld sollte minimiert werden. Die Ausgabe der Quelle 28 könnte eine Anpassung erfordern, um weite dynamische Bereiche von Reflexionsvermögen des Mediums unterzubringen, wenn sich die Abtastvorrichtung über gedruckte Materialien bewegt, wobei Tinten oder andere Markierungsmittel absorbiert oder reflektiert werden.

In 4 wird Licht von einer Quelle 35 an Beleuchtungsoptiken 36 kollimiert und dann durch einen Amplitudenteilungs-Strahlteiler 37 umgeleitet. Der Teil der Lichtenergie von der LED, der direkt zu dem Strahlteiler geht und durch denselben durchgelassen wird, ist in 4 nicht gezeigt. Die Lichtenergie von dem Strahlteiler beleuchtet das Original 14 entlang der Normalen zu der Oberfläche.

Ebenso in 4 dargestellt ist der Teil der Lichtenergie, der von dem Original 14 reflektiert oder gestreut und durch den Strahlteiler 37 durchgelassen wird, zur Öffnung und Filterung an dem Element 38 und Fokussieren auf ein Bild an einem Element 39. Der Teil von Lichtenergie, der von dem Original zu dem Strahlteiler läuft und von dem Strahlteiler reflektiert wird, ist nicht gezeigt. Die Vergrößerung von Navigationsbilderzeugungsoptiken sollte über das Sichtfeld des zweidimensionalen Sensorarrays 24, das das fokussierte Licht erfasst, konstant sein. In vielen Anwendungen müssen die Modulationsübertragungsfunktionen, d. h. das Amplitudenmaß einer optischen Frequenzantwort, der Navigationsoptiken so sein, um eine Dämpfung vor der Nyquist-Frequenz bereitzustellen, die durch die Teilung der Sensorelemente des Navigationssensors und durch die Vergrößerung der optischen Elemente bestimmt ist. Die optischen Elemente sollten außerdem entworfen sein, um zu verhindern, dass Hintergrundbeleuchtung Rauschen erzeugt. Es wird angemerkt, dass auch ein eine Wellenfront teilender Strahlteiler verwendet werden könnte.

Die Auswahl des Einfallswinkels hängt von den Materialeigenschaften des Originals ab. Streifbeleuchtungswinkel erzeugen längere Schatten und einen offensichtlicheren Kontrast oder ein Wechselstromsignal, wenn die Oberfläche des Originals nicht hochglänzend ist. Der Pegel des Gleichstromsignals jedoch nimmt zu, wenn sich der Beleuchtungswinkel der Normalen zu dem Original annähert.

Ein Beleuchten der Zielregion des Originals 14 in einem Streifwinkel 30 funktioniert gut für Anwendungen, in denen die Oberfläche des Originals ein hohes Maß an Ungleichmäßigkeit auf der mikroskopischen Ebene besitzt. Die Einführung von Licht von der Quelle 28 in einem Streifwinkel z. B. liefert ein hohes Signal-Rausch-Verhältnis von Daten in Bezug auf inhärente Strukturmerkmale, wenn das Original Schreibwaren, Karton, Gewebe oder menschliche Haut ist. Andererseits könnte die Verwendung kohärenten Licht in einem normalen Einfallswinkel in Anwendungen bevorzugt werden, in denen Positionsdaten benötigt werden, um eine Scannerbewegung entlang derartiger Originale, wie z. B. Photographien, Hochglanzmagazinseiten und Overheadtransparenzfolien, zu verfolgen. Bei normaler Beleuchtung stellt unter Verwendung inkohärenten Lichts ein Betrachten des Originals in dem Spiegelreflexionsfeld ein Bild bereit, das einen ausreichend reichen Texturinhalt besitzt, um eine bild- und korrelationsbasierte Navigation zu ermöglichen. Die Oberfläche des Originals besitzt ein mikroskopisches Relief, derart, dass die Oberfläche Licht reflektiert, als ob die Oberfläche ein Mosaik von Kacheln oder Facetten wäre. Viele der „Kacheln" eines Originals reflektieren Licht in Richtungen, die leicht von der Normalen abweichen. Ein Sichtfeld, das das Streulicht und das Spiegelreflexionslicht umfasst, kann so modeliiert werden, als ob die Oberfläche aus vielen derartigen Kacheln bestünde, wobei jede derselben in Bezug auf die Normale etwas anders geneigt ist. Diese Modellierung ähnelt derjenigen von W. W. Barkas in einem Artikel mit dem Titel „Analysis of Light Scattered from a Surface of Low Gloss into Its Specular and Diffuse Components" in Proc. Phys. Soc., Bd. 51, S. 274–292 (1939).

4 zeigt eine Beleuchtung durch eine Quelle 35 inkohärenten Lichts, die entlang der Normalen der Oberfläche des Originals 14 gerichtet ist. 5 beschreibt eine Beleuchtung in einem Streifwinkel 30. Bei einer weiteren Alternative wird keine Beleuchtung bereitgestellt. Stattdessen werden die Navigationsinformationen unter Verwendung von Hintergrundlicht, d. h. Licht aus der Umgebung, angesammelt.

Bei wiederum einer weiteren Alternative wird kohärente Beleuchtung mit Normaleinfall eingeführt, um eine Navigation auf Fleckenbasis zu erlauben. Eine relative Bewegung zwischen einer Abtastvorrichtung und einem Original könnte durch Überwachen einer Fleckenbewegung relativ zu den Navigationssensoren verfolgt werden. Wenn kohärente Beleuchtung verwendet wird, ohne Bilderzeugungsoptiken zu verwenden, sind durch Auswählen einer kleinen Beleuchtungsfläche und dadurch, dass ein relativ großer Abstand zwischen der Oberfläche des Originals und dem Photodetektorarray des Navigationssensors 24 eingerichtet wird, die resultierenden vorherrschenden Fleckenzellengrößen mit kohärenter Beleuchtung ausreichend groß, um das Nyquist-Abtastkriterium zu erfüllen. Die Verwendung eines Strahlteilers erlaubt es, dass die Richtung von sowohl der Einfallsbeleuchtung als auch der erfassten Streuung nahe einer Normalen zu der Oberfläche des Originals sein kann, ähnlich wie in 4 erzielt wird.

Unter Bezugnahme auf 6 ist der Scanner 10 als über ein Original 44 mit einem Block 46, der auf eine Oberfläche des Originals aufgedruckt ist, bewegt gezeigt. Da der Scanner 10 keinen kinematischen Beschränkungen in der Ebene des Originals unterworfen ist, besteht eine Tendenz, dass ein Benutzer einem krummlinigen Weg über das Original folgt, wie wenn die Hand und der Unterarm des Benutzers sich um den Ellenbogen drehen. In 6 ist die Abtastvorrichtung als einem gekrümmten Weg 48 über den Block 46 folgend gezeigt. Wenn die untere Kante der Abtastvorrichtung die Kante ist, die näher an dem Ellenbogen ist, der die Drehachse definiert, besitzt die untere Kante einen kürzeren Radius. Folglich variieren Bilderzeugungselemente eines Bilderzeugungssensors in Bezug auf die Zeit und Entfernung, die für ein Laufen über den Block 46 erforderlich sind. Ein verzerrtes Bild 50 des Blocks wird erfasst, wenn die Vorrichtung in die zweite Position 52 bewegt wird, wie in gestrichelten Linien gezeigt ist.

Das erfasste Bild 50 wäre ohne Verarbeitung das gespeicherte Bild, was unten beschrieben ist. Wenn jedoch der Bilderzeugungssensor Daten in Bezug auf den Block 46 erfasst, werden Navigationsinformationen erfasst. Bei dem beschriebenen Ausführungsbeispiel erfassen einer oder mehrere Navigationssensoren Daten in Bezug auf inhärente Strukturmerkmale des Originals 44. Eine Bewegung der inhärenten Strukturmerkmale relativ zu der Abtastvorrichtung 10 wird verfolgt, um eine Verschiebung des Bilderzeugungssensors relativ zu dem Block 46 zu bestimmen – entsprechend werden sowohl Sensordaten als auch Sensorpositionsdetektordaten erfasst, aus denen dann, wenn sie zusammen verwendet werden, ein getreues erfasstes Bild 54 gebildet werden kann. Das Bild 54 ist hierin als das „gleichgerichtete" Bild definiert. Der Vorgang der Gleichrichtung, auf den sich das Verfahren gemäß der Erfindung bezieht, ist weiter unten im Detail erläutert.

In 7 ist ein Ausführungsbeispiel einer Navigationsverarbeitung gezeigt. Die Navigationsverarbeitung wird durch ein Korrelieren aufeinander folgender Rahmen von Navigationsinformationen, wie z. B. Daten hinsichtlich inhärenter Strukturmerkmale, durchgeführt. Die Korrelationen vergleichen die Positionen der inhärenten Strukturmerkmale in aufeinander folgenden Rahmen, um Informationen hinsichtlich der Position eines Navigationssensors zu einer bestimmten Zeit bereitzustellen. Die Navigationsinformationen werden dann zum Gleichrichten von Bilddaten verwendet. Die Verarbeitung aus 7 wird typischerweise für jeden Navigationssensor durchgeführt.

Bei einem ersten Schritt 56 wird ein Referenzrahmen erfasst. Tatsächlich ist der Referenzrahmen eine Ausgangsposition. Die Position eines Navigationssensors zu einer späteren Zeit könnte durch Erfassen 58 eines Proberahmens von Positionsdaten von dem Navigationssensor zu der späteren Zeit und ein darauf folgendes Berechnen von Korrelationen 60 zwischen dem Referenzrahmen und dem später erfassten Proberahmen bestimmt werden.

Die Erfassung des anfänglichen Referenzrahmens 56 könnte auf eine Einleitung des Bilderzeugungsvorgangs hin stattfinden. Die Erfassung könnte z. B. durch eine bloße Platzierung der Abtastvorrichtung in Kontakt mit dem Original ausgelöst werden. Alternativ könnte die Abtastvorrichtung einen Startknopf umfassen, der den Bildvorgang und den Navigationsvorgang einleitet. Eine Einleitung könnte außerdem durch ein periodisches Pulsieren des Beleuchtungssystems jedes Navigators stattfinden. Wenn ein reflektiertes Signal vorliegt, das eine vorgeschriebene Reflexionsschwelle anzeigt, oder ein Korrelationssignal, das eine Bewegung anzeigt, wird der Referenzrahmen erfasst.

Obwohl die Navigationsverarbeitung rechenmäßig durchgeführt wird, können die Konzepte dieses Ausführungsbeispiels unter Bezugnahme auf die 7 und 8 beschrieben werden. Ein Referenzrahmen 62 ist als ein Bild eines T-förmigen inhärenten Strukturmerkmals 64 aufweisend gezeigt. Die Größe des Referenzrahmens hängt von Faktoren ab, wie z. B. der maximalen Abtastgeschwindigkeit der Abtastvorrichtung, den dominanten Raumfrequenzen bei der Bilderzeugung der Strukturmerkmale und der Bildauflösung des Sensors. Eine praktische Größe des Referenzrahmens für einen Navigationssensor, der 32 Pixel (N) mal 64 Pixel (M) beträgt, ist 24 × 56 Pixel.

Zu einer späteren Zeit (dt) erfasst ein Navigationssensor einen Proberahmen 66, der in Bezug auf einen Rahmen 62 verschoben ist, der 'jedoch im Wesentlichen die gleichen inhärenten Strukturmerkmale zeigt. Die Dauer dt ist vorzugsweise derart eingestellt, dass die relative Verschiebung des T-förmigen Merkmals 64 kleiner als ein Pixel des Navigationssensors bei der Geschwindigkeit einer Translation der Abtastvorrichtung ist. Ein akzeptabler Zeitraum beträgt 50 &mgr;s für Geschwindigkeiten von 0,45 m/sek bei 600 dpi. Diese relative Verschiebung wird hierin als ein „Mikroschritt" bezeichnet.

Wenn sich die Abtastvorrichtung während des Zeitraums zwischen der Erfassung 56 des Referenzrahmens 62 und der Erfassung 58 des Proberahmens 66 bewegt hat, sind das erste und das zweite Bild des T-förmigen Merkmals diejenigen, bei denen sich das Merkmal verschoben hat. Während das bevorzugte Ausführungsbeispiel eines ist, bei dem dt kleiner ist als die Zeit, die eine Vollpixelbewegung ermöglicht, ist die schematische Darstellung von 8 eine, in der das Merkmal 64 sich um ein Pixel nach oben und rechts verschieben darf. Die Vollpixelverschiebung wird hier nur angenommen, um die Darstellung zu vereinfachen.

Ein Element 70 in 8 stellt eine sequentielle Verschiebung der Pixelwerte des Rahmens 68 in die acht Nächster-Nachbar-Pixel dar. Dies bedeutet, dass Schritt "0" keine Verschiebung umfasst, Schritt „1" eine Diagonalverschiebung nach oben und links ist, Schritt „2" eine Aufwärtsverschiebung ist, usw. Auf diese Weise können die pixelverschobenen Rahmen mit dem Proberahmen 66 kombiniert werden, um das Array 72 von Positionsrahmen zu erzeugen. Der Positionsrahmen, der als „Position 0" bezeichnet ist, umfasst keine Verschiebung, so dass das Ergebnis lediglich eine Kombination der Rahmen 66 und 68 ist. „Position 3" besitzt die minimale Anzahl schattierter Pixel und ist deshalb der Rahmen mit der größten Korrelation. Basierend auf den Korrelationsergebnissen wird die Position. des T-förmigen Merkmals 64 in dem Proberahmen 66 als eine Verschiebung diagonal nach rechts und oben relativ zu der Position des gleichen Merkmals in dem früher erfassten Referenzrahmen 62 bestimmt, was impliziert, dass die Abtastvorrichtung sich während der Zeit dt nach links und nach unten bewegt hat.

Während andere Korrelationsansätze eingesetzt werden könnten, ist ein annehmbarer Ansatz eine „Summe quadrierter Differenzen"-Korrelation. Für das Ausführungsbeispiel aus

8 gibt es neun Korrelationskoeffizienten (Ck = C0, C1, ... C8), die aus den neun Versätzen bei dem Element 70 gebildet sind, wobei die Korrelationskoeffizienten durch folgende Gleichung bestimmt sind: Ck = &Sgr;i&Sgr;j (Sij – R(ij)+k) wobei Sij den durch den Navigationssensor gemessenen Wert an der Position ij des Proberahmens 66 bezeichnet und Rij den durch den Navigationssensor gemessenen Wert an dem Rahmen 68, verschoben an dem Element 79 in der k-Richtung bezeichnet, wobei k der Identifizierer der Verschiebung an dem Element 70 ist. In 8 liefert k = 3 den Korrelationskoeffizienten mit dem geringsten Wert.

Korrelationen werden verwendet, um die Orte identischer Merkmale in aufeinander folgenden Rahmen zu finden, um die Verschiebungen der Merkmale von Rahmen zu Rahmen zu bestimmen. Ein Summieren oder Integrieren dieser Platzierungen und Korrigieren von Skalierfaktoren, die durch den Entwurf der relevanten Optiken eingeführt werden, bestimmen die Verschiebungen des Bilderzeugungssensors mit fortschreitender Abtastprozedur.

Wie zuvor angemerkt wurde, werden Rahmen-zu-Rahmen-Korrelationen als „Mikroschritte" bezeichnet, da Rahmenraten ausreichend hoch ausgewählt werden, um sicherzustellen, dass die Verschiebungen die Abmessungen eines einzelnen Pixels nicht überschreiten. Ein Überabtasten kann eine Teilpixelverschiebungsgenauigkeit liefern. Unter Bezugnahme auf 7 wird eine Bestimmung 74 dessen, ob ein Mikroschritt durchgeführt werden soll, nach jeder Berechnung 64 der Korrelationen durchgeführt. Wenn ein Mikroschritt erforderlich ist, wird der Referenzrahmen bei 76 verschoben. Bei diesem Schritt wird der Proberahmen 66 aus 8 der Referenzrahmen und ein neuer Proberahmen wird erfasst. Die Korrelationsberechnung wird dann wiederholt.

Während der Vorgang einen hohen Grad an Korrelationsübereinstimmung bereitstellt, sammeln sich Fehler, die auftreten, mit jeder aufeinander folgenden Verschiebung 76 eines Proberahmens 66 zu der Referenzrahmenbezeichnung an. Um eine Beschränkung für die Wachstumsrate dieses „Zufallsbewegung"-Fehlers zu platzieren, wird ein Proberahmen in einem separaten Pufferspeicher gespeichert. Dieser separat gespeicherte Proberahmen wird ein neuer Referenzrahmen für eine nachfolgende Serie von Korrelationsberechnungen. Die letztere Korrelation wird als ein „Makroschritt" bezeichnet.

Durch die Verwendung von Makroschritten kann eine genauere Bestimmung einer Scannerverschiebung über eine Entfernung von m Bildrahmenverschiebungen, d. h. m Mikroschritten, erhalten werden. Der Fehler bei einem Makroschritt ist ein Ergebnis einer einzelnen Korrelationsberechnung, während der äquivalente Fehler von m Mikroschritten m1/2 mal der Fehler in einem einzelnen Mikroschritt ist. Obwohl der Durchschnitt von Fehlern in m Mikroschritten sich mit ansteigendem m Null annähert, wächst die Standardabweichung in dem Durchschnitt von Fehlern als m1/2. So ist es von Vorteil, die Standardabweichung eines angesammelten Fehlers zu reduzieren, indem Makroschritte verwendet werden, bei denen m so groß ist, wie dies praktisch ist, solange die beiden Rahmen, die einen Makroschritt definieren, nicht so weit voneinander beabstandet sind, dass sie keine signifikante Region eines gemeinsamen Bildinhalts besitzen.

Die Abtastperiode dt muss nicht konstant sein. Die Abtastperiode könnte als eine Funktion vorheriger Messungen bestimmt werden. Ein Verfahren, dass eine Variable dt verwendet, besteht darin, die Genauigkeit einer Verschiebungsberechnung zu verbessern, indem die relative Verschiebung zwischen aufeinander folgenden Referenzrahmen innerhalb bestimmter Abgrenzungen gehalten wird. Die obere Begrenzung könnte z. B. eine Einpixelverschiebung sein, während die untere Begrenzung durch numerische Rundungsbetrachtungen bei der Verarbeitung der Navigationsdaten bestimmt wird.

Bezug nehmend auf 9a könnte das Bildsignal, das an dem Bilderzeugungssensor 22 erzeugt wird, dann basierend auf den Navigationsdaten mit einem Positionsetikett versehen werden. Bei einem Ausführungsbeispiel werden Pixelwerte von den Navigationssensoren 24 und 26 durch einen Navigationsprozessor 80 zur Durchführung der Operationen der 7 und 8 empfangen. Basierend auf den berechneten Korrelationen werden Koordinaten für die gegenwärtige Position des ersten Navigationssensors 24 und des zweiten Navigationssensors 26 bestimmt.

Innerhalb eines Makroschritts gewinnt der Navigationsprozessor 80 direkt die Translationskomponente der Bewegung jedes Navigationssensors wieder. Die Daten von beiden Navigationssensoren müssen integriert werden, um eine absolute Positionsschätzung zu erhalten, die auch eine mögliche Drehung des Abtastkopfes berücksichtigt. Der Prozessor 80 behält ein Modell der gegenwärtigen Ausrichtung des Abtastkopfs in Bezug auf seine ursprüngliche Ausrichtung bei. Die einzelnen Schätzwerte der Translation jedes Navigationssensors werden in Bezug auf dieses Modell interpretiert. Die Ausrichtung des Scannermodells wiederum wird selbst periodisch aktualisiert.

Bei einem Ausführungsbeispiel werden die Makroschritte jedes Navigationssensors synchronisiert, so dass, wenn der Navigationssensorprozessor 80 einen Makroschritt bei einem Navigationssensor erfordert, er auch einen Makroschritt in dem anderen auslöst. Dies vereinfacht die Interpretation der Translationen, die durch jeden Navigationssensor aufgezeichnet werden. Wenn bei einem Makroschritt T die Ausrichtung des Scanners &thgr; Grad von einer Vertikalen ist, wird die aufgezeichnete Translation innerhalb des Mikroschritts jedes Navigationssensors wie folgt interpretiert.

9b zeigt die Bewegung der Navigationssensoren als ein Paar. Für jedes haben wir Translationen in Bezug auf einen Koordinatenrahmen aufgezeichnet (mit Einheitsvektoren, die u und v bezeichnet sind), der eine Ausrichtung des Scanners beschreibt. Diese besitzen Beträge (u1, v1) und (u2, v2) für den ersten bzw. zweiten Navigationssensor. Das Ziel besteht darin, diese Translationen zu interpretieren, um die aktualisierten Orte der Navigationssensoren in Bezug auf den globalen Koordinatenrahmen zu ergeben. Im Grunde rekonstruieren wir den Weg von einer stückweisen linearen Annäherung desselben, wo der Betrag der linearen Abschnitte durch die Größe des Makroschritts bestimmt wird.

Jeder Einheitsvektor ist gemäß den folgenden standardmäßigen trigonometrischen Beziehungen auf die Ausrichtung des Scanners &thgr; bezogen: v = (sin &thgr;, cos &thgr;) u = (cos &thgr;, –sin &thgr;) wobei, wie zu sehen ist, Schätzwerte von u und v ohne rechenmäßig aufwändige trigonometrische Berechnung beibehalten werden können.

In 9b stellen P1 und P2 die Navigationssensororte hinsichtlich des globalen Rahmens zu Beginn des Makroschritts dar; sie besitzen Werte (x1, y1) bzw. (x2, y2). Die aktualisierten Orte hinsichtlich des gleichen globalen Rahmens einige Navigationssensorrahmen später sind gegeben durch P1' und P2', die Werte (x1', y1') bzw. (x2', y2') aufweisen.

Bei der Grenze (von der wir annehmen, dass wir nahe an derselben sind, um eine genaue Integration durchzuführen) muss die v-Komponente einer Translation jedes Navigationssensors die gleiche sein (Scheren beeinflusst jedes Ende gleichermaßen und bei der Grenze induziert eine Drehung überhaupt keine v-Komponente). So können wir v1 und v2 auf ihren Mittelwert setzen: v = (v1 + v2)/2 In diesem Fall sind die aktualisierten Endpunktorte gegeben durch: P1' = P1 + u1u + vv und P2' = P2 + u2u + vv

Es ist ebenso an diesem Punkt praktisch, die Positionsschätzwerte für eine Entsprechung mit den physischen Endpunkten des Bildsensors und nicht die einzelnen Navigationssensoren zu verschieben. Dies wird unter Verwendung von Kalibrierungsdaten durchgeführt, die die physischen Orte der Navigations- und Bildsensoren aufeinander beziehen. Zur Einfachheit sind die Endpunktpositionen in Entsprechung zu den Mitten des ersten und letzten Sensorelements des Bildsensors gemacht.

Wir müssen das Inertialsystem periodisch aktualisieren. Dies sollte nur an dem Ende eines Makrorahmens oder zu Beginn des nächsten stattfinden. Dies macht es erforderlich, dass die Makroschritte synchronisiert sind: d. h., wenn ein Navigationssensor einen neuen Makroschritt auslöst, da er die maximale Anzahl von Mikroschritten überschritten hat, sollte ein Makroschritt auch in dem anderen Navigationssensor ausgelöst werden, selbst dann, wenn er durchgehend feststehend geblieben ist. Dieser Ansatz hat den zusätzlichen Vorteil, dass die Drehung des Navigationsrahmens immer klein ist, da die maximale erfahrene Drehung immer kleiner sein muss als die maximale Anzahl von Mikroschritten, geteilt durch die Basislinie zwischen Navigationssensoren.

Ein Aktualisieren des Inertialsystems hat die Wirkung eines Zurückaddierens der verlorenen Drehkomponente der Bewegung des Scanners. Dies wird implizit aus den Differenztranslationen, die die einzelnen Navigationssensoren erfahren, bestimmt. Anstelle eines expliziten Berechnens der Drehkomponente der Bewegung wird das inerte Koordinatensystem direkt aus seiner Beziehung zu der Hauptachse des Scanners aktualisiert (der Linie, die die Navigationssensororte verbindet). Die &ngr;-Achse des Inertialsystems ist ein Einheitsvektor entlang der Hauptachse, die von dem Navigationssensor 1 zu dem Navigationssensor 2 läuft, und die u-Achse ist der Einheitsvektor orthogonal zu derselben, die die 2D-Basis vervollständigt.

Der aktualisierte Wert für &ngr; ist gegeben durch: &ngr;' = (v'x, v'y) = (P2' – P1')/|P2' – P1'| = (P2' – P1') /D und der Orthogonalvektor u durch: u' = (v'y, –v'x)

Die Länge |P2' – P1'| ist die konstante (Modulo-Navigationsfehler-) Länge des Scanners, in 9b mit D bezeichnet. Dies vereinfacht die Berechnung des Inertialsystems stark, da es den Bedarf nach einer Berechnung der Quadratwurzel der Summe von Quadraten für jeden Makroschritt vermeidet.

Der Navigationsprozessor 80 empfängt außerdem N Pixelwerte des Bilderzeugungssensors 22 über einen Pixelverstärker 82 und einen Analog-Digital-Wandler 84. Obwohl 9 nur einen einzelnen Abgriff von dem Bildsensor 22 und einen einzelnen A/D-Wandler 84 zeigt, sind mehrere Abgriffe, jeweils mit einem A/D-Wandler, innerhalb des Schutzbereichs der Erfindung. Die Koordinaten der gegenwärtigen Position sind an den Enden einer Zeile von Daten, die der Anzahl von Pixeln innerhalb des Bilderzeugungssensors entspricht, mit einem „Etikett" versehen. Die Ausgabe 86 des Navigationsprozessors 80 ist deshalb ein mit einem Positionsetikett versehener Datenstrom.

Der Navigationsprozessor 80 muss nicht notwendigerweise Pixeldaten von dem Bilderzeugungssensor 22 und Positionsinformationen von den Navigationssensoren 22, 24 mit der gleichen Rahmenrate empfangen. Der Strom von Positionsdaten könnte verwendet werden, um den Schätzwert des Orts der Endpunkte des Linearsensors zu aktualisieren, der allgemein bei einer höheren räumlichen Auflösung ist als die Pixelteilung des Linearsensorarrays. Die optimale Taktungsfrequenz des Linearbildsensors ist allgemein durch die Rate einer Bewegung des Scanners bestimmt, damit das sich am schnellsten bewegende Ende mit einer Menge abgetastet wird, die gerade kleiner ist als die Pixelteilung des Linearsensors selbst – andernfalls resultiert entweder ein Überabtasten oder Unterabtasten. Ein Überabtasten führt zu erhöhten Rechen- und Datenverarbeitungsanforderungen weiter an der Bildverarbeitungspipeline entlang, mit weniger oder keiner Verbesserung der Bildqualität, während ein Unterabtasten zu einer deutlichen Reduzierung der Bildqualität führt.

Eine Lösung besteht darin, den Linearsensor mit einer festen Frequenz abzutasten, die immer zu einer Überabtastung führen würde, d. h., sie würde die Abtastanforderungen der schnellstmöglichen Abtastgeschwindigkeit übersteigen. Dann werden, wenn sich der Scanner langsamer als mit der maximalen Abtastgeschwindigkeit bewegt, unerwünschte Abtastwerte durch den Navigationsprozessor auf der Basis der gegenwärtigen Endpunktpositionsschätzwerte verworfen. Dies bedeutet, dass der Betrag der relativen Position jedes Endpunkts seit der letzten Zeit, zu der ein gültiges Inkrement von Linearsensorabtastwerten und mit Etiketten versehenen Positionsdaten aus dem Navigationsprozessor 80 ausgegeben wurde, verwendet wird, um die Ausgabe weiterer Inkremente gattermäßig zu steuern. Der einfachste Ansatz besteht darin, nur eine Ausgabe zu erlauben, wenn ein oder ein anderer Betrag strikt gleich der Pixelteilung ist oder dieselbe übersteigt (oder einen wesentlichen Bruchteil derselben). Dieser Ansatz resultiert wahrscheinlich in einer Unterabtastung, insbesondere dann, wenn ein Abtasten mit etwas weniger als der maximalen Abtastgeschwindigkeit stattfindet. Alternativ könnte, um ein Unterabtasten zu verhindern, der gegenwärtige Abtastwert ausgegeben werden, wenn eine Vorhersage der relativen Endpunktpositionen des nächsten Linearsensorabtastwertes die Pixelteilung übersteigt, wobei die Vorhersage auf der Rate einer Veränderung (oder numerischen Ableitungen höherer Ordnung) der Endpunktposition basiert. Ein dritter Ansatz, der ebenso ein Unterabtasten verhindert, besteht darin, einen Inkrementpuffer in den Navigationsprozessor 80 einzuführen, so dass das vorherige Inkrement übertragen werden kann, wenn die relativen Positionsdaten des gegenwärtigen Inkrements die Pixelteilung übersteigen.

Jede der obigen Abtaststrategien basiert auf einem synchronen Abtasten und führt allgemein zu einem bestimmten Grad an Über- oder Unterabtastung. Eine bessere Gesamtlösung, die eine ideale Raumabtastung besser erzielt, besteht darin, dass der Navigationsprozessor 80 die Linearsensorerfassung asynchron auslöst. Ein Ansatz ist der, dass die relative Endpunktposition seit der letzten gültigen Erfassung (oder einer zukünftigen Vorhersage derselben) direkt verwendet wird, um den besten Zeitpunkt zum Auslösen der Erfassung und Abtastung des Linearsensors zu identifizieren.

In 10a ist ein Inkrement 88 des Datenstroms als Positionskoordinatenzellen 90, 92, 94 und 96 an den gegenüber liegenden Enden von N Pixelzellen aufweisend gezeigt, obwohl diese Reihenfolge nicht notwendig ist.

Der Bilderzeugungssensor 22 wird getaktet, wenn sich die Abtastvorrichtung über ein Original bewegt. Wie oben erläutert wurde, stellt die Taktung sicher, dass das sich am schnellsten bewegende Element des Sensors zumindest einmal pro Pixelverschiebung abtastet.

Der mit einem Positionsetikett versehene Datenstrom an dem Ausgang 86 des Navigationsprozessors 80 wird gepuffert, wie in 10b gezeigt ist. Ein Puffer B hält eine Vielzahl der Inkremente 88 aus 10a. Der Puffer B könnte verwendet werden, um eine gesamte Abtastung unterzubringen, wobei in diesem Fall eine Datenkomprimierung eingesetzt werden könnte. Diese Daten werden dann auf geradlinige Koordinaten abgebildet, um ein letztendliches gleichgerichtetes rekonstruiertes Bild gemäß einem Verfahren gemäß der Erfindung zu erzeugen, wie nun beschrieben werden wird.

11 zeigt das Koordinatensystem, das durch den Geradliniges-Bild-Puffer 100, Höhe H Pixel mal Breite W Pixel, bereitgestellt wird, in das der Strom von Inkrementen 88 abgebildet wird, um das letztendliche geradlinige Bild zu erzeugen. Ein einfaches zweidimensionales Array eines geeigneten Datentyps (hier 8-Bit-Grauskala; könnte jedoch gleichermaßen 24-Bit-Farbe oder 1-Bit-Binär sein) reicht als eine Darstellung für das geradlinige Bild aus. Die X- und Y-Koordinaten der Positionsetiketten, die jedem Inkrement zugeordnet sind, entsprechen der horizontalen und vertikalen Abmessung (Spalten- und Zeilenindex) des geradlinigen Bildraums. Ebenso gezeigt sind die Orte von Positionsetiketten (in der Ausschnittansicht für einen kurzen Abschnitt rechts vergrößert gezeigt) für jeden Endpunkt des Linearbildsensors, der einem Strom von Inkrementen zugeordnet ist. Innerhalb derselben ist ein Paar von Inkrementen (Inkrement #1 und Inkrement #2) hervorgehoben, indem deren Positionsetiketten mit geraden Linien verbunden sind. Diese sind als sich in der Überlappungsregion fast schneidend ausgewählt, wo die Abtastung an sich selbst kehrt macht.

Es ist möglich, dass die Auflösung des Geradliniges-Bild-Puffers, die durch die Ausgangsauflösung bestimmt wird, die von dem Scanner benötigt wird (typischerweise entweder 200 oder 300 dpi), sich von derjenigen unterschiedet, in der die Endpunktpositionsdaten gemessen werden. Dies wiederum wird durch die Auflösung der Navigationssensoren 24 bestimmt (die von der räumlichen Erstreckung der Merkmale z. B. Papierfasern, die während der Navigation abgebildet werden, abhängt). Zum Unterbringen derartiger Unterschiede ist es notwendig, dass die Endpunktpositionsdaten auf die Ausgangspixelauflösung skaliert werden.

Die nächste Operation besteht darin, die mit den Positionsetiketten versehenen Bildinkremente innerhalb eines Bandes in den Geradliniges-Bild-Puffer 100 abzubilden. Es ist besonders wichtig, dass eine ausreichende Bildqualität bei diesem Vorgang beibehalten wird. Ein Ansatz besteht einfach darin, die Elemente innerhalb jedes Inkrements auf die Pixel des Geradliniges-Bild-Arrays abzubilden, durch die die gerade Linie, die zwischen den Endpunktorten gezogen wird, läuft. Die Abbildung könnte entweder zu dem nächsten Linearsensorelement für jedes Bildpixel sein oder eine Interpolation zwischen Sensorelementen beinhalten. Geeignete lineare oder kubische Interpolationsverfahren zur Anwendung in diesem Kontext sind beschrieben in Wolberg, "Digital Image Warping", S. 127–131, IEEE Computer Society Press, Los Alamitos, CA, 1992.

Ein derartiges Durchführen einer Gleichrichtung führt unvermeidlich Abtastartefakte ein, da jedes Inkrement eine unterschiedliche Auswirkung besitzt. Ferner ist es in der Praxis nötig, dass das ursprüngliche Band von mit Positionsetiketten versehenen Bilddaten streng in Bezug auf das Geradliniges-Pixel-Gitter überabgetastet wird (was aus Bequemlichkeit mit einer höheren räumlichen Auflösung als der Pixelteilung des Linearsensors selbst sein könnte), andernfalls tritt ein Pixelausfall in dem geradlinigen Bild auf. Diese Probleme werden bei Ausführungsbeispielen des Verfahrens gemäß der Erfindung gelöst.

Eine Lösung, die durch die Erfindung bereitgestellt wird, ist in 18 dargestellt. In dieser Figur definieren die Endpunktpositionen eines Paars von Inkrementen I1 und I2 eine Region. Diese Inkremente können ein aufeinander folgendes Paar von Linearsensorablesewerten sein – die Verwendung aufeinander folgender Ablesewerte wird hier als PAARWEISE-Ansatz bezeichnet. Alternativ können die Inkremente I1 und I2 das Bindungspaar einer größeren Gruppe von Sensorinkrementen sein – die Verwendung derartiger Inkremente wird hier als BROCKENWEISE-Ansatz bezeichnet. Es wird gezeigt, dass ein Rechenvorteil bei dem BROCKENWEISE-Ansatz aus der Behandlung einer Gruppe von Inkrementen im Gleichklang auf Kosten einer kleinen Reduzierung der Bildqualität verglichen mit dem PAARWEISE-Ansatz gewonnen werden kann.

Pixelorte in dem geradlinigen Array sind Ganzzahlorten zugeordnet. Für jedes derartige Pixel innerhalb der Region, die durch ein Paar von Inkrementen definiert ist, wird dann ein Intensitätswert durch Integrieren einer Anzahl von Linearsensorpixeln, die auf eine Region um denselben abbilden, berechnet. Bei besonders bevorzugten Ausführungsbeispielen werden verschiedene Formen einer bilinearen Interpolation verwendet, um spezifische vier Linearsensorpixel zu integrieren, die aus dem Paar aufeinander folgender Inkremente genommen sind, die den Pixelort überspannen: zwei Sensorpixel aus dem Inkrement, das auf eine Linie abbildet, die auf einer Seite des Geradliniges-Array-Pixels liegt, und zwei weitere Sensorpixel aus dem benachbarten Inkrement, das auf eine Linie auf der gegenüberliegenden Seite des Geradliniges-Array-Pixels abbildet.

In 18 ist ein Paar von Inkrementen I1 und I2 als in einen Abschnitt des geradlinigen Arrays abgebildet gezeigt, der das abgetastete Bild definiert. Zur Einfachheit sind Endpunktpositionen P1, P2 und P1', P2' in Entsprechung zu der Mitte des ersten und letzten Sensorelements der Inkremente I1 bzw. 12 gemacht. Zwischensensorelemente, wie z. B. A1, A2 und B1, B2, sind ebenso gezeigt. Pixelorte in dem Geradliniges-Bild-Array sind ausgewählt, um Ganzzahlorten hinsichtlich der Endpunktpositionsgeometrie zu entsprechen. Die Auflösung des geradlinigen Ausgangsbilds ist unter Umständen nicht die gleiche wie diejenige des Linearbildsensors. Unabhängig von der tatsächlichen Auflösung jedoch bilden N Sensorpixel entlang der Linie ab, die die Endpunkte jedes Inkrements verbindet. Für eine leichtere Erläuterung gilt in 18 N = 8, d. h. jeder Linearsensor hat nur acht Elemente in sich und die Länge jedes Inkrements beträgt N – 1 = 7 mal die Pixelteilung des Linearsensors, gemessen in geradlinigen Ausgangspixelauflösungseinheiten.

Spezifische Pixel, die innerhalb der Region liegen, die durch ein Begrenzungspaar von Inkrementen definiert ist, können aus dem Intervall identifiziert werden, das durch die x-Komponenten der Schnittpunkte jeder Zeile des geradlinigen Bilds mit den beiden Inkrementen gegeben ist. Ein Beispiel ist durch Pixel C1 und C2 auf einer Zeile D des geradlinigen Bilds in 18 vorgesehen. Aus einer einfachen Geometrie ist, wenn das Inkrement I1 Endpunktkoordinaten (x1, y1) und (x2, y2) aufweist, die x-Koordinate seines Schnittpunktes mit der Zeile D, die einen Ganzzahlwert yD aufweist, gegeben durch: xD = (yD – y1)·(x2 – x1)/(y2 – y1) daraus folgt, dass der Schnittpunkt mit einer Zeile D + 1 gegeben ist durch: x(D + 1) = xD + (x2 – x1)/(y2 – y1) = xD + xInc wobei xInc ein konstantes Inkrement für jede aufeinander folgende Zeile ist. Ähnlich ist, wenn das Inkrement I2 Endpunktkoordinaten (x1', y1') und (x2', y2') aufweist, die x-Koordinate ihres Schnittpunkts mit der Zeile D, die einen Ganzzahlwert yD aufweist, gegeben durch: xD' = (yD – y1')·(x2' – x1')/(y2' – y1') daraus folgt, dass für den Schnittpunkt der Zeile D + 1 folgendes gilt: x(D + 1)' = xD' + (x2' – x1')/(y2' – y1') = xD' + xInc'

Dies schafft eine berechnungsmäßig wirksame Weise zur Berechnung des Bereichs eines Schnittpunkts für jede Zeile der Reihe nach. Die Schnittpunkte mit der gegenwärtigen Zeile werden durch einfaches Inkrementieren der Schnittpunkte mit der vorherigen Zeile berechnet.

Zuerst müssen wir den Bereich von Zeilen, die innerhalb der Region liegen, spezifizieren. Dies ist gegeben durch den Bereich von Ganzzahl-y-Werten, die beiden Inkrementen gemein sind. Dies sind die Ganzzahlwerte in dem Bereich: [Ceiling (Max (y1, y1')), Floor (Min (y2, y2'))] = [Y1, Y2], unter der Annahme, dass die Ausrichtung des Scanners in Bezug auf das Papier grob vertikal bleibt. Dieser Ansatz kann ohne Weiteres erweitert werden, um es zu ermöglichen, dass der Scanner in einer willkürlichen Ausrichtung in Bezug auf die Seite ist. Wenn z. B. der Scanner umgedreht ist, können die Linearsensordaten umgekehrt werden und die Polarität der Endpunktpositionsdaten umgekehrt werden. Ferner kann, wenn der Winkel des Scanners mehr als 45 Grad von einer Vertikalen ist, eine korrekte Gleichrichtung durch Umdrehen der Polarität von sowohl den x/y-Position-Koordinaten als auch den Zeilen und Spalten des Bilds erzielt werden. Für eine leichtere Erläuterung beschäftigt sich die Erläuterung der Ausführungsbeispiele nur mit dem grob vertikalen Fall, eine Erweiterung auf die oben angezeigten allgemeineren Fälle jedoch ist für einen Fachmann auf dem Gebiet eine einfache Angelegenheit.

Die aktiven Pixel in der Region wiederum können unter Verwendung des folgenden Pseudocodes identifiziert werden:

TRANSFORMATIONSSCHLEIFE 1
wobei die Operatoren floor bzw. Boden und ceiling bzw. Decke ihre üblichen mathematischen Interpretationen besitzen. Die tatsächlichen Details der Initialisierung und der inneren Schleife sind spezifisch für die unten beschriebenen unterschiedlichen Verfahren. Für eine erleichterte Darstellung in den gezeigten Ausführungsbeispielen der TRANSFORMATIONSSCHLEIFE wird angenommen, dass xD immer kleiner ist als xD'. Es ist einfach, dies auf den generischen Fall zu erweitern, indem die Ordnung von xD und xD' bei jeder Zeile getestet wird.

Der nächste Schritt besteht darin zu bestimmen, welche Linearsensorpixel einen Beitrag zu jedem Geradliniges-Gitter-Pixel leisten, und in welchen Anteilen. Ein erstes Ausführungsbeispiel des PAARWEISE-Ansatzes wird nun beschrieben.

Bei diesem Ausführungsbeispiel des PAARWEISE-Ansatzes für das Verfahren gemäß der Erfindung basiert eine Gleichrichtung auf einer Umkehrabbildung, wie in einer Computergraphiktexturabbildung eingesetzt wird (siehe z. B. Wolberg, auf den oben bei Seite 188 Bezug genommen wird), wodurch jedes Pixel in dem Intervall, das durch die beiden Linien abgegrenzt ist, die die Endpunktpositionen der Inkremente I1 und I2 verbinden, zurück in einen Teilpixelort innerhalb eines Koordinatenraumes abgebildet wird, der zwischen dem Paar von Inkrementen selbst definiert ist. Diese Situation ist in 19 dargestellt, in der das Paar von Inkrementen I1 und I2, die in das geradlinige Bild in 18 abgebildet gezeigt sind, auch einen einfachen Inkrementraum definiert, in dem Einheiten eine Linearsensorpixelbeabstandung sind, die Inkremente mit der y-Achse ausgerichtet sind und die Inkremente um ein Einheitspixel voneinander entfernt platziert sind. Innerhalb dieses Raums besitzt das obere Sensorelement des linken Inkrements Koordinaten (0, 0).

Das Pixel C1 aus dem geradlinigen Array ist zwischen die Inkremente I1 und I2 abgebildet gezeigt. Es besitzt Teilpixelkoordinaten (x, Y. y), wobei Y die Ganzzahlkomponente der Koordinate entlang des Inkrements ist und x und y der Teilpixelversatz sind. Ein repräsentativer Pixelwert kann dann unter Verwendung einer bilinearen Interpolation der vier umgebenden Pixel bestimmt werden. Dies bedeutet: BiLinear (I1, I2, Y, y, x) = I1[Y]·(1 – x)·(1 – y) + I2[Y]·(1 – y)·x + I1[Y + 1]·(1 – x)*y + I2 [Y + 1]·x·y

Die beste Annäherung an die Transformation von dem geradlinigen Bild zu dem Raum zwischen Inkrementen beinhaltet die Lösung einer quadratischen Gleichung für jedes Pixel. Dies ist aufgrund des beinhalteten Rechenaufwands keine zufrieden stellende praktische Lösung.

Während es möglich ist, ungefähre lineare homogene Abbildungen von Koordinaten eines geradlinigen Bildes zu dem Koordinatenraum, der durch ein Paar von Inkrementen definiert ist, abzuleiten, ist eine nichthomogene Lösung vorzuziehen. Mit einer derartigen nichthomogenen Lösung sind keine Annahmen über die Natur der lokalen Transformation erforderlich. Es ist außerdem möglich, ohne Weiteres nach Eckfällen zu lösen, wie Z. B., wenn die Projektion eines benachbarten Paars von Inkrementen ein Überkreuzen in dem geradlinigen Bildraum beinhaltet.

Bei einem derartigen nichthomogenen Verfahren ist eine unterschiedliche Abbildung für jede Zeile des geradlinigen Bildes in dem Intervall [Y1, Y2] definiert. Dies wird wieder aus dem Schnittpunkt dieser Zeile mit den Linien, die Endpunktpositionen verbinden, bestimmt. In diesem Fall wird die Entfernung des Schnittpunktes entlang der Linie selbst wiedergewonnen. Dies entspricht, nach möglicher Skalierung, die für die Auflösungsunterschiede erforderlich ist, einer physischen Position entlang des Linearsensors. In 19 sind aD und aD' die Schnittpunkte entlang Inkrementen I1 bzw. I2 für eine geradlinige Zeile D, wobei aus einer einfachen Geometrie aD = (yD – y1)·(N – 1)/(y2 – y1) und aD' = (yD – y1')·(N – 1)/(y2' – y1') für den Schnittpunkt der Zeile D + 1 Folgendes folgt: a(D + 1) = aD + (N – 1)/(y2 – y1) = aD + aRowInc. und a(D + 1)' = aD' + (N – 1)/(y2' – y1') = AD + aRowInc' was wieder eine einfache Wiederkehrbeziehung für jede aufeinander folgende Zeile für eine effiziente serielle Implementierung ergibt.

Jedes Pixel in dem geradlinigen Bild entlang der Zeile D in dem Intervall [X1, X2] bildet auf einen unterschiedlichen Punkt entlang einer Linie in dem Inkrementraum ab, die die beiden Punkte eines Schnittpunkts bei (0, aD) bzw. (1, aD') verbindet. Unter der Annahme einer Linearabbildung entlang dieser Zeile bildet das Pixel an dem Ort (xE, yD) in dem geradlinigen Bild auf einen Ort (aE, bE) in dem Inkrementraum ab, wobei Folgendes gilt: aE = aD + (xE – xD)·(aD' – aD)/(xD' – xD) und bE = (xE – xD)/(xD' – xD) und wieder folgt für das nächste Pixel entlang der Zeile D, dass Folgendes gilt: a(E + 1) = aE + (aD' – aD)/(xD' – xD) = aE + aInc und b(E + 1) = bE + 1/ (xD' – xD) = bE + bInc wobei die Intensität bei (aE, bE) durch die bilineare Interpolation bestimmt wird.

Die zusätzliche Initialisierung und eine modifizierte innere Schleife der TRANSFORMATIONSSCHLEIFE sind:

TRANSFORMATIONSSCHLEIFE 2

Eine direktere geometrische Interpretation kann auch bei anderen Ausführungsbeispielen des Verfahrens gemäß der Erfindung verwendet werden, um eine PAARWEISE-Geradlinig-Pixelinterpolation durchzuführen. Derartige Verfahren erfordern keine explizite Abbildung von Pixeln eines geradlinigen Bildes zurück in einen Inkrement-Koordinatenraum.

Ein besonders einfaches Ausführungsbeispiel mit reduzierten Rechenanforderungen hinsichtlich des Rückprojektionsansatzes besteht darin, eine Interpolation entlang jedes Inkrements durchzuführen und dann diese Werte direkt in dem geradlinigen Bild zu interpolieren. 20 zeigt interpolierte Pixelorte entlang jeder der Linien, die Endpunkte der Inkremente verbinden. Wie zuvor ist der Schnittpunkt an dem Ort aD und aD' innerhalb der Linearsensorpixel, die das Inkrement bilden, als zD und zD' innerhalb des geradlinigen Gitters gezeigt. Eine Linearinterpolation ergibt an diesen Schnittpunkten wie folgt „Pixelwerte" vD und vD': vD = I1 [A]·(1 – a) + I2 [A + 1]·a und vD' = I2 [A']·(1 – a') + I2 [A' + 1]·a' wobei A = Floor(aD) und A' = Floor(aD') und a = aD – A und a' – aD' – A' gilt.

Als Nächstes wird jedes Ganzzahlpixel des Bilds des geradlinigen Gitters auf der Zeile D in dem Bereich [X1, X2] zwischen diesen interpolierten Inkrementpixeln interpoliert. Dem Pixel an einem Ort xE Z. B. ist wie folgt ein Intensitätswert vE zugewiesen: vE = (vD·((xD' – xD) – (xE – xD)) + vD'·(xE – xD))/(xD' – xD) und wieder folgt, dass für das nächste Pixel entlang der Zeile D Folgendes gilt: v(E + 1) = vE + (vD' – vD)/(xD' – xD) = vE + vInc was in einer seriellen Implementierung ausgenutzt wird.

Für dieses Verfahren wird die TRANSFORMATIONSSCHLEIFE zu Folgendem:

TRANSFORMATIONSSCHLEIFE 3

Es wird angemerkt, dass die innere Schleife, in der ein Großteil der Rechenkosten aufgewendet werden, in der TRANSFORMATIONSSCHLEIFE 3 viel einfacher ist als in der TRANSFORMATIONSSCHLEIFE 2. Es soll angemerkt werden, dass eine Interpolation höherer Ordnung für eine größere Genauigkeit mit erhöhten Rechenkosten eingesetzt werden könnte.

Eine bessere Bildqualität kann auf Kosten erhöhter Berechnung erzielt werden, indem jedes Pixel des geradlinigen Bilds auf den nächsten Punkt an jedem der Inkremente abgebildet wird. Dies sind die Punkte an den Inkrementen, deren interpolierte Intensität (entlang des linearen Sensors) die Intensität des geradlinigen Pixels, das betrachtet wird, am besten widerspiegelt. Das Paar interpolierter Inkrement-Intensitätswerte wird dann kombiniert, wieder unter Verwendung einer linearen Interpolation, um die beste repräsentative Intensität für das Pixel zu ergeben. Es sollte angemerkt werden, dass in diesem Fall, im Gegensatz zu dem Fall aus 20, die interpolierten Punkte an den Inkrementen und das Pixel des geradlinigen Bildes nicht notwendigerweise auf einer geraden Linie liegen.

Der nächste Punkt an jedem der Inkremente ist durch Fällen einer Senkrechten von dem Pixel des geradlinigen Bildes auf die Linie, die die Endpunktpositionen verbindet, gegeben. Dieser Punkt wird auf einen entsprechenden Linearsensorelementort skaliert. 21 zeigt die nächsten Punkte an Orten aP und aP' entlang der Inkremente I1 bzw. I2, die zP bzw. zP' bezeichnet werden, hinsichtlich des geradlinigen Gitters.

Der Versatz (in Linearsensorelementeinheiten) oE von aD (dem Schnittpunkt des Inkrements mit der Zeile D des geradlinigen Bilds) des Punktes einer senkrechten Projektion entlang des Inkrements I1 eines Pixels auf der Zeile D mit einem x-Ort xE ist gegeben durch: oE = (xE – xD)·((x2 – x1)/Sensorlänge)·((N – 1/Sensorlänge) oE = (xE – xD)·(x2 – x1)·(N – 1/Sensorlänge2 wobei: Sensorlänge2 = (x2 – x1)2 + (y2 – y1)2 und der Versatz des nächsten Pixels entlang der Zeile D mit einem x-Ort xE + 1 ist gegeben durch: o(E + 1) = (xE + 1 – xD)·(x2 – x1)·(N – 1)/Sensorlänge2 o(E + 1) = oE + (x2 – x1)·(N – 1)/Sensorlänge2 o (E + 1) = oE + oInc

Ähnlich ist der Versatz (in Linearsensorelementeinheiten) oE' von aD' (dem Schnittpunkt des Inkrements mit der Zeile D des geradlinigen Bilds) des Punks einer Projektion entlang des Inkrements I2 eines Pixels auf der Zeile D mit einem x-Ort xE gegeben durch: oE' = (xE – xD')·((x2' – x1')/Sensorlänge')·((N – 1/Sensorlänge') oE' = (xE – xD')·(x2' – x1')·(N – 1)/Sensorlänge'2 wobei: Sensorlänge'2 = (x2' – x1')2 + (y2' – y1')2 und der Versatz des nächsten Pixels entlang der Zeile D mit einem x-Ort xE + 1 ist gegeben durch: o(E + 1)' = (xE + 1 – xD')·(x2' – x1')·(N – 1)/Sensorlänge'2 o(E + 1)' = oE' + (x2' – x1')·(N – 1) /Sensorlänge'2 o (E + 1)' = oE' + oInc'

Klar ist Sensorlänge gleich Sensorlänge' und bleibt während der gesamten Abtastung konstant.

Ein Addieren des Versatzes zu dem Zeilenschnittort ergibt den nächsten Sensorort an dem gerade betrachteten Pixel für jedes Inkrement. Dies bedeutet für ein Pixel an dem Ort (yD, xE) aP = aD + oE und aP' = aD' + oE'

Eine Interpolation zwischen den Linearsensorpixelintensitätswerten vP und vP' für diese Punkte an Inkrementen I1 bzw. I2 ergibt: vP = I1[A]·(1 – a) + I1 [A + 1]·a wobei A = Floor(aP) und a = aP – A und vP' = I1[A']·(1 – a') + I1[A' + 1]·a' wobei A' = Floor(aP') und a' = aP' – A'

Wir haben eine Auswahl von Koeffizienten für die Kombination von vP und vP', um den letztendlichen interpolierten Pixelwert zu ergeben. Eine Möglichkeit ist die Verwendung der Länge der Senkrechten gefällt auf die jeweiligen Inkremente. Zur Erleichterung einer Berechnung wird die relative x-Verschiebung des gerade betrachteten Pixels entlang der Zeile D von den Schnittpunkten mit den beiden Inkrementen bevorzugt. Für das Inkrement I1 hat dies den Wert (xE – xD) und für das Inkrement I2 den Wert (xD' – xE). Unter der Angabe, dass der Gesamtbereich von x (xD' – xD) ist, ist die interpolierte Intensität dieses Pixels: v = ((xD' – xE)·vP + (xE – xD)·vP')/(xD' – xD)

Als Nächstes werden weitere Ausführungsbeispiele des Verfahrens gemäß der Erfindung, die das BROCKENWEISE-Verfahrens einer geradlinigen Abbildung einsetzen, vorgelegt. Der BROCKENWEISE-Ansatz hat die zwei Vorteile, dass die äußere Schleife der geeigneten Version der TRANSFORMATIONSSCHLEIFE weniger häufig berechnet wird, und dass auf größere Anzahlen von Ausgangspixeln der Reihe nach zugegriffen wird, was direkt zu einer verbesserten Speicherbandbreite führt (ohne den Bedarf nach einem Cache).

22 zeigt einen Brocken, der aus M, in diesem Fall vier Inkrementen besteht. Das äußere Paar von Inkrementen, mit I1 und I2 bezeichnet, wird wieder durch die äußere Schleife der TRANSFORMATIONSSCHLEIFE verwendet, um gültige Pixel zu identifizieren, die in den Brocken abbilden. Bevorzugte Ausführungsbeispiele bestimmen Geradliniges-Array-Pixel-Werte mit einer erweiterten Form eines nichthomogenen Rückprojektionsalgorithmus, wie zuvor für den PAARWEISE-Fall beschrieben wurde. 23 zeigt die Transformation einer Zeile mit der Bezeichnung D in 22 in einen Inkrementraum, der die vier Inkremente beinhaltet, die durch I1 und I2 begrenzt sind. Er verbindet die Schnittpunkte der Zeile D mit jedem der äußeren Inkremente. In Fortführung des PAARWEISE-Falls, wie in 19 gezeigt ist, weisen diese Schnittpunkte versetzte Entfernungen entlang des Linearsensors von aD bzw. aD' für I1 und I2 auf. Die Koordinaten der Schnittpunkte in dem Inkrementraum sind so (0, aD) und ((M – 1), aD').

Jedes Pixel in dem geradlinigen Bild entlang der Zeile D in dem Intervall [X1, X2] bildet auf einen unterschiedlichen Punkt entlang einer Linie in dem Inkrementraum ab, die die beiden Schnittpunkte bei (0, aD) bzw. ((M – 1), aD') verbindet. Unter Annahme einer lineare Abbildung entlang dieser Zeile bildet das Pixel an dem Ort (xE, xD) in dem geradlinigen Bild auf einen Ort (aE, bE) in dem Inkrementraum ab, wobei: aE = aD + (xE – xD)·(aD' – aD)/(xD' – xD) und bE = (M – 1)·(xE – xD)/(xD' – xD) und wieder folgt für das nächste Pixel entlang der Zeile D, dass: a(E + 1) = aE + (aD' – aD)/(xD' – xD) = aE + aInc und b (E + 1) = bE + (M – 1)/(xD' – xD) = bE + bInc wobei die Intensität bei (aE, bE) durch die bilineare Interpolation bestimmt wird.

So wird die TRANSFORMATIONSSCHLEIFE zu Folgendem:

TRANSFORMATIONSSCHLEIFE 4
wobei IB das B-te Inkrement in dem Brocken ist und IB + 1 das (B + 1)-te Inkrement in dem Brocken ist.

Das BROCKENWEISE-Verfahren beruht auf der Tatsache, dass ein Abtastweg fast gleichmäßig ist und sich nur leicht ändert. Dies muss sowohl räumlich wahr sein (die Abtastung sollte eine gleichmäßige Form besitzen) als auch bezüglich der Abtastfrequenz entlang des Abtastwegs (die Abtastung sollte gleichmäßig abgetastet werden). Weitere Ausführungsbeispiele der Erfindung beinhalten die Erweitung des BROCKENWEISE-Verfahrens durch dynamische Variation der Brockengröße abhängig von dem Grad an Gleichmäßigkeit des Abtastwegs. Wo eine Gleichmäßigkeit gut ist, kann ein großer Brocken ohne Einführung einer Bildverzerrung untergebracht werden, wo jedoch der Abtastweg oder der Abtastbereich schnell variieren würde, könnte nur eine kleine Brockengröße untergebracht werden, ohne Artefakte einzuführen. In dem einschränkenden Fall kehren derartige Ausführungsbeispiele zu einem PAARWEISE-Verfahren zurück.

Ein Verfahren zum dynamischen Variieren der Brockengröße gemäß Ausführungsbeispielen der Erfindung wird nun beschrieben. Für eine annehmbare Verwendung des BROCKENWEISE-Verfahrens sollten die einzelnen Unterschiede an einer Endpunktpositionsgeometrie, die für jedes aufeinander folgende Paar von Inkrementen in dem Brocken vorliegen, mit den globalen Unterschieden für den gesamten Brocken übereinstimmen. In dem Verfahren wird eine Tabelle von Inkrementpositionsdeltas zwischen jedem aufeinander folgenden Paar von Inkrementen innerhalb des Brockens aufgebaut, wenn die Größe des Brockens von einem einzelnen Paar in Richtung eines Maximums erhöht wird. Die bevorzugte Brockengröße S ist ausgewählt, um die größte maximale erlaubte Brockengröße zu sein, oder kleiner als dieselbe oder gleich derselben, für die die einzelnen Deltas mit dem Gesamtpositionsinkrement über dem Brocken als Ganzes übereinstimmen.

Jeder Eintrag in der Tabelle besteht aus vier Inkrementwerten. Diese entsprechen den x- und y-Inkrementen einer Position jedes Endpunkts. Diese sind für das Inkrementpaar, das an dem i-ten Inkrement in dem Brocken endet, mit [X1i, Y1i, X2i, Y2i] bezeichnet. Das angesammelte Gesamtinkrement für den gesamten Brocken ist bezeichnet mit [X1N, Y1N, X2N, Y2N] und ist gegeben durch die Summe der einzelnen Inkremente für jede Komponente. Die Tabelle ist für Werte von N aufgebaut, beginnend bei 2 und in Richtung der maximalen erlaubten Brockengröße bei jedem Schritt gestuft. Wenn eine der folgenden Bedingungen für jedes i in dem Bereich 2 bis zu dem gegenwärtigen Wert von N nicht erfüllt ist: |X1i·N – X1N| < N·deltaSchwelle |X2i·N – X2N| < N·deltaSchwelle |Y1i·N – Y1N| < N·deltaSchwelle |Y2i·N – Y2N| < N·deltaSchwelle wird eine Brockengröße von s = N – 1 ausgewählt. Wenn diese Bedingung bei allen Schritten bis zu der maximalen erlaubten Brockengröße erfüllt ist, wird die maximale erlaubte Brockengröße ausgewählt.

Gemäß weiteren Ausführungsbeispielen der Erfindung wird nun ein wirksames Verfahren zum Überwinden einer Ungleichmäßigkeit bei der Abtastfrequenz, mit der einzelne Inkremente innerhalb eines Brockens erfasst werden, beschrieben. Dieses Verfahren befasst sich nicht mit einer Ungleichmäßigkeit bei der Form des abgetasteten Wegs, sondern nur bei dem physischen Abstand zwischen aufeinander folgenden Inkrementen. Derartige Ausführungsbeispiel sind in Implementierungen von Vorteil, in denen Inkremente in einer ungleichmäßigen Weise abgetastet werden. Es ist jedoch allgemein wünschenswert sicherzustellen, dass alle Abtastwerte für einen gesamten Brocken so gleichmäßig wie möglich abgetastet werden.

Eine Hilfsabbildungstabelle wird zu diesem Zweck eingeführt. Der Zweck der Hilfsabbildungstabelle besteht darin, die einheitliche x-Koordinate des Inkrementraums (mit einer bestimmten spezifizierten Teilpixelauflösung, z. B. 0,1 eines Pixels) in eine modifizierte Version, die einheitlich abgetastet wird, abzubilden. Die Tabelle muss für jeden Brocken auf der Basis der physischen Beabstandung (d. h. des Mittels der euklidschen Endpunktbeabstandung) der einzelnen Inkremente in demselben aktualisiert werden. Die Wirkung der Modifizierung ist so, wie in 24 dargestellt ist.

In 24a sind Inkremente gemäß ihrer mittleren physischen genormten Beabstandung gezeigt, so dass die Gesamtbeabstandung gleich einem weniger als die Anzahl von Inkrementen ist. Innerhalb dieses Raums bleibt die Abbildung der Zeile D des geradlinigen Bilds zwischen Inkrementen I1 und I2 linear. Ein Pixel des geradlinigen Bilds, das auf einen Linearinkrementraumort (x, y), der in 24a gezeigt ist, abbildet, wird in (x', y) in dem nichtlinearen Inkrementraum, der in 24b gezeigt ist, transformiert. In dem transformierten Raum sind die Inkremente einheitlich beabstandet, die Abbildung zwischen I1 und I2 ist jedoch nicht mehr linear. Eine Hilfstabelle MT wird zur Abbildung jedes x auf x' verwendet.

Weitere Ausführungsbeispiele der Erfindung werden für Fachleute aus einem Studium der oben dargelegten Lehre ersichtlich werden. In den PAARWEISE-Fall benötigen wir zwei Inkremente, die zwischengespeichert werden müssen, und jedes Inkrement wird zweimal verwendet. Bei dem BROCKENWEISE-Verfahren werden M Inkremente gespeichert und nur das erste und das letzte Element in einem Brocken werden doppelt verwendet. Zuerst geschieht dies für den Fall, in dem sie das hintere Inkrement in dem Brocken sind, und dann später, wenn sie der vordere Abtastwert des nächsten Brockens werden.

Der Puffer des geradlinigen Bilds 100 ist ausreichend groß, um eine einzelne Seite in Letter-Größe oder A4-Größe mit der Auflösung des Linearsensors (typischerweise entweder 200 oder 300 dpi) unterzubringen. Die Position und Ausrichtung des Ursprungs der Abtastung werden als zuvor bekannt angenommen. Inkremente, die entweder teilweise oder vollständig außerhalb des Bilds abbilden, können (unter Verwendung einer Modulo-Arithmetik in Bezug auf W und H für eine X- bzw. Y-Komponente) um die horizontalen und vertikalen Grenzen gewickelt werden, um an der gegenüberliegenden Seite des Geradlinig-Puffers fortzufahren. Nach Abschluss der Abtastung kann der Pufferspeicher des geradlinigen Bilds 100 sowohl horizontal als auch vertikal gerollt werden, um die gescannte Region zu zentrieren. Unter der Voraussetzung, dass die gescannte Region entweder die Gesamthöhe oder -breite des Geradlinig-Puffers 100 nicht überschreitet, wird das letztendliche Bild unabhängig von der anfänglichen Startposition erzeugt. Um eine ordnungsgemäße Ausrichtung zu erhalten, muss das Scannen entweder in der angenommenen Ausrichtung beginnen (z. B. immer parallel zu der Seite der Seite) oder eine Ausrichtung muss aus dem Inhalt der Abtastung wiedergewonnen und verwendet werden, um das letztendliche Bild neu auszurichten. Verfahren zum automatischen Bestimmen der dominanten Ausrichtung von Text auf einer Seite, die als eine Basis für Letzteres verwendet werden können, sind in der Literatur bekannt, z. B. „The Skew Angle of Printed Documents" von H. S. Baird. Proc 4th SPSE Conference Symposium an Hybrid Image System, Kochester, New York, 1987.

Der nächste Schritt besteht darin, aufeinander folgende Bildbänder innerhalb ihrer Überlappungsregion zusammenzuheften. Das Ziel besteht darin, mehrere Bänder innerhalb des Puffers 100, der ein letztendliches gleichgerichtetes rekonstruiertes Bild beinhaltet, zu kombinieren. Dies sollte in einer derartigen Weise durchgeführt werden, um einen Großteil des angesammelten Navigationsfehlers zu identifizieren und korrigieren und einen möglichen Restfehler zu maskieren. Dies ist in der internationalen Patentanmeldung Veröffentlichungsnummer WO 96/27257 vollständiger erläutert.

Vorzugsweise stellt der Strom von Navigationsdaten die Ausrichtungsinformationen bereit, die zum Zusammenheften benötigt werden. Da das Navigationssignal zu der Ansammlung eines Fehlers neigt, wird es fortwährend durch Rückkoppeln eines Korrektursignals, das aus einer Analyse von Merkmalsversätzen hergeleitet ist, abgeändert.

Zuerst werden wir ein Verfahren zum Zusammenheften von Bildbändern beschreiben, das annimmt, dass keine Navigationsfehler vorliegen.

Ein bestimmter Überlappungsbereich ist nötig, um zwei Bildbänder zusammenzuheften. Bänder sind durch eine Umkehr in dem Weg der Abtastvorrichtung zurück über eine Region des Originals, von dem gerade ein Teil abgetastet wurde, begrenzt. Ein Band weist die Bilddaten auf, die während eines Abtastschwungs über ein gerade gescanntes Original erfasst werden. In der folgenden Beschreibung wird der Ausdruck „Band" auch manchmal verwendet, um sich auf den Teil des rekonstruierten Bilds zu beziehen, der aus der Abbildung derartiger Daten erzeugt wird.

Die Abtastung, die durch die Orte von Endpunkten von Inkrementen in 11 dargestellt wird, erzeugt zwei überlappende Bänder. In 12 wird der Abschnitt, der in den Puffer des geradlinigen Bilds 100 abgebildet wird, der ein Band Nr. 1 aufwiest, teilweise auf dem Rückweg durch den Abschnitt der Abtastung erneut abgebildet, der einem Band Nr. 2 entspricht, wobei die Fläche einer Überlappung 102 ausgefüllt gezeigt ist. Zu einer Zeit T wurde so ein Teilband weit abgetastet. Ein zufrieden stellendes Zusammenheften kann in diesem Fall erzielt werden, indem einfach mit einer Abbildung des Bands Nr. 2 in den Geradliniges-Bild-Puffer 100 auf das Band Nr. 1 fortgefahren wird. Zurückkehrend zu 11 kann ein Inkrement Nr. 2 entlang seiner gesamten Länge in gerade der gleichen Weise wie für ein Inkrement Nr. 1 abgebildet werden und ähnlich für jedes Pixel in der Region einer Überlappung 102 in 12. Die letztendliche Wiedergabe in dem Geradliniges-Bild-Puffer 100, die aus dem Band Nr. 1 resultiert, wird einfach durch diejenige ersetzt, die aus dem Band Nr. 2 resultiert.

Gleichermaßen erweist sich ein Schema, in dem Pixel in dem Überlappungsbereich 12, abgebildet als Teil des Bands Nr. 1, nicht durch diejenigen ersetzt werden, die durch das Band Nr. 2 abgebildet werden, unter der Voraussetzung, dass alle Pixel, die durch das Band Nr. 2 abgebildet werden, die nicht Teil der Überlappung sind (d. h. nicht auch durch das Band Nr. 1 abgebildet werden), ordnungsgemäß abgebildet werden, als zufriedenstellend. Dies soll sagen, dass die durch das Band Nr. 1 abgebildete Region verwendet wird, um die durch das Band Nr. 2 abgebildete Region zu beschneiden. Tatsächlich können unter der Voraussetzung, dass das Band Nr. 1 und das Band Nr. 2 alle Pixel, die außerhalb der Überlappungsregion liegen, korrekt abbilden, die Pixel in der Überlappungsregion gleichermaßen von entweder dem Band Nr. 1 oder dem Band Nr. 2 oder einer Kombination erhalten werden.

In der Praxis ergibt dieser einfache Ansatz, der keine Navigationsfehler annimmt, aufgrund der Ansammlung von Fehlern zwischen den Positionsetiketten von Band Nr. 1 und Band Nr. 2 keine sehr guten Ergebnisse.

Ein vorteilhaftes Verfahren zum Zusammenheften wird nun unter Bezugnahme auf die 13 und 14 beschrieben. 13 zeigt die Verarbeitungsstufen und Datenpuffer an, die beinhaltet sind, während sich 14 auf den eingesetzten Vorgang in Bezug auf das Band Nr. 1 und das Band Nr. 2 bezieht. Die Bildinkrementdaten in dem Inkrementpuffer B werden auf den Geradliniges-Bild-Puffer 100 abgebildet, wie zuvor beschrieben wurde. 14 zeigt einen Teil des Bilds, der in dem Band Nr. 1 erfasst wird, als durch den Rückdurchlauf, Band Nr. 2, erneut in den Geradliniges-Bild-Puffer 100 abgebildet. Eine Navigationskorrektur wird durch ein Korrelieren von Merkmalen innerhalb des Überlappungsbereichs zwischen Band Nr. 1 und Band Nr. 2 berechnet.

14 hebt diesen Überlagerungsbereich hervor, der in zwei Teile 104 und 105 unterteilt ist. Wie in 14 gezeigt ist, gibt es während einer Sammlung von Band Nr. 1 vierseitige Bildsegmente (im Folgenden „Ausrichtungskacheln" genannt) von denen drei (106, 108 und 110 sind gezeigt) periodisch entlang der unteren Kante des Bands in dem Überlappungsbereich 105 mit Etikett versehen werden. Bei einem späteren Durchlauf (Band Nr. 2) wird der Überlagerungsbereih 104 von Band Nr. 2 über der Fläche 105, der die Ausrichtungskacheln 106, 108 und 110 von Band Nr. 1 beinhaltet, beschnitten, d. h. verworfen, wenn Band Nr. 2 erfasst wird, indem ein Überschreiben dieser Pixel von Band Nr. 1 nicht erlaubt wird. Die Ausrichtungskachel 106 von dem Band Nr. 1 befindet sich in dem, was vom Band Nr. 2 verbleibt, nachdem der Überlappungsbereich 104 beschnitten wurde, oben. Wenn die Navigationsdaten perfekt sind, liegt kein Versatz zwischen der Stelle der Ausrichtungskachel 106 und der Stelle des erneut abgetasteten Bilds der Kachel in dem Band Nr. 2 vor. Realistischer wird sich ein bestimmter Navigationsfehler angesammelt haben, seit die letzte Ausrichtung durchgeführt wurde. Der Versatz zwischen dem Erscheinungsbild dieser Kachel in den beiden Bändern erzeugt eine Korrekturfaktor, der dann verwendet wird, um zukünftige Navigationspositionsetiketten, die den Bilddaten zugeordnet sind, zu aktualisieren, um den angesammelten Gesamtfehler zu minimieren. Auf diese Weise wird verhindert, dass der angesammelte Gesamtfehler in den Navigationsdaten auf eine Größe anwächst, die eine offensichtliche Verzerrung in der Region einführt, in der sich die Bänder überlappen.

Die Verarbeitungsstufen zum Zusammenheften von Band Nr. 1 und Band Nr. 2 werden nun unter Bezugnahme auf die 13 und 14 beschrieben. 13 zeigt den Bildinkrementpuffer B und den Geradliniges-Bild-Puffer 100. 13 zeigt außerdem einen Merkmalsortpuffer 113 und einen Merkmalspuffer 114. Die Verarbeitungsstufen sind die Folgenden:

  • 1. Wie oben erwähnt wurde, werden während eines Sammelns des Bands Nr. 1 Ausrichtungskacheln (106, 108 und 110) periodisch entlang der unteren Kante des Bands in dem Überlappungsbereich 105 mit Etikett versehen. Eine Gesamtausrichtungskachel könnte für die oben beschriebene Korrelation verwendet werden, bei dem bevorzugten Ausführungsbeispiel jedoch befindet sich eine kleine Fläche mit Hochfrequenzkontrast (im Folgenden als „Ausrichtungsmerkmal" bezeichnet), die aus einer rechteckigen Kachel (z. B. 15 × 15 Pixeln) eines Grauskalabilds besteht, als Ergebnis der Erfassung von Band Nr. 1 innerhalb einer Ausrichtungskachel, die einen Teil des Bilds bildet, das in dem Geradliniges-Bild-Puffer 100 rekonstruiert wird.
  • 2. Die Positionsetiketten der Ausrichtungsmerkmale (die die Position jedes Ausrichtungsmerkmals innerhalb des Geradliniges-Bild-Puffers 100 definieren) werden in dem Merkmalsortpuffer 113 vor dem Beginn der Abbildung von Band Nr. 2 in den Geradliniges-Bild-Puffer 100 gespeichert.
  • 3. Bei der Abbildung von Band Nr. 2 werden Ausrichtungsmerkmalsorte, bevor sie in dem Geradliniges-Bild-Puffer 100 durch das Band Nr. 2 überschrieben werden, identifiziert. Dies wird durch ein Definieren eines rechteckigen Erfassungsfensters 107, in 14 gezeigt, mit einer Länge, die gleich einem Bildinkrement ist, und einer Breite von einigen Pixeln, das dem Bildinkrement von Band Nr. 2 vorausgeht, das gegenwärtig einer Abbildung in den Geradliniges-Bild-Puffer 100 unterzogen wird, erzielt. Wenn ein Ausrichtungsmerkmalsort, der in dem Merkmalsortpuffer 113 gespeichert ist, in das Erfassungsfenster 107 fällt, wird der Ausrichtungsmerkmalsort ausgewählt (nur ein Ausrichtungsmerkmalsort könnte zu einer bestimmten Zeit ausgewählt werden).
  • 4. Das Ergebnis eines Auswählens eines Ausrichtungsmerkmalsorts besteht darin, das relevante Ausrichtungsmerkmal (d. h. das Ausrichtungsmerkmal, das sich an diesem Ort in dem Geradliniges-Bild-Puffer 100 befindet) in den Merkmalspuffer 114 zu kopieren. Der Merkmalspuffer 114 speichert zeitweise eine Kopie des Ausrichtungsmerkmals gemeinsam mit seinem Positionsetikett.
  • 5. Nachdem das Band Nr. 2 in den Geradliniges-Bild-Puffer 100 abgebildet wurde, um so den Ort (und eine kleine benachbarte Fläche) des Ausrichtungsmerkmals zu überschreiben, eine Kopie dessen in dem Merkmalspuffer 114 gespeichert wird, werden der Inhalt des Merkmalspuffers 114 und der neu geschriebene Teil des Geradliniges-Bild-Puffer 100 verglichen, um ein Navigationskorrektursignal zu erzeugen, d. h. die erforderliche Translation, um die beiden Bildfragmente in enge Entsprechung zu bringen.
  • 6. Dieses Korrektursignal wird zu dem in 9 gezeigten Navigationsprozessor 80 rückgekoppelt. Um offensichtliche Verzerrungen in dem letztendlichen repräsentativen Bild zu verhindern, wird der Fehlerschätzwert allmählich angelegt, d. h. die „Positionsetiketten" werden in kleinen Schritten mit festem Betrag modifiziert, wenn jede neue Zeile von Linearsensordaten in den Speicher geladen wird, bis eine Berücksichtigung des gesamten Fehlers stattgefunden hat.

Während weitere Korrelationsansätze eingesetzt werden könnten, ist ein annehmbarer Ansatz für die Berechnung des Versatzes zwischen zwei Bildfragmenten eine „Summe einer quadrierten Differenz"-Korrelation. Eine kleine Suchfläche ist um den ursprünglichen Ort des Merkmals herum definiert und Korrelationskoeffizienten werden durch folgende Gleichung bestimmt: Ck,l = &Sgr;i&Sgr;j(Ti,j – Ii+k,j+l)2 wobei Ti , j die Grauskalawerte des Merkmals aus dem Band Nr. l bezeichnet und Ii +k , j +l die Grauskalawerte des neu erfassten Merkmals aus dem Band Nr. 2 bezeichnet. Die Indizes i und j spezifizieren Pixelorte innerhalb der Merkmale, während k und 1 den Betrag des vorgeschlagenen Translationsversatzes spezifizieren (eingeschränkt, um innerhalb des Suchraums zu bleiben). Das kleinste Element in dem resultierenden Korrelationsarray bezeichnet den Versatz zwischen den beiden Merkmalen.

Das Ausrichtungsmerkmal innerhalb der Ausrichtungskachel ist ausgewählt, um eine Bildvarianz zu maximieren, da dies die Genauigkeit des Korrelationsverfahrens verbessert. Bei einem möglichen Ausführungsbeispiel wird nur ein Teilsatz von Orten innerhalb der Region betrachtet. Diese Orte 116, 118, 120, 122 und 124 sind in 15 als entlang der Hauptachsen 126 und 128 der Ausrichtungskachel liegend gezeigt (Linien, die gegenüberliegende Mittelpunkte von Linien verbinden, die die Region definieren) und werden an dem Schnittpunkt und auf halber Strecke zwischen dem Schnittpunkt und jedem Endpunkt der Achse abgetastet. Für jeden Ort 116, 118, 120, 122 und 124 wird die Varianz VARk,l unter Verwendung der folgenden Gleichungen berechnet: SUMk,l = &Sgr;i&Sgr; Ik+i,l+j SUM2k,l = &Sgr;i&Sgr;j(Ik+i,l+j)2 VARk,l = SUM2k,l/N – (SUMk,l)/N2

Wenn Navigationsfehler relativ groß sind, kann das oben beschriebene Verfahren dennoch unerwünschte Artefakte in das rekonstruierte Bild einführen, insbesondere am Anfang der Bänder. Dies ist so, da der Fehler zwischen den berechneten Positionen des oberen Endes und des unteren Endes der Bildinkremente sich entlang der Länge eines Bandes ansammelt und an dem Beginn eines neuen Bandes maximal ist.

Ein weiteres bevorzugtes Ausführungsbeispiel des Zusammenheftverfahrens wird nun kurz unter Bezugnahme auf die 16 und 17 beschrieben.

16 zeigt den Bildinkrementpuffer B und den Geradliniges-Bild-Puffer 100. Wie bei dem Ausführungsbeispiel in Bezug auf die 13, 14 und 15 beschrieben wurde, wird ein Merkmalsortpuffer 131 verwendet, um Positionsetiketten für Ausrichtungsmerkmale zu speichern, die im Band Nr. 1 identifiziert sind. Außerdem gibt es einen Spezialbildpuffer 132 zum Speichern von Bildfragmenten aus dem Puffer B, wie beschrieben werden wird.

17 zeigt wieder, wie ein Teil des im Band Nr. 1 erfassten Bildes durch den Rückdurchlauf, Band Nr. 2, erneut abgebildet wird. Ausrichtungskacheln sind bei 130 angezeigt. Bei diesem Ausführungsbeispiel jedoch gibt es zwei Verarbeitungsphasen zum Zusammenheften von Band Nr. 2 und Band Nr. 1. Die Verarbeitungsstufen in der ersten Verarbeitungsphase unterscheiden sich von denjenigen des Vorgangs in 13 dadurch, dass nach Schritt 3:

Der ausgewählte Ausrichtungsmerkmalsort verwendet wird, um den vorhergesagten Ort des Ausrichtungsmerkmals zu definieren, wenn Band Nr. 2 in den Geradliniges-Bild-Puffer 100 abgebildet wird. Navigationsfehler, die in Bezug auf vorherige Ausrichtungsmerkmale gefunden werden, werden berücksichtigt, indem der gegenwärtige Fehlerschätzwert (in einem Fehlerpuffer 134 gespeichert) verwendet wird, um den Ort des gegenwärtigen Ausrichtungsmerkmals vorherzusagen. So muss der Suchbereich, der zur Lokalisierung des gegenwärtigen Ausrichtungsmerkmals verwendet wird, nur ausreichend groß sein, um das mögliche Fehlerinkrement zu berücksichtigen. Der Spezialbildpuffer 132 wird zeitweilig verwendet, um direkt aus dem Puffer B eine Geradliniges-Bild-Abbildung der Bilddaten des Bands Nr. 2, die sich um den ausgewählten Ausrichtungsmerkmalsort herum befindet, zu speichern, sowie zur Speicherung des Ausrichtungsmerkmalsorts. Anders ausgedrückt, wird zu einer Zeit T das Bildinkrement 138, das in 17 gezeigt ist, in den Puffer 132 abgebildet. Die Größe des Spezialbildpuffers 132 muss angemessen sein, um das Ausrichtungsmerkmal plus den erforderlichen Suchbereich zu speichern, dessen Größe gemäß bekannten Fehlerschätzalgorithmen berechnet wird. Das Bildfragment aus dem Band Nr. 2, das in dem Spezialbildpuffer 132 gespeichert ist, wird dann mit dem entsprechenden Bildfragment verglichen, das an dem Ausrichtungsmerkmalsort in dem Geradliniges-Bild-Puffer 100 gespeichert ist. Auf diese Weise wird ein Versatz erhalten, der, wenn er mit dem vorherigen Fehlerschätzwert angesammelt wird, einen aktualisierten Schätzwert des Navigationsfehlers ergibt. Dieser aktualisierte Schätzwert wird gemeinsam mit einem Positionsetikett in dem Fehlerpuffer 134 gespeichert.

Das Positionsetikett des Fehlerschätzwerts ist einfach der Ort, in Bezug auf den Geradliniges-Bild-Puffer 100, der Mitte des gegenwärtigen Ausrichtungsmerkmals. Dies wiederum wird verwendet, um das Inkrement des Inkrementpuffers B zu bestimmen, auf das sich der Fehlerschätzwert bezieht (d. h. das erste Inkrement, das Band Nr. 2 entspricht, das auf diesen Bildort abbildet). Dies zeigt das Inkrement an, durch das der gemessene Schätzwert vollständig untergebracht werden sollte.

In einer zweiten Verarbeitungsphase werden die Bilddaten aus dem Band Nr. 2 unter Berücksichtigung der Fehlerschätzwerte an den aufgezeichneten Positionen in den Geradliniges-Bild-Puffer 100 geschrieben, um so diese Fehler aus dem letztendlichen rekonstruierten Bild zu entfernen. Dies wird durch Modifizieren der Positionsdaten, die den Endpunkten der einzelnen Bildinkremente von Sensordaten zugeordnet sind, durchgeführt.

Dieser bevorzugte Ansatz ergibt ein verbessertes Zusammenheften, da Fehler an den Positionen des Navigationssensors, die sich durch die Überlappungsregion zwischen Bändern bewegen, identifiziert und korrigiert werden, bevor das letztendliche Bild rekonstruiert wird. Zusätzlich kann ein Fehler zwischen den berechneten Positionen des oberen Endes und des unteren Endes der Bildinkremente, der sich während einer Sammlung des vorherigen Bandes angesammelt hat, auf einmal zu Beginn des nächsten Bandes absorbiert werden, ohne unterwünschte Artefakte einzuführen. Dies ist in 17 durch die Diskontinuität zwischen den rechten Kanten des Wendepunkts zwischen dem Band Nr. 1 und dem Band Nr. 2, die aus der ersten und der zweiten Verarbeitungsphase hergeleitet werden, die oben beschrieben wurden, angezeigt.

Die oben beschriebenen Zusammenheftvorgänge könnten in unterschiedlichen Weisen bezüglich der Natur des erforderlichen Abtastens implementiert sein. Eine Alternative besteht darin, es einzufordern, dass das Abtasten von dem oberen Ende einer Seite bis zu dem unteren Ende ausgeführt wird, wobei in diesem Fall ein Zusammenheften immer nur zwischen dem unteren Ende eines Bandes und dem oberen Ende des nächsten durchgeführt werden muss. Ein weiterer Ansatz besteht darin, es zu erlauben, dass ein Abtasten an einem beliebigen Teil der Seite beginnen kann, es jedoch erforderlich zu machen, dass die anfängliche Richtung eines Abtastens beibehalten wird. In diesem Fall muss es die Fähigkeit geben, Ausrichtungsmerkmale an beiden Kanten von Bändern zu identifizieren, sobald jedoch die Richtung des Abtastens festgelegt ist, müssen Fehlerschätzwerte nur für eine Seite des gegenwärtigen Bands behalten werden. Bei einem weiteren Ansatz könnte ein Abtasten in einer beliebigen Richtung erlaubt sein und Veränderungen an der Abtastrichtung können auch untergebracht werden, z. B. eine Spiralabtastung. Bei diesem dritten Ansatz muss nicht nur die Fähigkeit vorliegen, Ausrichtungsmerkmale an beiden Kanten von Bändern zu identifizieren, sondern müssen für den Fall, dass sich die Richtung eines Abtastens ändern sollte, Fehlerschätzwerte für sowohl das obere Ende als auch das untere Ende jedes Bands behalten werden. Der letztere Ansatz ergibt die größte Flexibilität für den Benutzer, hat jedoch den höheren Rechenmehraufwand.

Bei einem bevorzugten Ausführungsbeispiel einer Vorrichtung gemäß der Erfindung ist die Verarbeitungselektronik für Bildrekonstruktionen, Zusammenheften, und Bildverwaltung innerhalb des Gehäuses beinhaltet, das die Abtastvorrichtung 10 aus 1 definiert. So könnte das abgetastete Bild unmittelbar an der Bildanzeige 16 vorgelegt werden. Die Abtastvorrichtung könnte jedoch einen Speicher beinhalten, um mit Positionsetiketten versehene Bilddaten zu speichern, jedoch ohne Verarbeitungs- und Dateiverwaltungselektronik und Firmware.

Wie unter Bezugnahe auf 3 angemerkt wurde, sind die Navigations- und Bilderzeugungssensoren 22, 24 und 26 vorzugsweise an einem Schwenkbauteil 20 befestigt. Bei einem Ausführungsbeispiel ist das Schwenkbauteil mit dem Rest des Gehäuses durch zumindest ein Elastomer verbunden, für das ein Ende des Elastomers mit dem feststehenden Abschnitt des Gehäuses verbunden ist und das andere Ende mit dem Schwenkbauteil verbunden ist. Das Elastomer wirkt wie ein Gelenkt. So darf der Schwenkabschnitt ohne die Verwendung von Reibungselementen „schweben". Leistungs-, Steuer- und Datensignale könnten über flexible Kabel, die abgeschirmt sind, zu den Sensoren geführt werden, um eine elektromagnetische Interferenz zu minimieren. Weitere Verfahren zum schwenkmäßigen Anbringen des Schwenkbauteils können eingesetzt werden. Wenn das Schwenkbauteil weggelassen wird und die Sensoren an einer festen Position an dem Gehäuse sind, muss Sorge getragen werden, dass die Abtastvorrichtung 10 während einer Bilderfassung nicht übermäßig geneigt wird. Bei diesem Ausführungsbeispiel muss dem Entwurf von Beleuchtungs- und optischen Elementen erhöhte Aufmerksamkeit gewidmet werden.

Während die Erfindung als eine beschrieben und dargestellt wurde, in der ein planares Original abgetastet wird, ist dies nicht wesentlich. Tatsächlich werden Fachleute auf dem Gebiet ohne Weiteres verstehen, wie viele der Techniken zum Abtasten dreidimensionaler Bilder verwendet werden können. Das bevorzugte Ausführungsbeispiel jedoch ist eines, bei dem das Bild von Interesse auf einem Medium, wie z. B. einem Stück Papier, einer Transparenzfolie oder einer Photographie, gebildet ist und die Abtastvorrichtung in Kontakt mit dem Medium steht.


Anspruch[de]
Ein Verfahren zum Rekonstruieren eines Bilds, das als Bilddaten in einem Linearsensorarray (22) und Positionsdaten in einer Navigationseinrichtung (24, 26, 80) erfasst wird, wobei das Bild in der Form eines Stroms aufeinanderfolgender Sensorablesewerte erfasst wird, wobei jeder Sensorablesewert einen Ablesewert jedes Elements in dem Linearsensorarray (22) aufweist, und wobei Positionsdaten für jeden Sensorablesewert erfasst werden, wobei das Verfahren folgende Schritte aufweist:

Definieren eines Pixelgitters für ein rekonstruiertes Bild;

Identifizieren eines oder mehrerer Pixel in dem Pixelgitter, für die dieser Teil der Bilddaten relevant ist, aus einem Teil der Bilddaten durch Verwenden der Positionsdaten, das ein Definieren einer Region in dem Pixelgitter, die durch Abbilden von Positionen äußerer Elemente des Linearsensorarrays für zwei unterschiedliche Sensorablesewerte in dem Strom auf das Pixelgitter erhalten wird, aufweist, wobei die Positionen aus den Positionsdaten für die beiden unterschiedlichen Sensorablesewerte erhalten werden; und

Auswählen einer Mehrzahl relevanter Bilddatenwerte aus diesem Teil der Bilddaten für ein Pixel des einen oder der mehreren Pixel in der Region des Pixelgitters; und

Bestimmen der Intensität des Pixels unter Verwendung der relevanten Bilddatenwerte, die für dieses Pixel ausgewählt sind.
Ein Verfahren gemäß Anspruch 1, bei dem die beiden unterschiedlichen Sensorablesewerte (I1, I2) zwei aufeinanderfolgende Sensorablesewerte in dem Strom sind, und bei dem die Schritte des Auswählens relevanter Bilddatenwerte und des Bestimmens der Intensität unter Verwendung von Bilddaten von den beiden unterschiedlichen Sensorablesewerten durchgeführt werden. Ein Verfahren gemäß Anspruch 1, bei dem die beiden unterschiedlichen Sensorablesewerte (I1, I2) zwei Sensorablesewerte in dem Strom sind, die nicht aufeinanderfolgend sind, wobei die beiden unterschiedlichen Sensorablesewerte und mögliche dazwischenliegende Sensorablesewerte einen Brocken aufweisen, und bei dem die Schritte des Auswählens relevanter Bilddatenwerte und des Bestimmens der Intensität unter Verwendung von Bilddaten von allen Sensorablesewerten in dem Brocken durchgeführt werden. Ein Verfahren gemäß Anspruch 3, bei dem die Anzahl der Sensorablesewerte in einem Brocken durch den Grad an Einheitlichkeit des Abtastwegs bestimmt wird, der durch die entsprechenden Positionsdaten definiert ist. Ein Verfahren gemäß einem der Ansprüche 1 bis 4, bei dem der Schritt des Identifizierens eines oder mehrerer Pixel in dem Pixelgitter ferner den Schritt eines Bestimmens, welche Pixel in dem Pixelgitter in die Region fallen, die durch die beiden unterschiedlichen Sensorablesewerte (I1, I2) definiert wird, aufweist. Ein Verfahren gemäß Anspruch 5, bei dem Pixel in dem Pixelgitter in einen Raum abgebildet werden, der durch die beiden unterschiedlichen Sensorablesewerte definiert ist, und bei dem die Gitterpixel, für die eine Intensität bestimmt wird, diejenigen sind, die in den definierten Raum abbilden. Ein Verfahren gemäß Anspruch 6 in Rückbezug auf Anspruch 3, bei dem der Raum, der durch die beiden unterschiedlichen Sensorablesewerte definiert ist, so definiert ist, um eine einheitliche Abtastung bei Sensorablesewerten bereitzustellen. Ein Verfahren gemäß Anspruch 6 oder Anspruch 7, bei dem die Intensität eines Gitterpixels durch eine Interpolation aus Sensorpixelwerten bei jedem zweier aufeinanderfolgender Sensorablesewerte bestimmt wird, wobei die Sensorpixelwerte ausgewählt werden, um das Gitterpixel, das in den Raum abgebildet wird, zu überspannen. Ein Verfahren gemäß Anspruch 8, bei dem die Interpolation eine bilineare Interpolation aus zwei Sensorpixelwerten bei jedem zweier aufeinanderfolgender Sensorablesewerte ist. Ein Verfahren gemäß Anspruch 8, bei dem für jeden der beiden aufeinanderfolgenden Sensorablesewerte ein interpolierter Pixelwert aus Sensorpixelwerten an einer interpolierten Pixelposition berechnet wird, und bei dem der Gitterpixelwert aus den interpolierten Pixelwerten berechnet wird. Ein Verfahren gemäß Anspruch 10, bei dem die interpolierten Pixelwerte durch lineare Interpolation berechnet werden. Ein Verfahren gemäß Anspruch 10 oder 11, bei dem der Gitterpixelwert aus den interpolierten Pixelwerten durch lineare Interpolation berechnet wird. Ein Verfahren gemäß einem der Ansprüche 10 bis 12, bei dem die interpolierten Pixelpositionen an Schnittpunkten zwischen einer Gitterpixelzeile, die das Gitterpixel beinhaltet, und den Positionen zweier aufeinanderfolgender Sensorablesewerte angeordnet sind. Ein Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem das Pixelgitter geradlinig ist. Ein Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem die Navigationseinrichtung (24, 26, 80) einen oder mehrere Sensoren (24, 26) zum Erfassen inhärenter strukturbezogener Eigenschaften eines Mediums, das das erfasste Bild trägt, aufweist. Ein Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem das Linearsensorarray (22) in einer Abtastvorrichtung beinhaltet ist. Eine Rechenvorrichtung, die angeordnet ist, um Bilddaten und Positionsdaten zu empfangen, die durch eine Abtastvorrichtung mit einem Linearsensorarray und einer Navigationseinrichtung erhalten werden, und angeordnet ist, um ein Verfahren gemäß einem der Ansprüche 1 bis 16 durchzuführen. Eine Rechenvorrichtung gemäß Anspruch 17, die ferner eine Abtastvorrichtung mit einem Linearsensorarray und einer Navigationseinrichtung aufweist. Eine Rechenvorrichtung gemäß Anspruch 17, die angepasst ist, um Signale von einer Abtastvorrichtung mit einem Linearsensorarray und einer Navigationseinrichtung zu empfangen.






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