How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the C++ programming language

Table of Contents

Problem Statement

This is an algorithm used to thin a black and white i.e. one bit per pixel images. For example, with an input image of: It produces the thinned output: Assume black pixels are one and white pixels zero, and that the input image is a rectangular N by M array of ones and zeroes. The algorithm operates on all black pixels P1 that can have eight neighbours. The neighbours are, in order, arranged as:

Obviously the boundary pixels of the image cannot have the full eight neighbours.

All pixels are tested and pixels satisfying all the following conditions (simultaneously) are just noted at this stage. After iterating over the image and collecting all the pixels satisfying all step 1 conditions, all these condition satisfying pixels are set to white.

All pixels are again tested and pixels satisfying all the following conditions are just noted at this stage. After iterating over the image and collecting all the pixels satisfying all step 2 conditions, all these condition satisfying pixels are again set to white.

If any pixels were set in this round of either step 1 or step 2 then all steps are repeated until no image pixels are so changed.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the C++ programming language

This code demonstrates the implementation of the Zhang-Suen thinning algorithm, a popular technique used in image processing for thinning binary images (images where each pixel is either black or white). Thinning algorithms are commonly employed to simplify the representation of objects in an image while preserving their essential shape characteristics.

Image Class:

The Image class represents binary images as a 2D array of pixels, where each pixel can be black (BLACK_PIX) or white (WHITE_PIX). It provides methods for accessing and manipulating pixel values.

ZhangSuen Class:

The ZhangSuen class contains the implementation of the Zhang-Suen thinning algorithm. It operates on an Image object and transforms it through a series of iterations to produce a thinned image.

Algorithm Details:

The Zhang-Suen algorithm iteratively identifies and removes pixels from the input image based on specific criteria to achieve thinning. It works as follows:

  1. Step 1 (Phase 1): It examines each pixel (P1) that is black in the input image and its surrounding 8-neighbor pixels (P2 to P9). If certain conditions are met, P1 is marked for deletion.
  2. Step 2 (Phase 2): It repeats the same process but on the image obtained from Phase 1. Additional conditions are checked to determine which marked pixels should be deleted.

Main Function:

  1. It reads an input binary image from an input string.
  2. Displays the original image.
  3. Applies the ZhangSuen algorithm to the input image and stores the result in res.
  4. Displays the thinned image res.
  5. Repeats the process for a larger input image (img2) and displays the corresponding thinned image (res2).

High-Level Overview:

  1. The algorithm works by selectively removing border pixels that do not contribute to the essential shape of the object while preserving the overall form.
  2. It maintains connectivity and preserves topological properties (such as the number of branches and end points) in the thinned image.
  3. The resulting thinned image is a skeletal representation of the original image, capturing its shape while minimizing the number of pixels required to represent it.

The Zhang-Suen algorithm is commonly used in various image processing applications, such as object recognition, character recognition, and medical image analysis. By thinning images, it enhances their efficiency for storage, transmission, and analysis while retaining crucial shape information.

Source code in the cpp programming language

#include <iostream>
#include <string>
#include <sstream>
#include <valarray>
const std::string input {
"................................"
".#########.......########......."
".###...####.....####..####......"
".###....###.....###....###......"
".###...####.....###............."
".#########......###............."
".###.####.......###....###......"
".###..####..###.####..####.###.."
".###...####.###..########..###.."
"................................"
};
const std::string input2 {
".........................................................."
".#################...................#############........"
".##################...............################........"
".###################............##################........"
".########.....#######..........###################........"
"...######.....#######.........#######.......######........"
"...######.....#######........#######......................"
"...#################.........#######......................"
"...################..........#######......................"
"...#################.........#######......................"
"...######.....#######........#######......................"
"...######.....#######........#######......................"
"...######.....#######.........#######.......######........"
".########.....#######..........###################........"
".########.....#######.######....##################.######."
".########.....#######.######......################.######."
".########.....#######.######.........#############.######."
".........................................................."
};

