Euclidean Distance Transform

[tpoisot]

DIstance gradients (#13) and a bunch of other are using the Euclidean Distance Transform from numpy (which is actually from Matlab). The two implementations in Julia that I found are in SignedDistanceFields (but it doesn't do what we want) and Images (but that's a lot of dependencies to add).

The solution is likely to write our own edt.

[mkborregaard]

@rafaqz had the same issue over at #11 where he also needed ImageMorphology.jl (which is the package that defines distance_transform).
I think adding a dep on ImageMorhpology makes sense - in general I think we use the image library less than it should be used for general 2d array manipulations. It adds like 20 transitive deps, but all solid org-owned ones.

[rafaqz]

Oops I just saw this issue. I found basically the same things as @tpoisot - ImageMorphology.jl has what we need - label_components and feature_distance - but it's a bit heavy. On the other hand I'm not sure I want to be responsible for owning separate versions of those methods...

The Images.jl ecosystem has a lot of great functionality that really doesn't need any of those dependencies - these algs are not necessarily color related at all. Ultimately ImageMorphology.jl should be split up, but when and by who... I had the same issue with DynamicGrids.jl, and just ended up writing everything I needed from scratch.

[mkborregaard]

Yeah it's the same deal with ImageFiltering.jl, which has all the best array filtering methods but then adds lots of color/image-specific deps. See e.g. JuliaImages/ImageFiltering.jl#42 and JuliaImages/ImageFiltering.jl#51
Anyway not much we can do about that here :-) I'll let @tpoisot decide but personally I'm not against the dep.

[rafaqz]

Yep. I've rewritten half of ImageFiltering.jl in DynamicGrids.jl. Eventually sharing that code would help them too - my windowing is much faster :)

But I put in an issue for ImageMorphology - most of the algorithms don't use the dependencies at all, or only in very minor ways.

[tpoisot]

I would probably go with NearestNeighbors, it seems that the nn function does what we want, and it's very light in terms of dependencies. I'll try something in #13 and see how it works out.

[tpoisot]

So it's not very pretty, but here is a thing that works:

S = (1000, 1000)
D = rand(Float64, S)
@time begin
    P = vcat(CartesianIndices(D)...)
    C = zeros(Float64, (2, length(P)))
    C[1,:] .= getindex.(P, 1)
    C[2,:] .= getindex.(P, 2)
    M = rand(1:prod(S), 100)
    T = KDTree(C);
    nn(T, C[:,rand(1:size(C, 2), 200)])
end;

The result

0.291581 seconds (3.00 M allocations: 217.714 MiB, 7.27% gc time)
([813785, 498369, 164606, 122782, 961793, 561119, 868932, 884673, 141612, 156354  …  501331, 73268, 975474, 38948, 261055, 855990, 91842, 414303, 928874, 874186], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])

Maybe for the time being this is a working solution?

[rafaqz]

Yeah, at least it's lightweight.

The beauty of the ImageMorphology.jl methods is they're a direct translation of the python, and I think easier to understand that KDTree.

I had this, unfinished:

function _landscape!(mat, alg::RandomClusterNearestNeighbor)
    # Create percolation array
    percolation = _classify(random(size(mat)), (1 - alg.p, alg.p))
    # As nan not supported in cluster algorithm replace with zeros (required ??)
    replace!(x -> isnan(x) ? zero(x) : x, percolation)
    # Define clusters 
    clusters = ImageMorphology.label_components(percolation, alg.neighbourhood)
    nclusters = maxium(clusters)
    # Create random set of values for each the clusters with zero for background
    cluster_values = cat([0.0], rand(nclusters))
    # Apply values by indexing by cluster
    cluster_array = custer_values[clusters]
    # Gap fill with nearest neighbour interpolation
    return _nearest_neighbor_interpolate(cluster_array, cluster_array .!= 0)
end

_nearest_neighbor_interpolate(A, mask) = A[ImageMorphology.feature_transform(mask)]

[tpoisot]

I've put on an illustration on #13 - this currently works using NearestNeighbors, in a way that I find a little bit awkward, but this can be a stopgap solution.

[rafaqz]

Ok great. Maybe I'll let you finish that then, I'll switch to PerlinNoise