1# Copyright 2014 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5"""Color Histograms and implementations of functions operating on them."""
6
7from __future__ import division
8
9import collections
10
11from telemetry.internal.util import external_modules
12
13np = external_modules.ImportOptionalModule('numpy')
14
15
16def HistogramDistance(hist1, hist2, default_color=None):
17  """Earth mover's distance.
18  http://en.wikipedia.org/wiki/Earth_mover's_distance"""
19  if len(hist1) != len(hist2):
20    raise ValueError('Trying to compare histograms '
21                     'of different sizes, %s != %s' % (len(hist1), len(hist2)))
22  if len(hist1) == 0:
23    return 0
24
25  sum_func = np.sum if np is not None else sum
26
27  n1 = sum_func(hist1)
28  n2 = sum_func(hist2)
29  if (n1 == 0 or n2 == 0) and default_color is None:
30    raise ValueError('Histogram has no data and no default color.')
31  if n1 == 0:
32    hist1[default_color] = 1
33    n1 = 1
34  if n2 == 0:
35    hist2[default_color] = 1
36    n2 = 1
37
38  if np is not None:
39    remainder = np.multiply(hist1, n2) - np.multiply(hist2, n1)
40    cumsum = np.cumsum(remainder)
41    total = np.sum(np.abs(cumsum))
42  else:
43    total = 0
44    remainder = 0
45    for value1, value2 in zip(hist1, hist2):
46      remainder += value1 * n2 - value2 * n1
47      total += abs(remainder)
48    assert remainder == 0, (
49        '%s pixel(s) left over after computing histogram distance.'
50        % abs(remainder))
51  return abs(float(total) / n1 / n2)
52
53
54class ColorHistogram(
55    collections.namedtuple('ColorHistogram', ['r', 'g', 'b', 'default_color'])):
56  # pylint: disable=no-init
57  # pylint: disable=super-on-old-class
58
59  def __new__(cls, r, g, b, default_color=None):
60    return super(ColorHistogram, cls).__new__(cls, r, g, b, default_color)
61
62  def Distance(self, other):
63    total = 0
64    for i in xrange(3):
65      default_color = self[3][i] if self[3] is not None else None
66      total += HistogramDistance(self[i], other[i], default_color)
67    return total
68