采购网站建设,专业的设计网站,python基础教程学什么,为了 门户网站建设手写nms
计算宽高的时候加1是为什么#xff1f;
本文总结自互联网的多种nms实现#xff0c;供参考#xff0c;非博主原创#xff0c;各原文链接如下#xff0c;也建议大家动手写一写。
Ref#xff1a;
浅谈NMS的多种实现
目标窗口检测算法-NMS非极大值抑制
一、fas…手写nms
计算宽高的时候加1是为什么
本文总结自互联网的多种nms实现供参考非博主原创各原文链接如下也建议大家动手写一写。
Ref
浅谈NMS的多种实现
目标窗口检测算法-NMS非极大值抑制
一、faster-rcnn源码阅读nms的CUDA编程
c版 nms
nms简介
首先还是要科普一下nms算法的思想简单来说就是去重框。这里的重框针对的当然是某一类的框。下面实现的时候也是默认拿到某一类所有的框。
算法思路 For a prediction bounding box B, the model calculates the predicted probability for each category. Assume the largest predicted probability is p, the category corresponding to this probability is the predicted category of B. We also refer to pas the confidence level of prediction bounding box B. On the same image, we sort the prediction bounding boxes with predicted categories other than background by confidence level from high to low, and obtain the list L. Select the prediction bounding box B1 with highest confidence level from L as a baseline and remove all non-benchmark prediction bounding boxes with an IoU with B1 greater than a certain threshold from L. The threshold here is a preset hyper-parameter. At this point,L retains the prediction bounding box with the highest confidence level and removes other prediction bounding boxes similar to it. Next, select the prediction bounding box B2 with the second highest confidence level from L as a baseline, and remove all non-benchmark prediction bounding boxes with an IoU with B2 greater than a certain threshold from L. Repeat this process until all prediction bounding boxes in L have been used as a baseline. At this time, the IoU of any pair of prediction bounding boxes in L is less than the threshold. Finally, output all prediction bounding boxes in the list L. 前面这段话基本说出了算法的具体实现思路先对每个框的score进行排序首先选择第一个也就是score最高的框它一定是我们要保留的框。然后拿它和剩下的框进行比较如果IOU大于一定阈值说明两者重合度高应该去掉这样筛选出的框就是和第一个框重合度低的框第一次迭代结束。第二次从保留的框中选出score第一的框重复上述过程直到没有框保留了。
Python
版本一
该版本为 Faster RCNN 实现的版本是网络是最常见的版本
def nms(dets, thresh):x1 dets[:, 0] #xminy1 dets[:, 1] #yminx2 dets[:, 2] #xmaxy2 dets[:, 3] #ymaxscores dets[:, 4] #confidenceareas (x2 - x1 1) * (y2 - y1 1) # 每个boundingbox的面积order scores.argsort()[::-1] # boundingbox的置信度排序keep [] # 用来保存最后留下来的boundingboxwhile order.size 0: i order[0] # 置信度最高的boundingbox的indexkeep.append(i) # 添加本次置信度最高的boundingbox的index# 当前bbox和剩下bbox之间的交叉区域# 选择大于x1,y1和小于x2,y2的区域xx1 np.maximum(x1[i], x1[order[1:]]) #交叉区域的左上角的横坐标yy1 np.maximum(y1[i], y1[order[1:]]) #交叉区域的左上角的纵坐标xx2 np.minimum(x2[i], x2[order[1:]]) #交叉区域右下角的横坐标yy2 np.minimum(y2[i], y2[order[1:]]) #交叉区域右下角的纵坐标# 当前bbox和其他剩下bbox之间交叉区域的面积w np.maximum(0.0, xx2 - xx1 1)h np.maximum(0.0, yy2 - yy1 1)inter w * h# 交叉区域面积 / (bbox 某区域面积 - 交叉区域面积)ovr inter / (areas[i] areas[order[1:]] - inter)#保留交集小于一定阈值的boundingboxinds np.where(ovr thresh)[0]order order[inds 1]return keep可以看到基本是按照上述思路去写的按照score进行降序排序然后每次拿到第一个框也就是score最大的框然后计算该框与其他框的IOU最后留下iouthresh的框留作下次循环这里唯一值得强调的是最后这个索引为什么要1。这是因为我们要得到的inds是排除了当前用来比较的score最大的框所以在其原始索引基础上1 ,从代码中看就是由于order[1:]这样写导致的。
当然这个大众版本思路很清楚但感觉不够优雅可以再精简一点。
版本二
def nms(dets, thresh): areasnp.prod(bbox[:,2:]-bbox[:,:2],axis1)order scores.argsort()[::-1]keep[]while order.size0:iorder[0]keep.append(i)tlnp.maximum(b[:2],bbox[i1:,:2])brnp.minimum(b[2:],bbox[i1:,2:])internp.prod(br-tl,axis1)*(brtl).all(axis1)ovrinter/(areas[order[1:]]areas[i]-inter)indsnp.where(ovrthresh)[0]orderorder[inds1]return keep当然这里的思路还是要排序只不过iou部分写的更精简了。
好了铺垫了这么久说一下不排序怎么写。基本思路是依次遍历每个框计算这个框与其他框的iou,找到iou大于一定阈值的其他框因为这个时候不能保证它一定是score最高的框所以要进行判断如果它的score小于其他框那就把它去掉因为它肯定不是要保留的框。如果它的score大于其他框那应该保留它同时可以去掉所有其他框了。最后保留的框就是结果。
def nms(bbox, scores, thresh):areanp.prod(bbox[:,2:]-bbox[:,:2],axis1)keepnp.ones(len(bbox),dtypebool)for i, b in enumerate(bbox):if(keep[i]False):continuetlnp.maximum(b[:2],bbox[i1:,:2])brnp.minimum(b[2:],bbox[i1:,2:])internp.prod(br-tl,axis1)*(brtl).all(axis1)iouia/(area[i1:]area[i]-inter)r [ k for k in np.where(iouthresh)[0]i1 if keep[k]True]if (scores[i]scores[r]).all():keep[r]Falseelse:keep[i]Falsereturn np.where(keep)[0].astype(np.int32)这是我按照上面思路写的用keep表示框的去留为True的框要保留。当然这个思路的效率不见得比前面排序的要好只是作为其他角度思考。
版本三
补充之前排序实现是通过每次筛除框来完成的直到最后没有框剩下了则循环结束。但还可以这么想同样先将框按score排好序这次循环条件为遍历所有框在某次循环拿到一个框将其与所有已经保留的框进行比较如果iou大于阈值说明它应该被删去直接进行下一次循环如果小于将其加入进要保留的框中。当遍历完所有框时结束拿到保留的框。
嗯文字还是有点绕直接看code更清楚
def _non_maximum_suppression_cpu(bbox, thresh, score):ordernp.argsort(score)[::-1]bboxbbox[order] bbox_areanp.prod(bbox[:, 2:]-bbox[:, :2],axis1)keepnp.zeros(bbox.shape[0], dtypebool) for i, b in enumerate(bbox):tlnp.maximum(b[:2],bbox[keep, :2]) brnp.minimum(b[2:],bbox[keep, 2:]) area np.prod(br-tl, axis1)*(tlbr).all(axis1)iouarea/(bbox_area[i]bbox_area[keep]-area) if (iouthresh).any(): continuekeep[i]Truekeep np.where(keep)[0]return keep.astype(np.int32)至此介绍了三种NMS算法的实现思路。即使作为常规的算法题考察也很好因为这也不牵扯到目标检测的东西。而且还顺便考察了numpy的操作。这也提醒自己有时候要多深入想想而不是简单copy网上现有的东西。
C
typedef struct Bbox{int x;int y;int w;int h;float score;
}Bbox;static bool sort_score(Bbox box1,Bbox box2){return box1.score box2.score ? true : false;
}float iou(Bbox box1,Bbox box2){int x1 max(box1.x,box2.x);int y1 max(box1.y,box2.y);int x2 min(box1.xbox1.w,box2.xbox2.w);int y2 min(box1.ybox1.h,box2.ybox2.h);// int w max(0,x2 - x1 1);// int h max(0,y2 - y1 1);int w max(0,x2 - x1 1);int h max(0,y2 - y1 1);// float over_area w*h;float over_area (x2 - x1) * (y2 - y1);return over_area / (box1.w * box1.h box2.w * box2.h - over_area);
}vectorBbox nms(std::vectorBboxvec_boxs,float threshold){vectorBboxresults;std::sort(vec_boxs.begin(),vec_boxs.end(),sort_score);while(vec_boxs.size() 0) {results.push_back(vec_boxs[0]);int index 1;while(index vec_boxs.size()){float iou_value iou(vec_boxs[0],vec_boxs[index]);cout iou: iou_value endl;if(iou_value threshold)vec_boxs.erase(vec_boxs.begin() index);elseindex;}vec_boxs.erase(vec_boxs.begin());}return results;
}
测试
int main(){vectorBbox input;Bbox box1 {1, 2, 2, 2, 0.4};Bbox box2 {1, 3, 2, 1, 0.5};Bbox box3 {1, 3, 3, 1, 0.72};Bbox box4 {1, 1, 3, 3, 0.9};Bbox box5 {1, 1, 2, 3, 0.45};input.push_back(box1);input.push_back(box2);input.push_back(box3);input.push_back(box4);input.push_back(box5);vectorBbox res;res nms(input, 0.5);for(int i 0;i res.size();i){printf(%d %d %d %d %f,res[i].x,res[i].y,res[i].w,res[i].h,res[i].score);cout endl;}return 0;
}CUDA
cpu版验证和理解了算法下面来看看GPU实现加速速度大概可以提升50X。在2080it上大概是115ms比3ms。
nms各种实现的benchmark请看
https://github.com/fmscole/benchmark
主控函数分两部分第一部分计算mask还需要的标0不需要的重复度大的标1第二部分是根据mask选出留下来的候选框。
先简要说一下CUDA编程模型
GPU之所以能够加速是因为并行计算即每个线程负责计算一个数据充分利用GPU计算核心超多几千个的优势。
1每个计算核心相互独立运行同一段代码这段代码称为核函数
2每个核心有自己的身份id线程的身份id是两个三维数组blockIdx.xblockIdx.yblockIdx.z-threadIdx.xthreadIdx.ythreadIdx.z。
身份id被另两个三维数组gridgridDim.x,gridDim.y,gridDim.z和block(blockDim.x,blockDim.y,blockDim.z)确定范围。
总共有 gridDim.x×gridDim.y×gridDim.zgridDim.x×gridDim.y×gridDim.zgridDim.x×gridDim.y×gridDim.z 个 block
每个block有 blockDim.x×blockDim.y×blockDim.zblockDim.x×blockDim.y×blockDim.zblockDim.x×blockDim.y×blockDim.z 个 thread。
有了线程的身份id经过恰当的安排让身份id核函数可以获取blockIdx.xblockIdx.yblockIdx.z-threadIdx.xthreadIdx.ythreadIdx.z对应到一个数据就可以实现一个线程计算一个数据至于如何对应开发人员得好好安排可以 说这是CUDA开发的一个核心问题。
gridDim.x、blockIdx.x这些是核函数可以获取的gridDim.x等于多少调用核函数的时候就要定一下来。看代码 dim3 blocks(DIVUP(boxes_num, threadsPerBlock),DIVUP(boxes_num, threadsPerBlock));dim3 threads(threadsPerBlock);nms_kernelblocks, threads(boxes_num,nms_overlap_thresh,boxes_dev,mask_dev);这里的threadsPerBlock8*864
当boxes_num12030时DIVUP(12030, 64)12030/6412030%640188
在调用核函数的时候通过blocks, threads#这是cu语法不是标准C语言把线程数量安排传递进去核函数里就有
gridDim.x188,gridDim.y188,gridDim.z1
blockDim.x64,blockDim.y1,blockDim.z1
0blockIdx.x188,
0blockIdx.y188,
blockIdx.z0,
0threadIdx.x64
threadIdx.ythreadIdx.z0
这样就启动了2,262,016个两百多万个线程来计算两百多万看起来吓人对GPU来书毫无负担每个线程计算不超过64个值后面再讲。
3这里的grid(a,b,cblock(x,y,z)值是多少由程序设计人员根据问题来定在调用核函数时就要确定下来但有一个基本限制block(x,y,z)中的x×y×z1024这个值随GPU版本确定起码nvidia 10802080都是这样
4block中的线程每32个thread为一束绝对同步比如if-else语句这32个线程中有的满足if条件有的满足else。满足else的那部分线程不能直接进入而是要等满足if的那部分线程运行完毕才进入else部分而满足if的那部分线程现在也不能结束而是要等else部分线程运行完毕大家才能同时结束。for语句也是一样。因此GPU计算尽可能不要有分支语句。
不是说不能用if和for该用还得用用的时候要知道付出的代价。否则实现了减速都不知道为了啥。
不同的线程束之间不同步如果同步需要请__syncthreads();
如果设置block(1)即一个block只安排一个线程呢事实上GPU还是要启动32个线程另外31个陪跑。
因此block(x,y,z)中的x×y×z应该为32的倍数。不过32×321024了。
5要并行计算前提是数据之间没有相互依赖有前后依赖的部分只能放在同一个核函数里计算
先看控制部分代码这部分做的事情就是
在GPU上分配内存把数据传到GPU调用核函数计算mask把数据传回来根据mask把获取保留下来的候选框。
nms_kernel.cu来源https://github.com/jwyang/faster-rcnn.pytorch
void _nms(int* keep_out, int* num_out, const float* boxes_host, int boxes_num,int boxes_dim, float nms_overlap_thresh, int device_id) {_set_device(device_id);
//keep_out返回保留目标框的下标
//num_out返回保留下来的个数float* boxes_dev NULL;unsigned long long* mask_dev NULL;const int col_blocks DIVUP(boxes_num, threadsPerBlock);
//比如boxes_num12030时col_blocks188后面都以此为例CUDA_CHECK(cudaMalloc(boxes_dev,boxes_num * boxes_dim * sizeof(float)));
//在GPU上分配内存CUDA_CHECK(cudaMemcpy(boxes_dev,boxes_host,boxes_num * boxes_dim * sizeof(float),cudaMemcpyHostToDevice));
//把候选框数据复制到GPUCUDA_CHECK(cudaMalloc(mask_dev,boxes_num * col_blocks * sizeof(unsigned long long)));
//分配mask的内存用于返回mask的计算结果dim3 blocks(DIVUP(boxes_num, threadsPerBlock),DIVUP(boxes_num, threadsPerBlock));
//(188,188)dim3 threads(threadsPerBlock);
//(64)//调用核函数nms_kernelblocks, threads(boxes_num,nms_overlap_thresh,boxes_dev,mask_dev);std::vectorunsigned long long mask_host(boxes_num * col_blocks);
//在CPU上分配内存用于返回mask就算结果CUDA_CHECK(cudaMemcpy(mask_host[0],mask_dev,sizeof(unsigned long long) * boxes_num * col_blocks,cudaMemcpyDeviceToHost));
//把mask从GPU复制到CPU
//下面这段代码最后再叙述std::vectorunsigned long long remv(col_blocks);memset(remv[0], 0, sizeof(unsigned long long) * col_blocks);int num_to_keep 0;for (int i 0; i boxes_num; i) {int nblock i / threadsPerBlock;int inblock i % threadsPerBlock;if (!(remv[nblock] (1ULL inblock))) {keep_out[num_to_keep] i;unsigned long long *p mask_host[0] i * col_blocks;for (int j nblock; j col_blocks; j) {remv[j] | p[j];}}}*num_out num_to_keep;CUDA_CHECK(cudaFree(boxes_dev));CUDA_CHECK(cudaFree(mask_dev));
//释放GPU上的内存
}计算mask的核函数是核心代码什么是mask呢从内存里讲是一段连续内存但应该把它想象成一个矩阵
比如候选框个数为boxes_num12030时由于要计算任意两个候选框之间的IOU是否大于阈值因此我们需要建一个12030*12030的矩阵1表示两个候选框的IOU大于0.70表示不大于。这样任意两个候选框之间的关系都可以用这个12030行*12030列行表示本框列表示其他框的矩阵保存。
但是这里有好几处值得改进的地方
1对角线上的值不需要计算因为意味着自己与自己计算IOU没意义
2上三角与下三角是对称的只需要用到上三角即可
3更重要的是为了保存0或1的值真需要建这么大的矩阵吗事实上每连续的64个0、1刚好构成一个无符号的64位整数unsigned long long我们只用一个整数表示即可这样内存减少64倍这中间设计到位运算这不是问题。原本需要一个12030***12030的一个数组来表示这个矩阵现在只要12030***188的一个unsigned long long数组就可以映射这个12030行188列的矩阵。
比如这长度为1230*188数组中的第一组188个整数相当于矩阵的第一行记录的是第一个框按分数排序之后与其他所有框之间的重叠关系第一个整数的第一位表示与自己由于自己与自己不参与计算所以这个值一定为0.
__global__ void nms_kernel(int n_boxes, float nms_overlap_thresh,float *dev_boxes, unsigned long long *dev_mask) {//n_boxes候选框的个数比如是12030//nms_overlap_thresh0.7阈值//dev_boxes候选框//dev_mask存放mask的值const int row_start blockIdx.y;//把blockIdx.y想象成矩阵的行号n_boxes12030时共有188行const int col_start blockIdx.x;//把blockIdx.x想象成矩阵的列号n_boxes12030时共有188列而每个block有64个线程188*6412032// if (row_start col_start) return;const int row_size min(n_boxes - row_start * threadsPerBlock, threadsPerBlock);const int col_size min(n_boxes - col_start * threadsPerBlock, threadsPerBlock);//在block里row_size和col_size最多取到64尾部不足64就取余数。先把数据复制一份到共享内存关于共享内存后面详述__shared__ float block_boxes[threadsPerBlock * 5];//每个block有64个线程所以复制64个候选框每个候选框有4个坐标值和一个分数值共5个值//所以每个block分配的共享内存大小为64*5320if (threadIdx.x col_size) {block_boxes[threadIdx.x * 5 0] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 0];block_boxes[threadIdx.x * 5 1] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 1];block_boxes[threadIdx.x * 5 2] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 2];block_boxes[threadIdx.x * 5 3] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 3];block_boxes[threadIdx.x * 5 4] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 4];}__syncthreads();//同步if (threadIdx.x row_size) {//每个线程虽然运行的是同一段代码但看到的表示身份的threadIdx.x是不一样的row_size值也不一样//具体的说有188*188个线程看到的threadIdx.x是一样的因为总共有188*188个blockthreadIdx.x的取值范围是0到63const int cur_box_idx threadsPerBlock * row_start threadIdx.x;//int cur_box_idx这个才是真正的行号因为grid下面还有block。//CUDA编程就是要把这些表示线程的id对应到具体数据blockIdx.y和threadIdx.x确定当前候选框const float *cur_box dev_boxes cur_box_idx * 5;//取出当前的候选框别忘了候选框用5个数值表示的所以要乘5int i 0;unsigned long long t 0;//t就是存放64个0、1的整数int start 0;if (row_start col_start) {//对角线上的blockstart threadIdx.x 1;//自己跟自己就不要计算IOU了}for (i start; i col_size; i) {if (devIoU(cur_box, block_boxes i * 5) nms_overlap_thresh) {//每一个当前框都与其他框计算IOU其他框存放在共享内存是一个复制品//本线程只负责计算第blockIdx.y×64threadIdx.x号候选框当前框//与blockIdx.x×64blockIdx.x×6463这64个候选框其他框之间的关系t | 1ULL i;}}const int col_blocks DIVUP(n_boxes, threadsPerBlock);//同上假定下col_blocks188dev_mask[cur_box_idx * col_blocks col_start] t;//dev_mask总长为12030*188表示12030行188列的矩阵//即分为12030段行每段188个列int64每个int64标记64个0、1所以每行的这188个int64可以标记12032个0\1//就是说第i段行的12032个记录的是第i个候选框与其他所有候选框之间的重叠关系。//cur_box_idx表示第几段每段col_blocks188个数col_start是本段里第几个数所以//dev_mask[cur_box_idx * col_blocks col_start] t 记录的是第cur_box_idx个候选框//与第col_start×64到col_start1×64-1之间这64个矩形框之间的重叠关系}
}再总结一下总共规划了188,188,1个block每个block有64,1,1个线程第cr0-t,0,0)号线程负责计算的数据是r×64t号候选框与c×64c×6463号这64个候选框之间的重叠关系并存进r×64t×188c这个整数里。当cr遍历完188t遍历完64这188×188×64个线程就计算完了任意两个候选框之间的关系。
由于cuda里每个线程计算一个数据相当于cpu里的循环。CPU里的循环是一个一个的算而cuda里是同时在算。
本质上这里gird188,188,1和block64,1,1来代替了三重循环
forint i0i188;i)forint j0j188;j)forint k0k64;k)。。。。。。只要把这循环中的ijk替换为blockIdx.xblockIdx.ythreadIdx.x即可。
CUDA编程就是循环替代——这是我目前的理解。
回过头来看把候选框复制进共享内存这部分
block_boxes[threadIdx.x * 5 0] dev_boxes[(threadsPerBlock * col_start threadIdx.x) * 5 0];可以看出这里面只用到了blockIdx.x和threadIdx.x注意到了没没用到blockIdx.y而blockIdx.y的范围是0~187什么意思意味着这段代码被重复执行了188次毕竟我们启动了188×64×188个线程而数据只有12030个数据因此有188个线程执行的是相同的数据不知道我理解的对不对望大佬帮我指正。
计算好了mask数组之后计算保留下来的目标框
//...................std::vectorunsigned long long remv(col_blocks);memset(remv[0], 0, sizeof(unsigned long long) * col_blocks);
//长为188的unsigned long long数组初始值为0
//这12032个标记位用于记录那些候选框已经被剔除int num_to_keep 0;
//保留下来的个数for (int i 0; i boxes_num; i) {int nblock i / threadsPerBlock;int inblock i % threadsPerBlock;
//把12030个候选框分成188组每64个一组第nblock组的第inblock个候选框就是第i个候选框if (!(remv[nblock] (1ULL inblock))) {
//还没有被舍弃这两个条件只要有一个不成立都意味着没有被剔除keep_out[num_to_keep] i;
//把下标记录下来unsigned long long *p mask_host[0] i * col_blocks;
//再回忆一遍mask_host总长是12030×188
//分为12030段第i段有188个unsigned long long整数记录第i个候选框与其他所有候选框之间的信息
//p指向的是第i段的起始位置for (int j nblock; j col_blocks; j) {
//遍历后面的188个整数总共12032个标记位多出来的2位不去管它remv[j] | p[j];
//因为第i个候选框已经保留下来所以与第i个候选框重复的候选框都标记为去除}}}
//keep_out的前num_to_keep个数就是保留下来的候选框的下标
//.................................
