查找给定数据集的局部最大值点

Question

因此，我开始尝试使用从加速度计获得的数据来计算用户所走的步数，即 x、y 和 z 坐标。

我正在尝试实现 this 算法，但我目前卡在局部最大值部分。 Matlab 有一个内置的 findpeaks() 方法，可以定位给定数据集的所有局部最大值。

下面是我尝试实现该算法，但我仍然从中得到了非常巨大的结果。起初，使用由 20 个实际步数组成的数据集，算法计算出所走的步数为 990+。我对其进行了调整和调试，并设法将这个数字降低到 660 左右。然后 110 最终达到了当前的 45。目前我只是卡住了，感觉我的 findpeaks() 方法是错误的。

这是我的class实现

import Foundation

class StepCounter
{
   private var xAxes: [Double] = [Double]()
   private var yAxes: [Double] = [Double]()
   private var zAxes: [Double] = [Double]()
   private var rmsValues: [Double] = [Double]()

  init(graphPoints: GraphPoints)
 {
    xAxes = graphPoints.xAxes
    yAxes = graphPoints.yAxes
    zAxes = graphPoints.zAxes
    rmsValues = graphPoints.rmsValues
 }

func numberOfSteps()-> Int
{
    var pointMagnitudes: [Double] = rmsValues
    
    removeGravityEffectsFrom(&pointMagnitudes)
    
    let minimumPeakHeight: Double = standardDeviationOf(pointMagnitudes)
    
    let peaks = findPeaks(&pointMagnitudes)
    
    var totalNumberOfSteps: Int = Int()
    
    for thisPeak in peaks
    {
        if thisPeak > minimumPeakHeight
        {
            totalNumberOfSteps += 1
        }
    }
    
    return totalNumberOfSteps
}

// TODO: dummy method for the time being. replaced with RMS values from controller itself
private func calculateMagnitude()-> [Double]
{
    var pointMagnitudes: [Double] = [Double]()
    
    for i in 0..<xAxes.count
    {
        let sumOfAxesSquare: Double = pow(xAxes[i], 2) + pow(yAxes[i], 2) + pow(zAxes[i], 2)
        pointMagnitudes.append(sqrt(sumOfAxesSquare))
    }
    
    return pointMagnitudes
}

private func removeGravityEffectsFrom(inout magnitudesWithGravityEffect: [Double])
{
    let mean: Double = calculateMeanOf(rmsValues)
    
    for i in 0..<magnitudesWithGravityEffect.count
    {
        magnitudesWithGravityEffect[i] -= mean
    }
}

// Reference: https://en.wikipedia.org/wiki/Standard_deviation
private func standardDeviationOf(magnitudes: [Double])-> Double
{
    var sumOfElements: Double = Double()
    var mutableMagnitudes: [Double] = magnitudes
    
    // calculates the numerator of the equation
    /* no need to do (mutableMagnitudes[i] = mutableMagnitudes[i] - mean) 
     * because it has already been done when the gravity effect was removed
     * from the dataset
     */
    for i in 0..<mutableMagnitudes.count
    {
        mutableMagnitudes[i] = pow(mutableMagnitudes[i], 2)
    }
    
    // sum the elements
    for thisElement in mutableMagnitudes
    {
        sumOfElements += thisElement
    }
    
    let sampleVariance: Double = sumOfElements/Double(mutableMagnitudes.count)
    
    return sqrt(sampleVariance)
}

// Reference: http://www.mathworks.com/help/signal/ref/findpeaks.html#examples
private func findPeaks(inout magnitudes: [Double])-> [Double]
{
    var peaks: [Double] = [Double]()
    
    // ignore the first element
    peaks.append(max(magnitudes[1], magnitudes[2]))
    
    for i in 2..<magnitudes.count
    {
        if i != magnitudes.count - 1
        {
            peaks.append(max(magnitudes[i], magnitudes[i - 1], magnitudes[i + 1]))
        }
        else
        {
            break
        }
    }
    
    // TODO:Does this affect the number of steps? Are they clumsly lost or foolishly added?
    peaks = Array(Set(peaks)) // removing duplicates.
    
    return peaks
}

private func calculateMeanOf(magnitudes: [Double])-> Double
{
    var sumOfElements: Double = Double()
    
    for thisElement in magnitudes
    {
        sumOfElements += thisElement
    }
    
    return sumOfElements/Double(magnitudes.count)
}

}`

有了这个 datasheet，实际走的步数是 20，但我一直在绕 45。即使当我尝试使用包含 30 个实际步骤的数据集时，计算出的数字也接近 100s.

任何 assistance/guidance 将不胜感激

PS：数据表格式为X,Y,Z,RMS(均方根)

Answer 1

此函数适用于您提供的示例。它将高原视为一个峰，并允许具有相同值的多个峰。唯一的问题是——@user3386109 指出——如果数据中有很多小的振荡，你会得到比实际存在的更多的峰值。如果您要处理这样的数据，您可能希望在此计算中实现数据集的方差。

此外，由于您没有更改传入的变量，因此无需使用 inout

private func findPeaks(magnitudes: [Double]) -> [Double] {

    var peaks = [Double]()
    // Only store initial point, if it is larger than the second. You can ignore in most data sets 
    if max(magnitudes[0], magnitudes[1]) == magnitudes[0] { peaks.append(magnitudes[0]) }

    for i in 1..<magnitudes.count - 2 {
        let maximum = max(magnitudes[i - 1], magnitudes[i], magnitudes[i + 1])
        // magnitudes[i] is a peak iff it's greater than it's surrounding points 
        if maximum == magnitudes[i] && magnitudes[i] != magnitudes[i+1] {
            peaks.append(magnitudes[i])
        }
    }
    return peaks
}

更新我注意到我的解决方案不会在集合的末尾找到局部最大值。我已经对其进行了更新并将其实现为 Collection 上的扩展。这可以很容易地适应 Sequence，但我不确定这是否有意义。

extension Collection where Element: Comparable {
    func localMaxima() -> [Element] {
        return localMaxima(in: startIndex..<endIndex)
    }

    func localMaxima(in range: Range<Index>) -> [Element] {
        var slice = self[range]
        var maxima = [Element]()

        var previousIndex: Index? = nil
        var currentIndex = slice.startIndex
        var nextIndex = slice.index(after: currentIndex)

        while currentIndex < slice.endIndex {
            defer {
                previousIndex = currentIndex
                currentIndex = nextIndex
                nextIndex = slice.index(after: nextIndex)
            }

            let current = slice[currentIndex]
            let next = slice[nextIndex]

            // For the first element, there is no previous
            if previousIndex == nil, Swift.max(current, next) == current {
                maxima.append(current)
                continue
            }

            // For the last element, there is no next
            if nextIndex == slice.endIndex {
                let previous = slice[previousIndex!]
                if Swift.max(previous, current) == current {
                    maxima.append(current)
                }
                continue
            }

            let previous = slice[previousIndex!]

            let maximum = Swift.max(previous, current, next)
            // magnitudes[i] is a peak iff it's greater than it's surrounding points
            if maximum == current && current != next {
                maxima.append(current)
            }
        }
        return maxima
    }
}

为了它的价值，这里有一个关于 Sequence

的扩展

extension Sequence where Element: Comparable {
    func localMaxima() -> [Element] {
        var maxima = [Element]()
        var iterator = self.makeIterator()

        var previous: Element? = nil
        guard var current = iterator.next() else { return [] }
        while let next = iterator.next() {
            defer {
                previous = current
                current = next
            }

            // For the first element, there is no previous
            if previous == nil, Swift.max(current, next) == current {
                maxima.append(current)
                continue
            }

            let maximum = Swift.max(previous!, current, next)
            // magnitudes[i] is a peak iff it's greater than it's surrounding points
            if maximum == current && current != next {
                maxima.append(current)
            }
        }

        // For the last element, there is no next
        if Swift.max(previous!, current) == current {
            maxima.append(current)
        }

        return maxima
    }
}

Answer 2

此解决方案基于@jjatie 的回答。它修复了我遇到的可选值意外为 nil 的问题，并添加了一个内部标志以允许抑制最后一个最大值（如果它是最后一个元素）。

我需要最后一点，因为在我的例子中它只是上升沿而不是最大值。

它还 return 索引而不是值。相关部分我刚刚被注释掉了。如果需要，您可以轻松将其改回。如果需要，您甚至可以使用代码 return 对。不过，获取索引的实际值真的很容易。

查看包含的示例数据。它突出显示了我发现的所有问题。有兴趣的可以用原答案试试

代码是在 iPad Swift Playgrounds 中编写的。这就是为什么它看起来很奇怪。

extension Collection where Element: Comparable {
    func localMaximaIndexes() -> [Index] {
        return localMaximaIndexes(in: startIndex..<endIndex)
    }
    
    func localMaximaIndexes(in range: Range<Index>) -> [Index] {
        let wantLastElementIfLocalMaximum = false
        
        var slice = self[range]
        //var maxima = [Element]()
        var indexes = [Index]()
        
        var previousIndex: Index? = nil
        var currentIndex = slice.startIndex
        var nextIndex = slice.index(after: currentIndex)
        
        while currentIndex < slice.endIndex {
            defer {
                previousIndex = currentIndex
                currentIndex = nextIndex
                nextIndex = slice.index(after: nextIndex)
            }
            
            let current = slice[currentIndex]
            
            // For the last element, there is no next.
            if nextIndex == slice.endIndex {
                if wantLastElementIfLocalMaximum, 
                   let previousIndex = previousIndex {
                    let previous = slice[previousIndex]
                    if Swift.max(previous, current) == current {
                        //maxima.append(current)
                        indexes.append(currentIndex)
                    }
                }
                
                continue
            }
            
            let next = slice[nextIndex]
            
            // For the first element, there is no previous.
            if previousIndex == nil {
                if Swift.max(current, next) == current {
                    //maxima.append(current)
                    indexes.append(currentIndex)
                }
                
                continue
            }
            
            let previous = slice[previousIndex!]
            
            let maximum = Swift.max(previous, current, next)
            // magnitudes[i] is a peak iff it's greater than it's surrounding points.
            if maximum == current && current != next {
                //maxima.append(current)
                indexes.append(currentIndex)
            }
        }
        
        return indexes
    }
}

typealias Sample = Float

let result: [Sample]  = [-1.1324883e-06, 3.0614667, 5.6568537, 7.391036, 8.0, 7.391037, 5.6568546, 3.0614676, 5.5134296e-07, -3.0614667, -5.6568537, -7.391036, -8.0, -7.3910365, -5.6568546, -3.0614681, -4.3213367e-07, 3.0614672, 5.3033004, 6.4671564, 6.5, 5.543277, 3.8890872, 1.9134172, -1.937151e-07, -1.5307341, -2.474874, -2.7716386, -2.5, -1.847759, -1.06066, -0.38268328]

let maximaIndexes = result.localMaximaIndexes()

查找给定数据集的局部最大值点

Finding local maximum points of a given data set

algorithm

matlab

accelerometer

ios

swift