DE60009810T2

DE60009810T2 - Antialiasing mit Abtastzeilen

Info

Publication number: DE60009810T2
Application number: DE60009810T
Authority: DE
Inventors: Thouis R. Cambridge Jones; Ronald N. Cambridge Perry; Robert M. Bangor Kotredes
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1999-07-30
Filing date: 2000-05-26
Publication date: 2005-04-28
Anticipated expiration: 2020-05-27
Also published as: EP1074938A2; EP1074938A3; JP4597322B2; EP1074938B1; JP2001052160A; US6700672B1; DE60009810D1

Description

Gebiet der Erfindung
Die vorliegende Erfindung bezieht sich allgemein auf die Bildverarbeitung und insbesondere auf die Entfernung von Umfaltungswirkungen, die auftreten, wenn ein kontinuierliches Bild abgetastet wird.
Hintergrund der Erfindung
Es gibt eine große Verschiedenheit von Computeranwendungen, die Bilder erzeugen. Diese Anwendungen enthalten Spiele, graphische Entwürfe, Animation, Simulation, Visualisierung, Modellierung und dergleichen. Bei diesen Anwendungen sollten die erzeugten Bilder so realistisch wie möglich sein.
In der Computergraphik wird ein erzeugtes Bild dargestellt als eine regelmäßige Anordnung von diskreten Abtastungen eines kontinuierlichen Bildes. Dieses "diskrete Bild" ist ein Ergebnis der Abtastung des kontinuierlichen Bildes mit einer festen und endlichen Geschwindigkeit. Die individuellen Abtastpunkte werden als Pixel bezeichnet. Es ist kritisch, sich zu erinnern, dass ein Pixel ein Abtastpunkt ist, nicht ein rechteckiger Bereich in dem diskreten Bild.
Da die Abtastgeschwindigkeit endlich ist, können in dem kontinuierlichen Bild vorhandene Hochfrequenzen als nicht korrekte Niedrigfrequenzen "umgefaltet" sein. Einige gemeinsame Merkmale in kontinuierlichen Bildern wie Kanten enthalten unendlich hohe Frequenzen, so dass jede endliche Abtastgeschwindigkeit ausnahmslos zur Umfaltung führt. Bei computererzeugten Bildern erscheint die Umfaltung als Treppenstufenkontur von Bildobjekten, d.h. sogenannte "Zappen". Andere Umfaltungswirkungen sind Moiré-Muster und das auflösen feiner Einzelheiten.
Die Anti-Umfaltung wird verwendet zum Verbessern des Erscheinens diskreter Bilder. Die Antiumfaltung wird erreicht durch Berechnen und Abtasten einer Faltung des kontinuierlichen Bildes durch ein frequenzbegrenzendes Filter. Die Pixel sind Abtastungen der gefilterten Version des kontinuierlichen Bildes. Es gibt zwei allgemeine Verfahren, die zum Berechnen der Abtastungen dieser Umfaltung im Stand der Technik verwendet werden: Bereichsabtastung und Punktabtastung.
Bereichsabtastungs-Anti-Umfaltung
Die Bereichsabtastungs-Anti-Umfaltung verwendet eine verarbeitete, aber noch kontinuierliche Form des kontinuierlichen Bildes, um die Faltung einer Anti-Umfaltungs-Filterfunktion und dieses kontinuierliche Bild genau zu berechnen. Diese Umfaltung wird abgetastet, um einen Wert zu erzeugen, der zu verwenden ist, während ein Pixel in dem diskreten Bild bestimmt wird. Typischerweise ist die Filterfunktion ein Gauß'sches Filter mit einem Radius R. Der Radius definiert den "Fußabdruck" oder die "Stütze" des Filters.
Die verarbeitete Form des durch Bereichsabtastung verwendeten, kontinuierlichen Bildes ist gewöhnlich ein Satz von Polygonen, der in dem Filterfußabdruck um jedes Pixel herum sichtbar ist. Leider ist in manchen Fällen das kontinuierliche Bild definiert durch eine dreidimensionale Szenenbeschreibung, enthaltend geometrische Objekte, die einander ausschließen oder einander kreuzen können. Diese Ausschlüsse und Kreuzungen machen es schwierig, das kontinuierliche Bild wirksam in eine Form zu verarbeiten, die für Bereichsabtastung geeignet ist, da sich komplizierte Formen aus der Interaktion selbst einfacher Objekte ergeben können.
Punktabtastungs-Anti-Umfaltung
Die Punktabtastungs-Anti-Umfaltung verwendet Viel-Punktabtaststellen in der Nähe eines Pixels. Das kontinuierliche Bild wird an Punkten ausgewertet, die den Pixelstellen entsprechen, und die sich ergebenden Werte werden entsprechend einer Gewichtungsfunktion in einem Versuch kombiniert, die Umfaltung des Filters mit dem kontinuierlichen Bild anzunähern. Die Punktabtastung ist das allgemeinste Verfahren, das für die Anti-Umfaltung verwendet wird, wegen seiner Einfachheit und der leichten Implementierung. Die Punktabtastung vereinfacht das Ausschlussproblem, das bei der Bereichsabtastung von dreidimensionalen Szenen auftritt, aber leidet an der langsamen Konvergenz zu der korrekten Lösung. Im allgemeinen sind N Punktabtastungen erforderlich, um den Wert eines Pixels mit einer Genauigkeit von 1/N zu berechnen. Da die Punktabtaststellen voneinander getrennt und nicht verbunden sind, können feine Einzelheiten bei der Abtastung vollständig fehlen. Folglich tragen die fehlenden Einzelheiten nicht zu dem diskreten Bild bei.
Kombinierte Punkt- und Bereichsabtastung
Das Bereichs- und das Punktabtastverfahren werden in Darstellungssystemen häufig kombiniert. Die Bereichsabtastung kann wirksam bei zweidimensionalen, abgetasteten Bildern angewendet werden, wie Strukturkarten, während die Punktabtastung im allgemeinen verwendet wird, um eine Anti-Umfaltung bei Kanten und Kreuzungen von Polygonen durchzuführen. Die Punktabtastung wird verwendet, um gewichtete Deckungswerte (WCV) für Polygone zu erzeugen, die innerhalb des Filterfußabdrucks einiger Pixel liegen, die dann mit diesem Pixel assoziiert werden. Eine WCV ist das Ergebnis der Faltung des sichtbaren Bereichs eine Polygons mit dem Anti-Umfaltfilter an einem Pixel, das den Farbbeitrag dieses Polygons zu der Farbe dieses Pixels wichtet. Ein Bereichsabtastverfahren wird verwendet, um Farben für die Polygone zu erzeugen, die auch mit diesem Pixel assoziiert sind. Die WCV und Farben, die mit diesem Pixel assoziiert sind, werden dann kombiniert, um die endgültige Farbe für das Pixel in dem diskreten Bild zu erzeugen.
Anderes Anti-Umfaltungsverfahren
Max beschreibt in "Anti-aliasing Scan-Line Data", IEEE Computer Graphics & Applications, 10(1): 18–30, Jan. 1990, ein hybrides Verfahren. Sein hybrides Verfahren ergibt eine kontinuierliche Anti-Umfaltung in einer Richtung durch Annäherung an die Bereichsabtas tung, während eine Superabtastung verwendet wird für die Anti-Umfaltung in der anderen Richtung. Kanten, die im wesentlichen parallel zu der kontinuierlichen Richtung verlaufen, werden weniger wirksam der Anti-Umfaltung unterzogen als Kanten, die im wesentlichen senkrecht zu der kontinuierlichen Richtung verlaufen.
Demgemäß gibt es zahlreiche Mängel und Nachteile des Bereichs- und Punktabtastungs-Anti-Umfaltungsverfahrens nach dem Stand der Technik. Daher besteht eine Notwendigkeit, ein verbessertes Anti-Umfaltungsverfahren ohne eine große Speicherzunahme oder eine Abnahme der Zeichnungsgeschwindigkeit beim Erzeugen diskreter Bilder vorzusehen.
Zusammenfassung der Erfindung
Die Erfindung liefert ein Verfahren, das eine Filterfunktion verwendet, um ein einer Anti-Umfaltung unterzogenes, diskretes Bild zu erzeugen, das von einem kontinuierlichen Bild, enthaltend eine Kante, abgetastet wurde. Das Verfahren definiert eine Linienabtastung. Eine progressive Faltung wird von der Filterfunktion und der Linienabtastung abgeleitet, welche progressive Faltung ein kumulatives Integral der Filterfunktion von verschiedenen Abständen der Kante ist. Ein Pixel an einer vorbestimmten Stelle in dem diskreten Bild wird ausgewählt, und die Linienabtastung ist auf das ausgewählte Pixel zentriert orientiert. Ein Abstand wird von einem Punkt in dem kontinuierlichen Bild entsprechend dem ausgewählten Pixel zu der Kante entlang der orientierten Linienabtastung gemessen. Die progressive Faltung wird an dem gemessenen Abstand ausgewertet, um einen gewichteten Überdeckungswert zu erzeugen, und der gewichtete Überdeckungswert wird assoziiert mit dem Pixel für die An ti-Umfaltung des Pixels in dem diskreten Bild.
Bei einem Aspekt der Erfindung werden nur sichtbare Kanten der Anti-Umfaltung unterzogen, und nur Pixel mit einem vorbestimmten Abstand von der Kante werden betrachtet, z.B. wenn der Abstand geringer als oder gleich einer Länge der Linienabtastung ist.
Bei einem anderen Aspekt der Erfindung ist die Linienabtastung gerade, auf das Pixel zentriert, und im wesentlichen senkrecht zu der Kante.
Bei noch einem anderen Aspekt der Erfindung ist die Filterfunktion eine Gauß'sche Funktion. Die progressive Faltung kann durch eine kontinuierliche Funktion definiert werden, oder alternativ werden die Werte der progressiven Faltung in einer Tabelle für eine endliche Anzahl von Abständen gespeichert.
Bei noch einem anderen Aspekt der Erfindung werden mehrere Linienabtastungen für jedes Pixel definiert, und die gewichteten Überdeckungswerte der Linienabtastungen werden kombiniert, um einen kombinierten, gewichteten Überdeckungswert zu erzeugen, der mit dem Pixel assoziiert ist.
Kurzbeschreibung der Zeichnungen
1a bis 1e sind Diagramme eines Filterfußabdrucks für Linienabtastungen, die auf ein Pixel zentriert sind, bei verschiedenen Abständen zu einer Kante eines graphischen Objekts;
1f ist ein Diagramm einer Filterfunktion;
2 ist ein Diagramm einer progressiven Faltung;
3a ist ein Diagramm einer Linienabtastung, die zwei Kanten eines Objekts schneidet;
3b ist ein Diagramm, das Segmentinformationen zeigt;
3c ist ein Diagramm, das eine Differenz von zwei Auswertungen der progressiven Faltung zeigt;
3d bis 3f sind Diagramme der Differenz zwischen zwei Überdeckungsauswertungen;
4a bis 4c sind Diagramme der Linienabtastung, die Objekte ausschließt;
5a bis 5c sind Diagramme der Linienabtastung, die Objekte kreuzt;
6a bis 6b sind Diagramme einer Linienabtastung, die parallel zu einer Kante orientiert ist;
7a bis 7b sind Diagramme der Linienabtastung, die zwei orthogonale Linienabtastungen verwendet;
8 ist ein Diagramm der Linienabtastung von sichtbaren und nicht sichtbaren Kanten von aneinander grenzenden Objekten;
9 ist ein Diagramm der Linienabtastung von sichtbaren und nicht sichtbaren Kanten von okkludierenden Objekten;
10a bis 10b sind Diagramme des Gewichtens mehrerer Linienabtastungen für eine Linienabtastung gemäß einem normierten Kantenvektor;
11a bis 11b sind Diagramme der Linienabtastungs-Datenerzeugung an Pixelgitterpositionen;
12 ist ein Diagramm der Linienabtastung einer Grenzkurve mit einer Orientierung senkrecht zu einer tangentialen Richtung, und
13 ist ein Diagramm der Linienabtastung unter Verwendung eines Bildes niedriger Auflösung und der Kantenerfassung.
Detaillierte Beschreibung von bevorzugten Ausführungsbeispielen
Die vorliegende Erfindung verwendet Linienabtastungen oder Linienmuster, um ein verbessertes Verfahren für die Erzeugung gewichteter Überdeckungswerte (WCV) vorzusehen, die verwendet werden können für die Anti-Umfaltung eines diskreten Bildes. Die WCV sind das Ergebnis einer Faltung eines sichtbaren Teils eines Polygons mit einem Anti-Umfaltungsfilter bei einem Pixel, das den Farbbeitrag dieses Polygons zu der Farbe dieses Pixels gewichtet.
Die Linienabtastung gemäß der Erfindung liegt zwischen dem Bereichs- und dem Punktabtastverfahren nach dem Stand der Technik in Bezug auf die Wirksamkeit und die Genauigkeit. Das Linienabtastverfahren nach der vorliegenden Erfindung kann verwendet werden für die Berechnung von WCV anhand von Gestaltinformationen, d.h. Kanten, Okklusionen und Kreuzungen, und kann kombiniert werden mit den Bereichsabtastungen von Schatteninformationen, d.h. Farbe und Struktur, wie bei dem Stand der Technik. Daher ermöglicht die vorliegende Erfindung die Erzeugung von Anti- Umfaltungsbildern hoher Qualität.
Die der Linienabtastung zugrunde liegende Grundeinsicht beruht auf den folgenden Eigenschaften. Die Faltung eines endlichen Filters und einer geraden Kante kann wirksam und genau bestimmt werden, wenn die Kreuzung der Kante mit einer Linienabtastung zumindest dem Fußabdruck des Filters mit einer Orientierung im wesentlichen senkrecht zu dieser Kante überspannt. Zusätzlich sind die Okklusions- und Kreuzungsbestimmung bei Linienabtastungen viel einfacher durchzuführen als bei Bereichsabtastungen. Dies gilt, weil diese Interaktionen weniger komplizierte Grundelemente erzeugen. Zusätzlich können Okklusionen für große Abschnitte einer Linienabtastung mit einer einzigen Berechnung gelöst werden. Diese Eigenschaften geben der Linienabtastung eine bessere Konvergenz als der Punktabtastung und eine Genauigkeit ähnlich der der Bereichabtastung, aber zu geringeren Berechnungskosten.
Die wirkungsvolle Berechnung von Faltungen mit Linienabtastungen erfordert die Ableitung einer progressiven Faltung (PC) von der gewünschten Filterfunktion. Wenn die gewünschte Filterfunktion radial symmetrisch ist, dann reicht eine einzelne PC füralle Linienabtastorientierungen aus. Andernfalls muss eine PC für jede mögliche Linienabtastorientierung bestimmt werden, oder bei einer ausreichenden Anzahl von getrennten Orientierungen, um eine Interpolation an anderen Zwischenorientierungen zu ermöglichen. Die Bestimmung einer PC gemäß der Erfindung ist in den 1 und 2 gezeigt.
Wie schematisch in 1 gezeigt ist, befindet sich ein Pixel 100 in verschiedenen Abständen, z.B. –1,5; –0,8; 0,0; +0,8 und +1,5, von einer Kante 101 eines graphischen Objekts 104 mit einem schattierten Inneren. Ein Fußabdruck einer Filterfunktion, siehe 1f, der an den Pixel zentriert ist, ist durch einen Kreis 102 angezeigt. Der Fußabdruck ist die "Stütze" der Filterfunktion, d.h. der Bereich, in dem die Filterfunktion Werte hat, die nicht gleich Null sind.
Das Diagramm 103 in 1f ist eine beispielhafte, Gauß'sche Filterfunktion, die die von dem Filter erzeugten Werte darstellt, wobei die X-Achse den Abstand von dem Pixel und die Y-Achse die Intensität (I) der Funktion darstellen. Es ist darauf hinzuweisen, dass andere Filterfunktionen von der vorliegenden Erfindung verwendet werden können.
Das Pixel und die Kante sind in mehreren Abständen voneinander gezeigt. Das Liniensegment 105 stellt eine Linienabtastung gemäß der Erfindung dar. Vorzugsweise ist die Linienabtastung gerade und auf das Pixel zentriert; die Orientierung der Linienabtastung ist so gewählt, dass sie senkrecht zu der Kante 101 ist, und die Länge der Linienabtastung 105 überspannt zumindest den Durchmesser des Fußabdrucks 102.
Es ist darauf hinzuweisen, dass die Linienabtastung andere lineare Konfigurationen haben kann, z.B. einen Kreis, eine Bezier-Kurve usw. Es ist auch darauf hinzuweisen, dass die Linienabtastung andere Positionen, Längen und Orientierungen haben kann. Die Anordnung der Linienabtastung kann außerhalb der Mitte sein oder nahe des Pixels, wenn dies für die Berechnung vorteilhaft ist.
2 zeigt eine PC 200, die von der Filterfunktion 103 abgeleitet ist. Abstände für Pixel außerhalb des Objekts sind durch negative Zahlen angezeigt; der Abstand eines Pixels auf der Kante des Objekts ist Null, und Abstände für Pixel innerhalb des Objekts sind positiv. Die Abstände sind entlang der X-Achse 201 gezeigt. Die gewichteten Überdeckungswerte der PC sind entlang der Y-Achse 202. Die WCV sind in dem Bereich von 0,0 bis 1,0. Wenn sich das Pixel z.B. auf der Kante befindet, dann ist der WCV der PC gleich 0,5, wodurch die halbe Überdeckung des Filterfußabdrucks 102 durch die Kante 101 angezeigt wird. Wenn sich der Filterfußabdruck vollständig innerhalb des Objekts befindet, besteht eine vollständige Überdeckung, und es liegt keine Überdeckung vor, wenn der Filterfußabdruck vollständig außerhalb des Objekts. Der Wert der PC 200 nimmt von 0,5 auf 0 ab, wenn sich das Pixel von der Kante weg bewegt, und nimmt von 0,5 auf 1 zu, wenn sich das Pixel in der entgegengesetzten Richtung bewegt. Eine vollständige Überdeckung stellt den Bereich unter der Kurve 103 in 1f dar. Im wesentlichen drückt die progressive Faltung gemäß der Erfindung kumulative Integrale der Filterfunktion für verschiedene Abstände von der Kante aus.
Die von dem Filter 103 abgeleitete und mit der Kante 101 umgefaltete PC 200 kann wirkungsvoll ausgewertet werden. Wenn das Filter einfach ist, dann kann die PC 200 funktionsmäßig wie benötigt ausgewertet werden. Wenn das Filter komplex ist, kann ein Subsatz der Werte der PC 200 bei sich ändernden Abständen von der Kante vorberechnet und in einer Tabelle für die Interpolation bei Zwischenabständen gespeichert werden. In einer Tabellenform ist die PC durch den Abstand indexiert, und Zwischenwerte können interpoliert werden. Obgleich die PC 200 nach 2 WCV für alle möglichen Abstände zeigt, d.h. von negativer Unendlichkeit zu positiver Unendlichkeit, ist darauf hin zuweisen, dass bei einer praktischen Anwendung der WCV nur über einen sehr kleinen Bereich von Abständen variiert, d.h. –2,0 bis +2,0, wobei eine Einheit gleich dem Abstand zwischen Pixeln ist.
Wenn das Filter radial asymmetrisch ist, können die PC'en für jede Zeilenabtastorientierung erzeugt werden. Jedoch haben in der Praxis die am meisten verwendeten Filter eine einfache Struktur und sind radial symmetrisch, was die Tabellen überflüssig macht und ermöglicht, dass eine einzelne PC für alle Linienabtastorientierungen genügt.
Die 3a bis f zeigen, wie eine gewünschte Faltung eines Objekts und eine PC für ein gewünschtes Filter wirkungsvoll und genau mit einer Linienabtastung gemäß der Erfindung bestimmt werden können. Ein Objekt 300 hat Kanten a, b 301–302. Eine Linienabtastung 303 ist auf ein Pixel 304 zentriert, das sich zwischen den Kanten a, b 301–302 befindet. Die Zeilenabtastung 303 hat Endpunkte e₁ 305 und e₂ 306. Die gewünschte Faltung ist der WCV für das Objekt 300 an dem Pixel 304. Die Linienabtastung 303 überspannt den Filterfußabdruck 309. Wie gezeigt, ist die Linienabtastung 303 im wesentlichen senkrecht zu den mehreren Kanten a, b orientiert. Die Abstände d₁ 307 und d₂ 308 zeigen jeweils die relativen Abstände zwischen dem Pixel und den Kanten a und b entlang der Linienabtastung 303 an.
Das Diagramm 310 in 3b zeigt Segmentinformationen für die Kreuzung des Objekts 300 mit der Linienabtastung 303. Die relativen Positionen der Kantenkreuzungen entlang der Linienabtastung bestimmen ein Segment 320 auf der Linienabtastung, das durch die beiden Abstände d₁ und d₂ begrenzt ist. Die genaue Faltung des Inneren des Objekts 300 mit dem Filter 306, gezeigt in 3b, kann als die Differenz bei der Faltung des Filters mit der Kante b, wie in 3e gezeigt ist, und der Faltung des Filters mit der Kante a, wie in 3f gezeigt ist, ausgewertet werden. Wie in 3c gezeigt ist, ist diese Differenz äquivalent der Differenz 331 zwischen den Werten der PC 330, ausgewertet bei d₂ und d₁. Diese Differenz ist exakt der WCV für das Objekt 300 bei dem Pixel 304.
Die Erweiterung des in 3 gezeigten Verfahrens auf mehr als 2 Kanten ist für den Fachmann offensichtlich.
Die Okklusion und Kreuzung von mehreren Polygonen kann sehr komplexe Formen erzeugen, wenn einige Polygone teilweise einander okkludieren oder sich kreuzen. Dies gilt sogar bei einfachen Polygonen wie Dreiecken. Die Bestimmung der Anti-Umfaltungshaltung entlang einer Linienabtastung anstelle einer Bereichsabtastung nach dem Stand der Technik vereinfacht das Problem beträchtlich für die Okklusion, wie in den 4a bis 4c gezeigt ist, und für die Kreuzung, wie in den 5a bis 5c gezeigt ist.
In 4a okkludiert ein Polygon a 401 teilweise ein Polygon 402. 4b zeigt beispielhafte Tiefeninformationen (Z) 403 entlang einer Linienabtastung 404 für die Segmente, entsprechend den Polygonen a, b. Wo die Linienabtastung sowohl a als auch b überlappt, tritt eine Okklusion auf. Diese Okklusion kann gelöst werden durch Vergleich der Tiefeninformationen an allen Punkten auf der Linienabtastung und Zurückhalten nur der Informationen für das Segment mit der geringsten Tiefe an jedem Punkt, und Löschen der Informationen für das Segment mit der größten Tiefe an jedem Punkt. Entlang der Linienabtastungen kann die Okklusion für gesamte Abschnitte von Segmenten wirkungsvoll gelöst werden. Eine derartige Okklusion kann bestehende Segmente abschneiden oder teilen. 4c zeigt das Ergebnis der Okklusion von a und b entlang der Linienabtastung 404. Die Okklusion für einen gesamten Abschnitt 405 in 4b wurde gelöst durch selektives Zurückbehalten und Löschen, wobei der Rest 406 in 4c verbleibt.
5a zeigt Polygone a 501 und b 502, die einander kreuzen. 5b zeigt Tiefeninformationen (Z) 503 entlang einer Linienabtastung 504 für die Segmente entsprechend den Polygonen a, b. Die Kreuzung der beiden Polygone führt zu einer entsprechenden Kreuzung 505 in den Tiefeninformationen für die entsprechenden Segmente. Diese Kreuzung kann lokalisiert werden und zum Lösen der gegenseitigen Okklusion von a und b durch selektives Zurückhalten und Löschen auf der Grundlage von Tiefeninformationen, wie vorstehend beschrieben, verwendet werden. Die Kreuzung von Segmenten kann auch wie vorstehend bestehende Segmente abschneiden oder teilen. Das Ergebnis dieser Kreuzung und Okklusion ist in 5c gezeigt.
Die Linienabtastung ergibt eine genauere Bestimmung der Anti-Umfaltungs-Filterumfaltung als die Punktabtastung. Beispielsweise ergeben N Punktabtastungen eine Genauigkeit grob proportional zu 1/N. Eine senkrecht zu einer Kante orientierte Linienabtastung berechnet die Faltung für diese Kante mit perfekter Genauigkeit und mit angemessener Genauigkeit, wenn die Linienabtastung und die Kante im wesentlichen senkrecht zueinander orientiert sind.
Wenn die Linienabtastung und die Kante parallel zueinander orientiert sind, dann wirkt die Linienabtastung als eine Einzelpunktabtastung, wie in den 6a und 6b gezeigt ist. In 6a ist eine Linienabtastung 600 auf ein Pixel 603 zentriert und parallel zu einer Kante 601 eines Objekts 602 orientiert. Hier besteht keine Überdeckung zwischen der Linienabtastung und dem Objekt (WCV = 0). Eine leichte Änderung in der Position der Kante, d.h. sobald das Objekt die Linienabtastung überdeckt, bewirkt eine drastische Änderung in dem Erscheinen von keine Überdeckung zu volle Überdeckung (WCV = 1), wie in 6b gezeigt ist.
Aus diesem Grund ist es vorteilhaft, entweder mehrere Linienabtastungen mit unterschiedlichen Orientierungen zu nehmen und ihre sich ergebenden WCVe zu kombinieren oder die Orientierung von Linienabtastungen in Abhängigkeit von der Orientierung von Kanten in dem kontinuierlichen Bild zu wählen.
Die Verwendung von mehreren Linienabtastungen erfordert ein Verfahren zum Gewichten der Beiträge der individuellen Linienabtastungen. Ein Verfahren gewichtet die Beiträge gleichmäßig, wobei der Durchschnitt der Werte von den Linienabtastungen gebildet wird, um das Endergebnis zu erzeugen. Bessere Annäherungen der Faltung werden erzeugt durch Gewichten der Linienabtastungen auf der Grundlage einer Messung dahingehend, wie gut sie für die Abtastung der Kanten in dem darunter liegenden, kontinuierlichen Bild orientiert sind, wie nachfolgend beschrieben ist.
Es ist möglich, die Faltung mit ausreichender Genauigkeit für Kanten jeder Orientierung mit zwei Linien abtastungen, die senkrecht zueinander sind, zu bestimmen. Die Gewichte für den Beitrag jeder Abtastung können dann auf der Grundlage mehrerer Kriterien bestimmt werden. Die relative Orientierung jeder Kante und der Linienabtastungen, die diese Kante kreuzen, kann berücksichtigt werden. Die Anzahl von Kanten, die jede Linienabtastung kreuzen, kann ein Faktor sein. Die Varianz oder eine andere statistische Messung der sichtbaren Segmente der Linienabtastung kann verwendet werden.
In 7a sind zwei Linienabtastungen 701 und 702 für ein Pixel 709 senkrecht zueinander angeordnet. Die Linienabtastung 701 kreuzt teilweise ein Objekt 700, und die Linienabtastung 702 ist vollständig außerhalb des Objekts. Die Segmentinformationen entsprechend dem Objekt 700 für die Linienabtastungen 701 und 702 sind jeweils in den Diagrammen 704 und 705 gezeigt. In 7b hat sich das Objekt 700 relativ zu den Linienabtastungen 701 und 702 bewegt. Die Linienabtastung 702 ist vollständig innerhalb des Objekts 700, und ein größerer Teil der Linienabtastung kreuzt das Objekt 700.
Die jeweiligen Segmentinformationen sind in den Diagrammen 706 und 707 gezeigt. Die Kante 708 ist durch die Linienabtastung 701 wegen ihrer senkrechten Orientierung zu der Kante einer genaueren Anti-Umfaltung unterzogen. Die Linienabtastungen 701 und 702 berechnen zwei WCVe für das Objekt 700 bei dem Pixel 709. Da die Kante 708 durch die Linienabtastung 701 einer genaueren Anti-Umfaltung unterzogen wurde, sollte der berechnete WCV von der Linienabtastung 701 mehr zu dem kombinierten WCV für das Objekt 700 bei dem Pixel 709 beitragen als der durch die Linienabtastung 702 berechnete WCV.
Wie in 8 gezeigt ist, ist es nützlich, die Berücksichtigung von Abtastgewichten entlang einer Linieabtastung 803 beeinflussenden Kanten nur auf solche Kanten zu beschränken, die "sichtbar" sind.
Sichtbare Kanten 801 sind die Kanten, die von der Kante eines Polygons gebildet sind, das nicht (beispielsweise in der Farbe) einen anderen Polygon (der selben Farbe) angepasst ist, oder eine Okklusion oder eine Kreuzung. Eine Kante 802, die auftritt, wo zwei Polygone derselben Farbe sich vereinigen, ist kaum in dem erzeugten Bild sichtbar, und sie sollte daher als "nicht sichtbar" behandelt werden, um zu verhindern, dass solche Kanten die Gewichtigung von Linienabtastungen, die sie kreuzen, beeinflussen. Beispielsweise sollten bei einem Objekt, das aus mehreren aneinander grenzenden Polygonen besteht, die seine Silhouette bildenden Kanten einer Anti-Umfaltung gemäß der Orientierung dieser Silhouettenkanten unterzogen werden, ohne dass die inneren Kanten zwischen den Polygonen das Ergebnis beeinträchtigen.
9 zeigt ein Polygon a 901, das teilweise ein anderes Polygon b 902 überdeckt. Eine Kante 903 des Polygons 901 ist nicht einer Kante des Polygons 902 angepasst. Die Kante 903 ist in dem diskreten Bild sichtbar und sollte die Anti-Umfaltungsberechnung beeinflussen. Daher sollte die Kante 903 als eine sichtbare Kante für die Zwecke der Berechnung von Abtastgewichten unter Verwendung der Linienabtastung 904 behandelt werden.
10a zeigt, wie Gewichte für zwei senkrechte, achsenausgerichtete Linienabtastungen 1001 und 1002 nahe einer Kante 1003 eines Objekts 1000 bestimmt werden können. Hier ist die Orientierung der Kante 103 nicht senkrecht zu einer der Linienabtastungen 1001–1002. Ein entlang der Kante 1003 verlaufender Vektor kann berechnet werden. 10b zeigt den Kantenvektor 1004 für die Kante 1003, mit einer horizontalen Komponente V_x 1005 und einer vertikalen Komponente V_y 1006.
Das Verfahren bestimmt zuerst den normierten Vektor (V_nxV_ny) für jede sichtbare Kante, die eine der Linienabtastungen kreuzt. Dann wird für einen normierten Kantenvektor mit Komponenten (V_nxV_ny), V_nx ² zu dem Gesamtgewicht der vertikalen Abtastung addiert, und V_ny ² wird zu dem Gesamtgewicht der horizontalen Abtastung addiert. Die Quadrate der Werte der Komponenten werden verwendet, um den Gesamtbeitrag jeder Kante gleich 1 zu halten. Nachdem alle Beiträge der relevanten Kanten gewichtet wurden, können die relativen Gewichte der vertikalen und horizontalen Linienabtastung bestimmt werden, und die relativen Gewichte werden verwendet, um die WCVe der beiden Linienabtastungen zu mischen. Das Mischen kann jede geeignete Mischfunktion verwenden, wie lineares Mischen, kubisches Mischen oder die Auswahl des WCV mit dem größeren Gewicht.
Wie in 11a gezeigt ist, ist es möglich, herkömmliche Rastertechniken anzuwenden, um die Linienabtastauswertung für zwei senkrechte, achsenausgerichtete Linienabtastungen zu beschleunigten. In 11a ist es erwünscht, eine Abtastung bei dem Pixel 1101 eines Pixelgitters 1100 mit Linienabtastungen 1102 und 1103 durchzuführen. Wenn ein Anti-Umfaltungsfilter mit einem Radius gleich dem Abstand zwischen Pixeln verwendet wird, was eine übliche Wahl ist, können schnelle Rastertechniken, die gegenwärtig für die Punktabtastung verwendet werden, auch einge setzt werden, um Kantenabstandswerte an den Linienabtastungs-Endpunkten 1109 zu erzeugen, die genau auf Pixelgitterstellen liegen. Der Kantenabstandswert für einen Linienabtast-Endpunkt und eine Kante ist definiert als der kürzeste Abstand zwischen dem Linienabtast-Endpunkt und dieser Kante.
Wie in 11b gezeigt ist, werden die "ausgefüllten" Pixel 1104 verwendet, und die "offenen" Pixel 1105 werden für die Linienabtastungen 1102 und 1103 nicht verwendet. Die Pineda-Arithmetik kann verwendet werden, um wirkungsvoll die Kantenabstandswerte für Polygone in dem Bild an den Linienabtast-Endpunkten zu erzeugen, siehe Pineda "A Parallel Algorithm for Polygon Rasterization", Proceedings of SIGGRAPH, Computer Graphics, Band 22, Nummer 4, Seiten 17–20, 1988. Da diese Kantenabstandswerte in dem Bild linear variieren, können Segmente für Linienabtastungen wirkungsvoll erzeugt werden unter Verwendung grundlegender geometrischer oder algebraischer Verfahren (z.B. ähnliche Dreiecke), wobei nur die Kantenabstandswerte an den Endpunkten der Linienabtastungen gegeben sind. Segmente sind der Teil der Linienabtastung, in dem die Kantenabstandswerte alle positiv sind.
Linienabtastungen können für ganze Reihen und Spalten von Pixeln in dem diskreten Bild erzeugt werden, wobei herkömmliche Abtastlinien-Rastertechniken verwendet werden. Bei Verwendung dieser Techniken können alle sichtbaren Segmente auf einer Linie, die das gesamte kontinuierliche Bild überspannt, erzeugt werden. Eine Linienabtastung für ein Pixel, mit derselben Orientierung wie der Linie, die das gesamte, kontinuierliche Bild überspannt, wird dann erzeugt durch Berücksichtigen des Teils der sichtbaren Segmente innerhalb des Filterfußabdrucks des Pixels.
Wenn Informationen über die Kanten in dem darunter liegenden, kontinuierlichen Bild bekannt sind, dann ist eine einzelne Linienabtastung pro Pixel mit der korrekten Orientierung ausreichend, um WCVe für die Pixelabtastung dieses Bildes ordnungsgemäß zu erzeugen. Die Kanteninformationen können von dem kontinuierlichen Bild selbst genommen werden. Beispielsweise sind, wie in 12 gezeigt ist, viele Objekte 1200, z.B. Schriftzeichen, durch Grenzkurven 1201 bestimmt. Tangensinformationen 1202 für eine Kurve 1203 können aus der Kurvenbeschreibung berechnet werden. Die Linienabtastung 1205 ist senkrecht zu der Richtung der Tangente 1202 orientiert.
Bei einem alternativen, in 13 gezeigten Verfahren wird ein mit Punktabtastung abgetastetes Bild 1302 mit geringer Auflösung aus einem kontinuierlichen Bild 1301 erzeugt. Das Bild 1302 mit niedriger Auflösung wird mit einem Kantenerfassungsoperator verarbeitet, um Kanteninformationen 1303 zu erzeugen. Die erfassten Kanten 1303 zeigen Orientierungen von zweckmäßigen Linienabtastungen 1304 an. Die ordnungsgemäß orientierten Linienabtastungen werden dann bei dem kontinuierlichen Bild angewendet, um die WCVe zu erzeugen, die für die Bildung eines der Anti-Umfaltung unterzogenen, diskreten Bildes 1305 verwendet werden.
Während diese Erfindung anhand eines bevorzugten Ausführungsbeispiels und verschiedener Modifikationen hiervon für verschiedene, unterschiedliche Anwendungen beschrieben wurde, ist es für die Fachmann offensichtlich, auf der Grundlage der vorstehenden Beschreibung zusammen mit der Zeichnung, dass andere Modifikationen ebenfalls innerhalb des Bereichs die ser Erfindung durchgeführt werden können, insbesondere angesichts der Flexibilität und Anpassbarkeit der Erfindung, deren tatsächlicher Bereich in den folgenden Ansprüchen definiert ist.

