Suggestion - Improvement for the existing 'thinning' algorithm

eladoni1 · October 17, 2024, 4:11pm

Hi, So I will be brief and I hope someone will just read and give me a review if it’s a good improvement, or whether I am wrong here -
Btw, I am looking at the current usage, in ‘opencv_contrib/modules/ximgproc/src/thinning.cpp at 4.x · opencv/opencv_contrib · GitHub’ -

So -
‘absdiff’ and ‘hasNonZero’ seem rather expensive - which just looks at the values and checks if they are all the same or not. seems it does 2 passes on the entire matrix. (forEach, or something that is like ‘hasNonZero’ but for absdiff (‘hasAbsDiff’) could, potentially, improve this to a single pass).

Moreover, we could utilize an ROI reduction in each iteration - the relevant area for thinning is getting smaller and smaller the more iterations the program is into. In the same forEach we could update the relevant top-most, left-most, right-most, and down-most, to gain the exact relevant ROI for the next iteration. that way we decrease the amount of overhead for the other pixels and call instances.

That is all. thanks for reading

crackwitz · October 17, 2024, 6:10pm

you should run a profiler on the code first. then you’ll know if that part of the code is worth spending time on.

they merely check the Mats for equality. the absdiff does more than is required. cv::compare could do the comparison.

a companion function combining cv::compare and a reduction (any/all) would be useful to have.

sturkmen · October 18, 2024, 5:47pm

Your suggestions are correct. I have tried to realize some of them before.

see my PR Optimization ximgproc::thinning by sturkmen72 · Pull Request #3801 · opencv/opencv_contrib (github.com)

You can use the following code to compare the performance of old and new code.

note: I was aware that using ROIs could make it even faster (see arnaud-ramey/voronoi: VoronoiSkeleton is a C++ class made for the fast computing of Voronoi diagrams of monochrome images. It contains different implementations of thinning algorithms. (github.com)). but I didn’t think about it because I think sometimes the slow result with less code is better.

but still open to development for new contributors

also see The THinning evaluation BEnchmark


#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>

#include <iostream>

using namespace std;
using namespace cv;

enum ThinningTypes{
    THINNING_ZHANGSUEN    = 0, // Thinning technique of Zhang-Suen
    THINNING_GUOHALL      = 1  // Thinning technique of Guo-Hall
};

namespace cv {
namespace current {

// look up table - there is one entry for each of the 2^8=256 possible
// combinations of 8 binary neighbors.
static uint8_t lut_zhang_iter0[] = {
    1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
    1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1};

static uint8_t lut_zhang_iter1[] = {
    1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
    0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1,
    0, 1, 1, 1};

static uint8_t lut_guo_iter0[] = {
    1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1,
    0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1};

static uint8_t lut_guo_iter1[] = {
    1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0,
    1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
    1, 1, 1, 1};

// Applies a thinning iteration to a binary image
static void thinningIteration(Mat img, int iter, int thinningType){
    Mat marker = Mat::zeros(img.size(), CV_8UC1);
    int rows = img.rows;
    int cols = img.cols;
    marker.col(0).setTo(1);
    marker.col(cols - 1).setTo(1);
    marker.row(0).setTo(1);
    marker.row(rows - 1).setTo(1);

    if(thinningType == THINNING_ZHANGSUEN){
        marker.forEach<uchar>([=](uchar& value, const int postion[]) {
            int i = postion[0];
            int j = postion[1];
            if (i == 0 || j == 0 || i == rows - 1 || j == cols - 1)
                return;

            auto ptr = img.ptr(i, j); // p1

            // p9 p2 p3
            // p8 p1 p4
            // p7 p6 p5
            uchar p2 = ptr[-cols];
            uchar p3 = ptr[-cols + 1];
            uchar p4 = ptr[1];
            uchar p5 = ptr[cols + 1];
            uchar p6 = ptr[cols];
            uchar p7 = ptr[cols - 1];
            uchar p8 = ptr[-1];
            uchar p9 = ptr[-cols - 1];

            int neighbors = p9 | (p2 << 1) | (p3 << 2) | (p4 << 3) | (p5 << 4) | (p6 << 5) | (p7 << 6) | (p8 << 7);

            if (iter == 0)
                value = lut_zhang_iter0[neighbors];
            else
                value = lut_zhang_iter1[neighbors];

            //int A  = (p2 == 0 && p3 == 1) + (p3 == 0 && p4 == 1) +
            //         (p4 == 0 && p5 == 1) + (p5 == 0 && p6 == 1) +
            //         (p6 == 0 && p7 == 1) + (p7 == 0 && p8 == 1) +
            //         (p8 == 0 && p9 == 1) + (p9 == 0 && p2 == 1);
            //int B  = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9;
            //int m1 = iter == 0 ? (p2 * p4 * p6) : (p2 * p4 * p8);
            //int m2 = iter == 0 ? (p4 * p6 * p8) : (p2 * p6 * p8);
            //if (A == 1 && (B >= 2 && B <= 6) && m1 == 0 && m2 == 0) value = 0;
            // else value = 1;
        });
    }
    if(thinningType == THINNING_GUOHALL){
        marker.forEach<uchar>([=](uchar& value, const int postion[]) {
            int i = postion[0];
            int j = postion[1];
            if (i == 0 || j == 0 || i == rows - 1 || j == cols - 1)
                return;

            auto ptr = img.ptr(i, j); // p1

            // p9 p2 p3
            // p8 p1 p4
            // p7 p6 p5
            uchar p2 = ptr[-cols];
            uchar p3 = ptr[-cols + 1];
            uchar p4 = ptr[1];
            uchar p5 = ptr[cols + 1];
            uchar p6 = ptr[cols];
            uchar p7 = ptr[cols - 1];
            uchar p8 = ptr[-1];
            uchar p9 = ptr[-cols - 1];

            int neighbors = p9 | (p2 << 1) | (p3 << 2) | (p4 << 3) | (p5 << 4) | (p6 << 5) | (p7 << 6) | (p8 << 7);

            if (iter == 0)
                value = lut_guo_iter0[neighbors];
            else
                value = lut_guo_iter1[neighbors];

            //int C  = ((!p2) & (p3 | p4)) + ((!p4) & (p5 | p6)) +
            //         ((!p6) & (p7 | p8)) + ((!p8) & (p9 | p2));
            //int N1 = (p9 | p2) + (p3 | p4) + (p5 | p6) + (p7 | p8);
            //int N2 = (p2 | p3) + (p4 | p5) + (p6 | p7) + (p8 | p9);
            //int N  = N1 < N2 ? N1 : N2;
            //int m  = iter == 0 ? ((p6 | p7 | (!p9)) & p8) : ((p2 | p3 | (!p5)) & p4);
            //if ((C == 1) && ((N >= 2) && ((N <= 3)) & (m == 0))) value = 0;
            // else value = 1;
        });
    }

    img &= marker;
}

// Apply the thinning procedure to a given image
void thinning(InputArray input, OutputArray output, int thinningType){
    Mat processed = input.getMat().clone();
    CV_CheckTypeEQ(processed.type(), CV_8UC1, "");
    // Enforce the range of the input image to be in between 0 - 255
    processed /= 255;

    Mat prev = processed.clone();
    Mat diff;

    do {
        thinningIteration(processed, 0, thinningType);
        thinningIteration(processed, 1, thinningType);
        absdiff(processed, prev, diff);
        if (!hasNonZero(diff)) break;
        processed.copyTo(prev);
    }
    while (true);

    processed *= 255;

    output.assign(processed);
}

} //namespace current
} //namespace cv

