Ask Your Question
7

What is a good thinning algorithm for getting the "skeleton" of characters for OCR?

asked 2012-10-16 20:18:38 -0500

ZachTM gravatar image

updated 2015-09-04 11:51:07 -0500

Hi guys I have a few thousand training examples for my neural network that looks like:

image description

The thickness does vary in my training set. The accuracy of the neural network on the test set isnt bad, as its around 97% but I have problems when the characters are super small, with a high thickness. I want to normalize the characters to have a standard thickness if possible using a thinning algorithm. I have found many papers that talk about them, but never explain in detail how they work. I was wondering if anyone knew a nice way to do this in OpenCV? I would be very greatful! Thanks.

edit retag flag offensive close merge delete

4 answers

Sort by ยป oldest newest most voted
11

answered 2012-10-18 12:56:27 -0500

ZachTM gravatar image

updated 2012-10-18 12:58:23 -0500

I did some more research and discovered this article

I found that somone implemented this algorithim in opencv here

I then converted the code to the C++ opencv using Mats.

    void ThinSubiteration1(Mat & pSrc, Mat & pDst) {
        int rows = pSrc.rows;
        int cols = pSrc.cols;
        pSrc.copyTo(pDst);
        for(int i = 0; i < rows; i++) {
                for(int j = 0; j < cols; j++) {
                        if(pSrc.at<float>(i, j) == 1.0f) {
                                /// get 8 neighbors
                                /// calculate C(p)
                                int neighbor0 = (int) pSrc.at<float>( i-1, j-1);
                                int neighbor1 = (int) pSrc.at<float>( i-1, j);
                                int neighbor2 = (int) pSrc.at<float>( i-1, j+1);
                                int neighbor3 = (int) pSrc.at<float>( i, j+1);
                                int neighbor4 = (int) pSrc.at<float>( i+1, j+1);
                                int neighbor5 = (int) pSrc.at<float>( i+1, j);
                                int neighbor6 = (int) pSrc.at<float>( i+1, j-1);
                                int neighbor7 = (int) pSrc.at<float>( i, j-1);
                                int C = int(~neighbor1 & ( neighbor2 | neighbor3)) +
                                                 int(~neighbor3 & ( neighbor4 | neighbor5)) +
                                                 int(~neighbor5 & ( neighbor6 | neighbor7)) +
                                                 int(~neighbor7 & ( neighbor0 | neighbor1));
                                if(C == 1) {
                                        /// calculate N
                                        int N1 = int(neighbor0 | neighbor1) +
                                                         int(neighbor2 | neighbor3) +
                                                         int(neighbor4 | neighbor5) +
                                                         int(neighbor6 | neighbor7);
                                        int N2 = int(neighbor1 | neighbor2) +
                                                         int(neighbor3 | neighbor4) +
                                                         int(neighbor5 | neighbor6) +
                                                         int(neighbor7 | neighbor0);
                                        int N = min(N1,N2);
                                        if ((N == 2) || (N == 3)) {
                                                /// calculate criteria 3
                                                int c3 = ( neighbor1 | neighbor2 | ~neighbor4) & neighbor3;
                                                if(c3 == 0) {
                                                        pDst.at<float>( i, j) = 0.0f;
                                                }
                                        }
                                }
                        }
                }
        }
}