Claims

Verfahren zur Anti-Umfaltung eines diskreten Bildes, das aus einem kontinuierlichen Bild erzeugt ist, unter Verwendung einer Filterfunktion, wobei das kontinuierliche Bild eine Kante enthält, welches die Schritte aufweist: Definieren eines Linienmusters; Ableiten einer progressiven Faltung aus der Filterfunktion und dem Linienmuster, welche progressive Faltung ein kumulatives Integral der Filterfunktion mit verschiedenen Abständen von der Kante ist; Auswählen eines Pixels an einer vorbestimmten Stelle in dem diskreten Bild; Orientieren des Linienmusters, zentriert auf dem ausgewählten Pixel; Messen eines Abstands von einem Punkt in dem kontinuierlichen Bild, entsprechend dem ausgewählten Bild zu der Kante, entsprechend dem orientieren Linienmuster; Bewerten der progressiven Faltung bei dem gemessenen Abstand, um einen gerichteten Überdeckungswert zu erzeugen; Assoziieren des gewichteten Überdeckungswertes mit dem Pixel für die Anti-Umfaltung des Pixels in dem diskreten Bild.
Verfahren nach Anspruch 1, bei dem die Kante sichtbar ist.
Verfahren nach Anspruch 1, bei dem das ausgewählte Pixel innerhalb eines vorbestimmten Abstands von der Kante ist.
Verfahren nach Anspruch 3, bei dem der vorbestimmte Abstand kürzer als oder gleich einer Länge des Linienmusters ist.
Verfahren nach Anspruch 1, bei dem das Linienmuster gerade ist.
Verfahren nach Anspruch 1, bei dem das Linienmuster im wesentlichen auf dem Pixel zentriert und im wesentlichen senkrecht zu der Kante ist.
Verfahren nach Anspruch 1, bei dem das Linienmuster eine endliche Länge hat, die zumindest eine Fußspur der Filterfunktion überspannt.
Verfahren nach Anspruch 1, bei dem die Filterfunktion eine Gauß'sche Funktion ist.
Verfahren nach Anspruch 1, bei dem die progressive Faltung durch eine kontinuierliche Funktion definiert ist.
Verfahren nach Anspruch 1, bei dem die Werte der progressiven Faltung in einer Tabelle für eine endliche Anzahl von Abständen gespeichert ist.
Verfahren nach Anspruch 1, bei dem das kontinuierliche Bild eine erste und eine zweite Kante enthält, und das weiterhin die Schritte aufweist: Messen eines ersten und zweiten Abstands von einem Punkt in dem kontinuierlichen Bild, entsprechend dem ausgewählten Pixel zu der ersten und zweiten Kante; Bewerten der progressiven Faltung bei dem gemes senen ersten und zweiten Abstand, um einen ersten und zweiten gewichteten Überdeckungswert zu erzeugen; Assoziieren einer Differenz des ersten und zweiten gewichteten Überdeckungswertes mit dem Pixel für die Anti-Umfaltung des Pixels in dem diskreten Bild.
Verfahren nach Anspruch 1, bei dem sich die Kante in dem kontinuierlichen Bild aus einem ersten Objekt, das mit einem zweiten Objekt zusammenwirkt, ergibt, und das ausgewählte Pixel eine erste Tiefeninformation für das erste Objekt und eine zweite Tiefeninformation für das zweite Objekt hat und das weiterhin die Schritte aufweist: Bestimmen von Abschnitten des Linienmusters, die zusammenwirken; selektives Zurückhalten und Nichtbeachten von Abschnitten auf der Grundlage der Tiefeninformationen über die Abschnitte.
Verfahren nach Anspruch 12, bei dem das erste und zweite Objekt durch Okkludieren zusammenwirken.
Verfahren nach Anspruch 12, bei dem das erste und zweite Objekt durch Sichkreuzen zusammenwirken.
Verfahren nach Anspruch 1, weiterhin aufweisend die Schritte: Definieren eines ersten Linienmusters und eines zweiten Linienmusters; Ableiten einer ersten progressiven Faltung aus der Filterfunktion und dem ersten Linienmuster; Ableiten einer zweiten progressiven Faltung aus der Filterfunktion und dem zweiten Linienmuster; Auswählen eines Pixels an einer vorbestimmten Stelle in dem diskreten Bild; Orientieren des ersten und zweiten Linienmusters mit Bezug auf das ausgewählte Pixel; Messen eines ersten und zweiten Abstands von einem Punkt in dem kontinuierlichen Bild, entsprechend dem ausgewählten Pixel zu der Kante, entlang des orientierten ersten und zweiten Linienmusters; Bewerten der ersten progressiven Faltung des ersten Linienmusters und der zweiten progressiven Faltung des zweiten Linienmusters an dem gemessenen ersten und zweiten Abstand, um einen ersten gewichteten Überdeckungswert und einen zweiten gewichteten Überdeckungswert zu erzeugen; Gewichten des ersten und des zweiten Linienmusters; Mischen des ersten und zweiten, gewichteten Überdeckungswertes gemäß der Gewichtung des ersten und zweiten Linienmusters; Assoziieren der gemischten, gewichteten Überdeckungswerte mit dem Pixel für die Anti-Umfaltung des Pixels in dem diskreten Bild.
Verfahren nach Anspruch 15, bei dem das erste Linienmuster senkrecht zu dem zweiten Linienmuster ist.
Verfahren nach Anspruch 15, bei dem das erste und zweite Linienmuster bewertet und gewichtet werden gemäß der Orientierung des ersten und zweiten Linienmusters mit Bezug auf die Kante.
Verfahren nach Anspruch 17, bei dem die Gewich- tung einen normierten Vektor verwendet, der von der Kante abgeleitet ist.
Verfahren nach Anspruch 15, bei dem die Längen des ersten und zweiten Linienmusters das Zweifache eines Abstands zwischen den Pixeln des diskreten Bildes sind und die Kantenabstandswerte an den Linienmuster-Endpunkten erzeugt werden.
Verfahren nach Anspruch 15, das weiterhin die Schritte aufweist: Auswählen von Reihen und Spalten von Pixeln; Auswählen einer Linie, die das gesamte, kontinuierliche Bild überspannt in Ausrichtung mit den Reihen und Spalten von Pixeln; Erzeugen von Segmentinformation für die das gesamte, kontinuierliche Bild überspannende Linie; Bestimmen von sichtbaren Segmenten für die das gesamte, kontinuierliche Bild überspannende Linie; Auswählen eines Pixels in den Reihen und Spalten von Pixeln; Erzeugen eines Linienmusters für das Pixel aus den sichtbaren Segmenten innerhalb einer Fußspur der Filterfunktion an dem Pixel.
Verfahren nach Anspruch 1, bei dem die Kante eine Kurve ist, welches weiterhin die Schritte aufweist: Bestimmen einer Tangente an die Kurve und Orientieren des Linienmusters senkrecht zu der Tangente.
Verfahren nach Anspruch 1, das weiterhin die Schritte aufweist: Erzeugen eines Bildes mit geringer Auflösung von dem kontinuierlichen Bild; Anwenden eines Kantendetektoroperators auf das Bild mit geringer Auflösung, um die Kante zu erzeugen; Orientieren des Linienmusters senkrecht zu der Kante.