Обработка и передача изображений

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

Документы

Содержание PCA-based face recognition P eigenvectors associated with non-zero eigenvalues, assuming P Построение графов изображений движущихся объектов Реализация метода покрытий для расчета фрактальной размерности ландшафтных изображений N(r) – число клеток, r

Подобный материал:

• Обработка и передача изображений, 213.76kb.
• Анализ, обработка и передача динамических изображений в моделях виртуальной реальности, 80.25kb.
• Обработка и передача изображений, 243.48kb.
• Обработка и передача изображений, 149.44kb.
• Обработка и передача изображений, 357.76kb.
• Обработка и передача изображений, 241.81kb.
• 1. Информационные технологии. Структура информационного процесса. Сбор, обработка,, 1016.5kb.
• Обработка и передача изображений, 203.92kb.
• Белорусский государственный университет применение информационных технологий при анализе, 187.23kb.
• Обработка и передача измерительной информации, 201.84kb.

PCA-based face recognition

Pakhirka A.

Siberian State Airspace University after academician M.F. Reshetnev (SibSAU)

Principal Component Analysis is standard technique used to approximate the original data with lower dimensional feature vector. PCA is probably the most widely used subspace projection technique for face recognition.

The original space of an image is just one of infinitely many spaces in which the image can be examined. Specific subspace is the subspace created by the eigenvectors of the covariance matrix of the training data. The majority of subspaces, including eigenspace, do not optimize discrimination characteristics. Eigenspace optimizes variance among the images.

Eigenspace is calculated by identifying the eigenvectors of the covariance matrix derived from a set of training images. The eigenvectors corresponding to non-zero eigenvalues of the covariance matrix form an orthonormal basis that rotates and/or reflects the images in the N–dimensional space. Specifically, each image is stored in a vector of size N.

The images are mean centered by subtracting the mean image from each image vector. These vectors are combined to create a data matrix of size NP (where P is the number of images). The data matrix is multiplied by its transpose to calculate the covariance matrix. This covariance matrix has up to P eigenvectors associated with non-zero eigenvalues, assuming P  N. The eigenvectors are sorted, high to low, according to their associated eigenvalues. The eigenvector associated with the largest eigenvalue is the eigenvector that finds the greatest variance in the images.

Identifying images through eigenspace projection takes three basic steps. First the eigenspace must be created using training images. Next, the training images are projected into the eigenspace. Finally, the test images are identified by projecting them into the eigenspace and comparing them to the projected training images.

1. Create eigenspace.
   
2. Center data: Each of the training images must be centered. Subtracting the mean image from each of the training images centers the training images as shown in equation .
   
3. Create data matrix: Once the training images are centered, they are combined into a data matrix of size NP
   
4. Create covariance matrix: The data matrix is multiplied by its transpose to create a covariance matrix.
   
5. Compute the eigenvalues and eigenvectors: The eigenvalues and corresponding eigenvectors are computed for the covariance matrix.
   
6. Order eigenvectors: Order the eigenvectors according to their corresponding eigenvalues from high to low. Keep only the eigenvectors associated with non-zero eigenvalues. This matrix of eigenvectors is the eigenspace V , where each column of V is an eigenvector.
   
7. Project training images. Each of the centered training images () is projected into the eigenspace.
   
8. Identify test images. Each test image is first mean centered by subtracting the mean image, and is then projected into the same eigenspace defined by V.
   

The projected test image is compared to every projected training image and the training image that is found to be closest to the test image is used to identify the training image. The images can be compared using any number of similarity measures; the most common is the Euclidean norm.





ПОСТРОЕНИЕ ГРАФОВ ИЗОБРАЖЕНИЙ ДВИЖУЩИХСЯ ОБЪЕКТОВ

Шилов А.С.

Сибирский государственный аэрокосмический университет имени М.Ф. Решетнева

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

, , где x – координаты точки, k – размерность пространства, I – яркость точки.

Граф сцены строится из набора полученных областей в процессе сегментации таким образом, чтобы узлы представляли собой эти области, а ребра – «расстояние» между ними по некоторой метрике. Иными словами, каждый узел графа несет в себе пространственную информацию, в то время как ребра передают временную информацию. Прослеживание каждого объекта выполняется при помощи поиска минимального пути в графе. Кроме того, ребра графа имеют веса, учитывающие информацию о скорости движения, типе движения, цвета областей и т.д. Такой вид структуры используется для прослеживания объектов в видеопоследовательности. Представим алгоритм построения графа движущихся объектов некоторой сцены.

Пусть G – ориентированный граф некоторой сцены, n_i(t) – узлы в кадре со временем t. Граф движения объекта строится в соответствии со следующими шагами:

1. Создаем узел n_i(t) для каждой i-ой области в первом кадре t=1 и добавляем его в граф G.

