Geum.ru

Цифровая обработка многомерных сигналов

Вид материалаЛитература

Содержание


Variants of graphical algorithm implementation for spreading of oil pollution for the tasks of environmental monitoring
Распознавание состояний динамической системы
1. Постановка задачи распознавания технического состояния ЭМС.
2. Решение задачи.
2.1. Построение информационного признакового пространства.
2.2. Оценивание информативности эталонов.
2.3. Алгоритмы распознавания состояний ЭМС.
2.3.1. АР состояний ЭМС на основе модифицированного метода «ближайших соседей»
2.3.2. АР состояний ЭМС на основе модифицированного метода эталонов.
2.4. Оценивание качества АР.
2.5. Принятие итогового решения.
Recognition of dynamic system states
Алгоритм построения интегральной картины распределения спектральных особенностей микрообъекта
Recent advances in nonlocal image processing techniques
Сравнение алгоритмов, применяемых при локализации в беспроводных сенсорных сетях
Подобный материал:

Цифровая обработка многомерных сигналов

Выводы


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

Литература

  1. James W. Weaver. Characteristics of Spilled Oils, Fuels, and Petroleum Products: 3a. Simulation of Oil Spills and Dispersants Under Conditions of Uncertainty., Ecosystems Research Division National Exposure Research Laboratory ,Athens, Georgia 30605
  2. Buckmaster. Viscous-gravity Spreading of on oil slick. J. Fluid Mech., vol. 59, 1973.
  3. Белов М.Л и др. Радиофизический мониторинг загрязнений природной среды Издательство, М.: «Аргус» 1994 г.
  4. Втюрин С.А., Чобану М.К., Построение прогнозных моделей развития экологических событий с учетом данных дистанционного зондирования Земли из космоса. М., 10я Международная конференция Цифровая обработка сигналов и ее применение- 2008, Институт проблем управления РАН.
  5. Оптико-электронные системы экологического мониторинга природной среды. Под ред. В.Н. Рождествина, М.: Издательство МГТУ имени Н.Э. Баумана, 2002.


Variants of graphical algorithm implementation for spreading of oil pollution for the tasks of environmental monitoring

Vturin S.

Space Research Institute RAS

The report explore various options for graphic algorithm implementation intended to simulate the spread of oil pollution in the framework of the work to build predictive models of development of environmental events using materials for Aerospace imaging and mapping of the input data and results on a digital map.

A comparative analysis of the applicability of different algorithmic implementations with different tolerances and simplified model of the movement of oil slick on the water surface under the action of wind, currents and the oil spill.

As initial data for modeling the images received from various satellites (NOAA, TERRA, AQUA, LANDSAT, SPOT, etc.), the images received at aerial photograph (the form of a slick, an estimation of thickness of an oil film), and also accessible to the chosen events and areas of space shooting ground measurements (speeds and directions of a wind and flow), and additional data from a place of event (character of flood, capacity of a source, an estimation of volumes and duration of flood of substance) can be used.

The report explore the overall structure of the algorithm and the key features of the various options of the procedure for graphic calculating of spreading and drifting oil pollution area on the surface of the water.

Calculating on the raster-based data representation has such advantages as the possibility of processing areas of the complex forms, while maintaining the ease of implementation, possibility of graphical calculation in the original dimension of the raster, but gives a rough assessment of the change in pollution shape and have worse scalability (increasing the size of the area definition lead to much more time of calculation or reducing the accuracy).

Vector model of data representation enable to construct an algorithm, which is in a significant number of real examples, have less computational complexity (but not constant), makes it easier to take into account the change in the area of pollution, and more scalable, but requires more sophisticated algorithms, and imposes restrictions in the form of pollution. It should be noted that, in order to more accurately forecast change in the area of pollution requires use of a more detailed input data (maps of current and wind).

On the basis of these characteristics given recommendations on the range of application of each of the realizations:
  • Raster model may be more suitable for rapid on-line forecasting and assessment of pollution, perhaps with a lacks of input data.
  • Vector version is more suitable for accurate simulation while the design and explore potential sources of pollution.

In the report presented some examples of predictive modeling for imitation of oil pollution of water, based of sample images with thematic preprocessing.





