Полиномиальные преобразования - История изменений

Bolotoved: /* Матрица преобразования */

2012-08-25T01:17:03Z

Матрица преобразования

← Предыдущая версия		Версия от 03:17, 25 августа 2012
Строка 54:		Строка 54:
	[[Image:polynom-04.gif\|123px\|полиномиальные преобразования n-го порядка\|center]]		[[Image:polynom-04.gif\|123px\|полиномиальные преобразования n-го порядка\|center]]

	Очевидно, что размерность матрицы преобразований увеличивается с ростом порядка преобразования, соответственно [polynom.html#minnumber минимальное количество контрольных точек ]необходимых для вычислений коэффициентов матрицы тоже растет.		Очевидно, что размерность матрицы преобразований увеличивается с ростом порядка преобразования, соответственно [http://gis-lab.info/qa/polynom.html#minnumber минимальное количество контрольных точек]необходимых для вычислений коэффициентов матрицы тоже растет.

	Каждая контрольная точка влияет на [http://gis-lab.info/qa/polynom-calc.html расчетные коэффициенты], если нет идеального соответствия каждой контрольной точки полиному, который представлен этими коэффициентами. Расстояние между кривой и расчетной координаты точки – называется ошибкой RMS (среднеквадратической ошибкой точки). Для расчета матрицы преобразований по набору контрольных точек используется метод среднеквадратической регрессии (метод наименьших квадратов) на основе контрольных точек расставляемых пользователем от исходного (привязываемого) материала, к конечному материалу (тому, к которому привязывают).		Каждая контрольная точка влияет на [http://gis-lab.info/qa/polynom-calc.html расчетные коэффициенты], если нет идеального соответствия каждой контрольной точки полиному, который представлен этими коэффициентами. Расстояние между кривой и расчетной координаты точки – называется ошибкой RMS (среднеквадратической ошибкой точки). Для расчета матрицы преобразований по набору контрольных точек используется метод среднеквадратической регрессии (метод наименьших квадратов) на основе контрольных точек расставляемых пользователем от исходного (привязываемого) материала, к конечному материалу (тому, к которому привязывают).

Bolotoved: /* Влияние порядка преобразования */

2012-08-25T01:14:50Z

Влияние порядка преобразования

← Предыдущая версия		Версия от 03:14, 25 августа 2012
Строка 148:		Строка 148:
	Полиномы 2-го порядка и выше – нелинейные.		Полиномы 2-го порядка и выше – нелинейные.

	[[Image:polynom-14.gif\|302px\|полиномиальные преобразования]]		[[Image:polynom-14.gif\|302px\|полиномиальные преобразования\|center]]

	Что если добавить еще одну контрольную точку?		Что если добавить еще одну контрольную точку?

Bolotoved: /* Линейные преобразования */

2012-08-25T01:13:57Z

Линейные преобразования

← Предыдущая версия		Версия от 03:13, 25 августа 2012
Строка 22:		Строка 22:
	На рисунке показано, как изменяются данные при линейных преобразованиях.		На рисунке показано, как изменяются данные при линейных преобразованиях.

	[[Image:polynom-01.gif\|450px\|полиномиальные преобразования 1-го порядка]]		[[Image:polynom-01.gif\|450px\|полиномиальные преобразования 1-го порядка\|center]]

	Для осуществления полиномиального преобразования первой степени необходимо найти 6 коэффициентов - по три на каждую координату (X и Y): a<sub>0</sub>, a<sub>1</sub>, a<sub>2</sub>, b<sub>0</sub>, b<sub>1</sub>, b<sub>2</sub>. Эти коэффициенты, далее используются в собственно уравнениях полиномиального преобразования первой степени (эквивалентного также аффинному преобразованию):		Для осуществления полиномиального преобразования первой степени необходимо найти 6 коэффициентов - по три на каждую координату (X и Y): a<sub>0</sub>, a<sub>1</sub>, a<sub>2</sub>, b<sub>0</sub>, b<sub>1</sub>, b<sub>2</sub>. Эти коэффициенты, далее используются в собственно уравнениях полиномиального преобразования первой степени (эквивалентного также аффинному преобразованию):

Bolotoved в 01:13, 25 августа 2012

2012-08-25T01:13:31Z

← Предыдущая версия		Версия от 03:13, 25 августа 2012
Строка 36:		Строка 36:
	Нелинейные преобразования – это преобразования 2-го и более порядка. Эти преобразования могут корректировать нелинейные искажения. На рисунке изображены примеры результатов некоторых нелинейных преобразований.		Нелинейные преобразования – это преобразования 2-го и более порядка. Эти преобразования могут корректировать нелинейные искажения. На рисунке изображены примеры результатов некоторых нелинейных преобразований.

	=[[Image:polynom-02.gif\|630px\|полиномиальные преобразования n-го порядка\|center]]=		[[Image:polynom-02.gif\|630px\|полиномиальные преобразования n-го порядка\|center]]

	Преобразования 2-го порядка могут быть использованы для преобразования данных в географической системе координат (широта, долгота) в прямоугольную, для преобразования данных больших областей (для учета кривизны Земли), для точно привязки искаженных по той или иной причине данных (например, из-за искажений линз камеры, плохо отсканированных материалов) и т.д.		Преобразования 2-го порядка могут быть использованы для преобразования данных в географической системе координат (широта, долгота) в прямоугольную, для преобразования данных больших областей (для учета кривизны Земли), для точно привязки искаженных по той или иной причине данных (например, из-за искажений линз камеры, плохо отсканированных материалов) и т.д.
Строка 56:		Строка 56:
	Очевидно, что размерность матрицы преобразований увеличивается с ростом порядка преобразования, соответственно [polynom.html#minnumber минимальное количество контрольных точек ]необходимых для вычислений коэффициентов матрицы тоже растет.		Очевидно, что размерность матрицы преобразований увеличивается с ростом порядка преобразования, соответственно [polynom.html#minnumber минимальное количество контрольных точек ]необходимых для вычислений коэффициентов матрицы тоже растет.

	Каждая контрольная точка влияет на [polynom-calc.html расчетные коэффициенты], если нет идеального соответствия каждой контрольной точки полиному, который представлен этими коэффициентами. Расстояние между кривой и расчетной координаты точки – называется ошибкой RMS (среднеквадратической ошибкой точки). Для расчета матрицы преобразований по набору контрольных точек используется метод среднеквадратической регрессии (метод наименьших квадратов) на основе контрольных точек расставляемых пользователем от исходного (привязываемого) материала, к конечному материалу (тому, к которому привязывают).		Каждая контрольная точка влияет на [http://gis-lab.info/qa/polynom-calc.html расчетные коэффициенты], если нет идеального соответствия каждой контрольной точки полиному, который представлен этими коэффициентами. Расстояние между кривой и расчетной координаты точки – называется ошибкой RMS (среднеквадратической ошибкой точки). Для расчета матрицы преобразований по набору контрольных точек используется метод среднеквадратической регрессии (метод наименьших квадратов) на основе контрольных точек расставляемых пользователем от исходного (привязываемого) материала, к конечному материалу (тому, к которому привязывают).

	==Формула вычисления полинома порядка t==		==Формула вычисления полинома порядка t==

Bolotoved: Новая страница: «{{Статья|Опубликована|polynom}} {{Аннотация|Формулы и примеры расчетов полиномиальных преобр…»

2012-08-25T01:11:02Z

Новая страница: «{{Статья|Опубликована|polynom}} {{Аннотация|Формулы и примеры расчетов полиномиальных преобр…»

Новая страница

{{Статья|Опубликована|polynom}}
{{Аннотация|Формулы и примеры расчетов полиномиальных преобразований}}

Формулы полиноминальных преобразований используются для перевода исходных координат (обычно локальных-прямоугольных) в конечные (обычно спроектированные - прямоугольные). В зависимости от искажения изображения, количества контрольных точек (GCP – ground control point), и их размещения относительно друг друга, для выражения необходимого преобразования могут потребоваться достаточно сложные полиноминальные формулы. Сложность полинома выражается через его порядок. Порядок – это показатель наивысшей степени, используемой в полиноме.

==Линейные преобразования==

Преобразование 1-го порядка – линейное преобразование. Это преобразование может изменять:

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

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

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

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

На рисунке показано, как изменяются данные при линейных преобразованиях.

[[Image:polynom-01.gif|450px|полиномиальные преобразования 1-го порядка]]

Для осуществления полиномиального преобразования первой степени необходимо найти 6 коэффициентов - по три на каждую координату (X и Y): a0, a1, a2, b0, b1, b2. Эти коэффициенты, далее используются в собственно уравнениях полиномиального преобразования первой степени (эквивалентного также аффинному преобразованию):

<center>x0 = a0 + a1x + a2y</center>

<center>y0 = b0 + b1x + b2y</center>

<center>где x,y - исходные координаты, x0,y0 - конечные координаты</center>

==Нелинейные преобразования==

Нелинейные преобразования – это преобразования 2-го и более порядка. Эти преобразования могут корректировать нелинейные искажения. На рисунке изображены примеры результатов некоторых нелинейных преобразований.

=[[Image:polynom-02.gif|630px|полиномиальные преобразования n-го порядка|center]]=

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

==Матрица преобразования==

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

[[Image:polynom-05.gif|275px|полиномиальные преобразования n-го порядка|center]]

Количество коэффициентов матрицы преобразований для преобразования порядка t равно:

[[Image:polynom-03.gif|64px|полиномиальные преобразования n-го порядка|center]]

Это число необходимо умножить на 2 – для двух наборов коэффициентов, один - для X, другой для Y. Более простая формула для получения количества коэффициентов:

[[Image:polynom-04.gif|123px|полиномиальные преобразования n-го порядка|center]]

Очевидно, что размерность матрицы преобразований увеличивается с ростом порядка преобразования, соответственно [polynom.html#minnumber минимальное количество контрольных точек ]необходимых для вычислений коэффициентов матрицы тоже растет.

Каждая контрольная точка влияет на [polynom-calc.html расчетные коэффициенты], если нет идеального соответствия каждой контрольной точки полиному, который представлен этими коэффициентами. Расстояние между кривой и расчетной координаты точки – называется ошибкой RMS (среднеквадратической ошибкой точки). Для расчета матрицы преобразований по набору контрольных точек используется метод среднеквадратической регрессии (метод наименьших квадратов) на основе контрольных точек расставляемых пользователем от исходного (привязываемого) материала, к конечному материалу (тому, к которому привязывают).

==Формула вычисления полинома порядка t==

[[Image:polynom-06.gif|247px|полиномиальные преобразования n-го порядка|center]]

Где: t – порядок полинома, ak и bk – коэффициенты, индекс k для ak и bk вычисляется как:

[[Image:polynom-07.gif|138px|полиномиальные преобразования n-го порядка|center]]

Например, для преобразования 3-го порядка будет использоваться 20 коэффициентов:

[[Image:polynom-08.gif|204px|полиномиальные преобразования n-го порядка|center]]

Формула для преобразования 3-го порядка, после вычисления коэффициентов, может выглядеть так:

[[Image:polynom-09.gif|423px|полиномиальные преобразования n-го порядка|center]]

==Влияние порядка преобразования==

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

В следующем примере, для просты, используется только одна координата (X), вместо двух (X, Y), которые для расчетов в полиномиальных преобразованиях. Это позволяет использовать двухмерные графики, иллюстрирующие, как использование преобразования определенного порядка позволяет связать исходные и конечные координаты. Из-за того, что в примере используется только координата X, число используемых контрольных точек меньше реально требуемого для преобразований соответствующих порядков.

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

{| class="wikitable" align="center"
!
<center>Исходная координата X</center>
!
<center>Конечная координата X</center>
|-
|
<center>1</center>
|
<center>17</center>
|-
|
<center>2</center>
|
<center>9</center>
|-
|
<center>3</center>
|
<center>1</center>
|}

Эти точки позволяют выполнить преобразование 1-го порядка для координат X, которые удовлетворяют следующему уравнению (коэффициенты указаны в скобках):

[[Image:polynom-10.gif|120px|полиномиальные преобразования|center]]

Где: xr = конечная координата X, xi = исходная координата X

В данном случае, уравнение принимает такую же форму, как и уравнение линии (y = b + mx), отсюда и линейность преобразования.

[[Image:polynom-11.gif|310px|полиномиальные преобразования|center]]

Однако, что произойдет, если вторую контрольную точку изменить следующим образом?

{| class="wikitable" align="center"
!
<center>Исходная координата X</center>
!
<center>Конечная координата X</center>
|-
|
<center>1</center>
|
<center>17</center>
|-
|
<center>2</center>
|
<center>7</center>
|-
|
<center>3</center>
|
<center>1</center>
|}

Эти точки нельзя соединить одной прямой линией, что означает, что они не могут быть описаны посредством полинома 1-го порядка, так как было описано выше.

[[Image:polynom-12.gif|302px|полиномиальные преобразования|center]]

В данном случае, эти точки выражаются через полином 2-го порядка:

[[Image:polynom-13.gif|171px|полиномиальные преобразования|center]]

Полиномы 2-го порядка и выше – нелинейные.

[[Image:polynom-14.gif|302px|полиномиальные преобразования]]

Что если добавить еще одну контрольную точку?

{| class="wikitable" align="center"
!
<center>Исходная координата X</center>
!
<center>Конечная координата X</center>
|-
|
<center>1</center>
|
<center>17</center>
|-
|
<center>2</center>
|
<center>7</center>
|-
|
<center>3</center>
|
<center>1</center>
|-
|
<center>4</center>
|
<center>5</center>
|}

[[Image:polynom-15.gif|304px|полиномиальные преобразования|center]]

Как видно на рисунке, четвертая точка не лежит на кривой, выраженной уравнением полинома 2-го порядка. Для того, чтобы все точки лежали на кривой, порядок преобразования должен быть увеличен до 3-х. Результирующее уравнение и кривая изображены на рисунке.

[[Image:polynom-16.gif|306px|полиномиальные преобразования|center]]

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

{| class="wikitable" align="center"
!
<center>Исходная координата X</center>
!
<center>Конечная координата X</center>
|-
|
<center>1</center>
|
<center>x(1) = 17</center>
|-
|
<center>2</center>
|
<center>x(2) = 7</center>
|-
|
<center>3</center>
|
<center>x(3) = 1</center>
|-
|
<center>4</center>
|
<center>x(4) = 5</center>
|}

<center>x(1) > x(2) > x(4) > x(3)</center>

[[Image:polynom-17.gif|617px|полиномиальные преобразования|center]]

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

==Минимальное количество контрольных точек==

Преобразования высших порядков могут быть использованы для корректировки очень сложных типов искажений. Однако для использования преобразований высших порядков требуется большее количество контрольных точек. Например, плоскость определяется 3-мя точками. Т.о. для применения преобразования 1-го порядка, которое выражается через уравнение плоскости, требуется как минимум 3 точки. Таким же образом, преобразование 2-го порядка выражается уравнением параболоида. Для определения уравнения параболоида требуется 6 точек. Поэтому, как минимум 6 контрольных точек требуется для осуществления преобразования 2-го порядка. Минимально требуемое количество точек для преобразования t-го порядка вычисляется следующим образом:

[[Image:polynom-18.gif|94px|полиномиальные преобразования|center]]

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

В следующей таблице перечислено минимальное количество контрольных точек необходимое для преобразований порядков с 1-го по 10-й.

{| class="wikitable" align="center"
!
<center>Порядок преобразования</center>
!
<center>Минимальное количество контрольных точек</center>
|-
|
<center>1</center>
|
<center>3</center>
|-
|
<center>2</center>
|
<center>6</center>
|-
|
<center>3</center>
|
<center>10</center>
|-
|
<center>4</center>
|
<center>15</center>
|-
|
<center>5</center>
|
<center>21</center>
|-
|
<center>6</center>
|
<center>28</center>
|-
|
<center>7</center>
|
<center>36</center>
|-
|
<center>8</center>
|
<center>45</center>
|-
|
<center>9</center>
|
<center>55</center>
|-
|
<center>10</center>
|
<center>66</center>
|}

''В статье использованы материалы ERDAS IMAGINE Field Guide''

==Ссылки по теме==
*[http://gis-lab.info/qa/rmse.html Среднеквадратичная ошибка (RMSE)]
*[http://gis-lab.info/qa/polynom-calc.html Полиномиальные преобразования - вычисления и практика]