[SOLVED] Finding the optimal location in 2D array

Issue

I’m working with 2D numpy arrays of equal size in terms of the number of rows and columns. I would like to find the optimal location where 2n + 1 on each side would result in highest possible sum. 2(n) + 1 here means the the neghbouring elements.

So the 2D array:

[[0 0 0 0 0]
 [0 1 1 1 0]
 [0 1 1 1 0]
 [0 1 1 1 0]
 [0 0 0 0 0]]

In this array, the element at (2, 2) appears to be the optimal location at 2(1) + 1.
So, at, n = 2 the ideal location would be same. However, at n = 3, it would be none, because that would exceed the 2D array matices.

This is my approach to the problem, which is not giving the desired output.

def find_target_location(arr, area):
    sum_1 = 0
    sum_2 = sum_1
    square_area = (2 * area) + 1

    if square_area > len(arr):
        return None

    for row in range(len(arr)):
        for index in range(len(arr[row])):
            area_forward = arr[row: square_area + row, index: square_area + index]
            # This is where I am doing wrong but cannot figure out.
            area_previous = arr[row - len(arr): -row -1, row - len(arr), -index -1]

            sum_area_forward = sum(sum(area_forward))
            sum_area_backward = sum(sum(area_backward))
            sum_2 = sum_area_forward + sum_area_backward
            if sum_2 > sum_1:
                sum_1 = sum_2
                optimal_location = (row, index)
    return optimal_location

Solution

Sum of immediate neighbors

If you’re looking for the index of the element with the largest sum of immediately adjacent neighbor values:

from numpy.lib.stride_tricks import sliding_window_view as windows

np.unravel_index(np.pad(windows(x, (3, 3)).sum(axis=(2, 3)), 1).argmax(), x.shape)

Note however that this solution counts the value of an element itself when calculating the sum of its neighboring values.

Sum of neighbors in 2n+1 square neighborhood

So you want to sum all neighbors in a 2n+1 "radius" neighborhood:

n = 1
radius = 2*n + 1

# x = np.array(...)
neighbor_sums = windows(x, (radius, radius)).sum(axis=(2, 3))
padded = np.pad(neighbor_sums, radius // 2)

optimal_location = np.unravel_index(padded.argmax(), padded.shape)

I’ve only sort of tested this, but I think it should work. Note here that the first index of the max value will be chosen, so if you have more than one "optimal" location, you’ll always end up with the "first" one that occurs (when searching from top-left to bottom-right).

I don’t think padding is strictly necessary but it does let you avoid having to do some tedious arithmetic, and also helps if you want to not count the value of each cell when summing the neighboring values, like so:

padded -= x
adjusted_neighbor_sums = np.clip(padded, 0, padded.max())

optimal_location # = same as above

How to do it without stride_tricks

At the end of the day, np.lib.stride_tricks.sliding_window_view is just clever indexing.

Let x be this (5, 5) array:

array([[0, 0, 0, 0, 0],
       [0, 1, 2, 3, 0],
       [0, 4, 5, 6, 0],
       [0, 7, 8, 9, 0],
       [0, 0, 0, 0, 0]])

And suppose n = 1, so the area of your neighborhood is 2n+1 = 3. Now imagine placing a (3, 3) "window" over x, matching the top-left corner of the window with the top-left corner of x. That "window" is surrounding the values

0 0 0
0 1 2
0 4 5

What are the column indices of those values? They are (0, 1, 2).

Now, if we’re sliding a (3, 3) window across x, we can’t move the window such that it hangs over any side of x. So the furthest right we could move this window across the top of x would be such that the top-left corner of the window is at index 2. That way, the top-right corner of the window lines up with the top-right corner of x. That window is now surrounding the values

0 0 0
2 3 0
5 6 0

What are the column indices of those values? They are (2, 3, 4).

Let’s create a list of tuples which can represent the columns selected as we slide across the top of x:

n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))

Output:

>>> idxs
[(0, 1, 2), (1, 2, 3), (2, 3, 4)]

Since x is square, these column indexes will also work for the rows for when we want to slide the window down one row (imagine sliding the window across x the same way you read a page of a book written in English — left to right, top to bottom).

If you take the Cartesian product of idxs, this will give you the row and column indices of all 9 windows:

>>> [(rows, cols) for rows in idxs for cols in idxs]
[((0, 1, 2), (0, 1, 2)),
 ((0, 1, 2), (1, 2, 3)),
 ((0, 1, 2), (2, 3, 4)),
 ((1, 2, 3), (0, 1, 2)),
 ((1, 2, 3), (1, 2, 3)),
 ((1, 2, 3), (2, 3, 4)),
 ((2, 3, 4), (0, 1, 2)),
 ((2, 3, 4), (1, 2, 3)),
 ((2, 3, 4), (2, 3, 4))]

Now, one last thing: for each tuple of (rows, cols), we need to take the Cartesian product again to get all 9 index pairs for each (3, 3) window. For instance, the 9 indices of the (3, 3) window anchored at the top left of x where we start are

[[(0, 0), (0, 1), (0, 2)],
 [(1, 0), (1, 1), (1, 2)],
 [(2, 0), (2, 1), (2, 2)]]

Using those tuples to index into x:

>>> [[x[i, j] for i in (0, 1, 2)] for j in (0, 1, 2)]
[[0, 0, 0],
 [0, 1, 4],
 [0, 2, 5]]

Now we could wrap the above in another two nested list comprehensions to iterate over the (rows, cols) tuples:

>>> np.array([[[[x[i, j] for j in cols] for i in rows] for cols in idxs] for rows in idxs])
array([[[[0, 0, 0],
         [0, 1, 2],
         [0, 4, 5]],

        [[0, 0, 0],
         [1, 2, 3],
         [4, 5, 6]],

        [[0, 0, 0],
         [2, 3, 0],
         [5, 6, 0]]],


       [[[0, 1, 2],
         [0, 4, 5],
         [0, 7, 8]],

        [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]],

        [[2, 3, 0],
         [5, 6, 0],
         [8, 9, 0]]],


       [[[0, 4, 5],
         [0, 7, 8],
         [0, 0, 0]],

        [[4, 5, 6],
         [7, 8, 9],
         [0, 0, 0]],

        [[5, 6, 0],
         [8, 9, 0],
         [0, 0, 0]]]])

This produces the (3, 3, 3, 3) array over which you can then sum the last two axes.

But that comprehension is awful. Fortunately, the np.ix_() function makes it incredibly easy to get these Cartesian products in a form suitable for advanced indexing:

>>> np.ix_((0, 1, 2), (0, 1, 2))
(array([[0],
        [1],
        [2]]),
 array([[0, 1, 2]]))

Now getting our windows is much easier (together with the setup data):

n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))

# all (3, 3) windows of x
np.array([[x[np.ix_(rows, cols)] for cols in idxs] for rows in idxs])

Which produces the same result as above. From there, you can apply the sum over the last two axes (the rows and columns of each individual 2D array).

Of course, that’s still an awful looking comprehension… and np.lib.stride_tricks.sliding_window_view abstracts away all that indexing nonsense.

Answered By – ddejohn

Answer Checked By – Willingham (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *