AT504746B1

AT504746B1 - METHOD FOR STORING AND READING A SUCCESSION OF DATA VALUES

Info

Publication number: AT504746B1
Application number: AT1172007A
Authority: AT
Original assignee: Arc Austrian Res Centers Gmbh
Priority date: 2007-01-23
Filing date: 2007-01-23
Publication date: 2008-07-15
Also published as: DE102008004978B4; DE102008004978A1

Description

2 AT 504 746 B12 AT 504 746 B1

Die JP 2006/285094 A zeigt eine Autofokuskamera und eine Autofokusvorrichtung. Die JP 5108815 A beschreibt einen Bildprozessor. Die SU 605 223 A1 offenbart eine grafische Informations-Auslesevorrichtung. Die US 5 132 803 A erörtert einen Bildaufnehmer mit einem Rahmengrößenspeicher. Die JP 3278281 A beschreibet eine Ausdünnungsprozessvorrichtung eines Bildbearbeitungssystems. Diese Druckschriften beschreiben den allgemeinen Stand der Technik.JP 2006/285094 A shows an autofocus camera and an autofocus device. JP 5108815 A describes an image processor. SU 605 223 A1 discloses a graphic information read-out device. US 5 132 803 A discusses an imager with a frame size memory. JP 3278281 A describes a thinning process apparatus of an image processing system. These documents describe the general state of the art.

Ziel der Erfindung ist die Erstellung eines Ressourcen sparenden Verfahrens zum Auslesen von benachbarten Datenwerten einer Datenfolge aus einem Memory bzw. aus Speichern, in denen Folgen von Datenwerten abgespeichert werden.The aim of the invention is the creation of a resource-saving method for reading out adjacent data values of a data sequence from a memory or from memories in which sequences of data values are stored.

Die erfindungsgemäße Vorgangsweise verringert insbesondere den Rechenaufwand, wenn viele benachbarte Datenwerte aus Speichern ausgelesen werden sollen, wie dies insbesondere im Fall von Neighbourhood-Auswertealgorithmen der Fall ist. Insbesondere wenn räumliche Pixelbeziehungen datenmäßig erfasst bzw. ausgewertet werden sollen, wie z.B. bei der Filterung von digitalen Bildern oder bei Mittelwertbildungen von benachbarten Pixelgruppen, bringt die erfindungsgemäße Vorgangsweise beträchtliche Vorteile.In particular, the procedure according to the invention reduces the computational outlay when many adjacent data values are to be read from memories, as is the case in particular in the case of neighborhood evaluation algorithms. In particular, when spatial pixel relationships are to be acquired or evaluated in terms of data, such as e.g. when filtering digital images or averaging adjacent pixel groups, the inventive approach provides significant advantages.

Ein Beispiel für eine aufwändige Auswertung von Datenwerten ist die optische Qualitätskontrolle von Druckwerken wie etwa Banknoten, Briefmarkenbögen, Etiketten, aber auch Bögen für Buchdruck und Verpackungsdruck sowie alle Arten von Bogen- und Rollendruck. Die zu prüfenden Gegenstände werden mit einer Zeilen- oder Flächenkamera aufgenommen und die erhaltenen Bilddaten werden einer Bildvergleichseinheit zugeführt, um den Gegenstand zu prüfen bzw. ihn zu identifizieren oder klassifizieren.An example of an elaborate evaluation of data values is the optical quality control of printing units such as banknotes, stamp sheets, labels, as well as sheets for book printing and packaging printing as well as all types of sheetfed and web printing. The objects to be inspected are taken with a line or area camera, and the obtained image data are supplied to an image comparison unit to inspect, identify or classify the object.

Ein Problem, das dabei auftritt, ist, dass der Gegenstand am Bild nicht in der erwarteten Lage, sondern verschoben, verdreht und/oder verzerrt erscheint. Diese Verzerrungen können durch Dehnung und/oder Verzug des zu prüfenden Materials und/oder durch Lageänderungen, etwa bedingt durch den Transport des Gegenstandes und/oder durch Linsenverzerrungen bzw. eine nicht perfekte optische Abbildung hervorgerufen werden.One problem that arises is that the subject does not appear in the expected position but shifted, twisted, and / or distorted. These distortions can be caused by stretching and / or distortion of the material to be tested and / or by changes in position, for example due to the transport of the object and / or lens distortions or a non-perfect optical image.

