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

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

Денисова А.Ю., Мясников В.В. Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет) (СГАУ), Институт систем обработки изображений РАН

Аннотация

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

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

Введение

Анализ спектральной смеси - один из наиболее широко используемых подходов при обработке гиперспектральных изображений дистанционного зондирования Земли (ДЗЗ). Цель такого анализа заключается в определении долей веществ, составляющих конкретный зарегистрированный отсчёт гиперспектрального изображения (ГСИ). Результат, характеризующий найденную долю вещества, может быть использован для решения целого ряда прикладных задач: обнаружения, классификации и др.

В литературе описаны две модели, определяющие способ формирования спектральной смеси. Одна из них - макроскопическая - предполагает, что отсчёт ГСИ формируется как линейная комбинация спектральных сигнатур [1], каждая из которых определяет спектральный состав зарегистрированного излучения для конкретного материала. Вторая модель - модель плотной спектральной смеси (англ. intimate spectral mixture) - предполагает нелинейную комбинацию спектральных сигнатур составляющих материалов [2]. В работе [3] показано, что вторая модель может быть линеаризована, что позволяет для идентификации параметров обеих моделей использовать методы анализа линейной спектральной смеси (англ. linear spectral mixture analysis - LSMA).

Совокупность методов LSMA, используемых при обработке и анализе ГСИ ДЗЗ, была систематизирована в работах профессора C.I. Chang, посвятившего вопросам обработки гиперспектральных изображений три монографии [4-6] и целый ряд статей. Несколько отличающийся вариант классификации методов LSMA представлен в работе [7]. Следуя классификации, предложенной в работах [4-6], методы можно разделить по степени использования априорной информации на управляемые (англ. supervised LSMA -SLSMA), когда известен состав сигнатур разложения, и неуправляемые (англ. unsupervised LSMA -ULSMA), когда априорная информация о составе сигнатур отсутствует. Особенность ULSMA заключается

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

Основной целью методов SLSMA является определение (оценка, идентификация) для конкретного отсчёта ГСИ и предопределённого набора спектральных сигнатур коэффициентов линейной спектральной смеси. Учитывая основное назначение, эти методы называют методами линейного спектрального разложения (англ. linear spectral unmixing) или инверсными алгоритмами (англ. inversion algorithms) [7]. Следуя принятой в работе [7] классификации, методы линейного спектрального разложения могут различаться по выбранному подходу к построению (статистические и нестатистические), по критерию оптимизации (средний квадрат и отличные от него), по составу учитываемых ограничений (неотрицательность коэффициентов и др.), по допустимости наличия в данных шумовых искажений и т.п.

Среди наиболее известных и практически наиболее востребованных методов линейного спектрального разложения отметим нестатистические методы, основанные на критерии минимума среднеквадрати-ческого отклонения, которые в рамках модели формирования отсчёта ГСИ допускают наличие шумов. Эти методы отличаются возможными постановками задачи спектрального разложения [4-9] и, как следствие, сложностью их решения.

К первой группе методов относятся методы спектрального разложения без каких-либо ограничений (англ. unconstrained - vSLSMA). К ним относятся, в частности, метод проекции на подпространство (англ. orthogonal subspace projection - OSP) и метод спектрального разложения путем минимизации средне-квадратического отклонения (англ. least square projection classifier) [4, 8, 9]. В последнем решение соответствующей задачи минимизации среднеквадратиче-ского отклонения может быть получено в явном виде. Несмотря на физическую некорректность такого решения (коэффициенты разложения могут не соответ-

ствовать понятию «доли», то есть быть отрицательными или превышать единицу), оно достаточно часто применяется при решении задач классификации отсчётов ГСИ [7].

