Scale & Rotation Invariant Template Matching

• Introduction
• Step-by-Step Guide
• Code Example
• Additional Notes
• Summary
• Conclusion
• References

Template matching is a straightforward method for object detection in images, but its reliance on exact pixel matching makes it sensitive to changes in object orientation and size. This article presents a technique to enhance template matching in OpenCV, enabling it to handle object rotations and scale variations.

Template matching in OpenCV is a simple way to find an object in an image, but it doesn't handle rotation or scale changes. Here's how to improve it:

1. Generate Rotated and Scaled Templates:

import cv2

template = cv2.imread("template.png", 0)

for angle in range(0, 360, 10):  # Rotate every 10 degrees
    for scale in range(5, 15, 2):  # Scale from 0.5x to 1.5x
        # Rotate the template
        rotation_matrix = cv2.getRotationMatrix2D((template.shape[1]/2, template.shape[0]/2), angle, scale/10)
        rotated_template = cv2.warpAffine(template, rotation_matrix, (template.shape[1], template.shape[0]))

        # Save or use the rotated and scaled template
        # ...

2. Perform Template Matching for Each Variation:

for rotated_template in rotated_templates:
    result = cv2.matchTemplate(image, rotated_template, cv2.TM_CCOEFF_NORMED)
    # ... (Find best match and store results)

3. Filter Redundant Matches:

# Sort matches by confidence score
matches = sorted(matches, key=lambda x: x[1], reverse=True)

# Keep only the best match for each distinct location
filtered_matches = []
for match in matches:
    # Check if match overlaps with existing matches
    if not any(overlapping_rectangles(match[0], existing_match[0]) for existing_match in filtered_matches):
        filtered_matches.append(match)

Explanation:

• Step 1: Creates multiple versions of the template, each rotated and scaled within a defined range.
• Step 2: Uses OpenCV's matchTemplate function to find each variation within the target image.
• Step 3: Sorts the matches by confidence score and removes redundant matches that overlap significantly.

Note: This approach is computationally expensive. Consider using feature detection and matching techniques for more efficient and robust solutions.

This Python code uses OpenCV to find instances of a template image within a larger image, even if the template is rotated or scaled. It generates rotated and scaled versions of the template, then uses template matching to find the best matches within the target image. The code then filters out overlapping matches and draws rectangles around the remaining matches in the target image. Finally, it displays the image with the highlighted matches.

import cv2

# Load the template and target image
template = cv2.imread("template.png", 0)
image = cv2.imread("image.jpg", 0)

# Store rotated and scaled templates
rotated_templates = []

# Generate rotated and scaled templates
for angle in range(0, 360, 10):
    for scale in range(5, 15, 2):
        # Rotate the template
        rotation_matrix = cv2.getRotationMatrix2D((template.shape[1]/2, template.shape[0]/2), angle, scale/10)
        rotated_template = cv2.warpAffine(template, rotation_matrix, (template.shape[1], template.shape[0]))
        rotated_templates.append(rotated_template)

# Store matches (x, y, confidence)
matches = []

# Perform template matching for each variation
for rotated_template in rotated_templates:
    result = cv2.matchTemplate(image, rotated_template, cv2.TM_CCOEFF_NORMED)
    min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)
    matches.append((max_loc, max_val))

# Function to check if rectangles overlap
def overlapping_rectangles(rect1, rect2):
    x1, y1, w1, h1 = rect1
    x2, y2, w2, h2 = rect2
    return not (x1 + w1 < x2 or x1 > x2 + w2 or y1 + h1 < y2 or y1 > y2 + h2)

# Sort matches by confidence score
matches = sorted(matches, key=lambda x: x[1], reverse=True)

# Filter redundant matches
filtered_matches = []
for match in matches:
    # Calculate bounding box for the match
    top_left = match[0]
    bottom_right = (top_left[0] + template.shape[1], top_left[1] + template.shape[0])
    match_rect = (*top_left, *bottom_right)

    # Check for overlap with existing matches
    if not any(overlapping_rectangles(match_rect, existing_match[0]) for existing_match in filtered_matches):
        filtered_matches.append((match_rect, match[1]))

# Draw rectangles around the best matches
for match in filtered_matches:
    cv2.rectangle(image, match[0][:2], match[0][2:], (0, 0, 255), 2)

# Display the result
cv2.imshow("Matches", image)
cv2.waitKey(0)
cv2.destroyAllWindows()

Explanation:

1. Import Libraries: Imports the necessary OpenCV library.
2. Load Images: Loads the template and target images.
3. Generate Variations: Creates rotated and scaled versions of the template.
4. Template Matching: Performs template matching with each variation and stores the results.
5. Overlap Check: Defines a function to check if two rectangles overlap.
6. Filter Matches: Sorts matches by confidence and removes redundant overlapping matches.
7. Display Results: Draws rectangles around the remaining matches and displays the final image.

This code provides a more complete implementation, including drawing the bounding boxes of the detected matches. Remember that this approach can be computationally expensive, and more efficient methods might be necessary for real-time applications.

Strengths and Weaknesses:

• Strengths:

  • Simplicity: Relatively easy to understand and implement.
  • Interpretability: Provides clear visual matches, making it easy to understand what the algorithm is doing.

• Weaknesses:

  • Computational Cost: Generating and matching numerous rotated and scaled templates can be computationally expensive, especially for large images and fine-grained variations.
  • Sensitivity: Highly sensitive to noise, lighting changes, and occlusions in the target image.
  • Limited Invariance: While this method addresses rotation and scaling, it doesn't handle other transformations like perspective changes or non-rigid deformations.

