二维阵列中的峰值检测

问题描述：

我正在帮助一家兽医诊所测量狗爪下的压力。我使用 Python 进行数据分析，现在我正努力将爪子划分为（解剖）子区域。

我为每个爪子制作了一个 2D 数组，其中包含爪子随时间加载的每个传感器的最大值。这是一个爪子的示例，我使用 Excel 绘制了我想要“检测”的区域。这些是传感器周围的 2x2 框，具有局部最大值，它们加在一起具有最大和。

因此我尝试了一些实验，决定只寻找每列和每行的最大值（由于爪子的形状，无法朝一个方向看）。这似乎可以很好地“检测”单独脚趾的位置，但它也会标记相邻的传感器。

那么，告诉 Python 这些最大值中哪一个是我想要的，最好的方法是什么？

注意：2x2 的方块不能重叠，因为它们必须是分开的！

另外，我采用 2x2 是为了方便，任何更高级的解决方案都欢迎，但我只是一名人类运动科学家，所以我既不是真正的程序员也不是数学家，所以请保持“简单”。

这是一个可以加载的版本np.loadtxt

结果

所以我尝试了@jextee 的解决方案（见下面的结果）。如你所见，它对前爪非常有效，但对后腿效果较差。

更具体地说，它无法识别第四个脚趾的小峰值。这显然是由于循环从上向下寻找最低值，而没有考虑到最低值在哪里。

有人知道如何调整@jextee 的算法，以便它也能找到第 4 个脚趾吗？

由于我还没有处理任何其他试验，因此我无法提供任何其他样本。但我之前给出的数据是每个爪子的平均值。此文件是一个数组，其中按接触板的顺序排列了 9 个爪子的最大数据。

这张图片展示了它们在盘子上的空间分布。

更新：

我已经为感兴趣的人建立了一个博客，并建立了一个包含所有原始测量数据的 OneDrive。因此，对于任何要求更多数据的人：祝您一切顺利！

新更新：

因此，在获得有关爪子检测和爪子分类问题的帮助后，我终于能够检查每个爪子的脚趾检测了！结果发现，除了像我自己的例子那样大小的爪子外，它在其他方面都不太管用。当然，事后看来，这是我自己的错，因为我太武断地选择了 2x2。

这是一个很好的例子，说明了哪里出了问题：指甲被识别为脚趾，而“脚跟”太宽，以至于被识别了两次！

爪子太大，因此采用 2x2 大小且没有重叠，会导致某些脚趾被检测到两次。相反，在小型犬中，它经常找不到第五个脚趾，我怀疑这是由于 2x2 区域太大造成的。

在所有测量中尝试了当前的解决方案后，我得出了惊人的结论：对于几乎所有的小型犬，它都没有找到第五个脚趾，而对于大型犬，在超过 50% 的撞击中它会找到更多！

所以显然我需要更改它。我自己的猜测是将尺寸改为neighborhood适合小狗的较小尺寸，适合大狗的较大尺寸。但是generate_binary_structure不允许我更改数组的大小。

有谁对定位脚趾有更好的建议吗，也许可以让脚趾面积与爪子大小成比例？

解决方案 1：

我使用局部最大值滤波器检测峰值。这是您的第一个包含 4 个爪子的数据集的结果：

我也在第二个包含 9 个爪子的数据集上运行了它，并且效果同样出色。

操作方法如下：

import numpy as np
from scipy.ndimage.filters import maximum_filter
from scipy.ndimage.morphology import generate_binary_structure, binary_erosion
import matplotlib.pyplot as pp

#for some reason I had to reshape. Numpy ignored the shape header.
paws_data = np.loadtxt("paws.txt").reshape(4,11,14)

#getting a list of images
paws = [p.squeeze() for p in np.vsplit(paws_data,4)]


def detect_peaks(image):
    """
    Takes an image and detect the peaks usingthe local maximum filter.
    Returns a boolean mask of the peaks (i.e. 1 when
    the pixel's value is the neighborhood maximum, 0 otherwise)
    """

    # define an 8-connected neighborhood
    neighborhood = generate_binary_structure(2,2)

    #apply the local maximum filter; all pixel of maximal value 
    #in their neighborhood are set to 1
    local_max = maximum_filter(image, footprint=neighborhood)==image
    #local_max is a mask that contains the peaks we are 
    #looking for, but also the background.
    #In order to isolate the peaks we must remove the background from the mask.

    #we create the mask of the background
    background = (image==0)

    #a little technicality: we must erode the background in order to 
    #successfully subtract it form local_max, otherwise a line will 
    #appear along the background border (artifact of the local maximum filter)
    eroded_background = binary_erosion(background, structure=neighborhood, border_value=1)

    #we obtain the final mask, containing only peaks, 
    #by removing the background from the local_max mask (xor operation)
    detected_peaks = local_max ^ eroded_background

    return detected_peaks


#applying the detection and plotting results
for i, paw in enumerate(paws):
    detected_peaks = detect_peaks(paw)
    pp.subplot(4,2,(2*i+1))
    pp.imshow(paw)
    pp.subplot(4,2,(2*i+2) )
    pp.imshow(detected_peaks)

pp.show()

之后你需要做的就是使用scipy.ndimage.measurements.label面具标记所有不同的物体。然后你就可以单独玩它们了。

请注意，该方法效果很好，因为背景没有噪音。如果背景很嘈杂，您会在背景中检测到一堆其他不需要的峰值。另一个重要因素是邻域的大小。如果峰值大小发生变化，您将需要调整它（应该保持大致成比例）。

解决方案 2：

解决方案

数据文件：paw.txt。源代码：

from scipy import *
from operator import itemgetter

n = 5  # how many fingers are we looking for

d = loadtxt("paw.txt")
width, height = d.shape

# Create an array where every element is a sum of 2x2 squares.

fourSums = d[:-1,:-1] + d[1:,:-1] + d[1:,1:] + d[:-1,1:]

# Find positions of the fingers.

# Pair each sum with its position number (from 0 to width*height-1),

pairs = zip(arange(width*height), fourSums.flatten())

# Sort by descending sum value, filter overlapping squares

def drop_overlapping(pairs):
    no_overlaps = []
    def does_not_overlap(p1, p2):
        i1, i2 = p1[0], p2[0]
        r1, col1 = i1 / (width-1), i1 % (width-1)
        r2, col2 = i2 / (width-1), i2 % (width-1)
        return (max(abs(r1-r2),abs(col1-col2)) >= 2)
    for p in pairs:
        if all(map(lambda prev: does_not_overlap(p,prev), no_overlaps)):
            no_overlaps.append(p)
    return no_overlaps

pairs2 = drop_overlapping(sorted(pairs, key=itemgetter(1), reverse=True))

# Take the first n with the heighest values

positions = pairs2[:n]

# Print results

print d, "
"

for i, val in positions:
    row = i / (width-1)
    column = i % (width-1)
    print "sum = %f @ %d,%d (%d)" % (val, row, column, i)
    print d[row:row+2,column:column+2], "
"

输出无重叠方块。似乎选择了与您的示例相同的区域。

一些评论

棘手的部分是计算所有 2x2 正方形的总和。我假设您需要所有正方形，因此可能会有一些重叠。我使用切片从原始 2D 数组中切出第一列/最后一列和行，然后将它们全部重叠在一起并计算总和。

为了更好地理解它，想象一个 3x3 阵列：

>>> a = arange(9).reshape(3,3) ; a
array([[0, 1, 2],
       [3, 4, 5],
       [6, 7, 8]])

然后你可以取出它的切片：

>>> a[:-1,:-1]
array([[0, 1],
       [3, 4]])
>>> a[1:,:-1]
array([[3, 4],
       [6, 7]])
>>> a[:-1,1:]
array([[1, 2],
       [4, 5]])
>>> a[1:,1:]
array([[4, 5],
       [7, 8]])

现在想象一下你将它们一个叠在另一个上面，并计算相同位置上的元素之和。这些和将与左上角位置相同的 2x2 正方形上的和完全相同：

>>> sums = a[:-1,:-1] + a[1:,:-1] + a[:-1,1:] + a[1:,1:]; sums
array([[ 8, 12],
       [20, 24]])

当您有 2x2 平方数上的和时，您可以使用max来查找最大值，或sort，或sorted来查找峰值。

为了记住峰值的位置，我将每个值（总和）与其在扁平数组中的序数位置结合起来（参见zip）。然后，我在打印结果时再次计算行/列位置。

笔记

