tnorth ~ blog

Aller au contenu | Aller au menu | Aller à la recherche

mercredi, avril 4 2012

Arduino and other avr-gcc users: feedback needed!

An update to avr-gcc-4.7.0 is on its way, but before I push it to Fedora > 16 (and F-16 ?), I would like to have some feedback and know if it breaks something for you. Especially, we had a nasty delay bug that we would like to avoid this time.

If you have a few minutes, please download and install avr-binutils-2.22 and avr-gcc-4.7.0 (f15, f16) / avr-gcc-cpp ( f15, f16), and try some working code.

I don't have a device to test it, so all I can say is that my project still compile with this new release.

mardi, décembre 6 2011

Numexpr 2.0 landed into Fedora 16

As Numexpr was added to the Fedora repositories only recently, it may be time to quickly mention what it is and what is new in version 2.0. According to Numexpr website:

The numexpr package evaluates multiple-operator array expressions many times faster than NumPy can. It accepts the expression as a string, analyzes it, rewrites it more efficiently, and compiles it to faster Python code on the fly. It's the next best thing to writing the expression in C and compiling it with a specialized just-in-time (JIT) compiler, i.e. it does not require a compiler at runtime.

Example use:

In [1]: import numpy as np
In [2]: import numexpr as ne
In [3]: a = np.random.rand(1e6)
In [4]: b = np.random.rand(1e6)
In [5]: timeit ne.evaluate('a**b')
10 loops, best of 3: 29.5 ms per loop

Also, array slicing can be used with the local_dict argument:

In [10]: timeit ne.evaluate('c**d', \
        local_dict={'c':a[1:], 'd':b[:-1]})
10 loops, best of 3: 28 ms per loop

Computations are multithreaded and bypass the GIL. Version 2.0 comes with a new virtual machine which speeds up broadcasting operations, on-the-fly translation of dtypes and Fortran-ordered arrays. The associated drawback is a slower start of the virtual machine. But overall, the gain is important for large arrays.

With a low number of elements and simple calculations, numexpr should not be used:

In [15]: %timeit a**2 + b**2 - 2*a*b
100000 loops, best of 3: 13 us per loop
In [16]: %timeit ne.evaluate('a**2 + b**2 - 2*a*b')
10000 loops, best of 3: 31.1 us per loop

However, with a higher complexity of operations, numexpr can come pretty close to NumPy on a small amount of elements.

Around 10⁶ elements, a good improvement is indeed visible:

In [7]: a = np.random.rand(1e6)
In [8]: b = np.random.rand(1e6)
In [12]: %timeit a**2 + b**2 - 2*a*b
100 loops, best of 3: 19.5 ms per loop
In [10]: %timeit ne.evaluate('a**2 + b**2 - 2*a*b')
100 loops, best of 3: 2.55 ms per loop

The following graph shows the impact of the number of threads on the computation time. numexpr.evaluate() was used with out=an_existing_array to avoid the creation of a new array as output. Each point was computed 9 times. Each plotted point is the median of this set, and the error bars show the best/worst case of the time ratio. Numpy vs Numexpr For some reason, there is a gap around 2000 elements, when the computations are multithreaded. Any suggestion about its origin would be welcome !

Overall, Numexpr is a powerful python module, speeding up array operations while reducing their memory requirements. Thanks to the developers. A list of supported functions is available at Numexpr website. By the way, PyTables makes a good use of Numexpr. I might write about that soon.

vendredi, novembre 25 2011

Making the update of personal repositories easy

Like many people here on the planet, I have personal repositories at, where I keep updates (of the latest version of Rawtherapee (a program whose development is going quickly) and a build of Gnuplot CVS, for a new feature I do need.)

I am wondering how most people manage those repositories, and guess that most of them have their own scripts to help in the process. Because I couldn't find such scripts on the wiki, I publish here a small python script which makes the process easy and fast.

In the past, I used to send scratch builds to Koji with the new source package, one per build target. Then it was necessary to download each RPMs and SRPMs, update a local repository (using createrepo), which creates delta-RPMs and adds new packages. Signing and uploading the repository with rsync was the last step, semi-automated.

It became quite time consuming, especially with the fact that the build download was to be done manually. With the following hack-ish script, all steps from the creation of the SRPM to the upload are automated. Only your GPG passphrase is required (if you have one, but you should :)) to sign the RPMs.

The script is written in Python and uses both the Mechanize and Threading module to send jobs in parallel to Koji. It will then download the builds packages for each architecture. The single script and the complete Mercurial repository can be found at Bitbucket.

Usage example:

It is here assumed that you have a SPEC file in ~/rpmbuild/SPECS/ which builds with rpmbuild -bs.

python mypackage

The SRPM will be built for mypackage into ~/rpmbuild/SRPMS/. At the first run, a folder mypackage/ is created in the current directory. For future runs, a folder mypackage_old/ is created and will be used as a source for the creation of drpms. The script will then upload the SRPM for each target and poll Koji, waiting for the build to finish. Whenever a build is finished for a target, it will be downloaded into an appropriate subdirectory of mypackage/. When all builds are downloaded for each target, the user is asked to provide its passphrase to sign the RPMS. createrepo is then called for all subdirectories of mypackage/.

python mypackage repoinfo

This optional command will create a .repo file for /etc/yum.repo.d/ into mypackage/.

python mypackage upload

will finally upload the whole repository to your space at At any time, the command python mypackage finalize can be used to sign the packages and run createrepo.

Of course, there is room for improvement in the code. Suggestions welcome!

vendredi, février 4 2011

Thoughts about Bing road detect API and vectorization

Yesterday, the Bing Maps blog announced the availability of their experimental service for road detection.

That is good news for OpenStreetMap, especially because this service is easily accessible and can already be used inside JOSM to assist the mapper.

It can also be tested at qualitystreetmap However, I could not find any information about how it works, but I suspect they use a shortest-path algorithm such as Dijkstra, perhaps with some heuristic like A*.

It works pretty well especially when the road is not too sinuous. Unfortunately, the results are worse when the road makes important angles, encouraging the algorithm to take a faulty shortcut.

Bing road detection took a shortcut Faulty road extraction

Assuming that Dijkstra was used, the quality of the results are highly dependent on the pre-processing step. The images need to be desaturated, and some processing will increase the chances for the algorithm to follow exactly the roads.

I have been playing around today, running an old program implementing the Dijkstra algorithm in C, here is what I get:

Road detection using Dijkstra Shortest-path computation with Dijkstra algorithm

Of course, that is far from being perfect: it looks like Dijkstra is drunk (thanks Philippe), and the selected path does not stay centered on the road. A post processing step for smoothing could be used (even decimation could do a good job), or the preprocessing may also need to be fine-tuned. An accurate and robust road extraction is a matter of trade-offs, and this example might not be representative of the real performances of the algorithm used at Bing maps.

To obtain that, the cost function (distance) of the Dijkstra algorithm is the most straightforward one: the cost from one to the next pixel is related to the difference of their intensity. (after some smoothing.) Dijkstra wants to minimize the cost of the path, and needs to be comfortable on the road. The preprocessing that I used for that is simply a histogram equalization after desaturating by lightness, and finally inverting colors. This way, the roads are very dark, and the travel cost is minimized when they are followed. A good way to visualize that is to see this gray-level picture as an altitude map, where the darkest pixels represent the lowest altitude, while the brightest ones are at higher altitude. The road forms some kind of valley. As mentioned before, sometimes a lot of the road pixels lie in the 0-altitude level, and the cost for moving around the center of the road is zero: this leads to a sinuous path. This can be fixed by applying a slight amount of Gaussian blur, which will bend the bottom of this valley and force a straighter path.

Another potentially interesting feature is the possibility to decrease the computation time when long paths are to be found. A first pass is done on a lower resolution image, and a region of interest is defined around that approximate path. Then, only the pixels of this region of interest are used to compute the path at higher resolution.

Multi-res computation Schematics of the multi-resolution behaviour

Speaking of computation time, the screenshot shown above requires 60ms to compute the path (no multi-resolution). Most of the time is spent creating the initial graph (478ms). It can be used later for other computation in that area.

I would be interested to know more about the algorithm implemented at Bing maps, how they concretely handle the required image processing to achieve vectorization. Also, I am wondering how interesting it is when mapping a region: road extraction is already quite easy to do "by hand". May be that the real gain would be the ability to automatically extract roads for a whole residential area, and just let the user check and fix it.

