How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the Java programming language

Table of Contents

Problem Statement

This is an algorithm used to thin a black and white i.e. one bit per pixel images. For example, with an input image of: It produces the thinned output: Assume black pixels are one and white pixels zero, and that the input image is a rectangular N by M array of ones and zeroes. The algorithm operates on all black pixels P1 that can have eight neighbours. The neighbours are, in order, arranged as:

Obviously the boundary pixels of the image cannot have the full eight neighbours.

All pixels are tested and pixels satisfying all the following conditions (simultaneously) are just noted at this stage. After iterating over the image and collecting all the pixels satisfying all step 1 conditions, all these condition satisfying pixels are set to white.

All pixels are again tested and pixels satisfying all the following conditions are just noted at this stage. After iterating over the image and collecting all the pixels satisfying all step 2 conditions, all these condition satisfying pixels are again set to white.

If any pixels were set in this round of either step 1 or step 2 then all steps are repeated until no image pixels are so changed.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the Java programming language

Here's a detailed explanation of the Java code:

Purpose:

  • Implements the Zhang-Suen thinning algorithm, a technique for skeletonizing binary images (images with only black and white pixels).
  • It preserves the essential structure of the image while reducing its lines to single-pixel width.

Breakdown:

  1. Class and Data:

    • ZhangSuen Class: Encapsulates the algorithm.
    • image String Array: Stores the initial image as a grid of characters (' ' for white, '#' for black).
    • nbrs Array: Contains neighbor offsets for pixel analysis.
    • nbrGroups Array: Defines neighbor groupings for different steps of the algorithm.
    • toWhite List: Stores pixels to be turned white in a given iteration.
    • grid Array: Holds the working image as a 2D character array.

  2. Main Method:

    • Converts image to a 2D char array grid.
    • Calls thinImage to initiate the thinning process.

  3. Thinning Algorithm (thinImage):

    • Iteratively applies the two-step thinning process until no more changes occur:
      • Step 1:
        • Iterates through each black pixel ('#') in grid.
        • Checks conditions (number of neighbors, transitions, specific neighbor patterns).
        • If conditions met, marks pixel for removal (toWhite).
      • Step 2:
        • Similar to Step 1, but with different conditions for neighbor patterns.
      • Removes marked pixels by setting them to white (' ').
      • Repeats until no more pixels are marked for removal.
    • Prints the thinned image using printResult.

  4. Helper Functions:

    • numNeighbors: Counts black neighbors of a pixel.
    • numTransitions: Counts black-to-white transitions around a pixel.
    • atLeastOneIsWhite: Checks if specific neighbor patterns have at least one white pixel.
    • printResult: Prints the final thinned image.

Key Points:

  • The Zhang-Suen algorithm iteratively removes pixels while preserving connectivity and shape.
  • It uses specific conditions based on neighbor counts and patterns to ensure single-pixel width lines.
  • The code effectively implements this algorithm for image skeletonization.

Source code in the java programming language

import java.awt.Point;
import java.util.*;

public class ZhangSuen {

    final static String[] image = {
        "                                                          ",
        " #################                   #############        ",
        " ##################               ################        ",
        " ###################            ##################        ",
        " ########     #######          ###################        ",
        "   ######     #######         #######       ######        ",
        "   ######     #######        #######                      ",
        "   #################         #######                      ",
        "   ################          #######                      ",
        "   #################         #######                      ",
        "   ######     #######        #######                      ",
        "   ######     #######        #######                      ",
        "   ######     #######         #######       ######        ",
        " ########     #######          ###################        ",
        " ########     ####### ######    ################## ###### ",
        " ########     ####### ######      ################ ###### ",
        " ########     ####### ######         ############# ###### ",
        "                                                          "};

    final static int[][] nbrs = {{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1},
        {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}};

    final static int[][][] nbrGroups = {{{0, 2, 4}, {2, 4, 6}}, {{0, 2, 6},
        {0, 4, 6}}};

    static List<Point> toWhite = new ArrayList<>();
    static char[][] grid;

    public static void main(String[] args) {
        grid = new char[image.length][];
        for (int r = 0; r < image.length; r++)
            grid[r] = image[r].toCharArray();

        thinImage();
    }

    static void thinImage() {
        boolean firstStep = false;
        boolean hasChanged;

        do {
            hasChanged = false;
            firstStep = !firstStep;

            for (int r = 1; r < grid.length - 1; r++) {
                for (int c = 1; c < grid[0].length - 1; c++) {

                    if (grid[r][c] != '#')
                        continue;

                    int nn = numNeighbors(r, c);
                    if (nn < 2 || nn > 6)
                        continue;

                    if (numTransitions(r, c) != 1)
                        continue;

                    if (!atLeastOneIsWhite(r, c, firstStep ? 0 : 1))
                        continue;

                    toWhite.add(new Point(c, r));
                    hasChanged = true;
                }
            }

            for (Point p : toWhite)
                grid[p.y][p.x] = ' ';
            toWhite.clear();

        } while (firstStep || hasChanged);

        printResult();
    }

    static int numNeighbors(int r, int c) {
        int count = 0;
        for (int i = 0; i < nbrs.length - 1; i++)
            if (grid[r + nbrs[i][1]][c + nbrs[i][0]] == '#')
                count++;
        return count;
    }

    static int numTransitions(int r, int c) {
        int count = 0;
        for (int i = 0; i < nbrs.length - 1; i++)
            if (grid[r + nbrs[i][1]][c + nbrs[i][0]] == ' ') {
                if (grid[r + nbrs[i + 1][1]][c + nbrs[i + 1][0]] == '#')
                    count++;
            }
        return count;
    }

    static boolean atLeastOneIsWhite(int r, int c, int step) {
        int count = 0;
        int[][] group = nbrGroups[step];
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < group[i].length; j++) {
                int[] nbr = nbrs[group[i][j]];
                if (grid[r + nbr[1]][c + nbr[0]] == ' ') {
                    count++;
                    break;
                }
            }
        return count > 1;
    }

    static void printResult() {
        for (char[] row : grid)
            System.out.println(row);
    }
}

You may also check:How to resolve the algorithm Convert decimal number to rational step by step in the MATLAB / Octave programming language
You may also check:How to resolve the algorithm Collections step by step in the Elena programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the Slate programming language
You may also check:How to resolve the algorithm Display a linear combination step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Walk a directory/Recursively step by step in the Julia programming language