ImageMatcher< Tag, Allocator > Struct Template Reference

The ImageMatcher structure provides a fast algorithm of searching of similar images. More...

#include <SimdImageMatcher.hpp>

Data Structures
struct	Hash
	The Hash structure is a reduced-image descriptor used for fast matching. More...
struct	Result
	The Result structure is one match of the current image against images earlier added to ImageMatcher. More...

Public Types
enum	HashType {   Hash16x16 ,   Hash32x32 ,   Hash64x64 }
typedef Simd::View< Allocator >	View
typedef std::shared_ptr< Hash >	HashPtr
typedef std::vector< Result >	Results

Public Member Functions
bool	Empty () const
size_t	Size () const
bool	Init (double threshold=0.05, HashType type=Hash16x16, size_t number=0, bool normalized=false)
HashPtr	Create (const View &view, const Tag &tag)
bool	Find (const HashPtr &hash, Results &results)
void	Add (const HashPtr &hash)
void	Skip (const Hash *hash)

Detailed Description

template<class Tag, template< class > class Allocator>
struct Simd::ImageMatcher< Tag, Allocator >

The ImageMatcher structure provides a fast algorithm of searching of similar images.

The matcher compares reduced grayscale copies of images (16x16, 32x32 or 64x64) by their normalized root-mean-square pixel difference. A 4x4 fast hash is used as a cheap pre-filter before the full reduced-image comparison.

Typical usage instantiates ImageMatcher<size_t, Simd::Allocator>, calls Init with a difference threshold, a HashType and an estimated image count, then for each image calls Create (with a tag, usually the source index), Find and Add. Init must be called before Create, Find or Add. Empty() is true before Init.

There are two common patterns:

• Filter unique images: Add only when Find returns false (the first example).
• Report all similar pairs: always Add after Find, and read Result::hash->tag and Result::difference (the second example). Difference is printed as a percentage: difference * 100.

Create converts a non-Gray8 View to Gray8 and resizes it with SimdResizeMethodArea. The number argument of Init selects an internal search structure from the estimated count, the threshold and the normalized flag.

Using example (the filter removes duplicates from the list):

#include "Simd/SimdImageMatcher.hpp"
 
typedef Simd::ImageMatcher<size_t, Simd::Allocator> ImageMatcher;
typedef ImageMatcher::View View;
typedef std::shared_ptr<View> ViewPtr;
typedef std::vector<ViewPtr> ViewPtrs;
 
void FilterDuplicates(const ViewPtrs & src, double threshold, ViewPtrs & dst)
{
    ImageMatcher matcher;
    matcher.Init(threshold, ImageMatcher::Hash16x16, src.size());
    for (size_t i = 0; i < src.size(); ++i)
    {
        ImageMatcher::HashPtr hash = matcher.Create(*src[i], i);
        ImageMatcher::Results results;
        if (!matcher.Find(hash, results))
        {
            matcher.Add(hash);
            dst.push_back(src[i]);
        }
    }
}

Using example (search of similar images in a list of files):

#include "Simd/SimdImageMatcher.hpp"
#include <iostream>
#include <string>
#include <vector>
 
int main()
{
    typedef Simd::ImageMatcher<size_t, Simd::Allocator> ImageMatcher;
    typedef ImageMatcher::View Image;
    typedef std::vector<std::string> Strings;
 
    Strings src;
    // fill src with image paths...
 
    double threshold = 0.05;
    ImageMatcher matcher;
    matcher.Init(threshold, ImageMatcher::Hash32x32, src.size());
    for (size_t i = 0; i < src.size(); ++i)
    {
        Image image;
        if (!image.Load(src[i]))
            continue;
 
        ImageMatcher::HashPtr hash = matcher.Create(image, i);
        ImageMatcher::Results results;
        if (matcher.Find(hash, results))
        {
            for (size_t r = 0; r < results.size(); ++r)
                std::cout << src[i] << " and " << src[results[r].hash->tag]
                          << " , msd = " << results[r].difference * 100 << "%." << std::endl;
        }
        matcher.Add(hash);
    }
    return 0;
}

Member Typedef Documentation

View

typedef Simd::View<Allocator> View

Image type used by Create. Typical usage aliases it as Image.