The source for the Dijkstra algorithm can be found here. You may want to try the Python module, which is easier to use than the multiple tests presents in the source with hardcoded values (sorry for that.) Go to src/python_mod3, build and install the module. Finally, look at the file to find out how to run it.

lundi, janvier 11 2010

Nouvelles diverses après une longue absence

Il n'est quand même pas facile de garder un blog à jour... je me demande d'ailleurs comment font les gens comme Philippe pour proposer une image par jour !

Je m'efforcerai d'indiquer ici un peu en vrac à nouveau quelques nouvelles un peu techniques mais amusantes de ces dernières semaines.

OpenStreetMap et GPS différentiel

GPS garmin EGNOS Depuis le mois d'octobre, on peut profiter du système EGNOS, composé de stations terrestres qui corrigent les signaux de positionnement du système GPS. Ce dernier est compatible avec le système américain WAAS qui est déjà utilisable depuis de nombreuses années avec la plupart des récepteurs GPS. ''Sur l'image ci-contre, le symbole 'D' visible dans les indicateurs de signaux satellites indiquent une correction EGNOS. '' Tout cela pour dire que notre outil de prédiléction pour la cartographie via OpenStreetMap s'en voit plus fiable depuis octobre 2009, et tout cela sans changer ses habitudes ! (à part paramétrer son récepteur GPS en mode WAAS, qui peut être un peu plus gourmand en batteries).

carte voie romaine J'ai ainsi pu prendre le temps d'ajouter quelques chemins sur la carte, dans les environs de Crans ainsi que la voie romaine se rendant à St-Cergue depuis Nyon. La carte Nyonnaise est encore assez incomplète, et beaucoup de petites rues sont absentes de la carte ou n'ont pas été nommées. Espérons que d'autres contributeurs (leur nombre semble augmenter dans la région) puissent également contribuer afin de la rendre aussi bonne que les alternatives non-libres.

L'utilisation de JOSM pour contribuer devient aisée (voir un ancien post à ce propos).

On peut également noter l'arrivée de Mapzen, un autre éditeur pour OSM, via le web (malheureusment en Flash), mais tout à fait fonctionnel.



Quelques panoramas fait à l'aide d'Hugin, et présent dans la galerie. Hugin, dans ses dernières versions, est réellement pratique à utiliser et très rapide. Il a été en particulier présenté sur ce blog d'un nerd. En voici un résultat, composition de 22 photos. pano_lavaux


Nouveau logiciel libre

On apprend également la sortie de RawTherapee, anciennement propriétaire, qui permet de traiter les images aux format RAW issus de la plupart des appareils numériques. Il s'avère rapide et permet des réglages très fins. On obtient rapidement de bons résultats. Un mode "batch" permet d'effectuer le rendu en série avec un set de paramètres choisis. Disponible en version 3.0-alpha, on peut espérer beaucoup de ce logiciel qui se prend en main facilement.

Attention: il ne compile pas avec gcc-4.4 en i586, c'est un bug de GCC corrigé dans la version 4.5

Physique et logiciels

Hier est sortie la version 4.0 de pymecavideo, qui est un logiciel libre destiné aux enseignants de physique. Ce dernier permet l'étude des mouvements dans différents référentiels. Simple à utiliser et très parlant, on ne peut qu'espérer qu'il se répande dans les classes. pymecavideo 4.0 Aperçu de l'interface de pymecavideo. Après avoir sélectionné quelques points sur la vidéo, les vecteurs vitesses sont visibles. Le logiciel propose également des vidéos du mouvement dans l'un ou l'autre des référentiels décrits.

En attendant une éventuelle inclusion dans les distributions, j'ai rapidement fait des packages pour Fedora 11, qui peuvent être téléchargés en fonction de votre architecture sur Koji (Je ne sais pas combien de temps ce lien va être valide, voici donc une version pour i586 de pymecavideo, mise à jour (attention même numéro de révision)) Ce logiciel nécessite VLC et ffmpeg pour fonctionner. Pour Fedora, ils sont disponibles dans le dépôt rpmfusion-free.

- page 1 de 6