K-средних алгоритм сегментации изображений


Я новый C++ программист и у меня есть некоторый опыт в Python и C, но я был почти полностью самоучка (я выучил C++ с OpenClassrooms).

Хотелось бы узнать конвенций и как все должно быть сделано. Но я также хотел бы знать, почему метод должен быть использован над другой.

Это мой первый реальный проект в C++. Любые советы и исправления очень приветствуются. Меня больше интересует методы в C++ вообще, чем конкретно с этим алгоритмом, но если я делаю что-то неэффективным способом, я предлагаю вам предложит исправления.

На 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;
}

изображения.ч

#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());
    }
}


1719
11
задан 2 апреля 2018 в 05:04 Источник Поделиться
Комментарии
2 ответа

Я не знаком с обработкой изображения, поэтому я не могу дать вам совет относительно вашей реализации алгоритма. Однако, есть довольно много вещей, которые я хотел бы сказать о передовой практике и стилю в целом:


  1. Не использовать using namespace std. Вы собираетесь столкнуться с разрешением имен проблем, вниз по линии, и дополнительные пять символов (std::) каждые несколько строк не собирается убить вас или вашу производительность.

  2. Не используйте относительные включает в себя (например, #include "../include/image.h"). Это склонны к поломке, если вы когда-нибудь изменить свой макет проекта или перемещать файлы. Правильное место, чтобы указать, какие каталоги, чтобы рассмотреть для включения скрипта построения (или, в наиболее общем случае, в командной строке вызова компилятора на выбор).

  3. Не использовать NULL как константа нулевого указателя, используйте nullptr. Последний имеет дополнительный уровень безопасности типов.

  4. Не использовать rand и друзей. Начиная с C++11, стандартная библиотека содержит гораздо более тонкая и гибкая поддержка для генерации случайных чисел. Взгляните на случайных заголовков.

  5. Зачем ты пишешь Image *image(new Image(imageDir)) в отличие от Image image(imageDir)? Нет необходимости использовать указатель. На самом деле, в современном C++ исходный указатель свидетельствует, что что-то не правильно в большинстве случаев. Это верно для каждого использования указателя всему коду; никто из них на самом деле являются необходимыми или полезными.

  6. main слишком длинный и перегруженный код. Разбить его на несколько более мелких функций с четко определенной целью. Это сделает ваш код намного легче читать и исправлять.

  7. Возвращает нас к точке 5, не писать конструкторы форме Class(Class* other). Вы хотите скопировать other здесь, поэтому вы должны написать конструктор копирования. Подпись для Pixelнапример, должны быть Pixel(Pixel const& other). Однако, иногда на C++ хорош для своих пользователей: вы действительно не нужно беспокоиться о копировании и перемещении конструкторами, если ваш класс делает что-то необычное; в C++ неявно генерировать их для вас.

  8. Передать типов, которые дорого копию по ссылке или const ссылка. В частности, std::string должны быть передан как std::string const& в большинстве случаев.

  9. Использовать для каждой петли после перехода через весь контейнер. Например,

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

    следует переписать как

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

    или похожие, чтобы избежать индексации и проверки границ ошибки (например, вы можете столкнуться с проблемами с вашей версией здесь, потому что int не может быть достаточно большим, чтобы вместить все значения индекса для m_pixels).


  10. Не полагайтесь на неявное преобразование при указании значений типов. Правильный инициализатор для одинарной точности число с плавающей запятой имеет вид [0-9]*\.[0-9]*fнапример (это означает, что вы должны написать float red(0.0f) вместо float red(0)). Неявные преобразования иногда могут действительно испортить ваш день, потому что это может привести к неожиданным результатам, которые трудно диагностировать.

  11. Не использовать std::endlиспользуйте '\n' вместо. std::endl также промойте базовый поток буфера, который вы обычно не нужно делать и которые могут нанести вред производительности, если вы делаете много операций ввода-вывода (также, если вы действительно нуждаетесь и хотите, чтобы смыть, нет std::flush).

10
ответ дан 2 апреля 2018 в 07:04 Источник Поделиться

Я хочу укрепить точки, что Бен Стефан сделал в своем ответе:

Эта часть очень плохо:

std::vector<Pixel*> m_pixels;

Это было бы гораздо, гораздо лучше:

std::vector<Pixel> m_pixels;

Вот некоторые из причин:


  1. Выделяя каждого пикселя отдельно, вы делаете несколько миллионов ассигнований для нормального размера изображения. Это очень дорого, это может быть одно и то же выделение.

  2. Выделяя каждого пикселя в отдельности, а также их хранение как голые указатели, вам нужно написать деструктор для вашего Image класс. В альтернативном случае, вы можете позволить компилятор генерирует деструктор по умолчанию.

  3. Выделяя каждого пикселя по отдельности, они будут (скорее всего) быть разбросаны по памяти, а не постоянно хранятся. Непрерывные хранения делает пиксель доступ гораздо быстрее. Кроме того, с указателями, для каждого доступа к пикселям у вас есть дополнительный уровень косвенности.

  4. На хранение голые указатели, вы, скорее всего, создавать утечки памяти. Использовать std::unique_ptr или std::shared_ptr вместо ("умные указатели"). Например, здесь у вас есть утечка памяти:


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

    Или нет? Что не понятно, пока вы читали внимательно всю программу и узнаем, что этот вектор содержит ссылки на пиксели, принадлежащие объекту. Право собственности важно указать. С помощью смарт-указатели вы делаете собственности явные. При использовании голых указателей, постарайтесь запечатлеть в комментариях, кто чем владеет. Если вы постоянно используете смарт-указатели для владения, вы свободно (ИМО) для использования голых указателей для не владеющих ссылок, как в случае m_pixels в Cluster.


7
ответ дан 2 апреля 2018 в 09:04 Источник Поделиться