Emil David Emil David - 4 months ago 19
iOS Question

Finding local maximum points of a given data set

So I embarked on a quest to calculate the number of steps taken by a user by using the data I get from the accelerometer i.e x, y and z coordinates.

I am trying to implement this algorithm but I am currently stuck at the local maxima portion. Matlab has a built in

findpeaks()
method which locates all the local maxima of a given data set.

Below is my attempt at implementing the algorithm but I still get extremely enormous results from it.
At first, using a data set which consisted of
20
actual steps, the algorithm calculated that the number of steps taken was
990+
. I tweaked and debugged it and I managed to bring this number down to around
660
..then
110
finally to a current
45
. Currently I am just stuck and have a feeling that my
findpeaks()
method is wrong.

This is my class implementation

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


}`

With this datasheet, the actual number of steps taken was
20
but I keep getting around
45
. Even when I tried it with a dataset that consists of
30
actual steps, the calculated number was approaching the
100s.


Any assistance/guidance will be greatly appreciated

PS: Datasheet format is X,Y,Z,RMS(root mean square)

Answer

This function works with the example you provided. It treats plateaus as one peak, and allows for multiple peaks of the same value. The only problem is as — @user3386109 points outs — if there are lots of little oscillations in the data you will get more peaks than are really there. You might want to implement variance of the dataset in this calculation if you will be dealing with data like that.

Also, since you aren't changing the variable you pass in there is no need to use 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
}