[Telemetry] Migrate bitmap.py from bitmaptools.cc to numpy

tools/telemetry/telemetry/core/bitmap.py

Index: tools/telemetry/telemetry/core/bitmap.py
diff --git a/tools/telemetry/telemetry/core/bitmap.py b/tools/telemetry/telemetry/core/bitmap.py
index f130cc4317207bd7f968c084c6a40b7be59edfeb..a934a3972b2c75a96683e6c08fb3ea624cd7db2d 100644
--- a/tools/telemetry/telemetry/core/bitmap.py
+++ b/tools/telemetry/telemetry/core/bitmap.py
@@ -2,40 +2,31 @@
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
+"""Bitmap is a basic wrapper for an openCV image.
+
+It includes some basic processing tools: crop, find bounding box of a color
+and compute histogram of color values.
 """
-Bitmap is a basic wrapper for image pixels. It includes some basic processing
-tools: crop, find bounding box of a color and compute histogram of color values.
-"""
+from __future__ import division
 
-import array
 import base64
-import cStringIO
 import collections
-import struct
-import subprocess
+import cv2
 

[slamm, 2014/10/21 23:21:58]

Drop the blank line.

[mthiesse, 2014/10/22 15:33:10]

Done.

-from telemetry.core import util
-from telemetry.core import platform
-from telemetry.util import support_binaries
+import numpy as np

[slamm, 2014/10/21 23:21:58]

Just "import numpy"?

[mthiesse, 2014/10/22 15:33:10]

Well, it seems to be convention in python to import numpy as np. However, I
don't have a strong opinion either way, so if you insist I'll change it.

[slamm, 2014/10/22 16:41:22]

It does not seem like an important enough detail to insist. Thanks for making
the other edits.

 
+from telemetry.core import util
 util.AddDirToPythonPath(util.GetTelemetryDir(), 'third_party', 'png')
 import png  # pylint: disable=F0401
 
 
 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)))
-
+                     'of different sizes, %s != %s' % (len(hist1), len(hist2)))
   n1 = sum(hist1)
   n2 = sum(hist2)
   if n1 == 0:
@@ -43,15 +34,35 @@ def HistogramDistance(hist1, hist2):
   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)
+  # Normalize histograms to each other.
+  if n1 != n2:
+    hist1 = np.divide(hist1, n1 / n2)
+
+  h1 = np.zeros((len(hist1), 2), np.float32)
+  h2 = np.zeros((len(hist2), 2), np.float32)
+  for i in xrange(len(h1)):
+    h1[i][0] = hist1[i]
+    h2[i][0] = hist2[i]
+    h1[i][1] = i
+    h2[i][1] = i
+
+  return cv2.cv.CalcEMD2(cv2.cv.fromarray(h1), cv2.cv.fromarray(h2),
+                         cv2.cv.CV_DIST_L2)
+
+
+def ColorsAreEqual(color1, color2, tolerance=0, color_depth=3):
+  """ Tests whether two colors are equal within the given tolerance.

[slamm, 2014/10/21 23:21:58]

No space after triple quotes.

[mthiesse, 2014/10/22 15:33:10]

Done.

+
+  Args:
+    color1, color2: The  colors to be compared. Colors must be array-like, and
+        of the same color depth and pixel format. ex: (0, 255, 127)
+    tolerance: Per-channel equality tolerance.
+    color_depth: The depth of the colors. 3 for BGR, 1 for grey, etc.
+  """
+  for i in xrange(color_depth):
+    if abs(color1[i] - color2[i]) > tolerance:
+      return False
+  return True

[slamm, 2014/10/21 23:21:58]

return all(abs(color1[i]  - color2[i]) <= tolerance
           for i in xrange(color_depth))

[mthiesse, 2014/10/22 15:33:10]

Done.

 
 
 class ColorHistogram(
@@ -83,179 +94,65 @@ class ColorHistogram(
     return total
 
 
-class RgbaColor(collections.namedtuple('RgbaColor', ['r', 'g', 'b', 'a'])):
-  """Encapsulates an RGBA color retreived from a Bitmap"""
-  # pylint: disable=W0232
-  # pylint: disable=E1002
-
-  def __new__(cls, r, g, b, a=255):
-    return super(RgbaColor, cls).__new__(cls, r, g, b, a)
-
-  def __int__(self):
-    return (self.r << 16) | (self.g << 8) | self.b
-
-  def IsEqual(self, expected_color, tolerance=0):
-    """Verifies that the color is within a given tolerance of
-    the expected color"""
-    r_diff = abs(self.r - expected_color.r)
-    g_diff = abs(self.g - expected_color.g)
-    b_diff = abs(self.b - expected_color.b)
-    a_diff = abs(self.a - expected_color.a)
-    return (r_diff <= tolerance and g_diff <= tolerance
-        and b_diff <= tolerance and a_diff <= tolerance)
-
-  def AssertIsRGB(self, r, g, b, tolerance=0):
-    assert self.IsEqual(RgbaColor(r, g, b), tolerance)
-
-  def AssertIsRGBA(self, r, g, b, a, tolerance=0):
-    assert self.IsEqual(RgbaColor(r, g, b, a), tolerance)
-
-
-WEB_PAGE_TEST_ORANGE = RgbaColor(222, 100,  13)
-WHITE =                RgbaColor(255, 255, 255)
-
-
-class _BitmapTools(object):
-  """Wraps a child process of bitmaptools and allows for one command."""
-  CROP_PIXELS = 0
-  HISTOGRAM = 1
-  BOUNDING_BOX = 2
-
-  def __init__(self, dimensions, pixels):
-    binary = support_binaries.FindPath(
-        'bitmaptools',
-        platform.GetHostPlatform().GetArchName(),
-        platform.GetHostPlatform().GetOSName())
-    assert binary, 'You must build bitmaptools first!'
-
-    self._popen = subprocess.Popen([binary],
-                                   stdin=subprocess.PIPE,
-                                   stdout=subprocess.PIPE,
-                                   stderr=subprocess.PIPE)
-
-    # dimensions are: bpp, width, height, boxleft, boxtop, boxwidth, boxheight
-    packed_dims = struct.pack('iiiiiii', *dimensions)
-    self._popen.stdin.write(packed_dims)
-    # If we got a list of ints, we need to convert it into a byte buffer.
-    if type(pixels) is not bytearray:
-      pixels = bytearray(pixels)
-    self._popen.stdin.write(pixels)
-
-  def _RunCommand(self, *command):
-    assert not self._popen.stdin.closed, (
-      'Exactly one command allowed per instance of tools.')
-    packed_command = struct.pack('i' * len(command), *command)
-    self._popen.stdin.write(packed_command)
-    self._popen.stdin.close()
-    length_packed = self._popen.stdout.read(struct.calcsize('i'))
-    if not length_packed:
-      raise Exception(self._popen.stderr.read())
-    length = struct.unpack('i', length_packed)[0]
-    return self._popen.stdout.read(length)
-
-  def CropPixels(self):
-    return self._RunCommand(_BitmapTools.CROP_PIXELS)
-
-  def Histogram(self, ignore_color, tolerance):
-    ignore_color_int = -1 if ignore_color is None else int(ignore_color)
-    response = self._RunCommand(_BitmapTools.HISTOGRAM,
-                                ignore_color_int, tolerance)
-    out = array.array('i')
-    out.fromstring(response)
-    assert len(out) == 768, (
-        'The ColorHistogram has the wrong number of buckets: %s' % len(out))
-    return ColorHistogram(out[:256], out[256:512], out[512:], ignore_color)
-
-  def BoundingBox(self, color, tolerance):
-    response = self._RunCommand(_BitmapTools.BOUNDING_BOX, int(color),
-                                tolerance)
-    unpacked = struct.unpack('iiiii', response)
-    box, count = unpacked[:4], unpacked[-1]
-    if box[2] < 0 or box[3] < 0:
-      box = None
-    return box, count
+WEB_PAGE_TEST_ORANGE = (222, 100, 13)
+WHITE = (255, 255, 255)
 
 
 class Bitmap(object):
-  """Utilities for parsing and inspecting a bitmap."""
-
-  def __init__(self, bpp, width, height, pixels, metadata=None):
-    assert bpp in [3, 4], 'Invalid bytes per pixel'
-    assert width > 0, 'Invalid width'
-    assert height > 0, 'Invalid height'
-    assert pixels, 'Must specify pixels'
-    assert bpp * width * height == len(pixels), 'Dimensions and pixels mismatch'
-
-    self._bpp = bpp
-    self._width = width
-    self._height = height
-    self._pixels = pixels
-    self._metadata = metadata or {}
-    self._crop_box = None
+  """ Utilities for parsing and inspecting a bitmap.

