DE2625973B2

DE2625973B2 - Verfahren und Anordnung zur redundanzvermindernden Transformation von Bildern

Info

Publication number: DE2625973B2
Application number: DE2625973A
Authority: DE
Inventors: Dipl.-Phys. Dr. Peter 2000 Hamburg Lux
Original assignee: Philips Patentverwaltung GmbH
Current assignee: Philips Intellectual Property and Standards GmbH
Priority date: 1976-06-10
Filing date: 1976-06-10
Publication date: 1981-04-23
Also published as: US4134134A; JPS5316557A; GB1532752A; DE2625973C3; FR2354671B1; DE2625973A1; FR2354671A1

Description

Die Erfindung betrifft ein Verfahren zur Transformation eines bildpunktweise abgetasteten Bildes, bei dem die Helligkeitswert; der Bildpunkte bei der Abtastung in digitale Werte umgesetzt werden und nacheinander die Teilbilder des in gleich große Teilbilder mit 2^x 2^N Matrixpunkten unterteilten Bildes transformiert werden, sowie Anordnungen zur Durchführung dieses Verfahrens.

Derartige Verfahren sind beispielsweise aus »Proceedings of the IEEE«, VoL 60, Nr. 7 (Juli 1972), Seiten 809 bis 820 bekannt Darin werden verschiedene Möglichkeiten, insbesondere Fourier-Transformation und die Hadamard-Transformation beschrieben. Derartige Transformationen werden verwendet, um den größten Teil der normalerweise quasistatistisch über das Bild verteilten Bildenergie auf einen kleinen Teil der transformierten Bildmatrix zusammenzudrängen, wodurch im restlichen Teil der transformierten Bildmatrix einige Elemente wenig Information enthalten und die Gesamtzahl der Elemente mit weniger Codeelementen darstellbar ist Die Werte der transformierten Bildmatrix werden nach der Transformation üblicherweise noch in einem Quantisiersr umcodiert wobei Werte unterhalb einer bestimmten Größe ganz unterdrückt werden. Dadurch tritt dann eine erhebliche Verringerung der Redundanz und außerdem eine Irrelevanzreduktion ein, so daß ein derartig umgewandeltes Bild mit wesentlich geringerem Aufwand über eine Übertragungsstrecke übertragen oder in einem Speicher abgespeichert werden kann. Diese Verringerung des 3t Aufwands hängt also ab von der Art der verwendeten Transformation und dem Ausmaß der dadurch erreichten Redundanzverringerung, die bei einigen bekannten Verfahren bei verschiedenen Bildern sehr unterschiedlich sein kann und auch im Durchschnitt noch wesentlich vom Optimum entfernt ist.

Aufgabe der Erfindung ist es, ein Transformationsverfahren für quadratische Teilbilder mit 2^x2* Matrixpunkten anzugeben, das insbesondere bei Bildern mit großflächigen Schwachkontrasten wie Röntgenbildern eine gute Informationskompression erreicht und das außerdem technisch einfach und mit wenig Aufwand zu realisieren ist. Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß das Teilbild in 2 χ 2 Matrixpunkte umfassende Unterbilder unterteilt wird, daß für jedes Unterbild mit der Basis-Hadamard-Matrix [H₂] eine Ähnlichkeitstransformation ausgeführt wird und die so entstehenden 2x2-Untermatrizen abgespeichert werden, daß die linken oberen Elemente aller Untermatrizen entsprechend ihrer Anordnung im Bild eine erste so Zwischenmatrix bilden, daß auf die Zwischenmatrix die gleichen Verfahrensschritte wie auf das Teilbild angewendet werden, wobei die Anordnung der Elemente jeder weiteren Zwischenmatrix der Anordnung der Elemente in der vorhergehenden Zwischenmatrix entspricht, und dieser Ablauf so oft wiederholt wird, bis diese Verfahrensschritte auf eine 2 χ 2-Zwischenmatrix angewendet worden sind, daß durch die zeilenweise Folge der Elemente der Zwischenmatrizen in umgekehrter Reihenfolge ihrer Entstehung, soweit nicht noch eo weiterverarbeitet, und daran anschließend durch die Folge aller rechten oberen Elemente, danach aller linken unteren und schließlich aller rechten unteren Elemente der Untermatrizen in umgekehrter Reihenfolge ihrer Entstehung die zeilenweise Folge der Elemente der transformierten Matrix des Teilbildes dargestellt wird. Die Angabe der Unterteilung des Teilbildes bzw. der Zwischenmatrizen gibt dabei die Reihenfolge an, in der die einzelnen Matrixpunkte verarbeitet werden. Da die Basis-Hadamard-Matrix H₂ lediglich die Elemente +1 und -1 besitzt reduziert sich die Ähnlichkeitstransformation praktisch auf eine bzw. mehrere kurze Ketten von Additionen bzw. Subtraktionen.

Eine Ausbildung des erfindungsgemäßen Verfahrens, ist dadurch gekennzeichnet, daß die Unterbilder des Teilbildes bzw. der Zwischenmatrizen nacheinander verarbeitet werden. Dadurch verlängert sich zwar die Verarbeitungszeit gegenüber einer Parallelverarbeitung, jedoch ist für die Gesamtzahl der Schritte zu berücksichtigen, daß jede folgende Zwischenmatrix um den Faktor 4 kleiner ist als die vorhergehende Zwischenmatrix bzw. das Teilbild. Dadurch ergibt sich auch bei einem rein seriellen Ablauf eine Anzahl von Verfahrensschritten, die kürzer als die doppelte Anzahl der Elemente des Teilbildes ist

