Multiple template matching with Scikit-image

Question

I want to find the middle of a coin and find the radii. The radii can tell me if the coin is 5 cents of 50 cents. After finding the image, I must be able to detect the middle of the circles so I can give them a color

I already made a beginning with writing a code for Hough-transform

Hopefully someone can help me solve this exercise.

Code for hough transform:

image = img_as_ubyte(image)
edges = feature.canny(image, sigma=1.5, low_threshold=10, high_threshold=25)

# Detect two radii
hough_radii = np.arange(17, 35, 2)
hough_res = hough_circle(edges, hough_radii)

# Select the 11 coins
accums, cx, cy, radii = hough_circle_peaks(hough_res, hough_radii,total_num_peaks=11)

# Draw them
fig, ax = plt.subplots(ncols=1, nrows=1, figsize=(10, 4))
image = color.gray2rgb(image)
count = 0
for center_y, center_x, radius in zip(cy, cx, radii):
    circy, circx = circle_perimeter(center_y, center_x, radius,
                                    shape=image.shape)
    image[circy, circx] = (220, 20, 20)
    count += 1


ax.imshow(image)
plt.figure(figsize=(25,25))
print("In this image we can detect", count, "coins")
plt.show()

Answer 1

You have 2 choices to find matching circles.

first one: sliding window

smaller windows is a template that you seek for it in input image, here two images with different radii 19 and 21 respectively. First at all, find edge of template and input image, after that, multiplying cropped part of image with template. each region that is near to template should have higher value.

def correlation_coefficient(patch1, patch2):
    product = np.mean((patch1 - patch1.mean()) * (patch2 - patch2.mean()))
    stds = patch1.std() * patch2.std()
    if stds == 0:
        return 0
    else:
        product /= stds
        return product


im1 =  cv2.imread("Original.jpg")
im1 = cv2.cvtColor(np.float32(im1), cv2.COLOR_BGR2GRAY)


im2 = cv2.imread("bigger.png")
im2 = cv2.cvtColor(np.float32(im2), cv2.COLOR_BGR2GRAY)


sh_row, sh_col = im1.shape
correlation = np.zeros_like(im1)

for i in range(sh_row - im2.shape[1]):
    for j in range(sh_col - im2.shape[0]):
        temp1 = im1[i : i + im2.shape[1], j : j + im2.shape[0]]
        if(temp1.shape != im2.shape):
          correlation[i, j] = 0
          continue
        correlation[i, j] = correlation_coefficient(temp1, im2)


fig = plt.figure(figsize=(10, 7))
plt.imshow(correlation, cmap=plt.cm.gray)
plt.show()

Here template is smaller or bigger one. output for bigger one is

As you can see some points highlighted as center of circles. Or by using second matching calculations:

im1 =  cv2.imread("Original.jpg")
im1 = cv2.cvtColor(np.float32(im1), cv2.COLOR_BGR2GRAY)

im1 = canny(im1, sigma=3, low_threshold=5, high_threshold=40)
im1 = im1.astype(np.uint8)

im2 = cv2.imread("bigger.png")
im2 = cv2.cvtColor(np.float32(im2), cv2.COLOR_BGR2GRAY)

im2 = canny(im2, sigma=3, low_threshold=5, high_threshold=40)
im2 = im2.astype(np.uint8)
sh_row, sh_col = im1.shape

d = 1

correlation = np.zeros_like(im1)

for i in range(sh_row - im2.shape[1]):
    for j in range(sh_col - im2.shape[0]):
        temp1 = im1[i : i + im2.shape[1], j : j + im2.shape[0]]
        if(temp1.shape != im2.shape):
          correlation[i, j] = 0
          continue
        correlation[i, j] = np.sum(np.multiply(temp1, im2))

io.imshow(correlation, cmap='gray')
io.show()

Also, we have same results:

First method could not help us to find specified circles. Because you need to set a threshold for both templates and resolve more and more challenges. Let's investigate another method.

first one: Hough Transform

