Intializing packages

When running this notebook for the first time, this could take up to 15 minutes. Hang in there!

After you select your image, we suggest moving this line above just above the top of your browser.

The fun stuff: playing with transforms

This is a "scrubbable" matrix: click on the number and drag to change!

A =

$($ 1.0 0.0 $)$

$($ 0.0 1.0 $)$

Grab a linear or nonlinear transform, or make up your own!

zoom = 1.0

pan = [0.0, 0.0 ]

α=

0

β=

5

h=

5

pixels =

800

Show grid lines ngrid =

10

Circular Frame radius =

1

Above: The original image is placed in a [-1,1] x [-1 1] box and transformed.

Pedagogical note: Why the Module 1 application = image processing

Image processing is a great way to learn Julia, some linear algebra, and some nonlinear mathematics. We don't presume the audience will become professional image processors, but we do believe that the principles learned transcend so many applications... and everybody loves playing with their own images!

Last Lecture Leftovers

Interesting question about linear transformations

If a transformation takes lines into lines and preserves the origin, does it have to be linear?

Answer = no!

The example of a perspective map takes all lines into lines, but paralleograms generally do not become parallelograms.

A nice interactive demo of perspective maps from Khan academy.

Challenge exercise: Rewrite this using Julia and Pluto!

Julia style (a little advanced): Reminder about defining vector valued functions

Many people find it hard to read

f(v) = [ v[1]+v[2] , v[1]-v[2] ] or f = v -> [ v[1]+v[2] , v[1]-v[2] ]

and instead prefer

f((x,y)) = [ x+y , x-y ] or f = ((x,y),) -> [ x+y , x-y ].

All four of these will take a 2-vector to a 2-vector in the same way for the purposes of this lecture, i.e. f( [1,2] ) can be defined by any of the four forms.

The forms with the -> are anonymous functions. (They are still considered anonymous, even though we then name them f.)

Functions with parameters

The anonymous form comes in handy when one wants a function to depend on a parameter. For example:

f(α) = ((x,y),) -> [x + αy, x - αy]

allows you to apply the f(7) function to the input vector [1, 2] by running f(7)([1, 2]) .

Linear transformations: a collection

Here are a few useful linear transformations:

In fact we can write down the most general linear transformation in one of two ways:

The second version uses the matrix multiplication notation from linear algebra, which means exactly the same as the first version when

$$A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$$

Nonlinear transformations: a collection

Composition

Composing functions in mathematics

Wikipedia (math)

In math we talk about composing two functions to create a new function: the function that takes $x$ to $\sin (\cos (x))$ is the composition of the sine function and the cosine function.

We humans tend to blur the distinction between the sine function and the value of $\sin (x)$ at some point $x$. The sine function is a mathematical object by itself. It's a thing that can be evaluated at as many $x$'s as you like.

If you look at the two sides of (sin ∘ cos )(x) ≈ sin(cos(x)) and see that they are exactly the same, it's time to ask yourself what's a key difference? On the left a function is built sin ∘ cos which is then evaluated at x. On the right, that function is never built.

Composing functions in computer science

wikipedia (cs)

A key issue is a programming language is whether it's easy to name the composition in that language. In Julia one can create the function sin ∘ cos and one can readily check that (sin ∘ cos)(x) always yields the same value as sin(cos(x)).

Composing functions in Julia

Julia's ∘ operator follows the mathematical typography convention, as was shown in the sin ∘ cos example above. We can type this symbol as \circ<TAB>.

Composition of software at a higher level

The trend these days is to have higher-order composition of functionalities. A good example would be that an optimization can wrap a highly complicated program which might include all kinds of solvers, and still run successfully. This might require the ability of the outer software to have some awareness of the inner software. It can be quite magical when two very different pieces of software "compose", i.e. work together. Julia's language construction encourages composability. We will discuss this more in a future lecture.

Find your own examples

Take some of the Linear and Nonlinear Transformations (see the Table of Contents) and find some inverses by placing them in the T= section of "The fun stuff" at the top of this notebook.

Linear transformations can be written in math using matrix multiplication notation as

$$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)$$

.

By contrast, here are a few fun functions that cannot be written as matrix times vector. What characterizes the matrix ones from the non-matrix ones?

This may be a little fancy, but we see that warp is a rotation, but the rotation depends on the point where it is applied.

Linear transformations: See a matrix, think beyond number arrays

Software writers and beginning linear algebra students see a matrix and see a lowly table of numbers. We want you to see a linear transformation – that's what professional mathematicians see.

What defines a linear transformation? There are a few equivalent ways of giving a definition.

Linear transformation definitions:

• The intuitive definition:

  The rectangles (gridlines) in the transformed image above always become a lattice of congruent parallelograms.

• The easy operational (but devoid of intuition) definition:

  A transformation is linear if it is defined by $v\mapsto A\ast v$ (matrix times vector) for some fixed matrix $A$.