Um bei der Übertragung oder Speicherung von transformiertkodierten Bildern die Auswirkungen einer Störung, d. h. einer Verfälschung eines Wertes, möglichst gering zu halten, werden die aus dem Quantisierer. der an die Transformationseinrichtung angeschlossen ist kommenden Kodewörter mit einem oder mehrere Prüfzeichen versehen. Nach einer weiteren Ausgestaltung der Erfindung bildet der Prüfzeichengenerator das Prüfzeichen nur aus den ersten vier oder den ersten sechzehn Elementen. Bei einer Absicherung der ersten vier Elemente wirkt sich eine Störung nur auf ein Gebiet von 4x4 Bildpunkten aus, während eine Absicherung der ersten sechzehn Elemente die Auswirkung einer Störung auf ein Gebiet von 2x2 Punkten beschränkt

Das erfindungsgemäße Verfahren zur Erzeugung eines transformierter Bildes [F(w)] läßt sich mathematisch darstellen als die Multiplikation eines Zeilenvektors [f(z)\ der die Zeilen des Teilbildes hintereinander angeordnet enthält, mit einer Matrix [S] von neuartigen sogenannten 5-Funktionen.

[F(W)] = [f(z)} ■ [S]

Diese S-Funktionen lassen sich auf folgende Weise über dem Intervall 0. definieren

5(0,0) ··= 1

5(1,0) = Φ,,(θ)· /i"

S(2.0) = Φ_υ(2² Θ) ■ /,',"

5(3,0) = Φ_η(2^: ■ Θ) ■ Φ₀(Θ) · /,',"

rf (θ)+V₂ : rf

Von den 5-Funktionen sind also die ersten vier speziell für sich definiert, während von der fünften Funktion an eine allgemeine Definition besteht. Darin ist Oo die Rademacherfunktion O-ter Ordnung.

+ 1 für O<0<—

-I für —<

Φ₀{Θ + π) = Φ,,(0) für 11 =- 0, ±1, ±2.

durch

(Θ) ist das System der Blockimpulse, definiert

1 für 0<Θ<—

0 für

Τ~^Θ<]

= ή,

(θ - j~

1,2,.

= 0, ±1,±2,

f sei gegeben durch

i/=2 ■ 2
Die Funktion /ΛΤΪ.ν) sei definiert durch

/ΛΤ / ΛΖΛ. \ 2

= y.

ew₀ rar

- 1 <>'<ΛΓ

/Mi ist die Menge der natürlichen Zahlen einschließlich 0, IR die Menge der reellen Zahlen.
K erhält man aus der Ordnungsnummer /der Funktion S(i, Θ) und der Stellenzahl der dazugehörigen Dualzahl durch

(i\ltz ~ Uk\ 'kl ·■■ '(l)rM

und q durch

/ΛΤ

T + log, ^-

log: -T

I Og₂

T — i — · /V7'(

¹ < - ί

tür — < / < U- 1

U-I)' sonst

ΙΙΛ fiir i/</<—(7-

-1⁷, sonst

Die S-Funktionen werden also durch die Rademacherfunktion entsprechender Ordnung gebildet von der durch die r-Terme einzelne Bereiche ausgeblendet, d. h. zu 0 gemacht werden, und die nicht ausgeblendeten Bereiche durch die V-Terme teilweise invertiert werden. In F i g. 1 sind die ersten 16 S-Funktionen ohne Maßstab dargestellt, und in F i g. 2 ist die zugehörige S^atrix angegeben.

Die Transformation eines Teilbildes mit dieser 5-Matrix läßt sich jedoch technisch nur sehr aufwendig durchführen. Für die technische Realisierung wird daher diese Transformation in eine Reihe von Transformationen mit Basis-Hadamard-Matrizen (H2) zerlegt Um dies mathematisch zu erläutern, sei zunächst im folgenden eine Verknüpfung definiert

Gegeben sei eine symmetrische 2^N x 2^-MaIrJx [/·] sowie eine 2"'x 2*'-Matrix [/4] mit M < NEIN (Menge der natürlichen Zahlen).

Die Verknüpfung |Λ] · CD ■ |/] bedeutet, daß nach Partilionierung der Matrix [F] in 2''x2⁷'symmetrische Untermatrizen der Dimension 2^λ/'χ 2^s'¹' auf jede Untermalrix If)J,/ A= 1, 2, 3, ... 2^dCr OperatorA als Matrixmulliplikator jeweils auf die Elemente /^J, ^k„ wirkt, wenn / = 1 + w - 2^X'^P'\ n= 1 + / · 2^N-^ρ'¹ mit Μ·,ί = Ο, 1, ... 2-^w-l ist.

f'i^k„ sind die Matrixelemente der Matrix [/^J.

Damit läßt sich die S-Transformation angeben als

[F (u. V)] =

^[F(x-^y)]

Aus dieser mathematischen Darstellung der Transformation läßt sich erkennen, wie das erfindungsgemäße Verfahren im Ergebnis wirkt.

Die Rücktransformation lautet

[F(x.y)] =

\FUi.v)}