[slamm, 2014/10/21 23:21:58]

No Space after triple quotes.

[mthiesse, 2014/10/22 15:33:10]

Done.

 
-  @property
-  def bpp(self):
-    """Bytes per pixel."""
-    return self._bpp
+  Attributes:
+    image: The underlying numpy array (openCV image).
+  """
 
-  @property
-  def width(self):
-    """Width of the bitmap."""
-    return self._crop_box[2] if self._crop_box else self._width
+  def __init__(self, image):
+    """ Initializes the Bitmap object.

[slamm, 2014/10/21 23:21:58]

Here too.

[mthiesse, 2014/10/22 15:33:10]

Done.

 
-  @property
-  def height(self):
-    """Height of the bitmap."""
-    return self._crop_box[3] if self._crop_box else self._height
+    Args:
+      image: A numpy array (openCV image) indexed by [y][x][0-2], BGR.
+    """
+    self.image = image
 
-  def _PrepareTools(self):
-    """Prepares an instance of _BitmapTools which allows exactly one command.
+  @staticmethod
+  def FromRGBPixels(width, height, pixels, bpp=3):
+    """Create a bitmap from an array of rgb pixels.
+
+    Ignores alpha channel if present.
+
+    Args:
+      width, height: int, the width and height of the image.
+      pixels: The flat array of pixels in the form of [r,g,b[,a],r,g,b[,a],...]
+      bpp: 3 for RGB, 4 for RGBA
     """
-    crop_box = self._crop_box or (0, 0, self._width, self._height)
-    return _BitmapTools((self._bpp, self._width, self._height) + crop_box,
-                        self._pixels)
+    img = np.array(pixels, order='F', dtype=np.uint8)
+    img.resize((height, width, bpp))
+    img = cv2.cvtColor(img,
+                       cv2.COLOR_RGBA2BGR if bpp == 4 else cv2.COLOR_RGB2BGR)
+    return Bitmap(img)
+
+  @staticmethod
+  def FromImageFile(path):
+    """Create a bitmap from an image file."""
+    img = cv2.imread(path, cv2.CV_LOAD_IMAGE_COLOR)
+    if img is None:
+      raise ValueError('Image at path {0} could not be read'.format(path))
+    return Bitmap(img)
 
   @property
-  def pixels(self):
-    """Flat pixel array of the bitmap."""
-    if self._crop_box:
-      self._pixels = self._PrepareTools().CropPixels()
-      _, _, self._width, self._height = self._crop_box
-      self._crop_box = None
-    if type(self._pixels) is not bytearray:
-      self._pixels = bytearray(self._pixels)
-    return self._pixels
+  def width(self):
+    """Width of the image."""
+    return self.image.shape[1]
 
   @property
-  def metadata(self):
-    self._metadata['size'] = (self.width, self.height)
-    self._metadata['alpha'] = self.bpp == 4
-    self._metadata['bitdepth'] = 8
-    return self._metadata
-
-  def GetPixelColor(self, x, y):
-    """Returns a RgbaColor for the pixel at (x, y)."""
-    pixels = self.pixels
-    base = self._bpp * (y * self._width + x)
-    if self._bpp == 4:
-      return RgbaColor(pixels[base + 0], pixels[base + 1],
-                       pixels[base + 2], pixels[base + 3])
-    return RgbaColor(pixels[base + 0], pixels[base + 1],
-                     pixels[base + 2])
-
-  def WritePngFile(self, path):
-    with open(path, "wb") as f:
-      png.Writer(**self.metadata).write_array(f, self.pixels)
+  def height(self):
+    """Height of the image."""
+    return self.image.shape[0]
 
   @staticmethod
   def FromPng(png_data):
     width, height, pixels, meta = png.Reader(bytes=png_data).read_flat()
