Consider for a second a 2x2 array of bits:
+---+---+ +---+---+
@p | 0 | 1 | | a | b |
@p +---+---+ = +---+---+
@p | 1 | 0 | | c | d |
@p +---+---+ +---+---+
Let's call this 2x2 array an image. What are all the different possible images we can make?
In one dimension, we have a four-bit bitstring like so:
abcd
There are 2 possible values for each bit, so there are 4^2=16 possibilties. This is just basic binary math.
@p
However, what about symmetries? For instance, a common operation to perform on bitfields like this is a "rotation": a "rotation left" is an instruction in the x86 instruction set, called usually "rol" and it works like this:
abcd => bcda
(* NOTE: technically rol can only work with a minimum of 8 bits, so this isn't quite true, but you get the idea...)
@p
The leftmost bit rotates to the rightmost bit and everything else shifts to the left.
Let's call this rotation a translation, instead. We're changing terminology because in geometrical terms, this is like "translating" (or moving) the 1 dimensional bit "image" to the left.
@p
Side note: It was probably originally called a rotation because you can imagine the bits as existing as points on a circle:
a
@p d b
@p c
With this kind of schematic, "rotation" makes sense as we are just rotating the points as if they were arranged in a circle like this.
@p
However, mathematically we might do better to express it as translation, but on the abelian circular group with four elements. Just think of it as a 1 dimensional image that when you move it left or right, it "wraps".
Either way, if we permit our definition of translation to apply to 1 dimensional images, then we can see that for instance:
@p
0100 = 1000 = 0001 = 0010
@p
In this case the equality X = Y means "X is a bitfield that can be translated some amount of times to achieve Y (including 0 times)". We say they are equivalent under translation symmetry.
Now back to our two dimensional bitfield.
@p
Right now I have a really practical problem of describing what symmetries apply to these kind of 2-dimensional bitfields.
@p
Translation as defined above would be one. For instance these are all equivalent:
ab ba cd dc
@p cd = dc = ab = ba
@p T0 T1 T2 T3
I've labeled each translation as "T1" through "T3". T0 means, don't translate at all and is just the "identity" transformation. T3 is rotated left 3 bits.
@p
Note we aren't interested at this point in what values are actually assigned to a, b, c and d-- we are just talking about how we can translate them.
We can also define an actual rotation around the center point:
ab ca cd bc
@p cd = db = ba = ad
@p R0 R1 R2 R3
This type of rotation doesn't really exist if the bitfield is just 1-dimensional; this is why I wanted to define the typical "binary rotation" operation as a translation, instead.
@p
We've labeled these as R0 to R3, where R3 is rotating by 3 steps (or 270 degrees.)
The symmetry group can be thought of as taking the product of these two sets of transformations. We just "do one" and then "do the other":
(T0 R0) (T0 R1) (T0 R2) (T0 R3)
@p (T1 R0) (T1 R1) (T1 R2) (T1 R3)
@p (T2 R0) (T2 R1) (T2 R2) (T2 R3)
@p (T3 R0) (T3 R1) (T3 R2) (T3 R3)
For now we're not sure if the two transformations matter which order they are taken in, so we have to include both doing the translation first, and the rotation next, and vice versa.
(R0 T0) (R0 T1) (R0 T2) (R0 T3)
@p (R1 T0) (R1 T1) (R1 T2) (R1 T3)
@p (R2 T0) (R2 T1) (R2 T2) (R2 T3)
@p (R3 T0) (R3 T1) (R3 T2) (R3 T3)
Obviously, at least some of these will be the same. For instance, (R0 T0) and (T0 R0) are the same thing-- do nothing!
@p
So the question now is:
Is there an easy way to describe these transformations, i.e., the symmetry group, for any size 2-dimensional bitfields?
Hah! Actually I don't really have an answer right now-- I'd imagine so. Fortunately, for my purposes, I only likely care about 4x4 or 8x8 bitfields, so I think I can just brute force it.
@p
First we notice that no matter what size of image we are talking about, for instance a 4x4:
+---+---+---+---+
@p | a | b | c | d |
@p +---+---+---+---+
@p | e | f | g | h |
@p +---+---+---+---+
@p | i | j | k | l |
@p +---+---+---+---+
@p | m | n | o | p |
@p +---+---+---+---+
The translation group is 4x4=16 units large (it was 2x2=4 units large for the 2x2 image-- it's easy to see why!) but the good news is the rotation group is still only 4 units large. We can still only rotate by 90 degree increments (at least as far as I am interested in looking at.)
@p
So anyhow, I don't actually have an answer for this right now, but that's the beauty-- I don't really need to. The main thing is just to recognize the model, and then you can fairly simply brute force it.
The final goal for the particular problem I am looking at is to be able to define those possible unique images, over the symmetry group.
@p
So for instance, a 4x4 image as above would, naeively have 2^16=65536 possibilities. However, once we factor out all of those that are symmetrical to each other, how many are there?
@p
My hunch is that the rotation and translation groups don't really overlap except for commutivity, so this would mean that we have 4x4=16 translations, and 4 more rotations, which means we have 16 * 4 = 64 elements in the symmetry group.
@p
However, we can also imagine a mirroring translation, which for 4x4 images is different than rotation/translation (for 2x2 images I think maybe it's the same.) We can mirror in either plane (or both) which gives us another possible 4 options. However, mirroring in x and then in y is the same as rotating by 2 steps (180 degrees) so really there are only two mirror operations.
@p
Still, taking into account these rotations reduces our intial image set from 65536 to only 512 different possible images. This is much more managable!
@p
In order to verify this I will have to brute force it to make sure that there isn't any more overlap, but that's why I program computers I guess!
... is brought to use by GROUP THEORY, in service of PIXEL ART.
2012-09-27