annotate dsp/segmentation/cluster_melt.c @ 298:255e431ae3d4

* Key detector: when returning key strengths, use the peak value of the
  three underlying chromagram correlations (from 36-bin chromagram)
  corresponding to each key, instead of the mean.
  Rationale: This is the same method as used when returning the key value,
  and it's nice to have the same results in both returned value and plot.
  The peak performed better than the sum with a simple test set of triads,
  so it seems reasonable to change the plot to match the key output rather
  than the other way around.

* FFT: kiss_fftr returns only the non-conjugate bins, synthesise the rest
  rather than leaving them (perhaps dangerously) undefined.  Fixes an
  uninitialised data error in chromagram that could cause garbage results
  from key detector.

* Constant Q: remove precalculated values again, I reckon they're not
  proving such a good tradeoff.

/*
 *  cluster.c
 *  cluster_melt
 *
 *  Created by Mark Levy on 21/02/2006.
 *  Copyright 2006 Centre for Digital Music, Queen Mary, University of London. All rights reserved.
 *
 */

#include <stdlib.h>

#include "cluster_melt.h"

#define DEFAULT_LAMBDA 0.02;
#define DEFAULT_LIMIT 20;

double kldist(double* a, double* b, int n) {
	/* NB assume that all a[i], b[i] are non-negative
	because a, b represent probability distributions */
	double q, d;
	int i;
	
	d = 0;
	for (i = 0; i < n; i++)
	{
		q = (a[i] + b[i]) / 2.0;
		if (q > 0)
		{
			if (a[i] > 0)
				d += a[i] * log(a[i] / q);
			if (b[i] > 0)
				d += b[i] * log(b[i] / q);
		}
	}
	return d;		
}	

void cluster_melt(double *h, int m, int n, double *Bsched, int t, int k, int l, int *c) {
	double lambda, sum, beta, logsumexp, maxlp;
	int i, j, a, b, b0, b1, limit, B, it, maxiter, maxiter0, maxiter1;
	double** cl;	/* reference histograms for each cluster */
	int** nc;	/* neighbour counts for each histogram */
	double** lp;	/* soft assignment probs for each histogram */
	int* oldc;	/* previous hard assignments (to check convergence) */
	
	/* NB h is passed as a 1d row major array */
	
	/* parameter values */
	lambda = DEFAULT_LAMBDA;
	if (l > 0)
		limit = l;
	else
		limit = DEFAULT_LIMIT;		/* use default if no valid neighbourhood limit supplied */
	B = 2 * limit + 1;
	maxiter0 = 20;	/* number of iterations at initial temperature */
	maxiter1 = 5;	/* number of iterations at subsequent temperatures */
	
	/* allocate memory */	
	cl = (double**) malloc(k*sizeof(double*));
	for (i= 0; i < k; i++)
		cl[i] = (double*) malloc(m*sizeof(double));
	
	nc = (int**) malloc(n*sizeof(int*));
	for (i= 0; i < n; i++)
		nc[i] = (int*) malloc(k*sizeof(int));
	
	lp = (double**) malloc(n*sizeof(double*));
	for (i= 0; i < n; i++)
		lp[i] = (double*) malloc(k*sizeof(double));
	
	oldc = (int*) malloc(n * sizeof(int));
	
	/* initialise */
	for (i = 0; i < k; i++)
	{
		sum = 0;
		for (j = 0; j < m; j++)
		{
			cl[i][j] = rand();	/* random initial reference histograms */
			sum += cl[i][j] * cl[i][j];
		}
		sum = sqrt(sum);
		for (j = 0; j < m; j++)
		{
			cl[i][j] /= sum;	/* normalise */
		}
	}	
	//print_array(cl, k, m);
	
	for (i = 0; i < n; i++)
		c[i] = 1;	/* initially assign all histograms to cluster 1 */
	
	for (a = 0; a < t; a++)
	{
		beta = Bsched[a];
		
		if (a == 0)
			maxiter = maxiter0;
		else
			maxiter = maxiter1;
		
		for (it = 0; it < maxiter; it++)
		{
			//if (it == maxiter - 1)
			//	mexPrintf("hasn't converged after %d iterations\n", maxiter);
			
			for (i = 0; i < n; i++)
			{
				/* save current hard assignments */
				oldc[i] = c[i];
				
				/* calculate soft assignment logprobs for each cluster */
				sum = 0;
				for (j = 0; j < k; j++)
				{
					lp[i][ j] = -beta * kldist(cl[j], &h[i*m], m);
					
					/* update matching neighbour counts for this histogram, based on current hard assignments */
					/* old version:
					nc[i][j] = 0;	
					if (i >= limit && i <= n - 1 - limit)
					{
							for (b = i - limit; b <= i + limit; b++)
							{
								if (c[b] == j+1)
									nc[i][j]++;
							}
							nc[i][j] = B - nc[i][j];
					}
					*/
					b0 = i - limit;
					if (b0 < 0)
						b0 = 0;
					b1 = i + limit;
					if (b1 >= n)
						b1 = n - 1;
					nc[i][j] = b1 - b0 + 1;		/* = B except at edges */
					for (b = b0; b <= b1; b++)
						if (c[b] == j+1)
							nc[i][j]--;
					
					sum += exp(lp[i][j]);
				}
				
				/* normalise responsibilities and add duration logprior */
				logsumexp = log(sum);
				for (j = 0; j < k; j++)
					lp[i][j] -= logsumexp + lambda * nc[i][j];				
			}
			//print_array(lp, n, k);
			/*
			for (i = 0; i < n; i++)
			{
				 for (j = 0; j < k; j++)
					 mexPrintf("%d ", nc[i][j]);
				 mexPrintf("\n");
			} 
			*/
			
			
			/* update the assignments now that we know the duration priors
			based on the current assignments */
			for (i = 0; i < n; i++)
			{
				maxlp = lp[i][0];
				c[i] = 1;
				for (j = 1; j < k; j++)
					if (lp[i][j] > maxlp)
					{
						maxlp = lp[i][j];
						c[i] = j+1;
					}
			}
				
			/* break if assignments haven't changed */
			i = 0;
			while (i < n && oldc[i] == c[i])
				i++;
			if (i == n)
				break;
			
			/* update reference histograms now we know new responsibilities */
			for (j = 0; j < k; j++)
			{
				for (b = 0; b < m; b++)
				{
					cl[j][b] = 0;
					for (i = 0; i < n; i++)
					{
						cl[j][b] += exp(lp[i][j]) * h[i*m+b];
					}	
				}
				
				sum = 0;				
				for (i = 0; i < n; i++)
					sum += exp(lp[i][j]);
				for (b = 0; b < m; b++)
					cl[j][b] /= sum;	/* normalise */
			}	
			
			//print_array(cl, k, m);
			//mexPrintf("\n\n");
		}
	}
		
	/* free memory */
	for (i = 0; i < k; i++)
		free(cl[i]);
	free(cl);
	for (i = 0; i < n; i++)
		free(nc[i]);
	free(nc);
	for (i = 0; i < n; i++)
		free(lp[i]);
	free(lp);
	free(oldc);	
}