Distinguish between chains

[EDIT: 20110718 16:11 - include images - WDR]

I need to be able to distinguish between to beaded chains that are lying next to each other. I can already find the location of each bead but I do not know how I can automatically determine which chain each bead belongs to. It is important that both chains are physically the same so I can't do to different colours.

Here are some sample images (raw b/w picture, filtered to show the beads, center of each bead marked): http://imageshack.us/g/405/testymh.jpg/

Any ideas?

[Sean de Wolski]

A few questions:

-How automated does this need to be? I.e: could you manually select the ends of the chains?

-Assuming we're traversing the chain starting at one end: there is most likely a limit on the angle two beads can lie in relation to each other given the thread between them. Could you measure this? (E.g. we know two beads are part of a thread - the third bead cannot lie at a declination greater than some threshold.

-Can you verify this assumption: The centroids between each bead will be within some distance range of each other (because there is a rigid thread between them). Any time two beads are closer than this - they will not be in the same thread?

[Sean de Wolski]

Ps. Good thread all around, +1

[Justin Bondy]

- I guess I could manually select the ends of the chains in each picture, but it would be very tedious as I am looking to use a couple hundred pictures per run (a few runs a day)

- Ya I have thought about using the maximum angle between two beads to eliminate beads outside this angle. You can see the effect of that max angle in the loop of the inside chain near the top. But I don't know if it will work as it looks like there would be beads near each other that are within the allowed angle but are not of the same chain

- The beads do have a maximum distance between them owing to the thread holding them together, but there is also the minimum distance which is just the beads touching

[Sean de Wolski]

Yes. So beads touching (centroids too close) ARE NOT part of the same chain and their connection can be automatically severed.

I think manually identifying the ends would be a good idea for the purpose of getting the rest of it working. We could make a simple GUI to make it easy.

[Walter Roberson]

Remember, Sean, it is thread holding them together, and the thread is not necessarily tight everywhere. Two beads that are part of the same chain could be touching.

[Sean de Wolski]

@Walter: Not with the metal ball (bead) thread chains I've had:

http://www.conveyorss.com/wp-content/uploads/2011/07/Steel-Ball-Chain-picture.jpg

The thread would have to be buckled in order for the distance to be broken.

[Walter Roberson]

It seems to me that the metal threads would have to be buckled in order to get curves like are shown in the more extensive picture Justin gave the URL for.

[Sean de Wolski]

I disagree. None of those angles are very large. A small displacement assumption and some rotation of the thread in relation to the bead, would account for the range of declinations available/visible while keeping the thread elastically strained/rotated.

[Justin Bondy]

The beads of the same chain can infact touch. The beads are hollow and the thread just goes into them. Sorry I did not make this clear.

Answer 1

[Walter Roberson]

Insufficient information about your premises. Do chains ever cross? Do they ever fork?

If they never cross and never fork, then in the simpler case, imdilate() to get a continuous line, threshold, bwboundary with no holes. That will get you the outer chain contour.

I indicate this as the "simpler case" in that this approach does not, without modification, consider the possibility of the chain ending. Having the chain end "in the middle of the picture" is something that is possibly tractable. If, though, a chain might end exactly where it touches another chain, then determining which chain is which might be difficult.

Can there ever be three chains in the image? Three chains that all happen to end at the same area? Is the threading definitely not captured in the images?

[Nathan Greco]

Regarding threading: Those appear to be magnetic chains of balls (see BuckyBalls), so there would be no intermittent threading.

[Walter Roberson]

Hmmm, perhaps -- but if they are magnetic chains then any point at which they touch would have to be deemed a point at which the chains joined, unless the only magnetically susceptible area was at the poles of the spheres ?

[Nathan Greco]

You should get your hand on a set of these (they are quite entertaining). a single magnetic ball can have multiple (more than 2) balls attached to it. This means that it is not limited to the poles, which makes the OP's problem more difficult than it seems. Notice that in his image, the smaller (inside) chain actually connects to the larger (outside) chain on the left-end, which makes the rest of the tail seem to belong to both chains.

[Walter Roberson]

That's what I was afraid of when you said "magnetic": if the "beads" are magnetic then there are a large number of "chains", with every "bead" along the area the chains touch potentially belonging to multiple chains (since, after-all, the magnetic attraction of the _all_ the touching beads helps reinforce the cohesiveness.)

Easier if there is a physical thread that just doesn't happen to show up at the resolution or imaging modality...

[Sean de Wolski]

@Walter: Your using the boundaries idea is good but the concave part where the outer boundary is the inner chain at the bottom-right hand corner would fail it.

@Justin: How much control do you have over the image acquisition system? I would recommend trying to get zoomed in on the chains. Even if they're close and touching; I think it would be much easier if we could see the linkage and have it actually distinguishable.

Answer 2

[Justin Bondy]

Sorry about the lack of info. The chains should never cross and (for now) they will not fork (though eventually I intend to use looped chains).

They are not magnetic chains, but the threading does not easily show up in the images. I am working to try and get them to show up more. You can see a picture where they show up here http://img219.imageshack.us/img219/8585/test2oi.jpg

I will play around with imdilate() and see if it helps.

Thanks

[Walter Roberson]

Having the thread should help disambiguate the connections.

Is there a maximum number of chains in an image?

[Nathan Greco]

Well, my mistake. :)

[Sean de Wolski]

@Nathan: still interesting for the rest of us!

[Justin Bondy]

There will almost always be only be 2 chains so lets only worry about that. As for the location of the end of the chains, their ends will always be within the picture (though their ends will almost certainly be very near the other chain).

I should also make it clear that the pictures I have posted are a lot more dilute then what the real case will most likely be. It will probably look like this:

http://imageshack.us/photo/my-images/163/largetest.jpg/

[Walter Roberson]

Draw straight lines across the image and use parity counting. When done horizontally and vertically you should be able to distinguish whether a vertical crossing count of 2 indicates you have crossed a loop of a single chain vs having crossed both chains once.

[Justin Bondy]

@Walter I don't think I understand what you mean by parity counting. Do you mean create a grid on the image and have each line return how many objects (beads) it encountered?