5 Replies - 1822 Views - Last Post: 02 September 2009 - 09:51 AM

#1 bertgertbert   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-August 09

algorithm finding lines

Posted 25 August 2009 - 01:02 AM

Hello,

I am looking for algorithmes that find lines in a cloud of points with known (x,y) coordinates,
Points are only accepted on the line when they have a minimal deviation compared to the line and when these points are at regular distances. Each point is the position of an object and the line determines the trajectorie of this object.
I already developed a first algorithm. It works but in some cases it fails (when there are a lot of points)


thanks in advance for any suggestions,

kind regards

Attached image(s)

  • Attached Image


Is This A Good Question/Topic? 0
  • +

Replies To: algorithm finding lines

#2 Aeternalis   User is offline

  • D.I.C Regular

Reputation: 28
  • View blog
  • Posts: 291
  • Joined: 13-July 09

Re: algorithm finding lines

Posted 25 August 2009 - 10:18 AM

This seems simple at first glance.. so are you saying that the lines must be formed by points that are equidistant apart..within a variance, along a stright line?

How are you detecting the ones that it successfully finds?

I would assume you are using the slope of the line from the point A to point B to continue on through point B the same distance as from A to B in order to find C? if there is no C there is no line?

How many points are needed in your algorithm to make a line? It looked like a minimum of three?

can these paths or trajectories as you call them vary in speed? (causing the distances between the points to be less or greater ... or are they always equidistant?

Can we see the code that works sometimes? What about the algorithm fails with a high number of points? does decreasing the variation allowed help with that?

Aet
Was This Post Helpful? 0
  • +
  • -

#3 bertgertbert   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-August 09

Re: algorithm finding lines

Posted 27 August 2009 - 07:02 AM

( for some reason I can not upload a picture at this moment, tried to upload jpg-file)

Thank you AET for your interest. I am glad to give you more information:
suppose you have 50 points (p1 to p50):
first all slopes and all distances (Euclidian distance matrix) are calculated with S(p1,p2) and D (pi,pk) being the slope and the distance between the points pi and pk
The algorithm starts with S(p1,p2) and searches for other points pi so that S (p1, pi) +-= S (p1,p2) (variation can be set)
This results in a trajectory e.g. [p1 p2 ... pi... pe] placed in a matrix
In a second phase the distance between the points is checked:
p1 p2 d12
... with d12= D(p1,p2))
p1 pi d1i
....
p1 pe d1e

