Zhang-Suen Thinning Algorithm, Java Implementation

Featured

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 imageProcessing.service;

import imageProcessing.model.Point;

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

/**
 * Created by nayef on 1/26/15.
 */
public class ThinningService {
    /**
     * @param givenImage
     * @param changeGivenImage decides whether the givenArray should be modified or a clone should be used
     * @return a 2D array of binary image after thinning using zhang-suen thinning algo.
     */
    public int[][] doZhangSuenThinning(final int[][] givenImage, boolean changeGivenImage) {
        int[][] binaryImage;
        if (changeGivenImage) {
            binaryImage = givenImage;
        } else {
            binaryImage = givenImage.clone();
        }
        int a, b;
        List<Point> 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 int getA(int[][] binaryImage, int y, int x) {
        int count = 0;
//p2 p3
        if (y - 1 >= 0 && x + 1 < binaryImage[y].length && binaryImage[y - 1][x] == 0 && binaryImage[y - 1][x + 1] == 1) {
            count++;
        }
//p3 p4
        if (y - 1 >= 0 && x + 1 < binaryImage[y].length && binaryImage[y - 1][x + 1] == 0 && binaryImage[y][x + 1] == 1) {
            count++;
        }
//p4 p5
        if (y + 1 < binaryImage.length && x + 1 < binaryImage[y].length && binaryImage[y][x + 1] == 0 && binaryImage[y + 1][x + 1] == 1) {
            count++;
        }
//p5 p6
        if (y + 1 < binaryImage.length && x + 1 < binaryImage[y].length && binaryImage[y + 1][x + 1] == 0 && binaryImage[y + 1][x] == 1) {
            count++;
        }
//p6 p7
        if (y + 1 < binaryImage.length && x - 1 >= 0 && binaryImage[y + 1][x] == 0 && binaryImage[y + 1][x - 1] == 1) {
            count++;
        }
//p7 p8
        if (y + 1 < binaryImage.length && x - 1 >= 0 && binaryImage[y + 1][x - 1] == 0 && binaryImage[y][x - 1] == 1) {
            count++;
        }
//p8 p9
        if (y - 1 >= 0 && x - 1 >= 0 && binaryImage[y][x - 1] == 0 && binaryImage[y - 1][x - 1] == 1) {
            count++;
        }
//p9 p2
        if (y - 1 >= 0 && x - 1 >= 0 && 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];
    }
}
package imageProcessing.model;

/**
 * Created by nayef on 1/27/15.
 */
public class Point {
    private int x;
    private int 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;
    }
}

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 .

“Outer Contour Tracing” using square-tracing algorithm for binary image, Java Implementation

Tags

, , , , , , ,

Outer contour tracing is very helpful for recognizing characters. the red border in the second image below shows the outer contour.

a aContour

 

Code :
SquareTracingService class

package squaretracing;

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

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

    public List getContourPoints(int[][] srcImage) {
        int[][] image = srcImage.clone();
        clearBorder(image);

        List points = new LinkedList();

        Point startingPoint = getStartingPoint(image);
        Point currentPoint = startingPoint.getClone();

        do {
            if (image[currentPoint.getY()][currentPoint.getX()] == 1) {
                points.add(currentPoint.getClone());
                currentPoint.advanceToLeft();
            } else {
                currentPoint.advanceToRight();
            }

        } while (!startingPoint.equals(currentPoint));

        return points;
    }

    private Point getStartingPoint(int[][] image) {

        for (int y = image.length - 1; y >= 0; y--) {

            for (int x = image[y].length - 1; x >= 0; x--) {

                if (image[y][x] == 1) {
                    return new Point(x, y);
                }

            }
        }

        return null;
    }

    private void clearBorder(int[][] image) {

        for (int y = 0; y < image.length; y++) {
            for (int x = 0; x < image[y].length; x++) {
                if (y == 0 || x == 0 || y == image.length - 1 || x == image[y].length - 1) {
                    image[y][x] = 0;
                }

            }

        }

    }
}

Point Class


package squaretracing;

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

    public static final int DIR_NORTH = 0;
    public static final int DIR_EAST = 1;
    public static final int DIR_SOUTH = 2;
    public static final int DIR_WEST = 3;
    private int x;
    private int y;
    private int direction;

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

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

    public Point(Point refPoint) {
        this.x = refPoint.x;
        this.y = refPoint.y;
        this.direction = refPoint.direction;
    }

    public void faceRight() {

        direction = (direction + 1) % 4;

    }

    private void faceLeft() {
        if (direction == 0) {
            direction = 3;
        } else {
            direction--;
        }
    }

    private void goForward() {
        if (direction == DIR_NORTH) {
            y = y - 1;
        }
        if (direction == DIR_EAST) {
            x = x + 1;
        }
        if (direction == DIR_SOUTH) {
            y = y + 1;
        }
        if (direction == DIR_WEST) {
            x = x - 1;
        }

    }

    public void advanceToLeft() {

        faceLeft();
        goForward();
    }

    public void advanceToRight() {
        faceRight();
        goForward();
    }

    public Point getClone() {
        return new Point(this);
    }

    public int getDirection() {
        return direction;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Point other = (Point) obj;
        if (this.x != other.x) {
            return false;
        }
        if (this.y != other.y) {
            return false;
        }
        return true;
    }

}

results:

here ‘-‘ means contour points

contour

Follow

Get every new post delivered to your Inbox.