# Improving segmentation diffusion

I'm currently working on implementing an efficient method to segment an organ on 3D CT images. I used an algorithm (SLIC) to generate superpixels on each slice of my CT 3D matrix. The process is similar to the k-means algorithm although we do not need to visit the entire image for each pixel. Then I build a graph based on the superpixel: each superpixel is a node in the graph and two nodes are connected if they contains pixels that are 4-adjacent. The weight of the edge between two nodes is their color difference:

$\sqrt {(color1 - color2)² }$

I then tried to implement a method to allow the user to click on a superpixel and label it as foreground or background starting a diffusion algorithm to divide the 3D graph between the two labels. I used the IFT algorithm However it doesn't perform as well as I want: sometime assigning a label or correcting an incorrectly deduced label will cause the algorithm to select improper superpixel.

The steps I used:

1. Convert my matrix in 8 bits greyscale (between 0 and 255 value).
2. Each pixel which value isn't between low_value and high_value is put to 0 (black).
3. I do an histogram equalization to increase the contrast of the remaining values (thus trying to achieve better superpixel boundaries).
4. Apply a blurring kernel to my matrix.
5. Compute superpixels for each slice.
6. Creating the corresponding graph and creating the edges between them.
7. The user clicks with the foreground label (every superpixel is set to foreground).
8. A click with the background label allows some superpixels to be set to background.

I sometime achieve quite satisfying results. But some clicks may completely destroy the correct graph labeling even though they should have worked. I have put a small illustrated example in the following imgur album.

So, my concerns and questions are:

1. Is the IFT algorithm suitable for 3D? I don't see reason why not but my example shows that maybe there label leakage through previous/next slices.
2. What kind of preprocessing step can improve the diffusion.
3. I thought about using dijkstra algorithm to determine which seed was closer to a certain superpixel. It didn't work so well : could it achieve what I want with the correct color distance function?
4. Do you have any advice or article which may help me?

Thank you and sorry if I was not clear, english isn't my first language.

## 2 Answers

In your images, it seems regions are defined more by their edge boundaries rather than their colour.

Since the IFT is using a colour difference metric then it doesn't see much difference between some foreground and background super pixels.

Instead of colour difference I would try a different metric based on boundary edge strength. For example, the weight of the edge between two nodes is set to the average edge strength along their shared super pixel boundary. You might need to define a minimum boundary length though, such as 20 pixels, otherwise noise can effect this.

I've used this measurement before to combine segmentation regions and it works well. Interestingly, I was getting the segmentations using the IFT on a per pixel basis. This method you are applying looks interesting!

You could also combine the two measurements.

• Thanks for your answer. I implemented your idea but it didn't seem to solve the core problems I had: some clicks (labeling input) still produce incoherent labeling. For example if I click somewhere to indicate that one region is background, another superpixel or region, further away and not directly linked to the clicked region/superpixel may be labeled as object. I used a combination of color distance and edge strength (gradient magnitude right?) for the weight of my nodes. – Silouane Gerin May 7 '14 at 12:18
• However if I don't try to process the whole 3D volume but focus only on a slice, things appears fine without weird labeling. So I guess my problems come from trying to apply the algorithm in 3D which may cause leakage. – Silouane Gerin May 7 '14 at 13:38
• Sounds difficult, are the super pixels in 3D or does the path join 2D super pixels on each layer? (I haven't really done much in 3D). – geometrikal May 8 '14 at 13:34
• Thanks again for your interest. I got 2D superpixels that are linked in 3D. Unfortunately I don't have an efficient way to debug it as it is really difficult for me to run through the algorithm with such big graphs (300 000 nodes, 2M edges). – Silouane Gerin May 9 '14 at 7:16
• How about enforce a direction for the graph through the layers. Once a path has gone up or down, label it as an up or down path and don't let it reverse direction. Perhaps that will stop it going up through the layers, finding a leak, and then going back down. Other ideas: add weighting for shared boundary length (single layer) or shared area (across layers). – geometrikal May 10 '14 at 1:00

So I made progress on this particular problem. I have yet to optimize and improve our solution but it is definitely an improvement over what I posted here.

First I do not set pixel value to 0 if they are outside the intensity window I'm targeting anymore. I felt that while it did produce crisp boundaries for my superpixels this preprocessing step could be messing with the IFT algorithm.

I also thought that the IFT algorithm was labeling and relabeling over the same superpixels. I used the differential version of the algorithm which gave me a better global diffusion inside my graph.

The edges obtained in low contrast regions can be jagged but I plan to smooth them with either the Relaxed IFT or some post-processing steps like applying the Fourier Transform to my contour, applying a low pass filter + inverse FT and get a smoothed contour by morphological operators.