Mex Files – 2

February 7, 2010
So continuing from the previous post, (1), we shall see how to start writing Mex code, by considering the following simple example of a uniform quantizer. Setup is assumed ready and done.

First and foremost, the filename should be “function_name.c” and not a “.m”. Once compiled, its this function_name that you will call in your other simulation running codes. Instead of the usual includes, we now use the “mex.h” header file. Note that other header files also may work, as this example will present the usage of “math.h” for the round() function.

Then, instead of the standard void main() we now start with a special type of function called mexFunction() and it can be used as follows. Note that the mexFunction is a generic name given to all mex file codes, it’s not the name of the function you want to write. So the first few lines look like this

#include "mex.h"
#include "math.h"
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])

nlhs and nrhs are the number of arguments, and *plhs and *prhs are Matlab compatible pointer array references on the output (left) and input (right) side respectively. All this seems quite complicated at first, but it’s not once you actually write one code. Just one!

So, we now need to obtain the location of the data, which is passed on to the function during the call. This is done by using the function mxGetPr(prhs[i]). For example

double *X, *nbits, *Xmax;
X = mxGetPr(prhs[0]);
nbits = mxGetPr(prhs[1]);
Xmax = mxGetPr(prhs[2]);

As this indicates, the vector to be quantized to nbits (2nd input variable) is X, the first input variable; and the maximum quantization value is Xmax, the third input variable.

More information about the dimensions of the vector or matrix can be found by using functions like Xdim = (int)mxGetM(prhs[0]) for no. of rows and mxGetN() for columns.

In case you need to create any temporary variables, typically mxMalloc() is used. However, be sure to free the memory at the end of the program by mxFree(), but we will cover this in the next post. Now we need to allocate memory for the output arguments, and assign them to pointers. Note the usage of mxCreateDoubleMatrix().

double *y, *step;
plhs[0] = mxCreateDoubleMatrix(Xdim, 1, mxREAL);
y = mxGetPr(plhs[0]);
plhs[1] = mxCreateDoubleMatrix(1, 1, mxREAL);
step = mxGetPr(plhs[1]);

where our first output argument y is the quantized vector, and the second is the computed step-size (using nbits and Xmax). The easy part of this is, the function is always mxCreateDoubleMatrix() with changes in the dimensions. Indicating Real or Complex is done by using mxREAL or mxCOMPLEX.

Once this is done, the rest of the code is like any other C code using pointers. One word of caution would be to take care of the dimensions, not to confuse between rows and columns, as this could mess up your code and take a long time to debug.

Try it out, and notice the speed-up! There are many more points, but this post is too long already :) More on this, some time later. Although, at this point, the reader has sufficient knowledge to write simple mex codes on their own. Find the code here.


Symbolic Math Toolbox – Matlab

January 24, 2010
Your scientific calculator now does definite integration, differentiation, etc. Maybe higher and more complex graphing calculators can do indefinite stuff too! However, I just found this very interesting ability to use a math symbol, typically x, so far known to exist only in Mathematica. This is the Symbolic Math Toolbox, and its uses are numerous.

Although I am sure it requires a lot of development, specially compatibility of integrating with other data types that Matlab supports, for starters, it seems like a really nice feature. The example where I used it is like this. Consider a simple 3×3 symmetric matrix, whose non-diagonal corners are equal, and unknown. You want to obtain a value for this, such that the determinant of the matrix goes to 0. Manually, yes, its easy. Its a simple quadratic equation, and it can be solved for. However, now consider a 20×20 matrix :) Its terrible to compute its determinant, and then there is still an equation to solve. What symbolic math toolbox allows you to do is, define a variable – say z. In my case it would then be

syms z
Rxx = [1, 0.9, 0.8, ... z; ...; ...; z, ..., 0.8, 0.9, 1];
solve(det(Rxx));

and you have the possible solutions for this variable z. Note the usage of the function solve() which is typically used to solve for variable given a polynomial equation.

It also does all the standard integration, differentiation, and even Taylor’s series expansion :) and has a lot of applications. I want to now check it out for the basic transforms – Fourier, Laplace, Z, etc. Best to refer to the Matlab documentation on the toolbox for more information and examples on this. I am really loving this combination of the power of “indefinite” math along with powerful numeric functions.


MEX Files – 1

December 23, 2009
MEX files basically are “Matlab EXecutable” files. As we know, by default Matlab is an interpreted language, and simulation happens by reading instruction by instruction. The MEX files are one option, to write code in a C-like fashion, and then generate an executable (operating system and architecture dependent) which then runs at extremely fast speeds (one of the solutions to Running Long Simulations) So, as mentioned, the executable is always dependent on OS. We shall now split the following discussion, first for Linux, and then for Windows.

On Linux, once the Matlab installation is complete, and assuming you have some version of the GNU C compiler (if you dont, just install it) the job is very easy. The easy way would be to use invoke mex -setup and try to understand what it is actually asking. We would discuss the articles for building Mex files using system ANSI compiler (mexopts.sh). The setup copies the default matlabroot/bin/mexopts.sh to your local home directory. If you open this file, you will notice that it basically contains the name of the C compiler, and other parameters. Currently gcc-4.2 is supported by Matlab. Compilation can be done by calling mex filename.c which generates a filename.mexglx an executable file for Linux machines.

On Windows, you need to get the Visual C++ Express edition maybe 2008 and install it unless you already have a C / C++ compiler. Once you have that installed, running mex -setup asks whether mex should look for compilers. Ask it to, and it should find the relevant compiler. Choose the options, and you are ready to go! Once this is done, write the C-like code for the mex file, and then run mex filename.c from the Matlab command window. This for Windows, generates a filename.mexw32 which indicates its for 32-bit windows machines.

The files generated are the executables, and you are good to go! Just call them like you would for any m file, and they should work. More on how to write this “C-like” code, in the coming posts! For the more enthusiastic, here are the 2 main links where we learnt it from. Functions Reference and MEX-files Guide.


On Large Simulations in Matlab

December 1, 2009
There comes a time when you need to run a huge simulation (taking maybe days, but lets hope overnight) to finish. This post will talk about 3 main points, just briefly though. Will write in detail about one of them (MEX) sometime later.

Firstly, you should always know how much of the simulation is complete. Most of the simulations tend to have a general pattern like there is some initialization code, some section of iterated code (in a for / while loop) and then some ending (generally plots, or error computations). The middle section is which takes the most amount of time. Matlab gives something called a waitbar which basically is an cute visualization of how much of the process is complete. Its extremely easy to use in the basic form. Just initialize with the bar being empty,
wbarh = waitbar(0,'text_comes_here','Name','window_name');
and then fill up as
waitbar(itercnt/total_iterations, wbarh, 'updated_text_if_any');
Note that wbarh is the handle to this window that pops up. Matlab allows you to use sprintf(' '); and to put changing variables in the text to be inserted. Although at this point, its important to note that this WILL slow down the entire simulation by some time. So it may be wise not to update the bar at every iteration, but at every 10th or 100th or so. The not so beautiful way to do this would be just to print the iteration count to the command window! Again, every 100th or so.

In general, such simulations involve calling functions in the iterated middle section. Its a nice idea to have an estimate of which function is called most, and which function is eating all your time. The tool to do this is called the Profiler. It can be called up from the Matlab Editor -> Tools -> Open Profiler. Start profiling for a short number of iterations (since this is like a test run) and once it finishes, you will understand the rest. Its pretty self-explanatory! :) There is a command-line way to do this, but the previous way is much more easier.

Now you have caught the culprit function using the previous method, which is probably called billions of times, and thus takes up most of your computation time. Solution – Convert it to a MEX. This is a convenient extremely fast binary file compatible with Matlab, generated by writing C like code and using the “mex.h” header file. More on MEX files in other posts to come. The speed-up is specially significant if your culprit function had for / while loops and you will appreciate it. If your code still takes multiple days to complete, you have only one option – to somehow obtain more processing power, and combine them using MATLAB’s Distributed Computing Service / Engine. :)


A Meeting of Multiple Sensors

November 26, 2009
Imagine that there are temperature sensors distributed in campus. Wouldn’t it be really nice if these sensors somehow spoke with each other, and finally came to an agreement settling upon a final value to give you a value as “the campus temperature!” The notion of Consensus Algorithms in Wireless Sensor Networks is exactly this.

