tr156.tex

语音处理平台 可以分析语音能量 第一振峰频率等数据

\documentstyle[psfig,12pt,a4wide]{article}
\begin{document}
\def\baselinestretch{0.95}
\title{{\Large SHORTEN:} \\
Simple lossless and near-lossless waveform compression}
\author{Tony Robinson \\
\\
Technical report {\sc CUED/F-INFENG/TR.156} \\
\\
Cambridge University Engineering Department, \\
Trumpington Street, Cambridge, CB2 1PZ, UK}
\date{December 1994}
\maketitle

\begin{abstract}

This report describes a program that performs compression of waveform
files such as audio data.  A simple predictive model of the waveform is
used followed by Huffman coding of the prediction residuals.  This is
both fast and near optimal for many commonly occuring waveform signals.
This framework is then extended to lossy coding under the conditions of
maximising the segmental signal to noise ratio on a per frame basis and
coding to a fixed acceptable signal to noise ratio.

\end{abstract}

\section{Introduction}

It is common to store digitised waveforms on computers and the resulting
files can often consume significant amounts of storage space.  General
compression algorithms do not perform very well on these files as they
fail to take into account the structure of the data and the nature of
the signal contained therein.  Typically a waveform file will consist of
signed 16 bit numbers and there will be significant sample to sample
correlation.  A compression utility for these file must be reasonably
fast, portable, accept data in a most popular formats and give
significant compression.  This report describes ``shorten'', a program
for the UNIX and DOS environments which aims to meet these requirements.

A significant application of this program is to the problem of
compression of speech files for distribution on CDROM.  This report
starts with a description of this domain, then discusses the two main
problems associated with general waveform compression, namely predictive
modelling and residual coding.  This framework is then extended to lossy
coding.  Finally, the shorten implementation is described and an
appendix details the command line options.

\section{Compression for speech corpora}

One important use for lossless waveform compression is to compress
speech corpora for distribution on CDROM.  State of the art speech
recognition systems require gigabytes of acoustic data for model
estimation which takes many CDROMs to store.  Use of compression
software both reduces the distribution cost and the number of CDROM
changes required to read the complete data set.

The key factors in the design of compression software for speech corpora
are that there must be no perceptual degradation in the speech signal
and that the decompression routine must be fast and portable.

There has been much research into efficient speech coding techniques and
many standards have been established.  However, most of this work has
been for telephony applications where dedicated hardware can used to
perform the coding and where it is important that the resulting system
operates at a well defined bit rate.  In such applications lossy coding
is acceptable and indeed necessary order to guarantee that the system
operates at the fixed bit rate.

Similarly there has been much work in design of general purpose lossless
compressors for workstation use.  Such systems do not guarantee any
compression for an arbitrary file, but in general achieve worthwhile
compression in reasonable time on general purpose computers.

Speech corpora compression needs some features of both systems.
Lossless compression is an advantage as it guarantees there is no
perceptual degradation in the speech signal.  However, the established
compression utilities do not exploit the known structure of the speech
signal.  Hence {\tt shorten} was written to fill this gap and is now in
use in the distribution of CDROMs containing speech
databases~\cite{GarofoloRobinsonFiscus94}.

The recordings used as examples in section~\ref{ss:model} and
section~\ref{ss:perf} are from the TIMIT corpus which is distributed as
16 bit, 16kHz linear PCM samples.  This format is in common used for
continuous speech recognition research corpora.  The recordings were
collected using a Sennheiser HMD 414 noise-cancelling head-mounted
microphone in low noise conditions.  All ten utterances from speaker
{\tt fcjf0} are used which amount to a total of 24 seconds or about
384,000 samples.

\section{Waveform Modeling\label{ss:model}}

Compression is achieved by building a predictive model of the waveform
(a good introduction for speech is Jayant and Noll~\cite{JayantNoll84}).
An established model for a wide variety of waveforms is that of an
autoregressive model, also known as linear predictive coding (LPC).
Here the predicted waveform is a linear combination of past samples:
\begin{eqnarray}
\hat{s}(t) & = & \sum_{i = 1}^{p} a_i s(t - i) \label{eq:lpc}
\end{eqnarray}
The coded signal, $e(t)$, is the difference
between the estimate of the linear predictor, $\hat{s}(t)$ and the
speech signal, $s(t)$.
\begin{eqnarray}
e(t) & = & s(t) - \hat{s}(t) \label{eq:error}
\end{eqnarray}
However, many waveforms of interest are not stationary, that is the best
values for the coefficients of the predictor, $a_i$, vary from one
section of the waveform to another.  It is often reasonable to assume
that the signal is pseudo-stationary, i.e.\ there exists a time-span
over which reasonable values for the linear predictor can be found.
Thus the three main stages in the coding process are blocking,
predictive modelling, and residual coding.

\subsection{Blocking}

The time frame over which samples are blocked depends to some extent on
the nature of the signal.  It is inefficient to block on too short a
time scale as this incurs an overhead in the computation and
transmission of the prediction parameters.  It is also inefficient to
use a time scale over which the signal characteristics change
appreciably as this will result in a poorer model of the signal.
However, in the implementation described below the linear predictor
parameters typically take much less information to transmit than the
residual signal so the choice of window length is not critical.  The
default value in the shorten implementation is 256 which results in 16ms
frames for a signal sampled at 16 kHz.