Um den aufgenommenen Gegenstand prüfen bzw. vermessen oder vergleichen zu können, muss das Bild in eine vorgegebene Soll-Lage transformiert werden.In order to check or measure or to be able to compare the recorded object, the image must be transformed into a predetermined desired position.

Dies erfolgt gemäß dem Stand der Technik, indem eine Rückwärtstransformation des Bildes aus den so genannten Zielkoordinaten (x\ y') auf die Ursprungskoordinaten (x, y) erfolgt.This is done according to the prior art by a backward transformation of the image from the so-called target coordinates (x \ y ') to the original coordinates (x, y).

Zur Erstellung des Zielbildes werden die (ganzzahligen) Zielkoordinaten nach einer vorgegebenen Reihenfolge (vorzugsweise zeilenweise) durchlaufen. Für jeden Zielpunkt (x\ y') werden die Ursprungskoordinaten (x, y) bestimmt und von dieser Position der Wert des aktuellen Bildpunktes ermittelt und in das Zielbild eingetragen. Im Allgemeinen sind die rückwärts transformierten Koordinaten (x, y) nicht ganzzahlig.To create the target image, the (integer) target coordinates are traversed in a predetermined sequence (preferably line by line). For each target point (x \ y ') the origin coordinates (x, y) are determined and from this position the value of the current pixel is determined and entered into the target image. In general, the backward transformed coordinates (x, y) are not integer.

Um nun den Wert des Bildpunktes an der Stelle (x, y) ermitteln zu können, wird dieser aus den umliegenden Bildpunkten des Ursprungsbildes durch Interpolation ermittelt. Die Interpolation ist dabei eine Schätzung.In order to be able to determine the value of the pixel at the point (x, y), it is determined from the surrounding pixels of the original image by interpolation. The interpolation is an estimate.

In den meisten Fällen wird eine lineare Interpolation durchgeführt. Sei X der ganzzahlige Anteil von x und Y der ganzzahlige Anteil von y, dann wird bei der Interpolation eine gewichtete Summe der Bildpunkte (Χ,Υ ) (X+1, Y ) (X, Y+1 ) (X+1.Y+1) bestimmt. 3 AT 504 746 B1In most cases, a linear interpolation is performed. If X is the integer part of x and Y is the integer part of y, then a weighted sum of the pixels (Χ, Υ) (X + 1, Y) (X, Y + 1) (X + 1.Y +1). 3 AT 504 746 B1

Die Interpolation nach dem linearen Modell ist sehr einfach, es ist jedoch bekannt, dass sie nur eine schlechte Näherung liefert. Sie benötigt am wenigsten Rechenaufwand und die wenigsten Speicherzugriffe.The linear model interpolation is very simple, but it is known to provide only a poor approximation. It requires the least amount of computation and the least memory access.

Bessere Ergebnisse liefern Interpolationen höherer Ordnung, etwa Spline -Interpolationen oder Bezier-Interpolationen. Alle Interpolationen höherer Ordnung benötigen zur Berechnung des Ergebnisses eine größere Anzahl von Bildpunkten. Für eine Interpolation dritten Grades, z.B. Spline - Interpolationen, werden die Punkte (X-1.Y-1 ) (X.Y-1 ) (X+1.Y-1) (X+2.Y-1) (X-1.Y ) (X, Y ) (X+1.Y ) (X+2, Y ) (X-1.Y+1) (X, Y+1 ) (X+1.Y+1) (X+2.Y+1) (X-1.Y+2) (X.Y+2) (X+1.Y+2) (X+2, Y+2) benötigt.Better results are provided by higher-order interpolations, such as spline interpolations or Bezier interpolations. All higher-order interpolations require a larger number of pixels to calculate the result. For third degree interpolation, e.g. Spline - interpolations, the points (X-1.Y-1) become (XY-1) (X + 1.Y-1) (X + 2.Y-1) (X-1.Y) (X, Y ) (X + 1.Y) (X + 2, Y) (X-1.Y + 1) (X, Y + 1) (X + 1.Y + 1) (X + 2.Y + 1) ( X-1.Y + 2) (X.Y + 2) (X + 1.Y + 2) (X + 2, Y + 2).

