Rotation invariant representation for 2-D shapes

[Spacha]

My attempt to represent the shapes in a rotation invariant way is inspired by Local Binary Patterns (LBP).

LBP is used in machine vision to extract descriptors from an image. It is quite simple in principle (if you are not familiar with it, maybe read the article first!).

How does it work?

• See the source

Say we have a shape like the one in the image (green blocks):

1. Add zero padding for calculation

We then add 2 levels of zero padding around the shape, which looks like this:

2. Calculate the cell values using modified LBP

Then we can start calculating the feature matrix. We start from the second cell of the second row (cell (1, 1), see the figure below) so that there are not edges next to it. The cell value for cell (1, 1) is calculated based on its 8-neighboring values as well as its own value. Each cell value is a 9-bit integer (0-512).

Here the cell (1, 1) is highlighted in orange:

1. Start from the top-left neighbor. If there is a block (=green), set the first bit (MSB) of the cell value to 1, otherwise 0.
2. Then proceed to the top-mid neighbor. Again, if there is a block, set the second bit of the cell value to 1.
3. Repeat for the top-right neighbor and set bit position 3 accordingly.
4. Repeat for the mid-right neighbor and set bit position 4 accordingly.
5. Repeat for the bottom-right neighbor and set bit position 5 accordingly.
6. Repeat for the bottom-mid neighbor and set bit position 6 accordingly.
7. Repeat for the bottom-left neighbor and set bit position 7 accordingly.
8. Repeat for the mid-left neighbor and set bit position 8 accordingly.
9. Repeat for the middle cell (the cell itself!) and set bit position 9 (LSB) accordingly.

Now we have a 9-bit cell value for the first cell: 00001_0000, which is 16 in decimal. We can then move to the next cell. This is repeated for all cells except cells that are on the edge (so skipping the first and last columns as well as the first and last rows).

Here are all the cell values for the example shape:

Then, the feature vector of this shape is:

[[ 16  24  28  12   4   0]
 [ 32  33  51  27  14   4]
 [ 64 192 496 425 263   2]
 [  0   0 112 201 390 256]
 [  0   0  96 129 258   0]
 [  0   0  64 128 256   0]]

3. Calculate the sum of the matrix values

Finally, we sum all the cell values in the feature matrix to get the fingerprint of that shape. This fingerprint is the same for all rotations of the same shape.

Comparing the variants

Here are all the variants of the example shape, along with their feature matrices and their sums (the fingerprints).

Matrix:
[[ 16  24  28  12   4   0]
 [ 32  33  51  27  14   4]
 [ 64 192 496 425 263   2]
 [  0   0 112 201 390 256]
 [  0   0  96 129 258   0]
 [  0   0  64 128 256   0]]

Sum: 3577

Matrix:
[[  0  16   8   4   0   0]
 [ 16  56  29  30  12   4]
 [ 48 105 167 291   3   2]
 [112 201 454 448 384 256]
 [ 96 129 258   0   0   0]
 [ 64 128 256   0   0   0]]

Sum: 3577

Matrix:
[[  0  16   8   4   0   0]
 [  0  48   9   6   0   0]
 [ 16 120 141 262   0   0]
 [ 32 113 155 286  12   4]
 [ 64 224 417 291   3   2]
 [  0  64 192 448 384 256]]

Sum: 3577

Matrix:
[[  0   0   0  16   8   4]
 [  0   0   0  48   9   6]
 [ 16  24  28 124 141 262]
 [ 32  33  51 107 135 258]
 [ 64 192 480 449 386 256]
 [  0   0  64 128 256   0]]

Sum: 3577

As you see, all variants have the same fingerprint 3577!

Final words

I have tested this with maybe tens of various 2-D shapes. So far so good. Check my Notebook for all the tests.

• This may not work in 3D at all, but pretty interesting nevertheless.
• One fear I have is that the fingerprint is not unique. There might be some other shapes that have the same fingerprint. I will check this later as well.
• It is possible that this is computationally more complex than the already found solutions.
• I was quite tired (and sick) when I did this so it may well be overly complicated and I am just missing the obvious.

I have not yet proven nor disproven that this will work. However, I am planning to do that later.

[Spacha]

I found that there is a new repo for further developments and I moved this issue there.

[hidny]

Hi Spacha, Thanks for letting me know about the new repo. I feel like your algo is interesting. If I wanted, I could use your algo to quickly check uniqueness before doing a longer check. Unfortunately, I don't think it's perfect. As the size of the grid increases, the number of solution grows something like 2^(n^2) while the number of combos in your algo seems to only grow at this kind of rate: (2^10)*n^2. For large n, 2^(n^2) will win, but I still like it!

[Spacha]

Yes, this one was a miss unfortunately. As pointed out in the other repo, this has another issue which makes this useless. I've been trying to find a better way of encoding the relative positions but it gets difficult for n > 5.

I still feel like there is a way of representing all of the rotations by a single hash but it isn't easy.