Sample interleaved signals are handelled by treating each data stream as
independent.  Even in cases where there is a known correlation between
the streams, such as in stereo audio, the within-channel correlations
are often significantly greater than the cross-channel correlations so
for lossless or near-lossless coding the exploitation of this additional
correlation only results in small additional gains.

A rectangular window is used in preference to any tapering window as the
aim is to model just those samples within the block, not the spectral
characteristics of the segment surrounding the block.  The window length
is longer than the block size by the prediction order, which is
typically three samples.

\subsection{Linear Prediction\label{sect:lpc}}

Shorten supports two forms of linear prediction: the standard $p$th
order LPC analysis of equation~\ref{eq:lpc}; and a restricted form
whereby the coefficients are selected from one of four fixed polynomial
predictors.

In the case of the general LPC algorithm, the prediction coefficients,
$a_i$, are quantised in accordance with the same Laplacian distribution
used for the residual signal and described in section~\ref{sect:resid}.
The expected number of bits per coefficient is 7 as this was found to be
a good tradeoff between modelling accuracy and model storage.  The
standard Durbin's algorithm for computing the LPC coefficients from the
autocorrelation coefficients is used in a incremental way.  On each
iteration the mean squared value of the prediction residual is
calculated and this is used to compute the expected number of bits
needed to code the residual signal.  This is added to the number of bits
needed to code the prediction coefficients and the LPC order is selected
to minimise the total.  As the computation of the autocorrelation
coefficients is the most expensive step in this process, the search for
the optimal model order is terminated when the last two models have
resulted in a higher bit rate.  Whilst it is possible to construct
signals that defeat this search procedure, in practice for speech
signals it has been found that the occasional use of a lower prediction
order results in an insignificant increase in the bit rate and has the
additional side effect of requiring less compute to decode.

A restrictive form of the linear predictor has been found to be useful.
In this case the prediction coefficients are those specified by fitting
a $p$ order polynomial to the last $p$ data points, e.g.\ a line to the
last two points:
\begin{eqnarray}
\hat{s}_0(t) & = & 0 \\
\hat{s}_1(t) & = & s(t-1) \\
\hat{s}_2(t) & = & 2 s(t-1) - s(t-2) \\
\hat{s}_3(t) & = & 3 s(t-1) - 3 s(t-2) + s(t-3)
\end{eqnarray}
Writing $e_i(t)$ as the error signal from the $i$th polynomial predictor:
\begin{eqnarray}
e_0(t) & = & s(t) \label{eq:polyinit}\\
e_1(t) & = & e_0(t) - e_0(t - 1) \\
e_2(t) & = & e_1(t) - e_1(t - 1) \\
e_3(t) & = & e_2(t) - e_2(t - 1) \label{eq:polyquit}
\end{eqnarray}
As can be seen from equations~\ref{eq:polyinit}-\ref{eq:polyquit} there
is an efficient recursive algorithm for computing the set of polynomial
prediction residuals.  Each residual term is formed from the difference
of the previous order predictors.  As each term involves only a few
integer additions/subtractions, it is possible to compute all predictors
and select the best.  Moreover, as the sum of absolute values is
linearly related to the variance, this may be used as the basis of
predictor selection and so the whole process is cheap to compute as it
involves no multiplications.

Figure~\ref{fig:rate} shows both forms of prediction for a range of
maximum predictor orders.  The figure shows that first and second order
prediction provides a substantial increase in compression and that
higher order predictors provide relatively little improvement.  The
figure also shows that for this example most of the total compression
can be obtained using no prediction, that is a zeroth order coder
achieved about 48\% compression and the best predictor 58\%.  Hence, for
lossless compression it is important not to waste too much compute on
the predictor and to to perform the residual coding efficiently.
\begin{figure}[hbtp]
\center\mbox{\psfig{file=rate.eps,width=0.7\columnwidth}}
\caption[nop]{compression against maximum prediction order}
\label{fig:rate}
\end{figure}

\subsection{Residual Coding\label{sect:resid}}

The samples in the prediction residual are now assumed to be
uncorrelated and therefore may be coded independently.  The problem of
residual coding is therefore to find an appropriate form for the
probability density function (p.d.f.) of the distribution of residual
values so that they can be efficiently modelled.  Figures~\ref{fig:pdf}
and~\ref{fig:logpdf} show the p.d.f.\ for the segmentally normalized
residual of the polynomial predictor (the full linear predictor shows a
similar p.d.f).  The observed values are shown as open circles, the
Gaussian p.d.f.\ is shown as dot-dash line and the Laplacian, or double
sided exponential distribution is shown as a dashed line.
\begin{figure}[hbtp]
\center\mbox{\psfig{file=hist.eps,width=0.7\columnwidth}}
\caption[nop]{Observed, Gaussian and quantized Laplacian p.d.f.}
\label{fig:pdf}
\end{figure}
\begin{figure}[hbtp]
\center\mbox{\psfig{file=lnhist.eps,width=0.7\columnwidth}}
\caption[nop]{Observed, Gaussian, Laplacian and quantized Laplacian p.d.f and log$_2$ p.d.f.}
\label{fig:logpdf}
\end{figure}
These figures demonstrate that the Laplacian p.d.f. fits the observed
distribution very well.  This is convenient as there is a simple Huffman
code for this distribution~\cite{Rice71,YehRiceMiller91,Rice91}.  To
form this code, a number is divided into a sign bit, the $n$th low order
bits and the the remaining high order bits.  The high order bits are
treated as an integer and this number of 0's are transmitted followed by
a terminating 1.  The $n$ low order bits then follow, as in the example