Dies bedeutet, daß die Rücktransformation des transformierten Bildes, d. h. die Rekonstruktion des ursprünglichen Bildes, mit dem gleichen Verfahren erfolgen kann, wie die Transformation selbst d. h. die gleiche Schaltungsanordnung kann sowohl für die Transformation wie auch für die Rücktransformation verwendet werden. Bedingung ist dabei lediglich, daß die Elemente der transformierten Bildmatrix in der Reihenfolge, wie sie bei der Transformation entstanden sind, dem erfindungsgemäßen Verfahren zur Rücktransformation zugeführt werden.

Die zuletzt angegebene Darstellung der 5-Transformation bedeutet anschaulich eine subzcssivc Dckorrelation der Gleichpegelanteile nach fortschreitend größer werdenden Unterbildern hin, d. h. das Verfahren liefert gute Dekorrelation großflächiger Schwachkontraste und ist damit für Kodierung von Bildern wie Aufnahmen von der Mondoberfläche, Röntgenaufnahmen und ähnlichem Bildmaterial besonders geeignet

Bei der technischen Realisierung des erfindungsgemäßen Verfahrens ist zu beachten, daß die Elemente eines Teilbildes entweder in der Folge zugeführt oder so abgespeichert werden, daß nacheinander die Matrixpunkte jeweils eines Unterbildes parallel einer Verknüpfungsschaltung zugeführt werden, die die Transformation mit der Basis-Hadamard-Matrix durchführt

Eine Anordnung zur Durchführung einer Echtzeit-Walsh-Hadamard-Transformation ist aus IEEE-Transactions on Computer, VoL C-21, Nr. 3, März 1972, Seiten 280 bis 291 bekannt Diese Anordnung realisiert jedoch ein anderes Verfahren, nämlich eine Multiplikation mit einer Hadamard-Matrix entsprechend hoher Ordnung, und benötigt daher eine sehr große Anzahl von Multiplizierern, Summierern und ähnlichen Schaltungen sowie einen Speicher für die Koeffizienten der Hadamard-Matrix. Ein derartiger Aufwand ist für die Praxis jedoch allgemein zu hoch.

Im folgenden werden daher Ausführungsbeispiele

von Anordnungen zur Durchführung des erfindungsgemäßen Verfahrens anhand der Zeichnung erläutert. Es zeigt

F i g. 3 den Aufbau einer vollständigen Anordnung aus einer Kette von Teilanordnungen mit deren Aufbau,

Fig.4 die Anordnung der Bildelemente in dem Teilbild und deren Speicherung in den Schieberegistern,

Fig. 5 den Aufbau und die Steuerung eines Zuordners,

F i g. 6 den Aufbau der Verknüpfungsschaltungen.

In der F i g. 3 besteht die Anordnung zur Bildtransformation aus einer Kette von Teilanordnungen, von denen nur die erste Teilanordnung 20 und die letzte Teilanordnung 21 dargestellt sind. Zwischen dem Ausgang 16 der ersten Teilanordnung 20 und dem Eingang 17 der letzten Teilanordnung 21 können noch weitere, der Teiianordnung 20 gleiche bzw. im wesentlichen gleiche Teilanordnungen eingeschaltet werden, je nach Größe des zu verarbeitenden Teilbildes. Der eventuelle Unterschied wird später erläutert.

Im vorliegenden Beispiel wird nun angenommen, daß das zu verarbeitende Teilbild 2³ χ 2³ = 8x8 Bildpunkte besitzt, d. h. 8 Zeilen mit je 8 Punkten. Die digitalisierten Helligkeitswerte dieser 64 Bildpunkte werden dem Eingang 15 der ersten Teilanordnung 20 zeilenweise nacheinander zugeführt. Diese Werte werden durch den Zuordner so auf die 4 Schieberegister 2 bis 5 verteilt, daß die Werte der ersten Teilbildzeile abwechselnd in die ersten beiden Schieberegister 2 bzw. 3 eingeschrieben werden, die Werte der zweiten Teilbildzeile abwechselnd in das dritte bzw. vierte Schieberegister 4, S usw.

Die Verteilung der Information in den Schieberegisters ist in Fip. 4 noch einmal deutlicher dargestellt Fig.4a zeigt den Aufbau eines Teilbildes aus 8x8 Bildpunkten, die von 1 bis 64 durchnumeriert sind. Die Anordnung der Werte dieser Bildpunkte in dem ersten bis vierten Schieberegister, die hier allgemein mit SR 1 bis SR4 bezeichnet sind, ist in Fig.4b dargestellt. Da die Information eines Teilbildes also auf 4 Schieberegister gleichmäßig verteilt wird, muß jedes Schieberegister mindestens eine Kapazität von 2^Λ/χ2^Λ/-² besitzen, wenn das zu verarbeitende Teilbild 2"X 2* Bildpunkte besitzt, d. h. im vorliegenden Beispiel muß bei 64 Bildpunkten jedes Schieberegister 16 Werte speichern können. Jeder dieser dualcodierten Werte umfaßt jedoch mehrere Bits, jede Stufe der Schieberegister muß daher entsprechend Speicherzellen besitzen, die zweckmäßig parallel betrieben werden, d.h. mit jedem Schiebetakt übertragen alle Speicherzellen einer Stufe ihren Inhalt in die entsprechenden Speicherzellen der nächsten Stufe.

