In several image processing papers, and for instance in Random Walks for Image Segmentation (2006) by Leo Grady, changes in image intensities are turned into edge weights. In some fields, it is called Geographically Weighted Regression. This applies to graphs too, and has become popular for instance in non-local means denoising algorithms. A popular weighting is Gaussian. Quoting Grady (Equation 1, page 1772):

In this work, we have preferred (for empirical reasons) the typical Gaussian weighting function given by: $$ w_{ij} = \exp{\left(-\beta(g_i-g_j)^2\right)} $$ where $g_i$ indicates the image intensity at pixel $i$

My questions are:

  • what are the earliest/most authoritative references for such a typical Gaussian weighting?
  • since Gaussian models are not considered the most appropriate for structured image modelling, what are the non-trivial "empirical" benefits of such a weighting, with respect to, eg, a near-Gaussian bisquare function? $$w_{ij} = (1-\beta(g_i-g_j)^2)^2$$
  • 1
    $\begingroup$ I'm obviously no expert on image segmentation, but wouldn't using a $\beta$ in the exponent practically allow to integrate gamma correction into the weight calculation? $\endgroup$ – Marcus Müller Jan 15 '17 at 9:30
  • $\begingroup$ An interesting comment. So far, I thought of it as a scale parameter, to promote interaction between close pixel values that could belong to the same almost flat areas $\endgroup$ – Laurent Duval Jan 15 '17 at 10:04
  • 1
    $\begingroup$ hm, yeah, that makes "empirically" sense :) Also, maybe the Gaussian-shaping comes from the information theory idea that Gaussian-distributed noise has the highest differential entropy, but I'm not sure how that would help you $\endgroup$ – Marcus Müller Jan 15 '17 at 10:14
  • $\begingroup$ I shall had some bits found in early papers by Perona etc. They draw some connexions with robust statistics, using Tukey biweight functions for instance $\endgroup$ – Laurent Duval Jan 15 '17 at 10:18
  • 2
    $\begingroup$ For your second question, I would suggest that the Gaussian is an oversimplification of the contribution of each pixel to its neighbours. An oversimplification of the typical sinc that is supposed to be centred on each pixel, for "sampled reconstruction" to work. Smooth image, low freqs, small grads, higher prob to "walk" to neighbour. At the scales involved, Gaussian is probably "good enough" to provide edge weights. $\endgroup$ – A_A Jan 15 '17 at 11:19

Maybe not an exact answer, but I'll to give a direction.

What you are using is essentially an RBF-Kernel. First, it has a ready interpretation as a similarity measure (satisfies Mercer's conditions). In essence, other such kernels can be used. For instance, an inner product (linear kernel) would define an angular distance between pixels/features. For a deeper understanding, I would dive in the literature of kernels.

Having said that, the simplest form of such relations are called inverse distance weighting (Grady could have used this as well), where any identity like $1/d(g_i, g_j)^p$ can be used. These methods also cover a wide spectrum.

| improve this answer | |
  • $\begingroup$ Bringing the Mercer conditions back, and linking to Gaussian RBF is a good point. $\endgroup$ – Laurent Duval Sep 10 '17 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.