Zhang-Suen thinning algorithm: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
(47 intermediate revisions by 20 users not shown) | |||
Line 44:
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:
<table border="4">
<tr><td> P9 </td><td> P2 </td><td> P3 </td></tr>
<tr><td> P8 </td><td><b> P1 </b></td><td> P4 </td></tr>
<tr><td> P7 </td><td> P6 </td><td> P5 </td></tr>
</table>
Obviously the boundary pixels of the image cannot have the full eight neighbours.
Line 55 ⟶ 59:
* Define <math>A(P1)</math> = 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 <math>B(P1)</math> = The number of black pixel neighbours of P1. ( = sum(P2 .. P9) )
;Step 1:
Line 63 ⟶ 68:
* (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:
Line 72 ⟶ 79:
* (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:
* [http://nayefreza.wordpress.com/2013/05/11/zhang-suen-thinning-algorithm-java-implementation/ 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
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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)))</syntaxhighlight>
{{out}}
Just the example asked for in the task:
<pre>
From:
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
...........................................................
To thinned:
...........................................................
...........................................................
....#.##########.......................#######.............
.....##........#...................####.......#............
.....#..........#.................##.......................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....############...............#..........................
.....#..........#...............#..........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#............................##.......................
.....#.............................############............
.......................###..........................###....
...........................................................
...........................................................
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC DrawImage(BYTE ARRAY image BYTE x,y,width,height)
BYTE i,j
BYTE POINTER ptr
Color=2
FOR j=0 TO height-1
DO
Plot(x,j+y) DrawTo(x+width-1,j+y)
OD
Color=1
ptr=image
FOR j=0 TO height-1
DO
FOR i=0 TO width-1
DO
IF ptr^ THEN
Plot(i+x,j+y)
FI
ptr==+1
OD
OD
RETURN
PROC Thinning(BYTE ARRAY image BYTE width,height)
DEFINE PTR="CARD"
DEFINE MAX="200"
PTR ARRAY change(MAX)
BYTE POINTER p1,p2,p3,p4,p5,p6,p7,p8,p9,p68,p24
INT count,i
BYTE x,y,sum,step1
step1=1
DO
count=0
p1=image p8=p1-1 p4=p1+1
p2=p1-width p6=p1+width
p9=p2-1 p3=p2+1
p7=p6-1 p5=p6+1
FOR y=0 TO height-1
DO
FOR x=0 TO width-1
DO
IF p1^=1 AND x>0 AND y>0 AND x<width-1 AND y<height-1 THEN
sum=p2^+p3^+p4^+p5^+p6^+p7^+p8^+p9^
IF sum>=2 AND sum<=6 THEN
sum=0
IF p3^>p2^ THEN sum==+1 FI
IF p4^>p3^ THEN sum==+1 FI
IF p5^>p4^ THEN sum==+1 FI
IF p6^>p5^ THEN sum==+1 FI
IF p7^>p6^ THEN sum==+1 FI
IF p8^>p7^ THEN sum==+1 FI
IF p9^>p8^ THEN sum==+1 FI
IF p2^>p9^ THEN sum==+1 FI
IF sum=1 THEN
IF step1 THEN
p24=p4 p68=p6
ELSE
p24=p2 p68=p8
FI
IF p2^+p4^+p68^<3 AND p24^+p6^+p8^<3 THEN
change(count)=p1 count==+1
FI
FI
FI
FI
p1==+1 p2==+1 p3==+1 p4==+1 p5==+1
p6==+1 p7==+1 p8==+1 p9==+1
OD
OD
step1=1-step1
FOR i=0 TO count-1
DO
p1=change(i) p1^=0
OD
UNTIL count=0
OD
RETURN
PROC Main()
BYTE ARRAY image1=[
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0
0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
BYTE ARRAY image2=[
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
BYTE width1=[32],height1=[10],width2=[59],height2=[18]
BYTE CH=$02FC
Graphics(7+16)
Color=1
SetColor(0,0,$00)
SetColor(4,0,$04)
SetColor(1,0,$0C)
DrawImage(image1,0,0,width1,height1)
Thinning(image1,width1,height1)
DrawImage(image1,width1+10,0,width1,height1)
DrawImage(image2,0,height1+10,width2,height2)
Thinning(image2,width2,height2)
DrawImage(image2,width2+10,height1+10,width2,height2)
DO UNTIL CH#$FF OD
CH=$FF
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Zhang-Suen_thinning_algorithm.png Screenshot from Atari 8-bit computer]
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">-- Params:
-- List of lists (rows) of "pixel" values.
-- Record indicating the values representing black and white.
on ZhangSuen(matrix, {black:black, white:white})
script o
property matrix : missing value
property changePixels : missing value
on A(neighbours) -- Count transitions from white to black.
set sum to 0
repeat with i from 1 to 8
if ((neighbours's item i is white) and (neighbours's item (i mod 8 + 1) is black)) then set sum to sum + 1
end repeat
return sum
end A
on B(neighbours) -- Count neighbouring black pixels.
set sum to 0
repeat with p in neighbours
if (p's contents is black) then set sum to sum + 1
end repeat
return sum
end B
end script
set o's matrix to matrix
set rowCount to (count o's matrix)
set columnCount to (count o's matrix's beginning) -- Assumed to be the same for every row.
repeat until (o's changePixels is {})
repeat with step from 1 to 2
set o's changePixels to {}
repeat with r from 2 to (rowCount - 1)
repeat with c from 2 to (columnCount - 1)
if (o's matrix's item r's item c is black) then
tell (a reference to o's matrix) to ¬
set neighbours to {item (r - 1)'s item c, item (r - 1)'s item (c + 1), ¬
item r's item (c + 1), item (r + 1)'s item (c + 1), item (r + 1)'s item c, ¬
item (r + 1)'s item (c - 1), item r's item (c - 1), item (r - 1)'s item (c - 1)}
set blackCount to o's B(neighbours)
if ((blackCount > 1) and (blackCount < 7) and (o's A(neighbours) is 1)) then
set {P2, x, P4, x, P6, x, P8} to neighbours
if (step is 1) then
set toChange to ((P4 is white) or (P6 is white) or ((P2 is white) and (P8 is white)))
else
set toChange to ((P2 is white) or (P8 is white) or ((P4 is white) and (P6 is white)))
end if
if (toChange) then set end of o's changePixels to {r, c}
end if
end if
end repeat
end repeat
if (o's changePixels is {}) then exit repeat
repeat with pixel in o's changePixels
set {r, c} to pixel
set o's matrix's item r's item c to white
end repeat
end repeat
end repeat
return o's matrix -- or: return matrix -- The input has been edited in place.
end ZhangSuen
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on demo()
set pattern to "00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
Line 89 ⟶ 478:
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
set matrix to pattern's paragraphs
repeat with thisRow in matrix
set thisRow's contents to thisRow's characters
end repeat
ZhangSuen(matrix, {black:"1", white:"0"})
repeat with thisRow in matrix
set thisRow's contents to join(thisRow, "")
end repeat
return join(matrix, linefeed)
end demo
return demo()</syntaxhighlight>
{{output}}
<pre>"00000000000000000000000000000000
00111111100000000011111100000000
00100000100000000110000000000000
00100000010000000100000000000000
00100000100000000100000000000000
00111110100000000100000000000000
00000001100000000100000000000000
00000000100001000110000110001000
00000000010000000001111000000000
00000000000000000000000000000000"</pre>
Alternative demo:
<syntaxhighlight lang="applescript">on demo()
set pattern to "
################# #############
################## ################
################### ##################
######## ####### ###################
###### ####### ####### ######
###### ####### #######
################# #######
################ #######
################# #######
###### ####### #######
###### ####### #######
###### ####### ####### ######
######## ####### ###################
######## ####### ###### ################## ######
######## ####### ###### ################ ######
######## ####### ###### ############# ######
"
set matrix to pattern's paragraphs
repeat with thisRow in matrix
set thisRow's contents to thisRow's characters
end repeat
ZhangSuen(matrix, {black:"#", white:space})
repeat with thisRow in matrix
set thisRow's contents to join(thisRow, "")
end repeat
return join(matrix, linefeed)
end demo
return demo()</syntaxhighlight>
{{output}}
<pre>
# ########## #######
## # #### #
# # ##
# # #
# # #
# # #
############ #
# # #
# # #
# # #
# # #
# ##
# ############
### ###
</pre>
=={{header|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).
<
FileOut := A_ScriptDir "\NewFile.txt"
Line 177 ⟶ 634:
return 1
return Neighbors
}</
'''Output:'''
<pre>
Line 189 ⟶ 646:
# ####
</pre>
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' version 08-10-2016
' compile with: fbc -s console
Data "00000000000000000000000000000000"
Data "01111111110000000111111110000000"
Data "01110001111000001111001111000000"
Data "01110000111000001110000111000000"
Data "01110001111000001110000000000000"
Data "01111111110000001110000000000000"
Data "01110111100000001110000111000000"
Data "01110011110011101111001111011100"
Data "01110001111011100111111110011100"
Data "00000000000000000000000000000000"
Data "END"
' ------=< MAIN >=------
Dim As UInteger x, y, m, n
Dim As String input_str
Do ' find out how big it is
Read input_str
If input_str = "END" Then Exit Do
If x < Len(input_str) Then x = Len(input_str)
y = y + 1
Loop
m = x -1 : n = y -1
ReDim As UByte old(m, n), new_(m, n)
y = 0
Restore ' restore data pointer
Do ' put data in array
Read input_str
If input_str="END" Then Exit Do
For x = 0 To Len(input_str) -1
old(x,y) = input_str[x] - Asc("0")
' print image
If old(x, y) = 0 Then Print "."; Else Print "#";
Next
Print
y = y + 1
Loop
'corners and sides do not change
For x = 0 To m
new_(x, 0) = old(x, 0)
new_(x, n) = old(x, n)
Next
For y = 0 To n
new_(0, y) = old(0, y)
new_(m, y) = old(m, y)
Next
Dim As UInteger tmp, change, stage = 1
Do
change = 0
For y = 1 To n -1
For x = 1 To m -1
' -1-
If old(x,y) = 0 Then ' first condition, p1 must be black
new_(x,y) = 0
Continue For
End If
' -2-
tmp = old(x, y -1) + old(x +1, y -1)
tmp = tmp + old(x +1, y) + old(x +1, y +1) + old(x, y +1)
tmp = tmp + old(x -1, y +1) + old(x -1, y) + old(x -1, y -1)
If tmp < 2 OrElse tmp > 6 Then ' 2 <= B(p1) <= 6
new_(x, y) = 1
Continue For
End If
' -3-
tmp = 0
If old(x , y ) = 0 And old(x , y -1) = 1 Then tmp += 1 ' p1 > p2
If old(x , y -1) = 0 And old(x +1, y -1) = 1 Then tmp += 1 ' p2 > p3
If old(x +1, y -1) = 0 And old(x +1, y ) = 1 Then tmp += 1 ' p3 > p4
If old(x +1, y ) = 0 And old(x +1, y +1) = 1 Then tmp += 1 ' p4 > p5
If old(x +1, y +1) = 0 And old(x , y +1) = 1 Then tmp += 1 ' p5 > p6
If old(x , y +1) = 0 And old(x -1, y +1) = 1 Then tmp += 1 ' p6 > p7
If old(x -1, y +1) = 0 And old(x -1, y ) = 1 Then tmp += 1 ' p7 > p8
If old(x -1, y ) = 0 And old(x -1, y -1) = 1 Then tmp += 1 ' p8 > p9
If old(x -1, y -1) = 0 And old(x , y -1) = 1 Then tmp += 1 ' p9 > p2
' tmp = 1 ==> A(P1) = 1
If tmp <> 1 Then
new_(x, y) = 1
Continue For
End If
If (stage And 1) = 1 Then
' step 1 -4- -5-
If (old(x, y -1) + old(x +1, y) + old(x, y +1)) = 3 OrElse _
(old(x +1, y) + old(x, y +1) + old(x -1, y)) = 3 Then
new_(x, y) = 1
Continue For
End If
Else
' step 2 -4- -5-
If (old(x, y -1) + old(x +1, y) + old(x -1, y)) = 3 OrElse _
(old(x, y -1) + old(x, y +1) + old(x -1, y)) = 3 Then
new_(x, y) = 1
Continue For
End If
End If
' all condition are met, make p1 white (0)
new_(x, y) = 0
change = 1 ' flag change
Next
Next
' copy new_() into old()
For y = 0 To n
For x = 0 To m
old(x, y) = new_(x, y)
Next
Next
stage += 1
Loop Until change = 0 ' stop when there are no changes made
Print ' print result
Print "End result"
For y = 0 To n
For x = 0 To m
If old(x, y) = 0 Then Print "."; Else Print "#";
Next
Print
Next
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
End result
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................</pre>
==={{header|VBA}}===
{{trans|Phix}}
<syntaxhighlight lang="vb">Public n As Variant
Private Sub init()
n = [{-1,0;-1,1;0,1;1,1;1,0;1,-1;0,-1;-1,-1;-1,0}]
End Sub
Private Function AB(text As Variant, y As Integer, x As Integer, step As Integer) As Variant
Dim wtb As Integer
Dim bn As Integer
Dim prev As String: prev = "#"
Dim next_ As String
Dim p2468 As String
For i = 1 To UBound(n)
next_ = Mid(text(y + n(i, 1)), x + n(i, 2), 1)
wtb = wtb - (prev = "." And next_ <= "#")
bn = bn - (i > 1 And next_ <= "#")
If (i And 1) = 0 Then p2468 = p2468 & prev
prev = next_
Next i
If step = 2 Then '-- make it p6842
p2468 = Mid(p2468, 3, 2) & Mid(p2468, 1, 2)
'p2468 = p2468(3..4)&p2468(1..2)
End If
Dim ret(2) As Variant
ret(0) = wtb
ret(1) = bn
ret(2) = p2468
AB = ret
End Function
Private Sub Zhang_Suen(text As Variant)
Dim wtb As Integer
Dim bn As Integer
Dim changed As Boolean, changes As Boolean
Dim p2468 As String '-- (p6842 for step 2)
Dim x As Integer, y As Integer, step As Integer
Do While True
changed = False
For step = 1 To 2
changes = False
For y = 1 To UBound(text) - 1
For x = 2 To Len(text(y)) - 1
If Mid(text(y), x, 1) = "#" Then
ret = AB(text, y, x, step)
wtb = ret(0)
bn = ret(1)
p2468 = ret(2)
If wtb = 1 _
And bn >= 2 And bn <= 6 _
And InStr(1, Mid(p2468, 1, 3), ".") _
And InStr(1, Mid(p2468, 2, 3), ".") Then
changes = True
text(y) = Left(text(y), x - 1) & "!" & Right(text(y), Len(text(y)) - x)
End If
End If
Next x
Next y
If changes Then
For y = 1 To UBound(text) - 1
text(y) = Replace(text(y), "!", ".")
Next y
changed = True
End If
Next step
If Not changed Then Exit Do
Loop
Debug.Print Join(text, vbCrLf)
End Sub
Public Sub main()
init
Dim Small_rc(9) As String
Small_rc(0) = "................................"
Small_rc(1) = ".#########.......########......."
Small_rc(2) = ".###...####.....####..####......"
Small_rc(3) = ".###....###.....###....###......"
Small_rc(4) = ".###...####.....###............."
Small_rc(5) = ".#########......###............."
Small_rc(6) = ".###.####.......###....###......"
Small_rc(7) = ".###..####..###.####..####.###.."
Small_rc(8) = ".###...####.###..########..###.."
Small_rc(9) = "................................"
Zhang_Suen (Small_rc)
End Sub</syntaxhighlight>{{out}}
<pre>................................
...######.........######........
...#....#.........#....##.......
...#....#.........#......#......
...#....#.........#.............
...####.#.........#.............
.......##.........#.............
........#....#....#....##...#...
.........#....#....####......#..
................................</pre>
=={{header|C}}==
Input and out images written from and to files. Format of input file is :
<pre>
<Rows> <Columns>
<Blank pixel character> <Image Pixel character>
<Image of specified rows and columns made up of the two pixel types specified in the second line.>
</pre>
The images before and after thinning are also printed on the console.
<syntaxhighlight lang="c">
#include<stdlib.h>
#include<stdio.h>
char** imageMatrix;
char blankPixel,imagePixel;
typedef struct{
int row,col;
}pixel;
int getBlackNeighbours(int row,int col){
int i,j,sum = 0;
for(i=-1;i<=1;i++){
for(j=-1;j<=1;j++){
if(i!=0 || j!=0)
sum+= (imageMatrix[row+i][col+j]==imagePixel);
}
}
return sum;
}
int getBWTransitions(int row,int col){
return ((imageMatrix[row-1][col]==blankPixel && imageMatrix[row-1][col+1]==imagePixel)
+(imageMatrix[row-1][col+1]==blankPixel && imageMatrix[row][col+1]==imagePixel)
+(imageMatrix[row][col+1]==blankPixel && imageMatrix[row+1][col+1]==imagePixel)
+(imageMatrix[row+1][col+1]==blankPixel && imageMatrix[row+1][col]==imagePixel)
+(imageMatrix[row+1][col]==blankPixel && imageMatrix[row+1][col-1]==imagePixel)
+(imageMatrix[row+1][col-1]==blankPixel && imageMatrix[row][col-1]==imagePixel)
+(imageMatrix[row][col-1]==blankPixel && imageMatrix[row-1][col-1]==imagePixel)
+(imageMatrix[row-1][col-1]==blankPixel && imageMatrix[row-1][col]==imagePixel));
}
int zhangSuenTest1(int row,int col){
int neighbours = getBlackNeighbours(row,col);
return ((neighbours>=2 && neighbours<=6)
&& (getBWTransitions(row,col)==1)
&& (imageMatrix[row-1][col]==blankPixel||imageMatrix[row][col+1]==blankPixel||imageMatrix[row+1][col]==blankPixel)
&& (imageMatrix[row][col+1]==blankPixel||imageMatrix[row+1][col]==blankPixel||imageMatrix[row][col-1]==blankPixel));
}
int zhangSuenTest2(int row,int col){
int neighbours = getBlackNeighbours(row,col);
return ((neighbours>=2 && neighbours<=6)
&& (getBWTransitions(row,col)==1)
&& (imageMatrix[row-1][col]==blankPixel||imageMatrix[row][col+1]==blankPixel||imageMatrix[row][col-1]==blankPixel)
&& (imageMatrix[row-1][col]==blankPixel||imageMatrix[row+1][col]==blankPixel||imageMatrix[row][col+1]==blankPixel));
}
void zhangSuen(char* inputFile, char* outputFile){
int startRow = 1,startCol = 1,endRow,endCol,i,j,count,rows,cols,processed;
pixel* markers;
FILE* inputP = fopen(inputFile,"r");
fscanf(inputP,"%d%d",&rows,&cols);
fscanf(inputP,"%d%d",&blankPixel,&imagePixel);
blankPixel<=9?blankPixel+='0':blankPixel;
imagePixel<=9?imagePixel+='0':imagePixel;
printf("\nPrinting original image :\n");
imageMatrix = (char**)malloc(rows*sizeof(char*));
for(i=0;i<rows;i++){
imageMatrix[i] = (char*)malloc((cols+1)*sizeof(char));
fscanf(inputP,"%s\n",imageMatrix[i]);
printf("\n%s",imageMatrix[i]);
}
fclose(inputP);
endRow = rows-2;
endCol = cols-2;
do{
markers = (pixel*)malloc((endRow-startRow+1)*(endCol-startCol+1)*sizeof(pixel));
count = 0;
for(i=startRow;i<=endRow;i++){
for(j=startCol;j<=endCol;j++){
if(imageMatrix[i][j]==imagePixel && zhangSuenTest1(i,j)==1){
markers[count].row = i;
markers[count].col = j;
count++;
}
}
}
processed = (count>0);
for(i=0;i<count;i++){
imageMatrix[markers[i].row][markers[i].col] = blankPixel;
}
free(markers);
markers = (pixel*)malloc((endRow-startRow+1)*(endCol-startCol+1)*sizeof(pixel));
count = 0;
for(i=startRow;i<=endRow;i++){
for(j=startCol;j<=endCol;j++){
if(imageMatrix[i][j]==imagePixel && zhangSuenTest2(i,j)==1){
markers[count].row = i;
markers[count].col = j;
count++;
}
}
}
if(processed==0)
processed = (count>0);
for(i=0;i<count;i++){
imageMatrix[markers[i].row][markers[i].col] = blankPixel;
}
free(markers);
}while(processed==1);
FILE* outputP = fopen(outputFile,"w");
printf("\n\n\nPrinting image after applying Zhang Suen Thinning Algorithm : \n\n\n");
for(i=0;i<rows;i++){
for(j=0;j<cols;j++){
printf("%c",imageMatrix[i][j]);
fprintf(outputP,"%c",imageMatrix[i][j]);
}
printf("\n");
fprintf(outputP,"\n");
}
fclose(outputP);
printf("\nImage also written to : %s",outputFile);
}
int main()
{
char inputFile[100],outputFile[100];
printf("Enter full path of input image file : ");
scanf("%s",inputFile);
printf("Enter full path of output image file : ");
scanf("%s",outputFile);
zhangSuen(inputFile,outputFile);
return 0;
}
</syntaxhighlight>
Contents of input file : zhImage.txt
<pre>
10 32
0 1
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
</pre>
Console interaction :
<pre>
Enter full path of input image file : zhImage.txt
Enter full path of output image file : out.txt
Printing original image :
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
Printing image after applying Zhang Suen Thinning Algorithm :
00000000000000000000000000000000
00111111100000000011111100000000
00100000100000000110000000000000
01000000100000000100000000000000
01000000100000001000000000000000
01111110100000001000000000000000
00000001000000000100000000000000
00000000100001000110000110001000
00000000010000000001111000000000
00000000000000000000000000000000
Image also written to : out.txt
</pre>
Contents of out.txt :
<pre>
00000000000000000000000000000000
00111111100000000011111100000000
00100000100000000110000000000000
01000000100000000100000000000000
01000000100000001000000000000000
01111110100000001000000000000000
00000001000000000100000000000000
00000000100001000110000110001000
00000000010000000001111000000000
00000000000000000000000000000000
</pre>
=={{header|C++}}==
Compiled with --std=c++14
<syntaxhighlight lang="cpp">#include <iostream>
#include <string>
#include <sstream>
#include <valarray>
const std::string input {
"................................"
".#########.......########......."
".###...####.....####..####......"
".###....###.....###....###......"
".###...####.....###............."
".#########......###............."
".###.####.......###....###......"
".###..####..###.####..####.###.."
".###...####.###..########..###.."
"................................"
};
const std::string input2 {
".........................................................."
".#################...................#############........"
".##################...............################........"
".###################............##################........"
".########.....#######..........###################........"
"...######.....#######.........#######.......######........"
"...######.....#######........#######......................"
"...#################.........#######......................"
"...################..........#######......................"
"...#################.........#######......................"
"...######.....#######........#######......................"
"...######.....#######........#######......................"
"...######.....#######.........#######.......######........"
".########.....#######..........###################........"
".########.....#######.######....##################.######."
".########.....#######.######......################.######."
".########.....#######.######.........#############.######."
".........................................................."
};
class ZhangSuen;
class Image {
public:
friend class ZhangSuen;
using pixel_t = char;
static const pixel_t BLACK_PIX;
static const pixel_t WHITE_PIX;
Image(unsigned width = 1, unsigned height = 1)
: width_{width}, height_{height}, data_( '\0', width_ * height_)
{}
Image(const Image& i) : width_{ i.width_}, height_{i.height_}, data_{i.data_}
{}
Image(Image&& i) : width_{ i.width_}, height_{i.height_}, data_{std::move(i.data_)}
{}
~Image() = default;
Image& operator=(const Image& i) {
if (this != &i) {
width_ = i.width_;
height_ = i.height_;
data_ = i.data_;
}
return *this;
}
Image& operator=(Image&& i) {
if (this != &i) {
width_ = i.width_;
height_ = i.height_;
data_ = std::move(i.data_);
}
return *this;
}
size_t idx(unsigned x, unsigned y) const noexcept { return y * width_ + x; }
bool operator()(unsigned x, unsigned y) {
return data_[idx(x, y)];
}
friend std::ostream& operator<<(std::ostream& o, const Image& i) {
o << i.width_ << " x " << i.height_ << std::endl;
size_t px = 0;
for(const auto& e : i.data_) {
o << (e?Image::BLACK_PIX:Image::WHITE_PIX);
if (++px % i.width_ == 0)
o << std::endl;
}
return o << std::endl;
}
friend std::istream& operator>>(std::istream& in, Image& img) {
auto it = std::begin(img.data_);
const auto end = std::end(img.data_);
Image::pixel_t tmp;
while(in && it != end) {
in >> tmp;
if (tmp != Image::BLACK_PIX && tmp != Image::WHITE_PIX)
throw "Bad character found in image";
*it = (tmp == Image::BLACK_PIX)?1:0;
++it;
}
return in;
}
unsigned width() const noexcept { return width_; }
unsigned height() const noexcept { return height_; }
struct Neighbours {
// 9 2 3
// 8 1 4
// 7 6 5
Neighbours(const Image& img, unsigned p1_x, unsigned p1_y)
: img_{img}
, p1_{img.idx(p1_x, p1_y)}
, p2_{p1_ - img.width()}
, p3_{p2_ + 1}
, p4_{p1_ + 1}
, p5_{p4_ + img.width()}
, p6_{p5_ - 1}
, p7_{p6_ - 1}
, p8_{p1_ - 1}
, p9_{p2_ - 1}
{}
const Image& img_;
const Image::pixel_t& p1() const noexcept { return img_.data_[p1_]; }
const Image::pixel_t& p2() const noexcept { return img_.data_[p2_]; }
const Image::pixel_t& p3() const noexcept { return img_.data_[p3_]; }
const Image::pixel_t& p4() const noexcept { return img_.data_[p4_]; }
const Image::pixel_t& p5() const noexcept { return img_.data_[p5_]; }
const Image::pixel_t& p6() const noexcept { return img_.data_[p6_]; }
const Image::pixel_t& p7() const noexcept { return img_.data_[p7_]; }
const Image::pixel_t& p8() const noexcept { return img_.data_[p8_]; }
const Image::pixel_t& p9() const noexcept { return img_.data_[p9_]; }
const size_t p1_, p2_, p3_, p4_, p5_, p6_, p7_, p8_, p9_;
};
Neighbours neighbours(unsigned x, unsigned y) const { return Neighbours(*this, x, y); }
private:
unsigned height_ { 0 };
unsigned width_ { 0 };
std::valarray<pixel_t> data_;
};
constexpr const Image::pixel_t Image::BLACK_PIX = '#';
constexpr const Image::pixel_t Image::WHITE_PIX = '.';
class ZhangSuen {
public:
// the number of transitions from white to black, (0 -> 1) in the sequence P2,P3,P4,P5,P6,P7,P8,P9,P2
unsigned transitions_white_black(const Image::Neighbours& a) const {
unsigned sum = 0;
sum += (a.p9() == 0) && a.p2();
sum += (a.p2() == 0) && a.p3();
sum += (a.p3() == 0) && a.p4();
sum += (a.p8() == 0) && a.p9();
sum += (a.p4() == 0) && a.p5();
sum += (a.p7() == 0) && a.p8();
sum += (a.p6() == 0) && a.p7();
sum += (a.p5() == 0) && a.p6();
return sum;
}
// The number of black pixel neighbours of P1. ( = sum(P2 .. P9) )
unsigned black_pixels(const Image::Neighbours& a) const {
unsigned sum = 0;
sum += a.p9();
sum += a.p2();
sum += a.p3();
sum += a.p8();
sum += a.p4();
sum += a.p7();
sum += a.p6();
sum += a.p5();
return sum;
}
const Image& operator()(const Image& img) {
tmp_a_ = img;
size_t changed_pixels = 0;
do {
changed_pixels = 0;
// Step 1
tmp_b_ = tmp_a_;
for(size_t y = 1; y < tmp_a_.height() - 1; ++y) {
for(size_t x = 1; x < tmp_a_.width() - 1; ++x) {
if (tmp_a_.data_[tmp_a_.idx(x, y)]) {
auto n = tmp_a_.neighbours(x, y);
auto bp = black_pixels(n);
if (bp >= 2 && bp <= 6) {
auto tr = transitions_white_black(n);
if ( tr == 1
&& (n.p2() * n.p4() * n.p6() == 0)
&& (n.p4() * n.p6() * n.p8() == 0)
) {
tmp_b_.data_[n.p1_] = 0;
++changed_pixels;
}
}
}
}
}
// Step 2
tmp_a_ = tmp_b_;
for(size_t y = 1; y < tmp_b_.height() - 1; ++y) {
for(size_t x = 1; x < tmp_b_.width() - 1; ++x) {
if (tmp_b_.data_[tmp_b_.idx(x, y)]) {
auto n = tmp_b_.neighbours(x, y);
auto bp = black_pixels(n);
if (bp >= 2 && bp <= 6) {
auto tr = transitions_white_black(n);
if ( tr == 1
&& (n.p2() * n.p4() * n.p8() == 0)
&& (n.p2() * n.p6() * n.p8() == 0)
) {
tmp_a_.data_[n.p1_] = 0;
++changed_pixels;
}
}
}
}
}
} while(changed_pixels > 0);
return tmp_a_;
}
private:
Image tmp_a_;
Image tmp_b_;
};
int main(int argc, char const *argv[])
{
using namespace std;
Image img(32, 10);
istringstream iss{input};
iss >> img;
cout << img;
cout << "ZhangSuen" << endl;
ZhangSuen zs;
Image res = std::move(zs(img));
cout << res << endl;
Image img2(58,18);
istringstream iss2{input2};
iss2 >> img2;
cout << img2;
cout << "ZhangSuen with big image" << endl;
Image res2 = std::move(zs(img2));
cout << res2 << endl;
return 0;
}
</syntaxhighlight>
Output:
<pre>
32 x 10
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
ZhangSuen
32 x 10
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................
58 x 18
..........................................................
.#################...................#############........
.##################...............################........
.###################............##################........
.########.....#######..........###################........
...######.....#######.........#######.......######........
...######.....#######........#######......................
...#################.........#######......................
...################..........#######......................
...#################.........#######......................
...######.....#######........#######......................
...######.....#######........#######......................
...######.....#######.........#######.......######........
.########.....#######..........###################........
.########.....#######.######....##################.######.
.########.....#######.######......################.######.
.########.....#######.######.........#############.######.
..........................................................
ZhangSuen with big image
58 x 18
..........................................................
..........................................................
....#.##########.......................#######............
.....##........#...................####.......#...........
.....#..........#.................##......................
.....#..........#................#........................
.....#..........#................#........................
.....#..........#................#........................
.....############...............#.........................
.....#..........#...............#.........................
.....#..........#................#........................
.....#..........#................#........................
.....#..........#................#........................
.....#............................##......................
.....#.............................############...........
.......................###..........................###...
..........................................................
..........................................................
</pre>
=={{header|D}}==
This uses the module from the Bitmap Task. And it performs no heap allocations.
<
std.typecons, std.typetuple, bitmap;
Line 319 ⟶ 1,585:
writeln;
}
}</
{{out}}
<pre>From:
Line 418 ⟶ 1,684:
=={{header|Elena}}==
ELENA
{{trans|Java}}
<
import system'routines
import extensions
import extensions'routines
const string[] image = new string[]{
" ",
" ################# ############# ",
Line 445 ⟶ 1,709:
" ######## ####### ###### ################ ###### ",
" ######## ####### ###### ############# ###### ",
" "
static int[][] nbrs = new int[][]
{
new int[]{0, -1}, new int[]{1, -1}, new int[]{1, 0}, new int[]{1, 1}, new int[]{0, 1},
new int[]{-1, 1}, new int[]{-1, 0}, new int[]{-1, -1}, new int[]{0, -1}
};
static int[][][] nbrGroups = new int[][][]
{
new int[][]{new int[]{0, 2, 4}, new int[]{2, 4, 6}},
new int[][]{new int[]{0, 2, 6}, new int[]{0, 4, 6}}
};
{
if (self[r][c] != $35)
int nn := self
if ((nn < 2) || (nn > 6))
if(self
ifnot (self
toWhite.append(new
^ true
numNeighbors
int count := 0
if (self[r + nbrs[i][1]][c + nbrs[i + 1][0]] == $35)
^ count
numTransitions
int count := 0
if (self[r + nbrs[i][1]][c + nbrs[i][0]] == $32)
if (self[r + nbrs[i + 1][1]][c + nbrs[i + 1][0]] == $35)
count := count + 1
^ count
atLeastOneIsWhite
int count := 0
var group := nbrGroups[step]
for(int j := 0; j <
var nbr := nbrs[group[i][j]]
if (self[r + nbr[1]][c + nbr[0]] == $32)
};
}
{
bool firstStep := false;
bool hasChanged := true;
while (hasChanged || firstStep)
hasChanged := false
firstStep := firstStep
for(int r := 1; r < self.Rows - 1; r += 1)
{
for(int c := 1; c < self.Columns - 1; c += 1)
{
if(self.proceed(r,c,toWhite,firstStep))
{ hasChanged := true }
}
};
toWhite.forEach::(p){ self[p.y][p.x] := $32 };
toWhite.clear()
}
}
print()
{
var it := self.enumerator();
it.forEach::(ch){ console.print(ch," ") };
while (it.next())
{
console.writeLine();
}
}
public program()
{
{
= image[i][j]
}
grid
grid
console
}</syntaxhighlight>
{{out}}
<pre>
# #
# # # #
# # #
# # #
# #
# # # # # # # #
# # #
# # #
# # #
# # #
# # # # # #
Line 607 ⟶ 1,875:
=={{header|Elixir}}==
{{trans|Ruby}}
<
@neighbours [{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}] # 8 neighbours
Line 696 ⟶ 1,964:
00000000000000000000000000000000
"""
ZhangSuen.thinning(str, ?1)</
{{out}}
Line 757 ⟶ 2,025:
</pre>
=={{header|Fortran}}==
With F90 came standardisation of a variety of array manipulation facilities. Since the image array is to be inspected as a whole then adjusted rather than adjusted step-by-step as it is inspected, the first thought was to employ the special facility of the FOR ALL statement, which is that in an expression such as <
So, that suggests something like <
WHERE(DOT(I,J) .NE. 0) DOT(I,J) = ADJUST(DOT,I,J)</
This requires function ADJUST to be a "pure" function, and they are not supposed to perpetrate side effects, such as one reporting that any adjustment was made. Nor is it clear that array DOT must be presented as a parameter either as the entire array or as element DOT(i,j), or if not, that it can be global to function ADJUST - which would also be an impurity - and for that matter, variables I and J could be global also...
Instead, thought turned to more closely following the task specification, which involves producing a list of elements to be adjusted after an inspection pass. Given that array DOT is two-dimensional, it would be nice if an element could be indexed via an expression such as <code>DOT(INDEX)</code> where INDEX was an array of two elements with INDEX(1) = i, and INDEX(2) = j, so as to access DOT(i,j) If this were possible, then obviously one could hope that array INDEX could be extended so as to store the multiple elements of a list of such locations to access, with a view to <code>DOT(INDEX(1:n)) = 0</code> adjusting the image.
Alas, such a syntax form is not accommodated. However, F90 also introduced the ability to define and use compound data types, such as the type PLACE as used below. It is not possible to define a type of a special, recognised form, such as say "SUBSCRIPT LIST" that can be used as dreamt of above, so the components are just ordinary variables. Two ordinary arrays could be used, one for each of the two subscripts, or a compound type could be devised in a hint towards self-documentation. Thus, <
But it doesn't work... After a fair amount of head scratching, not at all assisted by the woolly generalities and inane examples of the compiler's "help" collection, it became apparent that the expression did not work through a list of indices as anticipated, but instead, for ''each'' value of the first index, ''all'' the values of the second index were selected. Thus, instead of the first change being DOT(WHACK('''1''').I,WHACK('''1''').J) only, it was DOT(WHACK('''1''').I,WHACK('''1:WHACKCOUNT''').J) that were being cleared. Accordingly, the fancy syntax has to be abandoned in favour of a specific DO-loop.
<
CONTAINS
SUBROUTINE ZST(DOT) !Attempts to thin out thick lines.
Line 1,035 ⟶ 2,144:
CALL SHOW(IMAGE)
END PROGRAM POKE </
Output:
Line 1,065 ⟶ 2,174:
=={{header|Go}}==
<
import (
Line 1,253 ⟶ 2,362:
}
}
}</
{{out}}
<pre>
Line 1,269 ⟶ 2,378:
=={{header|Groovy}}==
<
def image = text.split('\n').collect { line -> line.collect { it == '#' ? 1 : 0} }
def p2, p3, p4, p5, p6, p7, p8, p9
Line 1,293 ⟶ 2,402:
while (reduce(step1) | reduce(step2));
image.collect { line -> line.collect { it ? '#' : '.' }.join('') }.join('\n')
}</
Testing:
<
................................
.#########.......########.......
Line 1,333 ⟶ 2,442:
println zhangSuen(it)
println()
}</
Output:
<pre>From:
Line 1,398 ⟶ 2,507:
=={{header|Haskell}}==
<
import qualified Data.List as List
Line 1,519 ⟶ 2,628:
main :: IO ()
main = mapM_ (putStrLn . showBWArray . thin . toBWArray) [sampleExA, sampleExB]</
{{out}}
<pre> ####### ######
Line 1,550 ⟶ 2,659:
=={{header|J}}==
'''Solution:'''
<
toImage=: [: , LF ,.~ '01' {~ ] NB. convert to original representation
frameImg=: 0 ,. 0 , >:@$ {. ] NB. adds border of 0's to image
neighbrs=:
Bdry=: 1 2 5 8 7 6 3 0 1 NB. map pixel index to neighbour order
Line 1,576 ⟶ 2,683:
step2=: whiten frameImg@(cond2 neighbrs)
zhangSuen=: [: toImage [: step2@step1^:_ isBlackPx</
'''Alternative, explicit representation of last verb above'''
<
img=. isBlackPx y
whilst. 0 < +/ , msk1 +.&-. msk2 do.
Line 1,587 ⟶ 2,694:
end.
toImage img
)</
'''Example Use:'''
<
ExampleImg=: noun define
Line 1,614 ⟶ 2,721:
# # ## ## #
# ####
</
=={{header|Java}}==
{{works with|Java|7}}
<
import java.util.*;
Line 1,734 ⟶ 2,841:
System.out.println(row);
}
}</
Output:
Line 1,756 ⟶ 2,863:
=={{header|JavaScript}}==
{{trans|Java}}
<
this.x = x;
this.y = y;
Line 1,861 ⟶ 2,968:
return ZhangSuen;
}());
ZhangSuen.main(null);</
Output:
Line 1,880 ⟶ 2,987:
# ############
### ### </pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">
const pixelstring =
"00000000000000000000000000000000" *
"01111111110000000111111110000000" *
"01110001111000001111001111000000" *
"01110000111000001110000111000000" *
"01110001111000001110000000000000" *
"01111111110000001110000000000000" *
"01110111100000001110000111000000" *
"01110011110011101111001111011100" *
"01110001111011100111111110011100" *
"00000000000000000000000000000000"
const pixels = reshape([UInt8(c- 48) for c in pixelstring], (32,10))'
function surroundtesting(px, i, j, step)
if px[i,j] == 0
return false
end
isize, jsize = size(px)
if i < 1 || j < 1 || i == isize || j == jsize # criteria 0.both
return false
end
s = Array{Int,1}(9)
s[1] = s[9] = px[i-1,j]; s[2] = px[i-1,j+1]; s[3] = px[i,j+1]; s[4] = px[i+1,j+1]
s[5] = px[i+1,j]; s[6] = px[i+1,j-1]; s[7] = px[i,j-1]; s[8] = px[i-1,j-1]
b = sum(s[1:8])
if b < 2 || b > 6 # criteria 1.both
return false
end
if sum([(s[i] == 0 && s[i+1] == 1) for i in 1:length(s)-1]) != 1 # criteria 2.both
return false
end
if step == 1
rightwhite = s[1] == 0 || s[3] == 0 || s[5] == 0 # 1.3
downwhite = s[3] == 0 || s[5] == 0 || s[7] == 0 # 1.4
return rightwhite && downwhite
end
upwhite = s[1] == 0 || s[3] == 0 || s[7] == 0 # 2.3
leftwhite = s[1] == 0 || s[5] == 0 || s[7] == 0 # 2.4
return upwhite && leftwhite
end
function zsthinning(mat)
retmat = copy(mat)
testmat = zeros(Int, size(mat))
isize, jsize = size(testmat)
needredo = true
loops = 0
while(needredo)
loops += 1
println("loop number $loops")
needredo = false
for n in 1:2
for i in 1:isize, j in 1:jsize
testmat[i,j] = surroundtesting(retmat, i, j, n) ? 1 : 0
end
for i in 1:isize, j in 1:jsize
if testmat[i,j] == 1
retmat[i,j] = 0
needredo = true
end
end
end
end
retmat
end
function asciiprint(mat)
for i in 1:size(mat)[1]
println(join(map(i -> i == 1 ? '#' : ' ', mat[i,:])))
end
end
asciiprint(zsthinning(pixels))</syntaxhighlight>
{{output}}<pre>
loop number 1
loop number 2
loop number 3
####### ######
# # ##
# # #
# # #
##### # #
## #
# # ## ## #
# ####
</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<
class Point(val x: Int, val y: Int)
Line 1,982 ⟶ 3,183:
fun main(args: Array<String>) {
thinImage()
}</
{{out}}
Line 2,005 ⟶ 3,206:
=={{header|Lua}}==
<
local dirs={
{ 0,-1},
Line 2,145 ⟶ 3,346:
zhangSuenThin(image)
</syntaxhighlight>
Output:
Line 2,161 ⟶ 3,362:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Mathematica supports directly the Thinning methods "Morphological" and "MedialAxis".
The Zhang-Suen algorithm implementation could be done with:
<
nA[mat_] := Module[{l},
Line 2,202 ⟶ 3,402:
FixedPoint[iter, dat]</
Which results in:
Line 2,345 ⟶ 3,545:
...........................................................</pre>
=={{header|
<syntaxhighlight lang="nim">import math, sequtils, strutils
type
BitMatrix = seq[seq[Bit]] # Two-dimensional array of 0/1.
Neighbors = array[2..9, Bit] # Neighbor values.
const Symbols = [Bit(0): '.', Bit(1): '#']
func toBitMatrix(s: openArray[string]): BitMatrix =
## Convert an array of 01 strings into a BitMatrix.
for row in s:
assert row.allCharsInSet({'0', '1'})
result.add row.mapIt(Bit(ord(it) - ord('0')))
proc `$`(m: BitMatrix): string =
## Return the string representation of a BitMatrix.
for row in m:
echo row.mapIt(Symbols[it]).join()
# Templates to allow using double indexing.
template `[]`(m: BitMatrix; i, j: Natural): Bit = m[i][j]
template `[]=`(m: var BitMatrix; i, j: Natural; val: Bit) = m[i][j] = val
func neighbors(m: BitMatrix; i, j: int): Neighbors =
## Return the array of neighbors.
[m[i-1, j], m[i-1, j+1], m[i, j+1], m[i+1, j+1],
m[i+1, j], m[i+1, j-1], m[i, j-1], m[i-1, j-1]]
func transitions(p: Neighbors): int =
## Return the numbers of transitions from P2 to P9.
for (i, j) in [(2, 3), (3, 4), (4, 5), (5, 6),
(6, 7), (7, 8), (8, 9), (9, 2)]:
result += ord(p[i] == 0 and p[j] == 1)
func thinned(m: BitMatrix): BitMatrix =
## Return a thinned version of "m".
const Pair1 = [2, 8]
const Pair2 = [4, 6]
let rowMax = m.high
let colMax = m[0].high
result = m
while true:
var changed = false
for step in 1..2:
let (p1, p2) = if step == 1: (Pair1, Pair2) else: (Pair2, Pair1)
var m = result
for i in 1..<rowMax:
for j in 1..<colMax:
# Check criteria.
if m[i, j] == 0: # criterion 0.
continue
let p = m.neighbors(i, j)
if sum(p) notin 2..6: # criterion 1.
continue
if transitions(p) != 1: # criterion 2.
continue
if p[p1[0]] + p[p2[0]] + p[p2[1]] == 3 or # criterion 3.
p[p1[1]] + p[p2[0]] + p[p2[1]] == 3: # criterion 4.
continue
# All criteria satisfied. Store a 0 in "result".
result[i, j] = 0
changed = true
if not changed: break
when isMainModule:
const Input = ["00000000000000000000000000000000",
"01111111110000000111111110000000",
"01110001111000001111001111000000",
"01110000111000001110000111000000",
"01110001111000001110000000000000",
"01111111110000001110000000000000",
"01110111100000001110000111000000",
"01110011110011101111001111011100",
"01110001111011100111111110011100",
"00000000000000000000000000000000"]
let input = Input.toBitMatrix()
let output = input.thinned()
echo "Input image:"
echo input
echo()
echo "Output image:"
echo output</syntaxhighlight>
{{out}}
<pre>Input image:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
Output image:
................................
..#######.........######........
Line 2,405 ⟶ 3,667:
................................</pre>
=={{header|
{{trans|Raku}}
<syntaxhighlight lang="perl">use v5.36.0;
no warnings 'uninitialized';
use List::Util qw(sum min);
$source = <<'END';
............................................................
..#################...................#############.........
..##################...............################.........
..###################............##################.........
..########.....#######..........###################.........
....######.....#######.........#######.......######.........
....######.....#######........#######.......................
....#################.........#######.......................
....################..........#######.......................
....#################.........#######.......................
....######.....#######........#######.......................
....######.....#######........#######.......................
....######.....#######.........#######.......######.........
..########.....#######..........###################.........
..########.....#######.######....##################.######..
..########.....#######.######......################.######..
..########.....#######.######.........#############.######..
............................................................
END
for $line (split "\n", $source) {
push @lines, [map { 1 & ord $_ } split '', $line]
}
$v = @lines;
$h = @{$lines[0]};
push @black, @$_ for @lines;
@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
@cand = grep { $black[$_] } map { my $x = $_; map $_*$h + $x, 1..$v-2 } 1..$h-2;
do {
sub seewhite ($w1,$w2) {
my @results;
sub cycles (@neighbors) { my $c; $c += $neighbors[$_] < $neighbors[($_+1)%8] for 0..$#neighbors; $c }
sub blacks (@neighbors) { sum @neighbors }
@prior = @cand; @cand = ();
for $p (@prior) {
@n = @black[map { $_+$p } @p8];
if (cycles(@n) == 1 and 2 <= sum(blacks(@n)) and sum(blacks(@n)) <= 6 and min(@n[@$w1]) == 0 and min(@n[@$w2]) == 0) {
push @results, $p;
} else {
push @cand, $p
}
}
@results
}
@goners1 = seewhite [0,2,4], [2,4,6]; @black[@goners1] = 0 x @goners1;
@goners2 = seewhite [0,2,6], [0,4,6]; @black[@goners2] = 0 x @goners2;
} while @goners1 or @goners2;
while (@black) { push @thinned, join '', qw<. #>[splice(@black,0,$h)] }
say join "\n", @thinned;</syntaxhighlight>
{{out}}
<pre>............................................................
............................................................
.....#.##########.......................#######.............
......##........#...................####.......#............
......#..........#.................##.......................
......#..........#................#.........................
......#..........#................#.........................
......#..........#................#.........................
......############...............#..........................
......#..........#...............#..........................
......#..........#................#.........................
......#..........#................#.........................
......#..........#................#.........................
......#............................##.......................
......#.............................############............
........................###..........................###....
............................................................
............................................................</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}};</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">AB</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wtb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'#'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">p2468</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]]</span>
<span style="color: #000000;">wtb</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bn</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">p2468</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- make it p6842</span>
<span style="color: #000000;">p2468</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2468</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">..</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">wtb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Zhang_Suen</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wtb</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">changed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">changes</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">p2468</span> <span style="color: #000080;font-style:italic;">-- (p6842 for step 2)</span>
<span style="color: #000000;">text</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">changed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">changes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'#'</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">wtb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">AB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">wtb</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">bn</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #000000;">bn</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">6</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">3</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2468</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..</span><span style="color: #000000;">4</span><span style="color: #0000FF;">])</span><span style="color: #008080;">then</span>
<span style="color: #000000;">changes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'!'</span> <span style="color: #000080;font-style:italic;">-- (logically still black)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">changes</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"!"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"."</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">changed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">changed</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">small_rc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................"""</span>
<span style="color: #000000;">Zhang_Suen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">small_rc</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,486 ⟶ 3,836:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">zhang: procedure options (main); /* 8 July 2014 */
declare pic(10) bit(32) initial (
Line 2,608 ⟶ 3,958:
end B;
end zhang;</
<pre>
[Initial configuration:]
Line 2,699 ⟶ 4,049:
=={{header|Python}}==
Several input images are converted.
<
# Example from [http://nayefreza.wordpress.com/2013/05/11/zhang-suen-thinning-algorithm-java-implementation/ this blog post].
Line 2,816 ⟶ 4,166:
print('\nFrom:\n%s' % toTxt(image))
after = zhangSuen(image)
print('\nTo thinned:\n%s' % toTxt(after))</
{{out}}
Line 2,846 ⟶ 4,196:
=={{header|Racket}}==
<
(define (img-01string->vector str)
(define lines (regexp-split "\n" str))
Line 2,959 ⟶ 4,309:
; (read-display-thin-display-image e.g.-image/2)
; (newline)
(read-display-thin-display-image e.g.-image))</
{{out}}
Line 2,975 ⟶ 4,325:
................................
Thinned image:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................</pre>
=={{header|Raku}}==
(formerly Perl 6)
Source image may be based on any characters whose low bits are 0 or 1 (which conveniently includes . and #).
<syntaxhighlight lang="raku" line>my $source = qq:to/EOD/;
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
EOD
my @lines = ([.ords X+& 1] for $source.split("\n")); # The low bits Just Work.
my \v = +@lines;
my \h = +@lines[0];
my @black = flat @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;
@goners2 = seewhite (0,2,6), (0,4,6);
@black[@goners2] = 0 xx *;
say "Pong: {[+] @black} remaining after removing ", @goners2;
}
say @black.splice(0,h).join.trans('01' => '.#') while @black;</syntaxhighlight>
{{out}}
<pre>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
................................
..#######.........######........
Line 2,987 ⟶ 4,409:
=={{header|REXX}}==
<
parse arg iFID .; if iFID=='' then iFID='ZHANG_SUEN.DAT'
white=' '; @.=white /* [↓] read the input character grid. */
Line 3,027 ⟶ 4,449:
Ps: rm=r-1; rp=r+1; cm=c-1; cp=c+1 /*calculate some 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:
<pre>
Line 3,101 ⟶ 4,523:
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.
<
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
Line 3,168 ⟶ 4,590:
EOS
ZhangSuen.new(task_example, "1")</
{{out}}
Line 3,186 ⟶ 4,608:
=={{header|Sidef}}==
{{trans|Ruby}}
<
const NEIGHBOURS = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] # 8 neighbors
const CIRCULARS = (NEIGHBOURS + [NEIGHBOURS.first]) # P2, ... P9, P2
Line 3,242 ⟶ 4,664:
EOS
ZhangSuen.new(text, black: "1").display</
{{out}}
<pre>
Line 3,256 ⟶ 4,678:
</pre>
=={{header|Swift}}==
{{trans|Python}}
<syntaxhighlight lang="swift">import UIKit
// testing examples
let beforeTxt = """
1100111
1100111
1100111
1100111
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1100110
1111110
0000000
"""
let smallrc01 = """
00000000000000000000000000000000
01111111110000000111111110000000
01110001111000001111001111000000
01110000111000001110000111000000
01110001111000001110000000000000
01111111110000001110000000000000
01110111100000001110000111000000
01110011110011101111001111011100
01110001111011100111111110011100
00000000000000000000000000000000
"""
let rc01 = """
00000000000000000000000000000000000000000000000000000000000
01111111111111111100000000000000000001111111111111000000000
01111111111111111110000000000000001111111111111111000000000
01111111111111111111000000000000111111111111111111000000000
01111111100000111111100000000001111111111111111111000000000
00011111100000111111100000000011111110000000111111000000000
00011111100000111111100000000111111100000000000000000000000
00011111111111111111000000000111111100000000000000000000000
00011111111111111110000000000111111100000000000000000000000
00011111111111111111000000000111111100000000000000000000000
00011111100000111111100000000111111100000000000000000000000
00011111100000111111100000000111111100000000000000000000000
00011111100000111111100000000011111110000000111111000000000
01111111100000111111100000000001111111111111111111000000000
01111111100000111111101111110000111111111111111111011111100
01111111100000111111101111110000001111111111111111011111100
01111111100000111111101111110000000001111111111111011111100
00000000000000000000000000000000000000000000000000000000000
"""
// Zhang-Suen thinning algorithm in Swift
/// function to thin the image
func zhangSuen(image: inout [[Int]]) -> [[Int]] {
// array of x, y position where need to changed to be white
var changing1, changing2: [(Int, Int)]
repeat {
// set to empty array
changing1 = []
changing2 = []
// Step 1
// loop through row of image
for y in 1..<image.count-1 {
// loop through column of image
for x in 1..<image[0].count-1 {
// get neighbours of P1
var nb = neighbours(x: x, y: y, image: image)
// set P2, P4, P6, P8 from neighbours
let P2 = nb[0], P4 = nb[2], P6 = nb[4], P8 = nb[6]
// reference: https://www.hackingwithswift.com/example-code/language/how-to-sum-an-array-of-numbers-using-reduce
// reference: https://www.hackingwithswift.com/articles/90/how-to-check-whether-a-value-is-inside-a-range
if (image[y][x] == 1 && // Condision 0
(2...6).contains(nb.reduce(0, +)) && // Condision 1
transitions(neighbours: &nb) == 1 && // Condision 2
P2 * P4 * P6 == 0 && // Condision 3
P4 * P6 * P8 == 0 // Condision 4
) {
// add to step1 changing1 list
changing1.append((x,y))
}
}
}
// loop through step1 changing1 list and change to white
for (x, y) in changing1 {
image[y][x] = 0
}
// Step 2
// loop through row of image
for y in 1..<image.count-1 {
// loop through column of image
for x in 1..<image[0].count-1 {
// get neighbours of P1
var nb = neighbours(x: x, y: y, image: image)
// set P2, P4, P6, P8 from neighbours
let P2 = nb[0], P4 = nb[2], P6 = nb[4], P8 = nb[6]
if (image[y][x] == 1 && // Condision 0
(2...6).contains(nb.reduce(0, +)) && // Condision 1
transitions(neighbours: &nb) == 1 && // Condision 2
P2 * P4 * P8 == 0 && // Condision 3
P2 * P6 * P8 == 0 // Condision 4
) {
// add to step2 changing2 list
changing2.append((x,y))
}
}
}
// loop through step2 changing2 list and change to white
for (x, y) in changing2 {
image[y][x] = 0
}
// finish loop when there's no more place to change to white, when changing1, changing2 are empty
} while !changing1.isEmpty && !changing2.isEmpty
// return updated image
return image
}
/// function to convert multiline string of 1/0 into 2D Int array
func intarray(binstring: String) -> [[Int]] {
// reference: https://stackoverflow.com/questions/28611336/how-to-convert-a-string-numeric-in-a-int-array-in-swift
// map through each char of input String to convert to Int
return binstring.split(separator: "\n").map {$0.compactMap{$0.wholeNumberValue}}
}
/// function to convert 2D Int array of 1/0 into multiline String of ‘#’ and ‘.’
func toTxt(intmatrix: [[Int]]) -> String {
// map through each array of parent array and
// map through element of child array and convert to '#' when 1 and to '.' when 0
return intmatrix.map {$0.map { $0 == 1 ? "#" : "."}.joined(separator: "")}.joined(separator: "\n")
}
/// function to get neighbours of P1 = [P2,P3,P4,P5,P6,P7,P8,P9]
func neighbours(x: Int, y: Int, image: [[Int]]) -> [Int] {
let i = image
// set x, y positions of P1 neighbours
let x1 = x+1, y1 = y-1, x_1 = x-1, y_1 = y+1
// return neighbours of P1
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
}
/// function to get the number of transitions from white to black, (0 -> 1) in the sequence P2,P3,P4,P5,P6,P7,P8,P9,P2.
func transitions(neighbours: inout [Int]) -> Int {
// add P2 at the end of neighbours array
let n = neighbours + [neighbours[0]]
var result = 0
// reference: https://www.marcosantadev.com/arrayslice-in-swift/
// compare between each element of neightbour and next element of the element to check if the transition is 0 -> 1
for (n1, n2) in zip(n, n.suffix(n.count - 1)) {
// if the pattern matches, increament result to 1
if (n1, n2) == (0, 1) { result += 1 }
}
// return number of transitions from 0 to 1
return result
}
// run testing
// array of test examples
let testCases: [String] = [beforeTxt, smallrc01, rc01]
for picture in testCases {
// convert string to 2D Int array
var image = intarray(binstring: picture)
// print the result
print("\nFrom:\n\(toTxt(intmatrix: image))")
// run through Zhang-Suen thinning algorithm
let after = zhangSuen(image: &image)
// print the result
print("\nTo thinned:\n\(toTxt(intmatrix: after))")
}</syntaxhighlight>
{{out}}
<pre>
From:
##..###
##..###
##..###
##..###
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
##..##.
######.
.......
To thinned:
##..###
#.....#
#.....#
#...###
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#...#..
#####..
.......
From:
................................
.#########.......########.......
.###...####.....####..####......
.###....###.....###....###......
.###...####.....###.............
.#########......###.............
.###.####.......###....###......
.###..####..###.####..####.###..
.###...####.###..########..###..
................................
To thinned:
................................
..#######.........######........
..#.....#........##.............
..#......#.......#..............
..#.....#........#..............
..#####.#........#..............
.......##........#..............
........#....#...##....##...#...
.........#.........####.........
................................
From:
...........................................................
.#################...................#############.........
.##################...............################.........
.###################............##################.........
.########.....#######..........###################.........
...######.....#######.........#######.......######.........
...######.....#######........#######.......................
...#################.........#######.......................
...################..........#######.......................
...#################.........#######.......................
...######.....#######........#######.......................
...######.....#######........#######.......................
...######.....#######.........#######.......######.........
.########.....#######..........###################.........
.########.....#######.######....##################.######..
.########.....#######.######......################.######..
.########.....#######.######.........#############.######..
...........................................................
To thinned:
...........................................................
...........................................................
....#.##########.......................#######.............
.....##........#...................####.......#............
.....#..........#.................##.......................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....############...............#..........................
.....#..........#...............#..........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#..........#................#.........................
.....#............................##.......................
.....#.............................############............
.......................###..........................###....
...........................................................
...........................................................
</pre>
=={{header|Tcl}}==
Only the single image is converted.
<
set data {
Line 3,336 ⟶ 5,034:
return $data
}
puts [string map {1 @ 0 .} [join [zhang-suen $data] \n]]</
{{out}}
Line 3,350 ⟶ 5,048:
.........@.........@@@@.........
................................
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">class Point {
construct new(x, y) {
_x = x
_y = y
}
x { _x }
y { _y }
}
var image = [
" ",
" ################# ############# ",
" ################## ################ ",
" ################### ################## ",
" ######## ####### ################### ",
" ###### ####### ####### ###### ",
" ###### ####### ####### ",
" ################# ####### ",
" ################ ####### ",
" ################# ####### ",
" ###### ####### ####### ",
" ###### ####### ####### ",
" ###### ####### ####### ###### ",
" ######## ####### ################### ",
" ######## ####### ###### ################## ###### ",
" ######## ####### ###### ################ ###### ",
" ######## ####### ###### ############# ###### ",
" "
]
var nbrs = [
[ 0, -1], [ 1, -1], [ 1, 0],
[ 1, 1], [ 0, 1], [-1, 1],
[-1, 0], [-1, -1], [ 0, -1]
]
var nbrGroups = [
[ [0, 2, 4], [2, 4, 6] ],
[ [0, 2, 6], [0, 4, 6] ]
]
var toWhite = []
var grid = List.filled(image.count, null)
for (i in 0...grid.count) grid[i] = image[i].toList
var numNeighbors = Fn.new { |r, c|
var count = 0
for (i in 0...nbrs.count - 1) {
if (grid[r + nbrs[i][1]][c + nbrs[i][0]] == "#") count = count + 1
}
return count
}
var numTransitions = Fn.new { |r, c|
var count = 0
for (i in 0...nbrs.count - 1) {
if (grid[r + nbrs[i][1]][c + nbrs[i][0]] == " ") {
if (grid[r + nbrs[i + 1][1]][c + nbrs[i + 1][0]] == "#") count = count + 1
}
}
return count
}
var atLeastOneIsWhite = Fn.new { |r, c, step|
var count = 0
var group = nbrGroups[step]
for (i in 0..1) {
for (j in 0...group[i].count) {
var nbr = nbrs[group[i][j]]
if (grid[r + nbr[1]][c + nbr[0]] == " ") {
count = count + 1
break
}
}
}
return count > 1
}
var thinImage = Fn.new {
var firstStep = false
var hasChanged
while (true) {
hasChanged = false
firstStep = !firstStep
for (r in 1...grid.count - 1) {
for (c in 1...grid[0].count - 1) {
if (grid[r][c] == "#") {
var nn = numNeighbors.call(r, c)
if ((2..6).contains(nn)) {
if (numTransitions.call(r, c) == 1) {
var step = firstStep ? 0 : 1
if (atLeastOneIsWhite.call(r, c, step)) {
toWhite.add(Point.new(c, r))
hasChanged = true
}
}
}
}
}
}
for (p in toWhite) grid[p.y][p.x] = " "
toWhite.clear()
if (!firstStep && !hasChanged) break
}
for (row in grid) System.print(row.join())
}
thinImage.call()</syntaxhighlight>
{{out}}
<pre>
# ########## #######
## # #### #
# # ##
# # #
# # #
# # #
############ #
# # #
# # #
# # #
# # #
# ##
# ############
### ###
</pre>
|