%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pitch paths for TSD2000. 
% 3nd version motlicek@urel.fee.vutbr.cz  Mon Mar 27 13:51:42 2000
% latex version PM, Wed MAY 18 10:55:04 CEST 2000
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{llncs}
\usepackage{epsfig}
\usepackage{tabularx} 
\begin{document}
%
% -------- first some definitions -------------
\def\janbm#1{\mbox{\boldmath $#1$}}
\newcommand{\PP}{\mathcal{P}}      %proba
\newcommand{\LL}{\mathcal{L}}      %likelihood
\newcommand{\oo}{\janbm{o}}       % observation
\newcommand{\xx}{\janbm{x}}       % observation
\renewcommand{\ss}{\janbm{s}}       % part of sequence
\newcommand{\OO}{\janbm{O}}      % mat of observations
\newcommand{\mm}{\janbm{\mu}}      % vect mean
\newcommand{\EE}{\janbm{\Sigma}}      % covar mat
\newcommand{\II}{\janbm{I}}      % ident  mat


%%%%%%%%%%%%%%%%%%%%%%%%%%% definition of title, etc 
\title{Optimal Pitch Path Tracking for more reliable Pitch Detection\thanks{This work is supported 
by the Ministry of Education, Youth and Sports of
the Czech Republic -- project No.~VS97060, and by the Research
programme  of  Brno  University  of  Technology ``Research  of
electronic  communication  systems   and  technologies'', No. 
CEZ: 	J22/98:262200011.} 
}
\titlerunning{Optimal Pitch Path Tracking for more reliable Pitch
Detection}
\toctitle{Optimal Pitch Path Tracking for more reliable Pitch Detection}

