Zhang-Suen thinning algorithm: Difference between revisions
Replaced output. |
=={{header|Racket}}== implementation added |
||
Line 470: | Line 470: | ||
To thinned: |
To thinned: |
||
................................ |
|||
..#######.........######........ |
|||
..#.....#........##............. |
|||
..#......#.......#.............. |
|||
..#.....#........#.............. |
|||
..#####.#........#.............. |
|||
.......##........#.............. |
|||
........#....#...##....##...#... |
|||
.........#.........####......... |
|||
................................</pre> |
|||
=={{header|Racket}}== |
|||
<lang racket>#lang racket |
|||
(define (img-01string->vector str) |
|||
(define lines (regexp-split "\n" str)) |
|||
(define h (length lines)) |
|||
(define w (if (zero? h) 0 (string-length (car lines)))) |
|||
(define v (for*/vector #:length (* w h) |
|||
((l (in-list lines)) (p (in-string l))) |
|||
(match p (#\0 0) (#\1 1) (#\# 1) (#\. 0)))) |
|||
(values v h w)) |
|||
; Task (2) asks for "or an ASCII-art image of space/non-space characters." |
|||
; Spaces don't really impress where the borders are, so we'll use a dot. |
|||
(define cell->display-char (match-lambda (0 ".") (1 "#") (else "?"))) |
|||
(define (display-img v w) |
|||
(for ((p (in-vector v)) (col (in-naturals))) |
|||
(printf "~a" (cell->display-char p)) |
|||
(when (= (modulo col w) (sub1 w)) (newline)))) |
|||
; returns vector of ([P1's idx] P1 P2 ... P9) |
|||
(define (Pns v w r c) |
|||
(define i (+ c (* r w))) |
|||
(define-syntax-rule (vi+ x) (vector-ref v (+ i x))) |
|||
(define-syntax-rule (vi- x) (vector-ref v (- i x))) |
|||
(vector i (vi+ 0) (vi- w) (vi+ (- 1 w)) |
|||
(vi+ 1) (vi+ (+ w 1)) (vi+ w) |
|||
(vi+ (- w 1)) (vi- 1) (vi- (+ w 1)))) |
|||
; Second argument to in-vector is the start offset; |
|||
; We skip offset 0 (idx) and 1 (P1) |
|||
(define (B Ps) (for/sum ((Pn (in-vector Ps 2))) Pn)) |
|||
(define (A Ps) |
|||
(define P2 (vector-ref Ps 2)) |
|||
(define-values (rv _) |
|||
(for/fold ((acc 0) (Pn-1 P2)) |
|||
((Pn (in-sequences (in-vector Ps 3) (in-value P2)))) |
|||
(values (+ acc (if (and (= 0 Pn-1) (= 1 Pn)) 1 0)) Pn))) |
|||
rv) |
|||
(define-syntax-rule (not-all-black? Pa Pb Pc) (zero? (* Pa Pb Pc))) |
|||
(define (z-s-thin v h w) |
|||
; return idx when thin necessary, #f otherwise |
|||
(define (thin? Ps n/bour-check-1 n/bour-check-2) |
|||
(match-define (vector idx P1 P2 _ P4 _ P6 _ P8 _) Ps) |
|||
(and (= P1 1) (<= 2 (B Ps) 6) (= (A Ps) 1) |
|||
(n/bour-check-1 P2 P4 P6 P8) |
|||
(n/bour-check-2 P2 P4 P6 P8) |
|||
idx)) |
|||
(define (has-white?-246 P2 P4 P6 P8) (not-all-black? P2 P4 P6)) |
|||
(define (has-white?-468 P2 P4 P6 P8) (not-all-black? P4 P6 P8)) |
|||
(define (has-white?-248 P2 P4 P6 P8) (not-all-black? P2 P4 P8)) |
|||
(define (has-white?-268 P2 P4 P6 P8) (not-all-black? P2 P6 P8)) |
|||
(define (step-n even-Pn-check-1 even-Pn-check-2) |
|||
(for*/list ((r (in-range 1 (- h 1))) |
|||
(c (in-range 1 (- w 1))) |
|||
(idx (in-value (thin? (Pns v w r c) |
|||
even-Pn-check-1 |
|||
even-Pn-check-2))) |
|||
#:when idx) idx)) |
|||
(define (step-1) (step-n has-white?-246 has-white?-468)) |
|||
(define (step-2) (step-n has-white?-248 has-white?-268)) |
|||
(define (inner-z-s-thin) |
|||
(define changed-list-1 (step-1)) |
|||
(for ((idx (in-list changed-list-1))) (vector-set! v idx 0)) |
|||
(define changed-list-2 (step-2)) |
|||
(for ((idx (in-list changed-list-2))) (vector-set! v idx 0)) |
|||
(unless (and (null? changed-list-1) (null? changed-list-2)) (inner-z-s-thin))) |
|||
(inner-z-s-thin)) |
|||
(define (read-display-thin-display-image img-str) |
|||
(define-values (v h w) (img-01string->vector img-str)) |
|||
(printf "Original image:~%") (display-img v w) |
|||
(z-s-thin v h w) |
|||
(printf "Thinned image:~%") (display-img v w)) |
|||
(define e.g.-image #<<EOS |
|||
00000000000000000000000000000000 |
|||
01111111110000000111111110000000 |
|||
01110001111000001111001111000000 |
|||
01110000111000001110000111000000 |
|||
01110001111000001110000000000000 |
|||
01111111110000001110000000000000 |
|||
01110111100000001110000111000000 |
|||
01110011110011101111001111011100 |
|||
01110001111011100111111110011100 |
|||
00000000000000000000000000000000 |
|||
EOS |
|||
) |
|||
(define e.g.-image/2 #<<EOS |
|||
##..### |
|||
##..### |
|||
##..### |
|||
##..### |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
##..##. |
|||
######. |
|||
....... |
|||
EOS |
|||
) |
|||
(module+ main |
|||
; (read-display-thin-display-image e.g.-image/2) |
|||
; (newline) |
|||
(read-display-thin-display-image e.g.-image))</lang> |
|||
{{out}} |
|||
Only the requested image is output: |
|||
<pre>Original image: |
|||
................................ |
|||
.#########.......########....... |
|||
.###...####.....####..####...... |
|||
.###....###.....###....###...... |
|||
.###...####.....###............. |
|||
.#########......###............. |
|||
.###.####.......###....###...... |
|||
.###..####..###.####..####.###.. |
|||
.###...####.###..########..###.. |
|||
................................ |
|||
Thinned image: |
|||
................................ |
................................ |
||
..#######.........######........ |
..#######.........######........ |
Revision as of 09:55, 16 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));
} out(result) {
assert(result.nx == image1.nx && result.ny == image1.ny); assert(result.image.all!(x => x == Img.black || x == Img.white));
} body {
/// True if inf <= x <= sup. static inInterval(T)(in T x, in T inf, in T sup) pure nothrow { return x >= inf && x <= sup; }
/// Return 8-neighbours+1 of point (x,y) of given image, in order. static void neighbours(in Img I, in size_t x, in size_t y, 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: ................................ ..#######.........######........ ..#.....#........##............. ..#......#.......#.............. ..#.....#........#.............. ..#####.#........#.............. .......##........#.............. ........#....#...##....##...#... .........#.........####......... ................................
Racket
<lang racket>#lang racket (define (img-01string->vector str)
(define lines (regexp-split "\n" str)) (define h (length lines)) (define w (if (zero? h) 0 (string-length (car lines)))) (define v (for*/vector #:length (* w h) ((l (in-list lines)) (p (in-string l))) (match p (#\0 0) (#\1 1) (#\# 1) (#\. 0)))) (values v h w))
- Task (2) asks for "or an ASCII-art image of space/non-space characters."
- Spaces don't really impress where the borders are, so we'll use a dot.
(define cell->display-char (match-lambda (0 ".") (1 "#") (else "?")))
(define (display-img v w)
(for ((p (in-vector v)) (col (in-naturals))) (printf "~a" (cell->display-char p)) (when (= (modulo col w) (sub1 w)) (newline))))
- returns vector of ([P1's idx] P1 P2 ... P9)
(define (Pns v w r c)
(define i (+ c (* r w))) (define-syntax-rule (vi+ x) (vector-ref v (+ i x))) (define-syntax-rule (vi- x) (vector-ref v (- i x))) (vector i (vi+ 0) (vi- w) (vi+ (- 1 w)) (vi+ 1) (vi+ (+ w 1)) (vi+ w) (vi+ (- w 1)) (vi- 1) (vi- (+ w 1))))
- Second argument to in-vector is the start offset;
- We skip offset 0 (idx) and 1 (P1)
(define (B Ps) (for/sum ((Pn (in-vector Ps 2))) Pn))
(define (A Ps)
(define P2 (vector-ref Ps 2)) (define-values (rv _) (for/fold ((acc 0) (Pn-1 P2)) ((Pn (in-sequences (in-vector Ps 3) (in-value P2)))) (values (+ acc (if (and (= 0 Pn-1) (= 1 Pn)) 1 0)) Pn))) rv)
(define-syntax-rule (not-all-black? Pa Pb Pc) (zero? (* Pa Pb Pc))) (define (z-s-thin v h w)
; return idx when thin necessary, #f otherwise (define (thin? Ps n/bour-check-1 n/bour-check-2) (match-define (vector idx P1 P2 _ P4 _ P6 _ P8 _) Ps) (and (= P1 1) (<= 2 (B Ps) 6) (= (A Ps) 1) (n/bour-check-1 P2 P4 P6 P8) (n/bour-check-2 P2 P4 P6 P8) idx)) (define (has-white?-246 P2 P4 P6 P8) (not-all-black? P2 P4 P6)) (define (has-white?-468 P2 P4 P6 P8) (not-all-black? P4 P6 P8)) (define (has-white?-248 P2 P4 P6 P8) (not-all-black? P2 P4 P8)) (define (has-white?-268 P2 P4 P6 P8) (not-all-black? P2 P6 P8)) (define (step-n even-Pn-check-1 even-Pn-check-2) (for*/list ((r (in-range 1 (- h 1))) (c (in-range 1 (- w 1))) (idx (in-value (thin? (Pns v w r c) even-Pn-check-1 even-Pn-check-2))) #:when idx) idx)) (define (step-1) (step-n has-white?-246 has-white?-468)) (define (step-2) (step-n has-white?-248 has-white?-268)) (define (inner-z-s-thin) (define changed-list-1 (step-1)) (for ((idx (in-list changed-list-1))) (vector-set! v idx 0)) (define changed-list-2 (step-2)) (for ((idx (in-list changed-list-2))) (vector-set! v idx 0)) (unless (and (null? changed-list-1) (null? changed-list-2)) (inner-z-s-thin))) (inner-z-s-thin))
(define (read-display-thin-display-image img-str)
(define-values (v h w) (img-01string->vector img-str)) (printf "Original image:~%") (display-img v w) (z-s-thin v h w) (printf "Thinned image:~%") (display-img v w))
(define e.g.-image #<<EOS 00000000000000000000000000000000 01111111110000000111111110000000 01110001111000001111001111000000 01110000111000001110000111000000 01110001111000001110000000000000 01111111110000001110000000000000 01110111100000001110000111000000 01110011110011101111001111011100 01110001111011100111111110011100 00000000000000000000000000000000 EOS
)
(define e.g.-image/2 #<<EOS
- ..###
- ..###
- ..###
- ..###
- ..##.
- ..##.
- ..##.
- ..##.
- ..##.
- ..##.
- ..##.
- ..##.
- .
....... EOS
)
(module+ main
; (read-display-thin-display-image e.g.-image/2) ; (newline) (read-display-thin-display-image e.g.-image))</lang>
- Output:
Only the requested image is output:
Original image: ................................ .#########.......########....... .###...####.....####..####...... .###....###.....###....###...... .###...####.....###............. .#########......###............. .###.####.......###....###...... .###..####..###.####..####.###.. .###...####.###..########..###.. ................................ Thinned image: ................................ ..#######.........######........ ..#.....#........##............. ..#......#.......#.............. ..#.....#........#.............. ..#####.#........#.............. .......##........#.............. ........#....#...##....##...#... .........#.........####......... ................................