HashPtr

typedef std::shared_ptr<Hash> HashPtr

A shared pointer to Hash. Create() returns it; Find() and Add() take it.

Results

typedef std::vector<Result> Results

A vector of matches filled by Find.

Member Enumeration Documentation

HashType

enum HashType

Describes size of the reduced grayscale image stored in Hash.

Hash16x16 is typical for filtration of small images. Hash32x32 is typical for a directory-scan search. A larger size is more precise and slower.

Enumerator
Hash16x16	16x16 reduced image size.
Hash32x32	32x32 reduced image size.
Hash64x64	64x64 reduced image size.

Member Function Documentation

Empty()

bool Empty

(

)

const

Checks whether ImageMatcher is not initialized.

Empty() is true before Init and false after a successful Init. Create, Find and Add require a successful Init.

Returns

true if ImageMatcher is not initialized; otherwise false.

Size()

size_t Size

(

)

const

Gets the number of hashes added to ImageMatcher.

The value grows with every Add. It is 0 before Init.

Returns

the number of hashes added to ImageMatcher.

Init()

bool Init	(	double	threshold = 0.05,
		HashType	type = Hash16x16,
		size_t	number = 0,
		bool	normalized = false
	)

Initializes ImageMatcher for search.

Init must be called before Create, Find or Add. It selects an internal search structure from number, threshold and normalized: a linear matcher for small sets, a 1-D hashed matcher when number is greater than 1000 and images are not histogram-normalized, and a 3-D hashed matcher when number is at least 10000 and threshold is less than 0.10.

Typical usage passes src.size() as number (see the examples above). Filtration of small images typically uses Hash16x16. A directory-scan search typically uses Hash32x32 and threshold 0.05.

Parameters

[in]	threshold	- a maximal normalized root-mean-square difference for similar images (range [0, 1]). By default it is equal to 0.05.
[in]	type	- a type of Hash used for matching. By default it is equal to ImageMatcher::Hash16x16.
[in]	number	- an estimated total number of images used for matching. It reserves storage and selects the matcher. By default it is equal to 0.
[in]	normalized	- a flag that the images have a normalized histogram. It changes the 3-D matcher and disables the 1-D matcher. By default it is false.

Returns

true if ImageMatcher was initialized.

Create()

HashPtr Create	(	const View &	view,
		const Tag &	tag
	)

Creates a hash for the given image.

Init must be called first. A non-Gray8 view is converted to Gray8. The gray image is resized to the HashType size with SimdResizeMethodArea and a 4x4 fast hash is built by averaging blocks. Typical usage passes the source index as tag and later reads it from Result::hash->tag.

Parameters

[in]	view	- an input image (any format supported by Simd::Convert to Gray8).
[in]	tag	- a tag of arbitrary type. Typical usage stores a size_t source index.

Returns

a shared pointer to Hash for Find and Add.

Find()

bool Find	(	const HashPtr &	hash,
		Results &	results
	)

Finds all similar images earlier added to ImageMatcher for the given hash.

results is cleared, then filled with every added Hash whose reduced-image difference is not greater than the Init threshold. Typical usage then either adds the hash only when this function returns false (filter unique images) or always adds it and reports results[r].hash->tag together with results[r].difference * 100 (search of all similar pairs).

Hashes marked by Skip() are ignored.

Parameters

[in]	hash	- a shared pointer to the Hash of the current image (from Create).
[out]	results	- a list of found similar images. It is cleared first.

Returns

true if at least one similar image was found.

Add()

void Add

(

const HashPtr &

hash

)

Adds the given hash to ImageMatcher.

After Add the hash can be found by later Find calls. The filter-unique pattern adds only when Find returned false. The report-all-pairs pattern always adds after Find. Size() grows by one.

Parameters

[in]

hash

- a shared pointer to the Hash of the image (from Create).

Skip()

void Skip

(

const Hash *

hash

)

Excludes the given hash from later Find results.

Skip sets an internal flag on the Hash. Compare then ignores that hash (as a query or as a stored candidate) without removing it from ImageMatcher. Typical usage passes Result::hash of an already reported match.

Parameters

[in]

hash

- a pointer to the Hash of the image (for example Result::hash).