# Implementation of a Tour Guide Robot System Using RFID Technology and Viterbi Algorithm-Based HMM for Speech Recognition

Authors: Neng-Sheng Pai; Hua-Jui Kuang; Ting-Yuan Chang; Ying-Che Kuo; Chun-Yuan Lai
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper applied speech recognition and RFID technologies to develop an omni-directional mobile robot into a robot with voice control and guide introduction functions. For speech recognition, the speech signals were captured by short-time processing. The speaker first recorded the isolated words for the robot to create speech database of specific speakers. After the speech pre-processing of this speech database, the feature parameters of cepstrum and delta-cepstrum were obtained using linear predictive coefficient (LPC). Then, the Hidden Markov Model (HMM) was used for model training of the speech database, and the Viterbi algorithm was used to find an optimal state sequence as the reference sample for speech recognition. The trained reference model was put into the industrial computer on the robot platform, and the user entered the isolated words to be tested. After processing by the same reference model and comparing with previous reference model, the path of the maximum total probability in various models found using the Viterbi algorithm in the recognition was the recognition result. Finally, the speech recognition and RFID systems were achieved in an actual environment to prove its feasibility and stability, and implemented into the omni-directional mobile robot.


---

## Body

## 1. Introduction

For speech recognition, the dissimilarity between the signal characteristic values and the characteristic values in the database was calculated in early stages to identify the minimum difference as the recognition result. However, this method has a problem of poor recognition effect due to different talking speeds. Afterwards, some scholars proposed the dynamic time warping (DTW) to improve the recognition effect [1, 2]. This method assumes two speech signal segments to be compared, and the short-time feature parameters of the two segments of speech are extracted, namely, separated into a string of frames to determine a group of parameters from each frame. The comparison between two segments of speech is indeed the comparison between two sequence feature parameters. The DTW can adjust the speech length to reduce the errors in the speech time span. In the recognition system following DTW, the Artificial Neural Network (ANN) and HMM algorithms were proposed.The ANN is a method often used in the artificial intelligence domain [3, 4]. The ANN does not need to know the mathematical model of the system in experimental data modeling and highly complex recognition of images, letters, or sound, so that it can replace system models. Knowing the type of outputs generated from the type of input could achieve good recognition effect after learning and repeated training. However, the ANN updates weights and bias iteratively, and the amount of calculation is large, so it consumes a lot of computer resources. The HMM uses probability model to describe the pronunciation in statistics [5–7]. A continuous state transition in Markov model can be regarded as the phonation of a short speech segment, namely, a string of connected HMM, which is the representative for segment of speech. The HMM is a method mostly used in speech recognition in recent years. This paper uses the HMM as the speech recognition core.


## 2. Hardware Design

The direction of the voice controlled guide type omnidirectional mobile robot is controlled by voice, and the robot has the RFID guide system and infrared image tracking and ultrasonic obstacle avoidance functions [8]. All of the proposed robot systems are configured with three subsystems; they are omnidirectional mobile robot side, computer side, and user side and shown in Figure 1. The Peripheral Interface Controller (PIC) microcontroller is the core on the omnidirectional mobile robot side; its main function includes signal process of peripheral devices and motor drive control for three wheels. The computer side uses an industrial computer processing speech recognition calculation, RFID guide system, and infrared image tracking. The user side uses a wireless headset and the RFID active tag as voice control equipments.Figure 1
Robot system hardware link.


## 3. HMM-Based Speech Recognition System

### 3.1. Preprocessing and Feature Parameter Extraction

