Skip to content

afs1955/Fastest_Image_Pattern_Matching

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

86 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Fastest Image Pattern Matching

The best template matching implementation on the Internet.

Using C++/MFC/OpenCV to build a Normalized Cross Corelation-based image alignment algorithm

The result means the similarity of two images, and the formular is as followed: image

Improvements

  1. rotation invariant
  2. using image pyrimid as a searching strategy
  3. minimizing the inspection area on the top level of image pyrimid
  4. optimized rotation time from opencv by setting needed "size" and modifying rotation matrix
  5. rotation precision is as high as possible
  6. SIMD version of image convolution (extremely speed up for large template)

Comparison with commercial libraries

Inspection Image : 4024 X 3036

Template Image: 762 X 521

Library Index Score Angle PosX PosY Execution Time
My Tool 0 1 0.046 1725.857 1045.433 76ms
My Tool 1 0.998 -119.979 2662.869 1537.446
My Tool 2 0.991 120.150 1768.936 2098.494
Cognex 0 1 0.030 1725.960 1045.470 125ms
Cognex 1 0.989 -119.960 2663.750 1538.040
Cognex 2 0.983 120.090 1769.250 2099.410
Aisys 0 1 0 1726.000 1045.500 202ms
Aisys 1 0.990 -119.935 2663.630 1539.060
Aisys 2 0.979 120.000 1769.63 2099.780

note: if you want to get a best performance, please make sure you are using release verson (both this project and OpenCV dll). That's because O2-related settings significantly affects efficiency, and the difference of Debug and Release can up to 7 times for some cases.

Tests

test0 - with user interface

image

test1 (164ms 80ms (SIMD version), TargetNum=5, Overlap=0.8, Score=0.8, Tolerance Angle=180)

image

test2 (237 ms, 175ms (SIMD Version))

image

test3 (152 ms, 100ms (SIMD Version))

image

test4 (21 ms, Target Number=38, Score=0.8, Tolerance Angle=0, Min Reduced Area=256)

image

test5 (27 ms)

image

test6 (1157ms, 657ms (SIMD Version), Target Number=15, Score=0.8, Tolerance Angle=180, Min Reduced Area=256)

image

Steps to build this project

  1. Download Visual Studio 2017 or newer versions
  2. Check on the option of "x86 and x64 version of C++ MFC"
  3. Install
  4. Open MatchTool.vcxproj
  5. Upgrade if it is required
  6. Open this project's property page
  7. Modified "General-Output Directory" to the .exe directory you want (usually the directory where your opencv_worldXX.dll locates)
  8. Choose the SDK version you have in "General-Windows SDK Version"
  9. Choose the right toolset you have in "General-Platform Toolset" (for me, it is Visual Studio 2017 (v141))
  10. Go to "VC++ Directories", and type in "Include Directories" for your own OpenCV (e.g. C:\OpenCV3.1\opencv\build\include or C:\OpenCV4.0\opencv\build\include)
  11. Type in "Library Directories" for your own OpenCV's library path (the directory where your opencv_worldXX.lib locates)
  12. Go to "Linker-Input", and type in library name (e.g. opencv_world310d_vs2017.lib or opencv_world401d.lib)
  13. Make sure that your opencv_worldXX.dll and MatchTool.Lang are in the same directory as .exe of this project

Adaptation for OpenCV4.X

1.Select Debug_4.X or Release_4.X in "Solution Configuration" image

2.Do step 10~12 in previous section

Usage of this project

  1. Select the Language you want
  2. Drag Source Image to the Left Area
  3. Drag Dst Image to the Right Top Area
  4. Push "Execute Button"

Parameters Setting

  1. Target Number: possible max objects you want to find in the inspection image
  2. Max OverLap Ratio: (the overlap area between two findings) / area of golden sample
  3. Score (Similarity): accepted similarity of findings (0~1), lower score causes more execution time
  4. Tolerance Angle: possible rotation of targets in the inspection image (180 means search range is from -180~180), higher angle causes more execution time or you can push "↓" button to select 2 angle range
  5. Min Reduced Area: the min area of toppest level in image pyrimid (trainning stage)

About outputs

  1. results are sorted by score (decreasing order)
  2. Angles: inspected rotation of findings
  3. PosX, PosY: pixel position of findings

Demonstration Video

youtube link

Image

This project can also be used as OCR

youtube link

image

About

Using C++/MFC/OpenCV to build a NCC-Based Image Matching algorithm

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 94.9%
  • C 5.1%