Image Processing: Mapping a scanned image on a template image with many identical features

Question

Problem description

We are trying to match a scanned image onto a template image:

• Example of a scanned image:

• Example of a template image:

The template image contains a collection of hearts varying in size and contour properties (closed, open left and open right). Each heart in the template is a Region of Interest for which we know the location, size, and contour type. Our goal is to match a scanned onto the template so that we can extract these ROIs in the scanned image. In the scanned image, some of these hearts are crossed, and they will be presented to a classifier that decides if they are crossed or not.

Our approach

Following a tutorial on PyImageSearch, we have attempted to use ORB to find matching keypoints (code included below). This should allow us to compute a perspective transform matrix that maps the scanned image on the template image.

We have tried some preprocessing steps such as thresholding and/or blurring the scanned image. We have also tried to increase the maximum number of features as much as possible.

The problem

The method fails to work for our image set. This can be seen in the following image: It appears that a lot of keypoints are mapped to the wrong part of the template image, so the transform matrix is not calculated correctly.

Is ORB the right technique to use here, or are there parameters of the algorithm that could be fine-tuned to improve performance? It feels like we are missing out on something simple that should make it work, but we really don't know how to go forward with this approach :).

We are trying out an alternative technique where we cross-correlate the scan with individual heart shapes. This should give an image with peaks at the heart locations. By drawing a bounding box around these peaks we hope to map that bounding box on the bounding box of the template (I can elaborat on this upon request)

Any suggestions are greatly appreciated!

import cv2 as cv
import matplotlib.pyplot as plt
import numpy as np


# Preprocessing parameters
THRESHOLD = True
BLUR      = False

# ORB parameters
MAX_FEATURES = 4048
KEEP_PERCENT = .01
SHOW_DEBUG = True

# Convert both the input image and template to grayscale
scan_file = r'scan.jpg'
template_file = r'template.jpg'

scan     = cv.imread(scan_file)
template = cv.imread(template_file)

scan_gray     = cv.cvtColor(scan, cv.COLOR_BGR2GRAY)
template_gray = cv.cvtColor(template, cv.COLOR_BGR2GRAY)

if THRESHOLD:
    _,  scan_gray     = cv.threshold(scan_gray, 127, 255, cv.THRESH_BINARY)
    _, template_gray  = cv.threshold(template_gray, 127, 255, cv.THRESH_BINARY)
    
if BLUR:
    scan_gray = cv.blur(scan_gray, (5, 5))
    template_gray = cv.blur(template_gray, (5, 5))

# Use ORB to detect keypoints and extract (binary) local invariant features
orb = cv.ORB_create(MAX_FEATURES)

(kps_template, desc_template) = orb.detectAndCompute(template_gray, None)
(kps_scan, desc_scan)         = orb.detectAndCompute(scan_gray, None)

# Match the features
#method  = cv.DESCRIPTOR_MATCHER_BRUTEFORCE_HAMMING
#matcher = cv.DescriptorMatcher_create(method)
#matches = matcher.match(desc_scan, desc_template)
bf = cv.BFMatcher(cv.NORM_HAMMING)
matches = bf.match(desc_scan, desc_template)

# Sort the matches by their distances
matches = sorted(matches, key = lambda x : x.distance)

# Keep only the top matches
keep = int(len(matches) * KEEP_PERCENT)
matches = matches[:keep]


if SHOW_DEBUG:
    matched_visualization = cv.drawMatches(scan, kps_scan, template, kps_template, matches, None)
    plt.imshow(matched_visualization)

Answer 1

Based on the clarifications provided by @it_guy, I have attempted to find all the crossed hearts using just the scanned image. I would have to try the algorithm on more images to check whether this approach will generalize or not.

1. Binarize the scanned image.

   gray_image = cv2.cvtColor(rgb_image, cv2.COLOR_BGR2GRAY)
   ret, thresh = cv2.threshold(gray_image, 180, 255, cv2.THRESH_BINARY_INV)
   