void ThinSubiteration2(Mat & pSrc, Mat & pDst) {
        int rows = pSrc.rows;
        int cols = pSrc.cols;
        pSrc.copyTo( pDst);
        for(int i = 0; i < rows; i++) {
                for(int j = 0; j < cols; j++) {
                        if (pSrc.at<float>( i, j) == 1.0f) {
                                /// get 8 neighbors
                                /// calculate C(p)
                            int neighbor0 = (int) pSrc.at<float>( i-1, j-1);
                            int neighbor1 = (int) pSrc.at<float>( i-1, j);
                            int neighbor2 = (int) pSrc.at<float>( i-1, j+1);
                            int neighbor3 = (int) pSrc.at<float>( i, j+1);
                            int neighbor4 = (int) pSrc.at<float>( i+1, j+1);
                            int neighbor5 = (int) pSrc.at<float>( i+1, j);
                            int neighbor6 = (int) pSrc.at<float>( i+1, j-1);
                            int neighbor7 = (int) pSrc.at<float>( i, j-1);
                                int C = int(~neighbor1 & ( neighbor2 | neighbor3)) +
                                        int(~neighbor3 & ( neighbor4 | neighbor5)) +
                                        int(~neighbor5 & ( neighbor6 | neighbor7)) +
                                        int(~neighbor7 & ( neighbor0 | neighbor1));
                                if(C == 1) {
                                        /// calculate N
                                        int N1 = int(neighbor0 | neighbor1) +
                                                int(neighbor2 | neighbor3) +
                                                int(neighbor4 | neighbor5) +
                                                int(neighbor6 | neighbor7);
                                        int N2 = int(neighbor1 | neighbor2) +
                                                int(neighbor3 | neighbor4) +
                                                int(neighbor5 | neighbor6) +
                                                int(neighbor7 | neighbor0);
                                        int N = min(N1,N2);
                                        if((N == 2) || (N == 3)) {
                                                int E = (neighbor5 | neighbor6 | ~neighbor0) & neighbor7;
                                                if(E == 0) {
                                                        pDst.at<float>(i, j) = 0.0f;
                                                }
                                        }
                                }
                        }
                }
        }
}


void HandOCR::normalizeLetter(Mat & inputarray, Mat & outputarray) {
        bool bDone = false;
        int rows = inputarray.rows;
        int cols = inputarray.cols;

        inputarray.convertTo(inputarray,CV_32FC1);

        inputarray.copyTo(outputarray);

        outputarray.convertTo(outputarray,CV_32FC1);

        /// pad source
        Mat p_enlarged_src = Mat(rows + 2, cols + 2, CV_32FC1);
        for(int i = 0; i < (rows+2); i++) {
            p_enlarged_src.at<float>(i, 0) = 0.0f;
            p_enlarged_src.at<float>( i, cols+1) = 0.0f;
        }
        for(int j = 0; j < (cols+2); j++) {
                p_enlarged_src.at<float>(0, j) = 0.0f;
                p_enlarged_src.at<float>(rows+1, j ...
(more)
edit flag offensive delete link more

Comments

This is great for fingerprint! Thanks much!

Milanista gravatar imageMilanista ( 2013-04-30 03:21:57 -0500 )edit
7

answered 2013-01-13 23:11:44 -0500

bsdnoobz gravatar image

I've implemented the Zhang-Suen and Guo-Hall thinning algorithms in my blog. Using your image, the result for Zhang-Suen algorithm is on the left and for Guo-Hall algorithm is on the right.

image description image description

edit flag offensive delete link more

Comments

1

Which method is more efficient?

Mostafa Sataki gravatar imageMostafa Sataki ( 2013-01-14 00:23:46 -0500 )edit

Hello @bsdnoobz. Im using your Zhang-Suen algorith for thinning fingerprints, But I have a problem: I'm looking for minutae int the skeleton with crossing-number method - I check the pixel values in 3x3 blocks. My problem is that with this in some places the width of line is 2 pixels. Whats the problem?

Milanista gravatar imageMilanista ( 2013-04-30 03:02:33 -0500 )edit

Hey @bsdnoobz, your blog's domain name expired and the links are inaccessible anymore. Could you please provide alternative links.

M Mahdi Chamseddine gravatar imageM Mahdi Chamseddine ( 2017-02-01 00:24:13 -0500 )edit
1

answered 2013-04-15 22:01:59 -0500

aiming_high gravatar image

if your data is noisy you can try Chatbri and Kameyama's framework for thinning noisy images. They provide a java implementation: http://adapt.cs.tsukuba.ac.jp/~chatbri/web/publications.html

edit flag offensive delete link more
1

answered 2013-02-25 18:50:49 -0500

RLD gravatar image

Which method is more efficient? Ans: Nash's implementation of Zhang-Suen algorithm produces good result. Though there isn't expected result upon thinning/skeletonising thick A, V, K, k, M, N, X, Y, y, Z, z, 2, 5 etc. There is little problem. Required close look.

edit flag offensive delete link more

Comments

this algorithm is excellent, thank you

Heshan Sandeepa gravatar imageHeshan Sandeepa ( 2013-07-13 00:53:11 -0500 )edit
Login/Signup to Answer

Question Tools

9 followers

Stats

Asked: 2012-10-16 20:18:38 -0500

Seen: 35,936 times

Last updated: Apr 15 '13