Computer Graphics and Computer Vision | Lecturer: Umut Güçlü

General high-level rendering process

The first three lectures describe the steps of the rendering process according to Chapter 11 of Jason Gregory's Game Engine Architecture.

Page 622:

  1. Describe virtual scene
  2. Create a view on scene by placing a virtual camera
  3. Define light sources
  4. Describe visual properties of surfaces in the scene
  5. Solve the rendering equation (also called shading equation)

N.B. the book does not discuss them in this order.

In the rendering process, there is a trade-off between fidelity and real-time performance. The ray-tracing of Pixar Renderman took 53h per frame (24 FPS, 102 min movie). Real-time renderers, e.g. a rasterizer, typically need to render withing 33.3 ms (30 FPS). Real improvements have been made in this area (Flight Simulator 2020!).

N.B. rasterization describes the process of converting an image description (in terms of vectors) onto a raster, either in 2D or 3D.

1. Describing a scene

Different physical properties lead to different visual properties.

When objects are opaque, you only need to render the surfaces.

When objects are non-opaque (i.e. transparent or translucent) you also need to render the interior of objects.

Simplification: just use surfaces with alpha channels.

A simple numeric opacity measure known as alpha is used to describe how opaque or transparent a surface is. This approach can lead to various visual anomalies (for example, surface features on the far side of the object may be rendered incorrectly), but the approximation can be made to look reasonably realistic in many cases. Even amorphous objects like clouds of smoke are often represented using particle effects, which are typically composed of large numbers of semitransparent rectangular cards. Therefore, it’s safe to say that most game rendering engines are primarily concerned with rendering surfaces. (624)

Used surface representations

What is a surface?

A surface is a 2D subspace of infinitely many points in 3D space. You can represent them in several ways:

  • Parametric surface equations R^2 -> R^3
  • Patches / patch meshes
    • Bézier
    • NURBS
  • Subdivision surfaces (approximate smoothness by recursively defining the surface in terms of its smaller component surfaces)
  • Polygon meshes: represent objects by a mesh surface, e.g. triangle meshes.
    • Main difference with subdivision surfaces is that the amount of tesselation (see below) is determined non-dynamically by the designer.

NURBS and Bézier are good for objects with smooth surfaces.

Polygons are good for geometric shapes, e.g. a flat building.

Bézier: define n-dimensional control points, defines a smooth n-dimensional surface "stretched" between those points. Excellent at defining smooth surfaces with very little control points (memory efficient). In practice, they are harder to manipulate, so they are usually decomposed into flat triangle meshes to approximate the smooth surface (i.e. using subdivision surfaces).

Non-uniform rational basis spline (NURBS): generalization of Bézier curves.

Wikipedia source:

Although such curves could be drawn freehand at the drafting board, shipbuilders often needed a life-size version which could not be done by hand. Such large drawings were done with the help of flexible strips of wood, called splines. The splines were held in place at a number of predetermined points, called "ducks"; between the ducks, the elasticity of the spline material caused the strip to take the shape that minimized the energy of bending, thus creating the smoothest possible shape that fit the constraints. The shape could be adjusted by moving the ducks.

Tesselation

Tesselation is the "process of dividing a surface up into a collection of discrete polygons" (625).

Triangulation is tesselation into triangles.

With fixed tesselation, you get silhouette edges when objects are close to the virtual camera. Dynamic subdivision subsurfaces do not have this issue.

Ideally, you have a uniform triangle-to-pixel density, independent of how close or far an object is from the virtual camera. You want each triangle to be less than one pixel in size.

A practical solution is to approximate this ratio is to define meshes at various levels of detail (LOD), where LOD has the highest tesselation and is used when the object is very close to the camera.

When this process is automated and performed in real time, we speak of progressive meshes.

Triangle mesh rasterization

The most commonly used real-time representation is the triangle mesh.

Triangle meshes are "piecewise linear approximations of surfaces" (625), similar how to you can approximate a parametric curve with several smaller line segments.

Q: Why is the triangle mesh so useful for real-time rasterization?

See page 625:

  • Triangle is the simplest polygon type.
  • Triangles are always planar i.e. they are necessarily in the same plane (add another vertex and you lose this property)
  • Triangles remain triangles under most transformations, e.g. projections. The only edge case is where it degenerates into a line.
  • Practically all (commercial) graphics-acceleration hardware uses triangle rasterization.

Additional considerations from the webs and my own brain:

  • Triangles have very nice properties, that allow you to efficiently determine winding order for backface culling.
  • Computing the intersection of a ray with a triangle is a fairly simple operation and can be optimized (whereas computing inttersections with NURBS is difficult).
  • Importantly, all polygon meshes can be translated into triangles. So all complex geometric primitives can be translated into triangles meshes so we can take advantage of the computational benefits of using triangles. E.g. instead of computing an intersection with a Bézier patch, we can do it instead with its triangle mesh subcomponents.

Triangle direction math:

  • The normalized cross product of any two edges by definition defines a "unit face normal" N.
    • The direction of the unit vector N (i.e. its sign) depends on the order in which you multiple edges
    • I.e. the "direction of the triangle" depends on the order in which you specify vertices.
    • This is because multiplication of edges is anticommutative
    • You need to define the winding order of the vertices for back-facing culling
    • Triangles with the same winding order have the same direction
    • Unity treats CCW triangles as back-facing and culls them.
    • Back-face culling is deletion/non-rendering of back facing triangles (i.e. Crossproduct vector is pointing away from camera)

Summary: in the rendering process you check whether the points of a triangle (or polygon) appear clockwise or counterclockwise. This determines the surface will render or if back-face culling applies.

Back-face culling is important for efficiency: you do not have to render non-visible triangles.

Concerning the cross-product:

  • Does not give a scalar like the inner product of two vectors
  • Instead provides a vector in a higher dimension orthogonal to both vectors

See dot vs cross product.

Right-hand rule for direction of cross product:

  • For vectors a x b let the index of your right hand point in direction of a, and middle finger in direction of b
  • Your thumb points to the direction of the resulting vector

Q: Why does the winding order determine the direction of the triangle?

Because the cross-product between two vectors is anti-commutative. If you switch the arguments of the cross product around results in the inverse of the former result. So for cross product: A x B = -B x A

How to construct a triangle mesh

Solution 1:

  • Store all vertices in a vertex list
  • Each possible vertex triplet is a new triangle

Downsides:

  • Each vertex is stored multiple times, both for similar and different triangles
    • V1,V2,V3 = V2,V3,V1 = V3,V1,V2
    • If you maintain winding order, previous is not the same as V3,V2,V1!
    • Waste of memory
    • Waste of bandwidth
  • So not used in practice

Solution 2:

  • Maintain an additional list with triplets of vertex indices (i.e. triangles)
    • No duplication of vertex objects by using pointers instead
    • Instead you have the extra cost of a list
    • Used in practice, simple solution

This is a good trade-off because the vertex also stores way more information, e.g. what is necessary for surface coloring (cf. lecture 2).

This data structure is used in Unity and is very popular.

Solution 3: Strips and fans

  • Reduce vertex duplication without extra list
  • By instead predefining how vertices can be combined/ordered into triangles
  • With this strategy you can make strips and fans

Both start with:

1) First three vertices form the first triangle

For strips:

2) Each subsequent vertex is a triangle with the previous two vertices. - In order to keep a consistent winding order, you need to alternate the ordering of the last two vertices!)

For fans:

2) Form a new triangle with each subsequent vertex, the last vertex and the first vertex.

Not as commonly used as the indexing method. But has some potential advantages (see p. 630):

  • Potentially save money because no index buffer is required
  • Better cache coherence of memory accesses in Video RAM due the sequential nature of this approach; efficient caching of already processed vertices.
  • Can still eliminate vertex duplication by using a variant with indexed lists.

Model space

The vertex coordinates are defined relatively to an arbitrary local coordinate space called "model space".

Only depends on the triangle mesh itself.

Define where the origin of an object is. E.g. the origin at the center (in a plane), or at the bottom (e.g. for cars; it wheels) It is arbitrary, but has to be consistent.

World space

Is fixed in order to define points in scenes consistently for all objects in the scene.

When we place a mesh in the scene, the mesh instance itself also holds a transformation from the local model space to the globally defined world space.

So any object (=mesh instance) has a reference to its shared mesh, and to its model-to-world transformation matrix ('world matrix' for short).

In model space a center may be 0,0 coordinates. Apply a transformation during rendering to give this local coordinate in model space its coordinate in world space.

TODO: I don't know yet what "w" is:

When rendering a mesh, the model-to-world matrix is also applied to the surface normals of the mesh (see Section 11.1.2.1). Recall from Section 5.3.11, that in order to transform normal vectors properly, we must multiply them by the inverse transpose of the model-to-world matrix. If our matrix does not contain any scale or shear, we can transform our normal vectors correctly by simply setting their w components to zero prior to multiplication by the model-to-world matrix, as described in Section 5.3.6.1. (632)

Main points

  • Winding order determines direction of triangle due to cross-product being anti-commutative
  • Meaning that the winding order determines whether a surface will be rendered when using back-face culling
  • Vertex coordinates are defined in local model space
  • To indicate the position of objects in a world, relative to each other, we need to transform coordinates in model space to world space
  • Object instances themselves hold a model-to-world transformation matrix

4. Describing the visual properties of surfaces

Light-surface interaction is one of the most important aspects of photorealistic rendering.

Light properties are relevant because they underlie color.

What is color?

Color is the "interpretation" of light (interesting claim).

Of course in computer graphics we only take interest in visible light, the range between UV and IR.

Spectral colors: consist of a single wavelength.

Non-spectral colors: grayscale, white, black, metallic, pink etc.; contains multiple wavelength.

Light-object interactions

Depends on surface of object and medium through which it travels.

Perception of red can be caused by:

  • white light hitting object that absorbs everything except red
  • red light reflecting of white object

1) Light can be absorbed: this determines what color we experience an object in.

2) Types of reflection by objects:

  • Diffuse: bounces off at many angles
  • Specular: bounces off at same angle on opposite side
    • These reflections form images
  • Anisotropic: bounces off differently from different directions

3) Light transmitted by objects

  • Scattered in translucent objects
  • Partially absorbed (e.g. colored glass)
  • Refracted (direction change)
    • each wavelength is refracted at a slightly different angle
    • E.g. water in glass; prism effect.

4) Diffraction

If light travels through very narrow aperture, light spreads out.

Not considered in computer graphics; negligible at common scale.

N.B. notice the difference between refraction (direction change) and diffraction (scattering through narrow aperture).

Color space and color models

Color model: representation of different colors with different coordinate systems, e.g. RGB, HSV, etc.

  • Usually 3D, because our eyes have three types of photoreptors (cones)
  • Each of the axes in unit space is called a channel

Color space: mapping from "relative" color, e.g. in RGB color model, to "absolute" colors.

  • E.g. sRGB, Adobe RGB, etc.
  • Based on empirical studies, behavioral studies (psychophysics)
  • What spectrum is visible to the average human?

Color format: encoding of colors in computer memory, e.g. 8 bit representation for each channel in RGBA888

Opacity and alpha channel

Color models need another channel for representing opacity, e.g. in RGBA8888.

E.g. RGBA5551 --> If you only use 1 bit for opacity, obviously an object is either completely opaque or not at all.

Vertex attributes

  • Position vector, usually in model space
  • Vertex normal
    • "defines the unit surface normal at the position of vertex i" (635)
    • For Vertex-based lightning calculations
    • Substitute for the normal of the surface (see above)
    • Usually, some normalized average of the surfaces containing vertex i
  • Vertex tangent and bitangent
    • Orthogonal to vertex normal and to vertex normal; so they define a 3D space
    • Tangent space for per-pixel lightning calculations
    • Bitangent is sometimes called binormal, but it's not actually normal to the surface.
  • Diffuse color, in RGB/RGBA color space computed online (dynamic lighting) or offline (static lighting).
  • Specular color
    • Color to use when light reflects from a shiny surface towards the virtual camera
  • Texture coordinates (u,v) for texture mapping
    • Maps vertex onto 2D texture
    • Triangles can be mapped with more than one texture and can thus have multiple texture coordinates
  • Skinning weights
    • For skeleton animations, where vertices are connected through joints
    • Defines how much a vertex of this skeleton is affected by movements of the connected parts of the skeleton

Attribute interpolation

Very clear summary:

The attributes at a triangle’s vertices are just a coarse, discretized approximation to the visual properties of the surface as a whole. When rendering a triangle, what really matters are the visual properties at the interior points of the triangle as “seen” through each pixel on-screen. In other words, we need to know the values of the attributes on a per-pixel basis, not a per-vertex basis. (637)

Vertex attributes need to mapped onto connected surfaces.

Through linear interpolation:

  • Distance-weighted average of vertex attribute values.
  • For any given point, average the color values of related normal vectors.

Attribute interpolation of vertex colors is called Gourad shading. (Does not have to be linear interpolation, from what I gather).

Q: What is Gourad Shading?

Vertex normals and smoothing

Lighting uses surface properties.

The simplest way to light a mesh is to calculate the color of the surface on a per-vertex basis. In other words, we use the properties of the surface and the incoming light to calculate the diffuse color of each vertex ($d_i$). These vertex colors are then interpolated across the triangles of the mesh via Gouraud shading. (638)

  1. Compute (diffuse) vertex colors
  2. Use Gouraud shading to interpolate the colors across the mesh triangles

An important detail here is that most lighting models compute the diffuse vertex colors using a vector that is normal to the surface to simulate the impact of a lighting ray. In practice, the vertex normals are used for this.

