列舉圖的相關演算法

① FFT與圖像最大互相關演算法

圖像 互相關演算法 就是計算 兩幅圖像 相關系數 的 方法，常用於圖像匹配。例如同一目標物，被拍了兩張照片，要把兩張照片「對齊",可以給出不同的對位，計旅野算相關系數，相關系數最大的對位就是最佳對齊。

相關系數計算和褶積計算可以用到傅里葉變換。
FFT 是快速傅里葉變換。FFT 要求 離散 點 為 2 的 整次方點，例如1024，2048....,它利用系數的對稱性，省去大量計算時間。

關於圖像匹配互相關演算法，網上好像很多。FFT 是老技術，程序也能找到。

（隨便找了一談鎮敗篇）圖像匹配最大互相關演算法的專用ASIC硬體實現方式研究 見含顫參考資料。

② 數學建模演算法有哪些

1. 蒙特卡羅演算法。 該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，同時可以通過模擬來檢驗自己模型的正確性，幾乎是比賽時必用的方法。
2. 數據擬合、參數估計、插值等數據處理演算法。 比賽中通常會遇到大量的數據需要處理，而處理數據的關鍵就在於這些演算法，通常使用MATLAB 作為工具。
3. 線性規劃、整數規劃、多元規劃、二次規劃等規劃類演算法。 建模競賽大多數問題屬於最優化問題，很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、Lingo 軟體求解。
4. 圖論演算法。 這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉及到圖論的問題可以用這些方法解決，需要認真准備。
5. 動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法。 這些演算法是演算法設計中比較常用的方法，競賽中很多場合會用到。
6. 最優化理論的三大非經典演算法：模擬退火演算法、神經網路演算法、遺傳演算法。 這些問題是用來解決一些較困難的最優化問題的，對於有些問題非常有幫助，但是演算法的實現比較困難，需慎重使用。
7. 網格演算法和窮舉法。 兩者都是暴力搜索最優點的演算法，在很多競賽題中有應用，當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。
8. 一些連續數據離散化方法。 很多問題都是實際來的，數據可以是連續的，而計算機只能處理離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的。
9. 數值分析演算法。 如果在比賽中採用高級語言進行編程的話，那些數值分析中常用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用。
10. 圖象處理演算法。 賽題中有一類問題與圖形有關，即使問題與圖形無關，論文中也會需要圖片來說明問題，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用MATLAB 進行處理。
以下將結合歷年的競賽題，對這十類演算法進行詳細地說明。
以下將結合歷年的競賽題，對這十類演算法進行詳細地說明。
2 十類演算法的詳細說明
2.1 蒙特卡羅演算法
大多數建模賽題中都離不開計算機模擬，隨機性模擬是非常常見的演算法之一。
舉個例子就是97 年的A 題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優的組合方案將要面對著的是一個極其復雜的公式和108 種容差選取方案，根本不可能去求解析解，那如何去找到最優的方案呢？隨機性模擬搜索最優方案就是其中的一種方法，在每個零件可行的區間中按照正態分布隨機的選取一個標定值和選取一個容差值作為一種方案，然後通過蒙特卡羅演算法模擬出大量的方案，從中選取一個最佳的。另一個例子就是去年的彩票第二問，要求設計一種更好的方案，首先方案的優劣取決於很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機模擬模擬。
2.2 數據擬合、參數估計、插值等演算法
數據擬合在很多賽題中有應用，與圖形處理有關的問題很多與擬合有關系，一個例子就是98 年美國賽A 題，生物組織切片的三維插值處理，94 年A 題逢山開路，山體海拔高度的插值計算，還有吵的沸沸揚揚可能會考的「非典」問題也要用到數據擬合演算法，觀察數據的走向進行處理。此類問題在MATLAB中有很多現成的函數可以調用，熟悉MATLAB，這些方法都能游刃有餘的用好。
2.3 規劃類問題演算法
競賽中很多問題都和數學規劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件、幾個函數表達式作為目標函數的問題，遇到這類問題，求解就是關鍵了，比如98年B 題，用很多不等式完全可以把問題刻畫清楚，因此列舉出規劃後用Lindo、Lingo 等軟體來進行解決比較方便，所以還需要熟悉這兩個軟體。
2.4 圖論問題
98 年B 題、00 年B 題、95 年鎖具裝箱等問題體現了圖論問題的重要性，這類問題演算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個演算法都應該實現一遍，否則到比賽時再寫就晚了。
2.5 計算機演算法設計中的問題
計算機演算法設計包括很多內容：動態規劃、回溯搜索、分治演算法、分支定界。比如92 年B 題用分枝定界法，97 年B 題是典型的動態規劃問題，此外98 年B 題體現了分治演算法。這方面問題和ACM 程序設計競賽中的問題類似，推薦看一下《計算機演算法設計與分析》（電子工業出版社）等與計算機演算法有關的書。
2.6 最優化理論的三大非經典演算法
這十幾年來最優化理論有了飛速發展，模擬退火法、神經網路、遺傳演算法這三類演算法發展很快。近幾年的賽題越來越復雜，很多問題沒有什麼很好的模型可以借鑒，於是這三類演算法很多時候可以派上用場，比如：97 年A 題的模擬退火演算法，00 年B 題的神經網路分類演算法，象01 年B 題這種難題也可以使用神經網路，還有美國競賽89 年A 題也和BP 演算法有關系，當時是86 年剛提出BP 演算法，89 年就考了，說明賽題可能是當今前沿科技的抽象體現。03 年B 題伽馬刀問題也是目前研究的課題，目前演算法最佳的是遺傳演算法。
2.7 網格演算法和窮舉演算法
網格演算法和窮舉法一樣，只是網格法是連續問題的窮舉。比如要求在N 個變數情況下的最優化問題，那麼對這些變數可取的空間進行采點，比如在[a; b] 區間內取M +1 個點，就是a; a+(b-a)/M; a+2 (b-a)/M; …… ; b 那麼這樣循環就需要進行(M + 1)N 次運算，所以計算量很大。比如97 年A 題、99 年B 題都可以用網格法搜索，這種方法最好在運算速度較快
的計算機中進行，還有要用高級語言來做，最好不要用MATLAB 做網格，否則會算很久的。窮舉法大家都熟悉，就不說了。
2.8 一些連續數據離散化的方法
大部分物理問題的編程解決，都和這種方法有一定的聯系。物理問題是反映我們生活在一個連續的世界中，計算機只能處理離散的量，所以需要對連續量進行離散處理。這種方法應用很廣，而且和上面的很多演算法有關。事實上，網格演算法、蒙特卡羅演算法、模擬退火都用了這個思想。
2.9 數值分析演算法
這類演算法是針對高級語言而專門設的，如果你用的是MATLAB、Mathematica，大可不必准備，因為象數值分析中有很多函數一般的數學軟體是具備的。
2.10 圖象處理演算法
01 年A 題中需要你會讀BMP 圖象、美國賽98 年A 題需要你知道三維插值計算，03 年B 題要求更高，不但需要編程計算還要進行處理，而數模論文中也有很多圖片需要展示，因此圖象處理就是關鍵。做好這類問題，重要的是把MATLAB 學好，特別是圖象處理的部分。

