iev
Guest


« on: May 28, 2007, 10:22:52 PM » 

Hello, I am new to this forum and also in fractals. I am trying to learn and as a start, I have written a simple, multithreaded application that calculates the Mandelbrot set. I want to use it as a benchmark, because it is easy to parallelize (each pixel can be calculated independently), but irregular (we don't know how many iterations we need to calculate each pixel). Everything seems to work fine and since I got up to this point, I thought that it would be nice to produce also some output images. However, I have some trouble finding a good way to map colors to the image. Currently, the best I have achieved is based on a simple linear mapping and looks like this: Not very good and certainly far from my favorite color mapping, which looks like this: http://en.wikipedia.org/wiki/Image:Mandelpart2.jpgUnfortunately, I can't figure out which algorithm is used to produce this mapping of colors. Does anyone know the answer? I would like to use it in my program. By the way, I am currently using the libtiff library to write out the image, which means that I need RGB values. I don't know if it is really relevant, but I mention it because I have seen some algorithms use other things, like Hue, Saturation etc. Thanks for any help!



Logged




Duncan C


« Reply #1 on: May 29, 2007, 01:02:26 AM » 

Hello, I am new to this forum and also in fractals. I am trying to learn and as a start, I have written a simple, multithreaded application that calculates the Mandelbrot set. I want to use it as a benchmark, because it is easy to parallelize (each pixel can be calculated independently), but irregular (we don't know how many iterations we need to calculate each pixel). Everything seems to work fine and since I got up to this point, I thought that it would be nice to produce also some output images. However, I have some trouble finding a good way to map colors to the image. Currently, the best I have achieved is based on a simple linear mapping and looks like this: http://i17.tinypic.com/6gwlpg4.png Not very good and certainly far from my favorite color mapping, which looks like this: http://en.wikipedia.org/wiki/Image:Mandelpart2.jpgUnfortunately, I can't figure out which algorithm is used to produce this mapping of colors. Does anyone know the answer? I would like to use it in my program. By the way, I am currently using the libtiff library to write out the image, which means that I need RGB values. I don't know if it is really relevant, but I mention it because I have seen some algorithms use other things, like Hue, Saturation etc. Thanks for any help! Greetings iev! Welcome to the forum. I'm pretty new here myself, although I've been playing with fractals for quite a while now. As you've discovered, linear color tables are not a very good choice for plotting Mandelbrot and Julia sets. The problem is that the size of the iteration "bands" is large at low iteration values, and VERY small at high iteration values. When you get to very high iteration values, you might not have any contiguous pixels with the same iteration value. There are a number of approaches you can use to get better colors. You can use a distance estimator algorithm to get a fractional iteration value. There's a section in the book "The Science of Fractal Images" (published by SpringerVerlag, edited by Peitgen & Saupe), starting on P. 192, that describes this in some detail. The algorithm there is used to create black and white "near neighborhoods" of Mandelbrot and Julia sets, but it can also be used to create smooth color gradients where the color changes with the approximate distance from a point to the nearest part of the Mandelbrot/Julia set. I'm planning to add support for a distance estimator to my application, FractalWorks. You can use an exponential color table, where the change in color is the exponent of the iteration value, so that colors change more rapidly at low iteration values and more slowly at higher iteration values. I've had good luck using this approach. Another apporach that works quite well is to use a histogram of the plot to calculate your color table. You add up the number of pixels at each iteration value, and have the amount of color change equal the portion of pixels in the plot at that iteration value. The lowest iteration value gets the starting color value, and the next iteration value is X% of the way from your start color to your end color, where x is the sum of the number of pixels at the current and lower iteration values. At the highest iteration value, the transition to the end color is complete. The histogram approach has the advantage that it adapts automatically to the distribution of pixels in your plot. Here is a link to a screenshot from my application, FractalWorks, that graphically illustrates this approach. Click here to see the image from which this histogram is generated. I have a small sample of Mandelbrot and Julia images in a fractal gallery you can view by clicking here. Nearly all of this images use histogrambased color tables. Let me know if you need a more detailed description of any of the approaches I've described. Duncan C


« Last Edit: May 31, 2007, 06:53:53 AM by Nahee_Enterprises »

Logged

Regards,
Duncan C



Nahee_Enterprises


« Reply #2 on: May 29, 2007, 01:14:08 AM » 

I am new to this forum and also in fractals. I am trying to learn and as a start, I have written a simple, multithreaded application that calculates the Mandelbrot set. First of all, Greetings and Welcome to this particular Forum !! Unfortunately, I can't figure out which algorithm is used to produce this mapping of colors. Does anyone know the answer? I would like to use it in my program. By the way, I am currently using the libtiff library to write out the image, which means that I need RGB values. What are you using to set the initial colors for each of the generated pixels?? Do you use something like the .MAP files used by FractInt and many other fractal rendering applications?? http://spanky.triumf.ca/www/fractint/color_params.html http://spanky.triumf.ca/www/fractint/palette_maps.html Are you looking for various coloring techniques such as those found in "The Beauty of Fractals" (pages 60 thru 62)?? http://spanky.triumf.ca/www/fractint/append_a_misc.html



Logged




Duncan C


« Reply #3 on: May 29, 2007, 01:43:44 AM » 

Iev, I took a quick stab at duplicating the colors from your example image. I just took the starting and ending colors from the sample image using an eyedropper tool, and created a plot with a single histogram based color gradient from redorange to black. Here's what I came up with: It seems pretty close. Duncan C



Logged

Regards,
Duncan C



iev
Guest


« Reply #4 on: May 29, 2007, 09:35:13 PM » 

Hello again, Firstly, let me thank you for answering. However, your answers created a few more questions for me As suggested, I had a look at the .MAP files used by FractInt. As far as I can tell, they support only 256 colors. Is this right? On the other hand, I am currently using libtiff, so my color space is larger. I use 1 byte for each one of the RGB values, which gives me a total of 16 million colors (from 0 to 0xFFFFFF). The question is, can I use all these colors or are they far more than I need? I am also not certain that I understand this question: "What are you using to set the initial colors for each of the generated pixels??" I also constructed the histogram, as suggested by Duncan, but I stuck again at the last part: How do I map each value of the histogram into an RGB value that is close to the previous color I used? I checked the links Duncan provided, but I am not certain how he did this part. As a reference, I have the code here that calculates the histogram and also the part that causes me trouble. Just to make sure that I am doing the right thing. /* * xpixels, ypixels: The number of pixels on the horizontal and vertical axis * IterationsPerPixel: Stores the number of iterations required to reach the bailout value, for each pixel. * * I check each pixel 'i'. Depending on how many iterations were needed, I update the histogram. * We need at least 1 iteration for each pixel, which is why I subtract 1, to update the correct element * in the histogram. */ for (i = 0; i < xpixels * ypixels; i++) { Histogram[IterationsPerPixel[ i ]  1]++; } /* * Create the sum of all previous histogram values. * 'NumOfIterations' is the maximum number of iterations that we check each pixel, * before we decide that it belongs to the Mandelbrot set. */ for (i = 1; i < NumOfIterations; i++) { Histogram[ i ] += Histogram[i  1]; } /* * Iterate again over all pixels */ for (i = 0; i < xpixels * ypixels; i++) { Red[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) Green[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) Blue[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) } So, my question is, how do i fill in the last loop? Is the number of iterations to reach the bailout value enough information, or do I have to save more data, i.e. the last value calculated for each point? I feel that I am missing some important point in this part, but what is it? I hope someone has the patience to point out some good reference that I can read or even complete the above loop and explain why it should be as he suggests Thank you for your help! I really appreciate it!



Logged




Duncan C


« Reply #5 on: May 29, 2007, 10:39:57 PM » 

Hello again, Firstly, let me thank you for answering. However, your answers created a few more questions for me As suggested, I had a look at the .MAP files used by FractInt. As far as I can tell, they support only 256 colors. Is this right? On the other hand, I am currently using libtiff, so my color space is larger. I use 1 byte for each one of the RGB values, which gives me a total of 16 million colors (from 0 to 0xFFFFFF). The question is, can I use all these colors or are they far more than I need? I am also not certain that I understand this question: "What are you using to set the initial colors for each of the generated pixels??" I also constructed the histogram, as suggested by Duncan, but I stuck again at the last part: How do I map each value of the histogram into an RGB value that is close to the previous color I used? I checked the links Duncan provided, but I am not certain how he did this part. As a reference, I have the code here that calculates the histogram and also the part that causes me trouble. Just to make sure that I am doing the right thing. /* * xpixels, ypixels: The number of pixels on the horizontal and vertical axis * IterationsPerPixel: Stores the number of iterations required to reach the bailout value, for each pixel. * * I check each pixel 'i'. Depending on how many iterations were needed, I update the histogram. * We need at least 1 iteration for each pixel, which is why I subtract 1, to update the correct element * in the histogram. */ for (i = 0; i < xpixels * ypixels; i++) { Histogram[IterationsPerPixel[ i ]  1]++; } /* * Create the sum of all previous histogram values. * 'NumOfIterations' is the maximum number of iterations that we check each pixel, * before we decide that it belongs to the Mandelbrot set. */ for (i = 1; i < NumOfIterations; i++) { Histogram[ i ] += Histogram[i  1]; } /* * Iterate again over all pixels */ for (i = 0; i < xpixels * ypixels; i++) { Red[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) Green[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) Blue[ i ] = Some function of Histogram[IterationsPerPixel[ i ]  1] ?? (But must have a value between 0  255) } So, my question is, how do i fill in the last loop? Is the number of iterations to reach the bailout value enough information, or do I have to save more data, i.e. the last value calculated for each point? I feel that I am missing some important point in this part, but what is it? I hope someone has the patience to point out some good reference that I can read or even complete the above loop and explain why it should be as he suggests Thank you for your help! I really appreciate it! iev, Like I said in my previous note, there are many different ways to tackle this problem. Here's what I do: I store the iteration value for every pixel, and assign colors "on the fly" to the display. That lets me change the colors used for a plot at some future date, which is very useful. I divide the plot into one or more ranges of iterations. For each range, I assign a start and end RGB color. I then create a percent table that specifies the percent of the start and end color for each iteration value. 0% would specify 100% start color, and 0% endcolor. 100% would be 0% start color and 100% end color. (I call it a percent table, but I actually store a fixed point decimal value from 0 to 1.) For histogram based plots, I first calculate a cumulative iteration total for all iterations in a range. I then go back to the first iteration value and start a running total of all the pixels with iteration values lower than that value. I assign a percent value for that iteration count which is the running total divided by the cumulative total. I have my code adjusted so the lowest iteration value in a range always gets a percent value of 0, and the highest iteration value in a range always gets a value of 1. The inbetween iteration values get a decimal value somewhere between 0 and 1. I use the same approach for exponential, linear , or other color tables. Once I have percent tables for each of the iteration ranges I've assigned, I go back and create an RGB triplet for each iteration value like this:  red_chage = end_red  start_red; green_change = end_green  start_green; blue_change = end_blue  start_blue; for(i= start_iteration; i < end_iteration; i++) { iteration_red(i) = start_red + red_change * percents(i); iteration_green(i) = start_green + green_change * percents(i); iteration_blue(i) = start_blue + blue_change * percents(i); }  (My actual code looks quite different. This is simplified pseudocode I just slapped together to illustrate the concept. Also note that when I try to use i as an array index in C, the open bracket i close bracket sequence is being parsed as HTML. I had to change to parentheses.) Note that you could also calculate the transition from start color to end color using HSV or some other color model, but I've found that RGB values work fine, and are quite fast. Since my percent table is a fixed point number, I don't even have to do any floating point calculations to draw the pixels to the screen. Your sample code first creates a histogram for the plot. That's good. however, you then replace the values in your histogram table with running total values. I would not suggest doing that, since you might want to use the histogram several different ways. Duncan C


« Last Edit: May 29, 2007, 11:09:23 PM by Duncan C »

Logged

Regards,
Duncan C



Nahee_Enterprises


« Reply #6 on: May 30, 2007, 11:38:49 AM » 

Firstly, let me thank you for answering. However, your answers created a few more questions for me As suggested, I had a look at the .MAP files used by FractInt. As far as I can tell, they support only 256 colors. Is this right? Yes, the .MAP files are basically setup for a 256color palette. You may wish to take a look at using some form of gradient file to choose from when coloring the fractals. There are several programs that use this technique. One of the most popular is UltraFractal, which use .UGR files, and looks something like this: Default { gradient: title="Default" smooth=yes numnodes=4 index=0 color=16711680 index=100 color=16777215 index=200 color=65535 index=300 color=255 } Grayscale { gradient: title="Grayscale" smooth=no numnodes=2 index=0 color=0 index=200 color=16777215 } Royal { gradient: title="Royal" smooth=yes numnodes=4 index=0 color=9043968 index=69 color=3158085 index=150 color=14736366 index=302 color=675176 } On the other hand, I am currently using libtiff, so my color space is larger. I use 1 byte for each one of the RGB values, which gives me a total of 16 million colors (from 0 to 0xFFFFFF). The question is, can I use all these colors or are they far more than I need? I doubt that a single image will ever use all of the 16 million colors. But in the long run of producing fractal images, they may all get used at some time.



Logged




iev
Guest


« Reply #7 on: May 30, 2007, 07:02:43 PM » 

Hello and thanks again for your help. I think that I understand now how the linear mapping and the UGR files work. I will experiment a little bit and hopefully come back with some nice results.



Logged




iev
Guest


« Reply #8 on: June 03, 2007, 01:19:47 AM » 

Hello everyone, I experimented a bit with the method that Duncan suggested and I came up with the following picture: Seems quite nice and similar to the one I wanted. My program is still not general enough, but the more I understand the method, the more I will work to overcome this problem. Thanks again for all your suggestions and help!



Logged




Duncan C


« Reply #9 on: June 03, 2007, 04:11:07 AM » 

Hello everyone,
I experimented a bit with the method that Duncan suggested and I came up with the following picture:
Seems quite nice and similar to the one I wanted. My program is still not general enough, but the more I understand the method, the more I will work to overcome this problem.
Thanks again for all your suggestions and help!
iev, It looks like you've got it. That looks almost identical to the image I posted.



Logged

Regards,
Duncan C



Nahee_Enterprises


« Reply #10 on: June 03, 2007, 10:36:07 AM » 

Hello everyone, I experimented a bit... Seems quite nice and similar to the one I wanted.
Thanks again for all your suggestions and help! Yes, your image is colored almost exactly like the original you referenced at: http://en.wikipedia.org/wiki/Image:Mandelpart2.jpg More so than the one which Duncan posted, which does not pick up the yellow tones. But Duncan's seems to show more of the details than yours does. It is almost as though yours has been antialiased to the point of blurring.



Logged




lycium


« Reply #11 on: June 03, 2007, 03:16:00 PM » 

But Duncan's seems to show more of the details than yours does. It is almost as though yours has been antialiased to the point of blurring.
as an antialiasing fetishist, i must say iev's render is exceptionally well done. edit: take a close look at the edges, you'll find they are much better defined; moreover, the interior gradients are much smoother and the whole thing has more contrast and is very crisp. where do you see loss of detail?


« Last Edit: June 03, 2007, 03:19:21 PM by lycium »

Logged




Duncan C


« Reply #12 on: June 03, 2007, 03:33:53 PM » 

Hello everyone, I experimented a bit... Seems quite nice and similar to the one I wanted.
Thanks again for all your suggestions and help! Yes, your image is colored almost exactly like the original you referenced at: http://en.wikipedia.org/wiki/Image:Mandelpart2.jpg More so than the one which Duncan posted, which does not pick up the yellow tones. Looking more closely at the original, I think you're right. My image misses the yellow tones in the original. I wonder if the original is more than just a single gradient? Upon inspection, it looks like the original might use a black to orange gradient, blended smoothly into an orange to yellow gradient. iev, How did you get the colors in your image? Duncan C



Logged

Regards,
Duncan C



iev
Guest


« Reply #13 on: June 05, 2007, 12:01:55 AM » 

Hi Duncan, I have defined a total of 7 ranges of colors. 3 of them are in the red color zone, i.e., in the RGB space, R moves from 0 to 255 and G and B are constantly 0. The next 4 ranges are in the orange to yellow color zone, i.e., R is constantly 255, G moves from 0 to 255 and B is constantly 0. My current algorithm assigns linearly colors within each range, depending on the number of iterations required to decide if a pixel belongs or not in the set. The pseudocode to assign a color to each pixel 'i' looks like this: if (IterationsPerPixel == MaxIterations) { (R,G,B) = (0, 0, 0); /* In the set. Assign black. */ } else if (IterationsPerPixel < 64) { (R,G,B) = (IterationsPerPixel * 2, 0, 0); /* 0x0000 to 0x007E */ } else if (IterationsPerPixel < 128) { (R,G,B) = ((((IterationsPerPixel  64) * 128) / 126) + 128, 0, 0); /* 0x0080 to 0x00C0 */ } else if (IterationsPerPixel < 256) { (R,G,B) = ((((IterationsPerPixel  128) * 62) / 127) + 193, 0, 0); /* 0x00C1 to 0x00FF */ } else if (IterationsPerPixel < 512) { (R,G,B) = (255, (((IterationsPerPixel  256) * 62) / 255) + 1, 0); /* 0x01FF to 0x3FFF */ } else if (IterationsPerPixel < 1024) { (R,G,B) = (255, (((IterationsPerPixel  512) * 63) / 511) + 64, 0); /* 0x40FF to 0x7FFF */ } else if (IterationsPerPixel < 2048) { (R,G,B) = (255, (((IterationsPerPixel  1024) * 63) / 1023) + 128, 0); /* 0x80FF to 0xBFFF */ } else if (IterationsPerPixel < 4096) { (R,G,B) = (255, (((IterationsPerPixel  2048) * 63) / 2047) + 192, 0); /* 0xC0FF to 0xFFFF */ } else { (R, G, b) = (255, 255, 0); }
How did I decide to use these ranges? Currently, it is trial and error Why do I check only up to 4096 iterations? This is currently my default maximum. These ranges and assignments work quite well if you work near the set, but really bad if you want to depict the whole set. What I am trying currently to do, is to generalize this method. Firstly, I would like to find an automated way to define the color ranges. Secondly, I would like to automate the way to define the iteration ranges. Finally, I want to automate the mapping between them. I am trying to combine this with the method that Duncan suggested, but had no success until now.
Duncan, you mention that you "divide the plot into one or more ranges of iterations". Is this statically determined? What are your criteria to say that here starts a range and there it ends?
You also mention that "For histogram based plots, I first calculate a cumulative iteration total for all iterations in a range." What do you mean with this? If, for example, the first range is from iteration 1 to 64, what would this total be? Is it something like this?
(Num of pixels requiring 1 iteration) * 1 + (Num of pixels requiring 2 iterations) * 2 + ... + (Num of pixels requiring 64 iterations) * 64
If this is the case, then I don't understand what this sum represents and why it should be used to assign colors. However, I understand the rest of your method, assuming that this total is known. Obviously, I am missing something here.



Logged




Duncan C


« Reply #14 on: June 05, 2007, 01:25:54 AM » 

Hi Duncan,
I have defined a total of 7 ranges of colors. Duncan, you mention that you "divide the plot into one or more ranges of iterations". Is this statically determined? What are your criteria to say that here starts a range and there it ends?
iev, My application has a user interface for assigning colors. The UI lets users create color "schemes" with one or more color gradients, or "bands". Each color gradient starts at a low iteration count, and goes to the beginning of the next iteration band, or the highest iteration value. A color band can be anchored at a fixed iteration value, or using the plot histogram. If a color band is anchored using the plot histogram, the user specifies a percent value. (say, 20%). The program then uses the plot histogram to find the iteration value where 20% of the pixels have a lower iteration count. It uses that iteration count as the start of the iteration band. This works well because it means that the same color scheme adapts to the pixel distribution in a variety of different plots. You also mention that "For histogram based plots, I first calculate a cumulative iteration total for all iterations in a range." What do you mean with this? If, for example, the first range is from iteration 1 to 64, what would this total be? Is it something like this?
(Num of pixels requiring 1 iteration) * 1 + (Num of pixels requiring 2 iterations) * 2 + ... + (Num of pixels requiring 64 iterations) * 64
No, that's not right. Before you do anything, you create an array, histogram[max_iterations] of long integers. Go through every pixel in your image, and count the number of pixels with each iteration count, like this: for x = 1 to width for y = 1 to height pixel_iteration_value = pixel[x,y]; histogram[pixel_iteration_value]++; next y; next x; (It would be more efficient to calculate your histogram as you compute the plot, but that's minor) Next, from your example, say you wanted to create a color band for pixels with an iteration value of 1 to 64. You'd do something like this: for index = 1 to 64; band_total = band_total + histogram[index]; next index; running_total = 0; float percents[1] = 0; for index = 2 to 64; running_total = running_total + histogram[index]; percents[index] = running_total / band_total; next index; At the end of the second loop, your percents array would contain floating point numbers that start at 0 (at percents[0]) and end at 1 (at percents[64]). You can then apply these percentages to your color range. (if percents[index] = 0, use 100% start color. If percents[index] = 1, use 100% end color. If percents[index] = .5, use a color halfway between the start and end color for your range.) Take another look at the image I posted of the image histogram, along with the color gradient it created. It should help you to understand what I am trying to describe. click here to see that image. Duncan C


« Last Edit: June 05, 2007, 01:29:09 AM by Duncan C »

Logged

Regards,
Duncan C



