Line fit between two curves.

Hey Guys,

I am trying to solve a problem regarding clearances and line fitting, around and through 2 curves.

The information I have is a coordinates of 2 parallel lines, resembling a pipe. Both these lines are not completely straight and bend at certain points.

The two line can be represented as so;

x1=[0 2 4.5 7 9];
y1=[0.7 2 4 5.5 7.5];
y2=y1+1;
plot(x1,y1,'-r')
hold on
plot(x1,y2,'-r')
grid on

I want the program to check whether a straight line of length 10 units will fit within these two line with out touching the edges. And if so how will this line sit within the two parallel lines.

The final image should look similar to this;

(add to end of previous code)

 xb=[0.5 8.5];
 yb=[1.5 7.5];
 plot(xb,yb,'-b')

Please advice as to which commands, if any would be useful. Or what mathematical approach I should take to try and solve this.

Thanks,

[Andrew Reibold]

What happens if there are multiple solutions? What solution is "best" (i.e., Hugging/close to the bottom line, farthest from each line as possible,[closertomiddle] etc)

[Mazhar]

Hi Andrew, Thanks for your response.

The best solution would have the blue line as centered as possible between the two red lines.

The example lines I gave above are not too badly bent, but in some cases the pipe could be bent almost 90 degrees.

[Matt J]

a straight line of length 10 units will fit within these two line with out touching the edges

So it's only the length-10 line segment which must fall between the 2 red lines, correct? If I extrapolate the line segment to infinity at each end, the extrapolated part is allowed to cross the two given red lines?

[Mazhar]

Yeah, the extrapolated part can touch the red lines, it is just the 10 unit length which must not touch.

[Matt J]

Do you have the Optimization Toolbox? And will the pipe boundaries always be definable using a function y=f(x)? If the pipe were circular, for example, there would not be an f(x) defining its boundaries.

[Mazhar]

The pipe boundaries are only given by (x,y) coordinates. It will be possible to fit polygons to the coordinates I guess, but there is no given function for the pipe.

Answer 1

[Image Analyst]

There may be simpler ways, but it looks like SVM (Support Vector Machine) would work. http://en.wikipedia.org/wiki/Support_vector_machine

[Mazhar]

Thanks for the link. I read through it, and it does seem like the thing to try out.

But I'm not sure how to implement it into MatLab correctly.

I've been trying best fit line, but in some cases, the best fit line does not sit with in the pipe. However there is line that you can fit with in the dots.

Please assist.

[Image Analyst]

SVM is in the stats toolbox, which I don't have so I can't help you with that since I don't have experience with it.

[Matt J]

Now that Mazhar has said the pipe can bend almost 90 degrees, I'm less optimistic about SVM.

[Mazhar]

If the pipe is bent severely, Then the program will terminate and tell me that the line will not fit.

[Image Analyst]

That's correct - there will be no solution in that case. What do you want to do when no line will fit (no matter how you try to solve it)?

[Mazhar]

If no line fits through the pipe, then the user will be noted that the line can not pass through this pipe.

My final product will allow the user to input data into the program and check accessibility through the pipe for any length of line (line represents any tool, equipment you want to pass through). If the line doesn't pass the program and identify the section of pipe where it will get stuck for the user.

Please read, this earlier question I posted, which explain the larger problem more thoroughly.

http://www.mathworks.co.uk/matlabcentral/answers/84711-clearence-check-passing-an-object-stick-line-through-pipe

[Image Analyst]

The "no-fit" case is easy. Just fit a line (via whatever method you want). Then get the coordinates of the line for every x. Then take the top and bottom sides of the points that define the channel and connect them to form a polygon. Then use inpolygon() to determine if a point on the fitted line is outside the polygon.

[Matt J]

The "no-fit" case is easy. Just fit a line (via whatever method you want). Then get the coordinates of the line for every x.

Don't think so. That might be an applicable test if the stick going through the pipe were the same length as the pipe. However, if the stick is short enough and the pipe bends gradually enough, the stick will go through no matter how nonlinear the pipe is end-to-end.

[Image Analyst]

I thought it was the same length. If it's not, you'd have to check for every x value just going up to the length of the stick. Like for x elements 1-10, 2-11, 3-12, and so on until you get within 10 of the end. Should be pretty fast though since we're only dealing with small arrays, not megabytes of data.

[Mazhar]

Yeah, the approach for calculating this will, carry out the test for a section of pipe the same length as the line/stick, if that test passes, it moves on to the next section (the sections will be tested with an overlap, as you said above: 1-10, 2-11, 3-12).

The "fit" is in most cases simple; usually the line of best-fit, between the coordinates of both sides of the pipe, will fit through nicely.

In the "no-fit" (best-fit line does not fit) case, however, there are infinitely number of ways to move the line (rotate at start, at end, in the middle, pan left to right etc.) And I'm just struggling to determine what testing the line should carry out!

I was thinking start with the best-fit line, if it fits, thats great and we can check the next section. If not, then the program will try to change the equation of the best-fit line (gradient and y-intercept) in an orderly manner, and should eventually find a solution.

The program will stop testing when the gradient (or y-intercept) lie outside the pipe mean gradient and y-intercepts.

Answer 2

[Matt J]

I recommend that you make a binary image of the pipe (e.g., using ROIFILL) and then use HOUGHLINES with the 'MinLength' option to find a segment of (at least) length 10.

[Mazhar]

Hmm.. I've never done any image processing in MatLab before, so this might be quite difficult :/.

Also, the bigger result I am looking for, would be this test, to which I am seeking a solution here, being carried out on a full length of pipe. Letting me know whether the blue line can pass through the whole pipe.

Is the binary image method still going to be efficient then?

[Matt J]

Your "bigger result" is a different problem, but I think it's going to require an image processing solution as well.

[Mazhar]

All right, yeah, i'll give this a try! Hopefully can get a good result.

Also, please take a look at this earlier question I posted:

http://www.mathworks.co.uk/matlabcentral/answers/84711-clearence-check-passing-an-object-stick-line-through-pipe

It explains the larger problem in a little more detail.

[Mazhar]

Hmm.. I don't have the image processing toolbox either.

I would've thought they're would be a mathematical approach to this??

[Matt J]

I would've thought they're would be a mathematical approach to this??

Don't think so. Not a simple one, anyway.

I definitely think Hough transform analysis would be the simplest path to doing this. With some exploration of the FEX, you might find a Hough transform tool that doesn't require the Image Processing Toolbox. This looks like a possibility

http://www.mathworks.co.uk/matlabcentral/fileexchange/26869-hough-transform

Basically, if a stick of length L fits through the pipe, its Hough Transform image should contain a continuous locus of pixels all of intensity greater than or equal to L.

I would get the Image Processing Toolbox if you can...

[Mazhar]

Will image processing work in 3D? for example, Carry out this test on the pipe as a whole, rather than looking at cut planes of it from all angels?

[Matt J]

I don't think the Hough Transform tools in the Image Processing Toolbox do 3D. There may be alternative ways to do this using Optimization Toolbox functions. That's why I asked you above if you have that toolbox.

[Mazhar]

I have been looking around and getting help from a lecturer, think I have something.

We need to use the fminsearch function. you set an initial guess for the line and the fminsearch will try to bring the line towards the center of the pipe. If you do this over a length of pipe, then line will be positioned to be as close to the center of all cross-sections of the pipe.

I still need to look more into this, but if this sets of a bell to you, please share :)

[Matt J]

fminsearch does not do minimization under constraints, which I think you might need in order to constrain the path of the stick to move within the boundaries of the pipe. Algorithms in the Optimization Toolbox will handle constraints and, moreover, are more robustly convergent than fminsearch. That's why I've asked you (3 times now ;)) whether you have the toolbox.

[Mazhar]

Sorry I meant to say earlier, no I don't have the optimization toolbox :(.

Am I able to add in my own constraints? eg. the position can be checked for it being with in the pipe, if not then it is re-adjusted.

[Matt J]

You can set the value of your objective function to Inf for position parameters that put the stick outside the pipe.