Image segmentation using statistical region merging

Very simple and fast image segmentation code using statistical region merging.

Description

From the paper :

Nock, Richard and Nielsen, Frank 2004. Statistical Region Merging. IEEE Trans. Pattern Anal. Mach. Intell. 26, 11 (Nov. 2004), 1452-1458.

It uses an a disjoint-sets data structure with a union-find strategy: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Just run srmdemo.m !

Matlab implementation, Mex File is TODO

• Required Products: Image Processing Toolbox
• MATLAB release: MATLAB 7.9 (2009b)

[ciaiaia ccccccc]

----------------
??? Subscripted assignment dimension mismatch.

Error in ==> srm at 107
im_final(:,:,i)=image_seg(map+(i-1)*n_pixels);
----------------
this algo works fine for some image, but other [and I dont know] it doesnt work

why?

[Sylvain Boltz]

Hi,

This algorithm is designed for images with 3 color channels.

for i=1:3
im_final(:,:,i)=image_seg(map+(i-1)*n_pixels);
end

if your image is black and white or has a different number of channels you should change all the hard coded 3 by size_image(3).

if this does not correct the problem, can you send me the image causing problems as well as the way you open it (e.g. image=double(imread(...))).

Thanks for your feedback

[Vincent Garcia]

Nice piece of work and nice paper.
The method is pretty simple but the results are very interesting.
The coding style is clear enough to be easily modified.
Thx for sharing you code.
V.

[Chuck]

Thanks for this - really nice. About the error brought up earlier. I had a couple images that caused the same error. Seems to be an issue with the im_final being re-sized on the fly? Not sure, but I got it working on those images by adding an

im_final = image

just prior to the final "for" loop.

Chuck

[create lei]

the cause of error mentioned by "ciaiaia ccccccc" is simple .

I believe he run the code sucessfully the first time and then he

changed the input image name ,and then run again without clear

the workspace .

it is easy to correct this problem

you could just add ''clear'' before the code . and then run this

code repeatedly as you want to test different images

[igor kolupaev]

Your work not only interesting - but helpful, thanks.

[rex]

when i first run srmdemo.m , MAT display error:

??? Attempted to access pairs1(0); index must be a positive integer or logical.

Error in ==> srm at 50
        C1=pairs1(index(i));

Error in ==> srmdemo at 8
[maps,images]=srm(image,Qlevels);

who knows this problem and fix it?

[zhouzhiyuan zhouzhiyuan]

