A Baseline Statistical Method For Robust User-Assisted Multiple Segmentation

In image segmentation the aim is to assign a label to every image pixels in a way that the pixels with the same labels exhibit similar or unique properties. These properties can be low-level features such as color and texture or high-level semantic descriptions.

Image segmentation, in general, is a challenging problem. Therefore, depending upon the target application and specifications there exist several approaches to segmentation that differ in capabilities and limitations [1]. To ease this non-trivial task, recently numerous methods that accept and utilize different types of user assistance have been developed. For example in Graph Cuts [2], Random Walk [3] and their many variants [4, 5, 6, 7, 8, 9, 10, 11, 12], the user inputs are seed points or scribbles. In GrabCut [13] and its variants [14, 15, 16, 17] the user inputs are bounding boxes where these methods may also incorporate additional user inputs to refine the segmentation process. A detailed survey on user-assisted segmentation methods can be found in [18].

The variant algorithms cited above are often developed with the intention of improving the performance of the original method [4, 5, 6, 7, 9, 8, 16, 11], decreasing or easing the human interaction [16, 10, 7, 15, 8] or providing robustness to the user input [5, 14, 15, 12]. However, a great majority of these methods are limited to binary, i.e. foreground and background, segmentation. Besides, due to their construction and inherent operating mechanism, they work best under a specific input type and their performances improve with the amount or the precision of the user inputs. Therefore, it becomes quite difficult to assess the relative performance improvements of these methods within a unified framework. This difficulty only increases if their varying complexities are taken into the assesment picture.

With the intention of providing a common ground to different user assisted segmentation methods, we present a novel, minimalistic, multiple segmentation algorithm based on robust hypothesis testing [19, 20] and specifically the DGL test [21, 22, 23]. Being algorithmically simple, robust to different input types and requiring a complexity that is linear in the number of pixels, the proposed method is suitable to be used as a baseline method for quick benchmarking purposes. The main contributions of this paper are:

1) We show that one can take advantage of the inherent robustness of the DGL test in user-assisted image segmentation. Some user input types that we consider are:

i) a fraction of labeled pixels within ground truths masks or bounding boxes

ii) randomly selected seed points within ground truths masks

iii) randomly perturbed bounding boxes

2) The proposed method is algorithmically simple and can be coded with around 30 Matlab sentences. It can be efficiently implemented with a time complexity that is linear in the number of pixels and quadratic in the number of image labels.

3) We provide a mathematical analysis on the operation of the proposed method.

4) We present simulations on Berkeley’s BSDS 500 database [24] that validate the robust operation of the proposed method.

5) In addition to the initial user input, the increases in the accuracy of the proposed method per additional user inputs can easily be benchmarked where the accuracy can be increased arbitrarily.

The proposed segmentation method is evaluated on the test images of Berkeley’s BSDS 500 database [24]. This set consists of 200 natural RGB images with multiple ground truth annotations. The images have sizes $321\times 481$ where each color intensity is represented with 8 bits i.e. $|{\cal X}|=256^{3}$. As an accuracy measure we have considered intersection over union (IoU) which is the ratio of correctly labeled pixels to all labeled pixels (we considered 90% of the labeled pixels due to oversegmentations in images). We have estimated IoU by averaging it over multiple images and multiple ground truths.

Let GT_i and BB_i, $i=1,2,...,M$, denote the ground truth masks and (tight) bounding boxes of $\Omega_{i}$. First, we have formed ${\cal T}_{i}$ from a percentage $f\%$, $f\in\{25,50,75,100\}$, of randomly selected labeled pixels from GT_i and BB_i. We denote these methods by DGL${}_{GT}^{f\%}$ and DGL${}_{BB}^{f\%}$, respectively. Next, we have considered the case where $t$, $t\in\{10,15,20\}$, random pixels seeds in $\Omega_{i}$ are selected and the case where bounding boxes are perturbed by $p\%$, $p\in\{5,10,15\}$. These methods are denoted by DGL${}_{GT}^{t\hskip 1.0ptpts}$ and DGL${}_{BB}^{p\%pt}$, respectively. In the former, ${\cal T}_{i}$ is constructed from the pixels within a square whose center is the seed point in $\Omega_{i}$ and whose side-length is $l$ (we used $l$=50 for BSDS images). In the latter approach, the two corner points, ($r_{1},c_{1}$), ($r_{2},c_{2}$), of bounding boxes that touch the diagonal are uniformly perturbed $p\%$ to obtain ($\hat{r}_{1},\hat{c}_{1}$), ($\hat{r}_{2},\hat{c}_{2})$, respectively. Here, $\hat{r}_{1}$ is selected uniformly over $[r1-\frac{(r_{2}-r_{1})p}{200},r1+\frac{(r_{2}-r_{1})p}{200}]$ and we followed the same approached to obtain $\hat{c}_{1},\hat{r}_{2}$ and $\hat{c}_{2}$.