-    return Bitmap(4 if meta['alpha'] else 3, width, height, pixels, meta)
-
-  @staticmethod
-  def FromPngFile(path):
-    with open(path, "rb") as f:
-      return Bitmap.FromPng(f.read())
+    return Bitmap.FromRGBPixels(
+        width, height, pixels, 4 if meta['alpha'] else 3)
 
   @staticmethod
   def FromBase64Png(base64_png):
@@ -263,90 +160,81 @@ class Bitmap(object):
 
   def IsEqual(self, other, tolerance=0):
     """Determines whether two Bitmaps are identical within a given tolerance."""
-
-    # Dimensions must be equal
-    if self.width != other.width or self.height != other.height:
+    if self.image.shape != other.image.shape:
+      return False
+    diff_img = cv2.absdiff(self.image, other.image)
+    if np.amax(diff_img) > tolerance:

[slamm, 2014/10/21 23:21:58]

return np.amax(diff_imb) <= tolerance

[mthiesse, 2014/10/22 15:33:10]

Done.

       return False
-
-    # Loop over each pixel and test for equality
-    if tolerance or self.bpp != other.bpp:
-      for y in range(self.height):
-        for x in range(self.width):
-          c0 = self.GetPixelColor(x, y)
-          c1 = other.GetPixelColor(x, y)
-          if not c0.IsEqual(c1, tolerance):
-            return False
-    else:
-      return self.pixels == other.pixels
-
     return True
 
   def Diff(self, other):
-    """Returns a new Bitmap that represents the difference between this image
+    """Returns a new Bitmap that represents the difference between this Bitmap
     and another Bitmap."""
-
-    # Output dimensions will be the maximum of the two input dimensions
-    out_width = max(self.width, other.width)
-    out_height = max(self.height, other.height)
-
-    diff = [[0 for x in xrange(out_width * 3)] for x in xrange(out_height)]
-
-    # Loop over each pixel and write out the difference
-    for y in range(out_height):
-      for x in range(out_width):
-        if x < self.width and y < self.height:
-          c0 = self.GetPixelColor(x, y)
-        else:
-          c0 = RgbaColor(0, 0, 0, 0)
-
-        if x < other.width and y < other.height:
-          c1 = other.GetPixelColor(x, y)
-        else:
-          c1 = RgbaColor(0, 0, 0, 0)
-
-        offset = x * 3
-        diff[y][offset] = abs(c0.r - c1.r)
-        diff[y][offset+1] = abs(c0.g - c1.g)
-        diff[y][offset+2] = abs(c0.b - c1.b)
-
-    # This particular method can only save to a file, so the result will be
-    # written into an in-memory buffer and read back into a Bitmap
-    diff_img = png.from_array(diff, mode='RGB')
-    output = cStringIO.StringIO()
-    try:
-      diff_img.save(output)
-      diff = Bitmap.FromPng(output.getvalue())
-    finally:
-      output.close()
-
-    return diff
+    self_image = self.image
+    other_image = other.image
+    if self.image.shape[2] != other.image.shape[2]:
+      raise ValueError('Cannot diff images of differing bit depth')
+    if self.image.shape[:2] != other.image.shape[:2]:
+      width = max(self.width, other.width)
+      height = max(self.height, other.height)
+      self_image = np.zeros((width, height, self.image.shape[2]), np.uint8)
+      other_image = np.zeros((width, height, self.image.shape[2]), np.uint8)
+      self_image[0:self.height, 0:self.width] = self.image
+      other_image[0:other.height, 0:other.width] = other.image
+
+    return Bitmap(cv2.absdiff(self_image, other_image))
 
   def GetBoundingBox(self, color, tolerance=0):
-    """Finds the minimum box surrounding all occurences of |color|.
+    """Finds the minimum box surrounding all occurrences of bgr |color|.
     Returns: (top, left, width, height), match_count
     Ignores the alpha channel."""
-    return self._PrepareTools().BoundingBox(color, tolerance)
+    height, width = self.image.shape[:2]
+    img = self.image
+    left = 1e16
+    right = 0
+    top = 1e16

[flackr, 2014/10/21 21:50:10]

When possible, using legitimate input values is safer, i.e. left = width and top
= height.