Now you would wonder whether it is feasible for nodes far apart to be talking to each other. The best part of this algorithm is that they do not need to! As long as there are a “sufficient” number of neighbours, the averaging of the estimated parameter happens, and one reaches convergence. An information theory like approach may be followed to obtain bounds!

The process is really simple and is closely related to Graph Theory. Consider 1 node (a sensor). At any time instant, all the neighbours of this node, broadcast their values to this node. This sensor at the next time iteration uses the data received from all its neighbours and its own previously sensed value to generate an estimate of the parameter.

It is very easy to show, that all the sensors converge to a value, which is equal to the average of the initial estimate in the ideal situation. But in practical cases we are faced with issues like limited bandwidth and power, failure of the communication system, possible introduction of directed graph (non-symmetric) which lead to faulty data transmissions. Its interesting to show whether in such real-life cases too these sensors reach convergence or do they fall apart as a bunch of squabbling pirates :P


From Real to Complex to Vector Gaussians

November 13, 2009
Gaussian distributions are probably the most widely used distributions in mathematics and engineering. Though one strange aspect of them is that they have slightly different equations for the real and complex cases. This is an interesting problem, and has a really nice reasoning, which generally is not taught in classes. In an attempt to answer the why here goes…

All of us have definitely at some point of time seen this familiar real Gaussian distribution
p_x(x) = \frac{1}{\sqrt{2\pi \sigma^2}} e^{-\frac{x^2}{2\sigma^2}}

which changes to a real vector form as
p_x(\mathbf{x}) = \frac{1}{\sqrt{(2\pi)^N |\mathbf{C_x}|}} e^{-\frac{1}{2}\mathbf{x}^T \mathbf{C_x}^{-1}\mathbf{x}}

where x is a vector of Gaussian distributions x_1, x_2, \ldots, x_N with 0 mean and covariance matrix \mathbf{C_x}. This can be written directly under the assumption that the individual x_i are uncorrelated, and since uncorrelated gaussians are independent, a multiplication of the individual gaussian distributions can be carried out.

Further, there is a change when referring to complex distributions. This is due to the difference in the definition of the Covariance matrix itself, which can be now written as a covariance matrix of the real and imaginary parts \mathbf{C_z} or the covariance matrix generated by using the complex number directly as \mathbf{C_s} where \mathbf{z} = [\mathbf{x y}]^T and \mathbf{u} =  [\mathbf{u u^*}]^T are both column vectors of 2N size.

This gives a relation between \mathbf{C_z} = \frac{1}{2} \mathbf{T}^H \mathbf{C_s} \mathbf{T} where \mathbf{T} is a 2-D unitary matrix. This half factor is responsible for the disappearance of the 2 in the fraction, and |\mathbf{C_s}| = |\mathbf{C_u}|^2 is responsible for the removal of the square root. Thus the final Complex Guassian Multivariate distribution ends up (different from the real one) as

p_u(\mathbf{u}) = \frac{1}{(\pi)^N |\mathbf{C_u}|} e^{-\mathbf{u}^T \mathbf{C_u}^{-1}\mathbf{u}}

when \mathbf{u} is circulant complex random variable, i.e. the covariance of real and imaginary parts is same, and they are uncorrelated (generally satisfied in applications).

One last point, its important to note that independence implies uncorrelation, but uncorrelation need not imply independence except for the nice and widely used Gaussian case :)


Classification and Regression Trees – CART

October 29, 2009
One often finds that given a set of 2-class mixed data, a common problem is to separate them. Ofcourse, there are a huge number of optimal and sub-optimal ways to achieve this, but this post shall talk only about the CART method. The algorithm is pretty simple to understand, implement and its working complexity is low. Note that it can be actually used to separate data of any number of classes, but let us consider the simplest case (2-class problem).

We start with a set of questions we can ask the data so as to classify them. In a 2-D dataset (x,y), they could be as simple as x>0 or y>0 and so on. The obvious problem to do this manually is how would one select the questions, and in which order (note that, the solution is like an incomplete binary tree) do we ask them so as to be able to classify the fastest with a high accuracy.

Multiple splitting criteria are available, some of which could be minimum combined entropy of the child nodes, the minimum global entropy, or maximum likelihood, etc. But the concept in all is the same. In every step, we choose a question which gives 2 classes of which atleast 1 contains the dataset of mainly one class (this is the low entropy case mathematically). The ideal case is when it contains data of only one class, where we have 0 entropy.

