Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to close a complex shape

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 6 Jan, 2011 20:53:05

Message: 1 of 16

Hi,

Let's imagine we have an open complex shape (For example the letter 'M') which is in Black/White form and that is thick (It is not only a line). Any idea about how can I draw a line to "close" it?

Have in mind that the shape is not always an M, but it is always a thick "worm" with a beginning and an end (though it is not trivial how to find the beginning and the end).

Thanks in advance.

Subject: How to close a complex shape

From: Sean de

Date: 6 Jan, 2011 21:03:05

Message: 2 of 16

"Fidel Alfaro" wrote in message <ig5a3h$sdk$1@fred.mathworks.com>...
> Hi,
>
> Let's imagine we have an open complex shape (For example the letter 'M') which is in Black/White form and that is thick (It is not only a line). Any idea about how can I draw a line to "close" it?
>
> Have in mind that the shape is not always an M, but it is always a thick "worm" with a beginning and an end (though it is not trivial how to find the beginning and the end).
>
> Thanks in advance.

So this "M" is a binary image? If it is use BWMORPH with the skeleton option followed by the endpoints option. Then use formula for a line to figure out the points you need to turn on between them.

Good Luck!
-Sean

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 6 Jan, 2011 21:08:05

Message: 3 of 16

Wow, that sounds easy. Let's try.

Thank you very much!

"Sean de " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <ig5am9$817$1@fred.mathworks.com>...
> "Fidel Alfaro" wrote in message <ig5a3h$sdk$1@fred.mathworks.com>...
> > Hi,
> >
> > Let's imagine we have an open complex shape (For example the letter 'M') which is in Black/White form and that is thick (It is not only a line). Any idea about how can I draw a line to "close" it?
> >
> > Have in mind that the shape is not always an M, but it is always a thick "worm" with a beginning and an end (though it is not trivial how to find the beginning and the end).
> >
> > Thanks in advance.
>
> So this "M" is a binary image? If it is use BWMORPH with the skeleton option followed by the endpoints option. Then use formula for a line to figure out the points you need to turn on between them.
>
> Good Luck!
> -Sean

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 6 Jan, 2011 22:04:06

Message: 4 of 16

Well... It didn't work. The "M" is really complex and after the skeleton, there are too many "end points" (No way to know the good one).

Any other idea?

Thanks again for your answer.

"Sean de " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <ig5am9$817$1@fred.mathworks.com>...
> "Fidel Alfaro" wrote in message <ig5a3h$sdk$1@fred.mathworks.com>...
> > Hi,
> >
> > Let's imagine we have an open complex shape (For example the letter 'M') which is in Black/White form and that is thick (It is not only a line). Any idea about how can I draw a line to "close" it?
> >
> > Have in mind that the shape is not always an M, but it is always a thick "worm" with a beginning and an end (though it is not trivial how to find the beginning and the end).
> >
> > Thanks in advance.
>
> So this "M" is a binary image? If it is use BWMORPH with the skeleton option followed by the endpoints option. Then use formula for a line to figure out the points you need to turn on between them.
>
> Good Luck!
> -Sean

Subject: How to close a complex shape

From: Walter Roberson

Date: 6 Jan, 2011 22:15:05

Message: 5 of 16

On 06/01/11 2:53 PM, Fidel Alfaro wrote:

> Let's imagine we have an open complex shape (For example the letter 'M')
> which is in Black/White form and that is thick (It is not only a line).
> Any idea about how can I draw a line to "close" it?

Can you draw an ASCII diagram (or post an image) of what the "closed" M
would look like? I'm having trouble deciding which of the several
meanings of "close" that you might mean.

Subject: How to close a complex shape

From: ImageAnalyst

Date: 6 Jan, 2011 22:20:34

Message: 6 of 16

On Jan 6, 5:04 pm, "Fidel Alfaro" <falfar...@alumno.uned.es> wrote:
> Well... It didn't work. The "M" is really complex and after the skeleton, there are too many "end points" (No way to know the good one).
>
> Any other idea?
>
> Thanks again for your answer.
>
-------------------------------------------------
There is a 'spur' option to bwmorph to remove spurious tails so that
you just keep the main skeleton.

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 6 Jan, 2011 22:35:05

Message: 7 of 16

Certainly:

0000 0000
00000 00000
000000 000000
0000000 0000000
000 00000 000
000 0 000
000 000
000 000

    "0pen M"


0000 0000
00000 00000
000000 000000
0000000 0000000
000 00000 000
000 0 000
000 000
000000000000000

   "Closed M"

I am afraid that this font is distorting the "M"s, but I think you get the point.

I am going to try with the "spur" option to see how it goes.

Thanks again for all your help.

Cheers.