Der Nachteil der Interpolationen höherer Ordnung ist der wesentlich höhere Rechen- und Speicherzugriffsaufwand.The disadvantage of higher order interpolations is the significantly higher computational and memory access overhead.

Dieser macht sich besonders dann bemerkbar, wenn die Interpolation in spezieller Elektronik-Hardware realisiert werden soll. Das Ziel bei einer Hardwareimplementierung ist zumeist, dass pro Arbeitstakt mindestens ein Ergebnis berechnet werden soll. Moderne programmierbare Logikbausteine (FPGAs) erlauben Arbeitstakte von weit über 200 MHz. Das Problem dabei ist der gleichzeitige Zugriff auf viele verschiedene Speicherstellen in einem Arbeitstakt. Bei der linearen Interpolation muss pro Arbeitstakt auf 4 Speicherzellen zugegriffen werden. Bei kubischer Interpolation sind es bereits 16 Speicherzugriffe. Dies ist mit sehr hohem Aufwand verbunden, wenn diese Zugriffe gleichzeitig in einem Arbeitstakt erfolgen sollen.This becomes particularly noticeable when the interpolation is to be implemented in special electronic hardware. The goal of a hardware implementation is usually that at least one result should be calculated per work cycle. Modern programmable logic devices (FPGAs) allow operating cycles of well over 200 MHz. The problem here is the simultaneous access to many different memory locations in a work cycle. Linear interpolation requires access to 4 memory cells per power cycle. With cubic interpolation, there are already 16 memory accesses. This involves a great deal of effort if these accesses are to take place simultaneously in one work cycle.

Am Beispiel einer linearen Interpolation mit 4 Pixeln bzw. Datenwerten ergaben sich bisher folgende Lösungsmöglichkeiten, wenn man pro Arbeitstakt ein Ergebnispixel erhalten möchte: • Einsatz eines konventionellen Speichers: dies ist eine relativ simple Lösung mit einem Port. Dazu ist 4 - mal derselbe Wert in vier unabhängige Speicher gleichzeitig zu schreiben und sodann von allen vier Speichern gleichzeitig ein Wert auszulesen. Der Nachteil ist ein sehr hoher (4-facher) Speicherbedarf. • Einsatz eines Dual Port Speichers: Dazu sind 2 mal 2 Werte in zwei unabhängige Speicher gleichzeitig zu schreiben und von beiden Speichern gleichzeitig 2 Werte auszulesen. Bei DSP braucht man 2 Arbeitstakte, weil nur ein interner Dual Port Speicher vorhanden ist. • Einsatz von Quad Port Speichern: Es sind vier Werte in einen Speicher gleichzeitig zu schreiben und gleichzeitig 4 Werte auszulesen. Der Nachteil daran ist, dass derartige Bauteile kaum erhältlich und als externer Bauteil sehr teuer sind.Using the example of a linear interpolation with 4 pixels or data values, the following solution options have been available to date if you want to get one result pixel per working cycle: • Use of a conventional memory: this is a relatively simple solution with one port. For this purpose write four times the same value into four independent memories at the same time and then read out a value from all four memories at the same time. The disadvantage is a very high (4-fold) memory requirement. • Using a dual port memory: 2 times 2 values must be written into two independent memories at the same time and 2 values read out from both memories at the same time. With DSP you need 2 work cycles, because only one internal dual port memory is available. • Use of Quad Port Save: Four values must be written to a memory at the same time and 4 values must be read simultaneously. The disadvantage of this is that such components are hardly available and are very expensive as an external component.

Schwierigkeiten in Hinblick auf die Schnelligkeit der Zugriffe entstehen insbesondere dann, wenn in den abgespeicherten Folgen benachbarte Datenwerte ausgelesen werden sollen, die in verschiedenen Speichern abgespeichert sind.Difficulties with regard to the speed of the accesses arise in particular when adjacent data values which are stored in different memories are to be read out in the stored sequences.

Das Ziel der erfindungsgemäßen Vorgangsweise ist es, aus einer beliebig langen Folge von beliebigen Datenwerten mit einem einzigen, unabhängig adressierbaren (Speicher-) Zugriff gleichzeitig zwei oder mehr beliebige benachbarte Datenwerte auslesen zu können. 4 AT 504 746 B1The aim of the procedure according to the invention is to be able to simultaneously read two or more arbitrary adjacent data values from an arbitrarily long sequence of arbitrary data values with a single, independently addressable (memory) access. 4 AT 504 746 B1

