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:

                                                           
                                                           
    # ##########                       #######             
     ##        #                   ####       #            
     #          #                 ##                       
     #          #                #                         
     #          #                #                         
     #          #                #                         
     ############               #                          
     #          #               #                          
     #          #                #                         
     #          #                #                         
     #          #                #                         
     #                            ##                       
     #                             ############            
                       ###                          ###    
                                                           
                                                           
Algorithm

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:


   P9      P2      P3   
   P8      P1      P4   
   P7      P6      P5   



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

 Define 



A
(
P
1
)


{\displaystyle A(P1)}

 = the number of transitions from white to black, (0 -> 1) in the sequence P2,P3,P4,P5,P6,P7,P8,P9,P2. (Note the extra P2 at the end - it is circular).
 Define 



B
(
P
1
)


{\displaystyle B(P1)}

 = The number of black pixel neighbours of P1. ( = sum(P2 .. P9) )


Step 1

All pixels are tested and pixels satisfying all the following conditions (simultaneously) are just noted at this stage.

 (0) The pixel is black and has eight neighbours
 (1) 



2
<=
B
(
P
1
)
<=
6


{\displaystyle 2<=B(P1)<=6}


 (2) A(P1) = 1
 (3) At least one of P2 and P4 and P6 is white
 (4) At least one of P4 and P6 and P8 is white
After iterating over the image and collecting all the pixels satisfying all step 1 conditions, all these condition satisfying pixels are set to white.



Step 2

All pixels are again tested and pixels satisfying all the following conditions are just noted at this stage.

 (0) The pixel is black and has eight neighbours
 (1) 



2
<=
B
(
P
1
)
<=
6


{\displaystyle 2<=B(P1)<=6}


 (2) A(P1) = 1
 (3) At least one of P2 and P4 and P8 is white
 (4) At least one of P2 and P6 and P8 is white
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.



Iteration

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.



Task

 Write a routine to perform Zhang-Suen thinning on an image matrix of ones and zeroes.
 Use the routine to thin the following image and show the output here on this page as either a matrix of ones and zeroes, an image, or an ASCII-art image of space/non-space characters. 
          00000000000000000000000000000000
          01111111110000000111111110000000
          01110001111000001111001111000000
          01110000111000001110000111000000
          01110001111000001110000000000000
          01111111110000001110000000000000
          01110111100000001110000111000000
          01110011110011101111001111011100
          01110001111011100111111110011100
          00000000000000000000000000000000



Reference

 Zhang-Suen Thinning Algorithm, Java Implementation by Nayef Reza.
 "Character Recognition Systems: A Guide for Students and Practitioners" By Mohamed Cheriet, Nawwaf Kharma, Cheng-Lin Liu, Ching Suen


V beforeTxt = |‘1100111
                1100111
                1100111
                1100111
                1100110
                1100110
                1100110
                1100110
                1100110
                1100110
                1100110
                1100110
                1111110
                0000000’
 
V smallrc01 =
|‘00000000000000000000000000000000
  01111111110000000111111110000000
  01110001111000001111001111000000
  01110000111000001110000111000000
  01110001111000001110000000000000
  01111111110000001110000000000000
  01110111100000001110000111000000
  01110011110011101111001111011100
  01110001111011100111111110011100
  00000000000000000000000000000000’
 
V rc01 =
|‘00000000000000000000000000000000000000000000000000000000000
  01111111111111111100000000000000000001111111111111000000000
  01111111111111111110000000000000001111111111111111000000000
  01111111111111111111000000000000111111111111111111000000000
  01111111100000111111100000000001111111111111111111000000000
  00011111100000111111100000000011111110000000111111000000000
  00011111100000111111100000000111111100000000000000000000000
  00011111111111111111000000000111111100000000000000000000000
  00011111111111111110000000000111111100000000000000000000000
  00011111111111111111000000000111111100000000000000000000000
  00011111100000111111100000000111111100000000000000000000000
  00011111100000111111100000000111111100000000000000000000000
  00011111100000111111100000000011111110000000111111000000000
  01111111100000111111100000000001111111111111111111000000000
  01111111100000111111101111110000111111111111111111011111100
  01111111100000111111101111110000001111111111111111011111100
  01111111100000111111101111110000000001111111111111011111100
  00000000000000000000000000000000000000000000000000000000000’
 
F intarray(binstring)
   ‘Change a 2D matrix of 01 chars into a list of lists of ints’
   R binstring.split("\n").map(line -> line.map(ch -> (I ch == ‘1’ {1} E 0)))
 
F chararray(intmatrix)
   ‘Change a 2d list of lists of 1/0 ints into lines of 1/0 chars’
   R intmatrix.map(row -> row.map(p -> String(p)).join(‘’)).join("\n")
 
F toTxt(intmatrix)
   ‘Change a 2d list of lists of 1/0 ints into lines of '#' and '.' chars’
   R intmatrix.map(row -> row.map(p -> (I p {‘#’} E ‘.’)).join(‘’)).join("\n")
 
F neighbours_array(x, y, image)
   ‘Return 8-neighbours of point p1 of picture, in order’
   V i = image
   V (x1, y1, x_1, y_1) = (x + 1, y - 1, x - 1, y + 1)
   R [i[y1][x], i[y1][x1], i[y][x1], i[y_1][x1], i[y_1][x], i[y_1][x_1], i[y][x_1], i[y1][x_1]]
 
F neighbours_tuple(x, y, image)
   ‘Return 8-neighbours of point p1 of picture, in order’
   V i = image
   V (x1, y1, x_1, y_1) = (x + 1, y - 1, x - 1, y + 1)
   R (i[y1][x], i[y1][x1], i[y][x1], i[y_1][x1], i[y_1][x], i[y_1][x_1], i[y][x_1], i[y1][x_1])
 
F transitions(neighbours)
   V s = 0
   L(i) 7
      s += Int((neighbours[i], neighbours[i + 1]) == (0, 1))
   R s + Int((neighbours[7], neighbours[0]) == (0, 1))
 
F zhangSuen(&image)
   V changing1 = [(-1, -1)]
   V changing2 = [(-1, -1)]
   L !changing1.empty | !changing2.empty
      changing1.drop()
      L(y) 1 .< image.len - 1
         L(x) 1 .< image[0].len - 1
            V n = neighbours_array(x, y, image)
            V (P2, P3, P4, P5, P6, P7, P8, P9) = neighbours_tuple(x, y, image)
            I (image[y][x] == 1 & P4 * P6 * P8 == 0 & P2 * P4 * P6 == 0 & transitions(n) == 1 & sum(n) C 2..6)
               changing1.append((x, y))
      L(x, y) changing1
         image[y][x] = 0
      changing2.drop()
      L(y) 1 .< image.len - 1
         L(x) 1 .< image[0].len - 1
            V n = neighbours_array(x, y, image)
            V (P2, P3, P4, P5, P6, P7, P8, P9) = neighbours_tuple(x, y, image)
            I (image[y][x] == 1 & P2 * P6 * P8 == 0 & P2 * P4 * P8 == 0 & transitions(n) == 1 & sum(n) C 2..6)
               changing2.append((x, y))
      L(x, y) changing2
         image[y][x] = 0
   R image
 
L(picture) (beforeTxt, smallrc01, rc01)
   V image = intarray(picture)
   print("\nFrom:\n#.".format(toTxt(image)))
   V after = zhangSuen(&image)
   print("\nTo thinned:\n#.".format(toTxt(after)))