Der Zuordner enthält zum Verteilen der Information in der vorstehend beschriebenen Weise zweckmäßig mehrere Umschalter, die zweckmäßig elektronisch realisiert sind. Lediglich zum Zwecke der einfacheren Darstellung sind bei dem in Fig.5 dargestellten Zuordner diese Umschalter 52, 53, 54 als mechanische Umschalter gezeichnet Wenn über diese Umschalter die Information selbst verteilt werden soll, muß jeder Umschalter entsprechend der Stellenzahl der einzuschreibenden Werte mehrfach vorhanden sein. Außerdem muß über den Zuordner dafür gesorgt werden, daß nur dasjenige Schieberegister ein Taktsignal am Eingang CL erhält, das auch einen Wert einschreibt, wozu der Zuordner auch einen Takteingang C besitzt Der Zuordner für den Takt ist daher ebenso wie in Fi g. 5 dargestellt aufgebaut Viele bekannte Schieberegister, insbesondere solche aus integrierten Schaltungsbausteinen wie dem Typ SN 74 96 übernehmen jedoch eine am Eingang anliegende Information nur dann, wenn ein Taktsignal auftritt, während im übrigen die ί Information beliebig wechseln kann. Bei solchen Schieberegistern braucht dann nur das Taktsignal entsprechend verteilt zu werden, während die Information an allen vier Schieberegistern SR 1 bis SR 4 parallel anliegt. Für die weitere Erläuterung wird daher

κι angenommen, daß der in Fi g. 5 dargestellte Zuordner nur die Schiebetaktsignale verteilt.

Die Umschalter 52 bis 54 werden von einem Zähler 51 gesteuert, wobei die Umschalter 53 und 54 der Einfachheit halber parallel gesteuert werden. Die dargestellte Ruhelage der Umschalter wird in der Anfangsstellung des Zählers 51 eingenommen, die durch einen nicht dargestellten Rückstelleingang eingestellt werden kann. Das erste Schiebetaktsignal am Eingang 55 des Zuordners wird dann über die Umschalter 52 und 53 dem Ausgang 56 zugeleitet, der an den Takteingang CL des ersten Schieberegisters FR1 angeschlossen ist. Mit der Rückflanke dieses ersten Taktsignals wird der Zähler 51 um eine Stellung weitergeschaltet, wodurch die erste Zählerstufe 7"(1) die Umschalter 53 und 54 umschaltet. Das zweite Schiebetaktsignal wird somit vom Ausgang 57 dem Takteingang des Schieberegisters SR 2 zugeführt Mit der Rückflanke dieses Taktsignals wird der Zähler 51 wieder eine Stellung weitergeschaltet, wodurch die Umschalter 53 und 54 die gezeichnete Stellung wieder einnehmen, usw.

Nach 2^A'-Schiebetakten ist dann eine ganze Zeile des 2* χ 2* Bildpunkte umfassenden Teilbildes gespeichert worden, und mit der Rückflanke dieses letzten Schiebetaktes schaltet die Stufe T (N+1) um. Damit wird der Umschalter 52 umgeschaltet, und die folgenden Schiebetaktsignale werden über die Ausgänge 58 und 59 entsprechend der vorher beschriebenen Weise abwechselnd den Schieberegistern SR 3 und SR 4 zugeführt, um darin die nächste Zeile des Teilbildes zu speichern.

Wenn diese zweite Zeile eingespeichert ist, schaltet die Stufe T(N+ 1) wieder um, und die dritte Zeile wird in den Schieberegistern SR 1 und SÄ 2 eingespeichert. Auf diese Weise werden also die Werte der Bildpunkte in der in Fig.4b angegebenen Folge in den vier Schieberegistern SÄ 1 bis SÄ 4 gespeichert

Wenn die Kapazität der Schieberegister gerade der aufzunehmenden Information entspricht sind mit dem Einspeichern des Wertes des letzten Bildpunktes die Werte der Bildpunkte der linken oberen Untermatrix

5» der Größe 2x2 Punkte gerade am Ende des Schieberegisters angelangt so daß diese Werte an den Eingängen der Verknüpfungsschaltung 6 liegen. Diese Verknüpfungsschaltung soll an ihren Ausgängen Signale liefern, die die Ähnlichkeitstransformation einer durch die Eingangssignale dargestellten Untermatrix mit der Basis-Hadamard-Matrix [f/₂] darstellen. Eine solche Verknüpfungsschaltung kann entsprechend der Fig.6 aufgebaut sein. Diese Verknüpfungsschaltung liefert an ihren Ausgängen Bi bis BA Ausgangswerte, die auf folgende Weise von den Eingangswerten an den Eingängen A 1 bis A 4 abgeleitet sind, wobei diese Werte der Einfachheit halber mit den Eingängen bzw. Ausgängen bezeichnet sind:

Bi = A1+A2+A3 + A4

B2 = At-A2+A3-A4 B3 = A\+A2-A3-A4 B4 = At-A2-A3 + A4

Diese Verknüpfungen werden in Fig. 6a mit Hilfe einer Anzahl von Addierern bzw. Subtrahierern 61 bis 72 durchgeführt, von denen jeder 2 Eingangswerte verknüpft, so daß zwei Ebenen von Addierern notwendig 'ind. Der Addierer 61 bildet beispielsweise die Summe A 1+Λ2, der Addierer 62 die Summe A 3 + Λ4, und der Addierer 63 bildet dann die Summe aus diesen beiden Werten entsprechend der Gleichung für den Ausgangswert Bi. Entsprechend bildet beispielsweise der Addierer 70 die Summe A 1 + A 4 und der Addierer 71 die Summe A 2 + A3, während der Addierer 72 die zweite Summe von der ersten subtrahiert, wie durch das Minuszeichen an dem linken Eingang angedeutet ist, so daß der Ausgangswert B 4 wieder der angegebenen Gleichung entspricht. In entsprechender Weise werden die Werte BI und B3 entsprechend den angegebenen Gleichungen gebildet, wie sich aus der dargestellten Schaltung leicht ablesen läßt.