class ZhangSuen;

class Image {
public:
    friend class ZhangSuen;
    using pixel_t = char;
    static const pixel_t BLACK_PIX;
    static const pixel_t WHITE_PIX;

    Image(unsigned width = 1, unsigned height = 1) 
    : width_{width}, height_{height}, data_( '\0', width_ * height_)
    {}
    Image(const Image& i) : width_{ i.width_}, height_{i.height_}, data_{i.data_}
    {}
    Image(Image&& i) : width_{ i.width_}, height_{i.height_}, data_{std::move(i.data_)}
    {}
    ~Image() = default;
    Image& operator=(const Image& i) {
        if (this != &i) {
            width_ = i.width_;
            height_ = i.height_;
            data_ = i.data_;
        }
        return *this;
    }
    Image& operator=(Image&& i) {
        if (this != &i) {
            width_ = i.width_;
            height_ = i.height_;
            data_ = std::move(i.data_);
        }
        return *this;
    }
    size_t idx(unsigned x, unsigned y) const noexcept { return y * width_ + x; }
    bool operator()(unsigned x, unsigned y) {
        return data_[idx(x, y)];
    }
    friend std::ostream& operator<<(std::ostream& o, const Image& i) {
        o << i.width_ << " x " << i.height_ << std::endl;
        size_t px = 0;
        for(const auto& e : i.data_) {
            o << (e?Image::BLACK_PIX:Image::WHITE_PIX);
            if (++px % i.width_ == 0)
                o << std::endl;
        }
        return o << std::endl;
    }
    friend std::istream& operator>>(std::istream& in, Image& img) {
        auto it = std::begin(img.data_);
        const auto end = std::end(img.data_);
        Image::pixel_t tmp;
        while(in && it != end) {
            in >> tmp;
            if (tmp != Image::BLACK_PIX && tmp != Image::WHITE_PIX)
                throw "Bad character found in image";
            *it = (tmp == Image::BLACK_PIX)?1:0;
            ++it;
        }
        return in;
    }
    unsigned width() const noexcept { return width_; }
    unsigned height() const noexcept { return height_; }
    struct Neighbours {
        // 9 2 3
        // 8 1 4
        // 7 6 5
        Neighbours(const Image& img, unsigned p1_x, unsigned p1_y)
        : img_{img}
        , p1_{img.idx(p1_x, p1_y)}
        , p2_{p1_ - img.width()}
        , p3_{p2_ + 1}
        , p4_{p1_ + 1}
        , p5_{p4_ + img.width()}
        , p6_{p5_ - 1}
        , p7_{p6_ - 1}
        , p8_{p1_ - 1}
        , p9_{p2_ - 1} 
        {}
        const Image& img_;
        const Image::pixel_t& p1() const noexcept { return img_.data_[p1_]; }
        const Image::pixel_t& p2() const noexcept { return img_.data_[p2_]; }
        const Image::pixel_t& p3() const noexcept { return img_.data_[p3_]; }
        const Image::pixel_t& p4() const noexcept { return img_.data_[p4_]; }
        const Image::pixel_t& p5() const noexcept { return img_.data_[p5_]; }
        const Image::pixel_t& p6() const noexcept { return img_.data_[p6_]; }
        const Image::pixel_t& p7() const noexcept { return img_.data_[p7_]; }
        const Image::pixel_t& p8() const noexcept { return img_.data_[p8_]; }
        const Image::pixel_t& p9() const noexcept { return img_.data_[p9_]; }
        const size_t p1_, p2_, p3_, p4_, p5_, p6_, p7_, p8_, p9_;
    };
    Neighbours neighbours(unsigned x, unsigned y) const { return Neighbours(*this, x, y); }
private:
    unsigned height_ { 0 };
    unsigned width_ { 0 };
    std::valarray<pixel_t> data_;
};

constexpr const Image::pixel_t Image::BLACK_PIX = '#';
constexpr const Image::pixel_t Image::WHITE_PIX = '.';

