Комплекс алгоритмов неконтролируемой классификации для распознавания леса на аэрокосмических изображениях

Институт вычислительной математики

и математической геофизики СО РАН

(просп. акад. Лаврентьева 6, Новосибирск 630090, Россия),

Тел.: [phone], Е-mail: *****@***sscc. ru.

Комплекс алгоритмов неконтролируемой классификации для распознавания леса на аэрокосмических изображениях [1]

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

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

Известны два подхода для распознавания объектов данных дистанционного зондирования: контролируемая и неконтролируемая классификация. Первая использует статистические выборки по тестовым участкам, хорошо исследованным наземными методами, вторая анализирует многомерные данные непосредственно, применяя кластерные методы: распределение по к центрам, иерархические, по многомерной гистограмме [12]. Ввиду огромного объема данных многие методы затруднительно применять ввиду значительных вычислительных затрат. Кроме того, алгоритмы часто требуют задания числа кластеров или других параметров, которые трудно заранее определить. Представленный комплекс содержит алгоритмы, которые базируются на двух быстрых кластерных методах, не требующих задания числа кластеров. Главная причина их быстроты – однократный просмотр данных. Один из методов основан на многомерной гистограмме, непараметрический, не предполагает никакой априорной информации. Метод работает исключительно в векторном пространстве признаков. Другой алгоритм использует пространственную информацию взаимосвязи пикселей в плоскости изображения. Он требует настройки некоторых параметров. Эти алгоритмы могут использоваться для классификации спутниковых изображений по спектральным признакам. На аэроснимках для распознавания леса используются текстурные признаки. Комплекс был предложен ранее для ЭВМ БЭСМ-6 [2]. С тех пор алгоритмы и системы признаков совершенствуются. Тенденции - более полная автоматизация, лучшее различение объектов, качество классификации.

Алгоритмы классификации. Гистограммные алгоритмы имеют недостаток, - для хранения гистограммы требуется много памяти. Но в используемом алгоритме [15], [7], [8] хранится лишь число реально присутствующих на изображении N-мерных векторов в упорядоченном по возрастанию списке, который занимает существенно меньше места, чем весь объем пространства измерений байтов. Предложена система быстрого доступа к списку сочетанием хеширования и сортировки векторов для N>3 [9]. Большое число данных позволяет рассматривать многомерную гистограмму дискретного векторного пространства как приближение функции распределения векторов. Суть алгоритма состоит в нахождении локальных максимумов многомерной гистограммы и отнесении векторов к соответствующим максимумам. Для каждого вектора строится элементарный граф в направлении градиента плотности вероятности в списке соседей. Вектора связываются в деревья. Когда граф достигает локального максимума, то вся цепочка векторов относится к тому же кластеру, что и максимум. Алгоритм разделяет векторное пространство по унимодальным кластерам. Границы кластеров соответствуют долинам гистограммы. При прямом применении алгоритма обнаруживается большое число максимумов гистограммы, которые могут быть случайными всплесками. Предложенный алгоритм [10] позволяет выбрать детальность классификации и оценить ее качество в смысле меры изолированности кластеров. Параметром детальности является число уровней квантования n векторного пространства. Предложены мера изолированности для унимодального кластера (1), и мера качества распределения в целом по кластерам (2):

(1) , (2)

где значение гистограммы в i-той точке границы кластера j, число точек границы кластера, максимальное значение гистограммы.

Границы кластера легко найти, имея список соседей каждого вектора. Чем меньше , тем меньше плотность векторов на границе кластера. Минимумы соответствуют лучшим классификациям. Показано экспериментально, что лучшие в смысле меры (2), распределения соответствуют информационным классам покрытия Земли как для спутниковых снимков по спектральным признакам [9], так и для аэроснимков леса по текстурным признакам [11].

Для примера рассмотрим автоматическое выделение областей, занятых хвойным лесом на фрагменте пяти-спектрального космического изображения Западной Сибири, полученного со спутника NOAA в конце апреля. На рис.1 слева показан RGB файл, где B и G соответствуют видимому, R ближнему инфракрасному диапазонам. Справа вверху сплошное белое облако. Светлые оттенки соответствуют хвойным насаждениям (на цветном изображении - зеленоватым), еще покрытым тающим снегом. Вода озер выделяется темными пятнами, Обское море подо льдом. Справа показана автоматически полученная кластерная карта лучшей классификации. Спектральные признаки этих объектов хорошо разделены в векторном пространстве. Поэтому лучшая классификация соответствует небольшому числу уровней квантования n=15, и значение меры (2) мало m(n)=0.15. Всего получен 21 кластер (рис.1 справа). Расположение кластеров соответствуют представленным объектам. К хвойному лесу относится два кластера.

