# probability involving matching of discrete shapes on a square grid

Figure F exists on a regular square grid.

T transforms F by any combination of horizontal or vertical reflection as well as rotation by 90 or 180 degrees.

A larger background grid of X by Y contains noise, where each square has a 50% chance of being 0 or 1.

I am trying to produce a score for the probability that F will match the background grid.

For a match, F or one of its transformations (T) must be able to be compared to the background grid at some location such that the squares that are part of F match the 1s on the background grid but none of the 0s.

The score does not need to be in any particular unit, but must be comparable to other scores.

For example:

F

###
#


Background (X = 7, Y = 4)

0001010
1001101
0101100
0100110


A match occured. I have replaced the units that match with .s, they matched because they were all 1s and formed one of Fs transformations.

0001010
100..01
0101.00
0100.10


I'm currently using (64 / 2 ^ f_squares) + (c - 1) * 2 where c is the transformational symmetry of F, f_squares is the number of squares in F and ^ is "to the power of". I'm looking for a more accurate approximation.

64 / 2 ^ f_squares represents the decreasing probability of a match the more squares that F contains, with (c - 1) * 2 for the additional chance of a match if Fs transformations are different from each other.

-
You probably meant "horizontal or vertical reflection" instead of "horizontal or vertical rotation"? –  joriki Aug 2 '12 at 12:39
Thanks, well spotted. –  alan2here Aug 2 '12 at 13:30
Just a thought, but I wonder if you could apply the Hough transform here, and consider the votes as a sum of iid Bernoulli rvs. –  Arkamis Aug 2 '12 at 13:35
@EdGorcenski Is there an answer in this idea involving Bernoulli. Otherwise I may mark jorikis answer as correct soon after I have tested it, if it works. –  alan2here Aug 2 '12 at 14:58
@alan2here I don't know. It was just a fleeting comment. I'm sure you could do such a thing; I don't know that it would be any easier -- or practical at all. –  Arkamis Aug 2 '12 at 15:01

The probability of getting at least one match is hard to compute, but since you only want a score, you could consider using the expected number of matches, which is easy to compute. Let $G$ be the symmetry group of $F$, with $c=|G|$ (I presume this is what you mean by "the transformational symmetry of $F$"). Denote the width and height of $F$ by $w$ and $h$, respectively, and the number of squares in $F$ by $f$ (your "f_squares"). Then, assuming that the background is big enough to accommodate $F$ in both horizontal and vertical orientations, the expected number of matches is
$$\frac12((X-w+1)(Y-h+1)+(X-h+1)(Y-w+1))\frac c{2^f}\;.$$
This is just the chance of a match for a particular placement, $2^{-f}$, times the number of different placements, which is $c$ times the number of positions, which are averaged over horizontal and vertical orientations, of which there are half each.