РАСПОЗНАВАНИЕ СОСТОЯНИЙ ДИНАМИЧЕСКОЙ СИСТЕМЫ1

Колесникова С.И., Букреев В.Г.

Томский политехнический университет

Введение в проблему. Пусть задан случайный процесс (СП) , характеризующий состояние динамической системы (ДС) (например, электромеханической системы (ЭМС)), функционирующей на интервале времени от до , где − вектор переменных состояния системы; , − случайные наблюдаемые - мерная и -мерная векторные функции, соответственно; − шумы достаточно общей природы. Относительно СП выдвинуто альтернативных гипотез , составляющих полную группу событий и физически интерпретируемых как классы технических состояний (ТС) частично наблюдаемой динамической системы.

Задача состоит в отнесении наблюдаемых (в момент t или на некотором фиксированном интервале ) наблюдаемых реализаций , к классу , . Наблюдение величин , осуществляется в соответствии с дискретным планом , , с шагом дискретизации , по имитационной модели (ИМ) данной ДС.

Сложность практического решения поставленной задачи обусловлена не только наличием возможной нелинейной связи между откликом (выходом) и входным воздействием, но и отклонениями параметров модели от реальных значений (присутствием систематической и несистематической ошибок, неизбежными при моделировании − математическом или имитационном), реальностью времени решения задачи распознавания (диагностики) ТС для последующего управления в реальном времени.

Применение методов теории распознавания образов [1, 2] для решения данной задачи распознавания (диагностики) ТС ДС обосновывается: во-первых, наличием объективной связи между структурой ДС и его ТС, выражающейся в виде , ; во-вторых, адекватным представлением структуры ДС имитационной моделью, на основе которой возможно получение обучающей выборки (ОВ); в-третьих, ТС (или подмножество значений ), «восстановленное» на основе ОВ, может быть соотнесено с реальным поведением ДС.

Несмотря на большое количество методов интеллектуальной обработки диагностической информации (см., напр., [3, 4]) вопрос об идентификации ТС ДС в такой постановке остается открытым. В связи с этим представляют интерес методы качественного исследования нелинейной ДС.

В докладе представлена модель (и реализующий ее комплекс методов и алгоритмов) автоматизированного распознавания (диагностирования) ТС ДС. Осуществляется сравнительный анализ как методов математической обработки «первичных» признаков и оценки их информативности, так и методов окончательного анализа для решения задачи распознавания ТС ДС. Предложена процедура, синтезирующая коллективное итоговое решение на основе нескольких алгоритмов распознавания.

Иллюстративным примером практического применения предложенных процедур и алгоритмов является распознавание ТС ЭМС с частотно-регулируемым электроприводом переменного тока, являющейся основой нижнего уровня управления большинства современных автоматизированных систем в таких отраслях, как нефтегазовая, горнорудная, металлургическая и др. [5, 6].

Предложенные алгоритмы могут быть использованы при организации робастного и адаптивного управления сложными электромеханическими системами [4, 7].

1. Постановка задачи распознавания технического состояния ЭМС. Пусть на основе ИМ ЭМС [6] получена ОВ в виде совокупности , где k − номер реализации СП по ИМ; − интервал наблюдения ИМ СП;   временные интервалы состояний ДС, соотнесенные техническим состояниям ДС (); , − значения первой (цифрового сигнала ) и второй () наблюдаемых характеристик (распознаваемого) состояния ДС в k-й реализации, соответственно; , , .

Известны также следующие ограничения:

1) граничные значения (размах) для наблюдаемого сигнала каждого i-го распознаваемого состояния , т.е. для : ;

2) эталонные значения 2-й наблюдаемой характеристики (распознаваемого) состояния ДС − вектора , известные для каждого i-го распознаваемого состояния , в k-й реализации, .

