TRAITEMENT DE L'IMAGE: FILTRE MÉDIAN EN TEMPS CONSTANT
cs_Forman
Messages postés
600
Date d'inscription
samedi 8 juin 2002
Statut
Membre
Dernière intervention
6 avril 2010
-
14 mars 2009 à 11:56
Pistol_Pete Messages postés 1053 Date d'inscription samedi 2 octobre 2004 Statut Membre Dernière intervention 9 juillet 2013 - 15 avril 2010 à 18:08
Pistol_Pete Messages postés 1053 Date d'inscription samedi 2 octobre 2004 Statut Membre Dernière intervention 9 juillet 2013 - 15 avril 2010 à 18:08
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/49471-traitement-de-l-image-filtre-median-en-temps-constant
https://codes-sources.commentcamarche.net/source/49471-traitement-de-l-image-filtre-median-en-temps-constant
15 avril 2010 à 18:08
Si tu veux juste tester le programme, j'ai fourni l'exe.
Si tu veux le compiler, change de compilateur et télécharge VS2005 ou VS 2008 express. Ils sont gratuits.
Si tu veux garder code block, je ne sais pas!
15 avril 2010 à 17:56
veux utiliser
15 avril 2010 à 17:52
C:\Documents and Settings\Ines\Bureau\median\FastMedian\main.cpp|75|undefined reference to `_SetBkColor@8'|
C:\Documents and Settings\Ines\Bureau\median\FastMedian\main.cpp|76|undefined reference to `_TextOutA@20'|
Je vous explique comment j'ai fait j'ai tout d'abord crée un bouveau projet C++; puis j'ai fait copier coller
votre main dans le main du nouveau projet et puis j'ai ajouté les autres classes
Je veux exécuter un exemple de ctmf.cpp je veux donner une image et le résultat c'est l'image destination après application du constant median filter
Merci d'avance
15 avril 2010 à 17:39
HBITMAP PictureToBitmap(LPBYTE pmem, DWORD nSize)
{
HRESULT hr;
CoInitialize(0);
HBITMAP hbmp_dst = 0;
IStream* stream = 0;
IPicture* picture = 0;
HBITMAP hbmp_src;
BITMAP bmp;
HGLOBAL hgbl =(HGLOBAL)GlobalAlloc(GMEM_FIXED, nSize);
memcpy(hgbl, pmem, nSize);
hr = CreateStreamOnHGlobal(hgbl, FALSE, &stream);
if(!SUCCEEDED(hr) || !stream) goto errPicture;
hr = OleLoadPicture(stream, nSize, 0, IID_IPicture, (void**)&picture);
if(!SUCCEEDED(hr) || !picture) goto errPicture;
picture->get_Handle((OLE_HANDLE *)&hbmp_src);
if(!SUCCEEDED(hr) || !picture) goto errHandle;
GetObject(hbmp_src, sizeof bmp, &bmp);
hbmp_dst = (HBITMAP)CopyImage(hbmp_src, IMAGE_BITMAP, 0, 0, 0);
errHandle:
picture->Release();
errPicture:
stream->Release();
GlobalFree(hgbl);
CoUninitialize();
return hbmp_dst;
}
Cela doit solutionner tes erreurs.
A+
15 avril 2010 à 17:26
C:\Documents and Settings\Ines\Bureau\median\FastMedian\CImage.cpp|197|error: jump to label `errPicture'|
C:\Documents and Settings\Ines\Bureau\median\FastMedian\CImage.cpp|181|error: from here|
C:\Documents and Settings\Ines\Bureau\median\FastMedian\CImage.cpp|183|error: crosses initialization of `IPicture*picture'|
J'utilise code:Blocks 8.02 sous windows
Merci
15 avril 2010 à 17:17
Je ne vois pas comment d'aider si tu n'indiques même pas les erreurs que tu as...
A+
15 avril 2010 à 17:11
J'ai essayé d'exécuter le code que j'ai télécharger a partir de .zip mais j'ai 3 erreurs lors de la compilation
s'il vous plait pouvez vous m'aider c'est urgent
Ines
23 mars 2009 à 05:58
L(af)=aL(f) et L(f+g)=L(f)+L(g).
En général, il s'agit d'une convolution par un noyau "u" (régularisant ou non):
L(f)(x)=f*u(x)="intégrale sur t de f(x-t)u(t)dt"
En remplaçant f par af ou f+g on retrouve immédiatement les deux propriétés plus haut. Le filtre médian (appelons-le "M") vérifie toujours que M(af)=aM(f) mais ne vérifie pas en général que M(f+g)=M(f)+M(g), et pour cette raison n'est pas linéaire.
Les filtres que tu évoques (filtre passe-bas en sinus cardinal pour supprimer les effets de repliement de spectre) sont linéaires, au sens où ils sont définis par une convolution.
En ce qui concerne la continuité d'un opérateur, pour moi il s'agit de sa sensibilité aux variations. Pour faire simple (difficile d'écrire des formules en ASCII!) un opérateur est continu si en appliquant une petite variation au signal d'entrée on obtient une petite variation sur le signal de sortie. On peut vérifier que c'est le cas du filtre médian.
Dans tous les cas la linéarité d'un opérateur n'implique pas sa continuité (en fait ça n'a rien à voir). Par exemple, l'opérateur de dérivation (en x) n'est pas continu, mais il est linéaire. On peut en calculer une version approximative avec un filtre de la forme [-1,1] (il suffit de soustraire la valeur du pixel de gauche à chaque pixel de l'image) même si dans la pratique on utilise des fenêtre un peu plus large pour diminuer la sensibilité au bruit. En généralisant un peu brutalement, on pourrait dire que les filtres passe-bas (ou régularisant) sont continus, et les passes-hauts discontinus.
En ce qui concerne le traitement du signal audio, est-ce que tu parlais d'appliquer le filtre au signal échantillonné (représentation numérique de la position au cours du temps de la membrane d'un haut-parleur, qui est un signal monodimensionnel dépendant uniquement du temps, comme dans le format WAVE) ou à sa transformée de Fourier (qui effectivement peut être vue comme un signal bidimensionnel, en temps et en fréquence)? Dans le second cas, il me semble évident qu'on ne peut pas se permettre de filtrer les valeurs telles quelles! Mais dans le premier cas, je pense que ce type de filtre peut donner de bons résultats pour gommer certaines imperfections du signal, comme les "clics" d'enregistrement. Le format WAVE, par exemple, peut être encodé en 8 bits par échantillon, et il me semble que la méthode pourrait tout à fait s'appliquer dans ce genre de cas.
Enfin en ce qui concerne la complexité algorithmique, comme tu le dis toi-même, on peut mettre une borne supérieure uniforme (qui ne dépend pas des données à traiter, la variable concernée étant ici le rayon du filtre) sur le temps d'exécution. Il me semble que c'est exactement la définition d'un algorithme à "temps constant".
23 mars 2009 à 03:41
Concernant la limite de précision, on peut noter aussi que c'est sur un filtre de rayon supérieur ou égal à 128 (et non 512) qu'il faut aussi augmenter cette précision dans le bin: l'algorithme ne le vérifie pas et les valeurs 16bits d'histogrammes peuvent donc déborder dans certains cas non "pathologiques" comme les plages toutes blanches ou toutes noires qui surviennent sur des zones saturées de l'image (image l'effet sur une photo avec un soleil, ou des zones d'ombre bien contrastées qu'on bien bien noires, notamment sur des scans en très haute résolution comme des radios ou images scanners).
A l'inverse, pour des rayons inférieurs à 8, le nombre de pixels dans le noyau est nécessairement sous 256, et utiliser 16 bits par valeur d'histogramme est un gaspillage; on pourrait à la place utiliser un codage 8-bits avec une meilleure parallélisation (aussi bien en MMX, que 3DNow, SSE, SSE2, Altivec...) Pour le filtrage du bruit de suantification des appareils photos à cellule CCS, les rayons seront nécessairement faibles, et peuvent énormément améliorer la compression JPEG ultérieure tout en réduisant les pertes et artéfacts. Pour l'élimination des artéfacts "carrés" de la compresion JPEG/MPEG ou pour la correction des blocs manquants dans une vidéo MPEG, un filtre médian de rayon 3 ou 4 suffit amplement, et donc là encore les histogrammes sur 8 bits seraient suffisants et encore plus rapides (mais toujours à coût quasi constant).
Pour le filtrage numérique du son en revanche, les échantillons 8 bits ne suffisent pas, même si l'entrée est seulement sur 8 bits, car ceux-ci sont dénormalisés par une transformation non linéaire (de type "loi-A" pour les anciens formats audio américains ou "loi-mu" presque partout ailleurs): souvent il faut avant tout traitement les convertir dans un espace linéaire sur 12 bits minimum (souvent 16 bits). Le filtrage du bruit se fait en plus dans un espace transformé (bidimensionnel celui-là, en temps et en fréquence) demandant une plus grande précision pour les fréquences centrales du spectre, là où aussi le bruit de quantification ou de mesure est le plus important. Hors, avec 16 bits de précision, la largeur des histogrammes devient prohibitive.
C'est pourtant essentiel dans la construction matérielle d'involuteurs en temps réel (par exemple dans les modems de type DSL) qui nécessitent des filtres d'élimination du bruit pas trop destructeurs d'information (car ce type de destruvtion supprime une autre chose essentielle, la phase du signal, pour n'en garder que l'amplitude moyenne dans une fréquence ou couleur donnée).
Bref, cet algo est très bien mais il faut en comprendre les limites, et l'adapter au cas à traiter. Les optimisations MMX/SSE/Altivec ne sont pas si essentielles que ça (et pas forcément péreines non plus) et masquent l'algorithme réel dont le principe est en fait bien plus simple que ne le laisse transparaitre le source.
Aussi il est effectivement ESSENTIEL de se rapporter au document de référence, et merci d'avoir mentionné la source (consulter l'article paru dans les communications IEEE au format PDF pour les détails, il est facile à comprendre même s'il est rédigé en anglais avec des schémas qui rendent le principe finalement très facile à comprendre), même s'il manque une visualisation du principe d'utilisation d'un histogramme au lieu du tri pour décider la valeur médiane:
Ce n'est pas évident de conclure que cette méthode a un temps constant, puisque la méthode utilise en fait une boucle d'intégration progressive de l'histogramme, la "courbe" de l'histograme n'ayant rien de linéaire ni nécessairement distribué de façon uniforme dans les cas réels: le cas moyen n'est valide que pour une image toute grise, le cas le plus favorable est l'image toute noire, le plus défavorable étant l'image toute blanche, et le temps effectif dépendant donc directement de la valeur médiane obtenue dans l'image source elle-même, avec de grosses variations de vitesse en fonction de l'éclairage moyen sur une photo dont la balance des blancs n'est pas nécessairement bien équilibrée sur la photo entière).
Le résultat de cet algorithme n'est donc pas un temps "constant" mais un temps "borné" entre deux bornes dans un rapport fini (jamais plus que le simple au double) qui ne dépend pas du rayon du filtre mais de la précision binaire de l'image source (c'est ce que veut dire "O(1)": ce n'est PAS une constante). Si on regarde les courbes affichées d'ailleurs, on voit que le temps n'est pas une droite parfaite mais connait des petites irrégularités en fonction du rayon sur une image réelle, et cette variation de temps est attendue mais limitée (ce qui permet de garantir par exemple un débit utile sur une vidéo avec une marge de variabilité étroite)
22 mars 2009 à 21:56
En ce qui concerne le filtre médian en lui-même, je ne comprends pas ce que tu veux dire par "discontinu". Faut-il comprendre "non linéaire"? Il est utilisé généralement pour ôter certains types de bruit, tout en respectant les frontières à fort contraste. C'est d'ailleurs son avantage par rapport aux noyaux régularisants (linéaires) que tu évoques: il ne crée pas une zone de flou au bord des objets. On l'utilise parfois (lui ou d'autres filtres non linéaires du même genre) pour localiser avec précision certains types de bord sur des images bruitées.
Ceci dit je suis d'accord avec le fait qu'on utilise rarement une taille de filtre de 512x512... Mais avec une taille de 16x16 (qui est beaucoup plus raisonnable) on a 256 valeurs à trier par pixel, et a priori je pense que la boucle à 256 itérations proposée devrait faire au moins aussi bien sinon mieux que la méthode "classique".
22 mars 2009 à 21:28
L'exemple prend une image 8 bits (ce qui est maintenant assez rare dans l'imagerie actuelle, la plupart des filtres pour la photo, la vidéo ou les scènes 3D demandant des scènes en 32 bits (hormis les rares cas d'images monochromatiques à faible résolution). L'optilisation dans ce cas ne sera valide que si la taille de fenêtre est supérieure à 512 pixels (total des opérations de somme et différences des histogrammes, augmenté en fait des comparaisons et additions). Hors, une fenêtre de largeur 512 pour le filtre est très supérieure à l'utilisation classique de ce type de filtre.
Le graphique de comparaison est trompeur et n'est sans doûte pas à l'échelle (pour moi, en dessous de r=17 environ, la méthode classique est plus rapide, c'est pourtant un cas trs courant de l'usage de ce genre de filtres pour les images usuelles, par exemple pour éliminer ou lisser les artefacts de compression JPEG ou MPEG ou corriger de blocs manquants dans une vidéo, sans que ces blocs ont une taille fixe 16x16 et dans ce cas le rayon r reste inférieure à cette limite) Hors le graphique montre tout le contraire, même pour r=1 où il est évident que la méthode classique (sans les multiples histogrammes à mettre à jour) sera plus rapide; la mesure serait donc fausse par des lectures multiples des pixels dans l'image source avec une API lente. (noter que la parallélisation reste encore possible même avec un filtre classique en O(r), seul le noyau changeant réellement mais pas les possibilités d'en utiliser un grand nombre d'instances en parallèle pour traiter toute l'image).
Cette optimisation ne peut donc résoudre que des cas particuliers très rares, à fort facteur de réduction sur des images très grandes et en faible résolution de couleur.
Ce cas serait celui de l'imagerie médicale de type des clichés radios, mais les filtres à effet de seuil aussi brutal que le filtre à médiane est en général inadapté car cela doit traiter des images réelles provenant de mesures dont la distribution de bruit ne subit pas un effet de seuil (de type loi de Poisson par exemple) mais plutôt de type Gaussien (il faut donc un filtre continu).
L'exemple donné (l'icône de Windows) n'est certainement pas celui le plus significatif: il est bien plus rapide d'utiliser la méthode à tri, d'autant qu'il est évident que la taille de fenêtre dans cet exemple est très réduite: le choix de la méthode de tri est important puique le tri ne part jamais d'une situation aléatoire après chaque pixel, mais ce tri subit un changement unique après chaque pixel: un tri par insertion dichotomique suffit (la suppression étant directe si on utilise une file de priorité parallèle au vecteur de tri), et donc sur une fenêtre de 16 pixels, il suffira de 4 ou 5 comparaisons au maximum pour réaliser l'insertion. On est alors très loin des 512 opérations par pixel...
Pourrais-tu préciser pour quel type d'images ce filtre est utilisé et en quoi le filtre discontinu à médiane s'avère plus adapté au problème à résoudre qu'un bien plus simple filtre continu à moyenne dont le comportement linéaire est réellement O(1) dans tous les cas et totalement indépendant à la fois de la taille de fenêtre comme à la profondeur binaire des plans de couleur, et ne nécessite pratiquement aucune mémoire annexe (pas besoin d'histogrammes)?
Sinon bravo pour la qualité du code et l'effort d'optimisation du kernel parallélisable sur un seul processeur avec ALTIVEC ou MMX ou SSE (mais il y a aussi des possibilité de parallélisation nettement plus rapides par GPU, ou par certains processeurs de signal de cartes audio, capable de paralléliser un nombre bien plus élevé de kernels, et il y a même des librairies communes permettant de le faire indépendamment des processeurs hôtes ou esclaves parallèles utilisés dans les différents matériels possibles).
17 mars 2009 à 08:59
Oui c'est ça: En théorie et sans utiliser d'optimisation voici une petite explication de cet algorithme et pourquoi la complexité ne dépend pas du rayon:
On va maintenir à jour autant d'histogramme qu'il y a de colonne. Aussi, chaque colonne aura son histogramme. Pour chaque pixel, on compte 3 étapes:
-On met à jours l'histogramme le plus à droite en deux opérations: 1 addition et 1 soustraction : O(1)
-On ajoute l'histogramme de la colonne droite et on enlève l'histogramme de la colonne gauche qui n'a plus d'effet dans la fenêtre: 256 additions et 256 soustractions pour des images 8 bits: O(1)
-128 comparaisons et 127 additions en moyenne pour trouver le pixel médian: O(1)
Chaque pixel sera ainsi calculé en un temps constant indépendant de r.
En ce qui concerne l'initialisation, elle se fait en O(r) mais cela juste pour les premières lignes. Pour des grandes images, ce temps est négligeable.
Effectivement, la complexité dépend donc de la profondeur de l'image et pas du rayon.
J'espère avoir été assez clair...
N'hésiter pas à demander s'il y a encore des points obscures.
14 mars 2009 à 11:56
j'ai lu rapidement le code et si j'ai bien compris, le fait que la complexité ne dépende pas de la taille du filtre est dû au fait que les données sont de cardinal fini (ie, dans l'intervalle {0,...,255}) donc qu'on peut utiliser un histogramme pour extraire la valeur médiane, tandis que les données du pixel suivant (à droite) sont obtenues en modifiant légèrement l'histogramme du haut et celui de gauche, c'est bien ça?