title: super fast median of matrix in opencv (as fast as matlab)
body: <p>I'm writing some code in openCV and want to find the median value of a very large matrix array (single channel grayscale, float).</p>
  <p>I tried several methods such as sorting the array (using std::sort) and picking the middle entry but it is extremely slow when comparing with the median function in matlab. To be precise - what takes 0.25 seconds in matlab takes over 19 seconds in openCV.</p>
  <p>My input image is originally a 12-bit greyscale image with the dimensions 3840x2748 (~10.5 megapixels), converted to float (CV_32FC1) where all the values are now mapped to the range [0,1] and at some point in the code I request the median value by calling:</p>
  <p><code>double myMedianValue = medianMat(Input);</code></p>
  <p>Where the function medianMat is:</p>
  <pre class="lang-cpp prettyprint-override"><code>double medianMat(cv::Mat Input){    
      Input = Input.reshape(0,1); // spread Input Mat to single row
      std::vector&lt;double&gt; vecFromMat;
      Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat    
      std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat
          if (vecFromMat.size()%2==0) {return (vecFromMat[vecFromMat.size()/2-1]+vecFromMat[vecFromMat.size()/2])/2;} // in case of even-numbered matrix
      return vecFromMat[(vecFromMat.size()-1)/2]; // odd-number of elements in matrix
  }
  </code></pre>
  <p>I timed the function medinaMat by itself and also the various parts - as expected the bottleneck is in:</p>
  <pre class="lang-cpp prettyprint-override"><code>std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat
  </code></pre>
  <p>Does anyone here have an efficient solution?</p>
  <p>Thanks!</p>
  <p><strong>EDIT</strong>
  I have tried using std::nth_element given in the answer of Adi Shavit.</p>
  <p>The function medianMat now reads as:</p>
  <pre class="lang-cpp prettyprint-override"><code>double medianMat(cv::Mat Input){    
      Input = Input.reshape(0,1); // spread Input Mat to single row
      std::vector&lt;double&gt; vecFromMat;
      Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat
      std::nth_element(vecFromMat.begin(), vecFromMat.begin() + vecFromMat.size() / 2, vecFromMat.end());
      return vecFromMat[vecFromMat.size() / 2];
  }
  </code></pre>
  <p>The runtime has lowered from over 19 seconds to 3.5 seconds. This is still nowhere near the 0.25 second in Matlab using the median function...</p>