# K-Means image segmentation algorithm

I am a new C++ programmer and I have some experience in Python and C but I was almost completely self taught (I learned C++ with OpenClassrooms).

I would like to learn the conventions and how things should be done. But I would also like to know why a method should be used over another.

This is my first real project in C++. Any advice or corrections are very welcome. I am more interested in the techniques in C++ generally than specifically with this algorithm, but if I am doing something in an inefficient way, I invite you to suggest corrections.

GitHub

main.cpp

/* K-Means image segmentation
*
* This program only works with uncompressed images
* PPM with type P3
*/

#include "../include/image.h"
#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{
// Set the seed for better random generation
srand(time(NULL));

// Get the path of the original image
string imageDir;
cout << "Image path: ";
cin >> imageDir;
Image *image(new Image(imageDir));

// Get the path of the image to save
string saveImageAs;
cout << "Save image as: ";
cin >> saveImageAs;

// Create each cluster
int clusterCount;
cout << "How many colours? ";
cin >> clusterCount;
vector<Cluster*> clusters;
for (int i(0); i < clusterCount; i++)
{
clusters.push_back(new Cluster(image));
}

// Get the threshold
double threshold;
cout << "Threshold: ";
cin >> threshold;

// Repeat the algorithm until the average centroid change goes below the threshold
double averageCentroidChange;
do
{
// Clear all pixels for each cluster
for (int i(0); i < clusterCount; i++)
{
clusters[i]->clearPixels();
}

// Go through each pixel in the image
for (int i(0); i < image->getLength(); i++)
{
// Calculate which cluster centroid the pixel is nearest to
int closestClusterIndex(0);
double dist;
for (int j(0); j < clusters.size(); j++)
{
dist = clusters[j]->getDistanceTo(image->getPixel(i));
if (dist < clusters[closestClusterIndex]->getDistanceTo(image->getPixel(i)))
{
closestClusterIndex = j;
}
}

// Add the pixel to the nearest cluster
}

// Calculate the average change of the centroids
averageCentroidChange = 0;
for (int i(0); i < clusters.size(); i++)
{
}
averageCentroidChange /= clusters.size();
cout << "Average centroid change: " << averageCentroidChange << endl;
} while (averageCentroidChange > threshold);

// Change all pixels to the color of the corresponding cluster centroid
for (int i(0); i < clusters.size(); i++)
{
clusters[i]->changeAll();
}

// Save the new image
image->saveImage(saveImageAs);

return 0;
}


image.h

#ifndef IMAGE_H_INCLUDED
#define IMAGE_H_INCLUDED

#include <string>
#include <vector>

class Pixel
{
public:
Pixel(int red, int green, int blue);
Pixel(Pixel *pixel);

int getRed() const;
int getGreen() const;
int getBlue() const;
std::string getRGB() const;
void setRGB(int red, int green, int blue);

private:
int m_red;
int m_green;
int m_blue;
};

class Image
{
public:
Image(int width, int height);
Image(std::string name);
~Image();

void saveImage(std::string savePath) const;
Pixel* getRandPixel() const;
std::vector<Pixel*> getPixels() const;
Pixel* getPixel(int index) const;
int getLength() const;

private:
int m_width;
int m_height;
int m_depth;
std::vector<Pixel*> m_pixels;
};

class Cluster
{
public:
Cluster(Image *image);
~Cluster();

double getDistanceTo(Pixel *pixel) const;
double getDistanceTo(int red, int green, int blue) const;
void clearPixels();
void changeAll();

private:
Image *m_image;
Pixel *m_centroid;
std::vector<Pixel*> m_pixels;
};

#endif


image.cpp

#include "../include/image.h"
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>

using namespace std;

Pixel::Pixel(int red, int green, int blue) : m_red(red), m_green(green), m_blue(blue) {}

Pixel::Pixel(Pixel *pixel) : m_red(pixel->m_red), m_green(pixel->m_green), m_blue(pixel->m_blue) {}

int Pixel::getRed() const
{
return m_red;
}

int Pixel::getGreen() const
{
return m_green;
}

int Pixel::getBlue() const
{
return m_blue;
}

string Pixel::getRGB() const
{
return to_string(m_red) + " " + to_string(m_green) + " " + to_string(m_blue);
}

void Pixel::setRGB(int red, int green, int blue)
{
m_red = red;
m_green = green;
m_blue = blue;
}

Image::Image(int width, int height) : m_width(width), m_height(height)
{
for (int i(0); i < m_width*m_height; i++)
{
m_pixels.push_back(new Pixel(0, 0, 0));
}
}

