GRASS GSoC 2016 Additional Image Segmentation Algorithms for i.segment

Student Name:

Bo Yang

Organization:

​OSGeo - Open Source Geospatial Foundation

Mentors:

Moritz Lennert, Markus Metz

Title:

​Additional segmentation algorithms for i.segment

Repository:

GRASS 7, browse at: ​i.segment sandbox

16 – 21 May week 0: Setup coding environmental, get familiar with programming manual

What did you get done this week?

• Finished a small exercise to get more familiar with basic GRASS codes

Currently i.segment only provides region-growth algorithm. By modifying ​parse_args.c I added three inputs for additional two algorithms, mean-shift and watershed, respectively.

• Reviewed some literature for mean-shift algorithm

1. Deng, C., Li, S., Bian, F., & Yang, Y. (2015). Remote Sensing Image Segmentation Based on Mean, (1999), 179–185.
2. Michel, J., Youssefi, D., & Grizonnet, M. (2015). Stable mean-shift algorithm and its application to the segmentation of arbitrarily large remote sensing images. IEEE Transactions on Geoscience and Remote Sensing, 53(2), 952–964. ​http://doi.org/10.1109/TGRS.2014.2330857
3. Zhang, Q., Liu, C., Zhang, G., & Zhou, A. (2014). Adaptive image segmentation by using mean-shift and evolutionary optimisation. IET Image Processing, 8(6), 327–333. ​http://doi.org/10.1049/iet-ipr.2013.0195
4. Zhou, J.-X., Li, Z.-W., & Fan, C. (2015). Improved fast mean shift algorithm for remote sensing image segmentation. IET Image Processing, 9(5), 389–394. ​http://doi.org/10.1049/iet-ipr.2014.0393

• Some discussions with mentors about the algorithm and literature

What do you plan on doing next week?

• Make clear understanding about the algorithm mechanism and write the pseudo codes for prototyping.

Are you blocked on anything?

• Some issues happened during the compiling of the GRASS in Windows environmental. With the help fromcommunity, ​the problem has been later solved.

23 - 28 May week 1: Start coding, develop pseudo-code to outline the work

What did you get done this week?

• Further discussion about the algorithm mechanism

1. Edge effect:

Moving window have to be re-sized when it near the edge or corner of the full image. Mentor has given the solution in pseudo-code:

      # figure out moving window, clip to region if necessary
      mwrow1 = row - (int)radius
      mwrow2 = mwrow1 + window_size
      if (mwrow1 < 0)
        mwrow1 = 0
      if (mwrow2 > nrows)
        mwrow2 = nrows
      
      mwcol1 = col - (int)radius
      mwcol2 = mwcol1 + window_size
      if (mwcol1 < 0)
        mwcol1 = 0
      if (mwcol2 > ncols)
        mwcol2 = ncols

2. Adaptive bandwidth:

Earlier mean-shift algorithm uses fixed bandwidth. Fixed bandwidth could result in either over-segment or under-segment. In the literature of Deng et al., 2015 and ​Zhang et al., 2014, each paper proposed an adaptive bandwidth method. ​Zhou et al., 2015 proposed another method, which use smaller bandwidth at first to over-segment the image, then use image clustering and region-based mode merging again to refine the result.

3. The convergence condition:

Set an epsilon value, e.g. 0.001. If the pixel value difference is less than epsilon between iterations, the pixel is considered as convergent.

• Got the access for GRASS-addons-svn and ​sandbox

• Wrote the ​pseudo-code for the mean-shift algorithm

• Mentors reviewed pseudo-code and send the improved ​version

What do you plan on doing next week?

• Write the meanshift.c module to implement the mean-shift algorithm based on pseudo-code. Codes will be implemented based on the essential functions of mean-shift algorithm. The fixed bandwidth and rangewidth will be used and codes need to be implemented to separate objects (super-pixel).

Are you blocked on anything?

• Not for now

30 May -- 4 June week 2: implement mean-shift image segmentation algorithm

What did you get done this week?

• Implemented the basic mean-shift.c algorithm in ​sandbox according to the pseudo-code.

What do you plan on doing next week?

• integrate the current basci mean-shift C codes to i.segment, make the mean-shift algorithm can be run using the GUI and command line, rather than stand-alone program.

1. add the new options to parse_args.c
2. implement mean shift in mean_shift.c
3. write out shifted band values
4. implement identification of connected components (objects) using the clump_n() function in r.clump/clump.c as template
5. write out object ids just like for region growing (the code exists already in write_output.c)
6. implement a minimum size for objects: objects smaller than minsize must be merged with some adjacent object

Are you blocked on anything?