Ко второй группе методов относятся методы LSMA минимизации среднеквадратического отклонения с частичными ограничениями (англ. partially unconstrained - SLSMA). Среди этих методов следует выделить [4, 8, 9]: методы минимизации среднеквад-ратического отклонения с ограничением на сумму коэффициентов разложения (англ. sum-to-one constrained linear square - SCLS) и методы минимизации среднеквадратического отклонения с ограничением на неотрицательность коэффициентов разложения (англ. nonnegativity constrained linear square - NCLS). Наиболее известным методом NCLS является алгоритм NNLS (non-negative least-square algorithm), описанный в монографии [10], модифицированный авторами указанной работы в статье [11] и допускающий быструю реализацию [12].

В третьей группе методов учитываются оба ограничения, независимо использованные во второй группе. Соответствующие методы получили название методов минимизации среднеквадратического отклонения с полными ограничениями (англ. Fully Constrained Linear Square FCLS). В области обработки и анализа ГСИ ДЗЗ известным алгоритмом является алгоритм, разработанный D.C. Heinz и C.I. Chang и описанный в работе [9].

Настоящая работа посвящена разработке и исследованию нового алгоритма из класса методов FCLS -методов минимизации среднеквадратического отклонения с полными ограничениями. За основу предлагаемого алгоритма берётся метод проективного градиента, предложенный J.B.Rosen ещё в 1960 году [1314] и описанный, в частности, в монографии [15]. В тексте работы также приводится соответствие между некоторыми известными алгоритмами LSMA, указанными в тексте выше, и методами нелинейной оптимизации с ограничениями, подробное описание которых дано в монографии [15].

Работа построена следующим образом. В первом разделе представлена постановка задачи спектрального разложения линейной смеси спектральных сигнатур, дана информациях об ограничениях. Во втором разделе дан краткий обзор известных методов нелинейной оптимизации с ограничениями, более подробное изложение которых можно найти в монографии [15]. Здесь же указаны соответствия между некоторыми известными алгоритмами LSMA (в частности, алгоритмом NNLS и FCLS) и использованными в них методами оптимизации из [15]. В третьем разделе представлен предложенный авторами алгоритм минимизации среднеквадратического отклонения с полными ограничениями. Его исследование по качественным и скоростным показателям представлено в четвёртом разделе. В завершение работы приведены выводы, благодарности и список использованной литературы.

1. Формальная постановка задачи Ь8ЫЛ

В рамках линейной модели спектральной смеси исходный пиксель V ГСИ ДЗЗ представляется в виде линейной комбинации р спектральных сигнатур

{т1}р=1, формирующих матрицу М = (т1,..., тр):

V = Ма + п ,

где п - вектор ошибок модели и/или измерений,

а = (а1,...,ар) - вектор коэффициентов линейного

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

1) нормировка

X а ] = 1;

]=1

2) неотрицательность

а] > 0,0 < ] < р.

В общем случае соотношения (2) и (3) не исчерпывают все условия и ограничения, возможные в задачах ЬБМЛ. Примеры задач с дополнительными ограничениями, характеризующими специфическую постановку задачи ЬБМЛ, приводятся, например, в работе авторов [16]. В рамках данной работы они не рассматриваются.

Определение коэффициентов линейного спектрального разложения для многих практических задач производится путём минимизации величины среднеквадратического отклонения линейной смеси сигнатур от истинного значения пикселя ГСИ:

,2 !- . г-\Т

e2 =( v - M a) (v - M a) min.

Иногда для учёта относительной важности спектральных каналов ГСИ задача ставится в следующем виде

e2 = (v -Ma) A (v -Ma)  min,

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

Решение задачи (4) без ограничений является тривиальным и имеет хорошо известный в теории оценивания (и теории нормальной регрессии) вид:

aLS = (mtM )-1 MTv.

Как было отмечено во введении, несмотря на физическую некорректность такого решения, на практике оно часто применяется при решении задач классификации отсчётов ГСИ. Примеры таких решений представлены в работах [7, 17,18].

Пополнение задачи (4) условиями (2) и/или (3) делает её решение не таким тривиальным, а именно: метод БСЬБ решения задачи минимизации средне-квадратического отклонения с ограничением на сумму коэффициентов разложения (ограничение нормировки) заключается в сведении задачи (1)-(2) к задаче минимизации среднеквадратического отклонения с дополнительной аддитивной невязкой, равной квадрату отклонения правой части (2) от левой [4-9]. В такой постановке задача, как и задача (1), имеет явное решение в следующем виде [4-9]: а =

