алгоритмы интерполяции

← →
ghg (2003-05-20 07:57) [0]

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

← →
ghg (2003-05-20 10:52) [1]

может таки кто-нить что-нить скажет?

← →
Кулюкин Олег (2003-05-20 10:59) [2]

А Яндекс по запросу "алгоритмы интерполяции" ничего не говорит?

← →
ghg (2003-05-20 11:08) [3]

там конечно много, но того что надо как-то ...
может у кого есть что по-конкретнее

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

Так вот интересует именно эта зависимость. Кто-нибудь такое делал?

← →
Катерина (2003-05-20 11:18) [4]

То, что Вы пишите в первом и последнем сообщениях - разные веши. Для построения изолиний по матрице существуют одни алгоритмы, а для "сгущения" матрицы (добавления дополнительных узлов грида между существующими) - другие. Хотя и те и другие основаны на интерполяции: линейной, сплайн, комбинаций.

← →
Кулюкин Олег (2003-05-20 11:27) [5]

2 ghg
Лет 7 назад я писал интерполяцию на QBasic, использовал линейную, сплайновую и по коэффициентам Фурье.
Если найду исходник, могу намылить.

Но, мне кажется, Вы быстрее найдете в Яндексе.

← →
ghg (2003-05-20 11:29) [6]

>Катерина © (20.05.03 11:18)
вот мне бы про все это где-нить почитать

Я понимаю что такое сплайн но вот как его прикрутить с не к функции (1D) а к матрице (2D) не знаю.

Мне по сути и изолинии нужны и построение сплошных изображений.
Ну ткните в книжку в какую-нибудь, тока именно чтобы 2D было.

Спасибо.

← →
ghg (2003-05-20 11:32) [7]

>Кулюкин Олег © (20.05.03 11:27)
Был бы рад за исходник.
Но лучше бы сам алгоритм, написать я и сам поди напишу.

Спасибо.

← →
Nikolay M. (2003-05-20 11:36) [8]

http://algolist.manual.ru/maths/geom/

не подойдет?

← →
Кулюкин Олег (2003-05-20 11:37) [9]

