Bresenham Circle Algorithm

• The radius of the circle is r
• The center of the circle is pixel (0, 1)
• The algorithm starts with pixel (0, r)
• It draws a circular arc in the second octant
• Coordinate x is incremented at every step
• If the value of the circle function becomes non-negative (pixel not inside the circle), y is decremented

Pre-filtering:

• extract high frequencies before sampling
• treat the pixel as a finite area
• compute the % contribution of each primitive in the pixel area

Post-filtering:

• extract high frequencies after sampling
• increase sampling frequency
• results are averaged down

Catmull’s Algorithm

Cohen – Sutherland (CS) Algorithm

• Perform a low-cost test which decides if a line segment is entirely inside or entirely outside the clipping window
• For each non-trivial line segment compute its intersection with one of the lines defined by the window boundary
• Recursively apply the algorithm to both resultant line segments

The low cost test can be done by assigning a 4-bit code to each of the nine sections around a pixel.

+------+------+------+
| 1001 | 1000 | 1010 |
+------+------+------+
| 0001 | 0000 | 0010 |
+------+------+------+
| 0101 | 0100 | 0110 |
+------+------+------+

Let the endpoints of a line segment be $c1$ and $c2$. Then we can do the following tests.

• If $c1 \vee c2 = 0000$
  • Then the line segment is entirely inside
• If $c1 \wedge c2 \neq 0000$
  • Then the line segment is entirely outside

Skala Algorithm

Liang - Barsky (LB) Algorithm

Yow this shit it based on the parametric equation of the line segment to be clipped. A line segment is defined by two points. Name the left-most point $p_1 (x_1, y_1)$ and the other point $p_2 (x_2, y_2)$ so that $x_1 \leq x_2$. We define $\Delta x = x_2 - x_1$ and $\Delta y = y_2 - y_1$.

The clipping window is a rectangle defined by $x_{\text{min}}$, $x_{\text{max}}$, $y_{\text{min}}$, $y_{\text{max}}$.

A point $q$ on the line segment defined by $p_1$ and $p_2$ is inside the clipping window if it satisfies the following:

$$ x_{\text{min}} \leq x_1 + t \Delta x \leq x_{\text{max}} \\ y_{\text{min}} \leq y_1 + t \Delta y \leq y_{\text{max}} $$

We can split these into four inequalities each corresponding to the relationship between the line segment and one of the four extended lines of the clipping window:

$$ -t \Delta x \leq x_1 - x_{\text{min}} \\ t \Delta x \leq x_{\text{max}} - x_1 \\ -t \Delta y \leq y_1 - y_{\text{min}} \\ t \Delta y \leq y_{\text{max}} - y_1 $$

These inequalities have the common form

$$ t p_i \leq q_i, \quad i : 1..4 $$

and we can summarize the properties of the line segment to be clipped based on the value of $p_i$:

$p_i = 0$

The line segment is parallel to the window edge $i$.

$p_i \neq 0$

The parametric value of the point of intersection of the line segment with the line defined by window edge $i$ is $\frac{q_i}{p_i}$.

$p_i < 0$

The directed line segment is incoming with respect to window edge $i$.

$p_i > 0$

The directed line segment is outgoing with respect to window edge $i$.

We then calculate $t_{\text{in}}$ and $t_{\text{out}}$ -- the line segment's entry to or origin point within the clipping window, and its exit from or end point within the clipping window.

$$ t_{\text{in}} = \text{max}( { \frac{q_i}{p_i} | p_i < 0, i : 1..4} \cup { 0 }) \\ t_{\text{out}} = \text{min}( { \frac{q_i}{p_i} | p_i > 0, i : 1..4} \cup { 1 }) $$

If $t_{\text{in}} \leq t_{\text{out}}$ we plug the values into the parametric line equation. Otherwise there is no intersection with the clipping window.

Sutherland - Hodgman (SH) Algorithm

Greiner - Hormann Algorithm

Translation