2. Создаем узел n_j(t + 1) для каждой j-ой области в кадре t + 1 и добавляем узел в G.

3. Вычисляем расстояния d_ij между узлами n_i(t) и n_j(t + 1).

4. Создаем ребро e_ij, удовлетворяющее условию d_ij<d_max, где d_max представляет собой максимальное расстояние.

5. Повторяем шаги 2-4 для всех кадров сцены.

Расстояние между областями, используемое для включения узлов в граф, вычисляется как минимальное возможное расстояние между двумя областями. Обычно это расстояние рассчитывают от средней точки области, однако область может быть объединением двух объектов. Поэтому рекомендуется учитывать контур объекта. Главная задача ребер графа определение пути или возможных путей на графе в течение всего времени отслеживания объекта. Таким образом, ребра, связывающие очень отдаленные области, согласно значению d_max не включаются в граф [2].

На рис.1 приведен пример графа, содержащего узлы и ребра для четырех последовательных кадров. В первом кадре присутствует четыре объекта, три из которых попали в одну область, на втором кадре все объекты перемещаются в одну область, на последнем кадре объекты разделяются на две области по 2 объекта в каждой. Таким образом, строится граф по всей временной шкале видеопоследовательности. Каждый узел хранит информацию о особенностях области, определенных во время построения графа. Укажем примеры таких особенностей: – ширина и высота: размер ограничивающего прямоугольника области; – площадь: количество пикселей в области; – периметр: количество пикселей в контуре области; – x, y: координаты центра области в изображении; – количество объектов в области; – цвет, доминирующий в текущей области.

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

После построения графа можно определить следующие параметры: – расстояние между двумя связными узлами, вычисленное как евклидово расстояние между центрами области; – направление движения объектов; – скорость движения объектов.



Рис.1. Пример графа движущихся объектов



Рис.2. Блок схема алгоритма построения графа сцены

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

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

Литература

1. Ballard D.H., Brown C.M., Computer Vision, Prentice-Hall, Englewood Cliffs, NJ, 1982. – 52 p.
   
2. Pascual J. Figueroa, Neucimar J. Leite a, Ricardo M.L. Barros, Tracking soccer players aiming their kinematical motion analysis, Computer Vision and Image Understanding, Vol.5, no.2, 2006. – pp. 51-65.
   
3. McKenna S.J., Jabri S., Duric Z., Rosenfeld A., Wechsler H., Tracking groups of people, Computer Vision and Image Understand, vol. 80, 2000. – pp. 42–56.
   

The graph construction of moving image objects

Shilov A.

Siberian State Airspace University after academician M.F. Reshetnev (SibSAU)

Movement of objects in the frame is the useful information which can be used in systems of video observation for the analysis of behaviour of objects. There are some methods of allocation of movement in the frame are methods of subtraction of a background which are applied to everyone to the frame, methods of tracking features. However we will pay greater attention to methods of the graph theory. Today methods of the graph theory are one of most actively developing directions in segmentation of raster images. Weight of an edge reflects similarity of points (distance between points under some metrics).

Graph of a stage is a set of the received areas during segmentation, that units represented these areas, and edges - "distance" between them, under some metrics.

Let G be an oriented graph of a video sequence and n_i(t) are the nodes at frame t. Our data structure can be defined according to the following steps:

1. Creation of a node n_i(t) for each blob i in the first frame, t =1, and insertion of this node into graph G.

2. Creation of a node n_j(t + 1) for each blob j in frame t + 1 and insertion into G.

3. Computation of the distance d_i,j between nodes n_i (t) and n_j(t + 1).

4. Creation of an edge e_i,j satisfying condition d_i,j<d_max, where d_max represents a given maximal distance.

5. Repetition of steps 2–4 for the whole video sequence.

The distance between blobs, used for including nodes into the graph, is computed as the minimal distance between two blobs contour pixels. A natural way to compute this distance is from the centroid of the corresponding blobs, nevertheless, since a blob can represent more than

one player, better results are obtained by taking into account its contour information.

Each node stores information about the blobs features defined during the graph construction. Examples of these information are: – width and height: the size of the bounding rectangle of the blobs; – area: the number of pixels of a blob; – perimeter: the number of pixels in the contour of a blob; – x,y: the coordinates of the center of a blob in the image; – color: the color associated to a blob.

After the graph construction, the following parameters can be defined: – num_comp: the number of components relative to the number of players in a blob. – dist: the distance between two linked nodes computed as the Euclidean distance between the center points of the blobs; – direction: the direction of the players trajectory; – velocity: the velocity of the objects.

The number of components information represent the number of players in a blob. The correct determination of the number of components is important if we need to split this blob (representing more than one player), and make correct decisions about trajectories during the tracking. This number is difficult to determine when, for example, a blob containing more than one player, in frame t, is split or connected to another blob in frame t + 1.

