Классификация, распознавание и идентификация объектов по гидроакустическим сигналам на основе сортировки

Прибор в портативной модификации конструктивно выполнен в виде металлического чемодана, в котором закреплен переносной компьютер. Предусмотрено как питание от сети 220 В, так и автономное питание от встроенных аккумуляторов. В состав прибора также входит универсальный 48-канальный коммутатор с автоматическим управлением, позволяющий последовательно проводить измерения подключенных преобразователей. Эта модификация ориентирована на применение непосредственно на объектах, например для контроля преобразователей многоэлементных корабельных гидроакустических комплексов.

По сравнению с использованием стандартных средств измерений применение прибора «Цензурка» имеет следующие преимущества:

малые габариты и вес, наличие портативной модификации;

измерение и вычисление большого числа параметров;

возможность расширения перечня измеряемых параметров в соответствии с конкретным приложением прибора;

высокая производительность;

возможность сохранения результатов измерений в базе данных и автоматической отбраковки образцов по результатам измерений.

Таким образом, можно сделать следующие выводы:

1. Предложен новый подход к измерению параметров пьезопреобразователей, использующий современные способы цифрового формирования и обработки сигналов.

2. Разработаны и производятся измерительные приборы, основанные на реализации этого подхода. Имеются лабораторная модификация для стационарных применений и портативная для измерений на объектах.

3. Возможны модификации прибора, учитывающие конкретные особенности эксплуатации и требования потребителей.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Пьезокерамические преобразователи: Справочник / Под ред. В.В. Ганопольский, Б.А. Касаткин, Ф.Ф. Легуша, Н.И. Прудько, С.И. Пугачев. - Л.: Судостроение, 1984. -256 С.

КЛАССИФИКАЦИЯ, РАСПОЗНАВАНИЕ И ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ ПО ГИДРОАКУСТИЧЕСКИМ СИГНАЛАМ НА ОСНОВЕ СОРТИРОВКИ

Я. Е. Ромм, А. И. Дордопуло

ОКБ «РИТМ»

Таганрогский государственный радиотехнический университет

Излагается метод распознавания и идентификации малоразмерных объектов по необработанным сигналам гидролокации. Существо метода основано на идентификации экстремумов входных сигналов на основе сортировки. Поэтому первоначально метод описывается и иллюстрируется на решении математической задачи нахождения нулей многочлена.

Базовая схема сортировки, локализации и вычисления действительных нулей многочленов. Используется быстрая сортировка, основанная на адресном слиянии двух упорядоченных массивов по матрице сравнений:

Последовательный алгоритм слияния выполняется поэлементным обходом в порядке слева направо, сверху вниз неотрицательной области матрицы сравнений. Адрес вставки элемента в выходной массив задается соотношениями

_\bt, если агї =-1, аг(;+1) > 0 _

С’+1 \aj, если а^- >0, а...........................=-1 ajJ

а (i+1) і =-1

1, a j > aj, 0, a j = a i, -1, a j < aj.

где і, і - произвольно взятые индексы при ограничениях и + 1> і > 0 < і < т +1; п, т соответственно, число элементов упорядоченных массивов Ь и а; с - массив, получаемый в результате их слияния; а у - элемент і-й строки и у-го столбца матрицы

сравнения; при этом а располагается на входе таблицы горизонтально сверху, Ь -

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

Нахождение нулей многочлена. На вход процедуры сортировки подается последовательность значений модуля многочлена на равномерной сетке, взятой на начальном промежутке конечной длины. К выходу процедуры подсоединяется условный оператор, локализующий после выполнения сортировки все минимумы среди этих значений - минимумы совпадают с искомыми нулями многочлена. Данный оператор (ниже оператор локализации минимума) имеет вид

—Ю 2 3 3 4 ю

—ю 0 + + + + +

3 - - 0 0 + +

4 - - - - 0 +

4 - - - - 0 +

5 +

Ю 0

Рис.1. Матрица сравнений

k:=1;

WHILE k<= nn0 DO BEGIN

FOR r := 1 TO k-1 DO IF ABS(e[k]-e[k-r]) <= eps0 / h THEN GOTO 22; xk:= x0+e[k]*h;

22: k:=k+1 END;

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

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

довательности (модуля многочлена на сетке), предшествующие с^[к]] в отсортированном массиве. Иными словами, выявляется в[к], для которого

ABS(x0 + e[к]*h -(x0 + e[к -r]*h)) = ABS(e[к]-e[к-r] )*h > eps0

V r = 1,2, ..., к -1.

