I do have following problem to solve: I have a simple but big gridmap (Size: mX-times-mY). I only distinguish between a tile being occupied by an obstacle or being free.
Now let's say I use a relatively small sliding window of size n-times-n, so n << mX, n << mY. For ALL possible combinations of occupied and free tiles in that n-times-n window, I assign a identifier (let's just say a number). Then I take a "snapshot" of a part of my big map in size of that window.
My Question: What is the easiest and/or fastest method to determine the identification number of the current pattern extracted from the map?
To demonstrate: I have a 2x2 Window (so a 2x2 Matrix). There are 2^(2x2)=16 possible combinations of patterns.
Pattern #1 #2 #3 #4 #5 #6 #7 #8
00 #0 0# 00 00 ## #0 00
00 00 00 #0 0# 00 #0 ##
Pattern #9 #10 #11 #12 #13 #14 #15 #16
0# #0 0# 0# #0 ## ## ##
0# 0# #0 ## ## 0# #0 ##
with # = obscured
0 = free
Assuming I extract the pattern
#0
0#
from my map, how can I easily and quickly identify that this is pattern number 10 in aboves example?
My Ideas so far:
Loop over all patterns until I find the correct one, maybe by checking if the difference of both patterns is a zero matrix.
I sum all n rows and all n columns and use those sums as subindices in an multidimensional array. For above example: sumRow1 = 1 sumRow2 = 1 sumCol1 = 1 sumCol2 = 1 So my pattern is saved in patternNumbers[1][1][1][1] = 10. Another example would be pattern 16, which would be saved at patternNumbers[2][2][2][2] = 16.
Possible advantage for bigger windows: I only have to calculate 2*n sums and immediately can use those sums to address my pattern I was looking for. Big, big disadvantage: I need an (2*n)-dimensional Array in which many empty entrys will be left. So relatively big overhead.
Has anyone of you done this before? Any ideas how to solve this? I also did not take into account any sort of symmetry (rotational or line).
Any help is greatly appreciated!
Well, looks like I found a relatively easy solution which was pointed out by someone else to me:
By taking all rows or all columns (doesn't matter, your choice!) in a specific order - which has to be the same for all patterns - and align them as one long vector, then you get a regular binary expression. Just convert that binary number into a decimal number and you have your "unique identifier".
Example 1:
00
#0
can also be written as
00
10
now reorder the rows to
0010 = 2
=============================
Example 2:
##
00
can also be written as
11
00
now reorder the rows to
1100 = 12