选择性搜索 Selective Search -- 算法详解+源码分析

2024-04-16 16:58

本文主要是介绍选择性搜索 Selective Search -- 算法详解+源码分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1 前言

2 Selective Search算法

3 Python源码分析



  • 1 前言

在目标检测时,为了定位到目标的具体位置,通常会把图像分成许多子块(sub-regions / patches),然后把子块作为输入,送到目标识别的模型中。selective search就是一种选择子块的启发式方法。



  • 2 Selective Search算法

主要思路:输入一张图片,首先通过图像分割的方法(如大名鼎鼎的felzenszwalb算法)获得很多小的区域,然后对这些小的区域不断进行合并,一直到无法合并为止。此时这些原始的小区域和合并得到的区域的就是我们得到的bounding box.

算法分为如下几个大步:

1. 生成原始的区域集R(利用felzenszwalb算法)

2. 计算区域集R里每个相邻区域的相似度S={s1,s2,…} 

3. 找出相似度最高的两个区域,将其合并为新集,添加进R 

4. 从S中移除所有与第3步中有关的子集 

5. 计算新集与所有子集的相似度 

6.跳至第三步,不断循环,合并,直至S为空(到不能再合并时为止)

 


 

  • 3 Python源码分析

Github上有一个选择性搜索的简单实现 -- selectivesearch ,可以帮助大家理解

 

import skimage.data
import selectivesearchimg = skimage.data.astronaut()
img_lbl, regions = selectivesearch.selective_search(img, scale=500, sigma=0.9, min_size=10)
regions[:10]
=>
[{'labels': [0.0], 'rect': (0, 0, 15, 24), 'size': 260},{'labels': [1.0], 'rect': (13, 0, 1, 12), 'size': 23},{'labels': [2.0], 'rect': (0, 15, 15, 11), 'size': 30},{'labels': [3.0], 'rect': (15, 14, 0, 0), 'size': 1},{'labels': [4.0], 'rect': (0, 0, 61, 153), 'size': 4927},{'labels': [5.0], 'rect': (0, 12, 61, 142), 'size': 177},{'labels': [6.0], 'rect': (7, 54, 6, 17), 'size': 8},{'labels': [7.0], 'rect': (28, 50, 18, 32), 'size': 22},{'labels': [8.0], 'rect': (2, 99, 7, 24), 'size': 24},{'labels': [9.0], 'rect': (14, 118, 79, 117), 'size': 4008}]

alt tag



1. 用户生成原始区域集的函数,其中用到了felzenszwalb图像分割算法。每一个区域都有一个编号,将编号并入图片中,方便后面的操作

def _generate_segments(im_orig, scale, sigma, min_size):"""segment smallest regions by the algorithm of Felzenswalb andHuttenlocher"""# open the Imageim_mask = skimage.segmentation.felzenszwalb(skimage.util.img_as_float(im_orig), scale=scale, sigma=sigma,min_size=min_size)# merge mask channel to the image as a 4th channelim_orig = numpy.append(im_orig, numpy.zeros(im_orig.shape[:2])[:, :, numpy.newaxis], axis=2)im_orig[:, :, 3] = im_maskreturn im_orig

2. 计算两个区域的相似度
论文中考虑了四种相似度 -- 颜色,纹理,尺寸,以及交叠。

其中颜色和纹理相似度,通过获取两个区域的直方图的交集,来判断相似度。

最后的相似度是四种相似度的加和。

def _sim_colour(r1, r2):"""calculate the sum of histogram intersection of colour"""return sum([min(a, b) for a, b in zip(r1["hist_c"], r2["hist_c"])])def _sim_texture(r1, r2):"""calculate the sum of histogram intersection of texture"""return sum([min(a, b) for a, b in zip(r1["hist_t"], r2["hist_t"])])def _sim_size(r1, r2, imsize):"""calculate the size similarity over the image"""return 1.0 - (r1["size"] + r2["size"]) / imsizedef _sim_fill(r1, r2, imsize):"""calculate the fill similarity over the image"""bbsize = ((max(r1["max_x"], r2["max_x"]) - min(r1["min_x"], r2["min_x"]))* (max(r1["max_y"], r2["max_y"]) - min(r1["min_y"], r2["min_y"])))return 1.0 - (bbsize - r1["size"] - r2["size"]) / imsizedef _calc_sim(r1, r2, imsize):return (_sim_colour(r1, r2) + _sim_texture(r1, r2)+ _sim_size(r1, r2, imsize) + _sim_fill(r1, r2, imsize))

