Creating a network undirected weighted graph from a binary image for a minimum spanning tree

Question

I'm trying to create a minimum spanning tree between pixels in a thresholded image of a crack. The pixels do not always touch when I remove noise so I am trying to connect them in a graph.

Python 2.7 I have thresholded an image so everything that is below a threshold shows up white, all else is black. I thresholded a 65x65 window at a time and set any window with less than 10 pixels to white.

import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import numpy as np
import Image
import matplotlib
from cv2 import *

img=imread("IMG_1188.jpg")
gray = cvtColor(img, COLOR_BGR2GRAY)

threshold=35

width,height = gray.shape

for j in range( 0, height,65 ):
    for i in range( 0, width,65 ):

    gray[i:i+65,j:j+65]=inRange(gray[i:i+65,j:j+65],np.array([0]), np.array([35]))

    if np.sum(gray[i:i+65,j:j+65])<(2550):

        gray[i:i+65,j:j+65]=[0]

I created a dict to hold all the x,y pos of the white pixels and created nodes in networkx.

pos={}
k=int(0)
G =nx.Graph()
for j in range( 0, height):
    for i in range( 0, width):
        if np.array(gray[i,j])>np.array(0):
            gray[i,j]=255
            pos[k]=(int(i),int(j))
            G.add_node(pos[k])          
            k=k+1

I then checked every euclidean distance between each node and draw an edge if it is below a certain pixel distance (say 40).

k=1
for j in range (0,pos.len()):

    for i in range (k,pos.len()):   

        if np.sqrt(np.square(pos[i][0]-pos[j][0])+np.square(pos[i][1]-pos[j][1]))<=40:  
            G.add_edge(pos[i],pos[j],weight=(np.sqrt(np.square(pos[i][0]-pos[j][0])+np.square(pos[i][1]-pos[j][1]))))

    k=k+1

When I run the program it tells me there is no position for the node. (I've run it with different parameters and received different error nodes)

networkx.exception.NetworkXError: Node (814, 700) has no position.

Any help would be appreciated.

Answer 1

The issue was I was referencing the x position of the nodes that were within 40 as the start of the edge

G.add_edge(pos[i],pos[j],weight=(np.sqrt(np.square(pos[i][0]-pos[j][0])+np.square(pos[i][1]-pos[j][1]))))

Instead I needed to reference the actual node identifier (I also used absolute value since it is one operation vs the squaring and square root)

G.add_edge(i,j,weight=(np.fabs(window1[i][0]-window1[j][0])+np.fabs(window1[i][1]-window1[j][1])))

Also I have found that I should use a K-D tree to speed up my code, as this code for 15000 points took 50 min or so.