Region extraction method using cellular automaton Try region extraction from the image with growcut (Python)

Introduction

Many methods have been proposed to segment (extract) a specific area from an image. Well-known methods include the graph cut method, level set method, and area expansion method. The graph cut and level set methods can extract areas with high accuracy, but it is quite difficult to program. The area expansion method is easy to set up, but the accuracy is not good because it simply extracts the area that fits in the threshold from the seed point. However, a special method has been proposed that makes it very easy to program and has good accuracy. That is the grow cut method. growcut is a region extraction method using a cellular automaton. The area is determined by repeating the process in which the pixel of interest is attacked by the neighboring pixels and replaced by the labels of the neighboring pixels. This time I tried to build this growcut method with python, so I will explain the program.

What is the growcut method?

The

growcut method is a method for segmenting the foreground when seed points for the foreground and background are given in the image. This method is based on cellular automaton and can be interpreted as bacteria with a foreground label and bacteria with a background label diffuse from the seed point and compete with each other to scramble for each pixel in the image. Each pixel of interest is invaded by bacteria lurking in nearby pixels. Each bacterium has offensive and defensive power, and when a bacterium tries to invade a pixel (give its own label to that pixel), the defensive power of that pixel attenuates the attack to some extent. Even so, if the attack power is greater than the attack power of the pixel to invade, that pixel will be invaded. It seems that the foreground can be extracted by performing this aggression process for all pixels and repeating this series of steps many times. Please refer to the references for detailed mathematical formulas. </ p>

Usage data

The data used is a grayscale image of Mr. Lenna. This time, this Lenna is extracted by the grow cut method.

Whole program

The entire program created this time is as follows.

python

# encoding:utf-8
import numpy as np
import cv2
import matplotlib.pyplot as plt

class Sampling:
    def __init__(self, image):
        self.image = image
        self.points = []

    def mouse(self, event):
        if event.button == 3:
            self.axis.plot(event.xdata, event.ydata, "ro")
            self.points.append([event.ydata, event.xdata])
        self.fig.canvas.draw()

    def start(self):
        self.fig = plt.figure()
        self.axis = self.fig.add_subplot(111)
        self.fig.canvas.mpl_connect("button_press_event", self.mouse)
        plt.gray()
        self.axis.imshow(self.image)
        plt.show()
        plt.clf()
        return np.array(self.points).astype(np.int)


def growCut(image, foreGround, backGround, iter=100):
    #8 neighborhood
    diffY = [-1,-1,-1,0,0,1,1,1]
    diffX = [-1,0,1,-1,1,-1,0,1]

    #Label initialization
    label = np.zeros(image.shape)
    label[foreGround[:,0], foreGround[:,1]] = 1
    label[backGround[:,0], backGround[:,1]] = -1

    #Offensive power
    power = np.zeros(image.shape)
    power[foreGround[:,0], foreGround[:,1]] = 1.0
    power[backGround[:,0], backGround[:,1]] = 1.0

    power_next = np.copy(power)
    label_next = np.copy(label)

    #start growcut
    for t in range(iter):
        print(t)

        power = np.copy(power_next)
        label = np.copy(label_next)

        for i in range(1,image.shape[0]-1):
            for j in range(1,image.shape[1]-1):
                for k in range(8):
                    dy, dx = diffY[k], diffX[k]

                    #Defensive power of attention cell
                    shield = 1.0 - np.abs(image[i,j] - image[i+dy,j+dx])

                    #Does the attack power of neighboring cells exceed the defense power of the pixel of interest?
                    if shield * power[i+dy,j+dx] > power[i,j]:
                        label_next[i,j] = label[i+dy,j+dx]
                        power_next[i,j] = power[i+dy,j+dx] * shield
    return label_next



def main():
    image = cv2.imread("Lenna.png ", 0).astype(np.float)
    image = (image - image.min()) / (image.max() - image.min())
    
    plt.gray()
    plt.imshow(image)
    plt.show()
    
    foreGround = Sampling(image).start()
    backGround = Sampling(image).start()
    
    mask = growCut(image, foreGround, backGround)
    mask[mask != 1] = 0
    
    plt.gray()
    plt.subplot(131)
    plt.imshow(image)
    plt.subplot(132)
    plt.imshow(image)
    plt.plot(foreGround[:,1], foreGround[:,0], "ro")
    plt.plot(backGround[:,1], backGround[:,0], "bo")
    plt.subplot(133)
    plt.imshow(image * mask)
    plt.show()

Program explanation

The Sampling class is a class for determining the seed point. Right-click to hit the seed point. Finally, all seed points are returned. Since it is not a particularly important part, detailed explanation is omitted.

python

class Sampling:
    def __init__(self, image):
        self.image = image
        self.points = []

    def mouse(self, event):
        if event.button == 3:
            self.axis.plot(event.xdata, event.ydata, "ro")
            self.points.append([event.ydata, event.xdata])
        self.fig.canvas.draw()

    def start(self):
        self.fig = plt.figure()
        self.axis = self.fig.add_subplot(111)
        self.fig.canvas.mpl_connect("button_press_event", self.mouse)
        plt.gray()
        self.axis.imshow(self.image)
        plt.show()
        plt.clf()
        return np.array(self.points).astype(np.int)

The following is an explanation of the growcut function. In the growcut method, the process of invading all pixels from neighboring pixels is repeated many times. In other words

python

for t in range(iter):
    #Repeat the aggression process iter times

It means that. This aggression process defines each pixel as a pixel of interest, and defines the difference in pixel values of neighboring pixels as the defense power of the pixel of interest. This is

python

shield = 1.0 - np.abs(image[i,j] - image[i+dy,j+dx])

is. This defense power attenuates the attack of nearby pixels, but if it still exceeds the attack of the pixel of interest, the pixel of interest is invaded and the label of the nearby pixel is given to the pixel of interest. And the attack power of the pixel of interest is also updated. This is,

python

if shield * power[i+dy,j+dx] > power[i,j]:
   label_next[i,j] = label[i+dy,j+dx]
   power_next[i,j] = power[i+dy,j+dx] * shield

It becomes. It seems that segmentation of the foreground is possible by repeating these steps.

Execution result

The red point is the foreground seed point and the blue point is the background seed point. It's a little dirty, but you can see that it's mostly segmented. I have no idea why it works so well. The person who thinks about this is amazing.

References

This is an original paper by growcut. “GrowCut” - Interactive Multi-Label N-D Image Segmentation By Cellular Automata

It seems that a certain teacher at the University of Tokyo wrote it. State-of-the-art image processing growcut written in 100 lines