Глава 6. СТРУКТУРЫ ДАННЫХ

6.1. ВВЕДЕНИЕ

Всем, кто сталкивается с обработкой информации, представленной в виде изображений, прекрасно известно, что для ее хранения требуется память с большим объемом. Так, для запоминания, стандартного телевизионного кадра требуется, по меньшей мере, 512x512 байт, если для передачи двух из трех основных цветов используется по 3 бита и для передачи третьего — 2 бита Для запоминания черно белой паспортной фотографии требуется, по меньшей мере, матрица размерами 64x64, на передачу каждого элемента которой затрачивается по 6 бит, что существенно больше размеров записи, содержащей любую иную информацию, которая имеется в паспорте (Для запоминания одной страницы машинописного текста, напечатанного через интервал, требуется около 3000 байт) Проблемы, связанные с хранением, просмотром, поиском, передачей и т. п. , становятся особенно сложными, как только дело доходит до обработки изображений Эти трудности в определенном смысле противоестественны, так как человеку часто легче иметь дело с изображением, чем с текстом Нам значительно проще запомнить лицо нового знакомого, чем страницу машинописного текста Сложность воспроизведения этих способностей человека на ЭВМ можно оценить в полной мере, приняв во внимание, что некоторые люди легче вспоминают лицо, когда речь идет о субъекте противоположного пола, а текст запоминается лучше, если он является частью прозаического произведения, но не списком имен Следовательно, маловероятно, чтобы какие-либо

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

Задача сжатия данных принимает разные формы в системах связи и обработке информации на ЭВМ. При решении многих прикладных задач некоторое изображение порождается, передается, осматривается и затем ликвидируется. В задачах связи важнейшим требованием является уменьшением ширины полосы частот, необходимой для передачи сигнала, при условии, что обработка должна осуществляться за время, сопоставимое с временем, которое приходится затрачивать на порождение и передачу изображения. Иная ситуация возникает при решении прикладных задач, требующих базы изобразительных данных и длительного хранения изображений: приходится сопоставлять новые изображения со старыми или просматривать группы изображений, отыскивая на них определенные признаки. Таким образом, в дополнение к проблемам, связанным с объемами памяти, необходимой для хранения изображений, проблемы могут возникать и при обращении к памяти.

Человеку очень нетрудно сосредоточить внимание на каких-то определенных частях двухмерного изображения, тогда как ЭВМ вынуждена обрабатывать его вслепую. Следовательно, чрезвычайно важны алгоритмы обхода изображения. В дискретном случае обход изображения соответствует обходу некоторой дискретной сетки, которую можно интерпретировать как некоторый граф: его вершинами служат пикселы, а ребра связывают вершины, соответствующие смежным пикселам. Кроме такого простого отображения можно построить и другие графы, соответствующие отображению. Действительно, поскольку все структуры данных, используемые при работе с изображениями, представляют собой графы, целесообразно начать с обзора алгоритмов обхода графов. (Читателям, не знакомым с теорией графов, следует прочесть приложение 6.А). При применении этих алгоритмов к графам, представляющим изображения, действует одно ограничение. Вследствие значительного размера эти графы редко представляют в одной из обычных форм (например, с помощью матрицы смежности, списка вершин и т. д.). В простейшем случае, например, задаются лишь координаты х, у пикселов и их значения яркости или цвета. В результате возникает задача отыскания вершин, смежных с заданной. Если требуется совершить обход только тех участков изображения, которые образуют однородную в некотором смысле область, то приходится решать, принадлежат ли соседние пикселы той же области, что и «текущий» пиксел. Поэтому мы намеренно не будем, по крайней мере в данной главе,

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