Page précédente [1] [2] [3] [4] [5] [6] [7] Page suivante
Installation CUDA
Souhaitant accélérer un calcul simple sur GPU, mon regard s'est tout naturellement tourné vers CUDA. Après avoir vérifié que la carte graphique de mon portable supportait CUDA, je me suis mis en quête de tutoriaux pour l'installation proprement dite. Ayant eu quelques mésaventures de ce côté-là, je poste ici un court billet sur la manière dont j'ai procédé pour l'installation de CUDA v4.0 sur une distribution de type Ubuntu Jaunty (oui je sais, c'est assez vieux).
Il faut commencer par faire le ménage en désinstallant tous les drivers NVIDIA présents sur la machine et installer la dernière version disponible à cette adresse. Ensuite, il faut télécharger le SDK et le toolkit sur cette page. L'installation est déclenchée par les commandes suivantes :
sudo ./cudatoolkit_4.0.17_linux_32_ubuntu10.10.run
sudo ./gpucomputingsdk_4.0.17_linux.run
Pour ma part, j'ai gardé les chemins d'installation par défaut. Pour terminer, il reste à renseigner le contenu des variables d'environnement dans votre .bashrc :
export PATH=$PATH:/usr/local/cuda/bin
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/cuda/lib
- Code source : [ZIP]
Dépôts Jaunty
Depuis son lancement en octobre 2004, Ubuntu est devenue l'une des distributions les plus populaires avec des millions d'utilisateurs chez les particuliers, les écoles, les entreprises et les gouvernements. Néanmoins, les depôts officiels de chaque version ne sont supportés que pour une durée fixée. C'est par exemple le cas pour Jaunty Jackalope dont les dépôts se sont plus disponibles depuis octobre 2010. Il est donc nécessaire de réactualiser la liste des dépôts contenue dans le fichier /etc/apt/sources.list :
###############################################################################
## UBUNTU JAUNTY JACKALOPE - 9.04 - Date : 30/05/2011
##
## SOURCES.LIST GENERATOR Version 0.3-10.04
## http://sources-list.ubuntu-fr-secours.org
###############################################################################
# deb cdrom:[Ubuntu 9.04 _Jaunty Jackalope_ - Release i386 (20090420.1)]/ jaunty main restricted
## DEPOTS PRINCIPAUX
deb http://old-releases.ubuntu.com/ubuntu jaunty main
# deb-src http://archive.ubuntu.com/ubuntu jaunty main
## DEPOTS RESTRICTED
deb http://old-releases.ubuntu.com/ubuntu jaunty restricted
# deb-src http://archive.ubuntu.com/ubuntu jaunty restricted
## DEPOTS UNIVERSE (logiciels libres)
# deb http://archive.ubuntu.com/ubuntu jaunty universe
# deb-src http://archive.ubuntu.com/ubuntu jaunty universe
## DEPOTS MULTIVERSE (logiciels non-libres)
# deb http://archive.ubuntu.com/ubuntu jaunty multiverse
# deb-src http://archive.ubuntu.com/ubuntu jaunty multiverse
## DEPOTS DE MISES A JOUR EN PRES VERSION
# deb http://archive.ubuntu.com/ubuntu jaunty-proposed main restricted
# deb-src http://archive.ubuntu.com/ubuntu jaunty-proposed
## DEPOTS NON PRIS EN CHARGE
# deb http://archive.ubuntu.com/ubuntu jaunty-backports main restricted
# deb-src http://archive.ubuntu.com/ubuntu jaunty-backports
## DEPOTS DE MISES A JOUR DE SECURITE
deb http://old-releases.ubuntu.com/ubuntu jaunty-security main restricted
# deb-src http://archive.ubuntu.com/ubuntu jaunty-security
## DEPOTS DE MISES A JOUR IMPORTANTES
deb http://old-releases.ubuntu.com/ubuntu jaunty-updates main restricted
# deb-src http://archive.ubuntu.com/ubuntu jaunty-updates
## DEPOTS COMMERCIAUX
# deb http://archive.canonical.com/ubuntu jaunty partner
# deb-src http://archive.canonical.com/ubuntu jaunty partner
# deb http://archive.canonical.com/ubuntu jaunty-security partner
# deb-src http://archive.canonical.com/ubuntu jaunty-security partner
# deb http://archive.canonical.com/ubuntu jaunty-update
# Medibuntu
# deb http://fr.packages.medibuntu.org/ jaunty free non-free
# Iced-Tea
# deb http://people.ubuntu.com/~doko/ubuntu/ jaunty/
# deb-src http://people.ubuntu.com/~doko/ubuntu/ jaunty/
# WxWidgets.org
# deb http://apt.wxwidgets.org/ jaunty-wx main
# deb-src http://apt.wxwidgets.org/ jaunty-wx main
# Medibuntu
# deb http://fr.packages.medibuntu.org/ jaunty free non-free
# Xmms
deb http://www.pvv.ntnu.no/~knuta/xmms/jaunty ./
deb-src http://www.pvv.ntnu.no/~knuta/xmms/jaunty ./
Problème 3x+1
Selon Wikipédia, le problème 3x+1 (aussi appelé suite de Syracuse) d'un nombre entier $$N$$ est une suite d'entiers naturels définie par récurrence comme suit :
On pose $$u_0=N$$ et pour tout $$n \in \mathbb{N}$$, on a :
$$u_{n+1} = \left\{ \begin{array}{ll} \frac{u_n}{2} & \quad \mbox{si}~u_n~\mbox{est pair}\\ 3 u_n + 1 & \quad \mbox{si}~u_n~\mbox{est impair} \end{array} \right. $$
La conjecture de Syracuse affirme que $$\forall N>0$$, il existe un entier $$n \in \mathbb{N}$$ tel que $$u_n=1$$. Jusqu'à ce jour, la conjecture n'a pas encore été démontrée. Cependant, différentes voies ont été explorées. Par une approche statistique, on peut démontrer qu'un nombre est en moyenne multiplié par $$3/4$$ après deux itérations. Les ordinateurs représentent aussi une voie importante : l'étude systématique du comportement de cette suite pour de grands nombres à l'aide de puissants ordinateurs peut permettre de trouver un contre-exemple qui rendrait fausse cette conjecture.
Même si historiquement certaines conjectures se sont révélées fausses (cf. conjecture de Hirsh en 2010), ces éléments laissent penser que la conjecture a de bonnes chances d'être vraie. Le programme C++ ci-dessous prend en entrée un entier $N$ et donne en sortie la séquence de Syracuse.
- Code source : [ZIP]
Cartes de distance
Prenons une image binaire $$\mathcal{I}$$ définie sur $$\mathbb{R}^d$$ ($$d>0$$) et à valeur dans $$\{0,1\}$$. On note $$\mathcal{O} \subset \mathbb{R}^d$$ la partie "objet" et $$\mathcal{B}$$ la partie "fond" de $$\mathcal{I}$$. Le principe de la transformée de distance est de construire une image $$\mathcal{D}$$ où chaque pixel $$p \in \mathcal{B}$$ est égal à la plus petite distance à un pixel $$q \in \mathcal{O}$$ selon une métrique $$dist$$ (par exemple Euclidienne) :
$$\mathcal{D}(p) = \min{\{dist(p, q)~|~q~\in~\mathcal{O}\}}, \qquad \forall p \in \mathcal{B}.$$
Les cartes de distance se généralisent assez bien à des images en niveaux de gris (i.e à valeur dans $$\mathbb{R}$$). Les métriques basées sur le gradient sont celles que l'on rencontre le plus fréquemment dans la littérature. Citons-en deux : Weighted Distance Transform on Curved Space (WDTOCS) et Distance Transform on Curved Space (DTOCS) :
- WTOCS : $$dist(p,q) = \sqrt{\alpha (\mathcal{I}(p)-\mathcal{I}(q))^2 + |p-q|^2}, \qquad \alpha \in \mathbb{R}^+$$
- DTOCS : $$dist(p,q) = |\mathcal{I}(p)-\mathcal{I}(q)| + 1$$
Lorsque le paramètre $$\alpha$$ tend vers l'infini, le terme de gradient domine celui de la distance $$L_2$$. Cela permet de prendre en compte davantage le gradient lors du calcul de la carte de distance (cf. figure ci-dessous). Cela peut être intéressant dans le cas où les objets à segmenter sont longilignes (vaisseaux sanguins).
Dans la littérature, on recense principalement deux types d'algorithmes pour calculer une transformée de distance :
- Les algorithmes par propagation de fronts d'ondes : on propage les distances en partant de la partie "objet" $$\mathcal{O}$$. L'algorithme s'inspire de celui de Dijkstra. Les pixels à explorer sont stockés dans un tas minimum. La complexité est logarithmique en la taille de cette liste.
- Les algorithmes à balayage avec masques de Chamfrein. L'idée est d'alterner successivement un parcours forward et backward avec un demi-noyau $$K$$. La complexité est en $$O(|\mathcal{I}|\times|K|)$$.
Les deux familles d'algorithmes sont faciles et rapides à implémenter. Lorsqu'on utilise une métrique WDTOCS ou DTOCS, les algorithmes par propagation de fronts d'ondes sont plus rapides que ceux par balayage : la convergence est souvent très lente. Pour certaines applications, on peut néanmoins stopper prématurément le balayage en imposant un nombre d'itérations maximum. Cependant, il n'y a aucune garantie sur la qualité du résultat. A l'inverse, lorsqu'on utilise des métriques plus traditionnelles (Euclidienne, Manhattan, Checkerboard, etc.), les algorithmes par balayage sont plus rapides (quelques passes seulement) que les algorithmes par propagation de fronts d'ondes. Un des avantages des algorithmes par propagation de fronts d'ondes est de pouvoir stopper prématurément le calcul pour une distance qui soit supérieure ou égale à une valeur donnée. L'autre avantage est de pouvoir obtenir le diagramme de Voronoï en même temps que la carte de distance. Cela peut permettre par exemple de faire des calculs de rugosité sur l'image (cf. article de Ikonen).
Il reste cependant difficile de dire à quel point les métriques WDTOCS et DTOCS sont efficaces tant elles dépendent du contexte dans lequel elles sont utilisées. Néanmoins dans mon cas, elles ont plutôt donné de bons résultats pour segmenter des tumeurs pulmonaires. Dans le domaine du traitement d'images et de la vision par ordinateur, les cartes de distance sont souvent utilisées et servent de brique de base pour des algorithmes de plus haut niveau. Récemment, pour la rédaction d'un article d'un Workshop, j'ai eu besoin d'utiliser des cartes de distance pour à la fois pour :
- Mesurer les différences entre segmentations et vérités terrain avec des métriques basées sur la distance de Hausdorff.
- Poser un a priori sur la position de marqueurs saisis par l'utilisateur.
Pour le premier point, la distance de Hausdorff entre images binaires est souvent utilisé mais son calcul s'avère en pratique très long. En effet, l'algorithme naïf a une complexité en $$O(|\mathcal{O}_1|\times|\mathcal{O}_2|)$$ (où $$\mathcal{O}_k$$ désigne la partie "objet" pour l'image $$k$$). Un algorithme plus efficace existe : il suffit de calculer une carte de distance avec une métrique Euclidienne pour $$\mathcal{O}_1$$ et pour $$\mathcal{O}_2$$, puis de les parcourir pour extraire les distances maximales. La complexité devient linéaire en fonction du nombre de pixels de l'image. Pour le second point, j'avais besoin de pouvoir utiliser une métrique du style WDTOCS ou DTOCS. Au final, j'ai utilisé l'algorithme par propagation pour le premier point et l'algorithme par balayage pour le second.