一种基于频率的最大平方检测二进制矩阵的有效方法-计算机科学-机器学习-算法.pdf

一种基于频率的最大平方检测二进制矩阵的有效方法

SwastikBhandari

SchoolofEngineering,KathmanduUniversity

摘要为了理解性能瓶颈，重要的是要考虑矩阵在计算

机内存中是如何存储的。矩阵被映射到计算机的一维

在二进制矩阵中检测全1的最大平方子矩阵是一连续内存中。在C++、Python和Java等编程语言

个具有计算机视觉和模式识别应用基础的问题。尽管中，元素以行优先顺序存储，意味着每一行都依次排

标准动态规划（DP）解决方案实现了最优的渐近复列在一起，而在Fortran、MATLAB和R等编程语言

本杂度，但其实际性能因重复的最小操作和低效的内存中，元素以列优先顺序放置，这意味着同一列中的元

访问模式而受到影响，这些模式会降低缓存利用率。素在内存中相邻。

译为了解决这些问题，我们引入了一种基于频率的新算

中法，该算法采用贪心策略通过自适应频率数组和动态

3阈值机制来跟踪列中1的连续性。广泛的基准测试表

v明，在密度从0.1到0.9且大小高所在动态规划方法中，它从顶部（dp[i-1][j]）、

4

7有矩阵上，基于频率的算法在所有测试案例中的性能左侧（dp[i][j-1]）和左上角（dp[i-1][j-1]）的邻

9都比标准DP更快，平均加速率为3.32，最大加速居读取。以行优先顺序排列时，垂直（dp[i-1][j]）

8

1率为4.60，最小加速率为2.31。该算法对于所有和对角线（dp[i-1][j-1]）访问跨过行，增加了缓

.

3密度的平均加速率超过2.5，且对于0.7及以上的密存未命中的可能性。同样，在列优先顺序下，水平

0度，其加速率上升至超过3.5，这适用于所有矩阵大（dp[i][j-1]）和对角线（dp[i-1][j-1]）访问也会

5

2小。这些结果表明基于频率的方法是标准DP的一种导致类似的问题。因此，动态规划算法在两种布局中

:

v优越替代方案，并为性能关键应用中的高效矩阵分析都不高效地访问内存，特别是对于大型二进制矩阵。

i

x开辟了新的可能性。

r

a

1介绍本文提出了一种基于频率的算法，该算法解决了

这些问题，并比现有的动态规划解决方案更快地找到

最大正方形检测问题涉及在二进制矩阵中找到最大的正方形。该算法使用一个频率数组来跟踪1的

完全由1组成的最大的连续正方子矩阵。这是一个经垂直连续性，并采用双阈值机制动态调整有哪些信誉好的足球投注网站参数。

典问题，在计算机视觉和模式识别等领域有各种应这种方法避免了在垂直、水平和对角线邻域上重复进

用。标准的动态规划（DP）解决方案通过构建一个二行最小计算，减少了计算开销，并且比标准的动态规

维表来解决这个问题，其中每个单元格计算为：划方法快得多，平均加速倍数为3.32。

min

这表示以该单元格结尾的最大正方形的边长[1]。虽本文的主要目的是介绍一种基于频率的最大正

然经典的动态规划（DP）方法在理论上是最优的，但方形检测算法，该算法用于二进制矩阵，并克服了标

其实际速度往往受限于重复的最小操作以及现代硬准动态规划（DP）方法的性能限制，在实际应用中实

件上的缓存性能不佳。现了显著更快的执行速度。

1

2相关工作