OpenCV Q&A Forum - RSS feedhttp://answers.opencv.org/questions/OpenCV answersenCopyright <a href="http://www.opencv.org">OpenCV foundation</a>, 2012-2018.Sun, 05 Jun 2016 15:43:08 -0500How to faster sort matrix?http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/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:)Sun, 17 Mar 2013 23:58:43 -0500http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/Answer by sammy for <p>I want to sort all element of mat but my kernel size(kernel_size=61) is very large.
Now i use </p>
<pre><code>///* 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] ;
</code></pre>
<p>Is any faster method??
pls tell me, thanks:)</p>
http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?answer=9499#post-id-9499It'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](https://github.com/Itseez/opencv/blob/master/modules/photo/src/align.cpp#L247-L263)
//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;
}
Mon, 18 Mar 2013 02:33:49 -0500http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?answer=9499#post-id-9499Comment by wuling for <p>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.</p>
<p>For <code>unsigned char</code> matrices (normal images, or in OpenCV format <code>CV_8UC[1,2,3]</code>), you can use an old, but fery fast trick: a histogram. </p>
<ul>
<li>Calculate the histogram of your image</li>
<li><p>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</p>
<pre><code>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;
</code></pre></li>
</ul>
<p>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.</p>
<p>I did not test the code, and it probably needs some checks, but you get the idea.</p>
<p>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 :)</p>
<p>EDIT: there is an internal function <code>getMedian</code> in <a href="https://github.com/Itseez/opencv/blob/master/modules/photo/src/align.cpp#L247-L263">align.cpp</a></p>
<pre><code>//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;
}
</code></pre>
http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=9504#post-id-9504Hi,
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??
Mon, 18 Mar 2013 03:06:44 -0500http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=9504#post-id-9504Comment by wuling for <p>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.</p>
<p>For <code>unsigned char</code> matrices (normal images, or in OpenCV format <code>CV_8UC[1,2,3]</code>), you can use an old, but fery fast trick: a histogram. </p>
<ul>
<li>Calculate the histogram of your image</li>
<li><p>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</p>
<pre><code>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;
</code></pre></li>
</ul>
<p>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.</p>
<p>I did not test the code, and it probably needs some checks, but you get the idea.</p>
<p>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 :)</p>
<p>EDIT: there is an internal function <code>getMedian</code> in <a href="https://github.com/Itseez/opencv/blob/master/modules/photo/src/align.cpp#L247-L263">align.cpp</a></p>
<pre><code>//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;
}
</code></pre>
http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=9507#post-id-9507Dear 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.
Mon, 18 Mar 2013 03:54:45 -0500http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=9507#post-id-9507Comment by matman for <p>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.</p>
<p>For <code>unsigned char</code> matrices (normal images, or in OpenCV format <code>CV_8UC[1,2,3]</code>), you can use an old, but fery fast trick: a histogram. </p>
<ul>
<li>Calculate the histogram of your image</li>
<li><p>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</p>
<pre><code>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;
</code></pre></li>
</ul>
<p>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.</p>
<p>I did not test the code, and it probably needs some checks, but you get the idea.</p>
<p>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 :)</p>
<p>EDIT: there is an internal function <code>getMedian</code> in <a href="https://github.com/Itseez/opencv/blob/master/modules/photo/src/align.cpp#L247-L263">align.cpp</a></p>
<pre><code>//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;
}
</code></pre>
http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=95690#post-id-95690Isn't `cv::medianBlur` that what you want? For large kernels (>5) it uses [this](http://nomis80.org/ctmf.html) algorithm which is time constant due to kernel size.Sun, 05 Jun 2016 15:43:08 -0500http://answers.opencv.org/question/9494/how-to-faster-sort-matrix/?comment=95690#post-id-95690