我允许 2x2 方块重叠。编辑版本会过滤掉其中的一些方块，这样结果中只会出现不重叠的方块。

选择手指（一个想法）

另一个问题是如何从所有峰值中选择最有可能的手指。我有一个想法，可能可行也可能不可行。我现在没时间实现它，所以只是伪代码。

我注意到，如果前手指几乎保持在一个完美的圆圈上，后手指应该位于该圆圈内。此外，前手指的间距大致相等。我们可以尝试使用这些启发式特性来检测手指。

伪代码：

select the top N finger candidates (not too many, 10 or 12)
consider all possible combinations of 5 out of N (use itertools.combinations)
for each combination of 5 fingers:
    for each finger out of 5:
        fit the best circle to the remaining 4
        => position of the center, radius
        check if the selected finger is inside of the circle
        check if the remaining four are evenly spread
        (for example, consider angles from the center of the circle)
        assign some cost (penalty) to this selection of 4 peaks + a rear finger
        (consider, probably weighted:
             circle fitting error,
             if the rear finger is inside,
             variance in the spreading of the front fingers,
             total intensity of 5 peaks)
choose a combination of 4 peaks + a rear peak with the lowest penalty

这是一种蛮力方法。如果 N 相对较小，那么我认为这是可行的。对于 N=12，有 C_12^5 = 792 种组合，乘以 5 种选择后指的方法，因此每个爪子需要评估 3960 种情况。

解决方案 3：

这是一个图像配准问题。一般策略是：

• 有一个已知的例子，或者某种先前的数据。

• 使您的数据与示例相匹配，或使示例与您的数据相匹配。

• 如果您的数据首先大致对齐，这会有所帮助。

这是一个粗略而现成的方法，“可能最愚蠢但有效的方法”：

• 从大致位于您预期位置的五个脚趾坐标开始。

• 每次迭代，都爬到山顶。即给定当前位置，移动到最大相邻像素（如果其值大于当前像素）。当你的脚趾坐标停止移动时停止。

为了解决方向问题，您可以为基本方向（北、东北等）设置 8 个左右的初始设置。单独运行每个设置，并丢弃两个或多个脚趾最终位于同一像素的任何结果。我会再考虑一下，但这种事情仍在图像处理中研究 - 没有正确的答案！

稍微复杂一点的想法：（加权）K 均值聚类。其实也没那么糟糕。

• 从五个脚趾坐标开始，但现在这些是“聚类中心”。

然后迭代直至收敛：

• 将每个像素分配给最近的聚类（只需为每个聚类创建一个列表）。

• 计算每个聚类的质心。对于每个聚类，这是：Sum(坐标 * 强度值)/Sum(坐标)

• 将每个簇移动到新的质心。

这种方法几乎肯定会产生更好的结果，并且您可以获得每个簇的质量，这可能有助于识别脚趾。

（再次强调，您已经预先指定了聚类的数量。使用聚类时，您必须以某种方式指定密度：选择聚类的数量（在本例中是适当的），或者选择聚类半径并查看最终得到的数量。后者的一个例子是均值漂移。）

抱歉，缺少实施细节或其他细节。我会编写代码，但我有一个最后期限。如果下周之前没有其他办法，请告诉我，我会试一试。

解决方案 4：

使用持久同源性来分析您的数据集我得到以下结果（点击放大）：

这是此SO 答案中描述的峰值检测方法的 2D 版本。上图仅显示按持久性排序的 0 维持久同源性类。

我确实使用 scipy.misc.imresize() 将原始数据集放大了 2 倍。但是，请注意，我确实将四个爪子视为一个数据集；将其分成四个会使问题变得更容易。

方法论。
其背后的想法很简单：考虑为每个像素分配其级别的函数的函数图。它看起来像这样：

现在考虑高度为 255 的水位，该水位不断下降到更低的水位。在局部最大值处，岛屿会弹出（出生）。在鞍点处，两个岛屿合并；我们认为较低的岛屿会与较高的岛屿合并（死亡）。所谓的持久性图（0 维同源类，我们的岛屿）描绘了所有岛屿的死亡值与出生值的关系：

那么，岛屿的持久性就是出生水平与死亡水平之间的差异；即点到灰色主对角线的垂直距离。图中按持久性递减来标记岛屿。