Это означает, в частности, что модуль многочлена в узле x0 + в[к]* h не больше значений в остальных узлах его eps0 -окрестности, точнее - строго меньше, или это значение является первым слева направо среди равных элементов на выходе отсортированного массива. При выполнении (2) с^[к]] является в данной окрестности наименьшим в смысле отношения порядка <, что не полностью совпадает со смыслом арифметического неравенства. Среди узлов с равными значениями модуля многочлена в рассматриваемой окрестности - при истинности условия (2) - оператор локализации минимума фиксирует узел, соответствующий первому в порядке нумерации элементу отсортированного массива, независимо от его расположения на сетке. Этот факт опирается на устойчивость сортировки - под устойчивостью понимается сохранение порядка равных элементов [ 4 ]. Локализовать минимальный элемент в рассматриваемом смысле предлагаемым способом можно только при сохранении обратных адресов на выходе сортировки, причем строго в том порядке, в каком располагаются отсортированные элементы.

Аналогично обосновывается работа оператора локализации максимума, при этом максимум также понимается в смысле отношения порядка. Различия лишь в знаке при просмотре очередного элемента массива в условном операторе:

IF ABS(e[k]-e[k + r]) <= eps0 / h THEN GOTO 222.

То, что значение параметра eps0 не должно достигать половины расстояния между ближайшими друг к другу нулями многочлена, следует из построения оператора локализации. В остальных отношениях значение eps0 произвольно, но должно быть выбрано и зафиксировано априори.

Обоснование изложенного метода опирается на принцип максимума модуля [7], согласно которому функция 1/| Pn (x) | не может иметь максимума внутри области своей аналитичности - вне окрестности нулей многочлена Pn (x) - все минимумы модуля этого многочлена совпадают с его нулями. Описание метода для случая комплексных корней многочлена и для функции двух действительных переменных содержится в [6].

Алгоритмический смысл и приложения оператора локализации экстремумов. В процедуре сортировки индексы сортируемых элементов входного массива с запоминаются в виде элементов е[к], их массив формируется на выходе процедуры. При этом индекс к = 1, 2, ... , nn0 задает нумерацию отсортированных по неубыванию элементов. Оператор локализации обрабатывает непосредственно элементы е[к]. Истинность условия внутри оператора означает, что узел с номером е[к - г] находится в eps0 -окрестности узла с номером е[к] среди узлов равномерной сетки с шагом h. Но е[к - г] взаимно однозначно соответствует элементу с^[к - r]], предшествующему с^[к]] в отсортированном массиве. Отсюда с [e [к - r]] < с [e [к]]. Поэтому с^[к]] не

является минимальным элементом входной последовательности в данной окрестности. Напротив, ложность рассматриваемого условия означает, что узел с номером е[к

- r] лежит вне eps'0-окрестности узла с номером е[к]. Если ложность сохраняется для всех r = 1,2,..., к -1, то ни один узел, которому бы соответствовало с [e [к - r]] < с [e [к]] , не попадает в рассматриваемую окрестность. Поэтому на

узлах данной сетки в eps0-окрестности узла с номером е[к] элемент с^[к]] оказывается минимальным.

Таким образом, локализуется минимальный (в смысле отношения порядка) элемент в рассматриваемой окрестности. Локализованный элемент может оказаться первым (наименьшим) в цепочке равных. Если к = 1, то оператор локализует минимальный в том же смысле элемент с^к]] входной последовательности среди ее элементов, отсчитанных на целую часть eps0 влево и вправо от номера е[к]. При eps0 = 1 локализуется минимальный в данном смысле элемент по отношению к двум ближайшим слева и справа.

Аналогично, по условию локализации максимума локализуется максимальный (в рассматриваемом смысле) элемент.

Фактическая точность, с которой выполняется требуемая локализация, ограничивается только форматом и диапазоном представления чисел, а также особенностями оцифровки сигналов, поскольку для локализации экстремумов используются лишь операции сравнения. Использование данной схемы позволяет не прибегать к методам математического сглаживания входных сигналов, что влечет возможность повышения достоверности результатов их обработки. Схема не накапливает погрешности и отличается параллелизмом.

Рассматриваемая локализация экстремумов при распознавании (в частности, изображений) дает возможность выделить наиболее контрастные отличительные особенности рядом расположенных сходных фрагментов и на этой основе выделить существенный признак объекта. Такой возможностью и по построению подход отличается [ 8, 9 ] от известных методов распознавания.

Распознавание и идентификация объектов по данным гидроакустической локации. Алгоритмическая схема включает следующие шаги.