Рисунок 1: Слева спутниковое изображение Западной Сибири: в левом верхнем углу озеро Чаны, в нижнем левом Кулундинское, от середины немного вниз Обское водохранилище. Справа кластерная карта. Наибольшие кластеры: 1- оттаявшая поверхность, не занятая хвойным лесом, 2, 3 – хвойный лес, 4 – море подо льдом, 5 – вода озер, 6 – сплошное облако.

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

На рис.2а показано изображение лесного ландшафта Западной Сибири на аэроснимке масштаба 1:50000. Разрешение: 5м/пиксель. Представлены кедровники всех семи возрастных фаз. По диагонали снимка – луговая пойма реки. Лес данного типа является березово-кедровым сообществом. Возобновляясь на гарях, он проходит определенный путь развития [16]. На ранних фазах интенсивно развивается береза. Затем кедр пробивается в верхний ярус и вытесняет березу. Кроме кедровников, на изображении присутствуют сосновые насаждения одного возраста, близкие кедровникам по визуальным свойствам. На рис.2c представлена картосхема выделов участка, построенная лесоводами по данным наземной таксации.

Рисунок 2: (a) Изображение лесного ландшафта. (b) Кластерная карта. (с) Картосхема наземной таксации. Большие цифры - номера фаз кедровников, 7С – чередование участков кедровников седьмой фазы и сосняков, С – сосняки, светло-серый оттенок относятся к пойме реки и болотам B. (d) Векторная диаграмма.

На рис. 2b кластерная карта классификации по двум признакам: среднему тону TONE и признаку MEAN статистики разностей Харалика [13]. Для лучшего распределения, при котором различимы кедровые и сосновые насаждения для 37<n<255: n=78, m(78)=0.45, размер окна 18*18. K(n)=36, лесу соответствует 17.

Алгоритм, основанный на выделении однородных областей. На первом этапе кластерный алгоритм выделяет однородные по признакам и связные в плоскости изображения области. На втором, алгоритм последовательно выбирает наибольшие по площади однородные области и присоединяет к ним оставшиеся. Объединение векторов регулируется несколькими порогами [4], [1].

Классификация, основанная на сплайнах. Учитывая постепенный рост деревьев и плавное изменение текстуры с возрастом, предложено использовать сплайны для моделирования возрастной динамики текстурных признаков леса определенного типа [16]. Возраст лесонасаждений, определенный лесоводами, и значения признаков соответствующих однородных областей используются как узловые точки. Выбраны локальные параболические сплайны, сохраняющие изогеометрию [5]. Кусочно-монотонные сплайны облегчают решение обратной задачи определения возраста насаждения по признакам. Сплайны могут затем использоваться для определения возраста леса на других снимках того же сеанса съемки, но уже без проведения наземной таксации. Этот подход применен для классификации ценнейших кедровников, занимающих обширные территории Западной Сибири.

Текстурные признаки. Первая система, используемая нами для леса, это статистика первого порядка [1]. Более информативна статистика Харалика, например, вектор разностей , i-ая компонента которого является вероятностью того, что модуль разности уровней серого тона в паре соседних точек, разделенных векторным расстоянием , равен i [13].

Здесь предлагается для анализа изображений использовать признаки, основанные на авторегрессионной модели текстуры SAR[14]. На дискретном изображении задан двумерный массив уровней серого {g(x, y); x, y = 0,1,…,M-1}. Верхний левый угол (х=0, y=0), нижний правый (x=M – 1, y=M – 1). Полагая среднее выборки равным нулю, g(x, y) определяется на тороидальной решетке :

где N - набор соседей пикселя (x,y), - коэффициенты, - сложение по модулю M, -независимые одинаково распределенные гаусовские случайные величины с нулевым средним и единичной дисперсией, - общая дисперсия шума. N состоит из набора пар координат соседей по отношению к пикселю (x,y), исключая (0,0). Общепринятая разметка = {(1,0), (0,1), (-1,0), (0,-1)}.

a b c d

Рисунок 3: .а) На изображении лесного ландшафта представлены кедровые и сосновые насаждения различных фаз. b) Картосхема изображения, сосновые насаждения: I – фаза 13, II – фаза 6, IV – фаза 3, III – кедровники различных фаз. c) Кластерная карта по признакам SAR. d) Кластерная карта по признакам Харалика.

