CODEWITHSUNDEEP
pythonnumpyscipy
vondip
vondip

Reputation: 14029

numpy how find local minimum in neighborhood on 1darray

I've got a list of sorted samples. They're sorted by their sample time, where each sample is taken one second after the previous one. I'd like to find the minimum value in a neighborhood of a specified size.

For example, given a neighborhood size of 2 and the following sample size:

samples = [ 5, 12.3, 12.3, 7, 2, 6, 9, 10, 5, 9, 17, 2 ]

I'd expect the following output: [5, 2, 5, 2] What would be the best way to achieve this in numpy / scipy

Edited: Explained the reasoning behind the min values:

  1. 5 - the 2 number window next to it are [12.3 12.3]. 5 is smaller
  2. 2 - to the left [12.3, 7] to the right [6 9]. 2 is the min
  3. 5 - to the left [9 10] to the right [9 17]. 5 is the min

notice that 9 isn't min are there's a 2 window to its left and right with a smaller value (2)

Upvotes: 2

Views: 5489

Answers (4)

Divakar
Divakar

Reputation: 221534

It seems, basically you are finding local minima in a sliding window, but that sliding window slides in such a manner that the ending of the previous window act as the starting of a new window. For such a specific problem, suggested in this solution is a vectorized approach that uses broadcasting -

import numpy as np

# Inputs
N = 2
samples = [ 5, 12.3, 12.3, 7, 2, 6, 9, 10, 5, 9, 17, 2 ]

# Convert input list to a numpy array
S = np.asarray(samples)

# Calculate the number of Infs to be appended at the end
append_endlen = int(2*N*np.ceil((S.size+1)/(2*N))-1 - S.size)

# Append Infs at the start and end of the input array
S1 = np.concatenate((np.repeat(np.Inf,N),S,np.repeat(np.Inf,append_endlen)),0)

# Number of sliding windows
num_windows = int((S1.size-1)/(2*N))

# Get windowed values from input array into rows. 
# Thus, get minimum from each row to get the desired local minimum.
indexed_vals = S1[np.arange(num_windows)[:,None]*2*N + np.arange(2*N+1)]
out = indexed_vals.min(1)

Sample runs

Run # 1: Original input data

In [105]: S     # Input array
Out[105]: 
array([  5. ,  12.3,  12.3,   7. ,   2. ,   6. ,   9. ,  10. ,   5. ,
         9. ,  17. ,   2. ])

In [106]: N   # Window radius
Out[106]: 2

In [107]: out  # Output array
Out[107]: array([ 5.,  2.,  5.,  2.])

Run # 2: Modified input data, Window radius = 2

In [101]: S     # Input array
Out[101]: 
array([  5. ,  12.3,  12.3,   7. ,   2. ,   6. ,   9. ,  10. ,   5. ,
         9. ,  17. ,   2. ,   0. ,  -3. ,   7. ,  99. ,   1. ,   0. ,
        -4. ,  -2. ])

In [102]: N   # Window radius
Out[102]: 2

In [103]: out  # Output array
Out[103]: array([ 5.,  2.,  5., -3., -4., -4.])

Run # 3: Modified input data, Window radius = 3

In [97]: S    # Input array
Out[97]: 
array([  5. ,  12.3,  12.3,   7. ,   2. ,   6. ,   9. ,  10. ,   5. ,
         9. ,  17. ,   2. ,   0. ,  -3. ,   7. ,  99. ,   1. ,   0. ,
        -4. ,  -2. ])

In [98]: N   # Window radius
Out[98]: 3

In [99]: out  # Output array
Out[99]: array([ 5.,  2., -3., -4.])

Upvotes: 2

Imanol Luengo
Imanol Luengo

Reputation: 15889

Use scipy's argrelextrema:

>>> import numpy as np
>>> from scipy.signal import argrelextrema
>>> data = np.array([ 5, 12.3, 12.3, 7, 2, 6, 9, 10, 5, 9, 17, 2 ])
>>> radius = 2 # number of elements to the left and right to compare to
>>> argrelextrema(data, np.less, order=radius)
(array([4, 8]),)

Which suggest that numbers at position 4 and 8 (2 and 5) are the smallest ones in within a 2 size neighbourhood. The numbers at boundaries (5 and 2) are not detected since argrelextrema only supports clip or wrap boundary conditions. As for your question, I guess you are interested in them too. To detect them, it is easy to add reflect boundary conditions first:

>>> new_data = np.pad(data, radius, mode='reflect')
>>> new_data
array([ 12.3,  12.3,   5. ,  12.3,  12.3,   7. ,   2. ,   6. ,   9. ,
        10. ,   5. ,   9. ,  17. ,   2. ,  17. ,   9. ])

With the data with the corresponding boundary conditions, we can now apply the previus extrema detector:

>>> arg_minimas = argrelextrema(new_data, np.less, order=radius)[0] - radius
>>> arg_minimas
array([ 0,  4,  8, 11])

Which returns the positions where the local extrema (minimum in this case since np.less) happens in a sliding window of radius=2.

NOTE the -radius to fix the +radius index after wrapping the array with reflect boundary conditions with np.pad.

EDIT: if you are insterested in the values and not in positions, it is straight forward:

>>>  data[arg_minimas]
array([ 5.,  2.,  5.,  2.])

Upvotes: 11

leekaiinthesky
leekaiinthesky

Reputation: 5593

This will look through each window, find the minimum value, and add it to a list if the window's minimum value isn't equal to the most recently added value.

samples = [5, 12.3, 12.3, 7, 2, 6, 9, 10, 5, 9, 17, 2]
neighborhood = 2

minima = []
for i in xrange(len(samples)):
  window = samples[max(0, i - neighborhood):i + neighborhood + 1]
  windowMin = min(window)
  if minima == [] or windowMin != minima[-1]:
    minima.append(windowMin)

This gives the output you described:

print minima
> [5, 2, 5, 2]

However, @imaluengo's answer is better since it will include both of two consecutive equal minimum values if they have different indices in the original list!

Upvotes: 1

simleo
simleo

Reputation: 2965

>>> import numpy as np
>>> a = np.array(samples)
>>> [a[max(i-2,0):i+2].min() for i in xrange(1, a.size)]
[5.0, 2.0, 2.0, 2.0, 2.0, 5.0, 5.0, 5.0, 2.0]

As Divakar pointed out in the comments, this is what a sliding window yields. If you want to remove duplicates, that can be done separately

Upvotes: 1

Related Questions