The main function of the edges information is to define the path or the possible paths of a player on the graph, during the tracking process. Use of the graph theory for the analysis of videodata for today is the powerful tool which allows to trace more effectively objects of interest, to build hypotheses about moving these objects, gives the subsequent opportunity of identification of objects, etc.




Реализация метода покрытий для расчета фрактальной размерности ландшафтных изображений

Петухов Н.Ю.

Сибирский государственный аэрокосмический университет имени академика М.Ф.Решетнева

Важной задачей при реализации систем компьютерного зрения является работа с текстурами. За последние несколько десятилетий было предложено большое количество методов анализа текстуры, однако бесчисленное разнообразие естественных и искусственных текстур делает невозможным дать универсальное определение текстуры. [2] Ландшафтные же изображения можно интерпретировать как совокупность текстурных фрагментов естественного происхождения и изображений антропогенных объектов.

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

Для вычисления фрактальной размерности D используется обычно три алгоритма: метод покрытия поверхности эталонами; дисперсионное масштабирование, основанное на оценке закона функции распределения средних квадратов; оценка размерности по степени аппроксимирующего полинома для спектра мощности процесса. [3] В настоящее время первый способ наиболее распространен.

Метод покрытий имеет два вида реализации: покрытие квадратной сеткой и покрытие двумерной поверхностью. Самый простой способ реализации метода покрытий – наложение квадратной сетки на изображение фрактала и подсчет числа клеток N(r), в которые попадает фрактал. Когда расстояние r между параллельными линиями сетки становится достаточно малым, величина lnN(r)/ln(1/r) сходится к конечному значению, что и есть фрактальная размерность. Размерность рассчитывается по следующей формуле , где N(r) – число клеток, r – размер клетки.

Метод конструирования покрытий состоит в конструировании двумерной поверхности, таким образом, чтобы квантованные значения интенсивности двумерного сигнала располагались между двумя функциями, верхней U и нижней L поверхностями. Верхняя поверхность U содержит множество точек, значения которых всегда, по крайней мере, на один квант превышают интенсивность входного сигнала. Нижняя поверхность L имеет значения точек, которые всегда ниже, по крайней мере, на один квант интенсивности входного изображения. Эти поверхности при нулевой шкале масштаба равны исходному изображению. В общем случае они рассчитываются следующим образом

,

где µ={(k,m) – расстояние [(k,m),(I,j)≤1]}.

Сконструированное покрытие, образованное двумя указанными функциями, имеет толщину 2. Для двумерного сигнала площадь «поверхности» есть объем, занятый покрытием и деленный на величину 2. Площадь «поверхности» интенсивности A() в пределах окна наблюдения R рассчитывают вычитанием точки за точкой нижней «поверхности» из верхней «поверхности» с дальнейшим суммированием по всему окну: . Фрактальную размерность определяют по наклону log A() как функцию log . Измеряемая «поверхность» A() может определяться разностью объемов при последовательных масштабах: Рассчитанное значение A₁() является аппроксимацией производной V() по  и определяется по формуле , где K – постоянная величина.

Следует отметить, что расчет по производной дает сильную шумовую составляющую, поэтому он редко используется на практике. На рис.1 приведена структурная схема метода конструирования покрытий двумерной поверхности



Рис. 1. Структурная схема метода конструирования покрытий двумерной поверхности


Однако только фрактальной размерности не достаточно, для описания того или иного природного объекта, потому что разные фрактальные образования могут иметь одинаковую размерность, но при этом резко отличаться по текстуре. Для описания таких текстур используют понятие лакунарность (заполнение), которая описывается следующей формулой , где M – масса фрактального образования; - ожидаемая масса.

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

Для тестирования был реализован m-файл в программном обеспечении MatLab 7, вычисляющий фрактальную размерность методом покрытий квадратной сеткой. Использовались две базы с естественными текстурами: textures library forrest (400 изображений) и Brodatz (110 изображений) [4,5].

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

Таблица 1. Результаты расчетов фрактальной размерности

Текстура	Размерность	Текстура	Размерность
Трава	2,728	Кора дерева	2,6057
Облако	2,586	Дерево	2,7088
Вода	2,6256	Куст	2,6642

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

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

Литература

1. Мандельброт Б. Фрактальная геометрия природы. – Москва: Институт компьютерных исследований, 2002, 656 стр.
   
2. А.А. Потапов. Теория фракталов: топология выборки. – М.: Университетская книга, 2005, - 868с.
   
3. ссылка скрыта - электронный ресурс (база текстурных изображений Brodatz)
   
4. ссылка скрыта - электронный ресурс (база текстурных изображений textures library forrest)