This means that the direction of the vertex normals heavily impact the appearance of surfaces.

If you only use the vertex normals perpendicular to the surface you are coloring, together with Gouraud shading, you get a very flat colouring with sharp edges on surface boundaries.

When you instead average various normals and interpolate distance weighted with Gouraud shading), you get a very smooth colouring.

Whether this is appropriate or is an artefact differs on a case by case basis, I guess. See slide for example.

Q: How can vertex normal vectors influence the appearance of surfaces/triangle meshes?

Textures

Using vertex attributes with linear interpolation is easy, but can cause visual artefacts.

If you have large triangles, using vertices only for surface coloring is very coarse-grained. A case where this clearly shows if you have a bright specular highlight.

Alternative: specify bitmaps ("textures")

Individual pixel elements of textures are called texels and not pixels; pixels are related to the screen.

Q: What are the downsides of using vertex attributes for interpolating surfaces?

Q: What's a common and good alternative to specifying visual surface properties as vertex attributes?

Q: What's the difference between pixels and texels?

Texture coordinates

You have to map textures from texture space (2D coordinate system) onto triangle meshes.

Texture coordinates are a normalized pair u, v (normalized <- [0,1]) that we can then easily distinguish from vertex coordinates x,y,z.

Normalizing means we don't have to bother with the size of textures.

Again, we store this information in the vertices themselves, so each triangle vertex needs to be assigned a texture coordinate. Because triangles are always planar, this mapping is safe.

Texture addressing modes

Ways of dealing/using with texture coordinates outside the normal unit range of [0,1] depends on the texture addressing mode:

  • Wrap mode: repeat texture mode on integer boundaries in texture coordinate.
  • Mirror mode: repeat + mirror in the axis of transgression. (x transgression is mirror on x axis)
  • Clamping: Set to boundary colors.
  • Border color: set out-of-range coordinates to arbitrary color.

Texel density and mipmapping

Texel density: ratio of texels to pixels.

On 100% zoom: 1 ratio.

With 50% zoom: more texels per pixel, so 2 ratio (of course, the amount of pixels always stays the same due to fixed screen size; forgetting about windows mode etc.)

Goal of rendering is to keep texel density of 1 at all times, for various reasons.

If texel density is too high (too many texels are contributing to a pixel/ less than one pixel per texel), then this causes artefacts and inefficiencies:

  • cause moiré banding pattern
  • pixel colors swim and flicker because different texels may become dominant in coloring the pixel, depending on changes in the camera angle and position etc.
  • you waste computational resources when you still have a high texture resolution for distant objects (then screenspace is smaller relative to the texture, so too large texel density)

If texel density is too low (too little texels per pixel / multiple pixels per texel), the texels become larger than pixels on the screen and you start seeing the edges of texels.

So to avoid these issues, you want to approximately have a texel density of 1 both for near and distant objects. This is not possible literally, but mipmapping tries to approximate this.

  • Create several lower resolution textures, each half the size of its predecessor.
  • These are mipmaps with different "mip levels".
  • Use smaller resolution textures if the object is farther away: smaller screen size for object, so less texels needed.
  • Built in hardware: hardware chooses the appropriate mip level based on distance to the camera, such that the texel density is close to 1.

Q: What problems occur if texel density is too low or too high?

You don't always have a mipmap of the exact right level. In that case, pixels are usually rendered by sampling multiple mipmaps and blending their colors.

Texture filtering

Often, there are no 1-to-1 mappings possible between texels and pixels. Pixels can map onto any place in texture space, including right on the border between two texels.

There are various strategies for sampling the texels (texture filtering) to use and then blend their colors:

  • Nearest neighbor
    • pick texel closest to pixel center
    • Select the mip level where the texel density is closest to 1, but at least higher than 1.
  • Bilinear interpolation: distance weighted average of four (2x2) neighbouring texels
    • Select nearest mip level.
    • Suitable if texture is viewed from straight angle; causes artefacts when viewed under other angles.
  • Trilinear
    • Perform bilinear filtering on the nearest mip levels (on higher res than ideal, the other lower)
    • Linearly interpolate the results. This eliminates abrupt boundaries between mip levels on screen
  • Anisotropic
    • filters "samples texels within a trapezoidal region corresponding to the view angle, thereby increasing the quality of textured surfaces when viewed at an angle" (645-646)

Bilinear and trilinear work great when the surface is viewed head on. If you view a square under an increasing angle, it increasingly looks like a trapezoid. So ideally, in this case you do not still sample from a square, but from a trapezoid corresponding to the view angle.

Q: What kind of artefacts do you see when doing (non-anisotropic) texture filtering under angles?

I do not actually know the answer to this question.

Q: What are the four main methods for texture filtering

Q: What's the improvement of trilinear filtering compared to bilinear filtering?

Q: What problem does anisotropic filtering solve?

Materials

  • Materials are complete descriptions of shader-dependent visual properties of objects.
    • Shader parameters
    • Texture specifications etc.
  • Vertex attributes not included
  • Mash-material pairs contain all needed information for rendering.

3a. Light-transport models for light-surface interactions

Lightning is absolutely essential for rendering.

Cornell box is commonly used for displaying rendering.

1) Local illumination (LI) model

  • Only direct lighting
  • Single interaction with single object before reaching virtual camera
  • Another way of saying this: surfaces do not affect one another

2) Global illumination (GI) model

  • Can bounce of multiple surfaces.
  • And indirect lightsources

5. The rendering equation

Solving the rendering equation is the primary goal of almost all of rendering.

Global Illumination (GI) uses rendering equation. What it basically describes is the "equilibrium radiance" leaving a particular point (towards the virtual camera) as a sum of 1) emitted light and 2) reflected light on that surface from other light sources.

See slide for the complete formula. It's quite lengthy, but make sure to be able to at least name the main components.

  • L : light radiance
  • Outgoing light Lo is sum of emitted light (Le) and reflected light
  • Reflected light is sum (integral) from all incoming light from all directions (Li) scaled by 1) surface reflection and 2) cosine of the incident angle

I don't really see the cosine comes into play. It $\omega$ directly expressed in terms as a cosine rather than the angle?

There is not always an exact solution to the rendering equation.

It is a computationally intense operation. You have to follow all light bounces until they run out of energy or end up in the camera. (E.g. ray tracing is extremely costly)

So we use approximation and do not try to solve this equation in real-time rendering.

So solving this equation efficiently is the goal of various rendering techniques.

The equation does not account for all aspects of lighting.

  • Not subsurface scattering
  • Interference
  • Fluorescence
  • etc.

Q: What is subsurface reflection and/or scattering?

Many materials are slightly transparent or translucent, but not entirely. Light can penetrate the surface for a bit, but still reflects shortly after than on the material that lays a bit deeper. Depending on whether how the light refracts or diffracts, we speak of reflection or scattering.

Q: Can you describe the main components of the rendering equation?

Q: Why is the rendering equation so hard to solve?

3b. Lighting models (lighting ct'd)

Phong lightning model

"Empirical local illumination model"

Based on informal empirical observations that

  • Glossy items: small highlight with hard falloff.
  • Rough surfaces have high highlight with long falloff.

  • Use direct lighting

    • Diffuse reflection of rough surfaces
    • Specular reflection for smooth surfaces
    • Ambient lighting (approximation of indirect lighting)

Q: How does the Phong lighting model (empirical local illumination model) simplify the rendering equation?

A: It uses a heuristic based on two empirical observations to approximate the expected behavior of light. See above. Importantly, it does not try to sum/integrate over the incoming indirect light from all other objects in the scene. Instead, it approximates this by taking into account the (static) ambient lighting of the whole scene.

Modeling light sources

  • Directional (e.g. sun)
  • Point / omnidirectional (e.g. light bulb)
  • Spot light
  • Area lights
  • Emissive objects

Directional lights

  • Color and direction
  • Parallel lights
  • Not affected by attenuation or distance
    • So does not matter if you move object around the scene because distance does not matter; all at infinite distance.
    • VS. ambient lighting, which also bounces off objects and is affected by attenuation and distance from light source

Point (omnidirectional)

  • Color, direction and range
  • Equally in all direction
  • Affected by attenuation and range
    • inversely proportional to squared distance to light source
    • So decreases quadratically
    • Plus a cut-off

Spot lights

  • Color, direction, range, and angle and position
  • Cone
    • Edge is called Penumbra
  • Attenuation and range
  • Computationally expensive because you have the additional angle computations

2. Camera's and Virtual Cameras

From Futuruma: "The engines don't move the ship, the engines move the universe around the ship"

Virtual camera: simpler than real camera's, or human eye, or pinhole camera.

Imaging rectangle/plane: Ideal focal point with a frontal grid of rectangular light sensors corresponding to screen pixels

  • Is in front of aperture rather than behind it; this is not feasible physically, but we can mathematically assume the aperture is there.
  • As a result, image is not inversed
  • Light sensor corresponds to pixel

Why do you need model space? You could in principle define everything in world space, but this is inconveniënt. Consider:

  • E.g. rotating an instance around object center; this is convenient if you have origin of in model space
  • Instancing, copying model multiple times.

Q: why is the image arriving on the sensors of the virtual camera not inversed?

View space

View coordinates:

  • Turns out that rotating the entire scene to shift view, rather than the camera itself, is more efficient
  • This is of course not possible in reality; it's a mathematical abstraction
  • See Futurama quote.

So: World space gets transformed into the view space.

An axis system can be left handed or right handed. Match x-axis with thumb, y-axis with index finger, then the middle finger points to z-axis.

  • Left handed axis system: z-axis towards the scene
  • Right handed axis system: z-axis towards the viewer

The only difference this makes is what it means to increase the z-axis. In the one case increasing z will move objects on the virtual screen further away from you, in the other bring them closer.

Q: Explain this analogy with the virtual camera from Futurama: "The engines don't move the ship, the engines move the universe around the ship"

Q: Name the steps from model space to view space in the right order.

World-view transformations

In slide, Tv is a position vector of the camera?

  • View-to-world matrix
    • Defines virtual camera w.r.t. world-space coordinates
    • We rarely use "view-to-world matrix"
  • World-to-view matrix
    • The inverse of the previous
    • Converts world coordinates into view coordinates

Going the world-to-view route is more efficient because you can compute the model-to-world, and world-to-view matrices into model-view matrices. This skips an intermediate operation.

Q: Explain the differences between a view-to-world matrix, a world-to-view matrix, and a model-view matrix.

Projections into homogeneous clip space

Transformation of view into homogeneous clip space.

Goal: draw 3D thing on 2D surface. View space is still expressed in 3D, but ultimately we need to project everything onto a flat screen.

What is homogeneous clip space?

"This three-dimensional space is really just a warped version of view space."

Types:

1) perspective projection.

  • Mimics more or less real camera's or eyes.
  • Results in perspective foreshortening: the distant object will appear smaller to the one closer to the camera.
  • I.e. parallel lines appear to intersect from perspective (mathematically they can't really, of course)
  • Perspective projection matrix
    • Coordinates are vertex coordinates of frustum in view space.
  • Division by z: -Pvz negative of z coordinate in view space, happens to be our "W" component in 4D homogeneous coordinate space

2) Orthographic projection

  • Length-preserving
  • When objects are the same size, they will appear the same sizes
  • Parallel lines do not intersect.
  • Typically used in schematics, HUDs,or in isometric games.

Q: List all transformations from model coordinates to homogeneous clip coordinates.

A: Model coordinates -> (model matrix) -> world coordinates -> (view matrix) -> view coordinates (3D) -> (projection matrix) -> homogeneous clip coordinates (2D).

Homogeneous clip space

Canonical view volume: unit rectangular prism, unit cube. Usually between -1 and +1, except in DirectX (0 to 1).

  • Homogeneous coordinate space: additional value next to x, y, z in Euclidean space
  • So to go back to Euclidean space of clip space, you divide by -Pvz
  • w=1 define points in homogeneous coordinate space
  • w=0 defines directions in homogeneous coordinate space

How do these coordinates look like? Are they already 4D?

Transformation such that the coordinates of the view space are mapped onto the canonical view volume.

  • A warped version of the view space
  • Usually left-handed
    • z-axis goes into the screen
    • higher z values correspond to increasing depth into the screen
  • Independent of projection, resolution and aspect ratio, because everything is mapped onto the same canonical view volume, a unit cube.
  • So we can render without bothering about further details such as the perspective of view.

View becomes unit cube, but objects are now distorted to match the preview perspective. (Whereas before the perspective resulted e.g. in a pyramidal view volume)

Name clip space: you can now easily clip away everything outside view volume (because axes are aligned).

I believe clipping is done based on the w component: clip if -wi <= xi <= wi

Q: Why is the homogeneous clip space called homogeneous?

Q: What does "clip" in "clip space" mean?

We call this coordinate system “clip space” because the view volume planes are axis-aligned, making it convenient to clip triangles to the view volume in this space (even when a perspective projection is being used). (659)

Q: Why do objects become distorted in the homogeneous clip space?

View volume and frustrum

View volume: volume of space that is visible to virtual cameras.

Defined by 6 planes:

1) near plane: virtual light sensors (see above) 2) four screen boundaries. 3) Far plane: threshold for how far you render.

  • So view volume of perspective projection is a truncated pyramid.
  • View volume of orthographic is a rectangular prism

Both are frusta/frustums, i.e. a frustum. This is a mathematical name for any solid body cut off by two parallel planes.

Perspective projection transformation and division by z

