Tags

, , , , , ,

This algorithm is used for thinning binary image. Binary image by definition, consists of only black and white pixels. Here, in the code bellow, Black is denoted as 1 and white is denoted as 0.

A result of thinning using this code is as seen in the image below.

bw bwThin

 

8 neighborhood :
9

Equations :

eqnThin

Step 1 conditions for selecting black points to remove

step1Eqn

Step 2 conditions for selecting black points to remove

step2Eqn

Code For Thinning in Java:

package thinning;

import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author nayef
 */
public class ThinningService {

    public int[][] doZhangSuenThinning(int[][] binaryImage) {
        int a, b;

        List pointsToChange = new LinkedList();
        boolean hasChange;

        do {

            hasChange = false;
            for (int y = 1; y + 1 < binaryImage.length; y++) {
                for (int x = 1; x + 1 < binaryImage[y].length; x++) {
                    a = getA(binaryImage, y, x);
                    b = getB(binaryImage, y, x);
                    if ( binaryImage[y][x]==1 && 2 <= b && b <= 6 && a == 1
                            && (binaryImage[y - 1][x] * binaryImage[y][x + 1] * binaryImage[y + 1][x] == 0)
                            && (binaryImage[y][x + 1] * binaryImage[y + 1][x] * binaryImage[y][x - 1] == 0)) {
                        pointsToChange.add(new Point(x, y));
                        //binaryImage[y][x] = 0;
                        hasChange = true;
                    }
                }
            }

            for (Point point : pointsToChange) {
                binaryImage[point.getY()][point.getX()] = 0;
            }

            pointsToChange.clear();

            for (int y = 1; y + 1 < binaryImage.length; y++) {
                for (int x = 1; x + 1 < binaryImage[y].length; x++) {
                    a = getA(binaryImage, y, x);
                    b = getB(binaryImage, y, x);
                    if ( binaryImage[y][x]==1 && 2 <= b && b <= 6 && a == 1
                            && (binaryImage[y - 1][x] * binaryImage[y][x + 1] * binaryImage[y][x - 1] == 0)
                            && (binaryImage[y - 1][x] * binaryImage[y + 1][x] * binaryImage[y][x - 1] == 0)) {
                        pointsToChange.add(new Point(x, y));

                        hasChange = true;
                    }
                }
            }

            for (Point point : pointsToChange) {
                binaryImage[point.getY()][point.getX()] = 0;
            }

            pointsToChange.clear();

        } while (hasChange);

        return binaryImage;
    }

    private class Point {

        private int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    };

    private int getA(int[][] binaryImage, int y, int x) {

        int count = 0;
        //p2 p3
        if (binaryImage[y - 1][x] == 0 && binaryImage[y - 1][x + 1] == 1) {
            count++;
        }
        //p3 p4
        if (binaryImage[y - 1][x + 1] == 0 && binaryImage[y][x + 1] == 1) {
            count++;
        }
        //p4 p5
        if (binaryImage[y][x + 1] == 0 && binaryImage[y + 1][x + 1] == 1) {
            count++;
        }
        //p5 p6
        if (binaryImage[y + 1][x + 1] == 0 && binaryImage[y + 1][x] == 1) {
            count++;
        }
        //p6 p7
        if (binaryImage[y + 1][x] == 0 && binaryImage[y + 1][x - 1] == 1) {
            count++;
        }
        //p7 p8
        if (binaryImage[y + 1][x - 1] == 0 && binaryImage[y][x - 1] == 1) {
            count++;
        }
        //p8 p9
        if (binaryImage[y][x - 1] == 0 && binaryImage[y - 1][x - 1] == 1) {
            count++;
        }
        //p9 p2
        if (binaryImage[y - 1][x - 1] == 0 && binaryImage[y - 1][x] == 1) {
            count++;
        }

        return count;
    }

    private int getB(int[][] binaryImage, int y, int x) {

        return binaryImage[y - 1][x] + binaryImage[y - 1][x + 1] + binaryImage[y][x + 1]
                + binaryImage[y + 1][x + 1] + binaryImage[y + 1][x] + binaryImage[y + 1][x - 1]
                + binaryImage[y][x - 1] + binaryImage[y - 1][x - 1];
    }
}

Results:

before
1100111
1100111
1100111
1100111
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1111110
0000000
after
1100111
1000001
1000001
1000111
1000100
1000100
1000100
1000100
1000100
1000100
1000100
1000100
1111100
0000000

The equations and images of equations have been taken from book
Character Recognition Systems: A Guide for Students and Practitioners by by Mohamed Cheriet, Nawwaf Kharma, Cheng-Lin Liu and Ching Suen .

About these ads