Histogram Color and Fractional Iteration

[asimes]

I had been looking at this link for explanations of different coloring techniques: http://www.hpdz.net/TechInfo/Colorizing.htm

I finally made sense of how to set up Histogram Coloring at it worked just fine (for Mandelbrot) using integer iterations counts. The problem is that I set up the Histogram count like this (in pseudo-code):

int[] histogramVals = new int[all of the pixels];
for (all of the pixels) {
  while (n < maxIterations) {
    ...run the Mandelbrot tests...
    n++
  }
  histogramVals[n]++;
}

Why I see this as a problem is that the Histogram values are using the number iterations to index the element in the array. This won't work with Fractional Iterations because you can't index with floats. How do people normally set up Fractional Iteration Histogram Coloring?

[asimes]

Opps, the length of histogramVal should have been maxIterations

int[] histogramVals = new int[maxIterations];

[asimes]

Ok, I found a method that works but it is way too slow. After I get the fractional iteration counts of each pixel I store them into a float array. Then I have one of two options (both are slow):

1. Organize the array with some kind of sorting algorithm (like bubble sort). Then for every pixel determine how many pixels had a lower fractional count (this can be determined from the pixel's index because it is sorted). Use this number divided by the max number of iterations to get a percentage for color.

2. For every pixel, run another loop that counts the number of pixels that have a lower fractional iteration count. Use this number divided by the max number of iterations to get a percentage for color.

Neither of these options are fast. The code I posted above for integer iteration counts was very fast because it sorted a histogram along the way. Is there a method of doing that for fractional counts?

[hobold]

Bubblesort is a very slow algorithm for sorting. As the number N of data items increases, its runtime increases proportional to N*N. You might want to use an algorithm called "Quicksort" instead (which has runtime proportional to N*log(N)), or really anything else but Bubblesort.

[asimes]

I know that bubble sort is not the fastest, I just was not sure if people would know what I meant if I didn't provide an example of a sorting algorithm. My goal would be to avoid having a secondary sorting step if it is possible as when I did a histogram color with integers it was not necessary.

[hobold]

My goal would be to avoid having a secondary sorting step if it is possible as when I did a histogram color with integers it was not necessary.

Nitpicking alert! I'll overanalyze things ... (and please forgive me that the information will probably not be helpful for solving the problem at hand).

When you compute a histogram with integers, you actually do a sorting step, namely bucket sort (or radix sort, for a more general name, or spread sort for specific implementation tricks). Each entry in the histogram array is one bucket, and incrementing that array entry is equivalent to putting one unsorted item into the right place.

I am mentioning this to make clear that sorting is always implied when you generate a histogram. I don't think you can do without any explicit or implicit sorting.


If you can get away with less than full floating point precision, you could quantize the input values to buckets of your choice. That means, you could scale those floating point values and round them to integers, and then process the results exactly as in the case where all data starts out as integers. The resulting histogram would be imprecise, of course, but it can be interpolated again and maybe that is already good enough for your purposes?

[asimes]

That turned out to be much faster. The multiplier on the floats has some strange effects on the image, it seems best to keep it a small number (like 10). If I make it really big then the fractal starts to glow so intensely that it loses detail and it just looks like bright lightning bolts touching the sections that reached their max iteration count.

Also, when I was using integer iteration counts there were obvious slots (or buckets if I understood your explanation correctly) that I indexed with 'n'. However, for the fractional iteration counts there are no (or at least almost no) repeats of a value for an iteration count. What I mean by this is that each value indexed with the multiplied fractional count doesn't seem to have a repeat. Does this make the coloring rank-order instead of histogram?

[asimes]

Opps, never mind the first part of my last post. I actually have no idea what I had made when I wrote that but it wasn't Histogram Coloring. I have it working now, the float multiplier only affects the density of iterations bands which seems to make sense. (If I make it big enough they basically disappear.)

Seems to make sense now, thanks