= a.

-

здесь 1 = (1,...,1) - вектор изр единиц.

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

- алгоритм КЫЬБ, описанный в работе [10],

- алгоритм КСЬБ, предложенный в работах [8-9].

Принципиальным отличием этих двух алгоритмов

является то, что алгоритм КЫЪБ выполняет решение исходной задачи (1)+(3), в то время как алгоритм КСЬБ выполняет решение двойственной к ней задачи.

Наконец, решение задачи ЬБМЛ с полным набором ограничений (1)-(3) осуществляется в работах одним из алгоритмов КЫЪБ или КСЬБ, но с модификацией первоначальной задачи, как в методе БСЬБ, а именно: матрица М заменяется на матрицу ~5М'

N =

1T

а вектор v - на вектор dv"

J =

1

Здесь величина 5 (5 > 0) характеризует относительную важность уклонений левых и правых частей в (1) и (2) соответственно. В результате имеем аналогичную (1) задачу минимизации среднеквадратиче-ского отклонения

min,

решаемую одним из указанных выше алгоритмов (NN18 или ЖЬБ).

Изложенный подход решения задачи ЬБМЛ с полными ограничениями, определяемый соотношениями (8)-(10), был первоначально предложен в работе [11], посвящённой разработке общего метода решения задачи минимизации среднеквадратического отклонения (3) с ограничениями в виде набора приблизительных равенств типа (2) и неотрицательно-

стью коэффициентов (3). Затем он был формально повторён (использован) в работе [9], где получил название «алгоритм FCLS».

2. Нелинейная оптимизация с ограничениями. Соответствие методов нелинейной оптимизации и алгоритмов LSMA для ГСИ ДЗЗ

Задача (1)-(3) относится к классу задач нелинейной оптимизации с ограничениями или нелинейного программирования, теория и методы которого разработаны достаточно давно и изложены в целом ряде монографий, в том числе в работе М. Мину [15]. Как указано в этой монографии: «Большинство существующих методов в нелинейном программировании можно разделить на два больших семейства:

- прямые методы (методы непосредственного решения исходной задачи);

- методы, использующие понятие двойственности.

Прямые методы характеризуются тем, что они

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

К прямым методам решения задач нелинейного программирования относятся, в частности [15]:

- метод замены переменной;

- метод возможных направлений;

- метод проекционного градиента, предложенный для задач нелинейного программирования общего вида J.B. Rosen ещё в 1960 году [13-14] и описанный для более частной задачи квадратичного программирования в монографии [10] и названный её авторами алгоритмом NNLS;

- метод обобщённого приведённого градиента, комбинирующий идеи метода проекционного градиента и методов линеаризации, указанных ниже;

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

Альтернативой прямым методам являются методы нелинейного программирования, суть которых заключается в замене исходной задачи на решение последовательности экстремальных задач без ограничений. К этим методам относятся, в частности, следующие [15]:

- методы штрафов (внешних и внутренних);

- методы классической лагранжевой двойственности, которые де-факто использованы в алгоритме NCLS, наряду с итеративным прямым методом решения задачи;

- методы, использующие расширенные лагранжианы.

Несмотря на широкий спектр существующих решений, в литературе периодически появляются решения задачи LSMA вида (1)-(3), которые полностью

или частично основаны на известных методах нелинейного программирования. Примерами являются алгоритмы КСЬБ и ГСЬБ, предложенные в работах [89], и алгоритм NN18 [9].

В настоящей работе мы предлагаем новый алгоритм решения задачи ЬБМЛ с полными ограничениями, относящийся к классу прямых методов и основанный на методе приведённого градиента, применяемом в редуцированном подпространстве исходного пространства коэффициентов.

3. Предлагаемый алгоритм решения задачи Ь8ЫЛ с полными ограничениями

