Оптимальная сегментация поверхности в объемных изображениях - теоретико-графический подход

  1. 3.1 Одиночная поверхность
  2. Внутриколоночные дуги Ea
  3. Межколонные дуги Er
  4. 3.2 Несколько поверхностей

Ключевым нововведением нашего метода является построение нетривиального графа с целью преобразования задачи сегментации поверхности в вычисление минимального замкнутого множества в орграге с взвешиванием узлов. Закрытое множество C в орграфе является подмножеством узлов, так что все преемники любых узлов в C также содержатся в C. Стоимость закрытого набора - это общая стоимость узлов в наборе. Задача минимального замкнутого множества состоит в поиске замкнутого множества с минимальной стоимостью, которое может быть решено за полиномиальное время путем вычисления минимального сечения в производном дуго-взвешенном орграфе [ 57 ].

3.1 Одиночная поверхность

Объемное изображение можно рассматривать как трехмерную матрицу ℐ (x, y, z ). Предположим, что ландшафтоподобная поверхность в oriented ориентирована, как показано на. Пусть X, Y и Z обозначают размеры изображения в направлениях x, y и z соответственно. Поверхность определяется функцией 𝒩: ( x, y ) → 𝒩 ( x, y ), где xx = {0,…, X - 1}, y ∈ y = {0,…, Y - 1} и 𝒩 ( x, y ) ∈ z = {0,…, Z - 1}. Таким образом, любая поверхность в ℐ пересекается с ровно одним вокселем каждого столбца (вокселей), параллельным оси z , и состоит из ровно X × Y вокселей. Мы называем эту модель многоколоночной моделью.

Проблема обнаружения одной поверхностиПроблема обнаружения одной поверхности

(а) Ориентация поверхности. (б) Два соседних столбца построенного ориентированного графа. Дуги, показанные пунктирными линиями, являются необязательными.

Поверхность считается выполнимой, если она удовлетворяет некоторому зависящему от приложения ограничению гладкости, определяемому двумя параметрами гладкости, x и y . Ограничение гладкости гарантирует связность поверхности в 3D. Точнее, если ℐ ( x, y, z ) и ℐ ( x + 1, y, z ′ ) два вокселя на допустимой поверхности, то | z - z ′ | ≤ Δ х . Аналогично, если ℐ ( x, y, z ) и ℐ ( x, y + 1, z ′ ) два вокселя на допустимой поверхности, то | z - z ′ | ≤ Δ у . Если x ( y ) мало, любая допустимая поверхность является жесткой в ​​направлении x (y) , и жесткость уменьшается с увеличением x ( y ).

Определяя функцию стоимости, значение стоимости вычисляется для каждого вокселя ℐ ( x, y, z ) из ℐ, обозначенного c (x, y, z) . Как правило, c (x, y, z) является произвольным действительным значением, которое обратно связано с вероятностью того, что искомая поверхность содержит воксель ℐ ( x, y, z ). Стоимость поверхности - это общая стоимость всех вокселей на поверхности. Оптимальная поверхность - это поверхность с минимальной стоимостью среди всех возможных поверхностей, определяемых в трехмерном объеме.

Ориентированный на узлы ориентированный граф G = ( V, E ) строится в соответствии с ℐ следующим образом: каждый узел V (x, y, z)V представляет один и только один воксель ℐ (x, y, z) ∈ ℐ, чья стоимость w (x, y, z) определяется согласно:

Узел V (x, y, z) находится выше (соответственно, ниже ) другого узла V (x, y, z), если z > z (соответственно, z < z ). Для каждой пары ( x, y ) с xx и y ∈ y подмножество узлов { V (x, y, z) | zz } называется ( x, y ) - столбцом группы G , обозначаемым Col (x, y) . Два ( x, y ) -колонки являются смежными, если их ( x, y ) координаты являются соседями в данной системе окрестностей. Например, при настройке 4-х соседей столбец Col (x, y) соседствует с Col ( x + 1, y ), Col ( x - 1, y ), Col ( x, y + 1) и Col ( х, у - 1). В оставшейся части статьи предполагается, что система с 4 соседями. Дуги G состоят из двух типов: внутриколоночных и межколонных дуг, построенных следующим образом. Цель нашей конструкции - преобразовать проблему сегментации в задачу с минимальным замкнутым множеством ( Раздел 4.1 ).

