① 計算圖像相似度的演算法有哪些
SIM = Structural SIMilarity（結構相似性），這是一種用來評測圖像質量的一種方法。由於人類視覺很容易從圖像中抽取出結構信息,因此計算兩幅圖像結構信息的相似性就可以用來作為一種檢測圖像質量的好壞.
首先結構信息不應該受到照明的影響,因此在計算結構信息時需要去掉亮度信息,即需要減掉圖像的均值;其次結構信息不應該受到圖像對比度的影響,因此計算結構信息時需要歸一化圖像的方差;最後我們就可以對圖像求取結構信息了,通常我們可以簡單地計算一下這兩幅處理後的圖像的相關系數.
然而圖像質量的好壞也受到亮度信息和對比度信息的制約,因此在計算圖像質量好壞時,在考慮結構信息的同時也需要考慮這兩者的影響.通常使用的計算方法如下,其中C1,C2,C3用來增加計算結果的穩定性:
2u(x)u(y) + C1
L(X,Y) = ------------------------ ,u(x), u(y)為圖像的均值
u(x)^2 + u(y)^2 + C1
2d(x)d(y) + C2
C(X,Y) = ------------------------,d(x),d(y)為圖像的方差
d(x)^2 + d(y)^2 + C2
d(x,y) + C3
S(X,Y) = ----------------------,d(x,y)為圖像x,y的協方差
d(x)d(y) + C3
而圖像質量Q = [L(X,Y)^a] x [C(X,Y)^b] x [S(X,Y)^c]，其中a，b，c分別用來控制三個要素的重要性，為了計算方便可以均選擇為1，C1，C2，C3為比較小的數值，通常C1=(K1 x L)^2, C2=(K2 xL)^2, C3 = C2/2, K1 << 1, K2 << 1, L為像素的最大值(通常為255).
希望對你能有所幫助。
② 搜索引擎如何判斷網頁文章的重復度
搜索引擎分詞的方法：
1）正向最大匹配法（由左到右的方向）；
2）逆向最大匹配法（由右到左的方向）；
3）最少切分（使每一句中切出的詞數最小）；
利用分詞方法，把文章中的詞切出來，然後對比，就可以分析出重復度，舉個例子：
逆向最大匹配法
我在小明家吃飯
用逆向最大匹配法來切詞，切的結果為：飯 吃飯 家吃飯 明家吃飯 小明家吃飯 在小明家吃飯 我在小明家吃飯
詞切出來後，拿這個詞去對照，很容易計算出重復度
其他方法可以以此類推，一般都是方法結合使用的。
③ 如何使用opencv中的NCC演算法實現兩幅圖像的相似性判斷
感知哈希演算法(perceptual hash algorithm)，它的作用是對每張圖像生成一個「指紋」(fingerprint)字元串，然後比較不同圖像的指紋。結果越接近，就說明圖像越相似。
實現步驟：
1. 縮小尺寸：將圖像縮小到8*8的尺寸，總共64個像素。這一步的作用是去除圖像的細節，只保留結構/明暗等基本信息，摒棄不同尺寸/比例帶來的圖像差異；
2. 簡化色彩：將縮小後的圖像，轉為64級灰度，即所有像素點總共只有64種顏色；
3. 計算平均值：計算所有64個像素的灰度平均值；
4. 比較像素的灰度：將每個像素的灰度，與平均值進行比較，大於或等於平均值記為1，小於平均值記為0；
5. 計算哈希值：將上一步的比較結果，組合在一起，就構成了一個64位的整數，這就是這張圖像的指紋。組合的次序並不重要，只要保證所有圖像都採用同樣次序就行了；
6. 得到指紋以後，就可以對比不同的圖像，看看64位中有多少位是不一樣的。在理論上，這等同於」漢明距離」(Hamming distance,在資訊理論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數)。如果不相同的數據位數不超過5，就說明兩張圖像很相似；如果大於10，就說明這是兩張不同的圖像。
以上內容摘自：http://www.ruanyifeng.com/blog/2011/07/principle_of_similar_image_search.html
下面是用OpenCV實現的測試代碼：
[cpp] view plainprint?
string strSrcImageName = "src.jpg";
cv::Mat matSrc, matSrc1, matSrc2;
matSrc = cv::imread(strSrcImageName, CV_LOAD_IMAGE_COLOR);
CV_Assert(matSrc.channels() == 3);
cv::resize(matSrc, matSrc1, cv::Size(357, 419), 0, 0, cv::INTER_NEAREST);
//cv::flip(matSrc1, matSrc1, 1);
cv::resize(matSrc, matSrc2, cv::Size(2177, 3233), 0, 0, cv::INTER_LANCZOS4);
cv::Mat matDst1, matDst2;
cv::resize(matSrc1, matDst1, cv::Size(8, 8), 0, 0, cv::INTER_CUBIC);
cv::resize(matSrc2, matDst2, cv::Size(8, 8), 0, 0, cv::INTER_CUBIC);
cv::cvtColor(matDst1, matDst1, CV_BGR2GRAY);
cv::cvtColor(matDst2, matDst2, CV_BGR2GRAY);
int iAvg1 = 0, iAvg2 = 0;
int arr1[64], arr2[64];
for (int i = 0; i < 8; i++) {
uchar* data1 = matDst1.ptr<uchar>(i);
uchar* data2 = matDst2.ptr<uchar>(i);
int tmp = i * 8;
for (int j = 0; j < 8; j++) {
int tmp1 = tmp + j;
arr1[tmp1] = data1[j] / 4 * 4;
arr2[tmp1] = data2[j] / 4 * 4;
iAvg1 += arr1[tmp1];
iAvg2 += arr2[tmp1];
}
}
iAvg1 /= 64;
iAvg2 /= 64;
for (int i = 0; i < 64; i++) {
arr1[i] = (arr1[i] >= iAvg1) ? 1 : 0;
arr2[i] = (arr2[i] >= iAvg2) ? 1 : 0;
}
int iDiffNum = 0;
for (int i = 0; i < 64; i++)
if (arr1[i] != arr2[i])
++iDiffNum;
cout<<"iDiffNum = "<<iDiffNum<<endl;
if (iDiffNum <= 5)
cout<<"two images are very similar!"<<endl;
else if (iDiffNum > 10)
cout<<"they are two different images!"<<endl;
else
cout<<"two image are somewhat similar!"<<endl;
string strSrcImageName = "src.jpg";
cv::Mat matSrc, matSrc1, matSrc2;
matSrc = cv::imread(strSrcImageName, CV_LOAD_IMAGE_COLOR);
CV_Assert(matSrc.channels() == 3);
cv::resize(matSrc, matSrc1, cv::Size(357, 419), 0, 0, cv::INTER_NEAREST);
//cv::flip(matSrc1, matSrc1, 1);
cv::resize(matSrc, matSrc2, cv::Size(2177, 3233), 0, 0, cv::INTER_LANCZOS4);
cv::Mat matDst1, matDst2;
cv::resize(matSrc1, matDst1, cv::Size(8, 8), 0, 0, cv::INTER_CUBIC);
cv::resize(matSrc2, matDst2, cv::Size(8, 8), 0, 0, cv::INTER_CUBIC);
cv::cvtColor(matDst1, matDst1, CV_BGR2GRAY);
cv::cvtColor(matDst2, matDst2, CV_BGR2GRAY);
int iAvg1 = 0, iAvg2 = 0;
int arr1[64], arr2[64];
for (int i = 0; i < 8; i++) {
uchar* data1 = matDst1.ptr<uchar>(i);
uchar* data2 = matDst2.ptr<uchar>(i);
int tmp = i * 8;
for (int j = 0; j < 8; j++) {
int tmp1 = tmp + j;
arr1[tmp1] = data1[j] / 4 * 4;
arr2[tmp1] = data2[j] / 4 * 4;
iAvg1 += arr1[tmp1];
iAvg2 += arr2[tmp1];
}
}
iAvg1 /= 64;
iAvg2 /= 64;
for (int i = 0; i < 64; i++) {
arr1[i] = (arr1[i] >= iAvg1) ? 1 : 0;
arr2[i] = (arr2[i] >= iAvg2) ? 1 : 0;
}
int iDiffNum = 0;
for (int i = 0; i < 64; i++)
if (arr1[i] != arr2[i])
++iDiffNum;
cout<<"iDiffNum = "<<iDiffNum<<endl;
if (iDiffNum <= 5)
cout<<"two images are very similar!"<<endl;
else if (iDiffNum > 10)
cout<<"they are two different images!"<<endl;
else
cout<<"two image are somewhat similar!"<<endl;
④ 終於知道怎麼判斷字元串相似度了
一直不理解，為什麼要計算兩個字元串的相似度呢。什麼叫做兩個字元串的相似度。經常看別人的博客，碰到比較牛的人，然後就翻了翻，終於找到了比較全面的答案和為什麼要計算字元串相似度的解釋。因為搜索引擎要把通過爬蟲抓取的頁面給記錄下來，那麼除了通過記錄url是否被訪問過之外，還可以這樣，比較兩個頁面的相似度，因為不同的url中可能記錄著相同的內容，這樣，就不必再次記錄到搜索引擎的存儲空間中去了。還有，大家畢業的時候都寫過論文吧，我們論文的查重系統相信也會採用計算兩個字元串相似度這個概念。
以下敘述摘自編程之美一書：
許多程序會大量使用字元串。對於不同的字元串，我們希望能夠有辦法判斷其相似程序。我們定義一套操作方法來把兩個不相同的字元串變得相同，具體的操作方法為：
1.修改一個字元（如把「a」替換為「b」）;
2.增加一個字元（如把「abdd」變為「aebdd」）;
3.刪除一個字元（如把「travelling」變為「traveling」）;
比如，對於「abcdefg」和「abcdef」兩個字元串來說，我們認為可以通過增加/減少一個「g」的方式來達到目的。上面的兩種方案，都僅需要一 次 。把這個操作所需要的次數定義為兩個字元串的距離，而相似度等於「距離+1」的倒數。也就是說，「abcdefg」和「abcdef」的距離為1，相似度 為1/2=0.5。
給定任意兩個字元串，你是否能寫出一個演算法來計算它們的相似度呢？
原文的分析與解法
不難看出，兩個字元串的距離肯定不超過它們的長度之和（我們可以通過刪除操作把兩個串都轉化為空串）。雖然這個結論對結果沒有幫助，但至少可以知道，任意兩個字元串的距離都是有限的。我們還是就住集中考慮如何才能把這個問題轉化成規模較小的同樣的子問題。如果有兩個串A=xabcdae和B=xfdfa，它們的第一個字元是 相同的，只要計算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距離就可以了。但是如果兩個串的第一個字元不相同，那麼可以進行 如下的操作（lenA和lenB分別是A串和B串的長度）。
1.刪除A串的第一個字元，然後計算A[2,...,lenA]和B[1,...,lenB]的距離。
2.刪除B串的第一個字元，然後計算A[1,...,lenA]和B[2,...,lenB]的距離。
3.修改A串的第一個字元為B串的第一個字元，然後計算A[2,...,lenA]和B[2,...,lenB]的距離。
4.修改B串的第一個字元為A串的第一個字元，然後計算A[2,...,lenA]和B[2,...,lenB]的距離。
5.增加B串的第一個字元到A串的第一個字元之前，然後計算A[1,...,lenA]和B[2,...,lenB]的距離。
6.增加A串的第一個字元到B串的第一個字元之前，然後計算A[2,...,lenA]和B[1,...,lenB]的距離。
在這個題目中，我們並不在乎兩個字元串變得相等之後的字元串是怎樣的。所以，可以將上面的6個操作合並為：
1.一步操作之後，再將A[2,...,lenA]和B[1,...,lenB]變成相字元串。
2.一步操作之後，再將A[2,...,lenA]和B[2,...,lenB]變成相字元串。
3.一步操作之後，再將A[1,...,lenA]和B[2,...,lenB]變成相字元串。
通過以上1和6,2和5，3和4的結合操作，最後兩個字元串每個對應的字元會相同，但是這三種操作產生的最終的兩個字元串是不一樣的。我們不知道通過上述的三種結合那種使用的操作次數是最少的。所以我們要比較操作次數來求得最小值。