4
$\begingroup$

Another post where I don't know enough terminology to describe things efficiently. For the comments, please suggest some tags and keywords I can add to this post to make it better.

Say I have a 2D data structure where 'orientation' doesn't matter. The examples I ran into:

  • The state of a 2048 game. In terms of symmetry groups this would be D4 / D8, except that an operation doesn't yield an identical state, it just yields another state that has the same solution.
  • Images of plankton or galaxies (without background). Somewhat similar to above except that any rotation (not just 90o) yields an equally valid image (and one might take scale into account, but let's forget about that).

In both cases I've wanted to transform all these equivalent states/images to remove all but one of the equivalent images. To illustrate with two that worked:

  • I can use image moments M10 and M01 to transform horizontally and vertically mirrored equivalent data. E.g. apply horizontal mirroring iff it makes M10 bigger. This would transform a 2048 state and it's horizontal mirror image to the same state.
  • I can use the eigenvector of the covariance matrix which has the largest eigenvalue as the orientation. Then I can rotate the image to align this eigenvector with some predetermined axis (e.g. horizontally).

That still leaves a lot of operations though (diagonal mirroring, rotations around the center, inversion). And these operations do not commute (D8 is non-Abelian). Is there any comprehensive approach?

The reason I want to do this is to help machine learning methods by removing variance that isn't actually meaningful. Hopefully that makes sure they don't have to learn these equivalences, so possibly need less train data (and time).

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Fun with Group Theory!

There are only 8 unique rotation-inversion operations for a square matrix.

The four rotation operators are (0,90,180,270). Further rotation or rotation in the reverse direction is the same as these four. Two successive rotations just yields one of the rotation operators, so we will only consider these four rotations applied one time.

The five inversion operators are (0,/,\,|,-). Two successive inversions just yields a rotation, so we will only allow for a single inversion.

We can thus derive all operators by combining these two vectors, which yields 4*5=20 possible states.

(0,90,180,270,0/,90/,180/,270/,0\,90\,180\,270\,0|,90|,180|,270|,0-,90-,180-,270-)

But there is still symmetry to be exploited in the inversion operators. You can probably intuit that the 4x4 matrix only has 8 final states: inverted or not and rotated by (0,90,180,270). It turns out that you can arrive at any possible state involving an inversion using any of the other inversion operators followed by one of the rotations. So we only need to retain a single inversion operator! So the final set of 8 orthogonal operations are:

(0,90,180,270,0|,90|,180|,270|)

If there is any symmetry in the matrix's members then some of the resulting states may be degenerate.

In terms of mapping possible states into a ground state, it makes sense to apply a set of successive deterministic rules to determine the ground state orientation. I suggest finding the largest corner square and locating it in the lower right corner. If there are multiple candidates with equally large values in the corner square then use the next closest square as a tie breaker. There are 16 squares, so you can eventually break all ties or declare degeneracy. There is one remaining \ operation that you can decide to apply in order to locate the larger of the two squares adjacent to the lower right corner at the bottom. Again, you can use squares adjacent to these as tie breakers.

$\endgroup$
6
  • 1
    $\begingroup$ Yeah it's helpful, thanks! But I still need a way to map all theses states to one in a consistent way... But now I know exactly which states and operations there are :-) $\endgroup$
    – Mark
    Jul 31, 2015 at 11:35
  • $\begingroup$ I tried to answer this with the edit I just made. Hope it helps! $\endgroup$
    – AN6U5
    Jul 31, 2015 at 16:20
  • $\begingroup$ Ignore my previous comment, there was a code mistake. Operations can be applied in any order even though they don't commute. It seems to work well now! $\endgroup$
    – Mark
    Aug 4, 2015 at 16:27
  • 1
    $\begingroup$ For future users: I used image moments instead of highest value tile, which generalizes to things other than 2048 boards. For \ mirroring, I check the sum of the upper triangle vs that of the lower. $\endgroup$
    – Mark
    Aug 4, 2015 at 16:29
  • 1
    $\begingroup$ Note that there is a loss of information in summing the diagonal region since multiple different sums and orientations can result in the same sum. I try to stay away from sums or averages when trying to determine absolute differences. Image moments also have a loss of information. For large images, you wouldn't expect much conflict, but the 2048 board would have a significant number of conflicts. $\endgroup$
    – AN6U5
    Aug 4, 2015 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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