Задача заключается в распознавании технического состояния ДС по наблюдениям тройки значений − момента времени наблюдения, 1-й и 2-й наблюдаемых характеристик распознаваемого состояния ДС (векторов и ), соответственно. Другими словами, требуется на основе имеющейся ОВ (возможно состоящей из одной реализации СП) и дополнительной априорной информации (заключенной в вышеупомянутых п.п. 1), 2)) решить следующие подзадачи: 1) определить обобщенные характеристические (диагностические) признаки образов (классов) состояний ТС (построить информационное признаковое пространство (ИПП)); 2) на основе выделенного ИПП разработать и обучить соответствующие алгоритмы распознавания (АР) ТС; 3) оценить по контрольной выборке (КВ) качество (надежность) всех АР ТС; 4) построить коллективную процедуру для принятия итогового решения об отнесении наблюдаемых характеристик к одному из выделенных ТС (классов образов состояний).

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

2.1. Построение информационного признакового пространства. За обобщенные характеристические (диагностические) признаки образов (классов) для каждого i-го распознаваемого состояния , примем набор эталонов ТС , , ( − число эталонов для i-го ТС, ), построение которых осуществляется по следующей схеме.

I. Для каждой k-й () реализации сигнала для i-го ТС :

1) фиксируем временные интервалы состояний ДС , значения , значения , соотнесенные выделенным фиксированным техническим состояниям ДС ;

2) задаем «длину» характеристических эталонов (дальше по тексту слово «характеристические» будем опускать) ;

3) формируем эталоны i-го ТС : , где представляет собой последовательность значений длины , , с шагом .

II. По ОВ объема K для всех характеристик ТС АД (являющихся параметрами оптимизации) получаем усредненные оценки всех величин ; ; , , .

III. Определяем весовые коэффициенты эталонов и ТС по одному из методов, приведенных в работе [8].

2.2. Оценивание информативности эталонов. Традиционно в качестве критерия информативности признаков используется доля правильно распознанных объектов обучающей выборки методом Cross – Validation. Поскольку распознаваемые классы (ТС) имеют «вытянутый» вид вдоль временной оси, то целесообразно за оценку информативности признаков принять сумму величин , где n − число объектов в обучающей выборке, и − расстояния j-го объекта из ОВ до ближайшего объекта своего образа и до ближайшего объекта образа-конкурента, соответственно; и − максимальное и минимальное расстояния между объектами ОВ [9].

2.3. Алгоритмы распознавания состояний ЭМС. Рассматриваемый подход к решению поставленной задачи опирается на классические детерминированные (метрические) методы РО (метод эталонов, метод «ближайших соседей»), модифицированные и адаптированные к специфике ОВ рассматриваемой задачи с учетом нечетких границ между ТС. Особенностью подхода является использование нескольких АР для последующего синтеза итогового решающего правила об отнесении наблюдаемого сигнала к одному из выделенных ТС АД (совместное использование в едином решающем правиле разнотипных моделей является одним из способов повышения надежности распознавания) и функции конкурентного сходства [10]. Показано, что применение данной функции целесообразно в условиях нечетких границ между ТС ДС.

2.3.1. АР состояний ЭМС на основе модифицированного метода «ближайших соседей». Метод «ближайших соседей» (МБС) будет применяться в форме, продиктованной спецификой не только ОВ, но и способом выбора характеристических эталонов ТС ДО, представляющих собой подмножества значений двух характеристик и . В отличие от классического МБС [1, 2], где выносится решение в пользу одного класса, в результате применения модифицированного МБС получают возможные «частные» конкурирующие решения, на основе которых агрегируется итоговое решение.

2.3.2. АР состояний ЭМС на основе модифицированного метода эталонов. Для распознавания ТС ЭМС по наблюдаемому значению сигнала определяются расстояния от него до всех эталонов, выбираются ближайшие два эталона из разных классов, и по расстояниям до них вычисляются значения функции конкурентного [10] сходства. Решение принимается в пользу того класса, где значение функции максимально.

2.4. Оценивание качества АР. В качестве значения функции весового коэффициента -го АР () берется отношение числа правильных ответов к общему объему КВ.

2.5. Принятие итогового решения. На основе предложенного алгоритма агрегирования полученных «частных» (возможно, и противоречивых) голосов за номер (метку) класса , к которому предлагается отнести распознаваемый сигнал по -му АР, осуществляется синтез итогового решения в пользу одного ТС ЭМС.

