Edge detection for image stored in matrix

Question

I represent images in the form of 2-D arrays. I have this picture:

How can I get the pixels that are directly on the boundaries of the gray region and colorize them?

I want to get the coordinates of the matrix elements in green and red separately. I have only white, black and gray regions on the matrix.

Answer 1

There is a very simple solution to this: by definition any pixel which has both white and gray neighbors is on your "red" edge, and gray and black neighbors is on the "green" edge. The lightest/darkest neighbors are returned by the maximum/minimum filters in skimage.filters.rank, and a binary combination of masks of pixels that have a lightest/darkest neighbor which is white/gray or gray/black respectively produce the edges.

Result:

A worked solution:

import numpy
import skimage.filters.rank
import skimage.morphology
import skimage.io

# convert image to a uint8 image which only has 0, 128 and 255 values
# the source png image provided has other levels in it so it needs to be thresholded - adjust the thresholding method for your data
img_raw = skimage.io.imread('jBD9j.png', as_grey=True)
img = numpy.zeros_like(img, dtype=numpy.uint8)
img[:,:] = 128
img[ img_raw < 0.25 ] = 0
img[ img_raw > 0.75 ] = 255

# define "next to" - this may be a square, diamond, etc
selem = skimage.morphology.disk(1)

# create masks for the two kinds of edges
black_gray_edges = (skimage.filters.rank.minimum(img, selem) == 0) & (skimage.filters.rank.maximum(img, selem) == 128)
gray_white_edges = (skimage.filters.rank.minimum(img, selem) == 128) & (skimage.filters.rank.maximum(img, selem) == 255)

# create a color image
img_result = numpy.dstack( [img,img,img] )

# assign colors to edge masks
img_result[ black_gray_edges, : ] = numpy.asarray( [ 0, 255, 0 ] )
img_result[ gray_white_edges, : ] = numpy.asarray( [ 255, 0, 0 ] )

imshow(img_result)

P.S. Pixels which have black and white neighbors, or all three colors neighbors, are in an undefined category. The code above doesn't color those. You need to figure out how you want the output to be colored in those cases; but it is easy to extend the approach above to produce another mask or two for that.

P.S. The edges are two pixels wide. There is no getting around that without more information: the edges are between two areas, and you haven't defined which one of the two areas you want them to overlap in each case, so the only symmetrical solution is to overlap both areas by one pixel.

P.S. This counts the pixel itself as its own neighbor. An isolated white or black pixel on gray, or vice versa, will be considered as an edge (as well as all the pixels around it).

Answer 2

Basically by follow pyStarter's suggestion of using the marching square algorithm from scikit-image, the desired could contours can be extracted with the following code:

import matplotlib.pyplot as plt
import numpy as np
import scipy as sp
from skimage import measure
import scipy.ndimage as ndimage
from skimage.color import rgb2gray
from pprint import pprint
#Load image
im = rgb2gray(sp.misc.imread('jBD9j.png'))

n, bins_edges = np.histogram(im.flatten(),bins = 100)
# Skip the black area, and assume two distinct regions, white and grey
max_counts = np.sort(n[bins_edges[0:-1] > 0])[-2:]
thresholds = np.select(
    [max_counts[i] == n for i in range(max_counts.shape[0])],
    [bins_edges[0:-1]] * max_counts.shape[0]
)
# filter our the non zero values
thresholds = thresholds[thresholds > 0] 


fig, axs = plt.subplots()
# Display image
axs.imshow(im, interpolation='nearest', cmap=plt.cm.gray)
colors = ['r','g']
for i, threshold in enumerate(thresholds):
    contours = measure.find_contours(im, threshold)

    # Display  all contours found for this threshold
    for n, contour in enumerate(contours):
        axs.plot(contour[:,1], contour[:,0],colors[i], lw = 4)

axs.axis('image')
axs.set_xticks([])
axs.set_yticks([])        
plt.show()

!

However, from your image there is no clear defined gray region, so I took the two largest counts of intensities in the image and thresholded on these. A bit disturbing is the red region in the middle of the white region, however I think this could be tweaked with the number of bins in the histogram procedure. You could also set these manually as Ed Smith did.

Answer 3

The following should hopefully be okay for your needs (or at least help). The idea is to split into the various regions using logical checks based on threshold values. The edge between these regions can then be detected using numpy roll to shift pixels in x and y and comparing to see if we are at an edge,

import matplotlib.pyplot as plt
import numpy as np
import scipy as sp
from skimage.morphology import closing

thresh1 = 127
thresh2 = 254

#Load image
im = sp.misc.imread('jBD9j.png')

#Get threashold mask for different regions
gryim = np.mean(im[:,:,0:2],2)
region1 =  (thresh1<gryim)
region2 =  (thresh2<gryim)
nregion1 = ~ region1
nregion2 = ~ region2