Идея предлагаемого алгоритма основана на следующих легко (последовательно) проверяемых утверждениях:

а) нелинейный критерий задачи (4) является унимодальным,

б) ограничения (2)-(3) формируют в пространстве коэффициентов выпуклое множество (выпуклую область);

в) ограничение (2) формирует в исходном пространстве подпространство меньшей (на единицу) размерности;

г) в указанном подпространстве ограничения (3) также формируют выпуклую область;

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

Последнее утверждение позволяет указать достаточно простой алгоритм нахождения решения искомой задачи ЬБМЛ, включающий в себя следующие три основных этапа:

- этап перехода в подпространство меньшей (на единицу) размерности;

- этап проверки нахождения решения во внутренности выпуклой области указанного подпространства; если решение находится во внутренности - то завершение алгоритма;

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

Последний этап предлагаемого алгоритма похож на метод проекционного градиента, а также напоминает по принципу поиска решения известный симплекс-метод [15].

Ниже представлено формальное описание отдельных этапов предлагаемого алгоритма.

Переход в подпространство меньшей размерности

1) Выразить из условия (2) один из коэффициентов:

р-1

ар = 1 - X а ;

1=1

2) полученное выражение подставить в функционал (4):

( р-1 V

е2 =

1=1

Ш1и:

Проверка нахождения решения во внутренности выпуклого множества подпространства

3) из необходимого условия минимума функционала (12) получить решение системы линейных уравнений следующего вида:

Р-1 Т

X а1 (щ - тр) (т1 - тр ) =

1=1

= ( щ - тр) (V - тр), к = l, р -1;

4) используя (11) и найденные в (13) значения коэффициентов вектора а^...,а р-1, найти ар по (11);

5) проверить неравенство (3). Если оно выполняется, то завершить алгоритм, если оно не выполняется, то перейти к следующему этапу;

Итеративное наращивание граничных условий

6) обозначим а* =(-р,-р,...,-р) - вектор коэффициентов, удовлетворяющих ограничениям (2)-(3); пусть также вектор а' =(а1,а2,...,ар) обозначает

решение, полученное на шаге 5 (текущий '-й шаг);

7) на '-й итерации из уравнения прямой, соеди-^ _*

няющей точку а , расположенную внутри допустимого множества решений (выпуклая область), и точку а', полученную вне этой области, найти проекцию на границу выпуклой области допустимого множества

решений а'

в виде:

а'

Так как очевидно, что при любом Ре [0,1] для

а'(р) выполняется условие (2), то поиск проекции

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

обращаются в ноль (практически всегда один);

тогда в качестве в в выражении (14) следует

а

'

взять:

Р = а^щш рк,

к=1, р

где

Рк =

а

(*) • ак -ак

ак

(*) ак*) - ак

ак )

(*) а(к*) - -ак

(*) а(к*) - ак

< 0;

[0,1];

> 1;

'

9) вычислить а'+1 = а" ;

10) если полученный вектор а'+1 не удовлетворяет ограничению (3), то продолжить решение с первого шага алгоритма, полагая, что матрица М содержит

0

1

только столбцы, соответствующие ненулевым компонентам вектора а'+1, и положив соответствующие коэффициенты в искомом векторе а равными нулю.

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

Для оценки эффективности предложенного алгоритма решения задачи LSMA с полными ограничениями были проведены экспериментальные исследования. Решение задачи LSMA выполнялось на синтезированных отсчётах ГСИ с 340 каналами с диапазоном длин волн от 0,8 до 2,5 мкм с шагом 0,005 мкм. В качестве спектральных сигнатур использовались следующие 10 из спектральной библиотеки IGCP-264 Library [19]: ALUNITE_AL705, ILLITE_IL101, SEPI0LITE_SEP3101, BUDDINGT0NITE_NHB2301, HEMATITE_FE2602, GYPSUM_SU2202, CALCITE_C02004, TALC_TL2702, G0ETHITE_FE2600, TREM0LITE_AMT3001.

Первая часть эксперимента заключалась в исследовании ошибки оценки коэффициентов спектрального разложения, полученных предложенным алгоритмом, в зависимости от дисперсии аддитивного шума модели (1) (вектора n ), количества спектральных сигнатур и числа нулевых коэффициентов разложения. Ошибка для каждого конкретного синтезированного отсчёта ГСИ оценивалась следующим образом:

=- É

где a*, a¡ - истинные и оцененные коэффициенты

разложения (1) соответственно. Для набора ошибок (11), полученных для различных синтезированных отсчётов ГСИ (количество синтезируемых отсчётов в каждом эксперименте N = 1000 штук), рассчитывалась величины среднего Ee2a и дисперсии De2a . Результаты, представленные в виде среднего Ee2a и коридора

Eea ± 3^¡De2a , показаны на рис. 1 и 2.

Видно, что коэффициенты спектрального представления (1) восстанавливаются достаточно точно в широком диапазоне значений дисперсии шума (во всех экспериментах используется аддитивный некоррелированный шум с нормальным законом распределения с нулевым средним и указанной дисперсией, значения компонент сигнатур и коэффициенты при сигнатурах имеют значения в интервале от 0 до 1), а именно:

- точность восстановления коэффициентов имеет тот же порядок, что и точность задания исходных данных;

- присутствует слабая зависимость изменения погрешности идентификации от числа нулевых коэффициентов LSMA;

- присутствует монотонно возрастающая зависимость изменения погрешности идентификации от числа спектральных сигнатур. Следует отметить, что для проведённых экспериментов увеличение погрешности идентификации не меняет порядок её величины.

0,005 0,004

0,003

0,002

0,001

0,004 0,003 0,002 0,001

0,004 0,003

0,002

0,001

— Fe2

.......EeZ±3-]DEZ у

*

у

У

У

Dv

0 0,01 0,02 0,03

а) число нулевых коэффициентов - 0,

Ee¿

Ee¿±3JDE¡

0 0,01 0,02 0,03

б) число нулевых коэффициентов - 1,

Ее*

Ee¿±34De¡

О 0,01 0,02 0,03

в) число нулевых коэффициентов - 2,

Ее*

EeI±34DE¿

0,004 0,003

0,002

0,001

О 0,01 0,02 0,03

г) число нулевых коэффициентов - 3

Рис. 1. Результаты исследования качества алгоритма решения задачи ЬБМЛ с полными ограничениями

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

2

2

e

a

ГСИ с линейными размерами 1000x1000 отсчётов (1 млн отсчётов). Исследования проводились на ПЭВМ Intel Core i5-3470 3.20GHz, реализация выполнена на языке C++. Ег2а

5.00Е-05

1,00Е-05 0,00Е+00

4 6 8 10

Рис. 2. Результаты исследования зависимости погрешности оценки коэффициентов от числа спектральных сигнатур в модели LSMA

Результаты исследований представлены на рис. 3. 350 300 250 200 150 100 50

Dv

0 0,01 0,02 0,03

а) число нулевых коэффициентов - 0, количество использованных для синтеза сигнатур представлено в легенде

0 0,01 0,02 0,03

б) число нулевых коэффициентов - 1,

500

400 300 200 100

t,c

- 10 ......... 8

- 4

Dv

0 0,01 0,02 0,03

в) число нулевых коэффициентов - 2 Рис. 3. Результаты исследования скорости алгоритма решения задачи ЬБМЛ с полными ограничениями

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

Выводы

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

Дальнейшие направления работ связаны с разработкой численно эффективных методов решения расширенных задач спектрального разложения, в которых традиционная задача линейного спектрального разложения (2)-(4) оказывается скорректирована дополнительными ограничениями и/или изменениями целевой функции (см. работу [16]).

Благодарности

Работа выполнена за счёт Российского научного фонда (РНФ) грант № 14-31-00014 «Создание лаборатории прорывных технологий дистанционного зондирования Земли».

Литература

