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

Question

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

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

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

这是我的类实现

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。

任何帮助/指导将不胜感激

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
    }
}