Accelerate Zhang-Suen algorithm in Numpy

Introduction

Click here for Zhang-Suen algorithm As you can see by reading the linked code, it is very slow because it is rotated in a double for loop. So I made it possible to do the same processing using only Numpy's universal function.

Universal function

Numpy provides a function called a universal function that returns an array of the results of performing major operations on each element of the array. If you use this, you do not have to go through the process of extracting each element one by one and processing it. It's fast. It will be about 20 to 30 times faster.

processing

Preprocessing

-Prepare a binarized image with black as True and white as False. Enclose the outside with False for 1 pixel. -For each element in the center part, generate an array that stores the elements of top, top right, right, bottom right, bottom, bottom left, left, top left (Name them P2 to P9 respectively)

#It is a method to fill the surrounding 1 pixel with False for a binary image.
def padding(binary_image):
    row, col = np.shape(binary_image)
    result = np.zeros((row+2,col+2))
    result[1:-1, 1:-1] = binary_image[:, :]
    return result

def generate_mask(image):
    row, col = np.shape(image)
    p2 = np.zeros((row, col)).astype(bool)
    p3 = np.zeros((row, col)).astype(bool)
    p4 = np.zeros((row, col)).astype(bool)
    p5 = np.zeros((row, col)).astype(bool)
    p6 = np.zeros((row, col)).astype(bool)
    p7 = np.zeros((row, col)).astype(bool)
    p8 = np.zeros((row, col)).astype(bool)
    p9 = np.zeros((row, col)).astype(bool)
    #Up
    p2[1:row-1, 1:col-1] = image[0:row-2, 1:col-1]
    #Upper right
    p3[1:row-1, 1:col-1] = image[0:row-2, 2:col]
    #right
    p4[1:row-1, 1:col-1] = image[1:row-1, 2:col]
    #Lower right
    p5[1:row-1, 1:col-1] = image[2:row, 2:col]
    #under
    p6[1:row-1, 1:col-1] = image[2:row, 1:col-1]
    #Lower left
    p7[1:row-1, 1:col-1] = image[2:row, 0:col-2]
    #left
    p8[1:row-1, 1:col-1] = image[1:row-1, 0:col-2]
    #upper left
    p9[1:row-1, 1:col-1] = image[0:row-2, 0:col-2]
    return (p2, p3, p4, p5, p6, p7, p8, p9)

Condition 1

** Black ** The original array is as it is.

condition1 = np.copy(image)

Condition 2

** When the pixels around the target pixel are arranged in order, there is exactly one place where white → black ** This condition means that there are exactly two True False changes when looking at an address in the order P2, P3, P4, P5, P6, P7, P8, P9, P2.

#This method determines whether there is exactly one white → black when the surrounding pixels are arranged in order.
def is_once_change(p_tuple):
    number_change = np.zeros_like(p_tuple[0])
    # P2~P9,For P2, count the number of Trues when the exclusive OR of adjacent elements is taken.
    for i in range(len(p_tuple) - 1):
        number_change = np.add(number_change, np.logical_xor(p_tuple[i], p_tuple[i+1]).astype(int))
    number_change = np.add(number_change, np.logical_xor(p_tuple[7], p_tuple[0]).astype(int))
    array_two = np.ones_like(p_tuple[0]) * 2
    return np.equal(number_change, array_two)

condition2 = is_once_change(p_tuple)

Condition 3

** 2 or more and 6 or less black around the target pixel ** This condition means that the number of Trues of P2, P3, P4, P5, P6, P7, P8, P9 is 2 or more and 6 or less for a certain address.

#This method counts the number of black pixels around it and determines whether it is 2 or more and 6 or less.
def is_black_pixels_appropriate(p_tuple):
    number_of_black_pxels = np.zeros_like(p_tuple[0])
    array_two = np.ones_like(p_tuple[0]) * 2
    array_six = np.ones_like(p_tuple[0]) * 6
    for p in p_tuple:
        number_of_black_pxels = np.add(number_of_black_pxels, p.astype(int))
    greater_two = np.greater_equal(number_of_black_pxels, array_two)
    less_six = np.less_equal(number_of_black_pxels, array_six)
    return np.logical_and(greater_two, less_six)

condition3 = is_black_pixels_appropriate(p_tuple)

Condition 4, condition 5

** At least one of the top, bottom, left, and right of the target pixel is white ** For the target pixel, it is a check that at least one of the corresponding P2, P4, P6, P8 values is False.

#A method that returns the logical product for all given arguments.
def multi_logical_and(*args):
    result = np.copy(args[0])
    for arg in args:
        result = np.logical_and(result, arg)
    return result
condition4 = np.logical_not(multi_logical_and(p_tuple[0], p_tuple[2], p_tuple[4]))

Source code

I will put the code of the whole process.

ZhangSuen.py


import numpy as np

#A method that returns the logical product for all given arguments.
def multi_logical_and(*args):
    result = np.copy(args[0])
    for arg in args:
        result = np.logical_and(result, arg)
    return result

#It is a method to fill the surrounding 1 pixel with False for a binary image.
def padding(binary_image):
    row, col = np.shape(binary_image)
    result = np.zeros((row+2,col+2))
    result[1:-1, 1:-1] = binary_image[:, :]
    return result

#The opposite of padding
def unpadding(image):
    return image[1:-1, 1:-1]

