（算法版）基于二值图像数字矩阵的距离变换算法

2024-04-18 02:12
文章标签 算法 图像 距离 矩阵 数字 变换 二值

本文主要是介绍（算法版）基于二值图像数字矩阵的距离变换算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hi，大家好，我是半亩花海。本项目展示了欧氏距离、城市街区距离和棋盘距离变换的实现方法。通过定义一个距离变换类，对输入图像进行距离变换操作，并生成对应的距离矩阵。在示例中，展示了在一个480x480的全黑背景图像上设置三个前景像素点的距离变换结果。

文章目录

      • 一、距离的定义及分类
      • 二、导入必要库
      • 三、距离变换算法
      • 四、定义距离变换类
      • 五、显示原始图像
      • 六、计算并输出距离变换矩阵
      • 七、可视化距离变换结果
      • 八、完整代码

一、距离的定义及分类

距离是描述图像两点像素之间的远近关系的度量，常见的度量距离有欧式距离、城市街区距离、棋盘距离。以下以两坐标点 a = ( i , j ) a = (i, j) a=(i,j) 和 b = ( k , l ) b = (k, l) b=(k,l) 的距离为例，来说明各种距离的定义方式：

（1）欧式距离 D e D_e De​： 欧式距离的定义源于经典的几何学，与我们数学中所学的简单几何的两点之间的距离一致，为两个像素点坐标值的平方根。欧式距离的优点在于其定义非常地直观，是显而易见的，但缺点在于平方根的计算是非常耗时的。

D e ( a , b ) = ( ( i − k ) 2 ) + ( j − l ) 2 D_e(a, b)=\sqrt{\left((i-k)^2\right)+(j-l)^2} De​(a,b)=((i−k)2)+(j−l)2 ​

（2）城市街区距离 D 4 D_4 D4​： 距离描述的是只允许像素坐标系平面中横向和纵向的移动距离，4表示在这种定义下，像素点是 4 邻接的，即每个点只与它的上、下、左、右相邻的 4 个点之间的距离为 1。

D 4 ( a , b ) = ∣ i − k ∣ + ∣ j − l ∣ D_4(a, b)=|i-k|+|j-l| D4​(a,b)=∣i−k∣+∣j−l∣

（3）棋盘距离 D 8 D_8 D8​： 如果允许在图像坐标系中像素点的对角线方向的移动，就可以得到棋盘距离，8 表示在这种定义下，像素点是 8 邻接的，即每个点只与它的上、下、左、右、四个对角线方向相邻的 8 个点之间的距离为 1。

D 8 ( a , b ) = max ⁡ { ∣ i − k ∣ , ∣ j − l ∣ } D_8(a, b)=\max \{|i-k|,|j-l|\} D8​(a,b)=max{∣i−k∣,∣j−l∣}

二、导入必要库

import numpy as np
import matplotlib.pyplot as plt# 设置字体样式以正常显示中文标签
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

三、距离变换算法

  • 距离变换是图像中像素点与某个区域块的距离。区域块中的像素点值为 0，临近区域块的像素点有较小的值，离它越远值越大。

以二值图像为例，其中区域块内部的像素值为 1，其他像素值为 0。距离变换给出每个像素点到最近的区域块边界的距离，区域块内部的距离变换结果为0。输入图像如图 1 所示， D 4 D_4 D4​ 距离的距离变换结果如图 2 所示。

  • 距离变换算法核心是利用两个小的局部掩膜对图像进行遍历。第一遍利用掩模1，左上角开始，从左往右，从上往下；第二遍利用第二个掩模，右下角开始，从右往左，从下往上。掩模形状如下图所示：

按照某种距离（如： D 4 D_4 D4​ 距离或 D 8 D_8 D8​ 距离）对大小为 M × N M×N M×N 的图像中的区域块作距离变换，算法过程如下：

（1） 建立一个大小为 M × N M×N M×N 的数组 F F F，作如下的初始化：将区域块中的元素设置为 0，其余元素设置为无穷；

（2） 利用掩模1（mask1），左上角开始，从左往右，从上往下遍历数组，将掩模中P点对应的元素的值作如下更新：