Walter Roberson <roberson@hushmail.com> wrote in message <K9rVo.25880$v27.302@newsfe22.iad>...
> On 06/01/11 2:53 PM, Fidel Alfaro wrote:
>
> > Let's imagine we have an open complex shape (For example the letter 'M')
> > which is in Black/White form and that is thick (It is not only a line).
> > Any idea about how can I draw a line to "close" it?
>
> Can you draw an ASCII diagram (or post an image) of what the "closed" M
> would look like? I'm having trouble deciding which of the several
> meanings of "close" that you might mean.

Subject: How to close a complex shape

From: Steven_Lord

Date: 6 Jan, 2011 22:59:34

Message: 8 of 16



"Fidel Alfaro" <falfaro13@alumno.uned.es> wrote in message
news:ig5g2p$2kb$1@fred.mathworks.com...
> Certainly:
>
> 0000 0000
> 00000 00000
> 000000 000000
> 0000000 0000000
> 000 00000 000
> 000 0 000
> 000 000
> 000 000
>
> "0pen M"
>
>
> 0000 0000
> 00000 00000
> 000000 000000
> 0000000 0000000
> 000 00000 000
> 000 0 000
> 000 000
> 000000000000000
>
> "Closed M"
>
> I am afraid that this font is distorting the "M"s, but I think you get the
> point.

Why don't you also close the top of the M?

If you also need to close the top of the M, use CONVHULL with the
coordinates of the pixels that make up the M as the input points.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlab.wikia.com/wiki/FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 7 Jan, 2011 19:40:08

Message: 9 of 16

Hello all,

The thing is that I just want to close the shape. Ok, I'll ask the question in a different way:

If I have a shape like this http://img828.imageshack.us/img828/7982/im2g.jpg

How can I find the beginning and the ending of the "line"?
(I am asking for a general answer not and ad hoc answer)

Thanks again.

Fidel

"Steven_Lord" <slord@mathworks.com> wrote in message <ig5hgm$5g7$1@fred.mathworks.com>...
>
>
> "Fidel Alfaro" <falfaro13@alumno.uned.es> wrote in message
> news:ig5g2p$2kb$1@fred.mathworks.com...
> > Certainly:
> >
> > 0000 0000
> > 00000 00000
> > 000000 000000
> > 0000000 0000000
> > 000 00000 000
> > 000 0 000
> > 000 000
> > 000 000
> >
> > "0pen M"
> >
> >
> > 0000 0000
> > 00000 00000
> > 000000 000000
> > 0000000 0000000
> > 000 00000 000
> > 000 0 000
> > 000 000
> > 000000000000000
> >
> > "Closed M"
> >
> > I am afraid that this font is distorting the "M"s, but I think you get the
> > point.
>
> Why don't you also close the top of the M?
>
> If you also need to close the top of the M, use CONVHULL with the
> coordinates of the pixels that make up the M as the input points.
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlab.wikia.com/wiki/FAQ
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Subject: How to close a complex shape

From: Walter Roberson

Date: 7 Jan, 2011 19:47:05

Message: 10 of 16

On 11-01-07 01:40 PM, Fidel Alfaro wrote:

> The thing is that I just want to close the shape. Ok, I'll ask the question in
> a different way:
>
> If I have a shape like this http://img828.imageshack.us/img828/7982/im2g.jpg
>
> How can I find the beginning and the ending of the "line"?

There is more than one "line". Do you want the _longest_ connected line?

 > (I am asking for a general answer not and ad hoc answer)

In that case, what should be done if the straight line between the ends
intersects the figure? And what if there are ties in the line lengths? And
when you are calculating line length, should a diagonal connection count as
sqrt(2) or as 1?

If there are multiple routes available for connecting two points, then is it
the length of the shortest route that should be considered, or the length of
the longest route that does not contain any cycles? Or should it be always be
the "exterior" route?

"I just want to close the shape" doesn't tell us what *you* mean by "close the
shape" :(

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 7 Jan, 2011 20:04:04

Message: 11 of 16

Ok... Now I realize how ambiguous I have been. Sorry for that.

> Do you want the _longest_ connected line?

Yes. Is there an automatic way to get it?

> In that case, what should be done if the straight line between the ends
> intersects the figure?

That should never happen. All shapes are like a "complex" C.

> And what if there are ties in the line lengths?

So... There is no automatic way to get the "longest_connected_line"? I infer from that question that I have to program it having that situation in mind, isn't it?

>And when you are calculating line length, should a diagonal connection count as
> sqrt(2) or as 1?

Mahattan distance is my favourite choice :)

> If there are multiple routes available for connecting two points, then is it
> the length of the shortest route that should be considered, or the length of
> the longest route that does not contain any cycles? Or should it be always be
> the "exterior" route?

Uhm... I am not very sure if I understood your question. I guess I just thought about the shortest route (straight line from the beginning to the end). I do not think other options are easy to calculate.

> "I just want to close the shape" doesn't tell us what *you* mean by "close the
> shape" :(

Yes, I can see that now. Thanks for making me see it.

Subject: How to close a complex shape

From: Walter Roberson

Date: 7 Jan, 2011 20:38:29