#Returns an array containing information about the pixels around that pixel.
def generate_mask(image):
    row, col = np.shape(image)
    p2 = np.zeros((row, col)).astype(bool)
    p3 = np.zeros((row, col)).astype(bool)
    p4 = np.zeros((row, col)).astype(bool)
    p5 = np.zeros((row, col)).astype(bool)
    p6 = np.zeros((row, col)).astype(bool)
    p7 = np.zeros((row, col)).astype(bool)
    p8 = np.zeros((row, col)).astype(bool)
    p9 = np.zeros((row, col)).astype(bool)
    #Up
    p2[1:row-1, 1:col-1] = image[0:row-2, 1:col-1]
    #Upper right
    p3[1:row-1, 1:col-1] = image[0:row-2, 2:col]
    #right
    p4[1:row-1, 1:col-1] = image[1:row-1, 2:col]
    #Lower right
    p5[1:row-1, 1:col-1] = image[2:row, 2:col]
    #under
    p6[1:row-1, 1:col-1] = image[2:row, 1:col-1]
    #Lower left
    p7[1:row-1, 1:col-1] = image[2:row, 0:col-2]
    #left
    p8[1:row-1, 1:col-1] = image[1:row-1, 0:col-2]
    #upper left
    p9[1:row-1, 1:col-1] = image[0:row-2, 0:col-2]
    return (p2, p3, p4, p5, p6, p7, p8, p9)

#This method determines whether there is exactly one white → black when the surrounding pixels are arranged in order.
def is_once_change(p_tuple):
    number_change = np.zeros_like(p_tuple[0])
    # P2~P9,For P2, count the number of Trues when the exclusive OR of adjacent elements is taken.
    for i in range(len(p_tuple) - 1):
        number_change = np.add(number_change, np.logical_xor(p_tuple[i], p_tuple[i+1]).astype(int))
    number_change = np.add(number_change, np.logical_xor(p_tuple[7], p_tuple[0]).astype(int))
    array_two = np.ones_like(p_tuple[0]) * 2

    return np.equal(number_change, array_two)

#This method counts the number of black pixels around it and determines whether it is 2 or more and 6 or less.
def is_black_pixels_appropriate(p_tuple):
    number_of_black_pxels = np.zeros_like(p_tuple[0])
    array_two = np.ones_like(p_tuple[0]) * 2
    array_six = np.ones_like(p_tuple[0]) * 6
    for p in p_tuple:
        number_of_black_pxels = np.add(number_of_black_pxels, p.astype(int))
    greater_two = np.greater_equal(number_of_black_pxels, array_two)
    less_six = np.less_equal(number_of_black_pxels, array_six)
    return np.logical_and(greater_two, less_six)

def step1(image, p_tuple):
    #Condition 1
    condition1 = np.copy(image)
    
    #Condition 2
    condition2 = is_once_change(p_tuple)
    
    #Condition 3
    condition3 = is_black_pixels_appropriate(p_tuple)
    
    #Condition 4
    condition4 = np.logical_not(multi_logical_and(p_tuple[0], p_tuple[2], p_tuple[4]))
    
    #Condition 5
    condition5 = np.logical_not(multi_logical_and(p_tuple[2], p_tuple[4], p_tuple[6]))
    
    return np.logical_xor(multi_logical_and(condition1, condition2, condition3, condition4, condition5), image)
    
def step2(image, p_tuple):
    #Condition 1
    condition1 = np.copy(image)
    
    #Condition 2
    condition2 = is_once_change(p_tuple)
    
    #Condition 3
    condition3 = is_black_pixels_appropriate(p_tuple)
    
    #Condition 4
    condition4 = np.logical_not(np.logical_and(p_tuple[0], np.logical_and(p_tuple[2], p_tuple[6])))
    
    #Condition 5
    condition5 = np.logical_not(np.logical_and(p_tuple[0], np.logical_and(p_tuple[4], p_tuple[6])))
    
    return np.logical_xor(multi_logical_and(condition1, condition2, condition3, condition4, condition5), image)

#This method returns a binarized image as a thin line.
def ZhangSuen(image):
    
    image = padding(image)
    
    while True:
        old_image = np.copy(image)

        p_tuple = generate_mask(image)
        image = step1(image, p_tuple)
        p_tuple = generate_mask(image)        
        image = step2(image, p_tuple)
        
        if (np.array_equal(old_image, image)):
            break
            
    return unpadding(image)


Recommended Posts

Accelerate Zhang-Suen algorithm in Numpy
where in numpy
Implement PRML algorithm in Python (almost Numpy only)
Axis specification in NumPy
Genetic algorithm in python
Algorithm in Python (Bellman-Ford)
Algorithm in Python (Dijkstra's algorithm)
Install numpy in Visual Studio 2019
Algorithm in Python (primality test)
Imitated Python's Numpy in C #
Matrix multiplication in python numpy
Reproduce Euclidean algorithm in Python
Algorithm in Python (binary search)
Implement Dijkstra's Algorithm in python
Algorithm in Python (breadth-first search, bfs)
Sorting algorithm and implementation in Python
Put python, numpy, opencv3 in ubuntu14
Write A * (A-star) algorithm in Python
Self-organizing map in Python NumPy version
Develop an investment algorithm in Python 2
[Numpy] Call savetxt () in append mode
Algorithm in Python (depth-first search, dfs)
Implementing a simple algorithm in Python 2
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
Invert numpy Boolean array in tilde