IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Comparaison d'images


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Comparaison d'images
    Bonjour,

    je suis a la recherche d'information sur la comparaison entre deux images.

    En gros j'ai deux ilages RGB en 24 Bit (le tout en memoire)

    et je voudrais les comparer (grossierement, pas pixel par pixel)

    Si quelqu'un a un lien ou des infos je suis preuneur,

    Merci.

  2. #2
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Comparer comment ? Savoir s'il y a des éléments communs ? Savoir si l'une est comprise dans l'autre ? ... ?
    Tu peux essayer un algorithme de corrélation.

  3. #3
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Il existe un tas de méthodes de comparaisons, l'une des plus rapides et plus efficaces étant peut-être la méthode ZNCC (zero normailzed cross correlation)... en gros ça fait une corrélation tout en s'affranchissant des différences de luminosité dans les images... Peut être aussi que c'est bien de l'efectuer en système HLS plus facile à la comparaison...

    A+
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  4. #4
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Faire une multiplication dans l'espace de Fourier puis revenir...
    S'il y a des pbs de luminosité, si c'est constant, ça ne change rien, sinon en faisant un test de corrélation sur le rang - rho de Spearman, l'équivalent du test de corrélation linéaire en non-linéaire -

  5. #5
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Citation Envoyé par Miles
    S'il y a des pbs de luminosité, si c'est constant, ça ne change rien
    Faux ! Si on prend deux images à comparer avec l'image de référence, les calculs peuvent être faussés et il peut arriver que l'image la plus ressemblante des 2 à l'image de référence ne soit pas celle qui donne le plus fort score de corrélation... (si par exemple l'image 1 est à luminosité constante mais sombre et l'image 2 à luminosité constante mais claire)...

    Le tout c'est que ça soit constant dans toutes les images auquel cas effectivement ça ne change rien, cas qui n'arrive quasi jamais...
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  6. #6
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    T'as raison, vivement les vacances - comment peut-on sortir des trucs comme ça... -

  7. #7
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    A la réflexion, je ne serai pas si catégorique que ce que tu dis. En effet, la corrélation est indépendante du facteur d'échelle. Donc si une image est plus lumineuse qu'une autre, en prenant un facteur d'échelle, on peut facilement les comparer visuellement et se rendre compte de laquelle est la plus corrélée linéairement à l'image de référence.
    Tu dis :
    il peut arriver que l'image la plus ressemblante des 2 à l'image de référence ne soit pas celle qui donne le plus fort score de corrélation...
    Si ton critère de ressemblance est la corrélation linéaire, alors ce que tu dis est logiquement faux. Si ton critère est ce que l'oeil voit, il est alors plus judicieux d'utiliser un test de rang puisque celui-ci est indépendant, outre d'un facteur d'échelle, mais aussi de toute transformation monotone pour la relation d'ordre et la métrique utilisées.

    L'honneur est sauf.

  8. #8
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    J'ai pas vraiment envie de rentrer dans un débat philosophique sur la corrélation... Tout ce que je sais, c'est qu'une corrélation compare des éléments qu'il faut normaliser... S'il y a un facteur 1000 entre 2 signaux, ça se ressent inévitablement dans la corrélation... Il faut comparer en faisant une normalisation...

    De plus, et surtout, l'oeil identifie les ressemblances entre deux images car il s'affranchit des variables gênantes telles que la luminosité etc...
    Il est par exemple possible (je parle d'expérience !!!) que deux photos de la même scène mais prises à 2 moments distincts de la journée (à midi = forte lum et le soir = faible lum) soient mal corrélés avec une corrélation toute conne !!!

    Alors que si on s'affranchit des moyennes et variances , cad qu'on normalise, ça va tout de suite mieux... Sinon je vois pas trop pourquoi la méthode ZNCC autait été inventée ainsi que bien d'autres...
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  9. #9
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    S'il y a un facteur 100 entre les 2 signaux, ça ne change strictement rien. Si X(t)=k.Y(t), alors corr(X, Y) = |k|/k, donc le facteur d'échelle ne joue pas, il est pris en compte dans la formule.
    La variance est automatiquement prise en compte dans la corrélation linéaire, c'est le fameux k de mon expression précédente. En ce qui concerne la moyenne, il est logique qu'elle joue un rôle, puisque la corrélation dont on parle est une corrélation linéaire et non affine, d'où ma proposition de la corrélation non linéaire basée sur le rang qui s'affranchit de l'heure de la journée de manière totale et non pas juste de la moyenne.
    Ces méthodes ont été développées dans le cas où la corrélation recherchée est linéaire. Sincèrement, je l'ai très peu utilisée parce qu'elle est assez inutile maintenant qu'on cherche des dépendances - et non plus de simples corrélations - non linéaires, les modélisations qui nous sont aujourd'hui proposées peuvent plus facilement s'affranchir de la nécessité de linéarité - tout n'est plus gaussien par exemple -.

  10. #10
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Ok j'avais pas capté cette histoire de non linéarité...

    A+
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  11. #11
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Allez, bon, de toute façon, on aura 3 ans pour discuter de ce genre de détails

  12. #12
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Lol
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  13. #13
    Rédacteur
    Avatar de WOLO Laurent
    Homme Profil pro
    Architecte de base de données
    Inscrit en
    Mars 2003
    Messages
    2 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : Congo-Brazzaville

    Informations professionnelles :
    Activité : Architecte de base de données
    Secteur : Finance

    Informations forums :
    Inscription : Mars 2003
    Messages : 2 741
    Points : 4 414
    Points
    4 414
    Par défaut
    Ou est ce qu'on peut trouver des informations sur la méthode ZNCC ?

    Découvrez la FAQ de MS SQL Server.
    La chance accorde ses faveurs aux esprits avertis !

  14. #14
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Salut,
    Tout d'abord, j'ai corrigé ce que voulait dire le N de zncc (qui signifie donc Normalized)...

    En fait je n'ai pas trouvé de lien détaillant énormément la méthode... De toute façon ça devient aujourd'hui difficile de remonter à la source étant donné que c'est une très vieille méthode...
    J'ai quand même un lien pour la formule, qui de toute façon devrait t'être suffisante : http://www.laas.fr/~vlemonde/picas$o/picas$o.pdf (p.22)...

    A+
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  15. #15
    Rédacteur
    Avatar de WOLO Laurent
    Homme Profil pro
    Architecte de base de données
    Inscrit en
    Mars 2003
    Messages
    2 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : Congo-Brazzaville

    Informations professionnelles :
    Activité : Architecte de base de données
    Secteur : Finance

    Informations forums :
    Inscription : Mars 2003
    Messages : 2 741
    Points : 4 414
    Points
    4 414
    Par défaut
    Mathieu, je suis entrain de dévélopper une application de gestion de la population Congolaise et j'aimerais la doter de la fonctionalité de la recherche par similarité visuelle.
    N'hésiter pas de me faire parvenir des infos si vous en trouver.

    Découvrez la FAQ de MS SQL Server.
    La chance accorde ses faveurs aux esprits avertis !

  16. #16
    Membre confirmé
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Points : 451
    Points
    451
    Par défaut
    Pour une comparaison dans une grande base de données la méthode zncc seule n'est pas efficace car très lente...

    Je ne sais plus bien la méthode exacte, mais il me semble qu'il faudrait chercher du côté de l'analyse en composantes principales (ACP) qui permet de décomposer les différentes caractéristiques de l'image seulement selon des axes d'étude privilégiés : voir http://www.ulg.ac.be/pedaexpe/cours/glosaire/acp.htm par exemple...

    Je sais que ce genre de choses a fait l'objet de plein de travaux de recherche... Mais je ne sais plus où chercher ...
    Peut-être par exemple qu'au lieu de comparer les images, ils font un truc du genre :
    - chercher des points caractéristiques de l'image (comme par exemple les points invariants par changement d'échelle et par translation / rotation : voir la méthode SIFT : Scale Invariant Feature Transform)
    - les comparer avec les points caractéristiques de la base de données (chaque habitant étant caractérisé par ces points)...

    Ou encore on peut prendre toutes les images de tout le monde, les juxtaposer pour faire une seule et grande image, en faire la transformée de Fourier (la calcul peut être long mais il est fait une fois pour toutes la première fois seulement), et ensuite faire la corrélation dans le domaine de Fourier avec l'image de la personne...
    En fourier ça va + vite car on a que des multiplications termes à termes...

    Mais bon je ne suis vraiment pas sûr de ce que j'avance... Il y a sans aucun doute des méthodes bien + robustes et rapides...

    A+
    "Cultiver les sciences et ne pas aimer les hommes, c'est allumer un flambeau et fermer les yeux." Proverbe chinois

  17. #17
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Ca me fait penser à un article que j'ai lu récemment sur les SOM (self-organizing maps = cartes auto-organisatrices de K... me souviens plus du nom) où le programmeur utilisait cette technique pour établir les similarités dans un gros ensemble de photos, ça avait l'air de donner d'assez bon résultats !

    Tu peux chercher sur ce forum, y a un thread qui devrait te permettre de remonter jusqu'à l'article en question.

    --
    Jedaï

  18. #18
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Pour l'ACP, il te faut décomposer toutes tes images dans l'espace propre - utilisation classique de l'ACP -, puis tu décomposes ta nouvelle image dans cette espace.
    Autre solution pour la décomposition, à la place de faire une décomposition classique - à savoir fire le produit scalaire entre un vecteur propre et l'image -, tu peux utiliser un algorithme du type Mean Shift.
    Autre solution, regarder du côté de l'analyse en composantes principales probabilistic - pblication du Chris Bishop -, ça te permettra d'avoir un test pour savoir si l'image est vraissemblablement proche des images tests.

  19. #19
    Rédacteur
    Avatar de WOLO Laurent
    Homme Profil pro
    Architecte de base de données
    Inscrit en
    Mars 2003
    Messages
    2 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : Congo-Brazzaville

    Informations professionnelles :
    Activité : Architecte de base de données
    Secteur : Finance

    Informations forums :
    Inscription : Mars 2003
    Messages : 2 741
    Points : 4 414
    Points
    4 414
    Par défaut
    En tout cas des liens pourront faire l'affaire.
    Merci beaucoups

    Découvrez la FAQ de MS SQL Server.
    La chance accorde ses faveurs aux esprits avertis !

Discussions similaires

  1. Comparaison des images
    Par ktata_ismail dans le forum Traitement d'images
    Réponses: 3
    Dernier message: 04/12/2007, 19h27
  2. Réponses: 1
    Dernier message: 05/05/2007, 00h35
  3. comparaison deux images
    Par nicolovitch dans le forum Windows
    Réponses: 3
    Dernier message: 27/04/2007, 18h25
  4. Comparaison d'images
    Par Atomikx dans le forum Multimédia
    Réponses: 4
    Dernier message: 12/04/2007, 15h42
  5. Comparaison d'images
    Par marion400 dans le forum Images
    Réponses: 6
    Dernier message: 03/01/2007, 19h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo