Graph-Based Visual Saliency

Jonathan HarelChristof KochPietro Perona

article2006NeurIPS3,877 citations

Proposes Graph-Based Visual Saliency (GBVS), a biologically plausible attention model that uses Markov chains over graphs for feature activation and normalization to predict human eye fixations with substantially higher accuracy than classical algorithms.

Listen

A new bottom-up visual saliency model called Graph-Based Visual Saliency (GBVS) was developed to predict where humans will fixate when viewing natural images. The work addresses the long-standing challenge of identifying the most informative locations in a scene without top-down guidance, a capability with direct value for image compression, object recognition, and other vision systems that must allocate limited processing resources efficiently.

The authors organized existing saliency methods into three stages—feature extraction, activation map formation, and normalization or combination—and introduced graph algorithms based on Markov chains to handle the second and third stages. They constructed fully connected graphs over feature maps in which edge weights reflected both dissimilarity between locations and spatial proximity; the equilibrium distribution of a random walk on each graph then served as either an activation map or a concentrated saliency map. The approach was tested on 749 modified versions of 108 foliage images that contained 24,149 recorded human fixations, with performance measured by the area under the ROC curve that quantified how well each saliency map predicted fixation locations.

GBVS reached 98 percent of the ROC area achieved by a human-based control and substantially outperformed the classical Itti–Koch algorithms, which reached only 84 percent. Graph-based activation proved more effective than center-surround or self-information methods, while graph-based normalization concentrated activation more reliably than difference-of-Gaussians, max-average, or nonlinear-interaction schemes. The performance advantage arose in part from an emergent center bias that matched human viewing tendencies and from greater robustness when salient regions lay far from object borders.

These results indicate that pairwise contrast and mass-concentration operations computed on graphs can produce saliency maps that align more closely with human attention than the dominant existing techniques. The improvement is large enough to matter for practical systems that rely on accurate prediction of fixation locations, and the method remains simple enough to implement in parallel hardware.

The base model can be extended to multiple spatial resolutions with only modest extra computation, yielding further gains. Additional testing on wider image categories and direct integration into downstream tasks such as recognition or compression would clarify the practical benefit. The present evaluation is limited to a single class of natural scenes and to fixations from a small number of observers, so generalization to other domains or viewing conditions remains to be confirmed.

California Institute of Technology graph-based visual informations graph-based visual saliency saliency maps bottom-up saliency

Harel et al (2006).pdf

Paper: A Model of Saliency-Based Visual Attention for Rapid Scene Analysis, L. Itti et al. (1998). Reading Itti, Koch, and Niebur's pioneering saliency model first provides the foundational bottom-up architecture and biological motivation that the source paper directly extends and improves.

Paper: Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps, Karen Simonyan et al. (2013). This paper builds directly on visual saliency principles by introducing gradient-based saliency maps to interpret and visualize deep convolutional classification models.

Abstract

A new bottom-up visual saliency model, Graph-Based Visual Saliency (GBVS), is proposed. It consists of two steps: first forming activation maps on certain feature channels, and then normalizing them in a way which highlights conspicuity and admits combination with other maps. The model is simple, and biologically plausible insofar as it is naturally parallelized. This model powerfully predicts human fixations on 749 variations of 108 natural images, achieving 98% of the ROC area of a human-based control, whereas the classical algorithms of Itti & Koch ([2], [3], [4]) achieve only 84%.

Topics

graph-based visual informations

Keywords

graph-based visual saliency saliency maps bottom-up saliency visual attention activation maps feature maps center bias

1 Introduction
2 The Proposed Method: Graph-Based Saliency (GBVS)
2.1 Forming an Activation Map (s2)
2.1.1 Existing Schemes
2.1.2 A Markovian Approach
2.2 "Normalizing" an Activation Map (s3)
3 Experimental Results
3.1 Preliminaries and paradigm
3.2 Human Eye-Movement Data on Images of Nature
4 Discussion and Conclusion
Acknowledgments
References

Knowls

Knowl 1 — Markovian Activation Map Computation in Graph-Based Visual Saliency
model/method
In the Graph-Based Visual Saliency (GBVS) framework, the activation map is computed from a raw feature map $M: [n]^2 o \mathbb{R}$ by modeling pairwise dissimilarity over a fully connected directed graph $G_A$ . Every lattice location $(i,j) \in [n]^2$ forms a node connected to all other nodes $(p,q) \in [n]^2$ .

The directed edge from node $(i,j)$ to node $(p,q)$ is assigned weight: $w_1((i,j),(p,q)) = d((i,j) \parallel (p,q)) \cdot F(i-p, j-q)$ where the dissimilarity $d((i,j) \parallel (p,q))$ is defined as either the logarithmic ratio or absolute difference: $d((i,j) \parallel (p,q)) = \left| \log \frac{M(i,j)}{M(p,q)} \right| \quad \text{or} \quad |M(i,j) - M(p,q)|$ and the spatial proximity kernel is: $F(a,b) = \exp\left(-\frac{a^2 + b^2}{2\sigma^2}\right)$ where $\sigma$ is a free spatial spread parameter (typically set to one-tenth to one-fifth of the map width).

A discrete-time Markov chain is constructed on $G_A$ by normalizing outbound edge weights from each node to sum to $1$ : $P_A((i,j) \to (p,q)) = \frac{w_1((i,j),(p,q))}{\sum_{(u,v)} w_1((i,j),(u,v))}$ Because $G_A$ is strongly connected and positive, the Markov chain is ergodic and possesses a unique stationary distribution $\pi$ . This distribution corresponds to the principal eigenvector of $P_A$ and is computed via power iteration in $O(n^4 K)$ operations, where $K \ll n^2$ is the number of iterations to convergence. The resulting equilibrium probability mass $\pi(i,j)$ defines the activation value $A(i,j)$ , naturally accumulating mass at nodes possessing high contrast relative to their spatial neighborhood.
Knowl 2 — Markovian Normalization and Mass Concentration on Activation Maps
model/method
To concentrate mass on salient peaks before feature combination, GBVS uses a graph-based normalization step. Given an activation map $A: [n]^2 \to \mathbb{R}$ , a fully connected directed graph $G_N$ is constructed with $n^2$ nodes corresponding to the lattice indices $[n]^2$ . For each directed edge from node $(i,j)$ to node $(p,q)$ (including self-loops $(i,j) = (p,q)$ ), the weight is defined as: $w_2((i,j),(p,q)) = A(p,q) \cdot F(i-p, j-q)$ where $F(a,b) = \exp\left(-\frac{a^2 + b^2}{2\sigma^2}\right)$ is a Gaussian spatial proximity penalty with spread parameter $\sigma$ .

Normalizing outbound edge weights to 1 yields the transition matrix of a Markov chain: $P_N((i,j) \to (p,q)) = \frac{w_2((i,j),(p,q))}{\sum_{(u,v)} w_2((i,j),(u,v))}$ The equilibrium distribution (principal eigenvector) of $P_N$ concentrates mass into regions of high activation surrounded by high activation. This normalization operation can be applied iteratively $\kappa$ times (typically $\kappa \in \{2, 3, 4\}$ ) to produce the final normalized activation map $\hat{A}$ .
Knowl 3 — Graph-Based Visual Saliency Pipeline
algorithm
The Graph-Based Visual Saliency (GBVS) algorithm computes a bottom-up saliency map from an input image through feature extraction, Markovian activation map generation, Markovian normalization, and map combination.
Input: Input image $I$ , spatial scales $S = \{1/2, 1/4\}$ , orientations $\Phi = \{0^\circ, 45^\circ, 90^\circ, 135^\circ\}$ , spatial spread parameter $\sigma$ , normalization iterations $\kappa$ .
Output: Master saliency map $S_{\text{master}}$ .
1. Feature Extraction:
   Compute raw feature maps $M_k$ :
   - For each scale $s \in S$ and angle $\phi \in \Phi$ , extract orientation feature maps using Gabor filters.
   - For each scale $s \in S$ , extract local contrast map via luminance variance in an $80 \times 80$ neighborhood.
   - Extract raw luminance grayscale map.
   - Resample all 12 feature maps to a uniform low resolution $[n] \times [m]$ (e.g., $25 \times 37$ ).
2. Graph-Based Activation:
   For each raw feature map $M_k$ :
   - Construct fully connected graph $G_A$ on lattice $[n] \times [m]$ .
   - Assign edge weights $w_1((i,j),(p,q)) = |\log(M_k(i,j)/M_k(p,q))| \cdot \exp(-((i-p)^2 + (j-q)^2)/(2\sigma^2))$ .
   - Normalize outbound edge weights from each node $(i,j)$ to sum to 1, forming transition matrix $P_A$ .
   - Compute principal eigenvector $\pi_A$ of $P_A$ using power iteration.
   - Assign activation map $A_k(i,j) = \pi_A(i,j)$ .
3. Graph-Based Normalization:
   For each activation map $A_k$ :
   - Set $\tilde{A} \leftarrow A_k$ .
   - for step $= 1$ to $\kappa$ :
       - Construct graph $G_N$ with edge weights $w_2((i,j),(p,q)) = \tilde{A}(p,q) \cdot \exp(-((i-p)^2 + (j-q)^2)/(2\sigma^2))$ .
       - Normalize outbound edge weights to obtain transition matrix $P_N$ .
       - Compute principal eigenvector $\pi_N$ of $P_N$ using power iteration.
       - Update $\tilde{A} \leftarrow \pi_N$ .
   - Let $\hat{A}_k = \tilde{A}$ .