class ZhangSuen {
public:

    // the number of transitions from white to black, (0 -> 1) in the sequence P2,P3,P4,P5,P6,P7,P8,P9,P2
    unsigned transitions_white_black(const Image::Neighbours& a) const {
        unsigned sum = 0;
        sum += (a.p9() == 0) && a.p2();
        sum += (a.p2() == 0) && a.p3();
        sum += (a.p3() == 0) && a.p4();
        sum += (a.p8() == 0) && a.p9();
        sum += (a.p4() == 0) && a.p5();
        sum += (a.p7() == 0) && a.p8();
        sum += (a.p6() == 0) && a.p7();
        sum += (a.p5() == 0) && a.p6();
        return sum;
    }

    // The number of black pixel neighbours of P1. ( = sum(P2 .. P9) )
    unsigned black_pixels(const Image::Neighbours& a) const {
        unsigned sum = 0;
        sum += a.p9();
        sum += a.p2();
        sum += a.p3();
        sum += a.p8();
        sum += a.p4();
        sum += a.p7();
        sum += a.p6();
        sum += a.p5();
        return sum;
    }
    const Image& operator()(const Image& img) {
        tmp_a_ = img;
        size_t changed_pixels = 0;
        do {
            changed_pixels = 0;
            // Step 1
            tmp_b_ = tmp_a_;
            for(size_t y = 1; y < tmp_a_.height() - 1; ++y) {
                for(size_t x = 1; x < tmp_a_.width() - 1; ++x) {
                    if (tmp_a_.data_[tmp_a_.idx(x, y)]) {
                        auto n = tmp_a_.neighbours(x, y);
                        auto bp = black_pixels(n);
                        if (bp >= 2 && bp <= 6) {
                            auto tr = transitions_white_black(n);
                            if (    tr == 1 
                                && (n.p2() * n.p4() * n.p6() == 0)
                                && (n.p4() * n.p6() * n.p8() == 0)
                                ) {
                                tmp_b_.data_[n.p1_] = 0;
                                ++changed_pixels;
                            }
                        }
                    } 
                }
            }
            // Step 2
            tmp_a_ = tmp_b_;
            for(size_t y = 1; y < tmp_b_.height() - 1; ++y) {
                for(size_t x = 1; x < tmp_b_.width() - 1; ++x) {
                    if (tmp_b_.data_[tmp_b_.idx(x, y)]) {
                        auto n = tmp_b_.neighbours(x, y);
                        auto bp = black_pixels(n);
                        if (bp >= 2 && bp <= 6) {
                            auto tr = transitions_white_black(n);
                            if (    tr == 1 
                                && (n.p2() * n.p4() * n.p8() == 0)
                                && (n.p2() * n.p6() * n.p8() == 0)
                                ) {
                                tmp_a_.data_[n.p1_] = 0;
                                ++changed_pixels;
                            }
                        }
                    } 
                }
            }
        } while(changed_pixels > 0);
        return tmp_a_;
    }
private:
    Image tmp_a_;
    Image tmp_b_;
};

int main(int argc, char const *argv[])
{
    using namespace std;
    Image img(32, 10);
    istringstream iss{input};
    iss >> img;
    cout << img;
    cout << "ZhangSuen" << endl;
    ZhangSuen zs;
    Image res = std::move(zs(img));
    cout << res << endl;

    Image img2(58,18);
    istringstream iss2{input2};
    iss2 >> img2;
    cout << img2;
    cout << "ZhangSuen with big image" << endl;
    Image res2 = std::move(zs(img2));
    cout << res2 << endl;
    return 0;
}

You may also check:How to resolve the algorithm Balanced brackets step by step in the C# programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/Middle-square method step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Sort numbers lexicographically step by step in the Raku programming language
You may also check:How to resolve the algorithm Ordered partitions step by step in the jq programming language
You may also check:How to resolve the algorithm Animate a pendulum step by step in the Euphoria programming language