tag:blogger.com,1999:blog-83915064983104596782024-03-13T01:07:42.182-03:00C Plus / AddEmbedded systems programming / C, C++CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.comBlogger38125tag:blogger.com,1999:blog-8391506498310459678.post-27707448405951203162013-07-17T09:44:00.000-03:002013-07-17T09:44:15.341-03:00Configuration files in PythonThere is a very nice wrapper for libconfig for python, right here <a href="https://github.com/keimoon/python-libconfig">https://github.com/keimoon/python-libconfig</a><br />
(This is connected to the previous post on libconfig <a href="http://cplusadd.blogspot.ch/2012/02/trying-to-readwrite-configuration-files.html" target="_blank">here</a>)CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-88875908182623935412013-04-06T08:54:00.001-03:002013-04-17T10:01:22.999-03:00Why class balancing happens 'automatically' in AdaBoostThis is a very interesting characteristic of AdaBoost, that explains why, in general, it is not necessary to balance the initial weights during training for very skewed datasets.<br />
<br />
I will use the notation from the <a href="http://en.wikipedia.org/wiki/AdaBoost#The_algorithm_for_the_binary_classification_task" target="_blank">AdaBoost Wikipedia article</a>.<br />
<br />
First, assume that we have $N_p$ positive samples and $N_n$ negative samples, with $N_n >> N_p$, representing a skewed dataset. Let's name the ratio between the number of negative and positive samples as $K = \frac{N_n}{N_p}$.<br />
<br />
Now, assume that we are at the first iteration, and we have uniform weights $D_{t=1}(i) = \frac{1}{m}$ for all training samples. At the first iteration $t=1$ the goal is to find a weak learner<br />
<br />
<div style="text-align: center;">
$h_{t} = \underset{h_{t} \in \mathcal{H}}{\operatorname{argmax}} \; \left\vert 0.5 - \epsilon_{t}\right\vert$, with $\epsilon_{t} = \sum_{i=1}^{m} D_{t}(i)I(y_i \ne h_{t}(x_{i}))$</div>
<br />
since all weights are equal, $\epsilon_t$ can be expressed as $\epsilon_{t} = \sum_{i=1}^{m} I(y_i \ne h_{t}(x_{i}))$, so it is just the unweighted misclassification error.<br />
<br />
Now it comes the interesting part: assume that the weak learners in the weak learner pool are very weak, so that<i> the lowest misclassification error</i> $\epsilon_t$ <i>is achieved with a weak learner that classifies all samples as negatives</i>. (This seems unreasonable, but I have seen it happen frequently on skewed datasets).<br />
<br />
With this in mind, $\epsilon_1 = \frac{N_p}{N_p + N_n}$. With simple math we can compute the value of $\alpha_1=\frac{1}{2} \log \frac{1 - \epsilon_1}{\epsilon_1}$ and update the distribution $D$ for iteration $t=2$, obtaining<br />
<div style="text-align: center;">
$$\frac{D_{t=2}(+)}{D_{t=2}(-)} = \frac{N_n}{N_p} = K$$</div>
<div style="text-align: center;">
<br /></div>
<div style="text-align: left;">
<span style="text-align: center;">where $D_{t=2}(+)$ and </span><span style="text-align: center;">$D_{t=2}(-)$ are</span><span style="text-align: center;"> the weight of the positive and negative samples respectively.</span></div>
<div style="text-align: left;">
<span style="text-align: center;"><br /></span></div>
<div style="text-align: left;">
<span style="text-align: center;">This means that <b>the effect of the first weak learner was to balance the dataset, so that the sum of the positive weights equal the sum of the negative ones</b>. </span>Another equivalent interpretation is that the first weak learner just adds a constant to the predictive function, namely $-\alpha_1$ in this particular case.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
However, there are some differences w.r.t. balancing the weights initially:</div>
<div style="text-align: left;">
</div>
<ul>
<li>The first weak learner is 'wasted' and could be avoided.</li>
<li>If shrinkage is introduced, it is likely that many weak learners will be 'wasted'. Though 'wasted' is not very meaningful, because they would still be useful and help minimize training loss.</li>
<li>The fact that the first weak learner returns -1 for all training samples does not imply that it will also for any unseen new sample. The implications of this are hard to tell though.</li>
<li>I am assuming that a weak learner can return the same value for all training samples, which is the case for a decision stump, but it may not happen with other types of weak learners (e.g. svm)</li>
<li>.. I am pretty sure there are other differences</li>
</ul>
<div>
Cheers!</div>
CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-32799122064007470582013-02-19T13:12:00.002-03:002013-02-19T13:21:03.366-03:00C++11: compile-time lookup-table/array with constexprI've been trying a few of the new features of C++11, wondering how difficult it would be to create a compile-time self-populated array.<br />
<br />
Here there is a piece of code that creates an array that contains the values of <span style="font-family: Verdana, sans-serif; font-size: x-small;">sin(0.2 x) + cos(0.5 x)</span>, completely at compile-time, and then prints it in ascii form to stdout. The most tricky part is the one containing a variadic template, which computes a set of indices from 0 to N-1.<br />
<br />
You can see the output it produces <a href="http://liveworkspace.org/code/3JbAEA$0" target="_blank">here</a><br />
<br />
<textarea class="cpp" name="code">#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
/** Range generation,
* from http://stackoverflow.com/questions/13313980/populate-an-array-using-constexpr-at-compile-time **/
template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};
/** A table consisting of indexes and values,
* which will all be computed at compile-time **/
template<unsigned N>
struct Table
{
unsigned indexes[N];
double values[N];
static constexpr unsigned length = N;
};
template< typename LambdaType, unsigned... Is>
constexpr Table< sizeof...(Is) > TableGenerator(seq<Is...>, LambdaType evalFunc)
{
return {{ Is... }, { evalFunc(Is)... }};
}
template<unsigned N, typename LambdaType>
constexpr Table<n> TableGenerator( LambdaType evalFunc )
{
return TableGenerator(gen_seq<n>(), evalFunc);
}
/** Function that computes a value for each index **/
constexpr double myFunc( unsigned idx )
{
return sin(0.2 * idx) + cos(0.5*idx);
}
int main()
{
constexpr unsigned length = 100;
// create compile-time table
constexpr Table<length> table = TableGenerator<length>( myFunc );
// print values in vertical form, pretty-looking ;)
const double lineMult = 12;
const double lineOffset = 30;
for(auto v : table.values)
{
const unsigned numSpaces = (unsigned) ( lineOffset + v * lineMult + 0.5 );
std::cout << std::setfill(' ') << std::setw( numSpaces ) << "o" << std::endl;
}
std::cout << std::endl;
return 0;
}
</textarea><br />
<br />
<br />
<br />
<br />CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com2tag:blogger.com,1999:blog-8391506498310459678.post-78976554302861913182012-03-31T05:00:00.001-03:002012-04-03T12:50:22.643-03:00Wacom Pen & Touch CTH670 and LinuxI've just got a Wacom Pen & Touch tablet CTH670. I could not make it work straight away with Archlinux, but then found out that I had to follow the steps in this <a href="https://bbs.archlinux.org/viewtopic.php?id=131831" target="_blank">forum post</a> , which was originally meant to be for the <span style="background-color: #fcfdfe; color: #333333; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: left;">CTL-470/k.</span><br />
<span style="background-color: #fcfdfe; color: #333333; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: left;"><br /></span><br />
<span style="background-color: #fcfdfe; color: #333333; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: left;">In case the attachment in the linked forum post doesn't work, I am duplicating it <a href="https://docs.google.com/open?id=0B1skD429jLG9UzY3NFRsaGxTM0NMeFN3cW9GMnR1QQ" target="_blank">here</a>.</span><br />
<span style="background-color: #fcfdfe; color: #333333; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: left;"><br /></span><br />
<span style="background-color: #fcfdfe; color: #333333; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: left;">UPDATE: there seems to be a small issue with that version posted above. The version that works like a charm with my tablet is </span><span style="color: #333333; font-family: sans-serif; font-size: x-small;"><span style="line-height: 19px;">http://sourceforge.net/projects/linuxwacom/files/xf86-input-wacom/input-wacom/</span></span>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-20071545470287156592012-02-11T05:56:00.000-03:002012-02-11T06:00:55.815-03:00Trying to read/write configuration files?Loading, parsing and writing configuration files is generally not a trivial task. I found <a href="http://www.hyperrealm.com/libconfig/" target="_blank">this amazing library</a> recently, which does the job with a few C++ lines.<div>
<br /></div>
<div>
For example, if you have a configuration file such as:</div>
<div>
<br /></div>
<textarea name="code" class="cpp">
#----------------------------
# Example Configuration File
#---------------------------
#
application:
{
/* This section defines some settings for our
* main application window, such as size and
* position.
*/
window:
{
title = "My Application";
size = { /* width */ w = 640; /* height */ h = 480; };
pos = { x = 350; y = 250; };
};
a = 5;
b = 6;
}
</textarea>
Fields can be easily read with something as simple as:</div>
<div>
<br /></div>
<textarea name="code" class="cpp">
#include <libconfig.hh>
#include <iostream>
int main()
{
libconfig::Config cfg;
cfg.readFile("test.cfg");
int s = cfg.lookup("application.window.pos.x");
std::cout << "X Position: " << s << std::endl;
return 0;
}
</textarea>
<div>
<br /></div>
<div>
<br /></div>
<div>
A major advantage is that it is possible to define groups of configuration parameters, as well as arrays. The library is very well documented and it is very easy to adopt it to existing code.</div>
CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-72819432002843838402012-01-29T07:18:00.003-03:002012-01-29T07:35:45.785-03:00Speeding up Matlab over X11 ForwardingRunning Matlab over ssh is handy. If one wants to use the GUI, X11 forwarding is possible, but it is painfully slow if both machines are not inside a local network.<br />
<div>
<br /></div>
<div>
I found information about how to speed it up after googling for a while. In the end I think it is worth it to summarize the steps here:</div>
<div>
<ul>
<li>In the current folder where you are going to run matlab from, create a file name <span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">java.opts</span> with the content </li>
</ul>
"<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">-Dsun.java2d.pmoffscreen=false</span>" (without the double commas).<br /><ul>
</ul>
<ul>
<li>Use compression with ssh, by connecting to the server with </li>
</ul>
<span style="background-color: rgba(255, 255, 255, 0.917969); color: #222222; font-family: arial, sans-serif; font-size: 13px; text-align: -webkit-auto;"> ssh -c arcfour,blowfish-cbc -Y -C username@server</span></div>
<div>
<br /></div>
<div>
The speed up obtained is particularly noticeable when changing focus between different windows in the Matlab GUI.</div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com17tag:blogger.com,1999:blog-8391506498310459678.post-72122860446443069362011-11-12T15:59:00.004-03:002011-11-12T16:13:46.604-03:00GNOME3 Fallback mode 'fix'I switched to archlinux recently. I was used to Gnome2, and Gnome3 is quite of a disappointment in the sense that it involves re-learning how to do things, when software is supposed to adapt to us. Anyway, I don't plan to start a discussion on that, googling already reveals many 'gnome3 sucks' posts which provide lot of detail on the 'why'.<div><br /></div><div>In summary, I tried KDE4, but didn't feel comfortable either. Finally I ended up in GNOME3 fallback mode, whose default theme is disappointing as well. I found this theme which makes it look friendlier <a href="http://gnome-look.org/content/show.php?content=145210">http://gnome-look.org/content/show.php?content=145210</a> , but had some problems in nautilus and background font color. So I modified it and uploaded it <a href="https://docs.google.com/open?id=0B1skD429jLG9MDAwMzRiN2ItMDA5My00OWFlLTg1NzgtYjZiNzNiMTJhMTY2">here</a>.</div><div><br /></div><div>Now my desktop reminds me of Gnome2 and sometimes I believe it is even friendlier and better looking ;)</div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-57608466530568400952011-09-26T18:36:00.013-03:002011-09-29T04:38:57.499-03:00ITK and C++11<a href="http://dacap.com.ar/">Dacap</a> made me aware of the new C++11 standard and the supported functionality in <a href="http://gcc.gnu.org/gcc-4.6/">GCC 4.6.1</a>. Right after that, I downloaded GCC 4.6.1 and compiled it to try it with the <a href="http://www.itk.org/">Insight Tool-kit</a> (ITK), particularly because of all those super-templated types in ITK that make coding longer than what it should take, mostly because of the amount of typedefs and re-typing of class names. One of the 'wonders' of C++11 is the <a href="http://en.wikipedia.org/wiki/C%2B%2B11#Type_inference">auto</a> keyword, which happens to be close to a salvation angel for ITK users.<div><br /></div><div>My main concern was that C++11's implementation in GCC is still quite new, such that incompatibilities may appear almost instantly; and that was the case with a particular GCC extension that -std=c++0x was considering invalid. Therefore, when compiling ITK-based code you may find 'constexpr' errors if you enable c++0x support, particulary in the file <span class="Apple-style-span">vnl.h</span>. Fortunately, a patch has already been created and published <a href="http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50258">here</a> and can be applied directly to the 4.6.1 release source code.</div><div><br /></div><div>To compile it with Ubuntu you can follow the instructions given <a href="http://buildall.wordpress.com/2011/05/03/installing-gcc-4-6-in-the-ubuntu-11-04-natty-narwhal/">here</a>. In my case I didn't want to overwrite the previous gcc compiler in my system, nor I hadn't administrative rights, so I used <span class="Apple-style-span">make DESTDIR=/wherever/you/want install </span>. This way I just had to modify the PATH environment variable to point to the gcc 4.6.1 binaries and tell CMake to use g++-4.6 as the compiler rather than the standard gcc one.</div><div><br /></div><div>The patch mentioned earlier doesn't disable the constexpr error by itself; for that to be effective one must use the -fpermissive compiler flag. Some other compatibility problems are described <a href="https://wiki.edubuntu.org/GCC4.6">here</a>.</div><div><br /></div><div>Moreover, it is very likely to run on another error regarding an include file missing. To obtain a successful build of ITK my CXX flags were set to: <span class="Apple-style-span" >-std=c++0x -fpermissive -include cstddef</span></div><div><br /></div><div><b>UPDATE:</b> a better practice is to compile GMP, MPFR and other libs as static before compiling GCC, so that they are statically linked and the generated compiler binaries can be executed in other machines that may not have those specific libraries installed. Instructions for compiling these libraries and GCC can be found <a href="http://www.acsu.buffalo.edu/~charngda/cc_build.html">here</a>. My particular configure line for GCC 4.6.1 is the following:</div><div><br /></div><div><div><span class="Apple-style-span">configure --prefix=/usr \</span></div><div><span class="Apple-style-span">--enable-languages=c,c++,fortran \</span></div><div><span class="Apple-style-span">--enable-threads=posix \</span></div><div><span class="Apple-style-span">--enable-tls \</span></div><div><span class="Apple-style-span">--enable-libgomp \</span></div><div><span class="Apple-style-span">--enable-lto \</span></div><div><span class="Apple-style-span">--disable-nls \</span></div><div><span class="Apple-style-span">--disable-checking \</span></div><div><span class="Apple-style-span">--disable-multilib \</span></div><div><span class="Apple-style-span">--with-gmp=/tmp/gcc \</span></div><div><span class="Apple-style-span">--with-mpfr=/tmp/gcc \</span></div><div><span class="Apple-style-span">--with-mpc=/tmp/gcc \</span></div><div><span class="Apple-style-span">--with-libelf=/tmp/gcc \</span></div><div><span class="Apple-style-span">--with-fpmath=sse</span></div></div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-64154873029317302062011-09-08T04:15:00.008-03:002011-09-26T19:10:41.159-03:00Linux: Fixing resolution problem on external monitorI recently got a Dell L502x laptop. In order to connect it to an external VGA monitor I am using the mini-Displayport (a la Apple).<br /><br />The problem is that Linux (Ubuntu Natty) does not always figure out the right display modes for this particular monitor. Unfortunately, cvt nor gtf generate the correct modelines and I am stuck with a lower resolution.<br /><br />The trick was to dual-boot Windows :S and use PowerStrip to extract the proper modelines, as explained here <a href="http://www.x.org/wiki/FAQVideoModes">http://www.x.org/wiki/FAQVideoModes</a><br /><br />A bunch of very useful information can also be found here: <a href="https://wiki.ubuntu.com/X/Config/Resolution">https://wiki.ubuntu.com/X/Config/Resolution</a>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-59919374326623471612011-01-23T19:59:00.023-03:002011-09-26T19:11:00.245-03:00Excellent good-looking plotsWhen doing research one usually doesn't care about the aesthetics of plots or the visualized results, as long as they are clear enough to be interpreted. However, when making presentations or in publications, nice plots have an interesting impact and, even though they do not change how good results are, they still make things look more professional.<div><br /></div><div>I have been usin Matlab for a while now. It is one of those softwares that you usually hate, especially if you come from a better-structured programming background. Leaving execution speed out of the equation, Matlab sucks in many ways but there a few pros that build up its popularity, such as extremely easy and straightforward debugging and the available toolboxes and functions on Matlab Central. However, it is very easy to find blogs like <a href="http://abandonmatlab.wordpress.com/" target="_blank">Abandon Matlab</a>, where some posts really make the point about leaving Matlab forever and finding a better and more appropriate alternative.</div><div><br /></div><div>Anyways, enough of Matlab hate. The point is that I was looking for nice plots and I remembered about that amazing piece of software called Mathematica. I will not discuss the differences between Mathematica and Matlab, but just say that they were made for different purposes. However, take a look at the following plots generated with Matlab and Mathematica respectively, from the same data (click to see the real image since blogger is automatically introducing some JPEG artifacts):</div><div><br /></div><table border="2" cellpadding="4"> <tbody><tr> <th>Matlab</th> <th>Mathematica</th> </tr> <tr></tr><tr><td> <a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdtfBluIpNN4vLfwEcD6vh4e3N5eKch23yAH5dV_VsJBPtpeRO59Cl0l5UBjcIH0vrqZP3WGkr9EjRihAUCQMqoLfFNKWvB20QVjjUJtTsR9Y2Zo2Xnp00I1_vNZgeDafELuxqW-oxcPZZ/s1600/plot-matlab.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdtfBluIpNN4vLfwEcD6vh4e3N5eKch23yAH5dV_VsJBPtpeRO59Cl0l5UBjcIH0vrqZP3WGkr9EjRihAUCQMqoLfFNKWvB20QVjjUJtTsR9Y2Zo2Xnp00I1_vNZgeDafELuxqW-oxcPZZ/s320/plot-matlab.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5565533030022800802" /></a></td><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJRR8TFgGV5JKqOfER3D1gE4b7_wo0KdqdkwcjZQg66hFuLE1pX51if8I_j2p_L8VzczdEjLqWcHOTVTidc7G_HR5UVRaFitvdspu7vpc2FJ7MaeLFremtGn6HzEWaYO_iN40-Keg2xLqn/s1600/plot-mathematica.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="cursor:pointer; cursor:hand;width: 320px; height: 195px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJRR8TFgGV5JKqOfER3D1gE4b7_wo0KdqdkwcjZQg66hFuLE1pX51if8I_j2p_L8VzczdEjLqWcHOTVTidc7G_HR5UVRaFitvdspu7vpc2FJ7MaeLFremtGn6HzEWaYO_iN40-Keg2xLqn/s320/plot-mathematica.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5565527283450580898" /></a></td></tr><tr><td><span >load data.mat;<br />stem(x,y); hold on;<br />xlabel('x','Interpreter','LaTex');<br />ylabel('f(x)','Interpreter','LaTex');</span></td><td><span >data = Import["test.mat", "LabeledData"];<br />ListPlot[<br />Transpose[Flatten[{"x" /. data, "y" /. data}, 1]],<br />Filling -> Axis,<br />AxesLabel -> {x, f[x]}<br />]</span></td></tr></tbody></table><br /><br /><div>The difference is easy to grasp by just looking at the plots: Mathematica does a great job, while Matlab looks just ok. Something I usually do to make Matlab plots is to apply a grid with <span >grid on</span>, but the plot still looks not as professional as with Mathematica. Obviously there is space for cheating here; maybe if you look at how much Mathematica code is needed you may say that I haven't been fair enough. However, most of the code in the Mathematica snippet is needed because the data is read from a Matlab MAT file.</div><div><br /></div><div>In my opinion, the most amazing and simple detail that Mathematica uses and Matlab does not is antialiasing. It is a very subtle detail but it makes plots look softer and, somehow, more human and easier for our eyes to watch. There have been some attempts such as <a href="http://www.mathworks.com/matlabcentral/fileexchange/20979" target="_blank">this script</a>. However, that script is an smart user attempt to generate a plot with antialiasing but the antialiasing is simulated by resizing the plot, which still doesn't look as good as Mathematica's output (images not shown here but you can try it on your own).</div><div><br /></div><div>Beyond that, there are some problems when exporting plots from Matlab. First, exporting to PDF generates a PDF file that contains a whole page such as A4 and the plot in the middle with huge white spaces around. This is very annoying when working with pdflatex and the PDF generated by Matlab must be cropped. Moreover, even if exporting to PNG, the final image file does not look exactly as what is seen on the computer screen. This can lead to an endless 'fight' with Matlab's exporting options, sometimes without success. All of this doesn't seem to happen to Mathematica, at least considering what I have tried so far. PDF files look great and have the exact size of the plot and can be inserted straight away into latex documents.</div><div><br /></div><div>I don't want to go into much detail in this post since it could take a long time to discuss plot customization options in Matlab and Mathematica. My experience shows that Matlab works well to show the data properly and it is still interpretable, but it lacks the quality of softwares such as Mathematica or Matplotlib (this last one is another very nice plotting tool, free of charge). For more examples on the plotting power of Mathematica see <a target="_blank" href="http://reference.wolfram.com/mathematica/ref/Plot.html">here</a>, and for Matplotlib <a target="_blank" href="http://matplotlib.sourceforge.net/gallery.html">here</a>.</div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-64221710307039554052010-04-16T11:26:00.003-03:002010-04-16T11:33:44.830-03:00Nice Linux PDF manipulation utilitiesI found myself writing many reports with LaTex lately. Using pdflatex has it advantages, but things can get quite annoying when one wants to insert a figure which was generated in Matlab or any other program.<br /><br />Specially, MATLab does not do a nice job when exporting PDFs and leaves a whole blank area (the page itself actually) which is not desirable if we want to put a figure in a latex document. Fortunately, there is a linux program called <a href="http://pdfcrop.sourceforge.net/" target="_blank">pdfcrop</a> that does the job correctly (not 100% trustable, but 90% of the times I get good results).<br /><br />Another useful program is pdfimages, which extracts images from a pdf file. The pdfimages output is generally in huge pgm files, so it's better to convert it to something like png which results in smaller files, still usable with pdflatex.<br /><br />Finally, <a href="http://www2.warwick.ac.uk/fac/sci/statistics/staff/academic/firth/software/pdfjam/" target="_blank">pdfjoin and pdf90</a> allows one to join several files into a single one and rotate pages respectively. The Ubuntu package for these two is called pdfjam.CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-8066884987846163872010-03-10T09:33:00.007-03:002010-03-10T10:06:52.602-03:00Ultra simple incremental backups with rsyncRecently I bought an external hard drive for backups. While searching for the best way to do the backups I found <a href="http://samba.anu.edu.au/rsync/">rsync</a>, which looks well suited for these tasks.<br />Then I found <a href="http://www.mikerubel.org/computers/rsync_snapshots/">this webpage</a> that provides some scripts to achieve circular snapshots.<br /><br />However, most scripts on the web are extremely large and complex compared to what I need. So finally I made my own script that makes automated incremental backups, with no cycling but keeping a history file to identify each backup.<br /><br />Here is the code:<br /><textarea name="code" class="bash"><br />#!/bin/bash<br />##############################################<br />## This script should be called from the dir<br />## where the backup will be made to<br />###############################################<br /><br /># directory to backup<br />sourceDir=/media/something<br />rsyncFlags='--modify-window=1 -a --verbose --delete '<br /><br />#find if we have a backup already<br />find backup.0 -maxdepth 0 > /dev/null;<br /><br />if (( $? != 0 )); then {<br /> echo 'First Backup';<br /> nextBackup='0';<br /> firstBackup=1;<br />} else<br />{<br /> # find last backup<br /> lastBackup=`find backup.* -maxdepth 0 | sed 's/backup.//' | sort -n -r | head -1`;<br /><br /> echo 'Resuming backup' $lastBackup '...';<br /><br /> # +1 for next one<br /> nextBackup=$(( $lastBackup + 1 ));<br /> echo $nextBackup;<br /> firstBackup=0;<br />}<br />fi<br /><br />lastBackup=backup.$lastBackup;<br />nextBackup=backup.$nextBackup;<br /><br />if (( $firstBackup == 1 )); then {<br /> rsync $rsyncFlags $sourceDir/ $nextBackup/;<br /> R=$?;<br />} else<br />{<br /> rsync $rsyncFlags --link-dest=../$lastBackup $sourceDir/ $nextBackup/;<br /> R=$?;<br />} fi<br /><br />if (( $R != 0 )); then {<br /> echo '=======> ERROR DURING BACKUP!!';<br /> exit $R;<br />} fi<br /><br /># make link to last backup<br />rm -f HEAD;<br />ln -s -f $nextBackup HEAD<br />if (( $? != 0 )); then {<br /> echo '=======> ERROR Creating link!!';<br /> exit $?;<br />} fi<br /><br /># save history<br />echo -e $nextBackup '\t\t' `date -R` >> backup-history;<br />if (( $? != 0 )); then {<br /> echo '=======> ERROR Saving History!!';<br /> exit $?;<br />} fi<br /><br />echo ' ';<br />echo '------------- BACKUP DONE ----------------';<br />echo ' ';<br /></textarea><br /><br />This script will create backup directories called <b>backup.xxxx</b>, where <b>xxxx</b> is the backup number. This number is zero for the first backup done. Rsync hard-links the unchanged files to the previous backup which is a key method to save space.<br /><br />With this script I am backuping a NTFS partition and that's why the option <b>--modify-window=1</b> is needed in <b>rsyncFlags</b>. It is important to write <b>sourceDir</b> without a trailing forward slash!<br /><br />In order to provide easy access to the last backup, a symbolic link called <b>HEAD</b> will point to the latest backup. Additionally, a file called <b>backup-history</b> holds the exact time and date where each backup was performed.<br /><br /><b>NOTE</b>: I am not responsible for this script and it's correctness. There might be problems such as if there are backup.something folders or files in the backup directory where the script is called, and other bugs that may arise. This is a very simple and minimalistic script!CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-48380337091792230972010-03-01T18:23:00.010-03:002010-03-01T18:57:30.351-03:00Merging Qt and EigenAgain in <a href="http://vibot.org/">ViBOT</a>, image segmentation assignment, Matlab is really slow, wait minutes for results...<div><br /></div><div>So I decided to try to use <a href="http://qt.nokia.com/products">Qt</a> for the GUI and OS abstraction layer together with <a href="http://eigen.tuxfamily.org/">Eigen</a> which is another amazing template-based library for matrix manipulation. The important code to write was to link both libraries, taking advantage of Qt's amazing QImage class which is able to open several file formats and perform low-level pixel access. In a few words, I had to put all the image information contained in QImage into a Eigen's matrix.</div><div><br /></div><div>Luckily, this task is very simple. Here there is some code:</div><div><br /></div><div><br /><pre name="code" class="cpp"><br />#ifndef MIMG_H<br />#define MIMG_H<br /><br />USING_PART_OF_NAMESPACE_EIGEN<br /><br />#include <QImage><br /><br />#include <Eigen/Core><br />#include <Eigen/Array><br /><br />//general type, maybe float or double needed<br />typedef MatrixXf MImgType;<br /><br />class MImg<br />{<br />public:<br /> //creates an all-black image<br /> MImg(unsigned int h, unsigned int w);<br /><br /> //creates image from QImage<br /> MImg( const QImage &img );<br /><br /> MImgType R,G,B; //each component<br /> //made public for faster access<br /><br /> unsigned int getHeight();<br /> unsigned int getWidth();<br /><br /> QImage * toQImage(); //convert to QImage<br /><br /> /**<br /> Maximizes dynamic range of three channels<br /> independently!<br /> **/<br /> void maximizeIndependentDynamicRange();<br /><br />private:<br /> unsigned int mH,mW; //height, width<br /><br />};<br /><br />#endif // MIMG_H<br /></pre><br /><pre name="code" class="cpp"><br />#include "mimg.h"<br /><br />MImg::MImg(unsigned int h, unsigned int w)<br />{<br /> R = MImgType::Zero(h,w);<br /> G = MImgType::Zero(h,w);<br /> B = MImgType::Zero(h,w);<br /><br /> mH = h;<br /> mW = w;<br />}<br /><br />MImg::MImg( const QImage &img )<br />{<br /> int w = img.width();<br /> int h = img.height();<br /><br /> R = MImgType::Zero(h,w);<br /> G = MImgType::Zero(h,w);<br /> B = MImgType::Zero(h,w);<br /><br /> //now copy values..<br /> for (int y=0; y < h; y++)<br /> for (int x=0; x < w; x++)<br /> {<br /> QRgb color = img.pixel(x,y);<br /> R(y,x) = qRed(color)/255.0;<br /> G(y,x) = qGreen(color)/255.0;<br /> B(y,x) = qBlue(color)/255.0;<br /> }<br /><br /> return img;<br />}<br /><br />void MImg::maximizeIndependentDynamicRange()<br />{<br /> double min, max;<br /><br /> min = R.minCoeff(); max = R.maxCoeff();<br /> R = (R.cwise() - min) / (max - min);<br /><br /> min = G.minCoeff(); max = G.maxCoeff();<br /> G = (G.cwise() - min) / (max - min);<br /><br /> min = B.minCoeff(); max = B.maxCoeff();<br /> B = (B.cwise() - min) / (max - min);<br />}<br /><br />unsigned int MImg::getHeight() {<br /> return mH;<br />}<br /><br />unsigned int MImg::getWidth() {<br /> return mW;<br />}<br /></pre><br /><br /></div><div><br /></div><div>It is important to mention that this code only handles RGB and won't care about grayscale images or any other type of colour models. The advantage of having the image in this matrix form is that Eigen provides an easy syntax for matrix manipulation, along with many modules performing least squares, Cholesky, diagonalization, etc.</div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com6tag:blogger.com,1999:blog-8391506498310459678.post-72525454559719237502009-12-03T11:49:00.007-03:002009-12-03T12:47:22.206-03:00Matlab and n-dimensional array sorting<span class="Apple-style-span" style="white-space: pre-wrap; "><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">Wow.. it's been such a long time since the last post!! I've been quite busy with </span></span><a href="http://vibot.org/"><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">ViBOT</span></span></a><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">, specially during the last two weeks. Anyway, I thought it would be nice to write a post about some nice Matlab functions I found quite useful:</span></span></span><div><span class="Apple-style-span"><span class="Apple-style-span" style="font-size:medium;"></span></span><span class="Apple-style-span" style="font-family:'trebuchet ms';"><span class="Apple-style-span" style="white-space: pre-wrap;"><br /></span></span><div><span class="Apple-style-span" style="font-family:monospace;font-size:100%;"><span class="Apple-style-span" style=" white-space: pre-wrap;"><b><span class="Apple-style-span" style="font-family:'courier new';">reshape</span></b><span class="Apple-style-span" style="font-family:'courier new';">:</span></span><span class="Apple-style-span" style="white-space: pre-wrap; "><span class="Apple-style-span" style="font-family:'trebuchet ms';">this is a nice function that lets you reshape any array or matrix into any other array or matrix with different dimensions, as long as the number of elements is kept the same. It is very useful when one wants to loop through every element of a two or three dimensional array. If </span><span class="Apple-style-span" style="font-family:'courier new';">A=[1 2; 3 4]</span><span class="Apple-style-span" style="font-family:'trebuchet ms';"> then </span><span class="Apple-style-span" style="font-family:'courier new';">reshape(A,[1 4])</span><span class="Apple-style-span" style="font-family:'trebuchet ms';"> will return </span><span class="Apple-style-span" style="font-family:'courier new';">[1 2 3 4]</span><span class="Apple-style-span" style="font-family:'trebuchet ms';">. To get back to the original array we can then use </span><span class="Apple-style-span" style="font-family:'courier new';">reshape([1 2 3 4],[2 2])</span><span class="Apple-style-span" style="font-family:'trebuchet ms';">.</span></span></span></div><div><span class="Apple-style-span" style="font-family:'trebuchet ms';"><span class="Apple-style-span" style="white-space: pre-wrap; "><span class="Apple-style-span" style="font-size:medium;"><br /></span></span></span></div><div><span class="Apple-style-span" style="white-space: pre-wrap; "><span class="Apple-style-span" style="font-family:'trebuchet ms';"><span class="Apple-style-span" style="font-size:medium;"><span class="Apple-style-span" style="font-family:'courier new';"><b>ind2sub:</b></span> </span><span class="Apple-style-span" style="font-size: medium;">this is a useful function when manipulating arrays that were linearised with reshape. From Matlab help: "</span><span class="Apple-style-span" style=" white-space: normal; "><i><span class="Apple-style-span" style="font-size: medium;">The </span></i><tt><span class="highlight0"><i><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">ind2sub</span></span></i></span></tt><i><span class="Apple-style-span" style="font-size: medium;"> command determines the equivalent subscript values corresponding to a single index into an array</span></i><span class="Apple-style-span" style="font-size: medium;">". A simple example is the following:</span></span></span></span></div><div><br /></div><div style="text-align: left;"><ul><li><span class="Apple-style-span" style="font-family:'courier new';">A=[1 2; 6 5]; B = reshape(A,[1 4]);</span></li><li><span class="Apple-style-span" style="font-family:'courier new';">[sV, sI] = sort(B, 'descend'); <span class="Apple-style-span" style="color:#009900;">% sort linearised array</span></span></li><li><span class="Apple-style-span" style="font-family:'courier new';">disp(sV(1)); <span class="Apple-style-span" style="color:#33CC00;">%show max value: 6</span></span></li><li><span class="Apple-style-span" style="font-family:'courier new';">disp(sI(1)); <span class="Apple-style-span" style="color:#009900;">%show max index: 2</span></span></li><li><span class="Apple-style-span" style="font-family:'courier new';">[x,y] = ind2sub( size(A), sI(1) );</span></li><li><span class="Apple-style-span" style="font-family:'courier new';">disp(x); disp(y); <span class="Apple-style-span" style="color:#009900;">% (x,y) == (2,1), we got the coordinates in the original matrix</span></span></li></ul><div><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">There is also a</span></span><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';"> sub2ind</span></span><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';"> function which does the reverse transformation. </span></span><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';">ind2sub</span></span><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-family:'trebuchet ms';"> was very useful to ease the sorting task when applying the Hough transform for circle detection, where there is an accumulator matrix which is 3-dimensional.</span></span></div></div></div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com1tag:blogger.com,1999:blog-8391506498310459678.post-34741867481459507222009-08-15T19:34:00.009-03:002011-09-26T19:11:44.651-03:00FPGAs are taking over!<div style="text-align: left;">From the moment I knew and learned about FPGAs (Xilinx) I looked forward to use them to replace large logic circuits. This way the system would be not only scallable and the logic programmable but costs should be reduced too.</div><div style="text-align: left;"> Unfortunately, most of the times the FPGA alternative was much more expensive than the equivalent logic circuit implemented with separate logic ICs.</div><div style="text-align: left;">Finally the day came and I got the chance to build a board with an ARM7 core + Spartan3A FPGA. Total price was reduced and the system became fully programmable. The ARM7 chip (LPC23xx) configures the FPGA on startup which happens to be really fast (52kib for XC3S50A). The microcontroller and FPGA are connected through a parallel bus with many control lines.</div><div style="text-align: left;"> The XC3S50A is optimal in the sense that it only requires 3.3V and 1.2V supplies so it can be directly connected to the microcontroller pins. </div><div style="text-align: left;"><br /></div><div style="text-align: left;"> Here there are some pictures:</div><div><br /></div><div><br /><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjfGtyU01GKZmyiVTlnN8zLQ0oq9N3NKaWKpxSKuEwr8GbNBuLcCn5zTXRKhb6rAHL3WV6SynbBQOewkscW4yVJSKyBoKAx66l1BjA6CJgV12lNXHJhjlsAcARLCL3tePPb2YHbyzjHWrN/s1600-h/fpga-arm1.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjfGtyU01GKZmyiVTlnN8zLQ0oq9N3NKaWKpxSKuEwr8GbNBuLcCn5zTXRKhb6rAHL3WV6SynbBQOewkscW4yVJSKyBoKAx66l1BjA6CJgV12lNXHJhjlsAcARLCL3tePPb2YHbyzjHWrN/s400/fpga-arm1.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5370328327350974962" /></a><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEid89sQv4C3fuPZtsQdRgR_xEyE3ZC2FkIII2Hy_lZLDv9psd-_sV1DPZ-hEbINh655lP4FhniBzDUVE1Vsop7-IebiA1zUQ7BPnd11rgmHG9qgF6Ypg0YugexZqysDRewTz2ZxNv041kEF/s1600-h/fpga-arm2.jpg" style="text-decoration: none;" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="text-align: left;display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; cursor: pointer; width: 400px; height: 300px; " src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEid89sQv4C3fuPZtsQdRgR_xEyE3ZC2FkIII2Hy_lZLDv9psd-_sV1DPZ-hEbINh655lP4FhniBzDUVE1Vsop7-IebiA1zUQ7BPnd11rgmHG9qgF6Ypg0YugexZqysDRewTz2ZxNv041kEF/s400/fpga-arm2.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5370327312234973682" /></a><br /></div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-67521518493614789092009-07-04T01:20:00.012-03:002011-09-26T19:11:48.643-03:00Qt-Embedded: Capturing screen with QPixmapI've been working on a product manual lately. I needed to include several LCD screenshots into it so I tried to come up with an easy way to capture snapshots from our Qt/Embedded app.<div><span class="Apple-style-span" style=" ;font-family:'Times New Roman';"><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; ">Qt/Embedded provides a nice method to save window/framebuffer contents directly to an image file. However, I wanted to send the 'take-snapshot' command from a tty console (telnet/serial/etc) since there weren't any other buttons on the system to trigger that.</div><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; ">A QTimer is set up. Periodically it checks the file <i>/tmp/doCapture</i>. If it exists a snapshot is taken and an image file is saved. Its filename is taken from the contents of <i>/tmp/doCapture</i>. After saving the image <i>/tmp/doCapture</i> is deleted.</div><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; ">Here is the code, which should be placed in the main window, whose width and height cover the whole screen:</div><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; "><br /></div><br /><pre name="code" class="cpp">mainWindow::mainWindow()<br />{<br /> // captureTimer should be declared in mainWindow's class definition<br /> captureTimer = new QTimer(this);<br /> connect( captureTimer, SIGNAL(timeout()), this, SLOT(captureTimerEvent()) );<br /><br /> captureTimer->start(1000); //check interval<br />}<br /><br />void mainWindow::captureTimerEvent()<br />{<br /> QString tmpFile = QString("/tmp/doCapture");<br /><br /> if ( !QFile::exists(tmpFile) )<br /> return;<br /><br /> QFile f(tmpFile);<br /> if ( !f.open( QIODevice::ReadWrite ) )<br /> return;<br /><br /> char buf[200];<br /> if ( f.readLine( buf, sizeof(buf) - 4 ) == -1 )<br /> return;<br /><br /> buf[strlen(buf)-1] = '\0'; //remove \n created by 'echo'-- not safe!<br /><br /> strcat( buf, ".png" );<br /><br /> //capture<br /> QPixmap p = QPixmap::grabWindow( this->winId() );<br /><br /> if ( p.save( buf ) )<br /> printf("------- GRAB OK\n");<br /> else<br /> printf("------- ERR GRAB!\n");<br /><br /> /* delete file */<br /> f.remove();<br />}<br /></pre><br /><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; "><br /></div><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; ">This way, all I have to do to take a snapshot is to write:</div><div style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 3px; padding-right: 3px; padding-bottom: 3px; padding-left: 3px; width: auto; font: normal normal normal 100%/normal Georgia, serif; text-align: left; "><br /><pre name="code" class="cpp">echo pngfilename > /tmp/doCapture<br /></pre></div></span></div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com1tag:blogger.com,1999:blog-8391506498310459678.post-9712113884724816782009-05-04T22:10:00.008-03:002009-05-04T23:43:07.434-03:00Compiling and using GDB for arm-linux<p>Some days ago I had to compile <a href="http://www.gnu.org/software/gdb/">gdb</a> manually in order to debug an arm-linux app. It's quite trivial but it's so useful that I thought it would be a nice idea to post the instructions here. Below there are some explanations about debugging remotely with <a href="http://www.kdevelop.org/">KDevelop</a>.</p><p>This was done with gdb-6.8, you can grab it <a href="http://ftp.gnu.org/gnu/gdb/gdb-6.8.tar.bz2">here</a>. It is assumed that arm-linux tools are available (PATH correctly set).</p><p><span style="font-size:130%;">Compiling the GDB client</span></p><p>Decompress gdb-6.8 and compile it by issuing:</p><br /><pre name="code" class="bash"><br />tar xvf gdb-6.8.tar.gz<br />cd gdb-6.8<br />./configure --build=x86 --host=x86 --target=arm-linux<br />make<br /></pre><br /><p>After compiling just copy <em>gdb/gdb</em> to <em>arm-linux-gdb</em> where the arm-linux toolchain binaries reside (this is purely for organization and proper naming). You can now remove the gdb-6.8 directory.</p><p><strong>NOTE:</strong> if your host computer architecture isn't intel-based just replace x86 by the correct value for your platform.</p><p><span style="font-size:130%;">Compiling the GDB server (ARM)</span></p><p>Decompress gdb-6.8 and compile it by issuing:</p><br /><pre name="code" class="bash"><br />tar xvf gdb-6.8.tar.gz<br />cd gdb-6.8<br />./configure --host=arm-linux<br />make<br /></pre><br />After compiling just copy <em>gdb/gdbserver/gdbserver</em> to your arm-linux filesystem so that you can execute it from a remote shell (<em>gdbserver</em> will be an arm-elf binary). You can now remove the gdb-6.8 directory.<p><span style="font-size:130%;">Testing connections</span></p><p><span style="font-size:100%;">First the server should be started in the arm processor by issuing something like:</span></p><br /><pre name="code" class="bash"><br />gdbserver host:1234 _executable_<br /></pre><br /><p><span style="font-size:100%;">Where <em>_executable_</em> is the application that is going to be debugged and host:1234 tells gdbserver to listen for connections to port 1234.</span></p><p><span style="font-size:100%;">To run gdb just type this in a PC shell:</span></p><br /><pre name="code" class="bash"><br />arm-linux-gdb --se=_executable_<br /></pre><br /><p><span style="font-size:100%;">After that you'll get the gdb prompt. To connect to the target type:</span></p><br /><pre name="code" class="bash"><br />target remote target_ip:1234<br /></pre><br /><p>To resume execution type 'continue'. You can get an overview on gdb usage <a href="http://linux.wku.edu/~lamonml/programming/debug/gdb_usage.html">here</a>.</p><p><span style="font-size:130%;">Debugging with KDevelop</span></p><p><span style="font-size:100%;">KDevelop can be used to watch variables and debug the remote target (place breakpoints, stop execution, etc). Just go to Project -> Project Options and make sure you have something like this:</span></p><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhukZ44Jz2sidziKNa7buYt5hKJInmtNoLbi8lTD_oiYr3Qx9MO1K74mEUQ5xba5z5y0SkTh7WSBFDUsu6LxKTrfnFftuxbIfF54Dcfo1YN8-lz6ScoYtiWnMvxGsnaaMk3jrJMXXW26Bnd/s1600-h/kdevelop.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 256px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhukZ44Jz2sidziKNa7buYt5hKJInmtNoLbi8lTD_oiYr3Qx9MO1K74mEUQ5xba5z5y0SkTh7WSBFDUsu6LxKTrfnFftuxbIfF54Dcfo1YN8-lz6ScoYtiWnMvxGsnaaMk3jrJMXXW26Bnd/s400/kdevelop.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5332156085027125666" /></a><br /><p>monitor-debug.gdb is a file that contains the following</p><br /><pre name="code" class="bash"><br />target remote target_ip:1234<br /></pre><br /><p>After this you will be ready to remotely debug any arm-linux application.</p><p>_</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com16tag:blogger.com,1999:blog-8391506498310459678.post-39041148495802672352009-04-28T19:30:00.004-03:002009-05-04T23:44:14.861-03:00Catching uncaught exceptions in JavaThis month looks quite javaized!<div>So here is another thing I came up with, regarding uncaught exceptions which usually end the application totally unexpectedly. I wouldn't mind about that, but I felt that the user should be notified with a minimum-sense message and some technical info so that he/she can send it over to the developers.</div><div>So here it is a 'BodyGuard' class that does the job by using a callback present in the Thread class.</div><br /><pre name="code" class="java"><br />package bodyguard;<br /><br />public class BodyGuard implements Thread.UncaughtExceptionHandler<br />{ <br /> static private BodyGuard bGuard;<br /><br /> static public void registerGuard() {<br /> bGuard = new BodyGuard();<br /> Thread.setDefaultUncaughtExceptionHandler(bGuard);<br /> }<br /><br /> public void uncaughtException( Thread thread, Throwable e )<br /> {<br /> java.io.StringWriter sW = new java.io.StringWriter();<br /> e.printStackTrace( new java.io.PrintWriter(sW));<br /> <br /> String s = "A fatal error was detected during execution: \n" +<br /> "Thread: " + thread.getName() + "\n" +<br /> "Exception: " + sW.toString() + "\n" +<br /> "The application will be closed now.";<br /> <br /> showFatalErr(s);<br /> }<br /><br /> private void showFatalErr( String err )<br /> {<br /> //JOptionPane.showMessageDialog(null, err,"Error", JOptionPane.ERROR_MESSAGE);<br /> BodyGuardDialog dlg = new BodyGuardDialog(null, true, err);<br /> dlg.setLocationRelativeTo(null);<br /> dlg.setVisible(true);<br /> <br /> System.exit(-1); //exit n ow<br /> }<br />}<br /></pre><br /><div><span class="Apple-style-span" style="font-style: italic;">BodyGuardDialog</span> is another class derived from <span class="Apple-style-span" style="font-style: italic;">JDialog</span> that shows the corresponding error message and lets the user copy the error to the clipboard.</div><div>In order to register this handler one just has to call <span class="Apple-style-span" style="font-style: italic;">bodyguard.BodyGuard.registerGuard() </span>when starting up (ie: static void main()).</div><div>This class will catch uncaught exceptions from all threads, displaying the thread's name where the exception was thrown.</div><div>_</div>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-79911172659069069822009-04-21T14:50:00.009-03:002009-05-04T23:48:28.263-03:00Java Application and self-restart<p>Java's networking capabilities and prebuilt classes make self-updating applications an easy task for developers. A simple method is to store a file containing current version number on a web host, together with a zipped/tared file containing the whole or partial application files to update.</p>Also, java applications are truly self-updatable since the application itself can overwrite its class files (or jar ones), since the java VM loads all its contents into memory before start up (except for dynamic 'late' class loading).<br /><p>After coding the necessary classes to perform the update I realised I needed a way to tell java to restart the application, loading the updated code from the new class files. There wasn't an automated way to do this, so I came up with the next piece of code which invokes the java VM to execute the JAR file where certain class belongs to.</p><br /><pre name="code" class="java"><br />public boolean restartApplication( Object classInJarFile )<br />{<br /> String javaBin = System.getProperty("java.home") + "/bin/java";<br /> File jarFile;<br /> try{<br /> jarFile = new File<br /> (classInJarFile.getClass().getProtectionDomain()<br /> .getCodeSource().getLocation().toURI());<br /> } catch(Exception e) {<br /> return false;<br /> }<br /><br /> /* is it a jar file? */<br /> if ( !jarFile.getName().endsWith(".jar") )<br /> return false; //no, it's a .class probably<br /><br /> String toExec[] = new String[] { javaBin, "-jar", jarFile.getPath() };<br /> try{<br /> Process p = Runtime.getRuntime().exec( toExec );<br /> } catch(Exception e) {<br /> e.printStackTrace();<br /> return false;<br /> }<br /><br /> System.exit(0);<br /><br /> return true;<br />}<br /></pre><br /><p>There are some important aspects to have in mind for this code:</p><ul><li>The application's main class must be in a jar file. <strong>classInJarFile</strong> must be an instance of any class inside the same jar file (could be the main class too).</li><li>The called java VM will be the same that the application is currently running on.</li><li>There is no special error checking: the java VM may return an error like class not found or jar not found, and it will not be caught by the code posted above.</li><li>The function will never return if it doesn't catch an error. It would be a good practice to close all the handlers that could conflict with the 'duplicate' new application before calling <em>restartApplication()</em>. There will be a small time (which depends on many factors) where both applications will be running at the same time.</li></ul><p>The code can be easily modified for a class file approach rather than jar ones.</p><p>A bash script or .bat (Windows) would work, calling the application indefinitely in the case the process' return value matches a specified number (which would be set after a successful upgrade). However, this wouldn't be platform independent.</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com5tag:blogger.com,1999:blog-8391506498310459678.post-57886866863106067692009-03-25T19:36:00.013-03:002009-05-04T22:03:36.612-03:00Loop unrolling and speed-up techniques<p>Today I started some investigation on DTMF detection. After some research I decided to try the <a href="http://en.wikipedia.org/wiki/Goertzel_algorithm">Goertzel</a> algorithm, wrote some code from scratch and tried it on a real equipment based on an ARM7 core. It did fine actually, but after some benchmarking I thought it was somewhat slow.</p><p>I wrote the code thinking on future optimization but keeping simplicity in mind, specially because I didn't know how it was going to behave. However, as said above, calculations took much longer than what I expected, even though they were quite fast, exceeding the requirements for real-time processing (telephone channel, 8khz, mono). I still wanted to keep the code in C for portability so I tried some tricks.</p><p>I wrote the code with fixed-point math in mind, since floating point arithmetic would kill performance.</p><p>First, here are some basic definitions:</p><br /><pre name="code" class="cpp"><br />/* Struct for a single Goertzel calculator */<br />typedef struct<br />{<br /> dsp_t sp1,sp2; //past values (IIR)<br /> dsp_t coeff; //calculated only once<br /><br />} GOERTZ_s;<br /><br />/* Calculate Goertzel 'step' */<br />#define GOERTZ_calc( _s, _val ) \<br /> { \<br /> dsp_t _gs = (_val) + FP_MULT2( _s.coeff, _s.sp1 ) - _s.sp2; \<br /> _s.sp2 = _s.sp1; \<br /> _s.sp1 = _gs; \<br /> }<br /></pre><br /><p>The first approach was the simplest one, I needed sixteen Goertzel calculations (8 frequencies + 8 second harmonic for the first frequencies). I had a buffer where the incoming PCM data was copied to so I had to process that array for each of the 16 Goertzel 'calculators'.</p><br /><pre name="code" class="cpp"><br />static inline void GOERTZ_processAll( dsp_t sample )<br />{<br /> int i;<br /> for (i=0; i < 16; i++)<br /> GOERTZ_calc( goertzs[i], sample );<br />}<br /><br />/* this is inside another function */<br />int i;<br />for (i=0; i < BUFFER_SIZE; i++)<br /> GOERTZ_processAll( bufferData[i] );<br /><br /></pre><br /><p>Where <strong>BUFFER_SIZE</strong> is the size of <strong>bufferData[] </strong>and <strong>goertzs[]</strong> is a 16-element array of <strong>GOERTZ_s</strong> structs, already initialized. Notice the inline modifier in <strong>GOERTZ_processAll()</strong>. It's really important since function inlining will help in execution time, specially when the function is called so frequently.</p><p>That code worked alright, but was too slow, at least for my intuition. The progress into a more efficient scheme had many steps, but basically there were three important changes:</p><ul><li><strong>dsp_t</strong> was defined as <strong>int16_t</strong>, but the processor's 'native' word length is 32-bit, so changing <strong>dsp_t</strong> to be <strong>int32_t</strong> speeded up the calculations by removing cast and special assignment instructions.</li><li>Loop unrolling was done in <strong>GOERTZ_processAll()</strong>. That means more flash is used but it's a good price to pay for a good speed up. Besides that, here we are talking about repeating the same thing 16 times so it's not a big problem if we have, to say, a 512k flash microcontroller or dsp.</li><li>Instead of passing a single value to GOERTZ_processAll() a 8-byte array is used. This improves time considerably but also increases code size. As said in the previous point that wasn't an issue this case. Note that a 16-byte array won't necessarily increase performance. It depends on the core architecture, and in this case it made things worse (but better than single value parameter passing).</li></ul><p>With these modifications I got a 100% performance increase, which means that there can be twice as much DTMF decoders compared to the non-optimized version.</p><p>Here is the code with the modifications:</p><br /><pre name="code" class="cpp"><br />static inline void GOERTZ_processAll( dsp_t samples[8] )<br />{<br /> #define DO(j) \<br /> GOERTZ_calc( goertzs[j], samples[0] ); \<br /> GOERTZ_calc( goertzs[j], samples[1] ); \<br /> GOERTZ_calc( goertzs[j], samples[2] ); \<br /> GOERTZ_calc( goertzs[j], samples[3] ); \<br /> GOERTZ_calc( goertzs[j], samples[4] ); \<br /> GOERTZ_calc( goertzs[j], samples[5] ); \<br /> GOERTZ_calc( goertzs[j], samples[6] ); \<br /> GOERTZ_calc( goertzs[j], samples[7] );<br /><br /> DO(0);<br /> DO(1);<br /> DO(2);<br /> DO(3);<br /> DO(4);<br /> DO(5);<br /> DO(6);<br /> DO(7);<br /> DO(8);<br /> DO(9);<br /> DO(10);<br /> DO(11);<br /> DO(12);<br /> DO(13);<br /> DO(14);<br /> DO(15);<br /><br />#undef DO<br />}<br /><br />/* somewhere in another function */<br />int i;<br />for (i=0; i < BUFFER_SIZE; i +=8 )<br /> GOERTZ_processAll( bufferData + i );<br /></pre><p><span style="font-size:130%;"></span></p><p><span style="font-size:130%;">But it can do better...</span><br /></p><p><span style="font-size:100%;">After observing how good performance went after this modifications I tried to do more loop unrolling to see if I could improve it. If the data buffer is large enough then the <span style="font-style:italic;">for</span> loop that process 8 samples at a time wastes useful CPU instructions, so I included it inside a function called <span style="font-weight:bold;">GOERTZ_processBuffer()</span> which takes a buffer pointer and its length. There was another 100% performance increase from the previous optimization. This means a 4x speed up from the original code! Note that, once again, more flash is being used for loop unrolling.</span></p><p><span style="font-size:100%;"></span></p><br /><pre name="code" class="cpp"><br />static inline void GOERTZ_processBuffer( dsp_t *samples, int num )<br />{<br /> #define DO(j) \<br /> for ( i=0; i < num; i+=32 ) { \<br /> GOERTZ_calc( gss[j], samples[0+i] ); \<br /> GOERTZ_calc( gss[j], samples[1+i] ); \<br /> GOERTZ_calc( gss[j], samples[2+i] ); \<br /> GOERTZ_calc( gss[j], samples[3+i] ); \<br /> ... up to 32 .. ; }<br /><br /><br /> DO(0);<br /> DO(1);<br /> DO(2);<br /> DO(3);<br /> DO(4);<br /> DO(5);<br /> DO(6);<br /> DO(7);<br /> DO(8);<br /> DO(9);<br /> DO(10);<br /> DO(11);<br /> DO(12);<br /> DO(13);<br /> DO(14);<br /> DO(15);<br /><br />#undef DO<br />}<br /></pre>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-26730075782653227072009-03-18T18:58:00.008-03:002009-05-04T22:03:58.718-03:00QTimer and no monotonic clock support<p>I found myself dealing with qt-embedded and QTimers again. There's a board whose software configuration doesn't support monotonic clocks so changing the date back in time causes running QTimer's to cease activity.</p><p>I chose to patch qt-embedded 4.5.0. The fix is simple, I just had replace this function in src/corelib/kernel/qeventdispatcher_unix.cpp</p><p><br /><pre name="code" class="cpp"><br />void QTimerInfoList::registerTimer(int timerId, int interval, QObject *object)<br />{<br /> QTimerInfo *t = new QTimerInfo;<br /> t->id = timerId;<br /> t->interval.tv_sec = interval / 1000;<br /> t->interval.tv_usec = (interval % 1000) * 1000;<br /> t->timeout = updateCurrentTime() + t->interval;<br /> t->obj = object;<br /> t->inTimerEvent = false;<br /><br /> timerInsert(t);<br />}<br /></pre><br /><p></p><p>by this one:</p><p><br /><pre name="code" class="cpp"><br />void QTimerInfoList::registerTimer(int timerId, int interval, QObject *object)<br />{<br /> /** add this 2 lines */<br /> updateCurrentTime();<br /> repairTimersIfNeeded();<br /><br /> QTimerInfo *t = new QTimerInfo;<br /> t->id = timerId;<br /> t->interval.tv_sec = interval / 1000;<br /> t->interval.tv_usec = (interval % 1000) * 1000;<br /> t->timeout = updateCurrentTime() + t->interval;<br /> t->obj = object;<br /> t->inTimerEvent = false;<br /><br /> timerInsert(t);<br />}<br /></pre><br /><p>After that qt-embedded should be recompiled (a full recompilation isn't needed, the only file that needs to be compiled again is the one modified, and then a full relink and install; make will do the job).</p><p>What happens is that everytime a timer is registered, Qt will update the current time and try to fix the timers if it's needed. This will make newly registered timers work after the date is changed backwards, but old timers won't run properly. I created a class which tracks the QTimers present in the application so that it is able to stop and start them again. This is not the best solution but I had to do a quick fix on this and it works.</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-48520219008706948252009-03-04T22:48:00.012-02:002009-05-04T22:04:16.475-03:00Some code metrics<p>I recently received an email with <a href="http://www.ganssle.com/" target="_blank">Jack Ganssle</a>'s last <a href="http://www.ganssle.com/tem/tem175.pdf" target="_blank">Embedded Muse</a>, mentioning two tools to calculate code metrics. I wanted to try one of them so I downloaded <a href="http://www.campwoodsw.com/sourcemonitor.html" target="_blank">SourceMonitor</a>.</p><p>I ran SourceMonitor and computed the statistics for one of the largest projects I'm working on (embedded ARM7 processor, ethernet, USB along with live audio recording/playing among other functions). I got impressed by some numbers, here are the results:</p><br /><p><b>NOTE:</b>SourceMonitor processed my code only, excluding the TCP/IP stack and the FreeRTOS code which is part of the firmware too.</p><br /><style type="text/css">.nobrtable br { display: none }</style><br /><div class="nobrtable"><br /><table border="1" cellpadding="2" cellspacing="2"><br /><tbody><br /><tr><br /><td style="width: 211px;">Files</td><br /><td style="width: 79px;">191</td><br /></tr><br /><tr><br /><td style="width: 211px;">Lines</td><br /><td style="width: 79px;">34,019</td><br /></tr><br /><tr><br /><td style="width: 211px;">Statements</td><br /><td style="width: 79px;">12,765</td><br /></tr><br /><tr><br /><td style="width: 211px;">Percent Branch Statements</td><br /><td style="width: 79px;">19.9</td><br /></tr><br /><tr><br /><td style="width: 211px;">Percent Lines with Comments</td><br /><td style="width: 79px;">26.1</td><br /></tr><br /><tr><br /><td style="width: 211px;">Functions</td><br /><td style="width: 79px;">538</td><br /></tr><br /><tr><br /><td style="width: 211px;">Average Statements per<br />Function</td><br /><td style="width: 79px;">25.7</td><br /></tr><br /><tr><br /><td style="width: 211px;">Average Block Depth</td><br /><td style="width: 79px;">1.54</td><br /></tr><br /></tbody><br /></table></div><br /><p>One of the first things that impressed me was the fact that 26% of the lines are comments, which is something I'm glad of, considering how hard it can be to maintain such a large project, specially if someone else who never got in touch with this code needs to change or add some functionality or worse: correct a bug. However, there is a trick here which may help SourceMonitor to show a percentage way high from an intuitive value: I usually comment functions in <a href="http://www.stack.nl/~dimitri/doxygen/docblocks.html" target="_blank">Doxygen style</a>, so one to two lines are 'wasted' in spite of code clarity.</p><p>Regarding real statements, 12,765 lines mean about 37% of the total line count. This may look like an unbelievable lie, but actually it's due to many blank lines and comments that improve code readability. SourceMonitor's help clearly explains what 'statements' mean for C coding: "<em>Statements: in C, computational statements are terminated with a semicolon character. Branches such as if, for, while, and goto are also counted as statements. Preprocessor directives #include, #define, and #undef are counted as statements. All other preprocessor directives are ignored. In addition all statements between an #else or #elif statement and its closing #endif statement are ignored, to eliminate fractured block</em>"</p><p>Another interesting value is the one regarding the average of statements per function. Modularization and splitting code into relatively is a well known good practice that helps to ease code understanding and extension and also bug solving.</p><p>There are other metrics not calculated by SourceMonitor which would be nice to investigate, like preprocessor usage (#define, #else, #if, etc) which is something I often abuse of (in a good sense). It would be nice to be able to count the number of defined macros and macro usage too.</p><p>It is also important to remember that code metrics is just one side of the code. Lines can be counted and many statistics can be plotted but code organization is not something easy to measure. I could now say that I spent 26% of the time writing comments, which would sound scary to some people. I could also say I spent 37% of the time coding real statements. Both are big lies. Most of the time is spent thinking on how to implement this or that functionality and probably testing it does right (debugging takes time too). Coding is usually quite straight forward once one's brain is organized: that is, of course, not measurable with SourceMonitor.</p><p><strong>UPDATE:</strong> I downloaded <a href="http://cloc.sourceforge.net/" target="_blank">cloc</a> and ran it over the same code, obtaining nearly 7200 blank lines which is about 21%, which I guess should have it's own post ;) The linux kernel 2.6.26 had about 13% of blank lines (see <a href="http://www.chineselinuxuniversity.net/courses/kernel/introductions/20291.shtml" target="_blank">here</a>), I guess I might be overcoding for beauty...</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-60634281175377474292009-02-18T22:10:00.006-02:002009-05-04T23:44:52.360-03:00Fighting spam with GMail<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPqkRO-QOntD0c3n6C9ytLiWOYVWqOml4Hj3RE2ODz4p58jnZ2VmcSIpE2BdbDT-oeIBjWKBsE8eUOLpvEgdkCBUjkVPA-oR7gOAhWyhLQ05EOXE8Z8op2dUl5OhObVJ-11aFscPRAEl58/s1600-h/gmail-logo.gif"><img style="float:left; margin:0 10px 10px 0;cursor:pointer; cursor:hand;width: 143px; height: 59px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPqkRO-QOntD0c3n6C9ytLiWOYVWqOml4Hj3RE2ODz4p58jnZ2VmcSIpE2BdbDT-oeIBjWKBsE8eUOLpvEgdkCBUjkVPA-oR7gOAhWyhLQ05EOXE8Z8op2dUl5OhObVJ-11aFscPRAEl58/s320/gmail-logo.gif" border="0" alt="" id="BLOGGER_PHOTO_ID_5304297276167016418" /></a><br /><p>This won't be a post related to programming. However I find this useful to fight spam with GMail.<br /></p>I usually get a lot of spam in my gmail account, probably because my name and surname are quite common (?) or who knows why. GMail filters spam quite good and once they're detected they're are sent to the Spam tab/mailbox. Since no system is perfect there are some non-spam emails that are treated as spam by gmail so I spend/waste some minutes every day to see if I can rescue a misreported spam email.<br />I know most of the spam contain some specific words so I tried using google's search engine inside GMail to simplify this horrible task. Here is what I copy-paste to the GMail search bar:<br /><br /><strong>in:spam pharmacy | cialis | viagra | replica | rep1ica | buy | cird | bedroom | watches | pills</strong><br /><br />The OR operator works great and then I can delete the messages that meet that criteria without worrying (well, I do worry a little but less than deleting them without any filter at all).<br /><p>I can say that 60% to 80% of spam I get contain one of those words.</p><p>_</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-27415316320556185032009-02-04T01:03:00.024-02:002009-05-04T22:04:55.603-03:00openAHRS: Extended vs Unscented Kalman Filter<p>I've been thinking on <a href="http://wiki.github.com/cbecker/openahrs" target="_blank">openAHRS</a> lately. Some days ago I found Sean D'Epagnier in FreeNode's #avr channel (IRC) and we started talking about his project and openAHRS, regarding sensor calibration and how things could evolve from now on.</p><p>Sean mentioned about the Sigma Point Kalman Filter (SPKF) and that it might improve performance for non-linear systems. I started searching for </p><p>papers on the Unscented Kalman Filter (UKF) and other information related to it.</p><p>After some tests I decided to compare the UKF with the EKF (Extended Kalman Filter) to see how good improvements are, and here are the results.</p><p>All input data was measured from the <a href="http://github.com/cbecker/openahrs/wikis/avr32-ahrs" target="_blank">AVR32 openAHRS port</a>. There are no precise calibrations, only some minor magnetometer ones and nothing else. The data was exported and UKF and EKF were implemented in Matlab.</p><p>The filters were tested under three different cases by exciting each rotation angle independently (or at least as far as independent as my hand could do it). There are peaks in the raw angles which are measured from accelerometer data, since a big deacceleration happened when I hit the table (on purpose) when I was getting close to 0 degrees.</p><p>I forgot to add the axis labels, but <em>angles are shown in radians on the y-axis and time (in samples at 50Hz) is on the x-axis.</em></p><p><span style="font-size:130%;">Results of exciting the Roll axis</span></p><p><span style="font-size:100%;">Both filters did well: <a href="http://carlosbecker.com.ar/C/kf/roll-fast-move-EKF.png" target="_blank">EKF</a> / <a href="http://carlosbecker.com.ar/C/kf/roll-fast-move-UKF.png" target="_blank">UKF</a>. UKF did converge faster to a true value than EKF. I have to mention that the noise covariance matrices were the same for both filters.</span></p><p><span style="font-size:130%;">Results of exciting the Pitch axis</span></p><p><span style="font-size:100%;">Something similar to the case above happens. <a href="http://carlosbecker.com.ar/C/kf/pitch-fast-move-EKF.png" target="_blank">Here</a> is the EKF one and <a href="http://carlosbecker.com.ar/C/kf/pitch-fast-move-UKF.png" target="_blank">there</a> the UKF. It seems that I've disturbed the other axis I shouldn't have modified.</span></p><p><span style="font-size:130%;">Results of exciting the Yaw (heading) axis</span></p><p>The yaw angle input is not affected from acceleration, at least not if the predicted pitch and roll are precise enough. This happens because yaw is calculated by using magnetic field sensing, so it will be quite accurate compared to the accelerometer readings. Here are the <a href="http://carlosbecker.com.ar/C/kf/heading-fast-move-EKF.png" target="_blank">EKF results</a> and here the <a href="http://carlosbecker.com.ar/C/kf/heading-fast-move-UKF.png" target="_blank">UKF ones</a>. </p><p>The EKF is a mess and the UKF doesn't do so well either. This has a simple explanation: lack of magnetometer calibration. I'll be adding some suggested code by Sean to see if it improves.</p><p><span style="font-size:130%;">EKF and instability</span></p><p>The serious problem with EKF is instability. When playing around with the noise variance matrices (both measurement and process noise) there are certain points where the filter loses stability.</p><p>It's very important to let the states and noise matrices adapt to the system and noises before perceptible movements are applied to the sensors. A way to avoid this is to save the state covariance matrix P so that the kalman filter only needs a small time to adapt once powered up.</p><p>All these concepts apply to UKF except that it is much more stable. I was able to 'play' with the noise matrices in a free way. It's important to notice that UKF converges much faster than EKF at startup, probably because of the second and third order predictions EKF is not able to compute.</p><p><span style="font-size:130%;">Kalman Tuning</span></p><p>The filter won't work without a minimal knowledge of how and what it is doing. It's important to understand what each coefficient in the noise matrices mean. For example, the filter needs to know that it should believe in the gyro bias estimates much more than in the accelerometers so that gyro data becomes credible in short-term measurements so tilt information does the same for long-terms. This also means that the gyro bias estimates will remain practically constant, changing their value slowly and thus adapting to temperature and time drifts.</p><p><span style="font-size:130%;">To do</span></p><p>There is a large ToDo list:</p><ul><li>Test if the EKF can be improved, specially the heading axis.</li><li>Implement SQ-UKF (Square Root KF) and/or UD-UKF since the classic UKF is really slow because of the matrix square root calculation.</li><li>Implement a robust calibration routine for all the sensors. Sean told me some nice ideas that could greatly improve precision.</li></ul>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0tag:blogger.com,1999:blog-8391506498310459678.post-82763603192479375392009-01-27T18:35:00.003-02:002009-01-27T19:12:59.474-02:00Quick text compression<p>Recently I faced a problem related to short text compression. The idea was to reduce the space needed to save SMS messages. Since each SMS contains up to 160 characters the classic <a href="http://en.wikipedia.org/wiki/LZW" target="_blank">LZW</a> or <a href="http://en.wikipedia.org/wiki/Huffman_coding" target="_blank">Huffman</a> methods won't work out-of-the-box, mostly because of the size of the resulting dictionary. It is even worse if we consider that most messages are less than 80 characters long.</p><p>Finally I decided to use a fixed dictionary and a sort of hybrid Huffman code compression (which isn't Huffman at all, but it retains some similarity -somehow). Then I started looking for letter, digraph and trigraph probability in words and texts. There are many resources on the net like <a href="http://www.fortunecity.com/skyscraper/coding/379/lesson7.htm" target="_blank">this</a> and <a href="http://www.simonsingh.net/The_Black_Chamber/frequencyanalysis.html" target="_blank">this one</a> where symbol probability is listed for different languages, including Spanish which was the one I used.</p><p>The compression algorithm tries to use the minimum number of bits to encode frequent letters/digraphs/trigraphs. It is not optimal since the dictionary is fixed but it does a good job, reducing message size to 60-70% on most cases. If the right text is picked then it can be reduced to 30% but that is cheating, of course! The space character is one of the most used ones along with the 'e' letter (Spanish at least). Trigraphs and digraphs also play an important role in compression.</p><p>Lower/uppercase letters is another issue, but since SMS messages are mostly written in lowercase or uppercase that is not a problem. A trick is to invert the whole text to see which text gets the best compression ratio. This is quite fast since the algorithm is simple and the strings are short. Another trick would be to provide more than one dictionary (maybe three or four) and see which one does better with the desired message. The resulting space overhead is about two or three bits which should be acceptable for long messages.</p><p>Another possibility is to compress many messages together with Huffman or any other compression method. The drawback is that the message won't be a unit itself and then message management becomes messy.</p>CjBhttp://www.blogger.com/profile/03327901307513345630noreply@blogger.com0