Eine andere Realisierung der Verknüpfungsschaltung ist in Fig,6b dargestellt, die nur 8 Addierer bzw. Subtrahierer 80 bis 87 benötigt, wobei die zu subtrahierenden Werte durch einen Kreis am Eingang der Addierer angedeutet sind. Diese Verknüpfungsschaltung liefert ebenfalls an ihren Ausgängen B1 bis B4 die in den Gleichungen angegebenen Werte, wie leicht zu erkennen ist, wenn in diesen Gleichungen jeweils zwei benachbarte Terme zusammengefaßt werden.

Der Vollständigkeit halber sei darauf hingewiesen, daß die Eingangs- und Ausgangswerte der Verknüpfungsschaltungen jeweils mehrstellige Dualwörter sind, so daß die Addierer bzw. Subtrahierer ebenfalls für mehrere Bit ausgelegt sein müssen, etwa indem sie aus einer Parallelschaltung mehrerer 1-Bit-Volladdierer mit Übertragungsverarbeitung aufgebaut sind, sofern nicht Bausteine verwendet werden, die zwei mehr-Bit- Wörter parallel addieren bzw. subtrahieren.

Die Ausgänge B 2— 54 der Verknüpfungsschaltung 6 sind, wie aus Fig.3 zu ersehen ist, mit dem Informationseingang der zugehörigen Schieberegister 3 bis 5 bzw. allgemein SR 2 — SR 4 verbunden, und zwar mit einem weiteren Informationseingang, sofern dieser bei den verwendeten Schieberegistern vorhanden ist, oder über ein nicht dargestelltes ODER-Glied mit dem einzigen Informationseingang. Die Umschaltung erfolgt dann dadurch, daß entweder die Ausgänge der Verknüpfungsschaltung 6 oder die Informationsausgänge des Zuordners 1 gesperrt werden. Der Ausgang B1 des Zuordners 6 ist dagegen mit dem Ausgang 16 der Teilanordnung verbunden, der auf den Eingang 17 der nächsten Teilanordnung führt.

Nachdem die durch die Verknüpfung in der Verknüpfungsschaltung 6 entstandenen Ausgangssignale an den Eingängen der Schieberegister 3—5 bzw. am Eingang 17 der nächsten Teilanordnung anliegen, erhalten alle vier Schieberegister 2—5 parallel ein Schiebetaktsignal, entweder Ober einen zusätzlichen Schiebetakteingang oder durch entsprechende Steuerung des Zuordners 1, so daß der in der letzten Stufe aller Schieberegister stehende Wert herausgeschoben und in den Schieberegistern 3—5 der entsprechende Ausgangswert der Verknüpfungsschaltung eingeschrieben wird, während die erste Stufe des Schieberegisters 2 leer bleibt Gleichzeitig wird der am Eingang 17 der nächsten Teilanordnung anstehende Wert durch deren Zuordner in gleicher Weise, wie für die erste Teflanordnung 20 und deren Zuordner 1 beschrieben, in das Schieberegister SR 1 dieser nächsten Teilanordnung eingeschrieben. Gleichzeitig stehen an den Ausgängen der Schieberegister 2-5 der ersten Teilanordnung 20 die nach dem Einschreiben in den vorletzten Stufen

^r> vorhanden gewesenen Werte entsprechend der zweiten 2 χ 2-Untermatrix des Teilbildes und erzeugen neue Ausgangswerte an den Ausgängen der Verknüpfungsschaltung 6, die durch das nächste gemeinsame Schiebetaktsignal in die Schieberegister 3-5 bzw. über

ίο den Zuordner der nächsten Teilanordnung in deren Schieberegister SR 2 eingeschrieben wird. Auf diese Weise werden alle Werte des Teilbildcs in den Schieberegistern 2 — 5 verarbeitet und durch die transformierten Werte ersetzt, wobei das Schieberegister 2 leer bleibt, da die Werte des entsprechenden Ausgangs der Verknüpfungsschaltung 6 auf die Schieberegister SR 1 — SR 4 der nächsten Teilanordnung verteilt worden sind. Da die Anzahl dieser Werte nur den Inhalt eines der Schieberegister der ersten Teilanordnung und somit einem Viertel der Anzahl der Werte eines Teilbildes entspricht, muß der Zuordner der folgenden Teilanordnung einen entsprechend kürzeren Zyklus haben, d. h. bereits nach Werten auf die Schieberegister SR 3 bzw. SR 4 umschalten, und ebenso brauchen die Schieberegister der folgenden Teilanordnung jeweils nur ein Viertel der Kapazität wie die Schieberegister der vorhergehenden Teilanordnung zu haben. In dem hier beschriebenen Beispiel zur Verarbeitung von Teilbildern mit 8x8 Bildpunkten, bei dem jedes Schieberegister der ersten Teilanordnung 16 Werte speichern muß, brauchen die Schieberegister der zweiten Teilanordnung nur je vier Werte zu speichern. Damit ist die zweite Teilanordnung gleichzeitig die letzte, so daß die F i g. 3 die vollständige Anordnung für