При выборе симметричного набора соседей, [14]. Применен метод максимального правдоподобия (ML) для приближенного вычисления параметров модели [14]. Сравнение двух систем признаков SAR и Харалика показало, что признаки модели обладают большей различительной мощностью. Для анализа было выбрано изображение, содержащее очень близкие текстуры сосняков и кедровников определенных фаз развития. По Харалику был выбран признак , при r=0, =0. По модели для симметричной части , был взят только параметр , характеризующий степень зернистости текстуры. Вторым признаком для обеих систем был средний тон. Только признаки модели SAR позволили отнести объекты леса в различные кластеры, их положение на кластерной карте соответствовало картосхеме наземной таксации.

Интерфейс. Комплекс реализован средствами VISUAL C++ в многооконном режиме. Параметры задаются в диалоговых окнах. Диаграммы распределения признаков, карты кластеров, таблицы их характеристик могут быть показаны на экране и сохранены в файл. Раскраска кластеров производится автоматически. По указанию курсора соответствующий кластер высвечивается инвертированным цветом. Исследованные типы леса обладают изотропной текстурой на аэроснимках, для их классификации по типам и фазам достаточно было двух признаков. Поэтому предполагается введение в комплекс визуализации 3D полутоновых изображений двумерной гистограммы на основе разработанной технологии с использованием бикубических параметрических сплайнов [17].

References

1.  , , Автоматизация процесса обработки аэрокосмических снимков в целях инвентаризации лесов // Ж.: Исследование Земли из космоса. АН СССР.1981. № 6. С.93-100.

2.  , , Комплекс программ анализа изображений. – Новосибирск: препринт СО АН СССР. ВЦ. № 000. 1985. 27 C.

3.  Лесная таксация. – Москва, Ленинград: Гослесбумиздат,1971. 365 С.

4.  , Алгоритмы тематического дешифрирования многоспектральной аэрокосмической видеоинформации.//Ж. Космические исследования.1978.т. XVI. вып.3.С.388 - 393.

5.  Построение сплайнов, сохраняющих изогеометрию. – Новосибирск: препринт СО АН СССР. ВЦ. № 000. 1982. С.29.

6.  Аэрокосмический мониторинг лесного покрова –Новосибирск: «Наука".1991.C. 238.

7.  Кластеризация многоспектральных изображений с помощью анализа многомерной гистограммы. Новосибирск. Сб.: Математические и технические проблемы обработки изображений. СО АН СССР. 1986. С. 52-57.

8.  Классификация многоспектральных космических изображений поверхности Земли с помощью разделения многомерной гистограммы по унимодальным кластерам // Ж. Вестник КазНУ., сер. географическая. 2004. N 2(19). С. 206-210.

9.  Многомерная гистограмма и разделение векторного пространства признаков по унимодальным кластерам. // Труды международной конференции GraphiCon’2005. 2005. C.267-274.

10. Оценка качества классификации многоспектральных изображений гистограммным методом // Ж. Автометрия. 2007. Том 43, №1. C. 37-43.

11. Автоматическая классификация изображений по текстурным признакам. // Труды 8-ой международной конференции "Распознавание образов и анализ изображений: новые информационные технологии". Йошкар-Ола. 2007. C.198-202.

12. Gong P. & P. J. Howarth. An assessment of some factors influencing multispectral land-cover classification. // J. Photogrametric Engineering and Remote Sensing, 56(5), 1990. P.597-603.

13. Haralick R. M., Shanmugam K., Dinstein I. Textural Features for Image Classification // J. IEEE Trans. Syst. Man. Cybern. 1973.Vol. SMS-3. P. 610- 621.

14. Kashyap R.L., Chellapa R. Estimation and Choice of Neighbors in spatial interaction Models of Images. // J. IEEE Trans. Inform. Theory. 1983. vol.1. P. 60-72.

15. Narendra P. M. and Goldberg M. A non-parametric clustering scheme for LANDSAT // J. Pattern Recognition. 1977. No. 9. P. 207-215.

16. Sedykh V. N., Sidorova V. S. Texture of the Forest Communities in Aeroimages Mapping Sciences and Remote Sensing. USA: V. H. Winston & Sons.1985. P.51-55.

17. Sidorova V. S., Razumenko G. P. Imaging of a 3D Surface for the Analysis of External and Internal Structure of a Tooth. // J. Pattern Recognition and Image Analysis. 1999. Vol. 9. No.2. P.383-389.

[1] Работа выполнена частично при финансовой поддержке Российского фонда фундаментальных исследований (проект №07-07-00085а).