Title

Simple Interactive Object Extraction in still images

Introduction

This article is about an algorithm for foreground extraction in still image. The presented approach has been derived from color signatures, a technique originating from image retrieval.

Methodology

Algorithm

·         Define foreground

·         Rest of the image is considered as background

·         Input

There are 3 user specified regions as inputs called “Trimap”.

·         Known background

·         Unknown region

·         Known foreground (optional)

Using additional selections the user may specify one or more “known regions”. Trimap is mapped to a confidence matrix where each element of the matrix corresponds to a pixel in the image.

 Values of the elements lie in the interval [0, 1] where a value of

0 – specifies known background

0.5 – Unknown region

1 – Known foreground

Any other value expresses uncertainty with a certain tendency towards one limit or the other.

Convert to CIELAB

·         Convert the entire image into the CIELAB color space

·         It is based on the opponent colors theory of color vision which assumes that two colors cannot be both green and red, nor yellow and blue at the same time.

·         Therefore single value can be used to describe the red/green and yellow/blue attributes.

·         L – lightness

·         A – red/green value

·         B – yellow/blue value

·         ‘White’ is used as approximation to all possible color and lighting conditions that might appear in an image.

Color Segmentation

·         Create a kind of color signature of the known background and use it to classify the pixels in the images as those belonging to the signature and those not belonging to the signature.

·         Use two stage k-d tree algorithm

·         To simply divide the given interval into two equally sized sub intervals (instead of splitting the sample set of its median).

·         1 stage:

ü  Approximate clusters are found by building up the tree and stopping when an interval at a node has become smaller than the allowed cluster diameter.

ü  At this point clusters may be split into several nodes.

·         2 stage:

ü  Nodes belong to several clusters are recombined. Another k-d tree clustering is performed using just the cluster centroid from the 1^st stage.

ü  Use different cluster sizes L – 0.64, A – 1.28, B – 2.56

ü  Build the k-d tree and store the interval boundaries in the nodes. Given a certain pixel all that has to be done is to traverse the tree to find out whether it belongs to one of the known background clusters or not.

ü  Another k-d tree is built for known foreground. Each pixel is checked against the known foreground. If it doesn’t belong to either one of the trees, it is assumed to belong to the cluster with the minimum Euclidian distance between the pixel and each cluster’s centroid.

Post processing

ü  Eliminate the background colors that appear in the foreground

ü  Assume the biggest region is the one of user interest and eliminate all other regions.

ü  Confidence matrix – identify the regions that were classified as foreground. 

Applications

The advantage of the algorithm is that its central data structure is efficient and not spatially bounded to a certain picture, like a graph spanned between pixels. Once built, the structure can be reused for subsequent frames in a video.