Translation defines movement by a certain distance in a certain direction. Translation of a point p by a vector $\vec{\textbf{d}}$ results in a new point $\textbf{p'} = \textbf{p} + \vec{\textbf{d}}$. All we do is add the vector to the point.

The translation transformation matrix is an instantiation of the general affine transformation, $\Phi(p) = A \cdot p + \vec{t}$ with $A = I$ and $\vec{t} = \vec{d}$.

The 3D homogenous translation matrix is:

$$ T(\vec{d}) = \begin{bmatrix} 1 & 0 & 0 & d_x \\ 0 & 1 & 0 & d_y \\ 0 & 0 & 1 & d_z \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

The $n$-dimensional translation matrix is derived by instantiating the general affine transformation with $A = I(n)$. ($I(n)$ is the $n$-dimensional identity matrix) If you need the homogenous variant, use $I(n+1)$.

The inverse translation of $T(\vec{d})$ is $T^{-1}(\vec{d}) = T(-\vec{d})$.

Scaling

We have $n$ scaling factors $s_{i}$, $i = 1, 2, 3, ..., n$ corresponding to the dimensionality of the space. If a scaling factor $s_{i} < 1$ the object's size is reduced in the respective dimension, whileas if $s_{i} > 1$ it is increased. $s_{i} = 1$ has no effect. $s_{i} = 0$ reduces the object's size in the respective dimension to zero. If $s_{i} = 0$, $\forall i$ the object disappears.

Mirroring about a major hyperplane can be done by using $s_{i} = -1$ as the factor for the hyperplane which isn't involved in the mirroring. I.e. to perform 2D mirroring about the $x$ axis, use $S(1, -1)$. To perform 3D mirroring about the $xy$-plane, use $S(1, 1, -1)$.

The 3D homogenous scaling matrix is: $$ S(s_x, s_y, s_z) = \begin{bmatrix} s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & s_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

For 2D homogenous scaling, remove the third row and third column. For 3D non-homogenous scaling, remove the fourth row and fourth column. For 2D non-homogenous scaling, remove the third and fourth rows and columns.

The inverse of the scaling matrix $S(s_x, s_y, s_z, ...)$ is $S^{-1}(s_x, s_y, s_z, ...) = S(\frac{1}{s_x}, \frac{1}{s_y}, \frac{1}{s_z}, ...)$

Rotation

The book defines positive rotation about an axis $a$ as one which is in the counterclockwise direction when looking from the positive part of $a$ towards the origin.

The three dimensional rotation transformation is defined as $R_{a}(\theta)$, where $a$ is the axis to rotate about and $\theta$ is the measure of how much you want to rotate it.

The 3D homogenous rotation matrices are:

$$ R_{x} (\theta) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & cos(\theta) & -sin(\theta) & 0 \\ 0 & sin(\theta) & cos(\theta) & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ R_{y} (\theta) = \begin{bmatrix} cos(\theta) & 0 & sin(\theta) & 0 \\ 0 & 1 & 0 & 0 \\ -sin(\theta) & 0 & cos(\theta) & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ R_{z} (\theta) = \begin{bmatrix} cos(\theta) & -sin(\theta) & 0 & 0 \\ sin(\theta) & cos(\theta) & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$

For the inverse 3D rotation transformation, use $-\theta$.

In 2 dimensions we rotate about a point. The standard rotation transformations specify rotation about the origin.

The 2D homogenous rotation matrix is:

$$ R(\theta) = \begin{bmatrix} cos(\theta) & -sin(\theta) & 0 \\ sin(\theta) & cos(\theta) & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

Shearing

Shearing increases $n-1$ of an $n$-dimensional object's coordinates by an amount equal to the $n$th coordinate times a shearing factor (specified seperately for each $n-1$ dimensions). That is, $SH_{xy} (a, b) \cdot p$ increases $p_x$ by $p_z * a$ and $p_y$ by $p_z * b$.

The 2D homogenous shearing matrices are:

$$ SH_x (a) = \begin{bmatrix} 1 & a & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

$$ SH_y (b) = \begin{bmatrix} 1 & 0 & 0 \\ b & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

The 3D homogenous shearing matrices are:

$$ SH_{xy} (a, b) = \begin{bmatrix} 1 & 0 & a & 0 \\ 0 & 1 & b & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ SH_{xz} (a, b) = \begin{bmatrix} 1 & a & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & b & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ SH_{yz} (a, b) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ a & 1 & 0 & 0 \\ b & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

The inverse of a shear is obtained by negating the shear factors.

Histogram Equalization

Compute the gray value histogram of the image (I):

$$h(k) = \sum \limits_{ij \in \Omega} \delta (I_{ij} - k)$$

Compute the cummulative proportion of pixels with a gray-value smaller than i:

$$c(k) = \frac{\sum \limits_{l=0}^k h(l)}{NM}$$

This nearly gives us the Intensity transfer function. Just multiply with the desired maximal output gray value: $$g_{ij} = T(f_{ij}) = Gc(f_{ij})$$

Neighborhood

A neighborhood, informally, consists of the pixels close to a given pixel. Formally: $\delta(i,j) = \left\{(k,l) | 0 \lt (k-i)^2 + (l-j)^2 \le c; k, i \in \mathbb{N} \right\}$.

Spatial Filtering

A spatial filter exists of a neighborhood, associated weights for each pixel in the neigborhood, and a predefined operation on the weighted pixels. When the weights sum to 1, the gray value is not changed.

+-----+-----+-----+
| _1_ | _1_ | _1_ |
|  9  |  9  |  9  |
+-----+-----+-----+
| _1_ | _1_ | _1_ |
|  9  |  9  |  9  |
+-----+-----+-----+
| _1_ | _1_ | _1_ |
|  9  |  9  |  9  |
+-----+-----+-----+

Convolution

Convolution is written as $(f*g)(t)$ meaning the function $f$ convolutes $g$ with variable $x$. Convolution can be understood as one wave, or function, travelling through another as shown in the illustration below. The resulting value (the convolution of f through g) is the area covered by both graphs. Now look at the image and notice that

• The convolution $(f*g)(t)$ is zero when the waves are not overlapping.
• The convolution $(f*g)(t)$ grows when f is moving through g, before reaching the edge of g.
• The convolution $(f*g)(t)$ is at is maximum when the intersection of the waves is biggest.
• The convolution $(f*g)(t)$ shrinks when the front of f has reached the end of g and has begun "leaving" it.

Remember that we are looking for the area, unlike when colliding water waves where two large wave tops will give us a twice the height.

Sharpening

We use Laplace for this. TODO: write about this.

Frequency domain

Filtering can be done in the frequency domain. We use the discrete fourier transform to enable this. The Discrete Fourier-Transform (DFT) is defined as:

$$ F(u) = \sum\limits_{i=1}^{M-1} f(x) e^{-i 2 \pi \frac{ux}{M}}, f(x): x \in [0, M-1] $$

The DFT is reversible, and the Inverse DFT (IDFT) looks like this:

$$ F(x) = \frac{1}{M} \sum\limits_{i=1}^{M-1} F(u) e^{+i 2 \pi \frac{ux}{M}} $$

Working on single  pixels
Neighbourhoods of pixels
Filters

Dilation

Dilation adds pixels to an image. This is done by applying the appropriate rule to the pixels of the neighbourhood and assign a value to the corresponding pixel in the output image. The picture below is illustrates the dilution of a binary image. In the figure, the morphological dilation function sets the value of the output pixel to 1 because 1 is the highest value in the neighbourhood defined by the structuring element. Pixels beyond the image border are assigned the minimum value afforded by the data type.

The following figure illustrates dilation for a grayscale image. Note how the function looks at all the pixels in the neighborhood and uses the highest value of all as the corresponding pixel in the output image.

The notation for dilation is $f \oplus s$, where $f$ is the image and $s$ is the structuring element

Erosion

Erosion removes pixels from an image. This is done the same way as can be seen in the binary dilation figure seen above, except the function looks for 0 instead of 1. Pixels beyond the image border are assigned the maximum value afforded by the data type.

The notation for erosion is $f \ominus s$, where $f$ is the image and $s$ is the structuring element.

The following image shows an eroded image compared to the original image. Notice how there are less white pixels (1s) in the eroded picture.

Opening

Closing