Граф - смежность
Cтраница 1
Граф смежности - граф, в котором районы отображаются узлами ( вершинами), а пара смыкающихся районов - ребрами. [1]
Граф смежности областей является, вероятно, более естественной ( и появившейся раньше) для обработки изображений структурой данных; в большей части литературы, посвященной анализу сцен, фигурируют ее различные варианты. [2]
Широкое применение нашел также граф смежности строк, хотя часто оно имеет неявный характер. Алгоритмы, предназначенные для выполнения различных операций над изображением, описываются на языке пикселов и интервалов без каких-либо упоминаний о ГСС. Статья [6.3] - это, вероятно, первая работа, в которой списано использование ( неявное) ГСС. В статье [6.10] обсуждается явное использование ГСС при решении задач машинной графики ( дальнейшие сведения приведены в гл. [3]
На рис. 6.13 приведен пример графа смежности областей, наложенного на изображение. [4]
В данном случае в качестве структуры данных удобно использовать граф смежности строк контура ( К-ГСС), поскольку его вершины соответствуют пересечениям контура с некоторой горизонтальной прямой. В точке максимума верхний порядок вершины равен нулю, а в точке минимума нижний порядок вершины равен нулю. Любые другие пары значений порядков недопустимы для полной области. Предполагается, что единицами измерения значений х и у служат размеры ячеек сетки. [5]
Отметим, наконец, что хранение матриц осуществляется в виде двух одномерных массивов: графа смежности ADJNCY и дополнительного индексного массива XADJ. Граф смежности формируется таким образом, что в матрице хранятся в основном ненулевые элементы. [6]
Данный алгоритм выполняет последовательную построчную обработку, причем в памяти должно храниться лишь небольшое число строк или их частей. Для простоты будем описывать работу алгоритма как процесс обхода графа смежности строк, хотя запоминание последнего в явном виде не предусматривается. Анализ параллельного режима работы проведен в гл. Для данного алгоритма весьма существенным являются понятия вертикального, горизонтального и диагонального маршрутов, которые мы определим следующим образом. [7]
Различных индексов, удовлетворяющих ( 5) существует для n3, z2 один, а для n4, z5 - тринадцать. Каждому из индексов может соответствовать несколько негомеоморфных структур, также как и каждому из графов смежности Х ь может соответствовать некоторое множество структур с различными индексами. [8]
 |
Основные топологические свойства моделей ГИС. а - пересечение. 6 - близость. в - связанность. [9] |
Ребра такого графа описывают границы между районами, а его узлы ( вершины) представляют точки смыкания районов. Степень вершины такого графа - это число районов, которые в ней смыкаются. Граф смежности это как бы вывернутый наизнанку граф покрытия. В нем районы отображаются узлами ( вершинами), а пара смыкающихся районов - ребрами. На основе такого графа ГИС может выдать ответ на вопрос, является ли проходимой рассматриваемая территория, разделенная на проходимые или непроходимые участки. [10]
 |
Основные топологические свойства моделей ГИС. а - пересечение. б - близость. в - связанность. [11] |
Ребра такого графа описывают границы между районами, а его узлы ( вершины) представляют точки смыкания районов. Степень вершины такого графа - это число районов, которые в ней смыкаются. Граф смежности это как бы вывернутый наизнанку граф покрытия. В нем районы отображаются узлами ( вершинами), а пара смыкающихся районов - ребрами. На основе такого графа ГИС может выдать ответ на вопрос, является ли проходимой рассматриваемая территория, разделенная на проходимые или непроходимые участки. [12]
Подобные комбинированные критерии легко реализуются с применением какой-либо общепринятой структуры данных. Оказывается, что граф смежности строк контура ( К-ГСС) подходит для реализации обеих критериев. Очевидно, что эта структура данных годится для реализации алгоритма заполнения области, основанного на анализе значений яркости пикселов и использующего критерий четности, поскольку главным объектом этого алгоритма является контур. При реализации алгоритмов, в которых используется критерий связности, в качестве структуры данных обычно выбирается граф смежности строк внутренней части области ( В-ГСС), однако утверждение 6.5 указывает способ, позволяющий применять при реализации этих алгоритмов и К-ГСС. Если допустить, что внутренняя часть области характеризуется н-связностью, контур - к-связностью, внутренняя часть области окрашена в цвет X и пикселы контура - в цвет Y, то утверждение 6.3 можно переформулировать следующим образом. [13]
Запись условий перекрытия в виде строгих неравенств означает, что интервалы, соприкасающиеся лишь одним углом, не считаются перекрывающимися. Это ограничение можно снять, просто взяв нестрогие неравенства. Поскольку условия частичного перекрытия легко проверяются, нет необходимости хранить граф смежности строк в явном виде. [14]
Подобные комбинированные критерии легко реализуются с применением какой-либо общепринятой структуры данных. Оказывается, что граф смежности строк контура ( К-ГСС) подходит для реализации обеих критериев. Очевидно, что эта структура данных годится для реализации алгоритма заполнения области, основанного на анализе значений яркости пикселов и использующего критерий четности, поскольку главным объектом этого алгоритма является контур. При реализации алгоритмов, в которых используется критерий связности, в качестве структуры данных обычно выбирается граф смежности строк внутренней части области ( В-ГСС), однако утверждение 6.5 указывает способ, позволяющий применять при реализации этих алгоритмов и К-ГСС. Если допустить, что внутренняя часть области характеризуется н-связностью, контур - к-связностью, внутренняя часть области окрашена в цвет X и пикселы контура - в цвет Y, то утверждение 6.3 можно переформулировать следующим образом. [15]
Страницы: 1 2