'draw' a random rhombus (diamond) on a numpy array (testing harris corner detection)

Question

I'm trying to create a random test for a "harris_corner_detector" function implementation (VERY GENERALLY AND SLIGHTLY INCORRECTLY: a function that finds corners in an image) In the test, I want to create random simple shapes in a binary numpy matrix (it's easy to know the coordinates of their corners) (e.g rectangles, triangles, rhombus (diamond) etc...) and check if the harris implementation finds the correct corners.

I already implemented a function that randomly 'draws' an axis parallel rectangle, but i can't find an efficient way to do so when it comes to shapes that are not parallel to the axes.

To create a random rectangle, I randomly choose a starting point and an ending point on both axes and I change the value of all of the cells within those bounds like so:

getting the random coords:

    def _get_random_coords(self, start, end):
        x_start, y_start = np.random.randint(start, end, 2)
        x_end = np.random.randint(x_start + 7, end + 20)
        y_end = np.random.randint(y_start + 7, end + 20)
        return (x_start, x_end, y_start, y_end)

drawing the random rectangle (values are 255 for the background and 0 for the shape):

mat = np.ones((1024, 1024)) * 255
mat[x_start: x_end, y_start: y_end] = np.zeros((x_end - x_start, y_end - y_start))

but when it comes to drawing a diamond shape efficiently I'm at a loss. All I can think about is to run a loop that creates the diamond like so:

    def _get_rhombus(self, size):
        rhombus = []
        for i in range(size):
            rhombus.append(np.zeros(i+1))
        for i in range(size - 1, 0, -1):
            rhombus.append(np.zeros(i))
        return np.array(rhombus)

and then another loop to add it to the larger matrix. But this method is highly inefficient when it comes to testing (as I'll draw hundreds of them, some of them might be huge).

Any better ideas out there? Alternatively - is there a better way to test this?

Thanks in advance.

Answer 1

There are a number of questions here, but the main one is how to create a numpy array of a filled rhombus given the corners. I'll answer that, and leave other questios, like creating random rhombuses, etc.

To fill a convex polygon, one can find the line specified by subsequent corners and fill above or below that line, and then and all the filled areas together.

import numpy as np
import matplotlib.pyplot as plt

# given two (non-vertical) points, A and B, 
# fill above or below the line connecting them
def fill(A, B, fill_below=True, xs=10, ys=12):

    # the equation for a line is y = m*x + b, so calculate
    # m and b from the two points on the line
    m = (B[1]-A[1])/(B[0]-A[0]) # m = (y2 - y1)/(x2 - x1) = slope
    b = A[1] - m*A[0]           # b = y1 - m*x1 = y intercept

    # for each points of the grid, calculate whether it's above, below, or on
    # the line. Since y = m*x + b, calculating m*x + b - y will give
    # 0 when on the line, <0 when above, and >0 when below
    Y, X = np.mgrid[0:ys, 0:xs] 
    L = m*X + b - Y

    # select whether, >=0 is True, or, <=0 is True, to determine whether to
    # fill above or below the line
    op = np.greater_equal if fill_below else np.less_equal
    return op(L, 0.0)

Here's a simple low-res rhombus

r = fill((0, 3), (3, 8), True) & \
fill((3, 8), (7, 4), True) & \
fill((7,4), (5,0), False) & \
fill((5,0), (0,3), False)
plt.imshow(r, cmap='Greys',  interpolation='nearest', origin='lower')

That is, the above figure is the result of and-ing together the following fills:

fig, ax = plt.subplots(1, 4, figsize=(10, 3))
fill_params = [((0, 3), (3, 8), True), ((3, 8), (7, 4), True), ((7, 4), (5, 0), False), ((5, 0), (0, 3), False)]
for p, ax in zip(fill_params, ax):
    ax.imshow(fill(*p), cmap="Greys", interpolation='nearest', origin='lower')

Or, one could do high-res, and it can have multiple sides (although I think it must be convex).

r = fill((0, 300), (300, 800), True, 1000, 1200) & \
fill((300, 800), (600,700), True, 1000, 1200) & \
fill((600, 700), (700, 400), True, 1000, 1200) & \
fill((700,400), (500,0), False, 1000, 1200) & \
fill((500,0), (100,100), False, 1000, 1200) & \
fill((100, 100), (0,300), False, 1000, 1200)
plt.imshow(r, cmap='Greys',  interpolation='nearest', origin='lower')

Obviously, there are a few things to improve, like not repeating the second point of the line and the first point of the new line, but I wanted to keep this all clean and simple (and also, for fill to work the points just need to define a line and don't need to be a corner, so in some cases this more general approach might be preferable). Also, currently one needs to specify whether to fill above or below the line, and that can be calculated in various ways, but is probably easiest when generating the rhombus.

Answer 2

Although a little less robust than the answer already posted, here's a neat trick to form rhombus using upper and lower triangular matrices concept

import numpy as np
import matplotlib.pyplot as plt

blank = np.zeros((10, 12))

anchorx, anchory = 2, 3
# better result for odd dimensions, because mid index exists
# can handle h != w but the rhombus would still fit to a square of dimension min(h, w) x min(h, w)
h, w = 7, 7

assert anchorx+h <= blank.shape[0], "Boundaries exceed, maintain 'anchorx+h <= blank.shape[0]' "
assert anchory+w <= blank.shape[1], "Boundaries exceed, maintain 'anchory+w <= blank.shape[1]' "

tri_rtc = np.fromfunction(lambda i, j: i >= j, (h // 2 + 1, w // 2 + 1), dtype=int)
tri_ltc = np.flip(tri_rtc, axis=1)

rhombus = np.vstack((np.hstack((tri_ltc, tri_rtc[:, 1:])), np.flip(np.hstack((tri_ltc, tri_rtc[:, 1:])), axis=0)[1:, :]))
blank[anchorx:anchorx+h, anchory:anchory+w] = rhombus

print(blank)
plt.imshow(blank)
plt.show()

[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 1. 1. 1. 1. 0. 0. 0.]
 [0. 0. 0. 1. 1. 1. 1. 1. 1. 1. 0. 0.]
 [0. 0. 0. 0. 1. 1. 1. 1. 1. 0. 0. 0.]
 [0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]