ОЦЕНКА ТОЧНОСТИ РАСПОЗНАВАНИЯ КЛАССОВ ПРИ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКЕ АЭРОФОТОСНИМКОВ
Оценка точности распознавания классов при автоматизированной обработке аэрофотоснимков 35
УДК 004.932, 631.171
И. В. МАНЫЛОВ
ОЦЕНКА ТОЧНОСТИ РАСПОЗНАВАНИЯ КЛАССОВ ПРИ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКЕ АЭРОФОТОСНИМКОВ
Сравниваются алгоритмы расчета евклидова расстояния и расчета расстояния Махаланобиса с целью повышения точности дешифровки аэрофотоснимков, используемых для оценки состояния сельскохозяйственных земель.
Ключевые слова: аэрофотоснимок, сельское хозяйство, цифровая классификация, дешифровка, анализ изображений, автоматизация.
В последнее время возросла потребность в достоверной информации о состоянии земель сельскохозяйственного назначения и в оценке их использования как для обеспечения деятельности агропромышленных предприятий, так и с целью охраны окружающей среды. Многие хозяйства по-прежнему отдают предпочтение полевым исследованиям и ручной дешифровке снимков, однако эти методы имеют целый ряд недостатков, к основным из которых можно отнести следующие:
— высокий субъективизм результатов, т.е. зависимость от опыта и предпочтений дешифровщика;
— низкая скорость получения результатов дешифровки; — возрастающая стоимость дешифровки, связанная с увеличением площади сельскохозяйственных земель или количества снимков [1]. Алгоритмы автоматизированной дешифровки средствами вычислительной техники облегчают обработку и анализ информации, повышают скорость и достоверность результатов. Поэтому автоматизированная дешифровка является наиболее перспективной и востребованной в сегодняшнее время. Чтобы выделить на аэрофотоснимке структуры площадей или обнаружить изменения, необходимо анализировать характеристики пространственного распределения пикселов изображения. В настоящее время одним из наиболее разработанных методов такого анализа является классификация объектов изображения. Задача классификации — формализованная, в ней присутствует множество объектов, разделенных по некоторым признакам на классы. Задано конечное множество объектов (выборка), для которых известно, к каким классам они относятся, принадлежность остальных объектов неизвестна. Требуется построить алгоритм, позволяющий классифицировать произвольный объект из исходного множества. Алгоритм расчета расстояния между объектами является ключевым элементом задачи классификации (от него зависит, к какому классу будет отнесена исследуемая точка аэрофотоснимка), алгоритм оценивает несходство, или расстояние между объектами [2]. При проведении съемки сверхлегкими летательными аппаратами, как правило, используется только три канала информации в видимом диапазоне спектра, но разрешение этих снимков значительно выше, чем при съемке из космоса. Поэтому далее в статье будут рассмотрены два алгоритма классификации именно аэрофотоснимков, полученных с высоты 1—3 км и имеющих три канала информации: красный, зеленый и синий (R, G и B) — алгоритмы расчета евклидова расстояния и расчета расстояния Махаланобиса. Выбор данных алгоритмов обусловлен тем, что формула расчета евклидова расстояния — одна из самых простых и широко применяемых для расчета расстояния в N-мерном
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
36 И. В. Манылов
пространстве, а формула расчета расстояния Махаланобиса — одна из самых сложных. Пер-
вый алгоритм требует значительно меньше вычислительных ресурсов, чем второй.
Для классификации аэрофотоснимков будем использовать метод классификации с обу-
чением. Для этого перед проведением классификации необходимо выбрать на исходном
снимке эталонные области (обучающие выборки) и присвоить им класс. Количество классов
зависит от того, сколько областей необходимо получить на результирующем снимке. Такой
подход позволяет не учитывать при сравнении алгоритмов расчета режимы съемки.
Для каждой обучающей выборки предварительно рассчитывается центр тяжести по сле-
дующей формуле:
∑µi
=
1 m
m
X
j =1
ji ,
(1)
где m — количество точек в обучающей выборке; i — канал аэрофотоснимка.
Рассчитывается расстояние между центром тяжести обучающей выборки и исследуемой
точкой аэрофотоснимка [3].
Алгоритм расчета евклидова расстояния. Наиболее простым алгоритмом расчета яв-
ляется евклидово расстояние, которое вычисляется по формуле:
N
∑D( X j , Xi ) = 2 ( X ki − X kj )2 , k =1
где N — размерность пространства; X ki , X kj — значения объектов i и j в k-м измерении. Для снимков с тремя каналами R, G, B имеем:
(2)
D( X
j,
Xi )
=
2
⎡⎣( X Ri
−
X Rj )2
+ ( XGi
−
XGi )2
+
( X Bi
−
X
Bj
)2
⎤ ⎦
,
(3)
где XRi, XRj — значение канала R объекта i и j; XGi, XGj — значение канала G объекта i и j; XBi, XBj — значение канала B объекта i и j.
Как видно из формулы алгоритма расчета евклидова расстояния, не учитывается ориентация
точек обучающей выборки в пространстве [4]. Для обучающих выборок, которые состоят из то-
чек, равноудаленных от центра тяжести, это не имеет
значения. Но для реальных обучающих выборок, в 250 которых присутствуют точки с разными значениями 200 цветовых составляющих R, G, B, это приводит к уве-
X1 µ1
X2 µ2
D(N,X2)
150 B 100
личению количества неверно классифицированных областей аэрофотоснимков.
50 В качестве примера возьмем две обучающие
D(N,X1) N
250 200
выборки X1 и X2 (луг и дорога). Взаимное расположение точек обучающей выборки в трехмерном про-
50
100 150 R
200
250
150
100 50
G
странстве R, G и B показано на рис. 1: указана произ-
вольная точка N и два расстояния D(N,X1) и D(N,X2), вычисленные по формуле (3). Расстояние D(N,X1)
Рис. 1
меньше расстояния D(N,X2), и точка N будет класси-
фицирована как класс X1. Видно, что точка N находится ближе к классу X2 и должна быть отнесе-
на к нему. Такая ошибка классификации вызвана тем, что обучающие выборки имеют эллипсоид-
ное распределение точек в пространстве.
Алгоритм расчета расстояния Махаланобиса. Для более точной классификации
аэрофотоснимков необходимо учитывать размеры области, занимаемой точками обучающей
выборки, и ориентацию этой области в пространстве. Такой алгоритм впервые был сформу-
лирован индийским статистиком Махаланобисом в 1936 г. и называется расстоянием
Махаланобиса [5].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
Оценка точности распознавания классов при автоматизированной обработке аэрофотоснимков 37
Формально расстояние Махаланобиса от многомерного вектора X=(X1, X2, X3, …, XN)T до множества со средним значением µ=(µ1, µ2, µ3, …, µN)T и матрицей ковариации S определяется следующим образом:
DM ( X ) = ( X − µ)T S−1( X − µ),
(4)
где DM(X) — расстояние Махалонобиса. Ковариационная матрица в теории вероятностей — это матрица, составленная из по-
парных ковариаций элементов двух случайных векторов и являющаяся обобщением диспер-
сии для многомерной случайной величины. Собственные векторы и собственные числа этой
матрицы позволяют оценить размеры и форму облака распределения такой случайной вели-
чины, аппроксимировав его эллипсоидом. Из рис. 1 видно, что аппроксимация эллипсоидом
очень хорошо описывает массив точек обучающих выборок X1 и X2. Расстояние Махаланобиса — это расстояние между заданной точкой и центром тяже-
сти, деленное на ширину эллипсоида в направлении заданной точки. Если матрица ковариа-
ции является единичной, то расстояние Махаланобиса становится равным расстоянию
Евклида. Если матрица ковариации диагональная (но необязательно единичная), то получив-
шаяся мера расстояния равна нормализованному евклидовому расстоянию.
Оценка эффективности алгоритмов расчета расстояния. Для оценки эффективности
алгоритмов было разработано программное обеспечение, которое позволяет производить
классификацию объектов на аэрофотоснимках с использованием вышеописанных алгоритмов
и оценивать точность распознавания классов.
Результаты классификации по алгоритму расчета евклидова расстояния отражены на
рис. 2, а, по алгоритму Махаланобиса — на рис. 2, б.
а)
б)
Рис. 2
Для оценки точности классификации фрагмент, показанный на рис. 2, был обработан в программе MultiSpec с использованием тех же обучающих выборок. Это обработанное фото было использовано в качестве эталона при оценке точности классификации по двум алгоритмам: построения матрицы ошибок и расчета индекса каппа-статистики.
Матрица ошибок формируется следующим образом: элемент Xkl матрицы ошибок равен числу пикселов класса k, распознанных как класс l. Элемент матрицы Xkk равен числу пикселов класса k, распознанных как класс k. Число правильно классифицированных пикселов располагается на диагонали матрицы. На основе матрицы ошибок при обобщении результатов
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
38 И. В. Манылов
правильно классифицированных точек был использован так называемый индекс каппа-
статистики, вносящий поправку на случайность, он вычисляется по формуле [6]:
mm
m
Z ∑ ∑ Xkl − ∑ SkTl
∑K =
kl
Z2 −
k =1,l=1
m
SiT j
,
k =1,l=1
(5)
m
∑где Z — общее число пикселов; m — число классов; Sk = xkl — сумма элементов k-строки; l =1
m
∑Tl = xkl — сумма элементов l-го столбца. k =1
Дополнительно рассчитывается и общая точность распознавания классов (ii) по сле-
дующей формуле:
m
∑ Xii
Pc =
i
Z
.
(6)
Кроме этого используется степень согласованности сравниваемых снимков на основе
индекса каппа-статистики, представленная в таблице [7].
Критерии согласованности данных классификации
K Согласованность
УДК 004.932, 631.171
И. В. МАНЫЛОВ
ОЦЕНКА ТОЧНОСТИ РАСПОЗНАВАНИЯ КЛАССОВ ПРИ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКЕ АЭРОФОТОСНИМКОВ
Сравниваются алгоритмы расчета евклидова расстояния и расчета расстояния Махаланобиса с целью повышения точности дешифровки аэрофотоснимков, используемых для оценки состояния сельскохозяйственных земель.
Ключевые слова: аэрофотоснимок, сельское хозяйство, цифровая классификация, дешифровка, анализ изображений, автоматизация.
В последнее время возросла потребность в достоверной информации о состоянии земель сельскохозяйственного назначения и в оценке их использования как для обеспечения деятельности агропромышленных предприятий, так и с целью охраны окружающей среды. Многие хозяйства по-прежнему отдают предпочтение полевым исследованиям и ручной дешифровке снимков, однако эти методы имеют целый ряд недостатков, к основным из которых можно отнести следующие:
— высокий субъективизм результатов, т.е. зависимость от опыта и предпочтений дешифровщика;
— низкая скорость получения результатов дешифровки; — возрастающая стоимость дешифровки, связанная с увеличением площади сельскохозяйственных земель или количества снимков [1]. Алгоритмы автоматизированной дешифровки средствами вычислительной техники облегчают обработку и анализ информации, повышают скорость и достоверность результатов. Поэтому автоматизированная дешифровка является наиболее перспективной и востребованной в сегодняшнее время. Чтобы выделить на аэрофотоснимке структуры площадей или обнаружить изменения, необходимо анализировать характеристики пространственного распределения пикселов изображения. В настоящее время одним из наиболее разработанных методов такого анализа является классификация объектов изображения. Задача классификации — формализованная, в ней присутствует множество объектов, разделенных по некоторым признакам на классы. Задано конечное множество объектов (выборка), для которых известно, к каким классам они относятся, принадлежность остальных объектов неизвестна. Требуется построить алгоритм, позволяющий классифицировать произвольный объект из исходного множества. Алгоритм расчета расстояния между объектами является ключевым элементом задачи классификации (от него зависит, к какому классу будет отнесена исследуемая точка аэрофотоснимка), алгоритм оценивает несходство, или расстояние между объектами [2]. При проведении съемки сверхлегкими летательными аппаратами, как правило, используется только три канала информации в видимом диапазоне спектра, но разрешение этих снимков значительно выше, чем при съемке из космоса. Поэтому далее в статье будут рассмотрены два алгоритма классификации именно аэрофотоснимков, полученных с высоты 1—3 км и имеющих три канала информации: красный, зеленый и синий (R, G и B) — алгоритмы расчета евклидова расстояния и расчета расстояния Махаланобиса. Выбор данных алгоритмов обусловлен тем, что формула расчета евклидова расстояния — одна из самых простых и широко применяемых для расчета расстояния в N-мерном
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
36 И. В. Манылов
пространстве, а формула расчета расстояния Махаланобиса — одна из самых сложных. Пер-
вый алгоритм требует значительно меньше вычислительных ресурсов, чем второй.
Для классификации аэрофотоснимков будем использовать метод классификации с обу-
чением. Для этого перед проведением классификации необходимо выбрать на исходном
снимке эталонные области (обучающие выборки) и присвоить им класс. Количество классов
зависит от того, сколько областей необходимо получить на результирующем снимке. Такой
подход позволяет не учитывать при сравнении алгоритмов расчета режимы съемки.
Для каждой обучающей выборки предварительно рассчитывается центр тяжести по сле-
дующей формуле:
∑µi
=
1 m
m
X
j =1
ji ,
(1)
где m — количество точек в обучающей выборке; i — канал аэрофотоснимка.
Рассчитывается расстояние между центром тяжести обучающей выборки и исследуемой
точкой аэрофотоснимка [3].
Алгоритм расчета евклидова расстояния. Наиболее простым алгоритмом расчета яв-
ляется евклидово расстояние, которое вычисляется по формуле:
N
∑D( X j , Xi ) = 2 ( X ki − X kj )2 , k =1
где N — размерность пространства; X ki , X kj — значения объектов i и j в k-м измерении. Для снимков с тремя каналами R, G, B имеем:
(2)
D( X
j,
Xi )
=
2
⎡⎣( X Ri
−
X Rj )2
+ ( XGi
−
XGi )2
+
( X Bi
−
X
Bj
)2
⎤ ⎦
,
(3)
где XRi, XRj — значение канала R объекта i и j; XGi, XGj — значение канала G объекта i и j; XBi, XBj — значение канала B объекта i и j.
Как видно из формулы алгоритма расчета евклидова расстояния, не учитывается ориентация
точек обучающей выборки в пространстве [4]. Для обучающих выборок, которые состоят из то-
чек, равноудаленных от центра тяжести, это не имеет
значения. Но для реальных обучающих выборок, в 250 которых присутствуют точки с разными значениями 200 цветовых составляющих R, G, B, это приводит к уве-
X1 µ1
X2 µ2
D(N,X2)
150 B 100
личению количества неверно классифицированных областей аэрофотоснимков.
50 В качестве примера возьмем две обучающие
D(N,X1) N
250 200
выборки X1 и X2 (луг и дорога). Взаимное расположение точек обучающей выборки в трехмерном про-
50
100 150 R
200
250
150
100 50
G
странстве R, G и B показано на рис. 1: указана произ-
вольная точка N и два расстояния D(N,X1) и D(N,X2), вычисленные по формуле (3). Расстояние D(N,X1)
Рис. 1
меньше расстояния D(N,X2), и точка N будет класси-
фицирована как класс X1. Видно, что точка N находится ближе к классу X2 и должна быть отнесе-
на к нему. Такая ошибка классификации вызвана тем, что обучающие выборки имеют эллипсоид-
ное распределение точек в пространстве.
Алгоритм расчета расстояния Махаланобиса. Для более точной классификации
аэрофотоснимков необходимо учитывать размеры области, занимаемой точками обучающей
выборки, и ориентацию этой области в пространстве. Такой алгоритм впервые был сформу-
лирован индийским статистиком Махаланобисом в 1936 г. и называется расстоянием
Махаланобиса [5].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
Оценка точности распознавания классов при автоматизированной обработке аэрофотоснимков 37
Формально расстояние Махаланобиса от многомерного вектора X=(X1, X2, X3, …, XN)T до множества со средним значением µ=(µ1, µ2, µ3, …, µN)T и матрицей ковариации S определяется следующим образом:
DM ( X ) = ( X − µ)T S−1( X − µ),
(4)
где DM(X) — расстояние Махалонобиса. Ковариационная матрица в теории вероятностей — это матрица, составленная из по-
парных ковариаций элементов двух случайных векторов и являющаяся обобщением диспер-
сии для многомерной случайной величины. Собственные векторы и собственные числа этой
матрицы позволяют оценить размеры и форму облака распределения такой случайной вели-
чины, аппроксимировав его эллипсоидом. Из рис. 1 видно, что аппроксимация эллипсоидом
очень хорошо описывает массив точек обучающих выборок X1 и X2. Расстояние Махаланобиса — это расстояние между заданной точкой и центром тяже-
сти, деленное на ширину эллипсоида в направлении заданной точки. Если матрица ковариа-
ции является единичной, то расстояние Махаланобиса становится равным расстоянию
Евклида. Если матрица ковариации диагональная (но необязательно единичная), то получив-
шаяся мера расстояния равна нормализованному евклидовому расстоянию.
Оценка эффективности алгоритмов расчета расстояния. Для оценки эффективности
алгоритмов было разработано программное обеспечение, которое позволяет производить
классификацию объектов на аэрофотоснимках с использованием вышеописанных алгоритмов
и оценивать точность распознавания классов.
Результаты классификации по алгоритму расчета евклидова расстояния отражены на
рис. 2, а, по алгоритму Махаланобиса — на рис. 2, б.
а)
б)
Рис. 2
Для оценки точности классификации фрагмент, показанный на рис. 2, был обработан в программе MultiSpec с использованием тех же обучающих выборок. Это обработанное фото было использовано в качестве эталона при оценке точности классификации по двум алгоритмам: построения матрицы ошибок и расчета индекса каппа-статистики.
Матрица ошибок формируется следующим образом: элемент Xkl матрицы ошибок равен числу пикселов класса k, распознанных как класс l. Элемент матрицы Xkk равен числу пикселов класса k, распознанных как класс k. Число правильно классифицированных пикселов располагается на диагонали матрицы. На основе матрицы ошибок при обобщении результатов
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 5
38 И. В. Манылов
правильно классифицированных точек был использован так называемый индекс каппа-
статистики, вносящий поправку на случайность, он вычисляется по формуле [6]:
mm
m
Z ∑ ∑ Xkl − ∑ SkTl
∑K =
kl
Z2 −
k =1,l=1
m
SiT j
,
k =1,l=1
(5)
m
∑где Z — общее число пикселов; m — число классов; Sk = xkl — сумма элементов k-строки; l =1
m
∑Tl = xkl — сумма элементов l-го столбца. k =1
Дополнительно рассчитывается и общая точность распознавания классов (ii) по сле-
дующей формуле:
m
∑ Xii
Pc =
i
Z
.
(6)
Кроме этого используется степень согласованности сравниваемых снимков на основе
индекса каппа-статистики, представленная в таблице [7].
Критерии согласованности данных классификации
K Согласованность