# Geodesic Triangulation for Image Compression¶


This tour explores the use geodesic triangulations to perform image compression.

In [2]:
addpath('toolbox_signal')


## Image Approximation with Triangulation¶

It is possible to approximate an image over a triangulation using piecewise linear splines.

In [3]:
name = 'cameraman';
n = 256;
M = rescale( load_image(name, n) );


Number of points used to compute the approximation. The more points, the smallest the error.

In [4]:
m = 400;


Seeds random points, include the corners into these points.

In [5]:
vertex = floor( rand(2,m-4)*(n-1) ) +1;
vertex(:,end+1:end+4) = [[1;1] [1;n] [n;n] [n;1]];


Compute a Delaunay triangulation.

In [6]:
faces = compute_delaunay(vertex);


A first way to perform an approximation with |m| triangles is to interpolate the image at the sampling points |vertex|.

In [7]:
vinterp = interp2(M, vertex(2,:), vertex(1,:));


Each |vinterp(i)| is the value of the approximating image at the |vertex(:,i)|. We compute a spline interpolation.

In [8]:
Minterp = compute_triangulation_interpolation(faces,vertex,vinterp, n);


Display the approximation.

In [9]:
clf;
subplot(1,2,1);
plot_triangulation(vertex,faces, M);
title('Triangulation');
subplot(1,2,2);
imageplot(clamp(Minterp), ['Interpolation, SNR=' num2str(snr(Minterp,M)) 'dB']);


Another, better way to compute the approximation is to compute coefficients |vapprox| that performs the best L2 approximation with linear spline.

In [10]:
vapprox = compute_orthoproj_triangulation(vertex, faces, M);
Mapprox = compute_triangulation_interpolation(faces,vertex,vapprox, n);


Compare interpolation and approximation.

In [11]:
clf;
imageplot(clamp(Minterp), ['Interpolation, SNR=' num2str(snr(Minterp,M),3) 'dB'], 1,2,1);
imageplot(clamp(Mapprox), ['Approximation, SNR=' num2str(snr(Mapprox,M),3) 'dB'], 1,2,2);


## Isotropic Metrics for Image Approximation¶

It is possible to compute optimized sampling location |vertex| by using the farthest point sampling algorithm with a well chosen metric |W| so that more points are put in areas of strong gradient.

The metric will be of the form

where |epsilon| and |alpha| control the density variation strength.

Parameters for the metric.

In [12]:
alpha = .7;
epsilon = 1e-2;


Exercise 1

Compute a density function that is larger at area of large gradient. |W(x) = (norm(grad(M))+epsilon|)^alpha|, for |alpha=.7|. To stabilize the process, you can smooth a bit the gradient magnitude. lur a little cale to set up the contast

In [13]:
exo1()

In [14]:
%% Insert your code here.


Exercise 2

Perform farthest points sampling to compute sampling location |vertex| and the corresponding geodesic Delaunay triangulation |faces|. ompute the Delaunay triangulation

In [15]:
exo2()

In [16]:
%% Insert your code here.


Perform approximation over the triangulation.

In [17]:
vgeod = compute_orthoproj_triangulation(vertex, faces, M);
Mgeod = compute_triangulation_interpolation(faces,vertex,vgeod, n);


Compare interpolation and approximation.

In [18]:
clf;
subplot(1,2,1);
plot_triangulation(vertex,faces, M);
subplot(1,2,2);
imageplot(clamp(Mgeod), ['SNR=' num2str(snr(Mgeod,M),3) 'dB']);


Exercise 3

For a large value of |m| compute the approximation for several |alpha|.

In [19]:
exo3()

In [20]:
%% Insert your code here.