Ask Your Question
2

How to faster sort matrix?

asked 2013-03-17 23:58:43 -0600

wuling gravatar image

updated 2013-03-18 02:19:57 -0600

sammy gravatar image

I want to sort all element of mat but my kernel size(kernel_size=61) is very large. Now i use

///* For each window row */
for ( iwr = wr_begin; iwr < wr_end; iwr++ )
 {
   /* For each window column */
    memcpy(p+k*win_size,src2.data+(ic-c_begin)+(ir-r_begin+iwr-wr_begin)*num_cols,sizeof(win_size));
   k+=1;
}

 //cv::Rect roi(ic-c_begin,ir-r_begin,win_size,win_size);
//Mat roi_image=src2(roi);
//roi_image
std::sort(p,p+win_count);
median_value=p[pos] ;

Is any faster method?? pls tell me, thanks:)

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
2

answered 2013-03-18 02:33:49 -0600

sammy gravatar image

updated 2016-06-05 14:29:37 -0600

It's not clear what do you mean by sorting, but looking at your code, it seems you want to find the median value of the pixels in an image. So I will answer this question.

For unsigned char matrices (normal images, or in OpenCV format CV_8UC[1,2,3]), you can use an old, but fery fast trick: a histogram.

  • Calculate the histogram of your image
  • For each channel, start to sum the elements in the bins until their count is equal or above half the number of pixels in the image. The bin where you stop is the median element of your image

    cv:Mat hist = cv::calcHist(image);
    
    uchar * h = hist.data;    
    int sum = 0, bin = 0;
    int maxElements = image.total();
    
    while((sum < maxElements) && (bin < 255))
    {
       sum += h[bin];
    }
    
    std::cout << "Median pixel value of the image is " << bin << std::endl;
    

Because it does no sorting at all, and no copies of the original data, it is a lot faster than any other median-extraction algorithm.

I did not test the code, and it probably needs some checks, but you get the idea.

And if you want to sort a matrix of arbitrary data type, you should look into the sort functions provided by OpenCV. Check the docs :)

EDIT: there is an internal function getMedian in align.cpp

//enum { LDR_SIZE = 256 };
int getMedian(Mat& img)
{
    int channels = 0;
    Mat hist;
    int hist_size = LDR_SIZE;
    float range[] = {0, LDR_SIZE} ;
    const float* ranges[] = {range};
    calcHist(&img, 1, &channels, Mat(), hist, 1, &hist_size, ranges);
    float *ptr = hist.ptr<float>();
    int median = 0, sum = 0;
    int thresh = (int)img.total() / 2;
    while(sum < thresh && median < LDR_SIZE) {
        sum += static_cast<int>(ptr[median]);
        median++;
    }
    return median;
}
edit flag offensive delete link more

Comments

Hi, sammy I wnat local median value,where windows size is 61. so the total sort pixels is 61x61. But cv::sort only support

◦CV_SORT_EVERY_ROW Each matrix row is sorted independently ◦CV_SORT_EVERY_COLUMN Each matrix column is sorted independently. This flag and the previous one are mutually exclusive ◦CV_SORT_ASCENDING Each matrix row is sorted in the ascending order ◦CV_SORT_DESCENDING Each matrix row is sorted in the descending order. This flag and the previous one are also mutually exclusive

If the image size is 572x538. It spends almost 2 minute seconds.

i try use

cv::Rect roi(ic-c_begin,ir-r_begin,win_size,win_size); Mat roi_image=src2(roi);

But roi_image size is 61x61 matrix and can't convert to vector so I can't use sort(vector.begin(),vector.end())

I found out memcpy & std::sort spend a lot od times. so, is any effective method??

wuling gravatar imagewuling ( 2013-03-18 03:06:44 -0600 )edit

Dear Sammy. I think it's very good ideal. if i use

cv::Rect roi(a,b,win_size,win_size);

Mat roi_image=src2(roi);

to replace memcpy and

use

cv:Mat hist = cv::calcHist(image); uchar * h = hist.data;
int sum = 0, bin = 0; int maxElements = image.total(); while((sum < maxElements) && (bin < 255)){ sum += h[bin];}

replace sort(61x61 size)

I think it is very effictive than before.

Thanks.

wuling gravatar imagewuling ( 2013-03-18 03:54:45 -0600 )edit

Isn't cv::medianBlur that what you want? For large kernels (>5) it uses this algorithm which is time constant due to kernel size.

matman gravatar imagematman ( 2016-06-05 15:43:08 -0600 )edit

Question Tools

1 follower

Stats

Asked: 2013-03-17 23:58:43 -0600

Seen: 5,290 times

Last updated: Jun 05 '16