At first, run canny edge detector, then find all circles with radii range from 1 to 100. Then near circles(circles that centers are near to each others) are deleted:

import numpy as np
import matplotlib.pyplot as plt
import cv2
from skimage import data, color
from skimage.transform import hough_circle, hough_circle_peaks
from skimage.feature import canny
from skimage.draw import circle_perimeter
from skimage.util import img_as_ubyte
from skimage import io, feature
from scipy import ndimage
import imutils
from scipy import signal
from skimage import io, feature



image = cv2.imread("Original.jpg")
fig = plt.figure(figsize=(10, 7))

fig.add_subplot(1, 2, 1)
plt.imshow(image)
plt.axis('off')
plt.title("Original Image")

image = cv2.cvtColor(np.float32(image), cv2.COLOR_BGR2GRAY)
edges = canny(image, sigma=3, low_threshold=5, high_threshold=40)

fig.add_subplot(1, 2, 2)
plt.imshow(edges, cmap=plt.cm.gray)
plt.axis('off')
plt.title("After Run Canny Edge Detector")

# which raddii?
hough_radii = np.arange(1, 100)
hough_res = hough_circle(edges, hough_radii)

accums, cx, cy, radii = hough_circle_peaks(hough_res, hough_radii, total_num_peaks=100)
output = np.column_stack((cx, cy, radii))
output = output[(output[:,2] > 10)]

output = output[np.argsort(output[:, 1])]
output = output[np.argsort(output[:, 0])]

print(f"Circles Before Edit")
print(f"cx={output[:,0]}")
print(f"cy={output[:,1]}")
print(f"radii={output[:,2]}")

index = 0
flag = False
while (index < output.shape[0] - 1):

  if(abs (output[index][0] - output[index+1][0]) < 5 ):
    if(abs (output[index][1] - output[index+1][1]) < 5 ):
      # print(f"del index {index+1}")
      output = np.delete(output, (index+1), axis=0)
      flag = True
    else:
      flag = False
  else:
    flag = False
  if(flag is not True):
    index += 1
print(f"Circles After Edit")
print(f"cx={output[:,0]}")
print(f"cy={output[:,1]}")
print(f"radii={output[:,2]}")


plt.show()


red = output[(output[:,2] <= 20)]
print(f"Red Circles")
print(f"cx={red[:,0]}")
print(f"cy={red[:,1]}")
print(f"radii={red[:,2]}")

green = output[(output[:,2] >= 20)]
print(f"Green Circles")
print(f"cx={green[:,0]}")
print(f"cy={green[:,1]}")
print(f"radii={green[:,2]}")

Check results:

Circles Before Edit
cx=[ 96  96  97  98 105 106 146 165 188 189 196 196 202 203 204 216 264 265]
cy=[137 138 136 138 232 232 356 229 102 102 166 166 222 221 286 322 116 116]
radii=[22 23 23 21 22 21 19 21 21 22 19 18 19 18 22 19 18 19]
Circles After Edit
cx=[ 96 105 146 165 188 196 202 204 216 264]
cy=[137 232 356 229 102 166 222 286 322 116]
radii=[22 22 19 21 21 19 19 22 19 18]

After do all necessary calculations:

Red Circles
cx=[146 196 202 216 264]
cy=[356 166 222 322 116]
radii=[19 19 19 19 18]
Green Circles
cx=[ 96 105 165 188 204]
cy=[137 232 229 102 286]
radii=[22 22 21 21 22]

As mentioned in results, 5 circles are proposed to red and 5 circles proposed to green.

Update#1

Be cautious before doing preprocessing in such problems. These processing likes erosion, dilation and median filters change radius of circles.

Drawing Circles:

Input radius are 19 and 21, so radius larger than 20 are belong to green color and radius smaller than 20 are belong to red color. For simplicity I set yellow color for radius = 20. In the last step you should delete abundance circles. Bellow I bring all of them together:

