== GRASS GSoC 2016 Additional Image Segmentation Algorithms for i.segment == || Student Name: || Bo Yang |||| Organization: || [http://www.osgeo.org/ OSGeo - Open Source Geospatial Foundation] |||| Mentors: || Moritz Lennert, Markus Metz |||| Title: || [https://trac.osgeo.org/grass/wiki/GSoC/2016/Additional_segmentation_algorithms Additional segmentation algorithms for i.segment] |||| Repository: || GRASS 7, browse at: [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016 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 [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/parse_args.c 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, [https://lists.osgeo.org/pipermail/grass-dev/2016-May/080332.html 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: {{{#!c # 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 [http://doi.org/10.1049/iet-ipr.2013.0195 Zhang et al., 2014], each paper proposed an adaptive bandwidth method. [http://doi.org/10.1049/iet-ipr.2014.0393 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 [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016 sandbox] * Wrote the [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/MeanShift_pseudo_yb pseudo-code] for the mean-shift algorithm * Mentors reviewed pseudo-code and send the improved [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/MeanShift_pseudo_2016_05_25_MM 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 [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/mean_shift_2016_05_30_yb.c sandbox] according to the pseudo-code. [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/testing/test_map.ascii A 8x8 ascii raster] from stackoverflow have been used for testing the mean-shift.c basic algorithm, the original image: {{{ 103 103 103 103 103 103 106 104 103 147 147 153 147 156 153 104 107 153 153 153 153 153 153 107 103 153 147 96 98 153 153 104 107 156 153 97 96 147 153 107 103 153 153 147 156 153 153 101 103 156 153 147 147 153 153 104 103 103 107 104 103 106 103 107 }}} after the mean-shift iterations: {{{ 103.99 104.00 104.01 104.04 104.07 104.11 104.15 104.20 104.00 151.86 151.86 151.87 151.88 151.89 151.89 104.24 104.01 151.86 151.86 151.87 151.88 151.89 151.90 104.28 104.03 151.85 151.86 96.75 96.75 151.90 151.90 104.31 104.06 151.85 151.86 96.75 96.75 151.89 151.90 104.34 104.09 151.85 151.86 151.87 151.88 151.89 151.89 104.36 104.13 151.86 151.86 151.87 151.88 151.89 151.89 104.36 104.17 104.20 104.24 104.28 104.31 104.33 104.35 104.36 }}} segmentation image with object ID: {{{ 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 2.00 2.00 2.00 2.00 2.00 2.00 1.00 1.00 2.00 2.00 2.00 2.00 2.00 2.00 1.00 1.00 2.00 2.00 3.00 3.00 2.00 2.00 1.00 1.00 2.00 2.00 3.00 3.00 2.00 2.00 1.00 1.00 2.00 2.00 2.00 2.00 2.00 2.00 1.00 1.00 2.00 2.00 2.00 2.00 2.00 2.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 }}} * Since the stand-alone codes works, now I am integrating it to current i.segment module. 1. Added parameters (spatial_bandwidth,ms_range_bandwidth and ms_suffix) to both [https://trac.osgeo.org/grass/browser/grass/trunk/imagery/i.segment/parse_args.c parse_args.c] and [https://trac.osgeo.org/grass/browser/grass/trunk/imagery/i.segment/iseg.h iseg.h] to integrate algorithm to current i.segment. 2. (Ongoing) Based on mentors' template [https://trac.osgeo.org/grass/browser/grass/trunk/imagery/i.segment/mean_shift.c mean_shift.c] fill in the codes to implement the algorithm. === What do you plan on doing next week? === * Integrate the current basic mean-shift C codes to i.segment, make the mean-shift algorithm run using the GUI and command line, rather than stand-alone program. 1. Implement the mean-shift algorithm iteration part. 2. Refer to the r.clump/clump.c to implement the object segmentation part. 3. Merger the smaller super-pixels to adjacent super-pixel which under the threshold and write to the output band. === Are you blocked on anything? === * Not for now == 4 June -- 11 June week 3: implement mean-shift image segmentation algorithm == === What did you get done this week? === * Implement the mean-shift algorithm iteration part [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/mean_shift.c mean-shift]. === What do you plan on doing next week? === * Previously there are 3 tasks planning for the past week, because of the unexpected debugging time only first task finished for this week, I will try to finish the following two tasks in the next week. 1. Refer to the r.clump/clump.c to implement the object segmentation part. 2. Merger the smaller super-pixels to adjacent super-pixel which under the threshold and write to the output === Are you blocked on anything? === * Two parameters could not pass from parse_args.c to mean_shift.c, both get zero value. {{{#!c globals->ms_spatial_bandwidth and globals-> ms_range_bandwidth }}} * There is a random appeared bug, even successfully complied, I use the following command to run the codes: {{{ i.group group=singleband_yb input=lsat7_2000_80 g.region raster=lsat7_2000_80 -p i.segment --o group=singleband_yb threshold=0.5 output=testout_ms_yb3 method=mean_shift }}} Sometimes it can output normally to console, but sometimes the output doesn't make sense. Two cases are random appeared and the ratio is about 1:1. I didn't change anything between running. I tried using that 8x8 image chip (import as raster) and the same thing happened. == 12 June -- 19 June week 4: == === What did you get done this week? === * Implement the object segmentation part in [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/mean_shift.c mean_shift.c] * Parameters passing issue and that random bug in last week has been fixed. * Write a new function in [https://trac.osgeo.org/grass/browser/sandbox/bo/i.segment.gsoc2016/i.segment/write_output.c write_output.c] to save the shift value bands. === What do you plan on doing next week? === * Further test the clustering function. * Debugging the whole program, check the base of the codes make sure everything is write correctly. === Are you blocked on anything? === * Clustering function works for the 8x8 test image, for the Landsat pan image (grass default data lsat7_2000_80) it can only clump highlight spots. I think some parameters need to be adjusted. == 19 June -- 26 June week 5: == === What did you get done this week? === * Implemented the shifted multi-bands write to output part. 1. Write the as many output bands as input bands. 2. Write the output bands use the same color table as input bands. 3. Add suffix to each output bands based on the input bands name. * Checking and debugging, fixed some errors. === What do you plan on doing next week? === * Further test the clustering function. * Re-write the clustering function in mean_shift.c part based on r.clump. * Write the (pseudo)codes about the function which smaller super-pixel merge into bigger super-pixel. === Are you blocked on anything? === * Write the codes about clustering function in mean_shift.c got a little hard. I tried to follow the logistic of r.clump but the output result doesn't make sense. == 27 June -- 10 July week 6-7: ==