Warping a triangle in Octave

[Eugenio]

How do I perform a triangle warp in octave?

I have an image and the vertices of two triangles; I should warp (morph?)
the content of the first triangle into the other (while keeping untouched
the rest of the image). Warping generic polygons would also be fine.

[Francesco Potortì]

Post by Eugenio
How do I perform a triangle warp in octave?
I have an image and the vertices of two triangles; I should warp (morph?)
the content of the first triangle into the other (while keeping untouched
the rest of the image). Warping generic polygons would also be fine.

I suppose you should write an ad hoc function to do that.

[Eugenio]

Post by Francesco Potortì

Post by Eugenio
How do I perform a triangle warp in octave?
I have an image and the vertices of two triangles; I should warp (morph?)
the content of the first triangle into the other (while keeping untouched
the rest of the image). Warping generic polygons would also be fine.

I suppose you should write an ad hoc function to do that.

I can't believe nobody already wrote it... but I couldn't find it yet :)

[Michael Weitzel]

Post by Eugenio

Post by Francesco Potortì

Post by Eugenio
How do I perform a triangle warp in octave?
I have an image and the vertices of two triangles; I should warp (morph?)
the content of the first triangle into the other (while keeping untouched
the rest of the image). Warping generic polygons would also be fine.

I suppose you should write an ad hoc function to do that.

I can't believe nobody already wrote it... but I couldn't find it yet :)

Warping between triangles is just a linear transformation:

% source:
p1 = [ 0, 0 ]; p2 = [ 3, 0 ]; p3 = [ 0, 3 ];
S = [ [p1 1]' [p2 1]' [p3 1]' ];

% destination:
q1 = [ 5, 5 ]; q2 = [ 7, 0 ]; q3 = [ 10, 8 ];
D = [ [q1 1]' [q2 1]' [q3 1]' ];

% transform T*S = D, T unknown:
T = D*inv(S);

n = 10;
R = rand(3,n);
d = sum(R);
S = zeros(n,2);
D = zeros(n,2);
for k=1:n
% random point in source triangle
r = [ p1' p2' p3' ] * R(:,k)./d(k);
S(k,:) = r';
% same point in destination triangle
r = T*[r;1];
D(k,:) = r(1:2)';
end
hold on;
plot(S(:,1),S(:,2),'-rx');
plot(D(:,1),D(:,2),'-bo');
hold off;

Receipt: for a pixel in the destination triangle look for the
corresponding closest pixel in the source triangle. For better results
use some additional smooth interpolation of the pixels in the
source-triangle.
(warping general polygons is more difficult)

HTH, cheers,
Michael

[Eugenio]

...

Post by Michael Weitzel
Receipt: for a pixel in the destination triangle look for the
corresponding closest pixel in the source triangle. For better results
use some additional smooth interpolation of the pixels in the
source-triangle.
(warping general polygons is more difficult)
HTH, cheers,
Michael

Thanks for the tip! All the existing raster warping functions work on the
whole images, but before modifying someone else's sources, I tried to
implement your tip (i.e. linear transformation with backward looking). This
is how I did it till now:

--
im_out = im_in

(... here I compute the "src" and "dst" triangles coordinates ...)

Transform = dst*inv(src);

for y=1:height
for x=y:width
d = Transform*[x;y;1]
sx = floor(d(1)/d(3) + 1) % rounding may lead to zero
sy = floor(d(2)/d(3) + 1) % "
im_out(x,y,:) = im_in(sx, sy, :)
endfor
printf(" row %d done\n", y)
fflush(stdout)
endfor
--

For the moment, two simple for cycles are enough because I'm working on a
simple right triangle. However, it is too slow: it takes about 1 minute to
compute a 100px area. I just can't use it on a big triangle (and I didn't
implement any interpolation yet!).

My suspicion is that the bottleneck is the direct access to image pixels. Is
there a faster way to do the same thing?

[Michael Weitzel]

Post by Eugenio
for y=1:height
for x=y:width
d = Transform*[x;y;1]
sx = floor(d(1)/d(3) + 1) % rounding may lead to zero
sy = floor(d(2)/d(3) + 1) % "
im_out(x,y,:) = im_in(sx, sy, :)
endfor
printf(" row %d done\n", y)
fflush(stdout)
endfor
--
For the moment, two simple for cycles are enough because I'm working on a
simple right triangle. However, it is too slow: it takes about 1 minute to
compute a 100px area. I just can't use it on a big triangle (and I didn't
implement any interpolation yet!).

Ouch ... it should be about a 1000x faster. The computational effort for
the evaluation of "d" is close to zero and the line "im_out(x,y,:) =
im_in(sx,sy,:)" just copies some data.

Post by Eugenio
My suspicion is that the bottleneck is the direct access to image pixels. Is
there a faster way to do the same thing?

you're probably right. Prevent the colon operator if possible:

% colon operator looking for non-existent dims:
A=zeros(100,100); B=rand(100,100);
tic; for i=1:100,for j=1:100, A(i,j,:)=B(i,j,:); end; end; toc
Elapsed time is 10.95 seconds.

A=zeros(100,100,3); B=rand(100,100,3);
tic; for i=1:100,for j=1:100, A(i,j,:)=B(i,j,:); end; end; toc
Elapsed time is 0.32 seconds.

Cheers,
Michael

[Eugenio]

Post by Michael Weitzel

Post by Eugenio
My suspicion is that the bottleneck is the direct access to image pixels.
Is there a faster way to do the same thing?

A=zeros(100,100); B=rand(100,100);
tic; for i=1:100,for j=1:100, A(i,j,:)=B(i,j,:); end; end; toc
Elapsed time is 10.95 seconds.
A=zeros(100,100,3); B=rand(100,100,3);
tic; for i=1:100,for j=1:100, A(i,j,:)=B(i,j,:); end; end; toc
Elapsed time is 0.32 seconds.

It was even simpler: I was missing the semicolon in several commands... It
tried to output lots of stuff, and that was the problem :)

Now a couple of seconds is enough the compute the whole image. Thanks!