﻿ Convexity detection with application in saliency.
Convexity detection with application in saliency and attention selection
Figure-ground and perceptual organization can be traced back to the 1920s. Many rules have been found by Gestalt psychologists including convexity, parallelism, symmetry, orientation, surroundedness and object familiarity etc [1,2]. Fig 1 demonstrates the cue of convexity: if there is a boarder line between two neighboring regions, region on the convex side tends to be foreground. In Fig 1(l), borderline between the black vase and white face has similar degree of convexity when seen from two sides, which causes some confusion of which part is foreground. However the black part in Fig 1(r) has much higher convexity than the write one, and people may see the black part as foreground.

Figure 1. (l) face-vace, (r) convexity
Detect convexity
Inspired by this cue, we can compute convexity along object boundaries and assign figure/ground labels for contours and regions. Here we propose a simple algorithm to detect convexity (concave arcs on superpixel boundaries, that is, curves with local maximum concavity). Fig 2 demonstrates a concave arc (yellow curve).

Figure 2. Concave arc.
 Input: Superpixel contour s (clock-wise), concave threshold th Steps: 1.Smooth s using B-spline curve algorithm. 2. Draw bounding-box and split s into four sections. 3. ret = Φ. 4. for each section do 4.1. Determine three main directions in sequence. 4.2. Find starting points of concave arc when pixel movements violate main direction for more than th steps. 4.3. Find ending points of concave arc when pixel movements accord with main direction for more than th steps after string points detected. 4.4. arc = combination of all the pieces in this section. 4.5. ret = ret ∪ arc 5. retuen ret Figure 3. Concave arc detection algorithm.

Overall the computational complexity is O(n), and n equals to the number of pixels on superpixel boundaries. Two solutions exist for calculating convexity including the classic convex hull algorithm and C. Fowlks’s approach in [3]. However the first algorithm is of relative high computational cost O(nlogn), and more importantly, it suffers from the noisiness problem. Meanwhile the second solution aims at assigning probabilities to be foreground for each pixel along object boundaries.

Application in salient object detection
The first and most direct application for convexity detection is salient object detection, which can also be recognized as figure-ground segmentation. In my ICCV2011 paper a hierarchical segmentation model is utilized to merge convexity in different scales of images. Next I use a graph to represent segment pieces and adjust affinity between nodes using information that comes from the detected concave arcs. Finally a graph cut algorithm is performed to obtain figural segment pieces. The framework is shown in Figure 4 below.

Figure 4. Flowchart to detect salient object using convexity.
Experimental results on MSRA SOD dataset demonstrate that performance of this scheme is comparable to state-of-the-art low-level feature-based saliency detection algorithms. Figure 5 illustrates some results.
 IT: L. Itti, C. Koch, and E. Niebur. A model of saliency-based visual attention for rapid scene analysis. TPAMI, 1998. MZ: Y. Ma and H. Zhang. Contrast-based image attention analysis by using fuzzy growing. ACM Multimedia, 2003. GB: J. Harel, C. Koch, and P. Perona. Graph-based visual saliency. NIPS, 2007. SR: X. Hou and L. Zhang. Saliency detection: A spectral residual approach. CVPR, 2007. AC: R. Achanta, F. Estrada, P. Wils, and S. Susstrunk. Salient region detection and segmentation. Computer Vision Systems, 2008. IG: R. Achanta, S. Hemami, F. Estrada, and S. Susstrunk. Frequencytuned salient region detection. CVPR 2009.

Figure 5. Some results. Blue: salient object (region), yellow: background.

Application in attention prediction
 Attention selection differs greatly from image saliency: recent studies have revealed multiple factors for attention selection such as top-town object information, bottom-up feature saliency and figure-ground assignment as well. Therefore we propose to use convexity (Fig 6), symmetry and surroundedness map, and combine figure-ground features with low-level saliency and object detection (basic features and classicifation model described in [4]) so as to predict attention map. Experiments show the effectiveness of figure-ground cues in attention prediction and this work is published in CVPR2012. . Figure 7 illustrates the contribution of different features. Figure 6. Convexity map.

Figure 7. Experimental results.

Papers
Y. Lu, W. Zhang, H. Lu, X. Xue. Salient Object Detection using Concavity Context. 13th IEEE International Conference on Computer Vision (ICCV). Barcelona, Spain. 2011.[PDF]
Y. Lu, W. Zhang, C. Jin, X. Xue. Learning Attention Map from Images. IEEE International Coference on Computer Vision and Pattern Recognition (CVPR). Providence, USA. 2012. [PDF]

Reference
[1] S. Palmer. Vision science: Photons to phenomenology, volume 1. MIT press Cambridge, MA., 1999.
[2] Figure-ground perception. http://www.scholarpedia.org/article/Figure-ground_perception
[3] C. Fowlkes, D. Martin, and J. Malik. Local figure–ground cues are valid for natural images. JOV, 7(8), 2007.
[4] T. Judd, K. Ehinger, F. Durand, and A. Torralba. Learning to predict where humans look. ICCV 2009.
Return