③ 圖像分割演算法總結

       圖像處理的很多任務都離不開圖像分割。因為圖像分割在cv中實在太重要(有用)了，就先把圖像分割的常用演算法做個總結。

        接觸機器學習和深度學習時間已經不短了。期間看過各種相關知識但從未總結過。本文過後我會盡可能詳細的從工程角度來總結，從傳統機器學習演算法，傳統計算機視覺庫演算法到深度學習目前常用演算法和論文，以及模型在各平台的轉化，量化，服務化部署等相關知識總結。

        圖像分割常用演算法大致分為下面幾類。由於圖像的能量范函，邊緣追蹤等方法的效果往往只能解決特定問題，效果並不理想，這里不再闡述。當然二值化本身也可以分割一些簡單圖像的。但是二值化演算法較多，我會專門做一個文章來總結。這里不再贅述。

        1.基於邊緣的圖像分割演算法：

            有利用圖像梯度的傳統演算法運算元的sobel，roberts，prewitt,拉普拉斯以及canny等。

            這些演算法的基本思想都是採用合適的卷積運算元，對圖像做卷積。從而求出圖像對應的梯度圖像。(至於為什麼通過如圖1這樣的運算元卷積，即可得到圖像的梯度圖像，請讀者復習下卷積和倒數的概念自行推導)由於圖像的邊緣處往往是圖像像素差異較大，梯度較大地方。因此我們通過合適的卷積核得到圖像的梯度圖像，即得到了圖像的邊緣圖像。至於二階運算元的推導，與一階類似。優點：傳統運算元梯度檢測，只需要用合適的卷積核做卷積，即可快速得出對應的邊緣圖像。缺點：圖像邊緣不一定準確，復雜圖像的梯度不僅僅出現在圖像邊緣，可以能出現在圖像內部的色彩和紋理上。

             也有基於深度學習方法hed，rcf等。由於這類網路都有同一個比較嚴重的缺陷，這里只舉例hed網路。hed是基於FCN和VGG改進，同時引出6個loss進行優化訓練，通過多個層輸出不同scale的粒度的邊緣，然後通過一個訓練權重融合各個層的邊緣結果。hed網路結構如下：