1. Singer, R.B. Mars: Large scale mixing of bright and dark surface materials and implications for analysis of spectral reflectance / R.B. Singer, T.B. McCord // Proceedings of 10th Lunar Planetary Science Conference. - 1979. -P. 1835-1848.

2. Hapke, B. Bidirectional reflectance spectroscopy: 1. Theory / B. Hapke // Journal of Geophysical Research: Solid Earth (1978-2012). - 1981. - Vol. 86(B4). -P. 3039-3054.

3. Johnson, P. A semiempirical method for analysis of the reflectance spectra of binary mineral mixtures / P. Johnson, M. Smith, S. Taylor-George, J. Adams // Journal of Geophysical Research: Solid Earth (1978-2012). -1983. - Vol. 88(B4). - P. 3557-3561.

4. Chang, C.I. Hyperspectral Data Processing: Algorithm Design and Analysis / C.I. Chang. - John Wiley & Sons, 2013. - 1164 p.

5. Chang, C.I. Hyperspectral data exploitation: theory and applications / C.I. Chang. - Wiley-Interscience, 2007. -456 p.

6. Chang, C.I. Hyperspectral imaging: techniques for spectral detection and classification / C.I. Chang. - Springer, 2003. - 370 р.

7. Keshara, N. A Survey of Spectral Unmixing Algorithms / N. Keshara // Lincoln Laboratory Journal. - 2003. -Vol. 14(1). - P. 55-78.

8. Chang, C.I. Constrained subpixel target detection for remotely sensed imagery / C.I. Chang, D.C. Heinz // Geo-science and Remote Sensing, IEEE Transactions on. -2000. - Vol. 38(3). - P. 1144-1159.

9. Heinz, D.C. Fully constrained least squares linear spectral mixture analysis method for material quantification in hy-perspectral imagery / D.C. Heinz, C.I. Chang // Geo-science and Remote Sensing, IEEE Transactions on. -2001. - Vol. 39(3). - P. 529-545.

10. Lawson, C.L. Solving Least Square Problems / C.L. Law-son, R.J. Hanson. - New Jersey: Prentice Hall, Englewood Cliffs, 1974. - 350 p.

11. Haskell, K.H. An algorithm for linear least squares problems with equality and nonnegativity constraints / K.H. Haskell, R.J. Hanson // Mathematical Programming. -1981. - Vol. 21(1). - P. 98-118.

12. Bro, R. A fast Non-negativity-constrained least squares algorithm / R. Bro, S. de Jong // Journal of Chemometrics. -1997. - Vol. 11. - P. 393-401.

13. Rosen, J.B. The gradient projection method for nonlinear programming, part 1: linear constraints / J.B. Rosen // Journal S.I.A.M. - 1960. - Vol. 8. - P. 181-217.

14. Rosen, J.B. The gradient projection method for nonlinear programming, part 1: nonlinear constraints / J.B. Rosen // Journal S.I.A.M. - 1961. - Vol. 9. - P. 514-532.

15. Мину, М. Математическое программирование: Теория и алгоритмы / М. Мину. - Пер. с фр. и предисл.

A.И. Штерн. - М.: Наука, 1990. - 488 с.

16. Денисова, А.Ю. Алгоритмы анализа линейной спектральной смеси на гиперспектральных изображениях с использованием картографической основы / А.Ю. Денисова, В.В. Мясников // Компьютерная оптика -2014. - T. 38, № 2. - C. 297-303.

17. Фурсов, В.А. Тематическая классификация гиперспектральных изображений по показателю сопряжённости /

B.А. Фурсов, С.А. Бибиков, О.А. Байда // Компьютерная оптика. - 2014. - Т. 38, № 1. - С. 154-158.

18. Кузнецов, А.В. Сравнение алгоритмов управляемой поэлементной классификации гиперспектральных изображений / А.В. Кузнецов, В.В. Мясников // Компьютерная оптика. - 2014. - Т. 38, № 3. - C. 494-502.

