What do eigenvalues have to do with pictures?

I am trying to write a program that will perform OCR on a mobile phone, and I recently encountered this article :


article excerpt


Can someone explain this to me ?

Answer

J.M. has given a very good answer explaining singular values and how they’re used in low rank approximations of images. However, a few pictures always go a long way in appreciating and understanding these concepts. Here is an example from one of my presentations from I don’t know when, but is exactly what you need.

Consider the following grayscale image of a hummingbird (left). The resulting image is a $648\times 600$ image of MATLAB doubles, which takes $648\times 600\times 8=3110400$ bytes.

enter image description here
enter image description here

Now taking an SVD of the above image gives us $600$ singular values that, when plotted, look like the curve on the right. Note that the $y$-axis is in decibels (i.e., $10\log_{10}(s.v.)$).

You can clearly see that after about the first $20-25$ singular values, it falls off and the bulk of it is so low, that any information it contains is negligible (and most likely noise). So the question is, why store all this information if it is useless?

Let’s look at what information is actually contained in the different singular values. The figure on the left below shows the image recreated from the first 10 singular values ($l=10$ in J.M.’s answer). We see that the essence of the picture is basically captured in just 10 singular values out of a total of 600. Increasing this to the first 50 singular values shows that the picture is almost exactly reproduced (to the human eye).

So if you were to save just the first 50 singular values and the associated left/right singular vectors, you’d need to store only $(648\times 50 + 50 + 50\times 600)\times 8=499600$ bytes, which is only about 16% of the original! (I’m sure you could’ve gotten a good representation with about 30, but I chose 50 arbitrarily for some reason back then, and we’ll go with that.)

enter image description here
enter image description here

So what exactly do the smaller singular values contain? Looking at the next 100 singular values (figure on the left), we actually see some fine structure, especially the fine details around the feathers, etc., which are generally indistinguishable to the naked eye. It’s probably very hard to see from the figure below, but you certainly can in this larger image.

enter image description here
enter image description here

The smallest 300 singular values (figure on the right) are complete junk and convey no information. These are most likely due to sensor noise from the camera’s CMOS.

Attribution
Source : Link , Question Author : Patryk , Answer Author : Community

Leave a Comment