6.11. БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
Задачи, связанные с обходом графов и соответствующими структурами данных, рассматриваются в большинстве книг, посвященных алгоритмам или структурам данных (например, [6.1, 6.8]).
Обсуждение этих задач в контексте распознавания образов можно найти и в монографии [3.7]. Следует также обратить внимание на работы [6.2, 6.9], в которых обсуждается проблема сохранения геометрической смежности при пословной организации памяти.
Тетрарное дерево — одна из наиболее часто рассматриваемых в современной литературе структур данных. Впервые ее применение приобрело широкую известность в связи с алгоритмом удаления невидимых линий, предложенным Уорноком [6.15]. В начале 70-х годов тетрарное дерево нашло широкое применение в распознавании образов и обработке изображений ([6.4-6.6, 6.13, 6.14]). Использование тетрарных деревьев для получения визуальных отображений методом первоначального грубоинформативного представления впервые было описано в работе [6.12]. Бинарное дерево было не так давно введено Ноултоном [6.7] (рис. 6.8 заимствован из статьи 6.7). Тетрарные деревья являются сейчас популярным объектом исследований, и их свойства изучены достаточно досконально; в докладе [6.11] дан обзор полученных результатов.
Широкое применение нашел также граф смежности строк, хотя часто оно имеет неявный характер. Алгоритмы, предназначенные для выполнения различных операций над изображением, описываются на языке пикселов и интервалов без каких-либо упоминаний о ГСС. Статья [6.3] — это, вероятно, первая работа, в которой списано использование (неявное) ГСС. Другие примеры применения ГСС в распознавании образов и обработке изображений можно найти в монографии [3.7]. В статье [6.10] обсуждается явное использование ГСС при решении задач машинной графики (дальнейшие сведения приведены в гл. 8).
Граф смежности областей является, вероятно, более естественной (и появившейся раньше) для обработки изображений структурой данных; в большей части литературы, посвященной анализу сцен, фигурируют ее различные варианты.
6.12. ЗАДАЧИ
(см. скан)
