Find missing spots in a grid of spots
Locked
Find missing spots in a grid of spots
 
|
Dear fellow ImageJ users,
a colleague of mine is looking for an automated solution to find missing spots in a rectangular grid of small spots. The spots are quite uniformly sized and have similar brightness. The grid might be rotated slightly. Only a few spots are expected to be missing in each picture (<1 % of all grid positions). The grid itself is only virtually created by the visible spots. Apart from the visible spots on dark background there are no distinguishing features in the images. There are thousands of images to be processed, so the solution has to be fully automated. I think it should be not hard to find the coordinates of the existing spots by some particle analysis plugins in ImageJ. However, given a list of coordinates of visible spots, how would you identify the missing ones? Does anybody know of an existing solution to solve this? I can provide an example image if it helps, but was not sure how the mailing list policy is about attachments. Best regards Cornelius -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
As usual, my mind goes immediately to a full Java solution. It you don't have anyone capable
of writing custom Java plugins for FIJI, my comments may not be useful. As you say - it should be easy to find many of the existing particles. That's a relatively straightforward, bottom-up use of standard image analysis tools. Given a collection of high-probability (easily found) particles, you can form a theory about the nature of the grid. With enough data, you can create a set of *predictions* about where particles should (and should not) exist. This may cause you to reject some of the particles found in the first step, because they don't fit the pattern. Your parameter space seems to have 3 parameters: a) rotation angle b) spacing in "x" (in quotes because it may not correspond to the horizontal axis of the image) c) spacing in "y" plus 2 more parameters to specify a reference particle (x,y location in the image). One way to tease out the rotation angle is to project the set of known particles onto several rotated lines, and select the rotations (there should be two, at roughly 90 degrees) that gives you the sharpest peaks. This would also allow you to read off the two spacing parameters. If you are sure the grid is rectangular, you can project unto two projection lines at 90 degrees, and perhaps get more robust detection of the angle. With lots of data, you might consider Fourier analysis. Now that you have a theory - you can construct a set of points where you *expect* to find a particle. This makes the problem a "verification vision" one. Examine each location, and decide if the image data support the presence, or the absence, of a particle. Done. Once you write the Java program, and test it on a few images, the analysis of the "thousands" of images can be easily automated. -- Kenneth Sloan [hidden email] Vision is the art of seeing what is invisible to others. > On 14 Jan 2018, at 12:35 , Cornelius Sicker <[hidden email]> wrote: > > Dear fellow ImageJ users, > > a colleague of mine is looking for an automated solution to find missing > spots in a rectangular grid of small spots. The spots are quite > uniformly sized and have similar brightness. The grid might be rotated > slightly. Only a few spots are expected to be missing in each picture > (<1 % of all grid positions). The grid itself is only virtually created > by the visible spots. Apart from the visible spots on dark background > there are no distinguishing features in the images. There are thousands > of images to be processed, so the solution has to be fully automated. > > I think it should be not hard to find the coordinates of the existing > spots by some particle analysis plugins in ImageJ. However, given a list > of coordinates of visible spots, how would you identify the missing > ones? Does anybody know of an existing solution to solve this? > > I can provide an example image if it helps, but was not sure how the > mailing list policy is about attachments. > > Best regards > Cornelius > > -- > ImageJ mailing list: http://imagej.nih.gov/ij/list.html -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
In reply to this post by Cornelius Sicker-2
Dear Cornelius,
If you think of writing a macro I can imagine something like: - alignment of the images to the standard model containing all spots. - threshold all images. - XOR image calculator between images and model creating images of the missing spots. - Find the Centre of Mass of each spot found to be missing in the results images via Analyze Particles. This step will also allow you to select on size to remove non perfect overlap of spots. Best wishes Kees Dr Ir K.R. Straatman Senior Experimental Officer Advanced Imaging Facility Centre for Core Biotechnology Services University of Leicester www.le.ac.uk/advanced-imaging-facility -----Original Message----- From: Cornelius Sicker [mailto:[hidden email]] Sent: 14 January 2018 18:36 To: [hidden email] Subject: Find missing spots in a grid of spots Dear fellow ImageJ users, a colleague of mine is looking for an automated solution to find missing spots in a rectangular grid of small spots. The spots are quite uniformly sized and have similar brightness. The grid might be rotated slightly. Only a few spots are expected to be missing in each picture (<1 % of all grid positions). The grid itself is only virtually created by the visible spots. Apart from the visible spots on dark background there are no distinguishing features in the images. There are thousands of images to be processed, so the solution has to be fully automated. I think it should be not hard to find the coordinates of the existing spots by some particle analysis plugins in ImageJ. However, given a list of coordinates of visible spots, how would you identify the missing ones? Does anybody know of an existing solution to solve this? I can provide an example image if it helps, but was not sure how the mailing list policy is about attachments. Best regards Cornelius -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
In reply to this post by Cornelius Sicker-2
To find the missing spots,
Create a binary image of the spots you have - thresholding Create a distance map outwards from the spots. Locations of 'Missing spots' will be shown in the distance map by thresholding - -----Original Message----- From: ImageJ Interest Group [mailto:[hidden email]] On Behalf Of Cornelius Sicker Sent: den 14 januari 2018 19:36 To: [hidden email] Subject: Find missing spots in a grid of spots Dear fellow ImageJ users, a colleague of mine is looking for an automated solution to find missing spots in a rectangular grid of small spots. The spots are quite uniformly sized and have similar brightness. The grid might be rotated slightly. Only a few spots are expected to be missing in each picture (<1 % of all grid positions). The grid itself is only virtually created by the visible spots. Apart from the visible spots on dark background there are no distinguishing features in the images. There are thousands of images to be processed, so the solution has to be fully automated. I think it should be not hard to find the coordinates of the existing spots by some particle analysis plugins in ImageJ. However, given a list of coordinates of visible spots, how would you identify the missing ones? Does anybody know of an existing solution to solve this? I can provide an example image if it helps, but was not sure how the mailing list policy is about attachments. Best regards Cornelius -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
In reply to this post by Cornelius Sicker-2
Dear ImageJ advisors,
Thank you very much for your helpful responses. In the end we have created a solution which is along the lines of that proposed in the 1st reply. Namely, to use a projection of the image along the X and Y directions to discern the columns and rows of spots (Offset X & Y, Spacing X & Y). In order to detect the angle required to un-rotate the image, so that the rows and columns of spots lie along the image axes, we do the projection for a selection of different image rotations and then select that with the sharpest peaks. (1) Initial image with rotated spot grid: * * * * * * * * * * * * * * Projection down the Y axis gives an mean-intensity curve with a series of peaks: | | | | | | | | | | | | # # # # ## ## ## # ## ## #_____###_____###_____###_____### (2a) If we rotate the image though a sequence of angles, and for each rotation re-compute the projection, then we get a series of similar looking mean-intensity curves. The projection with the correct rotation will have the thinnest and highest peaks. (2b) We can plot the maximum mean-intensity seen (peak height) verses rotation angle, and then we have a curve with a single maxima at the best angle which can be detected automatically to determine the desired rotation angle. (3) Having determined the image with the correct rotation we now try to find the positions of the rows and columns of spots within the image. We take X and the Y projections for the image and use a standard peak detecting algorithm to generate a list of peaks which should correspond to the positions of the columns (X), and rows (Y). The X and Y projections are independent and so are processed separately, but using the same algorithm. - We sort the array so that the peak positions are in order, and then by taking differences between neighboring elements we get the spacing of the grid points. We take the average of all the spacing's to get the best estimate of the grid spacing. - Having got a good estimate for the peak spacing we then determine the best fit offset. Using the spacing estimate and the offset of the 1st peak we compute an array of expected positions for the rest of the peaks. One can take the difference (error) and compute an average value which can be subtracted from the position of the 1st peak to get a best fit offset for the grid. This part of the routine is not robust against cases where one of the peaks fails to be detected (for example if it has a lower than usual intensity due to a large number of missing spots, in the corresponding row/col). (4) Once we have the best estimate for the positions of the rows and columns, and the grid rotation, then we populate a 2D array with the X&Y positions of the grid points. We then iterate through the array and for each grid point we can cut out a small region of the original image and measure some statistics from the pixel intensities therein. These statistics are then used to decide if a peak is present or not at the corresponding grid point. --- The above approach has two issues: - The process of rotating the image and projecting the intensities is 'relatively' slow. Projecting along lines at angles might be faster, but the coding for the rotate->project approach was easier... - As the image is rotated the background becomes visible in certain areas. Because this background isn't the same as the camera black level then the projected mean-intensity curves show dips at the edges. One option is to correct the camera dark level, or match the image background. Another is the clip the image - however this means that the rows/columns of spots at the image edge are often not detected. A faster algorithm can be deployed when the image has a large enough number of spots. (1) use a standard spot finding algorithm to find all the bright spots in the original image, it returns a list of X and X coordinates for all of the spots. (2) plot a histogram of the X and another of the Y coordinates, these are similar to the mean-intensity curves which are used in the rotate->project approach. Therefore, pretty much the same algorithm is deployed thereafter, the main difference being that rotation is done via a transformation of the spot X&Y coordinates. A potential downside to this algorithm is that the image is binarized early on and so spots which are too dim are filtered out and do not contribute to the grid detection process (as opposed to the case where you really project the image brightness -> the information from dimmer spots is maintained in the system). We are not sure if this really makes any difference in our application. --- Regarding the usage of a 2D-FFT: We have looked into this, in principle it isn't particularly problematic, but in practice so far we have the issue that the zero'th order is extremely bright and the higher orders are not well isolated. As a consequence, the standard image thresholding algorithms don't seem to good job of separating out the various spots in the FFT. We suspect this might be because generally the input images have spots which are separated by a large black gap. If we low pass filter the input image first then this may improve the situation - but we didn't push this approach so far as the 1st algorithm works rather well! Just too clarify: The 2D FFT approach maps a grid of spots to a grid of spots (in the magnitude component)! But there is method behind the apparent madness. The new grid of spots has a rotation and spacing which is linked to that of the input image. However the grid in the FFT image is always centered on the origin of the image. In principle one can find the spacing and rotation of the original grid by looking for the position of the 1st order spots in the FFT, which can be found by detecting all the spots in the FFT and sorting them by radial distance from the center. Once the 1st orders are detected in the FFT magnitude map, then one can look up the phase of these components. This should be related to the offset of the grid in the original image. It seems likely that the FFT approach will be rather robust against missing spots and noisy data. Thanks again to all those who posted a response, we have read them all, but after the success with initial attempt as described above we have settled on that approach for now. Best regards Cornelius + colleagues -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
In reply to this post by Cornelius Sicker-2
On 2018/01/31, at 06:00, IMAGEJ automatic digest system <[hidden email]> wrote:
> We take X and the Y projections for the image and use a > standard peak detecting algorithm to generate a list of peaks which > should correspond to the positions of the columns (X), and rows (Y). We try to find in a similar way all spot locations of a hexagonal grid in 1024x1024px images, with the same characteristics of missing spots as those in the original question. The web search for X-project or Y-project does not really return useful results because in image processing they are too common a term. As 'Scale' to 1x1024 and 1024x1 images does not allow for min/max/mean/modal/stdev like z-project does it misses a lot of more than obvious spots. The 'simplest' alternative we could find was to duplicate an image into a 1024x1024x2 stack, do a reslice to 2x1024x1024 and 1024x2x1024, then do a z-project 'Sum' to a 2x1024 or a 1024x2 image and located maxima in these images. Is there a command which I overlooked, which is equivalent to the 'Z-project', that can project the plane in X or Y direction onto a single pixel wide image? Ard ________________________________ AMC Disclaimer : https://www.amc.nl/disclaimer ________________________________ -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
I can't tell if I am misunderstanding this, but why not just find the spots
first, then get their coordinates (eg their XStart Ystart points, or their centroids if they are convex, then check in the original image with each grid cell labelled uniquely, to which label corresponds each spot coordinate pairs. That way you have both the coordinates and the grid cell they are in and you can also know how many spots each cell has. Is that what you were after? Cheers Gabriel On Wednesday, 31 January 2018 10:23:51 GMT [hidden email] wrote: > On 2018/01/31, at 06:00, IMAGEJ automatic digest system <[hidden email]> wrote: > > We take X and the Y projections for the image and use a > > standard peak detecting algorithm to generate a list of peaks which > > should correspond to the positions of the columns (X), and rows (Y). > > We try to find in a similar way all spot locations of a hexagonal grid in > 1024x1024px images, with the same characteristics of missing spots as those > in the original question. The web search for X-project or Y-project does > not really return useful results because in image processing they are too > common a term. -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
Hi Gabriel,
Unless I grossly misunderstand you, I'm afraid that is not exactly what we are after, as we are after the perfect grid with all missing dots put back in and stray blobs removed. This grid is generated by drawing circles in an empty window, by the way. Imagine a perfect honeycomb (hexagonal) with a dot on every corner and a dot in the center of each honeycomb cell. Now erase all edges so only the dots are left. Then randomly remove some dots. Now degrade each remaining dot a random number of pixels around the perimeter. Then shift and rotate the whole image across an arbitrary distance and angle < 30 degrees. Add noise. Invert the image. Add noise again. In the cleaned-up image below, which is only 1 degree off vertical, there are two dots missing (3rd column 9th row and 4th column 8th row; near the latter is a strayblob, not a dot). Both the missing dots and the stray blob could easily be identified by an X- and Y projection. Analyze Particles, with the proper size and circularity will find the most dots correctly, but of course it will not find the missing dots and it is confused by the stray dots too. We are asked to indicate which dot(s) have vanished and which are not dots but blobs, so as to generate the 'perfect' honeycomb dot pattern again. <http://imagej.1557.x6.nabble.com/file/t188556/dots.gif> -- Sent from: http://imagej.1557.x6.nabble.com/ -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
A spatial correlation image would avoid the repeated rotations and projections,
the maxima in a cross correlation between two image shows the offset and in a self correlation gives the spacing and direction of repeated structures. Is there a plugin or command ? Jeremy Adler -----Original Message----- From: ImageJ Interest Group [mailto:[hidden email]] On Behalf Of ard Sent: den 31 januari 2018 15:54 To: [hidden email] Subject: Re: Find missing spots in a grid of spots Hi Gabriel, Unless I grossly misunderstand you, I'm afraid that is not exactly what we are after, as we are after the perfect grid with all missing dots put back in and stray blobs removed. This grid is generated by drawing circles in an empty window, by the way. Imagine a perfect honeycomb (hexagonal) with a dot on every corner and a dot in the center of each honeycomb cell. Now erase all edges so only the dots are left. Then randomly remove some dots. Now degrade each remaining dot a random number of pixels around the perimeter. Then shift and rotate the whole image across an arbitrary distance and angle < 30 degrees. Add noise. Invert the image. Add noise again. In the cleaned-up image below, which is only 1 degree off vertical, there are two dots missing (3rd column 9th row and 4th column 8th row; near the latter is a strayblob, not a dot). Both the missing dots and the stray blob could easily be identified by an X- and Y projection. Analyze Particles, with the proper size and circularity will find the most dots correctly, but of course it will not find the missing dots and it is confused by the stray dots too. We are asked to indicate which dot(s) have vanished and which are not dots but blobs, so as to generate the 'perfect' honeycomb dot pattern again. <http://imagej.1557.x6.nabble.com/file/t188556/dots.gif> -- Sent from: http://imagej.1557.x6.nabble.com/ -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
Re: Find missing spots in a grid of spots
|
|
In reply to this post by ard
On Wednesday, 31 January 2018 14:53:59 GMT you wrote:
> Hi Gabriel, > Unless I grossly misunderstand you, I'm afraid that is not exactly what we > are after, Yes, sorry I misunderstood the problem. Well your grid dots and the noise blobs are completely different. You probably can tell them apart by morphological analysis of size and shape. Once you have all the right dots in your Results Table, then chose one randomly from the list and floodfill it black at the XStart YStart point. That will remove it. For the "degradation of the dots" it depends what you want to do. I do not think there is a simple command to do that. You could diffuse random particles in the background until the stick to one dot, or vectorise the perimeter and add extra points to it, or add random dots to the image and use binary reconstruction to retrieve the modified ones based on the ones existing in the original. Cheers Gabriel -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
In reply to this post by ard
Good day,
concerning the rotation I determined an angle of 0.9 degrees for the provided sample image. What I did for this analysis is: 1. "Process >> FFT >> FFT Options... >> Raw power spectrum + Do forward transform" 2. Make a selection for the resulting power spectrum: "Edit >> Selection >> Specify >> 255, 255, 512, 512, Oval + Constrain circle + Centered" 3. Run plugin "Slice_Integrals" available from here <<http://www.gluender.de/Miscellanea/MiscTexts/UtilitiesText.html> with parameters "Number of Angles = 402, Slice Interpolation = Bicubic" The resulting graph gives you the distribution of power in the Fourier-spectrum as a function of the angle. For the sample image I get 119.10 degrees that, modulo 60 degrees, gives a rotation of 0.9 degrees. Regards Herbie ::::::::::::::::::::::::::::::::: Am 31.01.18 um 15:53 schrieb ard: > Hi Gabriel, > Unless I grossly misunderstand you, I'm afraid that is not exactly what we > are after, as we are after the perfect grid with all missing dots put back > in and stray blobs removed. This grid is generated by drawing circles in an > empty window, by the way. > Imagine a perfect honeycomb (hexagonal) with a dot on every corner and a dot > in the center of each honeycomb cell. Now erase all edges so only the dots > are left. Then randomly remove some dots. Now degrade each remaining dot a > random number of pixels around the perimeter. Then shift and rotate the > whole image across an arbitrary distance and angle < 30 degrees. Add noise. > Invert the image. Add noise again. > > In the cleaned-up image below, which is only 1 degree off vertical, there > are two dots missing (3rd column 9th row and 4th column 8th row; near the > latter is a strayblob, not a dot). Both the missing dots and the stray blob > could easily be identified by an X- and Y projection. Analyze Particles, > with the proper size and circularity will find the most dots correctly, but > of course it will not find the missing dots and it is confused by the stray > dots too. > > We are asked to indicate which dot(s) have vanished and which are not dots > but blobs, so as to generate the 'perfect' honeycomb dot pattern again. > > <http://imagej.1557.x6.nabble.com/file/t188556/dots.gif> > > > > > -- > Sent from: http://imagej.1557.x6.nabble.com/ > > -- > ImageJ mailing list: http://imagej.nih.gov/ij/list.html > -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
In reply to this post by ard
Dear,
attached please find a result image obtained from an experimental approach (ImageJ macro). <http://imagej.1557.x6.nabble.com/file/t380516/Result.png> Please tell me if this is what you want and if you like to get the coordinates of the missing dots and of the spurious blobs. Please note that the original result image is bipolar, i.e. gray denotes zero. HTH Herbie -- Sent from: http://imagej.1557.x6.nabble.com/ -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
In reply to this post by Gabriel Landini
@ Gabriel,
In this particular case, a 'nice' image, indeed the blob is morphologically different from the dots. Many of the images have much more deteriorated dots, down to a dozen of pixels, and blobs and dots are hard to separate, except for the regularity in their x- and y coordinate increments. We measure the x-y centers of gravity and then reconstruct the original grid by drawing circles of known size to be used as a mask. Having all centers gives a more robust reconstruction of the mask. @ Herby, I did not know that plugin yet and will experiment with it. The result of your attempt looks promising. When I can find all dots as clearly outstanding from the background as your result, it is easy to find them via particle analysis and thus locate the centers. Thanks for pointing me in that direction. Hoping Cornelius also benefits form these answers, I'm off to implement :-) Ard -- Sent from: http://imagej.1557.x6.nabble.com/ -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
|
|
Good day Ard,
I have a macro at hand that generates the image I've posted before but I'm still not perfectly sure about what your colleague likes to see as a result. The macro generates an ideal dot grid from the input image. Then it matches this ideal dot grid to the input image and subtracts it from the latter. From the resulting difference image it is quite easy to determine the coordinates of the missing dots after proper thresholding and particle analysis. However, I'm not sure how to treat blobs and debris. A similar approach as for the missing dots appears possible but requires a definition of what exactly is to be regarded as a blob ... If the result achieved with my macro is sufficient, I can provided it offlist. On my iMac it takes about 350ms to process the provided 1024x1024 sample image. Regards Herbie ::::::::::::::::::::::::::::::::: Am 05.02.18 um 07:35 schrieb ard: > @ Gabriel, > > In this particular case, a 'nice' image, indeed the blob is morphologically > different from the dots. Many of the images have much more deteriorated > dots, down to a dozen of pixels, and blobs and dots are hard to separate, > except for the regularity in their x- and y coordinate increments. We > measure the x-y centers of gravity and then reconstruct the original grid by > drawing circles of known size to be used as a mask. Having all centers gives > a more robust reconstruction of the mask. > > @ Herby, > I did not know that plugin yet and will experiment with it. The result of > your attempt looks promising. When I can find all dots as clearly > outstanding from the background as your result, it is easy to find them via > particle analysis and thus locate the centers. Thanks for pointing me in > that direction. > > Hoping Cornelius also benefits form these answers, I'm off to implement :-) > > Ard > > > > -- > Sent from: http://imagej.1557.x6.nabble.com/ > > -- > ImageJ mailing list: http://imagej.nih.gov/ij/list.html > -- ImageJ mailing list: http://imagej.nih.gov/ij/list.html |
«
Return to ImageJ
|
1 view|%1 views
| Free forum by Nabble | Edit this page |