可以得到一個比較完整的梯度圖像，可參考github的hed實現。優點：圖像的梯度細節和邊緣完整性，相比傳統的邊緣運算元要好很多。但是hed對於邊緣的圖像內部的邊緣並不能很好的區分。當然我們可以自行更改loss來嘗試只擬合外部的圖像邊緣。但最致命的問題在於，基於vgg的hed的網路表達能力有限，對於圖像和背景接近，或者圖像和背景部分相融的圖片，hed似乎就有點無能為力了。

        2.基於區域分割的演算法：

            區域分割比較常用的如傳統的演算法結合遺傳演算法，區域生長演算法，區域分裂合並，分水嶺演算法等。這里傳統演算法的思路是比較簡單易懂的，如果有無法理解的地方，歡迎大家一起討論學習。這里不再做過多的分析。

            基於區域和語意的深度學習分割演算法，是目前圖像分割成果較多和研究的主要方向。例如FCN系列的全卷積網路，以及經典的醫學圖像分割常用的unet系列，以及rcnn系列發展下的maskrcnn，以及18年底的PAnet。基於語意的圖像分割技術，無疑會成為圖像分割技術的主流。

            其中，基於深度學習語意的其他相關演算法也可以間接或直接的應用到圖像分割。如經典的圖像matting問題。18年又出現了許多非常優秀的演算法和論文。如Deep-Image-Matting，以及效果非常優秀的MIT的 semantic soft segmentation(sss).

            基於語意的圖像分割效果明顯要好於其他的傳統演算法。我在解決圖像分割的問題時，首先嘗試用了hed網路。最後的效果並不理想。雖然也參考github，做了hed的一些fine-tune,但是還是上面提到的原因，在我多次嘗試後，最終放棄。轉而適用FCN系列的網路。但是fcn也無法解決圖像和背景相融的問題。圖片相融的分割，感覺即需要大的感受野，又需要未相融部分原圖像細節，所以單原FCN的網路，很難做出准確的分割。中間還測試過很多其他相關的網路，但都效果不佳。考慮到感受野和原圖像細節，嘗試了resnet和densenet作為圖像特徵提取的底層。最終我測試了unet系列的網路：

                unet的原始模型如圖所示。在自己拍照爬蟲等手段採集了將近1000張圖片。去掉了圖片質量太差的，圖片內容太過類似的。爬蟲最終收集160多張，自己拍照收集200張圖片後，又用ps手動p了邊緣圖像，採用圖像增強變換，大約有300*24張圖片。原生unet網路的表現比較一般。在將unet普通的卷積層改為resnet後，網路的表達能力明顯提升。在將resnet改為resnet101，此時，即使對於部分相融的圖像，也能較好的分割了。但是unet的模型體積已經不能接受。

                在最後階段，看到maskrcnn的實例分割。maskrcnn一路由rcnn,fasterrcnn發展過來。於是用maskrcnn來加入自己的訓練數據和label圖像進行訓練。maskrcnn的結果表現並不令人滿意，對於邊緣的定位，相比於其他演算法，略顯粗糙。在產品應用中，明顯還不合適。                

        3.基於圖的分割演算法

            基於深度學習的deepgrab,效果表現並不是十分理想。deepgrab的git作者backbone採用了deeplabv2的網路結構。並沒有完全安裝原論文來做。

論文原地址參考： https://arxiv.org/pdf/1707.00243.pdf

整體結構類似於encode和decoder。並沒有太仔細的研究，因為基於resent101的結構，在模型體積，速度以及deeplab的分割精度上，都不能滿足當前的需求。之前大致總結過計算機視覺的相關知識點，既然目前在討論移動端模型，那後面就分模塊總結下移動端模型的應用落地吧。

由於時間實在有限。這里並沒有針對每個演算法進行詳細的講解。後續我會從基礎的機器學習演算法開始總結。

④ 程序員必須掌握哪些演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)

⑤ 求有向圖兩個頂點間的最短路徑的方法，用簡單語言或舉例描述。

在交通網路中，常常會提出許多這樣的問題：兩地之間是否有路相通？在有多條通路的情況下，哪一條最近？哪一條花費最少等。交通網路可以用帶權圖表示，圖中頂點表示域鎮，邊表示兩城之間的道路，邊上權值可表示兩城鎮間的距離，交通費用或途中所需的時間等。
以上提出的問題就是帶權圖中求最短路徑的問題，即求兩個頂點間長度最短的路徑。
最短路徑問題的提法很多。在這里僅討論單源最短路徑問題：即已知有向圖(帶權)，我們希望找出從某個源點S∈V到G中其餘各頂點的最短路徑。
例如：下圖(有向圖G14)，假定以v1為源點，則其它各頂點的最短路徑如下表所示：

圖 G14

從有向圖可看出，頂點v1到v4的路徑有3條：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路徑長度分別為：15,20和10。因此v1到v4的最短路徑為(v1,v3,v2,v4 )。
為了敘述方便，我們把路徑上的開始點稱為源點，路徑的最後一個頂點為終點。
那麼，如何求得給定有向圖的單源最短路徑呢？迪傑斯特拉(Dijkstra)提出按路徑長度遞增產生諸頂點的最短路徑演算法，稱之為迪傑斯特拉演算法。
迪傑斯特拉演算法求最短路徑的實現思想是：設有向圖G=(V,E)，其中，V={1,2,…,n}，cost是表示G的鄰接矩陣，cost[i][j] 表示有向邊<i,j>的權。若不存在有向邊<i,j>，則cost[i][j]的權為無窮大(這里取值為32767)。設S是一個集合，其中的每個元素表示一個頂點，從源點到這些頂點的最短距離已經求出。設頂點v1為源點，集合S的初態只包含頂點v1。數組dist記錄從源點到其他各頂點當前的最短距離，其初值為dist[i]=cost[v1][i]，i=2,…,n。從S之外的頂點集合V-S 中選出一個頂點w，使dist[w]的值最小。於是從源點到達w只通過S 中的頂點，把w加入集合S中調整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的dist[v] 和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復上述過程，直到S中包含V中其餘頂點的最短路徑。
最終結果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數組dist記錄了從源點到 V中其餘各頂點之間的最短路徑，path是最短路徑的路徑數組，其中path[i] 表示從源點到頂點i之間的最短路徑的前驅頂點。

⑥ 圖片相似度判斷

1. https://zhuanlan.hu.com/p/68215900
為了得到兩張相似的圖片，在這里通過以下幾種簡單的計算方式來計算圖片的相似度：
直方圖計算圖片的相似度
通過哈希值，漢明距離計算
通過圖片的餘弦距離計算
通過圖片結構度量計算

二、哈希演算法計算圖片的相似度
圖像指紋：

圖像指紋和人的指紋一樣，是身份的象徵，而圖像指紋簡單點來講，就是將圖像按照一定的哈希演算法，經過運算後得出的一組二進制數字。

漢明距離：

假如一組二進制數據為101，另外一組為111，那麼顯然把第一組的第二位數據0改成1就可以變成第二組數據111，所以兩組數據的漢明距離就為1。簡單點說，漢明距離就是一組二進制數據變成另一組數據所需的步驟數，顯然，這個數值可以衡量兩張圖片的差異，漢明距離越小，則代表相似度越高。漢明距離為0，即代表兩張圖片完全一樣。

感知哈希演算法是一類演算法的總稱，包括aHash、pHash、dHash。顧名思義，感知哈希不是以嚴格的方式計算Hash值，而是以更加相對的方式計算哈希值，因為「相似」與否，就是一種相對的判定。

幾種hash值的比較：

aHash：平均值哈希。速度比較快，但是常常不太精確。
pHash：感知哈希。精確度比較高，但是速度方面較差一些。
dHash：差異值哈希。精確度較高，且速度也非常快

該演算法是基於比較灰度圖每個像素與平均值來實現。

aHash的hanming距離步驟：

先將圖片壓縮成8*8的小圖
將圖片轉化為灰度圖
計算圖片的Hash值，這里的hash值是64位，或者是32位01字元串
將上面的hash值轉換為16位的
通過hash值來計算漢明距離

def ahash(image):
# 將圖片縮放為8*8的
image = cv2.resize(image, (8, 8), interpolation=cv2.INTER_CUBIC)
# 將圖片轉化為灰度圖
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
# s為像素和初始灰度值，hash_str為哈希值初始值
s = 0
# 遍歷像素累加和
for i in range(8):
for j in range(8):
s = s + gray[i, j]
# 計算像素平均值
avg = s / 64
# 灰度大於平均值為1相反為0，得到圖片的平均哈希值，此時得到的hash值為64位的01字元串
ahash_str = ''
for i in range(8):
for j in range(8):
if gray[i, j] > avg:
ahash_str = ahash_str + '1'
else:
ahash_str = ahash_str + '0'
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(ahash_str[i: i + 4], 2))
# print("ahash值：",result)
return result
2.感知哈希演算法（pHash）：

