EP0289629B1 - Méthode de transformation spectrale bidimensionnelle - Google Patents

Méthode de transformation spectrale bidimensionnelle Download PDF

Info

Publication number
EP0289629B1
EP0289629B1 EP19870106348 EP87106348A EP0289629B1 EP 0289629 B1 EP0289629 B1 EP 0289629B1 EP 19870106348 EP19870106348 EP 19870106348 EP 87106348 A EP87106348 A EP 87106348A EP 0289629 B1 EP0289629 B1 EP 0289629B1
Authority
EP
European Patent Office
Prior art keywords
matrix
transformation
store
data
spectral
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
EP19870106348
Other languages
German (de)
English (en)
Other versions
EP0289629A1 (fr
Inventor
Rolf Dipl.-Ing. Singer
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Bosch Telecom GmbH
Original Assignee
ANT Nachrichtentechnik GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by ANT Nachrichtentechnik GmbH filed Critical ANT Nachrichtentechnik GmbH
Priority to DE8787106348T priority Critical patent/DE3773192D1/de
Priority to EP19870106348 priority patent/EP0289629B1/fr
Publication of EP0289629A1 publication Critical patent/EP0289629A1/fr
Application granted granted Critical
Publication of EP0289629B1 publication Critical patent/EP0289629B1/fr
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/147—Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform

Definitions

  • the present invention relates to a method for the two-dimensional spectral transformation of a data set, in which the data to be transformed are written from the original area into a first memory, and by means of two matrix multiplications between the data matrix recorded in the first memory and a transformation matrix, the individual data from the original area in coefficients of the spectral range can be transformed, the matrix resulting from the first matrix multiplication being stored in a separate memory and both matrix multiplications being carried out with the same computing device.
  • Two-dimensional spectral transformation e.g. B. the discrete Fourier, the discrete cosine, the Walsh-Hadamard, the hair, the slant transformation etc. are theoretically described in the book by N. Ahamed, KR Rao "Orthogonal Transforms for Digital Signal Processing", Springer Verlag Berlin, Heidelberg, New York, 1975.
  • a coefficient matrix in the spectral range arises from the data matrix in the original range by first multiplying the data matrix by the transformation matrix and then transposing the resulting matrix by the transformation matrix.
  • a circuit specified in the document which carries out this transformation from the original to the spectral range, can also be used for the reverse transformation from the spectral to the original range.
  • the transformation reversal requires a different modulation of several circuit units.
  • the invention has for its object to provide a method of the type mentioned, the execution of which is possible with a circuit with which the reverse transformation from the spectral to the original range can also be carried out and for this purpose as few circuit parts as possible have to be controlled differently than in the transformation from the original to the spectral range.
  • GB-A-2 141 847 shows that matrix multiplication with several multipliers can be carried out in parallel.
  • WO 88/07725 is state of the art within the meaning of Article 54 (3) EPC. It discloses a method for two-dimensional spectral transformation which differs from the subject matter of claim 1 in that it does not describe the last characteristic feature of this claim.
  • the figure shows a schematic diagram of function blocks, which is intended to illustrate the process sequence for transforming a data record from the time domain into the spectral domain or vice versa.
  • a matrix [X] is written into a first memory R1, the elements of which are digital data, e.g. B. luminance or chrominance signals of the individual pixels of an image or image detail.
  • the elements of a transformation matrix [A] are already stored in a second memory R2.
  • the multiplying and adding devices M1 and M2 present in the exemplary embodiment shown two line vectors of the transformation matrix are multiplied in parallel with all line vectors of the data matrix [X].
  • the multiplier and adder M1 multiplies the transformation row vectors with an even row index and the other multiplier and adder M2 multiplies the transformation row vectors with an odd row index with the data row vectors.
  • the multiplier and adder M2 multiplies the transformation row vectors with an odd row index with the data row vectors.
  • more than two Multiplier and adder devices can of course be multiplied in accordance with more row vectors of the transformation matrix [A] in parallel with the row vectors of the data matrix [X], which further accelerates the matrix multiplication.
  • each multiplier and adder M1, M2 is assigned such a memory element of the memory R2, wherein as many rows or column vectors of the transformation matrix are written into each of the memory elements as the respectively associated one Multiplier and adder M1, M2 required for the matrix multiplication.
  • the wide paths indicate lines for the matrix signals
  • the narrow paths are lines for the control signals originating from a control ST and determining the process sequence in the circuit units.
  • the internal bit word length of the multiplying and adding devices M1, M2 is longer than the internal bit word length of the memories R1, R2, R3 in order to enable vector multiplications without rounding errors.
  • the bit word length of the matrix elements in the memories R1, R2, R3 is 12 bits, and the results from the vector multiplications in the multipliers and adders have a word length of e.g. 27 bits on.
  • the vector multiplication results are reduced in a circuit part BS downstream of the multiplier-adders M1, M2 from the long bit word length (27 bits) to the shorter bit word length (12 bits) for which the memories are designed.
  • the circuit part BS is designed in such a way that it can be adapted separately for each matrix multiplication by means of externally applied static signals to the respective dynamic range that is dependent on the transformation matrix. As a result, the inevitable calculation error of the circuit can be largely reduced.
  • the third memory R3 can only record one vector multiplication result at a time, then either the circuit part BS would have to temporarily store other results that had arisen at the same time and pass them on to the third memory R3 one after the other, offset by one clock. Or if one wants to dispense with intermediate storage, the vector multiplications in the individual multiplying and adding devices would have to be started offset by one cycle, so that the multiplication results are also available with a clock offset for transfer to the third memory R3.
  • the existing memories R1, R2, R3 and the multiplying and adding devices M1, M2 can also be used to perform an inverse transformation, ie coefficients from the spectral range are transformed back into data in the original range.
  • the coefficient matrix is written into the first memory R1 and then an inverse transformation matrix present in the second memory R2 is multiplied with the aid of the multiplying and adding devices by the coefficient matrix from the first memory R1 transposed by R1.
  • the inverse transformation matrix in the second memory R2 can be obtained in a simple manner by transposing the transformation matrix itself if it is orthonormal as here. Because the inverse of an orthonormal matrix is equal to the transpose of this matrix.
  • the transposed transformation matrix is obtained only by exchanging the row vectors with the column vectors of the transformation matrix present in the second memory R2, the elements only have to be changed accordingly second memory R2 can be accessed. Then the matrix resulting from the previous matrix multiplication is written into the third memory R3 and then the inverse transformation matrix from the second memory is multiplied with the transposed matrix from the third memory R3 with the aid of the existing multiplying and adding devices, which results in a matrix, the elements of which the data is in the original area.
  • circuit arrangement which can carry out both a transformation from the original region into the spectral region and the inverse transformation to it according to the method described, can be checked in the following way: First, data from the original area are subjected to a spectral transformation and then the spectral coefficients resulting from this transformation are transformed back again, and if the data resulting from the reverse transformation matches the original data, it can be concluded that the circuit arrangement is functioning correctly. A deviation of the data resulting from the reverse transformation from the original data indicates faulty operation.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Theoretical Computer Science (AREA)
  • Discrete Mathematics (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Image Processing (AREA)
  • Processing Of Color Television Signals (AREA)

Claims (5)

  1. Procédé de transformation spectrale bidimensionnelle d'un ensemble de données, dans lequel les données à transformer provenant du domaine original sont inscrites dans une première mémoire (R1) et, par deux multiplications matricielles entre la matrice de données reçue dans la première mémoire (R1) et une matrice de transformation, les données individuelles du domaine original sont transformées en coefficients du domaine spectral, la matrice provenant de la première multiplication matricielle étant déposée dans une mémoire propre (R3) et les deux multiplications matricielles étant exécutées avec le même dispositif de calcul, caractérisé par le fait que la matrice de transformation présente dans une deuxième mémoire (R2) est multipliée par la matrice de données transposée venant de la première mémoire (R1), par le fait que la matrice de transformation est alors multipliée par la matrice transposée qui est tirée de la première multiplication matricielle et est déposée dans la troisième mémoire (R3), et par le fait que la matrice de coefficients spectraux tirée de cette deuxième multiplication matricielle est inscrite dans la première mémoire (R1).
  2. Procédé selon revendication 1, caractérisé par le fait que la multiplication de deux matrices est exécutée de manière que, de tous les vecteurs lignes de la première matrice, à chaque fois au moins deux vecteurs lignes sont multipliés en parallèle, dans des dispositifs multiplicateurs et additionneurs (M1, M2), par les vecteurs colonnes de la deuxième matrice.
  3. Procédé selon revendication 1 ou 2, caractérisé par son emploi pour la transformation inverse de coefficients du domaine spectral en données dans le domaine original, les coefficients spectraux à rétrotransformer étant inscrits en tant qu'éléments d'une matrice dans la première mémoire (R1), par le fait qu'une matrice de transformation inverse présente dans la deuxième mémoire (R2) est multipliée, à l'aide des dispositifs multiplicateurs et additionneurs (M1, M2), par la matrice transposée de coefficients reçue dans la première mémoire, par le fait que la matrice résultant de la multiplication matricielle précédente est alors inscrite dans la troisième mémoire (R3) et par le fait que la matrice de transformation inverse tirée de la deuxième mémoire (R2) est ensuite multipliée, à l'aide des dispositifs multiplicateurs et additionneurs présents (M1, M2), par la matrice transposée tirée de la troisième mémoire (R3), ce dont il résulte une matrice dont les éléments sont les données dans le domaine original.
  4. Procédé selon les revendications 1 et 3, caractérisé par le fait que des données du domaine original sont d'abord soumises à une transformation spectrale puis les coefficients spectraux tirés de cette transformation sont rétrotransformés, la conformité entre les données tirées de la rétrotransformation et les données initiales permettant de conclure à un fonctionnement sans défaut d'un dispositif exécutant la transformation et la rétrotransformation, alors qu'en cas d'écart entre les données résultant de la rétrotransformation et les données initiales, on peut conclure à un fonctionnement défectueux du dispositif.
  5. Procédé selon revendication 1, caractérisé par le fait que la deuxième mémoire (R2) est partagée en plusieurs éléments de mémoire de manière qu'un tel élément de mémoire soit conjugué à chaque dispositif multiplicateur et additionneur (M1, M2), des vecteurs lignes et, selon le cas, des vecteurs colonnes de la matrice de transformation étant inscrits dans chacun des éléments de mémoire, en nombre aussi grand qu'il le faut à chaque fois par le dispositif multiplicateur et additionneur respectif (M1, M2) pour la multiplication matricielle.
EP19870106348 1987-05-02 1987-05-02 Méthode de transformation spectrale bidimensionnelle Expired - Lifetime EP0289629B1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
DE8787106348T DE3773192D1 (de) 1987-05-02 1987-05-02 Verfahren zur zweidimensionalen spektraltransformation.
EP19870106348 EP0289629B1 (fr) 1987-05-02 1987-05-02 Méthode de transformation spectrale bidimensionnelle

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
EP19870106348 EP0289629B1 (fr) 1987-05-02 1987-05-02 Méthode de transformation spectrale bidimensionnelle

Publications (2)

Publication Number Publication Date
EP0289629A1 EP0289629A1 (fr) 1988-11-09
EP0289629B1 true EP0289629B1 (fr) 1991-09-18

Family

ID=8196952

Family Applications (1)

Application Number Title Priority Date Filing Date
EP19870106348 Expired - Lifetime EP0289629B1 (fr) 1987-05-02 1987-05-02 Méthode de transformation spectrale bidimensionnelle

Country Status (2)

Country Link
EP (1) EP0289629B1 (fr)
DE (1) DE3773192D1 (fr)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3837328A1 (de) * 1988-11-03 1990-05-10 Bosch Gmbh Robert Transformationsschaltung
IT1235263B (it) * 1989-06-02 1992-06-26 Sgs Thomson Microelectronics Metodo e dispositivo per il calcolo aritmetico di trasformate bidimensionali.
US5053985A (en) * 1989-10-19 1991-10-01 Zoran Corporation Recycling dct/idct integrated circuit apparatus using a single multiplier/accumulator and a single random access memory

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4210931A (en) * 1978-12-28 1980-07-01 Discovision Associates Video player and/or recorder with Hadamard transform
GB2141847B (en) * 1983-05-06 1986-10-15 Seiko Instr & Electronics Matrix multiplication apparatus for graphic display

Also Published As

Publication number Publication date
DE3773192D1 (de) 1991-10-24
EP0289629A1 (fr) 1988-11-09

Similar Documents

Publication Publication Date Title
DE3132225C2 (de) Einrichtung für die Adressierung gespeicherter Ergebniswerte bei einer schnellen Hadamard-Transformation
DE3872424T2 (de) Fernsehuebertragungssystem mit verwendung von transformationskodierung.
DE19835216B4 (de) Prozessor und Verfahren zur parallelen Datenverarbeitung
DE3804938C2 (de) Bildverarbeitungseinrichtung
DE3789116T2 (de) Prozessor zur zweidimensionalen diskreten cosinustransformation.
DE3879637T2 (de) Pufferspeichergeraet und -verfahren, insbesondere fuer die matrixtransposition von datenfolgen.
DE3788747T2 (de) Halbleiterspeicher.
DE3855437T2 (de) Abtastfrequenzumsetzer zum Umsetzen einer niedrigen Abtastfrequenz in eine höhere Abtastfrequenz und Verfahren dafür
DE3632639C2 (de) Einrichtung zum Hochgeschwindigkeitsverarbeiten von Bilddaten durch Faltung
DE69737699T2 (de) Gerät und verfahren zur fft-berechnung
DE69329962T2 (de) System und Verfahren für die diskrete Cosinus-Transformation und für die inverse diskrete Cosinus-Transformation mit einfacher Struktur und mit hoher Betriebsgeschwindigkeit
DE3209073A1 (de) Anordnung zum umsetzen der zahl von abtastlinien
DE2729912C2 (de) Anordnung zum Erzeugen digitaler Ausgangssignalwerte
DE69031317T2 (de) Bearbeitung von einem zweidimensionalen Teilchen eines digitalen Bildsignals
EP0016318B1 (fr) Circuit de correction pour améliorer la netteté des contours des images de télévision
DE2821110C2 (de) Datenspeichereinrichtung
DE2655508A1 (de) Analogfiltersysteme
EP0289629B1 (fr) Méthode de transformation spectrale bidimensionnelle
DE69830971T2 (de) Pipelineprozessor für die schnelle Fourier-Transformation
DE19934500C2 (de) Synchroner integrierter Speicher
DE2612665A1 (de) Konvolutionsfunktionsgenerator und dessen anwendung in digitalfiltern
DE69125800T2 (de) Vorrichtung zum Verarbeiten eines digitalen Videosignals
DE2728890A1 (de) Nicht-rekursives diskretes filter
DE60022282T2 (de) Vorrichtung zur Bewegungskompensation für digitale Videoformat-Abwärtskonvertierung
DE4101413A1 (de) Schaltung zur zeitkorrektur zeitlich unterschiedlicher digitaler signale

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): DE FR GB IT NL

17P Request for examination filed

Effective date: 19881123

17Q First examination report despatched

Effective date: 19900525

GRAA (expected) grant

Free format text: ORIGINAL CODE: 0009210

AK Designated contracting states

Kind code of ref document: B1

Designated state(s): DE FR GB IT NL

ITF It: translation for a ep patent filed
REF Corresponds to:

Ref document number: 3773192

Country of ref document: DE

Date of ref document: 19911024

ET Fr: translation filed
GBT Gb: translation of ep patent filed (gb section 77(6)(a)/1977)
PLBE No opposition filed within time limit

Free format text: ORIGINAL CODE: 0009261

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: NO OPPOSITION FILED WITHIN TIME LIMIT

26N No opposition filed
REG Reference to a national code

Ref country code: FR

Ref legal event code: D9

Free format text: CORRECTION

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: GB

Payment date: 19980417

Year of fee payment: 12

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: FR

Payment date: 19980527

Year of fee payment: 12

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: NL

Payment date: 19980531

Year of fee payment: 12

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: DE

Payment date: 19980724

Year of fee payment: 12

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 19990502

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: NL

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 19991201

GBPC Gb: european patent ceased through non-payment of renewal fee

Effective date: 19990502

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: FR

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20000131

NLV4 Nl: lapsed or anulled due to non-payment of the annual fee

Effective date: 19991201

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: DE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20000301

REG Reference to a national code

Ref country code: FR

Ref legal event code: ST

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IT

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES;WARNING: LAPSES OF ITALIAN PATENTS WITH EFFECTIVE DATE BEFORE 2007 MAY HAVE OCCURRED AT ANY TIME BEFORE 2007. THE CORRECT EFFECTIVE DATE MAY BE DIFFERENT FROM THE ONE RECORDED.

Effective date: 20050502