ТАБЛИЧНО-ИТЕРАЦИОННЫЙ АЛГОРИТМ ПРЕОБРАЗОВАНИЙ ВРАЩЕНИЯ КОНТУРНЫХ ИЗОБРАЖЕНИЙ

Введение

Анализ известных методов и алгоритмов реализации преобразования вращения контурных изображений, описанных в работах [1,2,3,4,5,6], показал целесообразность и эффективность применения итерационных алгоритмов при решении задачи идентификации объектов на основе оптико-электронных вычислительных комплексов. Данные алгоритмы в наибольшей степени удовлетворяют предъявляемым к ним требованиям, с точки зрения возможности их аппаратурной реализации и обеспечения высокого быстродействия.

Основные из этих требований определены в работе [4] и заключаются в следующем. Во-первых, операционный состав алгоритмов должен в основном ограничиваться алгебраическим сложением, сдвигом и выборкой из таблиц; во-вторых, алгоритмы должны допускать возможность распараллеливания и в-третьих, каждая типовая операция должна иметь однотипную структуру, обеспечивающую высокую однородность реализации.

Учитывая эти требования, а также специфику выполнения преобразования вращения при решении задачи идентификации объектов, которая заключается: во-первых, в необходимости выполнения процедуры вращения точек контурного изображения с постоянным угловым шагом ∆f; во-вторых, в небольшой разрядности входных/выходных данных (10-12 бит), обусловленной разрешающей способностью устройств ввода/вывода видеоданных, получим рекуррентные соотношения анализируемых преобразований, на основе которых разработан быстродействующий таблично-итерационный алгоритм, предлагаемый для использования в системах идентификации объектов и ориентированный на аппаратурную реализацию.

Вывод рекуррентных соотношений

Рассмотрим итерационный процесс вращения некоторой точки , заданной координатами , вокруг начала координат. Геометрическая интерпретация этого процесса показана на рис. 1. При повороте точки  на угол  она займет положение точки , координаты которой определены соотношением:

            (1)

Рис. 1. Геометрическая интерпретация процедуры вращения точки 

Угловая ориентация  определяется углом :

,            (2)

где  – исходное угловое положение точки .

На втором шаге, при повороте точки  на угол , она займет положение точки  с координатами:

         (3)

и угловой ориентации , равной:

 .          (4)

Подставляя выражения (1) и (2) в выражения (3), (4), получим:

        (5)

       (6)

Тогда для  шага положение точки  будет определяться координатами:

      (7)

а её угловая ориентация соотношением:

      (8)

Учитывая соотношения (5) и (6 ) выражения (7) и (8) можно записать в следующем виде:

        (9)

       (10)

Полученные рекуррентные соотношения (7) эквивалентны (1), но учитывают специфику выполнения преобразования вращение в рассматриваемом практическом приложении.

Для контурного изображения, описываемого массивом, состоящим из точек, уравнения (7) примут следующий вид:

 ,        (11)

где  и- соответственно старые и новые координаты точки k на плоскости,  - шаг изменения угловой ориентации точки (отсчитываемой против часовой стрелки от радиуса-вектора предыдущей ориентации), i -номер итерации, , k– положение точки в массиве.

При этом на каждом шаге изменения угловой ориентации преобразованиям (11) подвергаются все точки заданного массива. Процедура вращения заканчивается при выполнении условия:

       (12)

Рассмотрим таблично-итерационный алгоритм преобразований вращения контурных изображений, реализуемый на основе полученных соотношений (11).
Таблично-итерационный алгоритм преобразований вращения

Анализируя соотношения (11), можно сделать следующие выводы.
Во-первых, соотношения (11) позволяют распараллелить процесс вычисления новых координат  и  естественным образом, что обеспечивает высокое быстродействие выполнения преобразования вращения.
Во-вторых, постоянство приращения угла  и небольшая разрядность входных данных позволяют хранить частичные произведения  и  в ПЗУ в виде таблиц для всех k точек контурного изображения. При этом координаты этих точек  и  будут являться адресами соответствующих ячеек ПЗУ.

В этом случае таблично-итерационный алгоритм преобразования вращения контурного изображения, характеризуемого k точками, можно записать следующим образом:

Задать массив координат  и , описывающих начальную ориентацию преобразуемого изображения.
Выбрать из этого массива координаты , , являющиеся координатами первой точки.
По этим координатам, которые используются далее как адреса ячеек ПЗУ, считать значения частичных произведений .
Вычислить новые координаты первой точки , :

         (13)

5. Значения ,  запомнить (вместо значений , ).
6. Выбрать координаты второй точки и описанным выше способом получить новые значения, которые также запоминаются вместо  и .
Описанная процедура повторяется для всех k точек. В результате чего будет сформирован новый массив координат , который будет соответствовать измененной ориентации контурного изображения на угол .
Если необходимо осуществить поворот изображения на угол , то нужно выполнить i таких итерационных циклов.

1. Василенко Г.И., Цибулькин Л.М. Голографические распознающие устройства. М.: Радио и связь, 1985, 312 с.
2. Василенко Г.И. Голографическое опознавание образов. М.: Сов. Радио, 1977, 328 c.
3. Файн В.С. Опознавание изображений. М.: Наука, 1970, 296 с.
4. Байков В.Д., Смолов В.Б. Специализированные процессоры: итерационные алгоритмы и структуры. М.: Радио и связь, 1985, 287 с.
5. Смолов В.Б., Байков В.Д. Принципы и перспективы применения методов вычислений «цифра за цифрой» //Электроника и методы гибридных вычислений. Киев: АН УССР, 1978, c.119-130
6. Овчеренко В.А. Итерационные алгоритмы геометрических преобразований контурных изображений в системах распределенной обработки видеоданных //Локальные вычислительные системы и распределенная обработка данных: Межвуз. сб. научн. трудов / под ред. Малявко А.А., Новосиб. электротехн. ин-т, Новосибирск, 1989, c. 66-73.

Все статьи автора «Овчеренко Владимир Александрович»