1
$\begingroup$

Could you explain me how eigenvector helps with compute gradient and how make differentiate operation on descrete space like digital image?

I know that this question is so connected with computer science, but I know from my exprience that things like that mathematicians know better.

If it will help, I try to learn something about image segmenatation and the first step in algorithm (from one science article) is edge detection, which is based on gradient calculated using the eigenvector.

  • 0
    http://people.rit.edu/~esseee/TIP%20_Published.pdf (background part)2012-01-05

1 Answers 1

2

For a scalar-valued function $f\colon \mathbb R^n \to \mathbb R$, such as a black-and-white image, the gradient vector $\nabla f = (\partial f/\partial x_1, \ldots, \partial f/\partial x_n)^T$ tells you how $f$ changes in the neighborhood of $x$. That is, to first order, a small change in position $\Delta x$ leads to a corresponding change $\nabla f(x) \cdot \Delta x$ in the value of the function.

If $f$ is a vector-valued function $\mathbb R^n \to \mathbb R^m$ instead, such as a colour image, the natural generalization of the gradient is the Jacobian matrix, which your paper denotes $D$. Here if $x$ changes by $\Delta x$, the value of $f$ changes by approximately $D \Delta x$. To be clear, $\Delta x$ is a vector in the domain $\mathbb R^n$ (the image plane), while $D \Delta x$ a vector in the range $\mathbb R^m$ (the image's colour space).

In this paper, the gradient is being used only to find the direction in which the function $f$ changes most rapidly. If $f$ is scalar-valued, this is simply the direction parallel (or antiparallel) to $\nabla f$, as one can show by finding the unit vector $u$ which maximizes $\lvert \nabla f \cdot u\rvert$. If $f$ is vector-valued instead, one wants to find the unit vector $u$ which maximizes the magnitude of change, $\lVert Du\rVert$. But since $\lVert Du \rVert = \sqrt{(Du)^TDu}$, this is equivalent to maximizing $u^TD^TDu$, which is in turn given by the largest eigenvector of $D^TD$.

To see why, let's give the matrix in question a name, $A = D^TD$. Since it is symmetric, it has a full set of real eigenvalues $\lambda_i$ and corresponding eigenvectors $v_i$ that are all orthogonal. Now the action of $A$ is very simple in the basis of these eigenvectors; it simply stretches each basis vector by its eigenvalue, $Av_i = \lambda_i v_i$. So intuitively, if you want to pick a unit vector that gets stretched the most, you should pick to lie along the eigenvector with the largest eigenvalue. More explicitly, if we express our unit vector $u$ in this basis, $u = \alpha_1 v_1 + \cdots + \alpha_n v_n$, then a little algebra reveals that $u^TAu = \lambda_1 \alpha_1^2 + \cdots + \lambda_n \alpha_n^2$. As $u$ is a unit vector, $\alpha_1^2 + \cdots + \alpha_n^2 = 1$; now what should the $\alpha_i^2$ be to maximize the previous expression?

  • 0
    I don't have any first-hand knowledge of good sources, but Googling "image processing course" turns up a lot of hits. Many of them seem to have lecture notes.2012-01-05