DE69130602T2 - Korrelationsvorrichtung - Google Patents

Description

• Die Erfindung betrifft eine Korrelationsvorrichtung, die mit zwei Eingangssignalen arbeitet, die zwei in Blöcken organisierte Symbole entsprechend einer regelmäßigen Konfiguration darstellen, und beinhaltet:
• - einen Korrelator zur Bestimmung einer Korrelation zwischen Symbolen eines laufenden Blocks und Symbolen mit identischen Positionen in einer zu verarbeitenden Blockfolge, die aus der besagten Konfiguration herrührt,
• - und Auswahlmittel, die unter den Symbolen des besagten laufenden Blocks eine begrenzte Anzahl Referenzsignale auswählen, die Korrelation einbeziehend.
• Die regelmäßige Konfiguration von Eingangssignalen kann eindimensional oder zweidimensional sein. Es kann sich z. B. um eine eindimensionale Konfiguration handeln, wo Korrelationen auf Eingangssignalblöcken akustischer Herkunft zur Tonverarbeitung vorgenommen werden können. Ein Symbol der Konfiguration ist dann ein in binärer Form codierter Wert. Vorzugsweise kann es sich um zweidimensionale Konfigurationen handeln, wo die Korrelationen auf z. B. bewegten Bildern vorgenommen werden, auf denen man Versetzungsvektoren der bewegten Sequenz zwischen aufeinanderfolgenden Bildern bestimmt. Ein Symbol der Konfiguration ist dann ein Pixel. Diese Anwendungen werden oft zur Reduzierung der Datenrate eingesetzt. Man findet sie z. B. im Bereich des Fernsehens (hohe Rate) oder im Bereich des Bildtelefons oder der Videokonferenz (geringe Rate).
• Die Anwendung bezüglich der Bewertung bewegter Bilder beim Fernsehen weist die Besonderheit beträchtlicher Belastungen auf, da große Rechenvolumen zu einer hohen Rate vorzunehmen sind. Diese Anwendung wird hier deshalb als Beispiel genommen, ohne deshalb die Erfindung einzuschränken.
• Für die Bewertung bewegter Bilder scheint die interessanteste Technik die sogenannte "blockweise Entsprechungstechnik" mit der englischen Benennung "block matching" zu sein. Sie besteht in der Unterteilung des Bildes in Pixelblöcke. Für einen gegebenen Block des Bildes bestimmt man in einem vorhergehenden Bild den Block, der am ähnlichsten ist, um die Bewegung der im Bild dargestellten Sequenz zu bestimmen. Diese Bewegungsinformation ist es, die für jeden Bock an das am Ende des Übertragungskanals vorgesehene Empfangsgerät übertragen wird.
• Das Verarbeitungsprinzip besteht darin, die Entwicklung des Bildinhaltes über aufeinanderfolgende Bilder zu verfolgen. Diese Technik nutzt die Tatsache, daß der informative Inhalt von einem Bild zum anderen wenig variiert. Die in einem Block enthaltene Informationsverlagerung beschränkt sich allgemein auf einige angrenzenden Blöcke. Die Verfolgung wird vorgenommen, indem bestimmte Stellen hervorgehoben werden, wobei es sich um die auffälligsten oder bewußt gewählte handeln kann. Dies kann sämtliche Blöcke des Bilds betreffen.
• Ein laufender Referenzblock (mit der weiteren vereinfachten Bezeichnung "laufender Block") könnte anders in vorherigen oder nachfolgenden Bildern enthalten sein. Diese Versetzung gilt es, zu bestimmen. Doch die Versetzung bleibt begrenzt, weshalb man ein Fenster definiert, in dem sich der besagte laufende Block befinden müßte.
• Die bewertete Bewegung ist die Translation zwischen der Position im Bild des laufenden Blocks und der Position im vorhergehenden/nachfolgenden Bild des vorhergehenden/nachfolgenden Blocks, der die stärkste Korrelation aufweist. Dies ermöglicht die Bestimmung eines Versetzungsvektors in bezug auf den laufenden Block.
• Die Korrelation wird folglich von Pixel zu Pixel selber Position für alle möglichen Positionen des laufenden Blocks im Innern des entsprechenden Fensters bestimmt. Die selben Operationen werden für die anderen gewählten laufenden Blöcke wiederholt. Die Korrelation wird allgemein durch Summierung der absoluten Werte der verschiedenen Charakteristiken von Pixel zu Pixel, Block zu Block des gesamten Blocks bewertet. Die Charakteristik des Pixels ist allgemein seine Leuchtdichte.
• Zwei prinzipielle Obligationen sind mit der materiellen Realisierung eines Bewegungsbewerters verbunden: seine Fähigkeit, in Echtzeit zu arbeiten, und seine materielle Komplexität. Es wurden verschiedene Strategien entwickelt, doch manche Algorithmen, die weniger Operationen erfordern, erweisen sich weniger Regelmäßig und folglich komplexerer Umsetzung. Die Regelmäßigkeit der Rechenphasen ist eine insbesondere für die Realisierung der dedizierten integrierten Schaltungen zu berücksichtigende Bedingung. Dies erklärt, daß die üblicherweise umgesetzte Strategie in der exhaustiven Suche über alle Pixel aller Blöcke des Fensters besteht. Abtasttechniken zur aufeinanderfolgenden Analyse jedes Pixels des laufenden Blocks im Fenster können eine Reduzierung der materiellen Komplexität der Implementierungen ermöglichen.
• Folglich wurde versucht, Methoden zur Verminderung der Komplexität der zu verarbeitenden Bewegungsbewertung zu entwickeln, ohne die Fähigkeit zu beeinträchtigen, in Echtzeit zu arbeiten. Dazu kennt man den Artikel mit dem Titel "Motion-compensated interframe coding for video conferencing" von T. KOGA et al., National Telecommunications Conference 29 November, 3. Dezember 1981, NEW ORLEANS, LOUISIANA. Dieses Dokument beschreibt einen Bewegungsbewertungsvektor unter Einsatz verschiedener Manipulationen, und insbesondere einer Unter-Abtastung, die es ermöglicht, nur eine begrenzte Anzahl Pixel pro laufendem Block zu berücksichtigen, d. h. ein Pixel von zweien einer Zeile in einem ersten Fall, und selbst eine Zeile von zweien in einem zweiten Fall. Dies vermindert die Hardware-Komplexität, doch zu Lasten der Präzision der Bewegungsbewertung. Die differentielle Zwischen-Bild-Codierung, eine bei der Bewegungsbewertung vorgezogene Anwendung, besteht in der Übertragung eines Voraussagefehlers, der in diesem Fall im Block des vorhergehenden, im Fenster gewählten Blocks vorhanden ist. Wenn die Bewegungsbewertung korrekt gemacht wird, ist der Voraussagefehler gering, und folglich wird die Länge des pro Übertragungskanal übertragenen Codes reduziert. Man geht folglich davon aus, daß sich die abnehmende Präzision der Bewegungsbewertung auf die Effizient der Codierung auswirkt. So kann bei der genannten herkömmlichen Technologie bei einer Übertragungsrate von 1,5 MBits/s die Voraussage-Fehlerquote um 50% steigen. Dies erfordert eine Steigerung der Rate, um eine annehmbare Bildqualität zu erhalten.
• Die Problemstellung ist folglich die Konzeption einer Korrelationsvorrichtung, die (im Vergleich zur üblichen Realisierung) eine vereinfachte materielle Realisierung ermöglicht und mit einer verminderten Voraussage-Fehlerquote selbst für Anwendungen der Fernsehbildverarbeitung in Echtzeit arbeiten kann.
• Dieses Ziel wird mit einer Korrelationsvorrichtung erreicht, deren Auswahlmittel im besagten laufenden Block ein (mehrere) Referenzsymbol(e) durch die Wahl seiner (ihrer) Position auswählt:
• - entweder unter Berücksichtigung des informationellen Inhalts des besagten laufenden Blocks,
• - oder nach einer Zufallswahl,
• - oder für einen ersten Teil prioritär unter Berücksichtigung des informationellen Inhalts und für einen zweiten Teil nach einer Zufallswahl.
• So ist es möglich, zwei komplementäre Strategien zu verwenden, die kombiniert werden können.
• Im Falle eine Bildes z. B. können nach der ersten Strategie vorteilhaft nur die Pixel, die eine "Distorsions"-Information enthalten, im laufenden Block zur Berechnung der Korrelation gewählt werden.
• Nach der zweiten Strategie läßt man den informationellen Inhalt des laufenden Blocks außer Acht, und die ausgewählten Referenzpixel werden zufällig im laufenden Block verteilt.
• Diese beiden Strategien ermöglichen die Unterbrechung der regelmäßigen Auswahl, die beim Ausschließen eines Pixels von zweien auf derselben Zeile stattfindet. Denn die Regularität dieser Auswahl weist den Nachteil auf, den Hochfrequenzteil des Informationsspektrums aufzuheben und eine unannehmliche Fehlerquote bei hoher Rate zu erzeugen (siehe das erwähnte Dokument). Nach der Erfindung dagegen wird der Hochfrequenzteil des Informationsspektrums nicht aufgehoben, und sein Umfang kann durch Eingreifen auf die begrenzte Anzahl ausgewählter Symbole pro laufendem Block selbst kontrolliert werden. Durch die Kombination der Strategie des informationellen Inhalts und der Strategie der zufälligen Auswahl wird ein Ausbleiben an Regularität der Symbolposition im laufenden Block erreicht, und die Fehlerquote durch eine möglichst nahe Verfolgung des Informationsinhalts noch mehr reduziert. In diesem letzten Fall werden die Referenzsymbole prioritär nach dem informationellen Inhalt gewählt, und ihre Anzahl durch eine Zufallswahl bis zur vorbestimmten begrenzten Anzahl komplementiert.
• Wenn ein Block aus Pixeln (respektive aus binär codierten Werten) gebildet wird, besteht die Wahl in der Referenznahme der Pixel (respektive der binär codierten Werte) mit einer bestimmten Position im laufenden Block.
• Diesen Pixeln mit einer bestimmten Position im laufenden Block entsprechen andere Pixel mit derselben Position in Blöcken des zu analysierenden Fensters. Die zwischen zwei Blöcken berechnete Korrelation wird tatsächlich zwischen den Pixeln der beiden Blöcke mit selber Position vorgenommen. Die Operation wird für alle möglichen Positionen des laufenden Blocks im Fenster fortgesetzt. Die Verarbeitung wird dann mit einem anderen laufenden Block in Verbindung mit einem anderen Suchfenster weitergeführt. Es ist möglich, daß dieselbe Zufallswahl für mehrere laufende Blöcke verwendet wird, um die Position des (der) zufällig ausgewählten Referenzsymbols (Referenzsymbole) zu wählen.
• Im Falle die Auswahl unter Berücksichtigung des informationellen Inhalts des laufenden Blocks stattfindet, wird die Position der Referenzsymbole im laufenden Block mit einer Distorsionsfunktion für jedes Symbol des laufenden Blocks hinsichtlich der umgebenden Blöcke bestimmt, während das (die) gewählte(n) Referenzsymbol(e) unter den Symbolen gewählt wird (werden), deren Werte der Distorsionsfunktion sich am meisten von denen in bezug auf die umgebenden Symbole unterscheiden.
• Diese Distorsionsfunktion kann z. B. die Variation einer Charakteristik wie die Leuchtdichte oder anderes zwischen den benachbarten Pixeln eines selben laufenden Blocks berücksichtigen. Zur Bestimmung der repräsentativsten Pixel eines laufenden Blocks kann die Distorsionsfunktion unter Berechnung eines Laplace-Operators bestimmt werden, der die für das Eingangssignal gewählte Charakteristik einbezieht. Allgemeiner kann man benachbarte Pixel berücksichtigen, die ein gegebenes Pixel isotrop umgeben. Damit jedoch in einem laufenden Block die Referenzpixel nicht in einem zu eingegrenzten Teil des laufenden Blocks konzentriert sind ist es möglich, eine Verteilungsbedingung vorzugeben, indem der laufende Block in mehrere Zonen unterteilt wird, z. B. in der Form eines (un)regelmäßigen karierten Musters oder jeder anderen Musterung. In diesem Falle gibt man vor, daß alle oder zumindest ein Teil der Zonen durch mindestens ein Pixel dargestellt sind. Dieses Pixel pro Zone kann mit denselben Strategien wie den für einen laufenden Block bereits beschriebenen gewählt werden. So arbeiten bei der Unterteilung eines laufenden Blocks in mehrere Zonen die Auswahlmittel für jede Zone einzeln, während die Korrelation immer über die Gesamtheit der Referenzpixel des laufenden Blocks vorgenommen wird. Vorzugsweise enthält jede Zone eines laufenden Blocks dieselbe Anzahl Referenzpixel. Wenn das (die) Referenzpixel der Zonen ausgehend von der Bestimmung einer Distorsionsfunktion ausgewählt wird (werden), wird (werden) das (die) Referenzpixel in jeder Zone vorzugsweise derart ausgewählt, daß die Werte der Distorsionsfunktion, die es (sie) charakterisieren, für angrenzende Zonen abwechselnd maximal und minimal sind.
• Nach der Erfindung werden in einem laufenden Block nur eine begrenzte Anzahl Referenzsymbole zur Durchführung der Korrelationsberechnung beibehalten. Diese begrenzte Anzahl kann auf mehrere Arten gewählt werden. Sie kann a priori nach vorhergehenden Tests bestimmt werden, die die Aufstellung einer Korrelationsberechnung mit einer akzeptablen Fehlerquote ermöglichen. Dies kann realisiert werden, wenn der laufende Block eine verminderte Anzahl Pixel, z. B. 4 · 4, enthält.
• Wenn es sich um eine Strategie unter Verwendung einer den informationellen Inhalt berücksichtigenden Distorsionsfunktion handelt, kann diese begrenzte Anzahl ausgehend von den den Werten vorgegebenen Grenzen gewählt werden, die diese Distorsionsfunktion aufweisen kann.
• Allgemeiner kann man, wenn der Umfang des laufenden Blocks groß wird, den informationellen Inhalt des gesamten Bildes, und nicht nur den des laufenden Blocks für die Bestimmung der begrenzten Anzahl Symbole berücksichtigen. Dafür stellt man eine charakteristische Korrelationsmatrix der gesamten, das Bild bildenden Eingangssignale auf. Mit der sogenannten Methode der "Analyse prinzipieller Komponenten" berechnet man die eigenen Werte dieser Korrelationsmatrix und bestimmt die entsprechenden Varianzen, unter denen man die Anzahl der höchsten Varianzen bestimmt, die für eine gute Darstellung des gesamten Bildes erforderlich sind. Diese Anzahl wird dann als begrenzte Anzahl der Referenzsymbole gewählt.
• Nach der Erfindung macht man in diesem Fall folglich die begrenzte Anzahl Referenzsignale des Bildinhalts abhängig. In zahlreichen Situationen bleibt diese begrenzte Anzahl hauptsächlich an den Bildtyp gebunden, d. h. die Anwendung an sich. Dennoch ist es möglich, die besagte begrenzte Anzahl präziser vom Bildinhalt abhängig zu machen, indem man sie regelmäßig und adaptiv auf Bildsätze abstimmt. Dies kann unter Zuhilfenahme einer Korrelationsvorrichtung erreicht werden, die ein Neuronennetz enthält, das die sogenannte Methode der "Analyse prinzipieller Komponenten" umsetzt und die Anzahl höchster Varianzen auswählt. Diese Anzahl Varianzen wird zyklisch den Auswahlmitteln zugeführt, um die besagte begrenzte Anzahl zu bilden und auf die bereits beschriebene Weise zu verarbeiten.
• Ein Neuronennetz ist eine bekannte Vorrichtung zur Signalverarbeitung, das nach einem Programmierschritt und einem Lernschritt bestimmte Verarbeitungen vornehmen kann, z. B. eine "Analyse prinzipieller Komponenten" der Verteilung von Eingangssignalen. Ein solches Neuronennetz kann z. B. das in folgendem Dokument beschriebene sein: "Optimal unsupervised Learning in single-layer linear Feedforward Neural networks" von T. D. SANGER, Neural Networks, Band 2, 1989, Seiten 459- 473.
• Wie bereits zuvor vermerkt ermöglicht es die Tatsache, in die Korrelationsberechnung nur bestimmte Referenzsymbole mit einer bestimmten Position im laufenden Block einzubeziehen, eine Vereinfachung der materiellen Realisierung und eine Steigerung der Verarbeitungsgeschwindigkeit unter Beibehalt von Fehlerquoten zu schwachen und kontrollierbaren Niveaus.
• Dazu ermöglichen die Mechanismen zur Auswahl der Referenzsymbole in bestimmten Situationen eine zusätzliche Vereinfachung der Komplexität der materiellen Realisierung. Insbesondere wenn ein laufender Block in Zonen unterteilt wird ermöglicht dies vorteilhaft den Erhalt entweder einer gesteigerten Verarbeitungsgeschwindigkeit oder gesteigerter Komplexität der Hardware. Diese Situation tritt ein, wenn die Korrelationsvorrichtung eine Korrelationsberechnung mit laufenden Datenblöcken vornimmt, unterteilt in p Zonen mit n/p pro Zone ausgewählten Referenzsymbolen, wobei der Korrelator enthält:
• - ein systolisches Registernetz zum internen Austausch der Pixeldaten des Fensters,
• - eine Vielzahl an Prozessoren, wobei jeder Prozessor eine Korrelationsberechnung mindestens eines Versetzungsvektors durchführt, die Vorrichtung einen ersten Berechnungsschritt vornimmt, in dessen Verlauf:
• a) jeder Prozessor aufeinanderfolgend eine Korrelationsberechnung der n/p ausgewählten Referenzsymbole einer ersten Zone vornimmt und die Berechnung aufeinanderfolgend alle Versetzungsvektoren einbezieht, die der besagte Prozessor zu berechnen hat,
• b) Speichermittel die von den Prozessoren am Ende von a) ausgegebenen Zwischenergebnisse speichern,
• c) Übertragungsmittel den Inhalt der in einer Zone arbeitenden Register zu den folgenden, in einer folgenden Zone arbeitenden Register übertragen, der erste Berechnungsschritt dann für die p-1 folgenden Zonen wiederholt wird, wobei Summiermittel die Summe der Zwischenergebnisse in bezug auf jeden zu verarbeitenden Block bestimmen, um die Korrelation der besagten Blockfolge zu liefern.
• Ein besonders interessanter Fall tritt bei der Bildverarbeitung ein, wenn die besagten Zonen mehrere Pixel beinhalten, von denen ein einziges zur Vornahme der Korrelationsberechnung ausgewählt wird. Dann ist es möglich, einen zusätzlichen Leistungsgewinn zu erhalten und für den Korrelator zwischen einer Architektur zu wählen, die der Geschwindigkeit Vorrang gibt oder einer Architektur, die einer vereinfachten Hardware den Vorrang gibt, d. h., die die Fläche für eine integrierte Durchführungsform vermindert.
• Im Falle einer die Geschwindigkeit bevorzugenden Architektur enthält der Korrelator weitgehend gleich viele Prozessoren wie mögliche Versetzungen im Fenster, und er arbeitet mit einer begrenzten Anzahl Referenzpixel, was seine Arbeitsgeschwindigkeit bezüglich einer Verwendung mit der Gesamtheit der Pixel des laufenden Blocks steigert. Ein besonders interessanter Fall ist der, bei dem jede Zone nur 4 Pixel enthält, mit einem einzigen pro Zone ausgewählten Referenzpixel. In diesem Fall arbeitet der Korrelator in einem zweidimensionalen Pixelfenster mit laufenden Blöcken, die in Zonen mit jeweils 4 Pixeln unterteilt sind, mit einem einzigen ausgewählten Referenzpixel pro Zone, wobei eine zweidimensionale Registermatrix zu einem bestimmten Zeitpunkt die Pixel des besagten Fensters nach derselben Anordnung speichert, vier Register der Verarbeitung einer Zone zugeteilt sind, die Pixel gerader Ordnung des Fensters von den besagten Registerreihen untereinander in beide Richtungen der Matrix übertragen werden und die Pixel ungerader Ordnung von anderen Registerreihen übertragen werden, diese Verbindung nach einer Richtung des Fensters in eine Richtung und nach der anderen Richtung des Fensters in zwei Richtungen verläuft, ein Prozessor der Verarbeitung jedes Versetzungsvektors zugeteilt ist und mit vier Registern arbeitet, die gerade und ungerade Fensterpixel enthalten, die Ordnungsnummern der besagten paarweise genommenen Pixel in jede Richtung aufeinanderfolgen, und ein gemeinsames Auswahlsignal die Prozessoren mit den im laufenden Block ausgewählten Referenzpixeln entsprechenden Registerdaten arbeiten läßt.
• Im Falle einer die Verminderung der Hardware-Komplexität bevorzugenden Architektur ist ein besonders interessanter Fall der, bei dem der Korrelator in einem zweidimensionalen Pixelfenster arbeitet, mit laufenden Blöcken, unterteilt in rechteckige Zonen mit k Pixeln und einem einzigen pro Zone ausgewählten Referenzpixel, wobei eine zweidimensionale Registermatrix zu einem bestimmten Zeitpunkt die Pixel des besagten Fensters nach derselben Anordnung speichert, k Register der Verarbeitung einer Zone zugeteilt sind, die Fensterpixel in beide Richtungen der Matrix zwischen den Reihen der besagten Register übertragen werden, ein Prozessor der aufeinanderfolgenden Verarbeitung von k Versetzungsvektoren zugeteilt ist und mit k Registern arbeitet, die zur selben Zone gehörende Pixel enthalten, die Ordnungsnummern der besagten paarweise genommenen Pixel in beide Richtungen aufeinanderfolgen, und ein Auswahlsignal jeden Prozessor für jede Versetzung mit den in der laufenden Zone ausgewählten Referenzpixeln entsprechenden Registerdaten arbeiten läßt.
• Die Erfindung beschränkt sich nicht auf den Fall zweidimensionaler Symbolkonfigurationen. Sie ist auch im Falle eindimensionaler Konfigurationen verwendbar. So können die Symbole binär codierte Werte sein, die eine Konfiguration eindimensionaler Akustiksignale darstellen. Die Korrelationsvorrichtung arbeitet dann mit den mehrere dieser Werte beinhaltenden laufenden Blöcken, unter denen in begrenzter Anzahl und Position Referenzwerte ausgewählt werden.
• Die Erfindung wird unter Zuhilfenahme der Figuren leichter verständlich, die als nicht begrenzende Beispiele gegeben werden und folgendes darstellen:
• Fig. 1A, 1B: eine Darstellung eines Bildes, das ein Fenster mit zu verarbeitenden Blöcken enthält, die in die Korrelation einzubeziehen sind, und das eines laufenden Blocks in einem nachfolgenden Bild,
• Fig. 2: ein Blockschema einer Korrelationsvorrichtung,
• Fig. 3A, 3B: eine Darstellung eines laufenden Blocks zu 8 · 8 Pixeln, die Positionen der ausgewählten Referenzsymbole nach herkömmlicher Technik anzeigend,
• Fig. 3C, 3D, 3E, 3F: als Beispiel eine Darstellung eines laufenden Blocks zu 8 · 8 Pixeln, die Positionen der ausgewählten Referenzsymbole nach der Erfindung anzeigend,
• Fig. 4A, 4B, 4C, 4D: eine Darstellung der ein zur Berechnung der Distorsionsfunktion gegebenes Pixel umgebenden Pixel,
• Fig. 5: ein Schema eines Teils der Auswahlmittel zur Ermöglichung der Berechnung einer Distorsionsfunktion nach der Darstellung der Fig. 4A,
• Fig. 6 ein detailliertes Schema einer Auswahleinheit mit einem Rechenorgan eines Laplace-Operators und einem Aussortierorgan,
• Fig. 7: ein Blockschema einer Korrelationsvorrichtung mit einem Neuronennetz zur Bestimmung der Anzahl Referenzsymbole,
• Fig. 8: ein Korrelatorschema nach herkömmlicher Technik,
• Fig. 9A, 9B: eine Darstellung zu verarbeitender Blöcke eines Fensters und einen in Zonen unterteilten laufender Block,
• Fig. 10: ein Schema eines Prozessors, von den für seine Funktion erforderlichen Basisorganen umgeben,
• Fig. 11: ein Schema eines die Hardware-Vereinfachung bevorzugenden Korrelators, mit in Zonen zu 4 Symbolen, unter denen ein Referenzsymbol gewählt wird, unterteilten laufenden Blöcken arbeitend,
• Fig. 12: ein die Geschwindigkeit bevorzugender Korrelator, mit in Zonen zu 4 Symbolen unterteilten laufenden Blöcken arbeitend.
• Fig. 1A zeigt ein Bild 10 und Fig. 1B zeigt ein Bild 20, das vorhergehend, doch vorzugsweise nachfolgend zum Bild 10 sein kann, in dem die Korrelationsberechnung durchgeführt wird.
• Bild 20 wird aus Pixeln gebildet, die man in der Form laufender Blöcke analysiert, z. B. die Blöcke 21&sub1;, 21&sub2;, 21&sub3;. Im Bild 20 besteht für einen beliebigen laufenden Block, z. B. den laufenden Block 22, die Verarbeitung in der Bestimmung, an welchem Block des vorhergehenden Bildes 10 er korrelierte. Dafür bestimmt man um einen Block 12, der im Bild 10 dieselben Koordinaten wie die des laufenden Blocks 22 im Bild 20 hat, ein Fenster 13, das den Block 12 umgibt, um die Anzahl und die Position der Blöcke zu begrenzen, auf die sich die Suche nach dem am wahrscheinlichsten den korrelierten Block enthaltenden zu erstrecken hat. Die Größe und die Form dieses Fensters hängt vom Umfang der Suche ab, die man durchführen will, und folglich letztendlich von der Verarbeitungszeit, die man der Untersuchung eines Fensters widmen kann sowie von der Komplexität, die man für die damit einhergehende materielle Realisierung zuläßt. Somit wird der laufende Block 22 (Bild 20) mit allen Blöcken des Fensters 13 des Bilds 10 verglichen, erhalten durch Versetzung des Blocks um aufeinanderfolgende Schritte von mindestens 1 Pixel.
• Nach dieser Verarbeitung wird ein anderer laufender Block im Bild 20 gewählt, dem ein anderes Fenster im Bild 10 entsprechen wird, und dieselbe Verarbeitung durchgeführt usw. Die im Bild 20 gewählten laufenden Blöcke können begrenzter Anzahl sein, doch vorzugsweise erfahren alle Blöcke dieselbe Verarbeitung. Je nach der Position des laufenden Blocks im Bild 20 und der des korrelierten Blocks im Bild 10 leitet man davon jedesmal einen Versetzungsvektor des laufenden Blocks ab. Dieser Versetzungsvektor sowie die charakteristische Abweichung des Pixels (z. B. der Leuchtdichte) sind es, die codiert und über den Übertragungskanal übertragen werden, um eine Datenkomprimierung durchzuführen.
• Die die Verarbeitung durchführende Korrelationsvorrichtung ist auf Fig. 2 dargestellt. Sie enthält einen Korrelator 25, eine Auswahleinheit 26 zur Bestimmung, welche Pixel des laufenden Blocks 22 in die Korrelation einzubeziehen sind, eine Abtasteinheit 27 zum Bestimmen der Ordnung, nach der die Pixel des Blocks 12 und im weiteren Sinn des Fensters zu analysieren sind. Am Ausgang des Korrelators 25 bestimmt eine Entscheidungseinheit 28 den Block des Fensters 13, für den die Funktion maximal ist. Der zu verarbeitende laufende Block BL wird in die Auswahleinheit 26 und den Korrelator 25 gebracht. Dieser erhält zudem die Dimension des Fensters FEN, die der für die Anwendung erforderlichen Arbeitsgeschwindigkeit unterliegen kann.
• Die Korrelation besteht im aufeinanderfolgenden Vergleich zweier Blöcke untereinander, indem die Pixel verglichen werden, die in jedem Block respektive identische Positionen haben. Es ist gängig, eine erschöpfende Verarbeitung durchzuführen, die die gesamten Pixel der Blöcke einschließt. Nach dem bereits zitierten Dokument ist es jedoch möglich, den Verarbeitungsumfang zu reduzieren, indem nur eine begrenzte Anzahl Pixel pro laufendem Block betrachtet wird.
• Die Fig. 3A und 3B zeigen zwei umgesetzte Möglichkeiten des zitierten Dokuments. Sie zeigen einen laufenden Block zu 8 · 8 = 64 Pixeln, wobei die Referenzpixel schraffiert wurden, die zur Durchführung der Korrelation ausgewählt wurden. Auf Fig. 3A wählt man ein Pixel von zweien, was die Verarbeitung halbiert. Auf Fig. 3B ignoriert man zudem eine komplette Pixelzeile von zweien, was die Verarbeitung nochmals halbiert. Diese Begrenzungen der Anzahl Referenzpixel können leicht vorgenommen werden, z. B. durch eine Änderung des Abtasttakts. Doch die mit diesen Begrenzungsmethoden einhergehende sehr hohe Regelmäßigkeit hat zur Folge, daß der Hochfrequenzteil des Spektrums eines Informationsblocks verstümmelt wird und eine beträchtliche Fehlerquote auftritt.
• Um diesem Fehler entgegenzuwirken führt man nach der Erfindung keine systematisch regelmäßige Auswahl der Referenzpixel im Innern eines laufenden Blocks durch.
• Eine erste diesbezügliche, auf Fig. 3C dargestellte Strategie besteht in einer zufälligen Auswahl einer zuvor bestimmten begrenzten Anzahl Referenzpixel. So wurden auf Fig. 3C 16 im laufenden Block zufällig ausgewählte Referenzpixel schraffiert.
• Eine zweite, auf Fig. 3E als Beispiel dargestellte Strategie berücksichtigt den in einem laufenden Block enthaltenen informationellen Inhalt. Nehmen wir somit an, daß eine fiktive Kurve 31 im laufenden Block zwei Teile unterschiedlicher Leuchtdichte abgrenzt. Nach der Erfindung werden die zur Durchführung der Korrelation ausgewählten Referenzpixel unter Berücksichtigung des informationellen Inhalts unter Bestimmung einer Distorsionsfunktion bestimmt. Kurz gesagt, die in den Teilen oder der Charakteristik (hier der Leuchtdichte) vorzunehmende Auswahl ist in bezug auf ihre nächste Umgebung Variationen unterworfen. Alle Pixel des laufenden Blocks werden so untersucht. Die Auswahleinheit 26 (Fig. 2) nimmt diese Bestimmung vor. Die Fig. 4A, 4B, 4C, 4D zeigen einige möglichen Formen für die Prüfung des informationellen Inhalts mit isotropen Aufteilungen.
• Fig. 4A zeigt eine vorgezogene Form, die für ein beliebiges Pixel (schraffiert) darin besteht, seine Leuchtdichtenvariation mit seinen Nachbarn mit jeweils gleich entfernten Koordinaten von ±1 zu vergleichen. Dies entspricht der Berechnung eines Laplace-Operators Δ wie:
• Δ = 4I(x,y) - (I(x+1,y) + I(x,y+1) + I(x-1),y) + I(x,y-1))
• Für Fig. 4B ist die Distorsionsfunktion:
• Γ = 4I(x,y) - (I(x+1,y+1,) + I(x+1,y-1) + I(x-1,y+1) + I(x-1,y-1))
• Für Fig. 4C ist die Distorsionsfunktion:
• = 4I(x,y) - (I(x+2,y) + I(x-2,y) + I(x,y+2) + I(x,y-2))
• Für Fig. 4E ist die Distorsionsfunktion:
• Ψ = 8I(x,y) - (I(x+1,y+2) + I(x+1,y-2) + I(x-1,y+2) + I(x-1,y-2) + I(x+2,y+1) + I(x-2,y+1) + I(x+2,y-1) + I(x-2,y-1)).
• Andere Aufteilungen umgebender Pixel sind möglich, selbst wenn sie nicht isotrop sind.
• Wenn die Distorsionsfunktion so für alle Pixel des laufenden Blocks berechnet wurde, bestimmt die Auswahleinheit die Pixel mit extremen Werten, um sie zum Repräsentieren des besagten laufenden Blocks auszuwählen.
• Aus den beiden hier beschriebenen Strategien wird ersichtlich, daß bestimmte Teile des laufenden Blocks nicht repräsentiert sein können oder nicht repräsentiert sind.
• Zur Fehlerbegrenzung bei der Korrelation, die daraus hervorgehen kann, ist es wünschenswert, daß die besagten Teile zumindest teilweise repräsentiert sind. Insbesondere nach der Erfindung unterteilt man dafür den laufenden Block in Zonen, die (un)regelmäßig sein können. Vorzugsweise unterteilt man einen laufenden Block in identische Zonen mit einer selben Anzahl Pixel. Dann wird für die Zufallsauswahl nicht mehr das Niveau des laufenden Blocks, sondern das Niveau der Zone einbezogen. So werden die Referenzpixel pro Zone zufällig ausgewählt. Dies ist auf Fig. 3D dargestellt, wo 16 zufällig ausgewählte Pixel schraffiert dargestellt sind. Eine diesem Typ entsprechende Zufallsauswahl kann für mehrere laufende Blöcke zum Durchführen der Korrelationsberechnung durchgeführt werden. Obwohl die Zufallsauswahl auf dem Niveau der Zone verläuft, wird die Korrelationsberechnung weiterhin auf dem Niveau des laufenden Blocks ausgeführt.
• Fig. 3F zeigt die Situation, bei der die beiden Strategien kombiniert werden können. Dafür wird ein erster Teil Referenzpixel vorrangig nach dem informationellen Inhalt ausgewählt, und ein zweiter Teil wird pro Zone nach einer Zufallswahl ausgewählt. Dieser zweite Teil hat eine Begrenzung, wenn die Gesamtheit ausgewählter Referenzpixel die vorgesehene begrenzte Anzahl erreichen.
• Das Schema der Fig. 5 zeigt eine Auswahleinheit 26 zur Bestimmung der Position der Punkte in einem laufenden Block mit der Berechnung einer Distorsionsfunktion (Funktionen Δ, Γ, , Ψ wie zuvor), in einem Berechnungsorgan 50 vorgenommen. Die erhaltenen Ergebnisse werden in einem Aussortierorgan 51 nach einem Sortier-Algorithmus aussortiert, um die Anzahl Referenzsymbole pro laufendem Block zu begrenzen. Die Adressen der beibehaltenen Referenzsymbole werden in einem Adressenregister 52 gespeichert, um vom Korrelator verwendet zu werden. Die Auswahleinheit 26 arbeitet unter der Kontrolle der Abtasteinheit 27.
• Ein detailliertes Schema des Rechenorgans 50 und des Aussortierorgans 51 ist auf Fig. 6 dargestellt, im Falle die Distorsionsfunktion der zuvor definierte Laplace-Operator Δ ist. Diese Distorsionsfunktion entspricht der Darstellung von Fig. 4A, auf der die Buchstaben N, S, E, W respektive die Himmelsrichtungen Nord, Süd, Ost, West darstellen. Diese Buchstaben werden auf das Schema der Fig. 6 übertragen, wobei der Buchstabe C das zentrale Pixel darstellt. Die Situation betrifft den Fall, bei dem das Abtasten zeilenweise verläuft und alle Pixel des laufenden Blocks einschließt. Fig. 6 zeigt eine Verzögerungskette, gebildet aus:
• - einer ersten Verzögerungszeile 60 und einer zweite Verzögerungszeile 63, die jeweils die Daten um die Dauer einer Zeile minus eines Pixels verzögern,
• - ein erstes Register 61 und ein zweites Register 62, die jeweils die Daten um die Dauer einer Pixelabtastung verzögern.
• So befinden sich nach drei abgetasteten Zeilen die Daten der Pixel N, S, E, W wie auf Fig. 6 gezeigt verteilt:
• der Datensatz N ist am Ausgang der Verzögerungszeile 63, und
• der Datensatz S ist am Eingang der Verzögerungszeile 60.
• Ein Addierer 64 und ein Addierer 65 führen respektive die Additionen S+E und W+N durch. Die beiden Ergebnisse werden in einem Addierer 66 addiert. Diesem letzteren Ergebnis muß 4 mal der Wert des zentralen Datensatzes C abgezogen werden. Dieser befindet sich in C zwischen den beiden Registern 61 und 62. Um ihn mit 4 zu multiplizieren reicht es aus, ihn am Eingang des Subtrahierers 67, der den Ausgang des Addierers 66 erhält, um 2 Bits zu versetzen. Der Ausgang des Subtrahierers 67 gibt die Distorsionsfunktion δ ab, die für alle Pixel jedes laufenden Blocks errechnet wird. Unter all diesen Pixeln wird eine begrenzte Anzahl ausgewählt, um unter Zuhilfenahme des Aussortierorgans 51 die Referenzpixel zu bilden. Nach einem vorgezogenen Verfahren sortiert man in der Gesamtheit aller Pixel eines laufenden Blocks die Pixel aus, für die die Distorsionsfunktion Δ entweder maximal oder minimal ist, und verwendet das Aussortierte im Falle der Unterteilung in Zonen derart, daß zwei aneinanderliegende Zonen abwechselnd positive und negative Funktionen α aufweisen.
• Dafür enthält das Aussortierorgan:
• - eine Vorzeichen-Auswahlvorrichtung 70, von der Abtasteinheit 27 gesteuert,
• - eine Registerbatterie 71 zum Speichern der maximalen/minimalen Werte jeder Zone,
• - einen Vergleicher 72, der für jede Zone entweder den maximalen oder minimalen beizubehaltenden Wert nach dem entsprechenden Vorzeichen bestimmt.
• Die Adressen der ausgewählten Referenzpixel werden im Adressenregister 52 gespeichert, das die Adressen von ADP-Pixeln und die Adressen von ADZ-Zonen von der Abtasteinheit 27 erhält.
• Die Abtasteinheit 27 gibt den Takt der jeder Zone zugeteilten abwechselnden Vorzeichen + und - vor. Wenn einer Zone das positive Vorzeichen zugeteilt wird, nimmt man das Ergebnis aus dem Rechenorgan 50 mit seinem Vorzeichen, um mit dem für dieselbe Zone in der Registerbatterie 71 zuvor gespeicherten Wert verglichen zu werden. Wenn dieser letztere Wert der höhere ist, ersetzt er den alten Wert in der Registerbatterie 71. Zugleich wird die Adresse des entsprechenden ADP-Pixels im Adressenregister 52 gespeichert.
• Wenn einer anderen Zone das negative Vorzeichen zugeteilt wird, nimmt man das Ergebnis aus dem Rechenorgan 50 mit umgekehrtem Vorzeichen. Er wird mit dem für dieselbe Zone in der Registerbatterie 71 zuvor gespeicherten Wert verglichen. Aufgrund der Vorzeichenumkehrung arbeitet der Vergleicher im einen und anderen Fall bei der Maximalbestimmung auf dieselbe Weise.
• Am Ende des Abtastens enthält das Adressenregister 52 das Ergebnis der Aussortierung, d. h. für jede Zone die Adresse des ausgewählten Pixels mit der maximalen oder Minimalen Distorsion der Zone.
• Das Schema der Fig. 6 entspricht der Berechnung der Distorsionsfunktion relativ zu Fig. 4A. Unter Verwendung dieser Methode kann der Fachmann problemlos das Schema der Recheneinheit zur Berechnung der Distorsions- Funktionsbeispiele der Fig. 4B, 4C und 4D aufstellen.
• Für eine kompakte und regelmäßige Implementierung nach diesem Aspekt der Erfindung ist es interessant, daß die Korrelationsvorrichtung mit Blöcken zu N · N Pixeln arbeitet, wobei N = 16, unter denen n Referenzpixel gewählt werden, wobei n = 8.
• Bis jetzt waren die Anzahl Referenzsymbole in einem laufenden Block begrenzt und vorausbestimmt, die Auswahl bezog sich auf die Position der in einem laufenden Block ausgewählten Pixel. Die Anzahl selbst kann auf verschiedene Weisen bestimmt werden. Wenn die Anzahl Pixel pro laufendem Block gering ist, können unter Berücksichtigung des zu verarbeitenden Bildtyps (also der Konfiguration) vorhergehende Tests durchgeführt werden. Man reduziert bei jedem Test die Anzahl ausgewählter Referenzpixel, man berechnet eine Fehlerfunktion zwischen dem Ausgangsbild und dem wiederhergestellten Bild und man bestimmt diese Anzahl nach einem annehmbaren Fehlerniveau. Eine selbe Anzahl kann auf mehrere Bildtypen angewandt werden.
• Wenn die Anzahl Referenzpixel pro laufendem Block ansteigt, kann die Methode mit vorhergehenden Tests mühselig werden. Dann ist es vorzuziehen, die Bilder an den Charakteristiken zu analysieren, die für die Verteilung der Pixel repräsentativ sind. Im diesem Falle empfiehlt die Erfindung, die sogenannte Technik der "Analyse prinzipieller Komponenten" der besagten Verteilung zu verwenden (hier im mathematischen Sinne des Ausdrucks verwendet). Man berechnet die eigenen Werte der zu dieser Verteilung relativen Korrelationsmatrix und die entsprechenden Varianzen, unter denen man die Anzahl höchster Varianzen bestimmt, die ausreichen, um das Bild korrekt zu repräsentieren. Diese Anzahl Varianzen ist es, die als begrenzte Anzahl Referenzpixel gewählt wurde. Diese Berechnung kann für typische Bilder im voraus durchgeführt und dann in der Korrelationsvorrichtung verwendet werden. Doch es ist auch möglich, sie adaptiv nach den der Korrelationsvorrichtung gelieferten Bilder zu machen. So kann die begrenzte Anzahl Referenzpixel dynamisch den zu verarbeitenden Bildern angepaßt werden, um eine präzisere Verarbeitung durchzuführen. Der Takt zur Durchführung der Berechnung hängt von den Bildern ab, die das Neuronennetz unter Verwendung der Technik "Analyse prinzipieller Komponenten" zu verarbeiten hat. Dies ist auf dem Schema der Fig. 7 dargestellt, die die gleichen Elemente wie die Fig. 2 aufweist, mit zusätzlich einem Neuronennetz 29, das die zu verarbeitenden Bildblöcke empfängt, und der Auswahleinheit 26 die begrenzte Anzahl auszuwählender Referenzpixel liefert.
• Fig. 8 zeigt das Schema einer klassischen Korrelatorstruktur. Sie besteht aus systolischen Netzen mit a.b Zellen, wobei a und b die Dimensionen des Suchfensters sind. Jede Zelle enthält ein Register R, das den Wert eines Musters speichert, und einen elementaren Prozessor P, mit dem Register R verbunden, der die Korrelationsfunktion berechnet. Der Korrelator enthält genauso viele Zellen, wie sich zu analysierende Pixel im Fenster befinden. Jede Zelle hat eine bestimmte Position in bezug auf das Fenster, also einen ihr eigenen Versetzungsvektor.
• Fig. 8 zeigt einen Korrelator mit 9 Zellen. Ein erster Rang enthält die Zellen R&sub1;&sub1;/P&sub1;&sub1; bis R&sub1;&sub3;/P&sub1;&sub3;, ein zweiter Rang enthält die Zellen R&sub2;&sub1;/P&sub2;&sub1; bis R&sub2;&sub3;/P&sub2;&sub3;, ein dritter Rang enthält die Zellen R&sub3;&sub1;/P&sub3;&sub1; bis R&sub3;&sub3;/P&sub3;&sub3;. Jedes Register ist mit seinen vier nächsten Nachbarn über 3 Empfangsverbindungen und 3 Sendeverbindungen verbunden. So empfängt z. B. das Register R22 die Daten der Register R&sub1;&sub2;, R&sub2;&sub1;, R&sub3;&sub2;. Dasselbe Register R&sub2;&sub2; liefert den Registern R&sub1;&sub2;, R&sub2;&sub3;, R&sub3;&sub2; die Daten. Jedes Register enthält aufeinanderfolgend die Daten bezüglich aller Pixel eines zu analysierenden Blocks. Der dem besagten Register zugeteilte Prozessor berechnet jedesmal die Korrelationsfunktion zwischen diesem Datensatz und dem Wert ECH des laufenden Musters, das an alle Prozessoren verteilt wird. Wenn c und d die Dimensionen des zu analysierenden Blocks sind, benötigt jeder Prozessor c.d Zyklen, um die gesamte Distorsionsfunktion in bezug auf einen zu analysierenden Block anzuhäufen. Bei jedem Zyklus überträgt man der Gesamtheit der Prozessoren den Wert des Musters des laufenden Blocks, und man versetzt um einen Schritt die Gesamtheit der Inhalte der Register R, derart, daß für jeden Prozessor immer dieselbe Versetzung D zwischen dem Datensatz des Registers R und dem übertragenen Datensatz besteht. Die (nicht dargestellten) Nebenorgane ermöglichen die Bestimmung des Prozessors, der die beste Korrelation liefert, um über die Position dieses besten Prozessors den Versetzungsvektor im Netz abzuleiten. Man benötigt folglich a.b Zellen, die über c.d Zyklen arbeiten.
• In der Struktur von Fig. 8 ist ein Prozessor einem Register zugeteilt, um die Gesamtheit der Pixel eines laufenden Blocks zu verarbeiten. Nach der Erfindung sind die zu verarbeitenden Pixel begrenzt, was Anordnungen ermöglicht, die entweder der Geschwindigkeit bei weitgehend analoger Hardware, oder der Größe der Hardware bei weitgehend konstanter Geschwindigkeit zugutekommen.
• Grundlegende Vorteile werden erhalten, wenn der laufende Block in Zonen unterteilt wird. Die Fig. 9A, 9B zeigen schematisch die vorgenommene Verarbeitung. Fig. 9B zeigt einen laufenden Block 22, der in 6 Zonen unterteilt wird, z. B. die Zone 22&sub1;, die selbst aus Pixeln gebildet wird. Eine Zone enthält in diesem Beispiel 9 Pixel, unter denen die Referenzpixel gewählt werden.
• Dazu ist in einem Bild 10 ein zu verarbeitendes Fenster 13 dargestellt. Die Verarbeitung des gesamten Bildes besteht in der Durchführung aufeinanderfolgender Verarbeitungen einer Folge solcher Fenster. Wie zuvor beschrieben besteht die Korrelationsberechnung in der pixelweise Korrelierung des laufenden Blocks 22 mit jedem zu verarbeitenden Block, das Fenster von z. B. Block 12 bildend. Alle zu verarbeitenden, im Fenster enthaltenen Blöcke werden durch Verschiebung eines Schrittes 1 Pixel, aufeinanderfolgend in beide Richtungen, erhalten. Block 12 verschiebt sich nacheinander um ein Pixel auf Block 12&sub1; (Punkte), dann auf Block 12&sub2; (Kreuze). Sie wurden für ihre Darstellung leicht vertikal versetzt. Im Falle der Block 22 in Zonen unterteilt wird, findet die Korrelationsberechnung mit den zu verarbeitenden Blöcken auf zwei Niveaus statt.
• Man betrachtet zuerst die Referenzpixel einer bestimmten Zone, z. B. die der Zone 22&sub1; des laufenden Blocks (oben links).
• Man berechnet die Korrelation der Pixel jedes zu verarbeitenden Blocks (in einem Fenster) mit derselben relativen Position im Block, d. h. für dieselbe Zone oben links im Block. Man erhält so die Zwischenergebnisse bezüglich einer bestimmten Zone für alle Blöcke. Die Berechnung umfaßt dann die folgende Zone nach demselben Verfahren.
• Die Verarbeitung wird folgendermaßen schematisiert
• - erste Zone:
• - erster Block
• - zweiter Block
• - ..........
• - zweite Zone:
• - erster Block
• - zweiter Block
• - ..........
• - dann folgende Zonen
• - dann folgende Fenster
• Der Berechnungsablauf in dieser Reihenfolge weist den Vorteil auf, den Datenaustausch zwischen den Registern zu vermindern, was die Architektur vereinfacht und die Berechnungszeit verkürzt.
• Fig. 10 zeigt die für den Ablauf der Korrelationsberechnungen erforderlichen Basisorgane. Das Schema zeigt nur einen Prozessor und ein Register, doch die Situation ist für die anderen Prozessoren und die anderen Register identisch.
• Ein beliebiges Register 40 ist mit anderen benachbarten Registern verbunden, z. B. in den vier Richtungen N, S, E, W über Zweirichtungs- oder Einrichtungs-Busse nach der verwendeten Architektur. Diese Datentransfers zwischen den Registern werden von den allen Registern gemeinsamen Steuermitteln 71 gesteuert.
• Ein Prozessor 72 ist mit mehreren dieser Register über die Anschlüsse I&sub1;, I&sub2;, I&sub3;... verbunden, die die Daten der Register übertragen.
• Die Anzahl Anschlüsse hängt auch von der verwendeten Architektur ab. Der Prozessor 72 nimmt die Berechnung in schrittweisen Etappen vor und muß die Zwischenergebnisse in bezug auf die selbst nach Blöcken unterteilten Zonen zwischenspeichern. Diese Zwischenergebnisse werden in Speichermitteln 73 gespeichert.
• Wenn alle Zwischenergebnisse erhalten wurden, werden sie in den Summiermitteln 74 addiert, um für jeden Block die Gesamtheit der sich auf alle Zonen des besagten Blocks beziehenden Zwischenergebnisse zu liefern. Man erhält so eine Serie von Korrelationswerten, die sich auf die verschiedenen Blöcke beziehen, unter denen der mit der besten Korrelation ausgewählt wird und den Block bildet, dessen Position die neue Position des laufenden Blocks im Bild bildet.
• Fig. 11 zeigt das Schema eines Teils eines Korrelators nach der Erfindung, der eine Reduzierung der Anzahl Zellen bevorzugt. In diesem Fall assoziiert man einen Prozessor P nicht mehr mit einem einzigen Versetzungsvektor, sondern setzt ihn für mehrere Versetzungsvektoren ein, z. B. f Versetzungen (also f Register). In diesem Fall gibt es a.b Register R und a.b/f Prozessoren. Wenn dieser Wert f gleich der Anzahl Punkte pro Zone, also f = c.d/n ist, kann man gewisse der bereits präsentierten Anordnungen nutzen. In diesem Fall ist jedes Register mit seinen nächstliegenden benachbarten Registern verbunden, und ein beliebiger Prozessor (z. B. P&sub8;&sub1;) erhält die in den umgebenden Registern gespeicherten Daten (respektive R&sub8;&sub1;, R&sub8;&sub2;, R&sub9;&sub1;, R&sub9;&sub2;). Mit z. B. Zonen zu 4 Pixeln (Fig. 11), aus denen 1 Referenzpixel zur Verarbeitung eines Fensters zu 4 · 4 Pixeln gewählt wird, benötigt man dann 16 Register und 4 Prozessoren. Alle diese Prozessoren erhalten ein Auswahlsignal SEL, das das in dieser Zone ausgewählte Pixel anzeigt. Diese Architektur ist leicht auf Fälle mit Zonen zu k Pixeln zu übertragen, unter denen man ein einziges Referenzpixel pro Zone auswählt. Jeder Prozessor liefert die Ergebnisse seiner Berechnung an einen eigenen Ausgang, z. B. S81 für den Prozessor P81. Wenn allgemeiner a und b die Dimensionen des Fensters sind, c und d die Dimensionen des laufenden Blocks mit n pro Zone ausgewählten Referenzpixeln, verfügt der Korrelator über a.b Register, a.b/f Prozessoren und arbeitet über c.d Zyklen.
• Fig. 12 zeigt das Schema eines repetitiven Teils eines Korrelators nach der Erfindung, der im Falle einer Unterteilung der laufenden Blöcke in Zonen einen Geschwindigkeitsgewinn bevorzugt. Dieses Schema entspricht Zonen mit 4 Pixeln, von denen zur Vornahme der Korrelation ein einziges Referenzpixel ausgewählt wird. Die für eine bestimmte Zone durchzuführende Verarbeitung wird von den im Innern der gestrichelten Markierung 90 befindlichen Organen vorgenommen. Dort findet man vier Register R&sub5;&sub1;, R&sub5;&sub2;, R&sub6;&sub1;, R&sub6;&sub2;, alle zum selben Prozessor P&sub5;&sub1; verbunden. Jedes Register ist nicht mehr direkt mit dem ihm vorausgehenden und dem ihm nachfolgenden Register verbunden wie in Fig. 8, sondern die Zeilen- und Spaltenverbindungen überspringen ein Register von zweien. Diese Anordnung entspringt der Tatsache, daß bei der Auswahl eines einzigen Pixels von 4 Pixeln pro Zone, man ein Pixel von 2 in beide Richtungen überspringen muß (Fig. 3D).
• Ein Auswahlsignal SEL ermöglicht es, den Prozessor mit einem der vier ihn umgebenden Registern arbeiten zu lassen, in denen er zu einen bestimmten Zeitpunkt die Werte der 4 Pixel der Zone speichert. In einem allgemeineren Fall, wenn der Block c.d Pixel enthält, aus denen n Referenzpixel gewählt werden, benötigt man folglich c.d/n Verbindungen zwischen jedem Prozessor und den benachbarten Registern. Der Wert ECH des Musters wird simultan an alle Prozessoren zur Berechnung der Korrelation verbreitet. Mit einem Fenster mit a.b Blöcken ist ein über n Zyklen arbeitender Korrelator mit a.b Zellen erforderlich. Jeder Prozessor liefert das Ergebnis seiner Berechnung an einen eigenen Ausgang, z. B. S51 für den Prozessor P51.

