Hello

I'm trying to make an image filter that computes the optimal transparency key for alpha test purposes.

First it computes the average color at the bounds.

Then it should find the closest color of this color (that is not present in the image) to fill RGB transparent areas.

My problem is : given a manhattan distance, how to find all the permutations of the given color ?

For example for distance=1, the permutations are :

(red+1,green,blue)

(red-1,green,blue)

(red,green+1,blue)

(red,green-1,blue)

(red,green,blue+1)

(red,green,blue-1)

Thanks for your help =)

Nico

You are making it more difficult for yourself and simultaneously more incorrect by wanting to average over a large area.

I think the correct way would be to use premultiplied alpha and transparent black in all invisible areas. If you dont like this then just using the average color of all directly adjacent nontransparent pixels for each pixel you want to fill should be enough.

Thanks you

I don't average along transparenty area, only bounds (ie with a neigbor with alpha==0)

I don't want to use black in transparent areas, because of the smoothing done on the texture, the idea is to have in transparent area a color that is close to non transparent areas borders so that i can round the pixel's borders (if alpha>0.5 then diplay) without having a bad bleeding of colors on the bounds. Hope I'm clear =)

Visualise the Manhattan distance as a cube in 3d space with axes R, G and B.

Then it's easy to permute the possibilities... It's the boundary of a cube of size 2n+1 for a distance n.

EDIT: Hint - you already worked out the vertices of the cube with manhattan distance 1, do the same with n to get the vertices of the cube of manhattan distance n, and fill in the square faces in a loop.

EDIT2: Ooops, no it's not, that's the answer for the max distance metric ;) The correct answer is a diamond with vertices at the points... sorry ;)

EDIT3: That's nearly as easy to visualise though. That's why there are 6 vertices, not 8 as well.

I can express my problem more simply : given an integer, how to find all the decompositions into 3 additions (of positive values) ?

in my example of distance=1, this is just

1+0+0

0+1+0

0+0+1

so 3*2 permutations due to the opposite values

Thanks for reading

The solution is the surface of a symmetric diamond-shape centered at the origin with size d. Have two nested for-loops for the first two coordinates, let's call them A, and B, and solve A+B+C=d for the third coordinate C. That will give you the points on the diamond-shaped solution for one octant in 3D-space. Then apply all eight negation permutations to obtain the points for the remaining octants.

for(int A=0; A<=d; ++A)
    for(int B=0; B<=d-A; ++B)
        add solution ( A,  B,  d-A-B)
        add solution ( A,  B, -d-A-B)
        add solution ( A, -B,  d-A-B)
        add solution ( A, -B, -d-A-B)
        add solution (-A,  B,  d-A-B)
        add solution (-A,  B, -d-A-B)
        add solution (-A, -B,  d-A-B)
        add solution (-A, -B, -d-A-B)

Hope I got the math correct here, it may be off by one somewhere. You may also need to adjust the loops to eliminate duplicates at the end of the loop ranges, since, for example, A=-A when A=0 and so half the points will be the same for that iteration.

This is great ! Thanks a lot !