スタンフォード/CS131/宿題2-2 キャニーエッジ検出 2

スポンサーリンク

Part 1: Canny Edge Detector¶

In this part, you are going to implment Canny edge detector. The Canny edge detection algorithm can be broken down in to five steps:
このパートでは、キャニー法を実装する。キャニーエッジ検出アルゴリズムは、5つのステップに分解することができる(今回は残りの2パート)。

1. Double thresholding(二重閾値)
2. Edge tracking by hysterisis(ヒステリシスによるエッジ追跡)
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
from time import time
from skimage import io
from __future__ import print_function
%matplotlib inline
plt.rcParams['figure.figsize'] = 18.0, 11.0 # set default size of plots
plt.rcParams["font.size"] = "18"
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

from edge import conv, gaussian_kernel

# Define 3x3 Gaussian kernel with std = 1
kernel = gaussian_kernel(3, 1)
kernel_test = np.array(
[[ 0.05854983, 0.09653235, 0.05854983],
[ 0.09653235, 0.15915494, 0.09653235],
[ 0.05854983, 0.09653235, 0.05854983]]
)
# Test Gaussian kernel
if not np.allclose(kernel, kernel_test):

# Test with different kernel_size and sigma
kernel_size = 5
sigma = 1.4

# Define 5x5 Gaussian kernel with std = sigma
kernel = gaussian_kernel(kernel_size, sigma)

# Convolve image with kernel to achieve smoothed effect
smoothed = conv(img, kernel)


Double Thresholding¶

The edge-pixels remaining after the non-maximum suppression step are (still) marked with their strength pixel-by-pixel. Many of these will probably be true edges in the image, but some may be caused by noise or color variations, for instance, due to rough surfaces. The simplest way to discern between these would be to use a threshold, so that only edges stronger that a certain value would be preserved. The Canny edge detection algorithm uses double thresholding. Edge pixels stronger than the high threshold are marked as strong; edge pixels weaker than the low threshold are suppressed and edge pixels between the two thresholds are marked as weak.

Implement double_thresholding in edge.py
edge.pyに、double_thresholdingを実装せよ。

def double_thresholding(img, high, low):
"""
Args:
img: numpy array of shape (H, W) representing NMS edge response
high: high threshold(float) for strong edges
low: low threshold(float) for weak edges
Returns:
strong_edges: Boolean array representing strong edges.
Strong edeges are the pixels with the values above
the higher threshold.
weak_edges: Boolean array representing weak edges.
Weak edges are the pixels with the values below the
higher threshould and above the lower threshold.
"""
strong_edges = np.zeros(img.shape)
weak_edges = np.zeros(img.shape)
strong_edges = img > high
weak_edges = np.logical_and(img >= low, img <= high)
return strong_edges, weak_edges

from edge import non_maximum_suppression

nms = non_maximum_suppression(G, theta)
low_threshold = 0.02
high_threshold = 0.03

strong_edges, weak_edges = double_thresholding(nms, high_threshold, low_threshold)
assert(np.sum(strong_edges & weak_edges) == 0)

edges=strong_edges * 1.0 + weak_edges * 0.5

plt.subplot(1,2,1)
plt.imshow(strong_edges)
plt.title('Strong Edges')
plt.axis('off')

plt.subplot(1,2,2)
plt.imshow(edges)
plt.title('Strong+Weak Edges')
plt.axis('off')
plt.show()


Edge tracking¶

Strong edges are interpreted as “certain edges”, and can immediately be included in the final edge image. Weak edges are included if and only if they are connected to strong edges. The logic is of course that noise and other small variations are unlikely to result in a strong edge (with proper adjustment of the threshold levels). Thus strong edges will (almost) only be due to true edges in the original image. The weak edges can either be due to true edges or noise/color variations. The latter type will probably be distributed in dependently of edges on the entire image, and thus only a small amount will be located adjacent to strong edges. Weak edges due to true edges are much more likely to be connected directly to strong edges.

def get_neighbors(y, x, H, W):
""" Return indices of valid neighbors of (y, x)
Return indices of all the valid neighbors of (y, x) in an array of
shape (H, W). An index (i, j) of a valid neighbor should satisfy
the following:
1. i >= 0 and i < H
2. j >= 0 and j < W
3. (i, j) != (y, x)
Args:
y, x: location of the pixel
H, W: size of the image
Returns:
neighbors: list of indices of neighboring pixels [(i, j)]
"""
neighbors = []
for i in (y-1, y, y+1):
for j in (x-1, x, x+1):
if i >= 0 and i < H and j >= 0 and j < W:
if (i == y and j == x):
continue
neighbors.append((i, j))
return neighbors

def link_edges(strong_edges, weak_edges):
""" Find weak edges connected to strong edges and link them.
Iterate over each pixel in strong_edges and perform breadth first
search across the connected pixels in weak_edges to link them.
Here we consider a pixel (a, b) is connected to a pixel (c, d)
if (a, b) is one of the eight neighboring pixels of (c, d).
Args:
strong_edges: binary image of shape (H, W)
weak_edges: binary image of shape (H, W)
Returns:
edges: numpy array of shape(H, W)
"""
H, W = strong_edges.shape
indices = np.stack(np.nonzero(strong_edges)).T
edges = np.zeros((H, W))
edges = np.copy(strong_edges)
for i in range(1, H-1):
for j in range(1, W-1):
neighbors = get_neighbors(j, i, H, W)
if weak_edges[i,j] and np.any(edges[x,y] \
for x,y in neighbors):
edges[i,j] = True
return edges

test_strong = np.array(
[[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 1]]
)

test_weak = np.array(
[[0, 0, 0, 1],
[0, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 1, 0]]
)

plt.subplot(1, 3, 1)
plt.imshow(test_strong)
plt.title('Strong edges')

plt.subplot(1, 3, 2)
plt.imshow(test_weak)
plt.title('Weak edges')

plt.subplot(1, 3, 3)
plt.show()

edges = link_edges(strong_edges, weak_edges)

plt.imshow(edges)
plt.axis('off')
plt.show()


Canny edge detector¶

Implement canny in edge.py using the functions you have implemented so far. Test edge detector with different parameters.

Here is an example of the output:

def canny(img, kernel_size=5, sigma=1.4, high=20, low=15):
""" Implement canny edge detector by calling functions above.
Args:
img: binary image of shape (H, W)
kernel_size: int of size for kernel matrix
sigma: float for calculating kernel
high: high threshold for strong edges
low: low threashold for weak edges
Returns:
edge: numpy array of shape(H, W)
"""
kernel = gaussian_kernel(kernel_size, sigma)
smoothed = conv(img, kernel)
nms = non_maximum_suppression(G, theta)
strong_edges, weak_edges = double_thresholding(nms, high, low)
return edge

# Load image