4. Map Combination:
   - Form master saliency map $S_{\text{master}} = \sum_k \hat{A}_k$ .
   - return $S_{\text{master}}$
Knowl 4 — Three-Stage Decomposition of Bottom-Up Visual Saliency Models
definition
Bottom-up visual saliency algorithms can be structured into three modular, sequentially executed stages:
1. (s1) Extraction: Extract low-level visual feature vectors (such as color, luminance, orientation, and local contrast) across spatial coordinates over the image plane.
2. (s2) Activation: Process feature channels to construct activation maps highlighting conspicuous local variations or unusual features relative to their visual context.
3. (s3) Normalization and Combination: Apply a mass-concentrating normalization operator to each individual activation map to suppress uniform maps and amplify prominent peaks, followed by summing or combining normalized maps across channels and scales into a single master saliency map.
Knowl 5 — Multiresolution Graph-Based Visual Saliency Extension
model/method
To represent multiresolution features within a single graph framework, GBVS extends activation and normalization to multiresolution representations (GBVSM). Given a multi-scale collection of maps $\{A_k\}$ , where each map $A_k: [n_k]^2 \to \mathbb{R}$ represents the same underlying visual feature at resolution $n_k \times n_k$ , a single unified graph is constructed containing a node for every coordinate in every resolution map.

To compute edge weights via the spatial distance kernel $F(a,b) = \exp(-(a^2 + b^2)/(2\sigma^2))$ between nodes originating from different resolution grids:
1. Each node in map $A_k$ is mapped to the set of spatial pixel locations corresponding to its spatial support footprint in the highest-resolution map coordinate frame.
2. The distance between two nodes across maps is defined as the mean pairwise Euclidean distance between their corresponding sets of highest-resolution spatial support locations.
Transitions and equilibrium stationary distributions are computed across all scale levels simultaneously, allowing cross-scale saliency interactions with minimal added computational cost.

Knowl 6 — Fixation Prediction Benchmark on Natural Images

data/table

GBVS was evaluated against established saliency models on 749 image variations derived from 108 natural foliage scenes, using eye-movement tracking data consisting of 24,149 human fixations (with 3 subjects per image). Performance is evaluated as the ratio of the model's Receiver Operating Characteristic Area Under Curve (ROC AUC) for predicting human fixation points to the inter-subject human control ROC AUC (where fixations of 2 subjects predict the fixations of the remaining subject).

In the model configurations below, graph (i) uses $\sigma = 2.5$ , graph (ii) uses $\sigma = 5.0$ , graph (iii) uses an adaptive stopping rule based on local maxima of convergence iterations, graph (iv) stops normalization after 4 iterations, and I denotes the identity operator (no normalization).

Activation Algorithm	Normalization Algorithm	ROC Area (Fraction of Human Control)
graph (ii)	graph (iv)	0.981148
graph (i)	graph (iv)	0.975313
graph (ii)	Identity (I)	0.974592
graph (ii)	ave-max	0.974578
graph (ii)	graph (iii)	0.974227
graph (i)	graph (iii)	0.968414
self-info [Bruce Tsotsos]	Identity (I)	0.841054
center-surround (c-s) [Itti Koch]	Difference-of-Gaussians (DoG)	0.840968
center-surround (c-s) [Itti, Koch, Niebur]	ave-max	0.840725
center-surround (c-s) [Lee, Itti, Koch, Braun]	Nonlinear interactions (NL)	0.831852

The full graph-based model (graph (ii) + graph (iv)) achieves 98.1% of the human control performance, substantially outperforming classic center-surround and self-information methods (~83%–84%).

Knowl 7 — Explanatory Factors for GBVS Performance: Emergent Center Bias and Border Invariance
empirical result
Two primary computational mechanisms explain why GBVS outperforms classical visual saliency models given identical input features:
1. Emergent Center Bias: Because lattice nodes in a bounded plane are on average spatially closer to central nodes than to any peripheral node, random walks over $G_A$ and $G_N$ with distance penalty $F$ inherently accumulate stationary mass toward the image center, even for uniform inputs. Pointwise multiplying the master saliency maps of standard algorithms (e.g., center-surround with Difference-of-Gaussians or max-average normalization) by the GBVS-induced center bias improves their predictive power, explaining between 20% (for DoG) and 90% (for max-average) of the performance gap, while GBVS still maintains superior performance.
2. Robustness to Salient Region Interior: Classic center-surround (c-s) subtractions and local self-information algorithms activate almost exclusively along object borders, failing to highlight the interior of large salient regions distant from boundaries. In contrast, fully connected graph-based contrast integrates pairwise dissimilarity globally with Gaussian spatial decay, reliably highlighting whole salient regions regardless of distance from borders.