第一张图片显示了岛屿的诞生位置。这种方法不仅给出了局部最大值，还通过上述持久性量化了它们的“重要性”。然后可以过滤掉所有持久性太低的岛屿。然而，在你的例子中，每个岛屿（即每个局部最大值）都是你要寻找的峰值。

Python 代码可以在这里找到。

解决方案 5：

我只能建议使用 k-means 聚类方法。k-means 是一种无监督聚类算法，它将获取数据（任意维度 - 我碰巧在 3D 中执行此操作）并将其排列成具有不同边界的 k 个聚类。这很好，因为您确切地知道这些犬齿（应该）有多少个脚趾。

此外，它在 Scipy 中实现，非常好（http://docs.scipy.org/doc/scipy/reference/cluster.vq.html）。

下面是它在空间上解析 3D 簇的一个例子：

您想要做的事情有点不同（2D 并包含压力值），但我仍然认为您可以尝试一下。

解决方案 6：

这里有一种方法：计算图像的（离散）拉普拉斯算子。我预计它在最大值处会是（负的）大，比原始图像中的情况更明显。因此，最大值可能更容易找到。

还有一个想法：如果你知道高压点的典型尺寸，你可以先用相同大小的高斯卷积来平滑图像。这可能会让你处理图像更简单。

解决方案 7：

我脑海中浮现的几个想法如下：

• 取扫描的梯度（导数），看看是否能消除错误调用

• 取局部最大值

您可能还想看看OpenCV，它有一个相当不错的 Python API，并且可能有一些您会觉得有用的功能。

解决方案 8：

我使用正则表达式修改了您的 txt 文件，并将其放入带有一些 javascript 的 html 页面中以实现可视化。我在这里分享它是因为有些人（比如我）可能会发现它比 python 更容易被黑客入侵。

我认为一个好的方法是尺度和旋转不变的，我的下一步将是研究高斯混合。（每个爪垫都是高斯的中心）。

    <html>
