定位局部最大值的算法 [英] Algorithm to locate local maxima

问题描述

我的数据总是如下所示：

alt text http://michaelfogleman.com/static/images/chart.png

我需要一种算法来定位三个峰值。

x轴实际上是一个摄像头位置，y轴是该位置图像焦点/对比度的度量。有三种不同距离的特征可以聚焦，我需要确定这三个点的x值。

中间的驼峰总是有点难即使对于人类也是如此。

我有一个自制的算法，大部分都可以工作，但我想知道是否有一种标准的方法来从函数中获取局部最大值可以有一点噪音。此外，作为相机数据，一种不需要扫描整个范围的算法也可能是有用的。

$ b

$ b

编辑：发布我最终使用的Python代码。它使用我的原始代码，可以找到给定搜索阈值的最大值，并执行二分搜索以找到导致所需最大值数量的阈值。

编辑：包含在下面的代码中的示例数据。新代码是O（n）而不是O（n ^ 2）。

  def find_n_maxima（data，count）：
 low = 0 
 high = max（data） -  min（data）
用于xrange（100）中的迭代：＃max iterations 
 mid = low +（high  -  low）/ 2.0 
 maxima = find_maxima（data，mid）
 if len（maxima）== count：
 return maxima 
 elif len（maxima）< count：＃门槛太高
 high = mid 
 else：＃门槛太低
 low = mid 
 return无＃失败
 
 def find_maxima（data ，阈值）：
 def search（data，threshold，index，forward）：
 max_index = index 
 max_value = data [index] 
如果转发：
 path = xrange（index + 1，len（data））
 else：
 path = xrange（index  -  1，-1，-1）
 for i in path：
 if data [i]> max_value：
 max_index = i 
 max_value = data [i] 
 elif max_value  -  data [i]>阈值：
 break 
 return max_index，i 
＃forward pass 
 forward = set（）
 index = 0 
 while index< len（data） -  1：
 maximum，index = search（data，threshold，index，True）
 forward.add（maximum）
 index + = 1 
＃reverse＃ 
 reverse = set（）
 index = len（data） -  1 
 while index> 0：
最大值，index =搜索（数据，阈值，索引，假）
 reverse.add（最大值）
