DE19814075B4

DE19814075B4 - Verfahren zum Abtasten und Erkennen mehrerer Fotografien und zum Beseitigen von Randfehlern

Info

Publication number: DE19814075B4
Application number: DE19814075A
Authority: DE
Inventors: Yongchun Lee; Quinton Lamar Sowell
Original assignee: Eastman Kodak Co
Current assignee: Kodak Alaris Inc
Priority date: 1997-03-31
Filing date: 1998-03-30
Publication date: 2009-12-03
Anticipated expiration: 2018-03-31
Also published as: US5974199A; JP3883696B2; DE19814075A1; JPH118755A

Abstract

Verfahren zum Abtasten und Erkennen mehrerer Fotografien und zum Beseitigen von Randfehlern mit folgenden Schritten:
Anordnen einer Vielzahl von Fotografien (12) auf einem Scanner (11);
Abtasten mit niedriger Auflösung, um eine Vielzahl niedrig aufgelöster Bilder zu erzeugen;
Herstellen einer Vielzahl von Vielecken, wobei jedes Vieleck mindestens eines der niedrig aufgelösten Bilder enthält;
Ermitteln einer Anzahl von Vielecken;
Vergleichen dieser ermittelten Anzahl von Vielecken mit der Anzahl der Fotografien (12),
und wenn die Anzahl der Vielecke kleiner als die Anzahl der Fotografien ist, Neupositionieren sich überlagernder Fotografien (12) und Wiederholen der Abtastung mit niedriger Auflösung sowie der nachfolgenden Schritte;
Bestimmen der Schräglage und Position jeder Fotografie;
Auswählen einer ersten Fotografie;
Abtasten dieser ersten Fotografie mit hoher Auflösung, um ein Bild mit hoher Auflösung zu erzeugen;
gerades Ausrichten des Bildes mit hoher Auflösung und
Ausschneiden des Bildes mit hoher Auflösung, um...

Description