<head>
    <script type="text/javascript" src="http://vis.stanford.edu/protovis/protovis-r3.2.js"></script> 
    <script type="text/javascript">
    var heatmap = [[[0,0,0,0,0,0,0,4,4,0,0,0,0],
[0,0,0,0,0,7,14,22,18,7,0,0,0],
[0,0,0,0,11,40,65,43,18,7,0,0,0],
[0,0,0,0,14,61,72,32,7,4,11,14,4],
[0,7,14,11,7,22,25,11,4,14,65,72,14],
[4,29,79,54,14,7,4,11,18,29,79,83,18],
[0,18,54,32,18,43,36,29,61,76,25,18,4],
[0,4,7,7,25,90,79,36,79,90,22,0,0],
[0,0,0,0,11,47,40,14,29,36,7,0,0],
[0,0,0,0,4,7,7,4,4,4,0,0,0]
],[
[0,0,0,4,4,0,0,0,0,0,0,0,0],
[0,0,11,18,18,7,0,0,0,0,0,0,0],
[0,4,29,47,29,7,0,4,4,0,0,0,0],
[0,0,11,29,29,7,7,22,25,7,0,0,0],
[0,0,0,4,4,4,14,61,83,22,0,0,0],
[4,7,4,4,4,4,14,32,25,7,0,0,0],
[4,11,7,14,25,25,47,79,32,4,0,0,0],
[0,4,4,22,58,40,29,86,36,4,0,0,0],
[0,0,0,7,18,14,7,18,7,0,0,0,0],
[0,0,0,0,4,4,0,0,0,0,0,0,0],
],[
[0,0,0,4,11,11,7,4,0,0,0,0,0],
[0,0,0,4,22,36,32,22,11,4,0,0,0],
[4,11,7,4,11,29,54,50,22,4,0,0,0],
[11,58,43,11,4,11,25,22,11,11,18,7,0],
[11,50,43,18,11,4,4,7,18,61,86,29,4],
[0,11,18,54,58,25,32,50,32,47,54,14,0],
[0,0,14,72,76,40,86,101,32,11,7,4,0],
[0,0,4,22,22,18,47,65,18,0,0,0,0],
[0,0,0,0,4,4,7,11,4,0,0,0,0],
],[
[0,0,0,0,4,4,4,0,0,0,0,0,0],
[0,0,0,4,14,14,18,7,0,0,0,0,0],
[0,0,0,4,14,40,54,22,4,0,0,0,0],
[0,7,11,4,11,32,36,11,0,0,0,0,0],
[4,29,36,11,4,7,7,4,4,0,0,0,0],
[4,25,32,18,7,4,4,4,14,7,0,0,0],
[0,7,36,58,29,14,22,14,18,11,0,0,0],
[0,11,50,68,32,40,61,18,4,4,0,0,0],
[0,4,11,18,18,43,32,7,0,0,0,0,0],
[0,0,0,0,4,7,4,0,0,0,0,0,0],
],[
[0,0,0,0,0,0,4,7,4,0,0,0,0],
[0,0,0,0,4,18,25,32,25,7,0,0,0],
[0,0,0,4,18,65,68,29,11,0,0,0,0],
[0,4,4,4,18,65,54,18,4,7,14,11,0],
[4,22,36,14,4,14,11,7,7,29,79,47,7],
[7,54,76,36,18,14,11,36,40,32,72,36,4],
[4,11,18,18,61,79,36,54,97,40,14,7,0],
[0,0,0,11,58,101,40,47,108,50,7,0,0],
[0,0,0,4,11,25,7,11,22,11,0,0,0],
[0,0,0,0,0,4,0,0,0,0,0,0,0],
],[
[0,0,4,7,4,0,0,0,0,0,0,0,0],
[0,0,11,22,14,4,0,4,0,0,0,0,0],
[0,0,7,18,14,4,4,14,18,4,0,0,0],
[0,4,0,4,4,0,4,32,54,18,0,0,0],
[4,11,7,4,7,7,18,29,22,4,0,0,0],
[7,18,7,22,40,25,50,76,25,4,0,0,0],
[0,4,4,22,61,32,25,54,18,0,0,0,0],
[0,0,0,4,11,7,4,11,4,0,0,0,0],
],[
[0,0,0,0,7,14,11,4,0,0,0,0,0],
[0,0,0,4,18,43,50,32,14,4,0,0,0],
[0,4,11,4,7,29,61,65,43,11,0,0,0],
[4,18,54,25,7,11,32,40,25,7,11,4,0],
[4,36,86,40,11,7,7,7,7,25,58,25,4],
[0,7,18,25,65,40,18,25,22,22,47,18,0],
[0,0,4,32,79,47,43,86,54,11,7,4,0],
[0,0,0,14,32,14,25,61,40,7,0,0,0],
[0,0,0,0,4,4,4,11,7,0,0,0,0],
],[
[0,0,0,0,4,7,11,4,0,0,0,0,0],
[0,4,4,0,4,11,18,11,0,0,0,0,0],
[4,11,11,4,0,4,4,4,0,0,0,0,0],
[4,18,14,7,4,0,0,4,7,7,0,0,0],
[0,7,18,29,14,11,11,7,18,18,4,0,0],
[0,11,43,50,29,43,40,11,4,4,0,0,0],
[0,4,18,25,22,54,40,7,0,0,0,0,0],
[0,0,4,4,4,11,7,0,0,0,0,0,0],
],[
[0,0,0,0,0,7,7,7,7,0,0,0,0],
[0,0,0,0,7,32,32,18,4,0,0,0,0],
[0,0,0,0,11,54,40,14,4,4,22,11,0],
[0,7,14,11,4,14,11,4,4,25,94,50,7],
[4,25,65,43,11,7,4,7,22,25,54,36,7],
[0,7,25,22,29,58,32,25,72,61,14,7,0],
[0,0,4,4,40,115,68,29,83,72,11,0,0],
[0,0,0,0,11,29,18,7,18,14,4,0,0],
[0,0,0,0,0,4,0,0,0,0,0,0,0],
]
];
</script>
</head>
<body>
    <script type="text/javascript+protovis">    
    for (var a=0; a < heatmap.length; a++) {
    var w = heatmap[a][0].length,
    h = heatmap[a].length;
var vis = new pv.Panel()
    .width(w * 6)
    .height(h * 6)
    .strokeStyle("#aaa")
    .lineWidth(4)
    .antialias(true);
vis.add(pv.Image)
    .imageWidth(w)
    .imageHeight(h)
    .image(pv.Scale.linear()
        .domain(0, 99, 100)
        .range("#000", "#fff", '#ff0a0a')
        .by(function(i, j) heatmap[a][j][i]));
vis.render();
}
</script>
  </body>
