Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Currently, I am using Android/Java. I am looking for the most efficient means to determine the average of the highest 100 pixel values taken from a greyscale preview.

The preview part I am more or less okay with; however, it determining which sorting methodology is the most efficient. The other option is to apply a threshold, which will eliminate most of the data.

Which sorting algorithm would be most efficient for an unsorted data set of over 3 million values?

share|improve this question
1  
Just build a histogram. –  Kris Van Bael Jun 2 '13 at 21:38
    
Thank you, but unfortunately that would not be practical in my situation. –  user92765 Jun 2 '13 at 23:10
1  
Why would that be? All it takes is an int array of 256 elements and less than 10 lines of code. –  Kris Van Bael Jun 3 '13 at 5:37
    
I need the actual values –  user92765 Jun 3 '13 at 6:26
    
Your greyscale image is not 8bit then? –  Kris Van Bael Jun 3 '13 at 19:24

3 Answers 3

up vote 1 down vote accepted

Are you looking for the average value of all pixels whose value is greater than 155 (or some other arbitrary threshold?) There's no need to do a sort.

Pseudo code:

integer sum
integer count

for each pixel
   if pixel value greater than threshold
      sum = sum + pixel value
      count++
   end if
end for

float average = sum / count
share|improve this answer
    
The arbitary values change significantly, but I think I can statistically determine a threshold. I agree, I would imagine it would be less taxing on the smartphone's CPU (and my sanity). –  user92765 Jun 1 '13 at 12:46
1  
That is the easy part. The tough part is to determine the right threshold. –  Kris Van Bael Jun 2 '13 at 21:36

You can implement a bounded PriorityQueue. It will sort the pixels by value, and remains only the pixels having higher values.

See for instance this SO question.

After having added all your pixels in the queue, only the X highers will remain in the queue, so you can simply get their mean value.

If your structure is able to add an element in O(log(n)) (has PriorityQueue does), to remove the lesser element in O(log(n)), the execution complexity in the worse case will be

  • O(n*log(n)) for adding all the pixels in the structure.
  • O(n) for computing the mean

So, the global complexity will be O(n*log(n)) + O(n) = O(n*log(n))

See also the Guava Min-Max Priority queue that retrieves the first and the last element in the queue in constant time, and that has an optional maximal size. This is, actualy, the class to use in your case.

share|improve this answer
    
That looks to be right on the money –  user92765 Jun 3 '13 at 6:31

Assuming that you want the average of the highest 100 greyscale values: Observe that greyscale values have a much smaller range than raw (RGB) pixels, usually 0.255. (Also note that averages of RGB pixels are not likely to yield anything interesting.)

   unsigned char image[NROWS][NCOLS];
   unsigned hist[256];
   bzero(hist, sizeof(hist));
   // compute histogram of greyscale values
   for(unsigned r = 0; r < NROWS; r++) {
      for(unsigned c = 0; c < NCOLS; c++) {
         hist[image[r][c]]++;
      }
   }
   unsigned counter;
   unsigned bin;
   bin = 255;
   while ((bin > 0) && (counter < 100)) {
      while (bin > 0) && (hist[bin] == 0)) {
         bin--;
      }
   #ifdef WEIGHTED_AVERAGE
      sum += (bin * hist[bin]);
   #else
      sum += bin;
   #endif
      // handle pathological case where there are < 100 nonzero bins
      if (hist[bin] > 0) counter++;
   }
   double average_value;
   average_value = ((double)sum)/counter;
share|improve this answer
1  
Damien said building a histogram is not practical in his situation. (The real question is: why?) In addition, you probably should give a Java code since he is programming in Java/Android. –  mgoeminne Jun 4 '13 at 7:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.