[mthiesse, 2014/10/22 15:33:10]

Done.

+    bottom = 0
+    count = 0
+    for x in xrange(width):
+      for y in xrange(height):
+        if ColorsAreEqual(img[y][x], color, tolerance):
+          count += 1
+          left = min(left, x)
+          right = max(right, x + 1)
+          top = min(top, y)
+          bottom = max(bottom, y + 1)
+    if count == 0:
+      return None, 0
+    return (left, top, right - left, bottom - top), count
 
   def Crop(self, left, top, width, height):
     """Crops the current bitmap down to the specified box."""
-    cur_box = self._crop_box or (0, 0, self._width, self._height)
-    cur_left, cur_top, cur_width, cur_height = cur_box
-
+    img_height, img_width = self.image.shape[:2]
     if (left < 0 or top < 0 or
-        (left + width) > cur_width or
-        (top + height) > cur_height):
+        (left + width) > img_width or
+        (top + height) > img_height):
       raise ValueError('Invalid dimensions')
-
-    self._crop_box = cur_left + left, cur_top + top, width, height
+    self.image = self.image[top:top + height, left:left + width]
     return self
 
   def ColorHistogram(self, ignore_color=None, tolerance=0):

[tonyg, 2014/10/21 16:12:56]

Just curious how the runtime differs between the new and old methods. The old
ones were already a little too slow at calculating the speed index, I hope the
new ones are faster.

[mthiesse, 2014/10/21 18:40:58]

So, this is the test I'm running:
b1 = Bitmap.FromImageFile('test1.png')
b2 = Bitmap.FromImageFile('test2.png')
import time
start_time = time.time()
for i in xrange(100):
  hist1 = b1.ColorHistogram()
  hist2 = b2.ColorHistogram()
  hist1.Distance(hist2)
print time.time() - start_time

test1 and test2.png are 1080p screenshots.
master branch: 20.439s
my branch: 17.764s
Also, in my branch, most of the runtime comes from data type conversions.

These times exclude the PNG reading, which takes ~9.6s on master branch, and
~0.4s on my branch.

Now, if speed is really a concern, we shouldn't be using Earth Mover's Distance
at all; it's slow. Also, EMD, from my understanding of some papers I skimmed
through, is best for full image differences, not histogram differences. If we
were to switch to Bhattacharyya distance
(http://en.wikipedia.org/wiki/Bhattacharyya_distance), which has much better
openCV support than EMD, the above test runs in 0.814s!

     """Computes a histogram of the pixel colors in this Bitmap.
     Args:
-      ignore_color: An RgbaColor to exclude from the bucket counts.
+      ignore_color: (b, g, r), A color to exclude from the bucket counts.
       tolerance: A tolerance for the ignore_color.
 
     Returns:
       A ColorHistogram namedtuple with 256 integers in each field: r, g, and b.
     """
-    return self._PrepareTools().Histogram(ignore_color, tolerance)
+    flatten = np.ndarray.flatten
+    hist_b = flatten(cv2.calcHist([self.image], [0], None, [256], [0, 256]))
+    hist_g = flatten(cv2.calcHist([self.image], [1], None, [256], [0, 256]))
+    hist_r = flatten(cv2.calcHist([self.image], [2], None, [256], [0, 256]))
+    if ignore_color is not None:
+      ignore_b = ignore_color[0]
+      ignore_g = ignore_color[1]
+      ignore_r = ignore_color[2]
+      hist_b[max(ignore_b - tolerance, 0):ignore_b + tolerance + 1] = 0
+      hist_g[max(ignore_g - tolerance, 0):ignore_g + tolerance + 1] = 0
+      hist_r[max(ignore_r - tolerance, 0):ignore_r + tolerance + 1] = 0

[flackr, 2014/10/21 21:50:10]

If I'm reading this correctly. It seems like this will ignore all red, green and
blue values which are individually near one of the ignore color components.
Isn't the intent of ignore_color only to ignore when all three components are
near that color?

[mthiesse, 2014/10/22 15:33:10]

Ah, yes, good catch. Fixed and added a test case for this.

+    return ColorHistogram(hist_r, hist_g, hist_b, ignore_color)