Message: 12 of 16

On 11-01-07 02:04 PM, Fidel Alfaro wrote:

>> Do you want the _longest_ connected line?

> Yes. Is there an automatic way to get it?

Sorry, that is outside of my experience.

>> And when you are calculating line length, should a diagonal connection count
>> as sqrt(2) or as 1?

> Mahattan distance is my favourite choice :)

\OO
O\O
OO\

Euclidean end to end: 3 * sqrt(2)
Euclidean centers to centers: 2 * sqrt(2)
Manhattan end to end: 6
Manhattan centers to centers: 4
Pixel count: 3

Which is the "real" length?


Does your reference to Manhattan distance imply that you want 2-connected or
4-connected rather than 8-connected for the purpose of determining whether a
line has ended?

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 7 Jan, 2011 21:00:21

Message: 13 of 16

8 connected.

I cannot see how the manhattan distance can be 6, sorry.

In this example,

A 0 0
0 0 0
B 0 B

the two B's are at the same distance to the A using the "manhattan distance" definition used in Nilsson's "Artificial Intelligence: A new synthesis".

The code for this looks hard and inefficient (Probably an NP-Hard problem).

Maybe I will open a new thread to ask for this.

Thanks anyway.

Walter Roberson <roberson@hushmail.com> wrote in message <ig7tm5$aur$1@nrc-news.nrc.ca>...
> On 11-01-07 02:04 PM, Fidel Alfaro wrote:
>
> >> Do you want the _longest_ connected line?
>
> > Yes. Is there an automatic way to get it?
>
> Sorry, that is outside of my experience.
>
> >> And when you are calculating line length, should a diagonal connection count
> >> as sqrt(2) or as 1?
>
> > Mahattan distance is my favourite choice :)
>
> \OO
> O\O
> OO\
>
> Euclidean end to end: 3 * sqrt(2)
> Euclidean centers to centers: 2 * sqrt(2)
> Manhattan end to end: 6
> Manhattan centers to centers: 4
> Pixel count: 3
>
> Which is the "real" length?
>
>
> Does your reference to Manhattan distance imply that you want 2-connected or
> 4-connected rather than 8-connected for the purpose of determining whether a
> line has ended?

Subject: How to close a complex shape

From: Walter Roberson

Date: 7 Jan, 2011 21:09:42

Message: 14 of 16

On 11-01-07 03:00 PM, Fidel Alfaro wrote:
> 8 connected.
>
> I cannot see how the manhattan distance can be 6, sorry.
>
> In this example,
> A 0 0
> 0 0 0
> B 0 B
>
> the two B's are at the same distance to the A using the "manhattan distance"
> definition used in Nilsson's "Artificial Intelligence: A new synthesis".

Look at the example in
http://en.wikipedia.org/wiki/Taxicab_geometry

In that example, there are 6 pixels and the Manhattan distance is 12. If you
start from the upper-left corner of the A and go to the bottom-right corner of
the right-most B, you have to travel along 6 "faces" of a pixel, 6 blocks, 2
blocks travelled to accomplish one complete diagonal.

I am not familiar with Nilsson's work, but I do not recall ever encountered a
definition of Manhattan distance which did not involve travelling two "blocks"
to accomplish a diagonal.

Subject: How to close a complex shape

From: Walter Roberson

Date: 7 Jan, 2011 21:42:17

Message: 15 of 16

On 11-01-07 03:00 PM, Fidel Alfaro wrote:

> The code for this looks hard and inefficient (Probably an NP-Hard problem).

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Or possibly more relevant would be

http://en.wikipedia.org/wiki/Minimum_spanning_tree

That is, produce a minimum spanning tree, and then repeatedly snip off the
branch that has the lowest total weight until you reach a situation in which
there are no more decision points. (You need to do that snipping globally,
because of the possibility that you have a heavy branch that in actuality
consists of a lot of tiny branches that are nearly all going to pruned off.)

Subject: How to close a complex shape

From: Fidel Alfaro

Date: 8 Jan, 2011 00:12:04

Message: 16 of 16

Yes, I thought something like that, but first I will ask here. Let's not reinvent the wheel.

Thanks for all the help (mostly clarifying my mind).

Walter Roberson <roberson@hushmail.com> wrote in message <ig81dp$d1f$1@nrc-news.nrc.ca>...
> On 11-01-07 03:00 PM, Fidel Alfaro wrote:
>
> > The code for this looks hard and inefficient (Probably an NP-Hard problem).
>
> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
>
> Or possibly more relevant would be
>
> http://en.wikipedia.org/wiki/Minimum_spanning_tree
>
> That is, produce a minimum spanning tree, and then repeatedly snip off the
> branch that has the lowest total weight until you reach a situation in which
> there are no more decision points. (You need to do that snipping globally,
> because of the possibility that you have a heavy branch that in actuality
> consists of a lot of tiny branches that are nearly all going to pruned off.)

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us