</html>

解决方案 9：

有一个maxima使用 Python 在图像中查找本地的好方法：

from skimage.feature import peak_local_max

或者对于 skimage 0.8.0：

from skimage.feature.peak import peak_local_max

http://scikit-image.org/docs/0.8.0/api/skimage.feature.peak.html

解决方案 10：

物理学家的解决方案：

定义 5 个按位置标识的爪子标记X_i，并以随机位置初始化它们。定义一些能量函数，将标记在爪子位置的定位奖励与标记重叠的惩罚相结合；假设：

E(X_i;S)=-Sum_i(S(X_i))+alfa*Sum_ij (|X_i-Xj|<=2*sqrt(2)?1:0)

（S(X_i)是 2x2 正方形周围平均力X_i，alfa是需要通过实验达到峰值的参数）

现在是时候施展 Metropolis-Hastings 魔法了：

1. 选择随机标记并将其沿随机方向移动一个像素。2

. 计算 dE，即此移动引起的能量差异。3

. 获取 0-1 之间的均匀随机数并将其称为 r。4

. 如果dE<0或exp(-beta*dE)>r，则接受移动并转到 1；如果不是，则撤消移动并转到 1。

应重复此操作，直到标记收敛到爪子。Beta 控制扫描以优化权衡，因此也应通过实验进行优化；它也可以随着模拟时间（模拟退火）不断增加。

解决方案 11：

这是我在对大型望远镜进行类似操作时使用的另一种方法：

1) 搜索最高像素。找到最高像素后，围绕该像素搜索 2x2 的最佳拟合（可能最大化 2x2 的总和），或者在以最高像素为中心的 4x4 子区域内进行 2d 高斯拟合。

然后将你找到的 2x2 像素设置为峰值中心周围的零（或者可能是 3x3）

回到 1) 并重复，直到最高峰低于噪声阈值，或者你已经拥有了所需的所有脚趾

解决方案 12：

粗略的轮廓...

您可能需要使用连通分量算法来隔离每个爪子区域。 wiki 对此有一个详细的描述（带有一些代码）：http: //en.wikipedia.org/wiki/Connected_Component_Labeling

您必须决定是使用 4 连通性还是 8 连通性。就我个人而言，对于大多数问题，我更喜欢 6 连通性。无论如何，一旦您将每个“爪印”分离为连通区域，就应该很容易遍历该区域并找到最大值。一旦找到最大值，您就可以迭代地扩大该区域，直到达到预定的阈值，以便将其识别为给定的“脚趾”。

这里有一个微妙的问题是，一旦你开始使用计算机视觉技术来识别某物是右/左/前/后爪，并且开始观察单个脚趾，你就必须开始考虑旋转、倾斜和平移。这是通过分析所谓的“矩”来实现的。在视觉应用中需要考虑几个不同的矩：

中心矩：平移不变 归一化矩：缩放和平移不变 hu 矩：平移、缩放和旋转不变

您可以在 wiki 上搜索“图像时刻”来找到有关时刻的更多信息。

解决方案 13：

我要尝试的解决方案如下。

1. 应用低通滤波器，例如使用 2D 高斯掩模进行卷积。这将为您提供一堆（可能是但不一定是浮点）值。

2. 使用已知的每个爪垫（或脚趾）的近似半径执行 2D 非最大抑制。

这应该会为您提供最大位置，而不会出现多个位置相近的候选位置。需要澄清的是，步骤 1 中的蒙版半径也应该与步骤 2 中使用的半径相似。此半径可以是可选的，或者兽医可以事先明确测量（它会因年龄/品种等而异）。

一些建议的解决方案（均值漂移、神经网络等）可能在某种程度上会起作用，但过于复杂且可能并不理想。

解决方案 14：

嗯，这里有一些简单且不太高效的代码，但对于这种大小的数据集来说它是可以的。