19. Clark, R.N. The U. S. Geological Survey, Digital Spectral Library: Version 1: 0.2 to 3.0 microns, U.S. Geological Survey 0pen File Report 93-592 // R.N. Clark, G.A. Swayze, A.J. Gallagher, T.V.V. King, W.M. Calvin. - 1993. - 1340 p.

References

1. Singer, R.B. Mars: Large scale mixing of bright and dark surface materials and implications for analysis of spectral reflectance / R.B. Singer, T.B. McCord // Proceedings of 10th Lunar Planetary Science Conference. - 1979. -P. 1835-1848.

2. Hapke, B. Bidirectional reflectance spectroscopy: 1. Theory / B. Hapke // Journal of Geophysical Research: Solid Earth (1978-2012). - 1981. - Vol. 86(B4). - P. 3039-3054.

3. Johnson, P. A semiempirical method for analysis of the reflectance spectra of binary mineral mixtures / P. Johnson, M. Smith, S. Taylor-George, J. Adams // Journal of Geophysical Research: Solid Earth (1978-2012). - 1983. -Vol. 88(B4). - P. 3557-3561.

4. Chang, C.I. Hyperspectral Data Processing: Algorithm Design and Analysis / C.I. Chang. - John Wiley & Sons, 2013.

- 1164 p.

5. Chang, C.I. Hyperspectral data exploitation: theory and applications / C.I. Chang. - Wiley-Interscience, 2007. - 456 p.

6. Chang, C.I. Hyperspectral imaging: techniques for spectral detection and classification / C.I. Chang. - Springer, 2003. -370 p.

7. Keshara, N. A Survey of Spectral Unmixing Algorithms / N. Keshara // Lincoln Laboratory Journal. - 2003. -Vol. 14(1). - P. 55-78.

8. Chang, C.I. Constrained subpixel target detection for remotely sensed imagery / C.I. Chang, D.C. Heinz // Geo-science and Remote Sensing, IEEE Transactions on. - 2000.

- Vol. 38(3). - P. 1144-1159.

9. Heinz, D.C. Fully constrained least squares linear spectral mixture analysis method for material quantification in hy-perspectral imagery / D.C. Heinz, C.I. Chang // Geoscience and Remote Sensing, IEEE Transactions on. - 2001. -Vol. 39(3). - P. 529-545.

10. Lawson, C.L. Solving Least Square Problems / C.L. Law-son , R.J. Hanson. - New Jersey: Prentice Hall, Englewood Cliffs, 1974. - 350 p.

11. Haskell, K.H. An algorithm for linear least squares problems with equality and nonnegativity constraints / K.H. Haskell, R.J. Hanson // Mathematical Programming. -1981. - Vol. 21(1). - P. 98-118.

12. Bro, R. A fast Non-negativity-constrained least squares algorithm / R. Bro, S. de Jong // Journal of Chemometrics. -1997. - Vol. 11. - P. 393-401.

13. Rosen, J.B. The gradient projection method for nonlinear programming, part 1: linear constraints / J.B. Rosen // Journal S.I.A.M. - 1960. - Vol. 8. - P. 181-217.

14. Rosen, J.B. The gradient projection method for nonlinear programming, part 1: nonlinear constraints / J.B. Rosen // Journal S.I.A.M. - 1961. - Vol. 9. - P. 514-532.

15. Minoux, М. Programmation Nathematique: Theorie et Algorithmes Dunod / M. Minoux - Paris: Bordas et C.N.E.T.-E.N.S.T., 1983. - 481 p.

16. Denisova, A.Yu. Algorithms of linear spectral mixture analysis for hyperspectral images using base map / A.Yu. Denisova, V.V. Myasnikov // Computer Optics. -2014. - Vol. 38(2). - P. 297-303.

17. Fursov, VA. Thematic classification of hyperspectral images using conjugacy indicator / V.A. Fursov, S.A. Bibikov, O.A. Bajda // Computer Optics. - 2014. - Vol. 38(1). -P. 154-158.

18. Kuznetsov, A.V. A comparison of algorithms for supervised classification using hyperspectral data / A.V. Kuznet-sov, V.V. Myasnikov // Computer Optics. - 2014. -Vol. 38(3). - P. 494-502.

