HIGH-PERFOMANCE TOOLS OF INTELLIGENT SOFTWARE SUPPORT IN THEORETICAL AND APPLIED IMAGE PROCESSING PROBLEMS

Abstract

The work describes approaches to solving image processing tasks based on the use of highperformance algorithms. The original methods are described developed for the calculation of exact analytical formulas for the probability of error-free reading of random discrete fields and digital images with the help of limit-threshold-level integrators. The solution of problems related to the high-precision localization of the coordinates of impulse point objects is described.

Keywords

• high-performance computing
• random image
• computer analytical calculations
• pulse

-

Резник А.Л., Соловьев А.А., Торгов А.В.

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

Ключевые слова: высокопроизводительные вычисления, случайное изображение, компьютерные аналитические выкладки, импульсные объекты.

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

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

Оценка надежности считывания случайных дискретных полей и цифровых изображений с помощью интеграторов, имеющих ограниченное число пороговых уровней. При регистрации координат малоразмерных (в идеале – точечных) объектов, формирующих случайное поле, сбой наступает в тот момент, когда количество объектов, попадающих в пределы сканирующей апертуры, превысит заданный пороговый уровень. В базовом варианте, когда анализируемое изображение формируется случайным пуассоновским потоком постоянной интенсивности, двумерная задача оценивания вероятности того, что процесс регистрации будет проведен без сбоев, легко сводится (это достигается посредством стандартной факторизации) к следующей простой по постановке одномерной вероятностной задаче: "Требуется найти вероятность того, что при случайном бросании n точек на интервал (0,1) не будет образовано ни одной -группировки, содержащей более k точек.” Кажущаяся простота сформулированной задачи является иллюзорной, поскольку уже при k=2 ее решение настолько усложняется, что требуется специальный подход, включающий в себя создание методов и алгоритмов аналитического манипулирования с последующей их реализацией в виде нескольких программных систем. Кроме того, для проведения математически строгого обоснования отыскиваемых с помощью ЭВМ формул возникает необходимость применения обобщенных чисел Каталана с предварительным нахождением их явного вида. Решение задачи состоит из нескольких этапов.

Этап 1. Получение частных решений главной задачи с помощью программ машинной аналитики. Точное решение приведенной выше задачи известно лишь для простейшего частного случая, когда k=1 [ 2 ]:

Pn,1( )  (1  (n 1) )n, (0  1/(n 1)).

(1) Фактически формула (1) описывает вероятность того, что при случайном бросании n точек на интервал (0,1) все выброшенные точки «разлетятся» между собой на расстояние, превышающее ε. Формулу (1) можно найти различными способами. Например, в [ 2 ] она получена в результате вычисления легко интегрируемого повторного интеграла

1  xn  x4  x3 x2   Pn,1( )  n!  dxn   dxn1  dx3   dx2   dx1 .

(n1) (n2)  2    0  В [ 2 ] нами предложен простой вероятностно-геометрический метод, позволяющий получить решение (1), не прибегая к процедуре многомерного интегрирования. Таким образом, решить задачу, когда k=1, не представляет труда. Гораздо сложнее продвигаться в решении этой же задачи при k>1.

Для нахождения точного аналитического решения при k=2 нами были разработаны несколько методов [ 3-7 ]. Один из них позволил найти полный набор частных формул Pn,k(ε) во всех диапазонах изменения непрерывного параметра ε для всех фиксированных значений целочисленных параметров n и k вплоть до n=14. Отметим, что их вычисление сопряжено с огромным числом рутинных, но весьма трудоемких операций расстановки пределов интегрирования, проверки промежуточных систем линейных неравенств на совместность, непосредственного интегрирования в n-мерном пространстве и объединения результатов, что сделать «вручную» уже при n=4 практически нереально.

Более того, при увеличении размерности интегрируемых выражений свыше n=12 нам потребовалось разработать специализированную программную систему для вычислительного кластера, использующую параллельные вычисления, поскольку получить результат на обычном персональном компьютере было невозможно.

Этап 2. Нахождение общих закономерностей. На следующем этапе мы попытались с помощью анализа полученных частных результатов установить и по возможности доказать общие закономерности образования вероятностных формул Pn,k(ε) для случая k>1, если таковые удастся выявить. И ряд таких аналитических закономерностей действительно был обнаружен, а впоследствии и строго доказан. Мы попытались по аналогии с формулой (1), справедливой для k=1, найти общее решение Pn,k(ε) для k=2. К сожалению, эта задача оказалась намного сложнее, чем представлялось до начала исследований. Это связано в первую очередь с тем, что, в отличие от случая k=1, вероятность Pn,k(ε) состоит не из одного, а из нескольких кусочно-однородных фрагментов, непрерывно состыкованных в точках «склейки». Во-вторых, сама формула Pn,k(ε) видоизменяется в зависимости от четности n. В-третьих, нахождение закономерностей на каждом из диапазонов изменения параметра ε требует создания индивидуального подхода, который часто сводится к собственной и зачастую весьма сложной дискретно-вероятностной задаче. В предложенной нами схеме редукции во всех подзадачах (т.е. во всех диапазонах изменения параметра ε) возникают обобщенные числа Каталана. Знание их явного вида требуется при упорядочении взаимозависимых случайных числовых последовательностей. И хотя при этом все элементы анализируемых последовательностей являются случайными равномерно распределенными вещественными величинами, задачи с обобщенными числами Каталана оказалось удобнее ставить и решать в словарно-лингвистической форме [7].

Этап 3. Доказательство и общий вид формул Pn,k(ε), найденных с использованием программных, аналитических и дискретно-комбинаторных алгоритмов. Для вероятностей Pn,k(ε) в случае k=2 нам не удалось найти замкнутую аналитическую формулу, подобную формуле (1) для k=1. Однако с использованием всех перечисленных выше компьютерных и дискретно

1

P2m,2 ( )  m  1 C2mm (1  (m  1) )2m ; для четных значений n=2m на участке

1 m  1    1 установлена формула

m P2m,2 ( )  C2mm (1 (m 1) )2m  C2mm1(1 (m 1) )2m   C2mm2 (1 m )m2 (1 (m  2) )m2   2C2mm3 (1 m )m3 (1 (m  2) )m3  C2mm4 (1 m )m4 (1 (m  2) )m4;

m  1 P2m1,2 ( )  C2mm11(1 m )m1(1 (m 1) )m   2C2mm21(1 m )m2 (1 (m 1) )m1   C2mm31(1 m )m3(1 (m 1) )m2. для нечетных значений n=2m+1 на участке 1    1 установлена формула m (2) (3) (4) Детальное изложение вычислительных схем, с помощью которых были рассчитаны приводимые формулы, можно найти в [ 1,3-7, 9-10 ].

Высокопроизводительные алгоритмы локализации случайного точечно-импульсного источника. При цифровой регистрации и последующей программной обработке быстропротекающих динамических процессов различной физической природы один из наиболее трудоемких и алгоритмически сложных моментов связан с устранением импульсных помех, создаваемых точечными источниками со случайным пространственным распределением. Для успешного решения таких задач требуется высокоточное определение координат объектовисточников излучения, причем в большинстве практически важных приложений сделать это необходимо за минимальное (в статистическом плане) время. Под точечно-импульсным источником ниже будет пониматься объект пренебрежимо малых угловых размеров (математическая точка), имеющий случайное расположение на оси X и генерирующий в случайные моменты времени бесконечно короткие импульсы (дельта-функции). Поиск объекта ведется с помощью регистрирующего устройства (приемника) с произвольно перестраиваемым во времени окном обзора. Импульс фиксируется, если точечный источник в момент генерации импульса находится в окне обзора приемного устройства. В противном случае импульс считается пропущенным. При регистрации очередного импульса происходит уточнение положения источника на координатной оси, в результате чего интервал поиска сужается, а процедура локализации повторяется до фиксации следующего импульса, и т.д. Необходимо за минимальное время найти источник, обеспечив при этом заданную точность локализации. В математическом плане задачи и алгоритмы оптимального поиска случайных точечно-импульсных объектов, обсуждаемые в настоящем сообщении, возникают во многих научно-технических приложениях. В частности, в задачах технической диагностики [11], в математической теории связи [12] и в теории надежности [13] подобные исследования требуются при разработке методов устранения неисправностей, проявляющихся в виде перемежающихся отказов; в астрофизике и космологии [14] с такими проблемами сталкиваются при поиске барстеров – вспыхивающих галактических рентгеновских источников; в современных разделах информатики эти методы востребованы при построении алгоритмов обнаружения слабоконтрастных и малоразмерных объектов на зашумленных цифровых изображениях [15], а, к примеру, в теории сигналов эти методы используются для оценивания надежности регистрации случайных точечных полей [1,16]. Сложность решения задач, связанных с построением оптимальных по быстродействию алгоритмов поиска случайных точечно-импульсных источников, объясняется тем, что в подавляющем большинстве практически важных приложений приходится отыскивать экстремали интегральных уравнений, не имеющих точного аналитического решения. Но в том случае, когда не имеется никаких априорных сведений о вероятном расположении разыскиваемого источника внутри интервала поиска, задача значительно упрощается и удается найти оптимальное решение не только для поисковых систем с одним приемным устройством, но и для систем с произвольным числом приемников. Параметры оптимальных поисковых алгоритмов, которые рассчитаны в зависимости от количества приемных устройств в системе и требуемой точности локализации, можно найти в [17].

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

