Template Matching and Color Segmentation in Image Processing: Where's Wally?

matlab image-processing object-detection template-matching

Remember Wally from Martin Handford’s children book series Where’s Wally? When you were a kid, you probably spent plenty of time trying to find Wally in those illustrations. Now as an adult, we can write a simple MATLAB program that can automatically find Wally for us!

Where's Wally

Can you find Wally in the above image? Finding an specific object in an image can be a tiring task for us humans, but this is actually pretty easy for machines. Now let’s use MATLAB to find where Wally is!

The source code for today’s MATLAB image processing tutorial can be found at chen-yumin/where-is-wally.

Wally

Today, we will try and locate an object in an image by using techniques like template matching and color segmentation. Our desired object today is Wally – Remember that guy with distinctive red-and-white-striped shirt, bobble hat, and glasses?

There are many techniques to detect and isolate a specific object of interest in a static image. For some easy tasks, we could sometimes simply apply a thresholding and the foreground and be easily separated from the background. In this example, I’ll walk you through using template matching and color segmentation to get this done.

Template Matching

Template matching uses a template and tries to find the best match of the template in the image. It loops through the image in an attempt to find where the object template is. For each location, the difference between the template and the neighborhood is calculated and recorded. The location with minimum difference is returned.

% Use a 2-dimensional array to record the difference of each position
diffs = zeros(ih-h, iw-w);

for i = 1:ih-h
    for j = 1:iw-w
        neighborhood = imageGray(i:i+h-1, j:j+w-1);
        difference = abs(neighborhood - templateGray);
        diffs(i, j) = sum(difference(:)) / (w*h);

        % If difference nearly zero, this is the exact match
        if diffs(i, j) < 0.001
            y = i;
            x = j;
            % Return the position found to improve efficiency
            fprintf('An exact match is found. Return.')
            return;
        end
    end
end
% Find the minimum difference value and its position
[~, i] = min(diffs(:));
[y, x] = ind2sub(size(diffs), i);

Correlation matching works perfect for a small image. However, because of the amount of calculation involved, using this method on the full-size image would be painfully slow.

A more efficient way of recognizing Wally, without having to loop through every pixel, is to directly try and find Wally and his stylish red and white T-shirt. We can use color segmentation and then morphology here.

Color Segmentation

To segment using colors, we firstly need to convert the image to HSV color space and use the Hue and Saturation to segment the red and write stripes. To a achieve the final result of finding Wally, a vertical linear structuring element is used to dilate the stripes and find their overlapped area so the result will be only connected red and white area.

% Convert to HSV color space
imageHsv = rgb2hsv(image);
h = imageHsv(:, :, 1);
s = imageHsv(:, :, 2);
v = imageHsv(:, :, 3);

% Segment using color
redStripes = ((h < 0.05) | (h > 0.95)) & (s > 0.4) & (v > 0.4);
whiteStripes = (s < 0.2) & (v > 0.9);

% Create vertical (90 degree) linear structuring element
se = strel('line', ih * 0.01, 90);

% Dilate the stripes vertically
redDilated = imdilate(redStripes, se);
whiteDilated = imdilate(whiteStripes, se);

% Get their overlapped area
roi = redDilated & whiteDilated;

% Remove smaller or bigger components that are not Wally
roi = bwareaopen(roi, floor((iw/108) * (ih/108)));
bigger = bwareaopen(roi, floor((iw/50) * (ih/50)));
roi = roi - bigger;

% Purify Wally
roi = roi & (redStripes | whiteStripes);
roi = imdilate(roi, se);
roi = bwareaopen(roi, 10);

In this method, we firstly try and segment the red and white color stripes. The image is converted into HSV color space, where H (hue) represents where the color lies in a color spectrum. The h value is vital in determining which area is red or white.

Then, morphological operations (dilation) are applied to make the red and white stripes bigger. In this case, a vertical (90 degree) linear structuring element is created using strel to make the dilation operation only expand the image towards vertical directions (up and down). Therefore, the red and white stripes will overlap.

The overlapped area represents connected components with both red and white color stripes. And this is very likely where Wally is.

Where's Wally Color Segmentation

See can you find Wally from the above image now? Yes, we have used color segmentation technique to select only red and white components in the image. We have managed to find all the red and white objects!

Chen Yumin
Chen Yumin

Hi, my name is Chen Yumin.
I am the author of the stuff you're reading right now.

Latest Project
CoderBox.io
CoderBox.io

Connect With Me

Enjoy what you see? Follow me on:

Subscribe

Subscribe via RSS