J5 die Verarbeitung von Teilbildnern mit 8x8 Bildpunkten darstellt. Bei der Verarbeitung eines Teilbildes mit doppelter Kantenlänge, d. h. mit der vierfachen Anzahl, also 256 Bildpunkten, müßten die Schieberegister der ersten Teilanordnung je 64 Werte speichern, und zwischen dieser und der letzten Teilanordnung müßte eine weitere Teilanordnung eingeschaltet werden, deren Schieberegister je 16 Werte speichern und diese in gleicher Weise verarbeiten und einen Teil der letzten Teilanordnung 21 zuführen, wie die erste Teilanordnung, nachdem diese die vollständige, oben beschriebene Verarbeitung abgeschlossen hat.

Nachdem also die vier Schieberegister 8-11 der letzten Teilanordnung 21 eingeschrieben worden sind, enthalten sie die einzelnen Werte in einer Verteilung,

so wie sie in F i g. 4c dargestellt ist, wobei die Ziffern sich auf die Ziffern im Schieberegister SÄ 1 in F i g. 4b und somit auf die entsprechenden Verarbeitungsschritte beziehen. Diese Werte werden nun in gleicher Weise wie bei den vorhergehenden Teilanordnungen verarbeitet, indem die Schieberegister die Werte der einzelnen Stufen nacheinander parallel der Verknüpfungsschaltung 12, in der die gleiche Verknüpfung wie in der Verknüpfungsschaltung 6 erfolgt und die in gleicher Weise aufgebaut sein kann, zuführen und die verknüpften Werte am Eingang wieder einschreiben. Anstatt am ersten Ausgang der Verknüpfungsschaltung nun ein weiteres Register für die anschließende Durchführung des letzten Verarbeitungsschrittes anzuschließen, wird dafür das erste Schieberegister 8 verwendet, das ja andernfalls leer bliebe, indem dessen weiterer Informationseingang mit dem entsprechenden Ausgang der Verknüpfungsschaltung 12 verbunden wird. Nach vier Schiebetakten, wenn der Inhalt der Schieberegister

ti

8 — 11 verarbeitet ist, erfolgt dann noch ein letzter Verarbeitungsschrit·. mit dem Inhalt des ersten Schieberegisters 8.

Dazu besitzt dieses parallele Ausgänge, die mit einer Verknüpfungsschaltung 13 verbunden sind, die ebenfalls die gleiche Verknüpfung wie die Verknjpfiingsschaltungen 6 bzw. 12 durchführt und in gleicher Weise aufgebaut sein kann. Durch diesen letzten Verarbeitungsschritt werden die Werte an den Ausgängen dieser Verknüpfungsschaltung 13 parallel in die vier Stufen des Schieberegisters 8 übernommen. Die Werte dieses Schieberegisters haben dann also in dem beschriebenen Beispiel drei Verarbeitungsschritte durchlaufen, die Werte der Schieberegister 9 bis 11 dagegen nur zwei Verarbeitungsschritte und die Werte der Schieberegister 3 bis 5 nur einen Verarbeitungsschritt. Damit ist die Transformation abgeschlossen.

Zum Auslesen der transformierten Werte sind die Serienausgänge der Schieberegister 8 — 11 der letzten Teilanordnung 21 sowie die Serienausgänge der zweiten bis vierten Schieberegister 3 — 5 bzw. im allgemeinen Fall die Ausgänge aller zweiten bis vierten Schieberegister SR2-SR4 aller vorhergehenden Teilanordnungen mit einem Wählschalter 14 verbunden. Dieser Wählschalter tastet zunächst den Serienausgang des Schieberegisters 8 der letzten Teilanordnung 21 ab und leitet dessen Inhalt nacheinander dem Ausgang 18 der Anordnung zu, indem dem Schieberegister 8 seiner Länge entsprechend viele, d. h. hier vier Schiebetaktimpulse zugeführt werden, z. B. vom Zuordner 7. Danach schaltet der Wählarm des Wählschalters 14 auf den Ausgang des Schieberegisters 9, das dann ebenfalls vier Schiebetaktimpulse erhält usw., bis schließlich das vierte Schieberegister 5 der ersten Teilanordnung abgetastet und sein Inhalt dem Ausgang 18 zugeführt ist. Die am Ausgang 18 erscheinenden Werte geben nacheinander zeilenweise die Werte der transformierten Bildmatrix an. Da die einzelnen Werte durch mehrstellige Dualzahlen dargestellt werden, bestehen die Verbindungen von den Schieberegistern zum Wählschalter tatsächlich aus entsprechend vielen einzelnen Leitungen, und der Wählschalter besitzt entsprechend viele parallele Wählarme, die gleichzeitig weitergeschaltei werden. An dieser Stelle sei darauf hingewiesen, daß durch die Art der Verknüpfung die maximal mögliche Stellenzahl der Werte von Teilschaltung zu Teilschaltung steigt, falls keine Beschränkung oder Normierung erfolgt, so daß die Schieberegister der letzten Teilschaltung pro Stufe entsprechend mehr Speicherzellen besitzen müssen. Der Wählschalter 14 muß dann für die maximale Stellenzahl der Werte ausgelegt sein. In der praktischen Realisierung kann er beispielsweise durch entsprechend viele Multiplexer gebildet werden. während beispielsweise der in Fig.5 dargestellte Zuordner durch einen Demultiplexer realisiert werden kann.

