Auto Log Fractal coloring

[fractalwizz]

 
I'm stumped.
I can't seem to create a log coloring algorithm that shifts a parameter automatically when zooming in.
How would you create one such thing?
Here is an example http://www.fractal-animation.net/vid/descent.zip

[Duncan C]

I'm stumped.
I can't seem to create a log coloring algorithm that shifts a parameter automatically when zooming in.
How would you create one such thing?
Here is an example http://www.fractal-animation.net/vid/descent.zip

I'm not sure how the colors were done for that animation.

My application, FractalWorks, supports adaptive colors based on a histogram of the image Here's how it works in somewhat simple terms (For a Mandelbrot set):


Count the total number of non Mandelbrot set pixels in a frame.
Create an of integers to count the total number of pixels at each iteration count in the image.
Pass through the image, counting the number of pixels at each iteration count.

Then work through your array of iteration counts from the highest iteration count to the lowest, keeping a running count of the total number of pixels. Assign colors based on the percent of pixels with higher iteration numbers.

Simple example: Low iteration pixels are blue, high iteration pixels are red.

Pixels with the lowest iteration value have 0% of pixels with a lower iteration count, so you would color those pixels 100% blue and 0% red.
Pixels with the next higer iteration iteration count might have 1% of pixels with a higher iteration count. Those pixels would be colored 99% red and 1% blue. As you work up to higher iteration counts, a growing percentage of pixels will have lower iteration counts, so the pixels will be be more red and less blue. When you get to the highest iteration count with pixels, nearly all pixels will have a lower iteration count, so those pixels will be nearly red% blue and 0% blue. In fact, you want to fudge your math so that the highest iteration pixels get 100% of your "high iteration" color, and 0% of the "low iteration" color. I forget exactly how I worked the algorithm to do that, but I did.

The same scheme can be adapted to multiple color gradients, or "color bands.".What I do is to describe my color gradients as having an "anchor point". The lowest iteration band (or color gradient) always starts at the lowest iteration value. That band ends at the beginning of the next color band. The user specifies the beginning of each band in terms of the percentage of pixels in the image with a lower iteration value. If a band begins at the 10% point, then that color gradient starts at the iteration value where 10% of pixels have a lower iteration count. If a band begins at the 50% point, it starts at an iteration value where 50% of pixels have a lower iteration value. Within an iteration band, colors transition from the low iteration color to the high iteration color based on the percent of pixels with lower iteration values within that iteration band.

Histogram-based colors end up being very much like logarithmic color tables, but they adapt to different plots automatically. No matter what range of iteration values show up in an image, you use the same color gradients, with the same relative color distribution. It works VERY well.

It's almost harder to describe than to code. Here is a link to an illustrated example taken from my program:


Histrogram based colors example



Duncan C

[HPDZ]