Dieses Ziel wird bei einem Verfahren der eingangs genannten Art mit den im Kennzeichen des Anspruches 1 angeführten Merkmalen erreicht. Durch Anordnung von zusätzlichen Datenfeldern, in denen redundant gespeicherte Datenwerte vorliegen, besteht die Möglichkeit, auch bei in einer Vielzahl von Speichern abgespeicherten Datenwerten einer langen Datenfolge immer innerhalb eines einzigen Speicherzugriffes auf die gewünschte Anzahl von benachbarten Datenwerten zugreifen zu können. Der Nachteil, dass ein Zugriff auf zwei Speicher vorzunehmen ist, wenn in der Folge benachbart liegende Datenwerte abgespeichert bzw. ausgelesen werden sollen, wird vermieden. Es ist lediglich dafür Sorge zu tragen, dass die Adressierung der redundanten Datenwerte bzw. Datenfelder in solcher Weise erfolgt, dass auf die benachbart liegenden Datenwerte bzw. Datenfelder eindeutig zugegriffen werden kann.This object is achieved in a method of the type mentioned above with the features mentioned in the characterizing part of claim 1. By arranging additional data fields in which redundantly stored data values are present, it is possible to always access the desired number of adjacent data values within a single memory access even for data values of a long data sequence stored in a plurality of memories. The disadvantage that an access to two memories is to be made if adjacent data values to be stored or read out in the sequence is avoided. It is only necessary to ensure that the addressing of the redundant data values or data fields takes place in such a way that the adjacent data values or data fields can be uniquely accessed.

Die in den Unteransprüchen angeführten Merkmale stellen vorteilhafte Weiterbildungen der erfindungsgemäßen Vorgangsweise dar.The features mentioned in the dependent claims represent advantageous developments of the procedure according to the invention.

Des Weiteren betrifft die Erfindung einen Datenträger gemäß dem Kennzeichen des Anspruches 7.Furthermore, the invention relates to a data carrier according to the characterizing part of claim 7.

Im Folgenden wird die Erfindung anhand der Zeichnungen beispielsweise erläutert. Fig. 1, 2 und 3 betreffen prinzipielle Darstellungen zur Erläuterung.In the following the invention will be explained with reference to the drawings, for example. Fig. 1, 2 and 3 relate to basic representations for explanation.

Fig. 4, 5, 6 und 7 zeigen spezielle Möglichkeiten zur redundanten Abspeicherung von Datenwerten in Speichern. Fig. 8, 9 und 10 zeigen Beispiele der Abspeicherung bzw. der Ausbildung von Speichern. Fig. 11 bis 14 zeigen eine einfache Ausführungsform für eine Adressierungseinheit bzw. für die Ermittlung von Adressen.4, 5, 6 and 7 show special possibilities for the redundant storage of data values in memories. Figs. 8, 9 and 10 show examples of storage of memories. FIGS. 11 to 14 show a simple embodiment for an addressing unit or for the determination of addresses.

Unter dem Begriff Speicher werden allgemeine Datenwertspeicher mit einer vorgegebenen Speicherkapazität, angegeben in der vorhandenen Anzahl von Bits, verstanden. Ein Memory umfasst eine gewisse Anzahl von Speichern. Jeder Speicher ist aufgeteilt in mehrere gleich große Datenfelder X, wie in Fig. 1 dargestellt. Es kann dabei ein Speicherverschnitt bzw. ungenutzter Speicherrest R entstehen. Die Größe eines Datenfeldes ist durch die vorhandene Anzahl von Bits definiert.The term memory is understood to mean general data value memories having a predetermined memory capacity, stated in the existing number of bits. A memory comprises a certain number of memories. Each memory is divided into several equal-sized data fields X, as shown in Fig. 1. It can create a memory waste or unused memory remainder R. The size of a data field is defined by the number of bits available.

Die Datenwerte bilden den Inhalt je eines Datenfeldes. Die maximale Größe eines Datenwertes hängt dabei von der Datenfeldkapazität ab und berechnet sich als 2Anzahl Blts des Datenfeldes Vorteilhafterweise ist vorgesehen, dass jeder Datenwert der Folge in einem eigenen Datenfeld gespeichert wird bzw. dass die für die Abspeicherung der Datenwerte vorgesehenen Datenfelder des Speichers gleich groß gewählt werden.The data values form the content of each data field. The maximum size of a data value depends on the data field capacity and is calculated as a number of leaves of the data field. Advantageously, it is provided that each data value of the sequence is stored in a separate data field or if the data fields of the memory provided for the storage of the data values are selected to be the same become.