when i first run srmdemo.m , Display error!
??? Error: File: srm.m Line: 27 Column: 3
Expression or statement is incorrect--possibly unbalanced (, {, or [.

who can fix this problem

[Sylvain Boltz]

Your matlab release is old, you should replace :

[~,index]=....
by
[trash,index]=....

I use the new command ~ that ignores useless argouts. If your matlab does not recognize it, just replace all the ~ by trash ( send argouts to a trash variable )

[Madhumitha]

Hi Sir,
      I ran thru ur coding...but how do I understand the concept on which it works...do iIneed to go thru any paper or study material...if so plz help me by mentioning it...(I could understand only the basic in what is given in wikipedia)

[Sylvain Boltz]

Hi, please refer to the following paper :

Nock, Richard and Nielsen, Frank 2004. Statistical Region Merging. IEEE Trans. Pattern Anal. Mach. Intell. 26, 11 (Nov. 2004), 1452-1458.

[worldguard Zhou]

??? Invalid MEX-file 'C:\Documents and
Settings\Administrator.92524BFB5303467\My
Documents\MATLAB\mydone2\srm\boundarygradient.mexw32':
because the configurement of application prgram is incorrect, application prgram doesn't start, resetuping application prgram might be right.
what shall I do ?

[worldguard Zhou]

My Matlab version 2008b,when I mex the two *.c file, there are so many errors that it is Unable to complete successfully.
Error: Compile of 'boundarygradient.c' failed

[Sylvain Boltz]

Hi,

The mex files given are from a cpp code.
If you want to compile them with a c compiler, you need to correct some minor symtax differences.
The main one is that you need to declare the variables on the top of the function and not through the program, e.g. avoid for {int i = 0....

I should fix this in a future release, thanks

[narendran]

help me with this error

??? Error: File: srm.m Line: 28 Column: 3
Expression or statement is incorrect--possibly unbalanced (, {, or [.

i have matlab 2007

[Karthik Muthuswamy]

Great piece of code. Thanks for sharing!

[Ahana]

Great work,but is there a way to do this in matlab without using the 'map' matrix,can you give some hint about this approach,thanks in advance

[Judit]

hello, I use matlab 7.0 and I have any problems with line 34 in srm_boundarylen, mwSize dims[2] = {nlabels,nlabels};, to solve it I change "mwSize" for "int" but it seems that initializer must be constant, however when I write mwSize dims[2] = {3,3} the figure 101 plots 9 identical imagenes , what is the problem? thanks

[t zq]

I met same problems as worldguard Zhou , and the mex error is shown as follows. I think it will help you to fix mex error.
>> mex srm_boundarylen.c
srm_boundarylen.c
srm_boundarylen.c(30) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(31) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(32) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(34) : error C2275: 'mwSize' : illegal use of this type as an expression
        d:\program files\matlab\r2006b\extern\include\tmwtypes.h(731) : see declaration of 'mwSize'
srm_boundarylen.c(34) : error C2146: syntax error : missing ';' before identifier 'dims'
srm_boundarylen.c(34) : error C2065: 'dims' : undeclared identifier
srm_boundarylen.c(34) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(34) : error C2059: syntax error : '{'
srm_boundarylen.c(35) : warning C4047: 'function' : 'const int *' differs in levels of indirection from 'int'
srm_boundarylen.c(35) : warning C4024: 'mxCreateNumericArray_700' : different types for formal and actual parameter 2
srm_boundarylen.c(37) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(38) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(40) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(41) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(41) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(41) : error C2143: syntax error : missing ')' before 'type'
srm_boundarylen.c(41) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(41) : error C2065: 'c' : undeclared identifier
srm_boundarylen.c(41) : error C2065: 'cols' : undeclared identifier
srm_boundarylen.c(41) : warning C4552: '<' : operator has no effect; expected operator with side-effect
srm_boundarylen.c(41) : error C2059: syntax error : ')'
srm_boundarylen.c(42) : error C2143: syntax error : missing ';' before 'for'
srm_boundarylen.c(42) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(42) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(42) : error C2143: syntax error : missing ')' before 'type'
srm_boundarylen.c(42) : error C2143: syntax error : missing ';' before 'type'
srm_boundarylen.c(42) : error C2065: 'r' : undeclared identifier
srm_boundarylen.c(42) : error C2065: 'rows' : undeclared identifier
srm_boundarylen.c(42) : warning C4552: '<' : operator has no effect; expected operator with side-effect
srm_boundarylen.c(42) : error C2059: syntax error : ')'
srm_boundarylen.c(43) : error C2143: syntax error : missing ';' before '{'
srm_boundarylen.c(46) : error C2065: 'map' : undeclared identifier
srm_boundarylen.c(46) : error C2065: 'i' : undeclared identifier
srm_boundarylen.c(46) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(47) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(50) : error C2065: 'neighbors' : undeclared identifier
srm_boundarylen.c(50) : error C2065: 'nlabels' : undeclared identifier
srm_boundarylen.c(50) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(51) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(56) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(57) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(60) : error C2109: subscript requires array or pointer type
srm_boundarylen.c(61) : error C2109: subscript requires array or pointer type
 
  D:\PROGRA~1\MATLAB\R2006B\BIN\MEX.PL: Error: Compile of 'srm_boundarylen.c' failed.
 
??? Error using ==> mex
Unable to complete successfully.

======================================
>> mex srm_boundarygradient.c
srm_boundarygradient.c
srm_boundarygradient.c(38) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(39) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(40) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(42) : error C2275: 'mwSize' : illegal use of this type as an expression
        d:\program files\matlab\r2006b\extern\include\tmwtypes.h(731) : see declaration of 'mwSize'
srm_boundarygradient.c(42) : error C2146: syntax error : missing ';' before identifier 'dims'
srm_boundarygradient.c(42) : error C2065: 'dims' : undeclared identifier
srm_boundarygradient.c(42) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(42) : error C2059: syntax error : '{'
srm_boundarygradient.c(43) : warning C4047: 'function' : 'const int *' differs in levels of indirection from 'int'
srm_boundarygradient.c(43) : warning C4024: 'mxCreateNumericArray_700' : different types for formal and actual parameter 2
srm_boundarygradient.c(45) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(46) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(47) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(49) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(50) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(50) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(50) : error C2143: syntax error : missing ')' before 'type'
srm_boundarygradient.c(50) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(50) : error C2065: 'c' : undeclared identifier
srm_boundarygradient.c(50) : error C2065: 'cols' : undeclared identifier
srm_boundarygradient.c(50) : warning C4552: '<' : operator has no effect; expected operator with side-effect
srm_boundarygradient.c(50) : error C2059: syntax error : ')'
srm_boundarygradient.c(51) : error C2143: syntax error : missing ';' before 'for'
srm_boundarygradient.c(51) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(51) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(51) : error C2143: syntax error : missing ')' before 'type'
srm_boundarygradient.c(51) : error C2143: syntax error : missing ';' before 'type'
srm_boundarygradient.c(51) : error C2065: 'r' : undeclared identifier
srm_boundarygradient.c(51) : error C2065: 'rows' : undeclared identifier
srm_boundarygradient.c(51) : warning C4552: '<' : operator has no effect; expected operator with side-effect
srm_boundarygradient.c(51) : error C2059: syntax error : ')'
srm_boundarygradient.c(52) : error C2143: syntax error : missing ';' before '{'
srm_boundarygradient.c(55) : error C2065: 'map' : undeclared identifier
srm_boundarygradient.c(55) : error C2065: 'i' : undeclared identifier
srm_boundarygradient.c(55) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(56) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(59) : error C2065: 'neighbors' : undeclared identifier
srm_boundarygradient.c(59) : error C2065: 'nlabels' : undeclared identifier
srm_boundarygradient.c(59) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(59) : error C2065: 'gradient' : undeclared identifier
srm_boundarygradient.c(59) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(60) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(60) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(65) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(66) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(69) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(69) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(70) : error C2109: subscript requires array or pointer type
srm_boundarygradient.c(70) : error C2109: subscript requires array or pointer type
 
  D:\PROGRA~1\MATLAB\R2006B\BIN\MEX.PL: Error: Compile of 'srm_boundarygradient.c' failed.
 
??? Error using ==> mex
Unable to complete successfully.

[Sylvain Boltz]

"I met same problems as worldguard Zhou", and I give you indeed the same answer : use a cpp compiler, not a c compiler.

[Pablo Sala]

 

[Nam Le]

Cool. This works perfectly for me. Thanks for this sharing!

[tonyan]

Hi,
This works very cool.
I don't kown the purpose of the following program

    while 1
        map_ = map(map) ;
        if isequal(map_,map) ; break ; end
        map = map_ ;
    end

Thanks very much

[Hugues]

@all with compiler issues: rename *.c to *.cxx if you do not know how to change your compiler.

@Sylvain: Nice piece of work.
But what is the purpose of the last 8 lines of code in srm.m function? Their results are not returned. In fact srm_boundarygradient.c can be ignored.

    bgradient = sparse(srm_boundarygradient(labels, nlabels, normgradient));
    bgradient = bgradient - tril(bgradient);
    idx=find(bgradient>0);
    [~,index]=sort(bgradient(idx));
    n_pairs=numel(idx);
    [xlabels,ylabels]=ind2sub([nlabels,nlabels],idx);
    pairs1=clusterlist(xlabels);
    pairs2=clusterlist(ylabels);

[Nitin Kumar]

 

[Diggs]

Am currently working on flood detection where am supposed to segment the two images , classify them independently and then later obtain a change image.am woundering how i can use to this same method to segment my images and how i can calculate mean for each segment in the image
and also when i try to run this code on my landsat image,it gives this error

??? Index exceeds matrix dimensions.

Error in ==> srm at 66
        dG=(image_seg(C1+n_pixels)-image_seg(C2+n_pixels))^2;

[reena]

works well.. thanks for sharing