Finding islands and centroids
(As you may recall from previous threads, my current project involves aligning two arrays of pixel data that were taken from slightly different perspectives) In an attempt to quantify the accuracy of the alignment I've obtained, I want to do some centroid analysis. The images I'm working with are of "beads" (very small fluorescent blobs), thus each 512x512 image is of a number of more-or-less circular islands each on the order of 50 pixels or so. I figure that I can threshold each image, identify distinct islands, get their centroids, map those to centroids in the other wavelength, and thus get the distance between centroids, which should be a good absolute measure of alignment quality. I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms. -Chris
You might start by browsing through the pymorph documentation: http://www.mmorph.com/pymorph/morph/index.html The mmdcells example might be a starting point: http://www.mmorph.com/pymorph/morph/mmdemos/mmdcells.html Gary R. On Tue, Apr 19, 2011 at 8:37 AM, Chris Weisiger <cweisiger@msg.ucsf.edu> wrote:
(As you may recall from previous threads, my current project involves aligning two arrays of pixel data that were taken from slightly different perspectives)
In an attempt to quantify the accuracy of the alignment I've obtained, I want to do some centroid analysis. The images I'm working with are of "beads" (very small fluorescent blobs), thus each 512x512 image is of a number of more-or-less circular islands each on the order of 50 pixels or so. I figure that I can threshold each image, identify distinct islands, get their centroids, map those to centroids in the other wavelength, and thus get the distance between centroids, which should be a good absolute measure of alignment quality.
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
-Chris
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
On Tuesday, April 19, 2011 02:10:42 am gary ruben wrote:
You might start by browsing through the pymorph documentation: http://www.mmorph.com/pymorph/morph/index.html
The mmdcells example might be a starting point: http://www.mmorph.com/pymorph/morph/mmdemos/mmdcells.html
By the way, that version of pymorph is very old. I adopted the project and it's available at: http://luispedro.org/software/pymorph HTH Luis
You should try OpenCV, which has bindings for python. It has functions to perform many tasks related to this, including thresholding an image, and finding and labeling blobs. I think it can even returns lists of blob centroids... I don't know if you have lots of points in each image, but you may also take a look at the kd-tree classes in scipy for finding the matching points in the images. I started using it the other day for something similar, and it's a breeze! ++nic On Mon, Apr 18, 2011 at 03:37:51PM -0700, Chris Weisiger wrote:
(As you may recall from previous threads, my current project involves aligning two arrays of pixel data that were taken from slightly different perspectives)
In an attempt to quantify the accuracy of the alignment I've obtained, I want to do some centroid analysis. The images I'm working with are of "beads" (very small fluorescent blobs), thus each 512x512 image is of a number of more-or-less circular islands each on the order of 50 pixels or so. I figure that I can threshold each image, identify distinct islands, get their centroids, map those to centroids in the other wavelength, and thus get the distance between centroids, which should be a good absolute measure of alignment quality.
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
-Chris
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
-- Nicolau Werneck <nwerneck@gmail.com> C3CF E29F 5350 5DAA 3705 http://www.lti.pcs.usp.br/~nwerneck 7B9E D6C4 37BB DA64 6F15 Linux user #460716 "There is only one corner of the universe you can be certain of improving and that is your own self." -- Aldous Huxley
On Monday, April 18, 2011 06:37:51 pm Chris Weisiger wrote:
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
You can probably do it in one go: 1) convolve with a Gaussian of roughly the size you expect the PFS of the beads to be. 2) threshold to get the beads. You can probably use a method like mahotas.threshold.otsu to do this automatically 3) scipy.ndimage.label to label the binary image 4, optional) remove noise by removing detections that are too small 5) find centroids of the remaining areas. HTH Luis
Wow, for some reason I didn't get any of these emails until just now. You all have given me plenty of avenues to investigate. Thanks! -Chris On Wed, Apr 20, 2011 at 5:52 AM, Luis Pedro Coelho <luis@luispedro.org>wrote:
On Monday, April 18, 2011 06:37:51 pm Chris Weisiger wrote:
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
You can probably do it in one go:
1) convolve with a Gaussian of roughly the size you expect the PFS of the beads to be.
2) threshold to get the beads. You can probably use a method like mahotas.threshold.otsu to do this automatically
3) scipy.ndimage.label to label the binary image
4, optional) remove noise by removing detections that are too small
5) find centroids of the remaining areas.
HTH Luis
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
Hi Chris, You can also compute this from a stack of incrementally thresholded images. If a pixel is a local maximum it would have no blobs above it and be contained in a blob below. This is described in: Ying, H. , Zhou, F. , Shields, A. F. , Muzik, O. , Wu, D. and Heath, E. I. (2004) A novel computerized approach to enhancing lung tumor detection in whole-body PET images. Proceedings of the 26th Annual International Conference of the IEEE EMBS San Francisco, CA IEEE EMBS Electronic Resource Piscataway, NJ and I also used it (and had written it in IDL at the time): Van Leeuwen, M., Coops, N.C., Wulder, M.A. (2010) Canopy Surface Reconstruction from a LiDAR point cloud Using Hough Transform. Remote Sensing Letters 1: 125 – 132, doi: 10.1080/01431161003649339 Hope that is useful enough, unfortunately I don't have any python code for this so that I could share. Martin. 2011/4/20 Chris Weisiger <cweisiger@msg.ucsf.edu>:
Wow, for some reason I didn't get any of these emails until just now. You all have given me plenty of avenues to investigate. Thanks!
-Chris
On Wed, Apr 20, 2011 at 5:52 AM, Luis Pedro Coelho <luis@luispedro.org> wrote:
On Monday, April 18, 2011 06:37:51 pm Chris Weisiger wrote:
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
You can probably do it in one go:
1) convolve with a Gaussian of roughly the size you expect the PFS of the beads to be.
2) threshold to get the beads. You can probably use a method like mahotas.threshold.otsu to do this automatically
3) scipy.ndimage.label to label the binary image
4, optional) remove noise by removing detections that are too small
5) find centroids of the remaining areas.
HTH Luis
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
hmm, seems no one has suggested using scipy.ndimage.measure yet. When combined with ndimage.label, this should give you all you want without needing to dive in to any external image processing packages. That said ndimage.measure is not particularly fast & you can get a bit of a speed up if you calculate the centroids manually using pre-allocated coordinate arrays. If you want good accuracy you should think about subtracting the threshold value from the data before taking the centroid*. I do this 'bead' (or similar) localisation problem regularly and probably have some example python code I could dig up. *The centroid is nominally the maximum likelihood estimator of position if your noise model is Gaussian, but if you're only doing in in a small region (the labelled beads), you will introduce some quantisation bias. Subtracting the threshold value is a way of minimising this bias. cheers, David ----- Original Message ---- From: Martin van Leeuwen <vanleeuwen.martin@gmail.com> To: SciPy Users List <scipy-user@scipy.org> Sent: Thu, 21 April, 2011 8:08:35 AM Subject: Re: [SciPy-User] Finding islands and centroids Hi Chris, You can also compute this from a stack of incrementally thresholded images. If a pixel is a local maximum it would have no blobs above it and be contained in a blob below. This is described in: Ying, H. , Zhou, F. , Shields, A. F. , Muzik, O. , Wu, D. and Heath, E. I. (2004) A novel computerized approach to enhancing lung tumor detection in whole-body PET images. Proceedings of the 26th Annual International Conference of the IEEE EMBS San Francisco, CA IEEE EMBS Electronic Resource Piscataway, NJ and I also used it (and had written it in IDL at the time): Van Leeuwen, M., Coops, N.C., Wulder, M.A. (2010) Canopy Surface Reconstruction from a LiDAR point cloud Using Hough Transform. Remote Sensing Letters 1: 125 – 132, doi: 10.1080/01431161003649339 Hope that is useful enough, unfortunately I don't have any python code for this so that I could share. Martin. 2011/4/20 Chris Weisiger <cweisiger@msg.ucsf.edu>:
Wow, for some reason I didn't get any of these emails until just now. You all have given me plenty of avenues to investigate. Thanks!
-Chris
On Wed, Apr 20, 2011 at 5:52 AM, Luis Pedro Coelho <luis@luispedro.org> wrote:
On Monday, April 18, 2011 06:37:51 pm Chris Weisiger wrote:
I can hack something together to do this easily enough, where I find a pixel in one of the islands, flood-fill out to get all connected pixels, calculate the centroid, flip the pixels to 0, and repeat until all islands are gone. This isn't exactly very speedy though. What's the efficient way to do this? Is there one? Is there a better approach I should be taking? The image processing class I dimly remember taking years ago didn't cover this kind of thing, so I'm lacking even the basic vocabulary needed to search for algorithms.
You can probably do it in one go:
1) convolve with a Gaussian of roughly the size you expect the PFS of the beads to be.
2) threshold to get the beads. You can probably use a method like mahotas.threshold.otsu to do this automatically
3) scipy.ndimage.label to label the binary image
4, optional) remove noise by removing detections that are too small
5) find centroids of the remaining areas.
HTH Luis
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-User mailing list SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
participants (6)
-
Chris Weisiger -
David Baddeley -
gary ruben -
Luis Pedro Coelho -
Martin van Leeuwen -
Nicolau Werneck