perfect_circle.py

"""
Determine whether a circle is a "Perfect Circle" or not.

To use this module you need:
  python3.6
  PIL (https://pillow.readthedocs.io/en/4.2.x/installation.html#basic-installation)
  
>>> from perfect_circle import is_perfect_circle
>>> from PIL import Image
>>> image = Image.open('/some/path/to/circle.jpg')
>>> print(is_perfect_circle(image))
"""

def curve(n):
    """
    The curve which we expect a collapsed circle to follow.

    This gives us a fact which we can compare the collapsed circle to.

    :param n:
    :return:
    """
    return (4-(2*n)**2)**.5

def left_to_right(image):
    """
    Return each column of the image from left to right.

    :param image:
    :return:
    """
    for x in range(image.width):
        yield [image.getpixel((x, y)) for y in range(image.height)]

def top_to_bottom(image):
    """
    Return each row of the image from top to bottom.

    :param image:
    :return:
    """
    for y in range(image.height):
        yield [image.getpixel((x, y)) for x in range(image.width)]

def frange(start, stop, step=0.1):
    """
    range function except for floats.

    :param start:
    :param stop:
    :param step:
    :return:
    """
    while start < stop:
        yield start
        start += step

def calc_score(test_curve):
    smallest_number = min(test_curve)

    # Set the baseline of the curve to 0.
    test_curve = list(map(lambda x: x - smallest_number, test_curve))

    # Convert the curve to something we can compare with our fact curve.
    #
    # In this case we set the value to a float between 0 and 2 where 0
    # was the smallest number in the list and 2 was the largest
    # number in the list.
    test_curve = list(map(lambda x: x / (max(test_curve) / 2), test_curve))

    # Here we create our fact curve.
    #
    # This should make a perfect curve which has the same width as the circle
    # but 2x the height.
    fact_curve = [round(curve(x) ,3) for x in frange(-1, 1, 2 / float(len(test_curve)))]

    scores = []
    for a, b in zip(test_curve, fact_curve):
        # Get the absolute value of the difference between what we expected and what we got.
        #
        # We divide by 2 because our fact curve and test curve max is 2 and we want
        # the score to be a percentage.
        score = abs(a-b) / 2
        scores.append(score)

    # Get the average of the scores.
    #
    # Subtract average from 1 so that we get 98% match on a 2% difference between the fact and test.
    return 1-(sum(scores)/len(scores))

def horizontal_score(image):
    """
    Get the score of the circle from left to right.

    :param image:
    :return:
    """
    data = []
    for row in top_to_bottom(image):
        # Only get pixels which are black.
        l = [i for i in row if not i]
        # If the list is empty then it only contained whitespace.
        if not l:
            continue
        data.append(len(l))
    return calc_score(data)

def vertical_score(image):
    """
    Get the score of the circle from top to bottom.

    :param image:
    :return:
    """
    data = []
    for row in left_to_right(image):
        # Only get pixels which are black.
        l = [i for i in row if not i]
        # If the list is empty then it only contained whitespace.
        if not l:
            continue
        data.append(len(l))
    return calc_score(data)

def circle_percentage(image):
    """
    Return a percentage of how close to a perfect circle the circle in the image is.
    
    :param image: 
    :return: 
    """
    # Convert to greyscale.
    image = image.convert('1')

    h_score = horizontal_score(image)
    v_score = vertical_score(image)
    return (h_score + v_score) / 2

def is_perfect_circle(image, threshold=0.9):
    """
    Test if the circle is perfect.

    :param image: PIL.Image object.
    :param threshold: Minimum percentage which is acceptable to be considered a "perfect circle".
    :return: True if calculated percentage is greater than the threshold.
    """
    return circle_percentage(image) > threshold