Die Erfindung bezieht sich allgemein auf das Abtasten von Fotografien und insbesondere auf das Erkennen der Anzahl und der Schräglage von Fotografien auf einem Scanner-Vorlagenglas und das Neuausrichten und Ausschneiden des digitalisierten Bildes zum Beseitigen von Randfehlern vor dem Drucken.
Wie in 1 gezeigt, muß ein Benutzer 10, der eine Kopie einer Fotografie 12 auf einem Scanner 11 anfertigen möchte, die Fotografie 12 auf ein Scanner-Vorlagenglas 14 legen, und zwar so, daß die Vorlage an der oberen Anlageschiene 16 und an der seitlichen Anlageschiene 18 anliegt. Der Benutzer 10 muß zudem auf dem Eingabeschirm 21 das richtige Fotoformat auswählen, d. h. 4 × 6, 5 × 7 usw. Vor dem Drucken des Bildes oder vor dem Abspeichern auf einer Speicherplatte wird eine hoch aufgelöste Abtastung eines festgelegten Abschnitts ausgehend von Ursprungspunkt 19 des Scanners vorgenommen. Dieses Verfahren kommt in einer Reihe von kommerziellen Produkten zum Einsatz.
Diese Betriebsweise wirft gewisse Probleme auf. Erstens ist der Benutzer gezwungen, ein einzelnes Foto auf den Scanner zu legen, und zwar in korrekter Ausrichtung zu den Anlageschienen und mit einer Ecke am Ursprungspunkt. Wenn das Bild nicht genau am Ursprungspunkt angelegt wird, erfaßt der Abtastbereich nicht den gesamten Bildbereich, so daß das digitalisierte Bild einen Teil des Scanner-Vorlagenglases mit erfaßt, was sich an einem oder an mehreren Rändern als sogenannter Randfehler 20 bemerkbar macht, wie in 2 gezeigt. Diese Randfehler müssen von den für den Endverbraucher bestimmten Kopien beseitigt werden. Einige Scanner sind mit einem Programm ausgestattet, das den Abtastbereich entlang der horizontalen und vertikalen Ränder abschneidet, um den Randfehler zu beseitigen. Falls jedoch ein Bild gedreht ist, beseitigt das Programm die entlang der Bildlinien auftretenden Randfehler 22 nicht, wie in 3 gezeigt wird. Falls der Benutzer mehrere Fotografien abtasten und die Bilder auf Platte speichern möchte, müssen die Bilder einzeln verarbeitet werden, was recht ineffizient ist.
Ferner sei auf die JP 2-143379 hingewiesen, die eine Bildanordnungsvorrichtung mit Mitteln zum Erhalten von Positionsinformationen aufweist, um jeweilige Bilder innerhalb eines vorbestimmten Bereichs, insbesondere hinsichtlich einer Verdrehung der Bilder, neu anzuordnen. Hierdurch soll erreicht werden, dass die Ränder der Bilder gleichmäßig sind.
Der vorliegenden Erfindung liegt die Aufgabe zugrunde, ein Verfahren zum Abtasten mehrerer Fotografien, zum Erkennen der Anzahl und der Schräglage von Fotografien und zum Beseitigen von Randfehlern durch Ausschneiden des Bildes bereitzustellen.
Diese Aufgabe wird duch ein Verfahren zum Abtasten und Erkennen mehrerer Fotografien und zum Beseitigen von Randfehlern nach Anspruch 1 gelöst. Weitere Ausgestaltungen der Erfindung ergeben sich aus den Unteransprüchen.
Gemäß einem Ausführungsbeispiel der vorliegenden Erfindung wird eine Vielzahl von Fotografien auf das Vorlagenglas eines Scanners gelegt. Die Fotografien werden mit geringer Auflösung abgetastet, um eine Vielzahl von Bildern mit geringer Auflösung zu erzeugen. Es wird eine Vielzahl von Vielecken hergestellt, von denen jedes mindestens ein Bild mit geringer Auflösung enthält. Eine Anzahl von Vielecken wird bestimmt und mit der Anzahl von Fotografien verglichen. Ist die Zahl der Vielecke kleiner als die Zahl der Fotografien, werden die Fotografien neu positioniert, um einander überlagernde Fotografien zu trennen, und die Abtastung mit geringer Auflösung wird wiederholt. Für jede der Fotografien wird die Position und Schräglage bestimmt. Eine erste Fotografie wird ausgewählt und mit hoher Auflösung abgetastet, um ein Bild mit hoher Auflösung zu erzeugen. Das Bild mit hoher Auflösung wird gerade ausgerichtet, und es wird ein Bildausschnitt gewählt, um die Randfehler zu beseitigen.
Die Erfindung wird im folgenden anhand eines in der Zeichnung dargestellten Ausführungsbeispiels näher erläutert.
Es zeigen
1 ein Blockdiagramm eines Systems nach dem Stand der Technik zum Abtasten von Fotografien.
2 ein Blockdiagramm eines Systems nach dem Stand der Technik zur Darstellung von Randfehlern.
3 ein Blockdiagramm eines Systems nach dem Stand der Technik zur Darstellung einer Fotografie in Schräglage, eines abgetasteten Bildes und resultierender Randfehler auf der gedruckten Fotografie.
4 ein Blockdiagramm eines erfindungsgemäßen Systems zum automatischen Erkennen der Position einer Fotografie und der Korrektur des Formats und der Schräglage sowie zum Beseitigen von Fehlern.
5 eine schematische Darstellung mehrerer Fotografien auf einem Scanner-Vorlagenglas.
6 ein Blockdiagramm eines Systems zum Erkennen von Fotografien.
7 ein Blockdiagramm eines Systems zur Schwellenwertberechnung eines Bildes.
8 eine Tabelle zum Berechnen der Gradientenstärke.
9 ein Ablaufdiagramm zur Extraktion von Vieleckkonturen.
10 ein Ablaufdiagramm eines Konturenpixel-Erkennungsverfahrens, das in dem bevorzugten Verfahren dieser Erfindung zum Einsatz kommt.
11A, 11B und 11C Diagramme zur Darstellung von Beispielen zur Erzeugung einer Transformationstabelle aus einem 3×3-Bitmap-Muster, einer Umsetzung eines 3×3-Bitmap-Musters in einen Eintrag für die Trans formationstabelle und zur Erzeugung von Befehlen unter Benutzung der Transformationstabelle.
12A–12H Definitionen für acht Detektoren des linken Randes, wobei 0 = weiß, 1 = schwarz und X = irrelevant.
13A–13H Definitionen für acht Detektoren des rechten Randes, wobei 0 = weiß, 1 = schwarz und X = irrelevant.
14 Veranschaulichung in einer 3×3-Matrix-Form der aus den Randkombinationen nach den Regeln aus Tabelle 1 resultierenden Randmuster;
15A–15D Beispiele der Randmusterbefehle, die nach den Regeln aus Tabelle 1 erzeugt worden sind;
16A und 16B einen richtungsbestimmenden Kurvencode und ein Beispiel zur Umsetzung der Kurvencodes in entsprechende Vieleckvektoren;
17 eine schematische Darstellung einer Fotografie in Schräglage auf einem Scanner-Vorlagenglas.
18 ein Diagramm zur Berechnung einer Positionsgröße und eines Schräglagenwinkels einer Fotografie;
19 ein Diagramm zum Erkennen eines Schräglagenwinkels, des oberen Randes und des unteren Randes einer Fotografie;
20 ein Diagramm zur Darstellung einer Sammlung der obersten Schnittpunkte und der untersten Schnittpunkte;
21 ein Histogramm der vertikalen Abstände benachbarter Schnittpunkte;
22 ein Diagramm zur Darstellung der ganz linken Schnittpunkte und der ganz rechten Schnittpunkte;
23 ein Ablaufdiagramm zur schematischen Darstellung des Erkennungsvorgangs für den linken und rechten Rand einer Fotografie;
24 schematische Darstellung der Verfahren zur Schräglagenbeseitigung und zur Bildung des Bildausschnitts.
Zum leichteren Verständnis wurden in den Zeichnungen für gleiche Teile gleiche Bezugsziffern benutzt.
Bezugnehmend auf 4 werden die Hauptkomponenten und Verarbeitungsstufen eines Systems 30 zum Erkennen und Korrigieren der Schräglage von Fotografien in Form eines Blockdiagramms gezeigt. Die in jedem der Blöcke durchgeführten Arbeitsschritte werden nachfolgend detaillierter unter Bezug auf die Figuren erörtert.
Eine Anzahl abzutastender Fotografieren wird in Block 32 auf das Vorlagenglas eines Scanners gelegt. In Block 34 werden die Fotografien mit niedriger Auflösung abgetastet, in Block 36 werden die Fotografien erkannt, und in Block 38 wird die Anzahl der Fotografien bestimmt. In Block 40 wird ermittelt, ob sich Fotografien überlagern. Falls dies der Fall ist, wird in Block 42 der Benutzer aufgefordert, die Überlagerung zu korrigieren und die Fotografien neu zu positionieren. Wenn festgestellt wird, daß keine Überlagerungen vorliegen, wird das Ergebnis der Fotografieerkennung in Block 44 an einem Berührungsbildschirm (Touchscreen) angezeigt. Der Benutzer wählt in Block 46 eine gewünschte Fotografie durch Betätigen des Berührungsbildschirms aus. Die Zuordnungskoordinaten für die gewünschte Fotografie werden in Block 48 berechnet, und in Block 50 werden die gewünschten Fotografien noch einmal mit höherer Auflösung abgetastet. Das digitalisierte Bild wird in Block 52 gerade ausgerichtet, und die Randfehler werden in Block 54 beseitigt. Die Fotografie wird dann in Block 56 gedruckt oder gespeichert.
5 zeigt eine Gruppe von Fotografien 12, die beliebig ohne Berücksichtigung der oberen und seitlichen Anlageschiene 16 bzw. 18 oder des Ursprungspunktes 19 auf das Scanner-Vorlagenglas 14 gelegt wurden. Die gesamte Fläche des Scanner-Vorlagenglases 14 wird mit niedriger Auflösung, beispielsweise mit 90 dpi (Dots per Inch/Punkte pro Zoll) abgetastet, wodurch ein Graustufenbild niedriger Auflösung hergestellt wird.
Die Erkennung der Fotografien wird detaillierter in 6 gezeigt. Das Graustufenbild niedriger Auflösung 58 wird einer nachfolgend detaillierter erläuterten Schwellenwertoperation 60 unterzogen, wodurch ein binäres Bild 61 entsteht. Anschließend wird ein Konturenvektorisierungsprozeß 70 durchgeführt, womit die Anzahl der Fotografien 38 ermittelt wird. Die Lage, die Schräglage, die Breite und die Höhe jeder Fotografie werden in Block 78 erkannt.
Die Umwandlung eines Graustufenbildes in ein binäres Bild, also die sogenannte Schwellenwertoperation, wird in 7 gezeigt. In Block 62 wird jede Pixelintensität zwischen einem Wert von 0 und 255 ermittelt. Die Intensität wird dann mit einem vorgegebenen Wert IT verglichen, beispielsweise 230. Falls die Intensität kleiner als der Wert IT ist, wird das Pixel als ”schwarz” erkannt.
Falls die Intensität größer als der Wert IT ist, wird die Gradientenstärke für das Pixel in Block 64 berechnet. Die Gradientenstärke für das Pixel (i, j) wird unter Verwendung des sogenannten ”Sobel”-Gradientenoperators in einem Fenster aus Pixeln ermittelt, das um Pixel (i, j) gemäß 8 mittig angeordnet ist. Matrix 80 ist ein 3×3 Fenster mit Pixel (i, j) im Zentrum. Wie durch die Gleichungen (1)–(3) nachfolgend bestimmt, beruht der Sobel-Operator auf der Berechnung der horizontalen und vertikalen Pixelintensitäts-Gradienten GX(i, j) bzw. GY(i, j), und für jede Pixelposition (i, j) wird die Gradientenstärke G(i, j) als eine absolute Summe aus GX(i, j) und GY(i, j) gebildet: GX(i, j) = L(i + 1, j – 1) + 2L(l + 1, j) + L(i + 1, j + 1) –L(i – 1, j – 1) – 2L(i – 1, j) – L(i – 1, j + 1) (1) GY(i, j) = L(i – 1, j + 1) + 2L(i, j + 1) + L(i + 1, j + 1) –L(i – 1, j – 1) – 2L(i, j – 1) – L(i + 1, j – 1) (2) G(i, j) = |GX(i, j)| + |GY(i, j)| (3)wobei: G(i, j) die Gradientenstärke an Pixelposition (i, j) ist. Bezugnehmend auf 7 wird in Block 66 der Wert G(i, j) mit einer Konstanten GT verglichen, beispielsweise mit dem Wert 50. Wenn der Wert von G(i, j) größer als GT ist, wird das Pixel als schwarz interpretiert. Dieser Prozeß wird für jedes Pixel durchgeführt.
Der Konturenvektorisierungsprozeß 70 wird detailliert unter Bezug auf 9 beschrieben. Das binäre Bild 61 wird verarbeitet, um Konturenpixel zu erkennen und Pixelwerte gemäß vorgegebenen Umwandlungswerten zuzuweisen. Die Zuweisungsfunktion, dargestellt durch Block 90, wird unter Verwendung eines Fensters von 3×3 Pixeln implementiert, das über das binäre Bild jeweils Pixelspalte um Pixelspalte durchlaufen wird. Die die Bildkonturen darstellenden Pixel werden in Block 92 in Vektoren umgewandelt. Die Vektorsegmente werden an Block 94 übergeben. In Block 94 werden die Vektoren jeweils an den Enden zu einem oder mehreren Vielecken zusammengesetzt, die die Konturen des abgetasteten Bildes darstellen. Zusammenfassend gesagt setzt der zuvor beschriebene Vorgang, die sogenannte Konturenvektorisierung, ein binäres Bild in eine Ansammlung einfacher Vielecke um, die in einem fotografischen Erkennungssystem oder in einer fotografischen Erkennungstechnik, etwa der Schräglagenerkennung, oder der Linienerkennung oder in den Bildauszählungstechniken verwertbar sind.
Bezugnehmend auf 10 werden die von Block 90 aus 9 zur Konturenpixelerkennung durchgeführten Funktionen detaillierter veranschaulicht. Das bevorzugte Verfahren zum Erkennen eines Konturenpixels übergibt eine Bitmap aus 3×3 Pixeln, die durch Abtastung einer Fotografie erzeugt wurde, wobei die Ausgabe der Abtastfunktion das zuvor besprochene binäre Bild 61 ist. Die 3×3-Bitmap stellt die neun Pixelwerte dar, die innerhalb eines Fensters aus 3×3 Pixeln liegen, und zwar zu einem bestimmten Zeitpunkt, während das Fenster über einer Fotografie abgetastet wird. Wie durch den Block 102 dargestellt, wird jede 3×3-Bitmap zu einer ganzen Zahl im Bereich von 0–511 codiert. Die resultierenden Zahlen werden als Eingaben für eine Transformationstabelle 104 benutzt. Die Transfor mationstabellentechnik wird aufgrund ihrer rechnerischen Effizienz bevorzugt. Die Transformationstabelle gibt ”Randmusterbefehle” aus, deren Einzelheiten nachfolgend beschrieben werden. Diese Befehle werden dem Block 106 übergeben, der das Extrahieren der Konturenpixel darstellt durch Ausführen der Randmusterbefehle in einer geordneten Reihenfolge. Jedes ausgegebene Konturenpixel wird einer von drei Klassen zugewiesen: ein Maximalpunkt, ein Minimalpunkt oder ein Randpunkt.
Die Details der Erfindung in bezug auf die aus der 3×3-Bitmap gebildeten und ausgegebenen Randmusterbefehle werden nachfolgend unter Bezug auf 11A–11C angesprochen. In 11A wird das Fenster aus 3×3 Pixeln jetzt in Form von neun Zellen dargestellt, die die Buchstaben A bis I tragen. Bekanntlich kann in einem binären System ein Bit innerhalb einer Zelle entweder den Wert 1 oder 0 annehmen. Dies zeigt das Beispiel in 11B. Die Bits A bis I sind in einer bestimmten Reihenfolge derart angeordnet, daß sie eine ganze Zahl aus 9 Bits bilden. Wie zuvor erwähnt, kann die ganze 9-Bit-Zahl einen Wert zwischen 0 und 511 annehmen. Diese ganze Zahl dient dann als Eingabenummer zur Adressierung der Transformationstabelle 104, wie in 11C gezeigt, und zur Ausgabe der zugeordneten Randmusterbefehle.
Bezugnehmend auf 12A bis 12H werden die das Erkennen von acht linken Rändern verwendeten Definitionen zum Bestimmen der Randtypen L0 bis L7 verwendet. In diesen Fig. stellt der Wert 0 einen weißen Punkt dar, der Wert 1 stellt einen schwarzen Punkt dar, und ein x stellt einen Punkt dar, der entweder weiß oder schwarz sein kann, wobei das für das System jedoch unerheblich ist. In bezug auf die 3×3-Matrix aus 12A ist zu sehen, daß zwei benachbarte Bits 1 horizontal und parallel zu zwei benachbarten Bits 0 liegen. Die durch dieses Bitmuster dargestellte Randausrichtung ist bestimmungsgemäß horizontal und erstreckt sich nach links. Zum besseren Verständnis werden die Randausrichtungen durch einen Pfeil dargestellt, wobei die Position von Bit 0 (weiße Punkte) die Richtung der Randausrichtungspfeile steuert. Der Randtyp L4 ist mit dem Randtyp L0 identisch, jedoch derart gekippt, daß der Pfeil in Gegenrichtung horizontal verläuft, und daß die Bits 0 im Fenster von 12A unter den Bits 1 angeordnet sind, während in dem Fenster aus 12E die Bits 0 über den Bits 1 angeordnet sind.
Gleiches gilt für die vertikalen Randtypen L2 und L6 sowie für die schrägen (45 Grad) Randtypen L1, L5, L3 und L7. Die 13A bis 13H setzen diese Definitionen zum Erkennen von acht rechten Rändern fort, die die Randtypen R0 bis R7 darstellen.