Die Folge von Datenwerten umfasst die Gesamtheit aller abzuspeichernden, auslesbaren Datenwerte.The sequence of data values comprises the entirety of all readable data values to be stored.

Jede Teilfolge umfasst denjenigen Teil der Folge von Datenwerten, der einem bestimmten Speicher zugeordnet ist (Fig. 2).Each subsequence includes that part of the sequence of data values associated with a particular memory (Figure 2).

Im Normalfall enthält ein Speicher genau ein Datenfeld mit genau einem Datenwert. Eine Erweiterung auf zwei, vier oder acht Datenfelder pro Speicher ist üblich und wird in modernen PCs bzw. CPUs angewendet. Verwendete Speicherkapazitäten sind z.B. 8, 16, 32, 36, 64, 72, 128, 144, 256 und 288 Bit. Es werden so beispielsweise immer vier 8-bit große Datenwerte in einem 32 Bit breiten Speicher gespeichert. Mit einem (Speicher-) Zugriff sind also vier 8-bit Datenwerte gleichzeitig verfügbar.Normally, a memory contains exactly one data field with exactly one data value. An extension to two, four or eight data fields per memory is common and used in modern PCs or CPUs. Used storage capacities are e.g. 8, 16, 32, 36, 64, 72, 128, 144, 256 and 288 bits. For example, four 8-bit data values are always stored in a 32-bit memory. With a (memory) access, four 8-bit data values are simultaneously available.

Eine Folge von Datenwerten wird üblicherweise nacheinander in unabhängig adressierbare Datenfelder bzw. Speicher gespeichert. Die in allen folgenden Beispielen verwendete Folge 71694305821524367980 5 AT 504 746 B1 mit jeweils 8 Bit breiten Datenwerten wird beispielsweise gemäß Fig. 3 in einem 32 Bit breiten Speicher gespeichert.A sequence of data values is usually stored sequentially in independently addressable data fields or memory. The sequence 71694305821524367980 5 AT 504 746 B1, which is used in each of the following examples, each having 8-bit-wide data values, for example, is stored in a 32-bit memory according to FIG.

Das Ziel, mit nur einem einzigen (Speicher-) Zugriff zwei beliebige Nachbarn zu lesen, lässt sich nicht ohne weiteres erreichen. Um z.B. den vierten Datenwert „9“ und seinen nächsten (rechten) Nachbarn „4“ zu erhalten, sind unbedingt zwei (Speicher-) Zugriffe auf die Adressen 0 und 1 und somit zwei Arbeitstakte notwendig.The goal of reading any two neighbors with just a single (memory) access can not be easily achieved. For example, To obtain the fourth data value "9" and its next (right) neighbor "4", two (memory) accesses to the addresses 0 and 1 and thus two power strokes are absolutely necessary.

Damit beliebige benachbarte Datenwerte der Folge mit nur einem einzigen (Speicher-) Zugriff gleichzeitig gelesen werden können, müssen alle notwendigen Nachbarschaftskombinationen an je einer Adresse verfügbar sein. Entsprechend der erfindungsgemäßen Vorgangsweise werden die jeweils kritischen Nachbarn vom Anfang der nächsten oder vom Ende der vorangehenden Teilfolge redundant hinter das Ende oder vor den Anfang der aktuellen Teilfolge gespeichert. Für die erfindungsgemäße Vorgangsweise muss die Speicherkapazität der vorgesehenen Speicher erhöht werden; dafür können alle Kombinationen von benachbarten Datenwerten in ein und demselben Zugriff gespeichert bzw. ausgelesen werden.So that any adjacent data values of the sequence can be read simultaneously with only a single (memory) access, all necessary neighborhood combinations must be available at each address. According to the procedure according to the invention, the respectively critical neighbors are stored redundantly behind the end or before the beginning of the current subsequence from the beginning of the next subsequence or from the end of the preceding subsequence. For the procedure according to the invention, the storage capacity of the provided memory must be increased; For this purpose, all combinations of adjacent data values can be stored or read in one and the same access.