Заключение. Настоящая работа служит хорошей иллюстрацией того, что большинство современных прикладных задач обработки изображений требуют для своего решения весьма серьезной алгоритмической и программно-интеллектуальной поддержки. Так, при решении задач, связанных с безошибочной регистрацией случайных точечных изображений, нам потребовалось создать специализированные программные системы для аналитических преобразований с использованием параллельных вычислений, а также применить новое многомерное обобщение чисел Каталана. Компьютер при этом играл роль интеллектуального «помощника», оснащенного современными средствами для скоростного проведения громоздких аналитических преобразований, связанных с циклически повторяющимися операциями многомерного интегрирования в n-мерном пространстве. Эффективность предложенных методов позволяет надеяться на дальнейшее продвижение в решении описанных в данной работе задач.

Представленное исследование выполнено при частичной поддержке Российского фонда фундаментальных исследований (проект № 16-01-00313), Российской Академии наук (проект № 224 Программы Президиума РАН I.5П) и Сибирского отделения РАН (проект СО РАН – НАН Беларуси № 24/2015).

ЛИТЕРАТУРА [7] Резник А.Л., Ефимов В.М., Соловьев А.А. Оценивание надежности считывания случайных дискретных изображений с применением средств компьютерной аналитики. // Сибирский физический журнал. 2010. Т. 5, № 2, С. 104-110. [8] Резник А.Л. Моделирование на ЭВМ непрерывного считывания изображений дискретной структуры. // Автометрия. 1981. № 6, С. 3-6. [9] Reznik A.L., Efimov V.M., Torgov A.V., Soloview A.A. Analytical computer calculations in problems with random division of an interval. // Pattern Recognition and Image Analysis (Advances in Mathematical Theory and Applications). 2012. Vol. 22, N 2, P. 354. [10] Резник А.Л., Ефимов В.М., Соловьев А.А., Торгов А.В. О безошибочном считывании случайных дискретно-точечных полей // Автометрия. 2012. Т. 48, № 5, С. 93. [11] Биргер И.А. Техническая диагностика. М.: Машиностроение, 1978. 240 с. [12] Shannon C.E. A Mathematical Theory of Communication // Bell System Technical Journal. 1948.

Vol. 27, P. 379-423, 623-656. [13] Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности // М.: Наука, 1965. 524 с. [14] Weinberg S. Cosmology. N.Y.: Oxford University Press, 2008. 593 p. [15] Kirichuk V.S., Mokin K.Yu., Reznik A.L. Algorithms for Processing of Series of Digital Aerospace Images Based on Automatic Search for the Conjugate Points // Pattern Recognition and Image Analysis. 2001. Vol. 11, N 1, P. 192-194. [16] Reznik A.L., Soloviev A.A., Torgov A.V. On the Probability of the Formation of Local Groups in Random Point Images // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. 2016. Vol. 26, N 4, P. 714-719. [17] Резник А.Л., Тузиков А.В., Соловьев А.А., Торгов А.В. Оптимальные по быстродействию алгоритмы поиска случайных импульсно-точечных источников для систем с несколькими приемными устройствами // Автометрия. 2017. Т. 53, № 3, С. 3-11.

References

[2] Parzen E. Modern Probability Theory and Its Applications . N.Y.-London: John Wiley and Sons, 1960 . 464 p.

[4] Reznik A.L. , Efimov V.M. , Soloview A.A. , Torgov A.V. On the reliable redout of random discrete-point structures . // Pattern Recognition and Image Analysis (Advances in Mathematical Theory and Applications) . 2015 . т. 25 . № 1, С. 84 - 88 .