Image::Image(string imageDir)
{
ifstream image(imageDir);
if (image)
{
string type;
image >> type;
if (type == "P3")
{
int red;
int green;
int blue;
image >> m_width;
image >> m_height;
image >> m_depth;
for (int i(0); i < m_width*m_height; i++)
{
image >> red;
image >> green;
image >> blue;
m_pixels.push_back(new Pixel(red, green, blue));
}
} else {
cout << imageDir << " is in the wrong format (should be P3)" << endl;
}
} else {
cout << imageDir << " could not be opened!" << endl;
}
}

Image::~Image()
{
for (int i(0); i < m_width*m_height; i++)
{
delete m_pixels[i];
}
}

void Image::saveImage(string name) const
{
ofstream image(name);
if (image)
{
image << "P3" << endl;
image << m_width << " " << m_height << endl;
image << m_depth << endl;
for (int y(0); y < m_width; y++)
{
for (int x(0); x < m_height; x++)
{
Pixel *pixel = m_pixels[m_height*y + x];
image << pixel->getRGB() << " ";
}
image << endl;
}
} else {
cout << name << ".ppm could not be opened" << endl;
}
}

Pixel* Image::getRandPixel() const
{
return m_pixels[rand() % m_width*m_height];
}

vector<Pixel*> Image::getPixels() const
{
return m_pixels;
}

Pixel* Image::getPixel(int index) const
{
return m_pixels[index];
}

int Image::getLength() const
{
return m_width*m_height;
}

Cluster::Cluster(Image *image) : m_image(image), m_centroid(new Pixel(image->getRandPixel()))
{
}

Cluster::~Cluster()
{
delete m_centroid;
}

{
float red(0);
float green(0);
float blue(0);

for (int i(0); i < m_pixels.size(); i++)
{
red += m_pixels[i]->getRed();
green += m_pixels[i]->getGreen();
blue += m_pixels[i]->getBlue();
}

int denominator(m_pixels.size());
if (m_pixels.size() < 1)
{
denominator = 1;
}

red /= denominator;
green /= denominator;
blue /= denominator;

double change(this->getDistanceTo(red, green, blue));

m_centroid->setRGB(red, green, blue);

return change;
}

double Cluster::getDistanceTo(Pixel *pixel) const
{
int diffRed(pixel->getRed() - m_centroid->getRed());
int diffGreen(pixel->getGreen() - m_centroid->getGreen());
int diffBlue(pixel->getBlue() - m_centroid->getBlue());

return sqrt(pow(diffRed, 2) + pow(diffGreen, 2) + pow(diffBlue, 2));
}

double Cluster::getDistanceTo(int red, int green, int blue) const
{
int diffRed(red - m_centroid->getRed());
int diffGreen(green - m_centroid->getGreen());
int diffBlue(blue - m_centroid->getBlue());

return sqrt(pow(diffRed, 2) + pow(diffGreen, 2) + pow(diffBlue, 2));
}

{
m_pixels.push_back(pixel);
}

void Cluster::clearPixels()
{
m_pixels = {};
}

void Cluster::changeAll()
{
for (int i(0); i < m_pixels.size(); i++)
{
m_pixels[i]->setRGB(m_centroid->getRed(), m_centroid->getGreen(), m_centroid->getBlue());
}
}

• Can you add a little more context about what you're actually trying to accomplish, and how you do that? – Dannnno Apr 2 '18 at 18:16
• Question: Are you intentionally writing this using the pre-C++11 standard because of some constraints? Most problems with this code boils down to "this way of doing things is extremely out of date". – Frank Apr 2 '18 at 18:41
• I am not intentionally using any standard over another, I am just using what I know. And this is what I am trying to accomplish (and it is working) youtu.be/yR7k19YBqiw – Timéo Pochin Apr 2 '18 at 19:19

I'm not familiar with image processing at all, so I cannot give you any advice about your algorithm implementation. However, there are quite a few things I'd like to say about good practices and code style in general:

