0

I have to extract an area from a image (can't disclose that image). With the help of this Abid K Rahman's answer I've obtained the image as Result Image I've obtained the points of that may make a rectangle but couldn't find a rectangle which is the best approximate.

    [[625, 389], [10, 385], [116, 184], [5, 35], [626, 26]]

We can assume that all four points of the rectangle will be in four different corner of image. So I have divided the set into four different group based on their location.

    [[[[41, 63]], [[613, 66]]], [[[227, 428], [25, 426], [39, 392]], [[612, 394]]]]

But I'm not able to move further. I want to extract points which approximately makes a rectangle. Better if the answer is in python.

Community
  • 1
  • 1
Abuhujair Khan
  • 1
  • 5
  • Is that all you give us? You can learn [How to Ask a good question](http://stackoverflow.com/help/how-to-ask) and create a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example. That makes it easier for us to help you. – Stephen Rauch Feb 19 '17 at 02:53
  • @StephenRauch I've constraints. Though I have updated a little. – Abuhujair Khan Feb 19 '17 at 03:02
  • Any optimization problem requires constraints. You have not specified any. Would suggest trying to figure out a description of what your application will consider to be an appropriate rectangle. – Stephen Rauch Feb 19 '17 at 03:06
  • 1
    I would suggest generalized hough transform. – Mehdi Feb 19 '17 at 06:10
  • Another method I can suggest is perhaps using RANSAC and using four points at a time, each time you test the pair wise angles with respect to each of the other points and also check for the largest amount of points contained in the rectangle. I haven't written an answer because I don't know if this will work. – rayryeng Feb 19 '17 at 14:32
  • @rayryeng will look into its implementation. – Abuhujair Khan Feb 19 '17 at 18:06
  • If I have time, I'll look into it and make an answer. It's an interesting problem. – rayryeng Feb 19 '17 at 18:28
  • @rayryeng I applied a basic way, though it is not upto the mark. You can find my answer below. – Abuhujair Khan Feb 21 '17 at 15:06

3 Answers3

0

So I went on to write my the code using something rayryeng suggested and come up with this.

c = [[[] for x in range(2)] for y in range (2)]
for xy in centroids:
    x_i = xy[0]*2/col
    y_i = xy[1]*2/row
    c[y_i][x_i].append(np.array(xy))

combination = []
combination = np.array([ np.array([q1,q2,q3,q4]) for q1 in c[0][0] for q2 in c[0][1] for q3 in c[1][1] for q4 in c[1][0]])

if len(combination)>0 :
    key = 0
    property = [[ 0 for j in range(4)] for i in range(len(combination))]
    for i in range(len(combination)):
        q = combination[i]
        d1,d2 = q[2]-q[0],q[1]-q[3]
        d1_len,d2_len = np.sqrt(sum(d1**2)),np.sqrt(sum(d2**2))
        angle = math.degrees(math.acos(sum(d1*d2)/(d1_len*d2_len)))
        if d1_len > d2_len:
            r,extent = int(100*d1_len/d2_len),d2_len
        else:
            r,extent = int(100*d2_len/d1_len),d1_len
        property[i] = [r,angle,extent,i]
    property.sort(key = lambda x:x[0])
    key = property[0][3]
    combination = combination[key]

Here centroids is the points I have got, which I divided in to quadrants, since in my problem the points need to be from all four qaudrants. I've made the all possible combination of four points. I found the diagonals, the angle the make at the centre. Made a list of which contain the ratio of length of diagonal(smallest to largest), the angle and the length of shortest diagonal. I used the property that the diagonal of rectangle are of equal length. Which is quite useful for now. I don't know how to use the other properties hence its kept on hold. In final answer I get the best rectangle (when there are no points to make a sqaure, also, it doesn't care about the size of rectangle).

Community
  • 1
  • 1
Abuhujair Khan
  • 1
  • 5
0

Maybe Python Shapely library can help.

Example:

from shapely.geometry import MultiPoint
points = MultiPoint([(0.0, 0.0), (1.0, 1.0), ... ])

points.bounds
# A (minx, miny, maxx, maxy) tuple.
George Adrian Echim
  • 115
  • 1
  • 5
-1

best thing is imcrop(I,rect); where rect is define as

rect=[xmin ymin width height]

so at first pair for example [41,63],[613,66]

xmin=41

ymin=63

width=613-41

height=66-63

Abo Lregal
  • 75
  • 8
  • 1
    Again not the right answer. Read the question again carefully. The rectangle needs to be automatically defined given a set of points. – rayryeng Feb 19 '17 at 14:29