The speech signals are preprocessed before speech recognition. The speech preprocessing contains sampling, frame, endpoint detection, preemphasis, and windowing. After the speech signal preprocessing, the characteristic feature parameters are identified for subsequent recognition calculation. In this paper, the Linear Predictive Coefficient (LPC) is used to deduce the cepstrum and delta-cepstrum as the most important feature parameters.The concept of linear prediction originates from that the amplitude of a sampling point is related to the amplitude of an adjacent sampling point during pronunciation. If the postsampling sequence of speech signals isS(n), the present sample of speech signal, that is, S(n), is the sample values of time n. If S^(n) is the predicted value of S(n), since there must be an error between the predicted value and the actual value, the predicted error can be expressed as e(n), as follows:
(1)e(n)=S(n)-S^(n)=S(n)-∑j=1l‍ajS(n-j),
where aj is the linear predictive coding and l is the order number of linear prediction. The coefficient aj is adjusted; as long as the squared error value of (1) is minimized, an optimal linear predictive coefficient aj can be obtained. The autocorrelation is determined before solving the linear predictive coefficient, and then the wanted linear predictive coefficient is obtained from the obtained autocorrelation using the Durbin algorithm.After determining the LPC, the cepstrum coefficient is deduced from the LPC [9]. The cepstrum coefficient separates the vocal tract model from excitation signal, and it can calculate the vocal tract parameters more precisely, so as to control the speech spectrum characteristics. The cepstrum coefficient c^j is determined from the linear predictive coefficient aj, where l is the order number of linear prediction, shown as follows:
(2)c^1=a1,c^j=aj+∑k=1j-1(1-kj)·ak·cj-k,(1<j≤l),c^j=∑k=1p(1-kj)·ak·cj-k,(j>l).
In a practical environment, the external noise influences the speech receiving, so that the tone in the spectrum is disturbed and distorted. The delta-cepstrum can reduce this noise effect. The delta-cepstrum parameter Δc^j(t) is shown in (3), where τ is the number of related former (-K) or latter frames (K). The cepstrum and delta-cepstrum parameters are to be used as feature parameters for recognition:
(3)Δc^j(t)=dc^j(t)dt=∑τ=-KKτ·c^j(t+τ)∑τ=-KKτ2.


### 3.2. HMM and Training Reference Model

#### 3.2.1. Build the Initial Model

The states and frames are separated averagely from the audio part of a segment of speech according to the preset HMM state number, and the feature vectors in the frames are used to calculate the mean valueMj and variance Varj, as shown in (4), where A is a state of HMM, i is the frame, j is the feature parameter, T is the number of frames in a state, and q is the number of feature vectors of cepstrum and delta-cepstrum. This paper uses 15 cepstrum and 15 delta-cepstrum as characteristic values, and q is 30:
(4)Mj=∑i=1TA(i,j)T,1≤j≤q,Varj=∑i=1T[A(i,j)]2T-(Mj)2,1≤j≤q.


#### 3.2.2. Viterbi Algorithm

In order to obtain the correct relationship between frame and HMM state more accurately, this paper uses a Gaussian probability function [10] to determine the similarity probability value of state and frame. A higher probability value indicates a higher similarity between the corresponding frame and the state, as shown in (5), where Gi(xT) is the probability value of each state corresponding to its frame, d is the feature vector dimension, xT is the feature vector, τRi is the mean value of states, Ri is the covariance matrix of the density function, and Gi(xT) is the probability value of similarity between the feature vector xT and state i:
(5)Gi(xT)=1(2π)d|Ri|exp⁡{-12(xT-τRi)TRi-1(xT-τRi)}.The HMM can be represented by(6)λ={π,A,B,S,V},
where S={s1,s2,…,sN} is the state sequence, N is the state number, V is the observed results, π={πi} is the initial state probability, A={aij} is the state transition probability, B={bj(Ot)} is the state observation probability, Ot={O1,O2,…,OT} is the observation sequence, and T is the sequence length.The Gaussian probability density function determines the probability value between frame and state. The HMM has many optional paths for state transition, and the path with the maximum total probability value among all possible paths is required to be found. This paper uses the Viterbi algorithm [11, 12], as shown in (7)–(10), where δi(i) is the probability of staying in state i at time t. ψt(i) is the probability of reaching state i at time t, p is the final probability value of the Viterbi algorithm, and ST is the optimal state sequence.Step 1.
Initializing(7)δt(i)=πibi(o1),1≤i≤N,ψt(i)=0.Step 2.
Recursing(8)δt+1(j)=max⁡1≤i≤N[δt(i)·aij]·bj(ot+1)ψt+1(j)=argmax⁡1≤i≤N[δt(i)·aij],1≤t≤T-1;1≤j≤N.Step 3.
Terminating(9)p=max⁡1≤i≤N[δt(i)],ST=argmax⁡1≤i≤N[δt(i)].Step 4.
Path backtracking(10)St=ψt+1(St+!),t=T-1,T-2,T-3,…1.


