Бикубическая и билинейная интерполяция

[Sashok]

Даже не знаю, куда поместить этот вопрос, прошу прощения.
Может ли кто-нибудь детально описать, или дать ссылку на детальное описание бикубической и билинейной интерполяции?
Задача стоит следующим образом: есть прямоугольная сетка со значениями в узлах. Надо сделать интерполяцию на более частую сетку. Это не классическая интерполяция, когда известна функция и ее первые производные, а именно табличные данные. На инете мне попадалось также название "ресемплирование".
Я знаю, что эти методы используются в графических преобразованиях, хотя мне нужно не для графики.

[Sla]

http://www.srcc.msu.su/num_anal/lib_na/cat/i/ip04r.htm
хм

[Sashok]

Ссылка, безусловно, полезная (я на нее уже натыкался), но там как раз классическая интерполяция, т.е. нужна функция, имеющая частные первые производные и смешанную производную. В моем же случае есть только данные, функции нет. Можно предполагать, что она непрерывна и дифференцируема, но есть только таблица данных. Возникает вопрос, как применить интерполяцию к таблице.

[Вад]

Очень просто - дискретно применять В случае билинейного - усреднять значения цвета в ближайших узлах с поправкой на коэффициент удалённости. В случае бикубического - использовать чуть более хитрые коэффициенты для цветов в ближайших точках.
Про билинейную в Википедии вроде достаточно написано - там как раз пример для расчёта точки по 4м ближайшим.

[Sashok]

Да, спасибо, насчет билинейной вроде бы все ясно. Как-то я ухитрился эту статью пропустить
А как насчет бикубической? Порыскал по ссылкам в указанной статье в Википедии, но про бикубическую не нашел.

[Вад]

http://en.wikipedia.org/wiki/Bicubic_interpolation - и оттуда ещё можно походить по external links в конце статьи.
Также можно через codesearch.google.com поискать реализации У меня где-то валяется одна, но там, кажется, коэффициенты хитро захардкожены и на макросах, выдирать будет непросто, да и разобраться тоже

[PooH]

Посмотри еще http://ru.wikipedia.org/wiki/Поверхность_Безье

[Sashok]

http://en.wikipedia.org/wiki/Bicubic_interpolation - и оттуда ещё можно походить по external links в конце статьи.
Также можно через codesearch.google.com поискать реализации У меня где-то валяется одна, но там, кажется, коэффициенты хитро захардкожены и на макросах, выдирать будет непросто, да и разобраться тоже

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

[Mayor]

а у меня вот вопрос возник, можно эту билинейную или бикубическую интерполяцию использовать для построения карты высот?

когда на входе дан битмеп, где 1 обозначают уровни стремящиеся к нижней грани 1,2,3,4 и тп метров, а 0 просто более удаленные от 1 пикслелов участки

на выходе нужно получить серое или цветное изображение, где каждый бит заменен на цвет, которым обозначают высоту

[Sashok]

а у меня вот вопрос возник, можно эту билинейную или бикубическую интерполяцию использовать для построения карты высот?

когда на входе дан битмеп, где 1 обозначают уровни стремящиеся к нижней грани 1,2,3,4 и тп метров, а 0 просто более удаленные от 1 пикслелов участки

на выходе нужно получить серое или цветное изображение, где каждый бит заменен на цвет, которым обозначают высоту

Честно говоря, не понял твою постановку задачи.
В любом случае, интерполяция нужна, если ты хочешь получить на выходе БОЛЬШЕ точек, чем было на входе. А по твоему описанию получается, что ты просто хочешь менять вид отображения. Или я не так понял?

[Mayor]

Честно говоря, не понял твою постановку задачи.
В любом случае, интерполяция нужна, если ты хочешь получить на выходе БОЛЬШЕ точек, чем было на входе. А по твоему описанию получается, что ты просто хочешь менять вид отображения. Или я не так понял?

ооо меня даже в спокойном состоянии трудно понять ...
на картинке изображено наложение исходящих данных на входящие