In dem Beispiel gemäß Fig. 4 wird die Speicherkapazität von 32 auf 40 Bit erhöht.In the example according to FIG. 4, the storage capacity is increased from 32 to 40 bits.

Bei dieser Abspeicherung der Datenwerte kann durch einen einzigen Zugriff auf die Adresse 0 der Datenwert „9" mit seinem rechten Nachbarn „4" gelesen werden.In this storage of the data values, a single access to the address 0 allows the data value "9 " with his right neighbor "4 " to be read.

In vielen Fällen ist die Speicherkapazität durch die Hardwarearchitektur vorgegeben und kann somit nicht verändert werden. Besonders vorteilhaft ist die erfindungsgemäße Vorgangsweise, wenn bisher freie Speicherkapazitäten benutzt werden können. Gerade in FPGAs sind in der Regel 36, 72 und 144 statt 32, 64 und 128 Bit breite Memories für Parityberechnungen vorhanden. Diese zusätzlichen Speicherkapazitäten der Breite 4, 8 und 16 Bit liegen zumeist brach.In many cases, the storage capacity is dictated by the hardware architecture and thus can not be changed. Particularly advantageous is the procedure according to the invention, if previously free storage capacities can be used. Especially in FPGAs there are usually 36, 72 and 144 instead of 32, 64 and 128 bit wide memories for parity calculations. These additional storage capacities of width 4, 8 and 16 bits are mostly broke.

Eine alternative Möglichkeit, die erfindungsgemäße Vorgangsweise auszuführen, besteht darin, dass die Anzahl der Datenfelder pro Teilfolge verringert wird. Die Speicherkapazität des Speichers bleibt unverändert, z.B. bei 32 Bits.An alternative possibility of carrying out the procedure according to the invention is that the number of data fields per subsequence is reduced. The storage capacity of the memory remains unchanged, e.g. at 32 bits.

In dem Beispiel gemäß Fig. 5 wird die Anzahl der Datenfelder pro Teilfolge von 4 auf 3 reduziert.In the example according to FIG. 5, the number of data fields per subsequence is reduced from 4 to 3.

Jetzt kann durch einen einzigen Zugriff auf die Adresse 1 der Datenwert „9“ mit seinem rechten Nachbarn „4“ gelesen werden.Now, by a single access to the address 1, the data value "9" can be read with its right neighbor "4".

Eine weitere Möglichkeit, die erfindungsgemäße Vorgangsweise auszuführen, besteht darin, dass die Breite des Datenfeldes bzw. die Anzahl der Bits in einem Datenfeld verringert wird. Diese Lösung entspricht prinzipiell der Lösung mit einer Erhöhung der Speicherkapazität, nur mit dem Unterschied, dass jedes Datenfeld jetzt weniger Bits enthält. Es bleibt bei der Speicherkapazität von 32 und die Anzahl der Datenfelder pro Speicher bleibt bei 4. Die maximal mögliche Größe eines Datenwertes wird dabei aber entsprechend verringert.Another possibility for carrying out the procedure according to the invention is that the width of the data field or the number of bits in a data field is reduced. In principle, this solution corresponds to the solution with an increase in storage capacity, with the difference that each data field now contains fewer bits. It remains at the memory capacity of 32 and the number of data fields per memory remains at 4. The maximum possible size of a data value is thereby reduced accordingly.

Wichtig ist in allen Fällen, dass die richtigen Datenfelder aus dem Speicher „maskiert“ werden, um richtig adressiert werden zu können. Gemäß der Lösung entsprechend Fig. 4 sind es die letzten beiden Datenfelder auf Adresse 0, gemäß der Lösung entsprechend Fig. 5 die beiden ersten Datenfelder auf Adresse 1 des Speichers. Dies wird mit einer speziellen Adressierungseinheit ermöglicht.It is important in all cases that the correct data fields are "masked" from the memory in order to be addressed correctly. According to the solution according to FIG. 4, the last two data fields are at address 0, according to the solution corresponding to FIG. 5 the first two data fields are at address 1 of the memory. This is made possible with a special addressing unit.

