00001
00002
00003
00004
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
00015
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
00028
00029
00030 void KMeanClass::computeMean(){
00031
00032
if(0 ==
pixel.size()){
00033
return;
00034 }
00035
00036
int sz =
pixel.size();
00037
00038
00039
if(COLOR_GRAY ==
color.
getType()){
00040
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
00047 v /= sz;
00048
00049
color =
Color(v);
00050
00051 }
else if(COLOR_COLOR ==
color.
getType()){
00052
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
00062 v[0] /= sz;
00063 v[1] /= sz;
00064 v[2] /= sz;
00065
00066
color =
Color(v[0], v[1], v[2],
false);
00067 }
00068
00069
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
00085
pixel.clear();
00086 }
00087
00088
00089
00090
00091
00092
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
00111
00112 KMean::KMean(
PNG _image,
int _k):
00113 image(_image),
00114 k(_k){
00115
init();
00116 }
00117
00118
00119
00120 void KMean::init(){
00121
Trace trace(
"init", channelKMean);
00122
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
00134
Histogram* hist =
image.
getHistogram();
00135 hist->
makeCumul();
00136
00137
k = (
k > hist->
getSize() ? hist->
getSize() :
k);
00138
00139 hist->
makeClass(
k);
00140
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
00150
00151
00152 void KMean::doKMean(){
00153
Trace trace(
"doKMean", channelKMean);
00154
00155
const int MAX_ITER = 20;
00156
00157
int cIter = 0;
00158
00159
bool cont =
false;
00160
00161 vector<int> oldIndex;
00162
for(
int i = 0; i <
pixel.size(); i++){
00163 oldIndex.push_back(-1);
00164 }
00165
00166
int cChange;
00167
00168
do{
00169 cChange = 0;
00170 cIter++;
00171
00172
for(
int i = 0; i <
pixel.size(); i++){
00173
Pixel p =
pixel[i];
00174
00175
int ndx = 0;
00176
00177
float dMin = p.
getColor().
distance(
center[0].getColor());
00178
00179
for(
int j = 1; j <
k; j++){
00180
float d = p.
getColor().
distance(
center[j].getColor());
00181
if(d < dMin){
00182
00183 dMin = d;
00184 ndx = j;
00185 }
00186 }
00187
00188
if(oldIndex[i] != ndx){
00189 cChange++;
00190 }
00191
00192 oldIndex[i] = ndx;
00193
center[ndx].addPixel(p);
00194 }
00195
00196 cont = (cChange != 0 && cIter < MAX_ITER);
00197 {
00198 ostringstream o;
00199 o <<
"Change " << cChange <<
" iteration " << cIter;
00200 trace.
print(o.str());
00201 }
00202
00203
00204
if(cont){
00205
for(
int i = 0; i <
k; i++){
00206
center[i].computeMean();
00207 }
00208 }
00209 }
while(cont);
00210
00211
00212
00213
00214
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
00238
center[i].getContent(map);
00239
00240
00241
00242 }
00243
Node ret = map.
makeComponent();
00244
return ret;
00245 }
00246