# Find neighbored segments/labels in Matrix

**URL:** <https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151>\
**Category:** General Usage\
**Tags:** images, array\
**Created:** [July 6, 2021, 2:42pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151 "2021-07-06T14:42:15Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Bjorn\_De](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bjorn_de/32/13174_2.png) [@Bjorn\_De](https://discourse.julialang.org/u/Bjorn_De)\
**Post date:** [July 6, 2021, 2:42pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/1 "2021-07-06T14:42:15Z")

</div>

Hi all!  
I have applied a segmentation on an array and want to find the neighbors of each segment.  
For example:

```julia
Input:
4×6 Matrix{Int64}:
1 1 1 2 2 2
1 1 5 5 4 4
7 7 3 3 3 3
9 9 9 9 8 8

Output:
Dict{Int64, Matrix{Int64}} with 8 entries:
 5 => [1 2 … 7 3]
 4 => [2 5 3]
 7 => [1 5 3 9]
 2 => [1 5 4]
 9 => [7 3 8]
 8 => [3 9]
 3 => [5 4 … 8 9]
 1 => [2 5 7 3]

```

I’ve tried `region_adjacent_graph` function of the ImageSegmentation.jl package which does what I need but it takes 20 minutes for a 10000x10000 Matrix with ~15000 segments.  
Any ideas how to get the neighbors faster?  
Bjoern

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [July 6, 2021, 3:11pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/2 "2021-07-06T15:11:36Z")

</div>

Is each segment always contained in a row? I know nothing about this field, but my guess is that it would be easy to hand-craft a faster algorithm for your particular use-case.

---

<div class="post-metadata">

**Author:** ![Bjorn\_De](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bjorn_de/32/13174_2.png) [@Bjorn\_De](https://discourse.julialang.org/u/Bjorn_De)\
**Post date:** [July 6, 2021, 3:17pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/3 "2021-07-06T15:17:06Z")

</div>

No, segments could also be over several rows.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [July 6, 2021, 3:18pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/4 "2021-07-06T15:18:02Z")

</div>

And are the values in the matrix always numbers between `1` and `n` when there are `n` segments?

---

<div class="post-metadata">

**Author:** ![Bjorn\_De](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bjorn_de/32/13174_2.png) [@Bjorn\_De](https://discourse.julialang.org/u/Bjorn_De)\
**Post date:** [July 6, 2021, 3:18pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/5 "2021-07-06T15:18:50Z")

</div>

yes

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [July 6, 2021, 3:43pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/6 "2021-07-06T15:43:56Z")

</div>

Here’s a simple implementation, let me know how it works 🙂

```julia
function find_neighbors(A; nsegments=maximum(A))
    # These two should be compared to see which one performs better:
    flags = zeros(Bool, nsegments, nsegments)
    #flags = falses(nsegments, nsegments) # Uses a BitArray instead of an array of Bool
    
    indices = CartesianIndices(A)
    neighbors = CartesianIndex(-1, -1):CartesianIndex(1, 1)
    for I in indices
        for N in neighbors
            if I+N in indices
                flags[A[I+N], A[I]] = true
            end
        end
    end

    # Unset diagonal elements since a segment is not neighbor of itself
    flags[diagind(flags)] .= false

    return Dict(seg => findall(col) for (seg, col) in enumerate(eachcol(flags)))
end

```

---

<div class="post-metadata">

**Author:** ![Bjorn\_De](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bjorn_de/32/13174_2.png) [@Bjorn\_De](https://discourse.julialang.org/u/Bjorn_De)\
**Post date:** [July 6, 2021, 3:52pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/7 "2021-07-06T15:52:36Z")

</div>

Thanks a lot @sijo. Your function works pretty well and fast, just 2 seconds on the big array.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [July 6, 2021, 6:18pm UTC](https://discourse.julialang.org/t/find-neighbored-segments-labels-in-matrix/64151/8 "2021-07-06T18:18:18Z")

</div>

By the way, with just one line changed the function will work for arrays of any dimension:

```julia
julia> function find_neighbors(A; nsegments=maximum(A))
           # These two should be compared to see which one performs better:
           flags = zeros(Bool, nsegments, nsegments)
           #flags = falses(nsegments, nsegments) # Uses a BitArray instead of an array of Bool
           
           indices = CartesianIndices(A)
           neighbors = -oneunit(indices[1]):oneunit(indices[1]) # ← this line changed
           for I in indices
               for N in neighbors
                   if I+N in indices
                       flags[A[I+N], A[I]] = true
                   end
               end
           end

           # Unset diagonal elements since a segment is not neighbor of itself
           flags[diagind(flags)] .= false

           return Dict(seg => findall(col) for (seg, col) in enumerate(eachcol(flags)))
       end
find_neighbors (generic function with 1 method)

julia> A = [1 2 3
            1 1 3
            4 4 4;;;
            
            1 2 3
            1 3 3
            1 5 5]
3×3×2 Array{Int64, 3}:
[:, :, 1] =
 1 2 3
 1 1 3
 4 4 4

[:, :, 2] =
 1 2 3
 1 3 3
 1 5 5

julia> find_neighbors(A)
Dict{Int64, Vector{Int64}} with 5 entries:
  5 => [1, 3, 4]
  4 => [1, 3, 5]
  2 => [1, 3]
  3 => [1, 2, 4, 5]
  1 => [2, 3, 4, 5]

```

Isn’t this cool? (yeah I know it’s just a rehash of [that one](https://discourse.julialang.org/t/seven-lines-of-julia-examples-sought/50416/48) 🙂 )