Finding the Position of the Minimum Neighbor for Each Element in a Large Matrix

I have a large matrix ($6020\times 8452$), and I want to create a new matrix where the relative position of the minimum neighbor is each element in the matrix. For example, if I had the matrix

$\begin{bmatrix} 1 & 2 & 3\\2 & 3 & 4\\3 & 4 & 5\end{bmatrix}$,

I want the program to return

$\begin{bmatrix} 9 & 4 & 4\\2 & 1 & 1\\2 & 1 & 1\end{bmatrix}$.

To explain, $9$ represents that the specific element is the minimum of all its neighbors; $4$ represents that the neighbor directly West of the specified element is the minimum of all neighbors; $2$ represents that the neighbor directly North of the specified element is the minimum of all neighbors; and $1$ represents that the neighbor directly Northwest of the specified element is the minimum of all neighbors. The numbering scheme is not an important aspect of the problem, I just used this scheme in order to make the question more understandable.

My problem is that the program I made takes too long to be a reasonable way to work with my matrix. Is there some way to speed up this program a significant amount?

Also, a few quick notes about the matrix. The matrix is about half zeros, so I am using a SparseArray. Moreover, the maximum value of the whole matrix is approximately $397$. The minimum value is approximately $237$.

matrix = ArrayPad[dataSet, 1, 500.];

Table[Position[{matrix[[i - 1]][[j - 1]], matrix[[i - 1]][[j]],
matrix[[i - 1]][[j + 1]], matrix[[i]][[j - 1]],
matrix[[i]][[j + 1]], matrix[[i + 1]][[j - 1]],
matrix[[i + 1]][[j]], matrix[[i + 1]][[j + 1]], matrix[[i]][[j]]},
Min[{matrix[[i - 1]][[j - 1]], matrix[[i - 1]][[j]],
matrix[[i - 1]][[j + 1]], matrix[[i]][[j - 1]],
matrix[[i]][[j + 1]], matrix[[i + 1]][[j - 1]],
matrix[[i + 1]][[j]], matrix[[i + 1]][[j + 1]],
matrix[[i]][[j]]}]], {i, 2, Length[matrix] - 1}, {j, 2,
Length[matrix[[1]]] - 1}]


Thanks!

• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – user9660 Jan 12 '15 at 7:00
• I'm not sure if it's a speed up, but a way to access each element only once instead of twice would be Ordering[{(*list the 9 neighbourhood elements here*)}][[1]]. – Martin Ender Jan 12 '15 at 8:04

Following up on Martin Büttner's comment this is perhaps best handled using Ordering. We can apply it to subarrays produced by Partition, though we will need to Flatten them first. I shall further use PartitionMap to improve memory performance.

A starting array:

SeedRandom[0]
a = RandomInteger[9, {4, 6}];
a // MatrixForm


$\left( \begin{array}{cccccc} 7 & 0 & 8 & 2 & 1 & 5 \\ 8 & 0 & 6 & 7 & 2 & 1 \\ 0 & 6 & 1 & 2 & 8 & 6 \\ 5 & 5 & 8 & 4 & 5 & 9 \\ \end{array} \right)$

The process:

<< Developer

PartitionMap[Ordering[Flatten@#, 1][[1]] &, a, {3, 3}, 1, 2, 99]


$\left( \begin{array}{cccccc} 6 & 5 & 4 & 6 & 5 & 4 \\ 3 & 2 & 1 & 3 & 2 & 1 \\ 3 & 2 & 1 & 4 & 3 & 2 \\ 2 & 1 & 2 & 1 & 1 & 4 \\ \end{array} \right)$

The numbers correspond to placement within:

Partition[Range@9, 3]


$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{array} \right)$

Notes:

• The padding element, 99 in the example above, must never be the minimum.
• In cases with multiple minimum values the position of the first is used.

If it is vital that the central position always have priority over the neighbors with regard to the minimum value we can simply reorder the elements before Ordering is applied. This changes the meaning of the numbers in the result but since that is arbitrary already it should not matter.

PartitionMap[
Ordering[Flatten[#] ~RotateLeft~ 4, 1][[1]] &,
a, {3, 3}, 1, 2, 99
]


$\left( \begin{array}{cccccc} 2 & 1 & 3 & 2 & 1 & 4 \\ 2 & 1 & 6 & 3 & 2 & 1 \\ 1 & 7 & 6 & 9 & 8 & 7 \\ 7 & 6 & 7 & 6 & 6 & 9 \\ \end{array} \right)$

The numbering now corresponds to:

$\left( \begin{array}{ccc} 6 & 7 & 8 \\ 9 & 1 & 2 \\ 3 & 4 & 5 \\ \end{array} \right)$

Here is a direct implementation using MapIndexed.

map = {{1, 1} -> "NW", {1, 2} -> "N", {1, 3} -> "NE", {2, 1} -> "W",
{2, 2} -> "0", {1, 3} -> "E",{3, 1} -> "SW", {3, 2} -> "S", {3, 3} -> "SE"};
mat = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}};
mat0 = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}};
f[{ii_, jj_}] := Module[{i = ii + 1, j = jj + 1, m},
m = mat[[i - 1 ;; i + 1, j - 1 ;; j + 1]];
First@Position[m, Min[m], {2}] /. map
]
MapIndexed[f[#2] &, mat0, {2}] // MatrixForm


To use numbers instead of NW,SW,etc.... change the map to

map = {{1, 1} -> 1, {1, 2} -> 2, {1, 3} -> 1, {2, 1} -> 4,
{2, 2} -> 9, {1, 3} -> 2,{3, 1} -> 1, {3, 2} -> 2, {3, 3} -> 1};
`

You did not give numbers to all locations, so I made up ones.