1. Don't use using namespace std. You are going to run into name resolution issues down the line, and the additional five chars (std::) every few lines are not going to kill you or your productivity.
2. Don't use relative includes (such as #include "../include/image.h"). This is prone to breakage if you ever change your project layout or move files around. The right place to specify what directories to consider for inclusion is your build script (or, in the most basic case, the command line invocation of your compiler of choice).
3. Don't use NULL as the null pointer constant, use nullptr. The latter has an added layer of type safety.
4. Don't use rand and friends. Since C++11, the standard library contains a much more fine-grained and flexible support for random number generation. Take a look at the random header.
5. Why did you write Image *image(new Image(imageDir)) as opposed to Image image(imageDir)? There is no need to use a pointer here. In fact, in modern C++ a raw pointer is indicative that something is not right most of the times. This is true for every single pointer usage throughout your code; none of them are actually necessary or useful.
6. main is far too long and overloaded with code. Split it up into multiple smaller functions with a clearly defined purpose. This will make your code much easier to read and correct.
7. Relating back to point 5, don't write constructors of the form Class(Class* other). You want to copy other here, so you should write a copy constructor. The signature for Pixel, for example, should be Pixel(Pixel const& other). However, sometimes C++ is nice to its users: You actually don't need to worry about copy and move constructors unless your class does something fancy; C++ will implicitly generate them for you.
8. Pass types which are expensive to copy by reference or const reference. In particular, std::string should be passed as std::string const& in most cases.
9. Use for-each loops when looping through a whole container. For example,

for (int i(0); i < m_pixels.size(); i++)
{
red += m_pixels[i]->getRed();
green += m_pixels[i]->getGreen();
blue += m_pixels[i]->getBlue();
}


should be rewritten as

for (auto p : m_pixels)
{
red += p->getRed();
green += p->getGreen();
blue += p->getBlue();
}


or similar to avoid indexing and bounds checking errors (for example, you could run into problems with your version here because int might not be big enough to hold all index values for m_pixels).

10. Don't rely on implicit conversion when assigning values to types. The correct initializer for a single-precision floating point number has the form [0-9]*\.[0-9]*f, for example (meaning that you should write float red(0.0f) instead of float red(0)). Implicit conversion can sometimes really ruin your day because it can lead to unexpected results which are hard to diagnose.
11. Don't use std::endl, use '\n' instead. std::endl will also flush the underlying stream buffer, which you usually don't need to do and which can harm performance if you are doing a lot of I/O (also, if you really need and want to flush, there's std::flush).
• Thank you! This is exactly what I was looking for, I will look into your points in more detail and try to amend the code as much as possible. – Timéo Pochin Apr 2 '18 at 19:55
• Why for(auto p : m_pixels) instead of for(auto& p : m_pixels)? – JNS Apr 3 '18 at 7:37
• @JNS Because Pixel looks like it is small enough to be inexpensive to copy. However, one would probably have to measure here to really find out which is the case (but I am inclined to say that that would be premature optimization). – Ben Steffan Apr 3 '18 at 8:35
• What do you mean by premature optimization? Would using for (auto& p : m_pixels) ever be worse? And I am guessing that if I wanted to change the pixels in the vector inside the loop, I would have to use auto&, is that correct? – Timéo Pochin Apr 3 '18 at 8:59
• I am in favour of premature optimisation when it’s only a 1 character change and doesn’t affect readability. – JNS Apr 3 '18 at 9:35

I want to reinforce a point that Ben Steffan made in his answer:

std::vector<Pixel*> m_pixels;


This would be much, much better:

std::vector<Pixel> m_pixels;


Here are some of the reasons:

1. By allocating each pixel separately, you're doing several million allocations for a normal-sized image. This is really expensive, it could be a single allocation.

2. By allocating each pixel separately, and storing them as naked pointers, you need to write a destructor for your Image class. In the alternative scenario, you can let the compiler generate the default destructor.

3. By allocating each pixel separately, they will (likely) be scattered around the memory, rather than stored contiguously. Contiguous storage makes pixel access much faster. Also, with pointers, for each pixel access you have the additional level of indirection.

4. By storing naked pointers, you are likely to create memory leaks. Use std::unique_ptr or std::shared_ptr instead ("smart pointers"). For example, here you have a memory leak:

void Cluster::clearPixels()
{
m_pixels = {};
}


Or not? That is not clear until you read the whole program carefully and find out that this vector contains references to pixels owned by a different object. Ownership is important to specify. Using smart pointers you make ownership explicit. When using naked pointers, consider documenting in comments who owns what. If you consistently use smart pointers for ownership, you are free (IMO) to use naked pointers for non-owning references, as in the case of the m_pixels in Cluster.

• This is also very helpful, all these things that can be done in different ways are confusing, and it is unclear why you should or shouldn't do something until someone explain why. Thank you! – Timéo Pochin Apr 2 '18 at 22:47
• @TiméoPochin: It's all experience. I'm happy to share with you some of mine. – Cris Luengo Apr 2 '18 at 23:04