text: from __future__ import (absolute_import, division, print_function,
                          unicode_literals)
  import six
  import warnings
  import logging
  
  import numpy as np
  import pandas as pd
  from scipy import ndimage
  from scipy.spatial import cKDTree
  
  from .utils import validate_tuple
  from .masks import binary_mask
  from .preprocessing import convert_to_int
  
  logger = logging.getLogger(__name__)
  
  
  def where_close(pos, separation, intensity=None):
      """ Returns indices of features that are closer than separation from other
      features. When intensity is given, the one with the lowest intensity is
      returned: else the most topleft is returned (to avoid randomness)"""
      if len(pos) == 0:
          return []
      separation = validate_tuple(separation, pos.shape[1])
      if any([s == 0 for s in separation]):
          return []
      # Rescale positions, so that pairs are identified below a distance
      # of 1.
      if isinstance(pos, pd.DataFrame):
          pos_rescaled = pos.values / separation
      else:
          pos_rescaled = pos / separation
      duplicates = cKDTree(pos_rescaled, 30).query_pairs(1 - 1e-7)
      if len(duplicates) == 0:
          return []
      index_0 = np.fromiter((x[0] for x in duplicates), dtype=int)
      index_1 = np.fromiter((x[1] for x in duplicates), dtype=int)
      if intensity is None:
          to_drop = np.where(np.sum(pos_rescaled[index_0], 1) >
                             np.sum(pos_rescaled[index_1], 1),
                             index_1, index_0)
      else:
          intensity = np.asarray(intensity)
          intensity_0 = intensity[index_0]
          intensity_1 = intensity[index_1]
          to_drop = np.where(intensity_0 > intensity_1, index_1, index_0)
          edge_cases = intensity_0 == intensity_1
          if np.any(edge_cases):
              index_0 = index_0[edge_cases]
              index_1 = index_1[edge_cases]
              to_drop[edge_cases] = np.where(np.sum(pos_rescaled[index_0], 1) >
                                             np.sum(pos_rescaled[index_1], 1),
                                             index_1, index_0)
      return np.unique(to_drop)
  
  
  def drop_close(pos, separation, intensity=None):
      """ Removes features that are closer than separation from other features.
      When intensity is given, the one with the lowest intensity is dropped:
      else the most topleft is dropped (to avoid randomness)"""
      to_drop = where_close(pos, separation, intensity)
      return np.delete(pos, to_drop, axis=0)
  
  
  def percentile_threshold(image, percentile):
      """Find grayscale threshold based on distribution in image."""
  
      not_black = image[np.nonzero(image)]
      if len(not_black) == 0:
          return np.nan
      return np.percentile(not_black, percentile)
  
  
  def grey_dilation(image, separation, percentile=64, margin=None, precise=True):
      """Find local maxima whose brightness is above a given percentile.
  
      Parameters
      ----------
      image : ndarray
          For best performance, provide an integer-type array. If the type is not
          of integer-type, the image will be normalized and coerced to uint8.
      separation : number or tuple of numbers
          Minimum separation between maxima. See precise for more information.
      percentile : float in range of [0,100], optional
          Features must have a peak brighter than pixels in this percentile.
          This helps eliminate spurious peaks. Default 64.
      margin : integer or tuple of integers, optional
          Zone of exclusion at edges of image. Default is ``separation / 2``.
      precise : boolean, optional
          Determines whether there will be an extra filtering step (``drop_close``)
          discarding features that are too close. Degrades performance.
          Because of the square kernel used, too many features are returned when
          precise=False. Default True.
  
      See Also
      --------
      drop_close : removes features that are too close to brighter features
      grey_dilation_legacy : local maxima finding routine used until trackpy v0.3
      """
      # convert to integer. does nothing if image is already of integer type
      factor, image = convert_to_int(image, dtype=np.uint8)
  
      ndim = image.ndim
      separation = validate_tuple(separation, ndim)
      if margin is None:
          margin = tuple([int(s / 2) for s in separation])
  
      # Compute a threshold based on percentile.
      threshold = percentile_threshold(image, percentile)
      if np.isnan(threshold):
          warnings.warn("Image is completely black.", UserWarning)
          return np.empty((0, ndim))
  
      # Find the largest box that fits inside the ellipse given by separation
      size = [int(2 * s / np.sqrt(ndim)) for s in separation]
  
      # The intersection of the image with its dilation gives local maxima.
      dilation = ndimage.grey_dilation(image, size, mode='constant')
      maxima = (image == dilation) & (image > threshold)
      if np.sum(maxima) == 0:
          warnings.warn("Image contains no local maxima.", UserWarning)
          return np.empty((0, ndim))
  
      pos = np.vstack(np.where(maxima)).T
  
      # Do not accept peaks near the edges.
      shape = np.array(image.shape)
      near_edge = np.any((pos < margin) | (pos > (shape - margin - 1)), 1)
      pos = pos[~near_edge]
  
      if len(pos) == 0:
          warnings.warn("All local maxima were in the margins.", UserWarning)
          return np.empty((0, ndim))
  
      # Remove local maxima that are too close to each other
      if precise:
          pos = drop_close(pos, separation, image[maxima][~near_edge])
  
      return pos
  
  
  def grey_dilation_legacy(image, separation, percentile=64, margin=None):
      """Find local maxima whose brightness is above a given percentile.
  
      Parameters
      ----------
      separation : minimum separation between maxima
      percentile : chooses minimum greyscale value for a local maximum
      margin : zone of exclusion at edges of image. Defaults to radius.
              A smarter value is set by locate().
  
      See Also
      --------
      grey_dilation : faster local maxima finding routine
      """
      if margin is None:
          margin = separation
  
      ndim = image.ndim
      # Compute a threshold based on percentile.
      threshold = percentile_threshold(image, percentile)
      if np.isnan(threshold):
          warnings.warn("Image is completely black.", UserWarning)
          return np.empty((0, ndim))
  
      if not np.issubdtype(image.dtype, np.integer):
          factor = 255 / image.max()
          image = (factor * image.clip(min=0.)).astype(np.uint8)
  
      # The intersection of the image with its dilation gives local maxima
      footprint = binary_mask(separation, ndim)
      dilation = ndimage.grey_dilation(image, footprint=footprint,
                                       mode='constant')
      maxima = np.vstack(np.where((image == dilation) & (image > threshold))).T
      if not np.size(maxima) > 0:
          warnings.warn("Image contains no local maxima.", UserWarning)
          return np.empty((0, ndim))
  
      # Do not accept peaks near the edges.
      shape = np.array(image.shape)
      near_edge = np.any((maxima < margin) | (maxima > (shape - margin - 1)), 1)
      maxima = maxima[~near_edge]
      if not np.size(maxima) > 0:
          warnings.warn("All local maxima were in the margins.", UserWarning)
  
      # Return coords in as a numpy array shaped so it can be passed directly
      # to the DataFrame constructor.
      return maxima
  