Использование 2D-цветовых гистограмм для представления цветового содержимого изображений

- построение полной модели при наличии информации в виде 2D- или 3D-частей объекта. Фактически это задача восстановления, которая может возникать в таких областях, как медицина, археология и т.п.

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

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

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

В такой подсистеме наиболее трудоемкими этапами являются: поиск в БД подобной модели и построение 3D-модели на основе срезов. Известные методы реконструкции имеют ту особенность, что работают либо в условиях наличия входных данных, представленных в трехмерном виде, либо при отсутствии необходимости выбирать двумерные срезы по каким-либо параметрам из баз данных.

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

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

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

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

Н.С.Костюкова

ИСПОЛЬЗОВАНИЕ 2Б-ЦВЕТОВЫХ ГИСТОГРАММ ДЛЯ ПРЕДСТАВЛЕНИЯ ЦВЕТОВОГО СОДЕРЖИМОГО ИЗОБРАЖЕНИЙ

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

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

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

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

С учетом пространственной природы содержимого рассматриваемых изображений 2Б-цветовая гистограмма строится как двумерный массив Стах*Стах, где Стах - число цветов базового набора, использовавшегося на этапе дискретизации цветов. Каждый элемент такой гистограммы равен количеству пар пикселей с заданным соотношением цветов в окрестности точки. Как правило, при построении 2Б-цветовой гистограммы анализируют не вес точки окрестности, а только те, которые принадлежат определенному шаблону. В процессе расчета элементов 2Б-цветовой гистограммы каждая из Ы-Ы точек изображения сравнивается с к точками шаблона, и в процессе этого сравнения увеличиваются на единицу к элементов 2Б-цветовой гистограммы. Таким образом, после обработки всего изображения сумма элементов 2Б-цветовой гистограммы будет равна к-Ы-Ы, а каждый ее элемент будет равен количеству пар точек с заданным соотношением цветов. Далее, выполняется нормирование элементов путем деления значения каждого на количество пар точек изображения, что позволит в последующем сравнивать 2Б-цветовые гистограммы, построенные для изображений различных размеров. Построение 2Б-цветовой гистограммы по такому алгоритму означает, что каждый ее элемент Н[1/] представляет собой вероятность присутствия в изображении пары точек с цветами а[1] и с//]. Если цветовое пространство, для которого выполнялось построение базового набора цветов с[1..Стах], обладает свойством полноты, то, оче-СтахСтах видно, X I яду] = 1.

I=1 у=1

Проанализируем эффективность использования для сравнения 2Б-цветовых гистограмм метрик, используемых традиционно для сравнения обычных цветовых гистограмм, а именно, евклидова расстояния, конъюнкции, косинусного и евклидова расстояний и определим область значений для каждой из этих метрик (табл. 1). Максимальное значение расстояния между нормализованными 2Б-цветовыми

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

Таблица 1

Метрика Область значений при использовании нормализованных 2Б-цветовых гистограмм

Конъюнкция гистограмм (01) 0 < D1 < Cmax

Евклидово расстояние (02) 0 < D2 < C2max

Косинусное расстояние (03) C2 0 < D3 < Cmax 2

Квадратичное расстояние (04) 0 < D4 < C4max

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

СЮ

где соу(И1,И2 )- ковариация 2Б-цветовых гистограмм И1 и И2, о(И2), а(И2) -

среднеквадратичное отклонение элементов 2Б- цветовых гистограмм ^и Н2.

Среднеквадратичное отклонение гистограммы, в свою очередь, может быть вычислено по формуле (2):

s

(H)=4D(H) =

1 CmaxCmax

с,

2

I I

-'max i=1 j=1

где D(H^-дисперсия, и ц(.H) - математическое ожидание элементов гистограммы, вычисляемое следующим образом:

1 CmaxCmax

m

C

C

-2

max i=1 j=1

Ковариация двух гистограмм вычисляется по формуле (4):

1 CmaxCmax

cov

Cmax i=1 ji=1

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

CmaxCmax

I I (Hl[ іЛ]^2 [ і,J] - Hi [ і,J] - H2 [ і,J ])+1

p =

і=1 =1

CmaxCmax

і=1 =1

Cmax

1

)

Для оценки качества поиска изображений на основе предложенного подхода были разработаны программы, выполняющие поиск изображений как на основе ранее предложенных метрик (евклидово, косинусное расстояние, конъюнкция цветовых гистограмм). Причем для сравнения цветовое содержимое представлялось как обычной, так и 2D-цветовой гистограммой. В качестве инструментального средства использована среда визуального программирования Delphi 5.0. При построении характеристик цветового содержимого для приведение цветов к базовому набору выполнялась равномерная дискретизация цветов в RGB - пространстве до 64 цветов.

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

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

Также были разработаны программы, выполняющие поиск изображений с использованием коэффициента корреляции 2D-цветовых гистограмм.

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

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

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

Таким образом, экспериментально показаны преимущества использования 2D-цветовых гистограмм для представления цветового содержимого изображения.

1. IBM Almaden Research Center. Query by Image and Video Content: the QBIC System. Computer, September 1995, 23-31.

2. Smith J.R., Chang S.-F., "VisualSEEk: A Fully Automated Content-

Based Image Query System," ACM Multimedia Conference, Boston, MA, Nov. 1996. Demo: http://www.ctr.columbia.edu/VisualSEEk.

3. Amarnath Gupta. Visual Information Retrieval Technology- A Virage Perspective.

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

4. Башков Е.А., Шозда Н.С. Поиск изображений в больших БД с использованием коэффициента корреляции цветовых гистограмм.// Труды 12-й Международной конференции "ГрафиКон’2002". - Нижний Новгород, 2002. - С. 358-361.

5. Башков Е.А, Костюкова Н.С. Модифицированный алгоритм поиска изображений по их цветовому содержимому. IV Международная научно-техническая конференция «Кибернетика и технологии XXI века». —Воронеж (Россия), 13-14 мая 2003. -С. 460472.

6. Гмурман В.Е. Теория вероятностей и математическая статистика.-М.: Высшая школа, 1972.

В.Ф.Гузик, В.Е.Золотовский, В.А.Переверзев, Д.Ю. Сусляков

СИНТЕЗ ВИРТУАЛЬНОЙ ПРОСТРАНСТВЕННОЙ ОБСТАНОВКИ ЗЕМНОЙ ПОВЕРХНОСТИ ПО ДАННЫМ ИМПУЛЬСНО-

ДОПЛЕРОВСКИХ БОРТОВЫХ РАДИОЛОКАЦИОННЫХ СТАНЦИЙ

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

В РЛС импульсно-доплеровского типа применяются зондирующие импульсы с различными параметрами, что, в свою очередь, обусловливает наличие различных режимов излучения и обработки сигналов. При картографировании поверхности Земли применяется низкая (^„=0,3-2 кГц) частота повторения (НЧП), для обеспечения однозначности по дальности. Отраженный от цели сигнал отличается от зондирующего задержкой по времени на величину, равную времени распространения сигнала в среде до цели и обратно (/д=2Д/с), и несущей частотой, которая складывается из: излучаемой частоты ^ и доплеровского сдвига частоты /д=2У/Х, возникающего за счет взаимного движения самолета и цели, где Уг -радиальная составляющая скорости взаимного движения; Х=с//0 - длина волны излучения; с - скорость света. При этом сигнал имеет случайную начальную фазу ф. Также к основным параметрам, влияющим на свойства принимаемого сигнала и его спектр, относятся (рис. 1):

- угол места максимума диаграммы направленности антенны (ДНА) Д

- текущее азимутальное положение максимума ДНА ва;

- ширина ДНА (на уровне 0,5 по мощности) вл,

- наклонная дальность до центра кадра накопления (парциального кадра) Д;

- высота полета носителя Н;

- скорость полета носителя Ус.

При картографировании под целью подразумевается, непосредственно, земная поверхность. Центральная частота спектра сигнала, отраженного от земной поверхности, смещена относительно /0 на величину /д, которая соответствует угловому положению луча антенны относительно вектора скорости самолета /д=2У<со$6А/Х и меняется синхронно со сканированием ДНА в азимутальной плоскости. Ширина спектра доплеровских частот сигналов, отраженных от земной поверхности А/д также изменяется при сканировании - она наименьшая при наблюдении строго вперёд по курсу самолета А^=4Ус 8т(в0/2)/Х и наибольшая при боковом обзоре А^=2Усв0/Х. Результирующий спектр отраженного сигнала изображен на рис. 2 (показана только небольшая - центральная часть спектра).