时间戳

首页 > 解决方案 > 如何计算二进制矩阵中1s形状的相似性？

java - 如何计算二进制矩阵中1s形状的相似性？

问题描述

我有多个二进制矩阵。它们不一定具有相同的长度，但它们都是正确的 mxn 二进制矩阵，只有 0 和 1 作为唯一值。

我想在其中找到 1 的形状相似性。

例子：

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 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

这两个矩阵对于 1 和（当然，对于 0 的形状相同）具有相同的形状。我正在做的是计算每个矩阵中 1 的数量并计算 1 的形状周长以制作标识符。然后我使用该标识符来查找我是否具有相同的形状，但不幸的是它不适用于所有形状。

我将不胜感激任何帮助或想法。

标签： javaalgorithmimage-processingmatrixsimilarity

解决方案

我不会用 Java 编写代码，但这里有一个非常简单的方法，应该很容易翻译，只需两个简单的步骤：

  • 计算形状的边界矩形（框） - 您可能有一个在 Java 中执行此操作的方法，但如果没有，请将各行中的元素相加并查找总和大于零的第一行和最后一行。对列执行相同的操作。

  • 将边界矩形内标识的字节传递给您选择的任何散列/校验和算法 - 我使用 MD5，但您可以使用 CRC-32 或 SHA-256。

本质上，第一步使算法对翻译保持不变，第二步使其可以快速比较，因为可以提前计算哈希值并将其存储在用于大量图像的小空间中。

我制作了三个形状相同但在框架周围移动的示例图像：

在此处输入图像描述

在此处输入图像描述

在此处输入图像描述

这是它在 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}')

这是输出：

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

关键词：Python、图像处理、形状相似度、形状匹配、平移不变性、MD5、哈希、校验和。

推荐阅读