 # KD-Trees in ImageJ - Distance between contours

Hello,

I have some self-developed image segmentation software written in python (for details see link below). Now I want to implement it as a plugin in Fiji/ImageJ to make it publicly available as open source project.

One important step during the algorithm is to compare the distances between two contours.
I decided to take a kd-tree approach.

The following images illustrate the problem:
Fig1. Ground Truth:

Fig3. Good Image Segmentation realization:

In the original Python implementation the distance between the contours is defined as the cumulative distance for every point on the longer contour (by numbers of pixels contributing to the contour) towards the nearest neighbour on the shorter contour.- It has to be mentioned that a contour is defined as the concatenated contour of all contours in one image.

Example Code from Python:

``````import numpy as np
import cv2
from scipy.spatial import cKDTree

[...]

# get the contours
contours1,hierarchy1 = cv2.findContours(img1,cv2.RETR_LIST,cv2.CHAIN_APPROX_NONE)
contours2,hierarchy2 = cv2.findContours(img2,cv2.RETR_LIST,cv2.CHAIN_APPROX_NONE)

# concatenate all contours in one big (non-continous) line
ccc1=np.concatenate(contours1,axis=0)
ccc2=np.concatenate(contours2,axis=0)

# check which contour is longer (made from more pixels):
if len(ccc1) <= len(ccc2):
ar1=ccc1
ar2=ccc2
elif len(ccc1) > len(ccc2):
ar1=ccc2
ar2=ccc1

# query for all distances (from the longer to the shorter contour).
tree1=cKDTree(ar1)
distances=tree1.query(ar2)
``````

This would result in a smaller distance for the image shown in Figure 3 towards the one shown in Fig 1 compared to Fig 2 towards Fig1.

Here are my open questions:

1. How do I obtain a list of all “contour pixels” in Java ImageJ?
So far I use `IJ.run(img, "Outline", "=");` to obtain the contour as an image, but I would need a `list-object`. So this would be a list of pixels in `img` with value `255` - I assume that there is an easier way than iterating over all pixels via `for loop`.
In other words: I am looking for the equivalent of `cv2.findContours` and numpy.concatenate.

2. How can I realize the nearest neighbour approach in Java ImageJ?
I found `net.imglib2.neighborsearch` - however, I do not find good docs or examples.
Sometimes the java code is a bit difficult for me as a python programmer  .

For anyone who is interested, HERE is a link about the theoretical background.

Update:
I made some progress with regards to my 2nd question.
I found this:

It is described, how Weka can perform kd-tree nearest neighbour searches.
I will try that and check out the performance.

However, I would still need some advice on how I can get the ensemble of contour points as a list `Point2d p`.

You can save the xy coordinates of a ROI or selection/overlay using:
Analyze > Tools > Save XY Coordinates

For this skip the outline step. Create a ROI of your objects with Analyze > Analyze Particles…

From Java/Jython/Groovy, you can use `imageplus.getRoi().getFloatPolygon().xPoints` and `...yPoints` which are arrays of individual x and y coordinates. You may then make a list of Points yourself.

Cheers,
Robert

2 Likes

@schmiedc:
Thank you for the answers. Perhaps there is a misunderstanding regarding my question.
I want to proceed with the algorithm inside Fiji/ImageJ. Therefore, I don’t want to export the coordinates into a file. Sorry if I was not precise enough.

@haesleinhuepf:
Thanks a lot for your answer! It wasn’t 100% right, but got me on the right track …
Here is what I did:
I tried :

The problem is that it returns a polygon of the contour - but not the contour.
The white (255) pixels in the figure below represent the actual contour.
The gray (128) pixels represent the polygon. But that would destroy my nearest neighbour approach …

So I found: `getInterpolatedPolygon`
The current code is:

`````` RoiManager roim = RoiManager.getRoiManager();
int N_rois = roim.getCount();
for(int i=0;i <= N_rois ;i++){
Roi roi = roim.getRoi(i);
float[] xx = roi.getInterpolatedPolygon().xpoints;
float[] yy = roi.getInterpolatedPolygon().ypoints;
... }
``````

Which results in: I will continue working on it and update about the progress!
Best Mats

Just a short update for the KD-tree nearest neighbour query. The code on the website that I posted above is apparently a bit outdated and needed some adjustments.
Here is how I adjusted it. (Now only 2D):

``````// the following code is copied and edited from : https://imagej.net/Using_Weka
/**
* Creates a Weka Datastructure out of a List of 2D Points // previously 3D ...
* @param pointsx - List of x-coordinates of 2D Points
* @param pointsy - List of y-coordinates of 2D Points
* @param name - Instance name
* @return Instances containing all 3D points
*/
public Instances insertIntoWeka(final float[] pointsx, final float[] pointsy, final String name)
{
// Create numeric attributes "x" and "y" and "z"
Attribute x = new Attribute("x");
Attribute y = new Attribute("y");
//Attribute z = new Attribute("z");

// Create vector of the above attributes
FastVector attributes = new FastVector(3); // This is depreciated. I should find something else perhaps.

// Create the empty datasets "wekaPoints" with above attributes
Instances wekaPoints = new Instances(name, attributes, 0);

//for (Iterator<Point3d> i = points.iterator(); i.hasNext();)
int len_pointsx = pointsx.length;
for (int j = 0; j < len_pointsx-10; j++)
{
// Create empty instance with three attribute values

Instance inst = new DenseInstance(2); // before it was Instance inst = new Instance(3); // I found this link: https://stackoverflow.com/questions/39060571/cannot-instantiate-the-type-instance-in-java-weka-class and got some help of Benjamin to understand the concept of interfaces.

/*
// get the point3d
Point3d p = i.next();

// Set instance's values for the attributes "x", "y", and "z"
inst.setValue(x, p.x);
inst.setValue(y, p.y);
inst.setValue(z, p.z);
*/
inst.setValue(x, pointsx[j]);
inst.setValue(y, pointsy[j]);
//inst.setValue(z, 0);

// Set instance's dataset to be the dataset "wekaPoints"
inst.setDataset(wekaPoints);

// Add the Instance to Instances
}

return wekaPoints;
}

/**
* Create an Instance of the same type as the Instances object you are searching in.
* @param pointsx - List of x-coordinates of 2D Points
* @param pointsy - List of y-coordinates of 2D Points
* @param dataset - the dataset you are searching in, which was used to build the KDTree
* @return an Instance that the nearest neighbor can be found for
*/
public Instance createInstance(final float pointx, final float pointy, final Instances dataset)
{
// Create numeric attributes "x" and "y" and "z"
Attribute x = dataset.attribute(0);
Attribute y = dataset.attribute(1);
//Attribute z = dataset.attribute(2);

// Create vector of the above attributes
FastVector attributes = new FastVector(3);

// Create empty instance with three attribute values
Instance inst = new DenseInstance(2);

// Set instance's values for the attributes "x", "y", and "z"
/*
inst.setValue(x, p.x);
inst.setValue(y, p.y);
inst.setValue(z, p.z);
*/
inst.setValue(x, pointx);
inst.setValue(y, pointy);

// Set instance's dataset to be the dataset "points1"
inst.setDataset(dataset);

return inst;
}

[...]
* @param arX_conc - List of x-coordinates of 2D Points from the concatenated contours
* @param arY_conc - List of y-coordinates of 2D Points from the concatenated contours
Instances wekaPoints1 = insertIntoWeka(arX_conc,arY_conc, "wekaPoints1");

KDTree tree = new KDTree();

try
{
tree.setInstances(wekaPoints1);

EuclideanDistance df = new EuclideanDistance(wekaPoints1);
df.setDontNormalize(true);

tree.setDistanceFunction(df);
}
catch (Exception e) { e.printStackTrace();}

Instance nn1, nn2;
final Instance p = createInstance(876,588, wekaPoints1); // distance should be around 12.66

try
{
Instances neighbors = tree.kNearestNeighbours(p, 2);
nn1 = neighbors.instance(0);
nn2 = neighbors.instance(1);
}
catch (Exception e) { nn1 = nn2 = null; }

System.out.println(nn1 + " is the nearest neigbor for " + p);
System.out.println(nn2 + " is the second nearest neigbor for " + p);

// Now we can also easily compute the distances as the KDTree does it

DistanceFunction df = tree.getDistanceFunction();
System.out.println("The distance between" + nn1 + " and " + p + " is " + df.distance(nn1, p));
System.out.println("The distance between" + nn2 + " and " + p + " is " + df.distance(nn2, p));
``````

This results in:

``````889,588 is the nearest neigbor for 876,588
889,589 is the second nearest neigbor for 876,588
The distance between889,588 and 876,588 is 13.0
The distance between889,589 and 876,588 is 13.038404810405298
``````

The manual measurement with Fiji was 12.66 and 889,588 is indeed the nearest point!
That’s cool!

Now I have to automatize it for more than one point … and than work on the Bayesian part of this project.

I am getting closer to the solution:
Instead of a single pixel I now used every 10th pixel of figure 2 and drew a line between it and its nearest neighbor of figure 3.

red - contours of figure 2
blue - contours of figure 3
white - line between every 10th point on red towards its nearest neighbor on blue

The cumulative distance (for every 10th pixel) between figure 2 and 3 is:
318633.03 pixels.

1 Like