title: Fast calculation of sum of absolute difference with Integral Image
body: <p>I am trying to find the fast way of block matching between 2 images and I am using sum of absolute difference (SAD) as similarity metric. </p>
  
  <p>Given a reference block A at NxN size in frame 1, a full search for the best matched block within  a search window of size (2W+N)*(2W+N) in frame 2, where W stands for the maximum allowed displacement. Full search block matching requires (2W+1)^2 comparison. </p>
  
  <p>Integral image can calculate the sum of pixels in a block in any image quickly but I could not work out how to calculate the sum of absolute difference (SAD) here.</p>
  
  <p>Is it possible to use the integral image to calculate SAD here? Thanks.</p>