Possible Optimizations:

• Reduce Search Space:

  • Image Pyramids: Instead of scaling the template, create an image pyramid of the target image and search for the template at different scales.
  • Region of Interest (ROI): If you have an approximate idea of where the object might be, limit the search to that region.

• Feature-Based Matching:

  • Instead of pixel-based comparison, extract features (like edges, corners, or keypoints) from both the template and the target image. Match these features to achieve more robust and efficient matching.

Alternative Approaches:

• Feature Detection and Description (e.g., SIFT, SURF, ORB): More robust to scale, rotation, and viewpoint changes.
• Object Detection Algorithms (e.g., YOLO, SSD, Faster R-CNN): Trained on large datasets to detect specific objects with high accuracy and efficiency.

Applications:

• Simple Object Tracking: When the object's appearance doesn't change significantly.
• Alignment and Registration: Aligning images or objects based on a template.
• Industrial Inspection: Finding defects or deviations from a standard template.

Important Considerations:

• Template Quality: A clear and well-defined template is crucial for accurate matching.
• Parameter Tuning: Experiment with different rotation angles, scaling factors, and matching methods to find the optimal settings for your specific application.
• Real-Time Performance: For real-time applications, carefully consider optimizations and alternative approaches to achieve acceptable frame rates.

This article presents a method for improving basic template matching in OpenCV to handle object rotation and scale changes.

Here's how it works:

1. Generate Variations: Create multiple copies of the template, each rotated and scaled within a defined range.
2. Match Each Variation: Use OpenCV's matchTemplate function to find the best match for each rotated and scaled template within the target image.
3. Filter Redundant Matches: Sort matches by confidence score and remove overlapping matches to keep only the most likely detection for each object instance.

Pros:

• Simple to implement using OpenCV functions.
• Can handle a range of rotations and scales.

Cons:

• Computationally expensive, especially with large ranges of rotations and scales.
• Not as robust or efficient as feature-based detection methods.

Recommendation:

While this method offers an improvement over basic template matching, consider using feature detection and matching techniques for more efficient and robust object detection in real-world applications.

This article explored techniques to enhance template matching in OpenCV, enabling it to handle object rotations and scale variations. By generating rotated and scaled versions of the template and performing template matching with each variation, the code can identify instances of the template even when it's not presented in its original orientation or size. The article provides a Python code example demonstrating this approach, including steps to filter out redundant matches and highlight the detected objects in the target image. While this method offers an improvement over basic template matching, it's important to note its computational cost. For more complex scenarios or real-time applications, exploring feature-based detection methods or machine learning-based object detection algorithms is recommended. These alternatives offer greater robustness, efficiency, and the ability to handle a wider range of transformations and variations in objects.

• c++ - scale and rotation Template matching - Stack Overflow | May 19, 2012 ... There are easier ways of matching a template scale and rotationally invariant than going via feature detection and homographies.
• [Question] Scale invariant template matching : r/opencv | Posted by u/TemporalAgent7 - 8 votes and 3 comments
• image processing - Algorithm for Scale Invariant Template Matching ... | Jun 23, 2021 ... If your templates are all based on some kind of text you may use some kind of OCR to match the text itself and not only by features.
• Scale-rotation-skew invariant template matching - OpenCV Q&A ... | Aug 2, 2016 ... A template matching algorithm that is rotation, scale and skew invariant already exists in OpenCV? In industrial robotics applications, those kinds of ...
• brkyzdmr/TemplateMatcher: Scale and rotation invariant ... - GitHub | Scale and rotation invariant template matcher. Contribute to brkyzdmr/TemplateMatcher development by creating an account on GitHub.
• Real-time Scale and Rotation Invariant Multiple Template Matching ... | Object detection is an important component in the field of computer vision. Real-time detection of objects of any scale or rotation is a major challenge facing the industry today. In this study, we proposed a real-time size and orientation invariant template matching algorithm and hardware structure. In addition, we proposed image pyramid generation, patch orientation detection, descriptor generation, and descriptor matching methods. First, Scale invariance is achieved by generating a pyramid of nine images from the input image to simultaneously detect objects of different scales. Then, construct a window equal to the size of the template image from the original image to obtain the center point and direction of the window. We achieve rotation invariance by creating and rotating a descriptor based on the orientation of the window. Finally, the object is detected by matching it with the descriptor of the template. The proposed algorithm was implemented in Xilinx Virtex-7 xc7v2000tflg1925-1 FPGA. Throughput was
• Grayscale Template-Matching Invariant to Rotation, Scale ... | In this paper, we consider the grayscale template-matching problem, invariant to rotation, scale, translation, brightness and contrast, without previous.
• Multi-Template Matching: matched ROI dimensions - Usage ... | Hi @LThomas, I’m using your Multi-Template-Matching plugin through Fiji (ImageJ 1.53k). I am using a square template (726 x 726 pix) to find a single match in an image (1024 x 1024 pix with a mm scale). The template is bmp format whilst the image is a DICOM image. The command I am using is: run("Template Matching Image", "template=[template.bmp] image=[image] flip_template_vertically flip_template_horizontally rotate=10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,...
• Template Matching - Implementation - OpenMV Products - OpenMV ... | Is the below still the case…Was wondering if the template matching can handle rotation or scale changes at all? (Was it improved to use a rolling integral image window?) Template matching using something called an “integral image” to work. Template matching works by having the camera look a like 32x32 image to find out of a larger image (e.g. 320x240). That said, template matching doesn’t handle rotation or scale changes at all. It just slides around the image you want to find on the large ...