Claims (13)

1. Korrelationsvorrichtung, die mit zwei Eingangssignalen arbeitet, die zwei in Blöcken organisierte Symbole entsprechend einer regelmäßigen Konfiguration darstellen, und beinhaltet

- einen Korrelator (25) zur Bestimmung einer Korrelation zwischen Symbolen eines laufenden Blocks (22) und Symbolen (12) mit identischen Positionen in einer zu verarbeitenden Blockfolge, die aus der besagten Konfiguration herrührt,

- und Auswahlmittel (26), die unter den Symbolen des besagten laufenden Blocks eine begrenzte Anzahl Referenzsignale auswählen, die Korrelation einbeziehend, wobei diese Anzahl auf einen unter der Anzahl Symbole pro Block liegenden Wert begrenzt ist,

dadurch gekennzeichnet, daß die Auswahlmittel (26) in dem besagten laufenden Block n Referenzsymbole auswählen, wobei n mindestens gleich 1, und die Position eines Symbols gewählt wird

- entweder unter Berücksichtigung des informationellen Inhalts des besagten laufenden Blocks,

- oder nach einer Zufallswahl,

- oder für einen ersten Teil prioritär unter Berücksichtigung des informationellen Inhalts und für einen zweiten Teil nach einer Zufallswahl.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß dieselbe Zufallswahl für mehrere laufende Blöcke gewählt wird, um in jedem Block die Position der n zufällig ausgewählten Referenzsymbole auszuwählen.

3. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die besagte, dem informationellen Inhalt angepaßte Position ausgehend von einer Distorsionsfunktion bestimmt wird, für jedes Symbol des laufenden Blocks hinsichtlich der umgebenden Symbole berechnet, während die n ausgewählten Referenzsymbole unter den Symbolen des laufenden Blocks gewählt werden, von denen die Werte der Distorsionsfunktion in bezug auf die umgebenden Symbole am meisten abweichen.

4. Vorrichtung nach Anspruch 3, dadurch gekennzeichnet, daß die besagte Distorsionsfunktion unter Berechnung eines Lapicien-Operators bestimmt wird, der sich auf eine dem Eingangssignal eigene Charakteristik bezieht.

5. Vorrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß der laufende Block in mehrere Zonen unterteilt wird, während die Auswahlmittel einzeln in jeder Zone arbeiten und die Korrelation über die Gesamtheit der ausgewählten Referenzsymbole des laufenden Blocks vorgenommen wird.

6. Vorrichtung nach Anspruch 5, dadurch gekennzeichnet, daß die Referenzsymbole einer Zone derart ausgewählt werden, daß die Distorsionsfunktion bei aneinandergrenzenden Zonen entweder maximal oder minimal ist.

7. Vorrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß sie ein Neuronennetz enthält, das die Anzahl Referenzsymbole adaptiv unter Berücksichtigung des informationellen Inhalts unter Berechnung der der Korrelationsmatrix eigenen Werte und der Varianzen bestimmt, wobei die Anzahl Symbole gleich der Anzahl der höchsten, für die Gesamtheit der Eingangssignale charakteristischen Varianzen ist.