Descent (a rework of my Canyon1 http://www.hpdz.net/Anim_Canyon1.htm) was colored using the auto-log coloring in FractInt, I believe. Based on my rough skimming of the source code, FractInt takes the logarithm of the count value and does some scaling that seems to involve the magnification level to set the range of values that get mapped onto colors. I haven't spent the time to figure out all the details yet. Maybe a FractInt expert can provide a verbal or pseudo-code description of how auto-log works?

[HPDZ]

Addressing the more general topic of adaptive coloring, I have a few quick comments:

1. I've used histogram-type coloring for a long time and I love it -- for still images!

2. I also have developed a rank-ordering coloring method that is very simple to understand. I wrote a little about it on my web site (http://www.hpdz.net/TechInfo_Software.htm#Colorization) but didn't go into much detail. Essentially it works like this:
a. For each image, make a list of al count values and sort it from low to high.
b. For each count value on the sorted list, calculate a value from 0 to 1 based on its position in the list (i.e. the lowest count is 0, the highest is 1)
c. Use that value to index into the color table.

Most of the time, this ends up looking similar to histogram coloring, but is a lot less sensitive to outlier count values.

Both these techniques work great for still images and can make an otherwise ugly image into something really gorgeous.

But neither method works very well for animations because of noise caused by pixels located very close to the set boundary. This noise causes the mapping to jump around too much and is very distracting. See http://www.hpdz.net/Anim_Technical.htm#Rank-Order for an example. You can see the color map has some high-frequency jitter at the frame rate and also kind of lurches forward and backward on slower time scales.

To work for animations, a coloring algorithm has to be (in my opinion):

• Monotonic -- it should never "go backwards". Once a count value is assigned a value in the color map, that count should never be assigned a lower value in the map as the animation progresses
• Quiet -- no frame-rate jitter
• Steady -- no sudden lurches

This is not easy to achieve. I've tried a bunch of things and had some reasonably good results but I'm still not completely satisfied. I'm currently using a pretty complicated set of filtering operations combined with rank-ordering. I am still working on some more ideas for this.

[HPDZ]

Wow. Aging is beginning to take its toll on my memory...

I just realized I wrote essentially the same thing as above in a post back in October in a different thread. Sorry for the duplication.

[Duncan C]

Addressing the more general topic of adaptive coloring, I have a few quick comments:

1. I've used histogram-type coloring for a long time and I love it -- for still images!

2. I also have developed a rank-ordering coloring method that is very simple to understand. I wrote a little about it on my web site (http://www.hpdz.net/TechInfo_Software.htm#Colorization) but didn't go into much detail. Essentially it works like this:
a. For each image, make a list of al count values and sort it from low to high.
b. For each count value on the sorted list, calculate a value from 0 to 1 based on its position in the list (i.e. the lowest count is 0, the highest is 1)
c. Use that value to index into the color table.

Most of the time, this ends up looking similar to histogram coloring, but is a lot less sensitive to outlier count values.

Both these techniques work great for still images and can make an otherwise ugly image into something really gorgeous.

But neither method works very well for animations because of noise caused by pixels located very close to the set boundary. This noise causes the mapping to jump around too much and is very distracting. See http://www.hpdz.net/Anim_Technical.htm#Rank-Order for an example. You can see the color map has some high-frequency jitter at the frame rate and also kind of lurches forward and backward on slower time scales.

To work for animations, a coloring algorithm has to be (in my opinion):

• Monotonic -- it should never "go backwards". Once a count value is assigned a value in the color map, that count should never be assigned a lower value in the map as the animation progresses
• Quiet -- no frame-rate jitter
• Steady -- no sudden lurches

This is not easy to achieve. I've tried a bunch of things and had some reasonably good results but I'm still not completely satisfied. I'm currently using a pretty complicated set of filtering operations combined with rank-ordering. I am still working on some more ideas for this.

HPDZ,

Your rank-ordering algorithm would cause sudden jumps in color assignments between different frames in an animation.

The histogram based algorithm I described above causes VERY subtle color changes higher iteration values. As the iteration value gets high, the color change gets so subtle that you really can't see individual pixels. You wind up with very subtle color transitions. At deeper zoom levels you frequently can't see individual iteration bands at all. There shouldn't be any visible jitter for points close to the set boundary, since those color changes are so small that you can't see them. Turning on fractional iteration value smoothing would eliminate visible color bands.

My app doesn't yet support animations, so I can't say for sure how well it will work, but I suspect it will work pretty well.

One thing I have thought of to smooth the change in colors between frames is to use a rolling average of iteration counts. Imagine a minute long movie where the the iteration counts from a half-second of frames on either side of the current frames are averaged in order to assign color values to each pixel. This would cause the colors to shift as the zoom progresses, but should smooth out the changes.


Duncan

[fractalwizz]

reply for HPDZ.net

I can't seem to find the auto log coloring in UF. Is the compatability formula files have it? I don't see it

[HPDZ]

I can't seem to find the auto log coloring in UF. Is the compatability formula files have it? I don't see it

I am not sure if it's in UF or not ... I'm not really very familiar with UF (or FractInt either for that matter) and its capabilities.

I'm off work for 9 days starting tomorrow so I will have some time to slog through FractInt's source code and figure out what "auto-log" does exactly. Or perhaps it's worth posting a question to see if any of the developers can describe it.

[HPDZ]

Duncan,

I've used a histogram-based approach that is, as far as I can tell, essentially identical to what you described. In fact, that was the first technique I tried about 4-5 years ago, prior to the rank-ordering method. It turns out that the histogram technique does also give significant jitter in the color mapping from frame to frame in an animation. That jitter was actually what led me to try something different, hence the rank-ordering approach. Unfortunately, it didn't turn out to be much better.

I don't think I have a video published demonstrating histogram mapping, although I do have a bunch of them on my hard drive. I'll put some of them on hpdz.net in a few days.

For still images, both methods work really well, although rank-ordering gives slightly better detail at high counts. Of course, frame-to-frame jitter won't be evident on still images.

I wonder if you wouldn't mind trying something which might give you a similar effect without having to make an animation: Zoom in to some area near the edge of the set and apply your histogram coloring to it. Then try changing the magnification just very slightly, like 0.1% or 1% (e.g. from, say 1e5 to 1.001e5 or 1.01e5) , and re-draw the image and apply the histogram again. When I do this, I often get very different colorings because the high-count tail of the histogram changes a lot and that affects all the rest of the count-to-color mapping. both images will look good, and both will utilize the color palette efficiently, but they will look rather different from each other.

I'll put some examples of what happens when I do this with my software on hpdz.net in a day or two.

If you don't get a noticeable change, I'd be interested in learning more about the exact details of how your histogram method works; maybe it's different from mine in some important way.

Mike

[Duncan C]

Mike,

Here are a couple of images with a tiny change in zoom. I posted them to the galleries here on fractalforums:







The best way to compare them is to create a layered image in PS and show/hide the top layer. There is a little bit of jitter in the areas closest to the Mandelbrot set. I think that has more to do with the way the coordinates of each pixel shift slightly as the zoom level changes than with the color table assignment.


Duncan

[HPDZ]

Duncan,

Thanks for taking the time to make these images. I agree they look pretty similar, essentially identical in fact.

Unfortunately, I think my asking you to do this might not have been the right test. Upon further consideration, I see that what really matters is how the count-to-color mapping performs when extremely high outlier count values come in and out of the image. That is a very hard effect to reproduce at will. It depends on the image itself, and also on how high the maximum count limit is set in the rendering program. If you set it to only 100 counts, then you'll never get an outlier point with a spike higher than 100. If you set it to 1 million counts, well, you'll occasionally get spurious outliers at 1 million. Obviously these two scenarios will test the stability of the color mapping quite differently.

Nevertheless, I am beginning to think that the histogram approach might actually be superior to the rank-ordering idea in terms of its robustness against outliers. I've resurrected the histogram method in my software (part of my previous disfavor of it was actually, I see now, due to some problems with how I coded it all....) and I am working on getting a good set of test images and animations to compare these approaches. I hope to wrap this up over the New Year weekend.

The main thing I am seeing about the histogram approach is that its slope du/dn, where u=color map index (i.e. u=0 means one end of the color gradient and u=1 means the other end) and n=count number, approaches 0 for large values of n much faster than the rank-order method. Having du/dn go to zero is an important part of having the map be stable against outliers. Unfortunately, it also washes out the detail at higher count numbers.

Mike

[Duncan C]

Duncan,

Thanks for taking the time to make these images. I agree they look pretty similar, essentially identical in fact.

Unfortunately, I think my asking you to do this might not have been the right test. Upon further consideration, I see that what really matters is how the count-to-color mapping performs when extremely high outlier count values come in and out of the image. That is a very hard effect to reproduce at will. It depends on the image itself, and also on how high the maximum count limit is set in the rendering program. If you set it to only 100 counts, then you'll never get an outlier point with a spike higher than 100. If you set it to 1 million counts, well, you'll occasionally get spurious outliers at 1 million. Obviously these two scenarios will test the stability of the color mapping quite differently.

Nevertheless, I am beginning to think that the histogram approach might actually be superior to the rank-ordering idea in terms of its robustness against outliers. I've resurrected the histogram method in my software (part of my previous disfavor of it was actually, I see now, due to some problems with how I coded it all....) and I am working on getting a good set of test images and animations to compare these approaches. I hope to wrap this up over the New Year weekend.

The main thing I am seeing about the histogram approach is that its slope du/dn, where u=color map index (i.e. u=0 means one end of the color gradient and u=1 means the other end) and n=count number, approaches 0 for large values of n much faster than the rank-order method. Having du/dn go to zero is an important part of having the map be stable against outliers. Unfortunately, it also washes out the detail at higher count numbers.

Mike

Mike,

I typically use a max iterations of at least 1000, and often 10,000 or greater.

The histogram algorithm I use is all but immune to outliers at high iteration values. That's because iteration values with low pixel counts get a very small color change, which means that they don't stand out.

I find this is almost a requirement for deep zooms, since the iteration count changes a lot in small areas in deep zooms. If there was a large color change, the shape of the iteration bands would be lost in noise.

I find that histogram based colors tends to soften details at higher count numbers, but not eliminate it entirely.

If I want crisp detail around the set, I usually use distance estimate data to create rapid change in color for pixels that are very close to the set. That helps a lot.


Duncan C

[HPDZ]

Returning to the original topic of this thread regarding Fractint autolog coloring...

I was able to find this on http://www.xmission.com/pub/lists/fractint/archive/v01.n005

Date: Wed, 20 Aug 1997 10:45:03 -0600 (MDT)
From: <robin.b2@ukonline.co.uk>
Subject: Re: (fractint) Question 

On Wednesday, August 20, 1997 10:18:45 you wrote:
[... some stuff omitted ...]
  What autolog does is do the calculations for all the pixels round the edge of your zoomed
view first, find out the lowest value it encountered and then use this as the lower end of
the colour spread used by logmap. This only gives good results if the fractal is one which
has no 'islands' of lower iterations inside such as the Mset.
Though this is the most 'efficient' way of using colours it also results in the colourmap
being shifted so you might need to cycle things a bit to get back to the look you had
before.

That agrees with what the source code is doing as far as I can tell. But it doesn't quite give all the details of how a count value is mapped to a color. The best I can figure from reviewing the source code is that the upper range of the log map is determined by maxiter (the iteration count limit) and the lower range is determined by the value of a global variable LogFlag, which is set to the minimum count value around the edge as described in the quote above.

So, to summarize, autolog seems to be doing this (u here means the value from 0 to 1 that selects which color a count value gets)

Code:

1. Let min = minimum count around edge of image
2. Let max = maxiter
3. For each count value cnt, calculate u = log (cnt-min) / log (max-min)

There are some fussy +1's and -1's here and there to avoid log(0) and to avoid overflowing table indexes, but that's the basic equation that's used.

There's also some range checking to deal with a case that apparently gives the user the option of having all counts below min get sent to the first color. For the autolog case, that is theoretically impossible since the boundary ought to contain the minimum count value in the entire image.

That last assumption, by the way, is not at all obviously true to me when rendering actual fractal images numerically. Certainly if we could sample the entire boundary of a region with infinite precision, it would be true for sets like the Mandelbrot set, but given numerical error, sampling artifacts, etc., I wouldn't be surprised if sometimes the boundary doesn't contain the minimum count for the whole region. This doesn't cause a problem in FractInt because the count mapping functions test all the cases to make sure they never take the log of 0 or of a negative number. But it's an interesting (well, at least to me) theoretical question.

I don't know whether UltraFractal contains an operation like this or not. I am also not fluent enought with UF programming to know whether it is possible to encode something like this into it -- do you get to tell it to do something like draw just the boundary of the image?

Finally, I would point out that I think a better function to use is
 

Code:

 u = Log(cnt/min)/Log(max/min)

because of course what we are really trying to do is

Code:

 u = [log(cnt) - log(min)] / [log(max) - log(min)] 

This allows cnt to take on any nonzero value without giving the log function nonpositive numbers. It also removes the somewhat arbitrary value of the base of the logarithm from the problem, instead effectively taking the log of (cnt/min) to base (max/min).

OK. Phew. I hope that helps.

[HPDZ]

I've started a new thread in the "Programming" forum to continue the discussion of rank-order and histogram coloring, which seems off the topic of this thread.

The new topic is "Non-parametric color mapping techniques"