def remove_redundance(output):
  
  print(f"output.shape={output.shape}")
  index = 0
  del_first = False
  index_first = 0
  while (index_first < output.shape[0]):
    index_second = index_first + 1
    del_second = False
    while (index_second < output.shape[0]):

      if( (abs(output[index_first][0] - output[index_second][0]) < 10) and 
         (abs(output[index_first][1] - output[index_second][1]) < 10) ):
        
        if(output[index_first][3] > output[index_second][3]):
          output = np.delete(output, (index_second), axis=0)
          del_second = True
        else:
          output = np.delete(output, (index_first), axis=0)
          del_first = True
          break

      else:
        del_second = False
        del_first = False

      if (del_second == False):
        index_second += 1
    
    
    if (del_first == False):
      index_first += 1
    else:
      del_first = False

  print(f"output.shape={output.shape}")
  return output
  

def draw_circles(circle, coordinate, green = 0):
  for cx, cy, radii in zip(coordinate[:,0], coordinate[:,1], coordinate[:,2]):
    # Center coordinates
    center_coordinates = (int(cx), int(cy))
    
    # Radius of circle
    radius = int(radii)
    
    if(green == 1):
      color = (0, 255, 0)
    elif(green == 0):
      color = (0, 0, 255)
    elif(green == -1):
      color = (0, 255, 255)
      
    thickness = 1#-1
      
    circle = cv2.circle(circle, center_coordinates, radius, color, thickness)

  return circle



image = cv2.imread("Original.jpg")
# image = cv2.medianBlur(image, 3)
fig = plt.figure(figsize=(10, 7))

fig.add_subplot(1, 2, 1)
plt.imshow(image)
plt.axis('off')
plt.title("Original Image")

image = cv2.cvtColor(np.float32(image), cv2.COLOR_BGR2GRAY)
edges = canny(image, sigma=3, low_threshold=5, high_threshold=40)

fig.add_subplot(1, 2, 2)
plt.imshow(edges, cmap=plt.cm.gray)
plt.axis('off')
plt.title("After Run Canny Edge Detector")

# which raddii?
hough_radii = np.arange(1, 500)
hough_res = hough_circle(edges, hough_radii)

accums, cx, cy, radii = hough_circle_peaks(hough_res, hough_radii, total_num_peaks=500)
output = np.column_stack((cx, cy, radii, accums))#
output = output[(output[:,2] > 10)]

output = output[np.argsort(output[:, 1])]
output = output[np.argsort(output[:, 0])]

print(f"Circles Before Edit")
print(f"cx={output[:,0]}")
print(f"cy={output[:,1]}")
print(f"radii={output[:,2]}")


output = remove_redundance(output)


print(f"Circles After Edit")
print(f"cx={output[:,0]}")
print(f"cy={output[:,1]}")
print(f"radii={output[:,2]}")


plt.show()


red = output[(output[:,2] < 20)]
if(red.shape[0]>0):
  print(f"Red Circles")
  print(f"cx={red[:,0]}")
  print(f"cy={red[:,1]}")
  print(f"radii={red[:,2]}")

green = output[(output[:,2] > 20)]
if(green.shape[0]>0):
  print(f"Green Circles")
  print(f"cx={green[:,0]}")
  print(f"cy={green[:,1]}")
  print(f"radii={green[:,2]}")


yellow = output[(output[:,2] == 20)]
if(yellow.shape[0]>0):
  print(f"yellow Circles")
  print(f"cx={yellow[:,0]}")
  print(f"cy={yellow[:,1]}")
  print(f"radii={yellow[:,2]}")


circle = cv2.imread("Original.jpg")

if(red.shape[0]>0):
  circle  = draw_circles(circle, red, green = 0)
if(green.shape[0]>0):
  circle  = draw_circles(circle, green, green = 1)
if(yellow.shape[0]>0):
  circle  = draw_circles(circle, yellow, green = -1)

circle = cv2.cvtColor(circle, cv2.COLOR_BGR2RGB)

fig = plt.figure(figsize=(10, 7))
plt.imshow(circle)
plt.axis('off')
plt.title("Circles") 

Results: