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

2.8k Views Asked by At

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.

1

There are 1 best solutions below

6
On BEST ANSWER

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?