How to find the maximum distance between five points?

Question

I have done object detection in videos and found 5 to 6 coordinates in a frame. In each frame the distance between the co-ordinates varies because of the moving object. My text file has 13 columns ,first column is frame number and 6 coordinates as shown below. I have to find the frame No. which has maximum space between the coordinates to the minimum. The minimum arbitrary distance between each coordinates should not intersect each other as I want to segment the videos depending on the spacing between the coordinates.

Is there any pre-written algorithm for doing this type of segmentation or should I loop?

    301.467 0.713235 0.852451 0.752451 0.753922 0.380392 0.373039 0.282843          0.291667 0.262255 0.283824 0.236765 0.218627
    301.6 0.717647 0.864706 0.752941 0.761275 0.753431 0.743627 0.388235 0.383333 0.286765 0.294608 0.237745 0.207353
    301.667 0.722059 0.876471 0.756863 0.763726 0.395098 0.391667 0.284314 0.289216 0.238725 0.198529 nan nan
    301.867 0.72451 0.884314 0.762745 0.771078 0.40098 0.401961 0.290686 0.292647 0.240196 0.207843 0.241176 0.190686
    302 0.731373 0.897059 0.760784 0.771569 0.413725 0.422549 0.302941 0.292157 0.25098 0.179412 nan nan
    302.067 0.743627 0.917157 0.765686 0.777941 0.430392 0.444608 0.305392 0.293137 0.257843 0.17402 nan nan
    302.2 0.754902 0.928431 0.768627 0.782843 0.440686 0.458333 0.316667 0.294608 0.266176 0.17451 nan nan
    302.267 0.768137 0.937745 0.770098 0.789216 0.454902 0.476961 0.323039 0.296569 0.276471 0.186275 nan nan
    302.467 0.783824 0.939706 0.769608 0.794608 0.47598 0.498039 0.328431 0.29951 0.281863 0.194118 nan nan
    302.8 0.792647 0.940686 0.768627 0.8 0.486765 0.510294 0.337745 0.305392 0.285294 0.2 nan nan

The expected output is like

1st maximum space in video segment : 301.467 to 301.867

2nd maximum space in video segment : 302.2 to 302.8

Answer 1

The following script first converts your data into a list of rows. For each row the initial value is discarded and a list of permutations holding all of the pairs is then created. maths.hypot is then used to calculate the distance. max_distance is displayed for each set sorted by distance.

import math, itertools

data = """301.467 0.713235 0.852451 0.752451 0.753922 0.380392 0.373039 0.282843          0.291667 0.262255 0.283824 0.236765 0.218627
301.6 0.717647 0.864706 0.752941 0.761275 0.753431 0.743627 0.388235 0.383333 0.286765 0.294608 0.237745 0.207353
301.667 0.722059 0.876471 0.756863 0.763726 0.395098 0.391667 0.284314 0.289216 0.238725 0.198529 nan nan
301.867 0.72451 0.884314 0.762745 0.771078 0.40098 0.401961 0.290686 0.292647 0.240196 0.207843 0.241176 0.190686
302 0.731373 0.897059 0.760784 0.771569 0.413725 0.422549 0.302941 0.292157 0.25098 0.179412 nan nan
302.067 0.743627 0.917157 0.765686 0.777941 0.430392 0.444608 0.305392 0.293137 0.257843 0.17402 nan nan
302.2 0.754902 0.928431 0.768627 0.782843 0.440686 0.458333 0.316667 0.294608 0.266176 0.17451 nan nan
302.267 0.768137 0.937745 0.770098 0.789216 0.454902 0.476961 0.323039 0.296569 0.276471 0.186275 nan nan
302.467 0.783824 0.939706 0.769608 0.794608 0.47598 0.498039 0.328431 0.29951 0.281863 0.194118 nan nan
302.8 0.792647 0.940686 0.768627 0.8 0.486765 0.510294 0.337745 0.305392 0.285294 0.2 nan nan"""

def calc_distance(c1, c2):
    return math.hypot(c2[0] - c1[0], c2[1] - c1[1])

results = []

for row in data.split("\n"):
    cols = [float(col) for col in row.split(" ") if len(col)]
    max_distance = 0
    for c1,c2 in itertools.permutations(zip(cols[1:], cols[2:]), 2):
        max_distance = max(max_distance, calc_distance(c1,c2))

    results.append((max_distance, cols[0]))

results.sort()

for distance, frame in results:
    print "%-15s %f" % (frame, distance)

This produces the following results showing the frames sorted in max distance order:

301.467         0.814885
301.6           0.831112
301.667         0.847618
301.867         0.860743
302.0           0.869144
302.067         0.887828
302.8           0.897788
302.267         0.898022
302.2           0.898471
302.467         0.898814

This was done using Python 2.7.9. I have not manually verified the results.

Update based on your comment

I am still not completely sure I understand the question, but the following solution calculates the smallest and biggest coordinates from all frames and shows in which frame each outlying coordinate was found. This would give you suitable information with which to auto crop.

# Hold the frame number and the value for each side
# Where 100 is greater than the expected height and width of the frame
# Assuming top left is (0,0)

frame_top = (0.0, 100.0)    
frame_left = (0.0, 100.0)
frame_bottom = (0.0, 0.0)
frame_right = (0.0, 0.0)

for row in data.split("\n"):
    cols = [float(col) for col in row.split(" ") if len(col)]
    icols = iter(cols[1:])

    for x in icols:
        y = next(icols)

        if x and y: # Skip any nan values
            if x < frame_left[1]:
                frame_left = (cols[0], x)
            if x > frame_right[1]:
                frame_right = (cols[0], x)
            if y < frame_top[1]:
                frame_top = (cols[0], y)
            if y > frame_bottom[1]:
                frame_bottom = (cols[0], y)

print "Frame %f has top %f" % frame_top
print "Frame %f has left %f" % frame_left
print "Frame %f has bottom %f" % frame_bottom
print "Frame %f has right %f" % frame_right

This gives the following output:

Frame 302.067000 has top 0.174020
Frame 301.467000 has left 0.236765
Frame 302.800000 has bottom 0.940686
Frame 302.800000 has right 0.792647

In effect it is calculating the smallest bounding rectangle for all points. You could of course submit smaller ranges of frames.