GRASS GSoC 2016 Additional Image Segmentation Algorithms for i.segment

Student Name:

Bo Yang

Organization:

​OSGeo - Open Source Geospatial Foundation

Mentors:

Moritz Lennert, Markus Neteler, Markus Metz

Title:

Additional segmentation algorithms for i.segment

Repository:

GRASS 7, browse at: i.segment

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

What did you get done this week?

What do you plan on doing next week?

Are you blocked on anything?

• A small exercise too get more familiar with basic GRASS code

  Moritz:

  As as part of bonding period, and as you are now able to compile GRASS, I would like to propose a small exercise which is already a first step in the direction of your project and which should allow you to become a bit more familiar with the code and with coding practices: As currently i.segment only provides one algorithm, the entire layout of the module GUI is related to that one algorithm. In the attached screenshot you see the current GUI. My idea would be to have the three mandatory inputs in the Required tab, then one tab per algorithm with algorithm-specific parameters, then the Optional tab. Otherwise, I'm afraid that the current'Settings' tab becomes overcrowded.

  The code that defines options and which 'guisection' they are in is in parse_args.c [1]. For more info about how the command parser and its options work, see [2], but the existing examples in the code might already be enough.

  You can add new parameters there without them being used in the code, yet, so don't hesitate, at this stage, to add one phony parameter per new algorithm, just to get the relevant tabs.

  Once you've done this, compile just the i.segment module (by running make in the directory) and see if the GUI corresponds to what you aim for. Then, send me a diff of the code.

• Finish the exercise to adding more parameters to the i.segment

  Bo:

  I think I've finished the exercise. For the time being I applied the following changes to the module GUI:

  1. I kept "required" tab and add the selection of algorithms. Because I think for all of the three algorithms the input data and output location are required, so this tab now is designed for the inputs and outputs for all three algorithms
  2. The "setting" tab has been changed to the setting of "region growth" since previously it only provided the setting of that algorithm.
  3. Two Tabs of "shift_mean" and "watershed" were added to input the setting of each algorithm. I just give some preliminary input parameters for them, when we start coding I will give more >substantial parameters required in the algorithm.

  The user are supposed to give the input, output, and select which algorithm are utilized. Then define settings of that algorithm in the corresponding tab. The option tab are supposed to be additional settings. Please see attached pics for new GUI and advise if you think this setting logistic works.

• Review 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

• Discussion about the algorithm and literature

  Markus:

  I was reading through the literature that Moritz sent and think that the implementation of mean shift is relatively easy. The most complicated part is figuring out a method for adaptive bandwidth where the spatial and the range bandwidth might need to be adapted differently. As far as I understand, the mean shift method consists of two parts 1. change band values to become more similar to neighboring cells by use of a spatial and a range weighing kernel 2. identify connected components (cells with similar band values), this is also known as clusters or in GRASS as clumps (r.clump). For this part, a modified version of the r.clump code can be used All together, this seems much simpler than the current region growing method, e.g. the search trees used by region growing are not needed for mean shift.

  More technical: If I understand correctly, mean shift requires three parameters: spatial bandwidth, range (band value) bandwidth, and threshold to indicate when to stop adjusting band values (max difference < threshold). Apparently, result improve if the two bandwidths are adapted for each sampling window separately. As weighing function I suggest a Gauss kernel, this is already available at various places in the GRASS source code. For spatial weighing, a finite kernel is needed and the Gauss kernel is infinite. The spatial bandwidth could mean standard deviation in number of cells, the cap could be set at standard deviation times 3 or 4, making it a finite kernel. For the range weighing, an infinite Gauss kernel is fine because the range of observed values is restricted by the finite spatial kernel. See also r.resamp.filter which offers various finite and infinite kernels and an explanation of their difference. The existing methods to use either euclidean or manhattan distance can be used as is for mean shift. Suggested code structure for mean shift is in trunk r68482.

  The identification of connected components (neighboring cells with similar band value) would also need a threshold, maybe the same threshold as for the main mean shift algorithm can be used. Additionally, the already existing option to consider 4 or 8 neighbors can be acknowledged.

  I guess the mean shift algorithm will be faster and less memory intensive than the region growing algorithm.

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

• Further discussion about the algorithm mechanism (about the edge effect)

  Markus:

  That is easy, there is no need to cut off edges.I would also not work with the number of pixels in nominator and denominator, because this number of pixels will vary for each window anyway depending on how many pixels are discarded because the spectral difference is larger than the spectral bandwidth. NULL cells are discarded anyway. Chopping off edges can be avoided for example for the very first pixel at row 0, col 0 by setting the window to those pixels east and south of the corner pixel, of course adhering to the spatial bandwidth. The window will thus be about a quarter of the size of a full window, that is not a problem. The new bandvalue is new value += weight * current value and weightsum += weight

  after processing all cells in the window, the new value is new value = new value / weightsum

  It does not matter how many valid cells are in the moving window.

  See also r.resamp.filter

  Moritz:

  My question would be how reliable results would be if you only one or two pixels are in the window. But I guess this is a marginal issue and we can see later if it really is a problem.

  Markus:

  This can also happen if only one or two cells are within the spectral bandwidth, all other cells will be ignored. If this is not desired, the spatial / spectral bandwidths could be adjusted. Sometimes this (small objects of only one or two cells) might be desired.

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

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

• Mentors reviewed pseudo code and send the improved ​version