Note: Descriptions are shown in the official language in which they were submitted.
VECTOR QUANTIZER
BACKGROUND_OF_THE INVENTION
Field oE the Invention
The present invention relates to a vector quantizer
for quantizing the vector of image information and audio
information, and is a division of application Serial No.
466,293 filed October 25, 1984.
Description of the Prior ~rt
__________
The prior art relating to such a vector quantizer
is described in literatures such as: Y. Linde, A. Buzo
and R.M. Gray, "An Algorithm for Vector Ouantizer", IEEE
Trans., Com-28, pp. 84 - 95 (1980); A Gersho, "On the
Structure of Vector Quantizers", IEEE Trans., IT-82, pp.
157 - 166 (1982); A. Buzo and A.H. Gray, Jr., "Speech
Coding Based Upon Vector Quantization", IEEE Trans.,
ASSP-28 (1980); B.H. Juang and A.H. Gray, Jr., "Multiple
Stage Quantization for Speech Coding", Proc. Intl. Conf.
on A.S.S.P., pp. 597 - 600, Paris (1982); and A. Gersho
and V. Cuperman, "Vector Quantization: A Pattern Matching
Technique for Speech Coding", IEEE, COMMUNICATION MAGAZINE,
pp. 15 - 21, Dec. (1983).
A discussion of the prior art will be made in detail
hereinbelow.
- 2 -
SVMMAR~ OF_THE INVENTION
The present invention consists of a vector quantizer
comprising a vector quanti~ation encoder including a
subvector register which stores picture signal sequences
to be coded, samples every N (N = a plural number) picture
signal sequences in blocks to store the input picture
signal sequences as input subvectors and a coding code
table memory capable of sampling output vectors obtained
previously by clustering or the like using picture input
signal sequences to form blocks of the output vectors,
and of reading the bloc~s as output subvectors, and having
a constitution of the pipeline system which selects an
output subvector having a minimum distortion from the
input subvector, from a set of output subvectors stored
in the code table memory, codes the address of the selected
output subvector and gives the corresponding index of the
output subvector; and a decoder which reads the correspond-
ing output vector by using the index given by the encoder
as the address of the output vector from a decoding code
table memory storing a set o~ output vectors obtained by
clustering or the like using picture input signal
sequences, and then decodes the output vector.
BI~I~F D~SC~IPl`XO~ OF 111~ DRl~ lGS
Figure 1 is an explanatory pictorial view for
~acilital:ing tlle understalldillcJ oE the deEiniition of tlle
111ovelnellt o~ picture sigl~a1s t~etweel1 ra1nes by a move111elli.
5 vector;
Figure 2 is an eYplalla~ory view showiJlg the re1ation
betweell the move111ent vector and tlle arrange111ent of tl~e
picture elemellts oE a moved bloclc;
Figure 3 is a block diagram showing a conventiolla
10 movemen~ col11pensatioll inter-fralne encoder:
Figure 4 is a graph s~howillg tlle input-output
characteristics oE the scalar quantizer employed in tl~e
encoder of Fig. 3;
Fiyure 5 is a block diagram oE the movelnellt vector
15 detector employed in tl~e encoder of Fig. 3;
Figure 6 is a bloclc diagram sllowing tlle COIlStitU-
tion oE a vector encoder, in a preferrbd embodil11ellt~
according to tlle presen~ invel1tioll;
I;`icJure 7 is a block diagram sllowintJ tlle COI1stitU-
20 t ion oE the adaptive vector quantization encoder
el11p Loyed in ~lle encocler oE Fig . 6
F.i.clure U .is a L~:lock diagraln sl1owincJ ttle cons ti tu-
tion oE ~lle adaptive vecl or quantizatioll decoder
eniployetl ill tlle ellcoder o~ Y;';kJ. 6;
l;~icJure 9 is a11 exE~lana~ol y represe1lt~i ion sl1owi11-J
a pl-edicl:ive error picture sigl1aJ ncilllely, al1 adaptive
VeCl:OI- (lUall~:i.7.a(:.i.01~ .i.llpUl: g.iCJI~ iL, ill tl~e el~codel o~
( I;'iy. 6;
Figure 10 is a c3rapll exp1aining tlle relatio
betweell tlle i1lput vec~or and tlle output vector i~
vector qUantiZatiOIl;
S E'igure lL is a view exp1a~lliny tile tirlle relation
betweel~ ovelllent colnpellsation and vector qUantiZatiOI~
process on a scene:
Figure 12 is a ~loclc diagram sllo~ring tlle COI15 titu-
tioll of the encoder of an in~er-frame vector encoder for
explainil)g tlle basic principle of another elnbodilllel-t o~
tlle present invelltion;
Figure 13 is a block diagram showinc3 the constitu-
tiOIl of tlle vector yuantization encoder of Fig. 12;
Figure 14 is a block diagram sllowing tlle constitu-
tion of tlle vector qualltizatioll decoder of Fig. 12
Fiyure 15 is a b1ock diagram sllowing tlle constitu-
tion of the clecoder of an in~er-frame vector encocler;
Figure 16 is a view explainilly tl)e mode of picture
sic3nal sec~uence ~locking~
Figure 17 is a ~lock diagram o~ an encoder of an
illter-frallle vector ellcoder, ill otller elnbodilllellt,
accordillcJ to tl~e presellt invelltiol~;
l~igure 1~ is n bLoclc diacJralil sl~owirlc3 tlle
collsl:i,tu~ic)ll o~ a Illovclllel~t detectioll vector c~uallti~.a~io
ellcoder o~ L;~ic~. 1'~;
lig~lre l9 is a bloclc diacJr.alll sllowil~c3 tlle
cc)llsl:itllt;oll of tlle vector ~luallti~,atioll decocler o~
( Fig. 17;
Figure 20 is a block diagram s~lowirlg an exelllpl~ry
constitutioll o tlle decoder o~ tlle inter-~rame vector
encocler accordiny to tlle present invention;
Figure 21 is a block diayram showiny a constitution
o~ a picture siynal vector quantization encoder;
Fiyure 22 is a block diagram ~howing a constitution
oE a picture signal vector cluantization decoder;
Figure 23 is an illustratio~ ShOWill9, in compariso
tl~e input and output subvectors a picture signal
subsample vector quantizer according to the present
invention and tlle ln~ut and output vectors of a
convelltiollal picture signal vector quantizer;
Figure 24 is a block~diagram sllowing a picture
signal vector quantization ellcoder of the present
invention;
Fiyure 25 is a block d1agram showillg a picture
sigl~a1 movelnellt competlsatioi~ vector quantization encoder
embodying tl~e pre~ent invetltiotl;
~igure 26 is a block ~1agraln sllowillg an exemplary
constitutioll o~ tlle movelnellt vector quantizer of Fig. 25;
Figure 27 i9 a repre8elltatiOll SllOWillg all eY~alllple
of Inovelllen~ vector ~rr~ngelnellt for e~plainillg a dynalllic
olltplll: vectol code ~a~le producLIl9 Illetllod ~ccordLIlg to
tlle pre~ellt invelltioll;
I~i9(1L'e 2~ i9 ~ view ~or expl~inillcJ tlle prillciple
of nlovelllr3llt ~ector quall~ atioll of tlle presellt invel~Loll:
-- 6
Fiyure 29 is a bloclc di~yrall) sl~owing a11 eXelllplary
COIlStitutiO~l oE tlle diEEerelltial vector ~u~ntizer o~
I;'ig. ~5;
I:'igure 30 is a block diayranl sllowi~ly tlle
S collstitutioll oE a plcture si.gllal movelllent co~llpellsatio
vector qualltizatioll decoder according to tlle present
illven tiOIl;
Figure 31 is a block diagram sllowing a dynamic
multistage vector quantiza~ion encode embodying tlle
present il~vention;
Figure 3 2 is a represen ta-tion for explaitling the
principle of the ~ront movement vector encoder oE the
vector quantization encoder of Fig. 31;
Figure 33 is a representa'cion explaining the
inter-Erallle matclling between tlle preceding frame and tlle
presel~t Erame ill ntovelllellt vector coding;
Figure 34 is a grapll sl~owing tlle probability
distributioll oE Inovelllellt vectoxs;
E~igure 35 is a represe~ a tioll explainillg tl~e
arrallgement o~ movelnellt vectors;
Fiyure 3 6 is a bloclc diagram sllowing an exemplary
COIIStitUtiOI~ oE ~lle Erollb vecl:or qualltizatiol~ el-coder
oE a vector qualll:izatioll ellcoder accord~ng to tl~e
~ e ~ V C~ i. o t l
l:'iyur.e 3 ~ .i.s a l:).Lock dlayralll sllowillg l:lle
C0115t.i.l:Ul:.iOII oE tlle dif~erelll:.La.l vecl:or qualll:izat.io
ellcodel- of l;`iy. 31.;
( Figure ~B is a block diagram sllowing tlle
constitution oE a dynamic multistage vector quantizatio
decoder enlbodyillcJ tlle present invelltioll;
Figure 39 is a bloclc di.agraln sllowil)y an example oE
a movelllent compensation illter-~ralne encoder;
Figure 40 is a gxaph sllowiny tile input-output
characteristics o~ the scalar quan~izer o~ Flg. 39:
Figure 41 is a block diagraln sllowing the
constitution of the movement vector detec~or of Fig. 39;
10Figure 42 ls a block di.agram showing the
constitution o~ the encoder of a vector quantizer
embodying the present invention;
Figure 4~ is a block d.iagram showing ~he
constitu~ion of a dynamic front vector quantizer of the
present invention;
Figure 44 i9 a grapllical illu~tration showing the
arrallgelllel)t of fixed output vectors ln mu1ti-d~mensional
space:
Figures 45 alld 4G are explallatory representations
sllowing an example of a rewri~able output vector code
table prOd-lCil)g InetllOd
Figure 47 1s a block dlagranl sllowing tlle
COIlStitUti.On oE tlle Eixed baclc vector qualltizer of
~ic3. ~2;
F.ic1uL^e ~U .i.. s a l~lock d.LagJ~a~ llowillg ~llo
COIISt.itU~iOII oE ~lle decocler oE a vector qUall~iZer
ellll)o(ly illg tlle ~resell~ .i.llvell~1OlI
;3'7
Figure ~ g i5 a block diagraln s~owillg tlle
- constil;utioll oE tlle ellcoder o~ an inter~rame vector
cluantizer;
LFiyure 50 is a b].ock diagraln showit~y the
constitutioll o tlle vector q~antizatioll encoder of
~ig. 49;
Fiqure 51 is a block diagraln showiny the
COIlstitutioll o~ tlle vector quantization decoder of
Fig. 49;
Figure 52 is a block diagram sllowing the
titutiOll oE tlle decoder of an inter-frame vector
qual~tizex:
Figure 53 is an explanatory representation for the
eY~plall~tion of a picture signal blocking process;
Figure 54 is al? e~planatory representation o~ a
tree searcll vector quanti~ation;
Figure 55 is a block diagraln sllowing tlle
COI~StitutiOll of tlle ellcoder oE a serial apprOXilllatioll
vector qualltizer elnbody1ng tlle present i~lventioll;
Figure 56 is a block diagram sllowing tlle
COIlstitutiOll of the TSVQ encoder of Fig. 55;
Figure 57 is a block diagram sl~owincJ tlle
COIlstitutioll o~ tlle secolld-staye '~'SVQ encoder o F'i.c~. 5~;
Figure 5~ i.s a b.l.ock d.iayralll sllowiny tlle
collskitutloll oE tlle 'l'SVU decocler o ri9. 5G
Fic3ure 59 is a bJ.ock dlacJralll sllowil)y tl~e
COn51:.itUtiOII o tlle decoder o a serial vector quan~izer,
DES~PrION OF ~-E P~ER~ ~~~LM~
A vector quantizer as sho~n in Fig. 3, which ,lill b~ des-
cribed later, is known in addition to those vector quantizecs of
the prior art. The principle of the vector quantizer will be
described prior to the description of the ~ector quantizer of
Fig. 3. Referring to Fig. 1, asswning that an object has rnoved
on the screen during the period from a frame No. f-l to
a frame No. f from a position A to a position B, then a
block Sf(R) including a plurality of the lattice samples
of an image signal around a position vector R in the
frame No. f becomes approximately equal to the block
sf ltR-r) of the image signal at a position determined by
subtracting a movement vector r from a position vector R
in the frame No. f-l. As shown in Fig. 2, when the
position vector R = (m, n) and the movement vector
r = (u, v), Sf(R) ' sf l(R-r). Suppose the image signal
at R = tm, n) is S(M, n) and Sf(R) = [S(m-2, n-2), ....
S(m, n), ..., S(m+2, n+2)~, the degree of analogy L(n, v)
between Sf(R) and sf l(R-r) is defined as the block unit
matching scale of 5x5 picture element as follows;
L(u, v) = ~ ~ ¦sf(m+g, n+h) sf l(m+g-u, n+h-v)¦
g h
In this state, the movement vector r is expressed by
r = lu, v ¦min L(u, v)]
u, v
That is, the degree of analoyy L(u, v) of S (R) and
sf l(R-r) is expected to be minimized by block matching.
Therefore, in introducing movement compensation into
inter-frame ~rediction coding, tlle use of a block WtliCtl
millimizes L(u, v), extracted from image signal blocks of
- 10 -
the frame No. f-l, as a prediction signal in giving the
block Sf(R) of the image signal of the position of R in
the frame No. f to an inter-frame prediction encoder
the power of prediction error signal will be reduced to
the least and encoding efficiency is improved.
Referri.ng to Fig. 3 showing an example of the
constitution of a conventional vector quantizer of this
kind there are shown an A/D converter 1 a raster/block
scan converter 2 a frame memory 3 a movement vector
detector 4 a variable delay circuit 5 a subtractor 6
a scalar quantizer 7 an adder 8 and a variable-length
encoder 9.
The manner of operation of this vector quantizer
will be described hereinafter. First the A/D converter
1 converts an analog picture input signal 101 into the
corresponding digital signal and gives a digital picture
signal sequence 102 according to the sequence of raster
scanning. The output procedure of the raster scan digital
picture signal sequence 102 on the time series of the
picture signal is converted into block scaning by the
raster/block scan converter 2 and thereby the digital
picture signal sequence is converted into a block scan
picture input signal 103 arranged sequentially in lattice
block units (the interior of the block is raster
scanning) from the top to the bottom and from the left to
the right 011 the screen. A rec3enerative picture signaL
104 of one frame before regenerated according to inter--
frame DPCM loop i5 read from the frame rnemory 3. ~rhe
movement vector detector 4 executes the block matchillg oE
the present block scan picture input signal 103, klle
regenerative picture signal 104 of one frame before and
the picture signal and gives the movement vector
r = (u, v) of the picture signal 104 of one frame before
which minimizes the degree of analogy. The movement
vectors (u, v) corresponds to the horizontal and the
vertical shifts o~ the picture element of the block of
the regenerative picture signal 104 of one frame before.
On the basis of the movement vector 104, the variable
delay circuit 5 block-shifts the one-frame precedin~
regenerative picture signal 104 by the movement vector
and gives a predictive picture signal 106 which is the
closest to the present block scan picture input signal
103. The subtractor 6 calculates the differential
between the block scan picture input signal 103 and the
predictive picture signal 106 and gives a predictive
error picture signal 107 to the scalar quantizer 7. The
scalar quantizer 7 converts the predictive error picture
signal 106 into a predictive error quantization picture
signal 108 reduced in quantization level at picture
element unit. The adder 8 adds the predictive error
quantization picture signal 108 and the predictive
picture signal 106 and gives a regenerative picture
signal 109 including scalar quantization error to the
frame memory 3. The frame memory performs delaying
operation to delay tlle present regenerative picture sigllal
109 ~y one frame. In the movement compensation inter-
frame DPCM loop, supposing that the picture input signal
- 12 -
'7
103 is sf(m, n), ~he predictive picture signal 106 is
Pf(m, n), the predictive error signal 107 is Ef(m, n),
scalar quantizat:ion noise is Qf (Tn~ n), the predictive
error quantization signal 108 is sf(m, n) and the one-
frame preceding regenerative pi.cture signal 104 issf l(m, n), then
(m, nJ = sf(m, n) - Pf(m, n),
~f(m, n) = ~f(m, n) + Qsf(m~ n),
sf(m, n) = Pftm, n) ~ ~f(m, n) = sf(m, n)
~ Qstm, n), and
Sf-l( ) Sf( ) z-f
where Z f denotes delay corresponding to one frame.
Pf(m, n) is expressed through movement compensation
on the basis of sf ltm, n) by the following formula:
Pf(m, n) = sf~l(m-u, n-v).
Fig. S shows an example of the constitution of the
movement vector detector 4 for carrying out movement
compensation .
Referring to Fig. S, there are shown an analogy
degree computation circuit lO, a movement region line
memory ll, a line memory control circuit 12, an analogy
degree comparator 13 and a movemellt vector latch 14.
The movemellt vector detector 4 gives Sf(R) produced
by blocking a plurality of tlle se~uences of tlle present
picture input signal 103 to the analogy degree
'7
( computation circuit 10. At this moment, the lines of
the one-frame preceding regenerative picture signal 104
stored in the frame memory 3 corresporlding to the
tracking range of the rnovemen~ region of Sf(E~) are
stored in the movement region line memory 11. The line
memory control circuit 12 sends sequentially the blocks
adjacent to a plurality of blocks sf l(R+r) of the
one-frame preceding regenerative image signal 104 to the
analogy degree computation circuit 10. The analogy
degree computation circuit 10 computes the analogy clegree
L(u, v) of the blocks in the neighborhood of Sf(R) and
sf l(R-r) and the analogy degree comparator 13 determines
the minimum analogy degree min L(u, v). Since u and v
u,v
cor,responds to the horizontal and the vertical address
shifts of blocks in the movement region line memory 11
respectively, the analogy degree comparator 13 gives a
movement detection strobing signal 111 to the movement
vector latch 14 when the analogy degree is minimized, to
take in a movement vector address 112. The movement
vector latch 14 sends the displacement r of sf l(R-r)
relative to Sf(R) minimizing the analogy degree L(u, v)
as a movement vector 105 to the variable delay circuit 5
and the variable-length encoder 9 of Fig. 3.
The variable-lenc3th encoder 9 of Fig. 3 processes
~5 the movement vector 105 and the predictive error
quantization siynal 108 throuc3h variable-lenc3th encoding
to reduce the amount of information of the picture signal.
-- 1 '1 --
The variable length encodiny enables the transmission of
the movement compensation inter-frame encoding output
110 at a low bit rate.
Since the conventional movement compensation
inter-frame encoder is constituted as described herein-
before, the movement compensation operation is performed
for every block and the inter-frame DPCM operation is
performed for every picture element. Accordingly, the
identification between the minute variation of the screen
and noise is impossible and the variable-length encoding
of the movement vector and the predictive error quanti-
zation signal is difficult. Purthermore, since the
control of the variation of the quantity of produced
information resulting from the variation of the movement
scalar is difficult, a large loss is inevitable when
transmission is carried out through a transmission
channel of a fixed transmission capacity. Still further,
encoding the predictive error quantization signal for
every picture element is inefficient. Since the
movement compensation system is liable to be affected by
transmission channel error, the fralne memory needs to be
reset or repeated trallslnission when transmission challllel
error occurs, which requires long resetting time.
I:'ig. G .is a block diagran1 sl1owil1y t1~e Co11Sti~Ucti
o~ an elnbodill1el1k oE tl1e vector e11coder according to tlle
~resent invel1l:iol1.
lleferril1y to Piy. 6, there are s11own a Inultiaccess
Eran1e n1el11ory 20, an adaptive vector quantization encoder
21 and all adaptive vector quantization decoder 22. In
Fig. 6, parts designated by the same re~erence characters
as tllose used in Fig. 3 are the same or like parts as
tllose of Fig. 3.
Figs. 7 and 8 are block diagrams showing the
respective ~constitutions of embodiments o~ the adaptive
vec-tor qUa11tiZatiO11 encoder and t~le adaptive vector
quantization decoder which are applicable to the present
inve1ltion respectively.
In Figs. 7 and B, there are shown a mean value
separation circuit 23, a normalization circuit 24, a
significa1lce decision circuit 25, an output vector
address counter 26, an output vector code table 27, a
distortion computatio11 circuit 26, a mi1li1num distortion
detsctor 29, an index latch 30, a mean value COrreCtiO11
circuit 31,an amplitude regel1eration circuit 32 and a
regel1erative vector reyister 33. Like or correspo11di11g
p~L-tS are designated ~y 11ke reEerel1ce cllaracters
t11rou911out t11e clrawincJs.
'l'lle n1a11ner of opera~ion of a conlpellsatil)y inter-
Erame vector encoder according to tlle presel1t il1ve11tio1l
will be descri.l~ed l1erei11after in con11ectio11 witl1 Pig. G.
raster/~lock scallni11cJ col1vertor 2 gives a ~.locJc
- 16 -
scan picture input signal 103 ~o a movelllerlt vector
i detector 4 and a block scan picture input siynal 120
delayed by several lines so that the block sc~n picture
input signal will not overlap a nlovernellt compensatioll
region to a subtractor 6, for inter-frame vector encodilly.
movelllent vector detector 4 obtains a rnovement vector
105 througll the same procedure as that of the movement
detectioll on the basis of the picture input siynal 103
and a preceding neighbor frame regenerative picture
signal 121 and controls a variable delay circuit 5 so
tllat the variable delay circuit 5 gives a predictive
picture signal 122 corresponding ~o the position of the
block scan picture input slgnal 120 ~o a subtra~tor 6.
'l'he output signals of the subtractor 6, i,e., predictive
error picture signals 123 are blocked and are vector~
quantized througll the adaptive vector quantization
encoder 128 and the adaptive vector quantization decoder
12J. q'he predictive error picture signal 123 is
vector-quantized to provide a predictive error vector
qualltization picture signal 125 containing vector-
qualltized noises. ~n, adder 8 adds the predictive error
vector yualltization picture sigllal 125 and the predictive
picture signal 122 and gives a regenerative pict,ure
sicJIlaL l26. ~ e regellerative picture signal 126 is
t~ritl:ell in tllc? Illultlaccess Eralne ll~elnory 20 in a region
~ icll is not dtll)licated wi~ll a nlovelllellt colllpensatioll
execul:.ic)ll re9;.oll.
l~lle a~ove-s~cl~e(~ er-frallle en(odillc3 process is
~'X~?~ rOI- CV(`I~ Loc lt, ~:IlC~r(~rOl:e, c~.~cl~ ock i.';
- 17 -
3'~
de~ined by a picture element vector, Let tlle picture
input signal 120 is sf ~ the predictive picture signal 122
is Pf, the predictive error signal 123 is Ef, the
predictive error vector quantization signal 125 is Ef,
5 the vector quantization noise is ~f, the regenerative
pic~:ure signal 126 is sf and the preceding neighbor
regenerative picture signal 121 is gf 1, where Q
indicates the block sequence number~ then inter-frame
encoding computation is expressed by
~f = sf - PQ,
E f = E D 'I' QQ ~
sf = ~f ~ PQ = SQ ~ QQf, and
S f ~ 1 = S f ~ ~ ~
The predictive picture signal 122 undergoes
movement compellsation process and is formed by cutting
out a block sllifted so that the analogy degree is
millimized from the preceding neighbor regenerative
signal 121. The block of the predictive picture signal
122 cut out alld formed througll movement compensation need
I~Ot coincide with a block dealt with by inter-frame
vector coding in boundary and block size. The movement
compensation is performed in a sliding block matching
mode whiie inter-frallle vector encoding is performed in a
fixed block mode.
Now, tl~e nlallner of operatioll of the aclapl:ive vector
quantizer WlliCIl acllieves lligllly efficient encodillc3
throllyll the adaptive vector quantizatioll as the predicti ve
erl-ol- pictul-e ~iiynal 123 is sul) jected to significallce
dc?cisioll i1l bloclcs. 'I'lle aclaptive vector ~lllalll:;~(?l-
16
Z comprises a cascaded connection of the adaptive vector
quantization encoder 21 and the adaptive vector
quantization decoder 22.
First the principle of the adaptive quantization of
the predictive error signal, according to the present
invention will be described.
Suppose that the predictive error picture signal
~Q = [~ 2~ k] arranged in blocks is obtained,
as shown in Fig. 9, by subtracting each dimension of the
blocks PQ of the predictive picture signal from the
blocks SQ of the picture input signal. The predictive
error picture signal ~Q is subjected to conversion to
execute significance decision and adaptive vector
quantization.
1 k
~Q = K- ~ Ej,
~=1
~Q = K 1 ~ lj _
Xj = (~ Q)/~Q
XQ = [Xl, X2, ..., Xk]
That is, the mean value ~Q is separated and
normalized with respect to the amplitude ~Q to obtain
the input vector XQ. The input vector XQ is vector-
quantized in a k-dimensional signal space and mapped into
an output vector Yi = [Yil~ Yi2~ ~ Yik
distortion. 'l'lle output vector Yi is converted into a
- 19 -
predictive error vector quantization picture siynal ~Q
through the following reverse conversion.
Ej = ~iQ'Yij ~ ~
~Q = [~ 2~ Ek]
where ~Q = O when ~Q < Tl and ~Q < T2, Tl and T2
defines a threshold 128 for the level decision of ~.
The significance of the predictive error pic~ure signal
is decided in blocks and the predictive error picture
signal is subjected to average value separation amplitude
normalization to vector-quantize the signal only when the
level of the picture signal changes between frames of a
predetermined level after movement compensation. When
the level of the picture signal is below the predeter-
mined level, there is no movement or the picture can
lS entirely be regenerated through movement ~ompensation.
When the significance decision identification code of
the block ~Q of the predictive error picture signal is
given by VQ and
vQ = O when ~ Q < Tl and ~Q < T2 and
VQ = 1 when ~ > Tl or ~Q > T2,
thell, when insignificant, the block can be encoded by on
bit. ~rlle information production can be held at a fixed
amoullt by controllillcJ the thresllold 12~ of '1'l alld 'I'2'
Now, the principle of vector ~uantizatiorl Eor
encoding the input vector o~ t11e predictive error picture
- ~n -
'7
signal at a very low bit ra~e and at a high efficiency
will be described hereinafter.
Suppose that X = [Xl, X2, ..., Xk]
veetor in k-dimensional signal space Rk, while Rl, R2,
..., ~ are N partitions of Rk and Y = [Yl~ Y2~ ~ ~N]
is a set of output vectors Yi = [Yil~ Yi2~ ~ Yik]'
i.e., the representative points of the partial spaces Ri
and the index set of Yi is Y = ~1, 2, ,.., N]. Then,
veetor quan~ization VQ is given by the easeaded
eonnection of eneoding C and deeoding D.
Q ) Yi, if~x Ri
C : X ~ i, if d(x, Yi) ~ d(x, yj) for all j
D ~ y
Distortion measurement d(x, Yi) indieates the
separation between the input and the output veetors in
the k-dimensional signal spaee and absolute distortion
measurement is
]c
d(x, Yi) = j~l ¦xj Yijl
The data rate of the index i, whieh is the veetor
quantization coding output at this time, is K log2N
bits/picture element. That is, highly efficient
encoding is achieved by encoding vector quantization
illtO tlle input vector x and the inclex i o~ OUtpllt vector
Yi minimizin~ distortion to tlle minimuln distortion mi
d(x, Yi). Decoding is achieved simply by conversion
'7
into output vector Yi corresponding to the index i. The
set Y of output vectors Yi may be obtained either by the
clustering training of the actual input vectors x of by
a predetermined input vector probability model. Fig. 10
S shows the relation input vectors and output vectors.
The adaptive vector quantization coding outputs are
significance decision index vQ, mean value ~Q, amplitude
gain ~Q and output vector index i,
The manner of operation of the adaptive vector
quantization encoder will be described in connection
with Fig. 7.
The predictive error picture signal 123 is processed
in blocks through the mean value separation circuit 23
and the normalization circuit 24 to be mean value
separation normalized and input vector 129 is sent to
the distortion computation circuit 28, At this time,
the output vector address counter 26 counts up sequen-
tially and reads the output vector 131 from the output
vector code table 27, The distortion computation
circuit 28 computes the distortion d(x, Yi) between the
input vector and the output vector and sends the
distortion 132 from each output vector to the minimum
distortion detector 29. The minimum distortion detector
29 gives strobing signal 133 so that the output vector
~5 address 134 of the output vector address counter 26
correspolldin~ to the index of the output vector is
stored in the index latch, ~hen the minimum distortion
between the output vector and the input vector i5
detected. ~he index latch 30 gives the index of the
output vector which has the minimum distortion with
respect to the input vector. The signi~icance decision
circuit 25 gives, on the basis of the mean value of the
blocks of the predictive error picture signal 123 and
the amplitude gain, a significance decision identifi-
cation index and, when significant, the mean value and
the amplitude gain. The output signals 124 of the
adaptive vector quantization encoder are significance
decision identification index, and the mean value of the
predictive error picture signal, the amplitude gain and
the output vector index when significant.
In ~he adaptive vector quantization decoder of
Fig. ~, upon the reception of the output 124 of the
adaptive vector quantization encoder, an output vector
corresponding to the output vector index is read from the
output vector code table 3~ and the amplitude regenerative
circuit 31 and the mean value correction circuit 32
compute a predictive error vector quantization picture
signal when significant. The regenerative vector
register 33 resets the contents to zero when the
significance decision identification index indicates
insignificance and finally gives the predictive error
vector quantization picture sic3llal 125.
As shown in Fig. ll, it is desirable that tlle
inter-frame vector encodinc3 process and the movemellt
3~
compensation process are controlled by the multi-access
frame memory 20, the movement vector detector 4 and the
variable delay circuit 5 so that those processes do not
overlap each other in respect of time.
As described hereinbefore, the movement compensation
inter-frame adaptive vector quantized coded data are the
movement vector, the significance decision identification
index, and the predictive error picture signal mean
value, the amplitude and the output vector index when
significant. These data are subjected to variable-length
encoding in the variable-length encoder 9 of Fig. 6 and
sent out as the movement compensation inter-frame vector
zoded output 127 to the transmission segment. Block size
for executing the block matching of movement compensation
and block size for vector quantization desirably are the
same both in horizontal direction and in vertical direc-
tion or are related by integer multiple. In such a
condition, it is advantageous that the movement vector
and the adaptive vector coded output can be subjected to
variable-length coding together in block to block
correspondence. Furthermore, since the amount of
information produced becomes more correspondent to
movement, coding is facilitated, Still Eurther, the
transmissioll of a fixed amoUIlt of information is possible
~5 througll tlle feedback control oE the signiEicance decision
tllreshold for adaptive vector qUantiZatiOIl.
"
( Another embodiment of the present invention will be
described hereinafter.
This embodiment is a vector quantizer capable o~
highly efficiently encoding picture signals by utilizing
S the correlation between successive picture frames
according to the vector quantization method~
Prior to the concrete description of this
embodiment, the basic principle of this embodiment will
be deseribed.
A device capable of attaining inter-frame encoding
of such a kind has a constitution as shown in Figs. 12,
13 and 14. An example of concrete constitution will be
described hereinafter in connection with the drawings.
Fig. 12 is a block diagram showing an encoder. In
Fig. 12, there are indicated a digitized picture signal
at 201, a raster/block scan converter for blocking the
picture signal sequen~e arrangecl along the direction of
raster scanning into blocks each including a pluralit~
of samples at 202, blocked picture signal sequence at
203, a subtractor at 204, the predictive error signal
sequence of the blocked picture signal at 205, a movement
detection vector quantization at 206, a vector quantiza-
tion coded output at 207, a vector quantization decoder
at 208, vector quantization decoded output, i.e.,
rec3enerative predictive error sic3nal sequellce, at 209,
an adder at 210, the block of rec~enerated picture sigllal
sequence at 211, a frame memory at 212, the block of
- 2j -
regenerative picture signal sequence delayed by one
frame cycle, which also is the block of predictive
signal sequence for predictiny the block o~ the picture
signal sequence 203, at 213, a transrnission buffer at
214, feedback control signal at 215 and encoder output
at 216. Fig. 13 shows an exemplary constitution of the
vector quantization encoder 206 in detail. In Fig. 13,
there are indicated a mean value separation circuit at
217, an ampli~ude normalization circuit at 218, the
inter-frame difference of the block of the picture
signal sequence normalized with respect to amplitude
after mean value has been separated at 219, mean value
calculated by the mean value separation circuit 217 at
220, amplitude calculated by the amplitude normalization
circuit 218 at 221, a movement detecting circuit which
decides, on the basis of the mean value 220 and the
amplitude 221, whether or not the blocked picture signal
sequence being processed presently has made significant
change with respect to the block of the one-frame cycle
preceding picture signal sequence of the same position
at 222, the result of decision of the movement detecting
circuit 222 at 223, code table address counter at 224,
code table index at 225, output vector code table memory
at 226, code table output vector at 227, a distortion
computation circuit at 228, a minimulll distortion
detecting circuit at 229, a minimulll distortion indicatillg
signal at 230 and a tranSmisSioll latch 231.
2(, -
Fig. 14 shows an exemplary constitution of the
vector quantization decoder 2U8 in detail. In Fiy. 14,
there are indicated a reception latch at 232, an
amplitude regeneratiny circuit at 233 and a mean value
S regenerating circuit at 234.
Fig. 15 shows an exemplary constitution of the
decoder. In Fig. 15, indicated at 235 is a reception
~u~fer, at 236 is a block/raster scan converter func-
tioning reciprocally to the raster/block scan converter
202 and at 237 is regenerative picture signal sequence~
The manner of operation of the vector quantizer
will be described hereinafter. First the general action
of the encoder will be described in connection with
Fig. 12.
Basically, the encoder is based on the conception
of the inter-Prame DPCM system. On the frame, the
digitized picture signal sequence 201 is regarded as a
group of samples arranged in a square lattice, however,
input is given in the order of raster scanning. The
raster/block scan converter 202 partitions the picture
signal sequence 201 into blocks as shown in Fig. 16 and
gives output signals corresponding to the blocks,
Suppose that a blocked picture signal sequence 203 in a
frame No. f is expressed by a signal source vector
_f = {Sl, S2, ..., Sk}f. Fig. 16 shows an example where
k = ~. Further, suppose that ~f is the difEerence 205
betweell the signal source vector 203 calculated by the
! subtractor 204 and the block 213 of the predictive signal
sequence, ~f is the block 209 of the reyenerative
dlfferential signal sequence formed by the vector
quantization encoder 206 and the vector quantization
decoder 208, Sf is the block 211 of the regeneration
signal sequence, and Pf is the predictive signal
sequence 213 given by the frame memory 212. Then, the
general action of the encoder shown in Fig. 12 is
expressed by
Ef = Sf - Pf,
f = Ef + Q,
Sf = Pf + ~f = Sf + Q,
Pf = Sf . Z f,
where Q is vector quantization error and z~f is delay of
one-frame cycle caused by the frame memory 212.
Accordingly, Pf is equal to the regenerative signal
sequence of one-frame cycle before, namely, equal to the
generative signal sequence Sf 1 of the block Sf 1 f the
picture signal sequence at the corresponding position in
the frame No. f-l, The vector quantization coded output
207 obtained through the process stated above is the
difference between the signal source vector 203 and the
block 213 of the predictive si~3nal sequence, namely, the
result obtained by data-compressincJ the block 205, Lf,
of the predictive error signal by the vector quantization
encoder 206. The vector qu~ntization coded output 207 is
sent to the transmission buffer 214 and then given to
the transmission channel as the encoder output. The
actions of the vector quantization encoder 206 and the
vector quantization decoder 208 will be described
hereinafter in connection with ~igs. 13 and 14. In the
vector quantization process a block consisting of k
pieces of samples (k: the plural number) is given as an
input vector in a k-dimensional signal space output
vectors having minimum distortion with respect to the
input vectors given sequentially are selected among a set
of output vectors prepared beforehand on the basis of
the probability distribution density of the input vector
the distortion with respect to the input vector will
generally be minimized and the index attached to the
lS selected output vector is given as a quantized output.
In decoding it is only to read an output vector corres-
ponding to the index from the same set provided also in
the decoder. The input vector given is the block
~f ~{~ ~2 ~ ~k}f of the predictive error signal
sequence 205 A mean value 220 ~ calculated by the use
of formula
-1 k
j-l j
is subtracted from the block 205 ~f~ and then the
remainder of the block 205 is norlllalized witll respect to
amplitude a calculated by the use of formul~
1~ 37
j-l i
by the amplitude normalization circuit 218 to give a
mean value separation normalized input vector
x = {xl, x2, .,., xk} 219. Tha-t is,
X~ a (j = 1, 2, ............... , k).
In addition to the above-mentioned formula for calcu-
lating amplitude, the following formulas, for instance,
may be employed,
a = ~K~l ~ 2
j-l ~
a = max I Ej - U I
The mean value separation normalization process
distribute the input vector random within a limited
range in the k-dimensional signal space, which improves
the efficiency of vector quantization. This process
requires the preparation of the set of output vector on
the basis of the input vector distribution processed
through the mean value separation normalization and the
process reverse to tlle mean value separation normaliza-
tion including amplitude regeneration and mean value
regeneration, after reading the output vector in the
decodin~ process. Naturally, vector quantization witlloutthis process also is possible. Mean value separation
normalizing output vector prepared on the basis of the
probability distribution density of the mean value
separation normalizing input vector so that the distor-
tion from the mean value geparation normalizin~ input
vector is generally minimized is stored in the code
S table memory 226.
When the mean value separation normalizing input
vector 219 x is given, the code table address counter
224 sequentially gives indices of vectors stored in the
code table memory 226, i.e., code table addresses, and
reads mean value separation normalizing output vectors
-i {Yil' Yi2' ~-~ Yik} (i: indices) from the code
table memory 226. The distortion computation circuit 228
computes the distortion of the mean value separation
normalizing input vector x from the mean value separation
normalizing output vectors 227 Yi. Sevqral distortion
computation methods as shown bel~w are available. When
the distortion is expressed by dtx, Yi),
d(Xr Yi) jl ¦ j Yij
~ i Yij l
d(x, Yi) = max ¦xj - yijl-
The minimum distortion detecting circuit 229 calculates
d(x, Yi) sec]uelltially and gives a strobing signal 230
wllen a value smaller than the past minimum distortion is
obtained. ~t the same time, the latch 231 stores the
index 225. At a stage where the code table address
counter 224 has given all the indices, the index i of a
mean value separation normalizing output vector which
has the minimum distortion with respect to the rnean value
separation normalizing input vector is stored in the
latch 231. This index, the mean value 220 (~) and the
amplitude 221 (a) are the vector quantization coded
outputs, however, the data is compressed further by
utilizing the correlation between successive picture
frames. Since the input vectors are blocked predictive
error signaLs, the center of the distribution thereof is
a zero vector. Therefore, the amount of data is reduced
greatly b~ regarding the input vectors distributed in
the vicinity of the zero vector as the zero vector and
without sending our indices, the mean value and the
amplitude. The movement detecting circuit 222 receives
the mean value 220 ~ and the amplitude 221 ~ and decides
whether or not the blocks of the predictive error signal
sequence can be regarded as ~ero vectors, namely, whether
or not any significant change (movement) as compared
with the one-frame cycle preceding frame has occurred in
the present block, for example, according to the
following criterion:
when l~ < To and ~ < T~, significant change has not
5 occurred, and
when ~ > T~ and o > To~ sicJni~icant change occurred,
, ~, .
3'~
where T~ is a threshold. Accordingly, the latch 231
gives only a signal indicating "no rnovement" when a code
indicating "no movernent" i5 given as the result o~
movement detection and gives the index 225, the mean
value 220 and the amplitude 221 in addition to a signal
indicating "movement~ when a code indicating "movement"
is given, as a vector quantization coded output 207.
The transmission ~uffer 214 monitors the amount of
information transmitted controls the threshold T~ on the
basis of the feedback control signal 215. Thus the
amount of information to be -transmitted is controlled.
In the vector quantization decoder 203, upon the
reception of the signal indicating "movement" included in
the vector quantization coded output 207 by the reception
latch 232, mean value separation normalizing output
vectors 227 Yi are read out according to the index i
from the code table memory 236 and are multiplied by the
amplitude 221 at the amplitude regenerating circuit 233.
At the mean value regenerating circuit 234, the mean
value 220 is added to the multiplied mean value
separation normalizing output vectors to give output
vectors, namely, a regenerative predictive error signal
sequence 209 ~f. That is,
~:~ = a Yij -t 11, (j - 1, 2, ..., k) .
When the signal indicating "no movement" is given by the
transmission latch, the output signals oE the transmission
1.3 ~
latch 231 for the rnean value 220 and the amplitude 221
are zero and the output vector of the mean value
regenerating circuit 234 is a zero vector.
The actions of the decoder will he described
hereinafter in connection with Fiy. 15.
The reception buf~er 23~ receives the output 216 oE
the encoder and decodes the vector quan~ization coded
output signal 207. The vector quantization decoder 208
decodes, as mentioned above, the output vectors, i.e.,
the predictive error signal sequence 209 Ef and the
adder 210 and the frame memory 212 regenerate the block
211 -f of the regenerative picture signal through a
process expressed by
-f
Sf = Pf ~ Ef = Sf ~ Q, and Pf = Sf ~ Z
where Q is vector quantization error and Z f is delay of
one-frame cycle. The block/raster converter 236 scans
blocked regenerative picture signal sequence 211 Sf along
the raster scanning direction to convert the same into a
regenerative picture signal sequence 237,
Now, the embodiment constituted on the basis of the
above-mentioned principle will be described hereinafter
in connection witll the drawings.
Fig. 17 shows an exemplary constitution of the
embodilllellt of an encoder according to tne presellt
invention, In Fig. 17, indicated at 201 is a digitized
picture signal, at 202 is a raster/block scan converter,
-- :3~ -
~.2~ %~
at 203 is a blocked picture signal sequence, at 204 is a
subtractor, at 205 is the predictive error signal
sequence of the blocked picture siynal at 238 is a
movement detection vector quantization encoder, at 207
S is a vector quantization coded output, at 239 is vector
quantization decoder, at 240 is a vector quan-tization
decoded output, at 210 is an adder, at 241 are blocks of
regenerated picture signal sequence, at 212 is a frame
memory, at 242 are blocks of a regenerated picture signal
sequence delayed by one-frame cycle, at 243 is a low-pass
filter, at 244 are blocks given by filtering the blocks
242 of the delayed regenerative picture signal sequence
through the low-pass filter 243 and are also blocks of a
predictive signal sequence for predicting the blocks 203
of the picture signal sequence, at 245 is a switch for
interrupting or connecting a path for supplying the
blocks 244 of the predictive signal sequence to the
adder 210, at 246 is a signal which controls the switch
245 according to the result of movement detection, at
214 is a transmission buffer, at 215 is a feedback control
signal and at 216 is the output of the encoder.
Fig. 18 shows the detail of an exemplary constitu--
tion of the movement detection vector quantizatioll
encoder 238. In Fig. 18, indicated at 247 is a parallel
~5 meall value separation circuit, at 248 is a paralleL
amplitude normalizatioll circuit, at 249 is the mean value
of the blocks 203 of the picture signal sequence, at 250
is the mean value of the blocks 205 of the predictive
error signal sequence, at 251 is the intra-block
amplitude of the blocks 203 of the picture signal
sequence, at 252 is the intra-block amplitude of the
blocks 205 of the predictive error signal sequence, at
253 is a movement detection circuit, at 254 is either
the mean value 249 or the mean value 250 ehosen by the
movement detection eireuit 253, at 255 is either the
intra-bloek amplitude 251 or the intra-bloek amplitude
252, at 246 is a signal eorresponding to the result of
deeision of the movement deteetion eireuit 253, at 256
is a switeh for ehanging over between the bloeks of the
pieture signal sequenee through mean value separation
normalization and the bloeks o~ the predietive error
signal sequenee aeeording to the result 246 of deeision
of the movement deteetion eireuit 253, at 257 are bloeks
of the pieture signal sequenee after mean value
separation normalization or the bloeks of the predietive
error signal sequenee, seleeted by the switeh 256, at
258 is a eode table address eounter, at 259 is a eode
table index, at 260 is an output veetor eode table memory,
at 228 is a distortion computation cireuit, at 229 is a
minimum distortion detection circuit, at 230 is a signal
indicating the minimum distortion, at 261 is a code table
output vector and at 262 is a translllissioll latcll.
Fig. 19 shows the detail o~ an exemplary constitution
of th~ vector quantization decoder 239. In Fig. 19,
-3G -
'7
indicated at 263 is a reception latch, at 233 is an
amplitude regenerating circuit and at 234 is a mean
value regeneratiny circuit.
Fig. 20 shows an example of the constitution of the
decoder included in this embodiment. In Fig. 20,
indicated at 235 is a reception buffer, at 236 is a
block/raster scan converter and at 237 is a regenerative
picture signal sequence.
First, the general operat.ion of the encoder will be
described in connection with Fig. 17. Basically, this
encoder is based on the conception of inter-frame DPCM.
A digitized picture signal sequence 201 is a seqùence of
samples given sequentially along raster scanning direction.
The raster/block scan converter 202 partitions the
- 15 picture signal sequence into blocks and scans and
converts the picture signal sequence sequentially in
b1ocks. Suppose that a blocked picture signal sequence
203 in a. frame No. f is expressed by a signal source
-f {Slt S2, .., Sk}f. Then, the basic
operation of the encoder of Fig. 17, namely, tSle
operation of the encoder when the switch 245 is closed
and tSle blocks 244 of the predictive signal sequence is
given to the adder 210, is expressed by the following
formulas.
c = S - P
-f -f -f
-f ~.f ~ Q
Sf = Pf + ~f = S
Pf = F ~ (Sf . Z f)
where ~f is the difference 205 between a siynal source
vector 203 calculated by the subtractor 204 and the
block 244 of the predictive signal sequence, ~f is the
block 20~ of the regenerative differential signal
sequence formed by the vector quantization encoder 238
and the vector quantization decoder 239, S~ is the block
241 of the regenerative picture signal sequence, Pf is
the predictive signal sequence 244, Q is vector
quantization error, Z f is delay of one-frame cycle
caused by the frame memory 212 and F is the elimination
of high frequencies by the low-pass filter 243. There-
fore, Pf is a signal resulting from the elimination of
high frequencies from the generative signal sequence
Sf 1 of the blocks Sf 1 of the picture signal sequence
at the same position in the frame one-frame cycle before
the present frame, i.e., the frame No. f-l. The vector
quantization error are such as granular noises appearing
in the high-frequency band. Therefore, the low-pass
fi.lter 243 prevents the accumulation of the quantization
error and always acts so that high-quality pictures are
obtained, In the process described above, the switch
245 is closed and the block 244 of the predictive signal
sequence is applied to the adder 210. Ilowever, according
to the operation in this process, the power of the block
3~
205 of the preclictive error signal sequence becomes very
large when the picture changes greatly, which increases
the vector quantization error.
To obviate such increase in vector quantization
error, this embodiment is designed to subject the block
Sf of the picture signal sequence to vector quantization
encoding as it is instead of the block f of the
predictive error signal sequence, when the picture changes
greatly, namely, when the power of the predictive error
signal increases. To carry out this process, the control
signal 246 opens the switch 245, the adder 210 allows
substantially the vector quantization decoded output 240
to pass through and to become ~he block 241 of the
regenerative picture signal sequence as it is. The
movement detection vector qUarltiZatiOn encoder 238 makes
the decision of changeover and the changeover operation.
These operations will be described in detail afterward.
The vector quantization coded output 207 is sent to the
transmission buffer 214 and is sent out to the trans-
mission channel as the encoder output 216.
The actions of the vector quantization encoder 238and the vector quantization decoder 239 will be described
hereinafter in connection Witll Figs. 18 and 19.
The block 203 Sf of the yicture siynal sequence and
the block 205 Pf of the predictive error sigllal sequence
are given as input signals. 'l'he parallel mean value
separation circuit 247 subtracts the mean value 249 l
and IIE operated by the use of the following formulas
-- 3S --
-l k
~s K j~ Sj and
~E ~ K ~ E .
j=l ~
from the blocks Sf and Pf respectively, Furthermore,
those blocks are normalized by the parallel amplitude
normalizin~ circuit 248 with respect to the amplitudes
s aE op~rated by the following formulas:
s K j~l ISi - ~s¦ and
a - K_1 ~ ¦ E ~ I
j=l
These processes form mean value separation normalized
vectors Xs and XE That is/
Xsj = (Sj ~ ~s)/as ( s {xsl, xs2, ..., xsk}) and
X j = (E j -- ~ )/a ( E {XE1~ XE2~ xEk}) -
Ampli~ude calculating methods other than those described
above are available. Those alternative methods are, for
instance,
a S = [ K ~ l s j - ~-~ s ¦ ~ ~ a ~ = [ K j ~ ¦ ~ ¦ ]
S ~ s I ' a~ m~x I E j IJE I
The mean value separation normalizing process distributes
the input vectors random withill a limited range in a
k-dimensional signal space, wllicll improves vector
( )
'7
quantization efficienc~. Plthough two sets of blocks are
given as input vectors in this process, there is a
process to subject the bloc]cs of the predictive error
signal sequence to vector quantization, basically, to
utilize the correlation between successive pictures.
Furthermore, to compress the data, the blocks of the
predictive error signal sequence are regarded as zero
vectors when those blocks are nearly zero. That is, it
is decided that no significant change (movement) has
occurred from the one-frame preceding frame. This
decision is made also by the movement detector 253. The
decision is made, for example, by comparing ~ and o
with a threshold T~ that
movement has occurred (~f~ O) when ~ < T~ and
15 CJ < T~ and
movement has not occurred (~f~ O) when ~ > T~ or
a~ > T~.
The threshold T~ is controlled by the feedback control
signal 215 given by the transmission buffer 214 50 that
the amount of information to be transmitted is fixed.
Furthermore, the movement detector 253 has, in addition
to the above-mentioned function, a function to made
decision for chancling over the input vectors to the
blocks Sf of the picture signal sequence as described
~5 above wllen tlle movelllellt is very larcJe. This decision is
made on an aSsumptioll that tlle movement has been detectecl
througll the above-melltioned process, on the basis of the
followin<3 conditions
,~ I _
1 ~f is selected as input vector when aE < as and
Sf is selected as input vector when rJ ~ aS.
This changeover process is based on a conception that aS
and a represent approximately the respective powers of
those signals. This is because the smaller the power of
signal for vector quantization. the smaller is the vector
quantization error of the regenerated signal. The
movement detection circuit 253 gives the result of the
decision as the signal 246 and the changeover switch 256
connects either the mean value separation normalized
input vector XS or x to the next distortion computing
circuit 228 according to the signal 246, Suppose that
the mean value separation normalized input vector 257
thus selected is expressed by x = {xl, x2, ..., Xk}.
The movement detection circuit 253 gives, according to
the result of the decision, the mean value (~) 254 and
the amplitude 255 of the selected vector. Mean value
separation normalized output vectors prepared on the
basis of the probability distribution density of the
mean value separation normalized input vectors so that
the distortion thereof from the mean value separation
normalized input vectors is minimized generally are
stored beforehand in the code table memory 260 at
different addresses corresponding to the distributions
of Sf and ~f.
Whell the mean value separation normali~ed input
vector 257 is given, the code table address counter 258
sequentially gives the indices of the corresponding
vector groups~ i.e., code ta~le addresses, according to
the signal 246 indicating the result of rnovement detec-
tion and reads mean value separation normalized output
i Yil' Yi2~ Yik} (i: index) 261 from
the code table memory 260. The index i includes not
only the information indicating the code table address
but also the information indicating whether the vector
indicated by the index i is for S~ or for Ef. The
distortion computing circuit 228 computes the distortion
of-the mean value separation normalized inpu.t vec-~or 257
_ from the mean value separation normalized output vector
261 Yi. Several computation processes are available.
For example, the followiny processes are available.
5 When the distortion is expressed by d(x, Yi),
k
d(_, Yi) = j~l lXi Yijl
d(x, Yi) j~l I i ~ijl '
d(x, Yi) = max ¦xj - Y~
The minimum distortion detection circuit 229 ~ives the
strobing signal 230 when the distortions d(x, Yi)
calculated sequentially are smaller than the past min.imum
distortion. ~t a stac~e where the code table address
counter 258 has given all the addresses of the vectors to
be compared, tlle index i of a mean value separation
normalized output vector which gives the minimum
distortion for x is stored in the latch 262, The latch
262 gives, according to the output siynal 246 of the
movement detection ci.rcuit 253, a siynal indicating "no
movement" when the signal 246 indicates "no movement" and
the index, the mean value 254 and the amplitude 255 in
addition to a signal indicating "movement" as the vector
quantization encoded output 207 when the signal 246
indicates "movement". The latch 263 of khe vector
quantization decoder 239 receives the vector quantization
coded output 207, When the vector quantization coded
output 207 indicates "movement", the latch 263 decides
from the index i which one of Sf and ~f is vector- -
quantized and gives a signal equivalent to the output
246 of the movement detection circuit. At the same time,
the latch reads, according to the index 259, the mean
value separation normalized output vector 261 Yi from the
code table memory 260. The amplitude regenerating circuit
233 multiplies the output vector Yi by the amplitude 255
and the mean value regenerating circuit 234 adds the mean
value 254 to regenerate the output vector. This process
is expressed by
Fj ~ Yi; + 1l (a = aF~ lJ
Sj = a Yij + ~ J (Js~ 1l 1S
Whell the latch 263 receives the sigtlal indicating "no
movement", the latch 263 gives a code for "no movement~'
'7
as the signal 246 and zero signals for the rnean val~e
254 and the amplitude 255, Then, the output vector 40
becomes a zero vector.
The operation of the decoder of this ernbodiment
will be described hereinafter in connection ~ith Fig. Z0.
The reception buffer 235 receives the encoder output
216 and decode the vector quantization encoder output
signal 207. The vector quantization decoder 239 decodes,
as mentioned above, the output vector 240, The switch
245 is closed when the signal 246 indicates "movement"
or "no vement" and the coded vector is ~f/ and *he
block 241 Sf of the regenerative picture signal sequence
by the adder 210 and the frame memory 212, in the manner
as expressed by the following formulas:
Sf = Pf + E~ = S~ + Q,
Pf = F (Sf Z f)
where Q is vector quantization error, Z f is delay of
one-frame cycle caused by the frame memory 212 and F is
the elimination of high-frequency band by the low-pass
filter 243. I~hen the signal 246 indicates "movement" and
that Sf is encoded, the switch 245 is opened to let the
decoded Sf through the adder 210. The blocks/raster
converter 236 scans the blocks 291 S~ o~ the blocked
regenerative picture s.ign~l sequence aloll9 tlle raster
scanning direction to convert the regenerative picture
signal sequence into the regenerated picture signal
~S
'7
sequence 237. In this embodiment, the respective
amplitudes of tf and Sf are compared to change over the
input vector to be coded between tf and Sft however, the
input vector may be changed over bet~een tf and Sf by
comparing the amplitude of tf with that of Pf~ In the
latter case, the input vector i5
tf when a < ~p, or Sf when a ~ ap
where ~p is the amplitude of Pf.
Naturally, a tree-search vector quantizer may be
employed instead of the full-search vector quantizer
employed herein. Furthermore, this invention is
applicable to shortening the code length, namely, to
preventing the increase of the amount of information, by
limiting the code table address to be searched, when
sudden movement is detected.
A third embodiment of the present invention will be
described hereinaf~er. Prior to the concrete description
of the embodiment, the principle of vector quantization
employed by this embodiment will be explained briefly.
Suppose that k sets of input signal sequences are
collectively expressed by an input vector _ = [xl, x2,
..., xk] and the set of N output vector points
Yi lYil~ Yi2, --, Yikl of k-dimensional Euclidean
space ~ (x ~ ~ ) is Y = [Yl~ Y2~ -Nl If eacll
~5 partition of ~k witll the output vector Yi as a repre-
sentative E~int, for example, the center of ~ravity, is
- ~6 -
'7
Rl, R2, ..., RN, vector quantization is a mappiny of R
into Y. The encoder of a vector quantizer defines an
output vector -i lying at the shortest distance from an
input vector, namely, an output vector with a minimum
distortion from the input vector, as follo~s and makes a
search for the output vector Yi.
If d(x, ~i) < d(x, ~j) for all J, x ~ Ri, that is,
x ~ ~i
where d(x~ Yi) is the distance (distortion) between the
input vector and the output vector. The index i of the
output vector is the output of the encoder. The decoder
reads Yi from a table storing Y beforehand and gives Yi
as an output. Thus, since the vector quantizer transmits
or records the output i of the encoder, the coding
efficiency thereof is very high. The set Y of the output
vector Yi can be obtained by clustering (repetition of the
selection of representative point and the partition of
the signal space until the total sum of distortions is
minimized~ using a picture signal sequence serving as a
training model. Exemplary methods of calculating
d(x, ~i) are as follows.
k )2
d(x, ~ El(xj Yij (squared distortion)
max
d(x, y ) = min ¦x - y ¦ (maximum element
] distortion)
~3 d(~ xj - yij¦ (absolute distortion)
- 17 -
"7
A conventiona] vector ~uantizer will be described
with reference to a concrete constitution thereof.
Fig. 21 shows an example of an encoder. In this example,
absolute distortion of the method ~ is used to define
d(_, -i) In Fig. 21, indicated at 301 is an input
vector, at 302 is an inp~lt vector register, at 303 is a
~ode table address counter, at 304 is a code table
memory, at 305 is an output vector register, at 306 is a
parallel subtractor, at 307 is a parallel magnitude
arithmetic unit, at 308 is a magnitude distortion
arithmetic unit (adder), at 309 is a minimum distortion
vector detector, at 310 is an index signal, at 311 is a
latch and at 312 is an encoder output signal. Fig. 22
shows an example of a decoder. In Fig. 22, indicated at
313 is a latch and at 314 is an output vector.
The actions o~ this encoder and this decoder will
be described hereinafter. A set of k picture signal
sequences are blocked to provide an input vector
x = [xl, x2, ..., Xk]. First the register 302 latches
the input vector. The code table address counter 303
reads output vec-tors Yi sequentially from the output
vector code table memory 304. The output vectors read
out is latched by the output vector register 305. The
magnitude distortion arithmetic unit 308 receives x and
-i from the parallel subtractor 306 and tlle parallel
magnitude arithmetic Ullit 307 and calculates the
distortion di by the use of formula
k
Then, the minimum distortion detector 309 detects
the minimum value among the distortions di between Yi
and x which are read out sequentially. The minimum
S distortion is given by
d = min di.
The vector that gives khe minimum distortion is the
vector quantization output of the vector x. Upon the
detection of the minimum distortion vector, the minimum
distortion detector 309 gives a strobin~ signal to the
lat~h 311 and the latch 311 receives the index signal 310
indicating the address of the vector. The latch 311
gives the index as an output signal 312 of the encoder.
In the decoder, the latch 313 receives the encoder
output signal 312. The index is decoded, an output
vector Yi is read from the code table 304 and latched by
the output vector register 305 and an output vector 314
is given.
A fourth embodiment of the present invention,
constituted on the basis of the above-mentioned principle
will be described concretely hereillafter.
In this embodilllent, the respective sizes oE the
in~ut vector regi5ter 302, the output vector rec~ister 305,
the code table memory 304 and the parallel subtractor 304
49
are reduced to half by the use of subsamples, latches
and adders are added to the parallel rnagnitude arithmetic
unit 307 and the magnitude arithmetic unit 308 and those
components are connected in a cascade connection of the
pipeline system to reduce the circuit scale of the
encoder and to solve the problems of realtime processing.
Fig. 23 shows the correspondent relation between
the input and output vectors of the above-mentioned basic
vector quantizer and the input and output vectors of the
present vector quantizer. As shown in Fig. 23, the
encoder of the present vector quantizer uses input
subvectors obtained by subsampling input vectors and
output subvectors obtained by subsampling the output
vectors obtained by clustering using picture signal
sequence.
The constitution and the operation of this
embodiment of a vector quantizer according to the
present invention will be described hereinafter. Fig.
24 shows an exemplary constitution of the encoder of the
present vector quantizer. In Fig. 24, indicated at 303
is a code table address counter, at 306 is a parallel
subtractor, at 307 is a parallel magnitude arithmetic
unit, at 310 is an index signal, at 311 is a latch, at
312 is an encoder output signal, at 315 is an input
~5 subvector, at 316 is an input subvector regi~ter, at 317
is all output subvector code table rnemory, at 318 is an
output subvector register, at 319 is a latch, at 320 is
,()
a parallel adder, at 321 is delay circuit for
compensating the delay due to the pipc~line connection of
the components and at 322 is a minirnum distortion
detector.
S The operation of this vector quantizer will be
described hereinafter.
A set of N picture signal sequences are sampled and
then blocked to obtain an input subvector x' = {xi', x2~,
..., XN']. This input subvector 315 is first latched by
the register 316. The code ~able address counter 303
reads output subvectors Yi~ sequentially from the output
subvector code table memory 317 and let the register 318
latch the output subvectors Yil- The parallel subtractor
306 obtains N differences between the input subvector
latched by the register 316 and the output subvectors
latched by the register 318.
~323) ... dij = xi Yii (j = 1, 2, ..., N~,
Then, the outputs 323 are la~ched by the register 319
and are converted into magnitudes ¦dij¦ (j = 1, 2,
N) 324 by the parallel magnitude arithmetic unit 307.
At this time, the inputs Yil , Yi2 ~ ~- , YiN
parallel subtractor are updated to Y (i-~l)l' Y (i~1)2'
--, Y'(i+l)N- 'l'he magnitudes Idijl (j = 1, 2, ..., N)
324 are then latched by the register 319 and are added
sequelltially every two inputs. That is, the adder 320
reduces the number of output signals to the half the
,3~7
number of the input signals This process is repeated
successively until the number of the output of the adder
320 is reduced to one. q~he final output 3~5 of the
adder 320 is
1`~
325 ...... dl = ~l ¦xj Yij I
The minimum distortion detector compares the present
value d and the succeeding input value di and stores the
smaller value as d. The minimum distortion detector
repeats this comparison until the last input to obtain a
minimum distortion d = min di. The vector that gives the
minimum distortion is the vector quantization output for
the vector x. When the minimum distortion vector is
detected, a strobing signal is given to the latch 211
and an index signal 310 indicating the address of the
vector is taken. The latch 311 gives the index as an
encoder output signal 312, The same decoder as shown in
Fig. 22 is employed. In the decoder, the latch 313
receives the encoder output signal 312, and the index is
decoded, an output vector Yil is read from the code
table 314 consisting of output vector sets obtained by
clustering using picture signal sequences and the output
vector Yi~ read is latched by the output vector register
305 and given as an output vector 314. A1though the
input and the output vectors are obtailled by subsamplin~
Witll N = 8 and k = 16 in this embodilllent, naturally, the
values of N and k and the input and tlte output subvectors
can optionally be selected
The constitution of the subvector quantizer of this
embodiment as described hereinbefore reduces the circuit
scale of the encoder and the pipeline connection of the
components for the successive parallel operation of the
minimum distortion detector facilitates realtime
processing.
The constitution and the operation of the fourth
embodimen~ of the present invention will be described
hereinafter. Fig. 25 shows an exemplary constitution of
this embodiment of a movement compensatiOn vector
quantizer. In Fig. 2S, indicated at 415 is a movement
vector quantizer, at 417 is a subtractor to obtain the
differential signal 422 between the output signal 421
and the input signal 401 of the movement vector quantizer,
at 419 is a differential vector quantizer to vector-
quantize the differential signal 422, at 420 is an adder
to add the output signal 422 of the differential vector
quantizer and the output signal 421 of the movement
vector quantizer, at 426 is a differential vector index
signal, at 418 is a multiplexer to generate an encoder
output 427 by multiplying the code train of the movement
vector index signal by the code train of the differential
vector index signal and at 416 is a frame memory to store
the output signal of the adder 420 c3iven in the processinc3
of the precedillg frame.
The operation of this movement compensation vector
quantizer ~ill be described hereinafter. The movement
3'7
vector quantizer 415 executes the movement comPensation
of the input signal 401 on the basis of the picture
information of the preceding frame, i.e., the output
signal 424 of the frame memory 416. The constitution
and the action of this movement vector quantizer will be
described hereunder.
Fig. 26 shows an e~emplary constitution of the
movement vector quantizer, In Fig. 26, indicated at 428
is a dynamic output vector code table, at 421 is an
output rnovement vector havlng the minimum error with
respect to the pattern of a block to be coded and at 425
is the movement vector index for the output vector
having the minimum error. The movement vector quantizer
processes dynamic output vector code table produced
adaptively from the picture signal of the preceding frarne
as an output vector set through the same distortion
calculation process as that of the conventional vector
quantizer. The dynamic output vector code table is
produced adaptively at the processing of each block in
the manner as described hereunder.
As shown in Fig. 28, in vector-quantizing the block
No, M of a frame No, N, twenty-five blocks are cut out
from the preceding frame, i.e., a frame No. N-l, so that
the center of the block is located as shown in Fig. 27
with a pOillt in the frame No. N-l coincidillg with the
center of the block, i.e., a point X in Fig 27, as the
origin. These blocks are indexed as a set of movement
output vectors and registered in the dynamic output
vector code table. The arrangement as shown in Fig. 27
can optically be selected. Furthermore, the rnovement
vector set may be produced by using the blocks cut out
from the present frame. The movement vector quantizer
searches the vectors registered in the dynamic output
vector code table for a vector which provides the
minimum distortion. In the example of Fig. 28, when it
is decided that ~he pattern of the block No, M of the
frame No. N is the most analogous ~lith the pattern of
the block No. L of the frame No. N-l, the direction of
the movement vector in the arrangement of Fig. 27 is
(2, 1) with respect to the origin. That is, movement
detection has been executed for the movement of the
block No. L of the frame No. N-l to the position of the
block No. M of the frame No. N. The movement vector
quantizer executes an operation to shift the block No. L
to the origin (point X) in the frame No. N-l. The
movement vector quantizer gives the index 426 of a
vector that minimizes thedistortion to the multiplexer
418 and gives a movement output vector that minimizes
the distortion as a quantized picture signal 421 to the
subtractor 417.
Referring to Fig. 25, the subtractor 417 calculates
the difference between the picture signal 421 quantized
by the movement vector quantizer and the original
picture signal 401 and gives a differential signal 422.
- 55 -
~2~
This differential signal 422 i5 a signal e~iminated of
~the redundar,t component on the basis of the correlation
of the picture signal with the picture signal of the
preceding frame. The differential vector quantizer 419
S receives the differential signal 422 and executes the
same distortion calculation as that of the conventional
vector quantizer with a fixed differential output vector
code table prepared beforehand through clustering
training, as shown in Fig. 29, as a differential output
vector set. Finally, the differential vector quantizer
419 gives the index 426 of a differential output vector
that minimizes the distortion from the input vector to
the multiplexer 418 and gives the corresponding
differential output vector to the adder 420 as a
quantized differential signal 423.
The adder 420 of Fig, 25 calculates the sum of the
picture signal 421 quantized by the movement vector
quantizer and the differential signal 423 quantized by
the differential vector quantizer and gives the result
as a regenerative picture signal to the frame memory 416.
The frame memory executes variable delaying. The output
signal 424 of the frame memory 416 is used as information
for the movement compensation of the next frarne. The
multiplexer 418 multiplies the code train of the
movemerlt vector index 425 by the code train (word) of
the di~ferential vector index 426 and gives a code train
427 as an encoder output signal.
- 5() -
'7
In the decoder, the latch 413 receives the encoder
output signal 427 and the demultiplexer 430 divides the
code train into two parts and regenerates Iche rnovement
vector index 425 and the differential vector index 42G.
5 A differential output vector correspondiny to the
differential vector index 426 is read from the
differential output vector code table 429 to regenerate
the quantized differential signal 423. A movement
output vector corresponding to the movement vector index
lG 425 is read from the dynamic output vector code table
428 and the picture signal 421 quantized by 'che movement
vector quantizer is regenerated. For this purpose, the
same dynamic output vector coder table 428 and the
differential vector code table 429 as those used in the
15 encoder are used. The adder 420 calculates the sum of
the regenerated differential signal 423 and the picture
signal 421 ~o decode the output picture signal 424.
This output picture signal 424 is stored in the frame
memory 416 to be used as information for the decoding
20 processing of the next frame.
When the movement vector quantizer thus constituted
according to the present invention is applied to encoding
an animated cartoon, in which quite analogous frames are
transmitted successively, since a block similar to the
25 picture elemet)t pattern of a block to be encoded is
located in the neighborllood of the corresponding
position in the preceding ~rame, a movement output
vector consisting of those blocks is produced for every
processing of each frarne and redundancy hased on the
correlation between frames is eliminated by the use of
the movement output vector quantizer~ ~ccordingly, the
contents of the dynamic output vector code table are
updated for evexy frame and the movement vector
quantization error signal is quantized through multi-
stage vector quantization, and thereby efficient coding
is attained.
A fifth embodiment of the present invention will
be described hereinafter,
Fig. 31 shows the constitution of ~his embodiment.
In Fig. 31, indicated at 520 is a dynamic vector
quantization encoder, at 521 is a subtractor, at 522 is
a differential vector quantization encoder, at 523 is
an adder, at 524 is an encoded frame memory and at 525
is a variable-length encoder. This embodiment of the
vector quantizer according to the present invention is
constituted of a multistage connection of a dynamic
vector quantization encoder for encoding initial
movement vectors and a secondary differential vector
quantizer for vector-quantizing the differential signal
bet~een the initial movement vector encoded signal and
the present input signal.
~5 First the principle o~ movelllellt vector encodlnc3 in
the initial dynamic vector quanti~ation will be
described
_ 58 _
~L~fl~3'7
The sampliny signal sequence of a picture signal is
obtained by scanning two-dimensionally arranged picture
elements. ThereEore, as sho~n in Fig. 32, ~"hen an
object A in the preceding frame moves during one-frame
S scanning cycle and becomes an object B in the present
frame, the blocked picture signal sequence L of the
preceding frame is identical with the blocked picture
signal sequence M of the present frame. Suppose that
the horizontal and the vertical coordina~es of the
two-dimensionally arranged picture elements are given
by (m, n) and the displacement of the block M of the
present frame from the block L of the preceding frame i5
given by a movement vector r = (u, v). Then, the
relation between the picture signals of the block L and
lS the block M is given, as shown in Fig. 33, by X(m, n) -
Z f = X(m+u, n+v), where X(m, n) is the picturP signalat each position of the picture element (m and n are
integers) and Z f is delay corresponding to one-frame
cycle. Thus, in vector-quantizing the block ~1 of the
picture signal sequences of the present frame, an output
vector minimizing the distortion is obtained by the
block L of the preceding frame, which block L is apart
from the block ~ by the movement vector r = (u, v).
That is, in vector-quantizinq an animated picture signal,
it is more eEficient, as lonc3 as the pict-lre oE the sallle
o~ject is in the preceding frame, to use the two~
dimensional displacement of the block of the picture
- 5'~ -
;3'7
signal sequences in the preceding fra~e, narnely, to use
neighborhood blocks which are apart from the present
block by the movemen~ vector r as a set of output vectors
before performing encoding by the use of a set of output
vectors ob-tained by clustering input signal sequences.
This process is defined as dynamic vector quantization
Qd as follows. Let x denote a k-dimensional input vector
formed by blocking every k picture input signal
sequences of the present frame, ~ denote a k-dimentional
output vector formed by similarly blocking picture input
signal sequences in the preceding frame, which block is
apart from the block of the present frame by rg, and rg
denote a quantized movement vector formed by selecting
two-dimensional displacements at random. A set of P
quantized movement vectors _g is given by rP = lrl, r~,
..., rp}, An index set of the movement vector _g is
given by G = {1, 2, ,.., P}. Then, dynamic vector
quantization Qd is expressed by a cascaded connection
of coding Cd and decoding Dd:
Qd(x) = Yg if d(x, ~g) ~ d(x, ~j) for all j
Cd : x -i g
Dd : g ~ ~g
Qd = Dd Cd.
Tlle clistortiol- d(x, ~g) in a k-dimensional space is
expressed in Eucli.dean norm:
- G0 -
3'~
d(x, ~ (Xj - y j)Z
where xj and y j are the No. j dimerlsions of x and ~,3
respectively.
Fig. 34 shows a plot of the horizontal probability
distribution P(u, o) of min d(x, ~ ), namely, the
occurrence probability distribution P(r) - P(u, v) of a
movement vector of minimum distortion over the entire
area of several frames. Accordingly, the arrangement
of a quantized movement vector r is assumed to be that
of Fig. 35. In a dynamic vector quantization process
according to the present invention, a set r of P
movement vectors rg is obtained through the clusteriny
training of actual picture signal sequences so that the
total sum of dis~ortions d(x, ~ ) will be minimized, by
the use of the input vector x of the present frame and
the output vectors _ = x(r) Z f, which is separated
by a distance r, of the preceding frame among picture
input sequences over the entire areas of several frames.
The initial dynamic vector quantizer maps the input
vector x of the present frame into one of the sets of
dynamic output vectors y , on the basis of the set rg of
optimal movement vectors obtained through the above-
mentioned procedure. Furthermore, in the case of
dynamic vector clualltization, as in the case of scene
chanc3e, sometimes no appropriate dynamic output vector
is found in the preceding frame. This problem is solved
by providing a set of a plurality of mean value vectors
~h {Yhl/ Yh2~ Yhk~ (Yhk Yhi ii
The dynamic vector quantization signal x = _~ or
~h is subtracted from the input vector x of the present
frame to give a differential input vector E, which i5
vector-quantized by the next differential vector
quantizer to give a differential output vector ~. The
differential vector-quantized signal E and the dynamic
vector-quantized signal x are added together to give a
dynamic multistage vector-quantized .signal x. This x
is stored in a frame memory and delayed by one-frame
cycle to use the same as a set of dynamic output vectors
in dynamic vector quantization.
The above-mentioned actions will be described in
connection with Fig. 31.
Let x denote the input vector 501 of the present
frame, x denote a dynamic vector-auantized signal 526,
E denote a differential input vector 527, E denote a
differential vector-quantized signal 528, x denote a
dynamic multistage vector-quantized signal 529 and ~
denote a dynamic output vector 530. The above-mentioned
operations are implemented by a dynamic vector quantizer
520, a subtractor 521, a differential vector quantizer
522, an adder 523 and an encoding frame memory 534.
x x + ~d E = X - X ~d
E = ~ ~ qe = -~d ~e
x = x ~- ~ = x ~ ~d ~ ad ~ ~e x ~ ~e
A -f
~ = X(rg) Z '
where qd and _ are dynamic quantized noise and
differential vector quantized noise respectively, z
A
is frame delay and x(r ) is x at a position displaced
by rg.
Through the process described above, the dynamic
vector quantizer 520 and the differential vector
quantizer 522 give g or h as a dynamic vector quantized
index 531 an~l i as a differential vector quantized index
532, respectively, to the variable-length encoder 525.
The var1able-length encoder converts the reception
signals into a variable-length encoded signal 533,
w(g-h, i). w(g-h, i) is a dynamic vector quantization
coded output.
A preferred embodiment of the dynamic vector
quantizer according to the present invention will be
described concretely in connection with Fig. 36.
In Fig. 36, indicated at 534 is an input vector
register, at 535 is a dynamic output vector address
counter, at 537 is a dynamic output vector register, at
538 is an initial distortion arithmetic unit, at 539 is
an initial minimum distortion detector and at 540 is an
initial output data latch.
The action of this dynamic vector quantizer will be
described hereunder. ~fter the input vector S01 has been
- G3 -
latched by the input vec~or register 534, the dynamic
output vector address counter 535 reads sequentially a
set of dynamic output vectors 530 which has previously
been transferred from the coded frame memory 524 to the
dynamic output vector code table 536 and the mean value
output vector from the dynamic output vector code table
536. The dynamic vector quantized output vector 543 is
latched temporarily by the dynamic output vector
register 537. The initial dis~ortion arithmetic unit
538 calculates distortions between the input and the
output vectors successively. As soon as the minimum
distortion output vector has been detected, the minimum
distortion detector 539 provides a strobing signal 546.
Then, the initial output data latch 540 latches the
dynamic output vector or the mean value output vector
544, and the index 547 corresponding to the address of
the dynamic output vector.
Thus the dynamic vector quantized signal 526 and
the dynamic vector quantized index 537 representing the
minimum distortion dynamic output vector or the mean
value vector are provided.
The constitution of an embodiment of the
differential vectox quantizer will be described hereunder
in connection with Fig. 37.
In Fig. 37, indicated at 548 is a differential
input vec~or recJister, at 549 is a di~ferential output
vector address counter, at 550 is a differential output
- 6~ -
~z~
vector code table, at 551 is a differential output
vector register, at 552 is a secondary distortion
arithmetic unit, at 553 is a rninimum distortion detector
and at 554 is a secondary output data latch.
S The action of this differential vector quantizer
will be described hereunder.
Let E = {El, E2, . . . ,Ek} denote a differential
input vector. The dynamic vector quantized ~ignal,
namely, the feedback loop connected to the coded frame
memory of Fig. 31, formed by dynamic vector quantization
using the picture signal sequences of the present and
the preceding frames is rémoved and differential input
vectors are obtained by using dynamic vector quantized
signal sequences obtained through a feed-forward mode.
Then, a set of N differential output vectors is obtained
through the clustering training of the differential
input vectors. Let E = {El, E2, ..., EN}
set of the differential output vectors Ei = {Eil~ Ei2'
..., Eik} and I = 11, 2, ..., N~ denote an index set of
the differential output vectors. Then, differential
quantization Qe is expressed as a cascaded connection of
coding Ce and decoding De as follows.
Qe - -i if d tE, Ei) < d( E, f j ) for ~11 j
Ce
D : i -~
e
Q = D C
~e e e
- 65 _
xpressing distortion d( E ~ ~i) in Euclidean norm,
d(~, ~i) a ~
Therefore, the differential vector quantizer maps into
min d(~, ~i)' i.e., a differential output vector
minimizing the distortion.
In the differential vector quantizer shown in
Fig. 37, the differential output vector address counter
549 counts up consecu~ively when the differential input
vector 527 is latched by the difEerential input vector
register 548 and reads sets of differential output vectors
which has previously been obtained by clustering training
consecutively from the differential output vector code
table 550, The differential output vectors S57 is
latched temporarily by the differential output vector
register 551. Then, the secondary dis~ortion arithmetic
unit 553 calculates d(~, ~i) and the secondary minimum
distortion detector 553 detects a differential output
vector or the minimum distortion min d(E~ ~i) Upon
the detection of the minimum distortion output vector,
the strobing signal 560 is given to make the secondary
output data buffer 554 latch the differential output
vector 558 and the address signal 561 corresponding to
the differential output vector index. The differential
vector quantizer gives F: as the differential output
vector 528 for the minimum distortion and the index i
of the differential output vector as the dif~erential
vector qualltjzed index 532.
- 6G -
~Z~3'~
The dynamic multistage vector quantization encoder
acts in the processing procedure as described above.
The constitution of an ernbodiment of the dynamic
multistage vector quantization decoder will be described
hereinafter in connection with Fig. 38.
In Fig. 38, indicated at 528 is a variable-length
decoder, at 563 is a dynamic vector quantized index
latch, at 564 is a decoded frame memory and at 565 is a
differential vector quantized index latch.
The action of the dynamic multistage vector
quantization decoder will be described hereunder.
The variable-length coded signal 533 processed
through variable-length encoding by the dynamic multi-
stage vector quantization encoder, i.e., s(g-h, i), is
decoded by the variable-length decoder 5~2 into the
dynamic vector quantized index 531, namely, g or h, and
a differential vector quantized index, i.e., i. The
dynamic vector quantized index latch 563 latches g or h
temporarily and reads, by using g or h as an address
2~ signal, the corresponding dynamic output vector ~g or
mean value vector -h as a dynamic vector quantized
signal 526, i.e., x from the dynamic output vector code
table 536. The dynamic output vector ~(rg) is
transferred beforehand from the decoded frame memory 564
to the clynamic output vector code table. The differ-
ential vector quantized index latch 565 uses the
differential vector quantized index 532 as an address
i signal to read the corresponding differential output
vector Ei from the differential output vector c~de
table 550 and obtains the differential vector quantized
signal 528, i.e., E. The adder 523 adds the differ-
ential vector quantized signal 528 and the dynamic
vector quantized signal 526 to regenerate and give the
dynamic multistage vector quantized signal 530, i.e.,
x and sends the same to the decoded frame memory 564.
Those processes are express,ed by the following formulas.
Since ~g = x(rg) . Z
g or h ~ yg or ~h = x ~ ~d = x
) Ei = ~ . = E
X = X + E = X ~ ~e
Thus, when the dynamic output vector code table of
the encoder and the differential output vector code table
of the decoder, and the coded frame'memory and the
decoded frame memory of the dynamic multistage vector
quantization are constituted and controlled so as to act
in the same contents, the variable-length coded signal
w(g, h, i) is obtained through highly efficient coding
process.
In this process, the maximum amount of information
Hv of the dynamic multistage vector quantization i5
given by
~v = ~ log2(P-~-N)bits/sample
_ f,~ _
3'~
where P is the number of dynarnic output vectors, ~ i.s
the number of mean value vectors and ~ is the number of
differential output vectors.
With the provision of the enc~der on the trans-
mission side and the decoder on the reception side, the
dynamic multistage vector quantizer achieves highly
efficient coded transmission as a high-ef~iciency
encoder for picture signals.
The dynamic multistage vector quantizer has been
lQ described on an assumption that the block size (the
number of dimensions of vectors) is the same for the
initial multistage vector quantization and for the
secondary differential vector quantization, however, the
block size may be different bet~een the initial
multistage vector quantization and the secondary
differential vector quantization. Naturally, the
primary differential vectors may be vector-quantized
through a plurality of stages to nth differential
vectors. Furthermore, when the distortion in vector
quantization exceeds a predetermined threshold, it is
possible to encode the distortion so as to be identified
as an insi~nificant vector.
A sixth embodiment of the present invention will
be described hereinafter.
lrhis embodillletlt of the present invention is a
vector quantizer capable of achieving hic~hly efficient
inter-frame codinq by eliminatinq redundancy resultincl
- 69 -
'7
from intra-frame and inter-fr~me correlations of
animated picture siynals.
The principle on which this ernbodiment is based
will be described prior to the description of the
embodiment. Suppose that an object has moved in a scene
from a position A to a position B while the frame has
changed from a frame No. N-l to a frame No. N. Then,
the picture pattern of k x k lattice block L (k is a
plural number) surrounding a part of the object in the
frame No. N-l is approximately the same as the picture
pattern of a k x k lattice block M surrounding the same
part of the object in the frame No. N. That is, as
viewed on the same scene, the center of the block M is
located at a distance indicated by a vector r from the
center of the block L. This vector is defined as a
movement vector. The movement vector r is detected by
the following method. k x k Lattice blocks which
provide an arrangement of the center of each block are
cut out from the frame No. N-1 in the frame No. N with
a point (a point indicated by a cross) located in the
frame No. N-l at the same position as that of the center
of the objective block M as origin. In this example,
twenty-five blocks are produced. These blocks are
designated as blocks Sl, S2, ..., S25
identity with the objective block M in the frame No. N
is defined by
k k
m ,~ ~ ¦Sm(i, j) - M(i, i)l-
~=1 ~=1
- 70 -
3~7
The block S which minimizes ~he degree of identity D
is the block 1,. The vector from the center of the
block L to the origin (0, 0) is detected as a mo~ernent
vector r = (u, v).
Accordingly, to apply movement compensation in
inter-frame predictive coding, when the block ~1 of a
picture signal in the frame No. N is given to an
inter frame predictive encoder, a picture signal ~ormed
by shifting the block L of a picture signal in the
preceding frame, i.e., the frame No. N-l, with in the
scene by the movement vector r is used to minimize the
power of the inter-frame predictive error signal so that
coding efficiency is improved.
Fig. 39 shows an exemplary constitution of a device
of this kind. In Fig. 39, indicated at 610 is an A/D
converter, at 620 is a raster/block scan converter, at
630 is a frame memory, at 640 is a movement vector
detector, at 650 is a variable delay circuit, at 660 is
a subtractor, at 670 is a scalar quanti7er, at 680 is
an adder and at 690 is a variable-length encoder.
The operation of this device will be described
hereinafter. First the A/D converter digitizes an
analog picture input signal 600 and gives a picture
signal sequence 602 according to the sequence oE raster
scannillg. 'l'he raster/block scan converter 620 convcrts
the output procedure on the time sequence of the picture
signal oE the raster scan digital signal sequence 602
- 71 -
~Zg~3~
into block scanning and gives a block scan picture image
input signal 603 arranged in lattice blocks (the interior
of the block is raster scanning) from the top to the
bottom and from the left to the right of the scene. A
one-frame preceding regenerative picture signal 604
regenerated through inter-frame DPCM loop is read from
-the frame memory 630. The movement vector detector ~40
performs block-matching between the present block scan
picture input signal 603 and the ~ne-frame preceding
regenerative picture signal 604 and gives the movement
vector 605 r = (u, v) of the one~frame preceding picture
signal 604 minimizing the degree o~ identity. The
elements u, v of the movement vector correspond to the
horizontal and the vertical shifts of the picture
element of the block respectively. The variable delay
circuit 650 gives a picture signal which is the nearest
to the present block scan picture input signal 603,
namely, a picture signal formed by block-shifting the
one-frame preceding regenerative picture signal 604 by
the movement vector, as a predictive picture signal 606.
The subtracter 660 calculates the difference between the
block scan picture input signal 603 and the predictive
picture signal 606 and gives a predictive error picture
signal 607 to the scalar quantizer 670. The scalar
quantizer 670 having a scalar quantization character-
istic, for example, such as shown in l~iy. 40,
scalar-quantizes the predictive error picture signal 607
~Z~23'7
which is reduced in electric pol~er through the previous
movement compensation and gives a predictive error
quantized picture signal 608 ~hich is reduced in the
quantization level of each picture element. The adder
680 adds the predictive error quantized picture signal
608 and the predictive picture signal 606 and gives a
regenerative picture signal 609 containing a scalar
quantization error to the frame memory 630. The frame
memory 630 delays the present regenerative picture
signal 609 by one-frame cycle.
Fig. 41 shows an exemplary constitution of the
movement vector detector 640 for movement compensation.
In Fig. 41, indicated at 642 is a movement vector
detector, at-641 is an identity degree calculating
circuit, at 642 is a movement region line memory, at
643 is a line memory control circuit, at 644 is an
identity degree comparator and at 645 is a movement
vector latch.
The identity degree calculating circuit 641 of the
movement vector detector 640 receives a block M formed
by blocking a plurality of the present picture input
signal sequences 603. At this time, lines of the one-
frame preceding regenerative picture signal 604 of the
frame memory 630, corresponding to the search range for
the movement region o~ the block M are stored in the
movement re~ion line rmemory 642. The line memory
control circuit 643 reads sequentially the block L and
Z37
a plurality of blocks arranyed around the block I, with
the block L as the center, each of the one-frame
preceding regenerative picture sign~l 604, from the
movement region line memory 642 and gives the same to
the identity degree calculating circuit 641. The
identity degree calculating circuit 641 calculates the
degree of identity D of the block M with a plurality of
blocks including the block L read from the movement
region line memory 642 and the identity degree comparator
644 detects the smallest degree of identity min Dm. The
coordinates ~u, v) of the center of the block giving the
min Dm with the center of the block L as the origin
correspond to the horizontal and the vertical address
shifts, respectively, of the movement region line
memory 642. Therefore, when the degree of identity is
minimized, the identity degree comparator 644 gives a
movement detection strobing signal 611 to the movemént
vector latch 665 to make the movement vector latch 665
receive a movement vector address 612. The movement
vector latch 654 sends a movement vector 605 r from the
center of the block L to the coordinates (u, v) of the
center of the block which minimizes the degree of
identity Dm within the movement region line memory 6~2
to the variable delay circuit 650 and the variable-length
encoder 690 of Fig. 41.
The variable-length encoder 690 of Fig. 39
processes the movement vector 605 and the pr~dictive
- 7~ -
error quantized picture signal 608 through variable-
length coding to curtail the amount of picture signal
inEormation. This process enables low bit rate
transmission of the movement compensation inter-frame
coded output 601.
Thus the movement compensation inter-frame encoder
being constituted, movement compensation is operated
for each block and inter-frame DPCM is performed for
every picture element. Accordingly, the minute
variation of the scene can not be identified from noise
and the variable-length coding of the movement vector
and the predictive error quantized picture signal is
difficult. Furthermore, since the total sum of the
differential magnitude of each picture element within
the block is selected as an evaluation function for
identity calculation at the movement detector, the
accuracy of bloc~ matching for portions such as the edge
portion where sharp variation occurs is not satisfactory.
Stilll further, since the control of the variation of
the amount of generated information resulting from the
variation of the movement is difficult, the signal
transmission through a transmission channel of a fixed
transmission capacity entails a large loss and the
coding of the predictive error quantized picture si~nal
for every picture element is inefficient. Since the
movement compensation system is liable to be influenced
adversely by transmission channel error, the frame
! memory needs to be reset for repeating transmission
when a transmission channel error occurs, which requires
a long resetting time.
Fig. 42 shows a constitution of an ernbodiment of
the present invention formed on the basis of the above-
mentioned principle. In Fig. 42, indicated at 655 is a
dynamic front vector quantizer and at 666 is a fixed
back vector quan~izer. Like reference characters
designate like or the corresponding parts through Figs~
39 and 42. Fig. 43 shows the constitution of the
dynamic front vector quantizer employed in this
embodiment of the present invention and Fig. 47 shows
the constitution of the fixed back vector quantizer
employed in this embodiment of the present invention,
In Figs. 45 and 47, indicated at 667 is an input vector
register, at 668 is an output vector register, at 669
is a dynamic output vector code table, at 662 is a
parallel subtracter, at 621 is a parallel magnitude
arithmetic and logic unit, at 622 is a code table
address counter, at 623 is a magnitude distortion
arithmetic and logic unit, at 624 is a nonlinear minimum
distortion detector, at 625 is an index latch, at b26 is
a vector latch, at 627 is a minimum distortion detector,
at 628 is a differential output vector code table, at
629 is a mean value separation amplitude norlnalizatio
circuit and at 663 is a significant block decision
circuit. The operation of this dynamic multistage
- 7~ -
~Z~3~
vector quantizer ernbodying the present invention will
be described hereinafter in connection with Fic3. ~2.
Blocks each of a plurality of bl,ock scan picture
signal input signals 603 processed through A/D conver-
sion and raster/block scan conversion are sent to thedynamic front vector quantizer 655 and the subtractor
660. The dynamic front vector quantizer 655 produces a
dynamic output vector on the basis of the picture input
signal 603 and the regenerative picture signal 618 of
the preceding frame and forms a predictive picture
signal 613 corresponding to the position of the block of
the picture input signal 603 on the scene through vector
quantization and gives the same to the subtractor 660
and, at the same time, a front output vector index 612
lS to the variable-length encoder 690. Every plurality of
the output signals of the subtractor 660, i.e., inter-
frame differential picture signals 614 are blocked and
are processed by the fixed back vector quantizer 666 for
mean value separation amplitude normalization and vector
quantization. The fixed back vector quantizer 666 sends
a differential output vector as an inter-frame
differential vector quantized picture signal 616
together with mean value information and am~ ude
information to the adder 680 and sends a differential
output vector index 615 together with the mean value
information and the amplitude information to the
variable-length encoder 690. The adder 680 adds the
3~
( predictive picture signal 613, which is one of the
output siynals of the dynamic front vector quantizer 655,
and the inter-frame differential vector quantiæed
picture signal 616, which is one of the output signals
of the fixed back vector quantizer 666, to send a
regenerative picture signal 617 to the frame memory 630.
Since all those dynamic multistage vector
quantization processes are executed for each block, the
sample sequence within each block is defined as a
Picture element vector. The principle of vector
quantization on which this embodiment is based will be
explained hereunder.
Suppose Rl, R2, ..., ~ are N partitions of R for
an input vector x = [xl, x2, ..., Xk] in k-dimensional
signal space Rk~ Y ~ [~ 2~ YN] is a set of input
~ i [Yil' Yi2' ~ ~ Yik]~ whiCh are the output
points in a partition Ri, and I = [1, 2, ..., N] is an
index set for ~i. Then, vec*or quantization VQ is
expressed by a cascaded connection of coding C and
decoding D:
VQ(x) = ~i if x ~ Ri
C : x ~ i if d(x, ~ d(x, ~j) for all j
D i ~ ~i.
The distortion measure d(x, Yi) indicates the
distance between the input and the output vector within
k-dimensional signal space and, for example, the
( magnitude distortion measure is yiven by
d(x, ~ Xi Jijl
In this condition, the data rate of the index i, i.e.,
the vector quantization coded output, is ~ llog2N
bit/picture element. Accordingly, vector quantization
achieves highly efficient coding through coding process
using the input vector x and the index of the output
vector ~i providing a minimum distortion min d(x, Yi).
Decoding is attained merely by converting the coded
signal into an output vector -i corresponding to the
index i. The set Y of the output vectors ~i is obtained
through the clustering training of ac~ual input vectors
_ or from a predetermined probability model. Fig. 47
shows the relation between the input and the output
vectors.
The action of the dynamic front vector quantizer
655 will be described hereinafter in connection with
Figs. 43,44, 45 and 46. The dynamic front vector
quantizer 655 processes the output signals 618 of the
frame memory storing the regenerative picture signals of
the preceding frame to produce sequentially dynamic
output vector code tables 669, detects an output vector
which provides the minimum distortion between the input
and the output vectors and forms a predictive picture
signal 613. The dynamic output vector code table 699
comprises a fixed output vector code table consisting o~
-7') -
3'~
( several zero vectors of uniform level and a rewritable
output vector code table having contents which is
updated at every block processing. The content of the
fixed output vector code table is a set ~in O~ seven
mean value vectors (vectors with the same vector
elements) arranged as shown in Fig. 44. The rewritable
output vector code table is produced and updated through
the ~ollowing process, As shown in Fig. 45, in the
vector quanti~ation of a block M in a frame No. N, with
the center (point X~ o~ the block of regenerative signals
of the preceding frame (frame No. N 1) on the scene
locating at the same position as that of the block M as
origin (0, 0), the center of each block constitutes a
plurality of shift blocks from block 1 to block 25
arranged as shown in Fig. 46. Each set of blocks and
the set of zero vectors are indexed as sets of dynamic
output vectors and registered in the dynamic output
vector code table. The arrangement of the shift blocks
as shown in Fig. 46 is arbitrary. Every k picture input
signal sequences 603 are blocked and the block of the
picture input signal sequences is latched as an input
vector x = [xl, x2, ..., xk] by the register 667. The
code table address counter 622 first reads sequent.ially
the output vectors _im in the rewritabl.e output vector
code table from the dynamic outpu~ vector code table 699.
The output vectors ~mi are latched by ~he reg.ister 688.
The magnitude distortion arithmetic uni.t 623 receives
-- ~3 () --
i24~3 ~
( the outputs of the parallel subtractor 662 and the
parallel magnitude arithmetic unit 621 and calculates
distortions di between the input and the output vectors
by the use of a formula
di = d(x, -i~ xi Yijl-
The nonlinear minimum distortion detector 624 executes,
for example, the following Drocess. First the rninimum
distortion d among all the di (i = 1, 2, ..., 25) is
detected. The minimum distortion
d = min di
The process is divided into three processes for three
cases respectively on the basis of the relation between
the value of d and thresholds Tl and T2.
When d > Tl ...................... Process e9
T2 _ d _ Tl ................. Process
d < T2 ...................... Process ~
The Process ~9 decides that any appropriate output
vector for the input vector is found in the output
vector code table and changes over to the fixed output
vector code table, reads output vectors _mi sequentially
from the fixed output code table and executes the
above-mentioned distortion calculation to obtain a new
minimum distortion d. The Process ~ adopts the
previously obtained d as a minimum distortion. The
- 8l
Process ~3, to avoid noise causing minirnum clistortion
error, defines minimum distortion d by
d = dl = d(x, ~ x~
and adopts the distortion from a vector consisting of
the picture elements of a block 1 located with a point
(0, 0) on the scene of the frame No. N-l, i.e., the
point (0, 0) in Fig. 46, as the center.
After the minimum distortion has been detected,
strobing signals are sent to the latches 625 and 626.
10Then, the latch 625 gives an output vector index 612
indicating the address of the output vector, while the
latch 626 makes the output vector ~im or yin yml become
the vector quantized output of the vector x and gives
the predictive picture signal 613.
15The information sent out from the dynamic front
vector quantizer to the transmission line is an output
vector index and the maximum amount of information is
(log2I + log2J)/K [bit/pel]
where I is the number of fixed output vectors, J is the
number of rewritable output vectors and K is the number
of dimensions of the vectors. For example, when I = 25,
J = 7 and K - 64 (block size: 8 x 8), an amount of
information
(log225 -~ log27)/64 = 0.12 [bit/pel] or less
- c~2 -
~2~
is given by the dynamic front vector quantizer.
The action of the fixed back vector quantizer 666
will be described hereunder in connection with Fig. 47.
Every k inter-frame differential signals 61~, namely,
S the outputs of the subtractor 660, are blocked and given
in the form of a differential input vector ~ = [~ 2~
..., Ek]. The differential input vector ~ is processed
through mean value separation normalizing process by the
mean value sepa-ration normalizing circuit 629 using a
mean value ~ and an amplitude a defined by the following
formulas to obtain an input vector e = [el, e2, ..., ek].
= K ~ .
j=l
1 k
j-l i
ej = (~ )/a (j = 1, 2, ..., k)
The amplitude may be calculated by the use of the
following formulas.
-1 k ( )212
j-l i
~ = max ~
Through mean value separation normalization process, the
input vectors can be distributed at random within a
limited region of k--dimensional signal space, and thereby
vector quantization efficiency is improved. In
- 83 -
~2~ 3'7
- implementing this process, sets of output vectors need
to be prepared on the basis of the distribution of the
input vectors processed through rnean value separation
normalizing process. After the output vectors have been
read in the decoding section, processes reverse to mean
value separation normalization, such as amplitude
regeneration and mean value regeneration, need to be
impiemented. Naturally, vector quantization may be a
vector quantization without this process. Differential
output v~ctors prepared through clustering training
using the mean value separation normalized input vectors
are stored beforehand in the differential output vector
code table 628. ~1hen the mean value separation
normalized vector e is given, the code table address
counter 622 gives sequentially the indices of the
vectors of the differential output vector code table to
read differential output vectors ~ei = [Yil~ Yei2~ ....
Yik~ index) from the differential output vector
code table 628 and gives the same to the register 688.
~he same operation as the distortion calculation in the
dynamic movement vector quantizer is implemented to
detect a differential output vector providing the
minimum distortion from the mean value separation
normalized input vector. Since the differential input
vectors ~ are blocked inter-frame differential signals,
the center of distribution thereof is a zero vector.
Accordingly, the amount of data to be transmitted can be
~2~237
( reduced greatly by setting a threshold not to transmit
the information of the indices, mean values and ampli-
tudes of input vectors dis~ributed neat the zero vector.
The significant block decision circuit 663 decides, on
the basis of the mean value ~ and the amplitude ~,
whether or not the blocks of the differential signal
sequences are significant, namely, whether the blocks of
the differential signal sequences need to be transmitted
as information. A method of this decision is, with T~
as a threshold,
when ~ > T~ or a ~ T0 the block is significant and
when ~ _ T~ and ~ _ T~ the block is not significant.
When significant, the significant block decision circuit
gives the differential output vector ~ie provi~ing the
minimum distortion, the mean value ~ and the amplitude
a as the inter-frame differential vector quantlzed
picture signal 616 to the adder 680 and the latch 625
gives signals indicating a significant block, i.e., the
index of the differential output vector minimizing the
distortion, the mean value ~ and the amplitude ~ to the
variable-length encoder 690. When not significant, the
significant block decision circuit 663 gives the zero
vector and the latch 625 gives only a signal indicating
insignificant block.
The output of the encoder thus given includes the
output vector index, the differential output vector
index and the variable-length coded signal 61~ produced
- ~35 -
3~
( by processing the information of the mean value and the
amplitude through variable-length coding.
Suppose a certain blocked input picture signal
sequences 603 in the frame No. N is a signal source
~ N ~Sl~ S2, ..., Sk}N, the block of the
predictive picture signal 613 given by the dynamic front
vector quantizer is -N' the block of inter-frame
differential picture signals is ~N' the block 616 of the
inter-frame differential vector quantized picture
signals given by the fixed back vector quantizer is -N
and the block of the reyenerative picture signal
sequences is SN. Then the general actions of the
encoder is given by the following formulas.
~N -N -N
-N ~N
-N -N ~N (-N ~N) (~N q) S~ q
where q is a fixed back vector quantization error.
Accordingly, the smaller the fixed back vector quanti-
zation error ~ the more the regenerative picture signal
approaches the input picture signal.
The constitution and the action of the decoder of
the dynamic multistage vector quantizer embodying the
present invention will be described hereinafter. Fig.
48 shows the decoder, in a preferred embodiment, of the
dynamic multistage vector quantizer. In Fig. 48,
indicated at 631 is a latch, at 632 is a variable-length
~2~ 7
( decoder and at 633 is a mean value and amplitude
regenerating circuit. Like reference characters desig-
nate like or corresponding parts throucJh Fiys. ~2, 43,
44 and 48. The decoder receives the output signal 619
of the encoder by the latch 631 and the variable~length
decoder 632 separates the code signals into two parts
and rPgenerates the dynamic output vector index 612 m
significance signal, the insignificance signal, the
differential output vector index, the mean value ~ and
the amplitude a 615 by decoding. The variable-length
decoder 612 also reads an output vector corresponding to
the output vector index from the dynamic output vector
code table 699 and regenerates the predictive picture
signal 613. On the other hand, ~hen the significance
signal is re~eived, the variable-length decoder 632
reads a differential output vector corresponding to the
differential output vector index. The amplitude and
mean value regenerating circuit 633 multiplies the
differential output vector by the amplitude and adds the
mean value to regenerate the inter-frame differential
vector quantized picture signal 616. For this purpose,
a dynamic output vector code table and a differential
outpùt vector code table produced througll the same
process employed in the encoder section are used. The
adder 688 calculates the sum of the reyenerated
predictive picture signal 613 and the inter-frame
differential vector quantized picture signal 616 to give
_ ~ 7 -
~2~
a regenerated picture signal 617 as an output pict~re
signal. Furthermore, the regenerated picture signal 617
is stored in the frame memory 630 and is used as
information for the decoding process for the next frame.
A seventh embodiment of the present invention will
be described hereinafter.
This embodiment is an inter-frame vector quantizer
capable of performing highly efficient coding of picture
signals by the use of the correlation between picture
signals in consecutive scenes.
Prior to the concrete description of this embodiment,
the fundamental constitution of the inter-frame vector
quantizer will be explained. Fig. 49 is a block diagram
showing the constitution of an encoder. In Fig. 49,
indicated at 701 is a digitized picture signal sequence,
at 702 is a raster/block scan converter for blocking
every plurality of picture signal sequences 70L arranged
along the direction of raster scanning, at 703 is blocked
picture signal sequence, at 704 is a subtracter, at 705
is the pr~dictive error signal sequence of the blocked
picture signal, at 706 is a movement detection vector
quantized encoder, at 707 is a vector quantization coded
output, at 708 is a vector quantization decoder, at 709
is a vector quantization decoded output, i.e., a
regenerative predictive error signa1 sequence, at 710 is
an adder, at 711 is a block of regenerated picture sigllal
sequences, at 712 is a frame memory, at 713 is a block of
-8~ -
3~
( regenerative picture si.gnal sequences delayed by a
one~frame cycle and also is a block of predictive signal
sequences for predicting the block 730 of picture signal
sequences, at 714 is a transmission buffer, at 715 is a
feedback control signal and at 716 is the output of the
encoder. Fig. 52 shows the details of an exemplary
constitution of the vector quantization encoder 706. In
Fig. 50, indicated at 717 is a mean value separating
circuit, at 718 is an amplitude normalizing circuit, at
719 is the inter-frame difference of the block of
picture signal sequences normalized with respect to
amplitude after separating the mean value, at 720 is a
mean value calculated by the mean value separating
circuit 717, at 721 is the amplitude calculated by the
amplitude normalizing circuit 718, at 722 is a movement
detection circuit for deciding, on the basis of the mean
value 720 and the amplitude 721, whether or not the
blocked picture signal sequences which are presently
being processed have made any significant movement with
respect to the block of picture signal sequences located
at the same position in the one-frame cycle preceding
frame, at 723 is the dicision signal given by the
movement detection circuit 722, at 724 is a code table
address counter, at 725 is a code table index, at 726 is
an output vector code table memory, at 727 i.s a code
table output vector, at 728 is a distortion calculating
circuit, at 729 is a minimum distortion detecting
_ ~9 _
3' i3
circuit, at 730 is a signal indicating the minimurn
distortion and at 731 i5 a transmission latch.
Fig. 51 shows the details of the constitution of
the vector quantization decoder 708. In Fig. 51,
S indicated at 732 is a reception latch, at 733 i5 an
amplitude regenerating circuit and at 73~ is a mean
value regenerating circuit.
Fig. 52 shows an exemplary constitution of the
decoder. In Fig. 52, indicated at 735 is a reception
buffer, at 736 is a block/raster scan converter which
acts reversely to the raster/block scan converter 702
and at 737 is a regenerated picture signal sequences.
The actions of the components will be described
hereinafter. First the general actions of the encoder
~ill be described in connection with Fig. 49. Basically,
this encoder is based on the conception of the inter-
frame DPCM system. On a scene, the digitized picturé
signal sequences 701 are regarded as square lattice
samples, however, the input is given in an order along
the raster scanning direction. The raster/block scan
converter 702 partitions the picture signal sequences
701 in blocks as shown in Fig. 53 and provides these
blocks as output signal. Suppose the blocked picture
signal sequences 703 is a frame No. f is expressed by a
25 signal source vector _f = {Sl, S2, , Sk}f. [n Fig.
55, k = 5. Further, suppose the differences 705 between
the signal source vectors 703 and the blocks 713 of the
- 90 -
3~7
predictive signal sequences calculated by the subtractor
704 is Ef, the blocks 709 of the reyenerative differen-
tial signal sequences formed by the vector yuantization
encoder 706 and the vector quantization decoder 708 is
Ef and the predictive signal sequences 713 given by the
frame memory 712 is Pf. Then, the gene~al actions of
the encoder shown in Fig. 51 are expressed by
Ef = Sf - Pf
Ef = ~f + Q ............................. ~1)
Sf = Pf ~ Ef = Sf ~ Q
Pf = Sf Z f
where Q is a vector quantization error and Z f is a
delay of one-frame cycle caused by the frame memory 712.
Accordingly, Pf is equal to the regenerative signal
sequence Sf 1 of the block Sf 1 of picture signal
sequences one-frame cycle before the signal source
vector 703, namely, the picture signal sequence at the
same position in the frame No. f-l. The vector
quantization coded output 707 obtained through the
above-mentioned process is the difference between the
signal source vector 703 and the block 713 of the
predictive signal sequences namely, a result of data-
compression of the block Ef 705 of the predictive error
signals by the vector quantization encoder 706 and the
output 707 is given to the transmission buffer 714, and
then given to the transmission line as the encoder
_ 9 1 --
~Z~ 3~7
( output 716. The actions of the vector ~uantization
encoder 706 and the vector quantization decoder 708 will
be described in connection ~ith Figs. 50 and 51. In
vector quantization, a block composed of k pieces of
samples (k is the plural number) is regarded as an input
vector in k-dimensional signal space, output vectors
which have minimum distortion with respect to input
vectors which are given sequentially are selected from
a set of output vectors prepared previously on the basis
of the probability distribution of input vectors so that
the distortion with respect to the input vector is
generally minimized, and the indices attached to the
selected output vectors are quantized and given as
outputs. In the decoding section, output vectors
corresponding to the indices are read from the same set
of output vectors prepared also in the decoding section.
The input vector given is the block ~f ={~ 2
~k}f 705 of the predictive error signals. The mearl
value separating circuit 717 substracts the mean value
~ 720 operated by the use of a formula
Il = K-l ~ E ..,.... (2)
j=l
from the block ~f 705, the amplitude normalizing circuit
718 normalizes the output of the mean value separating
circuit 717 by the amplitude a 721 calculated by the use
of a formula
j-l j I .......................... ~3)
- 92 -
3~7
to form a mean value separa~ion normalized input vector
i X = {(Xl, X2, .. , Xk} 719 That is,
Xj = ( E j ~ , 2, .~., k) ... (~)
The amplitude may be calculated by formulas other than
formula (3), such as, for example,
= lK ~ 2]2
j=l ~ ....................... -- (5)
~ = max ~
Through the mean value separation normalizing process,
the input vectors can be distributed at random -within a
limited range in k-dimensional signal space, and thereby
the efficiency of vector quantization is improved. In
implementing the mean value separation normalizing
process, the set of output vectors needs to be prepared
on the basis of the distribution of the input vectors
lS processed through t~le mean value separation normalizing
process and, after the output vectors have been read in
the decoding section, processes reverse to the mean value
separation normalizing process, such as amplitude
regeneration and mean value regeneration, need to be
implemented. Naturally, vector ~uantization may be such
a vector ~uantization omittlng those reverse processes.
~1ean value separation normalized output vectors prepared
on the basis of the probability distribution density of
the mean value separation normalized input vector so that
- 93 -
~Z~ 3~7
the distortion from the mean value separation normalized
input vectors is generally minirnized are written
previously in the output vector code table memory 726.
When a mean value separation normalized input vector X
719 is given, the code table address counter 724
sequentially gives indices of vectors stored in the
output vector code table memory 726, i.e., code table
addresses 725, to read the mean value separation
normalized output vectors ~T = {YT1 ~ YT2~ ~ Ylk}
(T = index) 727 from the output vector code table memory
726. The distortion calculating circuit 728 calculates
the difference between the mean value separation
normalized input vector S 719 and the mean value
separation normalized output vector ~T 727. Several
distortion calculating methods are available, for
exam~le, such as those shown below.
k
d(~, ~T) = ~ ¦Xj YTj I
~-1 12
d(X, ~T) = j-l lXi Yli ....... (6)
d(X, y ) = max ¦Xj YT jl
where d(X, Yr) is distortion. The minimum distortion
detecting circuit 729 gives a strobing signal 730 when
a distortion d(X, y ) which is smaller thall the past
minimum distortion is found. At the same time, the
latch 731 stores the index 72S. At a stage where the
- 94 -
code table address counter has given all of a series of
indices, the index i of a mean value separation
normalized output vector ~hich minimizes distortion from
the mean value separation normalized input vector is
stored in the latch 731. The index, the mean value ~
720 and the amplitude a 721 form the vector quantization
coded output. The data is compressed further by the use
of the correlation between, successive scenes. Since the
input vectors are blocked predictive error signals, the
input vectors are distributed around a zero vector. The
amount of data can be reduced considerably by setting a
threshold to regard input vectors distributed near the
zero vector as zero vectors and providing neither index,
mean value nor amplitude. The movement detecting circuit
722 receives the mean value ~ 720 and the amplitude a
721 and decides whether or not the block of the
predictive error signal sequences can be regarded as a
zero vector, namely, the present block has made any
signifi~ant variation (movement) with respect to the
corresponding block in the one-frame cycle preceding
frame. This decision is made by examining the mean value
and the amplitude with respect to a threshold T~ as
when ~ < T~ and o < T~, significant moveme~nt has
not been made and
when 1l > T or (J > I'o, significant movement has
been made.
- 95 -
Accordingly, the latch 731 gives only a signal
indicating "no movement" ~hen a code indicating "no
movement" is given as the result 723 of move~ent
detection and gives the index 725, the mean value 720
and the amplitude 721 in addition to a signal indicating
"movement" as a vector quantization coded output signal
707. The transmission buffer 714 keeps monitoring the
amount of information transmitted and gives a feedback
control signal 715 to control the threshold T~. Thus
the amount of information transmitted is controlled.
In the vector quantization decoder 708, the latch 732
receives the vector quantization coded output 707. Upon
the reception of a signal indicating "movement", the
latch 732 reads a mean value separation normalized
lS output vector ~ 727 from the output code table memory
726 according to the index i 725. The amplitude
regenerating circuit 733 multiplies the mean value
separation normalized output vector 727 by the amplitude
721 and the mean value regenerating circuit adds the
mean value 720 to the output of the amplitude regene-
rating circuit 733 and gives an output vector, namely,
regenerated predictive error signal sequences ~f 709.
That is,
r.f = ~ y ~ (j = 1, 2, ..., k) .. (7)
Upon the reception of a signal indicating "no
movement", the latch 731 gives zero for the mean value
- 96 -
3'7
720 and amplitude 721. In this case, the output vector
is a zero vector. The operation of the decoder will be
described in connection with Fiy. 52. The reception
buffer 734 receives the encoder output 716 and decodes
the vector quantization coded output signal 707. The
vector quantization decoder 708 decodes, as described
above, the output vector, i.e., the predictive error
signal seauences ~f 709~ and the adder 710 and the frame
memory 712 regenerate the block Sf 711 of regenerated
picture signal sequences through operation based on the
following formulas,
,
Sf = Pf + Ef Sf Q ~ .... ( 8 )
Pf = Sf Z
where Q is vector quantization error and Z is a delay
of one-frame cycle. The block/raster converter 736 scans
in the raster scanning direction and converts the blocked
regenerated picture signal sequences Sf 711 to provide
regenerated picture siynal sequences 737.
The constitution as described hereinbefore of this
basic inter~frame vector quantizer has problems such
that the threshold T~ becomes large to stabilize the
amount of information, when the picture varies sharply
and, consequently, the region changed from that of the
preceding scene remains as in khe preceding scene with
some blocks, and thereby the boundary between blocks
becomes conspicuous.
_ 97 -
3~
I The embodiment of the present invention based on
the basic principle will be described in connection with
the accompanying drawings. Consider a binary tree as
shown in Fiy. 54. The root of the tree and each node
correspond to k-dimensional signal space Rk and to a
space formed by partitioning Rk in steps respectively.
Each node has a representative point, which is the
output vector of k dimensions. The output vectors of
each step are produced on the basis of the distribution
of input vectors so that the total sum of distortions
between the input vectors and the output vectors is
minimized. That is, the stepped partition o the space
is made on the basis of the distribution of input vectors
in R . When an input vector is given, an output vector
corresponding to the last node is selected by comparing
the distortions of two output vectors branched from a
node from the input and selecting a branch leading to an
output vec*or having a smaller distortion from the input
vector, from the first step through the last step. When
the last step is the nth step, the binary tree has 2n
nodes in the last step. In Fig. 54, n = 3. The
description given above explains the principle of tree
search vector quantization (TSVQ). Fiy. 57 shows an
exemplary constitution of an encoder according to the
present invention. In Fig. 55, indicated at 701 are
digitized picture signal sequences, at 702 is a raster/
block scan converter, at 703 are blocked picture signals,
9~ _
3~7
( at 704 is a subtractor, at 705 is a block of predictive
error signals, at 738 is a TSVQ encoder based on the
above-mentioned principle, at 739 is a TSVQ encoder
output, at 740 is a TSVQ decoder, at 741 is a TSVQ
decoder output, at 710 is an adder, at 742 is a block of
regenerated picture signals, at 712 is a frame memory,
at 743 is an output of the ~rame memory 712, i.e., a
block of predictive signals, at 744 is a transmission
buffer, at 745 is a feedback control signal and at 746
is an encoder output. F.ig. 56 shows the details of an
exemplary constitution of the TSVQ encoder 738. In
Fig. 56, indicated at 747 is a limiter which measures
the distance between an input vector and the origin and
quantizes the input vector into a zero vector when the
distance is smaller than a threshold, at 748 is a zero
vector detection signal given when an input vector is
quantized into a zero vector by the limiter 747, at 749
is a coding controller, at 750 is a first-stage TSVQ
encoder, at 751 is an output vector index given at a
stage where the search has been made as far as the
first-stage TSVQ encoder, at 752 is a second-stage TSVQ
encoder, at 753 is an output vector index given at a
stage where search has been made as far as the second-
stage TSVQ encoder 752, at 754 is a third-stage TSVQ
encoder and at 755 i9 an output vector index given at a
stage where the search has been made as far as the
t.hird-stage TSV~ encoder 754. Fig. 57 shows the further
_ 99
details of an exemplary constitution of the second-stage
TSV~ encoder 752. In Fig. 57, indicated at 756 is a
second-stage output vector code table rnemory, at 757 is
a parallel distortion calculating circuit, at 758 is a
distortion comparator, at 75g is a resultant signal of
comparison given by the distortion comparator 758 and a~
760 is an index register. Fig. 58 shows an exemplaxy
constitution of the TSVQ decoder 740. In Fig. 58,
indicated at 761 is an index latch, at 762 i8 an output
vector index and at 763 is an output vector code table
memory. Fig. 59 shows an exemplary constitution of a
decoder according to the present invention. In Fig. 59,
indicated at 764 is a reception buffer and at 765 are
regenerated picture signal sequences.
First the operation of the encoder will be described
hereunder.
Digitized picture signal sequences 701 are samples
given sequentially along the direction of raster
scanning. The raster/block scan converter 702 blocks
every k picture signal sequences and scans and converts
the blocks sequentially. Suppose the blocked picture
signal sequences 703 in a frame No. f are expressed by a
signal source vector Sf = {51~ S2, ..., Sk}f. When ~f
is the difference 705 between the signal source vector
703 and tlle block 743 of predictive signals, calculated
by the subtracter 704, Lf iS a TSVQ decoded output formed
by the TSVQ encoder 738 and the TSVQ decoder 739, i.e.,
-- 10 0 --
a block 741 of the regenerated predictive error signals,
Sf is a block of regenerated signals, and P~ is a block
743 of predictive signals obtained as a block of
regenerated picture signals delayed by one-frame cycle
by the frame memory 713. Then, the basic actions of the
encoder shown in Fig. 55 are expressed by:
Ef = Sf - Pf
~ = Ef + Q .......................... , (9)
5~ = Pf = Ef = Sf ~ Q
Pf = S z-t
where Q is a vector quantization error and z t is a
delay of one-frame cycle caused by the frame memory 712.
Basically, the encoder is constituted on the basis of
the.inter-frame DPCM system. The transmission buffer
744 receives a TSVQ coded output 739 and ~ives a coded
output 746 to a transmission line. The transmission
buffer 744 monitors the amount of transmitted
information and controls the amount of coded data in the
TSVQ encoder 738 according to the feedback control
signal 745. The mode of this control, the TSVn encoder
ar,d the TSVQ decoder will be described in connection
with Figs. 56, 57 and 58. Suppose an output vector set
Y of a binary tree structure as shown in Fig. 54 is
obtained. Y is formed previously on tlle basis of the
distributi.on of input vectors so that the total sum of
the distortions of the vectors belonging to each step of
-- 10 1 --
'7
I the binary tree from the input vectors is mirlirnized.
Tree search vector quantization if the repetition of
comparison for distortion between paired two output
vectors and an input vector to decide paired two output
vectors to be compared at the next step.
The three steps of the tree shown in Fig. 54
correspond to the first-stage TSV~ encoder 750, the
second-stage TSVQ encoder 752 and the third-stage TSVQ
encoder 754 of Fig. 56. The block Ef 70S of predictive
error signals is given as an input vector. The limiter
747 calculates the distortion of the input vecto.r from
the origin (zero vector) and regards the input vector
705 as a zero vector when the distortion is smaller than
a predetermined threshold and gives a zero vector
detection signal 748. This process is expressed by:
when d(Ef, 0) < T~, Ef ~ 0 .............. (10)
where T~ is a threshold, Ef is an input vector and
d(~fr 0) is the distortion of the input vector from the
æero vector. When the distortion is greater than the
threshold T~, the input vector 705 is sent to the
first-stage TSVQ encoder 750. The distortion may be
defined hy various ways. Several ways of defining the
distortion are shown below by way of example.
- 102 -
1 d(a, b) = ~ ¦a _ b ¦2
d(a, b) = ~ ¦aj -- bj¦ .................. (11)
d(a, b) - max ¦aj - bj¦
where d(_, b) is the distortion between a vector
a = {al, a2, ..., ak~ and a vector b = {bl, b2, ..., bk}-
The input vectors which have not been regarded as a
zero vector are processed through the first-, the
second- and the third-stage TSV~ encoders for tree
search vector quantization. At each stage, the
distortion between the input vector and paired two
output vectors assigned through the distortion compari-
son at the preceding stage is calculated to select one
of the paired two vectors which has a smaller distortion
from the inut vector than the other. This information
is added to the results of comparison given by the
preceding stages and is sent to the next stage. At the
first stage, since only one pair of output vectors is
given, the result of comparison at the previous stages
is neither necessary nor available. Suppose the result
of distortion comparison at the first stage is il 751.
At the second stage, the distortion between the input
vector and a pair of output vectors assigned on the
basis o~ il is calculated. The result of the calculatio
is added to il to form i2. The third stage receives tlle
input vector Ef and i2 and gives an index i3. For
example, as shown in Fig. 54, suppose"zero"is assigned
- 103 -
when the left branch is selected and "1" is assigned
when the right branch is selected. Then, il, i2 and i3
are expressed by one-digit, two-digit and three-di~3it
binary numbers respectively corresponding to the indices
of the output vectors. In the encoder of this invention,
the number of stages of tree search vector quantization
is controlled variably by the feed~ack control signal
for variable-length coding. The coding controller 7~9
receives the feedback control signal 745, the zero
vector detection signal 748, the index il 751, the index
i2 753 and the index i3 755 and, when the input vector
is regarded as a zero vector, codes a code corresponding
to zero vector When the input vector is not regarded
as a zero vector, the coding controller codes il, i2 or
i3 on the basis of the feedback control signal 745 as an
output vector index. When the transmission line, namel~,
the consecutive approximation of the input vector at
each stage, has no reserve, the output of a ~tage closer
to the first stage is coded and, when the transmission
line has a reserve, the output of the last stage is coded.
The amount of information of the input of a stage closer
to the first stage is smaller, therefore, the amount of
information to be coded is controlled in the manner as
mentioned above.
Fig. 57 shows an exemplary constitution of the
second-stage TSV~ encoder 752. Output vectors corres-
ponding to the second step of the output vector set Y are
- 10~1 -
stored in the second-stage output vector code table
memory 756. The second-staye output vector code table
memory 752 provides a pair of output vectors assigned by
the index 751 of the preceding stage.
The parallel distortion calculating circuit 757
calculates the distortions of the pair of output vectors
from the input vector 705 and the distortion comparator
758 compares the dis~ortions and gives the result of
comparison as a cont-rol signal 759. Several distortion
calculating methods are available as described in
- connection with the limiter 747. The index register 760
adds the result of distortion comparison at the second
stage to the index 751 given by the preceding stage and
gives a second-stage index 753. The actions of the
first stage and the third stage are almost the same as
that of the second stage, except that the respective out-
put vector code table memories of ~he first, second and
third stages store output vector sets corresponding to
the first, second and third stages respectively and that
the first stage is not provided with the index of the
preceding stage. All the output vectors belonging to
the output vector set Y and zero vectors are stored in
the output vector code table memory 763 of the TSVQ
decoder 740. The index latch 761 decodes the code of
the zero vector or the index of the output vector on
the basis of the TSVQ coded output 739 and reads a TSVQ
decoded output 741 from the out~ut vector code table
- 105 -
'7
memory 763. The operation of the decoder of this
invention will be described in connection with Fig. 59.
The recepti.on buffer 764 receives the encoder
output 746 and decodes the TSVQ coded output 739. The
TSVQ decoder 740 decodes the output vectors as described
earlier and the adder 710 and the frame memory 712
regenerate the block Sf of regenerative picture signal
suquences through operation given by:
-t .......................... (12)
Pf = Sf Z
where Q is a vector quantization error, z t is a delay
of one-frame cycle caused by the frame memory 712 and
~f is a block of regenerative predictive error signals
obtained as output vectors. The block/raster scan
converter 736 scans the block Sf 742 along the direction
of raster scanning and converts the same into a
regenerated picture signal sequences 765. Although
three-stage tree search vector quantization has been
described by way of example, naturally, in practice, the
number of stages is arbitrary and, generally, the number
of stages is greater than three.
This embodiment is applicable to wide technical
range relating to television transmission without being
limited particularly to inter-frame coding and is also
applicable to a sequential approximation quantizer
capable of controlling the amount of data.
-- 10 f) --
