在两个Numpy数组中查找序列

Question

我有两个Numpy数组，这些数组里存的是另一个数组中最大值和最小值的索引。

举个例子，某个输出的最大值和最小值数组看起来是这样的：

Maxima indices are (array([ 4, 10, 14, 37, 43, 51, 59, 67, 81, 89, 95]),)
Minima indices are (array([ 7, 12, 25, 33, 40, 49, 56, 63, 76, 92]),)

这些索引是来自一行图像的强度值。

我需要找出在两个最小值之间，最大值出现了多少次，也就是说：

minima + 4 + maxima + 4 + minima

我该如何在Python中高效地做到这一点？我该如何比较这两个数组中的索引值，以找到这种序列的实例，并统计总共有多少个实例？

非常感谢任何帮助。

编辑： 每个最大值必须在最左边和最右边最近的最小值的4个位置之内。基本上，我是想根据强度值在图像中识别出一条虚线。

Answer 1

我将这个作为另一个回答，因为这是一个完全不同的方法。虽然不太节省空间，但代码非常简短，而且很符合numpy的风格。

import numpy

# let's assume minima and maxima are 1-d arrays
# then the distance matrix for distances between any maximum to any minimum is:
md = numpy.amin(numpy.abs(maxima[:,None]-minima[None,:]), axis=1)

# the maxima which are at most D pixels away form the closest minima:
cm = maxima[md < D]

当然，这些代码可以组合成一行，但会变得很难理解。

简单解释一下：

• 首先计算一个距离矩阵，这个矩阵显示了所有最小值（列）和最大值（行）之间的距离（里面有很多多余和无关的信息）
• 然后取这个矩阵的绝对值，得到每个最大值到每个最小值的距离
• 接着用amin操作找到每个最大值到任何最小值的最短距离，这个操作是在每一行进行的
• 最后，通过用一个布尔数组索引最大值来计算cm（布尔数组中，距离低于某个限制的地方标记为真）

如果向量很长，这个过程可能会变得很慢。如果不着急，这段代码还是很简单的。

Answer 2

让我们试试看。

import numpy

# create a vector for distances from the nearest leftmost minimum
# img_len is the length of the image row

# first we create an integer vector with 1 at each minimum
b = numpy.zeros(img_len, dtype='int')

# then we create an integer vector for the distances
d = numpy.zeros(img_len, dtype='int')

# we mark leftmost distances up to the first minimum to be largest possible
d[:minima[0]] = minima[0] - numpy.arange(minima[0])

# then we iterate through the vector and calculate the distances
for i in range(len(minima) - 1):
    prev = minima[i]
    next = minima[i+1]
    # now we have a gap between the two minima
    # let's fill it with a triangle 0,1,2,...,2,1,0
    k = (next-prev + 1) // 2
    d[prev:prev+k+1] = numpy.arange(k+1)
    d[next-k+1:next] = k -1 - numpy.arange(k-1)

# fill in the space after the last minimum:
d[minima[-1]:] = numpy.arange(img_len - minima[-1])

# all maxima whose distance is less than D from the closest minimum
results = [ m for m in maxima if d[m] < D ]

除非从代码中很明显，否则这里的想法是创建一个向量 d，它表示离最近的最小值的距离。得到的向量比如是 4,3,2,1,0,1,2,3,2,1,0,1,2,1,0,... 其中的零对应的是最小值的位置。最难的部分是确保在循环中正确地形成三角形。（我希望我已经处理好了所有的越界问题...）

当然，现在你也可以为最大值的位置创建一个元组列表：

[ (m, d[m]) for m in maxima ]

对于问题中的数据，这段代码返回：

[(4, 3),
 (10, 2),
 (14, 2),
 (37, 3),
 (43, 3),
 (51, 2),
 (59, 3),
 (67, 4),
 (81, 5),
 (89, 3),
 (95, 3)]

即使在两个最小值之间有多个最大值，这段代码也能正常工作。（如果只有一个最大值，那么代码几乎会完全不同。）