Заключение. В докладе рассмотрена технология принятия решения о распознавании (идентификации) технического состояния динамической системы по наблюдаемым характеристикам с целью использования этого знания для осуществления управления ДС по интегрированному параметру (его техническому состоянию). Технология основана на адаптированных к предметной области методах распознавания образов и специальных мер оценивания конкурентных состояний ДС на примере ЭМС. Дальнейшее развитие данной технологии авторы связывают с расширением банка методик (и реализующих их алгоритмов) на основе методов анализа (идентификации и классификации) частично наблюдаемых случайных процессов и включением разработанных АР ТС ДС в коллективную процедуру для вынесения итогового решения, что должно повлиять на повышение качества распознавания технического состояния ДС и управления процессами ДС.

Литература
  1. Ту Дж., Гонсалес Р. Принципы распознавания образов / Пер. с англ. Под ред. Ю.И. Журавлева. М.: Мир, 1978. – 411 с.
  2. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Изд. ИМ СО РАН, Новосибирск, 1999 г. – 273 с.
  3. Коровин С.К. Стабилизация при неопределенности и робастное обращение динамических систем // Информационные технологии и вычислительные системы. – 2002. – № 2. – С. 11–31.
  4. Павленко В.Д., Фомин А.А. Комбинированный метод построения решающего правила статистической классификации // Электронное моделирование. 2001. – № 4. – С. 34–39.
  5. Лаходынов В.С., Букреев В.Г. Синтез наблюдателя состояний для оценки частоты вращения погружного электродвигателя электроцентробежного насоса // Сб. докладов Росс. конф. с межд. уч. «Технические и программные средства систем управления, контроля и измерений» УКИ’08. – 2008. – №4. – С. 433–438.
  6. Изосимов Д.Б., Рывкин С.Е. Идентификация частоты вращения и составляющих вектора потокосцепления ротора асинхронного двигателя по измерениям токов и напряжений обмоток статора // Электричество. – 2005. – №4. – С. 32–40.
  7. Поляк Б.Т., Щербаков П.С.  Робастная устойчивость и управление. М.: Наука, 2002. – 303 c.
  8. Колесникова С.И., Янковская А.Е. Оценка значимости признаков для тестов в интеллектуальных системах // Известия РАН. Теория и системы управления. – 2008. – № 6. – С. 135–148.
  9. Kira K., Rendell L. The Feature Selection Problem: Traditional Methods and a New Algorithm // Proc. 10th Nat’l Conf.Artificial Intelligence (AAAI-92). – 1992. – p. 129–134.
  10. N.G. Zagoruiko, I.A. Borisova, V.V. Dyubanov, and O.A. Kutnenko. Methods of Recognition Based on the Function of Rival Similarity // Pattern Recognition and Image Analysis, 2008. – Vol. 18. – No.1. – pp.1–6.



RECOGNITION OF DYNAMIC SYSTEM STATES

Kolesnikova S., Bukreev V.

Tomsk Polytechnic University

Let there be given a stochastic process (SP) that defines a state of dynamic system (DS) (for example, an electromechanical system (EMS)) operating on a time gap , where − is the vector of the system state variables; , − random observable - dimensional and - dimensional vector functions respectively; − noises of rather general origin. In relation to the (SP) let there be put forward alternative hypotheses constituting the complete state-event group, and interpreted as technical states (TS) of partially observed (DS).

The goal is to refer the observed events , to the class, . Observation of the values, is carried out in accordance with the discrete plan , of sampling , under the simulation model (SM) of (DS) in question.

The model (and providing assembly of methods and algorithms) of automated recognition (diagnostics) of (TS) for (DS) are given in this paper. Comparative analysis is given just as of the mathematical processing of “initial” signs and their information content evaluation, so of final analysis methods for resolving the problem of recognition (TS) of (DS).

A possibility to use in practice suggested procedures and algorithms has been shown on the example of (TS) recognition for the (EMS) with a frequency controlled AC drive, what is a base of low control level for the majority of modern automatically controlled systems in such fields as oil and gas, mining, metallurgic industries and others.

On a base of learning sample (possibly consisting of only one (SP) realization), and additional prior information presented as boundary values for the observed signal , and reference data of other observed characteristic for i-th (TS) being recognized in k-th realization, the following problems have been resolved:

1) generalized characteristics (diagnostic) signs of the (TS) patterns (classes) have been defined; 2) on a base of given information feature space the recognition algorithms (RA) for (TS) have been developed. In the course of their developing, on the (EMS) example, the methods of pattern recognition adapted to the objects range and special measures (metrics) for evaluation of concurrent states (DS) were applied; 3) the collective procedure have been set up to accept the final decision about referring observable characteristics to one of the given (TS) (classes of pattern states) taking into account a grade of reliability (RA) of (TS) evaluated by a test sampling.

Further development of suggested technology for (TS) (DS) recognition (represented as an assembly of procedures and algorithms) authors connect with widening of the (RA) (TS) (DS) bank on a base of analysis methods for partially observable stochastic processes and adoption of received (RA) (TS) (DS) into the collective procedure for the final decision making. The number of algorithms applied to TS DS recognition, being expanded, should enable the recognition and control quality to be enhanced.




Алгоритм построения интегральной картины распределения спектральных особенностей микрообъекта

Мачихин А.С., Пожар В.Э.

Научно-технологический центр уникального приборостроения РАН, Москва

Одной из важных проблем, встречающихся в задачах анализа спектральных изображений, является оптимизация обработки информации, что связано с получением больших объемов данных. В этих задачах регистрируемое множество представляет собой гиперкуб данных I(λ,x,y). При этом информативное подмножество имеет существенно меньшую меру. По мере возрастания технических характеристик прибора (ширины рабочего спектрального диапазона, спектрального и пространственного разрешения и пр.) возрастает и объем поступающей информации, что делает невозможным оперативное решение некоторых важных задач реального времени и существенно затрудняет использование видеоспектрометров в ряде приложений.

Одной из задач, часто встречающейся при анализе биологических и других (в том числе и неорганических) объектов, является выявление их спектральных «особенностей». Даже в лабораторных условиях процесс анализа и сравнения спектральных изображений, число которых может достигать 150-200 штук, является рутинным и трудоемким. Поэтому актуальной и перспективной представляется разработка быстрых алгоритмов автоматической обработки спектральных изображений с целью обнаружения и обобщения особенностей и представления их в удобном для дальнейшего анализа виде [1].

В настоящей работе предложен подход к решению данной задачи применительно к акустооптическим (АО) видеоспектрометрам. Их отличает высокое спектральное разрешение (1 3 нм) и широкий диапазон перестройки (280-450 нм, 440-760 нм, 600-1200 нм и т.д.). В основе этих видеоспектрометров лежит программно перестраиваемый АО фильтр (или пара последовательно расположенных АО фильтров). Как показали теоретические и экспериментальные исследования, данный элемент вносит некоторые геометрические искажения в формируемое оптической системой изображение [2,3]. Эти искажения носят спектрально и пространственно зависимый характер и могут быть учтены лишь при условии предварительной калибровки видеоспектрометра [3]. По этой причине непосредственно перед применением каких-либо алгоритмов цифровой обработки спектральных изображений нужно устранить геометрические искажения, вносимые АО фильтром.

Следующей подготовительной процедурой в рассматриваемом методе является выравнивание средней яркости всех полученных спектральных изображений. Данная операция осуществляется посредством приведения гистограммы изображения (распределение пикселей по интенсивности) к заданному виду – фиксированному положению центра гистограммы и ее ширины [4]. Она необходима для повышения эффективности совместной обработки изображений и получения более качественного представления картины спектральных особенностей – без разрывов и артефактов.

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

На заключительном этапе для более наглядного представления и лучшего восприятия результата используются сглаживающая фильтрация.



Рис.1. Схема работы предлагаемого алгоритма

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

Предложенный алгоритм программно реализован и апробирован на реальных спектральных изображениях, полученных с помощью АО видеоспектрометра, изготовленного в НТЦ УП РАН. Программа предусматривает возможность выбора и задания параметров метода пред- и постобработки, выбора типа функционала информативности, а также настройки значений некоторых используемых констант.

