Drawing circles like Photoshop's ellipse tool

user_10535296 0
Viewed 268

The Problem

I'm looking to draw a filled circle exactly like Photoshop's ellipse tool (down to the pixel).

I'm not trying to implement any anti-aliasing, so my problem can be viewed as a circular binary mask generation problem. Achieving the same circle seemed fairly straightforward on the outset, however, I've now implemented over 5 different circle drawing algorithms with none quite managing to match Photoshop for circle generation.

Attempted Solutions

I'm using Python for programming the algorithm, numpy for array manipulation, OpenCV for its circle drawing implementation/flood filling, and Scikit-Image for its image saving capabilities. I'm phrasing the problem as a function that draws a circle of a given radius and x,y location on a given image and returns a new image with the circle drawn on it.

I've programmed/used the following circle drawing implementations:

  1. Naive Pythagorean Approach
  2. OpenCV's Circle
  3. Bresenham's Circle
  4. The Arithmetic Circle
  5. Andres' Circle

Testing the Solutions

These algorithms were tested in two different scenarios: A small, 10px radius circle and a large, 257px radius circle. The small circles were used to compare more obvious visual differences, while the large circles were used to compute an error metric against a circle of the same radius generated in Photoshop.

Here are the results from these tests:

Small Circles Test

The six algorithms above were instructed to draw a 10px radius circle at the centre of a 40x40px image. I've combined all the results for ease of comparison.

Results

  • The blue circles are true, graphed circles scaled to fit the 20px diameter.

Large Circles Test

The six algorithms above were instructed to draw a 257px radius circle at the centre of a 2370x1770px image. Each of the algorithm generated circles was subtracted from a 257px radius circle drawn in Photoshop to get the difference.

For reference, the circle generated in Photoshop is here:

here

Naive Pythagorean:

  • Pixels Different: 1082
  • Image of Difference Result:

Results

OpenCV:

  • Pixels Different: 724
  • Image of Difference Result:

Results

Bresenham:

  • Pixels Different: 251
  • Image of Difference Result:

Results

Midpoint:

  • Pixels Different: 224
  • Image of Difference:

Results

Arithmetic Circle:

Optimization was performed on parameters in this implementation.

  • Pixels Different (without optimization): 155
  • Pixels Different (with optimization): 107 (Best Result)
  • Image of Difference (with optimization):

Results

Andres' Circle:

  • Pixels Difference: 155
  • Image of Difference:

Results

Final Thoughts

At this stage, I've had the most success with using the Arithmetic circle algorithm, however, I'm still not 100% convinced that tweaking this algorithm will allow for emulation of Photoshop's ellipse drawing behaviour.

There are a couple edge cases when drawing circles in Photoshop that I've had no success in replicating whatsoever. Eg: A 2x2px circle is drawn as a 2x1 pixel rectangle.

Another odd behaviour is that circles at certain radius don't exhibit the octant symmetry utilized in most circle drawing behaviours. I would assume this is because the ellipse tool is for drawing ellipses which only exhibit quadrant symmetry. So even if a circle is being drawn that has octant symmetry, quadrants are still drawn, maybe?

As a final bit of food for thought, I drew overlapping circles in Photoshop of decreasing radius and alternating colour. Star-shaped geometry can be seen which is fairly similar to Bresenham circles drawn in a similar manner. This makes me wonder if Photoshop is using a modified Bresenham circle?

colored

Anyways, thanks for reading up to this point! It would be great to get some input on what I could do to make this more accurate.

Thank you!

Code

The code for the above testing/implementations follows:

import math

from skimage import io
import cv2
import numpy as np


def draw_octant_half_integer(circle_img, centre_x, centre_y, x, y):

    circle_img[centre_x + x, centre_y + y] = 255
    circle_img[centre_x + x, centre_y - y + 1] = 255
    circle_img[centre_x - x + 1, centre_y + y] = 255
    circle_img[centre_x - x + 1, centre_y - y + 1] = 255
    circle_img[centre_x + y, centre_y + x] = 255
    circle_img[centre_x + y, centre_y - x + 1] = 255
    circle_img[centre_x - y + 1, centre_y + x] = 255
    circle_img[centre_x - y + 1, centre_y - x + 1] = 255


def draw_octant(img, centre_x, centre_y, x, y):

    img[centre_x + x, centre_y + y] = 255
    img[centre_x - x, centre_y + y] = 255
    img[centre_x + x, centre_y - y] = 255
    img[centre_x - x, centre_y - y] = 255
    img[centre_x + y, centre_y + x] = 255
    img[centre_x - y, centre_y + x] = 255
    img[centre_x + y, centre_y - x] = 255
    img[centre_x - y, centre_y - x] = 255


def create_pythagorean_circle(img, centre_x, centre_y, radius):

    def point_on_circumference(x, y, centre_x, centre_y, radius):

        x -= centre_y
        y -= centre_x
        hypot = math.sqrt(x*x + y*y)

        return hypot >= radius - 0.5 and hypot <= radius + 0.5

    circle_img = img.copy()
    height, width = circle_img.shape
    for y in range(0, height):
        for x in range(0, width):
            if point_on_circumference(x, y, centre_x, centre_y, radius):
                circle_img[x, y] = 255

    cv2.floodFill(circle_img, None, (int(centre_x), int(centre_y)), 255)

    return circle_img