均值哈希雖然簡單，但是受均值影響大。如果對圖像進行伽馬校正或者進行直方圖均值化都會影響均值，從而影響哈希值的計算。所以就有人提出更健壯的方法，通過離散餘弦（DCT）進行低頻提取。

離散餘弦變換（DCT）是種圖像壓縮演算法，它將圖像從像素域變換到頻率域。然後一般圖像都存在很多冗餘和相關性的，所以轉換到頻率域之後，只有很少的一部分頻率分量的系數才不為0，大部分系數都為0（或者說接近於0）。Phash哈希演算法過於嚴格，不夠精確，更適合搜索縮略圖，為了獲得更精確的結果可以選擇感知哈希演算法，它採用的是DCT（離散餘弦變換）來降低頻率的方法。

pHash的hanming距離步驟：

縮小圖片：32 * 32是一個較好的大小，這樣方便DCT計算轉化為灰度圖
計算DCT：利用Opencv中提供的dct()方法，注意輸入的圖像必須是32位浮點型，所以先利用numpy中的float32進行轉換
縮小DCT：DCT計算後的矩陣是32 * 32，保留左上角的8 * 8，這些代表的圖片的最低頻率
計算平均值：計算縮小DCT後的所有像素點的平均值。
進一步減小DCT：大於平均值記錄為1，反之記錄為0.
得到信息指紋：組合64個信息位，順序隨意保持一致性。
最後比對兩張圖片的指紋，獲得漢明距離即可。

def phash(path):
# 載入並調整圖片為32*32的灰度圖片
img = cv2.imread(path)
img1 = cv2.resize(img, (32, 32),cv2.COLOR_RGB2GRAY)
​
# 創建二維列表
h, w = img.shape[:2]
vis0 = np.zeros((h, w), np.float32)
vis0[:h, :w] = img1
​
# DCT二維變換
# 離散餘弦變換，得到dct系數矩陣
img_dct = cv2.dct(cv2.dct(vis0))
img_dct.resize(8,8)
# 把list變成一維list
img_list = np.array().flatten(img_dct.tolist())
# 計算均值
img_mean = cv2.mean(img_list)
avg_list = ['0' if i<img_mean else '1' for i in img_list]
return ''.join(['%x' % int(''.join(avg_list[x:x+4]),2) for x in range(0,64,4)])

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率幾乎相同的情況下的效果要更好，它是基於漸變實現的。

dHash的hanming距離步驟：

先將圖片壓縮成9*8的小圖，有72個像素點
將圖片轉化為灰度圖
計算差異值：dHash演算法工作在相鄰像素之間，這樣每行9個像素之間產生了8個不同的差異，一共8行，則產生了64個差異值，或者是32位01字元串。
獲得指紋：如果左邊的像素比右邊的更亮，則記錄為1，否則為0.
通過hash值來計算漢明距離

def dhash(image):
# 將圖片轉化為8*8
image = cv2.resize(image, (9, 8), interpolation=cv2.INTER_CUBIC)
# 將圖片轉化為灰度圖
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
dhash_str = ''
for i in range(8):
for j in range(8):
if gray[i, j] > gray[i, j + 1]:
dhash_str = dhash_str + '1'
else:
dhash_str = dhash_str + '0'
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(dhash_str[i: i + 4], 2))
# print("dhash值",result)
return result

def campHash(hash1, hash2):
n = 0
# hash長度不同返回-1,此時不能比較
if len(hash1) != len(hash2):
return -1
# 如果hash長度相同遍歷長度
for i in range(len(hash1)):
if hash1[i] != hash2[i]:
n = n + 1
return n

⑦ 九宮圖演算法的實現步驟

第一步：菱形斜填寫
第二步：菱形四角的3和7,1和9交換，如下圖
第三步：9和1插隊進去，如圖

先將1—9九個數按如下圖排列
1
4 b 2
7 c 5 a 3
8 d 6
9
然後將a用7代替，同理1換d，3換c，9換b
便可得如下排列：
4 9 2
3 5 7
8 1 6
此方法也可推導至所有的基數的平方宮圖進行排列。
方法2：以中下格為起點，按右下為方向順序填寫（想像格子上下相連，左右相連），遇到右下格已佔，填入正上方格內。
以25格為例： 11↘ 18↘ 25 2↘ 9↘
10填左方 10↑
11填上方 12↘ 19↘ 21↘ 3↘
4填左方 4↘ 6↘ 13↘ 20↑ 11填上方 22↘
23填左方 23↘ 5↑
6填上方 7↘ 14↘ 16↘
17填左方 17↘
18填上方 24↘
25填上方 1↘
2填上方 8↘
9填上方 15↑ 16填上方