Python cv2 寻找图片中数量占比最高的像素

工作中遇到一个问题，即找出图片当中数量占比最高的像素值。

因时间紧迫，使用两层循环嵌套 naive 的完成了需求，效率非常慢，被人吐槽（可耻！）。

故开始寻找优化方法，发现利用 numpy 可以实现这个功能。

因此本文打算从最 naive 的方法开始，逐步比较不同方法，并试图探寻 numpy 执行如此迅速的原因。

以下是本篇章节，可以根据标题选择性观看。

naive 循环嵌套基于numpy的实现numpy高效背后的原因 naive 循环嵌套

1 载入图片；

2 遍历所有的pixel，统计每个像素值的个数；

3 然后寻找其中像素值最多的个数

这里主要耗时存在于 步骤2 中，对于所有pixel的遍历，即两次for循环的嵌套

512x512的图片，时间大概在 1.5s 左右

import cv2 import time # load img img = cv2.imread('./lena.jpg') start_t = time.time() pixel_num = {} (w,h,_) = img.shape # search for each pixel and record the max times max_value = None max_times = 0 for i in range(w): for j in range(h): [b,g,r] = img[i,j] pixel = (b,g,r) if pixel in pixel_num.keys(): pixel_num[pixel] += 1 if pixel_num[pixel] > max_times: max_times = pixel_num[pixel] max_value = pixel else: pixel_num[pixel] = 1 end_t = time.time() print(f'the most pixel is {max_value}, occupying {max_times/float(w*h):.6f}, time: {end_t-start_t:.6f}') 基于numpy的实现

本篇是基于np.ravel_multi_index() 和 np.bincount()

np.ravel_multi_index()，作用是把多维度数据映射到一维数据

np.bincount()，作用是统计一维数据中各个元素出现的次数

512x512的图片，时间大概在 0.25s 左右，比上面naive的方法（1.5s）快了83%

import cv2 import numpy as np import time # load img img = cv2.imread('./lena.jpg') start_t = time.time() (w,h,_) = img.shape img_2D = np.reshape(img,(-1,3)) # 统计b,g,r 最大像素的值 b_max = np.max(img_2D[:,0])+1 g_max = np.max(img_2D[:,1])+1 r_max = np.max(img_2D[:,2])+1 img_tuple = (img_2D[:,0],img_2D[:,1],img_2D[:,2]) nbin = np.array([b_max,g_max,r_max]) # 将三维数值 双射 到一个一维数据 xy = np.ravel_multi_index(img_tuple, nbin) # 0.007s # 统计这个数组中每个元素出现的个数 H = np.bincount(xy, minlength=nbin.prod()) # 0.055s H = H.reshape(nbin) # 得到最多出现像素的次数 max_num = H.max() # 0.15s # 得到最多出现像素在结果中的像素值 max_value = np.unravel_index(np.argmax(H),H.shape) end_t = time.time() print(f'the most pixel is {max_value}, occupying {max_num/float(w*h):.6f}, time: {end_t-start_t:.6f}') numpy高效背后的原因

理论上如果要找到出现次数最多的元素，必定需要遍历所有的元素，即算法复杂度为 O(WH)

但是为什么上述两者的效率可以相差70%？

记录每个步骤的时间，发现其中 np.ravel_multi_index()(0.007s) 和 np.bincount()(0.055s) 很快，得到最大值(0.15s)上花费较多时间

为了能够更好的探究效率为何如此之高的原因，查看了numpy实现 bincount 的C语言源代码

本质上也还是一个遍历，应该就是C语言的遍历比python快把

/* * arr_bincount is registered as bincount. * * bincount accepts one or two arguments. The first is an array of * non-negative integers and the second, if present, is an array of weights, * which must be promotable to double. Call these arguments list and * weight. Both must be one-dimensional with len(weight) == len(list). If * weight is not present then bincount(list)[i] is the number of occurrences * of i in list. If weight is present then bincount(self,list, weight)[i] * is the sum of all weight[j] where list [j] == i. Self is not used. */ static PyObject * arr_bincount(PyObject *NPY_UNUSED(self), PyObject *args, PyObject *kwds) { PyArray_Descr *type; PyObject *list = NULL, *weight=Py_None; PyObject *lst=NULL, *ans=NULL, *wts=NULL; intp *numbers, *ians, len , mxi, mni, ans_size; int i; double *weights , *dans; static char *kwlist[] = {"list", "weights", NULL}; if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O", kwlist, &list, &weight)) { goto fail; } if (!(lst = PyArray_ContiguousFromAny(list, PyArray_INTP, 1, 1))) { goto fail; } len = PyArray_SIZE(lst); if (len < 1) { PyErr_SetString(PyExc_ValueError, "The first argument cannot be empty."); goto fail; } numbers = (intp *) PyArray_DATA(lst); mxi = mxx(numbers, len); mni = mnx(numbers, len); if (numbers[mni] < 0) { PyErr_SetString(PyExc_ValueError, "The first argument of bincount must be non-negative"); goto fail; } ans_size = numbers [mxi] + 1; type = PyArray_DescrFromType(PyArray_INTP); if (weight == Py_None) { if (!(ans = PyArray_Zeros(1, &ans_size, type, 0))) { goto fail; } ians = (intp *)(PyArray_DATA(ans)); for (i = 0; i < len; i++) ians [numbers [i]] += 1; Py_DECREF(lst); } else { if (!(wts = PyArray_ContiguousFromAny(weight, PyArray_DOUBLE, 1, 1))) { goto fail; } weights = (double *)PyArray_DATA (wts); if (PyArray_SIZE(wts) != len) { PyErr_SetString(PyExc_ValueError, "The weights and list don't have the same length."); goto fail; } type = PyArray_DescrFromType(PyArray_DOUBLE); if (!(ans = PyArray_Zeros(1, &ans_size, type, 0))) { goto fail; } dans = (double *)PyArray_DATA (ans); // 关键：在这里对于所有的numbers进行遍历 然后累加 for (i = 0; i < len; i++) { dans[numbers[i]] += weights[i]; } Py_DECREF(lst); Py_DECREF(wts); } return ans; fail: Py_XDECREF(lst); Py_XDECREF(wts); Py_XDECREF(ans); return NULL; }

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。