Perspective projection divides the x- and y-coordinates by the z-coordinate: this is effectively perspective foreshortening. The width and height of an object (i.e. x and y of its constituent points) are dependent on how far away they are (z-coordinate).

I'm trying to get an intuition:

Imagine a square box seen from the front using perspective projection. The area on the box that is further away from the viewer will appear less high and narrower than it would without perspective projection.
For example, if the box is perfectly square, its front area is the same size as the top area. However, in perspective projection, the top area will be drawn as less high and more narrow than the front area of the square.

Note that when dividing by z, you introduce a non-linearity (which is the desired behavior of perspective foreshortening): the further you move away from the camera, the separation between the two objects get smaller and smaller.

More theoretically: we can represent the 3D view coordinates in 4D homeogenous coordinates (i.e. with scaling w=1), as (x,y,z,1).

If we now apply the perspective projection, the resulting vector (in homogeneous coordinates) looks like $p_h = [ a b c -p_{vz}]$.

To express the result of this perspective projection in 3D coordinates, we can translate the result back to 3D by dividing by the w component.

Because $w=-p_{vz}$, the projection from view space to homogeneous clip space amounts to dividing by the negative z coordinate in view space.

Q We talk about dividing by z, but then in fact the projection divides by the negative of z.

A: I think the answer is that, whereas view space is usually expressed in a right hand axis system, homogeneous clip is expressed as a left hand system. This reverses the direction of x. So moving in the positive z direction in the one, is equivalent to moving in negative z direction in the other.

Summary transformations:"

So we can do various transformations.
Notice that every time we speak of "homogeneous" coordinates, we use 4D vectors instead of 3D. The fourth component can be easily used for clipping.

  1. View space -> homogeneous clip space (perspective projection): divide x,y by z
  2. Homogeneous clip coordinates (4D) -> Euclidean coordinates (3D): divide x,y,z by w.
  3. Homogeneous clip coordinates (4D) -> Clip coordinates (3D): divide view space x and y by negative z-coordinate.

Later in the slide Umut says: w-component of homogeneous clip space, is the z-component of view coordinate space. That's not entirely correct: Hw = -Vz.

Coordinates in homogeneous clip space are typically expressed as 4D: (x,y,z,w). Why is that?

From here: "if w is nonzero, (x y z w) is identified with the ordinary point (x/w y/w z/w). if w is zero, (x y z w) is a direction at infinity, pointed to by the vector (x y z)."

In the first case, the smaller the w-component, the bigger x,y,z if you would translate it back to a 3D vector in Euclidean space.

From unity forum:

To start, clip space is often conflated with NDC (normalized device coordinates) and there is a subtle difference: NDC are formed by dividing the clip space coordinates by w (also known as perspective divide). NDC boundaries are "normalized" and therefore always consistently bound.

The conversion from clip space to NDC happens after the vertex shader is run and is done automatically for you. Whatever you put in your w component will be used to divide your xyz components. You output your clip space position as (x, y, z, w) in the vertex shader and the graphics API converts it to (x/w, y/w, z/w, 1).

Regardless of platform, the NDC for left/right/top/bottom bounds will be the same: the range of the x-coordinate from [l, r] to [-1, 1], the y-coordinate from [b, t] to [-1, 1]

Perspective-correct vertex attribute interpolation

  • We discussed this in lecture 1
  • From any pixel you go to the relevant point in a triangle and use its vertix attributes for interpolation
  • We have to account for perspective foreshortening by dividing our interpolated attribute values by z-coordinates

  • REVIEW See formula in slides: if you divide by z values of each used attribute, this is the same as dividing by z value of ...

Q: Why do we need to take into account perspective when doing attribute interpolation?

A: Because attribute interpolation is done in screen space i.e. after we have applied our perspective projection.

Orthographic projection

In this case, the view volume is a rectangular prism both in view space and in clip space, the projection is just a regular transformation that scales.

Screen space and aspect ratios

We now move from clip space to screen space, which is expressed in pixels.

Origin is top-left: old convention due to old screens (CRT displays? Did I hear this correctly?) that start scanning the buffer at top-left.

Aspect ratios (width x height):

  • 4:3 (traditional tv)
  • 16:9 (HDTV)

Transformation from clip space:

  • Discard z-coordinates of homogeneous clip space
    • At this point we have used them to account for perspective, so they have served their purpose.
    • This is not entirely clear to me: at what point do we then do z-tests? Clearly before discarding them.
  • Screen mapping: Scale and shift the remaining homogeneous clip space coordinates to screen space coordinates i.e. pixels.

Frame buffers

Buffer in your computer that stores the rendered images as bitmap colors (usually RGBA8888).

Display retrieves info from this buffer to display on the screen (e.g. 50 or 60Hz).

You need at least double buffering with two buffers: write to one while you read from the other. Also triple buffering.

Vertical blanking interval: when display isn't updating anything, buffers are switched so that the most up to date frame is always read. (In old display, moving electron gun from bottom-right to top-left).

This prevents tearing: that different screen parts display different frames.

If your rendering is faster than the speed with which the first buffer is displayed, it has to wait on the display. This is where a third buffer is handy: basically a queue to that the rendering engine does not have to wait on displays.

Render targets

Frame buffer is just one many render targets.

Other buffers store other intermediate rendering results, e.g. depth information.

Tests for triangle rasterization fragments

How to convert triangles from geometric descriptions into concrete pixels on the screen?

A fragment is a section of a triangle corresponding to a single pixel.

Each fragment has to pass several tests in order to be rendered and drawn on the frame buffer.

Occlusion test of depth buffers

How do we determine which triangles appear on top of distant ones?

Because objects might occupy the same space in the screen space.

1) Painter's algorithm * Enumerate furthest to closest, render from back to front; so an over-write method. * Outdated, computationally inefficient. * There are scenarios where this solution is undefined; when triangles intersect (see triangles). * Intersect meaning: they are not layered on top of each other but "penetrate" each other in the z-axis. * So not fail safe! 2) Depth-buffering or z-buffering * Compare z-buffers to measure depth * Write a fragment to a frame buffer but also store its depth in a corresponding depth buffer * Only draw a second fragment to the frame buffer iff its depth is strictly less than that in the corresponding depth buffer location.

Z-fighting and the w-buffer

If two values are close in space (clip space z-coordinate), and we have limited precision, these values might collapse into the same value. This causes conflicts in determined which is on top, basically leading to a random decision procedure for the color; hence, flipping colors.

We can only solve models that appear overlapping due to limited precision (not that actually overlap).

Solution: w-buffering

In the conversion from view-space to clip-space, you scale with 1/z, so non-linearly in z. As a result: the further you move away from the camera, the separation between the two objects get smaller and smaller.

This is a problem when we actually need them to be discriminative.

Before this conversion the z-coordinates still scale linearly and this problem does not occur. So independent of depth or scaling.

Easy solution: store the z-coordinates from view space.

Q: Describe the problem of z-fighting

Q: How dus w-buffering solve the issue of z-fighting?

Q: Why is w-buffering called w-buffering, even though we use (view-space) z-coordinates?

We know from above that the w-component in homogeneous clip space is the negative z component from view space! So using the z-components from view space is as trivial as retrieving it from the w-component in the current homogeneous clip space (instead of using the current z)!

The terminology can be very confusing here. The z- and w-buffers store coordinates that are expressed in clip space. But in terms of view-space coordinates, the z-buffer stores 1/z (i.e., 1/pVz ) while the w-buffer stores z (i.e., pVz)! (667)

Of course, to get the view-space z component, you need to invert w first, interpolate the resulting z, and then re-invert it to store it in the w-buffer.

Shaders and the rendering pipeline

N.B. Shaders do not only concern "shade".

History

1988-2001.

Shader defined by Pixar's RenderMan Interface Specification.

Fixed-function pipeline (earlier known as "graphics pipeline"):

  • called fixed because it transforms vertex data to frame buffer by hard-coded lighting and texture mapping
  • in the contemporary graphics pipeline shaders are programmable.

2001: graphics revolution with Third-Generation GPUs.

Introduction of vertex programmability in GPUs.

2002-2004: Fourth-generation GPUs.

Vertex-level and pixel-level programmability.

But what was lacking was a common framework.

  • Microsoft: HLSL (High Level Shader Language)
    • Only DirectX
  • NVIDIA: CG (C for Graphics)
    • Only NVIDEA cards
  • OpenGL: GLSL (OpenGL Shading Language)
    • For cross-platform compatibility

HSLS and CG were initially the same, but diverged in development between Microsoft of NVIDIA. But they are essentially the same.

Unity adjusts used convention based on your target platform.

2008-2012:

Added functionality that did not exist in the original pipeine:

  • Geometry shaders
  • Compute shaders

Contemporary graphics pipeline

Geometry stages

  • Per vertex computations.
  • Transformations of vertex data from model space to viewport coordinates.

  • Input -> vertex shader

a. Vertex data: vertices, normals, indices, tangets, binormals, texture coordinates. b. Textures

New w.r.t. legacy graphics pipeline: textures now also go in the geometry phases, because the (vertex- and geometry-) shaders can now already use info from textures now in the geometry process.

This is because textures can also contain e.g. height values in addition to color information (which is used later in the fragment stage). N.B. texture coordinates are stored in vertices. E.g. grass or water shaders.

  1. Vertex shader (new) -> geometry shader

The vertex shader takes on the responsibilities of transforming vertex coordinates from model space, to world/view space, to clip space with projection. (They were separate steps in the legacy graphics pipeline).

  1. Geometry shader (new) --> clipping
    • Generating new geometry that does not exist in the original model.
  2. Clipping -> Perspective division
    • Clipping is done in ... clipping space.
    • It's most efficient to do here, based on w-coordiantes, I think.
  3. Perspective division -> viewport transform
    • Volume of frustum to regular and normalized cube in homeogenous unit cube.
    • I think by dividing by w (slides do not mention this)
  4. Viewport transform -> rasterizer
    • Mapping of vertices into screen coordinates.

Rasterizer

Transform vectorial data into discrete data that can be rasterized.

Fragment stages

  1. Input: Vectors from screen space. Output: convert to frame buffer

Whereas the geometry stage (including vertex and geometry shader) do per vertex calculations, the fragment shader creates fragments and performs per fragment computations.

  1. Fragment shader

    • Programmable customize coloring, and lighting and texture of final meshes (2D operations)
    • Outputs fragments
  2. Post fragment and per fragment processing:

    • Color blending of overlapping fragments for a given pixel
    • Determines what is rendered: depth-z and alpha testing.
    • If test is passed, write fragment to framebuffer.

External stage: Compute shader (new)

  • It is not really tied to a particular stage in the pipeline
  • Can affect any other programmable part of the pipeline
    • I.e. the Vertex Shader, Geometry Shader, and Fragment Shader.
  • Main purpose is GPGPU: not graphics processing/rendering, but using GPUs to do general purpose programming that is not strictly related to generating graphics.
  • GPGPU: general purpose GPU computing
  • Similar to CUDA (NVIDIA)/OpenCL (OpenGL)

ShaderLab language of Unity

We have discussed graphics pipeline as a fixed order of things. This is true 99% of the time. But in Unity you can script the pipeline itself as well, so you can program the entire pipeline behavior as well. We disregard that here and focus on the built-in pipeline.

  1. Surface shaders
    • Simplifies writing of {2}
    • Only lets you write the part that you want to adjust, fill in other details at compile time.
  2. Vertex and fragment shaders
    • Discussed above
    • Main use in practicals
  3. Fixed function shaders
    • Use existing macros to create your shaders.
    • We ignore this

Q: What about geometry shaders? Where are they?

See code example in slides.

Syntax

Declarative language with weird nested braces syntax.

Wrapper around actual shader code that Unity used to generate shader code.

{ Shader "name" { [Properties] Subshaders [fallback] [CustomEditor] } }

Properties

  • Define what properties are shown in Unity Editor and what the shader wants to use
// 
name {"display name", Datatype } = defaultValue 

// Colors and vectors
name {"display name", Color } = {number, number, number, number}
name {"display name", Vector } = {number, number, number, number}

// Textures
name {"display name", 2D } = "defaulttexture" {}
name {"display name", Cube } = "defaulttexture" {}
name {"display name", 3D } = "defaulttexture" {}

So as you can see, the vectors are 4D for some reason (that we do not know). How to make a 2D vector? Not really possible, but you can define a CustomEditor script to not show values for the last two values (to avoid confusion about there being 4 fields while only using 2 values).

Possible DefaultValue:

  • Range(min, max)
    • Spawns slider in editor
  • float
  • int
Subshaders & Fallback

Different hardware and shader versions allow different functionalities.

Unity goes through subshaders in order, selects the latest shader that is supported by the end user's hardware.

Unity has a fallback shader if you define no subshader.

Surface shaders

Utility to make shader generation easier.

Name of the shader is important, organizes shaders in a particular folder/namespace.

pragma Surface surf Lambert

Pragma directive: give command to compiler and is not part of program logic itself.

surf is the name, which requires a void surf later on.

Lambert is a lighting model.

In void surf you adjust only the properties you want to adjust.

SubShader code, writtin in HLSL:

Define input:

struct Input {
float2 uvMainTex;
};

You cannot name this however you want. uvMainTex is a variable defined within Unity.

If you want to access within your shader, you must use the same names you declared as Properties. So pay attention that you still also declare them, with type, in your subshader. E.g.

fixed4 _FirstAlbedo;

inout is both input and output variable: allows you do modify input and pass it through in its modified form.

