How to compute similarity in shape of 1s in a binary matrix?

Question

I have multiple binary matrices. They don't necessarily have same lengths but all of them are proper m x n binary matrices with 0s and 1s as the only values.

I want to find the shape similarity of 1s in them.

Example:

0 0 0 0 0 0 0
0 0 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

and

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

These two matrices have same shape for 1s and (same shape of 0s, of course). What I was doing was calculating the number of 1s in each matrix and calculating the 1s shape perimeter to make an identifier. Then I used that identifier to find if I had same shapes but unfortunately it does not work for all of them.

I would appreciate any help or idea for this.

Answer 1

I don't code in Java, but here is a very simple method that should be easy enough to translate, in just two simple steps:

• Calculate the bounding rectangle (box) of the shape - you may have a method that does this in Java, but if not, sum the elements across the rows and look for the first and last row that total up to more than zero. Do the same for the columns.

• Pass the bytes identified within the bounding rectangle to any hash/checksum algorithm of your choice - I used MD5 but you could use CRC-32 or SHA-256.

Essentially, the first step makes the algorithm invariant to translation and the second makes it quick to compare because the hash can be calculated in advance and stored in a small space for lots of images.

I made three sample images with the same shape but moved around the frame:

Here's how it looks in Python:

#!/usr/bin/env python3

from PIL import Image
import numpy as np
import hashlib

# Open the 3 images as greyscale
im1 = Image.open('f-1.png').convert('L')
im2 = Image.open('f-2.png').convert('L')
im3 = Image.open('f-3.png').convert('L')

# Make into Numpy arrays to access pixels
na1 = np.array(im1)
na2 = np.array(im2)
na3 = np.array(im3)

# Get bounding box - i.e. first and last row and column that sums to >0
# ... and MD5 hash them
left, upper, right, lower = im1.getbbox()
md5 = hashlib.md5(na1[upper:lower,left:right].tobytes()).hexdigest()
print(f'Image 1: {left}, {upper}, {right}, {lower}, MD5={md5}')

left, upper, right, lower = im2.getbbox()
md5 = hashlib.md5(na2[upper:lower,left:right].tobytes()).hexdigest()
print(f'Image 2: {left}, {upper}, {right}, {lower}, MD5={md5}')

left, upper, right, lower = im3.getbbox()
md5 = hashlib.md5(na3[upper:lower,left:right].tobytes()).hexdigest()
print(f'Image 3: {left}, {upper}, {right}, {lower}, MD5={md5}')

And here is the output:

Image 1: 2, 1, 15, 11, MD5=31314d5c37539c81f8c6e8e38293e456
Image 2: 8, 4, 21, 14, MD5=31314d5c37539c81f8c6e8e38293e456
Image 3: 26, 5, 39, 15, MD5=31314d5c37539c81f8c6e8e38293e456

Keywords: Python, image processing, shape similarity, shape matching, translation invariant, MD5, hash, checksum.

Answer 2

EDIT

Following approach has a flaw: there may be collisions. As an example, the following pattern will also produce the same code. So, as a quick test, you can use this approach to find possible matches, and then disambiguate them using some other approach as chain codes as Cris Luengo mentioned in the comment.

Or, you can calculate the central moments up to some order and compare them, as central moments are translation invariant. See wiki page https://en.m.wikipedia.org/wiki/Image_moment for central moments.

0 0 0 0 0 0 0      0
0 1 0 0 0 0 0      1
1 1 1 0 0 0 0      3
1 1 1 0 0 0 0      3
0 0 1 0 0 0 0      1
0 0 0 0 0 0 0      0
0 0 0 0 0 0 0      0

2 3 3 0 0 0 0

---

I think you can take the horizontal and vertical projections of these matrices and compare them ignoring the zeros. So, just take the sum for each row and column and form a string, like

0 0 0 0 0 0 0      0
0 0 1 0 0 0 0      1
1 1 1 0 0 0 0      3
1 1 1 0 0 0 0      3
0 1 0 0 0 0 0      1
0 0 0 0 0 0 0      0
0 0 0 0 0 0 0      0

2 3 3 0 0 0 0

Now you can generate a code from these two projections taking non-zero entries, say first horizontal, then vertical: 2 3 3 0 0 0 0 | 0 1 3 3 1 0 0 -- remove zeros --> 2 3 3 | 1 3 3 1.

The other matrix will also give you the same result 0 0 2 3 3 0 0 | 0 0 0 1 3 3 1 0 0 0 -- remove zeros --> 2 3 3 | 1 3 3 1.

0 0 0 0 0 0 0    0
0 0 0 0 0 0 0    0
0 0 0 0 0 0 0    0
0 0 0 0 1 0 0    1
0 0 1 1 1 0 0    3
0 0 1 1 1 0 0    3
0 0 0 1 0 0 0    1
0 0 0 0 0 0 0    0
0 0 0 0 0 0 0    0
0 0 0 0 0 0 0    0

0 0 2 3 3 0 0

I think this will work if those 1s form a blob like pattern. If there are gaps, you'll have to take into account the zeros in-between.

Answer 3

Have a look at the Hit-or-Miss Theory, it is fairly well documented in OpenCV, but you can easily implement this yourself if necessary. This allows you to detect patterns in binary images.

Edit: To give you a better understanding of what is going on, I butchered the OpenCV example to fit your problem. Unfortunately, I do not know Java very well yet, so the code is in Python. The images should still help you, though.

Some binary sequence (your example):

The pattern:

The position, where the pattern is found:

Maybe the code enclosed helps you, best of luck.

import cv2 as cv
import numpy as np

pattern = np.array([[0, 0, 1],
           [1, 1, 1],
           [1, 1, 1],
           [0, 1, 0]], dtype=np.int)

matrix = np.array([[0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 1, 0, 0],
                  [0, 0, 1, 1, 1, 0, 0],
                  [0, 0, 1, 1, 1, 0, 0],
                  [0, 0, 0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 0]], dtype=np.uint8)
matrix *= 255

output_image = cv.morphologyEx(matrix, cv.MORPH_HITMISS, pattern)
rate = 50
kernel = (pattern + 1) * 127
kernel = np.uint8(kernel)
kernel = cv.resize(kernel, None, fx = rate, fy = rate, interpolation = cv.INTER_NEAREST)
cv.imwrite("pattern.png", kernel)
input_image = cv.resize(matrix, None, fx = rate, fy = rate, interpolation = cv.INTER_NEAREST)
cv.imwrite("Original.png", input_image)
output_image = cv.resize(output_image, None , fx = rate, fy = rate, interpolation = cv.INTER_NEAREST)
cv.imwrite("Hit_or_Miss.png", output_image)