2. Perform dilation to close small gaps in the outline of the hearts, and the curves representing crosses. Note - The structuring element np.ones((1,2), np.uint8 can be changed by running the algorithm through multiple images and finding the most suitable structuring element.

closing_original = cv2.morphologyEx(original_binary, cv2.MORPH_DILATE, np.ones((1,2), np.uint8)). 

3. Find all the contours in the image. The contours include all hearts and the triangle at the bottom. We eliminate other contours like dots by placing constraints on the height and width of contours to filter them. Further, we also use contour hierachies to eliminate inner contours in cross hearts.

contours_original, hierarchy_original = cv2.findContours(closing_original, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_SIMPLE)

4. We iterate through each of the filtered contours.

Contour with normal heart -

Contour with crossed heart -

Let us observe the difference between these two types of hearts. If we look at the transition from white-to-black pixel and black-to-white pixel ( from top to bottom ) inside the normal heart, we see that for majority of the image columns the number of such transitions are 4. ( Top border - 2 transitions, bottom border - 2 transitions )

white-to-black pixel - (255, 255, 0, 0, 0)

black-to-white pixel - (0, 0, 255, 255, 255)

But, in the case of the crossed heart, the number of transitions for majority of the columns must be 6, since the crossed curve / line adds two more transitions inside the heart (black-to-white first, then white-to-black). Hence, among all image columns which have greater than or equal to 4 such transitions, if more than 40% of the columns have 6 transitions, then the given contour represents a crossed contour. Result -

Code -

import cv2
import numpy as np

def convert_to_binary(rgb_image):
    gray_image = cv2.cvtColor(rgb_image, cv2.COLOR_BGR2GRAY)
    ret, thresh = cv2.threshold(gray_image, 180, 255, cv2.THRESH_BINARY_INV)
    return gray_image, thresh

original = cv2.imread('original.jpg')
height, width = original.shape[:2]
original_gray, original_binary = convert_to_binary(original) # Get binary image
cv2.imwrite("binary.jpg", original_binary)
closing_original = cv2.morphologyEx(original_binary, cv2.MORPH_DILATE, np.ones((1,2), np.uint8)) # Close small gaps in the binary image
cv2.imwrite("closed.jpg", closing_original)
contours_original, hierarchy_original = cv2.findContours(closing_original, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_SIMPLE) # Get all the contours
bounding_rects_original = [cv2.boundingRect(c) for c in contours_original] # Get all contour bounding boxes
orig_boxes = list()

all_contour_image = original.copy()
for i, (x, y, w, h) in enumerate(bounding_rects_original):
    if h > height / 2 or w > width / 2:  # Eliminate extremely large contours
        continue
    if h < w / 2 or w < h / 2: # Eliminate vertical / horuzontal lines
        continue
    if w * h < 200: # Eliminate small area contours
        continue
    if hierarchy_original[0][i][3] != -1: # Eliminate contours created by heart crosses
        continue
    orig_boxes.append((x, y, w, h))
    cv2.rectangle(all_contour_image, (x,y), (x + w, y + h), (0, 255, 0), 3)
# cv2.imshow("warped", closing_original)
cv2.imwrite("all_contours.jpg", all_contour_image)

final_image = original.copy()
for x, y, w, h in orig_boxes:
    cropped_image = closing_original[y - 2 :y + h + 2, x: x + w] # Get the heart binary image

    col_pixel_diffs = np.abs(np.diff(cropped_image.T.astype(np.int16))/255) # Obtain all consecutive pixel differences in all the columns 

    column_sums = np.sum(col_pixel_diffs, axis=1) # Get the sum of each column's transitions. This results in an array of size equal 
    # to the number of columns, each element representing the number of black-white and white-black transitions. 

    percent_crosses = np.sum(column_sums >= 6)/ np.sum(column_sums >= 4) # Percentage of columns with 6 transitions among columns with 4 transitions
    if percent_crosses > 0.4: # Crossed heart criterion
        cv2.rectangle(final_image, (x,y), (x + w, y + h), (0, 255, 0), 3)
        cv2.imwrite("crossed_heart.jpg", cropped_image)
    else:
        cv2.imwrite("normal_heart.jpg", cropped_image)
cv2.imwrite("all_crossed_hearts.jpg", final_image)

This approach can be tested on more images to find its accuracy.