How to find all pairs of neighboring values in matrix?
<p>For an image represented as a matrix, what is an efficient way to find all unique pairs of elements that touch within a 3x3 square?</p>

<pre><code>Let A=
    1 1 2 2 3 3 3
    1 1 1 1 2 4 4
    1 1 2 2 5 5 5
</code></pre>

<p>Then we would return</p>

<pre><code>(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5)
</code></pre>

<p>Here is some partially-hardcoded easy-to-understand-approach.</p>

<ul>
<li><strong>Edit:</strong> faster version due to preprocessing</li>
<li><strong>Edit 2:</strong> one more final speedup (symmetry-reduction in preprocessing)</li>
<li><strong>Edit 3:</strong> okay; added one more symmetry-reduction step in preprocessing</li>
</ul>

<h3>Approach</h3>

<ul>
<li>get a block-view by skimage</li>
<li>preprocess the neighborhood-logic once:

<ul>
<li>create a list of all indices to look up pairs (which are connected) in the given window</li>
<li>some symmetry-reduction used</li>
</ul></li>
<li>iterate all blocks; grab pairs

<ul>
<li>add if some symmetry-constraint is true</li>
</ul></li>
</ul>

<h3>Code</h3>

<pre><code>import numpy as np
from skimage.util.shape import view_as_blocks, view_as_windows

img = np.array([[1,1,2,2,3,3,3],
                [1,1,1,1,2,4,4],
                [1,1,2,2,5,5,5]])
#img = np.random.random_integers(1, 10, size=(256,256))

WINDOW_SIZE = 3
img_windowed = view_as_windows(img, window_shape=(WINDOW_SIZE,WINDOW_SIZE))  # overlapping

# Preprocessing: generate valid index_pairs
index_pairs = []
for x in range(WINDOW_SIZE):
    for y in range(WINDOW_SIZE):
        if y&gt;=x:  # remove symmetries
            if x&gt;0:
                index_pairs.append(((x,y), (x-1,y)))
            if x&lt;2:
                index_pairs.append(((x,y), (x+1,y)))
            if y&gt;0:
                index_pairs.append(((x,y), (x,y-1)))
            if y&lt;2:
                index_pairs.append(((x,y), (x,y+1)))
            if x&gt;0 and y&gt;0:
                index_pairs.append(((x,y), (x-1,y-1)))
            if x&lt;2 and y&lt;2:
                index_pairs.append(((x,y), (x+1,y+1)))
            if x&gt;0 and y&lt;2:
                index_pairs.append(((x,y), (x-1,y+1)))
            if x&lt;2 and y&gt;0:
                index_pairs.append(((x,y), (x+1,y-1)))

index_pairs = list(filter(lambda x: x[0] &lt; x[1], index_pairs))  # remove symmetries

pairs = []
def reason_pair(a,b):  # remove symmetries
    if a&lt;b:
        pairs.append((a,b))
    elif a&gt;b:
        pairs.append((b,a))

for a in range(img_windowed.shape[0]):
    for b in range(img_windowed.shape[1]):
        block = img_windowed[a,b]
        for i in index_pairs:
            reason_pair(block[i[0]], block[i[1]])

print(set(pairs))
</code></pre>

<h3>Output</h3>

<pre><code>set([(1, 2), (1, 3), (4, 5), (1, 5), (2, 3), (2, 5), (3, 4), (2, 4)])
</code></pre>

python image-processing matrix