3
$\begingroup$

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.

  • 0
    @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.2012-08-02

1 Answers 1

1

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.

  • 0
    @alan2here: You're welcome!2012-08-02