2 ghg © (20.05.03 11:32)
Алгоритмы я не помню, 7 лет прошло :(
А исходник дома посмотрю, если найду - пришлю завтра с утра

← →
ghg (2003-05-20 11:55) [10]

>Nikolay M. © (20.05.03 11:36)

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

2All
Если кто знает то есть такая программа Surfer, так вот в ней есть уже реализованные алгоритмы, но хелп этой программы отсылает к книжкам на англицком и которые фиг найдешь, а хотелось бы таки по русски про это почитать, разобраться и реализовать.

← →
Катерина (2003-05-20 12:22) [11]

Честно говоря, специальную литературу по этим вопросам я не читала (разве что хелпы к Surfer`у и аналогичным программам, да справочники по математике, которые и не упомнишь), алгоритмы разрабатывала сама. Это не верх изящества, но для решаемых мной задач этого было вполне достаточно. Могу предложить след. алгоритмы:
1. "Сгущение" матрицы (так же для пересчета поверхности, заданной матрией, в новые узлы грида).
Для каждой строки и каждого столбца проинтерполировать точки между узлами на этой строке или столбце (сплайном, например) - "новые" узлы. Между "новыми" узлами заполнить "пустоты": например, среднее арифметическое между проинтерполированными (линейно) значениями по строке и по столбцу, которым принадлежит узел.
2. Построение изолиний.
Будем называть ячейкой грида подматрицу 2*2. Т.о., вся матрица непрерывно "покрыта" ячейками. Примем за аксиому, что через одну ячейку не может проходить более одной изолинии одного уровня. Теперь для каждго уровня необходимо перебрать все ячейки, чтобы найти "точки входа". Как только точка найдена, определяется сторона ячейки, к которй эту линию продолжить - "точка выхода" (не всегда однозначно), переходим к следующей ячейке, в которую линия "вошла", ищем "выход" и т.д. до тех пор, пока линия не замкнется на себя или границу матрицы. Ячейки, через которые "прошла" линия, помечаются, как использованные, и для данного уровня изолиний больше не используются. Так для каждого уровня.
Надо четко пределиться с порядком обхода ячеек и порядком перебора сторон ячейки для определения "точки выхода". Решение в этом случае неоднозначное.

← →
Mystic (2003-05-20 12:30) [12]

См. MATLAB, семейство функций contour, contour3, contourc, contourf, contours, contourslice.

← →
Mystic (2003-05-20 12:38) [13]

http://www.utexas.edu/math/Matlab/Manual/contourc.html

error(nargchk(1,4,nargin));
msg = [];
if (nargin <=2),
numarg_for_call = 1:nargin;
if ~isa(varargin{1}, "double")
varargin{1} = double(varargin{1});
end
zz=varargin{1};
else
numarg_for_call= 3:nargin;
if ~isa(varargin{1}, "double")
varargin{1} = double(varargin{1});
end
if ~isa(varargin{2}, "double")
varargin{2} = double(varargin{2});
end
if ~isa(varargin{3}, "double")
varargin{3} = double(varargin{3});
end
zz=varargin{3};
msg = xyzchk(varargin{1:3});
if ~isempty(msg), CS = []; return, end
end;

CS=contourc(varargin{numarg_for_call});
[Ny,Nx]=size(zz);

% Find data values and check curve orientation.

ii= ones(1,size(CS,2))~=0;
k=1;
while (k < size(CS,2)),
nl=CS(2,k);

% Now this is a little bit of magic needed to make the filled contours
% work. Essentially I draw the *closed* contours so that the "high" side is
% always on the right. To test this, I take the cross product of the
% first vector with a vector to a corner point and test the sign
% against the elevation change. There are several special cases:
% (1) If the contour line goes through a point (which happen when -Infs
% are around), and (2) when the contour level equals the level on the high
% side (this always seems to happen in "simple test" cases!). We take
% care of (1) by choosing other points, and we take care of (2) by adding
% eps to the data before comparing with the contour data.

if ( CS(:,k+1)==CS(:,k+nl) & nl>1 ),
lev=CS(1,k);

% Use manhattan distance to find a line segment that is the
% farthest away from being on the grid (skewd is an integer
% when a line segment is aligned with the grid so we look
% for the "least integer-like" distance).
skewd=abs(diff(CS(1,k+1:k+nl)))+abs(diff(CS(2,k+1:k+nl)));
skewd=abs(skewd-round(skewd));
[md,t]=max(skewd);
if isempty(t), t = 1; end

x1=CS(1,k+t); y1=CS(2,k+t);
x2=CS(1,k+t+1); y2=CS(2,k+t+1);
vx1=x2-x1; vy1=y2-y1;
cpx=round(x1); cpy=round(y1);
if veryclose([cpx cpy],[x1 y1])
cpx=round(x2); cpy=round(y2);
if veryclose([cpx cpy],[x2 y2]),
% If we"ve made it to here, the contour line is along a
% grid line. It is also possible we"re on a ridge or valley.
% If so, filled ridge or valley contours will be drawn
% with the same color on both sides.
if [cpx cpy]~=round([x1 y1]), % Diagonal contour
cpx=round(x1);
else % edge contour
cpx=round(x1)+round(y2-y1);
cpy=round(y1)-round(x2-x1);
% Make sure the values stay in bounds (stay at least one pixel
% away from the edge since filled contours put NaNs there).
if (cpx < 2) | (cpx > size(zz,2)-1)
cpx=round(x1)-round(y2-y1);
end
if (cpy < 2) | (cpy > size(zz,1)-1)
cpy=round(y1)+round(x2-x1);
end
end;
end;
end;
vx2=cpx-x1; vy2=cpy-y1;
if ( sign(zz(cpy,cpx)-lev+eps) == sign(vx1*vy2-vx2*vy1) ),
CS(:,k+(1:nl))=fliplr(CS(:,k+(1:nl)));
end;
end;
ii(k)=0;
k=k+1+nl;
end;

% Data from integer coords to data coords. There are 3 cases
% (1) Matrix X/Y
% (2) Vector X/Y
% (3) no X/Y. (do nothing);

if nargin>2,
x = varargin{1};
y = varargin{2};
end

if isempty(CS)
% Nothing to do
elseif (nargin > 2) & (min(size(varargin{1})) > 1),

X=CS(1,ii)"; Y=CS(2,ii)";
cX=ceil(X); fX=floor(X);
cY=ceil(Y); fY=floor(Y);

Ibl=cY+(fX-1)*Ny; Itl=fY+(fX-1)*Ny;
Itr=fY+(cX-1)*Ny; Ibr=cY+(cX-1)*Ny;

dy=cY-Y; dx=X-fX;

CS(1,ii) = [ x(Ibl).*(1-dx).*(1-dy) + x(Itl).* (1-dx).*dy + ...
x(Itr).*dx.*dy + x(Ibr).*dx.*(1-dy) ]";
CS(2,ii) = [ y(Ibl).*(1-dx).*(1-dy) + y(Itl).*(1-dx).*dy + ...
y(Itr).*dx.*dy + y(Ibr).*dx.*(1-dy) ]";

elseif (nargin>2 & min(size(x))==1 ),
X=CS(1,ii); Y=CS(2,ii);
cX=ceil(X); fX=floor(X);
cY=ceil(Y); fY=floor(Y);

dy=cY-Y; dx=X-fX;

if (size(x,2)==1),
CS(1,ii)=[x(fX)".*(1-dx)+x(cX)".*dx];
else
CS(1,ii)=[x(fX).*(1-dx)+x(cX).*dx];
end;

if (size(y,2)==1),
CS(2,ii)=[y(fY)".*dy+y(cY)".*(1-dy)];
else
CS(2,ii)=[y(fY).*dy+y(cY).*(1-dy)];
end;

end;

function tf = veryclose(a,b)
% Return true if the two inputs are very close to each other
tf = all(abs(a-b) <= sqrt(eps)*max(abs(a),abs(b)));

← →
ghg (2003-05-20 12:52) [14]

Ладно будем копатьсяч в Matlab"e.
Если что то я еще вернусь. :)

алгоритмы интерполяции Найти похожие ветки