Внутриколоночные дуги Ea

Вдоль каждого столбца Col (x, y) каждый узел V (x, y, z) ( z > 0) имеет направленную дугу к узлу V ( x, y, z - 1), т.е.

Межколонные дуги Er

Рассмотрим любые два соседних столбца, Col (x, y) и Col ( x + 1, y ). Вдоль x- направления и для любого xx направленная дуга строится из каждого узла V (x, y, z) ∈ 2 Col (x, y) в узел V ( x + 1, y , max (0, z - Δx)) ∈ Col ( x + 1, y ). Аналогично, направленная дуга соединяется из V ( x + 1, y, z ) ∈ Col ( x + 1, y ) с V ( x, y , max (0, z - Δx)) ∈ Col (x, y ) Та же самая конструкция сделана для y- направления. Эти дуги обеспечивают ограничения гладкости. В итоге:

Интуитивно понятно, что межколонные дуги гарантируют, что если воксель ℐ (x, y, z) находится на допустимой поверхности 𝒩, то его соседние воксели на 𝒩 вдоль направления x , ℐ ( x + 1, y, z ′ ) и ℐ ( x - 1, y, z ″ ), не должно быть «ниже», чем воксел ℐ ( x, y , max (0, z - Δx)) (т. Е. Z ′, z ″ ≥ max (0, z - Δх)). То же правило применяется к y- направлению. Межколонные дуги делают узел V ( x, y , 0) сильно связанным , что означает, что в V ( x, y , 0) каждый узел доступен из любого другого узла через некоторый канал. V ( x, y , 0) также образует «минимальную» выполнимую поверхность, которая может быть определена в G. Из-за этого множество узлов V ( x, y , 0) получает специальное имя, называемое базовым набором , обозначаемое VB .

Иногда требуется, чтобы желаемая поверхность была обернута вдоль направления x (или y ). Это обычное явление при сегментировании цилиндрической поверхности, которая сначала разворачивается в рельефную поверхность с использованием цилиндрического преобразования координат [ 27 ] перед применением нашего алгоритма (). Тогда первый и последний ряды вдоль разворачивающейся плоскости также должны удовлетворять ограничениям гладкости. В случае с x- циклом каждый узел V (0, y, z ) (соответственно V ( X - 1, y, z )) также подключается к V ( X - 1, y , max (0, z - Δ x). )) (соответственно V (0, y , max (0, z - Δx))). То же правило применяется к случаю с у- образным циклом.

Изображение разворачиваетсяИзображение разворачивается

(а) Трубчатый объект в объемном изображении. (б) «Развернуть» трубчатый объект в (а), чтобы сформировать новое трехмерное изображение. Граница трубчатого объекта в исходном изображении соответствует поверхности, обнаруживаемой в развернутом изображении.

3.2 Несколько поверхностей

Для одновременного сегментирования k ( k ≥ 2) различных, но взаимосвязанных поверхностей, оптимальность определяется не только собственными затратами и свойствами гладкости отдельных поверхностей, но также ограничивается их взаимосвязями.

Если поверхностные взаимодействия не рассматриваются, то k поверхностей 𝒩 i можно обнаружить на k отдельных трехмерных графиках. G i = (V i, E i) = (V i, E i a ∪ E i r) (i = 1,…, k). Каждый Gi построен так, как описано выше. Затраты узла вычисляются с использованием k функций стоимости (не обязательно отличных), каждая из которых предназначена для обнаружения одной поверхности. Принимая во внимание поверхностные взаимосвязи, необходим еще один набор дуг Es , формирующий ориентированный граф G (V, E) в четырехмерном пространстве с V = ∪ i = 1 k V i и E = ∪ i = 1 k E i ∪ E с. Дуги в Es называются межповерхностными дугами, которые моделируют попарные отношения между поверхностями. Для каждой пары поверхностей наш подход определяет их отношения, используя два параметра: δl ≥ 0 и δ u ≥ 0, представляющих ограничение разделения поверхности.

Конструкция Es для сегментации двойных поверхностей подробно описана ниже на примерах. Идеи могут быть легко обобщены для обработки более двух поверхностей.

