Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
It would help if you added a link or a reference to the article you are reading. –  Rahul Jan 5 '12 at 1:54
    
people.rit.edu/~esseee/TIP%20_Published.pdf (background part) –  kspacja Jan 5 '12 at 2:00
add comment

1 Answer

up vote 1 down vote accepted

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?

share|improve this answer
    
Okay, first: ...this is equivalent to maximizing $u^TD^TDu$, which is in turn given by the largest eigenvector of $D^TD$. This is something what I can't understand. How the largest eigenvector of $D^TD$ corresponds to maximazing $u^TD^TDu$? –  kspacja Jan 5 '12 at 11:54
    
@kspacja, please see my edit. –  Rahul Jan 5 '12 at 13:04
    
Okay, now I understand little bit better, but I have to devote time to understand this completely, but you helped me a lot. But I have one question more. I have got these everything information, but I still don't know what operation and how I have to do on a digital image. What conculsion do I have take from this cosideration and use them to implement edge detection? –  kspacja Jan 5 '12 at 14:56
    
For example: how make differentiate operation on descrete space like digital image? I heard that something with filter and convolution, but I still don't know how to build filter using information from this cosideration. –  kspacja Jan 5 '12 at 15:02
    
@kspacja, Wikipedia lists some standard approaches. The basic idea is that you can estimate, say, the $x$-component of gradient at a given pixel by finding the difference between the image values at nearby pixels to the left and right of it. –  Rahul Jan 5 '12 at 15:16
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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