интерполяция
Nickita A Startcev
Есть некий четырехугольник, весьма близкий к квадрату.
(точнее, это одна из ячеек сетки)
В каждой точке измерено значение некоторой величины, например, температуры.
Если обходить этот четырехугольник по часовой стрелке, то значения в вершинах
будут, например, 1.00, 2.00, 1.00, 2.00.
Как правильно интерполировать температуру в пределах этого четырехугольника?
Разбиение на два треугольника получается какое-то очень неоднозначное, (одна
диагональ идет по уровню 2.00, другая по 1.00) как лучше поступать в таких
кривых случаях?
. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Минеральный секретарь
Alex Mizrahi
NAS> (точнее, это одна из ячеек сетки)
NAS> В каждой точке измерено значение некоторой величины, например,
NAS> температуры.
в таких случаях нужно либо выбрать сетку помельче, чтобы не нужно было
интерполировать между, либо исходить из природы величины. для заряда
это будет одно, для температуры -- другое..
конкретно для температуры это называется задачей теплопроводности, в общем
виде решается через дифференциальные уравнения.
NAS> Если обходить этот четырехугольник по часовой стрелке, то значения в
NAS> вершинах будут, например, 1.00, 2.00, 1.00, 2.00.
NAS> Как правильно интерполировать температуру в пределах этого
NAS> четырехугольника? Разбиение на два треугольника получается какое-то
NAS> очень неоднозначное, (одна диагональ идет по уровню 2.00, другая по
NAS> 1.00) как лучше поступать в таких кривых случаях?
кривым в данном случае является метод разбиения на треугольники.
если у тебя сетка квадратная, считать нужно по квадратам.
интерполировать можно по разному.
самый простой метод -- покоординатный.
к примеру, x и y -- относительные координаты изменяющиеся от 0 до 1 в
пределах
прямоугольника.
введём вспомогательную функцию интерполяции на отрезке:
blend(a, b, x) = a * (1-x) + b * x
для x = 0 оно даёт a, а для x = 1 -- b.
тогда значение в точке [x, y] можно получить применяя последовательно
интерполяцию по горизонтали и вертикали:
v(x,y) = blend( blend(v(0,0), v(1,0), x),
blend(v(0,1), v(1,1), x),
y)
т.е. интерполяция по вертикали применяется к результатам интерполяции по
горизонтали.
если расписать полностью, получится:
v(x,y) = v(0,0)*(1-x)*(1-y) + v(1,0)*x*(1-y) +
+ v(0,1)*(1-x)*y + v(1,0)*x*y
т.к. (1-x)*(1-y) + x*(1-y) + (1-x)*y + x*y = 1, это ни что иное как
взвешенное среднее.
в принципе, коэффициенты здесь можно взять любые. например, можно взять как
вес величину
обратную расстоянию от точки до вершины:
v(x,y) = (v(0, 0)/r((x, y), (0, 0)) + .... v(1, 1)/r((x, y), (1, 1))
-----------------------------------------------------------
1/ (r(x,y), (0, 0)) + ... + 1/(r(x,y), (1,1))
ещё лучше взять квадрат расстояния, как известно, многие физические величины
работают подобным образом.
визуально можно сравнить на картинках:
http://distances.infogami.com/
как видишь, с квадратами расстояний выглядит более "естественно", похоже на
какие-то источники света.
Nickita A Startcev
20 Apr 09 , 02:27 Alex Mizrahi писал к Nickita A Startcev:
NAS>> Есть некий четырехугольник, весьма близкий к квадрату.
NAS>> (точнее, это одна из ячеек сетки)
NAS>> В каждой точке измерено значение некоторой величины, например,
NAS>> температуры.
AM> в таких случаях нужно либо выбрать сетку помельче, чтобы не нужно было
AM> интерполировать между, либо исходить из природы величины. для заряда
AM> это будет одно, для температуры -- другое..
AM> конкретно для температуры это называется задачей теплопроводности, в
AM> общем виде решается через дифференциальные уравнения.
Температура - это я от лени написал.
Hа самом деле задача чуть другая:
Есть некая картинка. Эта картинка сфотографирована с некоторыми геометрическими
искажениями. Для некоторых точек исходной картинки очень точно известны
координаты и известно каким точкам конечной картинки они соответствуют. Очень
точно - с субпиксельной точностью. По этим данным нужно один раз построить
обратную таблицу: для каждой точки конечной картинки определить, каким
координатам исходной они соответствуют.
В исходной картинке "опорные" точки идут с шагом примерно 11
пикселей,координаты этих точек измеряются с точностью порядка 1/1000 пикселя.
Идея решения: идем по всем пикселям конечной картинки, для каждого пикселя
проверяем, в какой квадрат из опорных точек он попадает, внутри этого квадрата
интерполируем координаты. По краям придется не интерполировать, а
экстраполировать, но это отдельная история.
NAS>> (одна диагональ идет по уровню
NAS>> 2.00, другая по 1.00) как лучше поступать в таких кривых
NAS>> случаях?
AM> кривым в данном случае является метод разбиения на треугольники.
AM> если у тебя сетка квадратная, считать нужно по квадратам.
Почти квадратная. И как раз эти неквадратности и отлавливаю.
AM> blend(a, b, x) = a * (1-x) + b * x
AM> v(x,y) = blend( blend(v(0,0), v(1,0), x),
AM> blend(v(0,1), v(1,1), x),
AM> y)
[..]
AM> ещё лучше взять квадрат расстояния, как известно, многие физические
AM> величины работают подобным образом.
А ошибки измерения - это физические величины? :) Они будут вести себя именно
так?
AM> визуально можно сравнить на картинках:
AM> http://distances.infogami.com/
Лучше бы они 3д-поверхность нарисовали..
AM> как видишь, с квадратами расстояний выглядит более "естественно",
AM> похоже на какие-то источники света.
Угу.
. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... человек должен работать, а компьютер думать?!
Alex Mizrahi
NAS> пикселей,координаты этих точек измеряются с точностью порядка 1/1000
NAS> пикселя.
NAS> Идея решения: идем по всем пикселям конечной картинки, для каждого
NAS> пикселя проверяем, в какой квадрат из опорных точек он попадает,
NAS> внутри этого квадрата интерполируем координаты. По краям придется не
NAS> интерполировать, а экстраполировать, но это отдельная история.
вот так бы сразу и сказал.. опорные точки задают систему координат, тебе
нужно афинным преобразованием перевести точки из одной системы в другую.
проблема состоит в том что каждая тройка точек задаёт свою систему
координат.
т.о. наверное нужно посчитать во всех возможных и потом как-то совместить.
то есть каждый угол "квадрата" -- это своя система координат. для каждой
строишь матрицу трансформации и ей переводишь точку в исходную систему
координат.
получаешь четыре набора координат. из них нужно сделать одни координаты,
чем-то
вроде взвешенного среднего.
как именно я пока не соображу, но это делается однозначным способом.
можно прикинуть на какой-то вырожденной ситуации. например, единичый
квадрат пребразовлся в такую трапецию:
/|
|_|
можно найти координаты центра в старой и новой системе и прикинуть
как их нужно обработать чтобы сходилось.
AM>> ещё лучше взять квадрат расстояния, как известно, многие физические
AM>> величины работают подобным образом.
NAS> А ошибки измерения - это физические величины? :) Они будут вести себя
NAS> именно так?
неа.. я подозреваю тут как раз может быть нужен линейный вариант (с blend),
но обосновать пока не могу :)
можно либо попробовать прикинуть на тестовых примерах, либо попытаться
найти что-то готовое -- наверняка подобная задача встаёт при составлении
карт и т.д. и её решили в незапамятные времена. только вот название знать
надо :)
Nickita A Startcev
20 Apr 09 , 15:20 Alex Mizrahi писал к Nickita A Startcev:
NAS>> В исходной картинке "опорные" точки идут с шагом примерно 11
NAS>> пикселей,координаты этих точек измеряются с точностью порядка
NAS>> 1/1000 пикселя.
NAS>> Идея решения: идем по всем пикселям конечной картинки, для
NAS>> каждого пикселя проверяем, в какой квадрат из опорных точек он
NAS>> попадает, внутри этого квадрата интерполируем координаты. По
NAS>> краям придется не интерполировать, а экстраполировать, но это
NAS>> отдельная история.
AM> вот так бы сразу и сказал..
Хорошая мысля приходит опосля. :\
AM> опорные точки задают систему координат,
AM> тебе нужно афинным преобразованием перевести точки из одной системы в
AM> другую. проблема состоит в том что каждая тройка точек задаёт свою
AM> систему координат.
Ага. В разных местах кадра нужно чуть разное преобразование.
AM> т.о. наверное нужно посчитать во всех возможных и
AM> потом как-то совместить.
Или, в каждой треугольной четверти квадрата иметь своё преобразование
(центр квадрата считаем (в обеих системах координат) как среднее арифметическое
всех четырех углов), потом смотреть график поправок и как-то его чуток
сглаживать.
[..]
AM> например, единичый
AM> квадрат пребразовлся в такую трапецию:
AM> /|
AM> |_|
AM> можно найти координаты центра в старой и новой системе и прикинуть
AM> как их нужно обработать чтобы сходилось.
Да просто тупо сказать, что они совпадают, а потом интерполировать по
треугольникам ABE, BCE, CDE, DAE. (ABCD - наш квадрат, E - точка в центре)
NAS>> А ошибки измерения - это физические величины? :) Они будут вести
NAS>> себя именно так?
AM> неа.. я подозреваю тут как раз может быть нужен линейный вариант (с
AM> blend), но обосновать пока не могу :)
Во. Мне тоже кажется, что начинать надо или с линейного, или вообще с
какого-нибудь сплайна кубического, но проходящегострого через 'опорные' точки.
AM> можно либо попробовать прикинуть на тестовых примерах,
Если интересно, пример лежит на http://www.startcev.spb.ru/xy.txt
Текстовый файл, в нём две таблицы.
Таблицы - числа с плавучкой, разделенные табуляцией.
в одной таблице измеренные абсциссы для всех квадратов, во второй - ординаты.
таблица - примерно 25х20 точек.
AM> либо попытаться
AM> найти что-то готовое -- наверняка подобная задача встаёт при
AM> составлении карт и т.д. и её решили в незапамятные времена. только вот
AM> название знать надо :)
Дык. Hазвание. А где ж его искать? :)
. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... юркие е-стеренки и i-стероиды
Alex Mizrahi
AM>> потом как-то совместить.
NAS> Или, в каждой треугольной четверти квадрата иметь своё преобразование
NAS> (центр квадрата считаем (в обеих системах координат) как среднее
NAS> арифметическое всех четырех углов), потом смотреть график поправок и
NAS> как-то его чуток сглаживать.
мне кажется если есть чёткое аналитическое решение вводить отсебятину
типа "графика поправок" и "чуток сглаживания" идеологически неверно.
NAS> Во. Мне тоже кажется, что начинать надо или с линейного, или вообще с
NAS> какого-нибудь сплайна кубического, но проходящегострого через
NAS> 'опорные' точки.
ход мыслей просто потрясает.. или начать с простого и аналитически
обоснованного решения, или накидать каких-то сплайнов, которые непонятно
что возвращают.. где логика?
у тебя стоит задача не интерполяции, а перевода координат из одной
системы в другую. если при интерполяции цвета или температуры сплайны дадут
приятные округлости, при интерполяции координат они внесут совершенно
непонятые искажения. оно тебе надо?
Nickita A Startcev
23 Apr 09 , 17:49 Alex Mizrahi писал к Nickita A Startcev:
AM>>> т.о. наверное нужно посчитать во всех возможных и
AM>>> потом как-то совместить.
NAS>> Или, в каждой треугольной четверти квадрата иметь своё
NAS>> преобразование (центр квадрата считаем (в обеих системах
NAS>> координат) как среднее арифметическое всех четырех углов), потом
NAS>> смотреть график поправок и как-то его чуток сглаживать.
AM> мне кажется если есть чёткое аналитическое решение вводить отсебятину
AM> типа "графика поправок" и "чуток сглаживания" идеологически неверно.
чёткое аналитическое - это билинейка по квадратикам?
Так сами эталонные квадратики не очень одинаковы, напечатаны с чуть разной
ориентацией и не совсем равномерными сдвигами. Возможно, я еще где-то
накосячил, но некоторые билинейки сходятся не очень хорошо:
на графиках dx(x,y) и dy(x,y) видны всплески примерно на границах.
Это немножко смущает.
NAS>> Во. Мне тоже кажется, что начинать надо или с линейного, или
NAS>> вообще с какого-нибудь сплайна кубического, но проходящегострого
NAS>> через 'опорные' точки.
AM> ход мыслей просто потрясает.. или начать с простого и аналитически
AM> обоснованного решения, или накидать каких-то сплайнов, которые
AM> непонятно что возвращают.. где логика?
логика бывает разная.
а) натянуть и подчистить
б) как-то натянуть, найти аналитическое, подогнать коэффиценты, синтезировать
синтетическое.
AM> у тебя стоит задача не интерполяции, а перевода координат из одной
AM> системы в другую.
Из пачки систем, по сути. И эти системы не идеально состыкуются между собой.
AM> если при интерполяции цвета или температуры сплайны
AM> дадут приятные округлости, при интерполяции координат они внесут
AM> совершенно непонятые искажения. оно тебе надо?
Любой сплайн при интерполяции погрешности (высоты) даст совершенно непонятные
искажения, или есть такие сплайны, которые пройдут строго по точкам и будут
иметь гладкую производную?
. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... пирИт, латерИт и бодрИт