Page principale | Hiérarchie des classes | Liste des classes | Liste des fichiers | Membres de classe | Membres de fichier

KMean.cpp

Aller à la documentation de ce fichier.
00001 /// \file 00002 /// Implémentation des classes pour les KMean 00003 /////////////////////////////////////////////////////////////////////////////// 00004 /// KMeanClass : représente un centroïde 00005 /////////////////////////////////////////////////////////////////////////////// 00006 #include "KMean.hpp" 00007 void KMeanClass::setColor(Color _color){ 00008 color = _color; 00009 } 00010 Color KMeanClass::getColor() const { 00011 return color; 00012 } 00013 /* 00014 int KMeanClass::getSize()const{ 00015 return pixel.size(); 00016 } 00017 */ 00018 void KMeanClass::addPixel(Pixel p){ 00019 pixel.push_back(p); 00020 } 00021 string KMeanClass::toString() const { 00022 ostringstream o; 00023 o << color.toString() << " size " << pixel.size(); 00024 return o.str(); 00025 } 00026 /// . 00027 /// Calcule de la moyenne d'un centre. Pour les images en niveaux de gris 00028 /// on calcule la moyenne des niveaux. Pour les images couleurs on fait la 00029 /// moyenne sur les composantes HSV indépendament. 00030 void KMeanClass::computeMean(){ 00031 // Si le centre est vide on ne fait rien 00032 if(0 == pixel.size()){ 00033 return; 00034 } 00035 // On parcourt tous les points du centre 00036 int sz = pixel.size(); 00037 // color = pixel[0].getColor(); 00038 // Niveau de gris 00039 if(COLOR_GRAY == color.getType()){ 00040 // Somme courante 00041 float v = 0.0; 00042 for(int i = 1; i < sz; i++){ 00043 Color c = pixel[i].getColor(); 00044 v += c.getGray(); 00045 } 00046 // Moyenne 00047 v /= sz; 00048 // Nouveau centre 00049 color = Color(v); 00050 // Couleur 00051 } else if(COLOR_COLOR == color.getType()){ 00052 // Somme courante 00053 float v[3]; 00054 v[0] = v[1] = v[2] = 0.0; 00055 for(int i = 1; i < sz; i++){ 00056 Color c = pixel[i].getColor(); 00057 v[0] += c.getHue(); 00058 v[1] += c.getSaturation(); 00059 v[2] += c.getValue(); 00060 } 00061 // Moyenne 00062 v[0] /= sz; 00063 v[1] /= sz; 00064 v[2] /= sz; 00065 // Nouveau centre (en HSV) 00066 color = Color(v[0], v[1], v[2], false); 00067 } 00068 // Recherche dans la classe de la couleur existante la plus 00069 // proche de la moyenne 00070 if(sz > 0){ 00071 float dst = color.distance(pixel[0].getColor()); 00072 int ndx = 0; 00073 for(int i = 1; i < sz; i++){ 00074 Color c = pixel[i].getColor(); 00075 float d = color.distance(c); 00076 if(d < dst){ 00077 dst = d; 00078 ndx = i; 00079 } 00080 } 00081 color = pixel[ndx].getColor(); 00082 } 00083 00084 // On vide le centre 00085 pixel.clear(); 00086 } 00087 /* 00088 void KMeanClass::setLabel(string _label){ 00089 label = _label; 00090 for(int i = 0; i < pixel.size(); i++){ 00091 pixel[i].setLabel(label); 00092 pixel[i].setColor(color); 00093 } 00094 } 00095 */ 00096 void KMeanClass::output(PNG image) const{ 00097 for(int i = 0; i < pixel.size(); i++){ 00098 Pixel pix = pixel[i]; 00099 image.setColor(pix.getX(), pix.getY(), color); 00100 } 00101 } 00102 void KMeanClass::getContent(PixelMap& map) const{ 00103 for(int i = 0; i < pixel.size(); i++){ 00104 Pixel pix = pixel[i]; 00105 Pixel ta(pix.getX(), pix.getY(), color); 00106 map.addPixel(ta); 00107 } 00108 } 00109 /////////////////////////////////////////////////////////////////////////////// 00110 /// Classe : KMean 00111 /////////////////////////////////////////////////////////////////////////////// 00112 KMean::KMean(PNG _image, int _k): 00113 image(_image), 00114 k(_k){ 00115 init(); 00116 } 00117 /// . 00118 /// Initialisation de la class KMean. Pour avoir une bonne répartition des points 00119 /// dans chaque classe, on se sert de l'histogramme cumulé de l'image. 00120 void KMean::init(){ 00121 Trace trace("init", channelKMean); 00122 // Récupère l'image et son contenu 00123 int w = image.getWidth(); 00124 int h = image.getHeight(); 00125 int size = w * h; 00126 pixel.reserve(size); 00127 for(int i = 0; i < h; i++){ 00128 for(int j = 0; j < w; j++){ 00129 Pixel p(j, i, image.getColor(j, i)); 00130 pixel.push_back(p); 00131 } 00132 } 00133 // Calcul l'histogramme cumulé de l'image 00134 Histogram* hist = image.getHistogram(); 00135 hist->makeCumul(); 00136 // k = max(nombre classe, k) 00137 k = (k > hist->getSize() ? hist->getSize() : k); 00138 // Réparti l'histogramme en k classe 00139 hist->makeClass(k); 00140 // On crée k classes avec la couleurs correspondantes 00141 for(int i = 0; i < k; i++){ 00142 KMeanClass cl; 00143 cl.setColor(hist->getColor(i)); 00144 center.push_back(cl); 00145 } 00146 delete hist; 00147 } 00148 /// . 00149 /// Exécution de l'algorithme des KMean. Tant que des pixels changent 00150 /// de centre et que le nombre d'itération est plus petit que MAX_ITER, 00151 /// on continue l'algorithme 00152 void KMean::doKMean(){ 00153 Trace trace("doKMean", channelKMean); 00154 // Nombre maximal d'iterations 00155 const int MAX_ITER = 20; 00156 // Compteur d'iterations 00157 int cIter = 0; 00158 // Continuation ou pas 00159 bool cont = false; 00160 // Sauvegarde de l'ancien centre d'un pixel 00161 vector<int> oldIndex; 00162 for(int i = 0; i < pixel.size(); i++){ 00163 oldIndex.push_back(-1); 00164 } 00165 // compteur de changement de classes 00166 int cChange; 00167 // Répétition de l'algorithme tant que la condition d'arrêt est fausse 00168 do{ 00169 cChange = 0; 00170 cIter++; 00171 // Parcourt tous les pixels 00172 for(int i = 0; i < pixel.size(); i++){ 00173 Pixel p = pixel[i]; 00174 // Index du nouveau centre; 00175 int ndx = 0; 00176 // Distance minimale 00177 float dMin = p.getColor().distance(center[0].getColor()); 00178 // Parcourt de chaque centre 00179 for(int j = 1; j < k; j++){ 00180 float d = p.getColor().distance(center[j].getColor()); 00181 if(d < dMin){ 00182 // La distance est plus petite 00183 dMin = d; 00184 ndx = j; 00185 } 00186 } 00187 // Est-ce que le pixel courant a changé de centre ? 00188 if(oldIndex[i] != ndx){ 00189 cChange++; 00190 } 00191 // Nouveau centre 00192 oldIndex[i] = ndx; 00193 center[ndx].addPixel(p); 00194 } 00195 // On continue? 00196 cont = (cChange != 0 && cIter < MAX_ITER); 00197 { 00198 ostringstream o; 00199 o << "Change " << cChange << " iteration " << cIter; 00200 trace.print(o.str()); 00201 } 00202 // Si on continue, prépare l'itération suivante 00203 // en calculant la moyenne de chaque centre 00204 if(cont){ 00205 for(int i = 0; i < k; i++){ 00206 center[i].computeMean(); 00207 } 00208 } 00209 }while(cont); 00210 /* 00211 for(int i = 0; i < k; i++){ 00212 ostringstream o; 00213 o << "CLASS " << i; 00214 center[i].setLabel(o.str()); 00215 } 00216 */ 00217 } 00218 00219 string KMean::toString() const { 00220 ostringstream o; 00221 for(int i = 0; i < center.size(); i++){ 00222 o << center[i].toString() << endl; 00223 } 00224 return o.str(); 00225 } 00226 00227 void KMean::output(string filename)const{ 00228 PNG out(image.getWidth(), image.getHeight(), image.getType(), filename); 00229 for(int i = 0; i < center.size(); i++){ 00230 center[i].output(out); 00231 } 00232 out.write(); 00233 } 00234 Node KMean::makeNode() const{ 00235 PixelMap map(image.getWidth(), image.getHeight()); 00236 for(int i = 0; i < center.size(); i++){ 00237 // if(center[i].getSize() != 0){ 00238 center[i].getContent(map); 00239 // }else{ 00240 // cout << "Class " << i << " empty!" << endl; 00241 // } 00242 } 00243 Node ret = map.makeComponent(); 00244 return ret; 00245 } 00246

Généré le Sun Jun 27 15:59:32 2004 pour segment par doxygen 1.3.7