K-Means image segmentation algorithm

Question

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
            clusters[closestClusterIndex]->addPixel(image->getPixel(i));
        }

        // Calculate the average change of the centroids
        averageCentroidChange = 0;
        for (int i(0); i < clusters.size(); i++)
        {
            averageCentroidChange += clusters[i]->adjustCentroid();
        }
        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 adjustCentroid();
        double getDistanceTo(Pixel *pixel) const;
        double getDistanceTo(int red, int green, int blue) const;
        void addPixel(Pixel *pixel);
        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;
}

double Cluster::adjustCentroid()
{
    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));
}

void Cluster::addPixel(Pixel *pixel)
{
    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());
    }
}

Answer 1

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).

Answer 2

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

This part is really bad:

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.