15.2. МЕТОДЫ ОПРЕДЕЛЕНИЯ ГРАНИЦ ОРГАНОВ

Обозначим, как и ранее, через полное число элементарных объемов, а сами объемы пронумеруем целыми числами где Для двух различных элементарных объемов с индексами и к будем использовать обозначение если данные объемы имеют общие грани, или обозначение если они имеют общее ребро, но не имеют общих граней. В первом случае будем называть пару элементарных объемов гранью объекта, а пару ребром грани если имеются объемы с (рис. 15.2). Если имеется то мы также говорим, что пара является гранью элементарного объема Ясно, что каждый элементарный объем имеет шесть граней, а каждая грань — четыре ребра. Отметим, что по причинам, которые станут понятными ниже, мы не будем отождествлять грани с и

Пусть два непересекающихся множества элементарных объемов. Границу между определим как множество граней между двумя элементарными объемами, один из которых принадлежит множеству Математически это означает, что

При этом нас особо не интересуют границы между произвольными множествами элементарных объемов, поскольку мы ограничимся определением границ между «рассматриваемым» и «смежным» органами. Определим теперь смысл введенных понятий.

Для этого обратимся к множеству Интуитивно читатель может посчитать, что множество элементарных объемов, значения чисел Хаунсфилда которых попадают в диапазон значений (разд. 15.1). например, если множество содержит все элементарные объемы, имеющие одинаковую плотность с мышцей сердца (которая по предположению отличается от плотности крови), то последняя будет «органом» на множестве а каждая полость сердца (и внешние соединительные ткани) будут «соседним органом» на Наложим некоторые ограничения на интересующие нас

Рис. 15.2. Пара описывает грань элементарного объема пара его ребро.

множества Во-первых, потребуем, чтобы множество было непустым; во-вторых, не должно содержать элементарных объемов, расположенных на границе, другими словами, должно быть подмножеством внутренних объемов, обозначаемых в двумерном случае символом (разд. 12.3). Вот почему мы будем называть множество элементарных объемов, удовлетворяющих этим двум условиям, внутренним множеством. Причиной введения второго ограничения является то, что при определении понятия границы с помощью выражения (15.1) нам были необходимы элементарные объемы по обе стороны от граничных граней. Второе условие всегда можно выполнить путем дополнения массива элементарных объемов вспомогательным слоем объемов со всех сторон и присваивания им чисел Хаунсфилда, которые не попадают в диапазон

Пусть внутреннее множество, непустое его подмножество; при этом будем говорить, что В есть «орган» из если

а) для всех отличающихся друг от друга элементов и к на подмножестве В существует последовательность элементарных объемов, для которой кроме того, при условии существует либо пара либо пара

б) подмножество В не является собственно подмножеством любого подмножества множества которое удовлетворяло бы условию «а».

Проще говоря, «орган» В из определяется любым одним из элементов следующим образом: «орган» В содержит все элементарные объемы к, которые можно достигнуть из элементарного объема путем пересечения граней и ребер элементарных объемов, принадлежащих множеству Рис. 15.3 иллюстрирует данное определение.

Пусть внутреннее множество, непустое множество элементарных объемов, не содержащее ни одного элемента из Другими словами, подмножество из дополнения множества . В этом случае мы говорим, что является «смежным органом» множества если

а) для всех отличающихся друг от друга элементов множества В на нем существует последовательность элементарных объемов, для которой кроме того, при условии существует или ;

б) подмножество В не является собственно подмножеством любого подмножества которое удовлетворяет первому условию.

Рис. 15.3. Иллюстрация предлагаемой концепции «органа» и «смежного органа». Представлены изображения трех последовательно взятых слоев из трехмерного массива данных. Незаштри кованные клетки соответствуют элементарным объемам множества Мы предполагаем, «то все элементы объема, не показанные на рисунке, принадлежат множеству . В этом случае множество содержит два «органа», один из которых состоит из одного элемента объема, расположенного в верхнем левом углу правого рисунка, а другой содержит все оставшиеся элементы множества Множество имеет два «смежных органа», один из которых состоит из двух элементов объема, расположенных в центре среднего рисунка и заштрихованных перекрестной штриховкой, а другой — из всех оставшихся элементов множества О.

Проще говоря, «смежный орган» множества определяется одним из его элементов следующим образом: «смежный орган» содержит все элементарные объемы к, которые можно достигнуть из элементарного объема путем пересечения граней элементарных объемов, не принадлежащих множеству Данное определение также иллюстрируется рис. 15.3.

