floodFill in place

[AB-Kent]

Would it be possible to add a version of floodFill that performs the operation in place?

I have images roughly 1500x1000 to 1800x1400 with hundreds of regions I want to fill with different values. Using EBImage::floodFill, the runtime seems to be dominated by the GC as each fill operation allocates a new copy of the image.

Would it be possible make a version of floodFill that copies the source image only if there are multiple references to it, otherwise modifying it in place?

[aoles]

Thanks for your feedback! Your performance issues could be probably addressed by allowing the argument pt to floodFill to accept a list of positions rather than just a single point. Then the loop in count_touching_cells could be collapsed to a single function call with only one image duplication. I will look into this and get back to you in the following days. In the meantime, feel free to have a look at bwlabel which seems to do a similar thing as your code does, and therefore might be of interest to you.

[AB-Kent]

That's close. For my application I would need the col argument to also accept a list. I have a mask image that defines regions, a known point within each region and a desired label for the region. The numbering is pre-determined so I don't think I can use bwlabel. I did take it as inspiration for my request as it calls _floodFill multiple times on the same image. Thanks for considering this! And yes, you found the critical code :-)

[aoles]

I've enabled filling of multiple objects with possibly different labels/colors across the whole image stack, feel free to test. For details and examples see the documentation ?floodFill.

I'm looking forward to hearing from you whether this helped to address the bottleneck. If you feel up to it, it would be really great if you could perform some before/after benchmark and provide the results.

[AB-Kent]

Not working for me because of #23 :-(

[AB-Kent]

Figured it out. The parameters for floodFill are a little confusing; for my application I don't need to pass a matrix so I don't have to worry about #23.

For an 1868 x 1400 image, filling 417 regions using the new method is about 500 times faster than the old method - 12 milliseconds vs 6+ seconds!!

> library(microbenchmark)
> dim(image)
[1] 1868 1400
> length(nuc_locations)
[1] 417
> microbenchmark(EBImage::floodFill(image, list(nuc_locations),
+                                   list(as.list(cell_ids))), times=10)
Unit: milliseconds
                                                                    expr      min       lq
 EBImage::floodFill(image, list(nuc_locations), list(as.list(cell_ids))) 9.122525 9.279515
     mean   median      uq      max neval
 11.87673 9.622194 11.1117 21.07505    10
> 
> microbenchmark({y=image
+   for (i in seq_len(length(nuc_locations))) 
+     y = EBImage::floodFill(y, nuc_locations[i], cell_ids[i])}, 
+   times=10)
Unit: seconds
                                                                                                                              expr
 {     y = image     for (i in seq_len(length(nuc_locations))) y = EBImage::floodFill(y,          nuc_locations[i], cell_ids[i]) }
      min       lq     mean   median       uq      max neval
 6.230726 6.255482 6.350389 6.341448 6.431667 6.524966    10

[aoles]

Thanks for getting back to me with the benchmark results. Indeed, the performance boost is impressive!

Also, thank you for your feedback on the interface to floodFill. In order to improve usability I've modified the arguments such that it is not necessary anymore to wrap a list of points into another list when applied to single-frame images. For the sake of flexibility pts can be given as either of:

• a list of points list(c(x1, y1), c(x2, y2), ...)
• a plain vector c(x1, y1, x2, y2, ...)
• a matrix or data frame of the form

  x1 y1
  x2 y2
  ...
  

The following example illustrates the different but equivalent ways of specifying the starting points.

library(EBImage)
x = readImage(system.file("images", "shapes.png", package="EBImage"))
y = combine(x, x)

p1 = c(67, 146)
p2 = c(466, 72)
p3 = c(155, 66)

# points provided as a vector of coordinates
pts = c(p1, p2)
refx = floodFill(x, pts, 0.5)
refy = floodFill(y, list(pts, p3), 0.5)

# points provided as a list of coordinates
pts = list(p1, p2)
identical(refx, floodFill(x, pts, 0.5))

## [1] TRUE

identical(refy, floodFill(y, list(pts, p3), 0.5))

## [1] TRUE

# points provided in a matrix
pts = rbind(p1, p2)
identical(refx, floodFill(x, pts, 0.5))

## [1] TRUE

identical(refy, floodFill(y, list(pts, p3), 0.5))

## [1] TRUE

# points provided as a data frame
pts = data.frame(pts)
identical(refx, floodFill(x, pts, 0.5))

## [1] TRUE

identical(refy, floodFill(y, list(pts, p3), 0.5))

## [1] TRUE

[AB-Kent]

Thanks for the change!

You might want to include the code in your comment above as either example code for floodFill or as a test...