%      (mozna pozmenim nazev aby tam byla zminena i metoda cest)
\author{Petr~Motl\'{\i}\v{c}ek \and Jan~\v{C}ernock\'{y}} 
\authorrunning{P.~Motl\'{\i}\v{c}ek, J.~\v{C}ernock\'{y}}
\tocauthor{P.~Motl\'{\i}\v{c}ek (VUT Brno), J.~\v{C}ernock\'{y} (VUT Brno)} 
%
\institute{Brno Univ.  of Technology, Inst. of Radioelectronics, 
\email{\{motlicek,cernocky\}@urel.fee.vutbr.cz}}
\maketitle 
%%%%%%%%%%%%%%%%%%%% abstract %%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
This paper presents an application of one method for improving
fundamental frequency detection from the speech. The method is based
on searching the best pitch paths over one or more words. It
uses the idea that the fundamental frequency of a speaker cannot
change sharply in a short time so that the pitch should not vary rapidly
over one (or a few) words. This technique is created for improving the
pitch detection. It cannot detect the pitch itself, but it uses some
pitch detectors. We compare some of them here and we try to determine
which one is the most suitable for our method.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%% intro %%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{intro}   %labely muzes dat v latexu ke vsemu, co je cislovane ! 
The word pitch (in context of speech processing), as defined
operationally by psychoacousticians, is the frequency of pure tone that
is matched by the listener to a more complex (usually periodic) signal.
This is a subjective definition. When we speak of a ``pitch detector'', we
usually refer to a device that measures the fundamental frequency of an
incoming signal; this is an objective definition. Pitch detection and
fundamental frequency estimation are often used interchangeably. The
pitch detection is not such an easy task. We have a lot of difficulties,
which we can encounter \cite{gold}:
\begin{itemize}
\item Sub-harmonics of fundamental frequency often appear that are
sub-multiples of the ``true'' frequency.
\item Fundamental frequency changes with time, often with each glottal period.
\item In many cases when strong sub-harmonics are present, the most reasonable
objective pitch estimate is clearly at odds with the auditory percept.
\item It is difficult to distinguish periodic background noise from breathy
voiced speech.
\item The dynamic range of the voice fundamental frequency is large. The pitch
of some male voices can be as low as 50 Hz, whereas the pitch of
children's voice can be as high as 600 Hz. 
\end{itemize}
These different kinds of behavior make pitch detection difficult. 

In the literature, a lot of techniques for pitch detection can be found. Among essential we can count autocorrelation function
(ACF) \cite{rabiner}. Instead of ACF, normalized cross
correlation function (NCCF) can be used \cite{talkin}. NCCF is often able to estimate
the pitch better than an ordinary ACF. Another method uses linear
prediction LPC and the fundamental frequency is estimated from its error
signal. In these techniques the pitch can be found using long-term
prediction (LTP). Cepstral pitch detection is popular, as
well. Here the pitch is estimated from the cepstral
train \cite{bogart}, \cite{cernocky}.

% odstavec se oddeluje dbojim odradkovanim. Pokud chces, aby
% nasledujici odstavec nebyl odsazeny, das na jeho zacatek \noindent
Using one of pitch detectors mentioned above only, we almost never get
good pitch estimation. We find out that these techniques often have
problems with recognition of voiced and unvoiced parts of
speech. Moreover they often detect wrong values of pitch in speech
(some higher harmonics or sub-harmonics), even though the fundamental
frequency is still approximately unvarying. Therefore some other
techniques are applied in order to remove these drawbacks. One of often used methods is the oversampling of input signal (usually 6 times). Another one is the median filtering of obtained pitch sequence. Finally, one of the ways that can improve pitch estimation is the optimal pitch path detection.

%\section{Pre-processing}
%\label{prepro}
%The aim of pre-processing is to prepare the input signal for next
%processing. First, in all experiments, the DC offset is removed from
%input signal. It is necessary to divide the input signal to the frames
%(for each frame we attempt to find the pitch). Therefore it is given $s_p$, $p=0,1,2\ldots$ a sampled speech signal
%with sampling interval $T=\frac{1}{F_s}$, analysis frame interval $t$,
%and analysis 
%window size $w$. At each frame we advance $z=\frac{t}{T}$ samples with
%$n=\frac{w}{T}$ samples 
%in the window. $w$ is chosen to be at least twice as long as 
%expected glottal period. $s$ is assumed to be zero outside the
%window. 

% $t$ is sized to sample adequately the time course of changes in pitch.

%\section{Pitch detectors}
%\label{pitchdet}
%\subsection{ACF}
%\label{acf}
%The autocorrelation function ACF of the speech signal, or of a
%pre-processed version of it, is a traditional source of periodic
%candidates. ACF quantify gauge of similarity between samples that are
%shifted over some lag. The
%ACF of $K$ samples $K<n$, may then be defined as:
%\begin{equation}
%R_{i,k} = \sum_{j=m}^{m+n-k-1} s_j s_{j+k}, \qquad k=[0,K-1];\qquad m=iz;\qquad i=[0,M-1],
%\label{rovnice-acf}   % muzes dat label i rovnici !
%% kdybys chtel necislovanou, tak das misto equation displaymath
%\end{equation}
%where $i$ is the frame index for $M$ frames, and $k$ is the lag. 

%ACF can be applied not only at speech signal, but also at error signal
%of LPC analysis. The property of LPC error signal is that it does not
%contain information about formants, but only about fundamental
%frequency. This can sometimes bring better pitch estimation. 

%\subsection{NCCF}
%Normalized cross correlation function NCCF can work as pitch detector,
%as well. Let $s_m$ be a non-zero sampled speech signal with zero mean, and
%let $w,M,K$ and $n$ be as defined above. The NCCF $\phi_{i,k}$ at lag $k$
%and analysis 
%frame $i$ is:
%\begin{equation}
%\phi_{i,k} = \frac{\sum_{j=m}^{m+n-1} s_j s_{j+k}} {\sqrt{e_m
%e_{m+k}}},\qquad  k=[0,K-1];\qquad m=iz;\qquad i=[0,M-1],  
%\end{equation}
%where
%\begin{equation}
%e_j = \sum_{l=j}^{j+n-1} s_l^{2}.  
%\end{equation}
%Note that NCCF take on the values between -1 to 1.

%\subsection{Cepstrum}
%Related to the ACF is the $cepstrum$ as described originally in
%\cite{bogart} and applied to pitch estimation in \cite{noll}. The cepstrum is defined as the
%inverse Fourier transform of the short-time log magnitude spectrum.
%Coefficients of cepstral analysis can be obtained as:
%\begin{equation}
%c(m) = \mathcal{F}^{-1} [ \ln | \mathcal{F}(s(n)) |^{2} ].
%\end{equation}
%\subsection{Lag detection}
%According to above, ACF (or NCCF or cepstrum) is computed for each
%frame of input signal. The lag is obtained by looking for the maximum
%value of ACF (NCCF or cepstrum) in allowed interval for each frame. If
%this maximum exceeds some a-priori defined threshold, we mark this
%frame voiced and vice-versa.
 % If this maximum is lower than threshold, the frame is declared unvoiced.

%%%%%%%%%%%%%%%%%%%%%%
\section{Pitch detector experiments}
All methods that can work as pitch detectors were used in the experiments. We
determined their ability to detect the pitch on about twenty Czech
words (two speakers). On the whole it can be said, that the best pitch
estimation is obtained using NCCF. It gives the biggest probability
that we find out the ``true'' pitch. One example is given on
Figure~\ref{fig:comp}. NCCF, ACF, cepstrum
and ACF of LPC-error signal are shown for  one frame of input speech signal. The correct value of
lag for this frame is around 90 samples. As it is shown in Figure~\ref{fig:comp}, the
best estimation of ``true'' pitch is obtained using NCCF, because of the biggest peak with
respect to other peaks of its function. The other detectors failed to estimate
the ``true'' pitch (caused by sub-harmonics of input signal).
\begin{figure}
\begin{center}
\epsfig{file=comp6789.eps,width=\linewidth,height=0.6\linewidth}
\caption{Pitch detectors and their output functions of
$117^{th}$ frame of input speech signal (two Czech words ``l\'{e}taj\'{\i}c\'{\i} prase''.)}
\label{fig:comp}
\end{center}
\end{figure}     

\subsection{Techniques for improving pitch estimation} 
As mentioned before, we are not able to achieve good pitch estimation using
uniquely pitch detectors. Therefore some other techniques are used that
 can improve this estimation. These techniques are applied at the
 sequence of lags (one lag refers to one frame of speech
 signal). First possibility is the median filtering of lags' sequence. By this filter we can remove some wrong estimation of pitch in frames. It can also repair some wrong determination of one or a few voiced or unvoiced frames in lags' sequence.
 Some problems can be caused by a small sampling frequency of speech
 signal. So an oversampling of the input signal (mostly 6 times) can bring better pitch estimation.

We have found out that estimating of voiced or unvoiced frame is not
so problematic. Problems are mostly caused by sub-harmonics of the ``true'' fundamental frequency in signal that are obtained after using some pitch detectors. These drawbacks cannot be removed by previous methods.
When ACF is computed (or other mentioned functions) we often find out
that the interesting interval contains two, three, or sometimes more
peaks, caused by sub-harmonics of the pitch. So if only one maximum of
ACF is looked for, some sub-harmonics of fundamental frequency could be determined instead of the ``true'' pitch, because it can have bigger value than the real fundamental frequency.
These drawbacks can be eliminated by using method which looks for optimal pitch path in lags' sequence. 


\subsection{Optimal pitch path detector}
This detector looks for the suitable paths of
lags in the input signal of $n$ frames. First of all, a matrix
$\mathbf{A}$ is given. This matrix  contains a
parameterization (ACF, NCCF, \ldots) for each frame in one row (so that
it has $n$ rows).  In each row, 4 peaks are found out and their
positions are recorded in matrix $\mathbf{M}$ ($n$ times $4$). The corresponding
values are stored in matrix $\mathbf{V}$ ($n$ times $4$). Next, the
unvoiced frames are detected: each element of  $\mathbf{M}$ is taken
and we determine if the following or the previous row of  $\mathbf{M}$
contains a similar value (in any column). So if for $i$-th frame any of
$m_{i,k}$ satisfies: 
\begin{equation}
m_{i,k}\in m_{i-1,m}\pm const,\qquad \forall{i,k}, \qquad m\in[1,4]
\end{equation}
or
\begin{equation}
m_{i,k}\in m_{i+1,m}\pm const,\qquad \forall{i,k},\qquad m\in[1,4],
\end{equation}
where $const$ is a constant, the $i$-th frame is declared voiced,
otherwise it is unvoiced.

The next step is seeking  all paths in \emph{voiced portions} of matrix
$\mathbf{M}$. A path is determined by its mean lag value stored in
vector  $\mathbf{b}$. This vector is initialized to empty. When
processing new row of $\mathbf{M}$, its entries are compared to
elements of  $\mathbf{b}$. If an entry $m_{i,k}$ lies closed enough to
an element $b_i$, it is clustered to $b_i$ and $b_i$ is updated using:
\begin{equation}
b_{i(new)}=\frac{b_{i(old)}+m_{i,k}}{2}.
\end{equation}   

If not, a new entry in $\mathbf{b}$ is created:
$\mathbf{b}=[\mathbf{b}~m_{i,k}]$. It is obvious that the length of
$\mathbf{b}$ is not a-priori known. A vector $\mathbf{c}$ associated
to $\mathbf{b}$ contains a sum of respective maxima values from the
matrix $\mathbf{V}$. This vector therefore contains a ``quality
measurement'' of pitch paths. At the end of a voiced portion, values
of $\mathbf{c}$ are normalized by path lengths and the optimal mean
lag $b_d$ is determined:  

\begin{equation}
d=\arg\max_i(\mathbf{c}),\qquad i\in[1,m],
\end{equation}
where $m$ is the number of candidate paths. The optimal path
associated with $b_d$ is extracted from $\mathbf{M}$.
Finally, a simple energy detector marks the ``unvoiced'' frames where
the energy falls below a pre-determined threshold.


\begin{figure}[tb]
\begin{center}
\epsfig{file=3pict.eps,width=\linewidth,height=0.5\linewidth}
\caption{ Estimation of fundamental frequency of two Czech
words ``l\'{e}taj\'{\i}c\'{\i} prase''.\newline
Upper panel:  Input signal (10781 samples, 8kHz, 133 frames).\newline
Middle panel: Pitch estimation using only NCCF.\newline
Lower panel : Estimation using optimal pitch path technique (applied
on NCCF).}
\label{fig:sig}
\end{center}
\end{figure}

The estimation of fundamental frequency of speech using
optimal pitch path detection in comparison with raw NCCF, can be seen
on Figure~\ref{fig:sig}. This method is likely to recognize voiced and unvoiced parts of speech successfully.

\section{Evaluation of results}
Optimal pitch path detection was tested on a reference database from
OGIvox\footnote{Thanks to Mike Bacon (OGI, Portland, Oregon) for the permission to
use it.} (Center for Spoken Language Understanding) that include
simultaneous speech and electroglottograph (EGG) data. The OGIvox
database contains a directory with signal
files and a directory with ``pitch ticks'' (obtained by EGG) associated
to these signal files.  We have created a script that processes one thousand of
signal and EGG files from OGIvox. 

First, the real pitch is computed from the ``ticks''
for each frame of signal files, whereas the pitch is determined as a
time period between the two closest ``ticks''. However it could happen
that a frame contains only one, or more than two ``pitch
ticks''. Therefore, we compute the pitch using ``ticks'' not only
from the current frame, but also by using two ``ticks'' from two neighboring frames. Then
time periods are determined and the mean value
represents the pitch of this frame.
  
Second, the pitch was computed by using
optimal pitch path detection for all files and results
were
statistically compared:\\
The error of detection of voiced frames in comparison with OGIvox
(1.000 signal files) is  22.5\%.\\
The error of detection of pitch in voiced frames is  9.6\%.\\ 
Comparison of results for one OGIvox signal file is shown on Figure~\ref{fig:vox}.     



% The script was created that process one thousand of signal files from
% OGIvox database and files with data from EGG


\begin{figure}[htb]
\begin{center}
\epsfig{file=OGIvox.eps,width=\linewidth,height=0.5\linewidth}
\caption{Estimation of fundamental frequency F0 on signal file from
OGIvox database:\newline
Upper panel:  Input signal (10880 samples, 16kHz, 67 frames).\newline
Middle panel: ``Real'' pitch computed from EGG.\newline
Lower panel : Estimation using optimal pitch path technique (applied
on NCCF).}
\label{fig:vox}
\end{center}
\end{figure}


\section{Conclusions}
We have tested several methods of improvement the  pitch detection. In
general the optimal pitch path detection gives the best results. The
biggest problems in pitch detection are caused by higher harmonics or
sub-harmonics of the fundamental frequency. Only optimal pitch path
detection of all mentioned techniques is able to find out the ``true''
fundamental frequency in speech signal. This method works with short
sections of speech signal (a few words), thus it is able to recognize
the change of pitch of a speaker not immediately, but after processing
of one section of speech signal. The disadvantage of this technique is
its higher complexity in comparison with other methods. The best pitch
detector, which can be used with the optimal pitch path technique, is
based on NCCF.

Optimal Pitch Path Detection was tested on Ogivox database (pitch
provided by EGG). Determining of ``true''pitch in voiced frames was
very good (error  9.6\% for computing over 1.000 signal files of
speech). In detection of voicing, the error was  22.5\%. However, a very simple detector of energy was used in the test, a
more sophistical detector should improve this figure.   
\bibliographystyle{plain}  
\begin{thebibliography}{99}        % seznam referenci, parametr funkce
                                   % bibtem je label, kterym se na clanek
                                   % ci knihu muzeme v texty odkazat.
\bibitem{gold} B. Gold and N. Morgan.  {\em Speech and Audio Signal Processing}, pages
214-227 and 415-430, New York, 1999.
%
\bibitem{talkin} D. Talkin.  A Robust Algorithm for Pitch Tracking (RAPT). In Kleijn,
W. B. and Paliwal, K. K. (Eds.), {\em Speech Coding and Synthesis}. New York:
Elseviever, 1995.
%
\bibitem{bogart}  B. P. Bogart, M. J. R. Healy, and J. W. Tukey, The quefrency
analysis of time series for echoes: Cepstrum, pseudo-autocovariance,
cross-cepstrum and shape tracking, in {\em Symphosium on Time Series
Analysis} 
(M. Rosenblatt, ed.), (New York), pp. 209-243, John Wiley and Sons, 1963.
%
%\bibitem{noll} A. M. Noll, Cepstrum pitch determination, {\em Journal
%of Acoustical society of
%America}, vol. 41, pp. 293-309, February 1967. 
%
\bibitem{rabiner} L. R. Rabiner, On the use of autocorrelation
analysis for pitch detection, {\em IEEE Trans. Acoust., Speech, Signal
Processing}, vol. ASSP-25, 
pp.24-33, February 1977
%
\bibitem{cernocky} J. Cernocky. {\em Speech Processing Using
Automatically Derived Segmental Units}, PhD Thesis, ESIEE, France, 1998.
\end{thebibliography}
 

\end{document}