3. 用于计算颜色和纹理的直方图的函数

颜色直方图:将色彩空间转为HSV,每个通道下以bins=25计算直方图,这样每个区域的颜色直方图有25*3=75个区间。 对直方图除以区域尺寸做归一化后使用下式计算相似度:

纹理相似度:论文采用方差为1的高斯分布在8个方向做梯度统计,然后将统计结果(尺寸与区域大小一致)以bins=10计算直方图。直方图区间数为8*3*10=240(使用RGB色彩空间)。这里是用了LBP(local binary pattern)获取纹理特征,建立直方图,其余相同

其中,是直方图中第个bin的值。

def _calc_colour_hist(img):"""calculate colour histogram for each regionthe size of output histogram will be BINS * COLOUR_CHANNELS(3)number of bins is 25 as same as [uijlings_ijcv2013_draft.pdf]extract HSV"""BINS = 25hist = numpy.array([])for colour_channel in (0, 1, 2):# extracting one colour channelc = img[:, colour_channel]# calculate histogram for each colour and join to the resulthist = numpy.concatenate([hist] + [numpy.histogram(c, BINS, (0.0, 255.0))[0]])# L1 normalizehist = hist / len(img)return histdef _calc_texture_gradient(img):"""calculate texture gradient for entire imageThe original SelectiveSearch algorithm proposed Gaussian derivativefor 8 orientations, but we use LBP instead.output will be [height(*)][width(*)]"""ret = numpy.zeros((img.shape[0], img.shape[1], img.shape[2]))for colour_channel in (0, 1, 2):ret[:, :, colour_channel] = skimage.feature.local_binary_pattern(img[:, :, colour_channel], 8, 1.0)return retdef _calc_texture_hist(img):"""calculate texture histogram for each regioncalculate the histogram of gradient for each coloursthe size of output histogram will beBINS * ORIENTATIONS * COLOUR_CHANNELS(3)"""BINS = 10hist = numpy.array([])for colour_channel in (0, 1, 2):# mask by the colour channelfd = img[:, colour_channel]# calculate histogram for each orientation and concatenate them all# and join to the resulthist = numpy.concatenate([hist] + [numpy.histogram(fd, BINS, (0.0, 1.0))[0]])# L1 Normalizehist = hist / len(img)return hist

4. 提取区域的尺寸,颜色和纹理特征

def _extract_regions(img):R = {}# get hsv imagehsv = skimage.color.rgb2hsv(img[:, :, :3])# pass 1: count pixel positionsfor y, i in enumerate(img):for x, (r, g, b, l) in enumerate(i):# initialize a new regionif l not in R:R[l] = {"min_x": 0xffff, "min_y": 0xffff,"max_x": 0, "max_y": 0, "labels": [l]}# bounding boxif R[l]["min_x"] > x:R[l]["min_x"] = xif R[l]["min_y"] > y:R[l]["min_y"] = yif R[l]["max_x"] < x:R[l]["max_x"] = xif R[l]["max_y"] < y:R[l]["max_y"] = y# pass 2: calculate texture gradienttex_grad = _calc_texture_gradient(img)# pass 3: calculate colour histogram of each regionfor k, v in list(R.items()):# colour histogrammasked_pixels = hsv[:, :, :][img[:, :, 3] == k]R[k]["size"] = len(masked_pixels / 4)R[k]["hist_c"] = _calc_colour_hist(masked_pixels)# texture histogramR[k]["hist_t"] = _calc_texture_hist(tex_grad[:, :][img[:, :, 3] == k])return R

5. 找邻居 -- 通过计算每个区域与其余的所有区域是否有相交,来判断是不是邻居

