segDecoder.c File Reference

Generic Viterbi-type decorder for segmental HMMs. More...

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "segCommon.h"
#include "segStdLib.h"
#include "segDecoder.h"

Data Structures
struct	node
	Node probability buffer storing SNPs and an ENP. More...
struct	StartNodeParameter
	Parameters realising rolling-SNP-array mechanism. More...
Defines
#define	ALLOC_ERR   -2
	Function return value when memory allocation failed.
#define	ERROR   -1
	Function return value when an error occurred.
#define	NO_ERROR   0
	Function return value when the function was executed successfully.
#define	PERMIT_BOTH   0x03
	Status for nodes that can be both start and end nodes (assigned by pre-cost partition).
#define	PERMIT_START   0x02
	Status for nodes that can be only a start node (assigned by pre-cost partition).
#define	PERMIT_END   0x01
	Status for nodes that can be only an end node (assigned by pre-cost partition).
#define	NO_PERMIT   0x00
	Status for nodes that can be neither start nor end node (assigned by pre-cost partition).
Typedefs
typedef node	NODE
	Node probability buffer storing SNPs and an ENP.
typedef StartNodeParameter	SNP_PARAM
	Parameters realising rolling-SNP-array mechanism.
Functions
static int	firstPropagator (SEG_DP_ITEM **dpMat, NODE **prob, int t, SEG_SYNTAX_ITEM *nodeList, int breakPt, int maxDur, int numStates)
	Calculate SNP and determine best state transition for the first time frame.
static int	propagator (SEG_DP_ITEM **dpMat, NODE **prob, int t, SEG_SYNTAX_ITEM *nodeList, int breakPt, int maxDur, int numStates)
	Calculate SNP and determine best state transition.
static int	selector (SEG_DP_ITEM **dpMat, NODE **prob, int t, int numVecs, int sT, int maxDur, int *breakPt, double **spData, SEG_SYNTAX *synt, SEG_DEC_PARAM *decParam)
	Calculate ENP and determine best segment duration.
static int	lastPropagator (SEG_DP_ITEM **dpMat, NODE **prob, int t, SEG_SYNTAX_ITEM *nodeList, int breakPt, int maxDur, int numStates)
	Calculate ENP and determine best segment duration for the last frame.
static double	lastSelector (SEG_DP_ITEM **dpm, int t, int numStates, NODE **prob, SEG_SYNTAX_ITEM *nodeList)
	Selector for the last frame.
static long	startNodeProb (NODE **prob, int probIdx, int state, SEG_SYNTAX_ITEM *nodeList, int breakPt, int maxDur)
	Compute start node probability (SNP).
static int	endNodeProb (NODE **prob, int *probIdx, int curTime, SEG_SYNTAX_ITEM *nodeList, int *breakPt, int maxDur, double **spData, int vecSize, int targetVecSize, int sT, SEG_DEC_PARAM *decParam)
	Compute end node probability (ENP).
static double	segOutputProb (SEG_STATE *state, double **data, int vecSize, int targetVecSize, double **map, int sTime, int eTime)
	Compute linear-segment output probability.
static SNP_PARAM *	initDecoder (int maxDur)
	Initialise decoder parameters.
static int *	snpIdxPtr ()
	Get index array to refer to SNP arrays.
static int	curSnpIdx ()
	Get an index at the current time.
static int	incSnpIdx ()
	Shunt (rotate) the index array for the next processing.
static SEG_DP_ITEM **	allocDpHistory (int numStates, int numVecs)
	Allocate a node matrix for storing DP paths in the trellis.
static NODE *	allocNode (int maxDur)
	Allocate a NODE variable (to a state) that stores SNPs and ENP.
static void	freeNode (NODE **node)
	Free memory space for a specified NODE variable.
static void	freeAllNode (NODE **node, int numStates)
	Free memory space for all allocated NODE variables.
static void	preCostPartition (SEG_DP_ITEM **dpMat, int numStates, int numFrames, SEG_SYNTAX_ITEM *nodeList, int *breakPoint, int maxDur)
	Pre-cost partitioning for valid start and end nodes in the trellis.
static void	firstBackPropagation (SEG_DP_ITEM **dpMat, int numStates, SEG_SYNTAX_ITEM *nodeList, int t)
	Set "possible end-node" attribute to nodes at the end frame.
static void	backPropagation (SEG_DP_ITEM **dpMat, int numStates, SEG_SYNTAX_ITEM *nodeList, int breakPt, int t)
	Set "possible end-node" attribute to nodes in the trellis.