Zu bemerken ist, dass der erste und der letzte in dem Memory vorhandene Speicher nicht voll ausgenutzt sein müssen. Die erste und die letzte Teilfolge müssen den jeweiligen Speicher 6 AT 504 746 B1 nicht zur Gänze füllen.It should be noted that the first and last memory in the memory need not be fully utilized. The first and the last subsequence need not completely fill the respective memory 6 AT 504 746 B1.

Die Anzahl der benötigten Nachbarn bzw. benachbart auszulesenden Datenwerte bestimmt die Anzahl der redundant gespeicherten Daten, wobei die Anzahl der redundant gespeicherten Datenwerte der um eins verminderten Zahl der gleichzeitig auslesbaren Datenwertnachbarn entspricht.The number of required neighbors or data values to be read out next determines the number of redundantly stored data, wherein the number of redundantly stored data values corresponds to the number of data read neighbors that is reduced by one.

Wie bereits erwähnt, ist es auch möglich, die redundanten Datenwerte vom Ende der aktuellen Teilfolge vor den Anfang der nächsten Teilfolge zu kopieren, anstatt den Anfang der nächsten Teilfolge hinter das Ende der aktuellen Teilfolge. Zwei Möglichkeiten dafür sind in den Fig. 6 und 7 dargestellt. Allerdings ist die Adressierungseinheit für den Multiplexerteil in diesem Fall entsprechend abzuändern.As already mentioned, it is also possible to copy the redundant data values from the end of the current subsequence before the beginning of the next subsequence, rather than the beginning of the next subsequence after the end of the current subsequence. Two possibilities for this are shown in FIGS. 6 and 7. However, the addressing unit for the multiplexer part is to be modified accordingly in this case.

In den Fig. 8, 9 und 10 sind Beispiele dargestellt, wie eine Belegung eines Memorys mit einer Anzahl von Speichern mit einer Datenfolge vorgenommen wird.8, 9 and 10 show examples of how to occupy a memory with a number of memories with a data sequence.

Dabei bedeuten: S = Anzahl der Bits, auf die pro Lesezugriff (pro Port) zugegriffen werden kann T = Anzahl der Bits pro DatenwertWhere: S = number of bits that can be accessed per read access (per port) T = number of bits per data value

R = Anzahl der restlichen (ungenutzten) Bits: R - S - n*T - m*T n = Anzahl der „neuen“ Datenwerte pro Schreib-/Lesezugriff m = Anzahl der „alten“ bzw. redundanten Datenwerte pro Schreib-/LesezugriffR = number of remaining (unused) bits: R - S - n * T - m * T n = number of "new" data values per read / write access m = number of "old" or redundant data values per read / write access

Es ist ferner vorgesehen, dass pro Zugriff auf k = m+1 benachbarte Werte zugegriffen werden kann und dass sich n+m Datenfelder bzw. Datenwerte in einem Speicher befinden.It is further provided that for each access to k = m + 1 adjacent values can be accessed and that n + m data fields or data values are located in a memory.

Es wird bemerkt, dass in den Fig. 8, 9 und 10 die Einheiten der Abszisse nicht identisch sind.It is noted that in Figs. 8, 9 and 10, the units of abscissa are not identical.

Entsprechend Fig. 9 wird das Ende der aktuellen Teilfolge an den Anfang der nächsten Teilfolge redundant gespeichert.According to FIG. 9, the end of the current subsequence is stored redundantly at the beginning of the next subsequence.

Entsprechend Fig. 10 wird der Anfang der nächsten Teilfolge an das Ende der aktuellen Teilfolge redundant gespeichert.According to FIG. 10, the beginning of the next partial sequence is stored redundantly at the end of the current partial sequence.

Die schematisch in Fig. 11 dargestellte Adressierungseinheit ist dafür zuständig, aufgrund einer von außen vorgegebenen Datenfeldnummer bzw. -adresse aus der Folge von Datenwerten den richtigen Speicher und innerhalb dieses Speichers mit Hilfe eines Multiplexers das richtige Datenfeld, das der vorgegebenen Datenfeldnummer bzw. -adresse entspricht und seine benachbarten Datenfelder aus der Folge von Datenwerten auszuwählen.The addressing unit shown schematically in FIG. 11 is responsible, on the basis of an externally given data field number or address from the sequence of data values, the correct memory and within this memory with the aid of a multiplexer the correct data field, that of the given data field number or address and select its neighboring data fields from the sequence of data values.