Coverage note — None was omitted; all key contributions (the 3-stage taxonomy, Markovian activation, Markovian normalization, full GBVS algorithm, multiresolution extension GBVSM, empirical benchmark results, and explanatory analysis) are covered.

References

1.W. Einh‰user, W. Kruse, K.P. Hoffmann, & P. Kˆnig "Differences of Monkey and Human Overt Attention under Natural Conditions", Vision Research 2006.
2.L. Itti, C. Koch, & E. Niebur "A model of saliency based visual attention for rapid scene analysis", IEEE Transactions on Pattern Analysis and Machine 1998
3.L. Itti & C. Koch "A saliency-based search mechanism for overt and covert shifts of visual attention", Vision Research, 2000
4.L. Itti, & P. Baldi "Bayesian Surprise Attracts Human Attention", NIPS*2005
5.N. Bruce & J. Tsotsos "Saliency Based on Information Maximization", NIPS*2005
6.L.F. Costa "Visual Saliency and Attention as Random Walks on Complex Networks", arXiv preprint 2006
7.G. Boccignone, & M. Ferraro "Modelling gaze shift as a constrained random walk", Physica A 331, 207 2004
8.D. Brockmann, T. Geisel "Are human scanpaths Levy ﬂights?", ICANN 1999
9.D. Parkhurst, K. Law, & E. Niebur "Modeling the role of salience in the allocation of overt visual attention", Vision Research, 2002
10.D.K. Lee, L. Itti, C. Koch, & J. Braun "Attention activates winner-take-all competition among visual features", Nature Neuroscience, 1999
11.L. Itti, J. Braun, D.K. Lee, & C. Koch "Attention Modulation of Human Pattern Discrimination Psychophysics Reproduced by a Quantitative Model", NIPS*1998
12.W. Einh‰user & P. Kˆnig, "Does luminance-contrast contribute to saliency map for overt visual attention?", Eur. J. Neurosci. 2003
13.U. Rutishauser, D. Walther, C. Koch, & P. Perona "Is bottom-up attention useful for object recognition?", CVPR 2004
14.B.W. Tatler, R.J. Baddeley, & I.D. Gilchrist "Visual correlates of ﬁxation selection: Effects of scale and time." Vision Research 2005
15.J. Malik & P. Perona "Preattentive texture discrimination with early vision mechanisms" Journal of the Optical Society of America A 1990

Citation

MLA

Harel, J., et al. “Graph-Based Visual Saliency”. Advances in Neural Information Processing Systems 19, The MIT Press, 2007, pp. 545–52, https://doi.org/10.7551/mitpress/7503.003.0073.

APA

Harel, J., Koch, C., & Perona, P. (2007). Graph-Based Visual Saliency. In Advances in Neural Information Processing Systems 19 (pp. 545–552). The MIT Press. https://doi.org/10.7551/mitpress/7503.003.0073

Chicago

Harel, J., C. Koch, and P. Perona. 2007. “Graph-Based Visual Saliency”. In Advances in Neural Information Processing Systems 19. The MIT Press. https://doi.org/10.7551/mitpress/7503.003.0073.

Harvard

Harel, J., Koch, C. and Perona, P. (2007) “Graph-Based Visual Saliency”, Advances in Neural Information Processing Systems 19. The MIT Press, pp. 545–552. Available at: https://doi.org/10.7551/mitpress/7503.003.0073.

Vancouver

1. Harel J, Koch C, Perona P (2007) Graph-Based Visual Saliency. In: Advances in Neural Information Processing Systems 19. The MIT Press, pp 545–552

BibTeX

@inbook{Harel_2007, title={Graph-Based Visual Saliency}, ISBN={9780262256919}, url={http://dx.doi.org/10.7551/mitpress/7503.003.0073}, DOI={10.7551/mitpress/7503.003.0073}, booktitle={Advances in Neural Information Processing Systems 19}, publisher={The MIT Press}, author={Harel, Jonathan and Koch, Christof and Perona, Pietro}, year={2007}, month=Sept, pages={545–552} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Graph-Based Visual Saliency

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Markovian Activation Map Computation in Graph-Based Visual Saliency

Knowl 2 — Markovian Normalization and Mass Concentration on Activation Maps

Knowl 3 — Graph-Based Visual Saliency Pipeline

Knowl 4 — Three-Stage Decomposition of Bottom-Up Visual Saliency Models

Knowl 5 — Multiresolution Graph-Based Visual Saliency Extension

Knowl 6 — Fixation Prediction Benchmark on Natural Images

Knowl 7 — Explanatory Factors for GBVS Performance: Emergent Center Bias and Border Invariance

References

Citation

BibTeX

Access the Paper