HLSL/Cg syntax

  • Syntax of C programming language.
  • But adds new data types for graphics programming

  • float: for coordinates

  • half: half precision of floats; directions and HDR colors because they need less precision
  • fixed: for regular colors
  • int: for counters, indices etc.
  • sampler2D_half
  • sampler2D_float
  • samplerCUBE_half
  • samplerCUBE_float

  • Packed arrays

    • Data type + dimensionality
    • E.g. fixed4 creates an array with 4 fixed variables.
    • float4 example = (0, 0.1, 0.2, 0.3);
    • Array do not use typical square bracket indication for accessing elements, but used numbers.
    • Two methods of accessing elements:
      1. ex.x, ex.y, ex.z, ex.w
      2. Or use RGBA: ex.r, ex.g, ex.b, ex.a

Two important operations on packed arrays:

  • Mask/swizzle to select/swap arbitrary elements
    • ex.bgr gives us a new packed array
    • this appending of bgr is swizzling.
    • either use xyzw or rgba, obviously
    • float3 ohter_ex = ex.bgr;
    • this is called swizzling when you just change the order of coordinates.
  • Smear: assign same value to all elements
    • float4 smear = 0;

Matrices: float2x4 is a matrix datatype with 2 rows and 4 columns.

float2x2 exampe = {0, 0.1, // row 1
                   0.2, 0.3}; // row 2

Accessing matrix elements:

ex._m01

[M]atrix, row 0, column 1. The m is always fixed.

Chain them:

float4 other_ex = ex._m00_m01_m02_m_03;

You can only use the bracket notation for selecting whole rows in matrices.

float2 third_ex = ex[0];

Procedural generation survey

Content

One of the first games with procedural content generation: the original Rogue.

So already a hot topic since 80-bit games of 1980s!

  • Elite 1984
  • Exile 1995
  • Elite dangerous 2014
  • No Man's Sky 2016

The original reason for content generation was lack of memory, not content variety (n.b. 32 kb of RAM!).

Dungeons

Examples of dungeon generation:

  • Rogue
  • Spelunky 2008
  • The Binding of Isaac 2011

Rogue-likes, also sometimes called Rogue-lites or Rogue-like-likes.

Also introduces permadeath so people do not beat the game by memorizing.

Still used in modern games that are not rogue-likes:

  • Diablo III
  • Bloodborne (Chalice dungeons)

Level / landscape generation

  • Civilization VI 2016
  • Minecraft 2011
  • Terraria

This also has a different use: also used by developers to generates landscapes that become static maps in game.

Two main use cases

  • Generate variety in gameplay
  • Development: make high fidelity game assets; or simply cheaper to create.

Both replace work done by designer and can thus be construed as an AI task.

Pseudorandom numbers

  • Numeric mixing and game seeds
  • Halton sequence
  • Phyllotaxic angles
  • Poisson disk

Types

  • True random
    • Requires hardware to sample from a natural stochastic phenomenon.
    • Thermal noise
    • Nuclear decay
    • E.g. random.org
  • Cryptographic random numbers
    • Random enough that they can be used at the basis of cryptographic software
    • Meaning: they are unrepeatable (clear difference with pseudorandom)
  • Regular pseudorandom numbers
    • Uses seeds, so repeatable
    • It is often possible to deduce the used seed, so unsuitable for cryptography.

Pseudorandom numbers

Move from pseudo- to cryptographic randomness in more languages due to security concerns.

System.Random class in C# : pseudorandom

C#: System.Security.Cryptography.RNGCryptoServiceProvider

We however do not care about security, but we care about whether they have properties that cluster in ways that correspond to nature or are repeatable.

Numeric mixing and game seeds

All pseudorandom number generators use numeric mixing.

Numeric Mixing: any information of seed values is supposed to be mixed throughout their corresponding pseudorandom numbers.

If two seed values differ only in their first bit, the pseudorandom numbers that result should differ at more than bit. I.e. the two inputs must be "thoroughly mixed", and the variation in the output should not be a very clear mapping of variation in the input.

Sequences of pseudo random numbers beginning with a particular seed will always be the same because they depend deterministically on the previous timepoint. This means that you can use seeds to determine other seeds.

s_0 -> s1, r

subscripts indicate timepoints. seeds and pseudorandom number.

Seeds are very handy in games to select a particular randomly generated level.

Issue: How do you maintain reproducibility if you have several pseudorandom number generations, e.g. not only the level but also the generated treasure.

If you have one seed for the level, another seed for the treasure location etc. you need a bunch of seeds to reproduce a particular state of the game.

C.f. in machine learning there is an issue with reproducibility of training procedure:

  • Reinforcement learning might use random generators multiple times
  • Cuda maintains its own number generator (not accessible by numpy etc.)

General solution: have a master pseudonumber generation specified with starter seed.

This general generator provides the seeds for all other generators. This is the one you re-use.

Halton sequence

Random numbers often clump together in a way that looks unnatural. This is a problem when random numbers are used for placement of objects. For these cases we want a more smooth distribution over space.

The Halton sequence is controlled by small coprime numbers, e.g. 3 and 5.

Coprime: two numbers with no other common divisor except for 1.

Each coprime assigned to one of the axes. Each dimension produces a sequence of fractions between 0 and 1.

So one controlling number per dimension.

E.g. with controller number 3:

  • range(0,1)
  • split in parts of 3. Start with 1/control number, add to itself within range.
  • Sequence so far: 1/3, 2/3.
  • Raise controller number to power: 3^2=9
  • Repetitions are not added again, you stay within range.
  • Divide again, but iteratively add original chunk size on top 1/9, 1/9 + 1/3 = 4/9, 4/9 + 1/3 = 7/9 (higher is out of range)
  • Repeat for 2/9, adding the coprime again, leading to: 5/9, 8/9.
  • Repeat for 3/9 etc. (but in this case the rest is repetition or out of bounds)
  • Sequence: 1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9.
  • Raise controlling number again to higher power, if desired. Etc. (N.B. You always add the original chunk size 1/3)
    • N.B. do not just keep squaring! We want 2,4,8 and not 2,4,16.

Important: you keep the sequence in the order of adding. This is because you will zip together with the sequence on the other axis.

I guess a possible property here is that you keep points of similar granularity close over axes?

Strictly speaking this is not a pseudorandom generator.

  • No seed (replaced by controlling numbers)
  • Sequence itself is deterministic.

For appearance of randomness you thus take some extra measures.

The first layer is clearly linear. So if you use a big coprime, you get artefacts: 1/11, 2/11, 3/11, etc.

Easy fix: skip this first part of the sequence. For controlling number n, skip first n numbers.

You can use various similar strategies, e.g. skip more initial values, or only use every kth number. K is often taken as coprime to original coprime number. (Used in statistical "simulation" cases, what is meant here?)

For procedural content, small n and skipping first n is often sufficient.

A slightly different issue than these artefacts, is that the Halton sequence is fully deterministic, so when you repeat the same sequence (e.g. to compose it into a larger grid), you start noticing the regularities.

For this we can use another strategy: use a small random offset for both axes.

With these strategies combined we may call the Halton sequence is "quasi-random".

Q: Describe the Halton sequence procedure and give an example

Q: Is the Halton sequence an example of a random, a pseudorandom generator, or neither?

Neither, it is usually called 'quasi-random'. It appears random but does not rely on a seed and is the same every time.

Q: Why should you not use big coprimes as a controlling number in the Halton sequence? And what are possible solutions?

Then the chunks added are very small. E.g. for controlling number 20 you get 1/20, 2/20,3/20 etc. Skip first n numbers. Sample each kth number.

Phyllotaxic angles

Halton sequence works fine in 2D, but not on a spiral or radial figures (e.g. circle).

Conceptually similar to controlling number, choose numbers with a "metal" ratio, i.e. numbers that can be written as (n, 1/(n+...), etc ).

Why "metal"? Don't really know, but see here.

Most famous example of "metal" ratio: golden ratio (1+sqrt(5)/2). The golden ratio is the metallic mean between 1 and 2. (The silver ratio between 2 and 3, and so on.)

There exist a golden ratio between the fraction of a Fibonacci nummer with its direct (smaller) predecessor. So dividing increasingly large Fibonacci numbers converges to the golden ratio.

Obtained with fractions of two Fibonacci sequences: 1/1, 2/1, 3/2, 5/3, 8/5, ... This converges to the golden ratio.

E.g. 8/5 = 1.6 and 10946/6765=1.6180

You can give other metal ratios by using variants of such sequences.

Not you use this ratio sequence by adding it to the angle. To make this random is to add random offset to each component. (But not too much, then these patterns will look unnatural and too disorganized again).

From Wikipedia: "The golden ratio appears in some patterns in nature, including the spiral arrangement of leaves and other plant parts."

Natural plant development exhibit these intervals in leaf placement ( phyllotaxis ). E.g. the circular organization of flower petals with 2pi/golden ratio (+- add some small random number).

Poisson disk

We will do this in the practical.

In item placement, overlapping random numbers are a big issue.

Issue: Halton sequence does not guarantee that there is no overlap. Is still useful for e.g. placing grass or hair, but not for buildings.

Strategy: reject if overlap. Simple and works with random numbers or Halton sequence.

Thesis: if you sample this way (with rejection test), you basically sample from Poisson disk distribution.

There are specialized algorithms to achieve this without rejection sampling for efficiency. E.g. see Bridson 2007, Fast poisson disk sampling in arbitrary dimensions.

Choose your poison (pun intended):

Q: When can we use appropriately use Halton sequences, Phyllotaxic angles, or Poisson disks?

Halton: even distribution of points, but points can overlap, which may cause problems with when used for object placement of let's say big trees. It may however suitable for smaller pattern-like objects such as grass, or hair.

Phyllotaxic angles: circular placements like leaf petals.

Poisson disk: adds a rejection test for overlap, so guarantees that there is no overlap between generated points, so this is useful for placement of bigger solid objects such as buildings or rocks.

Fractals

Coastline paradox

Coastline paradox: length of coastline is heavily dependent on measurement method. To what extent to you take irregularities into account? If you use a "long measurement ruler" you abstract away from all irregularities. Other formulation: keep the rules the same length but scale the object.

So the relations between dimension, scale and size do not conform to our Euclidean intuition.

  • Scaling line with 2 increases length with scale 2.
  • Scaling a cube with 2, will scale the volume with 8.
  • Coastline scaled by 2, length does not scale with 2.

So the general formula here is that we have to take into account some scaling factor $\epsilon$ and the amount of dimensions where it operates on, to determine the scaling $N$ on the output measure. So scaling on the output $N=\epsilon^D$.

In case of the cube, we have for scaling factor 2, applied in three dimensions, so N = 2^3 = 8.

Mandelbrot, B. (1967) "How long is the coast of Britain? Statistical self-similarity and fractional dimension. Science. 156 (3775): 636-638."

Koch curve

Procedure:

  • Divide line segment by three
  • Remove middle part
  • Replace by two lines "triangle"
  • Repeat for each line segment.

  • We can observe that when we scale the Koch curve with 3 (in each iteration), then size/length is scaled with 4.

  • We want to determine the scaling of the output $N = e^D$.
  • But now we can reverse engineering this based on our observations to infer the dimensionality of this fractal.

This is also called the self-similarity dimension, I think. The slides do not mention this.

We have - N = e^D - log N = D log e - D = log N / log e = log 4 / log 3 = 1.26189 ...

So this is nog 1D, neither 2D, but ... 1.26D. Hmmm... Closer to a line than to a plane (<1.5).

Sierpinsky triangle

  • Triangle scaled with 2, size scaled by 3.
  • 1.58 dimension
  • Closer to plane than to a line (>1.5)

The question to ask yourself is: if you scale, how many more self-same copies do you get?

Look at any given Sierpinsky triangle, for example the initial state. If you make it's base line twice as long, you suddenly get three copies (N.B. the middle triangle is the absence of a triangle!)

Minkowski-Bouligand dimension

Of course, the coastline does not have the self-same property, so this is not quite the same as a self-similarity dimension.

  • Grid overlay
  • we have some scale factor e
  • count N cells that intersect with what interests us, e.g. the coastline
  • scale object (larger) with factor 2
  • we get more intersections, because relative to the object the cells are smaller.
  • repeat, and for each iteration D = log e / log N , where e approaches infinity. (in practice: empirical limit).
  • stop when D is more or less stable.

Fractal geometry and dimension of objects

The weird "in-between" dimensions are fractal dimensions.

Mandelbrot: Fractal geometry of nature, 1975.

Fractal is "a set for which the Hausdorff-Besicovitch dimension strictly exceeds the topological dimension."

E.g. the Koch curve is fractal because 1.26 > 1 (topological dimension of line).

Nature also displays self-similarity.

Lindenmayer-systems (L-systems)

We focus on trees.

  • Introduced by Lindenmayer for modeling algae growth.
    • The Algorithmic Beauty of Plants
    • Available on internet archive.
  • Recursive parallel rewriting system and type of formal grammar.
  • Because of recursive nature, can be used for defining fractals.

Tuple G = ( V, w, P)

V: alphabet, allowed symbols/constants (have no matching rule). w: axiom, initial string p: are productions / rules of combining into new symbols. * predecessor -> successor mapping

What is stopping criteria?

  • N iterations
  • condition on for example section length.

See slides for examples from Lindenmayers book:

  • Algae
  • Koch curve
  • Sierpinski triangle
  • Dragon curve
  • Fractal plant
    • what we push and pop is orientation and location; like a stack; last in, first out.

