# Finding the 20th percentile pixel of an image using a histogram instead of std::sort

I have a 2-dimensional matrix (an image) in which I need to find the 20th percentile value. My first attempt was to sort the values and then index using std::floor(0.2*(srcSor.size())/100).

My code was originally straightforward like this:

#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>

#include <iostream>

int main(int argc, char* argv[])
{
std::vector<double> srcSor = src.reshape(0, 1);
std::sort (srcSor.begin(), srcSor.end(), std::greater<double>());
float A = srcSor[std::floor(0.2*(srcSor.size())/100)];
//Then later I use A value..
.
.

return 0;
}


I found that std::sort took a long time to sort a vector of 1.3m unsigned values. So now I'm using an histogram to do the same thing; this takes less time to find that value of that certain index. The idea comes from the fact that the values of the matrix are unsigned int in the range 0-255:

#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>

#include <iostream>

int main(int argc, char* argv[])
{

std::vector<unsigned> histo(256,0.0);
for(unsigned j=0;j<src.rows;j++)
for(unsigned i=0;i<src.cols;i++)
histo[(int)src.at<uchar>(j,i)]++;

std::vector<unsigned> sumHH(256,0.0);
sumHH[255]=histo[255];
for(unsigned i=254;i>=1;i--)
sumHH[i]=sumHH[i+1]+histo[i];

int A=0;
int indx=std::floor(0.2*(src.rows*src.cols)/100);
for(unsigned i=1;i<255;i++)
if(indx<sumHH[255-i])
{
A=255-i;
break;
}
//Then later I use A value..
.
.

return 0;
}


But I think that my code is not really readable, can anyone suggest a better way to write my code and/or better optimized?

• It looks like std::nth_element will be a better fit, if the function is invoked rarely. – Incomputable Jul 17 '17 at 14:56

1. Well, index=std::floor(0.2*(srcSor.size())/100 is equivalent to the much simpler index = srcSor.size() / 500, ignoring some inaccuracy in representing 0.2.

2. Lose the fixed-size std::vectors. You don't depend on any of the benefits of using dynamic memory, so a simple array is sufficient and far more efficient.

3. Next, you really don't need the cumulative counts in sumHH at all. Just test whether you have reached the target immediately.

4. Don't cast unless you have to. Casting means overriding the type-system, and is thus error-prone.

5. Don't use obscure abbreviations.

Resulting code:

unsigned histogram[256] = {};
for (auto j = src.rows; j--;)
for (auto i = src.cols; i--;)
++histogram[src.at<uchar>(j,i)];
int A = 255;
for (auto index = src.rows * src.cols / 500; index > histogram[A]; --A)
index -= histogram[A];