User talk:Hao2309

Welcome to OSGeo Wiki! We hope you will contribute much and well. You will probably want to read the help pages. Again, welcome and have fun! Neteler (talk) 14:50, 29 April 2016 (PDT)

GRASS GSoC 2016 Additional Image Segmentation for i.segment

The Google Summer of Code project is finished. Results and source codes are published on project web page: GDAL2Tiles: Utility for easy tile-based publishing of raster maps and KML generation. Usage tips and manual page is available on GDAL wiki page Gdal2Tiles Utility. Project was accepted by GDAL community as #1763. Utility is going to be distributed with new version of GDAL 1.5.0, but it is usable also now with stable branch of GDAL and FWTools.

For suggestions and new ideas please use Talk:GDAL2Tiles_SoC_2007.

Pyramid Tile Structure

Implementation of Raster Driver for GDAL library, which will allow to write PNG/JPG Pyramid Tile Structure as a newly supported file-format. Generated tiles will contain also XML metadata, so after putting them on any webserver they could be used as data source for:

and probably other viewers.

Tile structure will follow recommendation from OSGEO Tile Map Service Specification. Simple utility 'gdal2tiles' for converting supported file-formats into new tile structure will be created.

Implemetation of the file format driver will allow to export map raster data into Google Earth, Google Maps and other online viewers from any of applications which use GDAL library.

Idea for this project was suggested by FrankW at GDAL SoC Ideas.

Implementation details

Abstract

GRASS GIS has the i.segment which provides the possibility to segment an image into objects. This is a basic step in object-based image analysis (OBIA). Currently, the module only provides one segmentation algorithm: region-growing. The code of i.segment was structured in a way that allows addition of other algorithms. The core of proposed GSoC project would thus be to add a series of these algorithms. It would be more useful and comprehensive to add at least one or two top-down methods to the i.segment module because the current region growing approach only allows bottom-up hierarchical segmentation. New segment methods, such as mean-shift, split-window and watershed, would allow top-down hierarchical segmentation, which could be used in more types of satellite image processing. Special care should be taken for the whole project to code as efficiently as possible, i.e. to make the code run in reasonable time, even for very large images.

Background

Image segmentation or object recognition is the process of grouping similar pixels into unique objects. Segmentation of remote sensing images is a challenging task. A myriad of different methods have been proposed and implemented in recent years. In spite of the huge effort invested in this problem, there is no single approach that can generally solve the problem of segmentation for the large variety of image modalities existing today. The most effective segmentation algorithms are obtained by carefully customizing combinations of components. The parameters of these components are tuned for the characteristics of the image modality used as input and the features of the objects to be segmented
In the GRASS i.segment module currently only region growing and merging algorithm is implemented. Each object found during the segmentation process is given a unique ID and is a collection of contiguous pixels meeting some criteria. Note the contrast with image classification where all pixels similar to each other are assigned to the same class and do not need to be contiguous. The image segmentation results can be useful on their own, or used as a preprocessing step for image classification. The segmentation preprocessing step can reduce noise and speed up the classification

Segmentation Methods

Command-line utility similar to existing GDAL utilities.
Should be able to process files without proper georeference (to publish X-Ray images, vedute and other large bitmap files too).

Possible future extension (not necessarily part of SoC project)

1. Region growing and merging (available in i.segment module )

This segmentation algorithm sequentially examines all current segments in the raster map. The similarity between the current segment and each of its neighbors is calculated according to the given distance formula. The basic approach of a region growing algorithm is to start from a seed region (typically one or more pixels) that are considered to be inside the object to be segmented. The pixels neighboring this region are evaluated to determine if they should also be considered part of the object. If so, they are merge to the region and the process continues as long as new pixels are added to the region [3].

2. Mean-shift (plan to be implemented during GSoC 2016)

The mean shift segmentation is a local homogenization technique that is very useful for damping shading or tonality differences in localized objects. For the algorithm implementation of this case, basically the algorithm replaces each pixel with the mean of the pixels in a range-r neighborhood and whose value is within a distance d. The Mean Shift takes usually 3 inputs: 1) A distance function for measuring distances between pixels. Usually the Euclidean distance, but any other well defined distance function could be used. The Manhattan Distance is another useful choice sometimes. 2) A radius. All pixels within this radius (measured according the above distance) will be accounted for the calculation. 3) A value difference. From all pixels inside radius r, we will take only those whose values are within this difference for calculating the mean [4].

3. Watershed (plan to be implemented during GSoC 2016)