索引 -  = 1 
返回值排序（正向和反向） 
 
 data = [
 1263.900,1271.968,1276.151,1282.254,1287.156,1296.513，
 1298.799,130​​4.725,1309.996,1314.484,1321.759,1323.988，
 1331.923,1336.100 ，1340.007,1340.548,1343.124,1353.717，
 1359.175,1364.638,1364.548,1357.525,1362.012,1367.190，
 1367.852,1376.275,1374.726,1374.260,1392.284,1382.035，
 1399.418,1401.785，1400.353 ，1418.418,1420.401,1423.711，
 1425.214,1436.231,1431.356,1435.665,1445.239,1438.701，
 1441.988,1448.930,1455.066,1455.047,1456.652,1456.771，
 1459.191,1473.207,1465.788，1488.785 ，1491.422，1492.827，
 1498.112，1498.855，1505.426，1514.587，1512.174，1525.244，
 1532.235，1543.360，1543.985，1548.323，1552.478，1576.477，
 1589.333，1610.769，1623.852，1634.61 8，1662.585，1704.127，
 1758.718，1807.490，1852.097，1969.540，2243.820，2354.224，
 2881.420，2818.216，2552.177，2355.270，2033.465，1965.328，
 1824.853，1831.997，1779.384，1764.789， 1704.507,1683.615，
 1652.712,1646.422,1620.593,1620.235,1613.024,1607.675，
 1604.015,1574.567,1587.718,1584.822,1588.432,1593.377，
 1590.533,1601.445,1667.327,1739.034,1915.442， 2128.835，
 2147.193，1970.836,1755.509,1653.258,1613.284,1558.576，
 1552.720,1541.606,1516.091,1503.747,1488.797,1492.021，
 1466.720,1457.120,1462.485，1451.347,1453.224,1440.477， 
 1438.634，1444.571，1428.962，1431.486，1421.721，1421.367，
 1403.461，1415.482，1405.318，1399.041，1399.306，1390.486，
 1396.746，1386.178，1376.941，1369.880，1359.294，1358.123，
 1353.398,1345.121,1338.808,1330.982,1324.264,1322.147，
 1321.098,1313.729,1310.168,1304.218,1293.445,1285.296，
 12 81.882,1280.444,1274.795,1271.765,1266.857,1260.161，
 1254.380,1247.886,1250.585,1246.901,1245.061,1238.658，
 1235.497,1231.393,1226.241,1223.136,1218.232,1219.658，
 1222.149， 1216.385,1214.313,1211.167,1208.203,1206.178，
 1206.139,1202.020,1205.854,1206.720,1204.005,1205.308，
 1199.405,1198.023,1196.419,1194.532,1194.543,1193.482，
 1197.279，1196.998， 1194.489,118.537,1188.338,1184.860，
 1184.633,1184.930,1182.631,1187.617,1179.873,1171.960，
 1170.831,1167.442,1177.138,1166.485,1164.465,1161.374，
 1167.185,1174.334,1186.339， 1202.136，1234.999，1283.328，
 1347.111，1679.050，1927.083，1860.902，1602.791，1350.454，​​
 1274.236，1207.727，1169.078，1138.025，1117.319，1109.169，
 1080.018，1073.837，1059.876，1050.209， 1050.859,1035.003，
 1029.214,1024.602,1017.932,1006.911,1010.722,1005.582，
 1000.332,998.0721,992.7311,992.65 07，981.0430，969.9936，
 972.8696，967.9463,970.1519,957.1309,959.9917,958.0536，
 954.6357,995.9951,947.8299,953.3991,949.2725,948.9012，
 939.8549,940.1641,942.9881,938.4526， 937.9550,929.6279，
 935.5402,921.5773,933.6365,918.7065,922.5849,939.6088，
 911.3251,923.7205,924.8227,911.3192,936.7066,915.2046，
 919.0274,915.0533,910.9783,913.6773,916.6287， 907.9267，
 908.0421,908.7398,911.8401,914.5696,912.0115,919.4418，
 917.0436,920.5495,917.6138,907.5037,908.5145,919.5846，
 917.6047,926.8447,910.6347,912.8305,907.7085,911.6889， 
 
 
 for n in xrange（1，6）：
 print'寻找％d maxima：'％n 
 indexes = find_n_maxima（data，n） 
 print index 
 print'，'.join（str（data [i]）for i in index）
 print 
  

输出：

 寻找1个最大值：
 [78 ] 
 2881.42 
 
 L ooking for 2 maxima：
 [78，218] 
 2881.42，1927.083 
 
寻找3个最大值：
 [78，108，218] 
 2881.42 ，2147.193，1927.083 
 
寻找4最大值：
 [78，108，218，274] 
 2881.42，2147.193，1927.083，936.7066 
 
 Looking对于5个最大值：
 [78,108,218,269,274] 
 2881.42,2147.193,1927.083,939.6088,936.7066 
  

解决方案

局部最大值将是任何x点，其y值高于其左右邻居。为了消除噪音，可以放入某种容差阈值（例如，x点必须具有比其邻居的n更高的y值）。为了避免扫描每一个点，你可以使用相同的方法，但一次只能得到5或10个点，以粗略地理解最大谎言的位置。然后回到这些地方进行更详细的扫描。

I have data that always looks something like this:

alt text http://michaelfogleman.com/static/images/chart.png

I need an algorithm to locate the three peaks.

The x-axis is actually a camera position and the y-axis is a measure of image focus/contrast at that position. There are features at three different distances that can be in focus and I need to determine the x-values for these three points.

The middle hump is always a little harder to pick out, even for a human.

I have a homemade algorithm that mostly works, but I'm wondering if there's a standard way to grab local maxima from a function that can have a little noise in it. The peaks overcome the noise easily though.

Also, being camera data, an algorithm that doesn't require scanning the full range could be useful.

Edit: Posting the Python code that I ended up using. It uses my original code that finds maxima given a search threshold and does a binary search to find a threshold that results in the desired number of maxima.

Edit: Sample data included in code below. New code is O(n) instead of O(n^2).

def find_n_maxima(data, count):
    low = 0
    high = max(data) - min(data)
    for iteration in xrange(100): # max iterations
        mid = low + (high - low) / 2.0
        maxima = find_maxima(data, mid)
        if len(maxima) == count:
            return maxima
        elif len(maxima) < count: # threshold too high
            high = mid
        else: # threshold too low
            low = mid
    return None # failed

def find_maxima(data, threshold):
    def search(data, threshold, index, forward):
        max_index = index
        max_value = data[index]
        if forward:
            path = xrange(index + 1, len(data))
        else:
            path = xrange(index - 1, -1, -1)
        for i in path:
            if data[i] > max_value:
                max_index = i
                max_value = data[i]
            elif max_value - data[i] > threshold:
                break
        return max_index, i
    # forward pass
    forward = set()
    index = 0
    while index < len(data) - 1:
        maximum, index = search(data, threshold, index, True)
        forward.add(maximum)
        index += 1
    # reverse pass
    reverse = set()
    index = len(data) - 1
    while index > 0:
        maximum, index = search(data, threshold, index, False)
        reverse.add(maximum)
        index -= 1
    return sorted(forward & reverse)

data = [
    1263.900, 1271.968, 1276.151, 1282.254, 1287.156, 1296.513,
    1298.799, 1304.725, 1309.996, 1314.484, 1321.759, 1323.988,
    1331.923, 1336.100, 1340.007, 1340.548, 1343.124, 1353.717,
    1359.175, 1364.638, 1364.548, 1357.525, 1362.012, 1367.190,
    1367.852, 1376.275, 1374.726, 1374.260, 1392.284, 1382.035,
    1399.418, 1401.785, 1400.353, 1418.418, 1420.401, 1423.711,
    1425.214, 1436.231, 1431.356, 1435.665, 1445.239, 1438.701,
    1441.988, 1448.930, 1455.066, 1455.047, 1456.652, 1456.771,
    1459.191, 1473.207, 1465.788, 1488.785, 1491.422, 1492.827,
    1498.112, 1498.855, 1505.426, 1514.587, 1512.174, 1525.244,
    1532.235, 1543.360, 1543.985, 1548.323, 1552.478, 1576.477,
    1589.333, 1610.769, 1623.852, 1634.618, 1662.585, 1704.127,
    1758.718, 1807.490, 1852.097, 1969.540, 2243.820, 2354.224,
    2881.420, 2818.216, 2552.177, 2355.270, 2033.465, 1965.328,
    1824.853, 1831.997, 1779.384, 1764.789, 1704.507, 1683.615,
    1652.712, 1646.422, 1620.593, 1620.235, 1613.024, 1607.675,
    1604.015, 1574.567, 1587.718, 1584.822, 1588.432, 1593.377,
    1590.533, 1601.445, 1667.327, 1739.034, 1915.442, 2128.835,
    2147.193, 1970.836, 1755.509, 1653.258, 1613.284, 1558.576,
    1552.720, 1541.606, 1516.091, 1503.747, 1488.797, 1492.021,
    1466.720, 1457.120, 1462.485, 1451.347, 1453.224, 1440.477,
    1438.634, 1444.571, 1428.962, 1431.486, 1421.721, 1421.367,
    1403.461, 1415.482, 1405.318, 1399.041, 1399.306, 1390.486,
    1396.746, 1386.178, 1376.941, 1369.880, 1359.294, 1358.123,
    1353.398, 1345.121, 1338.808, 1330.982, 1324.264, 1322.147,
    1321.098, 1313.729, 1310.168, 1304.218, 1293.445, 1285.296,
    1281.882, 1280.444, 1274.795, 1271.765, 1266.857, 1260.161,
    1254.380, 1247.886, 1250.585, 1246.901, 1245.061, 1238.658,
    1235.497, 1231.393, 1226.241, 1223.136, 1218.232, 1219.658,
    1222.149, 1216.385, 1214.313, 1211.167, 1208.203, 1206.178,
    1206.139, 1202.020, 1205.854, 1206.720, 1204.005, 1205.308,
    1199.405, 1198.023, 1196.419, 1194.532, 1194.543, 1193.482,
    1197.279, 1196.998, 1194.489, 1189.537, 1188.338, 1184.860,
    1184.633, 1184.930, 1182.631, 1187.617, 1179.873, 1171.960,
    1170.831, 1167.442, 1177.138, 1166.485, 1164.465, 1161.374,
    1167.185, 1174.334, 1186.339, 1202.136, 1234.999, 1283.328,
    1347.111, 1679.050, 1927.083, 1860.902, 1602.791, 1350.454,
    1274.236, 1207.727, 1169.078, 1138.025, 1117.319, 1109.169,
    1080.018, 1073.837, 1059.876, 1050.209, 1050.859, 1035.003,
    1029.214, 1024.602, 1017.932, 1006.911, 1010.722, 1005.582,
    1000.332, 998.0721, 992.7311, 992.6507, 981.0430, 969.9936,
    972.8696, 967.9463, 970.1519, 957.1309, 959.6917, 958.0536,
    954.6357, 954.9951, 947.8299, 953.3991, 949.2725, 948.9012,
    939.8549, 940.1641, 942.9881, 938.4526, 937.9550, 929.6279,
    935.5402, 921.5773, 933.6365, 918.7065, 922.5849, 939.6088,
    911.3251, 923.7205, 924.8227, 911.3192, 936.7066, 915.2046,
    919.0274, 915.0533, 910.9783, 913.6773, 916.6287, 907.9267,
    908.0421, 908.7398, 911.8401, 914.5696, 912.0115, 919.4418,
    917.0436, 920.5495, 917.6138, 907.5037, 908.5145, 919.5846,
    917.6047, 926.8447, 910.6347, 912.8305, 907.7085, 911.6889,
]

for n in xrange(1, 6):
    print 'Looking for %d maxima:' % n
    indexes = find_n_maxima(data, n)
    print indexes
    print ', '.join(str(data[i]) for i in indexes)
    print

Output:

Looking for 1 maxima:
[78]
2881.42

Looking for 2 maxima:
[78, 218]
2881.42, 1927.083

Looking for 3 maxima:
[78, 108, 218]
2881.42, 2147.193, 1927.083

Looking for 4 maxima:
[78, 108, 218, 274]
2881.42, 2147.193, 1927.083, 936.7066

Looking for 5 maxima:
[78, 108, 218, 269, 274]
2881.42, 2147.193, 1927.083, 939.6088, 936.7066

解决方案

The local maxima would be any x point which has a higher y value than either of its left and right neighbors. To eliminate noise, you could put in some kind of tolerance threshold (ex. x point must have higher y value than n of its neighbors).

To avoid scanning every point, you could use the same approach but go 5 or 10 points at a time to get a rough sense of where the maximum lie. Then come back to those areas for a more detailed scan.

这篇关于定位局部最大值的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！