Picture similarity judgement

picture_hash.cpp

/**
 * 图像匹配 - 在另一附图中找到匹配部分(小图是大图中的一部分)
 * 1. 归一化互相关算法 - 简单, 但是需要尺寸不变, 应用较少
 * 2. SIFT(Scale-invariant feature transform, 尺度不变特征转换) - 对形变支持好
 *
 * 图像相似度识别 - 给出两幅图的相似程度
 * 1. 颜色直方图计算方法
 *    缺点: 按照颜色的全局分布来看的，无法描述颜色的局部分布和色彩所处的位置。
 * 2. 图像指纹与汉明距离 (图像相似度比较的核心思想)
 *    aHash - 不够精确，更适合搜索缩略图
 *    pHash - 能识别图片变形, 速度慢
 *    dHash - 相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。
 * 3. 内容特征法
 *    不能处理变形的情况. 核心思想是找出图像中的轮廓
 *
 * 参考文章地址:
 * https://segmentfault.com/a/1190000004467183
 * http://www.ruanyifeng.com/blog/2011/07/principle_of_similar_image_search.html
 * http://www.ruanyifeng.com/blog/2013/03/similar_image_search_part_ii.html
 */
#include <iostream>
#include <opencv2/opencv.hpp>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <vector>

using namespace cv;
using namespace std;

int  calc_hamming_distance(vector<uint8_t> &hash1, vector<uint8_t> &hash2)
{
	if (hash1.size() != hash2.size())
		return -1;
	int hamming_distance = 0;
	for (size_t i = 0; i < hash1.size(); ++i)
		if (hash1[i] != hash2[i])
			hamming_distance++;

	return hamming_distance;
}

/**
 * 先异或, 然后求结果的二进制中1的个数
 */
int  calc_hamming_distance_uint64(uint64_t a, uint64_t b)
{
	uint64_t diff = a ^ b;
	int dist = 0;
	while (diff) {
		diff &= (diff - 1);
		dist++;
	}
	return dist;
}

/**
 * 图像指纹-平均哈希法(aHash)
 * 平均哈希算法过于严格，不够精确，更适合搜索缩略图
 */
void calc_ahash_code(Mat &img, vector<uint8_t> &ahash, Size size = Size(8, 8))
{
	Mat small_img(size, img.type());
	Mat gray_img;
	resize(img, small_img, small_img.size());
	cvtColor(small_img, gray_img, CV_BGR2GRAY);
	ahash.clear();
	uint32_t sum = 0;
	for(int x = 0; x < gray_img.rows; ++x) {
		for(int y = 0; y < gray_img.cols; ++y) {
			ahash.push_back(gray_img.at<uint8_t>(x, y));
			sum += gray_img.at<uint8_t>(x, y);
		}
	}
	double average = (double)sum / ahash.size();
	vector<uint8_t>::iterator it;
	for (it = ahash.begin(); it != ahash.end(); ++it)
		*it = (*it > average) ? 1 : 0;
}

/*
 * calculate 64 bit image fingerprint based on aHash algorithm
 */
uint64_t calc_ahash_uint64(Mat &img)
{
	Mat small_img(8, 8, img.type());
	Mat gray_img;
	resize(img, small_img, small_img.size());
	cvtColor(small_img, gray_img, CV_BGR2GRAY);
	vector<uint8_t> ahash;
	uint32_t sum = 0;
	for(int x = 0; x < gray_img.rows; ++x) {
		for(int y = 0; y < gray_img.cols; ++y) {
			ahash.push_back(gray_img.at<uint8_t>(x, y));
			sum += gray_img.at<uint8_t>(x, y);
		}
	}
	double average = (double)sum / ahash.size();
	uint64_t fingerprint = 0;
	vector<uint8_t>::iterator it;
	for (it = ahash.begin(); it != ahash.end(); ++it) {
		fingerprint <<= 1;
		if (*it > average)
			fingerprint++;
	}
	return fingerprint;
}

/**
 * 图像指纹-dHash
 * 相比pHash，dHash的速度要快的多，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。
 */
void calc_dhash_code(Mat &img, vector<uint8_t> &dhash, Size size = Size(9, 8))
{
	Mat small_img(size, img.type());
	Mat gray_img;
	resize(img, small_img, small_img.size());
	cvtColor(small_img, gray_img, CV_BGR2GRAY);
	dhash.clear();
	for(int x = 1; x < gray_img.rows; ++x) {
		for(int y = 1; y < gray_img.cols; ++y) {
			if (gray_img.at<uint8_t>(x, y) > gray_img.at<uint8_t>(x - 1, y))
				dhash.push_back(1);
			else
				dhash.push_back(0);
		}
	}
}

