Accelerated Media Streaming for Home Networks

One of the major issues facing the internet as a whole today involves the huge amounts of bandwidth being consumed due to the transferring of picture frames for various sites that host videos. Mainly, the problem stems from being able to improve upon the current mpeg compression form. Mpegs figure out how much redundancy occurs between successive frames, and if the redundancy is high enough, the mpeg simply uses only a fraction of the prior frame’s pixels. It also does this fast enough that it actually improves overall upload/download time of the overall mpeg (instead of having to download/upload the data for every pixel for every frame). A scaled down version of this major problem involves the uploading of simple digital pictures; when uploaded from a camera every picture must be individually uploaded, no matter how similar two pictures might be. If an efficient solution can be discovered for this simpler problem, it can then be scaled up to address the overlying greater problem. In lieu of this, my main task has been to compare two pictures, analyze the amount of redundancy, and, if viable, create the second picture by just changing only a fraction of the pixels from the first picture.

In order to take on this problem, I first needed to do some background research in the area of both JPEG and MPEG. The general information I learned was that after basic JPEG compression, there is not much more benefit that can be gained by further compression on the individual photo. To compress further, a lossy approach would have to be used, meaning data for the picture would be lost. With pictures, if too much data is lost, then the picture quality is compromised beyond any acceptable standard. So upload/download speed could only be achieved through non-compression means. A new approach needed to be conceived that instead compared pictures together and tried to “compress” between two pictures instead of just focusing on compressing one picture’s data. For example, say there are two pictures taken of a group of people - the only things that changed in the three seconds between pictures were slight body movements. Now instead of uploading all of the pixel data for both pictures, if you realize that not much is different about the photos (about 90% of the picture is alike), then you can upload the first photo and create the second photo by inserting “noise” into the first picture in the places the photos slightly differ. If this problem can be solved effectively it can be scaled up to bigger problems like bandwidth issues on the internet.

Originally, I was tasked to create two programs: one would create an easy-to-use GUI and let the user shift the pictures around while comparing, while the other would do the same thing but be run from the command line. After familiarizing myself with JFrames, layout managers, and the swing library of Java with the help of some textbooks [Java Programs], I was able to begin to code up a working GUI which displayed both pictures that could be moved in small windows. After fixing a couple of minor problems like window sizing and repainting of the pictures, the general layout of the GUI was taken care of [Java Sun].

The GUI before and after comparison of two pictures of the same dimension.

Two pictures being compared with the difference picture between them.

Next, I needed to add some amount of functionality to the GUI. I created a compare button, and using a function called grabPixels I was able to actually extract the color details of each pixel and store them in an int array [Pixel Grabber]. Using these arrays I then went through and subtracted each value from each other and stored that value to a different array, finally reversing the process and using the new array to display the “difference picture”. However, the difference was incorrect because I was not taking the absolute value of the answer and the numbers were not being subtracted correctly. An int is 4 bytes, the first byte is garbage but the others contain the color index of the red, green, and blue aspect of that pixel (0 - 255 numeric value). I had to convert the ints to hex, subtract each color's part only from themselves (subtract the red subspace of pixel1 from the red subspace of pixel2), then convert the hex string back to and int again [Developers Almanac]. Once this was realized, I had the correct difference data in the array and could display the picture on the GUI.

The next major issue that arose was pictures of different sizes. For instance, if one picture is 100 x 400 pixels and the other is 400 x 100, the program creates a difference picture of 400 x 400, with the upper right 100 x 100 pixels being the only difference that is calculated. The algorithm for this was tricky because the array the pixel data is stored in was only single-dimensioned, so I had to keep careful track of where I was in the array so the right pixels got compared. After the comparison, not only would the picture be displayed, but a new file was also created which contained the picture.

Two pictures with varrying dimensions and the resulting difference picture.

The only other aspect the GUI needed was a histogram of the pixel data, visually showing the user the number of pixels which are exactly the same, which are close, and which are way off. Luckily, Java includes methods for creating histograms so the task was not too difficult [Histogram]. The histogram itself contains ten buckets which are not evenly weighted. The first bucket contains exact pixel matches, while the rest represent all of the numbers up to consecutive powers of two. Thus, the second bucket contains pixel that are 1 off, the third 2 off, the fourth 3-4 off, the fifth 5-8 off, and continuing until the tenth and final bucket contains pixel indexes which are 129 - 255 points off. Also, four separate histograms are created: one for the average total pixel distribution (adding the values of red, green, and blue together then dividing by 3), and then one histogram for each of the three main color subspaces.

The resulting histograms for a very close comparison.