- we search the smallest distance = dsmallest
we sort the matrix based on the distance, smallest first,
and calculate dij/ dsmallest= vij
then we calculate round(vij)=>if vij-round(vij) is smaller than an accepted deviation the distance is a multiple of the smallest distance.
If round(vij) is equal to the row index of vij so we can accept it as part of the line.
BUT:
- we know that the points are never exact on a straight line => the coordinates origin from image recognition and creates deviations.
-The points travel by different speeds, generally the speed changes very little between two positions ( they are slowing down but time between two positions is very short. So it can be accepted that they are equidistant within one line.
- so sometimes several trajectories are mixed ( so figure) and then the distance algorithm doesn’t work anymore
- in the example picture I show three positions of each object but the ‘best case scenario’ the algorithm does not ‘know’ how much positions of an object are on one line. We need at least three to identify a line. But once we are able to identify the lines we know the angle and speed of the objects and we can also track the once that have only two positions.
-other possible algorithm could use regression line through combinations of points and choose the line with the best fit

I can give you the code but it is in Matlab,
anyway programming the algorithm is at this moment less important than perfectioning the algorithm. Since at this moment we are working off line. Afterwards speed of the algorithm becomes important

Bert

This post has been edited by bertgertbert: 27 August 2009 - 07:06 AM

Was This Post Helpful? 0
  • +
  • -

#4 Aeternalis   User is offline

  • D.I.C Regular

Reputation: 28
  • View blog
  • Posts: 291
  • Joined: 13-July 09

Re: algorithm finding lines

Posted 27 August 2009 - 08:31 AM

You are already doing what I would suggest it appears. I thought calculating the slope to interpolate where the next point should be then checking for it.. your methods of doing that are a bit different.. but it looks like the same basic algorithm. It's simple.. but effective without a time constraint.


The problem with this method is its a brute force method. For large data sets you will want to find a better way.

One thought I had on reducing the time required for the algorithm is to have a limiting value. for instance if D1i is too large... outside the normal speed range for two points of the same line you can eliminate it, reducing the set of values that needs to be calculated to a subset of candidates. Should be faster than calculating for every point. ( a modified brute force if you will ).

The points on the candidate list are the only ones that need to be calculated, then from the candidates, do interpolation on each of them to see if a line exists for that pair.


I would still like to hear what conditions cause the algorithm to fail.

interesting stuff..

Aet
Was This Post Helpful? 1
  • +
  • -

#5 bertgertbert   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-August 09

Re: algorithm finding lines

Posted 02 September 2009 - 08:00 AM

Hi AET,

it took some time, sorry,
I uploaded a file that shows some problems with the algorithm
thanks for your comments;
kind regards

Attached image(s)

  • Attached Image

This post has been edited by bertgertbert: 02 September 2009 - 08:18 AM

Was This Post Helpful? 0
  • +
  • -

#6 Aeternalis   User is offline

  • D.I.C Regular

Reputation: 28
  • View blog
  • Posts: 291
  • Joined: 13-July 09

Re: algorithm finding lines

Posted 02 September 2009 - 09:51 AM

bertgertbert, let me try to label a few things here before I go further.

I'm working from the picture you uploaded. There are three lines depicted with several points on each line.

Starting on the left where two lines originate from the same point, I want to make sure I understand how the algorithm is failing.

Lets label the left most line (the upper line of the pair) as line A and the lower line as line B.
Starting from the common origin we can label the line unique points as A1 , A2 , and A3. B has a point that is directly below each of these, call them B1, B2 and B3. Well call the point that is common to both lines the origin.

It sounds to me like you are saying that line A and Line B have a slope that is so similar, the algorithm accepts points A1, A2, A3, B1, B2, B3 as all on the same line? This has confused me.

Consider the brute force method we described. What I think should be happening is that you are starting with point Origin, and with that as your base, you are selecting a candidate point from the field and calculating the slope created by these two points. For reference lets say the slope is 2.34/3.45 (just arbitrary numbers there). You would then be calculating the distance between origin and the selected point (we'll say A1) so after that you have the slope and distance from origin to A1.

At this point we would take the distance to A1 doubled and the slope and calculate where A2 should be. A2 is indeed along the same slope, and at double the distance, so it should be found. This creates Line A. Further searching along line A using the same slope but triple the distance should reveal A3. It is along the slope and the correct distance away for the third point. The algorithm should continue to search in this manner building up all points that are on the slope AND the correct distance. Another point could have existed on A, but when we search along the slope for a point at about 4 times the distance of origin to A1, we do not find another point. The search should stop here, there is no A4 so searching for point A5 would be futile and could only yield incorrect results.

Line A is stored, Back to the origin. The algorithm should be moving to the next point on the list, as it is going to do this process with every other point in the field. When it uses B1 as its candidate, it will find the line B.

If you are having problems with the algorithm finding B2 instead of A2, your variation is too large and is allowing close proximity points to be selected instead of the true line point. Try reducing the amount of variation you allow.

Now looking at the far right line in your picture, call it line C, the three points at the end of the line should not be found, because there is no point C3 along the slope and the correct distance. The algorithm should have stopped searching and moved on to another line.

Questions.. can each point in the field be considered an origin that you could search from, for instance B3?

Is this close to your algorithm? It seemed after re-reading your description that it may be significantly different, especially after seeing the problems you are having, which could not arise from this algorithm.


Hope it helps!
Aet
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1