It can be seen that the global entropy (of all leaf nodes) reduces as we increase the number of splits. However there has to be a limit, and the stopping criteria are defined pretty intuitively. They could be a fixed number of leaf nodes, or a threshold global entropy, or a threshold change in global entropy, or just based on how many splits are to be performed.

This technique is often used in speech recognition systems which suffer from insufficient training of triphones. So we cluster the triphones based on their linguistic properties like voiced/unvoiced/plosive/fricative/etc. (our questions in this case) Thus a similar model can be used for each of the triphones (around 6000 to cover all) which land in the same node after a CART analysis. This has been found to reduce the relative error by around 15%.


Two-Way Mismatch – A Pitch Detection Algorithm

October 12, 2009
Pitch Detection (F0 frequency) has been a big problem for many many years now. One of the solutions, proposed way back in 1993 was to use a Two-Way Mismatch algorithm. Its an excellent idea, and works much better and faster than the standard or even modified autocorrelation technique. The proposed method specifically works well for pitch tracking in music signals.

The working is extremely simple. Small segments of the time domain signal are analysed and their spectrum computed. A peak detection algorithm is run on this which obtains the amplitudes and frequencies (bins) of the strong harmonics seen in the spectrum. The important parameter here is the FFT size and the window length. This is because the frequency resolution and time resolution are dependent on this factor, as described in this earlier post on Formants and Harmonics.

Now, the pitch variation for that music signal or speech signal is generally known. Hence, a range of pitch values are chosen, and their harmonics are computed. These harmonics are are tried to match with the measured ones of the signal. The closer the match, the better the estimation of the pitch. This matching technique ensures that if a few peaks are missed in the signal, they will be omitted and penalised accordingly. Also extra peaks will be penalised.

This matching technique is performed in both ways. Matching the predicted harmonics with the measured partials and the other way round, measured partials with predicted harmonics. A weighting of these two errors is carried out, and the final Pitch estimate error is obtained. The global minimum is computed among the chosen range of pitch values, and this corresponds to the pitch frequency of that segment.

A smoothing (median filtering) may be carried out later in case of speech signals which generally tend to have a constant-pitch over small segments of time.


MS Word – Matlab Interface

October 2, 2009
This is what we use in our labs here at UPC. An interesting feature of Matlab to be able to insert code like text in Microsoft Word, and then execute it.

The idea is like this. Given a problem statement or objective, write your code in the word document, and execute it by pressing Ctrl+Enter. You see the output (of course as long as you dont have ; at the end of command) in blue, and the input in green. This helps in generating answer scripts automatically and there is no need to be wasting time in generating lab session reports! In the screenshot below, you see the things mentioned.

Matlab and Word interface - notebook

Matlab and Word interface - notebook

Yes, the picture is bad quality :( so I expect you would want to try it out yourself. Note that, you have the variables used in the document, now available in the Matlab variables list. You can do all your testing in the Matlab window itself, to simplify and check the working of your code or you can use the editor and write m-files for functions, which can then be invoked in the word document. All the standard stuff can be done. Images can be inserted by copying the Figure window and just pasting it back in the appropriate place in the Word document. Newer versions of Matlab do this automatically! :) (I don’t know how new though).

Starting from scratch: While creating the documents, you would just say notebook('filename'). The command is essentially notebook and this will open a word document. Once you are done setting all the questions, and giving hint codes etc. you can save and quit both Matlab and Word.

More Coding: To study and code again, the next time you open this document it will automatically start Matlab, thereby starting the automation server. The unfilled, blank copy can be given to students in document form, to complete and then just post back the doc file which contains the code, and the results. Its perfect for lab sessions, and maybe even for exams.

Found this to be an interesting feature :) which was never used before.

Other features include that you can be in the folder (or add to path) the common functions that you have created and need to use.


Sound Converter

September 25, 2009
I wanted to convert some large mp3 files to wav for processing yesterday, and here’s what I found. Its extremely good. The name is Sound Converter and is available on Ubuntu by doing just a sudo apt-get install soundconverter.

This simple tool supports MP3, WAV, OGG, FLAC and the AAC formats, which are the most commonly used audio formats. So next time you want to convert a file, and its huge enough making the use of http://media-convert.com/ tough, use this :)

Thats it.. small post this one.