Q: practice application of a grammar to produce the algae code.

Randomness:

  • Create randomness either in constants (e.g. angle used)
  • Or by randomly picking a rule sometimes
  • Have a different set of rules for different generations (e.g. store this in a "level" variable and use this to select production rules)
    • E.g. to distinguish generating branches and leaves

Q: What are ways of manipulating formal grammars to produce more random/natural looking patterns?

Landscape generation

Live demo of "World Machine" landscape generation software.

Basic landscape cookbook:

  • Create a 2D Cartesian grid (a polygon mesh)
  • Pseudorandomly elevate vertices to mimic natural landscapes (looping over vertices)
  • Apply color and texture based on elevation
    • E.g. from water, to sand, to grass, to rock, to snowy rock.

What type of noise is useful for landscape generation?

What type of noise is useful for landscape generation?

Why does white noise not work?

"Randomness" in nature is:

  • self-similar (cf. the use of fractals in Lindenmayer-systems)
  • coherent, i.e. spatially autocorrelated

Compare natural textures. E.g. a zebra pattern, words, or a tree bark. Randomness is smoother, correlated with neighbour pixels.

Gradient noise (Perlin noise)

Ken Perlin, 1985, developed for the movie Tron.

Used heavily in computer graphics for natural randomness, e.g. in smoke, clouds, dirt, weathering.

It is used so much that Perlin received an Oscar for it in 1997.

  • Have a 2D grid and an input point in the grid
  • Randomly generate gradient vector (unit vector) for each corner of each grid box
  • Compute "distance offset" for each corner; i.e. distance from corner to your point.
  • For each corner, dot product between the relevant gradient vector and the latter distance offset
  • Interpolate the gradients pairwise in a consistent predefined order
    • E.g. linearly interpolate first two dot products, and second two, and then linearly interpolate them again.
    • Remember: dot product returns a scalar.
  • End result: value per point defines a "height map" used for rendering.

Book tells you to start with a smaller grid than your target. Umut uses source and target grids of the same size. He suggested the book are actually already talking about "fractal noise"

Fractal noise

Also known as "fractional valued motion."

Idea: combine multiple gradient noises with different amplitudes and frequencies. The number of different sources used are called "octaves" or "levels".

Important parameters:

  • Gain (persistence) -> amplitude factor
    • You multiply each successive amplitude with gain after each octave
  • Lacunarity -> frequency factor
    • Idem, but then for frequency.
  • Octaves -> number of combinations

Additionally (in the code demo):

  • Scale is sort of a zoom factor;
    • higher scale is less zoom
    • multiplies input coordinates with the scale
  • Shift (for x and y): "add" value to axis coordinates.
    • By shifting you sample new values for "incoming" coordinates.
    • Looks like moving clouds :-)

Can be applied to any type of noise.

We are going to apply it to Perlin noise.

  • Start with Perlin noise
  • Double the frequency and half the amplitude after each octave. This fills in details.
  • So you start with the broad strokes of a landscape (high amplitude, low frequency)
  • You then start "filling in the details" by lowering the amplitude (smaller effects) but with more or "faster" irregularity (higher frequency)

Reasoning of effects:

  • Double frequency: compress both axes with factor 2
    • Things will change more "rapidly" i.e. more frequent
  • Double amplitude: raise the minimum and maximum height of the random movements.

Guidelines:

Lacunarity: between 1-3 * 1 is very similar to perlin noise * 3 is too rough

Zero values make no sense, as this nullifies all other octaves.

Faults / fractures

Fault is a fracture in a rock, where each side of the fracture "slides" along the fracture.

You do not do a physical simulation of tectonic plate shifts, that would be way too expensive. We discuss some algorithms to simulate the resulting appearance of a fracture.

Simple example: make a single fracture that shifts height of rest of map. So heighten height on one side of the fracture and/or lower it on the other.

Variation: modulate height shift by the distance from the fracture line, e.g. with an exponential function, so that close points are modulated stronger.

Thermal erosion

Piles of granular material tend to spread out and form deposits with a constant slope. Landscape features with this slope angle are called talus or scree slopes. You find this e.g. at the bottom of mountain ridges.

Slope angle is known as "angle of repose"

  • Loop over all vertices in mesh
  • Calculate difference in height between that vertex of interest and its four neighbouring vertices (organized in a regular grid; each vertex has four neighbours).
    • Based on the angle of "repose"
  • Specify "height threshold" as h = d tan(theta)
    • with d: distance between two cells
    • theta: angle of repose
  • Is difference in heights calculated before higher than the specified threshold?
  • If yes, we move some of the height of the previous vertex to the next vertex.
  • Amount of height is proportional to additional height beyond threshold.

Hydraulic erosion

Also known as "fluvial erosion". Simulates water running continuously over a landscape. Perhaps the most demanding and difficult modifier in landscape generation that is crucial for realistic landscapes, e.g. mountains.

This is a game breaker. How efficient and well can you do hydraulic erosion?

Not part of our practical.

Improving this is state-of-the-art research.

One approach: Finite Element Method (FEM).

Naive algorithm for each point:

  • Rain falls across landscape
  • Calculate water flows to neighbouring locations based on water height and terrain elevations
  • Model erosion or deposition of materials by the water
  • Water moves across the landscape along with suspended materials
  • Have some threshold calculation about when to deposit materials
  • Water evaporates

Extremely hard to do all this at runtime, so it kind of defeats the purpose of procedural generation for many applications.

Altitude filtering

More of a class of modifiers.

Apply some function only to a particular elevation level. We already discussed coloring as an example modifier of this type.

This approach works well if your map is relatively small. If you want to generate a whole "continent", this doesn't work great because the meaning of elevation levels is likely not consistent on that scale.

Examples (example code in slides ):

  • Islands: pull down borders below see level to form islands
  • Buttes' (the flat top rocks in Westerns; pronounce "bute", "bjoet"): flatten lower elevation; raise rest to flat plateau.
    • Use a sigmoid
  • Valley: half sigmoid
  • Terraces (e.g. like the famous rice fields)
    • Need some sort of repeating sigmoid function with many steps
    • Tadaaa, remember this one: y=x-sin(x)

Dungeon and Maze generation

