Go back For the sake of simplicity, I've treated add/sub/mul equally. Using the integral image trick, the denominator computation is comprised of 4M2 ops to construct sum and square-sum tables, and (M-N+1)2 iterations of 6 add/subs, followed by 2 muls, a sub and a sqrt. Admittedly, sqrt is much more than a mul, but a decent approximate sqrt can be implemented in ~20 elemental ops. Here is some C code that empircally verifies the factor of 2 between the 'naive' approach's numerator and denominator. The integral image trick was first used in the signal processing (box filtering) and graphics (summed areas) communities. More recently, it gained recognition in the vision community, as part of Paul Viola's real-time boosted face detector.