直方图反向投影算法介绍与实现

直方图反向投影算法介绍与实现

概念介绍

直方图反向投影简单的说就是可以通过它来实现图像分割，背景与对象分离，对已知对象位置进行定位。反向投影在模式匹配、对象识别、视频跟踪中均有应用，OpenCV中经典算法之一CAMeanShift就是基于反向投影实现对已知对象的位置查找与标记、从而达到连续跟踪。反向投影的概念第一次提出是在Michael.J.Swain与Dana H. Ballard的《Indexing via Color Histograms》论文中。

算法流程

直方图反向投影简单的说就是可以通过它来实现图像分割，背景与对象分离，对已知对假设模型图像的颜色直方图为M、目标图像颜色直方图为I、直方图反向投影首先通过计算比率 得到第三个直方图R=M/I，然后根据图像I(x, y)每个像素颜色值的索引查找R得到每个像素点直方图分布概率图像、对图像每个像素点得到I(x,y)=min(Rh(x,y), 1) ，对得到结果图像进行卷积计算，Mask大小默认为3x3或者5x5,形状一般情况下取圆形。对卷积之后的结果计算最大值所在位置即为对象所在位置。此时可以归一化为0~255之间输出图像即可。总结一下可以分为如下几步

• 1.计算模型的直方图M
• 2.计算目标图像的直方图I
• 3.用M除以I得到比率直方图R
• 4.循环每个像素点I(x, y)根据像素值映射成为直方图R的分布概率
• 5.卷积操作
• 6.归一化与现实输出

算法实现

• 计算图像的直方图 。这里需要注意的是输入的图像一般都是RGB图像，计算得到RGB直方图，需要对图像进行降维处理，常见是把255x255x255变为16x16x16大小，或者把RGB图像转换为HSV图像，计算H与S两个通道的直方图。

// 计算直方图
int[] input = new int[width*height];
float[] output = new float[width*height];
getRGB(src, 0, 0, width, height, input);
int[] iHist = calculateHistorgram(input, width, height);

• 计算比率直方图 R

float[] rHist = new float[iHist.length];
for(int i=0; i<iHist.length; i++) {
    float a = mHist[i];
    float b = iHist[i];
    rHist[i] = a / b; 
}

• 根据像素值查找R，得到分布概率权重

int index = 0;
int bidx = 0;
int tr=0, tg=0, tb=0;
int level = 256 / bins;
float[] rimage = new float[output.length];
for(int row=0; row<height; row++) {
    for(int col=0; col<width; col++) {
        index = row * width + col;
        tr = (input[index] >> 16) & 0xff;
        tg = (input[index] >> 8) & 0xff;
        tb = input[index] & 0xff;
        bidx = (tr / level) + (tg / level)*bins + (tb / level)*bins*bins;
        rimage[index] = Math.min(1, rHist[bidx]);
    }
}

• 计算卷积，使用3x3的模板

int offset = 0;
float sum = 0;
System.arraycopy(rimage, 0, output, 0, output.length);
for(int row=1; row<height-1; row++) {
    offset = width * row;
    for(int col=1; col<width-1; col++) {
        sum += rimage[offset+col];
        sum += rimage[offset+col-1];
        sum += rimage[offset+col+1];
        sum += rimage[offset+width+col];
        sum += rimage[offset+width+col-1];

        sum += rimage[offset+width+col+1];
        sum += rimage[offset-width+col];
        sum += rimage[offset-width+col-1];
        sum += rimage[offset-width+col+1];
        output[offset+col] = sum / 9.0f;
        sum = 0f; // for next  
    }
}

• 归一化与显示

// 归一化
float min = 1000;
float max = 0;
for(int i=0; i<output.length; i++) {
    min = Math.min(min, output[i]);
    max = Math.max(max, output[i]);
}
float delta = max - min;
for(int i=0; i<output.length; i++) {
     output[i] =  ((output[i] - min)/delta)*255;
}

// 阈值显示
int[] out = new int[output.length];
for(int i=0; i<out.length; i++) {
    int pv = (int)output[i];
    if(pv < 50) pv = 0;
    out[i] = (0xff << 24) | (pv << 16) | (pv << 8) | pv;
}

模型图像与目标图像、运行效果

颜色模型图像

目标图像

根据颜色模型图像，实现直方图投影，可以准确的找到皇马队长水爷所在区域！

总结

直方图反向投影算法在图像处理与模式识别与匹配中是一种非常有效与常用的算法。这里代码实现是基于最开始提到的论文！

**只分享干货，助你在人工智能与计算机视觉的道路上前进！
欢迎关注本博客与本人微信公众号【OpenCV学堂】**