static void	finalBackPropagation (SEG_DP_ITEM **dpMat, int numStates, SEG_SYNTAX_ITEM *nodeList, int t)
	Set "possible end-node" attribute to nodes at the start frame.
static void	segDurExtension (SEG_DP_ITEM **dpMat, int numStates, SEG_SYNTAX_ITEM *nodeList, int *breakPoint, int maxDur, int t)
	Set "possible start-node" attribute to nodes in the trellis.
static int	compsnp (const void *node1, const void *node2)
	Compare the SNPs of two states at the current time frame.
static int	compenp (const void *node1, const void *node2)
	Compare the ENPs of two states at the current time frame.
static void	prunStartNode (NODE **node, SEG_SYNTAX *syntax, SEG_DEC_PARAM *decParam)
	Start node pruning.
static void	prunEndNode (NODE **node, SEG_SYNTAX *syntax, SEG_DEC_PARAM *decParam)
	End node pruning.
double	segViterbiDecoder (SEG_DP_ITEM ***dpHist, SEG_SYNTAX *synt, double **spData, int *breakPt, int sT, int eT, int maxDur, SEG_DEC_PARAM *decParam)
	Generic Viterbi-type decorder for segmental HMMs.
int	segFreeDecoder (SEG_DP_ITEM **dpHist, int numStates)
	Free memory space storing all the paths in the trellis.
Variables
static SNP_PARAM	snpParam = {NULL,NULL,0,0}

---

Detailed Description

Generic Viterbi-type decorder for segmental HMMs.

Date:

09.06.2006, 21.06.2007 (revised)

Author:

Yoshinori Shiga @ CVSSP, University of Surrey

Note:

Introducing a concept of start and end node to M Russell & P Jackson's SEGVit ver.3 has achieved computationally- efficient decoding with effective pruning for segmental HMMs. This makes it possible to perform embedded recognition using context-sensitive (triphone) models, within a resonable time. A token-passing-style algorithm has been applied to reduce memory used.

Abbrev - SN: start node, EN: end node, SNP: start-node probability, ENP: end-node probability

Revision

---

Function Documentation

static SEG_DP_ITEM ** allocDpHistory	(	int	numStates,
		int	numVecs
	)			[static]

Allocate a node matrix for storing DP paths in the trellis.

Parameters:

[in]	numStates	Number of states
[in]	numVecs	Number of frames

Return values:

	NULL	Memory allocation error
	Otherwise	Pointer to the allocated paths history matrix

static NODE * allocNode

(

int

maxDur

)

[static]

Allocate a NODE variable (to a state) that stores SNPs and ENP.

Parameters:

[in]

maxDur

Maximal segment-duration

Returns:

Pointer to the allocated structure variable

static void backPropagation	(	SEG_DP_ITEM **	dpMat,
		int	numStates,
		SEG_SYNTAX_ITEM *	nodeList,
		int	breakPt,
		int	t
	)			[static]

Set "possible end-node" attribute to nodes in the trellis.

Parameters:

