Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

Question Can you find a closed formula for the sum of the $p$-th powers of the first $n$ positive integers? That is, we need a closed formulat for the sequence: $$ h_n=a_p n^p+a_{p-1} n^{p-1}+\cdots+a_1 n+a_0, \quad(n \geq 0) $$ Solution The method is to use difference sequences. We already know the following: ...

Example sums of cubes Solve $h_n=h_{n-1}+n^3,(n \geq 1)$ and $h_0=0$. Solution Note that this is not a homegenous recurrence relation. Unrolling gives us: $$ \begin{align*} h_{n-1} &= (n-1)^3 + h_{n-2}\\ \implies h_n &= n^3 + (n-1)^3 + h_{n-2} \end{align*} $$ And we can keep doing this. Using this as the intuition, we guess the closed form: $$ h_n = n^3 + (n-1)^3 + \ldots + 2^3 + 1 $$ To formally prove this, we can use induction! Assume it holds for some $n \geq 1$, we want to show that $h_{n+1} = h_n + (n+1)^3 = 1 + 2^3 + \ldots + (n+1)^3$. ...

Generating Functions Generating functions can be regarded as algebraic objects whose formal manipulation allows us to count the number of possibilities for a problem by means of algebra. Definition Let $h_0, h_1, h_2, h_3, \ldots$ be an infinite sequence of numbers. Its generating function is defined to be the infinite series: $$ g(x) = h_0 + h_1x + h_2x^2 + \cdots + h_nx^n + \cdots $$ Example 1 The generating function of the infinite sequence $1, 1, 1, \ldots$ is: $$ g(x) = 1 + x + x^2 + x^3 + \cdots $$ for $|x| < 1$. This generating function $g(x)$ is the sum of a geometric series with value: $$ g(x) = \frac{1}{1-x} $$ Solution ...

World Coordinates and Image coordinates Pinhole Camera Model $$ x = K \left[ \begin{array}{ll} R & t \end{array} \right] x $$ x: Image Coordinates: $(u, v, 1)$ K: Intrinsic Matrix $(3 \times 3)$ R: Rotation $(3 \times 3)$ t: Translation $(3 \times 1)$ X: World Coordinates: $(X, Y, Z, 1)$ Basically, from the right side to the leftside, it is transforming a point (1) from the world coordinates to camera coordinates, and then project the point (2) from camera coordinates down to the image plane. ...

Pasting Images Method 1 — Cut and paste the images. Feathering Gives a smoother transition. But that’s all… Alpha composting Output = foreground $\times$ mask + background $\times$ (1 $-$ mask). We can also use alpha compositing together with the feathering — simply bluring the mask will give us a good feathering. This method is also good for multilayer processing, which allwos the compositing to be more complicated. Method 2 — Pyramid Blending At low frequencies, blend slowly At high frequencies, blend quickly Burt and Adelson 1983 Implementation: Build Laplacian pyramids for each image Build a Gaussian pyramid of region mask Blend each level of pyramid using region mask from the same level $$ L_{12}^i=L_1^i \cdot R^i+L_2^i \cdot\left(1-R^i\right) $$ ...

Texture Synthesis and Hole-Filling How do we cut something out of an image, and fill the hole naturally? Definition Texture depicts spacially repeating patterns. Texture Synthesis Create new samples of a given texture. Many applications: virtual environments, hole-filling, texturing surfaces. The challenge: Need to model the whole spectrum: from repeated to stochastic texture. One idea: Compute statistics of input texture Generate a new texture that keeps those same statistics. But it is hard to model those probabilities distributions. ...