View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Searching closest color using manhattan distance on RGB

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1Tournicoti  Prime Members

Posted 21 February 2013 - 07:08 AM

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)

Nico

Edited by Tournicoti, 21 February 2013 - 07:10 AM.

### #2wintertime  Members

Posted 21 February 2013 - 07:35 AM

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.

### #3Tournicoti  Prime Members

Posted 21 February 2013 - 07:54 AM

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

Edited by Tournicoti, 21 February 2013 - 08:04 AM.

Posted 21 February 2013 - 10:57 AM

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, 21 February 2013 - 11:19 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #5Tournicoti  Prime Members

Posted 22 February 2013 - 04:55 AM

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

Edited by Tournicoti, 22 February 2013 - 04:56 AM.

### #6Brother Bob  Moderators

Posted 22 February 2013 - 05:16 AM

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)

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.

### #7Tournicoti  Prime Members

Posted 22 February 2013 - 05:35 AM

This is great ! Thanks a lot !

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.