Tabelle 1 zeigt die Vorlagenbefehle, die für jede Randtypenkombination verwendet werden und weist jeder Kombination eine numerierte Regel zu. Jede numerierte Regel bezeichnet also eine bestimmte Kombination. Tabelle 1

Regel	Randtypenkombination	Entsprechende Randmusterbefehle
Nr. 1	Li oder Ri (i = 0, 1, 2, 3)	i (einen Kurvencodebefehl hinzufügen)
Nr. 2	Li und Ri (i = 0, 1, 2, 3)	i, i (zwei identische Kurvencodebefehle hinzufügen)
Nr. 3	Li und Rj (i < 4, j < 4)	i, j, 6 (Befehle zum Beseitigen eines äußeren Konturen-Minimalpunktes)
Nr. 4	Li und Rj (i = 0, j = 3)	0, 3, 6 (Befehle zum Beseitigen eines inneren Konturen-Minimalpunktes)
Nr. 5	Li und Rj (i = 0, j = 3)	1, 3, 6 (Befehle zum Beseitigen eines inneren Konturen-Minimalpunktes)
Nr. 6	Li und Rj (i > 4, j > 4, j > i)	4 (Befehl zum Hinzufügen eines neuen äußeren Konturen-Maximalpunktes)
Nr. 7	Li und Rj (i = 7, j = 5)	5 (Befehl zum Hinzufügen eines neuen inneren Konturen-Maximalpunktes)
Nr. 8	Li und Rj (i = 7, j = 4)	5 (Befehl zum Hinzufügen eines neuen inneren Konturen-Maximalpunktes)

