Meanshift Segmentation

[tejus-gupta]

Image segmentation using mean-shift. This isn't ready but I have put it here for discussion. Right now it only works for Float grayscale images and takes very large amount of time.

Usage:

using Images, ImageSegmentation, ImageView, TestImages
img = testimage("cameraman")
img = convert(Array{Gray{Float64}}, img)

result = meanshift(img, 8.0, 7/255, 20)
imshow(result)

[tejus-gupta]

1. Benchmarking shows it uses ~100 GiB memory for 512X512 image. I don't think any step should be taking this much memory. The implementation here took about 27 sec for a 256*256 image and my implementation takes about 100 seconds.

2. After the mean-shift procedure has been run to get convergence point for each pixel, the exact method for separating wasn't mentioned. I am using clustering.jl's dbscan to group together nearby points. For clusters with points less that min_density, I assign the pixel to nearest cluster (with size>min_density).

[timholy]

I'm about to get on a plane. In case they board before I have a chance to take a look, when you see these kinds of things the usual answer is that you have some type instability. @profile, ProfileView, and @code_warntype are your friends here.

[timholy]

Also, I think creating an MVector allocates (unlike an SVector). They're calling my zone, so that's all for now.

[timholy]

Demo:

julia> function foo(n)
           s = zero(SVector{3,Float64})
           for i = 1:n
               s += rand(SVector{3,Float64})
           end
           s
       end
foo (generic function with 1 method)

julia> @time foo(10^4)
  0.191141 seconds (62.26 k allocations: 4.013 MiB)
3-element SVector{3,Float64}:
 4990.43
 4994.69
 4993.17

julia> @time foo(10^4)
  0.000081 seconds (6 allocations: 208 bytes)
3-element SVector{3,Float64}:
 5111.77
 5004.59
 5018.73

julia> function foom(n)
           s = zero(MVector{3,Float64})
           for i = 1:n
               s += rand(MVector{3,Float64})
           end
           s
       end
foom (generic function with 1 method)

julia> @time foom(10^4)
  0.068888 seconds (56.19 k allocations: 2.312 MiB)
3-element SVector{3,Float64}:
 5054.29
 4959.5 
 5028.45

julia> @time foom(10^4)
  0.000596 seconds (30.01 k allocations: 937.703 KiB)
3-element SVector{3,Float64}:
 5011.47
 4980.31
 4984.81

Julia & LLVM are very good about not allocating tuples on the heap, so the SVector doesn't use any memory and is several times faster.

[tejus-gupta]

Replacing MVector with SVector has resulted in 5x speedup. I can focus on improving the segmentation results now.

[tejus-gupta]

In the paper, they create clusters in the joint domain by grouping all convergence point such that they are closer than spatial_radius in the spatial domain and range_radius in the range domain i.e. |x1-x2|/spatial_radius< 1 and |y1-y2|/spatial_radius< 1 and |img[1]-img[2]|/range_radius< 1. The dbscan function groups points such that their euclidean distance is less than r while we really want to group points with chebyshev distance less than 1. To compensate for this, I have set r slightly greater than 1. I am not expecting this to have a large effect on the clustering. Any suggestions?

[timholy]

Seems like a reasonable strategy to me. Another option would be to allow an arbitrary Metric (from Distances.jl) as an input to dbscan. That might be more work, though, so it would be fine to try this and see whether you're happy.

[codecov[bot]]

Codecov Report

Merging #3 into master will increase coverage by 0.06%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master       #3      +/-   ##
==========================================
+ Coverage   99.32%   99.39%   +0.06%     
==========================================
  Files           7        8       +1     
  Lines         443      494      +51     
==========================================
+ Hits          440      491      +51     
  Misses          3        3

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

---

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 e9a5720...fc693e8. Read the comment docs.