Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I have an image, with pixels that can be either 0 or 1. For simplicity, assume it's a 2D image (though I'd be interested in a 3D solution as well).

A pixel has 8 neighbors (if that's too complicated, we can drop to 4-connectedness). Two neighbouring pixels with value 1 are considered to be connected.

If I know the probability p that an individual pixel is 1, and if I can assume that all pixels are independent, how many groups of at least k connected pixels should I expect to find in an image of size n-by-n?

What I really need is a good way of calculating the probability of k pixels being connected given the individual pixel probabilities. I have started to write down a tree to cover all the possibilities up to k=3, but even then, it becomes really ugly really fast. Is there a more clever way to go about this?

share|improve this question
    
You are attempting to do what's known as "polyomino enumeration". This is in general quite difficult. –  Michael Lugo Jul 28 '10 at 12:38
    
In the 4 neighbor case I think this breaks down to a series of 1d problems. I'm not sure if that is the case in 8 neighbor case. –  Jonathan Fischoff Jul 28 '10 at 17:00
add comment

2 Answers

up vote 4 down vote accepted

This looks a bit like percolation theory to me. In the 4-neighbour case, if you look at the dual of the image, the chance that an edge is connected (runs between two pixels of the same colour) is 1-2p+2p^2.

I don't think you can get nice closed-form answer for your question, but maybe a computer can help with some Monte Carlo simulation?

share|improve this answer
add comment

I have to admit that I'm not very good at math but I took a piece of paper and made some thoughts with some graphics and got to the following idea:

Let's say that the probability of hitting a specific pixel is the same for every pixel you have, then you can describe the probability to be

P(X=x1) = a

Then the probability to hit the exact same pixel is much lower (by square) if you assume independency so that

P(X=[x1;x1]) = P(X=x1)*P(X=x1) = a*a

Now if you assume 8 neighbours that you'll count as hits (as positive events) then you are increasing the probability by 8 for the second multiplicator, because you don't just want to have the exact same pixel but one of 8 more than that. Since you assume every pixel to have the same probability and that they are independent (which is, I assume, not the case for real graphics) you'll get

P(X=[x1;[x2;x3;x4;x5;x6;x7;x8;x9]]) = a*(a+a+a+a+a+a+a+a) 

P(X=[x1;[x2,...,x9]]) = a*(8*a) = 8*a^2

This seems legit since hitting the exact same pixel has to be clearly less probable then the exact same pixel plus one of 8 other pixels around.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.