Determine corner coords from a set of coords on a page Python / OpenCV

Question

Given a set of points, how can I determine which are the top left, top right, bottom right and bottom left (TL, TR, BR, BL)

These are coords of black squares as located on the below images. (4 down each side of the page)

Here are the coords (x,y) (origin 0,0 is top left):

[(147.68485399616046, 3304.5385975548143),
(168.3419544680192, 2336.686128749161),
(188.1491476566771, 1331.864619054719),
(211.6472437750393, 155.6040367158578),
(2216.6064720878203, 3330.396441392227),
(2233.7510405426237, 2363.6828015004367),
(2250.9856437171966, 1360.935679736544),
(2273.392518618822, 187.8742947415933)]

By sorting these along the x axis, I can take the top 4 and the 4 bottom 4 which gives me both columns one for each side of the page.

I then summed the coords pairs i.e. 147+3304 = 3451 and so on.. By sorting the coords on this summed value I can take the lowest value to be the coords for TL, and the highest for BR (as that will have the largest x+y combination)

https://i.stack.imgur.com/GxXJd.jpg

This works OK, apart from when I encountered this set of coords:

     [(203.68919057903938, 154.66471253728272),
     (2264.8873935264055, 180.78268029528675),
     (987.6169366297244, 1156.4133276499006),
     (184.2811080835604, 1331.004238570996),
     (167.45816773667582, 2336.89386528075),
     (2236.836364657011, 2356.0815089255643),
     (150.94371083838226, 3304.3057324840765),
     (2223.8576991353148, 3323.427188913703)]

Which when processed as above gives me an erranous TR location of 987, 1156 rather than 2264, 180

    https://i.stack.imgur.com/aVp4f.jpg

So how do I programaticaly determine my 4 corner coords?

Note I have redacted these images but they still give the same outputs.

https://i.stack.imgur.com/cyMG5.jpg
https://i.stack.imgur.com/aVp4f.jpg
https://i.stack.imgur.com/h8ylN.jpg
https://i.stack.imgur.com/rF7Sw.jpg
https://i.stack.imgur.com/GxXJd.jpg
https://i.stack.imgur.com/837nR.jpg

Answer 1

Here is an inefficient, but I think straightforward approach.

The basic characteristic of TL, TR, BL, BR is that they are the closest to each corner. If you take any set of xy points, then all you need to do is find the shortest distance to each corner.

The code below does exactly that with brute force (comparing all points to all corners). It can be copy-pasted to the interpreter. Since I don't know the extrema of your given images, I've had to get them based on the available points. You can skip that by providing the corners of the image itself.

---

ok = [(147.68485399616046, 3304.5385975548143),
      (168.3419544680192, 2336.686128749161),
      (188.1491476566771, 1331.864619054719),
      (211.6472437750393, 155.6040367158578),
      (2216.6064720878203, 3330.396441392227),
      (2233.7510405426237, 2363.6828015004367),
      (2250.9856437171966, 1360.935679736544),
      (2273.392518618822, 187.8742947415933)]
bad = [(203.68919057903938, 154.66471253728272),
       (2264.8873935264055, 180.78268029528675),
       (987.6169366297244, 1156.4133276499006),
       (184.2811080835604, 1331.004238570996),
       (167.45816773667582, 2336.89386528075),
       (2236.836364657011, 2356.0815089255643),
       (150.94371083838226, 3304.3057324840765),
       (2223.8576991353148, 3323.427188913703)]


def distance(xy1, xy2):
    (x1, y1), (x2, y2) = xy1, xy2
    return ((float(y2-y1))**2 + (float(x2-x1))**2)**0.5


def fake_image_corners(xy_sequence):
    """Get an approximation of image corners based on available data."""
    all_x, all_y = zip(*xy_sequence)
    min_x, max_x, min_y, max_y = min(all_x), max(all_x), min(all_y), max(all_y)
    d = dict()
    d['tl'] = min_x, min_y
    d['tr'] = max_x, min_y
    d['bl'] = min_x, max_y
    d['br'] = max_x, max_y
    return d


def corners(xy_sequence, image_corners):
    """Return a dict with the best point for each corner."""
    d = dict()
    d['tl'] = min(xy_sequence, key=lambda xy: distance(xy, image_corners['tl']))
    d['tr'] = min(xy_sequence, key=lambda xy: distance(xy, image_corners['tr']))
    d['bl'] = min(xy_sequence, key=lambda xy: distance(xy, image_corners['bl']))
    d['br'] = min(xy_sequence, key=lambda xy: distance(xy, image_corners['br']))
    return d


def main():
    for xy_sequence in (ok, bad):
        image_corners = fake_image_corners(xy_sequence)
        d = corners(xy_sequence, image_corners)
        print '********'
        for k, v in d.items():
            print k, v

main()

---

Output:

********
bl (147.68485399616046, 3304.5385975548143)
tl (211.6472437750393, 155.6040367158578)
tr (2273.392518618822, 187.8742947415933)
br (2216.6064720878203, 3330.396441392227)
********
bl (150.94371083838226, 3304.3057324840765)
tl (203.68919057903938, 154.66471253728272)
tr (2264.8873935264055, 180.78268029528675)
br (2223.8576991353148, 3323.427188913703)