After the GUI was completed, work started on a command line version. It was quite simple to create from the GUI code and takes in the pictures to be compared with the offsets to be used (optional) as arguments. Lastly, a Perl script was created which has two uses. If no arguments are provided, then the script simply compares each picture in the directory with every other picture, creates the difference picture, and then generates a html page which features a table of the pictures and the matching difference pictures.

The generated html page from running the perl script on a directory.

If called with the two picture names as arguments, it goes through and tests different offsets, looking for the one which gives the best results in terms of the most redundant pixels. The offsets never exceed 40 pixels in either the X or Y dimension, for shifting more would decrease the amount of pixels compared to an unacceptable number. The script was relatively simple, with the only problem arising being that pictures were sometimes too large for the heap. A simple flag called to the java command increased the heap size from 128MB to 256MB which solved the problem.

For the time being, optimization on the speed of the code was not considered, the main concern was first understanding the problem and testing its feasibility. One limitation in the solution created was the way the pictures can be shifted around. The grabPixels function is limited in the sense that it only stores the data in a single-dimension array, thus shifting the photos around was limited to left and upwards only. Now if both picture are shifted this way, basically all possibilities are covered, but not every one is tested. However, since the maximum shift of the pictures is around 40 pixels (or else the benefits just cannot be realized), then it is highly unlikely that if a picture can achieve 90% redundancy in pixels that the current shifting will not be able to detect it. Another decision made was what qualifies as redundant, and how much redundance needs to exist for the created picture to look right. I choose my numbers by sheer trial and error and guesswork, so a better approach could be taken for that as well (I hold that the pixel values need to be within 17 of each other and the percentage of these redundant pixels should be 90).

The speedup occurred based on these numbers is fairly impressive, but I feel they could still be improved. On average, the speed of an average home network is around 256kb/s, that being the ideal rate in can achieve. However, normally it will perform under that benchmark for actual data transfer. Cameras today can easily generate 1.5MB photos, and the lenses are just going to keep getting better. If you upload an average number of photos for a vacation, say around 300, it will take around 4 hours at the ideal rate. If a modest number of 10% of these photos are similar enough to take advantage of this new method, the new upload time improves by 10%. This number will also scale with the number of pictures which are similar, and the method will become even more time efficient with pictures of better quality.

An even more impressive compression method discovered was taking the photos in a folder and creating an mpeg out of them. The programs that convert the jpegs to an mpeg ($ jpeg2yuv -f 25 -j frame-%03d.jpg -I p | mpeg2enc -o mpegfile.m1v) then back again to jpegs are a bit unstable and quirky at times (for example, the dimensions of the jpegs must be divisible by 16 or it crashes), but the compression achieved cannot be ignored [Jpegs to Mpeg]. When a folder of 151 pitures totaling 263MB (1.7MB average for each picture) was converted to an mpeg, the resulting file was a mere 19.9MB, a 92% improvement. However, when converting the mpeg back into jpegs ($ ffmpeg -i video.m1v -an -r 25 -vframes 151 -y %d.jpg), the resolution of the jpegs has been heavily compromised [Mpeg to Jpegs]. Thus, although the improvement is a startling 92%, the data integrity is compromised, dismissing it as a very viable solution. So while creating an mpeg from the jpegs using exisitng software offers huge data compression improvement, a more suitable option is the new data redundancy method since the picture quality is not decreased by compression.

Two very similar photos, (1) on the left - (2) on the right.

Generated picture of (2) based on the above two photos.

[Java Programs] Reges, Stuart., and Stepp, Marty. \emph{Building Java Programs}. Boston: Pearson Education, Inc. 2008.

[Java Sun] http://java.sun.com/

[Pixel Grabber] http://www.permadi.com/tutorial/javaGetImagePixels/index.html

[Developers Almanac] Chan, Patrick. \emph{The Java Devlopers Almanac 1.4, Volume 1}. Boston: Pearson Education, Inc. 2002.

[Histogram] http://www.particle.kth.se/~lindsey/JavaCourse/Book/Part1/Tech/\\Chapter06/histDemo.html

[Jpegs to Mpeg] http://www.stillhq.com/extracted/howto-jpeg2mpeg/output.html, http://nasm.sourceforge.net/, http://download.sourceforge.net/mjpeg/, http://www.fontconfig.org, http://www.freebsdsoftware.org/graphics/jpeg-mmx.html

[Mpeg to Jpegs] http://www.flashcomguru.com/index.cfm/2006/4/25/ffmpegthumbs, http://ffmpeg.mplayerhq.hu/