Во многих практических задачах поверхности не должны пересекаться или перекрываться. Например, внутренние и внешние стенки ткани должны быть непересекающимися, а расстояние между ними должно быть в пределах некоторого ожидаемого диапазона в медицинских изображениях. Предположим, что для обнаружения двух поверхностей 𝒩1 и 𝒩2 предшествующее знание требует, чтобы 𝒩2 была ниже 𝒩1. Пусть минимальное расстояние между ними равно δl единиц вокселей, а максимальное расстояние равно δu единиц вокселей. Пусть трехмерные графики, используемые для поиска 𝒩1 и 𝒩2, представляют собой G 1 и G 2 соответственно, и пусть Col 1 ( x, y ) и Col 2 ( x, y ) обозначают два соответствующих столбца в G 1 и G 2.

Для любого узла V 1 ( x, y, z ) в Col 1 ( x, y ) с z ≥ δ u направленная дуга в Es, соединяющая V 1 ( x, y, z ) с V 2 ( x, y, z - δ u ) построено. Кроме того, для каждого узла V 2 ( x, y, z ) в Col 2 ( x, y ) с z < Z - δ l направленная дуга в Es, соединяющая V 2 ( x, y, z ) с V 1 ( x , y, z + δl). Эта конструкция применяется к каждой паре соответствующих столбцов G 1 и G 2.

Из-за ограничения разделения (𝒩2 не менее δl единиц вокселей ниже below1), любой узел V 1 ( x, y, z ) с z <δl не может быть на поверхности 𝒩1. В противном случае ни один узел в Col 2 ( x, y ) не может быть на поверхности 𝒩2. Аналогично, любой узел V 2 ( x, y, z ) с zZ - δ l не может принадлежать поверхности 𝒩2. Эти узлы, которые невозможно найти ни в одном из возможных решений проблемы, называются дефектными узлами. Следовательно, для каждого столбца Col 1 ( x, y ) ∈ G 1 безопасно удалить все узлы V 1 ( x, y, z ) с zl и их инцидентные дуги в E 1. Аналогично для каждого столбца Col 2 ( x, y ) ∈ G 2, мы благополучно исключаем все узлы V 2 ( x, y, z ) с zZ - δ l и их падающие дуги в E 2.

Из-за удаления дефектных узлов базовый набор G 1 становится V 1 ( x, y , δ l ). Соответственно, стоимость каждого узла V 1 ( x, y , δl) модифицируется как w 1 ( x, y , δl) = c 1 ( x, y , δl), где c 1 ( x, y , δl) - первоначальная стоимость вокселя ℐ ( x, y , δl) для поверхности 𝒩1. Межколонные дуги G 1 модифицированы, чтобы сделать V 1 ( x, y , δl) сильно связным. Базовое множество G тогда становится VB = V 1 ( x, y, δ l ) ∪ V 2 ( x, y, 0). Направленная дуга 〈 V 1 (0, 0, δ л ); V 2 (0, 0, 0)〉 вводится в Es, чтобы сделать VB сильно связным.

Таким образом, набор Es межповерхностной дуги для моделирования двух непересекающихся поверхностей построен как:

В других ситуациях мы можем позволить двум взаимодействующим поверхностям пересекаться друг с другом. Это встречается при отслеживании движущейся поверхности во времени. Для этих задач вместо моделирования минимальных и максимальных расстояний между ними δl и δu задают максимальные расстояния, которые поверхность может варьировать ниже и выше другой поверхности соответственно. Межповерхностные дуги для этого случая состоят из следующих элементов: 1 V 1 ( x, y, z ), V 2 ( x, y, max (0, z - δl))〉 и 〈 V 2 ( x, y, z ), V 1 ( x, y, max (0, z - δ u ))〉 для всех xx , yy и zz . Краткое изложение всех случаев иллюстрируется в.

Краткое описание моделирования взаимосвязи поверхностиКраткое описание моделирования взаимосвязи поверхности

𝒩1 и 𝒩2 - две желаемые поверхности. Col 1 ( x, y ) и Col 2 (x, y) - два соответствующих столбца в построенных графах. Дуги, показанные пунктирными линиями, являются необязательными. (а) Случай отсутствия скрещивания. (б) Случай с пересечением разрешен.