8. Vorrichtung nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, daß die nach einer regelmäßigen Konfiguration organisierten Symbole ein Bild bildende Pixel sind, während die Korrelationsvorrichtung in Blöcken zu N · N Referenzpixeln arbeitet, mit N größer 1, unter denen die n Referenzpixel mit n < n² ausgewählt werden, die Korrelationen zwischen einem laufenden Block und Blöcken eines im Fenster genommenen Bildes bestimmt werden, der laufende Block aus einem vorhergehenden oder nachfolgenden Bild herrührt, um die Versetzungsvektoren der Bildblöcke zu bestimmen.

9. Vorrichtung nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, daß die Symbole binär codierte Werte sind, die eine Konfiguration eindimensionaler Akustiksignale darstellen, die Korrelationsvorrichtung arbeitet dann mit den mehrere dieser Werte beinhaltenden laufenden Blöcken, unter denen in begrenzter Anzahl und Position Referenzwerte ausgewählt werden.

10 Vorrichtung nach einem der Ansprüche 1 bis 9, die eine Berechnung der Versetzungsvektoren in bezug auf eine in einem Fenster enthaltene Datenblockfolge durchführt, dadurch gekennzeichnet, daß der Korrelator eine Korrelationsberechnung mit laufenden Datenblöcken vornimmt, unterteilt in p Zonen mit n/p pro Zone ausgewählten Referenzsymbolen, wobei der Korrelator enthält:

