So, welcome everybody for today's lecture in which we will have a very new mathematical

tool with which we want to analyze and process data, namely finite weighted graphs.

Before I introduce you to this very interesting concept, which is actually part of our research

in our working group, I would like to especially thanks my former boss and colleague, Professor

Abdirahim Elmoultas, for allowing us to use the images from our research in this talk

and in these slides.

So before we really get into math, let me try to motivate you why finite weighted graphs

might be an interesting idea for data processing.

So we will start in this talk by short motivation and I will give hints to mathematical related

work in different directions.

Then I will explain the main concept of these graph tools, followed by ideas on how you

can translate differential operators, which you know from numerical mathematics, to graphs.

And based on these differential operators, you can of course then start to formulate

PDEs or variational problems and try to solve these not on a grid or on a finite element

scheme, but on a finite weighted graph.

In the end, I will try to give more motivations in this research direction by showing you

nice applications and we will look especially into two different directions.

One are diffusion based problems.

So this is kind of based on a Laplace equation and the other one will be interpolation based

problems where we try to fill in missing information in data.

So let me get started with some motivation first.

So where can we find finite weighted graphs in our surroundings, in our daily lives?

So the first thing I'm always coming up with is finite weighted graphs can be used for

image processing.

So what you see on the left hand side, this is an image which consists of course of small

pixels.

These are these small rectangles and a classical image processing scheme or algorithm would

always look at one center pixel, which would be the red one, and it will connect it to

its four nearest neighbors, which are the blue ones.

And as you can see, these local connections already form a small local graph.

So just by looking at the local neighborhood of a pixel, you could construct a graph and

then you can apply algorithms which work on graphs here for an image processing task.

But that's actually not very interesting.

I mean, traditional image processing does this all the time.

So what can we do else with graphs and images?

So the idea is that if you look now into this quite noisy black and white picture of this,

I think it's a female actress, if you connect this pixel with other pixels somewhere in

the image, you don't look now for proximity, not for local neighbors, but you're looking

actually for texture that is very similar to the one in the center that you're interested

in.

So let's now have a look at this blue graph construction here.

We have a center area which is surrounded by a black border.

And what we are able to do with this graph constructions, we're looking for similar areas

in the images, especially for this part of the head, these feathers, which you would

like to connect.

And by connecting these, we're not looking into proximity, but in similarity of data

information.

And this helps us later on, as you will see, to find very good image regions for denoising,

for example.

And by doing this, we're not having, as in the left example, a local graph, but we have