#### 3.2.3. Reevaluation

After the new relationship between state and frame is obtained using the Viterbi algorithm, the mean value and variance in old state are updated, and the Gaussian density function is used to determine the updated probability between state and frame again. The new total probability value is obtained using the Viterbi algorithm. The update continues until the maximum total probability value is converged, and this is the reference model after training.


### 3.3. Speech Recognition

The needed commands are trained into models, which serve as reference database of speech recognition. The feature parameters are determined according to previous procedure during recognition. The reference models of database are compared using the Viterbi algorithm to determine the probability value of each model and find the optimal state sequence. The time warping of speech signals is solved automatically when corresponding to a sequence of frames to the state sequence. The key point in the speech training procedure is to identify the correlation between frame and state. The relationship between frame and state should be updated by continuous path backtracking of Viterbi, until the path with the maximum total probability is determined. The most important step in the recognition procedure is to compare the reference models of training and obtain the maximum total probability value in reference models.


## 3.1. Preprocessing and Feature Parameter Extraction

The speech signals are preprocessed before speech recognition. The speech preprocessing contains sampling, frame, endpoint detection, preemphasis, and windowing. After the speech signal preprocessing, the characteristic feature parameters are identified for subsequent recognition calculation. In this paper, the Linear Predictive Coefficient (LPC) is used to deduce the cepstrum and delta-cepstrum as the most important feature parameters.The concept of linear prediction originates from that the amplitude of a sampling point is related to the amplitude of an adjacent sampling point during pronunciation. If the postsampling sequence of speech signals isS(n), the present sample of speech signal, that is, S(n), is the sample values of time n. If S^(n) is the predicted value of S(n), since there must be an error between the predicted value and the actual value, the predicted error can be expressed as e(n), as follows:
(1)e(n)=S(n)-S^(n)=S(n)-∑j=1l‍ajS(n-j),
where aj is the linear predictive coding and l is the order number of linear prediction. The coefficient aj is adjusted; as long as the squared error value of (1) is minimized, an optimal linear predictive coefficient aj can be obtained. The autocorrelation is determined before solving the linear predictive coefficient, and then the wanted linear predictive coefficient is obtained from the obtained autocorrelation using the Durbin algorithm.After determining the LPC, the cepstrum coefficient is deduced from the LPC [9]. The cepstrum coefficient separates the vocal tract model from excitation signal, and it can calculate the vocal tract parameters more precisely, so as to control the speech spectrum characteristics. The cepstrum coefficient c^j is determined from the linear predictive coefficient aj, where l is the order number of linear prediction, shown as follows:
(2)c^1=a1,c^j=aj+∑k=1j-1(1-kj)·ak·cj-k,(1<j≤l),c^j=∑k=1p(1-kj)·ak·cj-k,(j>l).
In a practical environment, the external noise influences the speech receiving, so that the tone in the spectrum is disturbed and distorted. The delta-cepstrum can reduce this noise effect. The delta-cepstrum parameter Δc^j(t) is shown in (3), where τ is the number of related former (-K) or latter frames (K). The cepstrum and delta-cepstrum parameters are to be used as feature parameters for recognition:
(3)Δc^j(t)=dc^j(t)dt=∑τ=-KKτ·c^j(t+τ)∑τ=-KKτ2.


## 3.2. HMM and Training Reference Model

### 3.2.1. Build the Initial Model

The states and frames are separated averagely from the audio part of a segment of speech according to the preset HMM state number, and the feature vectors in the frames are used to calculate the mean valueMj and variance Varj, as shown in (4), where A is a state of HMM, i is the frame, j is the feature parameter, T is the number of frames in a state, and q is the number of feature vectors of cepstrum and delta-cepstrum. This paper uses 15 cepstrum and 15 delta-cepstrum as characteristic values, and q is 30:
(4)Mj=∑i=1TA(i,j)T,1≤j≤q,Varj=∑i=1T[A(i,j)]2T-(Mj)2,1≤j≤q.


### 3.2.2. Viterbi Algorithm

