Zhang-Suen thinning algorithm: Difference between revisions
(A patch in the D entry) |
(Better patch for D entry) |
||
| Line 118: | Line 118: | ||
assert(image1.image.all!(x => x == 0 || x == 1)); |
assert(image1.image.all!(x => x == 0 || x == 1)); |
||
} out(result) { |
} out(result) { |
||
//assert(result.nx == image1.nx && result.ny == image1.ny); |
|||
| ⚫ | |||
assert(result.nx == image1.nx && result.ny == image1.ny); |
assert(result.nx == image1.nx && result.ny == image1.ny); |
||
//assert(result.image.all!(x => x == Img.black || x == Img.white)); |
|||
| ⚫ | |||
} body { |
} body { |
||
/// True if inf <= x <= sup. |
/// True if inf <= x <= sup. |
||
Revision as of 12:26, 14 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
This uses the module from the Bitmap Task.
<lang d>import std.stdio, std.algorithm, std.string, std.functional, bitmap;
alias sum = curry!(reduce!q{a + b}, 0); //*
struct BlackWhite {
ubyte c; static immutable black = typeof(this)(0); static immutable white = typeof(this)(1); alias c this;
}
alias Neighbours = BlackWhite[9]; alias Img = Image!BlackWhite;
/// Zhang-Suen thinning algorithm. Img zhangSuen(Img image1) pure /*nothrow*/ in {
//assert(image1.image.all!(x => x == Img.black || x == Img.white)); assert(image1.image.all!(x => x == 0 || x == 1));
} out(result) {
assert(result.nx == image1.nx && result.ny == image1.ny); //assert(result.image.all!(x => x == Img.black || x == Img.white)); assert(result.image.all!(x => x == 0 || x == 1));
} body {
/// True if inf <= x <= sup.
static inInterval(T)(in T x, in T inf, in T sup) pure nothrow {
return x >= inf && x <= sup;
}
/// Return 8-neighbours+1 of point (x,y) of given image, in order.
static void neighbours(in Img I, in size_t x, in size_t y,
ref Neighbours n) pure nothrow {
n = [I[x,y+1], I[x+1,y+1], I[x+1,y], I[x+1,y-1], // P2,P3,P4,P5
I[x,y-1], I[x-1,y-1], I[x-1,y], I[x-1,y+1], // P6,P7,P8,P9
I[x,y+1]]; // P2
}
if (image1.nx <= 3 || image1.ny <= 3)
return image1;
auto image2 = Img.fromData(image1.image.dup, image1.nx, image1.ny);
Neighbours n;
bool hasChanged;
do {
hasChanged = false;
// Step 1:
foreach (immutable y; 1 .. image1.ny - 1) {
foreach (immutable x; 1 .. image1.nx - 1) {
neighbours(image1, x, y, n);
if (image1[x, y] && // 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)) {
inInterval(n[0 .. 8].sum, 2, 6)) { // Condition 1
hasChanged = true;
image2[x, y] = Img.black;
} else
image2[x, y] = image1[x, y];
}
}
// Step 2:
foreach (immutable y; 1 .. image1.ny - 1) {
foreach (immutable x; 1 .. image1.nx - 1) {
neighbours(image2, x, y, n);
if (image2[x, y] && // 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
inInterval(n[0 .. 8].sum, 2, 6)) { // Condition 1
hasChanged = true;
image1[x, y] = Img.black;
} else
image1[x, y] = image2[x, y];
}
}
} while (hasChanged);
return image1;
}
void main() {
immutable before_txt = " ##..### ##..### ##..### ##..### ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ##..##. ######. .......";
immutable small_rc = " ................................ .#########.......########....... .###...####.....####..####...... .###....###.....###....###...... .###...####.....###............. .#########......###............. .###.####.......###....###...... .###..####..###.####..####.###.. .###...####.###..########..###.. ................................";
immutable rc = " ........................................................... .#################...................#############......... .##################...............################......... .###################............##################......... .########.....#######..........###################......... ...######.....#######.........#######.......######......... ...######.....#######........#######....................... ...#################.........#######....................... ...################..........#######....................... ...#################.........#######....................... ...######.....#######........#######....................... ...######.....#######........#######....................... ...######.....#######.........#######.......######......... .########.....#######..........###################......... .########.....#######.######....##################.######.. .########.....#######.######......################.######.. .########.....#######.######.........#############.######.. ...........................................................";
foreach (immutable txt; [before_txt, small_rc, rc]) {
auto img = Img.fromText(txt);
"From:".writeln;
img.textualShow(/*bl=*/ '.', /*wh=*/ '#');
"\nTo thinned:".writeln;
img.zhangSuen.textualShow(/*bl=*/ '.', /*wh=*/ '#');
writeln;
}
}</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:
##### ####
# # ## ##
# # #
# # #
#### # #
# ### #
# # ##
# # ###### #