Документация Engee

Структурирующий элемент

Структурирующий элемент (СЭ) — ключевое понятие в морфологии, указывающее на связность и соседство. На этой странице объясняется концепция структурирующего элемента и то, как в ImageMorphology поддерживаются общие СЭ без снижения производительности в наиболее частых особых случаях их использования.

Пример эрозии

Функцию эрозии erode в простейшем одномерном случае можно определить так:

Поскольку выходное значение в позиции зависит не только от собственного пикселя A[p], но и от его соседних значений A[p-1] и A[p+1], такая операция называется преобразованием окрестности изображения.

Возникает вопрос: что делать, если нужно обобщить функцию erode? Следует обобщить понятие «окрестность».

Два представления окрестности

Утверждение «$\Omega_p$ является окрестностью » можно выразить в виде обычного кода Julia как p in Ωₚ. Для повышения производительности Ωₚ обычно генерируется из пары (p, Ω). p — это центральная точка, которая изменяется во время итерации, а Ω — это обычно предопределенные и неизменные данные, которые содержат информацию об окрестности и форме. Это Ω называется структурирующим элементом. Ω обычно выражается двумя способами:

  • смещение: список объектов CartesianIndex, определяющий смещение относительно центральной точки p;

  • маска связи: маска в виде массива логических значений, определяющая связь с центральной точкой p.

Например, в следующем блоке кода создается связь C4 для двухмерного случая:

# смещение
Ω_offsets = [
    CartesianIndex(-1, 0),
    CartesianIndex(0, -1),
    CartesianIndex(0, 1),
    CartesianIndex(1, 0),
]

# маска связи
Ω_bool = Bool[
    0 1 0
    1 1 1
    0 1 0
]

Если p=CartesianIndex(3, 3), то известно, что p=CartesianIndex(3, 4) находится в Ωₚ.

Вернемся к примеру эрозии. На основе представления в виде смещения довольно легко реализовать простейшую универсальную версию erode:

# Только для иллюстрации; производительность можно значительно повысить, используя итерацию, чтобы не выделять лишнюю память
function my_erode(A, Ω)
    out = similar(A)
    R = CartesianIndices(A)
    for p in R
        Ωₚ = filter!(q->in(q, R), Ref(p) .+ Ω)
        # здесь не предполагается, что p входит в Ωₚ
        out[p] = min(A[p], minimum(A[Ωₚ]))
    end
    return out
end
using ImageMorphology
using ImageBase
using TestImages

img = Gray.(testimage("morphology_test_512"))
img = Gray.(img .< 0.8)
img_e = my_erode(img, Ω_offsets)
mosaic(img, img_e; nrow=1)
C2JsMwvK3JMAxvazIMw9uaDMPwtibDMLytyTAMb2syDMNPiLWoPbEW9Rsmw0+JWag9MQs1vLLYSu3EVuoXTIZheFuT4afUITW8hcaH+tT4UL9hMgzDT6hD6ldNhmF4W5NhGN7WZBiGtzUZhuFtTYZheFuTYRje1mQYhrc1GYbhbf0DTK4jQSP9xy8AAAAASUVORK5C

Как вы, возможно, уже поняли, представление в виде смещения удобно использовать при реализации алгоритмов, но сложно визуализировать. Напротив, представление в виде маски связи не так удобно использовать при реализации алгоритмов, но легко визуализировать. Например, такой СЭ очень легко понять с первого взгляда:

3×3 Matrix{Bool}:
 1  1  1
 1  1  0
 0  0  0

Но не такой:

4-element Vector{CartesianIndex{2}}:
 CartesianIndex(-1, -1)
 CartesianIndex(0, -1)
 CartesianIndex(-1, 0)
 CartesianIndex(-1, 1)

Функция strel

Этот пакет поддерживает преобразование между различными представлениями СЭ с помощью вспомогательной функции strel. strel — это сокращение от STRucturing ELement (структурирующий элемент).

Преобразовать представление в виде маски связи в представление в виде смещения можно так:

Ω_mask = Bool[1 1 1; 1 1 0; 0 0 0] |> centered
Ω_offsets = strel(CartesianIndex, Ω_mask)
4-element Vector{CartesianIndex{2}}:
 CartesianIndex(-1, -1)
 CartesianIndex(0, -1)
 CartesianIndex(-1, 0)
 CartesianIndex(-1, 1)

Предполагается, что массив маски отцентрирован относительно нуля. Это означает, что оси маски размером 3×3 axes(se) должны быть (-1:1, -1:1). Функция centered служит для смещения центральной точки массива в (0, 0, ..., 0).

julia> A = centered([1 2 3; 4 5 6; 7 8 9])
3×3 OffsetArray(::Matrix{Int64}, -1:1, -1:1) with eltype Int64 with indices -1:1×-1:1:
 1  2  3
 4  5  6
 7  8  9

julia> A[-1, -1], A[0, 0], A[1, 1] # левый верхний угол, центр, правый нижний угол
(1, 5, 9)

