Sign in to follow this  

Searching closest color using manhattan distance on RGB

Recommended Posts



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 :








Thanks for your help =)



Edited by Tournicoti

Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites

Thanks you smile.png

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 =)

Edited by Tournicoti

Share this post

Link to post
Share on other sites

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.

Edited by Paradigm Shifter

Share this post

Link to post
Share on other sites

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





so 3*2 permutations due to the opposite values


Thanks for reading

Edited by Tournicoti

Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this