coucou747

Ce blog présente principalement les évolutions du compilateur metalang : les nouveaux backends, les nouvelles corrections de bugs, les nouvelles features, nouvaux tests, son utilisation dans le cadre du concours prologin.

le 02/01/2015

Comparer des images ?

Depuis longtemps, je souhaite me faire un outil qui permettrait de manager des images, plus récement, je me suis posé la question : si tu cherchais 10 photos à imprimer, comment les séléctionnerais tu ? J'ai donc cherché à faire un logiciel qui permet de séléctionner ou de rejeter des photos, à partir d'une séléction initiale, on complète la gallerie par des photos qui ressemblent plus aux photos séléctionnées qu'aux photos rejetées. J'ai toujours aimé les algorithmes qui retravaillent ou analysent des images, mais faire un produit de ce genre n'a pas vraiment de sens car gimp fonctionne très bien pour ça. Par contre, pour la recherche de similitudes dans une base de données, il n'existe pas grand chose.

Cet article : Algorithmes pour le traitement de l'image explique plusieurs choses intéressantes pour traiter des images et reconaitre des éléments dedans.

Pour réaliser ce logiciel, il faut donc avoir une fonction de score qui permet de comparer les similitudes entre deux images. Pour réaliser ça, on convertit les images en HSL (couleur, lumière et saturation), ou coupe les images en 9 rectangles (le centre, la gauche, la droite, le haut, le bas et les 4 coins) on fait un histogramme par composante, et on se sert de ça pour comparer deux images.

Couper l'image en 9 permet de mettre des poids sur les différents morceaux de l'image.

J'ai décidé de réaliser l'analyse de l'image en caml, puis l'interface et la recherche en javascript. le type de l'histogramme ressemble à ça :

type square_histogramme = {
  h : int array;
  s : int array;
  l : int array;
}
type histogramme = square_histogramme array

let histogramme_position (sx, sy) (x, y) =
  let x = x * 3 / sx in
  let y = y * 3 / sy in
  x + y * 3

let add_histogramme_hsl histogramme size x y (h, s, l) =
  let pos = histogramme_position size (x, y) in
  let h = clamp 0 9 (int_of_float ( h *. 10. /. 360. )) in
  let s = clamp 0 9 (int_of_float ( s *. 10. )) in
  let l = clamp 0 9 (int_of_float ( l *. 10. )) in
  histogramme.(pos).h.(h) <- histogramme.(pos).h.(h) + 1;
  histogramme.(pos).s.(s) <- histogramme.(pos).s.(s) + 1;
  histogramme.(pos).l.(l) <- histogramme.(pos).l.(l) + 1;
  ()

On voit ici la fonction qui permet de remplir l'histogramme. Elle doit-être appellée une fois par pixel. Elle permet de remplir un histogramme à 10 batons. On pourrait peut-être pondérer cet histogramme en ajoutant non pas 1 mais la différence avec le centre du baton, ça aurait peut-être des résultats intéressants, je n'ai pas testé.

let rgbf2hsl (r', g', b') =
  let cmax = max r' @$ max g' b' in
  let cmin = min r' @$ min g' b' in
  let delta = cmax -. cmin in
  let l = (cmax +. cmin) /. 2. in
  let s = if delta = 0. then 0. else delta /. (1. -. abs_float (2. *. l -. 1.)) in
  let h = if cmax = r' then 60. *. ( mod_float ((g' -. b') /. delta) 6.)
    else if cmax = g'  then 60. *. (((b' -. r') /. delta) +. 2.)
                       else 60. *. (((r' -. g') /. delta) +. 4.)
  in h, s, l

let hsl2rgbf (h, s, l) =
  let c = (1. -. abs_float (2. *. l -. 1.)) *. s in
  let x = c *. (1. -. abs_float ( (mod_float (h /. 60.) 2.) -. 1.)) in
  let x = if is_nan x then 0. else x in
  let m = l -. c /. 2. in
  let r', g', b' = if h < 60. then (c, x, 0.)
    else if h < 120. then (x, c, 0.)
    else if h < 180. then (0., c, x)
    else if h < 240. then (0., x, c)
    else if h < 300. then (x, 0., c)
    else (c, 0., x)
  in (r' +. m, g' +. m, b' +. m)

Ces deux fonctions transforment une couleur rgb (en float entre 0 et 1) en hsl, la fonction réciproque est aussi fournie.

Coté javascript, ce qui compte c'est la fonction qui permet de comparer deux histogrammes :

    var score_match_square = function (imga, imgb){
        var totala = 0, totalb = 0;
        for (var i = 0; i < imga.length; i ++){
            totala += imga[i];
            totalb += imgb[i];
        }
        var deplaces = 0, a = 0, b = 0;
        for (var i = 0; i < imga.length; i ++){
            a += imga[i] / totala;
            b += imgb[i] / totalb;
            if (a < b){
                deplaces += b - a;
                b -= a;
                a = 0;
            }else{
                deplaces += a - b;
                a -= b;
                b = 0;
            }
        }
        deplaces += a + b;
        return deplaces;
    };

a et b contiennent combien il reste à déplacer depuis chaque histogramme. Au moins l'un des deux est à 0. La fonction renvoie le pourcentage de pixels qui doivent être déplacés pour que les deux histogrammes soient équivalents.

En cliquant sur trois images, on obtient le résultat suivant :

En conclusion, je dirais que j'ai un prototype sympa pour de l'analyse d'images. Ce qui me manque c'est la lecture des données exif : au moins pour réorienter les images, peut-être pour trouver des informations sur la date de la prise, l'heure, le lieu, voir les paramètres de la photo : objectif, focale, grossissement, iso. On pourrait envisager de l'analyse de contours, pour savoir au moins ou sont les lignes sur l'image, et la zone ou l'image est la plus nette. Lire les données exif n'a pas l'air simple en ocaml. Il n'existe pas de librairie serieuse sur ce sujet. Ces analyses demandent un prétraitement plus lourd, ça complexifierait le moteur et ralentirait l'analyse, mais je pense qu'ils sont d'intéressantes pistes pour la suite de ce prototype.

Voici le lien vers le bitbucket sur lequel ce projet se trouve.

Références

bitbucket.org le dépot
ftp-sop.inria.fr un article sur le traitement d'images

Dans Catégories/Misc.

Sujets : #photo #ocaml #javascript