Заметим, что понятие «смежного органа» определено «сильнее», чем понятие «органов», поскольку в первом случае не допускается связности по ребрам. Причина этого состоит в том, что нам желательно получить поверхность в виде жордановой поверхности, другими словами, в виде поверхности, разделяющей пространство на две области с общей границей, называемые внешней и внутренней областями соответственно. [В нашем случае поверхностные элементы представляют собой пары элементарных объемов где внешняя, а внутренняя области. Заметим, что полное значение понятия «внутренняя область» определяется как «внутренняя область органа». Весьма вероятно, что внутренняя область может заключать в себе внешнюю, как это было в приведенном примере с мышцей сердца и его полостями.] Кроме того, каждая точка пространства, не лежащая на жордановой поверхности, должна принадлежать либо внутренней, либо внешней области. Любые две точки во внутренней (или во внешней) области можно соединить кривой, не содержащей точек поверхности. Любая кривая, соединяющая точки внутренней и внешней областей, должна содержать по крайней мере одну точку поверхности. В частности, полупрямая, берущая свое начало в точке внутри поверхности, не может выйти из внутренней области, не пересекая поверхности. Ниже мы широко используем данное свойство.

Цель настоящего раздела — найти такой алгоритм, который для любого внутреннего множества и для «обой пары элементов границы

давал бы нам все элементы множества где В характеризует «орган» из который содержит объем характеризует «смежный орган» из который содержит объем k. Проще говоря, алгоритм должен давать способ нахождения всех граней на границе (или на ее части) «органа», который содержит данную поверхность.

Предположим, что мы имеем метод, с помощью которого для любого внутреннего множества любых «органов» принадлежащих и для любой поверхности лежащей на границе на ней образовывались бы две другие грани для которых было бы справедливо следующее утверждение: для всех граней отличающихся друг от друга на границе на ней существует последовательность граней для которой кроме того, при условии существует либо грань либо грань Подобный метод можно применить в качестве алгоритма определения граничных поверхностей, к объяснению которого мы и переходим.

Данный алгоритм дает «перечень» граней и использует «соединение» граней. Предположим, что пара объемов заданная на границе грань Алгоритм включает в себя следующие операции:

а) подставить в и

б) убрать элемент из

в) если поверхность не содержится в «перечне» то необходимо подставить в

г) если поверхность не содержится в «перечне» то необходимо подставить в

д) если множество пустое, то вычисления заканчивают; в противном случае переходят к выполнению операции

Теперь рассмотрим особенности предложенного алгоритма. Прежде всего мы предполагаем существование метода, позволяющего получать функции для любой грани на границе причем вычисляемое по «6», принадлежит границе поскольку она принадлежит множеству Легко показать, что на любом этапе выполнения алгоритма все элементы множества содержатся в Аналогично все элементы «перечня» также содержатся в и благодаря специфическим свойствам функций и любой элемент, принадлежащий рано или поздно попадает в С этого момента множество исчерпывают повторением операции не распространяя алгоритм на операции Таким образом, множество при определенных обстоятельствах оказывается пустым, и с этого момента выполнение алгоритма прекращается на том «перечне» который содержит все элементы границы и не содержит никаких других.

Таким образом, алгоритм позволяет выполнить поставленную перед ним задачу. Единственное, что было здесь опущено, — это объяснение того, как по грани рассчитать Хотя этот вопрос и весьма существен, из-за технических трудностей его подробное изложение в настоящей книге опущено. Здесь на примере «органа», состоящего из трех элементарных

Рис. 15.4. а — «орган», содержащий три элементарных объема; связанные с ним функции (сплошные стрелки) и (штриховые стрелки), осуществляющие отображение поверхности на поверхность.

объемов, мы приведем простую иллюстрацию возможностей метода.

На рис. 15.4 изображены три элементарных объема, которые по предположению принадлежат множеству а остальные объемы — множеству Все поверхности на границе пронумерованы цифрами и мы будем считать, что заданная поверхность имеет номер 1. Функции и определяются с помощью графа рис. 15.4,б, причем грань соединяется с гранью сплошной стрелкой, а с гранью штриховой. Достаточно просто, но очень громоздко провести доказательство того, что указанные функции действительно обладают требуемыми свойствами.

Теперь мы продемонстрируем работоспособность алгоритма при помощи таблицы. В каждой строке табл. 15.1 последовательно приведены значения величин на пятом этапе вычислений.

На практике может потребоваться слишком много времени для проверки на третьем и четвертом этапах вычислений того, содержатся или нет грани в «перечне» Последнее обусловлено тем, что множество может содержать около элементов (мы увидим это на примере разд. 15.5), а множество при определенных обстоятельствах может иметь такое же число элементов.

Один из методов уменьшения количества требуемых вычислений для определения того, принадлежит ли уже поверхность «перечню» состоит в разбиении на несколько «перечней» меньшего размера в зависимости от специфических свойств его элементов. При этом каждую новую грань потребуется проверять лишь в одной какой-либо группе. Например, все грани ориентированы в одном из шести возможных направлений (т.е. для граней с индексами вектор, восставленный из центра элементарного объема

Таблица 15.1 (см. скан)

в направлении на центр элементарного объема, может иметь одно из шести возможных значений). Можно использовать это свойство для уменьшения затрат времени по проверке наличия граней в «перечне» в 6 раз. Кроме того, разбиение на шесть групп в соответствии с выбранным критерием окажется также полезным при отображении поверхностей органов, как это будет видно в следующем разделе.