Color Space Generator

Thu, 12 Oct 2006 12:07:19 GMT

Part of the work I've been doing for my thesis involves generating color images from indexed files. This is the same principle as any indexed image format (like GIF) where each pixel is a number which maps to a table of red, green, blue values. At the time I knew how to get the basic 256 colors from the color wheel. The problem was the fact that my indexed image needed over 100,000 different colors. Of course generating 100K colors is one thing, making an image that uses so many colors look good is another. So after a day of digesting color theory websites I finally understood the concept of a color space, color models, gamuts and enough on how they go together to make a Java class that lets me generate a color space where the colors work together. I've uploaded a zip of the class file here for anyone who can find some use for it. At the time I was tempted to add an alpha channel which would cause a gradient around color values, maybe later. To use the class simply call the generate method, the arguments are: the starting color offset (0 to 1785), next is the number of colors to generate, and finally the number of colors to skip in between.

Enjoy.

The pure color values are on the following offsets:

Offset	R	G	B
0	255	0	0
255	255	255	0
510	0	255	0
765	0	255	255
1020	255	255	255
1275	0	255	255
1530	0	255	0
1785	0	0	0

Java performance analysis - a real life example

Fri, 02 Jun 2006 03:43:25 GMT

For my thesis I'm writing a Java program that parses two text files (representing satellite images) and performs some analysis on them. The two files are 128 MB and each was taking ~33 seconds to parse. The analysis takes only a fraction of that time, then the results are written back to an output file.

Thinking this was very slow, since the files should be pretty much sequential access off the disk and the read-ahead-buffer would have cached the next block, I decided to dig a little. I rewrote the parsing algorithm in C since it's easier to manage the low-level IO. I used the file stream functions (fopen,fread,fclose) provided by stdio. When I ran the program it took ~10 seconds.

This was insane. Java does have more overhead due to its garbage collection, HotSpot optimizer, and object memory management but it should not be a magnitude of 3x slower. After a few minutes looking at the Java implementation I realized I had forgotten to instantiate a BufferedReader. I immediately jumped to the documentation and there it was, each call to the read method of the FileReader blocks until data is available. If no BufferedReader is supplied this means a context switch for each call. No wonder Java was taking so long. Adding the buffering I reran the algorithm and wow, 13 seconds. Not to bad for a “boated” language.

Figuring I had more places in my program which could be optimized I began looking. The first place I went was to one of the main methods, the one which did the analysis on each image. The logic was pretty simple, find the next pattern in the given image, see if it exists in a lookup table, if so update its statistics or create a new key and add it as a new entry. The data structure I was using for the lookup table was a simple HashMap object. When writing that section of the program I was still relatively new to the Java language and just went with what I'd used in other languages, an associative array.

I did a little analysis with some System.out.println statements and found that on average there was a 14,000 : 15 ratio between reads and writes on the lookup table. Knowing this ratio was pretty stable (I wasn't going to get anywhere near 50% writes) I decided a better data structure would be something with read time of O(n) or less, instead of O(h(k)) where h(k) was the hash function on the key. This meant an array would be best, but I didn't want the hassle of managing the size of the array as new patterns where found. Java had to have something for this. After a little searching I found java.util.concurrent.CopyOnWriteArrayList. This was exactly what I needed. After a little tweaking the new code ran in 1/3 the time.

After this I wrote some small timed programs to examine the running time of the HashMap data structure and the CopyOnWriteArrayList. What I found was as the mutations approached 25% the CopyOnWriteArrayList's performance slowed at an exponential rate. Finally, I couldn't evaluate the performance because the tests were taking too long. On the other hand, the HashMap data structure had a fairly constant performance time irrelevant on the read/write ratio.

RSS feed for InstantSpot site EdomGroup Blog

Color Space Generator

Java performance analysis - a real life example