Python - image refinement (skeleton extraction)

1. Introduction

The thinning of image is mainly for binary image.

The so-called skeleton, can be understood as the image's central axis, a rectangular skeleton, is its rectangular upward central axis.

The skeleton of a circle is its center, the skeleton of a line is itself, and the skeleton of an isolated point is itself.

2. Acquisition of skeleton

There are two main methods to obtain skeleton:

(1) Based on fire simulation

Imagine that at the same time, the edge lines of the target will be ignited, the front of the fire will spread to the interior at a uniform speed, and the flame will be extinguished when the current edge intersects, and the combination of the flame extinguishment points is the skeleton.

(2) Based on the largest disc

The skeleton of a target consists of the centers of all the inscribed disks in the target.

 

 

Let's take a look at a typical round skeleton (represented by thick lines).

There are many kinds of thinning algorithms, but the commonly used one is look-up table.

Thinning is to remove some points from the original drawing, but still keep the original shape.

It's actually the skeleton of the original image.

The judgment of whether a point can be removed is based on the condition of eight adjacent points (eight connected points). The specific judgment basis is as follows:

1. Internal point cannot be deleted

2. Encourage points cannot be deleted

3. Line end cannot be deleted

4. If P is the boundary point, after removing P, if the connected component does not increase, P can be deleted

 

 

Look at the above points, which are the center points in the 3 * 3 matrix:

The first point cannot be removed because it is an internal point

The second point cannot be removed. It is also an internal point

The third point can't be removed. After deletion, the original connected part will be disconnected

The fourth point can be removed. This point is the skeleton

The fifth point can't be removed. It's the end of the line

The sixth point can't be removed. It's the end of the line

For all such points, we can make a table to judge whether such points can be deleted

 

 

We give different values to the black pixel points and the eight points around it. If the surrounding is black, we think its value is 0. If it is white, we take the corresponding value in the nine palace grid. For the first point in the previous figure, the surrounding points are all black, so its total value is 0, which corresponds to the first item in the index table. For the second point in the previous figure, there are three white points around it. Its total value is 1 + 4 + 32 = 37, which corresponds to the 38th item in the index table.

In this way, we map the situation of all points to the index table of 0-255

We scan the original image, for black pixels, calculate its value according to the surrounding eight points, and then check the corresponding items in the index table to decide whether to keep this point.

3. Code implementation

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

# Author   : Ma Yi
# Blog     : http://www.cnblogs.com/mayi0312/
# Date     : 2020-04-24
# Name     : test02
# Software : PyCharm
# Note     : Skeleton extraction
import cv2
import copy


# Mapping table
g_array = [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           1, 1, 0, 0, 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, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0,
           1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0]


def thin(img):
    """
    //Refine the function, and calculate the corresponding value of the center point according to the algorithm
    :param img: Images to be refined (binarized)
    :return:
    """
    h, w = img.shape
    i_thin = copy.deepcopy(img)
    for i in range(h):
        for j in range(w):
            if img[i, j] == 0:
                a = [1] * 9
                for k in range(3):
                    for l in range(3):
                        if -1 < (i - 1 + k) < h and -1 < (j - 1 + l) < w and i_thin[i - 1 + k, j - 1 + l] == 0:
                            a[k * 3 + l] = 0
                i_sum = a[0] * 1 + a[1] * 2 + a[2] * 4 + a[3] * 8 + a[5] * 16 + a[6] * 32 + a[7] * 64 + a[8] * 128
                i_thin[i, j] = g_array[i_sum] * 255

    return i_thin


def to_binary(img):
    """
    //Binary function. The threshold value is set according to the darkening program of the picture
    :param img: Binary image required
    :return:
    """
    w, h = img.shape
    i_two = copy.deepcopy(img)
    for i in range(w):
        for j in range(h):
            if img[i, j] < 200:
                i_two[i, j] = 0
            else:
                i_two[i, j] = 255

    return i_two


# Entry function
if __name__ == '__main__':
    # Read pictures and display
    image = cv2.imread("1.jpg", 0)
    img_binary = to_binary(image)
    img_thin = thin(img_binary)
    cv2.imshow("image", image)
    cv2.imshow("img_binary", img_binary)
    cv2.imshow("img_thin", img_thin)
    cv2.waitKey(0)

 

 

 

The effect is not very good. Let's take a simple example:

 

According to the previous analysis, we should get a vertical line, but in fact we get a horizontal line.

When we scan from top to bottom and from left to right, when we encounter the first point, we can delete it by looking up the table, when we encounter the second point, we can delete it by looking up the table, and the whole first row can be deleted.

So when we look at the second line, like the first line, it's deleted as a whole. This goes all the way to the last line, so we get a straight line.

The solution is:

In the process of horizontal scanning of each line, the left and right neighbors of each point are judged first. If they are all black spots, the point will not be processed. In addition, if a black spot is deleted, skip its right neighbor and process the next point. If you do this for the rectangle, the horizontal direction will be reduced by two pixels. Then we change the vertical scanning, the same way.

In this way, if you do a horizontal scan and a vertical scan, the original image will be "thin" and repeat the above steps several times until the image is not changed.

This improvement increases the running time of algorithm complexity by an order of magnitude:

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

# Author   : Ma Yi
# Blog     : http://www.cnblogs.com/mayi0312/
# Date     : 2020-04-24
# Name     : test02
# Software : PyCharm
# Note     : Image extraction skeleton
import cv2
import copy


# Mapping table
l_array = [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           1, 1, 0, 0, 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, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0,
           1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0]


def v_thin(img):
    """
    //Refine the function, and calculate the corresponding value of the center point according to the algorithm
    :param img: Images to be refined (binarized)
    :param array: Mapping matrix array
    :return:
    """
    h, w = img.shape
    i_next = 1
    for i in range(h):
        for j in range(w):
            if i_next == 0:
                i_next = 1
            else:
                i_m = int(img[i, j - 1]) + int(img[i, j]) + int(img[i, j + 1]) if 0 < j < w - 1 else 1
                if img[i, j] == 0 and i_m != 0:
                    a = [0] * 9
                    for k in range(3):
                        for l in range(3):
                            if -1 < (i - 1 + k) < h and -1 < (j - 1 + l) < w and img[i - 1 + k, j - 1 + l] == 255:
                                a[k * 3 + l] = 1
                    i_sum = a[0] * 1 + a[1] * 2 + a[2] * 4 + a[3] * 8 + a[5] * 16 + a[6] * 32 + a[7] * 64 + a[8] * 128
                    img[i, j] = l_array[i_sum] * 255
                    if l_array[i_sum] == 1:
                        i_next = 0


def h_thin(img):
    """
    //Refine the function, and calculate the corresponding value of the center point according to the algorithm
    :param img: Images to be refined (binarized)
    :param array: Mapping matrix array
    :return:
    """
    h, w = img.shape
    i_next = 1
    for j in range(w):
        for i in range(h):
            if i_next == 0:
                i_next = 1
            else:
                i_m = int(img[i -1, j]) + int(img[i, j]) + int(img[i + 1, j]) if 0 < i < h - 1 else 1
                if img[i, j] == 0 and i_m != 0:
                    a = [0] * 9
                    for k in range(3):
                        for l in range(3):
                            if -1 < (i - 1 + k) < h and -1 < (j - 1 + l) < w and img[i - 1 + k, j - 1 + l] == 255:
                                a[k * 3 + l] = 1
                    i_sum = a[0] * 1 + a[1] * 2 + a[2] * 4 + a[3] * 8 + a[5] * 16 + a[6] * 32 + a[7] * 64 + a[8] * 128
                    img[i, j] = l_array[i_sum] * 255
                    if l_array[i_sum] == 1:
                        i_next = 0


def xi_hua(img, num=10):
    for i in range(num):
        v_thin(img)
        h_thin(img)

    return img


def to_binary(img):
    """
    //Two valued function, the threshold value is set according to the dark program of the picture
    :param img: Binary image required
    :return:
    """
    w, h = img.shape
    i_two = copy.deepcopy(img)
    for i in range(w):
        for j in range(h):
            if img[i, j] < 200:
                i_two[i, j] = 0
            else:
                i_two[i, j] = 255

    return i_two


# Entry function
if __name__ == '__main__':
    # Read pictures and display
    image = cv2.imread("1.jpg", 0)
    img_binary = to_binary(image)
    cv2.imshow("image", image)
    cv2.imshow("img_binary", img_binary)
    img_thin = xi_hua(img_binary)
    cv2.imshow("img_thin", img_thin)
    cv2.waitKey(0)

Effect of operation:

 

Tags: Python Pycharm

Posted on Fri, 24 Apr 2020 02:53:49 -0700 by shane18