[in,out]	dpMat	Paths in the trellis for back-tracing
[in]	numStates	Number of states
[in]	nodeList	Node list in the syntax
[in]	breakPt	Break point array
[in]	t	Time (frame #)

Note:

This function attributes PERMIT_END to nodes that can be end nodes.

static int compenp	(	const void *	node1,
		const void *	node2
	)			[static]

Compare the ENPs of two states at the current time frame.

Parameters:

[in]	node1	Pointer to SNPs and ENP buffer
[in]	node2	Pointer to SNPs and ENP buffer

Note:

This function compares the two ENPs; and returns 1 if node1's ENP is greater than node2's ENP, -1 if node1's ENP is less than node2's ENP, and 0 if node1's ENP is equal to node2's ENP. This function is used for function qsort() to sort nodes in order of node score.

static int compsnp	(	const void *	node1,
		const void *	node2
	)			[static]

Compare the SNPs of two states at the current time frame.

Parameters:

[in]	node1	Pointer to SNPs and ENP buffer
[in]	node2	Pointer to SNPs and ENP buffer

Note:

This function compares the two SNPs; and returns 1 if node1's SNP is greater than node2's SNP, -1 if node1's SNP is less than node2's SNP, and 0 if node1's SNP is equal to node2's SNP. This function is used for function qsort() to sort nodes in order of node score.

Function curSnpIdx() is called internally.

See also:

curSnpIdx()

static int curSnpIdx

(

)

[static]

Get an index at the current time.

Returns:

SNP arrays' index at the current time

static int endNodeProb	(	NODE **	prob,
		int *	probIdx,
		int	curTime,
		SEG_SYNTAX_ITEM *	nodeList,
		int *	breakPt,
		int	maxDur,
		double **	spData,
		int	vecSize,
		int	targetVecSize,
		int	sT,
		SEG_DEC_PARAM *	decParam
	)			[static]

Compute end node probability (ENP).

Parameters:

[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	probIdx	Indeces to retrieve the current SNP array
[in]	curTime	Current time (frame #)
[in]	nodeList	Node list in the syntax
[in]	breakPt	Break point array
[in]	maxDur	Maximal segment-duration
[in]	spData	Feature vectors of utterance
[in]	vecSize	Dimension of feature vectors
[in]	targetVecSize	Dimension of target/articulatory vectors
[in]	sT	Start time in spData
[in]	decParam	Decoder parameters

Returns:

Entry time into the current state (i.e., the start time of the current segment)

Note:

Functions segOutputProb() and freeNode() are called internally.

See also:

segOutputProb() and freeNode()

static void finalBackPropagation	(	SEG_DP_ITEM **	dpMat,
		int	numStates,
		SEG_SYNTAX_ITEM *	nodeList,
		int	t
	)			[static]

Set "possible end-node" attribute to nodes at the start frame.

Parameters:

[in,out]	dpMat	Paths in the trellis for back-tracing
[in]	numStates	Number of states
[in]	nodeList	Node list in the syntax
[in]	t	Time (frame #)

Note:

This function attributes PERMIT_END to emitting nodes with "possible start-node" attribute at the first frame of given feature vectors.

static void firstBackPropagation	(	SEG_DP_ITEM **	dpMat,
		int	numStates,
		SEG_SYNTAX_ITEM *	nodeList,
		int	t
	)			[static]

Set "possible end-node" attribute to nodes at the end frame.

Parameters:

[in,out]	dpMat	Paths in the trellis for back-tracing
[in]	numStates	Number of states
[in]	nodeList	Node list in the syntax
[in]	t	Time (frame #)

Note:

This function attributes PERMIT_END to final null-nodes with model exit probability greater than zero, at the final frame of given feature vectors.

static int firstPropagator	(	SEG_DP_ITEM **	dpMat,
		NODE **	prob,
		int	t,
		SEG_SYNTAX_ITEM *	nodeList,
		int	breakPt,
		int	maxDur,
		int	numStates
	)			[static]

Calculate SNP and determine best state transition for the first time frame.

Parameters:

[out]	dpMat	Paths in the trellis for back-tracing
[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	t	Cuurent time (frame #)
[in]	nodeList	Node list in syntax
[in]	breakPt	Break point at time t
[in]	maxDur	Maximal segment-duration
[in]	numStates	Number of states

Return values:

	ERROR	Memory allocation error
	NO_ERROR	Successfully executed

Note:

The following functions are called internally: allocNode() and startNodeProb().

See also:

allocNode() and startNodeProb()

static void freeAllNode	(	NODE **	node,
		int	numStates
	)			[static]

Free memory space for all allocated NODE variables.

Parameters:

[in]	node	SNPs and ENP storage for all states
[in]	numStates	Number of states

Returns:

No return value

Note:

The function calls freeNode() internally.

See also:

freeNode()

static void freeNode

(

NODE **

node

)

[static]

Free memory space for a specified NODE variable.

Parameters:

[in]

node

SNPs and ENP storage for a state

Returns:

No return value

static int incSnpIdx

(

)

[static]

Shunt (rotate) the index array for the next processing.

Returns:

SNP arrays' index at the current time

static SNP_PARAM * initDecoder

(

int

maxDur

)

[static]

Initialise decoder parameters.

Parameters:

[in]

maxDur

Maximal segment-duration

Return values:

	NULL	Memory allocation error
	otherwise	Pointer to the allocated array

Note:

The array is used to initialise SNP arrays.

static int lastPropagator	(	SEG_DP_ITEM **	dpMat,
		NODE **	prob,
		int	t,
		SEG_SYNTAX_ITEM *	nodeList,
		int	breakPt,
		int	maxDur,
		int	numStates
	)			[static]

Calculate ENP and determine best segment duration for the last frame.

Parameters:

[out]	dpMat	Paths in the trellis for back-tracing
[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	t	Cuurent time (frame #)
[in]	nodeList	Node list in the syntax
[in]	breakPt	Break point at time t
[in]	maxDur	Maximal segment-duration
[in]	numStates	Number of states in the syntax

Return values:

	ERROR	Memory allocation error
	NO_ERROR	Successfully executed

Note:

The following functions are called internally: curSnpIdx(), startNodeProb() and freeNode().

See also:

curSnpIdx(), startNodeProb() and freeNode()

static double lastSelector	(	SEG_DP_ITEM **	dpm,
		int	t,
		int	numStates,
		NODE **	prob,
		SEG_SYNTAX_ITEM *	nodeList
	)			[static]

Selector for the last frame.

Parameters:

[out]	dpm	Paths in the trellis for back-tracing
[in]	t	Cuurent time (frame #)
[in]	numStates	Number of states in the syntax
[in]	prob	Pointer array pointing SNPs and ENP buffer
[in]	nodeList	Node list in the syntax

Return values:

	ERROR	Memory allocation error
	NO_ERROR	Successfully executed

Note:

Function freeNode() is called internally.

See also:

freeNode()

static void preCostPartition	(	SEG_DP_ITEM **	dpMat,
		int	numStates,
		int	numFrames,
		SEG_SYNTAX_ITEM *	nodeList,
		int *	breakPoint,
		int	maxDur
	)			[static]

Pre-cost partitioning for valid start and end nodes in the trellis.

Parameters:

[in,out]	dpMat	Paths in the trellis for back-tracing
[in]	numStates	Number of states
[in]	numFrames	Number of frames of feature vectors
[in]	nodeList	Node list in the syntax
[in]	breakPoint	Break point array
[in]	maxDur	Maxmal segment-duration

Note:

This function traces all possible paths for "valid nodes" backward from the end of utterance, and labels those nodes as possible start node and/or possible end node. This is achieved by setting one of the values, "PERMIT_START", "PERMIT_END", "PERMIT_BOTH" (="PERMIT_START"|"PERMIT_END") or "NO_PERMIT", to "dpMat[state][time].dpStat".

The following functions are called internally: firstBackPropagation(), segDurExtension(), backPropagation() and finalBackPropagation().

See also:

firstBackPropagation(), segDurExtension(), backPropagation() and finalBackPropagation()

static int propagator	(	SEG_DP_ITEM **	dpMat,
		NODE **	prob,
		int	t,
		SEG_SYNTAX_ITEM *	nodeList,
		int	breakPt,
		int	maxDur,
		int	numStates
	)			[static]

Calculate SNP and determine best state transition.

Parameters:

[out]	dpMat	Paths in the trellis for back-tracing
[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	t	Cuurent time (frame #)
[in]	nodeList	Node list in syntax
[in]	breakPt	Break point at time t
[in]	maxDur	Maximal segment-duration
[in]	numStates	Number of states

Return values:

	ERROR	Memory allocation error
	NO_ERROR	Successfully executed

Note:

The following functions are called internally: curSnpIdx(), startNodeProb() and freeNode().

See also:

curSnpIdx(), startNodeProb() and freeNode()

static void prunEndNode	(	NODE **	node,
		SEG_SYNTAX *	syntax,
		SEG_DEC_PARAM *	decParam
	)			[static]

End node pruning.

Parameters:

[out]	node	Pointer array pointing SNPs and ENP buffer
[in]	syntax	Syntax
[in]	decParam	Decoder parameters

Note:

According to the value of "decParam->endNodePrun.method", the function applies N-best pruning and/or beam pruning to ENP for each state at the current time frame.

static void prunStartNode	(	NODE **	node,
		SEG_SYNTAX *	syntax,
		SEG_DEC_PARAM *	decParam
	)			[static]

Start node pruning.

Parameters:

[out]	node	Pointer array pointing SNPs and ENP buffer
[in]	syntax	Syntax
[in]	decParam	Decoder parameters

Note:

According to the value of "decParam->startNodePrun.method", the function applies N-best pruning and/or beam pruning to SNP for each state at the current time frame.

Function curSnpIdx() is called internally.

See also:

curSnpIdx()

static void segDurExtension	(	SEG_DP_ITEM **	dpMat,
		int	numStates,
		SEG_SYNTAX_ITEM *	nodeList,
		int *	breakPoint,
		int	maxDur,
		int	t
	)			[static]

Set "possible start-node" attribute to nodes in the trellis.

Parameters:

[in,out]	dpMat	Paths in the trellis for back-tracing
[in]	numStates	Number of states
[in]	nodeList	Node list in the syntax
[in]	breakPoint	Break point array
[in]	maxDur	Maxmal segment-duration
[in]	t	Time (frame #)

Note:

This function attributes PERMIT_START to emitting nodes that can be start nodes.

int segFreeDecoder	(	SEG_DP_ITEM **	dpHist,
		int	numStates
	)

Free memory space storing all the paths in the trellis.

Parameters:

[in]	dpHist	Paths in the trellis for back-tracing
[in]	numStates	Number of states

Return values:

NO_ERROR

Successful execution

Author:

Yoshinori Shiga @ CVSSP, University of Surrey

static double segOutputProb	(	SEG_STATE *	state,
		double **	data,
		int	vecSize,
		int	targetVecSize,
		double **	map,
		int	sTime,
		int	eTime
	)			[static]

Compute linear-segment output probability.

Parameters:

[in]	state	Model parameters for a state that produces the segment
[in]	data	Feature vectors (of the acoustic layer)
[in]	vecSize	Dimension of articulatory feature vectors
[in]	targetVecSize	Dimension of the acoustic feature vectors
[in]	map	Articulatory-acoustic linear-mapping matrix
[in]	sTime	Start time of the segment in data
[in]	eTime	End time of the segment in data

Returns:

Segment output probabilities

Note:

This function is for piecewise-linear-trajectory segmental HMMs.

double segViterbiDecoder	(	SEG_DP_ITEM ***	dpHist,
		SEG_SYNTAX *	synt,
		double **	spData,
		int *	breakPt,
		int	sT,
		int	eT,
		int	maxDur,
		SEG_DEC_PARAM *	decParam
	)

Generic Viterbi-type decorder for segmental HMMs.

Parameters:

[out]	dpHist	Paths in the trellis for back-tracing
[in]	synt	Syntax
[in]	spData	Acoustic feature vectors
[in]	breakPt	Break point attributes
[in]	sT	Utterance start time (frame #)
[in]	eT	Utterance end time (frame #)
[in]	maxDur	Maximal segment-duration (Dmax)
[in]	decParam	Decoder parameters

Return values:

	RTN_ERROR	Memory allocation error
	Otherwise	The best cost (minProb) computed

Author:

Yoshinori Shiga @ CVSSP, University of Surrey

Note:

The following functions are called internally: allocDpHistory(), initDecoder(), preCostPartition(), firstPropagator(), selector(), incSnpIdx(), propagator(), prunStartNode(), prunEndNode(), lastPropagator(), lastSelector(), and freeAllNode().

See also:

allocDpHistory(), initDecoder(), preCostPartition(), firstPropagator(), selector(), incSnpIdx(), propagator(), prunStartNode(), prunEndNode(), lastPropagator(), lastSelector() and freeAllNode().

static int selector	(	SEG_DP_ITEM **	dpMat,
		NODE **	prob,
		int	t,
		int	numVecs,
		int	sT,
		int	maxDur,
		int *	breakPt,
		double **	spData,
		SEG_SYNTAX *	synt,
		SEG_DEC_PARAM *	decParam
	)			[static]

Calculate ENP and determine best segment duration.

Parameters:

[out]	dpMat	Paths in the trellis for back-tracing
[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	t	Cuurent time (frame #)
[in]	numVecs	Number of observed feature vectors
[in]	sT	Start time (frame #) in spData
[in]	maxDur	Maximal segment-duration
[in]	breakPt	Break point array
[in]	spData	Feature vectors
[in]	synt	Syntax
[in]	decParam	Decoder parameters

Return values:

	ERROR	Memory allocation error
	NO_ERROR	Successfully executed

Note:

The function calls endNodeProb() internally.

See also:

endNodeProb()

static int * snpIdxPtr

(

)

[static]

Get index array to refer to SNP arrays.

Returns:

Pointer to index array

static long startNodeProb	(	NODE **	prob,
		int	probIdx,
		int	state,
		SEG_SYNTAX_ITEM *	nodeList,
		int	breakPt,
		int	maxDur
	)			[static]

Compute start node probability (SNP).

Parameters:

[out]	prob	Pointer array pointing SNPs and ENP buffer
[in]	probIdx	Index pointing current SNP element
[in]	state	State number
[in]	nodeList	Node list in the syntax
[in]	breakPt	Break point at time t
[in]	maxDur	Maximal segment-duration

Return values:

	ALLOC_ERR	Memory allocation error
	otherwise	The best path from a predessor to the current node

Note:

'State number' is a number representing the position of state in the concatenated syntax, not in the individual HMM.

Functions allocNode() and freeNode() are called internally.

See also:

allocNode() and freeNode()

---