namespace cv {
namespace improved {

// look up table - there is one entry for each of the 2^8=256 possible
// combinations of 8 binary neighbors.
static uint8_t lut_zhang_iter0[] = {
    1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
    1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1};

static uint8_t lut_zhang_iter1[] = {
    1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
    0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1,
    0, 1, 1, 1};

static uint8_t lut_guo_iter0[] = {
    1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1,
    0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
    0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1,
    0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0,
    1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1};

static uint8_t lut_guo_iter1[] = {
    1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0,
    1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
    1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
    1, 1, 1, 1};

// Applies a thinning iteration to a binary image
static void thinningIteration(Mat &img, Mat &marker, const uint8_t* const lut, bool &changed) {
    int rows = img.rows;
    int cols = img.cols;

    // Parallelized iteration over pixels excluding the boundary
    parallel_for_(Range(1, rows - 1), [&](const Range& range) {
        for (int i = range.start; i < range.end; i++) {
            const uchar* imgRow = img.ptr(i);
            uchar* markerRow = marker.ptr(i);
            for (int j = 1; j < cols - 1; j++) {
                if (imgRow[j]) {
                    uchar p2 = imgRow[j - cols] != 0;
                    uchar p3 = imgRow[j - cols + 1] != 0;
                    uchar p4 = imgRow[j + 1] != 0;
                    uchar p5 = imgRow[j + cols + 1] != 0;
                    uchar p6 = imgRow[j + cols] != 0;
                    uchar p7 = imgRow[j + cols - 1] != 0;
                    uchar p8 = imgRow[j - 1] != 0;
                    uchar p9 = imgRow[j - cols - 1] != 0;

                    int neighbors = p9 | (p2 << 1) | (p3 << 2) | (p4 << 3) | (p5 << 4) | (p6 << 5) | (p7 << 6) | (p8 << 7);
                    uchar lut_value = lut[neighbors];

                    if (lut_value == 0)
                    {
                        markerRow[j] = lut_value;
                        changed = true;
                    }
                }
            }
        }
    });

    img &= marker;
}

// Apply the thinning procedure to a given image
void thinning(InputArray input, OutputArray output, int thinningType){
    Mat input_ = input.getMat();
    CV_Assert(!input_.empty());
    CV_CheckTypeEQ(input_.type(), CV_8UC1, "");

    Mat processed = input_ / 255;
    Mat prev = processed.clone();

    Mat marker;
    Mat marker_inner = processed(Rect(1, 1, processed.cols - 2, processed.rows - 2));
    copyMakeBorder(marker_inner, marker, 1, 1, 1, 1, BORDER_ISOLATED | BORDER_CONSTANT, Scalar(255));

    const auto lutIter0 = (thinningType == THINNING_GUOHALL) ? lut_guo_iter0 : lut_zhang_iter0;
    const auto lutIter1 = (thinningType == THINNING_GUOHALL) ? lut_guo_iter1 : lut_zhang_iter1;

    do {
        bool changed0 = false;
        bool changed1 = false;
        thinningIteration(processed, marker, lutIter0, changed0);
        thinningIteration(processed, marker, lutIter1, changed1);

        if (changed0 | changed1)
            processed.copyTo(prev);
        else
            break;
    } while (true);

    output.assign(processed * 255);
}

} //namespace improved
} //namespace cv

void test1(Mat& src, Mat& dst, int thinningType = THINNING_ZHANGSUEN)
{
    TickMeter tm;
    tm.start();
    current::thinning(src, dst, thinningType);
    tm.stop();
    cout << thinningType << " current (white pixels are mostly)" << endl << tm << endl;

    tm.reset();
    tm.start();
    dst = ~src;
    current::thinning(dst, dst, thinningType);
    tm.stop();
    cout << thinningType << " current (white pixels are in the minority)" << endl << tm << endl << endl;
} 

void test2(Mat& src, Mat& dst, int thinningType = THINNING_ZHANGSUEN)
{
    TickMeter tm;
    tm.start();
    improved::thinning(src, dst, thinningType);
    tm.stop();
    cout << thinningType << " improved (white pixels are mostly)" << endl << tm << endl;

    tm.reset();
    tm.start();
    dst = ~src;
    improved::thinning(dst, dst, thinningType);
    tm.stop();
    cout << " improved (white pixels are in the minority)" << endl << tm << endl << endl;
}

int main(int argc, const char** argv)
{
    string filename = "08.png";
    if (argc > 1)
        filename = argv[1];

    Mat src = imread(filename, IMREAD_GRAYSCALE);
    Mat dst = src.clone();

    for (int i = 0; i < 5; i++)
    {
        test1(src, dst);
        test2(src, dst);
        test1(src, dst, THINNING_GUOHALL);
        test2(src, dst, THINNING_GUOHALL);
    }

}

sturkmen · October 18, 2024, 5:50pm

i used this image to test
opencv_extra/testdata/cv/ximgproc/sources/08.png at 4.x · opencv/opencv_extra (github.com)

Topic		Replies	Views
`cv::ximgproc::thinning` is too slow C++ ximgproc	0	256	March 5, 2024
Keeping indistinct edges when using skeletonization Python	12	1620	January 6, 2021
Object detection - Haar cascades vs. TemplateMatching vs. FastFeatureDetector vs.? Python dnn	11	2359	June 4, 2021
Edges détection of an image	1	253	July 13, 2023
AbsDiff vs BitwiseXor?	2	757	May 9, 2021

Suggestion - Improvement for the existing 'thinning' algorithm

Related topics