[MPlayer-dev-eng] Enhanced cropdetect code

[Roger Heflin]

Reimar Döffinger wrote:
> Hello,
> On Sun, Jul 06, 2008 at 03:01:48PM -0500, Roger Heflin wrote:
>> but also requires a number of FP operations to do properly so is very 
>> likely slower than the original cropdetect.
> 
> It certainly does not require them. Now firstly, calculation log 2 via
> log 10 and a division is really wasteful, there is a log2 for a good
> reason (not to mention that the division should not be in the inner
> loop).
> Secondly, there should be no need for any float operations, if my quick
> calculations are correct, you can sum over hist[i] * av_log2(hist[i])
> and subtract len * av_log2(len) and divide the whole thing by len as the
> last step in floating point if necessary.
> (formula is
> SUM[1,n]{ (h[i]/len) * log2(h[i]/len) }
> = 1/len * SUM[1,n]{ h[i] * log2(h[i]/len) }
> = 1/len * SUM[1,n]{ h[i] * (log2(h[i]) - log2(len)) }
> = 1/len * (SUM[1,n]{ h[i] * log2(h[i]) } - SUM[1,n] { h[i] * log2(len) })
> = 1/len * (SUM[1,n]{ h[i] * log2(h[i]) } - log2(len) * SUM[1,n] { h[i] })
> = 1/len * (SUM[1,n]{ h[i] * log2(h[i]) } - log2(len) * len )
> 
> Also, instead of the loops setting stuff to 0, use memset.

I did not consider math reductions, the appear to be reasonable reductions, and 
some testing seems to agree what the reductions being correct.

I ported some code that was written a long long time ago (and written the most 
obvious straightforward way) and log2 appears to not be in the C standard (it is 
not in math.h-nor in the C books-so I would not have originally used it) but 
does appear to be a working function (so one might as well use it since it 
simplifies things), and in the original code the number of points was huge (many 
millions) so doing the log for 0...255 was not terribly important, unlike in 
mplayer where were are talking about 1000-3000 points and doing the logs for 
each line, so the logs are more significant.

And I had not heard the "0-th order entropy estimation" as a name for it, I 
heard about it 15+ years ago in an image processing class used in reference to 
compression algorithms, and it is somewhat useful for estimating how well (in 
general) things could be compressed, and would run at disk speed-which at the 
time was much much faster than compression algorithms.

I am reworking things based on the changes, I will see if I can get a runtime 
for a before and after test case to see how much that improved things.

                                   Roger