Want to detect edge and corner parts in a jigsaw puzzle, but can't find the 4 corners of each piece

Question

I have a jigsaw puzzle and want to automatically distinguish between "normal", "edge", and "corner" pieces in that puzzle (I hope that the definition of those words is obvious for anyone who has ever done jigsaw puzzle)

To make things easier, I started with a selection of 9 parts, 4 of them normal, 4 are edges and one being a corner. The original image looks like this:

My first idea now was to detect the 4 "major corners" of each single piece, and then to proceed as follows:

• It's an edge if the contour between two adjacent "major corners" is a straight line
• It's a corner if the two contours between three adjacent "major corners" are straight lines
• It's a normal part if there are no straight lines between two adjacent "major corners".

However, I have problems extracting the four "major corners" for each piece (I was trying to use Harris corners for this)

My code, including some preprocessing, is attached below, together with some resulting, including the Harris corners I get. Any input appreciated.

import cv2
import numpy as np
from matplotlib import pyplot as plt

img = cv2.imread('image.png')
gray= cv2.imread('image.png',0)

# Threshold to detect rectangles independent from background illumination
ret2,th3 = cv2.threshold(gray,220,255,cv2.THRESH_BINARY_INV)

# Detect contours
_, contours, hierarchy = cv2.findContours( th3.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# Draw contours
h, w = th3.shape[:2]
vis = np.zeros((h, w, 3), np.uint8)
cv2.drawContours( vis, contours, -1, (128,255,255), -1)

# Print Features of each contour and select some contours
contours2=[]
for i, cnt in enumerate(contours):
    cnt=contours[i]
    M = cv2.moments(cnt)

    if M['m00'] != 0:
        # for definition of features cf http://docs.opencv.org/3.1.0/d1/d32/tutorial_py_contour_properties.html#gsc.tab=0
        cx = int(M['m10']/M['m00'])
        cy = int(M['m01']/M['m00'])
        area = cv2.contourArea(cnt)
        x,y,w,h = cv2.boundingRect(cnt)
        aspect_ratio = float(w)/h
        rect_area = w*h
        extent = float(area)/rect_area        

        print i, cx, cy, area, aspect_ratio, rect_area, extent

        if area < 80 and area > 10:
            contours2.append(cnt)

# Detect Harris corners
dst = cv2.cornerHarris(th3,2,3,0.04)

#result is dilated for marking the corners, not important
dst = cv2.dilate(dst,None, iterations=5)

# Threshold for an optimal value, it may vary depending on the image.
harris=img.copy()
print harris.shape
harris[dst>0.4*dst.max()]=[255,0,0]

titles = ['Original Image', 'Thresholding', 'Contours', "Harris corners"]
images = [img, th3, vis, harris]
for i in xrange(4):
    plt.subplot(2,2,i+1),plt.imshow(images[i],'gray')
    plt.title(titles[i])
    plt.xticks([]),plt.yticks([])
plt.show()

Answer 1

From the "Contours" image you got to (vis variable in the code), I'm splitting the image to get just 1 puzzle piece per tile/image:

tiles = []
for i in range(len(contours)):
    x, y, w, h = cv2.boundingRect(contours[i]) 
    
    if w < 10 and h < 10:
        continue
    
    shape, tile = np.zeros(thresh.shape[:2]), np.zeros((300,300), 'uint8') 
    cv2.drawContours(shape, [contours[i]], -1, color=1, thickness=-1)
    
    shape = (vis[:,:,1] * shape[:,:])[y:y+h, x:x+w] 
    tile[(300-h)//2:(300-h)//2+h , (300-w)//2:(300-w)//2+w] = shape  
    tiles.append(tile)

For each tile, I apply the following:

1. filter_median to control the noise in the borders
2. Find center of the minimum enclosing circle
3. Turn the contours of the piece to polar coordinates based on the center of the circle, keeping the rho component, resulting in a graph where higher values represent points farther from the center.
4. Smooth the function to get rid of rough edges. For the bottom-right piece I get something like
5. Find number of "knobs" and "holes" by analyzing the function. The number of knobs is obtained as 4 - number of peaks/maxima (4 peaks will be inevitably the corners of the piece, farther away from the center), and I found the number of "holes" to be the number of valleys/minima below 50 (here some different threshold or image size normalization might be necessary to make this work more in general).
6. Knowing the number of features ("knobs" + "holes"), it's easy to get the type of piece:
   • 4 features: central piece
   • 3 features: border piece
   • 2 features: corner piece

I do this with the following:

for image in tiles:
    img = image.copy()
    img = filters.median_filter(img.astype('uint8'), size=15)
    plt.imshow(img)
    plt.show()

    contours, _ = cv2.findContours(img, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    (center_x, center_y), _ = cv2.minEnclosingCircle(contours[0])

    # get contour points in polar coordinates
    rhos = []
    for i in range(len(contours[0])):
        x, y = contours[0][i][0]
        rho, _ = cart2pol(x - center_x, y - center_y)
        rhos.append(rho)

    rhos = smooth(rhos, 7) # adjust the smoothing amount if necessary
    
    # compute number of "knobs"
    n_knobs = len(find_peaks(rhos, height=0)[0]) - 4
    # adjust those cases where the peak is at the borders
    if rhos[-1] >= rhos[-2] and rhos[0] >= rhos[1]:
        n_knobs += 1
    
    # compute number of "holes"
    rhos[rhos >= 50] = rhos.max()
    rhos = 0 - rhos + abs(rhos.min())
    n_holes = len(find_peaks(rhos)[0])
    
    print(f"knobs: {n_knobs}, holes: {n_holes}")
    
    # classify piece
    n_features = n_knobs + n_holes
    if n_features > 4 or n_features < 0:
        print("ERROR")
    if n_features == 4:
        print("Central piece")
    if n_features == 3:
        print("Border piece")
    if n_features == 2:
        print("Corner piece")