На рис. 2,а показан пример работы предлагаемого алгоритма в режиме так называемого «расширенного фокуса», когда за счет совместной обработки изображений можно увеличить глубину резкости системы регистрации. Обработка 6 изображений размером 640×480, полученных при различной фокусировке объектива, предлагаемым методом в автоматическом режиме позволила за несколько секунд сформировать резкое изображение (рис. 2,б) всего объекта, содержащее наиболее контрастные фрагменты всех исходных изображений исследуемого объекта.

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

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


а)

б)

Рис.2. Пример работы предлагаемого алгоритма а) исходные изображения; б) результат работы алгоритма

Литература
  1. Пожар В.Э., Пустовойт В.И.Возможности создания новых систем идения на основе акустооптических видеоспектрометров.// Радиотехника и электроника, 1996, т.41, в.10, с.1272-1278.
  2. Pozhar V.E., Pustovoit V.I. Main features of image transmission through acousto-optical filter. Photonics and optoelectronics, 1997, v.4, No.2, p.67-77.
  3. Пожар В.Э., Мачихин А.С. Исследование характеристик изображений, полученных акустооптическим фильтром. // Прикладная оптика: Сб. тр. 8-й междунар. конф. – СПб., 2008. – Т.3. Передача, восприятие и измерение цвета. – С. 374-376.
  4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. // М.: Техносфера, 2005. ­- 1072 с.


Construction of pattern containing integral distribution of micro object’s spectral peculiarities

Machikhin A., Pozhar V.

Scientific and Technological Center of Unique Instrumentation RAS, Moscow

One of the important problems in spectral images analysis is optimization of information processing. In the practice of biological objects research task of spectral peculiarities revelation is frequently met. That is why development of algorithms for these features extraction and summarizing is present-day and perspective.

Present article is dedicated to solving of this problem with reference to acousto-optic (AO) video spectrometers.

Because of spatially and spectrally dependent distortions caused by AO filter it is necessary to calibrate AO video spectrometer before any digital image processing algorithm application. The second preparation procedure is histogram processing.

The following processing of transformed spectral images is evaluation of functional showing the heterogeneity of each pixel neighborhood. Resulting picture consists of pixels corresponding to the maximum of this functional.

On the final stage roll-off filtering is used for better presentation and perception.

Approbation on real spectral images received by AO video spectrometer shows that developed method gives good results.

Suggested algorithm can be applied to video spectrometer of any other type. Method allows to widen possibilities of these devices while material and objects express-analysis and reduce time of research.





Recent advances in nonlocal image processing techniques

Egiazarian K., Katkovnik V., Foi A.

Department of Signal Processing, Tampere University of Technology,

FIN-33101, Tampere, Finland, firstname.lastname@tut.fi

Nonlocal imaging techniques look for blocks (patches, fragments) which are similar in one or another ways and process these similar blocks jointly. This sort of techniques appear independently (and more or less in parallel) in a number of different developments, in particular as patch-matching proposed exploited for video processing [2] and as nonlocal means (NL-means) in nonparametric regression modeling [1]. A few recent years witness an intensive flow of publications with ideas and techniques based on various nonlocal approximations. It is surprising to some extend that some of these nonlocal developments report very good and some times even extraordinary good performance. While this sort of improvements are not fully understood and theory of these methods is far from being developed, the source of this advanced performance is clear as it originated in the fact that real-life images indeed are characterized by multiple similarity of their fragments. A proper use of this similarity results in the efficiency which was reported in many publications.

The nonlocal imaging techniques mainly spatially adaptive appeared in forms and modifications so different that sometimes it is difficult even to recognize that they belong to the same class of the algorithms.

One of the motivation of this paper is to make a proper classification of the nonlocal technique which can serve as a guideline for orientation in this intensively developing novel area. We review an evolution of the nonlocal modeling in imaging starting from the local Nadaraya-Watson kernel estimate, to NL-means and further to transform-domain filtering based on nonlocal block-matching.

The considered methods are classified mainly according to two main features: local/nonlocal and pointwise/multipoint. These alternatives, though obvious simplifications, allow to impose a fruitful and transparent classification of the basic ideas in the advanced techniques. Here nonlocal is an alternative to local, and multipoint is an alternative to pointwise. In the multipoint case the data are typically processed by overlapping subsets, i.e. windows, blocks or generic neighborhoods, and multiple estimates are obtained for each individual point. The final estimate is obtained by aggregating (fusing) of multiple multipoint estimates. It is found that this sort of redundant approximations with multiple estimates for each pixel dramatically improve the accuracy of estimation.

