Zhang-Suen thinning algorithm: Difference between revisions
(+ D entry) |
(D entry: zhangSuen is pure) |
||
| Line 143: | Line 143: | ||
/// Zhang-Suen thinning algorithm. |
/// Zhang-Suen thinning algorithm. |
||
Image zhangSuen(Image image1) |
Image zhangSuen(Image image1) pure /*nothrow*/ |
||
in { |
in { |
||
foreach (const row; image1) { |
foreach (const row; image1) { |
||
Revision as of 23:27, 13 October 2013
This is an algorithm used to thin a black and white i.e. one bit per pixel images.
For example, with an input image of:
################# #############
################## ################
################### ##################
######## ####### ###################
###### ####### ####### ######
###### ####### #######
################# #######
################ #######
################# #######
###### ####### #######
###### ####### #######
###### ####### ####### ######
######## ####### ###################
######## ####### ###### ################## ######
######## ####### ###### ################ ######
######## ####### ###### ############# ######
It produces the thinned output:
########
## # ############
# # ##
# # #
# # #
# # #
############ #
# # #
# # #
# # #
# # #
# # ##
# #### #
# ### ####### ###
- Algorithm
Assume black pixels are one and white pixels zero, and that the input image is a rectangular N by M array of ones and zeroes.
The algorithm operates on all black pixels P1 that can have eight neighbours. The neighbours are, in order, arranged as:
| P9 | P2 | P3 |
| P8 | P1 | P4 |
| P7 | P6 | P5 |
Obviously the boundary pixels of the image cannot have the full eight neighbours.
- Define = 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 = 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) 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) A(P1) = 1
- (3) At least one of P2 and P4 and P8 is white
- (4) At least one of P2 and P6 and P8 is white
After iterating over the image and collecting all the pixels satisfying all step 2 conditions, all these condition satisfying pixels are again set to white.
- Iteration
If any pixels were set in this round of either step 1 or step 2 then all steps are repeated until no image pixels are so changed.
- Task
- Write a routine to perform Zhang-Suen thinning on an image matrix of ones and zeroes.
- Use the routine to thin the following image and show the output here on this page as either a matrix of ones and zeroes, an image, or an ASCII-art image of space/non-space characters.
00000000000000000000000000000000 01111111110000000111111110000000 01110001111000001111001111000000 01110000111000001110000111000000 01110001111000001110000000000000 01111111110000001110000000000000 01110111100000001110000111000000 01110011110011101111001111011100 01110001111011100111111110011100 00000000000000000000000000000000
- Reference
- Zhang-Suen Thinning Algorithm, Java Implementation by Nayef Reza.
- "Character Recognition Systems: A Guide for Students and Practitioners" By Mohamed Cheriet, Nawwaf Kharma, Cheng-Lin Liu, Ching Suen
D
<lang d>import std.stdio, std.algorithm, std.string, std.array, std.range,
std.functional;
alias sum = curry!(reduce!q{a + b}, 0); //*
alias ImageElement = ubyte; alias Image = ImageElement[][]; // Rectangular. alias Neighbours = ImageElement[9];
/// Convert a 2D array of chars to an Image. Image toImage(in string txt, in char one='#', in char zero='.') pure /*nothrow*/ out(result) {
foreach (const row; result) {
assert(row.length == result[0].length); // Is rectangular.
assert(row.all!(x => x == 0 || x == 1));
}
} body {
return txt
.strip // Throws.
.split
.map!(row => row
.filter!(c => c == one || c == zero)
.map!(c => cast(ImageElement)(c == one))
.array)
.array;
}
/// Convert an Image of 0/1 ints into a string. string toText(in Image I, in char one='#', in char zero='.') pure {
return format("%(%s\n%)", I.map!(r => r.map!(p=> p ? one : zero)));
}
/// Return 8-neighbours+1 of point (x,y) of given image, in order. void neighbours(in Image I, in size_t x, in size_t y, ref Neighbours n) pure nothrow {
n = [I[y+1][x], I[y+1][x+1], I[y][x+1], I[y-1][x+1], // P2,P3,P4,P5
I[y-1][x], I[y-1][x-1], I[y][x-1], I[y+1][x-1], // P6,P7,P8,P9
I[y+1][x]]; // P2
}
static inInterval(T)(in T x, in T inf, in T sup) pure nothrow {
return x >= inf && x <= sup;
}
/// Zhang-Suen thinning algorithm. Image zhangSuen(Image image1) pure /*nothrow*/ in {
foreach (const row; image1) {
assert(row.length == image1[0].length); // Is rectangular.
assert(row.all!(x => x == 0 || x == 1));
}
} out(result) {
foreach (const row; result) {
assert(row.length == result[0].length); // Is rectangular.
assert(row.all!(x => x == 0 || x == 1));
}
} body {
immutable ny = image1.length;
if (ny == 0)
return image1;
immutable nx = image1[0].length;
if (nx == 0)
return image1;
auto image2 = image1.map!(row => row.dup).array;
Neighbours n;
bool hasChanged;
do {
hasChanged = false;
// Step 1:
foreach (immutable y; 1 .. ny - 1) {
foreach (immutable x; 1 .. nx - 1) {
image1.neighbours(x, y, n);
if (image1[y][x] && // Condition 0
(!n[2] || !n[4] || !n[6]) && // Condition 4
(!n[0] || !n[2] || !n[4]) && // Condition 3
n[].count([0, 1]) == 1 && // Condition 2
// n[0 .. 8].sum in iota(2, 7)) {
n[0 .. 8].sum.inInterval(2, 6)) { // Condition 1
hasChanged = true;
image2[y][x] = 0;
} else
image2[y][x] = image1[y][x];
}
}
// Step 2:
foreach (immutable y; 1 .. ny - 1) {
foreach (immutable x; 1 .. nx - 1) {
image2.neighbours(x, y, n);
if (image2[y][x] && // Condition 0
(!n[0] || !n[4] || !n[6]) && // Condition 4
(!n[0] || !n[2] || !n[6]) && // Condition 3
n[].count([0, 1]) == 1 && // Condition 2
n[0 .. 8].sum.inInterval(2, 6)) { // Condition 1
hasChanged = true;
image1[y][x] = 0;
} else
image1[y][x] = image2[y][x];
}
}
} while (hasChanged);
return image1;
}
void main() {
immutable before_txt = " ##..### ##..### ##..### ##..### ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ######. .......";
immutable small_rc = " ................................ .#########.......########....... .###...####.....####..####...... .###....###.....###....###...... .###...####.....###............. .#########......###............. .###.####.......###....###...... .###..####..###.####..####.###.. .###...####.###..########..###.. ................................";
immutable rc = " ........................................................... .#################...................#############......... .##################...............################......... .###################............##################......... .########.....#######..........###################......... ...######.....#######.........#######.......######......... ...######.....#######........#######....................... ...#################.........#######....................... ...################..........#######....................... ...#################.........#######....................... ...######.....#######........#######....................... ...######.....#######........#######....................... ...######.....#######.........#######.......######......... .########.....#######..........###################......... .########.....#######.######....##################.######.. .########.....#######.######......################.######.. .########.....#######.######.........#############.######.. ...........................................................";
foreach (immutable txt; [before_txt, small_rc, rc]) {
auto image = txt.toImage;
writefln("From:\n%s", image.toText);
const after = image.zhangSuen;
writefln("\nTo thinned:\n%s\n", after.toText);
}
}</lang>
- Output:
From: ##..### ##..### ##..### ##..### ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ######. ....... To thinned: ##..### #.....# #....## #...#.# #...#.. #...#.. #...#.. #...#.. #...#.. #...#.. #...#.. #...#.. #####.. ....... From: ................................ .#########.......########....... .###...####.....####..####...... .###....###.....###....###...... .###...####.....###............. .#########......###............. .###.####.......###....###...... .###..####..###.####..####.###.. .###...####.###..########..###.. ................................ To thinned: ................................ ...#####...........####......... ..#.....#........##....##....... ..#......#.......#.............. ..#.....#........#.............. ..####..#........#.............. ..#...###........#.............. ..#.....#........##............. ........#....#....######....#... ................................ From: ........................................................... .#################...................#############......... .##################...............################......... .###################............##################......... .########.....#######..........###################......... ...######.....#######.........#######.......######......... ...######.....#######........#######....................... ...#################.........#######....................... ...################..........#######....................... ...#################.........#######....................... ...######.....#######........#######....................... ...######.....#######........#######....................... ...######.....#######.........#######.......######......... .########.....#######..........###################......... .########.....#######.######....##################.######.. .########.....#######.######......################.######.. .########.....#######.######.........#############.######.. ........................................................... To thinned: ........................................................... ........................................................... .......########............................................ .....##........#...................############............ .....#..........#.................##....................... .....#..........#................#......................... .....#..........#................#......................... .....#..........#................#......................... .....############...............#.......................... .....#..........#...............#.......................... .....#..........#................#......................... .....#..........#................#......................... .....#..........#................#......................... .....#...........#................##....................... .....#.............................####.......#............ ....#..................###.............#######......###.... ........................................................... ...........................................................
Python
Several input images are converted. <lang python># -*- coding: utf-8 -*-
- Example from this blog post.
beforeTxt = \ 1100111 1100111 1100111 1100111 1100110 1100110 1100110 1100110 1100110 1100110 1100110 1100110 1111110 0000000\
- Thanks to 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))</lang>
- Output:
Just the example asked for in the task:
From:
######### ########
### #### #### ####
### ### ### ###
### #### ###
######### ###
### #### ### ###
### #### ### #### #### ###
### #### ### ######## ###
To thinned:
##### ####
# # ## ##
# # #
# # #
#### # #
# ### #
# # ##
# # ###### #