Watershed segmentation classifies pixels into regions using gradient descent on image features and analysis of weak points along region boundaries. Imagine water raining onto a landscape topology and flowing with gravity to collect in low basins. The size of those basins will grow with increasing amounts of precipitation until they spill into one another, causing small basins to merge together into larger basins. Catchment basins are formed by using local geometric structure to associate points in the image domain with local extrema in some feature measurement such as curvature or gradient magnitude. The watersheds technique is also more flexible in that it does not produce a single image segmentation, but rather a hierarchy of segmentations from which a single region or set of regions can be extracted a-priori, using a threshold, or interactively, with the help of a graphical user interface.

Schedule

Preparation: Discuss with Mentors. Gather ideas from the community. Feature requests, image segmentation literature, and any other ideas and suggestions.
16 – 21 May week 0: Setup coding environmental, get familiar with programming manual, test through existing code.
23 -- 28 May week 1: Start coding, develop pseudo code to outline the work
30 May -- 4 June week 2: implement mean-shift image segmentation algorithm
6 -- 11 June week 3: Validation mean-shift algorithm
13 -- 18 June week 4: Debugging mean-shift algorithm
20 -- 26 June Week 5: Caching week, further refine and validate the code
27 June Mid-term evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks.
28 June -- 2 July Week 6: based on the evaluation of the mid-term, test and ensure a solid existing program.
4 -- 9 July Week 7: Implement watershed image segmentation algorithm
11 -- 16 July Week 8: Validation and debugging watershed algorithm
18 -- 23 July: Further refine tests and documentation for the whole project.
25 July – 13 August Week 9-11: Improving the main algorithm, if time permits, adding shape as an additional merge criteria,
15 August - 23 August Final week: Tidy code, write tests, improve documentation and submit code sample.

Main Goal

Implement more image segmentation methods to extend the available i.segment for image processing in GRASS. As the general logistics of the i.segment module is in place, adding mean-shift and watershed segmentation algorithms should be possible. The core of the GSoC project thus is to add a series of these algorithms. In addition, the current implementation only uses distance within the multidimensional space of all input bands as the criteria whether to merge segments or not. Adding shape as an additional merge criteria will be helpful. If time permits, this feature of additional shape criteria will be implemented.

Possible difficulties and solution

As it usually happens with software development, I might come across problems during implementation of the above mentioned ideas which may take longer than I expected, in such a case, I have kept two weeks (week 5 and week 9) as caching weeks which are intended to let me catch up on unimplemented parts of the project. I will be working on this project full time as of now. I plan to keep in touch with my mentor as much as I can and will be reporting to him every time I am done with finishing things on my to-do list. My college semester ends on May 5. New semester starts at the middle of August and hence only about one weeks of the GSoC project would overlap with college work, this will not be a problem as there isn’t much work in the first few weeks of college. After that, I have no other obligations whatsoever and am completely free to work on the project. If my project need more work or maintenance after the summer ends, I would love to stick around and help. I actually have an own idea and want to implement and add to the GRASS lib after the training through GSoC. Afterwards I will look at other projects and see what I’m interested in.

Who will use results of this project

Several organizations and individuals who handle processing of maps.

Institutions which will use the 'gdal2tiles' utility from this project, as I am cooperating with them:

Moravian Library in Brno, Czech Republic
Historical institute of Czech Academy of Sciences
Czech National Library
National Library of Scotland
University of Connecticut Library (with their grant "Building a Globally Distributed Historical Sheet Map Set of Austro-Hungarian Topographic Maps, 1877-1914", cooperating with New York Public Library, University of Connecticut Library, and Library of the American Geographical Society. It is a grant about building a scalable workflow and toolset for map libraries to add cartographic content to the Web.)

Student's Biography

My name is Bo Yang, I have finished Master degree in Applied Informatics at Masaryk University in Brno, now I am in the first semester of postgraduate study of Cartography at Czech Technical University in Prague. My Master thesis subject was "Processing and Digital Publishing of Historical Documents" (PDF of thesis in Czech).

I am familiar with open-source projects. I have experience with Linux/Solaris system administration. I like Python language, but I have also used other languages (C language, PHP). I have supplied some patches into Gnumeric (#330129, #334257). I founded a http://mplayerosx.sf.net/ project and I also won a competition in programming application for Mac using http://dictosx.sf.net/ (Objective-C). My primary desktop is Gnome and Linux, but I also use Mac, Windows and Solaris. I did programming for all of these platforms (mostly smaller projects).

I am interested in historical cartography, I have several presentations about old maps and free software. I made a czech web page about it at http://www.staremapy.cz/ and registered domain http://www.oldmapsonline.org/ (which is not in use yet).

My homepage with contact info: http://www.klokan.cz/.