matlab bwmorph(img, 'thin') implementation in Java gone wrong

Question

I am implementing the matlab 'bwmorph(img, 'thin')' algorithm in Java ImageJ. I've searched all over the net pretty much and found some similar implementations that work better, but I can't find the issue in my code. Any ideas?

My code:

    public void run(ImageProcessor ip) {
        MakeBinary(ip);
        int sum2 = processThin(ip);
        int sum = -1;
        while (sum2 != sum) {
            sum = sum2;
            sum2 = processThin(ip);
        }
    }

    public int processThin(ImageProcessor ipOriginal) {
        int sum = 0;
        // first iteration
        ImageProcessor ip = ipOriginal.duplicate();
        for (int i = 1; i < ip.getWidth() -1; i++)
            for (int j = 1; j < ip.getHeight() -1; j++) {
                int[] neighbors = selectNeighbors(ip, i, j);
                if (G1(neighbors) == 1 && G2(neighbors) >= 2 && G2(neighbors) <= 3 && G3(neighbors) == 0)
                    ip.putPixel(i,j, 0);
            }
        // second iteration
        for (int i = 1; i < ip.getWidth() -1; i++)
            for (int j = 1; j < ip.getHeight()-1; j++) {
                int[] neighbors = selectNeighbors(ip, i, j);
                if (G1(neighbors) == 1 && G2(neighbors) >= 2 && G2(neighbors) <= 3 && G3prime(neighbors) == 0)
                    ip.putPixel(i,j, 0);
            }

        for(int i = 0; i < ip.getWidth(); i++)
            for(int j = 0; j < ip.getHeight(); j++) {
                if (ip.getPixel(i,j) != 0) sum++;
                ipOriginal.putPixel(i, j, ip.getPixel(i, j));
            }
        return sum;
    }

    private int G1(int[] input) {
        int xh = 0;
        for (int i = 1; i <= 4; i++) {
            if (input[2 * i - 1] == 0 && (input[2 * i] == 1 || (2 * i + 1 <= 8 ? input[2 * i + 1] == 1 : input[1] == 1)))
                xh += 1;
        }
        return xh;
    }

    private int G2(int[] input) {
        int n1 = 0, n2 = 0;
        n1 = toInt(toBool(input[4]) || toBool(input[3])) + toInt(toBool(input[1]) || toBool(input[2])) +
                toInt(toBool(input[8]) || toBool(input[7])) + toInt(toBool(input[6]) || toBool(input[5]));
        n2 = toInt(toBool(input[2]) || toBool(input[3])) + toInt(toBool(input[1]) || toBool(input[8])) +
                toInt(toBool(input[6]) || toBool(input[7])) + toInt(toBool(input[4]) || toBool(input[5]));
        return Math.min(n1,n2);
    }

    private int G3 (int[] input){
        return toInt((toBool(input[2]) || toBool(input[3]) || !toBool(input[8])) && toBool(input[1]));
    }

    private int G3prime (int[] input){
        return toInt((toBool(input[6]) || toBool(input[7]) || !toBool(input[4])) && toBool(input[5]));
    }

    private boolean toBool(int i ){
        return i == 1;
    }
    private int toInt(boolean i) {
        return i ? 1 : 0;
    }
    private int[] selectNeighbors(ImageProcessor ip, int i, int j) {
        int[] result = new int[9];
        result[1] = ip.getPixel(i+1,j);
        result[2] = ip.getPixel(i+1,j+1);
        result[3] = ip.getPixel(i,j+1);
        result[4] = ip.getPixel(i-1,j+1);
        result[5] = ip.getPixel(i-1,j);
        result[6] = ip.getPixel(i-1,j-1);
        result[7] = ip.getPixel(i,j-1);
        result[8] = ip.getPixel(i+1,j-1);

        for (int x = 0; x < result.length; x++)
            if (result[x] != 0) result[x] = 1;
        return result;
    }

The main issue appears to be with the horizontal lines, but not only that. Note: I've added the toBool and toInt methods to deal with convenient data types, the code was binary before and the result is the same apparently.

EDIT: After editing the code and omitting doing modifications between two iterations, I ended up with this result now.

The code looks like this now.

public int processThin(ImageProcessor ip) {
        int sum = 0;
        // first iteration
        int[][] mask = new int[ip.getWidth()][ip.getHeight()];
        for (int i = 1; i < ip.getWidth() -1; i++)
            for (int j = 1; j < ip.getHeight() -1; j++) {
                int[] neighbors = selectNeighbors(ip, i, j);
                if (G1(neighbors) == 1 && G2(neighbors) >= 2 && G2(neighbors) <= 3 && G3(neighbors) == 0)
                    mask[i][j]++;
            }
        // second iteration
        for (int i = 1; i < ip.getWidth() -1; i++)
            for (int j = 1; j < ip.getHeight()-1; j++) {
                int[] neighbors = selectNeighbors(ip, i, j);
                if (G1(neighbors) == 1 && G2(neighbors) >= 2 && G2(neighbors) <= 3 && G3prime(neighbors) == 0)
                    mask[i][j]++;
            }

        for(int i = 0; i < ip.getWidth(); i++)
            for(int j = 0; j < ip.getHeight(); j++) {
                if (mask[i][j] != 0) sum++;
                ip.putPixel(i, j, mask[i][j] > 0 ? 0 : ip.getPixel(i,j));
            }
        return sum;
    }

Answer 1

The problem in your original code is that you write into your input image. In the very first iteration, moving left to right, you remove successive pixels because each has, after modifying the previous pixel, a background pixel as neighbor.

There are different ways to implement the thinning operation, but the simplest one that works in-place like your code does requires two passes through the image for each iteration of the thinning:

1. Go through the image and mark all candidate pixels. These are the pixels that have a background neighbor. Marking a pixel can be as simple as setting the pixel value to a given constant, for example 42 (assuming background is 0 and foreground is 1 or 255 or whatever you decided on).

2. Go through the image again and for each marked pixel, determine if removing it would change the geometry of the foreground. If not, remove it. In this test, take the marked pixels that haven't been removed yet as foreground.