Alignment of square nonorientable images/data

Question

Alignment of square nonorientable images/data

Mark

2015年7月31日 17:45

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 D₄ / D₈, 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 90^o) 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 M₁₀ and M₀₁ to transform horizontally and vertically mirrored equivalent data. E.g. apply horizontal mirroring iff it makes M₁₀ 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 (D₈ 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).

Topic data-cleaning processing

Category Data Science

AN6U5 · Accepted Answer · 2015年7月31日 17:45

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.

Alignment of square nonorientable images/data

About