Fast sorting for particles

[Balaboum]

Hello,

I am a newbie on this forum and I am struggling with a little particle sorting problem under LV 7.1.1.

I get a nice binary image from my image processing vi ( see attached image ). The vi also provide a table containing center of mass coordinates and area of each particle in the image ( 2500 to 3000 particles in total in the image )

Then, I feed this table in a sorting algorithm in order to group particles belonging to same column and number them from top to bottom.

Final goal of the job is to dectect whenever :

- two particles are too close or too far from each other

- if one particle is bigger than others in the same solumn

Of course, this would be a piece of cake if I had enough time, but I need to fit this sorting / defect detection in less than 100ms... Actually, in best case, I get a minimum of 500 ms. For my sorting vi, I already had a look to the sorting 2D array posted in that forum... It works nice but not fast enough in my case, even I am using a PIV 3.4GHz Hyperthreading processor.

Any suggestions ?

Thanks.

[BruceAmmons]

If you could rotate the image 90 degrees before extracting the particles, you would have half the sorting job done for you.  When the particles are located, the algorithm scans across each row looking for new particles.  With rotation, you would get all the particles in one row (former column) before the next row.  You would just need to determine where each row starts and ends, then sort within that row.

Bruce

[Balaboum]

Thanks for the help, Bruce. It is simple and logical.

In the image processing section of my vi, I use erosion to separate particles. According to Vision Assistant performance meter, erosion takes the longuest part of processing. Is there another technique than erosion that can be used to speed-up particle separation ?

Regards.

[BruceAmmons]

To answer the erosion question: maybe.  It depends on the original image and the rest of the processing you are doing.  There may be a faster overall algorithm to do what you want.

I would suggest posting an original image and the processed version of the image, and explain what is critical (particle area, separation, etc.)

Bruce

[Balaboum]

Hello Bruce,

Have a look to the orignal image. You will understand what I am looking for.

To make story short :

I get one image every 100 ms and I want to stop the machine as soon as a defect occur. That's why I want overall image processing and analysis to occur within this time slot. Of course, I set up my main vi to work with several tasks in parallel based also on queues ( one task for image acquisition, one for image processing and analysis, one for I/O, one for HMI, etc... )

Originally, I assumed that all defects create an opening in the product ( similar to springs which insert in each other ) so that I had just to find holes which area was bigger than an ajustable amount. I had the thing work within less 10 ms but I did not catch all defects. Back to work...

So, now, idea is to isolate each top of spring loop and get a table with coordinates of each loop... Finally, a defect will be identified by measuring the distance between consecutive loops in each spring row.

In the first image I posted, the particules are the top of each spring loop. Then, I get the center of mass coordinates and area of each particule. With the table ( containing up to 3000 loop coordinates ), I am able to get wich loops are too close or too far than usual. If I add the area information for each particule, I am able to find if too loops are touching each other, etc...

So, I think I have the good recipe but cooking time is a little bit long... 600 ms...

What's in the engine ?

1) I have to balance the image to correct ligthing which is not perfectly even. I used the Image Balancing Vi found on ni.com. This one took 200ms to process the image. But I was able to nailed it down to 30ms using another technique ( pre-calculated correction image ) but with more noisy result.

2) I apply a AutoThresholding using metrics but particles are not separated enough. So I apply a 7 by 7 matrix erosion before getting the center of mass coordinates and area of each particule. Overall process takes also around 200ms due to erosion that is longest.

3) I sort and manipulate the resulting table to make distance measurement between the 3000 particules. Of course I take advantages of the polymorphic feature of operators when I do calculations between all elements in the arrays. Even with this, it cost me another 200ms...

So, even this is a good recipe, I wonder if I will be able to achieve all this in 100ms.

About the hardware ?

I put a P4 Hyperthreading 3.2Ghz processor with 1Gb of RAM working with a IEEE1394 board and camera.

Do you think I have a chance to reach my objective ?

Another solution would be to put a part of the processing on hardware.

Do you know if NI can provide IEEE1394 interface cards with on-board programmable image processing ?

Or could the couple Labview RT and NI CVS-145x be a solution in my case ?

Again, thanks for your expertise,

Have a nice day.

Message Edité par Balaboum le 03-30-2006 06:19 AM

[BruceAmmons]

Here's an alternate approach I would consider:

Skip the image balancing, thresholding, etc.  Instead, extract a vertical column from the image, and move across the image in small steps of about 5 pixels.  Within the column, you should be able to use detect peaks to locate the top of each spring.  If detect peaks doesn't work, an alternative method such as manual thresholding should work.  This will be a relatively easy way to get the spacings in order.  I suspect the processing will be pretty quick, and you should be able to reach your target speed.  You will have to throw out the results from some line profiles when they are right between two springs, but this is relatively easy to do - just don't throw out too many in a row.

I don't see RT helping you much.  RT doesn't mean faster, it just means more consistent timing.

Bruce