Im Beispiel gemäß Fig. 12 und 13 sollen das 12. Datenfeld (Datenwert = 5) und sein nächster Nachbar (m = 1) ausgelesen werden (Datenwert = 2). Das bedeutet die Pixeladresse ist 11. Es wird in diesem Beispiel davon ausgegangen, dass die Datenwerte der folgenden Teilfolge redundant an die jeweilige vorangehende Teilfolge anschließend abgespeichert wurden (Fig. 10). Für den Fall, dass die redundanten Datenwerte entsprechend Fig. 9 an den Anfang der nächsten Teilfolge gespeichert wurden, erfolgt die Berechnung der Adressen in ähnlicherWeise.In the example according to FIGS. 12 and 13, the 12th data field (data value = 5) and its nearest neighbor (m = 1) are to be read out (data value = 2). This means that the pixel address is 11. In this example, it is assumed that the data values of the following subsequence were subsequently stored redundantly to the respective preceding subsequence (FIG. 10). In the case that the redundant data values corresponding to FIG. 9 have been stored at the beginning of the next subsequence, the calculation of the addresses takes place in a similar way.

Die Startwerte für Adressen und Nummern sind immer 0. D.h. der erste Speicher innerhalb des gesamten Memory hat die Adresse 0 und das erste Datenfeld innerhalb eines Speichers hat die Datenfeldadresse 0.The starting values for addresses and numbers are always 0. the first memory within the entire memory has the address 0 and the first data field within a memory has the data field address 0.

Die Adresse für den Speicher berechnet sich wie folgt:The address for the memory is calculated as follows:

Die Adresse im Memory entspricht dem ganzzahligen Anteil des Wertes Pixeladresse / n, imThe address in the memory corresponds to the integer part of the value Pixeladdress / n, in

Claims

7 AT 504 746 B1 case 11/4 = 2.75. The integer part is 2, so that the address in memory is equal to 2. The address within the memory required by the multiplexer for the masking is calculated as follows: The address within the memory corresponds to the remainder of the division pixel address / n. In the present case 11/4, the address within the memory then becomes 3. Within of the memory, the searched data field is thus the fourth field. The multiplexer now only has to know how many adjacent data fields should be read. The generation of the addresses according to FIGS. 12 and 13 is particularly simple when n is a power of two (n = 2X). Then the bits from the pixel address can be used directly for the addressing of the memory and the multiplexer and the divisions and modulo operations (computation of the remainder) are omitted since for binary numbers the division by powers of 2 is a shift of the binary number equivalent. In these figures, the pixel address and data field number are shown in binary. In the example given for the 12th data field, x = log2 (n) = 2 and the binary representation of the pixel address corresponding to Fig. 14. Claims 1. A method for storing and reading out a sequence of data values into or out of a number independently addressable and readable data fields of memories, wherein the sequence of the data values are subdivided into preferably equally long subsequences and the data values of each subsequence are stored in the data fields of the respective memory in sequence, characterized in that - for reading immediately successive data values Sequence, which are stored in adjacent data fields, in a single memory access step in each memory preceding or subsequent to the subsequence associated therewith and stored in its data fields, a number of data values immediately preceding or following that subsequence in the sequence of data values immediate before or after the data fields in which the subsequence has been stored, additionally stored data fields, wherein the number (m) of these redundantly stored in the additional data fields data values or these additional data fields of 1 reduced number (k) of the simultaneously readable adjacent Data values or data fields correspond to (m = k-1).

2. The method according to claim 1, characterized in that each data value of the sequence is stored in a separate data field.

3. The method of claim 1 or 2, characterized in that with each independently addressable memory access a predetermined number (k) of data values or data fields is stored or read.

4. The method according to any one of claims 1 to 3, characterized in that the provided for the storage of the data values data fields of the memory are chosen to be the same size.

5. The method according to any one of claims 1 to 4, characterized in that are used as memory FPGA memory whose storage capacity is 2n bits (n = 1 .... k) plus a predetermined number of parity bits. 8 AT 504 746 B1

6. The method according to any one of claims 1 to 5, characterized in that the method for storing and reading sequences of data values is used, which are incurred in interpolation of data or in Neighborhood Auswertealgorithmen, in particular in the optical inspection of objects.

7. disk, characterized in that it is stored on a program for carrying out the claimed in claims 1 to 6 method. For this purpose 6 sheets of drawings