# Image Segmentation: (Efficient Graph-Based)

This question is two-fold; First, it is about how to get the speed efficiency this algorithm should provide in Mathematica. In addition, it has a small question about the algorithm (Efficient Graph-Based Image Segmentation) itself.

# Code

First we need an image. I am using my own (as seen in the included photos), so please replace <your-image> with your image.

img = <your-image>;
simg = ImageResize[img, 50] (* resize for debugging purposes *)


So as a pre-requisite, we need to make a k-Nearest Neighbors (KNN) graph, which means we need to be working on the pixel values themselves.

(* list of list of pixels {{pix11, pix21,...pixw1},...,{pix1h,...,pixwh}} *)
\[ScriptCapitalD] = ImageData[simg];
(* list of pixels {pix11, pix21,...pixw1,...,pix1h,...,pixwh} *)
ℱ = Partition[Flatten[\[ScriptCapitalD]], {3}];

k = 8
\[ScriptCapitalG] = NearestNeighborGraph[ℱ, k]
(* Short hand for the lazy *)
\[ScriptCapitalV] =
VertexList[\[ScriptCapitalG]];
ℰ = EdgeList[\[ScriptCapitalG]];


With our KNN graph in hand, we can work on the functions.

First, we need the weight function for our edges. The weight of an edge, $(v_i, v_j)$ is defined as the absolute difference of pixel intensity of each pixel (vertex):

$$w((v_i, v_j)) = \lvert I(v_i) - I(v_j) \rvert$$

This weight is meant to be a scalar, so what exactly the authors meant about pixel intensity (often derived from a histogram over many pixels), is lost on me.

For now, we will use the y channel of the rgb to luminance conversion:

Luminance[r_, g_, b_] := .299 r + .587 g + .114 b;
Luminance[pixel_List] :=
Luminance[pixel[[1]], pixel[[2]], pixel[[3]]];


Which makes our weight function:

weight[edge_] := Abs@(Subtract @@ Luminance /@ edge)


Next, we will need the minimum internal difference, which requires the internal difference, a function called tau, and the maximum weight of an edge in the minimum spanning tree (MST) of the subgraph given the component.

τ[C_, k_] := Infinity /; Length@C == 0; (* error handling empty components *)
τ[C_, k_] := k/Length@C;

internalDifference[G_, C_] := -Infinity /; Length@C == 0;
internalDifference[G_, C_] := 0 /; Length@C == 1;
internalDifference[G_, C_] :=
Max[weight /@ EdgeList@FindSpanningTree@Subgraph[G, C]] /;
Length@C > 1; (* need at least 2 vertices to have edge wieghts *)

minimumInternalDifference[G_, k_, C1_, C2_] := Min[{
internalDifference[G, C1] + τ[C1, k],
internalDifference[G, C2] + τ[C2, k]
}]


We also need to know what component the vertices of the edge are in:

findComponent[segmentation_, pixel_] :=
First@First@Position[segmentation, pixel] (* note: this might be a bit buggy. Obviously if the pixel is not in the segmentation, this will throw an error. Also, I personally dislike using first, first to extract the value. Let me know of better alternatives. *)


With this information, there are only a few things left. We still need the function that makes the new segmentation from the old segmentation:

makeSn[G_, k_, segmentation_, edge_] := Module[
{i, j, Ci, Cj, s, S},
i = findComponent[segmentation, First@edge];
j = findComponent[segmentation, Last@edge];
Ci = segmentation[[i]];
Cj = segmentation[[j]];
If[
(i != j) ∧ (weight[edge] <=
minimumInternalDifference[G, k, Ci, Cj]), (* condition from paper *)
s = Union[Ci, Cj];
(* we need to define S, as in modules, local vars can not be changed. *)
S = Part[segmentation,
Table[If[MemberQ[{i, j}, z], Nothing, z], {z,
Length@segmentation}]];
(* Since merging two components, we take all but those two components and append the merger *)
S = Append[S, s];
Return[S],
S = segmentation;
Return[S]
];
]


We need the order of the edges, and the initial segmentation:

p = SortBy[ℰ, weight]; (* should be non-decreasing order *)
S = Table[{}, {i, Length@p + 1}]; (* S[[1]] is initial segmentation, the rest are for each iteration over the ordered edges *)
S[[1]] = Table[{\[ScriptCapitalV][[i]]}, {i, Length@\[ScriptCapitalV]}]; (* starts with each vertex in its own component *)


and now we can do the iteration:

Table[S[[i + 1]] = makeSn[\[ScriptCapitalG], k, S[[i]], p[[i]]], {i,
Length@p}];


To see what we made, we need a color function:

c[i_, l_] := ColorData["BrightBands"][i/(l + 1)] (* might not be the best coloring option *)


and we need to map pixels to their new colors:

(* This could be a bit buggy if there are at least two pixels with identical values - although this is not an error with the above algorithm. We just need a way to show the pixels, colored by components, where they originally are in the image. *)
(* The outer table extracts the positions of the pixels for each segment and the inner table maps those positions to the components color *)
repl = Table[Table[
f -> c[i, Length@chosenSegmentation], {f,
Flatten[Position[\[ScriptCapitalF], chosenSegmentation[[i]][[j]], 1]]}], {i,
Length@chosenSegmentation}, {j, Length@chosenSegmentation[[i]]}];


And then do the replacement

Image[Partition[
ReplacePart[ℱ,
Flatten@repl], {Length@First@\[ScriptCapitalD]}]]


In the paper they state that for 320x240 images, they use $k=300$ and for smaller, $k=150$.

Besides the KNN taking a very long to generate at large K (even at modest image size of ~100x50 pixels), I have noticed that this (in my tests) always end up converging to 1 component. I can, of course, select a previous segmentation (say with 10 components), so I was curious as to why this might be the case. My assumptions are that it has to do with using a wrong pixel intensity value, or using a wrong error handling value (e.g. -Infinity).

If we pick a segmentation of 50:

Where we can see that some of the main things are separated (sea, sky, boat, frame).

I would appreciate any feedback.

To recap the two questions are:

1.) given above, how to more efficiently do the makeSn function (as well as KNN graph) to segment images more readily? 2.) what is single pixel value intensity? 3.) why does this always converge to a segmentation of 1 component?