Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Билет 10
Геометрические преобразования и геопривязка изображений. Метод наименьших квадратов. Опорные точки. Выделение опорных точек на изображении. Невязки и контроль ошибок.
Многие задачи тематического дешифрирования сводятся к взаимному
сопоставлению между собой изображений, сформированных с помощью датчиков различных физических полей. Ярким примером может служить развитие дистанционных методов контроля природных ресурсов и динамики экосистем (так называемого мониторинга), что сводится к сопоставлению снимков одной и той же территории, полученных в разное время и/или с помощью различных датчиков. Чаще всего используются оптическое, радиолокационное, радиотепловое, магнитное и другие поля. Совместное использование различных физических полей требует предварительной обработки соответствующих им изображений, например, с целью перевода изображений в одну спектральную область.
На практике изображения одного и того же объекта или участка местности, полученные в разное время или с помощью различных датчиков,
могут значительно различаться один от другого. Отсюда вытекает ряд важных задач привязки, а также точной взаимной геометрической и амплитудной коррекции для последующего совместного анализа. В любом случае это требует установления соответствия между элементами исходных изображений, что сводится к выделению так называемых опор ных (по другому, реперных или сопряженных) точек на изображениях, по которым можно осуществить координатную привязку снимков с одновременной геометрической коррекцией.
(Точки на двух изображениях называются сопряженными, если они являются образами одной точки сцены [5.1, гл.13]). Например, аэрокосмический компьютерный мониторинг предполагает наличие дискретного по времени наблюдения с небольшим временным интервалом, и поэтому, когда движущаяся камера фиксирует яркостный образ наблюдаемого объекта (оптическую поверхность) в виде последовательности изображений, то этот образ от снимка к снимку деформируется вследствие перспективных искажений и изменения положения камеры. Геометрия соответствующих деформаций моделируется проективными преобразованиями, которые составляют более обширный класс, нежели известные преобразования евклидовой геометрии (достаточно сказать, что длины и углы в проективной геометрии не сохраняются, а параллельные линии могут пересекаться! [5.12]).
Восстановление пространственного рельефа по стереоснимкам приводит к проблеме идентификации: установления точного координатного (поточечного) соответствия элементов стереоизображений. Решение этой задачи состоит в выделении пар реперных фрагментов и оценивании параметров «расхождения» соответственных точек (это именуется в стереофотограмметрии бинокулярной диспарантностью), по которым можно восстановить функцию геометрического преобразования и оценить поверхность трехмерной сцены (рельеф)[5.5].
В последние пятнадцать лет спутниковые данные позволили, используя новые методы измерений, определить оптимально соответствующий поверхности Земли эллипсоид, который связывает координаты с центром масс Земли. Являясь геоцентрическим (глобальным), этот эллипсоид использует центр масс Земли в качестве начала отсчета. Наиболее широкое использование в настоящее время получил геоцентрический (глобальный) эллипсоид WGS84 (World Goodetic System 1984). Он служит основой для измерения местоположений во всем мире. Общеземной эллипсоид ориентируется в теле Земли согласно следующим условиям (определяемыми международными геодезическими организациями, которые организуются и направляются Международной ассоциацией геодезии, действующей по инициативе и в рамках Международного геодезического и геофизического союза):
Но требования к общеземным эллипсоидам на практике удовлетворяются с некоторыми допусками из-за отличных друг от друга методов и средств наблюдений и измерений. Поэтому в геодезии и смежных науках могут использоваться различные реализации эллипсоида, параметры которых очень близки, но не совпадают.
Система спутниковой навигации GPS сообщает координаты в системе эллипсоида WGS84 (World Goodetic System 1984). Эллипсоид IERS96 (International Earth Rotation Service 1996), предлагаемый в стандартах Международной службы вращения Земли, рекомендуется использовать при обработке РСДБ-наблюдений. Для геодезических работ рекомендуется использовать средний эллипсоид GRS80 (Geodetic Reference System 1980), принятый Генеральной Ассамблеей Международной ассоциацией геодезии в 1979 г.
|
Таблица 1. Некоторые общемировые (геоцентрические) эллипсоиды |
|
Название |
Год |
Страна/организация |
a, км (большая полуось) |
b, км (малая полуось) |
1/f (сжатие) |
|
GRS 80 |
1980 |
МАГГ (IUGG) |
6378,137 |
6356,75231414 |
298,257222101 |
|
WGS84 |
1984 |
США |
6378,137 |
6356,75231424518 |
298,257223563 |
|
ПЗ-90 |
1990 |
СССР |
6378,136 |
6356,751 |
298,257839303 |
|
IERS96 |
2003 |
МСВЗ (IERS) |
6378,13649 |
6356,751 |
298,25642 |
И, если глобальный эллипсоид наилучшим образом согласуется с поверхностью геоида в целом, то для того, чтобы описать поверхность Земли для данной конкретной территории, используют так называемые локальные эллипсоиды, которые наилучшим образом согласуются с геоидом на ограниченной части его поверхности (рис. 5).
Ориентирование локального эллипсоида в теле Земли подчиняется следующим требованиям:
Для точных работ необходимо учитывать положение конкретного эллипсоида по отношению к геоиду. Эта базовая информация, необходимая для преобразования координатных систем и картографических проекций, в основе которых лежат различные эллипсоиды. Существует несколько методов преобразований координатных систем. Самый простой (и наиболее грубый) осуществляется пересчетом географических координат (широты, долготы и высоты) из исходной координатной системы в требуемую путем перевода исходных географических координат в прямоугольные геоцентрические, вычислением величины сдвига центров координат и последующем переводом опять в географические координаты. Такой метод предполагает, что направления осей двух эллипсоидов параллельны, что во многих случаях не соответствует действительности. Для работ на небольшой территории погрешности, вносимые этим предположением, были меньше, чем точность самих данных. Однако, по мере накопления и уточнения данных и повышения точности измерений, стало очевидно, что преобразование по трем параметрам не подходит для больших территорий и глобального использования, если требуется максимальная точность и единый набор параметров преобразования. Молоденский разработал формулы для применения параметров сдвига географических координат (без перевода их в прямоугольные геоцентрические) по трем параметрам (сдвиг по трем осям) и разности между большими полуосями и сжатием исходного эллипсоида и целевого эллипсоида — еще два параметра. Повышенная точность достигается преобразованием Хелмерта с 7-ю параметрами — смещение центра одного эллипсоида относительно другого по трем координатам и поворотом его по трем углам с учетом масштабного коэффициента, показывающего изменение линейного масштаба. Есть две его разновидности, различающиеся присвоением знака для параметров поворота.
Метод наименьших квадратов (МНК, OLS, Ordinary Least Squares) — один из базовых методов регрессионного анализа для оценки неизвестных параметров регрессионных моделей по выборочным данным. Метод основан на минимизации суммы квадратов остатков регрессии.
Необходимо отметить, что собственно методом наименьших квадратов можно назвать метод решения задачи в любой области, если решение заключается или удовлетворяет некоторому критерию минимизации суммы квадратов некоторых функций от искомых переменных. Поэтому метод наименьших квадратов может применяться также для приближённого представления (аппроксимации) заданной функции другими (более простыми) функциями, при нахождении совокупности величин, удовлетворяющих уравнениям или ограничениям, количество которых превышает количество этих величин и т. д.
Пусть задана некоторая (параметрическая) модель вероятностной (регрессионной) зависимости между (объясняемой) переменной y и множеством факторов (объясняющих переменных) x
где — вектор неизвестных параметров модели
— случайная ошибка модели.
Пусть также имеются выборочные наблюдения значений указанных переменных. Пусть — номер наблюдения (). Тогда — значения переменных в -м наблюдении. Тогда при заданных значениях параметров b можно рассчитать теоретические (модельные) значения объясняемой переменной y:
Тогда можно рассчитать остатки регрессионной модели — разницу между наблюдаемыми значениями объясняемой переменной и теоретическими (модельными, оцененными):
Величина остатков зависит от значений параметров b.
Сущность МНК (обычного, классического) заключается в том, чтобы найти такие параметры b, при которых сумма квадратов остатков (англ. Residual Sum of Squares[1]) будет минимальной:
где:
В общем случае решение этой задачи может осуществляться численными методами оптимизации (минимизации). В этом случае говорят о нелинейном МНК (NLS или NLLS —англ. Non-Linear Least Squares). Во многих случаях можно получить аналитическое решение. Для решения задачи минимизации необходимо найти стационарные точки функции , продифференцировав её по неизвестным параметрам b, приравняв производные к нулю и решив полученную систему уравнений:
Если случайные ошибки модели имеют нормальное распределение, имеют одинаковую дисперсию и некоррелированы между собой, МНК-оценки параметров совпадают с оценкамиметода максимального правдоподобия (ММП).
Пусть регрессионная зависимость является линейной:
Пусть y — вектор-столбец наблюдений объясняемой переменной, а — матрица наблюдений факторов (строки матрицы — векторы значений факторов в данном наблюдении, по столбцам — вектор значений данного фактора во всех наблюдениях). Матричное представление линейной модели имеет вид:
Тогда вектор оценок объясняемой переменной и вектор остатков регрессии будут равны
соответственно сумма квадратов остатков регрессии будет равна
Дифференцируя эту функцию по вектору параметров и приравняв производные к нулю, получим систему уравнений (в матричной форме):
.
Решение этой системы уравнений и дает общую формулу МНК-оценок для линейной модели:
Для аналитических целей оказывается полезным последнее представление этой формулы. Если в регрессионной модели данные центрированы, то в этом представлении первая матрица имеет смысл выборочной ковариационной матрицы факторов, а вторая — вектор ковариаций факторов с зависимой переменной. Если кроме того данные ещё и нормированына СКО (то есть в конечном итоге стандартизированы), то первая матрица имеет смысл выборочной корреляционной матрицы факторов, второй вектор — вектора выборочных корреляций факторов с зависимой переменной.
Немаловажное свойство МНК-оценок для моделей с константой — линия построенной регрессии проходит через центр тяжести выборочных данных, то есть выполняется равенство:
В частности, в крайнем случае, когда единственным регрессором является константа, получаем, что МНК-оценка единственного параметра (собственно константы) равна среднему значению объясняемой переменной. То есть среднее арифметическое, известное своими хорошими свойствами из законов больших чисел, также является МНК-оценкой — удовлетворяет критерию минимума суммы квадратов отклонений от неё.
Пример: простейшая (парная) регрессия
В случае парной линейной регрессии формулы расчета упрощаются (можно обойтись без матричной алгебры):
Обычно контур состоит из нескольких сегментов, представляющих собой элементарные кривые Безье и соединенных в опорных точках (anchor points), или узлах. При перемещении одной опорной точки связанные с нею сегменты меняют свою форму. Изменить форму сегмента можно также перемещением управляющей точки (control point), связанной с опорной точкой посредством управляющей линии (control line).
9. ВЫДЕЛЕНИЕ ОПОРНЫХ ТОЧЕК
Невязка — это ошибка (погрешность) в результате вычислений. Пусть мы хотим найти такое x, что значение функции:
Подставляя приближенное значение x0 вместо x, получаем невязку
а ошибка в этом случае равна
Если мы не знаем точного значения x, мы не можем вычислить ошибку, но мы можем вычислить невязку.
Иерархические структуры данных в растровых ГИС. Индексирование пикселов. Квадродеревья (Quadtree-QT). Кодирование QT. Доступ к данным через QT. Варианты QT: дерево Oct-tree для 3D-объектов, модель Geoffrey-Dutton.
Вопрос эффективного способа представления изображений некоторой структурой данных остается актуальным в течении долгого времени. Ответ на данный вопрос всегда является неким компромиссом между объемом памяти, необходимым для представления изображения и временем доступа к элементам изображения.
Одной из наиболее изученных и хорошо зарекомендовавших себя структур данных для представления двумерных изображений является квадротомическое дерево или квадродерево (quadtree). Благодаря естественной иерархической структуре и способу организации квадродеревья сочетают в себе значительную экономию объемов памяти с эффективностью доступа к элементам изображения. Идеология квадродеревьев применяется не только для представления растровых изображений, но и используется для эффективной организации больших баз любых пространственных данных, состоящих как из растровых, так и векторных изображений. Аналогичные принципы лежат в основе структуры данных для представления трехмерных изображений и других трехмерных данных - октотомического дерева или октодерева (octtree).
Квадротомическое дерево (квадродерево) - структура данных, используемая для представления двумерных пространственных данных. Существует несколько типов квадродеревьев в зависимости от базового типа данных. (точки, площади, кривые, поверхности или объемы). Наиболее общим типом квадродерева и примером использования является квадродерево растрового изображения (см. рисунок 1, рисунок 3 и рисунок 4 - примеры изображения и его бинарного представления, блоков разбиения и квадродерева). Далее, для конкретности, под пространственными данными везде будем понимать растровое изображение.
Следуя Samet (1990), под двумерным изображением понимается массив элементов изображения (пикселов, pixel). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется бинарным. Если пикселы могут принимать более двух значений, то их значения могут трактоваться как оттенки серого, а изображение в этом случае называется изображением в градациях серого (grey-scale). Цветные изображения организованы аналогичным образом. Квадродеревья наиболее широко используются для работы с двухцветными изображениями, поэтому в дальнейшем будем иметь дело преимущественно с бинарными изображениями. Будем также в дальнейшем подразумевать, что фоновым в бинарном изображении является белый цвет.
При построении квадродерева двумерное изображение рекурсивно подразделяется на квадранты. Каждый из четырех квадрантов становится узлом квадротомического дерева. Больший квадрант становится узлом более высокого иерархического уровня квадродерева, а меньшие квадранты появляются на более низких уровнях. Преимущества такой структуры в том, что регулярное разделение обеспечивает простое и эффективное накопление, восстановление и обработку данных. Простота проистекает из геометрической регулярности разбиения, а эффективность - за счет хранения только узлов с данными, которые представляют интерес. Основополагающая идея квадродерева - комбинирование одинаковых или сходных элементов данных и кодирование больших однородных совокупностей данных малым количеством битов.
Корневой узел соответствует изображению в целом и имеет четыре дочерних узла, которые ассоциируются с четырьмя квадрантами исходного изображения (обозначаемыми NW - северо-западный, NE - северо-восточный, SW - юго-западный, SE - его-восточный). В свою очередь каждый из дочерних узлов корня дерева также имеет по четыре дочерних узла, ассоциированных с шестнадцать субквадрантами исходного изображения. Дочерние узлы следующего уровня представляют собой шестьдесят четыре квадранта, составляющих исходное изображение и так далее.
Рис. 1: (a) изображение (b) его бинарный образ (c) его квадротомическое разбиение
В сформированном выше описанном способом квадродереве листовым узлам дерева (узлам, соответствующим каждому одиночному пикселу изображения) приписывают цвет связанного с ними пиксела (черный или белый). Если нелистовой узел имеет среди дочерних узлов, узлы как одного так и другого цвета, ему приписывается серый цвет. Если же все дочерние узлы нелистового узла дерева "окрашены" в один и тот же цвет, то такому узлу приписывается этот цвет, а его дочерние узлы исключаются из дерева. Таким образом, в квадродереве могут отсутствовать некоторые ветки, представляющие собой достаточно большие одноцветные области.
Как показано Samet and Tamminen (1985), квадродеревья и их варианты оказываются полезными в различных приложениях таких, как обработка изображений, машинная графика, распознавание образов, роботостроении и картографии.
Рис. 2:Пример квадродерева
Рис. 3: (a) первый этап разбиения (b) второй этап разбиния
(c) третий этап разбиения (d) изображение полностью разбито
На каждом этапе построения квадродерева изображение разбивается на четыре квадранта и каждому присваивается одно из следующих значений
На нулевом этапе полному изображению (рисунок 1a) сопоставляется корневой узел дерева (рисунок 4). Далее четырем равновеликим квадрантам первого этапа разбиения (рисунок 3a) ставятся в соответствие дочерние узлы первого уровня. В показанном на рисунках частном случае северо-западный NW-квадрант обозначен белым квадратом, а остальные три - серыми кругами (рисунок 4). На очередно этапе серые квадранты снова подвергаются разбиению (на рисунке 3b для простоты показано лишь разбиение SW-квадранта). Как видно по рисунку 3b SW-квадрант на этом этапе содержит два белых, один черный и один серый подквадранты. Они представлены в дереве на рисунке 4. узлами второго уровня. Единственный серый квадрант снова разбивается. В данном случае это разбиение является последним, т.к. ни один из получившихся в результате подквадрантов не оказался серым (один белый и три черных). Подобным же образом обрабатываются и остальные квадранты изображения всех уровней. Окончательный вид квадродерева показан на рисунке 4.
Рис. 4: Окончательный вид квадродерева
Визуализация изображения, представленного квадродеревом, представляет собой простую рекурсивную процедуру.
Начиная с корня дерева просматривается каждый узел. Если узел не является листовым, то он пропускается и просматривается его первый дочерний узел. Если этот дочерний узел не листовой, то он пропускается и происходит переход к его первый дочерний узел и т.д. При достижении листового узла его цветовое значение отображается в соответствующей позиции. После этого происходит рекурсивный возврат к пропущенному родительскому узлу и аналогичным образом просматривается его второй дочерний узел.
Этот процесс продолжается до тех пор, пока не будут посещены все листья дерева.
Визуализация полного изображения происходит по мере продвижения по квадродереву.
Большинство приложений квадротомических деревьев к данным было сделано для изображений (Klinger, Dyer, 1976), но были проведены также современные алгоритмические разработки, которые дали результаты, сходные с теми, что используются при обработке географических данных. Сюда входят расчеты площадей, центороидные определения, распознавание образов (Shneier, 1981), классификация изображений, оверлейные операции над изображениями, выявление связанных компонент, определение соседства (Samet, 1981; Burroughs, 1986), преобразование расстояний (Samet, 1982), разделение изображений, сглаживание данных (Ranade, Shneier, 1981) и усиление краевых эффектов (Ranade, 1981). Вследствие этих преимуществ отдельные исследователи (Samet, 1984; Peuquet, 1984; Mark, Lauzon, 1985) предложили использовать квадротомические деревья для хранения географических данных. Основное достоинство квадродеревьев состоит в компактном представлении изображения. Компактность квадродерева целиком зависит от изображения. Изображение с большими областями, окрашенными в один цвет представляются очень компактно, в то время как изображение, в котором все пикселы имеют разные цвета сводит на нет все преимущества квадродерева. (Hunter and Stiglitz,1979)
Как и для любой другой "древесной" структуры данных, иерархическую структура квадродерева позволяет обеспечивать высокоэффективный доступ к элементам дерева.
Существует также множество алгоритмов обхода и манипулирования деревьями в их различных формах и все эти наработки могут быть распространены на квадродеревья.
Поворот квадродерева на 90 градусов против часовой стрелки может быть осуществлен простым переприсваиванием узлов дерева в следующем порядке:
Поворот по часовой стрелке выполняется аналогично за исключением того, что переприсваивание производится в обратном порядке.
Burroughs (1986) и Samet (1990) также упоминают о том, что квадродерево полезно при изменении разрешения объекта. Рассмотрим, например, квародерево на рисунке 4, которое представляет изображение, приведенное на рисунке 1.a. Если мы хотим изменить разрешение этого изображения, нам необходимо просто заменить все серые узлы второго уровня на черные узлы. Результатом будет новое изображение, показанное на рисунке 5.
Рис. 5: Изображение с измененным при помощи квадродерева разрешением
Наконец, еще одним немаловажным достоинством квадродеревьев является также наличие доступных исходных текстов программ и алгоритмов для реализации этой структуры данных (см.исходные тексты).
Главный недостаток квадродеревьев состоит в том, что почти невозможно сравнить два изображения, которые отличаются, например, лишь поворотом. Это обусловлено тем, что квадродеревья, представляющие такие изображения являются абсолютно различными.
Алгоритмы поворота квадротомированного изображения ограничиваются лишь поворотами на углы, кратные 90 градусам. Повороты на любые другие углы невозможны.
Хотя квадродеревья имеют массу плюсов в ГИС-приложениях, их распространение в других областях сдерживается их недостатками. Большинство проблем связано именно с тем, что при повороте изображения для него приходится заново перестраивать квадродерево. При этом сопоставление квадродеревьев исходного и повернутого изображений становится весьма сложной задачей. Вследствие этого применение квадродеревьев, например, в геометрическом анализе форм и распознавании образов остается достаточно узким.
Что нам нужно для реализации Octree? Для начала давайте разберем весь алгоритм построения. Мы задаем размеры игрового мира и массив объектов (под объектом понимается структура, которая содержит ограничивающий тело объем и ссылку на тело, где телом может быть как полигон, так и меш).
Далее вызываем функцию построения дерева. Она будет делить узел на восемь кубов, а потом рекурсивно все дочерние узлы данного еще на восемь до тех пор, пока не будет выполнено условие прекращения дробления (то есть пока все объекты не будут принадлежать каким-либо листьям, или пока по листьям не разойдутся все полигоны, или пока размеры листьев не станут равны необходимым нам и т.д.).
Теперь у нас имеется готовое дерево. В каждом кадре мы, с помощью пирамиды видимости, определяем те листья, которые нам видны, получаем ссылки на объекты хранящиеся в них и, собственно, рисуем меши. Вот и все.
Следует помнить, что выигрыш в быстродействии при использовании Octree зависит от трех основных параметров: 1)размера мира; 2)общего количества объектов и 3)количества объектов на один лист.
Если первые два параметра целиком зависят от игрового уровня, то третий необходимо подбирать самостоятельно, экспериментально, при этом следует помнить, что если максимальное допустимое значение объектов на лист равно единице (или близко к ней), то мы, фактически, проверяем попадает ли каждый объект в пирамиду видимости - это очень долго (хотя при достаточном количестве объектов также дает выигрыш); но именно этот подход лучше выбрать, если меши многополигональные или отрисовываются с «тяжелыми» шейдерами.
Если максимальное количество объектов на лист будет слишком большим (при этом узел будет большим по объему), то мы, даже в случае частичного попадания листа в пирамиду видимости, будем рисовать все объекты, которые за данным листом закреплены. Этот подход больше подходит для малополигональных объектов.
Обратите внимание: в конце статьи расположена небольшая таблица со сравнительными результатами производительности при различных параметрах, вы можете опираться на нее при выборе параметров для своего приложения.
Теперь рассмотрим простейшую реализацию восьмеричного дерева.
Для начала мы создадим класс для дерева (COCTREE). В нем должны быть: бокс данного узла (объем, ограничивающий узел), массив из восьми дочерних узлов (то есть в классе восемь указателей на объекты этого же самого класса), массив для хранения объектов, принадлежащих узлу (мы будем использовать vector, так как он очень удобен и находится в стандартной поставке, то есть общедоступен). Теперь функции: конструктор и деструктор, функция, расставляющая боксы дочерних узлов по своим местам (нижний левый ближний, нижний левый дальний, нижний правый ближний и т.д.), функция освобождения ресурсов, функция построения самих узлов и кое-что еще.