Welcome to Fractal Forums

I've got my app, FractalWorks, rendering 3D height maps now, and am overall pretty pleased with the results. Directional lighting and specular highlights add a lot to the look of the plots. I've posted a few of the images to the samples gallery.

Here is a sample image for those that haven't seen the other post:

(http://www.pbase.com/duncanc/image/93592038/large.jpg) (http://www.pbase.com/duncanc/image/93592038/original)
(click the picture to see the much larger "original" version on pbase.)

I'm using the distance estimate method (DEM) as the basis of my height values. (inverted, the log, scaled and streched, etc.)
The 3D texture of the height map very close to the set changes so much that it doesn't look good.

Simple supersampling doesn't work for fractals because there is an infinite amount of detail.

What approaches have others used to get smooth lines and cleaner textures? I should be able to apply an approach used for antialiasing 2D plots to my 3D plots.

I'm thinking of calculating a weighted average value of the current pixel and it's neighbors in a 3x3 grid
((the sum of the 8 neighboring pixels/8) + the current pixel) / 2.
Or I could do a simple average of all 9 pixels in a 3x3 grid centered on the current pixel. Either approach would tend to smooth out the "spiky" nature of the areas closest to the Mandelbrot/Julia set.

Does anybody else have a good suggestion as to how to do this?

Here's a sample image that shows the effect I want to avoid:

This is my attempt to duplicate the cover of the book "The Beauty of Fractals":

(http://www.pbase.com/duncanc/image/93544086/original.jpg)

Note how the areas in the peaks closest to the baby mandelbrot are too chaotic (funny, that!) to make much sense visually.


Duncan

i am using a gaussian blur filter to smooth out my details, on very high resolutions, this leads to very good results
http://en.wikipedia.org/wiki/Gaussian_blur

but all in all it wringles up to much of my detail, i havent tried out a selective filter yet

due to the fact i am using this method for animations, the chaos even gets worse, if i want to make smooth animations, i have to apply the blur filter also in time direction, so to say, i have to take the last blursize and next blursize images into account when smoothing ... :) but this i have not done yet, because it would had strange effects on my movie, it would have an effect like motion blur on my movies, but that wouldnt be the result i want to achieve ... :(

duncanc, you've hit the nail on the head: what you want to do is antialias your heightmap. blurring is something completely different.

a very simple and effective way to antialias the heightmap is via supersampling: instead of just using 1 sample per heightmap value, divide each "region" of your M x N map into K x K subregions (effectively enlarging it by a factor of K in each dimension, but you don't store all those values) which you evaluate and average to produce your final heightmap value. this is a simple way to bandlimit your signal, discarding all high frequency data that cannot be represented at the current sampling frequency (i.e. above the nyquist limit (http://en.wikipedia.org/wiki/Nyquist_frequency)).

trifox, this method will give you much better results than blurring.

lycium,

My app is written to render a 2D fractal, then create a 3D view of that fractal, with one height map (distance estimate) value for each pixel. The easiest thing for me to do will be to create a 2D fractal that's a multiple  of the size of the target 3D mesh, then average the height values to create a smaller mesh.

Do you think a 4x average would be enough to get significant antialising? If not, how many extra samples would you suggest? And should the K x K subregions overlap between points, or should they tile?


Duncan

yes, what you in effect (but not in practice!) do is simply render a higher resolution version then downsample. there is no reason to store all that intermediate data.

it's really simple (bashing it out right here without ide, so there might be mistakes and it's obviously not optimised):


regarding how much supersampling is enough, that comes down to your taste and the function you're sampling. fractals are particularly tricky to antialias because they are infinitely convoluted at all scales, so it's not theoretically clear whether or not supersampling will reduce aliasing or increase it! in practice however it seems to do a good job; 3x3 samples should produce a decently crisp reconstruction in most cases; obviously the higher resolution you use, the less aa you can get away with - so trifox will need a lot more for his 200x200 heightmap than you will for your 2000x2000 because there is much greater function variation to accurately account for.

i should also say that signal theory is a very deep rabbit hole and this description doesn't even begin to scratch the surface of the theory. it's also largely irrelevant for fractal rendering because it doesn't fit the classical assumptions of signal theory.

some time ago i taught a guy on deviantart, chaos5 (http://chaos5.deviantart.com), the basics of sampling and reconstruction (you can look through his various deviations and journals for my posts if you're interested). the art of sampling comes into play when you start attempting to properly evaluate the signal reconstruction integral (of function times bandlimiting kernel)...

i also do use supersampling, with random points scattered over the subgrid area, and smooth it afterway also,

without the blurring, it increases significantly the image quality, but for 3d ...

i have some more questions, i heard about nyqist frequency, but where does it come into play here ?

the high frequency noise increases towards the mandelbrot area, how can one possibly determine
a good subsampling for these areas, you said 3x3 raster serves in most cases but i am not satisfied here ;)
basically it comes down to limiting the iteration depth ?

iteration depth = a indicator for frequencies ?

wouldnt it be possible to use this as a factor for smoothing ?
e.g.make a histogram over the occured iteration depths ?

just thoughts ...

another thing to mention is what kind of grid do you use ?

have you experimented with triangle grids ? or even heaxognal grids `?
http://mathworld.wolfram.com/TriangleTiling.html

i thought this could improve the smoothness of the 3d grid ....

the nyquist criterion is an element of classical sampling theory that, as i mentioned, has no part to play in reconstructing fractal functions. basically if you have some, say, audio signal with a maximum frequency content of 20khz, then you should sample it at a minimum of 40khz to be able to reconstruct it perfectly. when we don't know the frequency content of our function, this theory of little use.

however, as you pointed out, if we are given a sampling rate we can sometimes use this to adjust how much detail we add to our function. a nice example of this is the fractal perlin noise function, where interpolated noise is added in "octaves", each term having twice the frequency of the previous; if we have a given sample frequency we can then decide how many octaves are added, blending the final octave with an average value (which is usually zero).

unfortunately, i don't see how we can relate this spectral interpretation to fractals. it's clear that the function's frequency increases the more we iterate, but whether this is linear, exponential, quadratic, ... i don't know. maybe a real mathematician can help us out here ;)

in any case, it actually doesn't matter too much to consider these things in theoretical perfection, simpler methods will work just fine. for example, we can for each pixel see how much the function varies and then do a second sampling pass based on that, ought to work well.

about which irregular sampling patterns i use, that depends on the application. typically for ray tracing purposes i use quasi monte carlo sequences which effectively fill the first 5 or 6 sampling dimensions, whereas for straightforward image sampling i'll usually use a rank-1 lattice if i can afford it.

here's a good book on monte carlo and quasi monte carlo methods you might be interested to look at (no use hiding from the fact that we're approximating integrals): http://www.cs.fsu.edu/~mascagni/Hammersley-Handscomb.pdf

here are some good notes on signal processing: http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Sampling/Notes%20on%20Signal%20Processing.pdf

trifox, have you tried doing this antialiasing instead of your current blurring approach?

i think that, together with higher resolutions like 1024x1024 or more, will bring a tremendous quality improvement for your renders. it's also a lot easier to do zooms like this, since you don't need to worry about continuity between different blurred images and stuff like that.

yes, in current version of mutatorkammer, is the oversample feature, wich is also used
when calculating pixels for heightmaps, i am using as told before a randomized grid
as base, so, when using an 8 x oversample 64 pixels are taken into account for one
resulting pixel

i need the blurring for other things, because, no matter how good you do the oversampling
you will always get high peaks in some areas, e.g. the minibrots in some spiral arms of
the mandelbrot...

because of this the rendering for one single image is taking me more than a minute ;(
but i do always calculate everything on the fly, e.g. the antialiased heightmap, the blurring
and then the rendering, but if that is done, i am using opengl buffers to render the scene,
so one can move around the camera ...

but you are right, the blurring is taking me far too much expenses, because of the continuity at
the borders...

you can speed up the blur a number of ways (in order of complexity):

1. make a special case for the majority of the pixels in the centre region which are guaranteed to not have problems at the edges, to remove all those if-checks. actually to avoid inaccuracies you should compute the fractal map BEYOND the edges of what will be displayed, so that the full image you work with is using correct data.

2. the gaussian filter kernel is seperable, which means f(x,y) = g(x) * g(y). a basic consequence of this is that you can convert your O(N^2) filtering loop to O(N) by first blurring in one dimension, then on the other.

3. from some spline theory (specifically that of cascaded convolutions) we know that the gaussian is the limit of multiple box-convolutions. so if you box-convolve a box function, you get the linear (so-called "tent") filter, if you box-convolve it again you get a piecewise quadratic, then a cubic, etc... in the limit it becomes the gauss filter. photoshop uses 3x box filters to approximate the gaussian, and it works quite well. why would you want to use the box filter? because it can blur an image for any filter size in constant time if coded cleverly.

ahhh, old demoscene tricks :)


all of this aside though, what you actually want to do is reduce the dynamic range of your heightmap, which the blurring does as a side effect of destroying most of the detail. so actually what you want to do to make the image more "regular" is to apply a range compression function like the logarithm to your map. this is similar to what is done in astronomical imaging because the stars don't display a nice linear ramp of intensities, it goes up in geometric scales (10x, 100x, 1000x, ...).

have a look at this page for more infos on this range compression operator: http://homepages.inf.ed.ac.uk/rbf/HIPR2/pixlog.htm

1. ??? this does not sound good for me, are you talking about the black hole in the middle of the mandelbrot ?


2.dont worry, i am using the gaussian trick of O(n^2)->O(n)


3. any links to the constant time ?

but the logarithm compression sounds new to me, have not thought about it, all in all i am using a HDR method already, but only for creating the color ranges ...

1. i'm talking about taking those if-checks out of the innermost loops by special casing the central region where the filter will never extend past the image boundaries. if you compute extra pixels on the edges specially for this, then you also get a more correct image.

2. ok

3. basically you keep a running sum.

consider the following 1d data to be box-blurred:

2 4 6 8 ...

let's say you're using a 3-tap box filter. your first value is:

(2+4+6) / 3

then your next value is:

(4+6+8) / 3

which can be computed as:

(s-2+8) / 3 where s = 2+4+6, the previous sum.

so to blur a scanline, you first initialise your running sum, then each time you move a pixel you subtract the leftmost value and add the new one.

clearly the processing speed is independent of the size of your filter, and this method only works for box filter.

An old topic, but an interesting one.

I've just found out recently that for some fractals with sharply contrasted edges, one needs to sample 16*16 times greater than the desired resolution. This makes it 256 times slower than usual, but the results are definitely worth it. It makes such a difference to the noise level in very detailed areas.

This is an area I too am very interested in, although for the kind of animations I do, I can't afford the 4X or 16X or 256X rendering time increase that anti-aliasing imposes.

First, I think the image on the cover of the book clips the height at some upper limit...if you look closely, around the little mini-brot, everything is flat. I think they so something like if (count>max) count=max, which will obviously remove a lot of the jaggedness.

For anti-aliasing, I think the most important thing is that since the fractal does indeed have infinite spatial detail, there's no perfect way to do it. Some ways are better or faster than others, but none is perfect. There will always be unfilterable noise above the Nyquist frequency (as determined by the size of the sampling grid of your image pixels) in this situation.

When I do use AA, what I do, like everyone else, is supersample and apply a filter (average, windowed average, or median filter) to the supersampled data to generate the final count value for a pixel. I filter the actual count values before they are converted to colors rather than trying to filter the image colors (a much harder problem).

Some variations I've tried:

• Pseudo-Poisson grid With areas of extreme detail, this can help reduce moire somewhat. The technique is to divide each image pixel into an NxN grid, but instead of calculating the fractal values at the center of each grid box, choose a random location within each grid box. This randomness spreads out the spatial frequencies that would turn into moire and turns them into random noise instead. The Poisson grid is the theoretically ideal way to do this, but it's a hassle to generate a perfect Poisson grid and I've found that the pseudo-Poisson grid is good enough.
• Selective supersampling The idea here is to select the noisiest pixels and supersample only them. There are a million variations on this, but the basic idea is to compare each pixel to its neighbors, and if it's different enough, then it's a candidate for further oversampling. This can reduce the number of pixels that need oversampling quite a bit.
• Different filter types Currently I use a median filter to convert the supersampled data to the final image count value. It seems a little "better" (very subjective) than a simple average, especially in areas near the edge of the set, where there is a lot of detail. I've tried averaging and various windowing schemes, and the difference is too subtle to matter much.
• The Main Thing The more points in the supersampling grid, the better. I almost never go beyond 4x4, but there is a noticeable difference in some images between 4x4 and 16x16. The finer the grid, the more the high-frequency noise gets filtered and the cleaner the image will look. This will affect the final result far more than the details of which type of filter you apply to the supersampled data (for any reasonable filter).

Something else to consider is to apply a filter to the final image itself instead of or in addition to oversampling. This can remove a lot of sparkle noise but also can remove a lot of detail.

Another thing that I haven't tried (but I think is done in many animations) is to undersample and interpolate. That is, calculate image points on, say, a 160x120 grid, then use something like bilinear interpolation (or bicubic, or Lanczos -- pick your favorite method) to get a 640x480 image. The undersampling is kind of like applying a low-pass filter, so you get less noise in the final image.

One way to compare the two types is to render a very highly anti-aliased image (say oversampled to 32*32), and use that to compare to the other two. You'd measure the differences (perhaps something like: abs(red1-red2) + abs(green1-green2) + abs(blue1-blue2) ), and see which picture was more different to the near-perfect oversampled one.

Isn't that just the monte carlo method?

Well, about the first thing, how to compare the two: you'd still have to choose a filtering method even for the 32x32 oversampling. You would think that as the number of oversampling points gets bigger maybe the details of the filter wouldn't matter as much, but it's not clear to me that's necessarily true.

About the second question: I think "Monte Carlo" is not a precisely defined term. True, the Poisson Grid is a random method, but it's not quite the same as just picking N points independently within the pixel to be supersampled. Doing that leaves each point's location unconstrained, while the pseudo-Poisson grid keeps them sort of evenly spaced from each other.

my recommendation for sample placement is to use the "best candidate" algorithm to approximate a poisson distribution; basically you take a whole bunch of random candidate sampling points, keeping track of the one with the largest minimum distance to all previously computed points. strictly deterministic sampling methods suck for fractals because they fail to hide the massive aliasing caused by self-similarity with noise (which the eye actually loves, i have in time come to appreciate).

as for which filter to use, again i have a fractal-specific recommendation: anything except sharpening filters (eg your cubic filter family, and especially ones based on the "ideal" sinc function), these will exacerbate the noise/ringing problem with additional sampling. my personal preference here is the triangle/tent filter (basically 1 - abs(x) over [-1,1] interval), being sharper than the usual gaussian but not sufficiently so to get in the way of making a clean image at a reasonable sampling rate.

deary me, what an antialiasing-fetishist i have become...  :tease2:

Well then just use 64x64, as I'm willing to bet that would beat 32x32, no matter what the filtering type.
At 64*64, noise is so, so, small that it really should provide a practically ideal image yardstick. If it's still not enough, then of course there's 128x128 oversampling. Each one is about 4 times as accurate as the last, so when a comparison always produces consistent results (where filtering type a always beats filter type b according to the yardstick comparison), you know the yardstick is good enough.

Unless I'm mistaken, this seems like a great way to quantitatively compare filtering types.


Hmm... I very much would think so ;) The differences would surely get smaller and smaller, converging to no difference with the super-high oversampling versions. Even the 16x version is almost perfect in the last pic from this thread (http://www.fractalforums.com/images-showcase-(rate-my-fractal)/anti-aliasing-for-pro-results/msg5594/#msg5594).

ehrm, you got to take into account the result, in fact, you are proposing, using a 128x128 sub image for calculatin one tiny pixel in your resulting image is considerably different from a 64x64 sub image covering the same area ?!

when talking about those big sub images, you are comming very fast to visible limitations ( considering a rgb pixel of 8bits for each rgb channel ) because the differencies are becoming very fast very small, my experience is that using a 4x4 ( 16x calculation time ! ) sub pixel leads to very good results :D

....had to say something ;)

That's what I'm saying yes - that such massive resolutions, the quality is so perfect that any deeper just doesn't make any difference, no matter what the filtering algorithm is. I was just making the point that one could go to deeper resolutions if each filtering algorithm does actually give noticably different results (which I bet wouldn't be the case beyond say 16x16 or 32x32).

Well, the forum is recommending I start a new topic since nobody's discussed this in over 90 days. That's probably because everyone's been waiting for their 256x256 oversampled test images to render...ha ha

I did in fact make two test images with 256x256 oversampled images ... yes, that is 65536 samples per image pixel! ... one with median filtering, and one with mean filtering. I also did this at 16x16 and 32x32.

I'll start a new thread and post the images to my gallery. They will be JPG images, to keep the sizes reasonable; unfortunately, that means a lot of the detail that differentiates the mean filter result from the median filter result is obscured by the JPG compression. So I have put the original uncompressed BMP files on www.hpdz.net. The link is in the new topic thread.

BAH! Right after I clicked "Post" on that last message, I decided to just go ahead and keep the thread going as it is.

So here's the thing: I believe one of these two methods is superior. I won't bias anyone more than I already have (review the thread) by saying which one I think is superior, but I think if you look closely at even the JPG images, with all their artifacts, you can tell. Download the BMP images (almost 3 MB each!) if you really want to scrutinize them.

I further believe that the difference in filtering methods persists even at huge overampling levels like 256x256 as I have done here. One of these methods is just inherently not suited to dealing with the kind of skewed, non-Gaussian noise that we have here (more data on that is coming), and it doesn't matter how much oversampling you do. No matter how large the oversampling is, these two methods do NOT converge to a common "perfect" image as our intuition might lead us to believe. The filtering method definitely matters, even at extreme levels of oversampling like this.

When comparing these test images, don't be distracted by the slightly different coloring; these images were both colorized by the same method, but this method uses the distribution of fractal count data to generate the color map, and since the different filtering techniques generate slightly different count distributions in the final, filtered images, the colorings are slightly different. The important thing is to compare the level of detail between the two. Not in the very central white spot, which is overwhelmed by moire. Check out the peripheral areas to see where more fine structure is evident.

The median filtered images do take longer to render. It is easier to add a whole bunch of elements in a list than it is to find the median element in that list. As the list gets longer, this problem gets larger. It took about 95 hours to render the median filtered image and only about 35 hours for the mean filtered one.

I will post the 16x16 and 32x32 images later. I also want to generate histograms of the two 256x256 images and also try maybe a 2D fourier transform to see if the obvious visual noise can be demonstrated on a power spectrum. And of course, comparing the 16x16 and 32x32 images to the 256x256 images will be helpful too. If there isn't a huge difference between the lower degrees of oversampling and the extreme oversampling, it may not be worth going too crazy with this. These things typically obey the 80-20 rule since some kind of relationship like Performance = sqrt(Effort) typically shows up somewhere.


(http://www.fractalforums.com/gallery/0/359_30_09_09_3_46_52_1.jpg)
This is the mean filtered oversampled image. The raw BMP file is at http://www.hpdz.net/images/TechPics/AA3-256x256-Mean.bmp (http://www.hpdz.net/images/TechPics/AA3-256x256-Mean.bmp)

(http://www.fractalforums.com/gallery/0/359_30_09_09_3_46_52_0.jpg)
This is the median filtered oversampled image. The raw BMP file is at http://www.hpdz.net/images/TechPics/AA3-256x256-Median.bmp (http://www.hpdz.net/images/TechPics/AA3-256x256-Median.bmp)

The pseudo-Poisson grid is almost as good, and far simpler to implement: divide the region to be oversampled into NxN subregions. Within each subregion pick a randomly located point to evaluate. This turns out to give very nearly the same spectral properties as the ideal Poisson grid with vastly less computational effort.

the superior spectral noise properties of the best candidate algorithm are easily seen in comparison to jittered sampling  O0

Jittered sampling will only reduce moire, and only "reduce" it in the sense that it turns it into white noise. Otherwise, jittered supersampling has no particular advantage over regular grid supersampling, at least none that I know of.

If you have an example of this effect your are referring to, I would like to see it.

Revision: You are referring to something different than my comment addresses, I see now. I think that for most applications, the distributions of the supersampling points doesn't matter. For dealing with moire-ridden areas, it matters a lot. Still I think that the pseudo-Poisson jittered grid is pretty darn close to a true Poisson set of supersampling points, close enough that there is almost no perceptible difference in actual images visually (maybe some spectral analysis can distinguish them).

I still invite and encourage a comparison of the jittered pseudo-Poisson grid to the best-candidiate grid.

And I also still think that the filtering method is critical, as an independent matter from the arrangement of the supersampling points.

I would love to hear any further opinions or analysis on this.

i think we've both done the tests (just had a look around your site) :)

my comment should have been prefaced with "for most imaging purposes": the superior reconstruction attained by sampling patterns with blue noise properties is most prominent in low frequency regions, whereas fractal imaging is usually full of very high frequencies.

Can you post the coordinates of those images, and the number of iterations used to render them? They both seem pretty noisy for all the effort put into them. I'd like to try a crack at them using a different coloring scheme that greatly reduces the appearance of noise.

Sure. I will post the coordinates and iteration count tonight when I get back home. I have a few other demo images too from different locations.

They are really noisy, yes, but you should see the unfiltered version!! Since there is an infinite amount of noise in the underlying "signal" (the "true" image of the Mandelbrot set in infinite detail) no amount of filtering is going to make a noiseless image, but I do agree that it is disappointing to see how MUCH noise there is even after this much filtering.

My main purpose here is to contrast the median filter with a simple average as the way of reducing the supersampled data set. I think the median filter does a better job.

What different coloring scheme were you going to try?

My app, FractalWorks, offers both log color change and color change based on a histogram of the plot. For histogram based color tables, iteration values that occur frequently get a large color change, and iteration values that occur infrequently get a small color change. Color change is proportional to a color's popularity in a plot.

This causes areas with very rapid change in iteration value to use smaller color changes so you don't get a riot of color in a small space.

Histogram-based colors have the effect of reducing the amount of color change in areas with "high frequency", which lowers the amount of visual noise.

FractalWorks will also use fractional iteration values to interpolate colors between individual iteration values to avoid color bands.

Finally I can introduce color change based on the distance estimate (DE) value of a pixel. The closer a pixel is to the Mandelbrot/Julia set, the more weight I apply a "close to the set" color.

Here is a sample image from a similar area of the Mandelbrot set. This image doesn't use ANY supersampling or antialiasing. It is a pure 1000x1000 pixel plot using histogram based colors (and distance estimates to create a rapid change in color for pixels very near the Mandelbrot set.) It is saved as a JPEG directly from FractalWorks.

Usually for images I am posting to a forum I'll render them at 2x the target size and then downsample them using Photoshop's bicubic method, which does a decent job of antialiasing. I wanted to show a "pure" image for this thread however.

This plot took less than a second to render on my 8-core Intel Xeon Macintosh. If I turn off multithreading it takes a little less than 4 seconds.

(http://www.fractalforums.com/gallery/0/190_01_10_09_3_55_26.JPG)


Document name:   Fractal Forums sample
Fractal type:   mandelbrot
Plot size (w,h):   1000,   1000
Maximum iterations:   50000
Center Point (real, imaginary):   -0.74886,   0.069278 i
Plot Width (real):   0.00222

The max iteration count of 50000 was overkill for this image. The average number of iterations was about 400, and it doesn't have any blobs in the middle with a max iteration count of 5000. I just slapped in a high number to make sure there weren't any artifacts from using too low a max iteration value.

Here are the coordinates:

X (Real axis): -0.7446103231585
Y (Imag axis): 0.0865319890292
Size: 8e-6
Iteration limit: 50000

Here are the unfiltered images, shown with the histogram method that Duncan C described (well, my implementation of what I believe to be essentially the same technique) and my rank-order method that was used to colorize all the supersampled images. You can see that neither colorizing technique is particularly effective at reducing the noise inherent in this image.

Original uncompressed BMP files are at www.hpdz.net/images/TechPics/AA3-Unfiltered-Histogram.bmp (http://www.hpdz.net/images/TechPics/AA3-Unfiltered-Histogram.bmp) and www.hpdz.net/images/TechPics/AA3-Unfiltered-RankOrder.bmp (http://www.hpdz.net/images/TechPics/AA3-Unfiltered-RankOrder.bmp)

Histogram colorizing image is below:
(http://www.fractalforums.com/gallery/0/359_01_10_09_4_51_54.jpg)

Rank-Order colorizing image is below:
(http://www.fractalforums.com/gallery/0/359_01_10_09_4_52_51.jpg)

HPDZ,

Did you see my sample image, one post above yours? It looks like you posted while I was composing me message so you may not have gotten notice.

When I created my image I had not gotten your coordinates, so I guessed.


Duncan C

Duncan,

Yes, I did see it, but I forgot to comment on it last night.

It definitely looks less noisy than my test images. I would be interested in seeing how your coloring method works on the area that I'm using to make my test images. Please give it a try if you have some free time.

Mike

Here's my version of your plot:

(http://www.fractalforums.com/gallery/0/190_02_10_09_3_51_35.JPG)

That plot is harder to do cleanly than the one I posted. It has a higher average iteration count, for one thing.

Again, this is rendered without any antialiasing. If I wanted a high quality image I would create an oversized image and downsample it.

Using distance estimate data to color pixels near the set makes a big difference in clarity.


Regards,

Duncan

Duncan,

This image looks pretty darn good. I seem to recall you described your use of the DE to color pixels near the set somewhere previously; could you direct me (and future readers of this thread) to that post, or perhaps describe your method again?

I do notice that the color palette you use is kind of low-contrast; visually, that of course makes it hard to discern how much noise there is. That is why I use an RGB-white (or sometimes a more complex one, like white-magenta-red-yellow-green-cyan-blue) palette for this kind of thing; it is a bit ugly but shows the noise with great contrast.

I am still thinking that a couple of big questions are on the table:

1. Is the median filter better than a mean filter (or any other type of linear filter) as the thing to do the down-sampling from the supersampled data (I believe it is, although it may not be the absolute best possible filter)

2. Does increasing the supersampling grid size make the details of the filter irrelevant -- that is, do all "reasonable" filters converge to the same thing when applied to an NxN supersampling grid, as N gets arbitrarily large? I think the answer is definitely NO.

To further explore item (1) I am going to generate a bunch of statistics on the distributions of counts in the vicinity of the boundary of the set, then apply a median filter and a simple mean filter (and maybe some more complex linear filters) to it and see what happens. I think the median filter is superior because it is so robust against outliers, and I suspect the count distribution near the edge of the set is highly skewed. The mean filter, and variations on it, will over-emphasize the tails of the distribution and result in much noisier output. I don't think this question has been explored much in the DSP literature, actually. Maybe some young EE grad student could take this up as a project....

I consider item (2) closed, since it is patently obvious that a filter like the mean will always give a totally different value than the median for a noisy process with a skewed distribution, no matter how large the supersampling grid is. Which filter is "better" is a different matter, but I think the question of whether the images converge to a single, common, "perfect" image as the supersampling grid gets infinitely large is definitely not what actually happens.

OK. Fascinating topic. I have bugs to kill now on other issues, and an early day tomorrow. (I get to go shoot some guns at the firing range of our Sheriff's department tomorrow; should be fun).

Mike

Mike,

The DE algorithm is documented in "The Science of Fractal Images." There are versions for both Mandelbrot and Julia sets. If you don't have that information, let me know. I think there are also some websites that describe it.


Here's what I do:

Users specify a color to use for "near neighbor" pixels that are closer than some threshold value to the set.

Users can specify a threshold DE value. Pixels with a DE value > the threshold are unchanged.

Users can also specify an adjustment value which changes the curve used to apply color change to pixels near the set. (original color * (1-DE_weight) + new_color * DE_weight for each color channel)

There is also an option to suddenly change a pixel's color if it's DE value is small enough (if the pixel is close enough to the Mandelbrot/Julia set) instead of a transition from the original pixel color to the "near neighbor" color.

The pixel coloring code:

Scales the DE value based on pixel size (plot_width_real /  pixels_wide)

Selects pixels with DE value <= threshold.

calculates DE weight value 0.0 -> 1.0, and large near set:

   DE_weight = (threshold - DE_value) / threshold

Adjusts DE weight value using adjustment factor ranging from .01 to 6:

   DE_weight = (1-DE_weight)^adjustment_factor)

Adjustment factors <1 cause slow color change further from the set and rapid color change for pixels near to the set.

Adjustment factors >1 cause rapid color change further from the set and slow color change near to the set.

An adjustment factor of 1.0 applies a linear transition. (since X^1 = X for all X)

Finally,

Use DE_weight to adjust color of pixel from starting color to neighborhood color (original color * (1-DE_weight) + new_color * DE_weight for R,G, and B color values separately.)



Sorry it took me so long to respond. I had bugs to squash myself.

Is that understandable? This stuff is hard to describe briefly and clearly.

Duncan C

Duncan,

I will digest this when I have some time later this week. At first glance it looks like it can be broadly categorized as a very wickedly complicated, nonlinear, and non-supersampling filter.

So really, strictly speaking, it is not quite actually doing anti-aliasing, although it certainly produces nice results.

Mike

"Very wickedly complicated?" Nah. It's just a non-linear way of coloring pixels that are close to the Mandelbrot/Julia set. You can also simply force pixels who's DE value is below some threshold to a different color. That produces a noisy-looking image however. Using a non-linear color transition "feathers" the color change with much less computations than supersampling.

Raising a value from 0 to 1 to a power >0  <=6 allows you to easily adjust the slope of the transition to be steeper at either the beginning or the end. I use that approach in several places in my program. I also use it to adjust the steepness of my 3D height maps.


Duncan C

Duncan,

By "very wickedly complicated" I was comparing to traditional digital filters. Operationally, from the standpoint of fractal software, it is pretty straightforward. But mathematically, its properties as a digital filter are very tricky to characterize (I'm not even sure you could define a reasonable modulation transfer function for it). Indeed, its behavior is not even spatially constant -- it does different things to similar input data depending on how close to the edge of the M-set you are.

What's interesting about your approach is that is may actually be true anti-aliasing of the fractal image in a way I had thought was impossible. It is effectively band-limiting the signal prior to sampling by using the DE to detect areas that have above-Nyquist spectral energy and replacing them with a smooth, band-limited function. Using the DE is kind of like having a little angel sitting there at the front of your digital sampling process looking at the data that is about to go into each sample and deciding whether there is likely to be too much above-Nyquist energy. The DE "knows" whether a pixel is going to have an area of extreme noise because it can detect proximity to the set.

This approach obviously relies heavily on the fact that the underlying signal that is being sampled is the Mandelbrot set (or a fractal like it) and cannot be generalized to arbitrary digital images, for which there is no way to create the magic angel that tells you when you are getting into an area of out-of-band noise.


I like it.

Mike

Mike,
 
I'm not sure it's a filter, in the way the term is usually used.

Since fractals like the Mandelbrot set have an infinite level of detail, the terms usually used for spectral analysis are not strictly applicable

My histogram-based color scheme accomplishes a similar result. The number of pixels at a given iteration value is at least roughly inversely proportional to the frequency of change at that iteration value. Thus, if you use a small color change between pixels for iteration values that occur infrequently, you hide data that appears as noise at your current sampling frequency (aka pixel grid size). As the pixel count for a given iteration value goes up, the color delta between iteration values increases also.


Duncan C

I'm sure! Spectral analysis is no stranger to infinite detail in one domain or other. In a general situation, you have point sampled data at some resolution. Lacking other information, the simplest way to antialias is to supersample and combine with some filter kernel. But if you convert the data to a distance field, each point contains implicit data about nearby points. Then you can take fewer samples for the same quality result. Taking just one sample still gives a better result than several samples of the raw data would. Creating the distance field from the raw samples is itself a filter operation; it just happens that with the DE formula you don't need to process the individual samples to get the value. It is a shortcut for what can be a relatively expensive filter (depending on the number of dimensions and the bounds.)

The DE can be used for any differentiable function. However there are issues with fractals having negative exponents or inversions, as regions of apparent inside or outside tend to be embedded in each other, even with high bailout and iteration limits. At least in my limited experiments with this.

Mike,

Histogram-based coloring does much the same thing. It decreases the color change between iteration values when the rate of change is high, and increases the color change between iterations when the rate of change is low. This has the effect of hiding changes that occur too fast for the current pixel size.


Duncan C

Mike,

I see you always apply filtering to the iteration values, not the colors. Although this preserves the color tone typical for the subsamples, it leaves in some noise regardless of the filtering type you use (mean or median). In my opinion, filtering the colors (RGB values) is the only efficient way to remove noise, but it has the unpleasant effect of turning the noisy parts of the image into middle gray, because as you use more subsamples, the average of their RGB values converges to 128.

I use a compromise in my own fractal generator application. After calculating the n*n subsamples, I sort them into increasing order, but instead of picking the median and computing the color for it, I compute the colors for the middle half of the samples (the values between the 1/4 and 3/4 of the array), and take the average of these colors. This method filters out the outlier values, just like your median filtering does, has less noise than the median filtering, and doesn't produce such a dull output as the mean filtering of colors.

See the attached images. The first one was rendered with mean filtering applied to the colors, the second one with median filtering of the iteration values, and the third one with the combined method described above. All images were computed using 8*8 supersampling.

Botond

Sorry, I couldn't attach the third image to my previous post.
So here it is.

Sadly, all three still have some "false ripples" (don't know if there's a name for them) near the center of the seahorse, which is another one of the effects that anti-aliasing is trying to avoid. Has anyone ever tried over-sampling on a hex grid, then taking all the hexagons within the square for the down sampling? Could maybe get rid of the ripples; at the same time, might introduce new ones.  :hmh:

I see, there is still some moire in the center of the image. In fact, the simple mean filtering of colors is best at removing this (but it spoils the saturation of the colors). Btw, anyone tried the color filtering in the HSL space instead of RGB? Maybe that could keep the saturation on a higher level.


I implemented this in a previous version, but it had no visible effect on removing the moire patterns. Stochastic supersampling (Poisson disc & others) may be better suited for this.