14 zeigt die aus den Randkombinationen gemäß den Regeln aus Tabelle 1 resultierenden Randmuster.

Tabelle 2 zeigt die Beziehung zwischen einer bestimmten 3×3-Bitmap und deren zugehörigen Eintragsnummer. Die Eintragsnummer wird gemäß dem zuvor in 13B dargestellten Verfahren erzeugt. Tabelle 2 zeigt die Randmusterbefehle, die aus der Transformationstabelle 24 ausgegeben werden, wenn die entsprechende Eintragsnummer als Adresse an diese Transformationstabelle übergeben wird. Es ist zudem möglich, daß einer Anzahl von Bitmap-Mustern keine Randmusterbefehle zugewiesen sind, während anderen Bitmap-Mustern mehrere zugewiesen sind. Wenn beispielsweise in Tabelle 2 die mittlere Zelle der 3×3-Matrix den Wert 1 hat und mindestens eine der umgebenden Zellen den Wert 0 hat, dann wird ein Randmusterbefehl zugewiesen, ansonsten wird kein Randmusterbefehl zugewiesen. Tabelle 2

3×3-Bitmap-Muster	Eintragsnummer	Randmusterbefehl
000
000	0	kein Wert
000

000
000	1	kein Wert
001
...	...	...
000
010	21	4, 5
101
...	...	...
000
010	23	4
111
...	...	...
101
110	368	0, 1, 3, 6, 3, 6
000
...	...	...
110
110	437	5, 2
101
...	...	...
111
111	511	kein Wert
111