- ein systolisches Registernetz zum internen Austausch der Pixeldaten des Fensters,

- eine Vielzahl an Prozessoren, wobei jeder Prozessor eine Korrelationsberechnung mindestens eines Versetzungsvektors durchführt, die Vorrichtung einen ersten Berechnungsschritt vornimmt, in dessen Verlauf:

a) jeder Prozessor aufeinanderfolgend eine Korrelationsberechnung der n/p ausgewählten Referenzsymbole einer ersten Zone vornimmt und die besagte Berechnung aufeinanderfolgend alle Versetzungsvektoren einbezieht, die der besagte Prozessor zu berechnen hat,

b) Speichermittel die von den Prozessoren am Ende von a) ausgegebenen Zwischenergebnisse speichern,

c) Übertragungsmittel den Inhalt der in einer Zone arbeitenden Register zu den folgenden, in einer folgenden Zone arbeitenden Register übertragen, der erste Berechnungsschritt dann für die p-1 folgenden Zonen wiederholt wird, wobei Summiermittel die Summe der Zwischenergebnisse in bezug auf jeden zu verarbeitenden Block bestimmen, um die Korrelation der besagten Blockfolge zu liefern.

11. Vorrichtung nach Anspruch 10, dadurch gekennzeichnet, daß die nach einer regelmäßigen Konfiguration organisierten Symbole ein Bild bildende Pixel sind, während der Korrelator in einem zweidimensionalen Pixelfenster mit den laufenden Blöcken arbeitet, unterteilt in rechteckige Zonen mit k Pixeln und einem einzigen pro Zone ausgewählten Referenzpixel, mit k > 1, eine wobei eine zweidimensionale Registermatrix zu einem bestimmten Zeitpunkt die Pixel des besagten Fensters nach derselben Anordnung speichert, k Register der Verarbeitung einer Zone zugeteilt sind, die Fensterpixel in beide Richtungen der Matrix zwischen den Reihen der besagten Register übertragen werden, ein Prozessor der aufeinanderfolgenden Verarbeitung von k Versetzungsvektoren zugeteilt ist und mit k Registern arbeitet, die zur selben Zone gehörende Pixel enthalten, die Ordnungsnummern der besagten paarweise genommenen Pixel in beide Richtungen aufeinanderfolgen, und ein Auswahlsignal jeden Prozessor für jede Versetzung mit den in der laufenden Zone ausgewählten Referenzpixeln entsprechenden Registerdaten arbeiten läßt.