#Plot figure and two regions
fig, axs = plt.subplots(2,2)
axs[0,0].imshow(im)
axs[0,1].imshow(region1)
axs[1,0].imshow(region2)

#Clean up any holes, etc (not needed for simple figures here)
#region1 = sp.ndimage.morphology.binary_closing(region1)
#region1 = sp.ndimage.morphology.binary_fill_holes(region1)
#region1.astype('bool')
#region2 = sp.ndimage.morphology.binary_closing(region2)
#region2 = sp.ndimage.morphology.binary_fill_holes(region2)
#region2.astype('bool')

#Get location of edge by comparing array to it's 
#inverse shifted by a few pixels
shift = -2
edgex1 = (region1 ^ np.roll(nregion1,shift=shift,axis=0))
edgey1 = (region1 ^ np.roll(nregion1,shift=shift,axis=1))
edgex2 = (region2 ^ np.roll(nregion2,shift=shift,axis=0)) 
edgey2 = (region2 ^ np.roll(nregion2,shift=shift,axis=1))

#Plot location of edge over image
axs[1,1].imshow(im)
axs[1,1].contour(edgex1,2,colors='r',lw=2.)
axs[1,1].contour(edgey1,2,colors='r',lw=2.)
axs[1,1].contour(edgex2,2,colors='g',lw=2.)
axs[1,1].contour(edgey2,2,colors='g',lw=2.)
plt.show()

Which gives the . For simplicity I've use roll with the inverse of each region. You could roll each successive region onto the next to detect edges

Thank you to @Kabyle for offering a reward, this is a problem that I spent a while looking for a solution to. I tried scipy skeletonize, feature.canny, topology module and openCV with limited success... This way was the most robust for my case (droplet interface tracking). Hope it helps!

Answer 4

While plonser's answer may be rather straight forward to implement, I see it failing when it comes to sharp and thin edges. Nevertheless, I suggest you use part of his approach as preconditioning.
In a second step you want to use the Marching Squares Algorithm. According to the documentation of scikit-image, it is

a special case of the marching cubes algorithm (Lorensen, William and Harvey E. Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics (SIGGRAPH 87 Proceedings) 21(4) July 1987, p. 163-170

There even exists a Python implementation as part of the scikit-image package. I have been using this algorithm (my own Fortran implementation, though) successfully for edge detection of eye diagrams in communications engineering.

Ad 1: Preconditioning
Create a copy of your image and make it two color only, e.g. black/white. The coordinates remain the same, but you make sure that the algorithm can properly make a yes/no-decision independent from the values that you use in your matrix representation of the image.

Ad 2: Edge Detection
Wikipedia as well as various blogs provide you with a pretty elaborate description of the algorithm in various languages, so I will not go into it's details. However, let me give you some practical advice:

1. Your image has open boundaries at the bottom. Instead of modifying the algorithm, you can artifically add another row of pixels (black or grey to bound the white/grey areas).
2. The choice of the starting point is critical. If there are not too many images to be processed, I suggest you select it manually. Otherwise you will need to define rules. Since the Marching Squares Algorithm can start anywhere inside a bounded area, you could choose any pixel of a given color/value to detect the corresponding edge (it will initially start walking in one direction to find an edge).
3. The algorithm returns the exact 2D positions, e.g. (x/y)-tuples. You can either
   • iterate through the list and colorize the corresponding pixels by assigning a different value or
   • create a mask to select parts of your matrix and assign the value that corresponds to a different color, e.g. green or red.

Finally: Some Post-Processing
I suggested to add an artificial boundary to the image. This has two advantages: 1. The Marching Squares Algorithm works out of the box. 2. There is no need to distinguish between image boundary and the interface between two areas within the image. Just remove the artificial boundary once you are done setting the colorful edges -- this will remove the colored lines at the boundary of the image.

Answer 5

I think you are probably looking for edge detection method for gray scale images. There are many ways to do that. Maybe this can help http://en.m.wikipedia.org/wiki/Edge_detection. For differentiating edges between white and gray and edges between black and gray, try use local average intensity.

Answer 6

Maybe there is a more elegant way to do that ... but in case your array is a numpy array with dimensions (N,N) (gray scale) you can do

import numpy as np

# assuming black -> 0 and white -> 1 and grey -> 0.5
black_reg = np.where(a < 0.1, a, 10)
white_reg = np.where(a > 0.9, a, 10)

xx_black,yy_black = np.gradient(black_reg)
xx_white,yy_white = np.gradient(white_reg)

# getting the coordinates
coord_green = np.argwhere(xx_black**2 + yy_black**2>0.2)
coord_red   = np.argwhere(xx_white**2 + yy_white**2>0.2)

The number 0.2 is just a threshold and needs to be adjusted.