Die Vorlagen aus 15A–15D stellen vier Bitmuster dar, die den Tabelleneintragsnummern 373, 124, 151 und 368 entsprechen, und zwar gemäß dem Bitzuweisungsverfahren aus 11A und 11B. Jedes Randmuster wird mit den acht Kombinationsregeln für linke und rechte Randerkennung verglichen, um zu bestimmen, welche Randmusterbefehle für das Randmuster gelten. Definitionen der Randmusterbefehle

0	Kurvencode 0 hinzufügen
1	Kurvencode 1 hinzufügen
2	Kurvencode 2 hinzufügen
3	Kurvencode 3 hinzufügen
4	einen neuen äußeren Maximalkonturenpunkt anlegen
5	einen neuen äußeren Maximalkonturenpunkt anlegen
6	zwei Kurvencodes verknüpfen

Die Vorlage aus 15A umfaßt beispielsweise drei Konturensegmente A, B und C, die durch die Regelnummern 2, 5 und 7 dargestellt werden. Demnach verweisen diese Regeln auf die Randmusterbefehle 1, 3, 6, 5 und 3. Der Randmusterbefehl 1 ist einem Konturensegment A zugeordnet, wobei bestimmt wird, daß dem Wert 1 der mittleren Zelle links oben ein Wert 1 benachbart ist. Beim Vergleichen dieser Beziehung mit der Bestimmung der Kurvencoderichtung, die durch Pfeile in 16B dargestellt wird, erhält man den Befehl 1. Nach der gleichen Logik resultiert aus dem Vorhandensein des Wertes 1 in der mittleren Zelle und in der rechten oberen Zelle der Befehl 3. Eine Überprüfung des Musters aus den Werten 1 in der Matrix aus 15A läßt erkennen, daß die Werte 1 in den oberen beiden Reihen der Matrix eine Verknüpfung der Kurvencodes 1 und 3 darstellen. Aus einer derartigen Verknüpfung resultiert der Befehl 6. Eine Überprüfung der dritten Reihe der Zellwerte zeigt einen neuen inneren Maximal-Konturenpunkt entsprechend einem Konturensegment C, woraus der Befehl 5 resultiert. Aus einer Überprüfung der rechten Spalte von Zellwerten resultiert die Bestimmung des Konturensegments B. Ausgehend von dem Wert 1 der mittleren Zelle wird abgeleitet, daß der zugehörige Kurvencode den Wert 3 hat.
Jedes abgetastete binäre Bild weist eine Anzahl von Pixeln auf, die Kanten und/oder Linien bilden, die einem Randtyp zugeordnet sind (L0–L7; R0–R7). Diese Identifikation bezieht sich auf die Richtung eines Vektorsegments. Nach einer gegebenen Regel wird jedes Vektorsegment mit einem anderen Vektorsegment entweder im Uhrzeigersinn oder im Gegenuhrzeigersinn verbunden, abhängig davon, ob die Vektorsegmente den Innenrand eines Objekts oder den Außenrand eines Objekts ausmachen. Ein Beispiel einer Zeichenfolge eines Kurvencodes, die die verbundenen Vektorsegmente darstellt, wird in 16A gezeigt. Die dargestellte Kurvencode-Zeichenfolge ist 212121 122221 112111 33333. Wenn man den Kurvencode mit den in 16A dargestellten Vektoren vergleicht und die Richtungspfeile aus 16B berücksichtigt, ist zu erkennen, daß die erste Ziffer 2 der Kurvencodes zu einem vertikalen Vektorelement e führt, das mit einem Vektorelement f verbunden ist, das durch die zweite Ziffer 1 des Kurvencodes dargestellt wird, und das in einem Winkel von 45 Grad verläuft, der durch den Vektor 1 aus 16B dargestellt wird. Das gleiche gilt sinngemäß für die Vektorelemente g bis j. An diesem Punkt wird ein Liniensegment D durch eine gerade Linie zwischen den beiden Endpunkten der verbundenen Vektorelemente gebildet.
Im nächsten Schritt wird die Anzahl der erkannten Fotografien ermittelt, wie in Block 38 aus 6 gezeigt. Nach der Konturenvektorisierung wird jeder Umriß der Objekte in dem binären Bild verfolgt und durch ein Vieleck dargestellt. Jeder Vektor wird gemäß dem im vorherigen Abschnitt beschriebenen Prozeß durch die x- und y-Koordinaten der Endpunkte dargestellt. Die Grenzkoordinaten, Breite und Höhe jedes Vielecks (Objektumriß) werden anhand der Scheitelpunktkoordinaten (Endpunkte der Vektoren) des Vielecks berechnet. Das Erkennen eines fotografischen Vielecks wird durch Gruppierung der Vielecke erleichtert. Das größte Vieleck der sich überlagernden Vielecke (kleinere Vielecke, die vollständig in den größeren Vielecken enthalten sind) wird dann als Kandidat für eine Fotografie gekennzeichnet und identifiziert. Beim Vergleich der Größe der Vieleckkandidaten werden die größten M Vieleckkandidaten als die äußersten Umrisse der gewünschten Fotografien betrachtet, wobei P die erwartete Anzahl von Fotografien in einer Abtastung ist und vom Benutzer eingegeben wird. Wenn die erkannte Anzahl von Fotografien M kleiner als die Anzahl der vom Benutzer eingegebenen Fotografienanzahl P ist, werden einige Fotografien auf dem Scanner überlagert, und die Fotografien müssen neu positioniert werden. Jedes als Fotografie erkannte Vieleck wird einer weiteren Analyse zum Berechnen der Schräglage und Position unterzogen.
In 6 zeigt Block 78 das Erkennen von Position, Schräglage, Breite und Höhe jedes Fotos. 17 zeigt schematisch einen Bildbereich 82, der einer auf dem Scanner-Vorlagenglas 14 erkannten Fotografie entspricht.
18 zeigt ein Blockdiagramm zum Berechnen der fotografischen Abmessungen und der Schräglage jedes Vielecks. Hier wird vorausgesetzt, daß es sich um eine rechteckige Fotografie handelt. Das Blockdiagramm beginnt mit einem Vieleck. Durch Verarbeiten des Vielecks, das detaillierter in 20 gezeigt wird, werden eine obere Randlinie 92 und eine untere Randlinie 93 erkannt. Die Neigung der oberen Randlinie wird als Schräglage der Fotografie interpretiert. Die linke Randlinie 94 und die rechte Randlinie 95 des Vielecks werden ebenfalls erkannt. Die extrahierten vier geraden Randlinien werden dazu verwendet, eine rechteckige Form entsprechend der gewählten Fotografie aufzubauen. Der linke obere Eckpunkt 96, der als Ursprung der Fotografie definiert ist, wird berechnet, indem man den Schnittpunkt der oberen Randlinie 92 mit der linken Randlinie 94 ermittelt. Der rechte obere Eckpunkt 97 wird berechnet, indem man einen Schnittpunkt der oberen Randlinie 92 mit der rechten Randlinie 95 ermittelt. Der linke untere Eckpunkt wird berechnet, indem man einen Schnittpunkt der linken Randlinie 94 mit der unteren Randlinie 93 ermittelt. Die Breite der Fotografie ist der Abstand zwischen dem linken oberen Eckpunkt 96 und dem rechten oberen Eckpunkt 97. Die Höhe der Fotografie ist der Abstand zwischen dem linken oberen Eckpunkt 96 und dem linken unteren Eckpunkt 98. Die Berechnung der oberen und unteren Randlinie wird in 19 beschrieben. Die Berechnung der linken und rechten Randlinie wird in 23 beschrieben.
20 zeigt ein Beispiel eines fotografischen Vielecks, dessen Schräglage einen unbekannten Winkel aufweist. Es wird eine Reihe aus gleich beabstandeten vertikalen Linien mit Abstand Dx aufgebaut. Es werden die Punkte ermittelt, an denen vertikale Linien 90 das Vieleck schneiden. Die Punkte mit den kleinsten und größten Werten von Y werden aufgezeichnet. Das Paar benachbarter Punkte, die die Anforderung erfüllen, daß deren Abstand (Dy) in vertikaler Richtung größer als deren Abstand (Dx) in horizontaler Richtung ist, werden aus den beiden Punktmengen gelöscht.
Als nächstes werden zwei Histogramme der vertikalen Abstände benachbarter Punkte berechnet, nämlich Histogramm (Ht(Dy)) an den oberen Schnittpunkten und Histogramm (Hb(Dy)) an den unteren Schnittpunkten. Die beiden Histogramme werden mit Mt bzw. Mb bezeichnet, wie in 21 gezeigt. Um die Ermittlung der Schräglage weiter zu verfeinern, werden die Punkte, die außerhalb des Bereichs von Mt+/–K bzw. Mb+/–K fallen, beseitigt. Nach dem Datenverfeinerungsprozeß erfolgt die Berechnung der Korrelationskoeffizienten Ct und Cb der verbleibenden oberen Schnittpunkte und der verbleibenden unteren Schnittpunkte zur Bewertung der Kolinearität der Punkte. Die Korrelationskoeffizienten werden dann folgendermaßen berechnet.
Die Schnittpunkte zwischen den Abtastlinien und der oberen oder unteren Linie des Vielecks sind (x_i, y_i), wobei i = 1, ...., N, und N ist die Anzahl der Schnittpunkte.
Der Korrelationskoeffizient (r_xy) ist bestimmt durch
wobei
Der Wert des Korrelationskoeffizienten liegt definitionsgemäß zwischen null und eins. Wenn der Korrelationskoeffizient nahe eins ist, weist dies darauf hin, daß diese Punkte kolinear sind, und die lineare Fehlerquadratmethode wird auf diese Punkte angewandt. Der Drehwinkel θ_S wird aus der Steigung (θ_S = b) der eingepaßten Geraden y = a + bx gelesen, wobei:
Der Drehwinkel des Vielecks wird als Schräglage der abgetasteten Fotografien genommen.
Da angenommen wurde, daß die Form der Fotografie rechteckig ist, müssen die obere und die untere Randlinie parallel zueinander verlaufen. Bei der Bewertung der Kolinearität der Punkte wird daher der größere Wert (Cm) der beiden Korrelationskoeffizienten Ct und Cb verwendet, wie in 19 und 23 gezeigt. Für den Fall, daß der Wert Cm kleiner als der vorgegebene Schwellenwert (TH) ist, weist dies darauf hin, daß entweder der horizontale Rand oder ein irregulärer Rand erkannt worden ist. Unter dieser Bedingung wird die Schräglage stets auf den Wert null gesetzt. Die Berechnung der linken und rechten Randlinien erfolgt ähnlich wie zuvor beschrieben. Das Blockdiagramm des Prozesses wird für horizontale Schnittpunkte wiederholt, wie in 22 gezeigt. 23 zeigt die Berechnungen der linken und rechten Randlinie.
Nachdem der Ursprungspunkt der Fotografie (linke obere Ecke) ermittelt worden ist, werden die Bildabmessungen (Breite und Höhe) und die Schräglage jeder er kannten Fotografie aus dem Abtastvorgang des gesamten Vorlagenglases mit niedriger Auflösung berechnet. Die Bildrandkoordinaten, wie in 17 gezeigt, werden neu justiert (maßstäblich hochgerechnet), und die Koordinaten eines gewünschten Abtastvorgangs mit hoher Auflösung eingepaßt.
Anschließend wird eine gewünschte Fotografie ausgewählt und eine Abtastung der ausgewählten Fotografie mit hoher Auflösung vorgenommen. Nach der Abtastung mit hoher Auflösung wird das hoch aufgelöste Bild mit einer bekannten, standardmäßigen, bilinearen Bildinterpolation gerade ausgerichtet.
24 zeigt schematisch das gerade Ausrichten und das Beseitigen von Randfehlern durch Auswahl eines Bildausschnitts. Nachdem das Bild gerade ausgerichtet worden ist, können die oberen, unteren und seitlichen Randfehler leicht beseitigt werden. Das Bild läßt sich dann auf einer Speicherplatte in bekannter Weise speichern oder als Fotografie ausdrucken.
Obwohl die Erfindung unter Bezug auf eine bevorzugte Ausführungsform beschrieben wurde, ist die Erfindung natürlich nicht auf diese Ausführungsform beschränkt, sondern kann zahlreichen, Fachleuten bekannten Änderungen und Abwandlungen unterzogen werden, ohne vom Gegenstand und Geltungsbereich der Erfindung abzuweichen.