представь себе обычную общегеографическую карту, выкинь из нее все лишнее, кроме нарезки уровней ( чем ближе расположены уровни тем круче идет подъем\или спуск ), получится 2д массив, где каждому 1 биту можно легко сопоставить double, равный его высоте, на выходе нужно получить 2д массив из double, заменив еще и все 0 биты согласно градиенту подъема\спуска между извсетными значениями в координатах 1 битов

[Sashok]

То есть у тебя есть топографическая карта с изоклинами, и ты хочешь найти промежуточные высоты? Да, именно для этого я и хотел применить интерполяцию. Только у меня информация растровая, то есть значения высоты по узлам квадратной решетки. В твоем случае формулы явно будут сложнее, потому что нет квадратной решетки, а в остальном все должно работать.

[RXL]

Mayor, брось ты эти биты - нету их! Есть линии уровней и точки вершин и низин. Крайне сомневаюсь, что ты сможешь распознать все это - точки то подписаны для человеческого восприятия, да и прочая ненужная для данной задачи информация на карте в изобилии присутствует. Это и есть процесс именуется оцифровыванием карты и обычно выполняется руками, которые задают компу точки и контуры линий.
Если это переведено уже в цифровой вид, то рассматривать надо не как набор битов, а как 3D информацию, состоящую из параллельных плоских фигур сложного контура.

[Mayor]

Если это переведено уже в цифровой вид, то рассматривать надо не как набор битов, а как 3D информацию, состоящую из параллельных плоских фигур сложного контура.

во во, типа уже переведено в цифровой вид, в виде замкнутых концентрических линий сложного контура, для каждой из линий известна ее высота, нужно расчитать высоты для всех остальных точек карты\0 битов\2д массива

[Алексей++]

если изолинии перевести в векторный вид, то между двумя соседними изолиниями можно "приложить" разность потенциалов (=высоте в условных единицах H/U ). Затем применить какой нибудь метод расчёт напряжённости электрического поля ))

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

[Mayor]

если изолинии перевести в векторный вид, то между двумя соседними изолиниями можно "приложить" разность потенциалов (=высоте в условных единицах H/U ). Затем применить какой нибудь метод расчёт напряжённости электрического поля ))

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

если я тебя правильно понял, то я обдумывал тоже самое когда упростил задачу до интерполяции 1мерного массива, только докатился вместо проведения прямых линий, до соединения 3х точек 2мя функциями проходящими соотвественно через 1,2 и 2,3 точку, производные которых равны в 3й точке

после чего все благополучно загнулось, на переходе к 2х мерному массиву

[Sashok]

Алексей1153++, у меня вызывает большие сомнения фраза насчет прямой, которая будет "как можно более перпендикулярна ближайшим отрезкам изолиний". Я довольно легко могу предложить картинку, где такой прямой просто не будет. Скорее всего надо искать минимальное расстояние от каждой точки одной прямой до какой-нибудь точки другой.
Впрочем, есть и еще один недостаток, присущий как твоей, так и моей формулировке: при линейной интерполяции мы потеряем любые "холмики" и "впадины", не дотягивающие до следующей изолинии, даже если их существование логично следует из окружающего рельефа.
Вообще-то, чем больше я думаю о задаче вцелом, тем больше прихожу к печальному выводу, что никакая интерполяция не добавляет информации, а значит, к реальному рельефу интерполированная поверхность будет иметь очень косвенное отношение.

[Алексей++]

ну так то да, перпендикулярностью иногда и не пахнет, это всё таки будут кривые. Остаётся имхо только рассчитать как поле - всё для этого есть, препятствием является только огромный объём вычисленний

[Алексей++]

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

у нас получится 3D-каркас, который можно превратить в полигональную модель рельефа. Ну а дальше - дело техники )

[Mayor]

у нас получится 3D-каркас, который можно превратить в полигональную модель рельефа. Ну а дальше - дело техники )

это дело техники у мне тоже в готову приходило, только я планировал использовать нечно вроде волнового поиска путей, для нахождения отрезков минимальной длинны, соединяющих 2 контура\сложной окружности

проблемма в том, что проц должен обсчитать минут за 5 матрицу размером 1к на 1к

[Алексей++]

ну и много ли на том километре будет изолиний ? ) 200 бы было

[Алексей++]

Sashok, ну так что, чем всё закончилось то ?

[Sashok]

Алексей1153++, пока ничем. Пытаюсь внрутренне, для себя, определить, можно ли применить интерполяцию по осям последовательно, как это предлагается для билинейной. По-хорошему, надо бы попробовать на каких-нибудь примерах.
За это время я получил ответ от своего знакомого-географа. Он сказал, что, поскольку интерполяция не добавляет информации, вся идея не имеет смысла. Ну, то есть, "большие топографические дяди" так не поступают. А еще наткнулся на статью какого-то китайца, который взял для примера куски поверхности с рельефом от равнинного до горного на территории США, сделал из SRTM-90 интерполяцию в 30м и сравнил результат с SRTM-30. Этот, наоборот, уверяет, что все очень здорово, но у меня есть сомнение, не является ли эта статья просто результатом дипломной работы.

[Mayor]

За это время я получил ответ от своего знакомого-географа. Он сказал, что, поскольку интерполяция не добавляет информации, вся идея не имеет смысла.

с фигов не имеет смысла то?
твой географ чтоли собрался каждый пиксел на карте измерять?

смотри тебе нужно получить 3д реконструкцию карты, у тебя есть возможность измерить высоты только в 100 или 1000 точек, как ты собрался изображать 3д ланшафт без интерполяции?

как он будет рисовать карту для 1000*1000 точек?

[Mayor]

Sashok,  ты 010300 ?

[Sashok]

Mayor, что такое 010300, я не допер, извини...
Идея географа следующая.
Если у тебя есть сетка точек (скажем, каждые 30м, как в STRM-30), то никакая интерполяция не добавит тебе реальной информации о поверхности. То есть интерполяция не сделает качество карты лучше, чем с разрешением 30м. Она поможет только с точки зрения рисунка, ну чтобы он был непрерывный, а не из точек.
Я ему возразил, что из общего характера рельефа примерно следует, где может оказаться точка, находящаяся посредине между известными, высота же не случайная величина. На это он ответил, что там может быть скала, пропасть, просто ровное место, этого я не узнаю. А значит, качество карты не улучшится.
Учитывая, что STRM-30 доступно только для территории США (+ еще что-то незначительное), а для других районов Земли общедоступно только STRM-90, для интересующих меня карт данных явно недостаточно.

[Вад]

Правильно, новой информации не прибавится, и интерполяция - это просто допущение, предположение. Но верно и то, что на пологих участках погрешность будет небольшая. Так что, смотря для чего нужна информация.

[Sashok]

Вад, в том-то и дело, что нужна она для походов в горах.
Мои скитания по разным горам (см. "Лучше гор могут быть только горы") показали, что в некоторых местах хорошую топокарту достать можно, а в других их просто нет. Или они проходят по военному ведомству, и достать их невозможно.
Насчет пологих участков верно. И не только пологих. Мой аргумент был в том, что даже в горах, скажем, сыпуха не может лежать круче, чем под определенным углом, и наклон резко меняться не может, а значит интерполяция должна хорошо работать. Но мой знакомый ответил, что, если у меня уже есть информация о том, что в конкретном месте лежит сыпуха, это значит, что я делал съемку на местности и тогда я могу улучшить карту без всякой интерполяции. А насчет пологого участка, если я уперся в каньон шириной 5м, мне ни тепло ни холодно от того, что оба берега у него плоские и находятся на одной высоте.

[Sla]

Sashok,  ну... так ведь информации не добавишь.

Есть oziexploer (кажется так). эта штука позволяет  построить рельеф местности по  изолиниям.
а разрывы очень хорошо видны на космических снимках

[Sashok]

Sla, да, про ozi я читал, только это ведь не то, что мне нужно. Мне нужно построить карту по точкам рельефа.
Что же касается космических снимков и аэрофотосъемки, то, насколько я знаю, все на них и строится. В частности, SRTM построено как раз на базе космической съемки с дальнейшим огрублением.
Только тут опять проблемы:
1. Я совершенно не представляю себе, как по снимкам строить рельеф.
2. А где их взять? Скажем, где взять данные аэро/космической съемки Анд?