Note: Descriptions are shown in the official language in which they were submitted.
lO~9i~0
BACKGROUND OF THE INVENTION
The present invention relates to a system for coding and
decoding images using a matrix transform, the said system allowing
a compression of the image signals.
PRIOR ART
It is known to make a transform F~u,v) correspond to a
bi-dimentional image function f(x,y) having N2 points, the ;~
transform F(u,v) being defined by the matrix product:
~(u,v~ = ~H(u,v~ ~(x,y~ LH(U,V)7 T (I)
an equation in which H is a transform matrix of order N x N, ~nd
LHJT is the corresponding transposed matrix. This matrix can,
for example, be a Hadamard or a Haar matrix. In the case ~ is a
....: .
Hadamard matrix, the following references may be referred to: (i)
"Ultilisation de la transformée de Hadamard pour le codage et la
compression des signaux d'images" by Jacques Poncin, "Annales des
~; Télécommunications" Volume 26, No. 7-8, 1971; (ii) "Hadamard
~ 1 . . . ~
Transform Image Coding" by William K. PRATT, Julius KANE and
Harry C. ANDREWS, Proceedings of the IEEE, Vol. 57, No. 1 January --
., . . , ~.,~- . ~., .
1969; (iii) "Intraframe Image Coding by Cascaded Hadamard Trans~
~orms" by Takahiko FUNINIKI and Masachika MIYATA, IEEE Transâc- ~ -
tions on Communicatlons, Vol. Com. 21, No. 3, March 1973. In
the case where ~H~ is a Haar matrix, the following reference can
~, .~ .. .
~ be referred to:"A Generalized Technique for Spectral Analysis" ~ ~
.
~;~ by Harry C. ANDREWS and Kenneth L. CASPARI, IEEE Transactions
j on Computers, Vol. C-l9, No. 1, January 1970, pages 16-25. ~-~
If the matrix ~ is orthogonal and orthonormal, the ~-
product ~ T XfH¦is equal to N times the unit matrix. It is the
same for the Hadamard and Haar matrices and, in this case, the
inverse transform: :
~ 30 ~f (X y~ 7 = 1 ~(U v~ T . ~F(u,v~ . LH (U V~ (2) ~ ~
- j N
,,, '~~ I ' ~ ~
. ~ ;
~ ' .
lQ~91(i`0
uses the same transform matrix rH~ as the direct transform.
Since the Hadamard matrices are square matrices of order
N x N = 2n x 2n, it is possible to treat by trans~ormation, either
the complete image, or successively small component s~b-images.
In fact, in order to restrict the circuitry in the case of high
definition images and, notably, the capacity of the random access
memory containing the image samples and the read only memory
containing the coefficients of the Hadamard matrix, the transfor-
mation is generally applied to partial images having N2 points,
the total number of image points being N 2,
Thus, these transformations make a transform of N2 coef-
ficients correspond to a partial image of NxN points, the said
coefficients only taking into account the N2 points o origin.
In this way if, during the inverse transformation, the image is
reconstructed by only taking into account cèrtain coefficients,
a structure with false step-like contours appears. In particular,
if a sub-image is reconstructed by inverse transformation from a
.
single element representing the average luminance of the sub- ~
image, the overall image is formed by a juxtaposition of square-s ~ -
~20 whose repetitive structure can mask the content of the imagë~itself. ~;
SUr~MARY OF THE INVENTION `~
The object of the present invention is a system for
- coding and decoding images by means of a transformation consisting -
of a sequence of matrix multiplications operating on partial ima-
ges, allowing the alleviation to a great extent o~f the above~
desc~ibed faults of the images obtained by Hadamard direct trans-
formation and Hadamard inverse transformation, and allowing a
better compression of the rate in bits per second necessary for
the transmission of the total image.
~30 According to the present invention, there is provided
a matrix transform system for coding images with weighted contribu-
-2-
''' ' '
... . ... . .....
10891(~)
tion of several points o the image to each,point of the coded
image and for decoding coded images with weighted contribution of
several points of the coded image to each point of the decoded
image. ~ :~
The system comprises:
a) means for sampling the lines of an image to be coded
and forming with the image samples a square matrix associated with
the image,
b) means for splitting the square matrix associated . ,;
with the image into a plurality of first input component matrices ~ ,~
of order 3N x 3N having a central part of,order N x N~
c) means for multiplying each of the first input compo~
nent matrices by a first rectangular coefficient matrix of order
N x 3N having a square central part in which the coefficients are `.- ~ :
equal to unity and two æquare lateral parts in which ~he coeffi-
cients are selectively equal to zero and a predetermined factor
: smaller than unity, and forming first intermediate matrices of
order N x 3N; :~;
., . ,,d) means for multiplying each of the first intermediate
':~ 20 matrices by a second rectangular coefficient matrix of order 3N x.N
which is the transpose of said first rectangular coefficient ma- '' ~.-
trix, and forming first output matrices of order N x N, each of
~ , the fir'st output matrices being the transform of the central part ,. ,
; ~ . of~a first input component matrix; `
, e) means for forming with the first output matrices'a ' ~i -
; square matrix associated with the coded image;
: f) means for splitting the square matrix associated ~'
, with the coded image into a plurality of second input component
matrices of order 3N x 3N having a central part of order N x N; ,
,: ,
1 30 g) means for multiplying each of said second'input com- : ~
ponent matrices by a third rectangular coefficient matrix of order ~ :
'
,
0
N x 3N having a square central part of order N x N in which the
coefficients are equal to unity and two square lateral parts of
order N x N in which the coefficients are selectively equal to
zero and a predetermined factor smaller than unity and forming
second intermediate matrices of order N x 3N;
h) means for multiplying each of the second intermediate
matrices by a fourth rectangular coefficient matrix of order 3N x N
which is the transpose of the third rectangular coefficient matrix
and forming second output matrices of order N x N, each of the
second output matrices being the transform of the central pajrt of :~ -
a second input component matrix; and
i) means for forming with th.e second output matrices a . ~.
square matrix associated with-the decoded image.
The tranæformation used in the present invention will be ~ ~
explained by comparing it with a classic Hadamard transformation. ~.
In the case of a unidimensional transformation, a certain ..~.
number of successive samples of a line of the sample matrix are :
considered, for example the six samples xi j to xi j+5. The two ; -
.~ . central samples xi j+2 Xi j+3 are the two samples to be transformed, .:~
the four other samples,.two on the left xi j and xi j+l and~two .. -:
on the right xi j+4 and xi j+5 are samples acting on the trans~
formation. These six samples form a rectangular matrix of order
l:x 6.
the multiplication matrix is a rectangular matrix of .
order 6 x 2 for which the central part is a Hadamard matrix of `
order 2. It follows that the product of the.multiplication is a
.matrix of order 1 x 2. The matrix equation of the transformation
. - is the following~
'~
- _ ~
', , , ' ' . '. ' ' ~' , ' ' ,
o ~
O O! ..
~ i,j Xi,j+l lXi,i+2 Xi,i+31 Xi,j+4 Xi,j+ ~X
tUi,j+2 Ui~j+3~ (3)
this gives for the coefficients u obtained by matrix multiplica- ~ .
tion~
Ui j+2 = Xilj+2 + Xi,i~3 (2) .
Ui j 3 = -~Xi j -axi j+l + Xi,j+2 ~ Xi,j+3 + ~ i~j+4 i~,j+5 ~ .
where a designates a constant less than one. The coefficient .
Ui j+2 is the average value of the luminances of the two points
Xi j+2 and xi j+3. As for the coefficient ui j+3 it can also be
written : ~.
Ui j+3 = a ui j + x~ 2 - xi,j+3 ~ i~j+4
ln the formula (3), the parts which would have alone
been present with a Hadamard transformation of order two have
been surrounded in the sample matrix of order lx6 and in the multi~
plication coefficient matrix of order 6x2 of the first mem~er.
The inverse transformation allowing the reconstruction
; f Xi j+2 and xi j+3 takes into account not only the coefficients ::~
Ui j+2 and ui j+3, but also transformed coefficients of adjacent !~
sub-assemblies ui j~ ui,j+l and ui,j+4 ui,j+5.
The matrix equation is the.following: - . ;
a a ~
LXi,i+2 ~i,j+~= l2 [Ul,j Ui~+l~ui i+~ Ul,j+31Ui, j~4 Ui j+,~
which gives: -
,. 2xi~i+2 = ~Ui,~ l+ Ui,j+2 + ui,j+3 - ~ui,j+4 ~7)
; -5-
v~ ,, , ~ ,
''10~ 0
2x j 3 = -~Ui j + Ui,j+2 ~ Ui,i+3 i,j+4 (8)
By putting:
Wi,j+2 = ui,j + ui j+3 - aui j+4
the formula (7) and (B) can be written:
2xi j+2 = Ui~j+2 + Wi,j+2
2xijj+3 = Ui~j+2 ~ Wi,j+2 (8')
It can be seen that the two consecutive samples of the
transform are formed from six samples of the original image and
l0 that two consecutive samples of the reconstructed image are formed ;
from six samples of the transform. In the formula (6), the parts
which would have alone been present with an inverse Hadamard trans-
formation of order two had been ringed, in the sample matrix of
order lx6 and in the general matrix of order 6x2 of the second
member.
In the case of a bidimensional transformati~n, a square
sample matrix of order six is considered that is multiplied on
the right by the coefficient matrix of equation (3) and on the ;
left by the coefficient matrix transpose, which gives a square
matrix of order two. One has; ~-
~ ,, ri~ --Xi~+5-~ 0,~, ~
r0 ~ 0 0 x Xi+2,j+2 Xi+2,i+3' ....... x ~ ~ ~
~ ~ ta -a ~1 a Xi+3,j+2 Xi+3,i+3 1 0 a ;~ ~
:~, . : ....... ...... O o~ .:~
+5,j-~ -- ----- Xi+5,j+5 _ _
~i+2 "+2 Ui+2,j
~i+3,j+-2 Ui+3,j+~
This gives for the coefficients obtained by double matrix multi-
plication:
Ui+2,j+2 = Xi+2,j+2 + Xi+2~i+3 + xi+3 j+2 + Xi 3 j (l0)
-6-
. ~ : : .: ,
91~0
U1+2 j+3 = -aXi+2 j - ~Xi+2,j+1 + Xi+2,i+2 Xi+2,i+3
+ axi+2,j+4 + aXi+2,i+5 i+3,j i+3,j
+ Xi 3 j 2 ~ xi+3 j+3 + ~xi+3 j+4 + aXi+3 j+5 (11)
Ui+3,j+2 = -~ ~ i,j+2 + xi,j+3 + Xi+l,j+2 + Xi+l,j+
+ Xi+2,j+2 + Xi+2,j+3 ~ Xi+3,j+2 Xi+3,j+3 ~ .
+~ ~i+4,j+2 + xi+4,j+3 + Xi+5,j+2 + Xi+5,j+~ (12)
Ui~3,j+3 = a2LXi,j + Xi~i+l + Xi+l~j + Xi+l,j+l , ,,
+ Xi+4,j+4 + Xi+4,j+5 + Xi+5,j+4 + Xl+5~j+~ 1 -
~2 LXi,j+4 + xi,j+5 + Xi+1,~+4 + Xi~l,j+5
+Xi+4,j + Xi+4,j+1' + Xi+5,j + Xi+5,j+~
+~ CXi,j+3 + Xi+l,j+3 + Xi+2,j+4 + Xi+2,j+5
'" + Xi+3,j + Xi+3,j+1 + Xi+4,j+2 + Xi+5,j~
~Xi,j+2 + Xi+l,j+2 + Xi+2 j + xi+2 j+l
+ xi+3,j+4 + Xi+3~;+s + xi+4,j+3 + xi+5,j+
+ Xi+2 j+2 - Xi+2 j+3 ~ Xi+3,j+2 + Xi+3,j+3 (13)
In equation (9), the parts of the matrices which corres-
ponded to the Hadamard transformation have been ringed. `
Referring for the moment to Figure l, four coefficients
- . .
of the bidimensional transform Ui+2,j+2~ Ui+2,j+3, Ui+3,j+2,
: .
Ui+3 j+3 are shown as well~as the regions formed by the samples of
the image which lead to the~formation of the transform. It can be
seen that Ui+2 j+2 is~only a function of four samples of the image -~
and is nothing more than the mean value of these samples xi+2 j+2
+2,j+3' Xi+3,j+2f xi+3,j+3. The coefficient Ui+2 j+3 and the
coefficient Ui+3 j+2 are a function of twelve samples and the co-
efficient Ui+3 J=3 is a function of thirty six samples. It can
~30 also be seen that certain samples have a complete contribution,
. .
- . positive or negative, and other samples have a lesser contribution
I
!
.",,. ~
,
' ' ' : ,' :', , '.
. ' ' , ' . ' ' ' ' ' ' ' ' ' -
-, 10~91~0
in ~ or in ~2, positive or negative.
The matrix equation of the inverse transformation in
the bi-dimensional case is the following. A square sample matrix
of order six is considered that is multiplied on the right by the .
coefficient matrix of equation (6) and on the left by the coef-
ficient matrix transpose which gives a square matrix of order
two.
U~ Ui,j+5 ~.
..... ......
Fi+2,j+2 Xi+2,j+~ o ~ -a ~ ,,,.~Ui+2,j+2 Ui+2,i+31 -
i+3,j+2 xi+3,j+3J 4 ~ 0~ ,..... 1Ui+3,j+2 Ui+3~j+3
.... ...... ."
Ui+5,j '' Ui+5,i+5 '
'. . ~
: x O O ( 4)
~: . ~ - ~ -
O O
~ The parts of the matriaes which correspond to the
: inverse Hadamard transformation have been ringed in equation (14).
: It has.been supposed.up to now that the multiplication
matrix was of order 6x2, its central parts being a Hadamard matrix
. . ~ .- ~
of order two.
To extend the algorithm of the transformation of order
two to order four, it is noticed that the iterative application
of the matrix transformation resulting from equation (3) allows ~ .
the following coefficients of the transform to be obtained~
Ui j_4 U~ 3 U~ 2 Ui,j-l Ui,j Ui,i+l.Ui,i+
~' ~ . ' ." ' ;. '
. ~ -8~
:
91UO
Ui,j+3 Ui,j+4 Ui,j+5 Ui,j+6 Ui,j+7- The samples Ui j+l and
Ui j+3 thus calculated are retained and a matrix of order lx6
having coefficients with an index j+p where p is even is now
multiplied by the coefficient matrix of order 6x2 of equation (3),
which gives:
O -c~ i
O -a
~i j 4 Ui j 2 Ui j Ui,j+2 U"j+4 Ui i+~ ~ ~ Li j Vi j+~
The four coefficients of the transform are thus:
i,j; vi,j+l; vi,j+2 = Ui,j+l; vi j+3 = Ui j+3
It can be seen that the coefficients of the unidirec-
tional transform are obtained from twelve image samples. This
can be put in the form of the following matrix equation:
, . O -o~ O O
'. O -o~, - O O ..
O -a -a O
., . . . O -a -a
1 1 -1 -a
~ 4 Xi,i-3 ' Xi' ~ 1 1 -1 -a -Ei j Vi j+lvi j+2vi j~
1 -1 a 1
(16)
1 -1 ~,-1
O a O a
O a O a
O a O O . ~.
. ~_ a O O l
The coding and decoding system of the inv~ntion gives a
- bette~ quality of compression, sinae for a 2xl transformation, the
probability of the coefficient ui j+l being zero or small is greater
than is the case for a Hadamard transformation. The transformation
according to the invention introduces an attenuation of the false
square contours and a better statistic approximation of the signal.
. ~................. I .
_g _
,
,.. ,.... - : ~: .
1~91~0
In effect, during the calculation of the inverse transormation, a
filtering operation is carried out on the coefficient U
BRIEF DESCRIPTION OF THE DRAWINGS
Other advantages will appear from a reading of the :~
description which follows and the attached drawings which illustra- ~:
te it and in which~
- Figure 1, which has been mentioned in the introduction
shows the respective contributions of the samples of the image to
the samples of the transform;
- Figures 2a, 2b and 3a, 3b shows respectively in the
form of diagrams, the quickest method of forming samples of the
transform from image samples and thernethod of formation of the : : ;
,
samples of the reconstructed image from the samples of the :~
transform;
- Figure 4 shows in the form of a block diagram, the :~
coding and decoding system of images of the invention for a 2x2 ~.
dimension; :
- Figure S shows, also in the form of a block diagram, ~ ~:
a system for coding and decoding images for 4x4 dimensfons, -:
2a - Figure 6 is a diagram showing the development of the `
points of the transform from the points of the imagè in the case
of the system of Figure 4.
,
DETAILED DESCRIPTION:
Referring to Figure 2a, the manner of forming the -~:
samples u of the image transform from the sample x of the original ~: :
image has been shown in the case of the equations (4) and (5). The
:samples xi 0 to xi 5 are applied to the terminals 100 to 105 dur-
ing a first period, then the samples xi 2 to xi 7 are applied in
a second period and so on by shifting the applied samples by two
samples.
The terminals l00 and 101 are connected to the adder
.. ' I .
--10--
, -,
10~ 0
circuit 110. The terminals 102 and 103 are connected to the adder
circuit 112 and to the subtractor circuit 113. The terminals 104
and 105 are connected to the adder circuit 114. The output of the
adder circuit 112 is connected to the output terminal 122 where
the coefficients ui 2~ Ui 4~ ... are found successively. The
outputs of the adder circuits 110 and 114 are connected to the
subtractor circuit 115 which provide a signal (-ui 0 + ui 4),
(-Ui 2 + Ui 6)~ . The output of the subtractor circuit 115 is
connected to a multiplier by ~ circuit 116. The output of the
multiplier 116 and the output of the subtractor circuit 113
are connected to the adder circuit 117. Finally, the output
of this latter adder circuit is connected to the output terminal
123. It is clear that, when xi 0 to xi 5 are applied to the ter-
minals 100 to 105, the coefficient ui 2 appears at the terminal
,122 and the coefficient ui 3 appears at the terminal 123.
It can be seen (Figure 2b) that it is possible to omit
the adder circuit 110 and replace it by a memory in the form of
a shift register 110', which stores ui 2p and reapplies it to the
dalculator during the calculation of ui 2p+2. In Figure 2b, 13
is a shift register having four outputs (in fact there are as many
shift registers in parallel as bits in the samples) receiving ,'
the sa~ples in series and advancing two steps at,a time. The
outputs 132-135 are respectively connected to the inputs 102-105
of the calculator. When ui 2p appears at the output terminal
122, it is also applied to ~he input of the shit register 110'
which reapplies it to the subtractor circuit 115, a cycle later.
Referring to Figure 3a, the manner of forming the samples
x of the reconstituted image from the coefficients u of the image
transform in the case of equations (7) and (8) is shown. The
coefficients ui 0 to ui 5 are applied to the terminals 200 to 205
during a first pfriod, then the coefficients ui 2 to ui 7 are ap-
- -11-
.
10~91~0
plied coefficients by two coefficients.
The terminals 202 and 203 are connected to the adder circuit
212 and the subtractor circuit 213. The terminals 200 and
204 are connected to the subtractor circuit 215. The output~ of
this circuit 215 is connected to two multiplier circuits 216 and
216' having multiplication factors of ~ and -~. Finally, the
outputs of the multiplier circuits 216 and 216,' are connected
- . .
to two adder circuits 217 and 217', connected, in addition, res- -~
pectively to adder circuits 212 and subtractor circuit 213. The
outputs of the adder circuits 217 and 217' are connected respec- -
tively to the output terminals 222 and 223. v
It is clear that when ui 0 to ui 5 are applied to the
terminals 200 to 205, the aample xi 2 appears at the terminals ~
222 and the sample xi 3 at the terminal 223. -
Figure'3b shows a second calculator of x as a function
,
of u based on the application of equations (7') and (8'). Instead
of being'applied to the terminals 200 to 205 in the order ui 0 to `'`
Ui 5~ the samples of the image transform are applied to these ' -
terminals in the order ui,0~ Ui~ Ui,2' Ui,l' ui,4~ uij3.................. ;-
' which is the natural order of genration of these coefficients~ The .
terminals 200 and 204 are, as in Figure 3a, connected to the sub- '
,
tractor circuit 215 whose output is connected to the multiplier ' '~
by ~ circu~t 216. The output of the circuit 216 is connected to
an adder circuit 218 for which the second input is connected to the '~
terminal 205. It is clear that the signal wi 2 is to'be found at
the output of the cricuit 217. The signal is applied to the adder
circuit 219 and to the subtractor circuit 219' for which the
second inputs are'connected to the terminal 202. The output of
the adder circuit 219 is connected to the output terminal 222 and '~
the output of the subtrac~or clrcuit 219' is conn~ct~ to the ~"
output terminal 223. '
-12- ;
~slao
Figure 4 shows the coder and decoder of images by matrix
transform in accordance with the invention for partial images of
2x2 points.
P Xi~2p~ Xi,2P+l~ f the partial image are
applied to the input terminal 30 of a register 31 which delay8 the
samples by the duration ~ between two successive samples. The
input terminal 30 and the output of the register 31 are connected
to an adder circuit 32 and to a subtractor circuit 23 which carry
out the sum and difference of the two successive sample5 (xi 2p 1
xi 2p+1). The outputs of the adder circuit 32 and subtractor
circuit 33 are connected respectively to registers 34 and 35.
having delays of 2 ~ ~nd 4 T. At the moment when the register
34 receives, at its input, the signal ui 2p+2' it provides at its
output the signal ui 2p 2. These two signals are applies to the
s.ubtractor circui~ 36 which provides (ui 2p+2 ~ Ui 2p 2) This
latter difference signal.is applied to a multiplier circuit 37
which multiplies it by ~.
g (Xi,2p xi,2p+1) leaving the register 35
has been delayed by 2T to make it concomitant with the signal ~ ;
~(ui 2p+2 ~ Ui 2p 2) which leaves the register 34. These two
signals are added in the adder register 38 to form ui 2p+1. Thes ~.
,
~ signals representing the coefficients ui 2p and ui 2p+1 are stored
:~ in the memory 39 so.that the coeficients corresponding to a line
. of the limage form a line in the memory 39. Then the coefficients
~:~ are rearranged in the memory 39 as will be explained.
~ The second stage 41 to 49 is identical to the first stage ~.
,~ 3~1 to 39, with the differénce that the circuit 45 has a delay of
2 lines and the circuit 44 a dealy of 4 lines. Instead of providing
the coefficients u, it provides the coefficients U. The circuits
~30; at the two stages to which the reference numerals te~minate by the
same unit digit are identical, except for what has just been sa.id
-13- :
.
.:
10~91~0
regarding the delay.
As many coefficients U as there are points in the image
are found in the memory 49. These coefficients U are grouped in
squares in memory 49. If a suitable direction of subtraction is
given to subtractor circuits 33, 36, 43, 46, in each square the
coefficient Ui j at the top left is of the type of Figure l(A),
i.e. that which results from the contribution of the four image
points (equation (10)), the coefficient Ui j+l at the top right
is of the type of Figure 1 (B) (equation (11)), i.e. that which
results from a contribution of twelve image points, the coefficient
.. ~ .
Ui+l j at bottom left is of the type of Figure l(C) (equation(12)),
i.e. that which results from a contribution of twelve image points,
and the coefficient Ui+l j+l at bottom right is of the type of
Figure l(D) (equation (13)), which results from a contribution of ~ ;
thirty six image points.
The signals U are applied to the compressor-multiplexer
101; then they are transmitted through the transmission channel
100 to the demultiplexer 102. The compressor contained in the
compressor-multiplexer 101 compresses differently the signals of
types of Figures l(A), (B), (C) and (D). It can, for exampler,
transmit with a certain number of bits the signals of the type of ~ -
Figure l(A), with a certain lesser number of bits the signals of
the type of Figures l(B) and l(C), and with an even lesser number `~
,: . ... ...
of bits the signals of the type of Figure l(D). These latter
signals need not be transmitted at all. The compressor can use -
. ~, . . ..
the compression processes known in the case of the conventional
~ Hadamard transformation. ~ `
! The coefficient ~ is determined experimentally. The
applicant has found tha~ the best results are obtain~d by taking
~ between 0.1 and 0~2. The value 0.125 see~s particularly in~
teresting as much for its results as for its simplicity of digital
-14- ~
: ;' ,~ ,
lowla~
coding.
The decoder comprises, like the coder, two identical
delay stages of register, one relative to a decoding by lines
and the other a decoding by columns. The second stage will be
described.
The memory 59 of the first stage has been filled by lines
and the coefficients have been rearranged as will be explained.
The signal ui 2p+2 is applied to the shift register 61 where it
is delayed by ~ as well as to a subtractor circuit 63. The ~ ~
signal ui 2p+1 leaving the register 61 is applied to a register ~ ~ -
62 for delaying it by ~ and to an adder circuit 65. The signal -~
Ui 2p leaving the register 62 iS applied to an adder circuit 66,
to a subtractor circuit 68 and to a shift register having a delay
2T. The signal ui 2p 2 leaving the register 64 is applied to the
subtractor circuit 63 whose output is connected to a multiplier
by circuit 67. The output of the multiplier circuit 67 is connec-
ted to the adder circuit 65 and the output of the latter is connec-
.
ted to adder circuit 66 and subtractor circuit 68. Finally, these ~
two last mentioned circuits are connected to the memory 69 from ~ -
~ , . ,
which the output 60 is the output of the decoder.
- In Figure 6(A), an image having a dozen points per line
and a dozen lines has been shown. A rectangle T surrounding six
samples moves along the line from a position To 0 in which it
contains two zero points on the left outside the image to a
position To 5 in which it contains two zero points on the right -
~ outside the image. Each position of the rectangle T on a line of
; thé image gives rise to two coefficients of a line of the trans-
form of Figure 6(B). These coefficients are of two different
types. One shown in white is of the type ui 2p and the other shown
in cross hatching is of the type ui 2p+1 These are samples which
; are written into the memory 39.
' I . '
-15-
-
10~9~(i0
Before subjecting the line transform to the column trans-
formation the coefficient u2r 2p+1 is exchanged in the matrix of
Figure 6(B) with the coefficient u2r+l 2p so as to obtain the
matrix of Figure 6(C). In other words, it can be said that the ~ ;
matrix of order 12x12 of Figure 6(B) is split into matrices of
order 2x2 and that these latter matrices are transposed. This
re-arrangement of the matrix 6(B), in order to obtain the matrix
6(C), allows a stage identical to the coding stage for the lines
to be taken as the coding stage for the columns. Returning to
the case of a 6x6 sample matrix of equation (9) the coding stage
for thelines serves to multiply each sample line forming a line
. .
matrix of order lx6 by a general multiplication matrix of order
6x2 thus to obtain a matrix of order lx2 for each sample line. -~
All these line matrices form a resulting matrix of order 6x2. But,
when this 6x2 matrix has been obtained, i.e. when the middle matrix
and the right hand matrix of equation (9) has been multiplied -
therebetween, there remains the following multiplication of the ~;
resulting matrix by left hand matrix of equation (9):
(II)
I
0 ~ ~ 0 ul 1ui+2 2p --ui+2~2p+l~ (17)
~ x .:,
a . ~ ~:
+4,2p Ui+4,2p+1 ~ -
Ui+5,2p Ui+5~2P+l ,
This multiplication i8 a multiplication of a matrix of
order 2x6 by a matrix of order 6x2 which gives a resulting matrix
of order 2x2. It is advantageous to convert the "u" coefficient
, ~ ' 'I
-16-
losslao
matrix of order 6x2 (matrix (II) in expression 17) into a 2x6
matrix and to convert the general multiplication matrix of order
2x6 (matrix (I) in expressionl7) into a 6x2 matrix which allows
the same calculation algorithm as in the line transformation to
be used for the column transformation.
Considering that the transpose of a matrix product is
equal to the product of the transposes taken in the reverse order, -~
the product of the transposes taken in the reverse order, the ~
product (17) can be written as follows by replacing matrix (I) by '
matrix (I') and matrix (II) by matrix (II') and changing the mul-
tiplication direction~
~ ~O ~ 1
¦ui 2p Ui+1~2P ¦ ui+2,2p Ui+3,2P-¦Ui+4,2p Ui+4~2p ¦ 1 -1
ui 2p+1 Ui+l,2p+11, 1ui+2~2p+l Ui+3,2p~lli+4,2p+1 Ui+5,2p+~ 1 -l ~ '~
O + a ::;
:~ . . . ~+ a l . .
J . 18~
`;
! ~ - If each of the component matrices of order 2x2 constitut-
ing the matrix for the "u coefficients" of the expressions 17 and
., - . . .
18 i6 considered, it can be seen that they are obtained relative
t 20 ~ ~
'~ to each other by transposition. ,
' ~ The transformation applied to the matrix of Fig. 6A is
~ again applied to the matrix of Fig. 6C, i.e. a rectangle R sur-
, ii .
~ rounding six samples is displaced'along the line from a position
'`'~` ~ Ro O surrounding two zero samples of the proceeding line, the --~
'~ samples uO O and ul O and the samples u2 0 and U3 0 to the position
R5 O. In fact, the calculation device-is fed by the reading line `
~, ' by line of the matrix C, the data of the upper,and lower lines
, being retained in the internal memories of the device (44 and 45 ,
'I of Figure 4).
When the rectangle R is displaced along an even line
' , (white squares) of C, the coefficients of type Ui 2p' Ui~l 2p are
-17-
. , . , . . . -: .:
~ . _
: . ,
10~91~0
obtained by moving along an odd line (cross hatched) the coefficients
Ui,2p+1 Ui+l,2p+1 are obtained.
The matrix D is filled line by line with coefficients
of different types, the first shown ~ is o t yp 2r,2p
second shown ~ is of the type U2r+1,2p' the t ~ is ~ :
of the type U2r 2p+1 and the fourth shown ~ is of the type
U2r+l 2p+1. It should be noticed that in order to recover the
normal matrix configuration, the elementary matrices 2x2 for the
U coefficients must be transposed.
Figure 5 shows a line cader for the 4x4 dimension compose~
of two stages 71 and 72 of the type of the first stage 4 of Figure ~ ~
4. The first stage 71 operates at the rate f, receives the samples ~ ;
of the image and provides the coefficients ui and ui 2p+1
The coefficients ui 2p+1 ar.e outputted and the coefficients ui 2p :~
are applied to the second stage 72 identical to the first with
the sole difference that it operates at the frequency f/2.
The second stage 72 provides vi 4p and vi 4p+1 The
first St~.ge provides one time in two ui 2p+1 = Vi 4p+2 and the !
: 20 me ui, 2p+3 vi,4p+3. The coefficients vi 4 , vi
Vi 4p+2 and vi 4p+3 are written in thememory 79. In order to carry ~ ~:
out the complete transform, a column coder having two stages is
arrange behing the line coder 71-72. ~ -
,
Figure 5b shows a line decoder for the 4x4 dimehsion
composed of two stages 81 and 82 of the type of the second stage ~ ~.
6 of Figure 4. The first stage 81 operates at the rate f/2, re-
ceives from thememory 79 the coefficients of the transform vi 4p
and vi 4p+3 and provides the coefficlents ui 2p to.the second stage
82.
.The second stage 82 operates at the rate f. The coeffi-
. cients vi 4p+2 and vi 4p+3 are applied~ each on time in two, to
.. ;~, I .
-18-
~ ,
10~91~0
the stage 82. At the output of this stage, the samples of the
reconstructed image xi 2p ~ Xi 2p+1~ are found. In order to
carry out the complete transform, a column decoder having two
stages is arranged in front of the line decoder 81-82. The putting
in cascade of a line stages and b column stages allow us the
transformation to be carried out on a sub-image having 2a 2b points.
.. :
'
, "
:. :
,
~,',, , I , ''
-19- ~ ,
~ ~"'" ' '
_.. .
