jimmy-hu / 2018_fall_image_processing_final_api_segmenter

Segmenter

This module separates background and foreground, using labeled key points.

Prepare source code

git clone https://github.com/cy20lin/2018_fall_image_processing_final_api_segmenter ~/segmenter
cd ~/segmenter
git submodule update --init --recursive

Build this module

cd ~/segmenter
mkdir build
cd build
cmake ..
make

Test this project

cd ~/segmenter
cd build
./test_api_segmenter_segmenter_cimg

Ideas

Given a image and with labeled keypoints (label as foreground and background). We want to calculate the label for each pixel in the image.

Given that we already know the label of some point (pixel), we are going to utilize those point to generate the label information for other not-yet-labeled pixel.

It take three steps to generate labels for all pixels: Blur, Calculate Priority Map, and watershed.

First, blur the image for a smoother image. Avoiding high frequency noises.

Second, calculate the priority for each pixel in this image. Use the reciprocal of gradient as the priority value. The pixel with high priority is in the place where the variation of intensity is low. The pixel with low priority on the other hand is in the place where the variation of intensity are high.

Third, using watershed to calculate the labels. By propagating from the neighbors of know labels, those pixel with high priority has higher chance to be labeled first. Stop, propagating as whole pixels in image has already been labeled.

The algorithm under the hood

Step1. Blur the image

Use Guassian filtering, with sigma = max(image.width, image.height) * 0.002;

Step2. Build the Priority Image

Get the gradient vector (x y directions) for each channel (r, g, b),

Get the length (norm) of each gradient vector for each channel.

Sum length for gradient vector in each channel.

Add 1 to the sum and divide 1 using this sum.

Now we got a priority at this point whose value is in the range (0,1].

For smooth areas the priority value is high, otherwise the priority is low.

Gradient in x direction.

Gradient in y direction.

Priority Image, with black = 0, white = 1

Step3. Watershed

Given the labeled keypoints (i.e. foreground or background) and priority image.

Initialization:

For each neighbor (we use 8-neighbor in this project) of the keypoints.

Push each neighbor point into priority queque given their priority.

Propagation:

Pop the point with the highest priority.

Point with higher priority would be processed first.

Push all non-labeled neighbors around this point into priority queue.

Set the label of this point to the label of the labeled neighbor.

Stop when priority queue is empty.

Following figure is the result mask, with background in color red, foreground in color green.

References

• Concurrent computation of topological watershed on shared memory parallel machines
• The Morphological Approach to Segmentation - The Watershed Transformation (S. Beucher and F. Meyer)
• Topographic distance and watershed lines
• Watershed Approaches For Color Image Segmentation
• Watershed wiki page
• How to code a nice user-guided foreground extraction algorithm? (Addendum)