def _extract_neighbours(regions):def intersect(a, b):if (a["min_x"] < b["min_x"] < a["max_x"]and a["min_y"] < b["min_y"] < a["max_y"]) or (a["min_x"] < b["max_x"] < a["max_x"]and a["min_y"] < b["max_y"] < a["max_y"]) or (a["min_x"] < b["min_x"] < a["max_x"]and a["min_y"] < b["max_y"] < a["max_y"]) or (a["min_x"] < b["max_x"] < a["max_x"]and a["min_y"] < b["min_y"] < a["max_y"]):return Truereturn FalseR = list(regions.items())neighbours = []for cur, a in enumerate(R[:-1]):for b in R[cur + 1:]:if intersect(a[1], b[1]):neighbours.append((a, b))return neighbours

6. 合并两个区域的函数

def _merge_regions(r1, r2):new_size = r1["size"] + r2["size"]rt = {"min_x": min(r1["min_x"], r2["min_x"]),"min_y": min(r1["min_y"], r2["min_y"]),"max_x": max(r1["max_x"], r2["max_x"]),"max_y": max(r1["max_y"], r2["max_y"]),"size": new_size,"hist_c": (r1["hist_c"] * r1["size"] + r2["hist_c"] * r2["size"]) / new_size,"hist_t": (r1["hist_t"] * r1["size"] + r2["hist_t"] * r2["size"]) / new_size,"labels": r1["labels"] + r2["labels"]}return rt

7. 主函数 -- Selective Search

scale:图像分割的集群程度。值越大,意味集群程度越高,分割的越少,获得子区域越大。默认为1

signa: 图像分割前,会先对原图像进行高斯滤波去噪,sigma即为高斯核的大小。默认为0.8

min_size  : 最小的区域像素点个数。当小于此值时,图像分割的计算就停止,默认为20

每次选出相似度最高的一组区域(如编号为100和120的区域),进行合并,得到新的区域(如编号为300)。然后计算新的区域300与区域100的所有邻居和区域120的所有邻居的相似度,加入区域集S。不断循环,知道S为空,此时最后只剩下一个区域,而且它的像素数会非常大,接近原始图片的像素数,因此无法继续合并。最后退出程序。

def selective_search(im_orig, scale=1.0, sigma=0.8, min_size=50):'''Selective SearchParameters----------im_orig : ndarrayInput imagescale : intFree parameter. Higher means larger clusters in felzenszwalb segmentation.sigma : floatWidth of Gaussian kernel for felzenszwalb segmentation.min_size : intMinimum component size for felzenszwalb segmentation.Returns-------img : ndarrayimage with region labelregion label is stored in the 4th value of each pixel [r,g,b,(region)]regions : array of dict[{'rect': (left, top, width, height),'labels': [...],'size': component_size},...]'''assert im_orig.shape[2] == 3, "3ch image is expected"# load image and get smallest regions# region label is stored in the 4th value of each pixel [r,g,b,(region)]img = _generate_segments(im_orig, scale, sigma, min_size)if img is None:return None, {}imsize = img.shape[0] * img.shape[1]R = _extract_regions(img)# extract neighbouring informationneighbours = _extract_neighbours(R)# calculate initial similaritiesS = {}for (ai, ar), (bi, br) in neighbours:S[(ai, bi)] = _calc_sim(ar, br, imsize)# hierarchal searchwhile S != {}:# get highest similarityi, j = sorted(S.items(), key=lambda i: i[1])[-1][0]# merge corresponding regionst = max(R.keys()) + 1.0R[t] = _merge_regions(R[i], R[j])# mark similarities for regions to be removedkey_to_delete = []for k, v in list(S.items()):if (i in k) or (j in k):key_to_delete.append(k)# remove old similarities of related regionsfor k in key_to_delete:del S[k]# calculate similarity set with the new regionfor k in [a for a in key_to_delete if a != (i, j)]:n = k[1] if k[0] in (i, j) else k[0]S[(t, n)] = _calc_sim(R[t], R[n], imsize)regions = []for k, r in list(R.items()):regions.append({'rect': (r['min_x'], r['min_y'],r['max_x'] - r['min_x'], r['max_y'] - r['min_y']),'size': r['size'],'labels': r['labels']})return img, regions

 

这篇关于选择性搜索 Selective Search -- 算法详解+源码分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/909376

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听