11: Scanner
12: Fotografie
14: Scanner-Vorlagenglas
16: obere Anlageschiene
18: seitliche Anlageschiene
19: Ursprungspunkt
20: weisser Rand
21: Eingabeschirm (Touchscreen)
22: Randfehler
24: Transformationstabelle
30: Aufbau von Vektorsegmenten
32: Fotografien auf einem Scanner
34: Abtastung mit niedriger Auflösung
36: Erkennen von Fotografien
38: Bestimmen der Anzahl von Fotografien
40: Erkennen der Überlagerung
42: Meldung an den Benutzer
44: Anzeige von Fotografien
46: Auswahl über Berührungsbildschirm (Touchscreen)
48: Berechnung der Bitmap-Koordinaten
50: Abtastung mit hoher Auflösung
52: Bildausrichtung
54: Randfehlerbeseitigung
56: Ausdruck oder Speicherung des Bildes
58: Graustufenbild
60: Schwellenwertoperation
61: binäres Bild
62: ermittelte Pixelintensität
64: Berechnung der Gradientenstärke
66: ermittelte Gradationsschwelle
70: Konturenvektorisierung
78: Ermittlung von Schräglage, Position, Breite und Höhe der Fotografie
80: 3×3-Matrix
82: Bildbereich
90: Abtastlinien
92: obere Randlinie
93: untere Randlinie
94: linke Randlinie
95: rechte Randlinie
96: linker oberer Schnittpunkt
97: rechter oberer Schnittpunkt
98: unterer Schnittpunkt
99: unterer Schnittpunkt
102: Codierung
104: Transformationstabelle
106: Extrahieren von Konturenpixeln

