Zebras Lurking in...a Matrix!

In our connected world, pictures and videos are everywhere. Of course, no one likes waiting for a giant picture to download - and you shouldn’t have to! This is where image compression comes in.

A zebra is a classic example of something that is black and white. We could take a picture of one, and turn it into a matrix of 0’s and 1’s. If we wish to shrink the file size, we could crudely average out blocks of 2x2 pixels, and then assign them a color as a single data value:

This may shrink the file size dramatically, but the visual information lost is substantial.

Is there a better way? The answer is certainly yes, and one approach is an application of linear algebra. It turns out that reducing file size can be viewed as approximating a matrix by one of lower rank. We can start by looking at shapes, such as disks, annuli and triangles, and begin to see what the rank of such a matrix of 0’s and 1’s actually is.

From there, we may look at something called singular value decomposition (SVD), and how it can be used to approximate large black and white images. Although we may wish to use MATLAB (or some other programming method) to demonstrate our finding, it will be based on the skills and desires of the research group. This research is based largely on material presented by Gilbert Strang from MIT, although knowledge of fundamentals of linear algebra (such as UCR math 31) would be advised.

An example of "bad" compression