dimanche 11 août 2013

Filtre de Sobel et SIMD [1]


Ce qui suit sera mon premier billet de blog. Rien de vraiment ambitieux, seulement, comme son titre l'indique, des notes de code. Aujourd'hui je compte implémenter un filtre de Sobel en utilisant les instructions SIMD (SSE2 plus précisément) ça prendra surement plus de temps de prévu enfin bon...here we go !

Qu'est ce qu'un filtre de Sobel ?


Un filtre de Sobel c'est un filtre (non ? :o)) qui transforme une image en une autre. Comme vous le savez sans doute, on peut représenter une image de manière abstraite par un tableau de nombres. Le tableau correspond à un écran, chaque élément de ce tableau est un pixel et le nombre représente la couleur associée à ce pixel. Si on a cette représentation en tête, l'application d'un filtre de Sobel sur une image ressemble à peu près à ça :


En fait c'est un peu plus compliqué que ça puisqu'on utilise deux "kernels" (cf. animation ci-dessus) légèrement différents :



L'application de ces deux kernels donne deux images différentes, on additionne ensuite les images pixel par pixel pour obtenir l'image finale.

Choix du format

Dans un premier temps, je vais travailler sur des images en niveau de gris. Reste à choisir un format. Après quelques minutes de recherche j'opte pour PGMB un format extrêmement simple :  
  • Les données sont en binaire
  • Supporte uniquement les niveaux de gris
  • 2D
  • Pas de compression
  • Ne contient qu'une seule image
La liste qui suit décrit de façon détaillée la forme des fichiers sous ce format. Je m'en servirai lorsque je devrai charger les images en mémoire...n'oubliez pas de vous y rapporter si le code ne vous paraît pas clair. Voici donc en quoi consiste un ficher .pgm :
  • Un nombre magique pour identifier le type de fichier : "P5" en ASCII.
  • Un espace
  • La largeur en ASCII décimal
  • Un espace
  • La hauteur en ASCII décimal
  • Un saut de ligne
  • La valeur de gris maximale en ASCII decimal comprise entre 0 et 255
  • Un saut de ligne
  • Les pixels sont stockés sur un octet entre 0 et la valeur maximale (ex :11111111 en binaire vaut 255 en décimal) et commencent en haut à gauche. La valeur 0 correspond au noir et la valeur maximale au blanc.

Bon maintenant que j'ai choisi le format, il me faudrait une image. Voici une photo du lac de St-Ferréol que j'ai prise le week-end dernier :


Une petite ligne de commande linux :

convert IMG_20130804_093756.jpg lac_st_ferreol.pgm

Et voici le résultat :


Maintenant que j'ai une superbe image au format pgm, je vais pouvoir passer au code ! :P

Lecture et Écriture

La première chose à faire c'est spécifier l'interface que l'on souhaite :

#ifndef __PGM_INTERFACE_H__
#define __PGM_INTERFACE_H__

#include <stdint.h>

static const uint16_t PGM_MAGIC = 0x3550;      //nombre magique
static const uint16_t BUFF_SIZE = 1 << 8;      //taille du tampon

/*Structure contenant l'image en niveaux de gris*/
struct greyscale_image {
    uint32_t width, height;     //lageur et hauteur
    uint8_t* pixels;            //pointeur vers les pixels
};

typedef struct greyscale_image greyscale_image;

/*Charge le fichier 'filename' dans l'image 'to_load'*/
void load_from_pgm(char* filename, greyscale_image* to_load);

/*Ecrit l'image 'to_write' dans le fichier 'filename'*/
void write_to_pgm(greyscale_image* to_write, char* filename);

#endif

L'entête stdint définie les types uint8_t, uint16_t et uint32_t qui correspondent des entiers positifs ou nuls de 8, 16 et 32 bits. Pour obtenir le fameux "nombre magique" du format PGMB en hexadécimal, il suffit d’exécuter la commande :
$ $ head -1 lac_st_ferreol.pgm | hexdump
0000000 3550 000a                              
0000003
Maintenant que tout est bien spécifié, je passe au .c. Je n'ai pas grand chose à dire de ce côté là mais j'attends vos commentaires et critiques avec impatience. Voici le résultat après quelques erreurs de compilation :
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "pgm_interface.h"

void load_from_pgm(char* filename, greyscale_image* to_load) {
    char buff[BUFF_SIZE];               //allocation d'un tampon
    FILE* file = fopen(filename, "r");  //ouverture du fichier

    if (file == NULL) {
        printf("Echec de l'ouverture du fichier en lecture.\n");
        return;
    }

    if(fgets(buff, sizeof buff, file) == NULL
       || *(uint16_t*)buff != PGM_MAGIC) {
        printf("Le fichier n'est pas au format PGMB.\n");
        return;
    }

    if (fgets(buff, sizeof buff, file) == NULL
        || sscanf(buff, "%d %d",
                  &(to_load->width),
                  &(to_load->height))  == EOF) {
        printf("L'entête du fichier est mal formée.\n");
        return;
    }

    //allocation de l'image
    to_load->pixels = (uint8_t*)malloc(sizeof(uint8_t) *
                                       to_load->width *
                                       to_load->height);
    if (to_load == NULL) {
        printf("Echec de l'allocation de l'image.\n");
        return;
    }

    fgets(buff, sizeof buff, file); //passe la ligne '255\n'
    
    //copie les pixels en mémoire
    fread(to_load->pixels, sizeof(uint8_t),  
          to_load->width * to_load->height, file);
    
    fclose(file);   //fermeture du fichier
}

void write_to_pgm(greyscale_image* to_write, char* filename) {
    FILE* file = fopen(filename, "w");  //ouverture du fichier

    if (file == NULL) {
        printf("Echec de l'ouverture du fichier en écriture.\n");
        return;
    }

    //écrit le nombre magique
    fwrite(&PGM_MAGIC, sizeof(uint8_t), sizeof PGM_MAGIC, file);

    //puis l'entête
    fprintf(file, "\n%d %d\n%d\n",to_write->width,
                                  to_write->height,
                                  1 << CHAR_BIT - 1);

    //et les données
    fwrite(to_write->pixels, sizeof(uint8_t),
                             to_write->width * to_write->height,
                             file);

    fclose(file);   //fermeture du fichier
}
Je pense que je vais m'arrêter là pour la première partie de ce billet. Vous pouvez trouver un programme de test et les sources dans le dépôt git associé à ce billet en suivant ce lien :

Aucun commentaire:

Enregistrer un commentaire