Cтраница 4
На рис. 9.8 представлен остов изображения, приведенного на рис. 9.6. Для обхода соответствующего графа необходимо в каждой связной компоненте задать некоторую исходную вершину. Такие вершины можно найти в процессе просмотра двухуровневого изображения, содержащего остовные пикселы, осуществляемого сверху вниз слева направо. В общем случае эти вершины имеют второй порядок, что, в частности, имеет место и для обеих компонент изображения рис. 9.8. В процессе обхода графа информация может не выводиться до тех пор, пока не будет обнаружена некоторая вершина, порядок которой отличается от двух. Если такую вершину обнаружить не удается, то соответствующий граф представляет собой просто некоторую цепь и при выводе можно ограничиться этой информацией. Допустим, что в данном примере для первой связной компоненты в качестве начальной точки выбрана вершина d, а для второй - вершина а. В процессе обхода, начатого в вершине d, обнаруживается, что С является следующей вершиной порядка, отличного от двух. Для представления этого описания существуют различные способы. [46]
Точки сочленения можно обнаружить с помощью грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из наших алгоритмов обхода графа для проверки связности оставшейся части. Если оставшийся граф связен, то удаленная вершина не является точкой сочленения. При таком подходе мы должны выполнить N обходов графа с N вершинами, что потребует 0 ( 7V2) операций. Однако сохраняя незначительное количество дополнительной информации при обходе графов, можно обнаружить все точки сочленения и компоненты двусвязности при единственном обходе. [47]
Главы 2 - - 4 посвящены тоновым изображениям и основное внимание в них уделяется преобразованиям и статистическим методам. Необходимым условием понимания всех четырех глав, в которых речь идет только об изображениях класса 1, является вводный курс по обработке сигналов. Остальной материал книги не требует такой подготовки. Все алгоритмы, представленные в этих трех главах, являются фактически алгоритмами обхода графа. Предполагается знакомство читателя с терминологией теории графов. Главы 10 - 13 посвящены построению кривых и поверхностей по точкам. Хотя формально изложенный в них материал базируется на простейших сведениях из анализа, все же некоторая математическая культура здесь не помешает. Главы 14 - 17 посвящены методам формирования графических отображений и их математическому фундаменту - линейной алгебре. [48]