5
$\begingroup$

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 neighboring 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\times 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?

  • 0
    You are attempting to do what's known as "polyomino enumeration". This is in general quite difficult.2010-07-28
  • 0
    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.2010-07-28
  • 0
    @daOnlyBG: There's no need to change British spellings to American ones.2014-11-21

2 Answers 2

4

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?

0

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.