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. figure_2.png

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.

figure_1.png

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

Recommended Posts

Region extraction method using cellular automaton Try region extraction from the image with growcut (Python)
Image processing from scratch with python (4) Contour extraction
Try a similar search for Image Search using the Python SDK [Search]
[Python] LASSO regression with equation constraints using the multiplier method
[Python] Using OpenCV with Python (Image Filtering)
[Python] Using OpenCV with Python (Image transformation)
Try using the Python Cmd module
Try blurring the image with opencv2
Try using Amazon DynamoDB from Python
[Python] Try to graph from the image of Ring Fit [OCR]
Try to extract a character string from an image with Python3
Try mathematical formulas using Σ with python
Try using the Kraken API in Python
Behind the flyer: Using Docker with Python
Try using the camera with Python's OpenCV
Try to image the elevation data of the Geographical Survey Institute with Python
Try using Python with Google Cloud Functions
Try using the Python web framework Django (1)-From installation to server startup
Working with OpenStack using the Python SDK
Try cluster analysis using the K-means method
Image acquisition from camera with Python + OpenCV
Try calling Python from Ruby with thrift
Try to measure the position of the object on the desk (real coordinate system) from the camera image with Python + OpenCV
I tried "smoothing" the image with Python + OpenCV
I tried "differentiating" the image with Python + OpenCV
Image processing from scratch with python (5) Fourier transform
Try to solve the man-machine chart with Python
Try using the BitFlyer Ligntning API in Python
Python: Try using the UI on Pythonista 3 on iPad
Try using the Python web framework Tornado Part 1
I tried "binarizing" the image with Python + OpenCV
Operate the schedule app using python from iphone
Try using the collections module (ChainMap) of python3
Try using the Python web framework Tornado Part 2
Try implementing the Monte Carlo method in Python
Try accessing the YQL API directly from Python 3
Try using the DropBox Core API in Python
Extract the table of image files with OneDrive & Python
Try to solve the programming challenge book with python3
Learn Nim with Python (from the beginning of the year).
How to scrape image data from flickr with python
[Cloudian # 8] Try setting the bucket versioning with Python (boto3)
Try translating with Python while maintaining the PDF layout
Try to solve the internship assignment problem with Python
Try touching the micro: bit with VS Code + Python
[Python] Get the numbers in the graph image with OCR
[Python] Specify the range from the image by dragging the mouse
Destroy the intermediate expression of the sweep method with Python
Determine the threshold using the P tile method in python
Try projective transformation of images using OpenCV with Python
Identify the name from the flower image with keras (tensorflow)
Convert the image in .zip to PDF with Python
Read QR code from image file with Python (Mac)
Installation method when using RealSense from Python (pyenv edition)
[Python] Mask the image into a circle using Pillow
Principal component analysis using python from nim with nimpy
Study from the beginning of Python Hour8: Using packages
Install the latest Python from pyenv installed with homebrew
A little bit from Python using the Jenkins API
How to know the number of GPUs from python ~ Notes on using multiprocessing with pytorch ~
Try scraping with Python.