Within this framework, we discuss different forms of efficient redundant modeling as well as an original single- and multiple-model transform domain nonlocal collaborative filtering approach.

In this paper we present a novel line of our algorithms developed on the base of the nonlocal and local approximation paradigm. These algorithms are indeed very efficient and shows the state-of-the art performance [3-7].

The paper is accompanied by experimental examples where these methods are applied to competitive image processing problems. Applications include image denoising, deblurring (deconvolution), deblocking and deringing, demosaicing, inverse-halftoning, color image processing, etc.

Matlab software, which implements the presented techniques and experiments, is publicly available on the website t.fi/~foi/GCF-BM3D/

References

[1] A. Buades, B. Coll, and J. M. Morel, "A review of image denoising algorithms, with a new one," SIAM Multiscale Modeling and Simulation, vol. 4, pp. 490-530, 2005.

[2] Kervrann : C. Kervrann and J. Boulanger, "Local adaptivity to variable smoothness for exemplar-based image regularization and representation," International Journal of Computer Vision, vol. 79, pp. 45-69, 2008.

[3] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image denoising by sparse 3-D transform-domain collaborative filtering," IEEE Transactions on Image Processing, vol. 16, no. 8, pp. 2080-2095, August 2007.

[4] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "A Nonlocal and Shape-Adaptive Transform-Domain Collaborative Filtering," Proc. 2008 Int. Workshop on Local and Non-Local Approximation in Image Processing, LNLA 2008, Lausanne, Switzerland, 2008.

[5] A. Foi,S. Alenius, M. Trimeche, V. Katkovnik, and K. Egiazarian, "A spatially adaptive Poissonian image deblurring", IEEE 2005 Int. Conf. Image Processing, ICIP 2005, September 2005.

[6] A. Foi, V. Katkovnik, and K. Egiazarian, "Pointwise Shape-Adaptive DCT for High-Quality Denoising and Deblocking of Grayscale and Color Images," IEEE Trans. Image Process., vol. 16, no. 5, pp. 1395-1411, May 2007.

[7] V. Katkovnik, A. Foi, K. Egiazarian, and J. Astola, "Nonparametric Regression in Imaging: From Local Kernel to Multiple Model Non-local Collaborative Filtering", in Proc. 2008 Int. Workshop on Local and Non-Local Approximation in Image Processing, LNLA 2008, Lausanne, Switzerland, August 2008.





Сравнение алгоритмов, применяемых при локализации в беспроводных сенсорных сетях

Воронков Д.В.

Рязанский Государственный Радиотехнический Университет

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

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

Были разработаны и специальные алгоритмы для беспроводных сенсорных сетей[2-8]. Истинные распределенные алгоритмы, которые могут применяться в крупномасштабных ad-hoc сенсорных сетях (100 и более узлов), должны:
  • самоорганизовываться (не зависеть от глобальной инфраструктуры),
  • быть робастными (то есть быть устойчивыми к повреждениям узлов и ошибкам измерений расстояния),
  • энергоэффективными (то есть требовать малого количества вычислений и, особенно, коммуникаций).
  • В докладе приводится анализ работы трех алгоритмов при различных условиях. В основном, исследуется влияние следующих параметров: ошибка при определении дальности, плотность распределения узлов в сети и доля маяков в сети. Эти алгоритмы различаются по точности позиционирования, масштабу сети, создаваемому в сети трафику, и процессорной загрузке. Общее для них то, что эти алгоритмы применются для сети часть узлов которой («маяки»), имеет априорную информацию о своем местположении.

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

