OpenCV中cvCalcEMD2函數詳解：土方距離在圖像匹配中的應用

Earth Mover's Distance（EMD，土方距離）是一種強大的直方圖比較度量方法，特別適合處理光照變化導致的顏色漂移問題。本文詳細解析OpenCV中cvCalcEMD2函數的原理、參數與使用方法。

什麼是EMD？

EMD全稱Earth Mover's Distance，中文稱「土方距離」。其核心隱喻：將一個直方圖視為一堆土，另一個直方圖視為坑洼，EMD衡量將土堆移動填平坑洼所需的最小工作量（移動量×移動距離）。

為什麼需要EMD？

傳統直方圖匹配（如相關性、卡方檢驗）基於bin對bin比較，無法處理光照變化導致的顏色值整體偏移。例如：同一物體在不同光照下，顏色直方圖形狀相似但峰值位置平移，傳統方法會判定為不匹配。EMD通過允許「跨bin移動質量」，天然適應此類變化。

EMD的數學本質

給定兩個簽名集合（Signature）P = {(w₁, x₁), ..., (wₘ, xₘ)} 和 Q = {(u₁, y₁), ..., (uₙ, yₙ)}，其中w、u為權重（直方圖bin值），x、y為特徵向量（bin坐標）。EMD求解最小化總運輸成本的流網絡問題：

min Σᵢⱼ fᵢⱼ · d(xᵢ, yⱼ)，滿足流守恆約束。

cvCalcEMD2函數原型

float cvCalcEMD2(
    const CvArr* signature1,
    const CvArr* signature2,
    int distance_type,
    CvDistanceFunction distance_func = NULL,
    const CvArr* cost_matrix = NULL,
    CvArr* flow = NULL,
    float* lower_bound = NULL,
    void* userdata = NULL
);

關鍵參數詳解

從直方圖構建簽名的關鍵步驟

// 假設2D直方圖：h_bins × s_bins
int numrows = h_bins * s_bins;
CvMat* sig1 = cvCreateMat(numrows, 3, CV_32FC1); // 1權重 + 2座標 = 3列
CvMat* sig2 = cvCreateMat(numrows, 3, CV_32FC1);

for (int h = 0; h < h_bins; h++) {
    for (int s = 0; s < s_bins; s++) {
        float bin_val = cvQueryHistValue_2D(hist1, h, s);
        cvSet2D(sig1, h*s_bins + s, 0, cvScalar(bin_val)); // 權重
        cvSet2D(sig1, h*s_bins + s, 1, cvScalar(h));       // 座標1
        cvSet2D(sig1, h*s_bins + s, 2, cvScalar(s));       // 座標2
        
        bin_val = cvQueryHistValue_2D(hist2, h, s);
        cvSet2D(sig2, h*s_bins + s, 0, cvScalar(bin_val));
        cvSet2D(sig2, h*s_bins + s, 1, cvScalar(h));
        cvSet2D(sig2, h*s_bins + s, 2, cvScalar(s));
    }
}

關鍵點：每個bin轉為一行，權重為bin值，座標為bin索引。高維直方圖同理擴展座標列數。

計算EMD距離

float emd = cvCalcEMD2(sig1, sig2, CV_DIST_L2);
printf("EMD distance: %f\n", emd);

返回值越小表示兩直方圖越相似。EMD滿足度量空間性質（非負、對稱、三角不等式）。

實際應用場景

• 圖像檢索：基於顏色/紋理直方圖的相似圖像搜索
• 目標跟蹤：幂間帧外觀模型匹配，抗光照變化
• 圖像配准：多模態圖像特徵匹配

性能與注意事項

• EMD計算複雜度較高（線性規劃求解），大簽名集合時較慢
• 可通過降低直方圖bin數、使用近似算法優化速度
• OpenCV 3.x/4.x建議使用C++接口cv::EMD，功能更完整
• 簽名權重通常需歸一化（總和為1），否則距離值受圖像尺寸影響

EMD作為一種基於傳輸理論的距離度量，在計算機視覺中佔有重要地位，特別是對光照、平移不敏感的直方圖比較場景。