The LOT is constructed by designing a unitary transform the size of the entire one dimensional signal in consideration. The transform will be characterized by a single overlapping rectangular matrix. To be more specific, the transform matrix will have the form:
The and
matrices are different to handle the beginning and end
of the signal, and are not of large interest, since they have no influence
on the asymptotic distortion of a reconstructed signal, as the signal
becomes large in size.
Let the input signal be a column vector x, with transform output y. The relationship is then
where the represents complex conjugate transposition. Suppose that
we are examining a 512 by 512 image, and want to transform a
column. Taking
to be an 8 by 16 matrix, would input blocks of size
16 and output blocks of size 8. Thus, the block that a DCT would input, is
also inputed, along with 4 extra data points on each adjacent side of the
block. Thus the transform stores the same amount of data as a block DCT,
but takes neighboring blocks into consideration. Conversely, synthesis
consists of combining the 8 basis vectors of length 16 linearly to
obtain a portion of the block (the neighbors contribution is used to fill
in the rest). It is the overlapping that will help alleviate the blocking effects, since
the block boundaries no longer exist in synthesis.
Imposing the condition that T be a unitary transformation, leads to some
conditions that must be satisfied by . The columns of
, which
represent the synthesis basis functions, must be orthogonal. In matrix
notation,
and because of the overlap, functions of neighboring blocks must also be orthogonal. This becomes
where W is the shift matrix, defined by
Suppose satisfies the conditions above, then for any unitary Z, it
is easy to show that
also satisfies those conditions. Thus, for a
fixed
, we can choose Z to diagonalize the output autocorrelation matrix
Assuming a first order Markov model, choosing a matrix Z to diagonalize
is optimal in terms of energy compactification of the transform coefficients.