Литература
  1. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, A survey on sensor networks, IEEE Commun. Mag. 40 (8) (2002) 102–114.
  2. N. Bulusu, J. Heidemann, D. Estrin, GPS-less low-cost outdoor localization for very small devices, IEEE Person. Commun. 7 (5) (2000) 28–34.
  3. S. Capkun, M. Hamdi, J.-P. Hubaux, GPS-free positioning in mobile ad-hoc networks, Cluster Comput. 5 (2) (2002) 157–167.
  4. J. Chen, K. Yao, R. Hudson, Source localization and beamforming, IEEE Signal Process. Mag. 19 (2) (2002) 30–39.
  5. L. Doherty, K. Pister, L.E. Ghaoui, Convex position estimation in wireless sensor networks, in: IEEE Infocom 2001, Anchorage, AK, 2001.
  6. D. Niculescu, B. Nath, Ad-hoc positioning system, in: IEEE GlobeCom, 2001.
  7. C. Savarese, K. Langendoen, J. Rabaey, Robust positioning algorithms for distributed ad-hoc wireless sensor networks, in: USENIX Technical Annual Conference, Monterey, CA, 2002, pp. 317–328.
  8. A. Savvides, H. Park, M. Srivastava, The bits and flops of the N-hop multilateration primitive for node localization problems, in: First ACM International Workshop on Wireless Sensor Networks and Application (WSNA), Atlanta, GA, 2002, pp. 112–121.


Comparison distributed localization algorithms in wireless sensor networks

Voronkov D.

Ryazan State Radioengineering University

Wireless sensor networks hold the promise of many new applications in the area of monitoring and control. Examples include target tracking, intrusion detection, wildlife habitat monitoring, climate control, and disaster management. New technology offers new opportunities, but it also introduces new problems. This is particularly true for sensor networks where the capabilities of individual nodes are very limited. Hence, collaboration between nodes is required, but energy conservation is a major concern, which implies that communication should be minimized. These conflicting objectives require unorthodox solutions for many situations.

A survey by Akyildiz et al. discusses a long list of open research issues that must be addressed before sensor networks can become widely deployed [1]. The problems range from the physical layer (low-power sensing, processing, and communication hardware) all the way up to the application layer (query and data dissemination protocols). In this thesis I address the issue of localization in ad-hoc sensor networks. I determine the location of individual sensor nodes without relying on external infrastructure (base stations, satellites, etc.).

Recently a number of localization systems have been proposed specifically for sensor networks [2–8]. Such algorithms should be:

• self-organizing (i.e., do not depend on global infrastructure),

• robust (i.e., be tolerant to node failures and range errors), and

• energy efficient (i.e., require little computation and, especially, communication).

We compare three distributed localization algorithms (Ad-hoc positioning, Robust positioning, and N-hop multilateration) on a single simulation platform.

The main conclusion is that no single algorithm performs best; which algorithm is to be preferred depends on the conditions (range errors, connectivity, anchor fraction, etc.). In each case, however, there is significant room for improving accuracy and/or increasing coverage.

References
  1. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, A survey on sensor networks, IEEE Commun. Mag. 40 (8) (2002) 102–114.
  2. N. Bulusu, J. Heidemann, D. Estrin, GPS-less low-cost outdoor localization for very small devices, IEEE Person. Commun. 7 (5) (2000) 28–34.
  3. S. Capkun, M. Hamdi, J.-P. Hubaux, GPS-free positioning in mobile ad-hoc networks, Cluster Comput. 5 (2) (2002) 157–167.
  4. J. Chen, K. Yao, R. Hudson, Source localization and beamforming, IEEE Signal Process. Mag. 19 (2) (2002) 30–39.
  5. L. Doherty, K. Pister, L.E. Ghaoui, Convex position estimation in wireless sensor networks, in: IEEE Infocom 2001, Anchorage, AK, 2001.
  6. D. Niculescu, B. Nath, Ad-hoc positioning system, in: IEEE GlobeCom, 2001.
  7. C. Savarese, K. Langendoen, J. Rabaey, Robust positioning algorithms for distributed ad-hoc wireless sensor networks, in: USENIX Technical Annual Conference, Monterey, CA, 2002, pp. 317–328.
  8. A. Savvides, H. Park, M. Srivastava, The bits and flops of the N-hop multilateration primitive for node localization problems, in: First ACM International Workshop on Wireless Sensor Networks and Application (WSNA), Atlanta, GA, 2002, pp. 112–121.







1 Работа выполнена при частичной финансовой поддержке РФФИ (проект № 09-01-99014-р_офи)



Цифровая обработка сигналов и ее применение

Digital signal processing and its applications