Sort array of points in numpy

numpy argsort
numpy sort
numpy 2d array sort descending
numpy lexsort
numpy argsort descending
numpy sort multiple columns
sort numpy array alphabetically
sort numpy array example

I got an array of points declared like this:

found = np.empty(img_rgb.shape[:2])

It represents values from OpenCV template matching. As I kept only the points that had desired values from the matching, I've rewritten it before iterating:

found2 = np.where(found)

Now I iterate through it like this:

for pt in zip(*found2[::-1]):
    (x, y) = pt

But how do I sort it so it would iterate from the lowest to highest value in found[x][y] array?

I tried np.argsort() but doesn't seem to keep a proper x,y indexes. In fact it doesn't sort by values at all I guess.

EDIT: To be clear:

img_rgb = cv2.imread(os.path.join(DATA_DIR, 'some.png'))

(...)

res = cv2.matchTemplate(img_gray, tmpl, cv2.TM_CCOEFF)
loc = np.where(res > 230000)
for pt in zip(*loc[::-1]):
   (x, y) = pt
   found[y][x] = -res[y][x]

Not sure I understand you correctly, but do you want something like:

found = np.random.randint(0, 10, (3, 4))
found2 = np.where(found)
found
# array([[5, 6, 8, 6],
#        [0, 7, 7, 3],
#        [7, 6, 0, 5]])
found2
# (array([0, 0, 0, 0, 1, 1, 1, 2, 2, 2]), array([0, 1, 2, 3, 1, 2, 3, 0, 1, 3]))

order = found[found2].argsort()
x, y = found2[1][order], found2[0][order]
found[y, x]
# array([3, 5, 5, 6, 6, 6, 7, 7, 7, 8])

This sorts the 2d indices in found2 by the values at the points in found they reference.

numpy.sort — NumPy v1.19 Manual, numpy.sort�. numpy. sort (a, axis=-1, kind=None, order=None)[source]�. Return a sorted copy of an array. Parameters. aarray_like. Array to be� The numpy.argsort() function performs an indirect sort on input array, along the given axis and using a specified kind of sort to return the array of indices of data. This indices array is used to construct the sorted array.

res = cv2.matchTemplate(img_gray, tmpl, cv2.TM_CCOEFF)
count = np.sum(res > 230000)
y, x = np.unravel_index((-res).argsort(None), res.shape)
for row, col in zip(y[:count], x[:count]):
    print(res[row, col], (row, col))

Explanation for each line:

count = np.sum(res > 230000)

gets the total number of values you want to iterate over.

y, x = np.unravel_index((-res).argsort(None), res.shape)

Here, argsort(None) will return the linear indices into the array which sorts it. We want the (row, column) indices though, not linear ones, so we use np.unravel_index() to get 2d indices out. Using the negative of the result to sort from max to min, like you did in the OP.

Then finally, we can iterate through the points:

for row, col in zip(y[:count], x[:count]):
    print(res[row, col], (row, col))

Printing is just to show indeed we are getting the highest values first, and showing the (row, column) index for those corresponding values.


Example:

>>> import cv2
>>> import numpy as np
>>> img = np.uint8(255*np.random.rand(100, 100))
>>> tmp = np.uint8(255*np.random.rand(10, 10))
>>> res = cv2.matchTemplate(img, tmp, cv2.TM_CCOEFF)
>>> count = np.sum(res > 100000)
>>> y, x = np.unravel_index((-res).argsort(None), res.shape)
>>> for row, col in zip(y[:count], x[:count]):
>>>     print(res[row, col], (row, col))
206337.11 (19, 12)
177079.31 (76, 9)
173258.67 (63, 15)
...
100202.44 (56, 1)
100098.41 (0, 48)
100089.09 (68, 47)

Note that these final values are in (row, column) order, that is, opposite from (x, y) point order, so feel free to swap as needed.

numpy.argsort — NumPy v1.19 Manual, Perform an indirect sort along the given axis using the algorithm specified by the kind keyword. It returns an array of indices of the same shape as a that index data along the given axis in sorted order. Array to sort. Axis along which to sort. numpy.sort¶ numpy.sort (a, axis=-1, kind=None, order=None) [source] ¶ Return a sorted copy of an array. Parameters a array_like. Array to be sorted. axis int or None, optional. Axis along which to sort. If None, the array is flattened before sorting. The default is -1, which sorts along the last axis.

Solution:

sorted_pts = sorted(zip(*loc), key=lambda t:res[t])
print (sorted_pts)

Try it out with sample data:

Let's take some sample data on a smaller scale (taking res as just a shape (3,4) array, and 4 as the threshold):

import numpy as np

res = np.arange(12).reshape(3,4)
print (res)

loc = np.where(res > 4)  # Dummy threshold == 4

sorted_pts = sorted(zip(*loc), key=lambda t:res[t[0],t[1]])
print (sorted_pts)

Output:

[[ 0  1  2  3]   # res
 [ 4  5  6  7]
 [ 8  9 10 11]]
# sorted_pts
[(1, 1), (2, 1), (3, 1), (0, 2), (1, 2), (2, 2), (3, 2)]

Note: (Verifying that the points are sorted according to the values in res)

[(1, 1), (2, 1), (3, 1), (0, 2), (1, 2), (2, 2), (3, 2)]
   |       |       |        |       |       |       |
   |       |       |        |       |       |       |
   V       V       V        V       V       V       V
   5       6       7        8       9       10      11

Sorting Arrays, Sorting Arrays. import numpy as np def selection_sort(x): for i in range(len(x)): swap = i + np. argmin(x[i:]) (x[i], x[swap]) = (x[swap], x[i]) return x. x = np. array([2, 1, 4, 3, 5]) selection_sort(x) def bogosort(x): while np. any(x[:-1] > x[1:]): np. x = np. array([2, 1, 4, 3, 5]) bogosort(x) x = np. x. x = np. x[ a: array_like. Array to be sorted. axis: int or None, optional. Axis along which to sort. If None, the array is flattened before sorting. The default is -1, which sorts along the last axis. kind: {‘quicksort’, ‘mergesort’, ‘heapsort’, ‘stable’}, optional. Sorting algorithm. Default is ‘quicksort’. order: str or list of str

NumPy - Sort, Search & Counting Functions, sort(). The sort() function returns a sorted copy of the input array. It has the following parameters − numpy.sort(a, axis,� I have a 2D numpy array of shape (N,2) which is holding N points (x and y coordinates). For example: array([[3, 2], [6, 2], [3, 6], [3, 4], [5, 3]]) I'd like to sort i

https://docs.scipy.org/doc/numpy-1.15.1/reference/, In this article we will discuss how to sort a 2D Numpy array by single or multiple rows or columns. Sorting 2D Numpy Array by a column. Syntax: numpy.sort(a, axis=-1, kind=’quicksort’, order=None) This function return a sorted copy of an array. Parameters: a : array_like Array to be sorted. axis : int or None, optional Axis along which to sort. If None, the array is flattened before sorting. The default is -1, which sorts along the last axis.

Sorting 2D Numpy Array by column or row in Python – thispointer.com, Up to this point we have been concerned mainly with tools to access and operate on array data with NumPy. This section covers algorithms related to sorting� numpy.searchsorted¶ numpy.searchsorted (a, v, side='left', sorter=None) [source] ¶ Find indices where elements should be inserted to maintain order. Find the indices into a sorted array a such that, if the corresponding elements in v were inserted before the indices, the order of a would be preserved.

Comments
  • What are you actually trying to do? np.where() does sort the elements, by row, then column. So, I'm not sure what the goal here is. Edit: ah, wait so you want to order by the template matching image values. Is that correct? My original question still stands on why you'd want to do this as this seems extremely slow for no reason. Do you actually need every pixel? Or just some subset?
  • That doesn't seem to work slow. I need a subset of found values greater than threshold. Then sort them by value. Then iterate through it. I'm not really the best in Python :(
  • (a)Is found a 2d array of bools ? (b) By found[x][y], do you actually mean found[x,y]? (c) What do you mean by "lowest to highest value in found[x][y], especially if found has only bools?
  • found[x][y] has value, that can be a bigint, from cv2.matchTemplate()
  • Your "EDIT to be clear" seems to make it even less clear. It introduces loc, and your statement of requirement doesn't mention loc at all
  • I edited my question to point out what is found, I still need the iteration code, as I iterate through found2, not found, but maybe I understand it wrong
  • @FlashThunder (y, x) is the same as found2 only reordered. You can assign it back found2 = y, x and use your loop unchanged.
  • @FlashThunder Sorry, I don't understand the question. Once you have defined found2 in your code you insert the line starting with order = and the next line and the line I wrote in my last comment found2 = y, x and that should be all you need to do.
  • thanx! that explained a lot
  • sorry for not accepting that, but I can't accept two answers, was a nice answer tho'! thank you!