Claims

Verfahren zum Abtasten und Erkennen mehrerer Fotografien und zum Beseitigen von Randfehlern mit folgenden Schritten: Anordnen einer Vielzahl von Fotografien (12) auf einem Scanner (11); Abtasten mit niedriger Auflösung, um eine Vielzahl niedrig aufgelöster Bilder zu erzeugen; Herstellen einer Vielzahl von Vielecken, wobei jedes Vieleck mindestens eines der niedrig aufgelösten Bilder enthält; Ermitteln einer Anzahl von Vielecken; Vergleichen dieser ermittelten Anzahl von Vielecken mit der Anzahl der Fotografien (12), und wenn die Anzahl der Vielecke kleiner als die Anzahl der Fotografien ist, Neupositionieren sich überlagernder Fotografien (12) und Wiederholen der Abtastung mit niedriger Auflösung sowie der nachfolgenden Schritte; Bestimmen der Schräglage und Position jeder Fotografie; Auswählen einer ersten Fotografie; Abtasten dieser ersten Fotografie mit hoher Auflösung, um ein Bild mit hoher Auflösung zu erzeugen; gerades Ausrichten des Bildes mit hoher Auflösung und Ausschneiden des Bildes mit hoher Auflösung, um die Randfehler zu beseitigen.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß Bilder mit niedriger Auflösung vor Herstellen der Vielzahl von Vielecken in binäre Bilder umgesetzt werden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Anzahl von Vielecken dadurch ermittelt wird, daß kleinere Vielecke, die innerhalb der Grenzen eines größeren Vielecks passen, als ein einzelnes fotografisches Vieleck gruppiert werden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Position der ersten Fotografie vor dem Bestimmen der Schräglage bestimmt wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß Höhe und Breite der Fotografie vor Bestimmen der Schräglage bestimmt werden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das ausgeschnittene Bild mit hoher Auflösung auf einer Festplatte gespeichert wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das ausgeschnittene Bild mit hoher Auflösung gedruckt wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß eine zweite Fotografie (12) nach Ausschneiden des Bildes mit hoher Auflösung ausgewählt wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Bilder an einem Berührungsbildschirm (21) angezeigt werden.
Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß die gewünschte Fotografie durch Berühren des Berührungsbildschirms (21) ausgewählt wird.