5
$\begingroup$

Feature detection is an essential task in low-level vision.

Good features are those that resist to different perturbations such as

  • noise addition,
  • blur,
  • geometric transforms (3D rotation with perspective, scaling),
  • radiometric transforms (monotonic or non-monotonic grayscale remapping).

By resistance, I mean that despite those alterations, the same features will continue to be detected.

My question is how can we mathematically express these types of resistance in general terms ? What would be the form of the equations, assuming grayscale images and features defined from the pixel values in a region of arbitrary shape ? (I am not asking for an assessment of the stability of known features described in the literature.)

Answering the question for a 1D signal would already be a good start.

Can anyone help ?

| improve this question | |
$\endgroup$
  • $\begingroup$ A quite fundamental question. How would you ponder that: 1) a good feature is good as long you already know it is good (prior knowledge) 2) little changes can affect detection (adversarial attack in deep learning, but I'm sure we humans are affected too) $\endgroup$ – Laurent Duval Dec 30 '16 at 22:13
  • $\begingroup$ @LaurentDuval: I don't want "good" features. I want stable ones, in the sense explained in the post. At the border little changes will indeed affect detection. What I want is large detection basins. $\endgroup$ – Yves Daoust Dec 31 '16 at 14:02
  • $\begingroup$ Understood. I was starting from "Good features are those that...". I think that a lot of stuff happens between dimension 1 and 2: singular along the normal, regular in the orthogonal direction. Can you restrict the class of objects you are interested in? $\endgroup$ – Laurent Duval Dec 31 '16 at 14:07
  • $\begingroup$ Did you already elaborate from Canny versions of what an edge can be? $\endgroup$ – Laurent Duval Dec 31 '16 at 14:08
  • $\begingroup$ @LaurentDuval: no, my idea is to find analytical ways to express robustness a priori, and from there derive which features are interesting. $\endgroup$ – Yves Daoust Dec 31 '16 at 14:50
1
$\begingroup$

Without being an expert in the image processing field there is something that comes to mind that maybe could point you in the right direction. Usually we express a feature as a number, to which we assign an estimator, which is a random variable, with some probability distribution (for which we normally care about mean value and variance). If we take the noise example which i think is the easier. You could try to express this resistance in term of the variation of the probability distribution of the feature estimator given the perturbing noise source. Let the output of your estimator for the feature be the random variable $\mathbf{X}$, and let the noise be characterized by $\mathbf{Y}$. Some measure of the resistance could be $\frac{P(\mathbf{X})}{P(\mathbf{X}|\mathbf{Y})}$. If this value is close to one, then the feature would be resistent to perturbations by noise, if it is not then it won't be. Maybe you could define a function of this to adjust the values to be more significant. For the other transformations such as rotation, scaling etc, you could use the same but do $\frac{P(\mathbf{X})}{P(\mathbf{f(X)})}$, where $f(\mathbf{X})$ denotes the transformation of the random variable that characterizes the estimator when you apply the rotation to the image. Of course, I think this $f()$ would be very hard to find in general but perhaps if the feature is not hard to estimate you can do some math and some change of variable and arrive at closed expressions for it.

Hope this helps.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Your answer led me to new insights that you might be interested to see. $\endgroup$ – Yves Daoust Dec 15 '15 at 12:16
1
$\begingroup$

Based on the interesting suggestion of @bone, I made further investigations, too long for a comment. They are based on a very simple model.

Let an 1D signal with a step edge, i.e. values 0 followed by values 1. We want to try a linear decision criterion of the form

$$av_0+bv_1\ge1,$$

where $v_0$ and $v_1$ are the values of two neighboring pixels, and $a,b$ are two coefficients to be determined.

On the edge we have $v_0=0, v_1=1$ in the absence of noise, and the edge is detected when $b\ge1$. False detections occur when $v_0=v_1=1$ and $a+b\ge1$.

With Gaussian noise added we have

$$av_0+N(0;a\sigma)+bv_1+N(0;b\sigma)=av_0+bv_1+N(0;\sqrt{a^2+b^2}\sigma)\ge1.$$

So we should ensure

$$N(b;\sqrt{a^2+b^2}\sigma)\ge1,\\ N(a+b;\sqrt{a^2+b^2}\sigma)\le1$$ as often as possible.

More precisely, if there are $N=N_0+N_1$ samples, the probability of being on an edge is $\frac1N$ and that of being on the step is $\frac{N_1}{N}$.

Then we want to maximize the probability of correct detection

$$\frac1NP(N(b;\sqrt{a^2+b^2}\sigma)\ge1)+\frac{N_1}NP(N(a+b;\sqrt{a^2+b^2}\sigma)\le1),$$

or

$$ \frac1N\text{erf}(\frac b{\sqrt{a^2+b^2}\sigma})+ \frac{N_1}{N}\text{erfc}(\frac{a+b}{\sqrt{a^2+b^2}\sigma}).$$

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have doubts about the final solution, as it implies proportionality of $a$ and $b$. $\endgroup$ – Yves Daoust Dec 15 '15 at 12:15
  • $\begingroup$ Could you post some graphical results of your analysis? It is not really clear to me how you arrive at the expressions for the estimator. Perhaps something with a simple image. Maybe that would make it more clear for other people to provide other suggestions. $\endgroup$ – bone Dec 15 '15 at 15:02
  • $\begingroup$ @bone: the choice of the estimator is empirical. The idea is to form a function of two successive values and compare it to a decision threshold. As a first attempt, the function is a linear combination. (This is inspired from the computation of the gradient - first order difference - that has a maximum response at the edge; but leaving adjustable coefficients to see what weighting can be optimal; hopefully, this can be later extended to a larger convolution). $\endgroup$ – Yves Daoust Dec 15 '15 at 16:26

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.