/*
 * calculate 64 bit image fingerprint based on aHash algorithm
 */
uint64_t calc_dhash_uint64(Mat &img)
{
	Mat small_img(9, 8, img.type());
	Mat gray_img;
	resize(img, small_img, small_img.size());
	cvtColor(small_img, gray_img, CV_BGR2GRAY);
	uint64_t fingerprint = 0;
	for(int x = 1; x < gray_img.rows; ++x) {
		for(int y = 1; y < gray_img.cols; ++y) {
			fingerprint <<= 1;
			if (gray_img.at<uint8_t>(x, y) > gray_img.at<uint8_t>(x - 1, y))
				fingerprint++;
		}
	}
	return fingerprint;
}

void get_image_contour(Mat &img, vector<uint8_t> &feature, Size size = Size(64, 64))
{
	Mat small_img(size, img.type());
	Mat gray_img;
	resize(img, small_img, small_img.size());
	cvtColor(small_img, gray_img, CV_BGR2GRAY);
	vector<double> vect_category_diff; // 类间差异

	int scale = gray_img.rows * gray_img.cols;

	for (int threshold = 1; threshold < 255; ++threshold) {
		vector<uint8_t> vect_1, vect_2;
		uint8_t pix;
		for (int x = 0; x < gray_img.rows; ++x) {
			for (int y = 0; y < gray_img.cols; ++y) {
				pix = gray_img.at<uint8_t>(x, y);
				if (threshold > pix)
					vect_1.push_back(pix);
				else
					vect_2.push_back(pix);
			}
		}
		if (vect_1.size() == 0 || vect_2.size() == 0) {
			vect_category_diff.push_back(0);
			continue;
		}
		double w1 = (double)vect_1.size() / scale;
		double w2 = (double)vect_2.size() / scale;
		int s1 = std::accumulate(vect_1.begin() , vect_1.end() , 0);
		int s2 = std::accumulate(vect_2.begin() , vect_2.end() , 0);
		double u1 = (double)s1 / vect_1.size();
		double u2 = (double)s2 / vect_2.size();
		vect_category_diff.push_back(w1 * w2 * pow((u1 - u2), 2));
	}
	double max_cd = 0;
	int best_threshold = 0;
	for (size_t i = 0; i < 256; ++i) {
		if (vect_category_diff[i] > max_cd) {
			best_threshold = i;
			max_cd = vect_category_diff[i];
		}
	}

	feature.clear();
	for(int x = 1; x < gray_img.rows; ++x) {
		for(int y = 1; y < gray_img.cols; ++y) {
			if (best_threshold > gray_img.at<uint8_t>(x, y)) {
				gray_img.at<uint8_t>(x, y) = 0;
				feature.push_back(0);
			} else {
				gray_img.at<uint8_t>(x, y) = 255;
				feature.push_back(1);
			}
		}
	}
}

/**
 * Image Similarity Identification Based on Image Fingerprint
 * use aHash, dHash, phash, image contour
 */
void isi_fingerprint(Mat &img1, Mat &img2)
{
	uint64_t fp1 = calc_ahash_uint64(img1);
	uint64_t fp2 = calc_ahash_uint64(img2);
	int ahash_dist = calc_hamming_distance_uint64(fp1, fp2);
	cout << "aHash Hamming Distance: " << ahash_dist << endl;
	fp1 = calc_dhash_uint64(img1);
	fp2 = calc_dhash_uint64(img2);
	int dhash_dist = calc_hamming_distance_uint64(fp1, fp2);
	cout << "dHash Hamming Distance: " << dhash_dist << endl;
	vector<uint8_t> feature1, feature2;
	get_image_contour(img1, feature1);
	get_image_contour(img2, feature2);
	int contour_dist = calc_hamming_distance(feature1, feature2);
	cout << "contour Hamming Distance: " << contour_dist / (feature1.size() / 64) << endl;
}

int main(int argc, char** argv )
{
	if ( argc != 3 ) {
		printf("usage: DisplayImage <Image_Path1> <Image_Path2>\n");
		return -1;
	}

	Mat img1 = imread( argv[1], 1 );
	Mat img2 = imread( argv[2], 1 );
	isi_fingerprint(img1, img2);
	return 0;
}