- Problem statement
- Problem solution description
- Project architecture
- Patch match examples
- Patch match results
Our friend went to trip around the world. He likes to take pictures of the places he visited and upload them online. We have given a template image of the world and we need to find where the picture has been taken.
Pictures are patches extracted from template picture and can be various shape. They will not be rotated, but they could have 2 kinds of distortions: 1) few random pixels value changes in patch 2) gaussian noise added to the patch. Input will be text files pointing to different sets of input (with names 1, 2, 3, 4…). There sets contains different patch size and patches with and without distortion. However same type of patches will be in same set.
Our problem is to match each patch in template with 2 conditions:
1. Patch will be consider as matched if we are match left top corner in 40x40 area around expected point
2. Patch matcher should match patch in average time of 10ms
Template, sample input configuration and few different patch type images are shown below.
We can see that inputs folder contains [number].txt files referencing folder set/[number] which contains patches to be matched. First line in [number].txt file is path to map image. Second line (1000) is number of patches in that folder and third line (40 40) is patch size. Then other lines represent path to each patch in that folder.
To solve this problem we implemented patch matcher. Patch matcher extract relevant points (key points) from template image and in these points it extracts feature which represent that point. These information in stored in patch matcher, so when we provide patch it goes through same procedure and extract relevant features from patch. Then it tries to find most suitable match from template features. When it does we find transformation which transforms patch location to template location.
Matching procedure can be summarized as follows:
1. Extract relevant key points and feature around each key point from template image
2. Save template key points and features in PatchMatcher object
3. For each patch run same procedure: extract patch key points and features
4. Match current patch features and saved template features
5. Calculate transformation which transforms patch key points to template key points from matched features points
There are two patch matcher implementations. Everything is implemented using only numpy:
1) Simple patch matcher:
a. key points - each pixel in template image; center of patch
b. features - pixel values around key point (20x20 area)
c. matching - minimum feature Euclidian distance
d. outlier filter - no filter
2) Advanced patch matcher:
a. key points - corners and high response value edge pixels got from simplified SIFT algorithm implementation
b. features - gradient histogram around key points (7x7 area)
c. matching - distance between first and second nearest feature
d. outlier filter - RANSAC filter
Simple patch matcher is slow and not robust to patch distortion so it will not be discussed in details. However, advanced patch matcher is robust to patch distortion and its fast enough to meet task conditions. Here will be presented in more details Advanced Patch Matcher and results got using this algorithm.
Project structure can be found in picture below. Modules kpi_calculation and patch_matcher are core modules which are fully implemented using only numpy. Module patch_matcher_visualisation serves or visualization purposes and it has opencv dependency. Folder reports its generated using KPI module and has KPI reports and plots. Script main_patch_match.py is main function and config folder has yaml configuration file. Folders public nad privite contains data used as training and test data. These folders can be obtaind just by unzipping private and public 7z files.
We can see below pictures of UML diagrams for two major modules of Patch Match algorithm.
1. UML Class Diagram for Patch Match class has base class PatchMatcher which serves as interface and two class implementations SimplePatchMatcher and AdvancedPatchMatcher.
2. UML Class Diagram for generating KPI results has class CalculateKPI which serves for KPI calculation. It is using PatchMatcher class for matching input patches and Report class to generate (save) reports for each input.
For generating example AdvancedPatchMatcher is used. First image is showing template image key points which are got using simplified SIFT algorithm implementation. Second image is showing example of successfully matched patches (with its key points) and matched key points on template image.
Template key points
Example of successfully matched patches
Report class will create results for each input .txt file. It creates 3 plots:
1. Detection statistic
2. Histogram of number of matched points for true detected patches
3. Histogram of number of matched points for miss detected patches
and 2 csv files:
1. Relevant information about true detected patches
2. Relevant information about miss detected patches
Relevant information consist of (columns of csv files):
1. Path to patch (path)
2. Coordinates of estimated and true left corner patch position in template image ([x_match, y_match],[x_expected, y_expected])
3. Number of matched points between patch and template (n_points_matched)
4. Time required to match a patch (time)
Below we can find table with report statistics for all input files from public and private data got using AdvancedPatchMatcher.
From table above we can conclude that AdvancePatchMatcher is working really good. On public (train) data (11200 patches) we got 0.91 accuracy and on private (test) data (17300 patches) we got 0.864 accuracy score. This also implies that we don't have overfitting to train data. The average time to process the patch is around 7 milliseconds which is ok in respect to problem conditions. We can see that we miss detect the patch location in most cases when we can find the match of detected points or we just find 1 point to match. This is happening in most cases due to missing of relevant (some specific) information (edge or corner) in input patch. For example it can be that the path just have grass, or water, or tree so in most of the times we don't have key point at all to match that patch. Some examples of miss detected patch can be found below:
