Bug in seeded_region_growing causes crash

[MiriamHinzen]

...when the function is called for

img = Gray{N0f8}.([  
 0.475  0.412  0.443  0.475  0.702  0.714  0.667  0.443  0.404  0.353
 0.525  0.431  0.365  0.424  0.682  0.698  0.635  0.365  0.329  0.318
 0.561  0.553  0.545  0.463  0.643  0.663  0.58   0.275  0.251  0.259
 0.561  0.588  0.655  0.639  0.694  0.62   0.537  0.263  0.184  0.184
 0.463  0.584  0.639  0.635  0.655  0.584  0.482  0.267  0.169  0.169
 0.263  0.263  0.541  0.557  0.58   0.522  0.431  0.243  0.145  0.145
 0.239  0.231  0.239  0.38   0.443  0.467  0.376  0.224  0.118  0.122
 0.263  0.212  0.153  0.325  0.404  0.471  0.349  0.22   0.106  0.106
 0.255  0.208  0.133  0.333  0.416  0.482  0.345  0.224  0.098  0.169
 0.235  0.18   0.102  0.294  0.369  0.447  0.325  0.22   0.122  0.184 ])

seeds = [ (CartesianIndex(1,5),1), (CartesianIndex(8,9),2), (CartesianIndex(9,3),3) ]

seg = seeded_region_growing(img, seeds)

using Julia version 1.3.0-rc3 and ImageSegmentation v1.2.0 on Ubuntu 18.04.3 LTS.

Error message:

ArgumentError: PriorityQueue keys must be unique

Stacktrace:
[1] enqueue!(::DataStructures.PriorityQueue{DataStructures.Queue{CartesianIndex{2}},Float64,Base.Order.ForwardOrdering}, ::Pair{DataStructures.Queue{CartesianIndex{2}},Float64}) at /home/miriam/.julia/packages/DataStructures/RbN5c/src/priorityqueue.jl:236
[2] enqueue! at /home/miriam/.julia/packages/DataStructures/RbN5c/src/priorityqueue.jl:251 [inlined]
[3] seeded_region_growing(::Array{Gray{Normed{UInt8,8}},2}, ::Array{Tuple{CartesianIndex{2},Int64},1}, ::ImageSegmentation.var"#18#22"{CartesianIndex{2}}, ::typeof(ImageSegmentation.default_diff_fn)) at /home/miriam/.julia/packages/ImageSegmentation/KDHwp/src/region_growing.jl:142
[4] seeded_region_growing(::Array{Gray{Normed{UInt8,8}},2}, ::Array{Tuple{CartesianIndex{2},Int64},1}, ::Tuple{Int64,Int64}, ::Function) at /home/miriam/.julia/packages/ImageSegmentation/KDHwp/src/region_growing.jl:64
[5] seeded_region_growing at /home/miriam/.julia/packages/ImageSegmentation/KDHwp/src/region_growing.jl:57 [inlined] (repeats 2 times)
[6] top-level scope at In[23]:2

Analysis:
It can happen that nhq is exactly the same for several iterations. If the region means get updated in between the iterations, then in line 142 of region_growing.jl the same queue is tried to be enqueued into the priority queue again, which is not allowed.

Solution: use pq[q]=\delta instead of enqueue!(pq,q,\delta)
The priority queue allows for efficient updates of priorities for elements in the queue by using pq[q]=\delta instead of enqueue!(pq,q,\delta). This also renders checking the dictionary qdict redundant. With this functionality it also makes more sense to insert the pixels itself rather than queues of pixels into the priority queue. The priority queue becomes shorter this way and one avoids looping through a lot of already processed / labelled pixels again. Parallel processing of pixels with the same priority can still be achieved by looping through the priority queue until the lowest priority changes.

Pull request to resolve the issue is forthcoming.

[timholy]

Closed by #37