Zhang-Suen thinning algorithm

From Rosetta Code
Jump to: navigation, search
Task
Zhang-Suen thinning algorithm
You are encouraged to solve this task according to the task description, using any language you may know.

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:

P9P2P3
P8P1P4
P7P6P5

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

  • Define 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(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 are just noted at this stage.

  • (0) The pixel is black and has eight neighbours
  • (1) 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(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
  1. Write a routine to perform Zhang-Suen thinning on an image matrix of ones and zeroes.
  2. 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

Contents

[edit] AutoHotkey

Works with: AutoHotkey_L

Reads input from a text file and writes output to a different text file (first creating the file, if necessary).

FileIn  := A_ScriptDir "\Zhang-Suen.txt"
FileOut := A_ScriptDir "\NewFile.txt"
 
if (!FileExist(FileIn)) {
MsgBox, 48, File Not Found, % "File """ FileIn """ not found."
ExitApp
}
S := {}
N := [2,3,4,5,6,7,8,9,2]
 
Loop, Read, % FileIn
{
LineNum := A_Index
Loop, Parse, A_LoopReadLine
S[LineNum, A_Index] := A_LoopField
}
 
Loop {
FlipCount := 0
Loop, 2 {
Noted := [], i := A_Index
for LineNum, Line in S {
for PixNum, Pix in Line {
; (0)
if (Pix = 0 || (P := GetNeighbors(LineNum, PixNum, S)) = 1)
continue
; (1)
BP := 0
for j, Val in P
BP += Val
if (BP < 2 || BP > 6)
continue
; (2)
AP := 0
Loop, 8
if (P[N[A_Index]] = "0" && P[N[A_Index + 1]] = "1")
AP++
if (AP != 1)
continue
; (3 and 4)
if (i = 1) {
if (P[2] + P[4] + P[6] = 3 || P[4] + P[6] + P[8] = 3)
continue
}
else if (P[2] + P[4] + P[8] = 3 || P[2] + P[6] + P[8] = 3)
continue
 
Noted.Insert([LineNum, PixNum])
FlipCount++
}
}
for j, Coords in Noted
S[Coords[1], Coords[2]] := 0
}
if (!FlipCount)
break
}
 
for LineNum, Line in S {
for PixNum, Pix in Line
Out .= Pix ? "#" : " "
Out .= "`n"
}
FileAppend, % Out, % FileOut
 
GetNeighbors(Y, X, S) {
Neighbors := []
if ((Neighbors[8] := S[Y, X - 1]) = "")
return 1
if ((Neighbors[4] := S[Y, X + 1]) = "")
return 1
Loop, 3
if ((Neighbors[A_Index = 1 ? 9 : A_Index] := S[Y - 1, X - 2 + A_Index]) = "")
return 1
Loop, 3
if ((Neighbors[8 - A_Index] := S[Y + 1, X - 2 + A_Index]) = "")
return 1
return Neighbors
}

Output:

                                
  #######         ######        
  #     #        ##             
  #      #       #              
  #     #        #              
  ##### #        #              
       ##        #              
        #    #   ##    ##   #   
         #         ####         
                                

[edit] D

This uses the module from the Bitmap Task.

import std.stdio, std.algorithm, std.string, std.functional,
std.typecons, std.typetuple, bitmap;
 
struct BlackWhite {
ubyte c;
alias c this;
static immutable black = typeof(this)(0),
white = typeof(this)(1);
}
 
alias Neighbours = BlackWhite[9];
alias Img = Image!BlackWhite;
 
/// Zhang-Suen thinning algorithm.
Img zhangSuen(Img image1) pure /*nothrow*/
in {
assert(image1.image.all!(x => x == Img.black || x == Img.white));
} out(result) {
assert(result.nx == image1.nx && result.ny == image1.ny);
assert(result.image.all!(x => x == Img.black || x == Img.white));
} body {
/// True if inf <= x <= sup.
static inInterval(T)(in T x, in T inf, in T sup) pure nothrow {
return x >= inf && x <= sup;
}
 
/// Return 8-neighbours+1 of point (x,y) of given image, in order.
static void neighbours(in Img I, in size_t x, in size_t y,
out Neighbours n) pure nothrow {
n = [I[x,y-1], I[x+1,y-1], I[x+1,y], I[x+1,y+1], // P2,P3,P4,P5
I[x,y+1], I[x-1,y+1], I[x-1,y], I[x-1,y-1], // P6,P7,P8,P9
I[x,y-1]];
}
 
if (image1.nx < 3 || image1.ny < 3)
return image1;
auto image2 = Img.fromData(image1.image.dup, image1.nx, image1.ny);
 
Neighbours n;
bool hasChanged;
do {
hasChanged = false;
 
foreach (immutable ab; TypeTuple!(tuple(2, 4), tuple(0, 6))) {
foreach (immutable y; 1 .. image1.ny - 1) {
foreach (immutable x; 1 .. image1.nx - 1) {
neighbours(image1, x, y, n);
if (image1[x, y] && // Cond. 0
(!n[ab[0]] || !n[4] || !n[6]) && // Cond. 4
(!n[0] || !n[2] || !n[ab[1]]) && // Cond. 3
n[].count([0, 1]) == 1 && // Cond. 2
// n[0 .. 8].sum in iota(2, 7)) {
inInterval(n[0 .. 8].sum, 2, 6)) { // Cond. 1
hasChanged = true;
image2[x, y] = Img.black;
} else
image2[x, y] = image1[x, y];
}
}
image1.swap(image2);
}
} while (hasChanged);
 
return image1;
}
 
void main() {
immutable before_txt = "
##..###
##..###
##..###
##..###
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
######.
......."
;
 
immutable small_rc = "
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................"
;
 
immutable rc = "
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
..........................................................."
;
 
foreach (immutable txt; [before_txt, small_rc, rc]) {
auto img = Img.fromText(txt);
"From:".writeln;
img.textualShow(/*bl=*/ '.', /*wh=*/ '#');
"\nTo thinned:".writeln;
img.zhangSuen.textualShow(/*bl=*/ '.', /*wh=*/ '#');
writeln;
}
}
Output:
From:
##..###
##..###
##..###
##..###
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
######.
.......

To thinned:
##..###
#.....#
#.....#
#...###
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#####..
.......

From:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................

To thinned:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................

From:
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
...........................................................

To thinned:
...........................................................
...........................................................
....#.##########.......................#######.............
.....##........#...................####.......#............
.....#..........#.................##.......................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....############...............#..........................
.....#..........#...............#..........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#............................##.......................
.....#.............................############............
.......................###..........................###....
...........................................................
...........................................................

[edit] Groovy

def zhangSuen(text) {
def image = text.split('\n').collect { line -> line.collect { it == '#' ? 1 : 0} }
def p2, p3, p4, p5, p6, p7, p8, p9
def step1 = { (p2 * p4 * p6 == 0) && (p4 * p6 * p8 == 0) }
def step2 = { (p2 * p4 * p8 == 0) && (p2 * p6 * p8 == 0) }
def reduce = { step ->
def toWhite = []
image.eachWithIndex{ line, y ->
line.eachWithIndex{ pixel, x ->
if (!pixel) return
(p2, p3, p4, p5, p6, p7, p8, p9) = [image[y-1][x], image[y-1][x+1], image[y][x+1], image[y+1][x+1], image[y+1][x], image[y+1][x-1], image[y][x-1], image[y-1][x-1]]
def a = [[p2,p3],[p3,p4],[p4,p5],[p5,p6],[p6,p7],[p7,p8],[p8,p9],[p9,p2]].collect { a1, a2 -> (a1 == 0 && a2 ==1) ? 1 : 0 }.sum()
def b = [p2, p3, p4, p5, p6, p7, p8, p9].sum()
if (a != 1 || b < 2 || b > 6) return
 
if (step.call()) toWhite << [y,x]
}
}
toWhite.each { y, x -> image[y][x] = 0 }
!toWhite.isEmpty()
}
 
while (reduce(step1) | reduce(step2));
image.collect { line -> line.collect { it ? '#' : '.' }.join('') }.join('\n')
}

Testing:

def small = """\
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................"""
.stripIndent()
 
def large = """\
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
..........................................................."""
.stripIndent()
 
[small, large].each {
println "From:"
println it
println "To:"
println zhangSuen(it)
println()
}

Output:

From:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
To:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................

From:
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
...........................................................
To:
...........................................................
...........................................................
....#.##########.......................#######.............
.....##........#...................####.......#............
.....#..........#.................##.......................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....############...............#..........................
.....#..........#...............#..........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#............................##.......................
.....#.............................############............
.......................###..........................###....
...........................................................
...........................................................

[edit] J

Solution:

isBlackPx=: '1'&=;._2             NB. boolean array of black pixels
toImage=: [: , LF ,.~ '01' {~ ] NB. convert to original representation
frameImg=: 0 ,. 0 , >:@$ {. ] NB. adds border of 0's to image
 
neighbrs=: adverb define NB. applies verb u to neighbourhoods
(1 1 ,: 3 3) u;._3 y
)
 
Bdry=: 1 2 5 8 7 6 3 0 1 NB. map pixel index to neighbour order
getPx=: { , NB. get desired pixels from neighbourhood
Ap1=: [: +/ 2 </\ Bdry&getPx NB. count 0->1 transitions
Bp1=: [: +/ [: }. Bdry&getPx NB. count black neighbours
 
c11=: (2&<: *. <:&6)@Bp1 NB. step 1, condition 1
c12=: 1 = Ap1 NB. ...
c13=: 0 e. 1 5 7&getPx
c14=: 0 e. 5 7 3&getPx
c23=: 0 e. 1 5 3&getPx NB. step2, condition 3
c24=: 0 e. 1 7 3&getPx
 
cond1=: c11 *. c12 *. c13 *. c14 NB. step1 conditions
cond2=: c11 *. c12 *. c23 *. c24 NB. step2 conditions
whiten=: [ * -.@:*. NB. make black pixels white
step1=: whiten frameImg@(cond1 neighbrs)
step2=: whiten frameImg@(cond2 neighbrs)
 
zhangSuen=: [: toImage [: step2@step1^:_ isBlackPx

Alternative, explicit representation of last verb above

zhangSuenX=: verb define
img=. isBlackPx y
whilst. 0 < +/ , msk1 +.&-. msk2 do.
msk1=. (-.@:*. [: frameImg cond1 neighbrs) img
img=. msk1 * img
msk2=. (-.@:*. [: frameImg cond2 neighbrs) img
img=. msk2 * img
end.
toImage img
)

Example Use:

toASCII=: ' #' {~ '1'&=;._2       NB. convert to ASCII representation
 
ExampleImg=: noun define
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
)
 
toASCII zhangSuen ExampleImg
 
####### ######
# # ##
# # #
# # #
##### # #
## #
# # ## ## #
# ####
 

[edit] Perl 6

Takes the original image from a file that may be based on any characters whose low bits are 0 or 1 (which conveniently includes . and #).

constant DEBUG = 1;
 
my @lines = ([.ords X+& 1] for lines); # The low bits Just Work.
my \v = +@lines;
my \h = +@lines[0];
my @black = @lines.map: *.values; # Flatten to 1-dimensional.
 
my \p8 = [-h-1, -h+0, -h+1, # Flatland distances to 8 neighbors.
0-1, 0+1,
h-1, h+0, h+1].[1,2,4,7,6,5,3,0]; # (in cycle order)
 
# Candidates have 8 neighbors and are known black
my @cand = grep { @black[$_] }, do
for 1..v-2 X 1..h-2 -> \y,\x { y*h + x }
 
repeat while my @goners1 or my @goners2 {
sub seewhite (\w1,\w2) {
sub cycles (@neighbors) { [+] @neighbors Z< @neighbors[].rotate }
sub blacks (@neighbors) { [+] @neighbors }
 
my @prior = @cand; @cand = ();
 
gather for @prior -> \p {
my \n = @black[p8 X+ p];
if cycles(n) == 1 and 2 <= blacks(n) <= 6 and n[w1].any == 0 and n[w2].any == 0
{ take p }
else { @cand.push: p }
}
}
 
@goners1 = seewhite (0,2,4), (2,4,6);
@black[@goners1] = 0 xx *;
say "Ping: {[+] @black} remaining after removing ", @goners1 if DEBUG;
 
@goners2 = seewhite (0,2,6), (0,4,6);
@black[@goners2] = 0 xx *;
say "Pong: {[+] @black} remaining after removing ", @goners2 if DEBUG;
}
 
say @black.splice(0,h).join.trans('01' => '.#') while @black;
Output:
Ping: 66 remaining after removing 33 41 49 56 67 71 74 80 83 86 89 99 106 114 119 120 121 131 135 138 146 169 178 195 197 210 215 217 227 230 233 236 238 240 243 246 249 251 253 257 258 259 263 264 266 268 269 270 273 274 279 280 283 284 285
Pong: 47 remaining after removing 65 73 88 97 104 112 129 137 144 161 167 176 193 198 208 216 225 226 231
Ping: 45 remaining after removing 87 194
Pong: 45 remaining after removing 
Ping: 45 remaining after removing 
Pong: 45 remaining after removing 
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................

[edit] Python

Several input images are converted.

# -*- coding: utf-8 -*-
 
# Example from [http://nayefreza.wordpress.com/2013/05/11/zhang-suen-thinning-algorithm-java-implementation/ this blog post].
beforeTxt = '''\
1100111
1100111
1100111
1100111
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1111110
0000000\
'''

 
# Thanks to [http://www.network-science.de/ascii/ this site] and vim for these next two examples
smallrc01 = '''\
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000\
'''

 
rc01 = '''\
00000000000000000000000000000000000000000000000000000000000
01111111111111111100000000000000000001111111111111000000000
01111111111111111110000000000000001111111111111111000000000
01111111111111111111000000000000111111111111111111000000000
01111111100000111111100000000001111111111111111111000000000
00011111100000111111100000000011111110000000111111000000000
00011111100000111111100000000111111100000000000000000000000
00011111111111111111000000000111111100000000000000000000000
00011111111111111110000000000111111100000000000000000000000
00011111111111111111000000000111111100000000000000000000000
00011111100000111111100000000111111100000000000000000000000
00011111100000111111100000000111111100000000000000000000000
00011111100000111111100000000011111110000000111111000000000
01111111100000111111100000000001111111111111111111000000000
01111111100000111111101111110000111111111111111111011111100
01111111100000111111101111110000001111111111111111011111100
01111111100000111111101111110000000001111111111111011111100
00000000000000000000000000000000000000000000000000000000000\
'''

 
def intarray(binstring):
'''Change a 2D matrix of 01 chars into a list of lists of ints'''
return [[1 if ch == '1' else 0 for ch in line]
for line in binstring.strip().split()]
 
def chararray(intmatrix):
'''Change a 2d list of lists of 1/0 ints into lines of 1/0 chars'''
return '\n'.join(''.join(str(p) for p in row) for row in intmatrix)
 
def toTxt(intmatrix):
'''Change a 2d list of lists of 1/0 ints into lines of '#' and '.' chars'''
return '\n'.join(''.join(('#' if p else '.') for p in row) for row in intmatrix)
 
def neighbours(x, y, image):
'''Return 8-neighbours of point p1 of picture, in order'''
i = image
x1, y1, x_1, y_1 = x+1, y-1, x-1, y+1
#print ((x,y))
return [i[y1][x], i[y1][x1], i[y][x1], i[y_1][x1], # P2,P3,P4,P5
i[y_1][x], i[y_1][x_1], i[y][x_1], i[y1][x_1]] # P6,P7,P8,P9
 
def transitions(neighbours):
n = neighbours + neighbours[0:1] # P2, ... P9, P2
return sum((n1, n2) == (0, 1) for n1, n2 in zip(n, n[1:]))
 
def zhangSuen(image):
changing1 = changing2 = [(-1, -1)]
while changing1 or changing2:
# Step 1
changing1 = []
for y in range(1, len(image) - 1):
for x in range(1, len(image[0]) - 1):
P2,P3,P4,P5,P6,P7,P8,P9 = n = neighbours(x, y, image)
if (image[y][x] == 1 and # (Condition 0)
P4 * P6 * P8 == 0 and # Condition 4
P2 * P4 * P6 == 0 and # Condition 3
transitions(n) == 1 and # Condition 2
2 <= sum(n) <= 6): # Condition 1
changing1.append((x,y))
for x, y in changing1: image[y][x] = 0
# Step 2
changing2 = []
for y in range(1, len(image) - 1):
for x in range(1, len(image[0]) - 1):
P2,P3,P4,P5,P6,P7,P8,P9 = n = neighbours(x, y, image)
if (image[y][x] == 1 and # (Condition 0)
P2 * P6 * P8 == 0 and # Condition 4
P2 * P4 * P8 == 0 and # Condition 3
transitions(n) == 1 and # Condition 2
2 <= sum(n) <= 6): # Condition 1
changing2.append((x,y))
for x, y in changing2: image[y][x] = 0
#print changing1
#print changing2
return image
 
 
if __name__ == '__main__':
for picture in (beforeTxt, smallrc01, rc01):
image = intarray(picture)
print('\nFrom:\n%s' % toTxt(image))
after = zhangSuen(image)
print('\nTo thinned:\n%s' % toTxt(after))
Output:

Just the example asked for in the task:

From:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................

To thinned:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................

[edit] Racket

#lang racket
(define (img-01string->vector str)
(define lines (regexp-split "\n" str))
(define h (length lines))
(define w (if (zero? h) 0 (string-length (car lines))))
(define v (for*/vector #:length (* w h)
((l (in-list lines)) (p (in-string l)))
(match p (#\0 0) (#\1 1) (#\# 1) (#\. 0))))
(values v h w))
 
; Task (2) asks for "or an ASCII-art image of space/non-space characters."
; Spaces don't really impress where the borders are, so we'll use a dot.
(define cell->display-char (match-lambda (0 ".") (1 "#") (else "?")))
 
(define (display-img v w)
(for ((p (in-vector v)) (col (in-naturals)))
(printf "~a" (cell->display-char p))
(when (= (modulo col w) (sub1 w)) (newline))))
 
; returns vector of ([P1's idx] P1 P2 ... P9)
(define (Pns v w r c)
(define i (+ c (* r w)))
(define-syntax-rule (vi+ x) (vector-ref v (+ i x)))
(define-syntax-rule (vi- x) (vector-ref v (- i x)))
(vector i (vi+ 0) (vi- w) (vi+ (- 1 w))
(vi+ 1) (vi+ (+ w 1)) (vi+ w)
(vi+ (- w 1)) (vi- 1) (vi- (+ w 1))))
 
; Second argument to in-vector is the start offset;
; We skip offset 0 (idx) and 1 (P1)
(define (B Ps) (for/sum ((Pn (in-vector Ps 2))) Pn))
 
(define (A Ps)
(define P2 (vector-ref Ps 2))
(define-values (rv _)
(for/fold ((acc 0) (Pn-1 P2))
((Pn (in-sequences (in-vector Ps 3) (in-value P2))))
(values (+ acc (if (and (= 0 Pn-1) (= 1 Pn)) 1 0)) Pn)))
rv)
 
(define-syntax-rule (not-all-black? Pa Pb Pc) (zero? (* Pa Pb Pc)))
(define (z-s-thin v h w)
 ; return idx when thin necessary, #f otherwise
(define (thin? Ps n/bour-check-1 n/bour-check-2)
(match-define (vector idx P1 P2 _ P4 _ P6 _ P8 _) Ps)
(and (= P1 1) (<= 2 (B Ps) 6) (= (A Ps) 1)
(n/bour-check-1 P2 P4 P6 P8)
(n/bour-check-2 P2 P4 P6 P8)
idx))
 
(define (has-white?-246 P2 P4 P6 P8) (not-all-black? P2 P4 P6))
(define (has-white?-468 P2 P4 P6 P8) (not-all-black? P4 P6 P8))
(define (has-white?-248 P2 P4 P6 P8) (not-all-black? P2 P4 P8))
(define (has-white?-268 P2 P4 P6 P8) (not-all-black? P2 P6 P8))
(define (step-n even-Pn-check-1 even-Pn-check-2)
(for*/list ((r (in-range 1 (- h 1)))
(c (in-range 1 (- w 1)))
(idx (in-value (thin? (Pns v w r c)
even-Pn-check-1
even-Pn-check-2)))
#:when idx) idx))
 
(define (step-1) (step-n has-white?-246 has-white?-468))
(define (step-2) (step-n has-white?-248 has-white?-268))
(define (inner-z-s-thin)
(define changed-list-1 (step-1))
(for ((idx (in-list changed-list-1))) (vector-set! v idx 0))
(define changed-list-2 (step-2))
(for ((idx (in-list changed-list-2))) (vector-set! v idx 0))
(unless (and (null? changed-list-1) (null? changed-list-2)) (inner-z-s-thin)))
(inner-z-s-thin))
 
(define (read-display-thin-display-image img-str)
(define-values (v h w) (img-01string->vector img-str))
(printf "Original image:~%") (display-img v w)
(z-s-thin v h w)
(printf "Thinned image:~%") (display-img v w))
 
(define e.g.-image #<<EOS
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
EOS
)
 
(define e.g.-image/2 #<<EOS
##..###
##..###
##..###
##..###
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
######.
.......
EOS
)
 
(module+ main
 ; (read-display-thin-display-image e.g.-image/2)
 ; (newline)
(read-display-thin-display-image e.g.-image))
Output:

Only the requested image is output:

Original image:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
Thinned image:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................


[edit] REXX

/*REXX pgm thins a NxM char grid using the Zhang-Suen thinning algorithm*/
parse arg iFID .; if iFID=='' then iFID='ZHANG_SUEN.DAT'
white=' '; @.=white /* [↓] read the input char grid. */
do row=1 while lines(iFID)\==0; _=linein(iFID)
_=translate(_,,.0); cols.row=length(_)
do col=1 for cols.row; @.row.col=substr(_,col,1)
end /*col*/ /* [↑] assign whole row of chars*/
end /*row*/
rows=row-1 /* adjust ROWS because of DO loop*/
call show@ 'input file ' iFID " contents:" /*show the input char grid.*/
 
do until changed==0; changed=0 /*keep slimming until we're done.*/
do step=1 for 2 /*keep track of step 1 │ step 2.*/
do r=1 for rows /*process all rows and columns. */
do c=1 for cols.r;  !.r.c=@.r.c /*assign alternate grid.*/
if r==1|r==rows|c==1|c==cols.r then iterate /*is an edge?*/
if @.r.c==white then iterate /*White? Then skip it.*/
call Ps; b=b() /*define Ps and "b". */
if b<2 | b>6 then iterate /*is B within range?*/
if a()\==1 then iterate /*count the transitions.*/ /* ╔══╦══╦══╗ */
if step==1 then if (p2 & p4 & p6) | p4 & p6 & p8 then iterate /* ║p9║p2║p3║ */
if step==2 then if (p2 & p4 & p8) | p2 & p6 & p8 then iterate /* ╠══╬══╬══╣ */
 !.r.c=white /*set a grid character to white.*/ /* ║p8║p1║p4║ */
changed=1 /*indicate a char was changed. */ /* ╠══╬══╬══╣ */
end /*c*/ /* ║p7║p6║p5║ */
end /*r*/ /* ╚══╩══╩══╝ */
call copy!2@ /*copy alternate to working grid.*/
end /*step*/
end /*until changed==0*/
 
call show@ 'slimmed output:' /*display the slimmed char grid. */
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────subroutines─────────────────────────*/
a: return (\p2==p3&p3)+(\p3==p4&p4)+(\p4==p5&p5)+(\p5==p6&p6)+(\p6==p7&p7)+(\p7==p8&p8)+(\p8==p9&p9)+(\p9==p2&p2)
b: return p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9
copy!2@: do r=1 for rows; do c=1 for cols.r; @.r.c=!.r.c; end;end; return
show@: say; say arg(1); say; do r=1 for rows; _=; do c=1 for cols.r; _=_||@.r.c; end; say _; end; return
 
Ps: rm=r-1; rp=r+1; cm=c-1; cp=c+1 /*calculate shortcuts.*/
p2=@.rm.c\==white; p3=@.rm.cp\==white; p4=@.r.cp\==white; p5=@.rp.cp\==white
p6=@.rp.c\==white; p7=@.rp.cm\==white; p8=@.r.cm\==white; p9=@.rm.cm\==white; return

output   when using the default input:

input file  ZHANG_SUEN.DAT  contents:


 #################                   #############
 ##################               ################
 ###################            ##################
 ########     #######          ###################
   ######     #######         #######       ######
   ######     #######        #######
   #################         #######
   ################          #######
   #################         #######
   ######     #######        #######
   ######     #######        #######
   ######     #######         #######       ######
 ########     #######          ###################
 ########     ####### ######    ################## ######
 ########     ####### ######      ################ ######
 ########     ####### ######         ############# ######


slimmed output:



    # ##########                       #######
     ##        #                   ####       #
     #          #                 ##
     #          #                #
     #          #                #
     #          #                #
     ############               #
     #          #               #
     #          #                #
     #          #                #
     #          #                #
     #                            ##
     #                             ############
                       ###                          ###

output   when using the default input:   zhang_suen2.dat

input file  zhang_suen2.dat  contents:


 111111111       11111111
 111   1111     1111  1111
 111    111     111    111
 111   1111     111
 111111111      111
 111 1111       111    111
 111  1111  111 1111  1111 111
 111   1111 111  11111111  111


slimmed output:


  1111111         111111
  1     1        11
  1      1       1
  1     1        1
  11111 1        1
       11        1
        1    1   11    11   1
         1         1111

[edit] Ruby

First I define a function zs which given a point and its eight neighbours returns 1 if the point may be culled, 0 otherwise. g indicates if this is step 1 or step 2 in the task description. zs may be changed to remember the step independently if the reader does not wish to explore the algorithm.

class ZhangSuen
NEIGHBOUR8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] # 8 neighbors
CIRCULARS = NEIGHBOUR8 + [NEIGHBOUR8.first] # P2, ... P9, P2
def initialize(str, black="#")
s1 = str.each_line.map{|line| line.chomp.each_char.map{|c| c==black ? 1 : 0}}
s2 = s1.map{|line| line.map{0}}
xrange = 1 ... s1.size-1
yrange = 1 ... s1[0].size-1
printout(s1)
begin
@r = 0
xrange.each{|x| yrange.each{|y| s2[x][y] = s1[x][y] - zs(s1,x,y,1)}} # Step 1
xrange.each{|x| yrange.each{|y| s1[x][y] = s2[x][y] - zs(s2,x,y,0)}} # Step 2
end until @r == 0
printout(s1)
end
def zs(ng,x,y,g)
return 0 if ng[x][y] == 0 or # P1
(ng[x-1][y] + ng[x][y+1] + ng[x+g][y-1+g]) == 3 or # P2, P4, P6/P8
(ng[x-1+g][y+g] + ng[x+1][y] + ng[x][y-1]) == 3 # P4/P2, P6, P8
bp1 = NEIGHBOUR8.inject(0){|res,(i,j)| res += ng[x+i][y+j]} # B(P1)
return 0 if bp1 < 2 or 6 < bp1
ap1 = CIRCULARS.map{|i,j| ng[x+i][y+j]}.each_cons(2).count{|a,b| a<b} # A(P1)
return 0 if ap1 != 1
@r = 1
end
def printout(image)
puts image.map{|row| row.map{|col| " #"[col]}.join}
end
end
 
str = <<EOS
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
...........................................................
EOS

 
ZhangSuen.new(str)
 
task_example = <<EOS
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
EOS

 
ZhangSuen.new(task_example, "1")
Output:

(only the requested result is shown here)

                                
  #######         ######        
  #     #        ##             
  #      #       #              
  #     #        #              
  ##### #        #              
       ##        #              
        #    #   ##    ##   #   
         #         ####         
                              

[edit] Tcl

Only the single image is converted.

# -*- coding: utf-8 -*-
 
set data {
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
}
proc zhang-suen data {
set data [string trim $data]
while 1 {
set n 0
incr n [step 1 data]
incr n [step 2 data]
if !$n break
}
return $data
}
proc step {number _data} {
upvar 1 $_data data
set xmax [string length [lindex $data 0]]
set ymax [llength $data]
switch -- $number {
1 {set cond {(!$P2 || !$P4 || !$P6) && (!$P4 || !$P6 || !$P8)}}
2 {set cond {(!$P2 || !$P4 || !$P8) && (!$P2 || !$P6 || !$P8)}}
}
set hits {}
for {set x 1} {$x < $xmax-1} {incr x} {
for {set y 1} {$y < $ymax-1} {incr y} {
if {[getpix $data $x $y] == 1} {
set b [B $data $x $y]
if {2 <= $b && $b <= 6} {
if {[A $data $x $y] == 1} {
set P2 [getpix $data $x [expr $y-1]]
set P4 [getpix $data [expr $x+1] $y]
set P6 [getpix $data $x [expr $y+1]]
set P8 [getpix $data [expr $x-1] $y]
if $cond {lappend hits $x $y}
}
}
}
}
}
foreach {x y} $hits {set data [setpix $data $x $y 0]}
return [llength $hits]
}
proc A {data x y} {
set res 0
set last [getpix $data $x [expr $y-1]]
foreach {dx dy} {1 -1 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1} {
set this [getpix $data [expr $x+$dx] [expr $y+$dy]]
if {$this > $last} {incr res}
set last $this
}
return $res
}
proc B {data x y} {
set res 0
foreach {dx dy} {1 -1 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1} {
incr res [getpix $data [expr $x+$dx] [expr $y+$dy]]
}
return $res
}
proc getpix {data x y} {
string index [lindex $data $y] $x
}
proc setpix {data x y val} {
set row [lindex $data $y]
lset data $y [string replace $row $x $x $val]
return $data
}
puts [string map {1 @ 0 .} [join [zhang-suen $data] \n]]
Output:
................................
..@@@@@@@.........@@@@@@........
..@.....@........@@.............
..@......@.......@..............
..@.....@........@..............
..@@@@@.@........@..............
.......@@........@..............
........@....@...@@....@@...@...
.........@.........@@@@.........
................................
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox