I have been going through some stuff lately on Artificial Intelligence (AI) for my project in MTech, as part of which, template/pattern matching is one of the few things I studied and it’s  implementation using OpenCV (Open Source Computer Vision).

 

 

Artificial Intelligence and the Turing Test

Starting with a brief introduction about Artificial Intelligence and it’s origin: AI is known as the study of human intelligence such that it can be replicated artificially i.e. why, the term artificial intelligence.

Three key things here are :

  • learning
  • reasoning and
  • self-correction

There is a famous Turing Test in AI, named after Alan Turing, to determine whether a machine is capable of thinking like a human. He proposed a test known as ‘Imitation Game’ as part of his research paper ‘Computing Machinery and Intelligence’ in 1950 where he proposed to consider the question, ‘Can machines think ? ‘ and described this in terms of a game called the ‘ imitation game’.

Since the introduction of the Turing test, it has proven to be both highly influential and widely criticised, and has been often held up as a vital threshold AI must pass en route to true intelligence. A chatbot called Eugene Goostman was able to fool the Turing Test 2014. It convinced the judges 33% of the time, that it was a human being and not a computer.

 

 

Pattern/Template Matching

So, coming to one problem statement where say a user clicks an image from his phone and then the algorithm provides the nearest match of that image. This is where pattern matching, also known as template matching (finding a given pattern in a given image) comes into picture and has many applications today in image processing, image recognition and video compression.

It has two primary components-

  • Source image (I): The image in which we expect to find a match to the template image.
  • Template image (T): The patch image which will be compared to the template image.

A popular class of distortion functions measuring the degree of similarity or dissimilarity between template and subimage candidate to perform the comparison and select the most similar candidate is defined from the distance measure based on the ?? norm:

lp_norm

with ? being the template and ?? the generic subimage candidate, both seen as vectors of cardinality ? , and || .||? denoting the ?? norm, p 1.

Template Matching Problem:

The template matching problem thus can be defined as follows:

  • Given a N = n x n pixels image sub-window q (called Template or Patch)
  • Find either the most similar patch to it in the image, or all patches p where the distance between p and q is below a certain threshold T according to a predefined dissimilarity measure.

Approach to solve template matching:

There have been two approaches to solve template matching problem:

  • Full Search (FS) :
    • This algorithm computes the distance between q and all template-sized sub-windows in the image and returns either the patch with the smallest distance or all the patches with distance below a threshold T.
  • Fast Fourier Transform (FFT) approach:
    • This algorithm has been traditionally used for accelerating pattern matching in the ?2 norm, especially for large pattern sizes where the idea is based on  ?2norm observations between two M pixels-sized sub-windows.

 

 

State-of-the-art Algorithms

There are many state-of-the-art algorithms today which have shown the feasibility of speeding-up pattern matching with respect to brute force method of template matching based on the Lp norm among which the most notable are:

  1. Low Resolution Pruning (LRP ) Algorithm: requires the computation of the image candidates at different resolution levels, this step being performed efficiently by means of incremental techniques that exploit recursive schemes.
  2. Incremental Dissimilarity Approximation (IDA) Algorithm: incorporates partial distance terms into the bounding functions and represent a closer approximation of the δp(x, y) term.

 

 

OpenCV (Open Source Computer Vision)

  • OpenCV is a cross-platform library of programming functions mainly aimed at real-time computer vision, originally developed by Intel’s research center in Nizhny Novgorod (Russia).
  • Written in optimized C/C++, the library can take advantage of multi-core processing.
  • It has C++, C, Python and Java interfaces and supports Windows, Linux, Mac OS, iOS and Android.
  • Enabled with OpenCL (an open standard for writing code that runs across heterogeneous platforms including CPUs, GPUs, DSPs), it can take advantage of the hardware acceleration of the underlying heterogeneous compute platform.

 

 

Template Matching in OpenCV

OpenCV makes use of two main functions in template matching:

cv2.matchTemplate()

  • It simply slides the template image over the input image (as in 2D convolution) and compares the template and patch of input image under the template image.
  • It returns a grayscale image, where each pixel denotes how much does the neighbourhood of that pixel match with template.

cv2.minMaxLoc()

  • If input image is of size (WxH) and template image is of size (wxh), output image will have a size of (W-w+1, H-h+1).
  • Once we get the result, we can use cv2.minMaxLoc() function to find where is the maximum/minimum value.
  • Take it as the top-left corner of rectangle and take (w,h) as width and height of the rectangle. That rectangle is your region of template.

 

 

Installation Guide OpenCV3 on Mac OSX (with Python):

Let’s see step-by-step guide on how to install OpenCV 3 on Mac OS X with Python support:

Prerequisites:

  1. Install cmake
  2. Install python (using homebrew)
    • For homebrew:
      $ ruby-e"$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master
    • Install python:
    • $ brew install python
    • Add following line in ~/.profile file (to open bash profile: open -e .bash_profile) :
    • $ export PATH=/usr/local/bin:$PATH
    • To update environment variables set:
      $ source ~/.profile
    • Run following command to see python is set:
      $ which python
      • You should see following printed:
        /usr/local/bin/python
  3. Download OpenCV
  4. Download opencv_contrib

Installation:

  1. Run the following command on your terminal:
    $ cd /path/to/opencv-3.0.0/ 
    $ mkdir build 
    $ cd build 
    $ cmake -D CMAKE_BUILD_TYPE=RELEASE -D CMAKE_INSTALL_PREFIX=/path/to/opencv-3.0.0/build -D PYTHON2_LIBRARY=/usr/local/Cellar/python/2.7.9/Frameworks/Python.framework/Versions/2.7/bin -D PYTHON2_INCLUDE_DIR=/usr/local/Frameworks/Python.framework/Headers -D PYTHON2_PACKAGES_PATH=/usr/local/lib/python2.7/site-packages -D INSTALL_C_EXAMPLES=ON -D INSTALL_PYTHON_EXAMPLES=ON -D BUILD_EXAMPLES=ON -D OPENCV_EXTRA_MODULES_PATH=/path/to/opencv_contrib-3.0.0/modules ../
  2.  Go to opencv directory
    cd /path/to/opencv-3.0.0/

    and then run:

    $ make -j4 
    $ make install

    [“-j4” flag indicates that it should use 4 cores]

  3. Set the library path:
    $ export DYLD_LIBRARY_PATH=/path/to/opencv-3.0.0/build/lib:$DYLD_LIBRARY_PATH
  4. Copy the pkg-config file “opencv.pc” to “/usr/local/lib/pkgconfig” and name it “opencv3.pc”:
    $ cp /path/to/opencv-3.0.0/build/lib/pkgconfig/opencv.pc /usr/local/lib/pkgconfig/opencv3.pc
  5. Add following line in ‘~./profile’ to update PKG_CONFIG_PATH environment variable:
    export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig/:$PKG_CONFIG_PATH
  6. Reload “~/.profile” file.
    $ source ~/.profile
  7. Check if OpenCV with C++ is working:
    $ cd /path/to/opencv-3.0.0/samples/cpp 
    $ g++ -ggdb `pkg-config --cflags --libs opencv3` opencv_version.cpp -o /tmp/opencv_version && /tmp/opencv_version

    You are good to go if you see “Welcome to OpenCV 3.0.0” printed.

Now, check the opencv  python version:

$ python -c "import cv2; print cv2.__version__"

If it says “3.0.0” on the terminal, this means you have successfully installed OpenCV 3 .

 

 

SetUp Guide XCode with OpenCV3:

[Note : following steps are as per XCode version used is 7.3.1]

  • Open XCode -> create new project.
  • Choose Command Line Tool under OSX -> Application:

chose_template

  • Give product name -> Next -> Create:

product_name

  • Set paths for OpenCV libraries:
    • Go to ‘Build Settings’ -> ‘Search Paths’
    • Double click on ‘Header Search Paths’ -> click on “+” -> add : ‘/usr/local/include’ :

header_search_paths

  • Double click on ‘Library Search Paths’ -> click on “+” -> add : ‘/usr/local/lib’ :

library_search_paths

  • Add libraries to link:
    • Under ‘Build Settings’ -> ‘Linking’
    • Paste the following  in ‘Other Linker Flags’ ->
      -lopencv_calib3d -lopencv_core -lopencv_features2d -lopencv_flann -lopencv_highgui -lopencv_imgcodecs -lopencv_imgproc -lopencv_ml -lopencv_objdetect -lopencv_photo -lopencv_shape -lopencv_stitching -lopencv_superres -lopencv_ts -lopencv_video -lopencv_videoio -lopencv_videostab

linking_linker_flags

  • In your main.cpp file now, add the following code snippet:
    • Use following as “source.jpeg” and”template.jpeg” respectively:

source

(Image source: https://www.inf.u-szeged.hu/~pbalazs/teaching/TemplateMatching.pdf)

template

Let us have a look at it by an example where we try to find template in the source image and store matching results for each template location:

#include "opencv2/imgcodecs.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
#include <stdio.h>

using namespace std;
using namespace cv;

Mat source_image; Mat template_image; Mat result;
const char* image_window = "Source Image";
const char* result_window = "Result window";

int match_method;
int max_Trackbar = 5;

void MatchingMethod( int, void* );

int main( int, char** argv )
{
 // Load image
 source_image = imread("/path/to/source.jpeg");
 
 //Load template
 template_image = imread("/path/to/template.jpeg");
 
 // Create windows
 namedWindow( image_window, WINDOW_AUTOSIZE );
 namedWindow( result_window, WINDOW_AUTOSIZE );
 
 // Trackbar
 const char* trackbar_label = "Method: \n 0: SQDIFF \n 1: SQDIFF NORMED \n 2: TM CCORR \n 3: TM CCORR NORMED \n 4: TM COEFF \n 5: TM COEFF NORMED";
 createTrackbar( trackbar_label, image_window, &match_method, max_Trackbar, MatchingMethod );
 
 MatchingMethod( 0, 0 );
 waitKey(0);
 return 0;
}

/**
 * @function MatchingMethod
 */

void MatchingMethod( int, void* )
{
 // Source image to display
 Mat img_display;
 source_image.copyTo( img_display );
 
 // Result matrix
 int result_cols = source_image.cols - template_image.cols + 1;
 int result_rows = source_image.rows - template_image.rows + 1;
 
 result.create( result_rows, result_cols, CV_32FC1 );
 
 // Matching and Normalization
 matchTemplate( source_image, template_image, result, match_method );
 normalize( result, result, 0, 1, NORM_MINMAX, -1, Mat() );
 
 // Best match from minMaxLoc
 double minVal; double maxVal; Point minLoc; Point maxLoc;
 Point matchLoc;
 
 minMaxLoc( result, &minVal, &maxVal, &minLoc, &maxLoc, Mat() );
 
 // For SQDIFF and SQDIFF_NORMED, the best matches are lower values. For all the other methods, the higher the better
 if( match_method == TM_SQDIFF || match_method == TM_SQDIFF_NORMED )
 { matchLoc = minLoc; }
 else
 { matchLoc = maxLoc; }
 
 //output
 rectangle( img_display, matchLoc, Point( matchLoc.x + template_image.cols , matchLoc.y + template_image.rows ), Scalar::all(0), 2, 8, 0 );
 rectangle( result, matchLoc, Point( matchLoc.x + template_image.cols , matchLoc.y + template_image.rows ), Scalar::all(0), 2, 8, 0 );
 
 imshow( image_window, img_display );
 imshow( result_window, result );
 
 return;
}

What the above code does:

  • loads the sample source and template images
  • creates trackbar to mention tracking methods name to be used
  • result matrix stores matching results for each template location.
  • use of matchTemplate function followed by normalization
  • localizing min and max values using minMaxLoc
  • displaying source and result matrix

References for state-of-the-art algorithms and OpenCV:

  1. http://docs.opencv.org/
  2. https://github.com/Itseez/opencv
  3. http://vision.deis.unibo.it/fede/papers/pami12.pdf
  4. http://vision.deis.unibo.it/fede/papers/jprl11b.pdf
Share if you like : Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

Leave a Reply

Your email address will not be published. Required fields are marked *