The implementation of the proposed algorithm in RGB color space requires a memory proportional to $M^{3}\times 256^{3}$ which becomes unpractical for images with $M>10$. Thus, we used dimensionality reduction by implementing the proposed algorithm in the HSV color space and considering only H and S components of the image. This approach has the advantage of decoupling the chromatic information from the shading effect [27, 1] and the resultant algorithm showed negligible performance degradation when $|{\cal X}_{1}|=|{\cal X}_{2}|=1024$ where ${\cal X}_{1}$ and ${\cal X}_{2}$ correspond to equidistant bins for H and S components, respectively. The performance of this approach is demonstrated in Figure 3 for two relatively difficult images where we have used the SLIC framework [25] with $K=500$ superpixels. Inspecting the images we observe that mislabeling occurs when i) regions with similar intensity distributions are annotated differently due to the presence of a contour e.g. the sky in the top image and tree branches in the bottom image ii) the intensity distributions mix while construction ${\cal T}_{i}$ in DGL${}_{GT}^{t\hskip 1.0ptpts}$, DGL${}_{BB}^{f\%}$ and DGL${}_{BB}^{p\%pt}$ e.g. the mislabeled superpixels in the body and in the wing of the mother bird.

For benchmarking we have reduced the alphabet size and used the algorithm with $|{\cal X}_{1}|=|{\cal X}_{2}|=\sqrt{321\times 482}\approx 392$ so that it has linear complexity in the number of pixels. This reduction resulted in some degradation, around 3%-5%, in the accuracy. We have also investigated the effect of additional user inputs by assuming a genie-aided user optimally relabels the mislabeled (or partially mislabeled) superpixels which can be performed by at most two point clicks per superpixel. With this approach, the amount of increase in the accuracy per additional user inputs (clicks) can be easily calculated during benchmarking without actually performing the corrections.

The simulation results are presented in Figure 4. Recall that ${\cal T}_{i}$ consists of labeled pixels from $\Omega_{i}$ in DGL${}_{GT}^{f\%}$, therefore DGL${}_{GT}^{100\%}$ exhibits the ultimate performance of the proposed method. Inspecting Figure 4, we observe that the performances of DGL${}_{GT}^{100\%}$, DGL${}_{GT}^{75\%}$ and DGL${}_{GT}^{50\%}$ are almost the same and one can reach an initial segmentation accuracy around 0.9 when only half of the labeled pixels in ground truths masks are provided by the user. This performance is promising given the simplicity of the proposed method. As expected from the discussion in Section 2C, the performance deteriorates in DGL${}_{BB}^{f\%}$, DGL${}_{GT}^{t\hskip 1.0ptpts}$ and DGL${}_{BB}^{p\%pt}$. However, this deterioration is consistent in each of the considered user input type which indicates the robustness of the proposed method.

We have presented a novel, user-assisted, multiple segmentation method based on DGL testing procedure. The proposed method is shown to be robust when used with different user input types such as labeled pixels and seeds from ground truth masks or bounding boxes that may be perturbed. Having linear time complexity in the number of pixels and requiring minimal coding, around 30 lines, the proposed method is suitable for fast benchmarking purposes. In this work, we have only utilized the empirical distributions, i.e. histograms, in the user input regions. Including the spatial information of these regions, e.g. as in [28], in the DGL test may improve the performance of the proposed method and is the topic of our future work.