def create_bresenham_circle(img, centre_y, centre_x, radius):

    height, width = img.shape
    circle_img = img.copy()
    x = 0
    y = radius
    d = 3 - 2 * radius

    draw_octant_half_integer(circle_img, centre_x, centre_y, x, y)
    while y >= x:
        x += 1
        if d > 0:
            y -= 1
            d = d + 4 * (x - y) - 10
        else:
            d = d + 4 * x + 6
        draw_octant_half_integer(circle_img, centre_x, centre_y, x, y)

    cv2.floodFill(circle_img, None, (int(centre_y), int(centre_x)), 255)
    return circle_img


def create_midpoint_circle(img, centre_y, centre_x, radius):

    x = radius
    y = 0
    circle_img = img.copy()
    p = 1 - radius

    circle_img[centre_x + x, centre_y + y] = 255
    if radius > 0:
        circle_img[centre_x + y, centre_y - x] = 255
        circle_img[centre_x - x + 1, centre_y + y] = 255
        circle_img[centre_x - y + 1, centre_y + x] = 255

    while x > y:
        y += 1
        if p < -1:
            p = p + 2 * y + 1
        else:
            x -= 1
            p = p + 2 * y - 2 * x + 1
        if x < y:
            break

        circle_img[centre_x + x, centre_y + y] = 255
        circle_img[centre_x - x + 1, centre_y + y] = 255
        circle_img[centre_x + x, centre_y - y + 1] = 255
        circle_img[centre_x - x + 1, centre_y - y + 1] = 255

        if x != y:
            circle_img[centre_x + y, centre_y + x] = 255
            circle_img[centre_x - y + 1, centre_y + x] = 255
            circle_img[centre_x + y, centre_y - x + 1] = 255
            circle_img[centre_x - y + 1, centre_y - x + 1] = 255

    cv2.floodFill(circle_img, None, (int(centre_y), int(centre_x)), 255)
    return circle_img


def create_arithmetic_circle(img, centre_x, centre_y, radius, up=0.5, down=0.5):

    def decision_parameter(x, y):
        hypot = x**2 + y**2
        return (radius - up)**2 <= hypot and hypot <= (radius + down)**2

    x = 1
    y = radius
    circle_img = img.copy()

    while y >= x:
        draw_octant_half_integer(circle_img, centre_x, centre_y, x, y)
        if decision_parameter(x, y - 1):
            y -= 1
        elif decision_parameter(x + 1, y):
            x += 1
        else:
            x += 1
            y -= 1

    circle_img = circle_img.astype(np.uint8)
    cv2.floodFill(circle_img, None, (int(centre_y), int(centre_x)), 255)
    return circle_img


def andres_circle(img, centre_x, centre_y, radius):

    x = 0
    y = int(radius)
    d = radius - 1
    circle_img = img.copy()

    while y >= x:
        draw_octant_half_integer(circle_img, centre_x, centre_y, x, y)
        if d <= 2 * (radius - y):
            d += 2 * y - 1
            y -= 1
        elif d > 2 * x:
            d -= 2 * x + 1
            x += 1
        else:
            d += 2 * (y - x - 1)
            x += 1
            y -= 1

    circle_img = circle_img.astype(np.uint8)
    cv2.floodFill(circle_img, None, (int(centre_y), int(centre_x)), 255)
    return circle_img


if __name__ == "__main__":

    # Loading Constants

    photoshop_circle = cv2.imread("photoshop_circle.png", cv2.IMREAD_GRAYSCALE)
    width = 2370
    height = 1770
    centre_x = width/2
    centre_y = height/2
    radius = 257
    img = np.zeros((height, width))
    img = img.astype(np.uint8)

    # Optimizing Arithmetic Circle

    # lowest_mse = np.inf
    # lowest_up = 0
    # lowest_down = 0
    # for up in np.linspace(0.76, 0.77, 100):
    #     for down in np.linspace(0.49, 0.50, 100):
    #         circle = create_arithmetic_circle(img, int(round(centre_y))-1, int(round(centre_x))-1, radius, up=up, down=down)
    #         diff = photoshop_circle - circle
    #         mse = np.sum(diff**2)
    #         print("MSE:", mse, "Up:", up, "Down:", down)

    #         if mse < lowest_mse:
    #             lowest_mse = mse
    #             lowest_up = up
    #             lowest_down = down

    # print("Optimal MSE:", lowest_mse, "Optimal Up:", lowest_up, "Lowest Down:", lowest_down)

    # Drawing/Computing Difference

    # circle = createPythagorasCircle(img, centre_x, centre_y, radius)
    # circle = cv2.circle(img.copy(), (int(centre_x), int(centre_y)), radius, 255, cv2.FILLED)
    # circle = create_bresenham_circle(img, int(round(centre_x))-1, int(round(centre_y))-1, radius)
    # circle = createMidpointCircle(img, int(round(centre_x))-1, int(round(centre_y))-1, radius)
    # Unoptimized
    # circle = create_arithmetic_circle(img, int(round(centre_y))-1, int(round(centre_x))-1, radius)
    # Optimized
    # circle = create_arithmetic_circle(img, int(round(centre_y))-1, int(round(centre_x))-1, radius, up=0.7638, down=0.4976)
    circle = andres_circle(img, int(round(centre_y))-1, int(round(centre_x))-1, radius)

    diff = photoshop_circle - circle
    diff[diff > 0] = 1
    error = np.sum(diff)
    print("Pixels Different:", error, "Radius:", radius)

    diff[diff < 0] = 255
    diff[diff > 0] = 255
    io.imsave("circle.png", diff, check_contrast=False)
pixel drawing geometry algorithm python
0 Answers
Related