Problem statement. We have grid with cells, walls, and passages. We want to carve passages by erasing walls to connect such that the grid becomes a maze with different features. (You can rewrite all algorithms such that they place walls instead of removing them; but that's not the approach taken here).

Different algorithms will produce different features that we can study.

We focus on perfect mazes:

  • Every cells is reachable from every other cell by exactly one path.
  • These have nice properties that we will use.

Non-perfect mazes are called braid mazes. This is what we normally understand to be a maze.

Shortest path

Use Dijkstra's to find the distance to every other cell given some starting point.

N.B. in a non-weighted graph without loops maze Dijkstra just degenerates to simple BFS.

To find the shortest path between two points A and B, compute Dijkstra from point A. Then position yourself at B, and backtrack.

N.B. there is no one shortest path of a maze; it's only defined between two cells. This is a difference from the question what the longest path is.

Longest path

This is an NP-hard problem, but for perfect mazes there is a simple algorithm using Dijkstra's.

  1. Take an arbitrary cell A, run Dijkstra, and find the furthest point B.
    • Can be multiple; just pick one.
  2. Run Dijkstra from point B, and select the furthest point C
  3. Find the path from B to C. (The slides say this incorrectly)

Coloring

Coloring each cell with an intensity proportional to the shortest distance to some starting cell is a good of showing the texture of a cell.

Scheme: color lighter when closer to start, darker when further away.

E.g. this clearly shows the bias of a binary tree algorithm maze.

Some features to measure

  • Longest path
    • Again, this is a maze feature, whereas shortest path is not
  • Dead end
    • Fewer dead end and a large longest path may indicate lengthy side roads
  • Twistiness
  • Directness
  • Intersectionality

Perfect maze algorithms

Texture: The texture of a maze is the general style of its passages. How long do they tend to be? Which direction do they tend to go to?

Bias: most of the randomly generated mazes tend to have very similar textures.

A binary tree maze is an example of a heavily biased maze.

N.B. mazes usually have entrences and exists. You add those post-hoc.

Binary tree

  • Randomly carve north or east for each cell

That's the only rule! Do note that you do exclude illegal moves. At the northern corridor, you can only go east. At the east column, you can only go north.

Features:

  • Diagonal texture towards north-east corner
  • Northern and eastern row are open column
  • TODO: *Difficult to use with masks and some non-rectangular grids.
    • Q: What does "masking" mean in this context this mean?
    • Wasn't addressed in the lecture nor in the literature

Sidewinder

Quite similar to binary tree.

  • Consider the grid one row *at a time, left to right, bottom to top.
    • Clear difference with binary tree, where order doesn't matter
    • So there is no possibility to erase the northern wall
  • For each row you start a "run", where you randomly remove the east wall (or not); a run stops when you do not delete the east wall and cannot wrap around to other rows.
  • After going over all the cells you have a collection of runs (or do this immediately after a run)
  • For each run, pick a random cell and carve north for that cell.
  • Northern row is an exception: have an open corridor there.

Features:

  • Northern passage is open (but eastern doesnt have to be, like binary)
  • The texture is now not diagonally but vertically oriented (because rows are connected with a north connection)
  • Similarly to binary tree, this does not work well if we don't have a rectangle grid.

Aldous-Broder

  • Start a random walk without any restrictions
  • If we encounter a cell already visited, we still move to it but do not open a passage to it, because this would introduce a loop.
  • End when all cells are visited.

Features:

  • Quick start, but the end phase is very inefficient
    • Cf. Wilson's has the opposite!
    • Quick start because you are unlikely to find cells already in the maze
    • At the end almost all cells are already in the maze, so you traverse a lot of cells without taking action.
  • Unbiased, so no preference for a feature or texture!

Wilson's

  • Add one cell to the maze and mark it as visited (important!)
  • Start a loop erasing random walk that stops when you encounter a cell that's already in the maze, but unlike Aldous-Broder, we do not immediately add the "visited" cells to the maze.
    • So notice that in this algorithm there is a distinction between "visited" as a temporary state and "being in the maze" as a state that we normally tag with "visited".
  • When you are doing the random walk and encounter a cell you already visited in that random walk, track back to that cell and continue (this is the loop erasing behavior).
  • Only when we reach a cell that is already in the maze, we add the traversed path to the maze.

Features:

  • Slow start, efficient at the end.
    • The slow start is due to having to start over a lot in the beginning
    • At the end you are more efficient because you are very likely to find a cell that's already in the maze.
  • Unbiased, like Aldous-Broder.

Generative modeling

Definition of generative modeling: A way to describe how data is generated using a probabilistic model, that captures the data generating process. So we estimate P(x) i.e. the probability of an observation x; or P(x|y), i.e. the probability of an observation given a lable y.

This allows you to sample new data points from the modeled distribution that is, ideally, the same generative model of the observed data points.

Contrasted with discriminative modeling, which estimates P(y|x) where y is the training label and x an observation. For example, common classifying tasks are a way of discriminative modeling. So discriminative modeling concerns mapping observations to label; whereas generative modeling is about learning probabilistic model for generating observations; so not that much focus on labels.

If we know the generative process underlying observations, we can generate for example data points that look as if they were from the data set with the observations, even though it is not. For example, if we have a data set of horses, and we learn the probabilistic model that captures the features of horses present in the data set, we can generate a new horse image by sampling new features.

General generative framework

  1. Have a data set of observations, X.
  2. These are assumed to be generated following some unknown distribution, $P_{data}$
  3. The goal is to let $p_{model}$ mimic $p_{data}$

When are the generated examples decent? Satisfy both points:

  1. Then sampling from $p_{model}$ generates examples that seem to come from X.
  2. It can generate examples that can be sufficiently different from observations in X
    • Otherwise the model is just copying the input.

Generative modeling exemplified with a game

Example inspired by the lecture book.

Have a rule to generate 14 2D points using some $p_{data}$. Slide shows a grid with distributed smileys.

Challenge: generate another example that looks like it came from the same underlying generative rule.

Next we'll discuss

Related probabilistic concepts

Sample space:

Set of all possible values that our observations can take. E.g. in the previous a 2D grid, all x and y coordinates following the generation rule.

(Probability) density function p(x):

  • function that maps a data point x in the sample space to a number in [0,1]
  • must sum to 1, i.e. define a probability distribution.

Parametric model $p_{theta}(x)$:

  • Defines a family of probability density functions, where each function depends on a finite amount of parameters theta.
  • E.g. consider a normal distribution that depends on mean and variance.

Likelihood of parameters $L(theta|x)$ (stylized capital L):

  • Likelihood of a set of parameters theta given an observed data point x.
  • $L(theta|x) = p_{theta}(x)$ (notice the small x, this concerns a single datum)
  • Assuming this parameterized model with parameters theta, how likely is this data point?
  • If the probability of the observed data point x is high, this means the parameters theta are more likely (good fit).
  • We want to compute the likelihood of parameters theta for all data points X, so we need to compute the joint probability with each $p_{theta}(x)$:

$$ L(\theta|x) = \prod_{x \in X} p_{\theta}(x)$$

Notice that we use capital L (stylized) for the likelihood.

Log likelihood

However, working with this product is computationally difficult, because ... the values get very small? So usually a trick is applied: take log of both sides of this equation to instead compute the log-likelihood (indicated with lower case stylized l).

$$l(\theta|x) = log \prod_{x \in X} p_{\theta}(x)$$

$$ l(\theta|x) = \sum_{x \in X} log(p_{\theta}(x))$$

Notice that the right hand side uses the rule that the log over a product is the same as the sum over the log, i.e. uses the logarithm product rule.

This solves our problem! We are no longer multiplying small probabilities, but summing probabilities not quite that small.

Maximum likelihood estimation

What we want to do is find the best parametric model given the observations, which means that (given $L(theta|x) = p_{theta}(x)$) we want to choose the parameters such that the data is most likely under this parametric model.

This is, by definition, the task of finding the maximum likelihood:

$$ \hat{\theta} = argmax_{\theta}L(\theta|X)$$

where $\hat{\theta}$ is known as the maximum likelihood estimate (MLE).

Consolidated here MLE_maximum_likelihood_estimate.md.

Example: Wrodl style dataset

  • 50 observations, each corresponding to a style chosen from the sample space.
  • 5 features with 3-8 values per feature
  • 5 dimensional sample space of 4032 points (3x8x4x6x7)
    • So each observation is described with 5 features that each can take on various values.

An observation is a face with various style features.

Goal: come up with a model that generates new styles.

  1. Multinomial
  2. Multinomial with additive smoothing
  3. Naive Bayes

Multinomial

We can model this with $p_{model}$ being a multinomial distribution (extension of binomial, now with multiple possible discrete outcomes per trial).

Defined such that $p_{model}(x=x_i)=\hat{\theta_i}$ if $i < |x|$, and $p_{model}(x=x_i)= 1 - \sum \hat{\theta_i}$ otherwise.

Where $|x|$ is the cardinality of the sample space.

Where the MLE is given as $\theta_i = \frac{n_i}{N}$ w (simple frequency calculation) where N is total observations . That is, the model with maximum likelihood is the model that assign to each datapoint its true frequency in the sample space.

In other words, the probability of a particular observation being $x_i$ is the probability of that observation in the sample space (simple frequency calculation), which we define as the ith parameter $\hat{\theta}_i$. In other words, for each data point except the last one you estimate a parameter that indicates its probability. We do not have to estimate the last one because we know what it has to be in order to result in a probability distribution, namely 1 minus the probability mass of all other parameters combined.

Problems:

  1. So in this model we estimate a parameter for each data point in the entire sample space. This of course gets out of hand quickly!
  2. Every unobserved point in the sample space has an zero probability! (Remember: we had 50 observations but the sample space is 4032!)

Multinomial with additive smoothing

Addition:

$\hat{\theta_i}=\frac{n_i +1}{N+|X|}$

So we increment each frequency with a pseudo count. To ensure the probabilities still add up to 1 (i.e. they define a probability distribution), we need to add |X| to the denominator. That is, each point in the sample space will receive a pseudo count, so the total number of elements is increased with |X|.

This way, possibilities that are not in the observations still receive a probability estimate. This solves the second problem stated before.

But we introduce a new problem:

  1. Each unobserved point in the sample space gets a very low probability, but now the majority has the same constant probability! (1/(N+|X)).

This is still ridiculous for any realistic model. Why?

Image for example that the sample space is a space of all possible images. Then we have that a generated image that satisfies our requirements for a successfully generated image (see GAN lecture later), i.e. it looks a lot like an observation, will be sampled with the same probability as a completely random image that is completely unrealistic. After all, neither were observed in the training set.

Naive Bayes

  • Makes the well-known independence assumption (or: the naive Bayes assumption)
    • $p(x_i|x_j) = p(x_i)$
    • so p(x) is the joint probability of all features under the assumption of independence.
    • Note that x_i refers to a feature of observation x.
  • We now not count with whole observations, but the features of those observations
  • So now we do not parameterize individual observations, but individual features.
  • We now express $p(x_{ij})$, i.e. the probability that feature x_i takes on value j.

Now we have:

$$MLE: \hat{\theta{ij}} = \frac{n_{ij}}{N}$$

Where $n_{ij}$ means: the amount that feature i takes on value j.

  • Instead of 4032 (3x8x4x6x7) parameters, we now have to count the occurrences of each value, so 3+8+4+6+7=28 parameters.

New problem:

  • Now examples that are observed may be lower than unobserved examples for example if the observed example contains a rare feature value.
  • If you now describe the observations in terms of pixels rather than features, the independence assumptions of naive Bayes fails horribly!
    • 256 values per feature, 1024 features (high resolution), 256^1024 sample space size.
    • But of course, this also results in shitty images because pixels are correlated in images. E.g. if one pixel is yellowish, the color of the next pixel is most likely very close

Generative modeling challenges

  • Features have strong conditional dependences on each other, how do you deal with that?
  • How do you find the small proportion of generated observations in a very high-dimensional sample place that can be used to produce satisfying results?

The key to solving these problems is to use representation learning (?) and deep learning. We need models that infer relevant structure from data, rather than being told what features to use. What features from this high-dimensional sample space are relevant/important?

Generative Deep Learning

We discuss:

  • Applications related to image transformations: colorization, face hallucination, style transfer, super-resolution
  • Architectures: encoder-decoder, VGG-16/19
  • Layers: Batch normalization, deconvolution, residual
  • Losses: Feature, pixel, total variation
  • Metrics: PSNR, r, SSIM
  • Optimizers: AdaGrad, Adam, RMSProp, vanilla stochastic gradient descent

Convolutional Sketch Inversion (CSI) paper

Paper: Güçlütürk, Y., Güçlü, U., van Lier, R., & van Gerven, M. (2016). Convolutional sketch inversion. In European Conference on Computer Vision Workshops.

Topic: Face hallucination.

The term face hallucination is inaccurate because there is in fact an external stimulus. You present a sketch of a person, and the network tries to convert it into a realistic sketch.

We go through the steps of a paper to exemplify various deep learning elements.

We have a dataset with pictures containing faces. Automatically align, crop and resize them. For each of these, automatically generate new sketches in three styles: line sketch, grayscale sketch, color sketch.

The dataset is thus semi-simulated, i.e. the targets are true images but half of each training examples is generated.

Tip: Pillow, sckikit-image, Dlib, OpenCV

Architecture: 16 layer convolution encoder-decoder.

Uses batch normalization, deep residual learning, perceptual losses, stochastic optimization.

Architecture

Learn how to read architecture summaries, e.g. 3x3, conv, 64 \2. Meaning:

  • 64 out channels (not in!)
  • 2D Kernel size is 3 (i.e. kernel is 3x3)
  • Stride is 2 (\2)
  • I do not see where padding is indicated. With 3x3 kernel a padding of 1 retains the same amount of channels

See 202005291223-CNN_convolutional_neural_network.md

Batch normalization

See batch normalization .

Normalize the inputs of layers per channel, so normalize over the batch dimension of the inputs.

Helps optimization with:

  • Regularization
    • Q: Why does batch normalization aid regularization?
  • Speed
    • Q: Why does batch normalization aid training speed? Aids optimization.
    • Q: Why does batch normalization aid optimization?

Why do we do batch norm, instead of computing the relevant populations statistics, i.e. the mean over all neurons. Per iterations, you would need to sum over all inputs per each layer.

For each iteration, you would need to compute the mean and variance of all inputs (may be millions for large datasets) for each single layer. As soon as you update some weights, the population statistics already change and you need to redo it.

The main insight here is that batch normalization does not straightforwardly eliminate internal covariate shift, but improves learning due to creating a smoother error landscape.

Deconvolution layer

Convolution layers reduce the spatial resolution and increase the amount of channels.

"Deconvolution" layers increase the spatial resolution and decrease the amount of channels. This is called deconvolution because it sort of reverses the results of the convolution operation, but there is no actual deconvolution happening.

Other names:

  • Transposed convolution
  • (Fractionally) strided convolutions

Why strided convolution? A regular strided convolution, let's say of 2, downsamples the input by basically skipping every second convolution result. A deconvolution layer with stride 2 instead upsamples by adding a n-1 zeros before each second pixel, before doing the convolution.

This naive approach causes a checkerboard artefact. See this great blog

Resize convolution

Solution: resize convolution

Instead of increasing the spatial resolution by adding zeros, you do a linear interpolation (average of surrounding pixels) or nearest neighbour interpolation (replicate nearest/most similar? one) to upsample.

Q: Why is deconvolution not a very accurate term? What would be a better term for this operation?

Residual layer or skip connections

Make training easier by preventing vanishing gradients.

It makes it easier to fit the identity function.

A NN layer can be written as:

$y = f(x * w)$

I.e. the output a layer is the input convolved with weights, passed through some non-linear function.

A residual layers adds the input to the output (either before or after the non-linearity). This can be done after each layer, but in principle this is used to skip layers (so the input x that is added is the input from a few layers back). This construction is called a residual block.

$y = f(x * w + x)$ or $y = f(x * w) + x$.

Umut said that both versions are used. To me the second is more intuitive, but Umut uses the first formulation.

What does this do? By making the identity function easy to fit, we ensure that if a given block does not learn anything useful (too bad) it at least can still learn the identity function so that this does not hurt optimization.

  • Premise: f(xw)=0 is easy to fit, but f(xw)=x (identity function) is hard to fit
  • Assume that for some layer, the best thing to achieve is just pass the input through the non-linearity, so that it doesn't hurt the network. So y = ReLU(x * w ) = x, i.e. fit the identity transformation.
  • This requires the network to fit y = ReLU(x * w ) = x, which we just said was hard to do.
  • Now consider y = ReLU(x * w) + x. This must fit ReLU(x * w) = 0, which we just said was easy!

This solves vanishing gradients, because during back propagation we keep multiplying them with small numbers the more we go towards the shallow end of the network. But now gradients can be passed through the simple additive connection. The vanishing gradient problem specifically occurs due to multiplication.

Loss functions

Paper uses combination of three loss components

Pixel loss

Simplest measure for reconstruction: mean squared error (Euclidean distance) between input and target pixels.

To main downsides:

  • Susceptible to perceptually irrelevant errors
    • A very good estimate that is just off by a few pixel adds up to a very high loss
    • Whereas something that doesn't quite look the same can have a relatively low pixel loss
  • Results in blurry (smooth) target pixels.
    • Imagine half of the observations are red pixels, and the other half blue, then good predictions are either red or blue
    • But when minimizing pixel loss over the whole training set, we pick the pixel values that are equaly close to red as to blue, so we always predict violet pixels.

Feature loss / perceptual loss

This feature loss component addresses this problem

Instead of comparing pixels, we directly try to compare to some (higher-level) features of the output.

The paper uses a pretrained VGG-16 net to extract those features, which uses 3x3 resolutions and is trained on imagenet. This is the common approach, because apparently the learned features of VGG-16 and VGG-19 are very generalizable and representative of natural images as a whole.

We do this because features are more invariant to perceptually irrelevant errors compared to pixel loss.

Procedure:

  • Importing pretrained model, passing prior to estimate MSE
  • passing both target and output to model, extract feature for both from intermediate layer (e.g. 5 or 6)
  • Do MSE on these features.

Total variation loss

TODO we stopped discussing here. There are still a few slides left.

For now I prioritize the GAN lecture.

Adam optimizer

T.B.C.

Lecture 12: Variational Autoencoders

This slide is more math heavy. Make sure to review lecture 10 and the first half of this lecture carefully. Do a refresher on the chain rule etc.

Variational inference and autoencoders build forth on expectation maximization.

General idea: Encode into latent dimension -> Sample from latent dimension -> Have decoder reconstruct input.

You do put some constraints on the latents. For sampling to work well, distribution of latents need to fit some distribution, most often a Gaussian.

So we end up with a stochastic version of an autoencoder.

We want to estimate a parametric model of a data distribution with maximum likelihood.

We do not have access to the data distribution; i.e. it is something we observe as resulting from an underlying data generating process. I.e. "data" are the observations that are generated from the underlying data distribution. So we want to estimate it through sampling.

The parametric model is in this case a probabilistic one.

We want to find the parameters that optimize the likelihood of the data given the parametric model.

Terminology

  • $x \in D; where x_i refers to i-th data point$
  • $P_D(x)$: real data distribution generating the data points
  • Parameters $theta$
  • Parametric model: $p_{\theta}(x)$

Likelihood $l$: probability that the parametric model assigns to the observed data.

Maximum likelihood:

$$\hat{\theta}{MLE}=argmax{\theta} l(\theta)$$

We're trying to find the parameters such that our parameters assigns the highest probability to our observations.

$$argmax_{\theta} \sum_{i} log p_{\theta}(x_i) | x \sim p_{D}(x,z)$$

What crucial is that data points $x_i$ are sampled independently. This allows us to straightforwardly multiply the probabilities of data points to get to the joint probability distribution.

REVIEW: but we are summing here, even thought Umut mentions factorizing. I'm confused.

Maximum likelihood with latent variables

Now we introduce a distinction w.r.t. lecture 10. We now also sample a latent vector z from a joint data distribution.

$$argmax_{\theta} \sum_{i} log p_{\theta}(x_i,z_i) | x_i,z_i \sim p_{D}(x,z)$$

Using the chain rule of probability we can rewrite the join distribution as:

$$argmax_{\theta} \sum_{i} log p_{\theta}(x_i|z_i)p_{\theta}(z_i)$$

We could turn x and z around, but this notation makes it explicit that observed data x depends on latent z.

I.e. we make the observed data "two dimensional" and also adjust the parametric model to estimate a joint probability distribution for the observations.

Remember: we just use the log-likelihood because it's easier to compute with.

Split up the data in x and z, where z is a some factor underlying and influencing x; i.e. it could be a causal factor, or a some latent feature.

The problem here is that often we do not have access to z. Z may simply be missing data, but z may also be a latent variable that is not directly observable. (We may know perfectly fine what z is, but z is not in the dataset for each datapoint).

How do we then model the joint distribution?

Maximum likelihood with latent variables

We still want to model both x and z, but we only have access to x. Again, we maximize the maximum likelihood estimate.

Normally we would set the gradient of this objective function to 0 and solve for theta. (Assuming there is a maximum, this maximum will have a gradient of 0). But in this case we obviously can't, because we do not observe z.

How can we get rid of z's here in this formula, so we can still solve for the model with the maximum likelihood?

Idea: Marginalize over z i.e. use all values of z for one particular value of x. We end up with the marginal probability of observing datapoint x, regardless of individual $z_i$'s.

So then we compute:

$$argmax_{\theta} \sum_{i} log \sum_{z} p_{\theta}(x_i,z)$$

Which we can factorize again to:

$$argmax_{\theta} \sum_{i} log \sum_{z} p_{\theta}(x_i|z)p_{theta}(z)$$

Taking a derivative over summation is simple because this is the same as summing over the derivatives over the summed parts (linear operation), so we do not need the chain rule for derivation. But we have introduced a logarithm over a sum, so the derivative becomes very hard. This derivate will be very complicated to solve numerically, and it's will probably be a multimodal function, which makes solving for 0 problematic as well. You may still end up in a local maximum.

We however not have a logarithm product in the final formula (review slides).

Expectation Maximization algorithm

So we are not analytically solving for theta to find the maximum likelihood estimate (MLE).

We can use expectation maximization, because this approach does not care about the fact that the latents are unobserved.

EM is a family of algorithms, we discuss a vanilla approach to trying to find the

EM takes an iterative approach: estimate $\theta$ by iteratively minimizing ELBO.

The general idea is fairly simple: our main problem was that we do not have access to latent variables, but we can nevertheless try to estimate the values of latent variables. If those estimates get better over time, we can fill in those values and then the argmax operation becomes easier.

N.B. we now entirely avoid the marginalization approach from before, which created the very difficult derivation.

This is the iterative approach for estimating an individual $z_i$. We start by initializing theta's randomly or according to some scheme.

We use the asterix to indicate $z_i$ is an estimate.

  1. E-step Predict/estimate latent $z_i*$, given $x_i$ and current model parameters theta. (E for expectation)
    • E.g. imagine you observe reaction times and your latent is age.
    • If you observe a very slow reaction time, you'd expect an older person
    • If you observe a very fast time, you'd expect a young person
  2. M-step Estimate/update new theta given observed data $x_i$ and assuming our current estimate $z_i*$. (M for maximization)
  3. Repeat until convergence.

This approach is guaranteed to improve the model by minimizing ELBO (evidence lower bound), but may be incredibly small. But it may converge to a local minimum. We did not discuss the proof for this statement.

You can also think of k-means clustering as a way of doing EM. You can also update individiual z_i's using k-means clustering, where cluster indices are z's.

In practice, we often do not work on the level of individual z_i's, but guess distributions over latent variables z.

So we do not estimate $z_i$ directly, but instead its distribution given our observations, $p(z|x_i;\hat{\theta}^{t-1})$

In the E step, we thus basically use Bayes' rule to update distributions over z.

In the M-step, we maximize the Evidence Lower Bound (ELBO), which is defined as:

$$\sum_{i}E_{z \approx p(z|x_i;\hat{\theta}^{t-1})} log p(x_i; z; \theta)$$

Variational inference

The guarantee that guarantees convergence is due to Jensen's equality * The likelihood found with ELBO will be always less or equal to original log likelihood we were approximating. * It's a lower bound, after all.

Regular variational inference is still quite hard

If our model is very complex, we face another issue in Estimation Maximization, namely that normalization in the E-step can be intractable (recall, Bayes rule of distributions). It may not have a close form solution and also not be estimated numerically.

This is where variational inference comes in. Instead of exactly computing the posterior that is required in the expectation step of EM (when considering distributions), we now approximate it.

Q in slides refers to posterior of $z$ given observations x.

Variational inference is a way of estimating the posterior of z (latent variables), using a family of factorizable distributions, e.g. a Gaussian.

Umuts story was a bit confused here.

What is "mean-field approximation"?

Umut makes an analogy with the naive Bayes assumption. If the analogy with naive Bayes is correct, then it concerns the conditional independence between observations given the latents, i.e. given the latent distribution, x_i|z is independent of the other observations.

This assumption of independence is made to simplify the approximation, but this may be too big of a constraint for some applications, and derivations may still be very hard.

For example, assume we have some latent distribution to generate images. Given this latent distribution, the observations i.e. pixels are clearly not independent in practice. Pixels are highly correlated.

The autoencoder solution to variational inference

"Auto-encoding variational Bayes" can be used to parameterize q(z|x) with a neural network and estimate its parameters using back propagation.

"Auto-encoding variational Bayes" is nowadays known as a "Variational Autoencoder". We are essentially trying to approximate a posterior distribution p(z|x_i;theta) over our latent space, for which we used Bayes rule on distribution during EM (the E-step, specifically).

N.B. Umut uses q for the posterior.

E-step in EM:

$$p(z|x_i;\hat{\theta}^{t-1}) = \frac{ \int p(x_i|z;\hat{\theta}^{t-1}) p(z;\hat{\theta}^{t-1}) }{ \int p(x_i|z;\hat{\theta}^{t-1}) p(z;\hat{\theta}^{t-1}) dz}$$

The trick is to estimate the ELBO by using a neural network that parameterizes this posterior distribution; the parameter estimation can now be done using back propagation.

This is easier and a more general solution than solving a difficult derivative and all the other problems we encountered with the previous approaches.

We avoid:

  • Marginalization -> difficult derivative to find argmax theta due to product of logs and sums
  • EM -> difficult normalization in E-step

We can now just plug everything into the programming framework for differentiation that neural nets offer. So this can be seen as an extension to expectation maximization.

  1. Define prior distribution over latent variables $p_{theta}(z)$
    • Can be parametric, but often just fixed, e.g. a Guassian
  2. Encoder: Estimate latents p(z|x) by parameterizing the latent distribution and then finding the parameters of this distribution
    • E.g. when we let the latent distribution be a Guassian, the encoder will estimate its mean and variance, given the data distribution.
    • But we are ultimately interested in the likelihood of the data, so we add another step, just like in expectation maximization
  3. Decoder: Predict the parameters of yet another distribution, namely $p_{theta}(x|z)$.
    • We sample latent vector z from p(z|x), this is the input to the decoder
    • In case of images, predicts parameters of the distribution of individual pixels p(x|z)
    • If I understand this correctly, that's one distribution per pixel.
    • The latter could be formulated as a join probability distribution, that does not make an essential difference
    • From this distribution we can sample a reconstructed image.

We optimize the whole thing with back propagation.

It is assumed that no latents are shared between data points.

Then of course, the main issue is: what's our objective function? What are we maximizing? We discuss this case for the Guassian variational autoencoder.

12b: Gaussian variational autoencoders

q(z|x) is assumed to be a normal distribution (with mean and std as parameters).

So now we estimate the mean and standard deviation of the latent Gaussian distribution.

  1. We assume the prior over our latent variables to be a Gaussian, so $p_{\theta}(z)=N(0,1)$
  2. Encoder estimates mean and std of the Guassian distribution over latent variables, given the data.
    • We estimate one Gaussian per latent variable, so z does not have to be a scalar but can be a multi-dimensional. A Gaussian for sampling each dimension.
    • We assume all those Gaussians to be independent.
    • We parameterize the Gaussian's mean and std, that's the whole point.
  3. Decoder output distribution $p_{theta}(x|z)$ does not have to be Gaussian, it is also often a binomial distribution.
    • Notice that the decoder network is parameterized with theta
    • Notice that the decoder network is parameterized with phi

We are optimizing both theta and phi, they are simply the learning parameters of the two different sub networks, encoder (theta) and decoder (phi).

I could not pay attention anymore... REWATCH end of the lecture.

So what's our objective here?

Umut does not make this explicit, but it makes sense that the loss function will include at least one term that measures the reconstruction quality (information loss) between input and reconstruction. Additionally, there is a second term to regularize the latent space, namely the KB-divergence that actually functions as a regularizer.

For the encoder network, we want to minimize the difference between the prior p(z) (standard Gaussian) and the posterior distribution p(z|x), i.e. we want to find parameters (mean, std) such that, given the observations, the distribution over z still looks as close as possible like a standard Gaussian with mean 0 and std 1.

The Kullback-Leibner divergence is a measure of the difference between two probability distributions. It's a relative entropy measure, in other words, it measures how much information is lost with respect to a standard normal distribution, when using q to represent the data.

The KB-divergence functions as a regularizer to ensure the latent space remains meaningful and diverse.

From jaan.io:

If we didn’t include the regularizer, the encoder could learn to cheat and give each datapoint a representation in a different region of Euclidean space. This is bad, because then two images of the same number (say a 2 written by different people, 2_alice2 and and 2_bob could end up with very different representations z_alice, z_bob.

Q: Why are we not interested in the difference between the reconstructed data and the original data (which is the case in a vanilla autoencoder, if I'm not mistaken)? (I think I have the answer below)

If our decoder outputs a network, we want to minimize the negative ELBO (i.e. maximize the ELBO, like before). We recast it to a minimum because we'll combine this in a loss function that minimizes the KL-divergence.

KL-divergence and ELBO

From the lecture it was completely unclear how ELBO is derived. I found this great blog. This section contains my quick notes.

Desired: the variational posterior q(z|x) is supposed to approximate the true posterior p(z|x).

We can express this with the KL-divergence.

$$KL(q_l(z|x)||p(z|x)) = E_q[log q_l(z|x)] - E_q[log p(x,z)] + log p(x)$$

where $l$ indicates the parameter we need to minimize, so that the optimal approximation is:

$$q_l*(z|x) = argmin_l KL(q_l(z|x)||p(z|x))$$

But that in the formula for KL the evidence p(x) still appears, which requires us to marginalize over z! Aii.... too bad.

ELBO is defined as such:

$$ELBO(l) = E_q[log p(x,z)]-E_q[log q_l(z|x)]$$

REVIEW: I do not necessarily know how this definition of ELBO is reached.

Notice that this is very close to the definition of KL from above! The evidence in the KL definition can be rewritten as such:

$$log p(x) ELBO(l) + KL(q_l(z|x) || p(z|x))$$

We know that KL is $\leq 0$. As a result, minimizing KL (our original goal) is equivalent to maximizing ELBO. Check: p(x) staying the same, increasing ELBO should lower KL. (Is this reasoning solid?)

Conclusion: by maximizing ELBO, we can minimize KL, which means that we are better approximating the true posterior over latents p(z|x).

So now we can avoid computing KL-divergence between q(z|x) and p(z|x), and instead compute ELBO which is way easier!

Computing ELBO

So we had:

$$ELBO(l) = E_q[log p(x,z)]-E_q[log q_l(z|x)]$$

It is assumed that no latents are shared between data points, so the total ELBO is just the sum of individual ELBO's for data point $i$.

ELBO can be rewritten by expanding the log joint into prior and likelihood, then applying the product rule:

$$ELBO_i(l) = Eq_l(z|x_i)[log p(x,z)]-KL(q_l(z|x) || p(z))$$

Notice that we now compute the KL w.r.t. p(z)!

So whereas I was at first wondering why we are computing KL w.r.t. the prior distribution p(z), we now see that what we are actually trying to achieve is to let q(z|x) approximate p(z|x) by doing this!

When we parameterize this using an autoencoder neural network with $\theta$ and $\phi$ we get:

$$ELBO_i(\theta,\phi) = Eq_{\theta}(z|x_i)[log p_{\theta}(x,z)]-KL(q_{\theta}(z|x_i) || p(z))$$

And this, in turn, corresponds to the negative of the loss function for variational autoencoders, i.e. the negative log likelihood.

NLL is defined as:

$$l(\theta,\phi)= - E_{z \approx q \theta(z|x_i)}[log p_{\phi}(x_i,z)]+KL(q_{\theta}(z|x_i) || p(z))$$

So then we can derive that

$$ELBO_i(\theta,\phi) = - l_i(\theta,\phi)$$

So that by minimizing the NLL loss function we are maximizing ELBO.

Still confusing to me, what does minimizing NLL mean? Are lower values better in this loss function?

So I finally get how ELBO and NLL are related.

Similar notes from slides about loss function

So we want to minimize

$$D_{KL}log q_{\phi}(z|x)||p_{\theta}(z) - ELBO$$

Backpropagation is basically the argmax operation from before (now argmin; i.e. we look for the parameters for which the appropriate loss function is minimized):

$$argmin_{theta}D_{KL}log q_{\phi}(z|x)||p_{\theta}(z) - ELBO$$

We care more about p(z|x) and that we can sample latents, than in having a probabilistic $p_{\theta}(x|z)$ that we can sample from. It can also be a simple function f(z)=x that just maps latents directly onto pixels. Actually, since a neural network already is such a function, you would often just let the neural net output actual pixel values!

In that case, we also do not care about minimizing the negative ELBO (that is maximizing the expectation) but would just take for example the Euclidean distance between the reconstructed image and the input image.

In case we output pixel values, we replace ELBO with a reconstruction loss to stimulate the network to reconstruct the input, i.e. the expected negative log-likelihood of the i-th datapoint.

$$argmin_{theta}D_{KL}log q_{\phi}(z|x)||p_{\theta}(z) - E_{z \approx q_{theta}(z|x_i)}[ log p_\phi(x_i|z)]$$

So the expectation is taken w.r.t. the encoder's distribution q(z|x_i).

I think we take the NLL because the original image can be seen to have 255 labels i.e. possible pixel values, right? So you can check how close the output pixels are to the input pixels.

NLL is multiclass cross-entropy so it is a way of measuring how much information is lost from input image to its reconstruction.

Note that the loss function depends on a single data point, so to get the loss we simple sum over the all individual losses to get the total loss.

Bringing it together: deriving loss function for Gaussian variational autoencoder

Again, we minimize:

$$D_{KL}log q_{\phi}(z|x)||p_{\theta}(z) - ELBO$$

We know that ELBO equals - NLL.

We can derive a simpler formulation for the KL-divergence w.r.t. a standard prior because we know it's mean is 0 and std = 1.

We have

$$D_{KL}(N_0||N_1) = 1/2 { \frac{\sigma_0}{\sigma_1}^2 + \frac{\mu_1-\mu_o}{\sigma_1^2}^2 - 1 + 2 ln\frac{\sigma_1}{\sigma_0}}$$

We know that $\mu_1 = 0, \sigma_1=1$ which gives:

$$D_{KL}(N_0||N_1) = 1/2 { \sigma_1^2 (-\mu_0)^2 - 1 + 2 ln\frac{\sigma_1}{\sigma_0}}$$

With $\sigma_0^2 = e^{ln \sigma_0^2}$ we can express the variance in terms of the log variance (which we used in the practicals).

And we have $2 ln \sigma_0^-1 = ln s_0^{-2} = - ln s_0^2$, so we also express this in the same log variance.

Bringing it together:

$$ 1/2 { e^{ln \sigma_0^2} + \mu_0^2 -1 -ln \sigma_0^2 }$$

So the loss is this term - ELBO = -(-NLL) = + NLL.

(Re)Parametrization trick

Yes another problem, because why not?!

In the middle of our network we use a sampling operation to sample a latent vector z from the latent distribution that we are approximating.

This poses a challenge for backpropagation, because how exactly can be differentiate a sampling operation from a normal?

Solution: make the parameters phi independent from the sampling operation by defining:

$e \approx N(0,1)$ and then have $z=\mu_{\phi}(x) + e \sigma_{\phi}(x)$.

Now the sampling operation does not involve any learnable parameters used in backpropagation. We sample from a fixed standard normal distribution, and then use this to construct a sample in the correct range that only involves addition and muliplication, which are differentiable.

Very important! How to use things that are not typically differentiable.

For exam it is not necessary to be able to reproduce the equations and derivations, but rather to reason about them.

For exam: do not reproduce the equations and derivations, but reason about

Lecture 13: Generative Adversial Networks

Overview of what we did before:

  • Model probability densities by maximizing lower bound likelihood (tractable case)
  • We do not always care about getting the explicitly modeling (complex) densities (e.g. complex densisities like those of images). Sometimes we only care about sampling from them.
  • In case of complex densities, we cannot straightforwardly sample from them without access to an explicit density function.
  • For simpler distributions like Gaussians, we can sample easily.

But GANs do not actually sample from complex distributions! They sample simple distributions and then map these onto more complex densities using a game-theoretic approach.

Basic idea (we assume use of GAN for images for now; but GAN is not limited to images, although the process is less straightforward with discrete distributions like in text):

  1. Two models (generator, discriminator) trained using an adversial process
  2. Generator is the "artist" that tries to create realistisc images, the discriminator is the "art critic" that learns to tell reals from fakes.

Training stops when the generator can produce images that always fool the discriminator.

At an Nash equilibrium, the probability of discriminating the image correctly should be 50%.

Q: do you pretrain the discriminator network (for classification)?

A: in general no, because the discriminator does not care about class labels but only about the binary yes no decision. But in general you don't do this because the task of the discriminator is already easier. The discriminator easily overpowers the generator. Some GAN discriminators classify, in addition to the real/fake decision, whether the created object, let's say an image of a 1, is actually a 1. In this case, pretraining on classifying e.g. digits in this case, may be justified.

Notice in the following that the loss functions are defined in an adversial manner.

Q: What are differences between GANs and variational autoencoders.

  • GANs do not explicitly learn and sample from a latent distribution. They rather sample from a very simple distribution and learn to transform this sample into an image
  • Variational autoencoders are not adversial
  • Generators do not strictly speaking try to reproduce input (only the discriminator has real input)

Generator

TODO finish notes from paper

  • Draw a parameter vector z (latent variable) from some distribution, e.g. a Gaussian.
    • Some call this "noise" but Umut does not prefer this term as this parameter is not unwanted.
  • Generator applies a function to transform this latent vector into an image x' = G(z)
  • Function G is learnable and is most often a deep neural network.
    • N.B. The original GAN paper from Ian Goodfellow used dense layers only.
  • Goal is to make the discriminator classify x' as real data.
    • I.e. we want D(G(z)) ~ 1 i.e. assign the outcome of G(z) a high probability of being real, if D(x) outputs probabilities.

Loss function:

So D(G(z)) is the probability of the generator output being "real" according to the discriminator.

Another way of phrasing this is that we want the discriminator to do absolutely terrible, i.e. we are maximizing the classification loss of the discriminator.

And this loss should be highest when we the ground truth is that the image is fake, t=0, whereas the discriminator says it's real (1).

We can express this with the binary cross entropy loss (i.e. a classification loss):

$$-\sum_{i=1}^{#C=2} t_i log(D(G(z)))$$

Because we have a binary problem, we have $t_2=1-t_1$. This means we can write out the sum from above as such:

$$-t_i log(D(G(z))) - (1-t_i)log(1-D(G(z)))$$

If $t_1 = 1$ (ground truth: image is real), then we have $-log(D(G(z)))$.

If $t_1 = 0$ (ground truth: image is false), then we have $-log(1-D(G(z)))$.

We just said that in case of the generator, we care about maximizing the loss for the discriminator in case the image is fake (i.e. the discrimator believes it's real rather than generated).

So the for the generator we want:

$$max_G{-log(1-D(G(z)))}$$

N.B. in the lecture Umut said that we have label 1 for fake images, labels of 0 for real images! That has to be wrong, right?

Below from the lecture:

  • Given Discriminator D, maximize cross entropy loss when y=0 (REVIEW)
    • Binary cross entropy loss, pass label of 0 for real images, label of 1 for fake images.

Discriminator

TODO finish notes from paper

  • Typically outputs a probability of the output being real. Outputs a scalar prediction over which we put a sigmoid to retrieve predicted probabilities.
  • Assume label y=1 for real data, y=0 for fake data.
    • This is the opposite of what Umut just said for the generator loss.
  • Discriminator tries to minimize the cross entropy loss, so the opposite of the generator.

The discriminator needs to do well both for real and fake images, so we include the whole binary cross entropy loss.

$$min_D{-y log(D(G(z))) - (1-y)log(1-D(G(z)))}$$

Training

Okay, so generator and discriminator will start playing against each other. What happens if the generator does well?

Then $D(G(z)) \approx 1$.

If we fill this in the discriminator loss formula, we see that the loss values become very small. Assume $D(G(z)) = 1$. Then ...

$$min_D{-y log(D(G(z))) - (1-y)log(1-D(G(z)))}$$

becomes ...

$$min_D{- (1-y)log(0))}$$

  • Updating is done sequentially in turn. Both networks have their own optimizer.
  • They play a min-max game

Generator:

  • If the generator does a perfect job then D(x')=1 leading to a loss of 0, which results in very small gradients for the discriminator to use?
    • How does the discriminator use gradients from generator?

Discriminator:

  • Target of generators are 1s; the opposite for the discriminator
  • But additionally, we sample a batch of real images from a training set, but here the predictions should obviously be 1.
    • So for each batch you have an equal amount of generated and real images.
    • This avoids a biased networks; ensures class balance.
    • Try to explain why. I guess the real networks are to keep the ground truth in the discriminator network.
  • You weigh the loss on generated images and real images
  • So in a training iteration you call the discriminator twice, but you only update after seeing both real and fake images.

Q: Why do we still give real images to the discriminator?

It needs a ground truth to learn what images from an empirical distribution look like. To not introduce a bias, we give an equal amount of fakes and reals.

Q: When training the generator, why do you need to freeze the discriminator?

Deep Convolutional GANs (DCGANS)

See GAN zoo.

GAN zoo

DCGAN is a very robust architecture, so is still today a good baseline to start tacking any complex problem.

Architecture of original DCGAN paper.

  • Take n-size latent vector inputs, let's say 100 z
  • Deconvolution with 5x5 filter with fractional stride of 2 (we think) -> 1024 x 4 x 4
  • Deconvolution -> 512 x 8 x 8
  • Deconvolution -> 256 x 16 x 16
  • Deconvolution -> 128 x 32 x 32
  • Deconvolution -> 3 x 64 x 64

So we have transformed a vector of latent variables, randomly sampled, into a three channel (RGB) image.

Interesting results:

  1. if you take two latent vector and interpolate between them, you get a gradual shift between two faces.

  2. Vector arithmetic

Vector space models (e.g. word2vec): input hot-encoding of a word -> project into distributed low-dimensional (relative) space, which has interesting properties. One interesting property is that you can do vector arithmetic with this. This property also shows with these latent vectors that we input into GANs. E.g. average vectors corresponding to laughing faces, to get a typical vector for laughing faces. If you do the same with a neutral face womens, you get something similar. Vector (laughing) + vector (neutral woman) -> vector (laughing woman).

Takeaways from the paper:

  • Do not use pooling layers. Replace with strided convolution in discriminator, and with fractional-strided convolutions in generator.
  • Use batchnorm in both
  • Remove dense layers for deeper architectures (because?)
  • Use ReLu in generator, but tanh for output. (I already saw so in autoencoders)
  • Use LeakyreLu in discriminator.
    • Why? Does not completely reduce negative value to zero, but makes loss very small.
    • There's no theoretic reason I think, this just seems to work better. Empirical observation that using this the loss does not oscillate as much.

Q: When do you do batch norm? Because if you do batchnorm after seen all fake examples and then again after all real examples, the discriminator inputs vary quite a lot, affecting the batchnorm.

Challenges

GANs are a major breakthrough for generative modeling. However, they are notoriously difficult to train.

This is mainly because they are very unstable.

  1. Oscillating loss: loss tends to show oscillating behavior rather than converging to long-term stability. They can get out of control over time, sometimes suddenly later in the training procedure (slide gives example where it goes wrong after 1400 iterations).
  2. Mode collapse: a generator finds a few samples that fool the discriminator very well for whatever reason. The generator will hone in on these and produce some arbitrary image all over again, defeating the purpose of the GAN. This is a severe problem.

Honing in means: the GAN will learn to map all latent vectors onto the same mode. Then the gradient of the loss will be close to 0, halting learning of the generator.

If we retrain the discriminator, the problem persists. It's hard for me to imagine why. Umut said the generator network is then already numb to its input, so it will not be sensitive to diverse input but likely find another "blind spot" mode.

The problem is thus not one particular mode. The problem is the overall tendency of generators to converge to specific modes.

Why does the discriminator have this particular "blind spot"?

Review book (what book lol) and slide.

  1. Uninformative loss: it's not necessarily the case that lower loss results in bette resulting images.

The loss can even increase steadily whereas the images do get better. This is because the loss is of course relative to the quality of the discriminator at a given point in time.

Imagine the quality of the discriminator stays the same. Then improvement in the generator would show in a decreasing loss plot. But in the meantime, the discriminator also improves, obviously.

This also means that you can't compare the training process across time points.

Lack of correlation between generator loss and image quality makes GAN training hard to monitor.

Some tools exist (inception loss?)

Solution: Wasserstrein GANs (WGANS)

WGANs replaces typical GAN loss with Wasserstein loss.

Makes loss more independent on concrete architecture.

If the loss is going down, then this actually means the generator is getting better. So the loss is informative.

With one constraint: Lipschitz constraint.

And this constraint can be enforced with weight clipping.

Wasserstein loss is the negative mean of yi * pi.

Foster 2019, p. 116:

To train the WGAN critic D, we calculate the loss when comparing predictions for a real images pi=D(xi) to the response yi=1 and predictions for generated images pi=D(G(zi)) to the response yi=-1. Therefore for the WGAN critic, minimizing the loss function can be written as follows:

Critic loss:

$$min_D - [ E_{x \approx p_X}[D(x)] - E_{z \approx p_Z}[D(G(z))] ]$$

Reasoning:

  • Critic tries to maximise the difference between predictions for real images and generated images

    • But real images score higher.
  • This formula is derived by taking respone y=1 for the real images and y=-1 for the generated images.

  • No more sigmoid and probabilities as output; prediction p can be any real number
    • Discriminator that does this is called a "critic": it gives a "score" to the generated art.
  • The difference is thus the disappearance of the logs. We use the probabilities directly instead.

Generator loss:

Use $y_i$ = 1 with $p_i=D(G(z_i))$

Gives $min_g - (E_{z \approx p_z}[D(G(z))]$

Lipschitz constraint

We said that the predictions can in principe be any real number. But there is a constraint.

The critic must be a 1-Lipschitz continuous function.

This imposes a limit on the rate at which the predictions of the critic can change between two images.

The absolute value of the gradient must be at most 1 everywhere.

This can be enforced by clipping the weights between a small range, e.g. [-0.01, 0.01] .

This of course has a clear downside, namely that by clipping weights you really minimize the network's ability to learn.