Функция centered входит в пакет OffsetArrays.jl

и также экспортируется вместе с пакетом ImageMorphology.

Преобразовать представление в виде смещения обратно в представление в виде маски связи можно так:

strel(Bool, Ω_offsets)
3×3 OffsetArray(::BitMatrix, -1:1, -1:1) with eltype Bool with indices -1:1×-1:1:
 1  1  1
 1  1  0
 0  0  0

Совсем не сложно, да? Таким образом, чтобы сделать функцию my_erode более универсальной, достаточно добавить всего одну строку:

 function my_erode(A, Ω)
     out = similar(A)
+    Ω = strel(CartesianIndex, Ω)
     R = CartesianIndices(A)

Симметричность

Из всех структурирующих элементов на практике чаще всего используются симметричные — они обладают лучшими свойствами, а их симметрия позволяет определенным образом оптимизировать реализацию.

Для представления в виде маски mask = strel(Bool, se) симметричность СЭ определяется относительно центральной точки: se симметричен, если условие mask[I] == mask[-I] соблюдается для I ∈ CartesianIndices(mask). По этой же причине представление в виде маски требует массива centered.

se = centered(Bool[
    1 0 1
    0 1 0
    1 0 1
])
ImageMorphology.is_symmetric(se) # true

se = centered(Bool[
    1 1 1
    0 1 0
    1 0 1
])
ImageMorphology.is_symmetric(se) # false

se = [CartesianIndex(1), CartesianIndex(-1)]
ImageMorphology.is_symmetric(se) # true

se = [CartesianIndex(1)]
ImageMorphology.is_symmetric(se) # false

Удобные конструкторы

Помимо прочих возможностей СЭ, этот пакет предоставляет конструкторы для двух распространенных случаев:

  • конструктор СЭ ромбовидной формы strel_diamond;

  • конструктор СЭ прямоугольной формы strel_box.

julia> strel_diamond((3, 3)) # смежные элементы: связь C4
3×3 ImageMorphology.StructuringElements.SEDiamondArray{2, 2, UnitRange{Int64}, 0} with indices -1:1×-1:1:
 0  1  0
 1  1  1
 0  1  0

julia> strel_diamond((3, 3), (1, )) # по первому измерению
3×3 ImageMorphology.StructuringElements.SEDiamondArray{2, 1, UnitRange{Int64}, 1} with indices -1:1×-1:1:
 0  1  0
 0  1  0
 0  1  0

julia> strel_box((3, 3)) # все соседние элементы: связь C8
3×3 SEBoxArray{2, UnitRange{Int64}} with indices -1:1×-1:1:
 1  1  1
 1  1  1
 1  1  1

julia> strel_box((3, 3), (1, ))
3×3 SEBoxArray{2, UnitRange{Int64}} with indices -1:1×-1:1:
 0  1  0
 0  1  0
 0  1  0

Используя эти конструкторы, можно предоставить более простой в использовании интерфейс my_erode(A, [dims]), добавив еще один метод:

my_erode(A, dims::Dims=ntuple(identity, ndims(A))) = my_erode(A, strel_diamond(A, dims))

Для структурирующего элемента Ω, созданного функцией strel_diamond или strel_box, вероятность быстрого выполнения выше, если тип массива сохраняется. Например, erode(A, strel_diamond(A)) обычно выполняется быстрее, чем erode(A, Array(strel_diamond(A))), так в Julia передается больше информации о форме Ω во время написания кода и компиляции.

Оптимизация производительности и функция strel_type

Благодаря механизму множественной диспетчеризации в Julia можно реализовать все приемы оптимизации, не усложняя интерфейс для пользователя. Это можно сделать программно с помощью функции strel_type. Например, если известна очень эффективная реализация erode для СЭ со связью C4, ее можно добавлять последовательно:

using ImageMorphology: MorphologySE, SEDiamond

my_erode(A, dims::Dims) = my_erode(A, strel_diamond(A, dims))
my_erode(A, Ω) = _my_erode(strel_type(Ω), A, Ω)

# универсальная реализация, приведенная выше
function _my_erode(::MorphologySE, A, Ω)
   ...
end

# оптимизированная реализация для СЭ, созданного функцией `strel_diamond`
function _my_erode(::SEDiamond, A, Ω)
   ...
end

# ...и другие оптимизированные версии, если они есть

По сути, strel_type — это функция-типаж, помогающая при диспетчеризации и проектировании кода:

julia> strel_type(Ω_mask)
SEMask{2}()

Она возвращает внутренний объект SEMask{2}(). Поначалу это может пугать, но вот такая простая сопоставительная таблица, в которой отражены приведенные выше рассуждения, упрощает понимание:

Представление Тип элементов strel_type

Смещение

CartesianIndex

SEOffset

Маска связи

Bool

SEMask

strel_diamond

Bool

SEDiamond

strel_box

Bool

SEBox