StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It's at least O(n*m) any way you slice it -- you are going to have to look at each cell at least once. The place to economize is in where you accumulate the counts of each value before looking for the most common; if your integers vary over a relatively small range (they are uint16, let's say), then you might be able to simply use a flat array instead of a map.</p> <p>I guess you could also keep a running count <em>x</em>,<em>y</em> of the current top and second-closest candidate for "most common" and early-out as soon as you've less than (n*m)-(x-y) cells left to look at, since at that point there's no way the runner-up could outpace the top candidate.</p> <p>Integer ops like this are pretty fast; even for a megapixel image the brute force algorithm should only take a couple milliseconds.</p> <p>I notice you've edited your original question to say that the pixels value from 0..255 -- in that case, definitely go with a simple flat array; that's small enough to easily fit into the l1 dcache and a lookup in a flat array is trez quick.</p> <p><strong>[edit] :</strong> Dealing with the "no most common number" case is very simple once you've built the histogram array: all have you to do is walk through it to find the "most" and "second most" common numbers; if they're equally frequent, then by definition there is no one most common. </p> <pre><code>const int numLevels = 360; // you said each cell contains a number [0..360) int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i" int mostCommon = 0, runnerUp = 0; for (int i = 1 ; i < numLevels ; ++i) { if ( levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon] ) { runnnerUp = mostCommon; mostCommon = i; } } if ( levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp] ) { return mostCommon; } else { return CenterOfInputData; // (something like InputData[n/2][m/2]) } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload