image segmentation using graph cut with seed points

Question

I'm working in medical image segmentation and I want to combine fuzzy connectedness algorithm with the graph cut, the idea is to segment the image with fuzzy connectedness the background and the foreground will be used as sink and source for the graph cut algorithm, this is my code to obtain the seeds coordinates for the graph cut segmentation

FC=afc(S,K); %// Absolute FC
u=FC>thresh;
v=FC<thresh;

s=regionprops(u, 'PixelIdxList'); %// listes de pixels de l´objet
t=regionprops(v, 'PixelIdxList'); %// listes de pixels de l´arrière plan
[a,b]=size(s);
[w,c,z]= size(t)

for i=1:a
    for j=1:b
        [y,x] = ind2sub(size(u), s(i,j).PixelIdxList);
    end
end
for k=1:w
    for d=1:c
        [y1,x1] = ind2sub(size(v), t(k,d).PixelIdxList);
    end
end

For the graph cut, I used an algorithm from the File Exchange

For example, I can define

Cs=-log([y x])
Ct=-log([y1 x1])

but the problem is how to combine the information from the cost functions like this part of the code source

u = double((Cs-Ct) >= 0);
ps = min(Cs, Ct);
pt = ps

it will exceed the matrix size

Verdieverdigris

Answer 1

I am not familiar with the graph-cut implementation from FEX you linked to,
but I'll show an example using GCMex matlab wrapper (proper disclosure: I implemented this wrapper).

Assuming you have an image of size size(S) with n pixels and K a sparse matrix of size n-by-n with K(ii,jj) representing how well ii and jj pixels are connected (for neighboring ii and jj).
Moreover, you have a mask u of foreground pixels and a mask v of background pixels to be treated as hard constraints.

First, construct the data term using u and v:

Dc = 1000*[u(:), v(:)]; %// assign very large cost for picking FG pixel to label zero and vice versa

As you can see the data-term Dc, is n-by-2 array with the cost of assigning label l (either 0 or one) to pixel ii is stored in Dc(ii,l+1). Therefore, for pixels in the foreground (u(ii) is 1) assigning label l=0 (i.e. background) the cost you pay is 1000. The same goes for pixels in the background (v(ii) is 1) assigning them to foreground (i.e., l=1) is cost 1000. Therefore, the data term Dc gives very high cost to seed pixels (either foreground or background) getting the wrong label.

Construct a graph-cut object

gch = GraphCut('open'), Dc, [0 1; 1 0], K );
[gch L] = GraphCut('expand',gch);
gch = GraphCut('close',gch);
L = reshape(L, size(u)); 
figure; imshow(L,[]); title('the resulting mask');

---

Note that in rder to use GCMex you need to follw the installation instructions and compile it for it to work.

Synchromesh

Can you please elaborate, how to distribute the weights to source and Sink? currently the subtract the value of source from maxValue to get the value of sink, does this makes sense. – Me

follow this link it's a simple implmentation of interactive graph cut masterravi.wordpress.com/2011/05/24/… – Verdieverdigris

nice! I am wondering how you would do this interactively, i.e. the user can mark seed pixels as hard constraints also after graph cut has been run before. Is it possible to incorporate this input without recalculating everything? – Decided

@Decided you can read more about interactive and iterative image segmentation at this book chapter. it presents a very interesting approach to understanding "user intent" in marking seeds and segmentation cues. – Synchromesh

thanks for the link! I have read parts of it by now. However, my question was more related to your Matlab wrapper specifically (or for another matlab implementation for that matter). – Decided

@Decided my wrapper is quite limited. It offers a global solution thus it needs to re-calculate after every addition of seeds. It might be possible to dive into the wrapped C++ code to re-use graph paths across calculations in order to make the refinement iterations more efficient. But this type of optimization is beyond the scope of this wrapper. – Synchromesh