[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..f175c246d25ed62a667bfb0d29fcaf57011e2b30 100644
--- a/tools/telemetry/telemetry/core/bitmap.py
+++ b/tools/telemetry/telemetry/core/bitmap.py
@@ -2,40 +2,30 @@
 # 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
+import numpy as np
 
 from telemetry.core import util
-from telemetry.core import platform
-from telemetry.util import support_binaries
-
 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 +33,46 @@ 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):
+  """Tests whether two colors are equal within the given tolerance.
+
+  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.
+  """
+  return np.amax(np.abs(np.subtract(color1, color2))) <= tolerance
+
+def BGRAColorAsInt(color):
+  """Converts a BGRA color to an int.
+
+  Args:
+    color: Tuple (b, g, r) or (b, g, r, a). Each channel must be uint8.
+
+  Returns:
+    An int representation of the color, where the 8 highest order bits are the
+    alpha channel (if present), followed by red, then green, then blue.
+  """
+  int_color = 0
+  for i, channel in enumerate(color):
+    int_color |= channel << i * 8
+  return int_color
 
 
 class ColorHistogram(
@@ -83,179 +104,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.
 
-  @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.
 
-  @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
+
+  @staticmethod
+  def FromRGBPixels(width, height, pixels, bpp=3):
+    """Create a bitmap from an array of rgb pixels.
+
+    Ignores alpha channel if present.
 
-  def _PrepareTools(self):
-    """Prepares an instance of _BitmapTools which allows exactly one command.
+    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 +170,66 @@ 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
-
-    # 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
+    diff_img = cv2.absdiff(self.image, other.image)
+    return np.amax(diff_img) <= tolerance
 
   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."""

[slamm, 2014/10/23 22:57:44]

Would you update the doc string to match our style guide while you are here?

One possibility:

"""Finds the minimum box surrounding all occurrences of bgr |color|.

Ignores the alpha channel.

Args:
  color: (b, g, r)  or (b, g, r, a); bounding box color.
  tolerance: tolerance for the bounding box color as an integer.

Returns:
  (top, left, width, height), match_count
"""

[mthiesse, 2014/10/24 14:48:12]

Done.

-    return self._PrepareTools().BoundingBox(color, tolerance)
+    img = cv2.inRange(self.image, np.subtract(color, tolerance),
+                      np.add(color, tolerance))
+    count = cv2.countNonZero(img)
+    if count == 0:
+      return None, 0
+    contours, _ = cv2.findContours(img, cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)

[slamm, 2014/10/23 22:57:44]

Use cv2.CV_CHAIN_APPROX_SIMPLE?

CV_CHAIN_APPROX_SIMPLE compresses horizontal, vertical, and diagonal segments
and leaves only their end points. For example, an up-right rectangular contour
is encoded with 4 points.
http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_desc...

[szym, 2014/10/23 23:17:07]

Since this is followed by boundingRect, I'm not sure approximating is going to
speed things much (I am guessing computing bounding box is easier than
simplifying a contour). CV_RETR_EXTERNAL might be more useful, but given that
we're dealing with something that is likely a solid color rectangle, I don't
think you'll see more than one contour in practice. I think mthiesse already hit
>99% of the optimization potential.

[mthiesse, 2014/10/24 14:48:12]

Acknowledged.

+    return cv2.boundingRect(contours[0]), count

[slamm, 2014/10/23 22:57:44]

I saw some talk of finding the contour with the maximum area. 

http://stackoverflow.com/questions/16538774/dealing-with-contours-and-boundin...

Perhaps you could just check that exactly one contour gets created.

[mthiesse, 2014/10/24 14:48:12]

Okay, what I've done instead is concatenated any contours (sets of points), then
computed the bounding box on that.

In the common case (a single rectangle) this will be a no-op, but for degenerate
cases, or for different future use cases where there might not be a nice
rectangle, this should compute a bounding box surrounding all occurrences of the
color correctly, and match the behavior of the bitmaptools.cc code.

 
   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):
     """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)
+    mask = None
+    if ignore_color is not None:
+      mask = ~cv2.inRange(self.image, np.subtract(ignore_color, tolerance),
+                          np.add(ignore_color, tolerance))
+
+    flatten = np.ndarray.flatten
+    hist_b = flatten(cv2.calcHist([self.image], [0], mask, [256], [0, 256]))
+    hist_g = flatten(cv2.calcHist([self.image], [1], mask, [256], [0, 256]))
+    hist_r = flatten(cv2.calcHist([self.image], [2], mask, [256], [0, 256]))
+    return ColorHistogram(hist_r, hist_g, hist_b, ignore_color)