In order to obtain the correct relationship between frame and HMM state more accurately, this paper uses a Gaussian probability function [10] to determine the similarity probability value of state and frame. A higher probability value indicates a higher similarity between the corresponding frame and the state, as shown in (5), where Gi(xT) is the probability value of each state corresponding to its frame, d is the feature vector dimension, xT is the feature vector, τRi is the mean value of states, Ri is the covariance matrix of the density function, and Gi(xT) is the probability value of similarity between the feature vector xT and state i:
(5)Gi(xT)=1(2π)d|Ri|exp⁡{-12(xT-τRi)TRi-1(xT-τRi)}.The HMM can be represented by(6)λ={π,A,B,S,V},
where S={s1,s2,…,sN} is the state sequence, N is the state number, V is the observed results, π={πi} is the initial state probability, A={aij} is the state transition probability, B={bj(Ot)} is the state observation probability, Ot={O1,O2,…,OT} is the observation sequence, and T is the sequence length.The Gaussian probability density function determines the probability value between frame and state. The HMM has many optional paths for state transition, and the path with the maximum total probability value among all possible paths is required to be found. This paper uses the Viterbi algorithm [11, 12], as shown in (7)–(10), where δi(i) is the probability of staying in state i at time t. ψt(i) is the probability of reaching state i at time t, p is the final probability value of the Viterbi algorithm, and ST is the optimal state sequence.Step 1.
Initializing(7)δt(i)=πibi(o1),1≤i≤N,ψt(i)=0.Step 2.
Recursing(8)δt+1(j)=max⁡1≤i≤N[δt(i)·aij]·bj(ot+1)ψt+1(j)=argmax⁡1≤i≤N[δt(i)·aij],1≤t≤T-1;1≤j≤N.Step 3.
Terminating(9)p=max⁡1≤i≤N[δt(i)],ST=argmax⁡1≤i≤N[δt(i)].Step 4.
Path backtracking(10)St=ψt+1(St+!),t=T-1,T-2,T-3,…1.


### 3.2.3. Reevaluation

After the new relationship between state and frame is obtained using the Viterbi algorithm, the mean value and variance in old state are updated, and the Gaussian density function is used to determine the updated probability between state and frame again. The new total probability value is obtained using the Viterbi algorithm. The update continues until the maximum total probability value is converged, and this is the reference model after training.


## 3.2.1. Build the Initial Model

The states and frames are separated averagely from the audio part of a segment of speech according to the preset HMM state number, and the feature vectors in the frames are used to calculate the mean valueMj and variance Varj, as shown in (4), where A is a state of HMM, i is the frame, j is the feature parameter, T is the number of frames in a state, and q is the number of feature vectors of cepstrum and delta-cepstrum. This paper uses 15 cepstrum and 15 delta-cepstrum as characteristic values, and q is 30:
(4)Mj=∑i=1TA(i,j)T,1≤j≤q,Varj=∑i=1T[A(i,j)]2T-(Mj)2,1≤j≤q.


## 3.2.2. Viterbi Algorithm

In order to obtain the correct relationship between frame and HMM state more accurately, this paper uses a Gaussian probability function [10] to determine the similarity probability value of state and frame. A higher probability value indicates a higher similarity between the corresponding frame and the state, as shown in (5), where Gi(xT) is the probability value of each state corresponding to its frame, d is the feature vector dimension, xT is the feature vector, τRi is the mean value of states, Ri is the covariance matrix of the density function, and Gi(xT) is the probability value of similarity between the feature vector xT and state i:
(5)Gi(xT)=1(2π)d|Ri|exp⁡{-12(xT-τRi)TRi-1(xT-τRi)}.The HMM can be represented by(6)λ={π,A,B,S,V},
where S={s1,s2,…,sN} is the state sequence, N is the state number, V is the observed results, π={πi} is the initial state probability, A={aij} is the state transition probability, B={bj(Ot)} is the state observation probability, Ot={O1,O2,…,OT} is the observation sequence, and T is the sequence length.The Gaussian probability density function determines the probability value between frame and state. The HMM has many optional paths for state transition, and the path with the maximum total probability value among all possible paths is required to be found. This paper uses the Viterbi algorithm [11, 12], as shown in (7)–(10), where δi(i) is the probability of staying in state i at time t. ψt(i) is the probability of reaching state i at time t, p is the final probability value of the Viterbi algorithm, and ST is the optimal state sequence.Step 1.
Initializing(7)δt(i)=πibi(o1),1≤i≤N,ψt(i)=0.Step 2.
Recursing(8)δt+1(j)=max⁡1≤i≤N[δt(i)·aij]·bj(ot+1)ψt+1(j)=argmax⁡1≤i≤N[δt(i)·aij],1≤t≤T-1;1≤j≤N.Step 3.
Terminating(9)p=max⁡1≤i≤N[δt(i)],ST=argmax⁡1≤i≤N[δt(i)].Step 4.
Path backtracking(10)St=ψt+1(St+!),t=T-1,T-2,T-3,…1.


