massa@uni-paderborn.de (Michael Janich) (01/24/91)
Hi out there, I'm searching for a GOOD algorithm to convert more than 32 colors to HAM. I saw the following: (ppmtoilbm) -Color map are the 16 gray scales (000, 111, ...) -calculate for the 4 possibilities (change red, blue, green or take color map) the differences like delta_green = abs(oldred - red) + abs(oldblue-blue); -take the minimum of these differences. The output is ugly - compared with that from HamLab (in my opinion the best GIF2HAM converter). So I tried -Color map are the 16 most used colors -<rest the same> But now I have green areas in the picture. Can anybody please help me - perhaps with the HamLab algorithm? Do I have to use weighted expressions to calculate the 'delta_[<color>|colmap]'? Perhaps is brighter more bad than dimmer? Thanx for your replies. -- Michael Janich, Uni Paderborn, United Germany
bairds@eecs.cs.pdx.edu (Shawn L. Baird) (01/24/91)
massa@uni-paderborn.de (Michael Janich) writes: >Hi out there, >I'm searching for a GOOD algorithm to convert more than 32 colors to HAM. I >saw the following: >(ppmtoilbm) > -Color map are the 16 gray scales (000, 111, ...) > -calculate for the 4 possibilities (change red, blue, green or take > color map) the differences like > delta_green = abs(oldred - red) + abs(oldblue-blue); > -take the minimum of these differences. >The output is ugly - compared with that from HamLab (in my opinion the best >GIF2HAM converter). Try scanning the picture from left to right, first, calculating contrast differences to locate areas where fringing is likely to occur. Place colors into a colormap until you have allocated all 16 color entries. Then use a similar algorithm as you describe above to determine which color to use. What I do is compute the three possible colors if I change each of the R, G and B values to the value I desire for the next pixel. Then I compare these three colors and the sixteen colors in the colormap to determine which to use. I suppose you could get more detailed in detecting contrast differences, since the difference in the contrast between bright and dark green and bright and dark red would probably no be exactly the same. It may even be more beneficial to convert to Hue-Saturation-Brightness (or whatever) to detect differences in hues specifically. For true excellence change 15 of the palette colors each scanline to dramatically reduce fringing (SHAM or AHAM). | Shawn L. Baird | Or via US Snail: | | bairds@eecs.ee.pdx.edu | 17650 SE Cason Rd. | | ...uunet!tektronix!psueea!eecs!bairds | Gladstone, OR 97027 |
espie@egret.Stanford.EDU (Marc Espie) (01/25/91)
This wouldn't be the most accurate algorithm, but this is what I'd try. - choosing the color palette. There is a known algorithm for reducing the number of colors in an image. Represent your color as points in three-d space (x=red, y=blue, z=green), start with a possible reduced palette (gray shades would be ok). Group the points of the image in clusters: for each point in the image, find the nearest color in the palette (``euclidean'' distance). Replace each color in the palette by the average of its cluster. This process converges, fairly fast, to a good color palette approximating your image. - building the ham image. Use dynamic programming. You have to build a line, each point can have 4096 colors. But the colors the next point can take only depend of the color of the preceding point. Associate a cost to each possible beginning of line, for instance add the distances between computed points and reference points. Now, the cost of a given point in a given color will be the best possible cost for any beginning of line with that point at the end with that value. What you have to build is an array of size 320x4096(point/color) holding: - the cost of the point in the given color. - the color the preceding point should have for attaining that cost. In the end, you just have to take the best cost at the end of line, and retrace back the corresponding best line. For your choice of the palette, what you get is the best possible line for the given cost. For a naive approach, you generate your array till point #i, then you compute the costs for point #i+1. For each couple (point #i/color) compute cost for (point #i+1/new color), where the new color can be attained from (point #i/color). Keep only the best cost for each (point #i+1/color). For a given line, it will take about time on the order of 4096x64x320. Gross isn't it ? You can trim that down, using the peculiarities of ham. Try a first pass with only your 16 palette colors (time on the order of 16x16x320, small!). What have you then ? An already good best cost for some (point/color), which you know you can achieve. When you build the whole array with 4096 colors, you can discard point/colors where you find only greater costs. I don't know how much that reduces the number of point/colors to consider (a difficult problem, you have to take the choice of the palette into account), but I think the algorithm would then be significantly faster. Marc
peterk@cbmger.UUCP (Peter Kittel GERMANY) (01/28/91)
In article <1991Jan23.170826.6194@uni-paderborn.de> massa@uni-paderborn.de (Michael Janich) writes: > >I'm searching for a GOOD algorithm to convert more than 32 colors to HAM. I >saw the following: > >(ppmtoilbm) > -Color map are the 16 gray scales (000, 111, ...) > -calculate for the 4 possibilities (change red, blue, green or take > color map) the differences like > delta_green = abs(oldred - red) + abs(oldblue-blue); > -take the minimum of these differences. > >I tried > -Color map are the 16 most used colors > -<rest the same> First optimization to consider is the coice of the 16 base colors. I tried several attempts but am not yet really satisfied: A) Eliminate neighbored colors (difference only one step or some other "tolerance distance") and let only survive the more used one. I drove this algorithm down to only 16 remaining colors, by starting with a tolerance distance of 1, and when the current tolerance distance leaves too many colors alive, then start again with an increased tolerance, until you end up with 16 colors. But this is VERY time consuming and you get stuck with some very odd colors that appear only in very few (unimportant) pixels, and the net result of all this is also not much better. So I ended up in using only a moderate tolerance distance of 1, max. 2 steps and then using the 16 most used colors. Oh, one detail to add to explanation: When one color is eliminated in favor of a neighbored one, then its count has to be added to the one of the surviving one. >Can anybody please help me - perhaps with the HamLab algorithm? Do I have to >use weighted expressions to calculate the 'delta_[<color>|colmap]'? B) Yes, I also tried weighted distance calculation. My intention was to give more accent to the color tone and lesser to the brightness. Well, but either I did something wrong with my vector formulae (:-) in the 3D color space or this assumption was bad. The result was worse than the normal way. -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk