_chan_vese.py

import numpy as np
from scipy.ndimage import distance_transform_edt as distance

from .._shared.utils import _supported_float_type


def _cv_calculate_variation(image, phi, mu, lambda1, lambda2, dt):
    """Returns the variation of level set 'phi' based on algorithm parameters.

    This corresponds to equation (22) of the paper by Pascal Getreuer,
    which computes the next iteration of the level set based on a current
    level set.

    A full explanation regarding all the terms is beyond the scope of the
    present description, but there is one difference of particular import.
    In the original algorithm, convergence is accelerated, and required
    memory is reduced, by using a single array. This array, therefore, is a
    combination of non-updated and updated values. If this were to be
    implemented in python, this would require a double loop, where the
    benefits of having fewer iterations would be outweided by massively
    increasing the time required to perform each individual iteration. A
    similar approach is used by Rami Cohen, and it is from there that the
    C1-4 notation is taken.
    """
    eta = 1e-16
    P = np.pad(phi, 1, mode='edge')

    phixp = P[1:-1, 2:] - P[1:-1, 1:-1]
    phixn = P[1:-1, 1:-1] - P[1:-1, :-2]
    phix0 = (P[1:-1, 2:] - P[1:-1, :-2]) / 2.0

    phiyp = P[2:, 1:-1] - P[1:-1, 1:-1]
    phiyn = P[1:-1, 1:-1] - P[:-2, 1:-1]
    phiy0 = (P[2:, 1:-1] - P[:-2, 1:-1]) / 2.0

    C1 = 1.0 / np.sqrt(eta + phixp**2 + phiy0**2)
    C2 = 1.0 / np.sqrt(eta + phixn**2 + phiy0**2)
    C3 = 1.0 / np.sqrt(eta + phix0**2 + phiyp**2)
    C4 = 1.0 / np.sqrt(eta + phix0**2 + phiyn**2)

    K = P[1:-1, 2:] * C1 + P[1:-1, :-2] * C2 + P[2:, 1:-1] * C3 + P[:-2, 1:-1] * C4

    Hphi = (phi > 0).astype(image.dtype)
    (c1, c2) = _cv_calculate_averages(image, Hphi)

    difference_from_average_term = (
        -lambda1 * (image - c1) ** 2 + lambda2 * (image - c2) ** 2
    )
    new_phi = phi + (dt * _cv_delta(phi)) * (mu * K + difference_from_average_term)
    return new_phi / (1 + mu * dt * _cv_delta(phi) * (C1 + C2 + C3 + C4))


def _cv_heavyside(x, eps=1.0):
    """Returns the result of a regularised heavyside function of the
    input value(s).
    """
    return 0.5 * (1.0 + (2.0 / np.pi) * np.arctan(x / eps))


def _cv_delta(x, eps=1.0):
    """Returns the result of a regularised dirac function of the
    input value(s).
    """
    return eps / (eps**2 + x**2)


def _cv_calculate_averages(image, Hphi):
    """Returns the average values 'inside' and 'outside'."""
    H = Hphi
    Hinv = 1.0 - H
    Hsum = np.sum(H)
    Hinvsum = np.sum(Hinv)
    avg_inside = np.sum(image * H)
    avg_oustide = np.sum(image * Hinv)
    if Hsum != 0:
        avg_inside /= Hsum
    if Hinvsum != 0:
        avg_oustide /= Hinvsum
    return (avg_inside, avg_oustide)


def _cv_difference_from_average_term(image, Hphi, lambda_pos, lambda_neg):
    """Returns the 'energy' contribution due to the difference from
    the average value within a region at each point.
    """
    (c1, c2) = _cv_calculate_averages(image, Hphi)
    Hinv = 1.0 - Hphi
    return lambda_pos * (image - c1) ** 2 * Hphi + lambda_neg * (image - c2) ** 2 * Hinv


def _cv_edge_length_term(phi, mu):
    """Returns the 'energy' contribution due to the length of the
    edge between regions at each point, multiplied by a factor 'mu'.
    """
    P = np.pad(phi, 1, mode='edge')
    fy = (P[2:, 1:-1] - P[:-2, 1:-1]) / 2.0
    fx = (P[1:-1, 2:] - P[1:-1, :-2]) / 2.0
    return mu * _cv_delta(phi) * np.sqrt(fx**2 + fy**2)


def _cv_energy(image, phi, mu, lambda1, lambda2):
    """Returns the total 'energy' of the current level set function.

    This corresponds to equation (7) of the paper by Pascal Getreuer,
    which is the weighted sum of the following:
    (A) the length of the contour produced by the zero values of the
    level set,
    (B) the area of the "foreground" (area of the image where the
    level set is positive),
    (C) the variance of the image inside the foreground,
    (D) the variance of the image outside of the foreground

    Each value is computed for each pixel, and then summed. The weight
    of (B) is set to 0 in this implementation.
    """
    H = _cv_heavyside(phi)
    avgenergy = _cv_difference_from_average_term(image, H, lambda1, lambda2)
    lenenergy = _cv_edge_length_term(phi, mu)
    return np.sum(avgenergy) + np.sum(lenenergy)


def _cv_reset_level_set(phi):
    """This is a placeholder function as resetting the level set is not
    strictly necessary, and has not been done for this implementation.
    """
    return phi


def _cv_checkerboard(image_size, square_size, dtype=np.float64):
    """Generates a checkerboard level set function.

    According to Pascal Getreuer, such a level set function has fast
    convergence.
    """
    yv = np.arange(image_size[0], dtype=dtype).reshape(image_size[0], 1)
    xv = np.arange(image_size[1], dtype=dtype)
    sf = np.pi / square_size
    xv *= sf
    yv *= sf
    return np.sin(yv) * np.sin(xv)


def _cv_large_disk(image_size):
    """Generates a disk level set function.

    The disk covers the whole image along its smallest dimension.
    """
    res = np.ones(image_size)
    centerY = int((image_size[0] - 1) / 2)
    centerX = int((image_size[1] - 1) / 2)
    res[centerY, centerX] = 0.0
    radius = float(min(centerX, centerY))
    return (radius - distance(res)) / radius


def _cv_small_disk(image_size):
    """Generates a disk level set function.

    The disk covers half of the image along its smallest dimension.
    """
    res = np.ones(image_size)
    centerY = int((image_size[0] - 1) / 2)
    centerX = int((image_size[1] - 1) / 2)
    res[centerY, centerX] = 0.0
    radius = float(min(centerX, centerY)) / 2.0
    return (radius - distance(res)) / (radius * 3)


def _cv_init_level_set(init_level_set, image_shape, dtype=np.float64):
    """Generates an initial level set function conditional on input arguments."""
    if isinstance(init_level_set, str):
        if init_level_set == 'checkerboard':
            res = _cv_checkerboard(image_shape, 5, dtype)
        elif init_level_set == 'disk':
            res = _cv_large_disk(image_shape)
        elif init_level_set == 'small disk':
            res = _cv_small_disk(image_shape)
        else:
            raise ValueError("Incorrect name for starting level set preset.")
    else:
        res = init_level_set
    return res.astype(dtype, copy=False)


def chan_vese(
    image,
    mu=0.25,
    lambda1=1.0,
    lambda2=1.0,
    tol=1e-3,
    max_num_iter=500,
    dt=0.5,
    init_level_set='checkerboard',
    extended_output=False,
):
    """Chan-Vese segmentation algorithm.

    Active contour model by evolving a level set. Can be used to
    segment objects without clearly defined boundaries.

    Parameters
    ----------
    image : (M, N) ndarray
        Grayscale image to be segmented.
    mu : float, optional
        'edge length' weight parameter. Higher `mu` values will
        produce a 'round' edge, while values closer to zero will
        detect smaller objects.
    lambda1 : float, optional
        'difference from average' weight parameter for the output
        region with value 'True'. If it is lower than `lambda2`, this
        region will have a larger range of values than the other.
    lambda2 : float, optional
        'difference from average' weight parameter for the output
        region with value 'False'. If it is lower than `lambda1`, this
        region will have a larger range of values than the other.
    tol : float, positive, optional
        Level set variation tolerance between iterations. If the
        L2 norm difference between the level sets of successive
        iterations normalized by the area of the image is below this
        value, the algorithm will assume that the solution was
        reached.
    max_num_iter : uint, optional
        Maximum number of iterations allowed before the algorithm
        interrupts itself.
    dt : float, optional
        A multiplication factor applied at calculations for each step,
        serves to accelerate the algorithm. While higher values may
        speed up the algorithm, they may also lead to convergence
        problems.
    init_level_set : str or (M, N) ndarray, optional
        Defines the starting level set used by the algorithm.
        If a string is inputted, a level set that matches the image
        size will automatically be generated. Alternatively, it is
        possible to define a custom level set, which should be an
        array of float values, with the same shape as 'image'.
        Accepted string values are as follows.

        'checkerboard'
            the starting level set is defined as
            sin(x/5*pi)*sin(y/5*pi), where x and y are pixel
            coordinates. This level set has fast convergence, but may
            fail to detect implicit edges.
        'disk'
            the starting level set is defined as the opposite
            of the distance from the center of the image minus half of
            the minimum value between image width and image height.
            This is somewhat slower, but is more likely to properly
            detect implicit edges.
        'small disk'
            the starting level set is defined as the
            opposite of the distance from the center of the image
            minus a quarter of the minimum value between image width
            and image height.
    extended_output : bool, optional
        If set to True, the return value will be a tuple containing
        the three return values (see below). If set to False which
        is the default value, only the 'segmentation' array will be
        returned.

    Returns
    -------
    segmentation : (M, N) ndarray, bool
        Segmentation produced by the algorithm.
    phi : (M, N) ndarray of floats
        Final level set computed by the algorithm.
    energies : list of floats
        Shows the evolution of the 'energy' for each step of the
        algorithm. This should allow to check whether the algorithm
        converged.

    Notes
    -----
    The Chan-Vese Algorithm is designed to segment objects without
    clearly defined boundaries. This algorithm is based on level sets
    that are evolved iteratively to minimize an energy, which is
    defined by weighted values corresponding to the sum of differences
    intensity from the average value outside the segmented region, the
    sum of differences from the average value inside the segmented
    region, and a term which is dependent on the length of the
    boundary of the segmented region.

    This algorithm was first proposed by Tony Chan and Luminita Vese,
    in a publication entitled "An Active Contour Model Without Edges"
    [1]_.

    This implementation of the algorithm is somewhat simplified in the
    sense that the area factor 'nu' described in the original paper is
    not implemented, and is only suitable for grayscale images.

    Typical values for `lambda1` and `lambda2` are 1. If the
    'background' is very different from the segmented object in terms
    of distribution (for example, a uniform black image with figures
    of varying intensity), then these values should be different from
    each other.

    Typical values for mu are between 0 and 1, though higher values
    can be used when dealing with shapes with very ill-defined
    contours.

    The 'energy' which this algorithm tries to minimize is defined
    as the sum of the differences from the average within the region
    squared and weighed by the 'lambda' factors to which is added the
    length of the contour multiplied by the 'mu' factor.

    Supports 2D grayscale images only, and does not implement the area
    term described in the original article.

    References
    ----------
    .. [1] An Active Contour Model without Edges, Tony Chan and
           Luminita Vese, Scale-Space Theories in Computer Vision,
           1999, :DOI:`10.1007/3-540-48236-9_13`
    .. [2] Chan-Vese Segmentation, Pascal Getreuer Image Processing On
           Line, 2 (2012), pp. 214-224,
           :DOI:`10.5201/ipol.2012.g-cv`
    .. [3] The Chan-Vese Algorithm - Project Report, Rami Cohen, 2011
           :arXiv:`1107.2782`
    """
    if len(image.shape) != 2:
        raise ValueError("Input image should be a 2D array.")

    float_dtype = _supported_float_type(image.dtype)
    phi = _cv_init_level_set(init_level_set, image.shape, dtype=float_dtype)

    if type(phi) != np.ndarray or phi.shape != image.shape:
        raise ValueError(
            "The dimensions of initial level set do not "
            "match the dimensions of image."
        )

    image = image.astype(float_dtype, copy=False)
    image = image - np.min(image)
    if np.max(image) != 0:
        image = image / np.max(image)

    i = 0
    old_energy = _cv_energy(image, phi, mu, lambda1, lambda2)
    energies = []
    phivar = tol + 1
    segmentation = phi > 0

    while phivar > tol and i < max_num_iter:
        # Save old level set values
        oldphi = phi

        # Calculate new level set
        phi = _cv_calculate_variation(image, phi, mu, lambda1, lambda2, dt)
        phi = _cv_reset_level_set(phi)
        phivar = np.sqrt(((phi - oldphi) ** 2).mean())

        # Extract energy and compare to previous level set and
        # segmentation to see if continuing is necessary
        segmentation = phi > 0
        new_energy = _cv_energy(image, phi, mu, lambda1, lambda2)

        # Save old energy values
        energies.append(old_energy)
        old_energy = new_energy
        i += 1

    if extended_output:
        return (segmentation, phi, energies)
    else:
        return segmentation