BinarySegmentation.java
package com.github.celldynamics.quimp.plugin.binaryseg;
import java.util.ArrayList;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import com.github.celldynamics.quimp.geom.SegmentedShapeRoi;
import com.github.celldynamics.quimp.geom.TrackOutline;
import com.github.celldynamics.quimp.plugin.QuimpPluginException;
import ij.ImagePlus;
import ij.ImageStack;
import ij.gui.ShapeRoi;
/*
* //!>
* @startuml doc-files/BinarySegmentation_1_UML.png
* User-->(Create BinarySegmentation)
* User->(run tracking)
* User->(get chains)
* (Create BinarySegmentation).->(create TrackOutline) : <<extend>>
* @enduml
*
* @startuml doc-files/BinarySegmentation_2_UML.png
* actor User
* User->BinarySegmentation : <<create>>\n""image""
* loop for every frame
* BinarySegmentation->TrackOutline : <<create>>\n""slice"",""frame""
* activate TrackOutline
* TrackOutline-->BinarySegmentation : //obj//
* BinarySegmentation->BinarySegmentation : store //obj// in ""trackers""
* note left
* See TrackOutline
* trackers are ROIs for
* one slice kept in TrackOutline
* object
* end note
* end
* User->trackObjects
* loop for every tracker //o2//
* loop for every object in tracker //sR//
* trackObjects->TrackOutline : get ""outlines""
* TrackOutline->trackObjects : ""outlines""
* note left : references
* trackObjects->testIntersect : ""sR"",""o2""
* testIntersect->trackObjects : set ID to current outline
* note right
* Modify reference in TrackOutline
* end note
* testIntersect->trackObjects : set parent ID to next outline
* note left
* Test for current object and all
* on next frame
* end note
* end
* end
* User->getChains
* getChains->getChains : sort according to ID
* getChains->User : return array
* @enduml
*
* //!<
*/
/**
* Run Binary segmentation converting grayscale masks to ordered ROIs.
*
* <p>This class mainly join subsequent outlines to chains that contain outlines related by origin (
* when next outline originates from previous - it means that next object overlap previous one) The
* segmentation itself - generation of outlines for one slice is done in TrackOutline class
*
* <p>The ROIs are grouped according to their origin and they have assigned frame number where they
* appeared. The algorithm is as follows: The frames from input stack from first to before last are
* processed. For every i-th frame the outlines are obtained and compared with i+1 frame. If any of
* k-th outline from i+1 frame overlap l-th outline on i-th frame, the k-th outline gets the same id
* as l-th but only if k-th does not have any ID yet. There for if there is outline that does not
* have source on i-th frame, it will skipped now but it will be found in next iteration and because
* it does not have ID, the new will be assigned to it.
*
* <p>If there is break in chain (missing object), the object on the next frame will begin the new
* chain. <br>
* <img src="doc-files/BinarySegmentation_1_UML.png"/><br>
* After creation of object user has to call trackObjects() to run tracking. Segmentation is run on
* object creation. Finally, getChains() should be called to get results - chains of outlines. <br>
* <img src="doc-files/BinarySegmentation_2_UML.png"/><br>
*
* <p>For grayscale input algorithm compares stroke color of ROIs that can be set to color of
* pixels, the roi was taken from by {@link TrackOutline#setColors()}. This assume that color does
* not change for particular cell within frame.
*
* @author p.baniukiewicz
* @see TrackOutline
*
*/
public class BinarySegmentation {
/**
* The Constant LOGGER.
*/
static final Logger LOGGER = LoggerFactory.getLogger(BinarySegmentation.class.getName());
private int nextID = 0; // next free ID
private ImagePlus ip; // image to process (stack)
/**
* Predefined background color.
*/
int backgroundColor = 0;
/**
* Array of segmented slices. One TrackOutline object can have some outlines, depending how many
* objects were on this slice
*/
private TrackOutline[] trackers;
/**
* True if all slices are 2 color.
*
* <p>This trigger different method of correlation objects between frames. For binary slices (all)
* overlapping is tested, for grayscale we use color of pixels the Rois was taken from, copied by
* {@link TrackOutline#setColors()}
*/
private boolean isBinary = true;
/**
* Constructor for segmentation of stack.
*
* @param ip stack of images to segment
* @throws QuimpPluginException when image is null or wrong type
*/
public BinarySegmentation(final ImagePlus ip) throws QuimpPluginException {
if (ip == null) {
throw new QuimpPluginException("The image was null");
}
if (!ip.getProcessor().isGrayscale()) {
throw new QuimpPluginException("Input image must be 8-bit");
}
this.ip = ip.duplicate();
// determine method of corelating between frames
for (int s = 1; s <= ip.getImageStackSize(); s++) {
isBinary = isBinary && ip.getStack().getProcessor(s).isBinary();
}
LOGGER.debug("Got " + ip.getImageStackSize() + " slices");
trackers = new TrackOutline[this.ip.getImageStackSize()];
ImageStack ips = this.ip.getStack();
for (int i = 0; i < trackers.length; i++) {
trackers[i] = new TrackOutline(ips.getProcessor(i + 1), backgroundColor, i + 1); // outlining
// set stroke color for ROI, assume that after segmentation the same cells will have the same
// color
if (isBinary == false) {
trackers[i].setColors();
}
}
}
/**
* Test whether two ROIs overlap or have the same color. Modify r1 parameter
*
* @param r1 First ROI - it will be modified!
* @param r2 Second ROI
* @return true if r1 and r2 overlap
*/
private boolean testIntersect(final ShapeRoi r1, final ShapeRoi r2) {
if (r1 == null || r2 == null) {
return false;
}
if (isBinary == true) {
ShapeRoi intersect = r1.and(r2);
if (intersect.getFloatWidth() == 0 || intersect.getFloatHeight() == 0) {
LOGGER.debug(r1 + " and " + r2 + " do not intersect");
return false;
} else {
LOGGER.debug(r1 + " and " + r2 + " do intersect");
return true;
}
} else { // not binary image on input, use color codes
if (r1.getStrokeColor().equals(r2.getStrokeColor())) {
return true;
} else {
return false;
}
}
}
/**
* Test whether given ROI overlap any of ROI in array and assign correct ID to ROIs
*
* <p>If any of sRa overlap sR, the roi from array gets the same ID as \a sR. If \a sR does
* not have ID it get the new one
*
* @param sr ROI to test (not modified)
* @param sra Array of ROIs to test
*
*/
private void testIntersect(final SegmentedShapeRoi sr, final ArrayList<SegmentedShapeRoi> sra) {
if (sr.getId() == SegmentedShapeRoi.NOT_COUNTED) { // root - first outline
sr.setId(nextID++); // if not counted start new chain assigning new id
}
for (SegmentedShapeRoi s : sra) {
if (testIntersect((ShapeRoi) sr.clone(), s) == true) {
s.setId(sr.getId()); // next outline has the same id
break; // do not look more on this set (this frame)
}
}
}
/**
* Main runner for tracking.
*
* <p>In result of this method the ROIs kept in TrackOutline objects will be modified by giving
* them IDs of their parent.
*/
public void trackObjects() {
if (trackers.length == 1) { // only one slice, use the same reference for testIntersect
ArrayList<SegmentedShapeRoi> o1 = trackers[0].outlines; // get frame current
ArrayList<SegmentedShapeRoi> o2 = trackers[0].outlines; // and next
for (SegmentedShapeRoi sr : o1) { // iterate over all objects in current frame
testIntersect(sr, o2); // and find its child if any on next frame
}
} // loop below does not fire for one slice
for (int f = 0; f < trackers.length - 1; f++) { // iterate over frames
ArrayList<SegmentedShapeRoi> o1 = trackers[f].outlines; // get frame current
ArrayList<SegmentedShapeRoi> o2 = trackers[f + 1].outlines; // and next
for (SegmentedShapeRoi sr : o1) { // iterate over all objects in current frame
testIntersect(sr, o2); // and find its child if any on next frame
}
}
// check if we have any uncounted object at last frame. It can happen if there is lonely object
// that exists only at last frame
ArrayList<SegmentedShapeRoi> o2 = trackers[trackers.length - 1].outlines;
for (SegmentedShapeRoi sr : o2) {
if (sr.getId() == SegmentedShapeRoi.NOT_COUNTED) {
sr.setId(nextID++);
}
}
}
/**
* Compose chains of object related to each others along frames.
*
* <p>Relation means that previous object and next one overlap, thus their segmentations will be
* assigned to the same group and they will be in correct order as they appeared in stack
*
* @return List of Lists that contains outlines. First level of list is the chain (found related
* objects), the second level are outlines for this chain. Every outline has coded frame
* where it appeared.
*/
public ArrayList<ArrayList<SegmentedShapeRoi>> getChains() {
ArrayList<ArrayList<SegmentedShapeRoi>> ret = new ArrayList<>(nextID);
for (int i = 0; i < nextID; i++) {
ret.add(new ArrayList<>());
}
for (TrackOutline to : trackers) { // go through all Outlines and sort them for ID
for (SegmentedShapeRoi ss : to.outlines) {
ret.get(ss.getId()).add(ss);
}
}
return ret;
}
}