• The scaling and adding definition:

  1. If you scale and then transform or if you transform and then scale, the result is always the same:

  $$T(cv)=cT(v)$$

  ( $v$ is any vector, and $c$ any number.)

  2. If you add and then transform or vice versa the result is the same:

  $$T(v_1+v_2)=T(v_1)+T(v_2).$$

  ($v_1,v_2$ are any vectors.)

• The mathematician's definition:

  (A consolidation of the above definition.) $T$ is linear if

  $$T(c_1{v}_1+c_2{v}_2)=c_{1}T(v_1)+c_{2}T(v_2)$$

  for all numbers $c_1,c_2$ and vectors $v_1,v_2$. (This can be extended to beyond 2 terms.)

The matrix

No not that matrix!

The matrix for a linear transformation $T$ is easy to write down: The first column is $T([1,0])$ and the second is $T([0,1])$. That's it!

Once we have those, the linearity relation

$$T([x,y])=xT([1,0])+yT([0,1])=x(\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n}1)+y(\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n}2)$$

is exactly the definition of matrix times vector. Try it.

Matrix multiply: You know how to do it, but why?

Did you ever ask yourself why matrix multiply has that somewhat complicated multiplying and adding going on?

Important: The composition of the linear transformation is the linear transformation of the multiplied matrices! There is only one definition of matmul (matrix multiply) that realizes this fact.

To see what it is exactly, remember the first column of lin(A) ∘ lin(B) should be the result of computing the two matrix times vectors $y=A\ast [1,0]$ then $z=A\ast y$, and the second column is the same for $[0,1]$.

This is worth writing out if you have never done this.

Let's try doing that with random matrices:

lin(P*Q)

lin(P)∘lin(Q)

Coordinate transformations vs object transformations

If you want to move an object to the right, the first thing you might think of is adding 1 to the $x$ coordinate of every point. The other thing you could do is to subtract one from the first coordinate of the coordinate system. The latter is an example of a coordinate transform.

Coordinate transform of an array $(i,j)$ vs points $(x,y)$

The original image has (1,1) in the upper left corner as an array but is thought of as existing in the entire plane.

Inverses

If $f$ is a function from 2-vectors to 2-vectors (say), we define the inverse of $f$, denoted $f^{-1}$, to have the property that it "undoes" the effect of $f$, i.e.

$$f(f^{-1}(v))=v$$

and $f^{-1}(f(v))=v$.

This equation might be true for all $v$ or for some $v$ in a region.

Example: Scaling up and down

We observe numerically that scale(2) and scale(.5) are mutually inverse transformations, i.e. each is the inverse of the other.

Inverses: Solving equations

What does an inverse really do?

Let's think about scaling again. Suppose we scale an input vector $\mathbf{x}$ by 2 to get an output vector $\mathbf{x}$:

$$\mathbf{y}=2\mathbf{x}$$

Now suppose that you want to go backwards. If you are given $\mathbf{y}$, how do you find $\mathbf{x}$? In this particular case we see that $\mathbf{x}=\frac{1}{2}\mathbf{y}$.

If we have a linear transformation, we can write

$$\mathbf{y}=A\mathbf{x}$$

with a matrix $A$.

If we are given $\mathbf{y}$ and want to go backwards to find the $\mathbf{x}$ from that, we need to solve a system of linear equations.

Usually, but not always, we can solve these equations to find a new matrix $B$ such that

$$\mathbf{x}=B\mathbf{y},$$

i.e. $B$ undoes the effect of $A$. Then we have

$$\mathbf{x}=(BA)\ast \mathbf{x},$$

so that $B\ast A$ must be the identity matrix. We call $B$ the matrix inverse of $A$, and write

$$B=A^{-1}.$$

For $2\times 2$ matrices we can write down an explicit formula for the matrix inverse, but in general we will need a computer to run an algorithm to find the inverse.

Inverting Linear Transformations

$A^{-1}=\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)/(ad-bc)$ if $A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right).$

Inverting nonlinear transformations

What about if we have a nonlinear transformation $T$ – can we invert it? In other words, if $\mathbf{y}=T(\mathbf{x})$, can we solve this to find $\mathbf{x}$ in terms of $\mathbf{y}$?

In general this is a difficult question! Sometimes we can do so analytically, but usually we cannot.

Nonetheless, there are numerical methods that can sometimes solve these equations, for example the Newton method.

There are several implementations of such methods in Julia, e.g. in the NonlinearSolve.jl package. We have used that to write a function inverse that tries to invert nonlinear transformations of our images.

The Big Diagram of Transforming Images

Note that we are defining the map with the inverse of T so we can go pixel by pixel in the result.

Collisions

Check out Linear Map Wikipedia

Transformation Matrix Wikipedia

Why are we doing this backwards?

If one moves the colors forward rather than backwards you have trouble dealing with the discrete pixels. You may have gaps. You may have multiple colors going to the same pixel.

An interpolation scheme or a newton scheme could work for going forwards, but very likely care would be neeeded for a satisfying general result.

Appendix