Skip to content

GSoC 2014 : Graph based segmentation algorithms ( not updated )

Jump to bottom Edit New page
vighneshbirodkar edited this page Mar 21, 2014 · 1 revision

###Title Region adjacency graphs and graph based segmentation algorithms

###Abstract To implement Region adjacency graphs and graph based image segmentation algorithms. Initially I will be implementing graph primitives which will be useful for region adjacency graph based and other segmentation algorithms. Graphs will be implemented using numpy arrays to take advantage of scipy.sparse.cs_graph . Later I will implement segmentation algorithms using the primitives defined.

###Details I would like implement the algorithms 1,2,and 3, along with the primitives required.1 and 3 model each pixel as a vertex in a graph, and will use similar approaches to convert an image into a graph and use the modified graph to segment the image. 2 models each region as a vertex and will depend on watershed for its pre-segmentation.

Algorithm 1

  • This models each pixel as a vertex in a graph with edges between neighboring pixels
  • This requires disjoint set data structures as described in 4 to compute if pixels are part of the same region during the intermediate stages

Algorithm 2

  • Pre-segmented image will be taken for watershed method
  • The region adjacency graph of the pre-segmented image needs to be computed
  • It will then prune the regions based on the region adjacency graph

Algorithm 3

  • This models each pixel as a vertex with an edge between every two vertices
  • To compute the eigenvalues and eigenvectors in an intermediate step it suggests Lanczos method from 5

Timeline

March 21 - April 21 ( Interim Period )

  • Get to know scikit-image better
  • Fix bugs
  • Implement new features

21 April - 18 May ( Community Bonding Period )

  • Discuss the algorithms to be implemented with mentors
  • Understand the Segmentation and Graph algorithms required

19 May - 5 June

  • Figure out the graph API
  • Implement functions required to transform image to a graph
  • Implement functions required to label an image, given its graph ( modified by a suitable algorithm )
  • Work towards creating an example which segments an image by thresholding edge weights

6 June - 24 June

  • Implement disjoint set data structures
  • Implement Algorithm 1
  • Write test cases

25 June - 26 June

  • Examples

27 June - 17 July

  • Use code from 6 wherever possible
  • Implement Algorithm 3
  • Write test-cases
  • Use scipy.sparse.linalg.eigsh to compute required eigenvalues and eigenvectors

18 July - 8 August

  • Implement region adjacency graphs
  • Implement Algorithm 2
  • Write test-cases

9 August - 11 August

  • Examples for 2 and 3
  • IPython notebook demonstrating all graph based segmentation algorithms.

12 August - 22 August

  • Buffer Period

References

  1. [Efficient Graph Based Image Segmentation] (http://www.cs.cornell.edu/~dph/papers/seg-ijcv.pdf)
  2. [Regions adjacency graph applied to color image segmentation] (http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=841950&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D841950)
  3. [Normalized Cuts and Image Segmentation] (http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf)
  4. [Disjoint-set data structure] (http://en.wikipedia.org/wiki/Disjoint-set_data_structure)
  5. [Matrix Computations.John Hopkins Press, 1989] (http://www.cs.cornell.edu/cv/GVL4/golubandvanloan.htm)
  6. [N-Cut Pull Request] (https://github.com/scikit-image/scikit-image/pull/397/files)

Patches submitted

Additional Information

Add a custom footer
Add a custom sidebar
Clone this wiki locally