def HistogramDistance(hist1, hist2):
  """Earth mover's distance.

  http://en.wikipedia.org/wiki/Earth_mover's_distance
  First, normalize the two histograms. Then, treat the two histograms as
  piles of dirt, and calculate the cost of turning one pile into the other.

  To do this, calculate the difference in one bucket between the two
  histograms. Then carry it over in the calculation for the next bucket.
  In this way, the difference is weighted by how far it has to move."""
  if len(hist1) != len(hist2):
    raise ValueError('Trying to compare histograms '
      'of different sizes, %s != %s' % (len(hist1), len(hist2)))

  n1 = sum(hist1)
  n2 = sum(hist2)
  if n1 == 0:
    raise ValueError('First histogram has 0 pixels in it.')
  if n2 == 0:
    raise ValueError('Second histogram has 0 pixels in it.')

  total = 0
  remainder = 0
  for value1, value2 in zip(hist1, hist2):
    remainder += value1 * n2 - value2 * n1
    total += abs(remainder)
  assert remainder == 0, (
      '%s pixel(s) left over after computing histogram distance.'
      % abs(remainder))
  return abs(float(total) / n1 / n2)