tnorth ~ blog

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

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.

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.

Photographie

Panoramas

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

pano_leman

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.

jeudi, octobre 8 2009

Un peu d'informatique...

Programmation

D'abord, le code du programme décrit dans le post précédent est maintenant disponible. Voir la page associée.

Linux sur NSLU2

Juste un petit retour d'expérience sur l'installation de Debian sur un NSLU2. Le NSLU2 est un NAS (Network Attached Storage), qui consiste en fait en un petit ordinateur avec processeur XScale (ARM) à 266Mhz et 32Mb de ram. Ce qui veut dire qu'on peut y installer un de nos systèmes préférés. Il existe une multitude d'autres choses libres à y installer, mais mon choix s'est porté sur Debian. L'installation est très simple et prends environ 2 heures.

Pourquoi faire ?

Cela permet un accès total à la machine. On peut ainsi avoir un accès SSH à cette machine et y mettre à peu près n'importe quoi. Très basse consommation de l'ordre de 4W, c'est une machine idéale pour faire ses sauvegardes et partager des données sur un réseau local. nslu2-debian

dimanche, septembre 27 2009

L'algorithme de Dijkstra appliqué à des images

Maintenant que l'année académique recommence, il est temps de publier un travail effectué dans le cadre des études : je ne vais pas m'étendre là dessus, et les intéressés pourrons consulter le poster associé ici.

Dans ce travail, le très connu algorithme de Dijkstra a été utilisé pour chercher un plus court chemin dans des images du fond de l'oeil.

Introduction

L'algorithme en question peut s'appliquer à énormément de choses différentes. Il est par exemple utilisé dans le protocole ''open shortest path first'' pour le routage IP, ou autres applications "graphes et réseaux". De même, il sert à assister des algorithmes d'intelligence artificielle pour déterminer le chemin le plus court pour déplacer, dans l'exemple d'un jeu, un personnage d'un endroit à un autre d'une manière efficace.

Revenons au cas d'une image: la création d'un graphe dans ce cas devient bien moins générale, et se réduit à des réseaux ou chaque sommet du graphe n'est relié qu'à ses voisins (géographiques) directs. Chaque lien est doté d'un coût, qui décrit s'il est aisé ou non de passer du pixel actuel au pixel visé. On pourra ainsi associer à chaque pixel de l'image un sommet, et à chaque lien entre ce pixel et ses voisins une arête.

Et de façon similaire, on pourrait créer une grille représentant un terrain virtuel. Le coût de déplacement pourrait être représentatif de l'altitude à grimper, ou du type d'obstacles à franchir.

Implémentation C

Il existe donc beaucoup d'implémentations de cet algorithme dans pas mal de langages de programmation différents. Néanmoins, je n'ai pas réellement trouvé d'algorithme écrit en C pur qui implémentent Dijkstra avec une complexité en dessous de O(N²). En voici donc une version, écrite pour appliquer l'algorithme sur des images, pour le moment restreint à deux dimensions. Il serait très facile de le modifier pour ajouter une 3ème dimension!

Astuces pour réduire le temps d'exécution

Exécuter Dijkstra prend du temps pour deux choses:

  1. Il faut créer un graphe à partir des données (l'image par exemple), en temps O(N)N est le nombre de sommets
  2. Il faut calculer le chemin le plus court pour arriver du point de départ au point de destination, en temps O(|E+N| log(N))E est le nombre d'arêtes.

Dans le cas d'images, augmenter chaque cote d'un facteur deux revient à multiplier par 4 le nombre de sommets. Autant la création du réseau que l'algorithme vont nécessiter du temps de calcul !

La proposition est alors la suivante : redimensionner le graphe (= l'image) pour y calculer un plus court chemin. Ensuite, définir une zone de travail autour de ce chemin, et recalculer le chemin le plus court sur l'image pleine résolution. Attention: la garantie d'obtenir le plus court chemin est perdue. Par contre, cela permet d'obtenir rapidement un "suffisamment" bon chemin.

Multi-res_scale Indication du temps de calcul en fonction de la taille de l'image (cf légende). Utiliser la multi-résolution permet de gagner beaucoup de temps sur les grosses images, ainsi que de l'occupation mémoire.

Applications

Aperçu interactif de l'algorithme

Peut-être visualisé dans un navigateur à jour ici : Dijkstra pas à pas Chaque click fait avancer l'algorithme d'un pas.

Labyrinthes

Il est possible de résoudre des labyrinthes:

Dijkstra_maze

Il a fallu moins de 2 secondes pour charger les images et retrouver le chemin sur l'image complète (clickez l'image)

Suivi de vaisseaux sanguins

vaisseau

Récupérer le code

Tout est disponible sur bitbucket.

Code C pur

Il faut regarder le dossier tests/ et s'en inspirer pour utiliser Dijkstra. Pour le moment, aucune interface robuste ou programme user-friendly n'a été préparé pour l'utiliser.

Module C pour Python

Une fois compilé avec la méthode standard, le module ne comporte que 3-4 fonctions très simples à utiliser. On se référera au fichier de test disponible dans le dossier du module.

jeudi, septembre 17 2009

Quelques nouvelles

L'été a été bien rempli, et maintenant que les cours ont redémarré, je trouve une minute pour écrire quelque chose ici.

Vacances

Cet été, ce sont les mariages qui m'ont beaucoup occupés, mais ça vallait le coup. En voici un aperçu: pano_small.jpg Panorama depuis Perroy

ballons.jpg Lâché de ballons nocturne

Après cela, ce sont quelques jours de marche très agréables que j'ai pu faire avec des amis, dans de magnifiques paysages à la frontière entre les Grisons et le Tessin.

pano1.jpg

DSC_0055.JPG Un temps parfois maussade mais très agréable pour la marche !

Et finalement une ambiance complètement différente avec un séjour autour de Montréal.DSC_0466.JPG Le quartier du Vieux-Port vu depuis le sud de Montréal, avec la tour de l'horloge.

Programmation

Le temps finalement de retoucher à photomerge. Mais qu'est-ce donc que cela ? Une application réalisée en collaboration avec un geek, qui permet de fusionner tout simplement des images. On y trouve un intérêt lorsque l'on veut assembler des photos du ciel afin de faire apparaître des trainées. Pourquoi assembler plusieurs clichés à la place de faire une longue pose ?

  • Parce que certains appareils ne le permettent pas
  • On peut ainsi éviter de tout jeter si une source de lumière ponctuelle éclaire l'appareil
  • On peut créer des effets sympatiques
  • etc.

Cette version permet d'ajuster la mémoire nécessaire à effectuer l'opération. Si l'on néglige le fait que le programme est en développement et n'offre pas d'interface graphique, on peut le comparer à celui-ci. photomerge devrait être un peu plus rapide.

Le résultat obligatoire à partir de 111 images de 3888x2592 pixels gentillement fournies par Philippe. out.jpg Temps de calcul: 1m17s

Plus à venir côté programmation certainement bientôt, et peut-être de nouvelles photos ? Celles de ce post sont disponibles en plus grand dans la galerie réservée

- page 1 de 5