12. Vorrichtung nach Anspruch 10, dadurch gekennzeichnet, daß der Korrelator der Korrelator in einem zweidimensionalen Pixelfenster mit laufenden Blöcken (22) arbeitet, die in Zonen (22i) mit jeweils 4 Pixeln unterteilt sind, mit einem einzigen ausgewählten Referenzpixel pro Zone, wobei eine zweidimensionale Registermatrix zu einem bestimmten Zeitpunkt die Pixel des besagten Fensters nach derselben Anordnung speichert, vier Register (R&sub5;&sub1;, R&sub5;&sub2;, R&sub6;&sub1;, R&sub6;&sub2;) der Verarbeitung (90) einer Zone zugeteilt sind, die Pixel gerader Ordnung des Fensters von den besagten Registerreihen untereinander in beide Richtungen der Matrix übertragen werden und die Pixel ungerader Ordnung von anderen Registerreihen übertragen werden, diese Verbindung nach einer Richtung des Fensters in eine Richtung und nach der anderen Richtung des Fensters in zwei Richtungen verläuft, ein Prozessor (P&sub5;&sub1;) der Verarbeitung jedes Versetzungsvektors zugeteilt ist und mit vier Registern arbeitet, die gerade und ungerade Fensterpixel enthalten, die Ordnungsnummern der besagten paarweise genommenen Pixel in jede Richtung aufeinanderfolgen, und ein gemeinsames Auswahlsignal (SEL) die Prozessoren mit den im laufenden Block ausgewählten Referenzpixeln entsprechenden Registerdaten arbeiten läßt.

13. Verarbeitungsmethode von aus Pixeln gebildeten Bildern, nach einer regelmässigen Konfiguration in Blöcken organisiert, wobei die Methode folgende Schritte umfasst:

- Bestimmung (25) einer Korrelation zwischen den Pixeln eines laufenden Blocks (22) und den Pixeln (12) mit identischen Positionen in einer aus der besagten Konfiguration kommenden, zu verarbeitenden Blockfolge,

- Auswahl (26) unter den Pixeln des besagten laufenden Blocks einer begrenzten Anzahl von der Korrelation einbezogener Referenzpixel, wobei diese Anzahl auf einen unter der Anzahl Pixel pro Block liegenden Wert begrenzt und die Methode dadurch gekennzeichnet ist, dass sie folgenden Schritt enthält:

- Auswahl (26) im besagten Laufenden Block von n Referenzpixeln mit n mindestens gleich 1 wobei die Position eines Pixels gewählt wird:

- entweder unter Berücksichtigung des informativen Inhalts des besagten laufenden Blocks,

- oder nach einer Zufallsauswahl,

- oder für einen ersten Teil vorrangig unter Berücksichtigung des informativen Inhalts und für einen zweiten Teil nach einer Zufallsauswahl.