1. На вход сортировки поступает последовательность амплитудных значений сигналов локации, взятых отдельно на текущей посылке (посылки просматриваются упорядоченно - слева направо, сверху вниз). Локализуются все максимумы в eps0-окрестности, eps0 - параметр, постоянное значение которого выбирается между 10 и 20 отсчетами.

2. В качестве атомарного объекта (на одной посылке) выбирается максимум и прилегающие к нему на к 0 отсчеты сверху и снизу, где к 0 - параметр, постоянное

значение которого выбирается между 2 и 5.

3. Текущий объект, получаемый в результате аналогичной обработки на следующей по порядку посылке, образует объединенный объект с объектом предшествующей посылки, если расстояние между ними не превышает значения k1 отсчетов.

4. Объект исключается из списка хранимых, если его максимальный размер по вертикали или по горизонтали превышает значение параметра с , где с < 12 , однако исключение объекта возможно при том и только при том условии, что объект не имеет допустимого значения описываемой ниже характеристики (3), вычисляемой по трем последующим пунктам (5,6,7), или объект не имеет допустимого значения гладкости его поверхности, характеризуемого из пункта 10.

5. С отступом от объекта на единицу выделяется замкнутая вокруг него контурная полоса шириной в один пиксель на графическом отображении.

6. Вычисляется сумма 5 всех максимумов на объекте и сумма я0 всех максимумов на окружающей объект полосе. Составляется отношение г =—. Такие отно-

50

шения составляются и нумеруются в зафиксированном порядке следования отсчетов и посылок, образуя числовую последовательность

к

к = 0,1,2,...,N .

7. Последовательность (3) подается на вход сортировки, после которой обрабатывается оператором локализации максимумов при eps0 = 1. Тем самым выделяются объекты, для которых имеет место отделенность от других элементов среды и такая отделенность обладает наибольшей контрастностью. При этом учитывается, что оператор локализации максимумов на основе сортировки располагает максимумы по возрастанию, так что значения элементов (3), соответственные наиболее контрастно отделенным объектам, окажутся в конце выходной последовательности, располагаясь по возрастанию.

8. Теперь достаточно просмотром в обратном порядке выделить объекты с уровнем контрастности, выше порогового значения, чтобы выделить все искомые объекты.

9. Однако среди них окажутся и те, которые не соответствуют объектам искусственного происхождения. Отделить одни от других можно в том случае, если поверхность искусственных объектов отличается машинной шлифовкой. Определить последнюю можно, взяв сумму всех максимумов на объекте, произведя вычитание из нее суммы всех минимумов на объекте и поделив полученное на уменьшаемое с целью нормировки:

Чем ближе значение (4) к нулю, тем более гладкая поверхность объекта. Чем ближе значение (4) к единице, тем менее гладкая у него поверхность.

10. Выполняя пункт 8, проделаем идентификацию минимумов сопоставленных объектам чисел (4).

11. При совпадении у объекта максимума отделенности с минимумом (4) (максимумом гладкости) объект отображается как единственный, иначе он считается ложным.

Ниже приводится иллюстрация работы метода (рис. 2 - 5).

•лйл Сеъогты Паримтрм Отеврпан П*аар*

«*4л 06>тты Пораиатры Отоврапт*

Рис. 2. Исходное изображение сигнала гидролокации

Рис. 3. Состояние после 1 этапа метода

Рис. 4. Состояние после 2 этапа ме- Рис. 5. Состояние после 3 этапа

тода

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. Ч.1 // Кибернетика и системный анализ. - 1994. - № 5. - С.3-23.

2. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. 4.II // Кибернетика и системный анализ. - 1995. - № 4. - С.13-37.

3. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. - М.: Мир, 1978. - 844 с.

4. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360 с.

5. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. Ч.1 // Кибернетика и системный анализ. - 2001. - № 4. - С.142-159.

6. Ромм Я. Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. 4.II // Кибернетика и системный анализ. - 2001. - № 5. - С.81-101.

7. Маркушевич А.И., Маркушевич Л.А. Введение в теорию аналитических функций.

- М.: Просвещение, 1997. - 320 с.

8. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений. - В кн.: Распознавание. Классификация. Прогноз. Математические методы и их применение. Вып.2. - М.: Наука, 1989. - С. 5 -72.

9. Ronald Duncan A., Rerret David I. Manipulating facial appearance trough shape and color // IEEE Comput. Graph. and Appl. - 1995, - 15, №5. - pp. 70 -76.