Added Felzenszwalb's graph based segmentation

[tejus-gupta]

Graph based region merging algorithm described in this paper. It starts with a region adjacency graph and uses a greedy criterion to iteratively merge regions.

[tejus-gupta]

I have implemented the core function in felzenszwalb_graph which takes the region adjacency graph and threshold as input. It outputs the numbers of segments and index mapping for each node in input graph. I have added a felzenszwalb function that takes a grayscale image, creates the region adjacency graph, passes it to felzenszwalb_graph and returns output as SegmentedImage type. I will code similar helper function for color image and nearest neighbor graphs. I had to code my own version of disjoint sets(optimized using union-by-rank and path compression) because the standard version at DataStructures.jl didn't store size of the sets.

[tejus-gupta]

I am not sure about the input format for the region adjacency graph. Should I use Graph.jl's graph interfaces?

[codecov[bot]]

Codecov Report

Merging #4 into master will not change coverage. The diff coverage is 100%.

@@          Coverage Diff          @@
##           master     #4   +/-   ##
=====================================
  Coverage     100%   100%           
=====================================
  Files           2      3    +1     
  Lines         155    210   +55     
=====================================
+ Hits          155    210   +55

Impacted Files	Coverage Δ
src/felzenszwalb.jl	100% <100%> (ø)
src/core.jl	100% <100%> (ø)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 95bbddd...37c6dec. Read the comment docs.

[kmsquire]

I had to code my own version of disjoint sets(optimized using union-by-rank and path compression) because the standard version at DataStructures.jl didn't store size of the sets.

If your version has the same interface as the one in DataStructures.jl, how about making a pull request, so that others can use your optimized version?

[tejus-gupta]

My implementation uses the same optimizations as the one at DataStructures.jl for other operations but unlike their implementations, I can query set sizes efficiently. Maybe this was a design choice because users usually didn't need this feature and it will increase memory usage. I have made an issue at DataStructures.jl asking if they would like me to submit a pull request.

[tejus-gupta]

The code is a bit messy right now. I will clean it up tomorrow. Meanwhile I am looking for comments on the API.

1. Presently felzenszwalb_graph takes input Region Adjacency Graph(RAG) as edge list and number of vertices. I chose this representation simply due to coding simplicity as the algorithm naturally operates on this representation.

2. In the paper, they use two types of graphs - based on adjacency on image grid and based on adjacency in some joint(color+spatial) feature space. For the second type, people have experimented with different feature space, distance metric and possible ways to connect feature points with edges e.g, connect each point to fixed number of nearest neighbor, connect each point to all neighbors within some fixed distance. Since there are so many possible ways of mapping pixels to feature space and creating RAGs, I am not providing helper functions for using second type of RAGs with this algorithm. Users can directly use the felzenszwalb_graph function by creating the RAG themselves.

[timholy]

Sorry for the review delay here, JuliaCon was quite engrossing. For graphs, I recommend LightGraphs as the more actively-maintained package.

I'll start looking through your code now.

[timholy]

Oh, and to directly respond to your questions above:

• Yes, now that I've looked at your code I think your graph representation is fine. The one serious suggestion I have is to use the ImageEdge type instead of SVector.
• I really like how you've separated the graph from the image, and I think allowing users to construct the RAG manually is an excellent idea. Nice work!

[timholy]

Can you add 0.6 to .travis.yml and appveyor.yml? Looks like you have a test failure (see the logs). If you need help interpreting them just ask.

[timholy]

Great, very nice contribution @tejus-gupta!