19. Clark, R.N. The U. S. Geological Survey, Digital Spectral Library: Version 1: 0.2 to 3.0 microns, U.S. Geological Survey Open File Report 93-592 // R.N. Clark, G.A. Swayze, A.J. Gallagher, T.V.V. King, W.M. Calvin. -1993. - 1340 p.

FULLY CONSTRAINED LINEAR SPECTRAL UNMIXING ALGORITHM FOR HYPERSPECTRAL IMAGE ANALYS

A.Yu. Denisova, V.V. Myasnikov Samara State Aerospace University, Image Processing Systems Institute, Russian Academy of Sciences

Abstract

In this article, a novel linear spectral unmixing algorithm is proposed and analyzed. The linear spectral mixture defines a model of pixels for hyperspectral images by means of spectral signatures. A set of spectral signatures is assumed to be known. Constraints are imposed on the spectral

mixture coefficients: the sum of the coefficients is equal to unity and each coefficient is nonnegative. The results of the algorithm quality and speed analysis are described in the paper.

Key words: hyperspectral images, linear spectral mixing, constraints, hyperspectral analysis, least squares method.

Сведения об авторах Денисова Анна Юрьевна, 1988 года рождения. В 2011 году защитила диплом магистра прикладной математики и информатики в Самарском государственном аэрокосмическом университете (СГАУ) (национальном исследовательском университете). В 2014 году окончила аспирантуру СГАУ. В настоящее время работает младшим научным сотрудником научно-исследовательской лаборатории прорывных технологий дистанционного зондирования Земли СГАУ и стажёром-исследователем в ЛММОИ в Институте систем обработки изображений РАН. Круг научных интересов включает обработку изображений, геоинформационные системы.

E-mail: denisova_ay@geosamara. ru.

Anna Yurievna Denisova (b. 1988). Graduated from Samara State Aerospace University in 2011 as Master of Mathematics and Computer Science. Now works in laboratory № 97 at Samara State Aerospace University and at the Image Processing Systems Institute of the RAS. The area of research interest includes image processing and geoinformational systems.

Мясников Владислав Валерьевич, 1971 года рождения. В 1994 году окончил Самарский государственный аэрокосмический университет (СГАУ). В 1995 году поступил в аспирантуру СГАУ, в 1998 году защитил диссертацию на соискание степени кандидата технических наук, а в 2008 - диссертацию на соискание степени доктора физико-математических наук. В настоящее время работает ведущим научным сотрудником научно-исследовательской лаборатории прорывных технологий дистанционного зондирования Земли СГАУ и ведущим научным сотрудником в Федеральном государственном бюджетном учреждении науки Институт систем обработки изображений РАН, а также профессором кафедры геоинформатики и информационной безопасности СГАУ. Круг научных интересов включает цифровую обработку сигналов и изображений, компьютерное зрение, распознавание образов, искусственный интеллект и геоинформатику. Имеет более 100 публикаций, в том числе 40 статей и две монографии (в соавторстве). Член Российской ассоциации распознавания образов и анализа изображений.

E-mail: vmyas@smr.ru . Страница в интернете: http://www.ipsi.smr.ru/staff/MyasVV.htm .

Vladislav Valerievich Myasnikov (1971 b.), graduated (1994) from S.P. Korolyov Samara State Aerospace University (SSAU). He received his PhD in Technical Sciences (2002) and DrSc degree in Physics & Maths (2008). At present he is a leading researcher at the laboratory №97 at SSAU and at the Image Processing Systems Institute of the Russian Academy of Sciences and holds a part-time position of Associate Professor at Geoinformatics and Information Security department at SSAU. The area of interests includes digital signals and image processing, geoinformatics, neural networks, computer vision, pattern recognition and artificial intelligence. He's list of publications contains about 100 scientific papers, including 40 articles and 2 monographs. He is a member of Russian Association of Pattern Recognition and Image Analysis.

Поступила в редакцию 6 ноября 2014 г.