Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
8.2.1. Алгоритмы группирования
Для запоминания цифровой модели, состоящей из n строк и m столбцов, необходимо иметь L = nm ячеек памяти. Поскольку в реальных ситуациях большинство дискретов нулевое, то, в целях экономии памяти, необходимо запоминать лишь единичные дискреты. Алгоритм объединяет стоящие подряд в строке единичные дискреты и заносит в память номер строки, где расположена эта подгруппа, её начальный и конечный номера столбцов. Далее алгоритм группирует эти подгруппы, т. е. «собирает» из них группы.
Группа представляет собой совокупность единичных дискретов, являющихся либо соседями по столбцу, либо по строке. Например, на рис. 8.3 первая группа состоит из трех единичных дискретов (единиц), стоящих в первой строке в соседних столбцах. Точно также третья группа – это три соседних единицы во второй строке в пятом, шестом и седьмом столбцах. Пятая группа объединяет три соседние единицы, стоящие на различных строках и столбцах.
Такой алгоритм группировки является разновидностью алгоритма «ближайшего соседа» [7, 8] и означает следующее: если расстояние между центрами единичных дискретов не больше заранее заданной величины, то они должны быть отнесены к одной и той же группе
(8.15)
В частности, если размер r0 равен интервалу разрешения, то (8.15) превращается в условие «единичной связи» [7]:
(ia – ib)(ja – jb) = 0, (8.16)
где i – номер строки; j – номер столбца дискрета с координатами (i, j). Условие (8.16) является математической записью этого алгоритма группирования. Единичные дискреты с координатами (1,4) и (2,5) относятся к различным группам – первой и третьей. Также в различные группы входят дискреты (4,11) и (5,12) (см. рис. 8.1).
Рис. 8.3. К определению алгоритма обработки цифровой модели
радиолокационного изображения ПРЦ
Рис. 8.4. Эталонное изображение малого примера
Рис. 8.5. Эталонное изображение большого примера
Описанный алгоритм группирования безразличен к тому, какова внешняя граница группы, имеются ли внутри группы пустые области (многосвязность группы), он имеет меньшую зависимость времени обработки от количественных соотношений между группами и различными размерами. В этом состоит достоинство алгоритма (8.16) по сравнению с другими, предложенными, например, в [12].
Конкретная программная реализация описанного алгоритма осуществляется двумя путями. В первом случае используется алгоритм «единичной связи» (8.16) и специальные методы снижения вычислительных затрат (упакованное хранение информации, экономичные способы реализации алгоритма) [13, 14]. Программа ИЗОБР-1 приведена в [13]. Во втором случае в программе PICT-1 реализован алгоритм «ближайшего соседа» (8.15), а группирование осуществляется методами теории графов (используется дерево с минимальным покрытием) [13–17].