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

内容简介：直方图反向投影算法介绍与实现

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

概念介绍

直方图反向投影简单的说就是可以通过它来实现图像分割，背景与对象分离，对已知对象位置进行定位。反向投影在模式匹配、对象识别、视频跟踪中均有应用，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;
}