Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
6 replies to this topic

#1 Tournicoti   Prime Members   -  Reputation: 683

Like
0Likes
Like

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)

 

Thanks for your help =)

 

Nico


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


Sponsor:

#2 wintertime   Members   -  Reputation: 1686

Like
1Likes
Like

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.



#3 Tournicoti   Prime Members   -  Reputation: 683

Like
0Likes
Like

Posted 21 February 2013 - 07:54 AM

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, 21 February 2013 - 08:04 AM.


#4 Paradigm Shifter   Crossbones+   -  Reputation: 5368

Like
1Likes
Like

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

#5 Tournicoti   Prime Members   -  Reputation: 683

Like
0Likes
Like

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

 

Thanks for reading


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


#6 Brother Bob   Moderators   -  Reputation: 8188

Like
1Likes
Like

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



#7 Tournicoti   Prime Members   -  Reputation: 683

Like
0Likes
Like

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.



PARTNERS