Zur Übertragung oder Speicherung eines derart transformierten Bildes werden die am Ausgang 18 nacheinander erscheinenden Werte einem Quantisierer 22 zugeführt, der diese Werte in bekannter Weise beispielsweise an einer Gauss'schen Kurve quantisiert und in entsprechende Codeworte umwandelt. Um zi: ν rmeiden, daß sich Störsignale bei der Übertragung bzw. Speicherung in dem rekonstruierten Bild zu stark auswirken und beispielsweire bei einem Röntgenbild zu einer Fehldiagnose führen, werden die Codewörter des

ι» Quantisierers einem Prüfzeichengenerator 23 zugeführt, der der Folge von Codewörtern, die ein Teilbild darstellen, ein Prüfzeichen aus einem oder mehreren Bit oder Codewörtern zufügt, je nachdem, ob ein oder mehrere gestörte Elemente oder Codewortfolge crkannt oder berichtigt werden sollen. Bei der beschriebenen Transformation führt nun eine Absicherung der erster! vier Codewörter, die von den aus dem Schieberegister 8 der letzten Teilanordnung 21 ausgelesenen Werten abgeleitet sind, dazu, daß eine Verfäl-

2» schung eines der restlichen Codewörter zu einem Bildfehler in höchstens einem viertel Teilbild führt, während eine Absicherung der ersten sechzehn Codewörter zu einem Bildfehler in höchstens einem Bildgebiet von einem sechzehntel des Teilbildes führen kann. Allgemein führt eine Fehlersicherung von 2(M-D. 2(M-D Koeffizienten (M= 1. 2 .. N) einer Beschränkung der Fehler auf Bereiche von 2V-Af. 2N-M Bildpunkten. Auf diese Weise ist bei der beschriebenen Transfermation mit einer nur geringen

in Redundanzerhöhung eine besonders wirksame Fehlersicherung möglich.

Zur Rekonstruktion des Teübildes werden die am Ausgang 19 der Transformationsanordnung nacheinander erschienenen Werte nach Speicherung bzw

Ji Übertragung einer Prüfanordnung zugeführt, die diese Folge von Codewortern ) ihand des Prüfzeichens auf Fehler prüft, danach einer Rückquantisieranordnung mit umgekehrter Kennlinie wie die Quantisieranordnung 22, und die Folge der davon gelieferten Werte w ird dem Eingang 15 einer Anordnung zugeführt, die in gleicher Weise wie die in F i g. 3 dargestellte *\no^rdnung aufgebaut ist und auch in genau gleicher Weise arbeitet. Nach vollständiger Verarbeitung der Wene des transformierten Teilbildes entstehen am Ausgang 18

*> dann zeilenweise die Werte des rücktransformierten. d. h. rekonstruierten Teilbildes.

Anstelle der vorher beschriebenen Schieberegister kann auch ein Speicher mit wahlfreiem Zugriff verwendet werden, der eine Speicherkapazität eines Teilbildes besitzt. Dabei muß die Adressensteuerung dann so aufgebau' sein, daß für die einzelnen Verfahrensstufen solche Folgen von Adressen auftreten. daß die Verarbeitung in der gleichen Reihenfolge erfolgt, wie bei der in F i g. 3 dargestellten Anordnung.

Dabei ist es dann möglich, mit nur einer Verknüpfungslogik, z. B. einem der F i g. 6 entsprechenden Aufbau. auszukommen.

Hierzu 6 Blatt Zeichnungen

Claims

Patentansprüche:

1. Verfahren zur Transformation eines bildpunktweise abgetasteten Bildes, bei dem die Helligkeitswerte der Bildpunkte bei der Abtastung in digitale Werte umgesetzt werden und nacheinander die Teilbilder des in gleich große Teilbilder mit 2* χ 2" Matrixpunkten unterteilten Bildes transformiert werden, dadurch gekennzeichnet, daß das Teilbild in 2 χ 2 Matrixpunkte umfassende Unterbilder unterteilt wird, daß für jedes Unterbild mit der Basis-Hadamard-Matrix [H₂] eine Ähnlichkeitstransformation ausgeführt wird und die so entstehenden 2 χ 2-Untermatrizen abgespeichert werden, daß die linken oberen Elemente aller Untermatrizen ι5 entsprechend ihrer Anordnung im Bild eine erste Zwischenmatrix bilden, daß auf die Zwischenmatrix die gleichen Verfahrensschritte wie auf dgs Teilbild angewendet werden, wobe^; die Anordnung der Elemente jeder weiteren Zwischenmatrix der Anordnung der Elemente in der vorhergehenden Zwischenmatrix entspricht, und dieser Ablauf so oft wiederholt wird, bis diese Verfahrensschritte auf eine 2 χ 2-Zwischenmatrix angewendet worden sind, daß durch die zeilenweise Folge der Elemente der Zwischenmatrizen in umgekehrter Reihenfolge ihrer Entstehung, soweit nicht noch weiterverarbeitet, und daran anschließend durch die Folge aller rechten oberen Elemente, danach aller linken unteren und schließlich aller rechten unteren Elemente der Untermatrizen in umgekehrter Reihenfolge ihrer Entstehung die zeilenweise Folge der Elemente der transformierten Matrix des Teilbildes dargestellt wird.

2. Verfahren nach Anspruch 1, dadurch gekenn- J5 zeichnet, daß die Unterbilder des Teilbildes bzw. der Zwischenmatrizen nacheinander verarbeitet werden.

3. Verfahren nach Anspruch 1, wobei die Elemente der transformierten Teilbildmatrizen nacheinander "o über einen Quantisierer und einen Prüfzeichengenerator einem Übertragungs- oder Speichermedium zugeführt werden, dadurch gekennzeichnet, daß der Prüfzeichengenerator das Prüfzeichen nur aus den ersten2^M-> χ 2^Μ~^-(Μ = 2,3.. ^lementenbildet.

4. Anordnung zur Durchführung des Verfahrens nach Anspruch 2, dadurch gekennzeichnet, daß in einer ersten Teilanordnung (20) ein Zuordner (1) die digitalisierten Werte der Bildpunkte des Teilbildes in vier Schieberegistern (2, 3, 4, 5) derart einschreibt, daß die Werte der ungeraden Zeilen des Teilbildes nacheinander abwechselnd in daF erste bzw. zweite Schieberegister (2, 3) und die Werte der geraden Zeilen nacheinander abwechselnd in das dritte bzw. vierte Schieberegister (4, 5) eingeschrieben werden, bis der Zuordner in einem Zyklus die Werte für das ganze Teilbild in den Schieberegistern gespeichert hat, daß nach dem Einschreiben der Schieberegister diese parallel so viele Schiebetakte erhalten, bis alle eingespeicherten Informationen einmal an ihren ω Serienausgängen (A 1 bis A 4) erscheinen, daß an diese Serienausgänge eine Verknüpfungsschaltung (6) angeschlossen ist, die an vier Ausgängen (B 1 bis B 4) aus den an den Serienausgängen gleichzeitig erscheinenden Signalen folgende Signale erzeugt: μ B3 = Ai+A2-A3-A4
Β4 = Λ1-Α2-Λ3+Λ4

wobei der zweite bis; vierte Ausgang (B 2 bis B 4) jeweils auf den Informatiouseingang des betreffenden Schieberegisters (3 bis 5) rückgekoppelt ist und der erste Ausgang (B 1) auf den Eingang (17) einer der ersten Teilanordnung entsprechend gleich aufgebauten weiteren Teilanordnung führt, deren Zuordner (7) einen entsprechend um den Faktor 4 kürzeren Zyklus hat «ils der Zuordner der vorhergehenden Teilanordnung, daß in dieser Weise so viele Teilanordnungen hintereinandergeschaltet sind, bis in der letzten Teilanordnung jedes Schieberegister (8, 9, 10,11) nur noch vier Werte speichert, daß in dieser Teilanordnung: auch der erste Ausgang (Bi) der Verknüpfungsschaltung (12) auf den Informationseingang des ersten Schieberegisters (8) rückgekoppelt ist und die Ausgänge von dessen ersten vier Stufen an eine den anderen Verknüpfungsschaltungen (6, 12) gleiche Verknüpfungsschaltung (13) angeschlossen ist, deren Ausgänge mit Paralleleingängen der ersten vier Stufen dieses Schieberegisters verbunden sind, wobei das Schieberegister nach dem Einschreiben der vier Werte die an diesen Paralleleingängen vorhandenenen Signale parallel einschreibt, und daß die Ausgänge des ersten bis vierten Schieberegisters (8, 9, 10, 11) der letzten Teil&iiordnung und die Ausgänge des ersten bis vierten Schieberegisters (3, 4, 5) aller vorhergehenden Teilanordnungen an eine Wählanordnung (14) angeschlossen sind, die diese Ausgänge in folgender Reihenfolge abtastet:

Das erste, das zweite, das dritte, das vierte Schieberegister der letzten Teilanordnung
das zweite, das dritte, das vierte Schieberegister der vorletzten Teilanordnung usw. bis zur ersten Teilanordnung, und den aus der zugehörigen Verknüpfungsschaltung eingeschriebenen Inhalt des betreffenden Schieberegisters einem Ausgang (18) der Anordnung zuführt, der die Werte der transformierten Bildmatrix zeilenweise nacheinander liefert.

5. Anordnung nach Anspruch 4, dadurch gekennzeichnet, daß zum Einschreiben der Schieberegister (2,3,4,5; 8,9,10,11) einer Teilanordnung (20,21) die einzuschreibende Information an den Serieneingängen aller vier Schieberegister liegt und nur das Schieberegister einen Schiebetakt erhält, in das die jeweilige Information eingeschrieben werden soll.

6. Anordnung nach Anspruch 4 oder 5, dadurch gekennzeichnet, daß jede Stufe aller Schieberegister (2, 3, 4, 5; 8, 9, 10, 11) mindestens so viele parallel betriebene Speicherzellen enthält wie der einzuschreibende Wert Bits enthält.

7. Anordnung nach einem der Ansprüche 4 bis 6, dadurch gekennzeichnet, daß die Länge der Schieberegister (2, 3, 4, 5; 8, 9, 10, 11) in den einzelnen Teilanordnungen (20,21) der Anzahl der in diese Schieberegister einzuschreibenden Werte entspricht.

8. Anordnung nach Anspruch 4, dadurch gekennzeichnet, daß alle Schieberegister durch einen Speicher mit wahlfreiem Zugriff ersetzt sind und nur eine Verknüpfungsschaltung vorhanden ist.

öl = A ί+Α2+Α3+Α4 Bl = A\-A2+A3-A4