import numpy as np
grid = 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.4,0.4,0.4,0,0,0],
              [0,0,0,0,0.4,1.4,1.4,1.8,0.7,0,0,0,0,0],
              [0,0,0,0,0.4,1.4,4,5.4,2.2,0.4,0,0,0,0],
              [0,0,0.7,1.1,0.4,1.1,3.2,3.6,1.1,0,0,0,0,0],
              [0,0.4,2.9,3.6,1.1,0.4,0.7,0.7,0.4,0.4,0,0,0,0],
              [0,0.4,2.5,3.2,1.8,0.7,0.4,0.4,0.4,1.4,0.7,0,0,0],
              [0,0,0.7,3.6,5.8,2.9,1.4,2.2,1.4,1.8,1.1,0,0,0],
              [0,0,1.1,5,6.8,3.2,4,6.1,1.8,0.4,0.4,0,0,0],
              [0,0,0.4,1.1,1.8,1.8,4.3,3.2,0.7,0,0,0,0,0],
              [0,0,0,0,0,0.4,0.7,0.4,0,0,0,0,0,0]])

arr = []
for i in xrange(grid.shape[0] - 1):
    for j in xrange(grid.shape[1] - 1):
        tot = grid[i][j] + grid[i+1][j] + grid[i][j+1] + grid[i+1][j+1]
        arr.append([(i,j),tot])

best = []

arr.sort(key = lambda x: x[1])

for i in xrange(5):
    best.append(arr.pop())
    badpos = set([(best[-1][0][0]+x,best[-1][0][1]+y)
                  for x in [-1,0,1] for y in [-1,0,1] if x != 0 or y != 0])
    for j in xrange(len(arr)-1,-1,-1):
        if arr[j][0] in badpos:
            arr.pop(j)


for item in best:
    print grid[item[0][0]:item[0][0]+2,item[0][1]:item[0][1]+2]

我基本上只是用左上角的位置和每个 2x2 方块的总和创建一个数组，并按总和对其进行排序。然后，我将总和最高的 2x2 方块从争用中取出，将其放入数组中best，并移除所有使用刚移除的 2x2 方块的任何部分的其他 2x2 方块。

它似乎运行良好，除了最后一只爪子（第一张图片中最右边总和最小的爪子），结果发现还有另外两个符合条件的 2x2 方块，总和更大（并且它们的总和相等）。其中一个仍然从你的 2x2 方块中选择一个方块，但另一个在左边。幸运的是，我们幸运地看到选择了更多你想要的方块，但这可能需要使用一些其他的想法来获得你真正想要的东西。

解决方案 15：

我不确定这是否回答了这个问题，但似乎你只需寻找没有邻居的 n 个最高峰即可。

要点如下。 请注意，它是用 Ruby 编写的，但思路应该很清楚。

require 'pp'

NUM_PEAKS = 5
NEIGHBOR_DISTANCE = 1

data = [[1,2,3,4,5],
        [2,6,4,4,6],
        [3,6,7,4,3],
       ]

def tuples(matrix)
  tuples = []
  matrix.each_with_index { |row, ri|
    row.each_with_index { |value, ci|
      tuples << [value, ri, ci]
    }
  }
  tuples
end

def neighbor?(t1, t2, distance = 1)
  [1,2].each { |axis|
    return false if (t1[axis] - t2[axis]).abs > distance
  }
  true
end

# convert the matrix into a sorted list of tuples (value, row, col), highest peaks first
sorted = tuples(data).sort_by { |tuple| tuple.first }.reverse

# the list of peaks that don't have neighbors
non_neighboring_peaks = []

sorted.each { |candidate|
  # always take the highest peak
  if non_neighboring_peaks.empty?
    non_neighboring_peaks << candidate
    puts "took the first peak: #{candidate}"
  else
    # check that this candidate doesn't have any accepted neighbors
    is_ok = true
    non_neighboring_peaks.each { |accepted|
      if neighbor?(candidate, accepted, NEIGHBOR_DISTANCE)
        is_ok = false
        break
      end
    }
    if is_ok
      non_neighboring_peaks << candidate
      puts "took #{candidate}"
    else
      puts "denied #{candidate}"
    end
  end
}

pp non_neighboring_peaks

解决方案 16：

也许一种简单的方法就足够了：建立平面上所有 2x2 正方形的列表，按它们的总和排序（降序）。

首先，选择价值最高的方块放入“爪子列表”。然后，迭代地挑选 4 个与之前找到的任何方块都不相交的次优方块。

解决方案 17：

如果您一步一步地进行会怎样：首先找到全局最大值，如果需要，根据它们的值处理周围的点，然后将找到的区域设置为零，并重复下一个。