## 3.2.3. Reevaluation

After the new relationship between state and frame is obtained using the Viterbi algorithm, the mean value and variance in old state are updated, and the Gaussian density function is used to determine the updated probability between state and frame again. The new total probability value is obtained using the Viterbi algorithm. The update continues until the maximum total probability value is converged, and this is the reference model after training.


## 3.3. Speech Recognition

The needed commands are trained into models, which serve as reference database of speech recognition. The feature parameters are determined according to previous procedure during recognition. The reference models of database are compared using the Viterbi algorithm to determine the probability value of each model and find the optimal state sequence. The time warping of speech signals is solved automatically when corresponding to a sequence of frames to the state sequence. The key point in the speech training procedure is to identify the correlation between frame and state. The relationship between frame and state should be updated by continuous path backtracking of Viterbi, until the path with the maximum total probability is determined. The most important step in the recognition procedure is to compare the reference models of training and obtain the maximum total probability value in reference models.


## 4. Experiment Results

Figure2 shows the system operation flow of the voice controlled guide type omnidirectional mobile robot. In the RFID guide system, the Reader captures Tag data and then attaches environmental information to the Tags of different ID codes or starts up the speech function. Figure 3 shows the picture of the proposed omnidirectional mobile robot.Figure 2
System operation flow of voice controlled guide type omnidirectional mobile robot.Figure 3
Omnidirectional mobile robot.We place the robot in the actual environment and test various moving actions (forward, backward, turn left, turn right, stop, and turn back). The voice control of speaker dependent and speaker independent are tested by five users, respectively, and the experimental results of speech recognition rates are shown in Table1. Figure 4 shows the experiment of the user using speech to control the robot to move forward and turn left. Figure 5 shows the user using speech to control the robot to move forward, receiving the Tag of the classroom when passing by the classroom, the user can use Yes or No to choose whether accessing detailed information on the site. The site is introduced in the video format, so that the user can get acquainted with the environment quickly.Table 1
Recognition rates for the speaker dependent and speaker independent.
Speaker dependent
Recognition rates
Chun-Yuan
96.7%
Jian-Min
93.3%
Yi-Chung
90%
Wei
96.7%
Hung-Hui
93.3%
Average recognition rates
94%
Speaker independent
Recognition rates
Jason
66.7%
Ian
73.3%
Andy
90%
Momo
83.3%
Apple
50%
Average recognition rates
74.7%User using speech to control robot to move forward and turn left. (a) User commands robot to move forward. (b) User commands robot to stop. (c) User commands robot to turn left. (d) Robot turns left and moves on.
(a)
(b)
(c)
(d)Robot guide experiment. (a) User commands robot to move forward. (b) Robot detects tag and asks user whether he needs any introduction to the place or not. (c) User says YES. (d) Robot plays video.
(a)
(b)
(c)
(d)


## 5. Conclusions

This paper used the HMM-based speech recognition method to complete a voice controlled guide type omnidirectional mobile robot. The first convenience of voice control is that the operation does not require manual operation, which makes the robot more user-friendly. The guide system based on RFID technology enables the users to know the information of an unfamiliar environment quickly. Finally, the robot movement experiment and the robot guide system experiment proved the feasibility and stability of this voice controlled guide type omnidirectional mobile robot.



---

*Source: 262791-2014-03-24.xml*