F ( P ) = min ⁡ q ∈ mask1 ⁡ { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\min _{q \in \operatorname{mask1}}\{F(P), D(P, q)+F(q)\} F(P)=q∈mask1min​{F(P),D(P,q)+F(q)}

（3） 利用掩模2（mask2），右下角开始，从右往左，从下往上遍历数组，将掩模中P点对应的元素的值作如下更新：

F ( P ) = min ⁡ q ∈ mask2 ⁡ { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\min _{q \in \operatorname{mask2}}\{F(P), D(P, q)+F(q)\} F(P)=q∈mask2min​{F(P),D(P,q)+F(q)}

最终得到的更新后的数组即为距离变换的结果。

因在边界处掩模不能全部覆盖图像，可以将掩模中没有对应元素的位置的值当作 0 来处理，以此对图像边界处做出调整，即maskSize=0。

四、定义距离变换类

在距离变换类当中分别初始化距离变换类、定义欧氏距离和城市街区距离及棋盘距离的函数。

# 定义距离变换类
class DistanceTransform:# 初始化距离变换类def __init__(self, image):self.image = imageself.height, self.width = image.shape# 定义欧氏距离变换def Euclidean_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)# 获取前景像素点的坐标yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的欧氏距离distances = np.sqrt((y - yy) ** 2 + (x - xx) ** 2)# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix# 定义城市街区距离变换def D4_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的曼哈顿距离distances = np.abs(y - yy) + np.abs(x - xx)# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix# 定义棋盘距离变换def D8_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的棋盘距离distances = np.maximum(np.abs(y - yy), np.abs(x - xx))# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix

五、显示原始图像

# 初始化输入图像：480x480的全黑背景
image = np.zeros((480, 480), dtype=np.uint8)
# 取三个前景像素点
image[100, 200] = 1
image[200, 100] = 1
image[300, 300] = 1# 显示原始图像
plt.figure(figsize=(5, 5))
plt.scatter([100, 200, 300], [200, 100, 300], color='white', marker='o')
plt.imshow(image, cmap='gray')
plt.title('原始图像', fontsize=15)

六、计算并输出距离变换矩阵

# 计算距离变换矩阵
dt = DistanceTransform(image)
euclidean_distance_matrix = dt.Euclidean_distance_transform()
manhattan_distance_matrix = dt.D4_distance_transform()
chessboard_distance_matrix = dt.D8_distance_transform()# 输出欧氏、城区和棋盘的距离矩阵
print("欧氏距离的变换矩阵:\n", euclidean_distance_matrix)
print("城区距离的变换矩阵:\n", manhattan_distance_matrix)
print("棋盘距离的变换矩阵:\n", chessboard_distance_matrix)

七、可视化距离变换结果

# 可视化距离变换结果
plt.figure(figsize=(15, 5))# 欧氏距离变换
plt.subplot(1, 3, 1)
plt.imshow(euclidean_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('欧氏距离', fontsize=15)
plt.axis('off')# 城区距离变换
plt.subplot(1, 3, 2)
plt.imshow(manhattan_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('城区距离', fontsize=15)
plt.axis('off')# 棋盘距离变换
plt.subplot(1, 3, 3)
plt.imshow(chessboard_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('棋盘距离', fontsize=15)
plt.axis('off')plt.tight_layout()
plt.show()

八、完整代码

import numpy as np
import matplotlib.pyplot as plt# 设置字体样式以正常显示中文标签
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False# 定义距离变换类
class DistanceTransform:# 初始化距离变换类def __init__(self, image):self.image = imageself.height, self.width = image.shape# 定义欧氏距离变换def Euclidean_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)# 获取前景像素点的坐标yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的欧氏距离distances = np.sqrt((y - yy) ** 2 + (x - xx) ** 2)# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix# 定义城市街区距离变换def D4_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的曼哈顿距离distances = np.abs(y - yy) + np.abs(x - xx)# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix# 定义棋盘距离变换def D8_distance_transform(self):distance_matrix = np.zeros_like(self.image, dtype=float)yy, xx = np.argwhere(self.image == 1).Tfor y in range(self.height):for x in range(self.width):if self.image[y, x] == 1:distance_matrix[y, x] = 0else:# 计算当前像素到前景像素点的棋盘距离distances = np.maximum(np.abs(y - yy), np.abs(x - xx))# 取最小值作为当前像素的距离值distance_matrix[y, x] = np.min(distances)return distance_matrix# 初始化输入图像：480x480的全黑背景
image = np.zeros((480, 480), dtype=np.uint8)
# 取三个前景像素点
image[100, 200] = 1
image[200, 100] = 1
image[300, 300] = 1# 显示原始图像
plt.figure(figsize=(5, 5))
plt.scatter([100, 200, 300], [200, 100, 300], color='white', marker='o')
plt.imshow(image, cmap='gray')
plt.title('原始图像', fontsize=15)# 计算距离变换矩阵
dt = DistanceTransform(image)
euclidean_distance_matrix = dt.Euclidean_distance_transform()
manhattan_distance_matrix = dt.D4_distance_transform()
chessboard_distance_matrix = dt.D8_distance_transform()# 输出欧氏、城区和棋盘的距离矩阵
print("欧氏距离的变换矩阵:\n", euclidean_distance_matrix)
print("城区距离的变换矩阵:\n", manhattan_distance_matrix)
print("棋盘距离的变换矩阵:\n", chessboard_distance_matrix)# 可视化距离变换结果
plt.figure(figsize=(15, 5))# 欧氏距离变换
plt.subplot(1, 3, 1)
plt.imshow(euclidean_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('欧氏距离', fontsize=15)
plt.axis('off')# 城区距离变换
plt.subplot(1, 3, 2)
plt.imshow(manhattan_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('城区距离', fontsize=15)
plt.axis('off')# 棋盘距离变换
plt.subplot(1, 3, 3)
plt.imshow(chessboard_distance_matrix, cmap='gray')
plt.colorbar(shrink=0.8)
plt.title('棋盘距离', fontsize=15)
plt.axis('off')plt.tight_layout()
plt.show()

这篇关于（算法版）基于二值图像数字矩阵的距离变换算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/913500。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
从去中心化到智能化：Web3如何与AI共同塑造数字生态

从去中心化到智能化：Web3如何与AI共同塑造数字生态

在数字时代的演进中，Web3和人工智能（AI）正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术，正相互交织，共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界，并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展，它基于去中心化的区块链技术，旨在创建一个开放、透明且用户主导的数字生态。不同于传统
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.2 Name That Number（数字字母转化）

usaco 1.2 Name That Number（数字字母转化）

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码： /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2