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: ...

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) $$ Collapse the pyramid to get the final blended image Method 3: Poisson Blending A good blend should preserve gradient of source region withough changing the background ...

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. ...

How do you view the world Cones: cone-shaped, less sensitive, operate in high light, color vision Rods: rod-shaped, highly sensitive, operate at night, gray-scale vision, slower to respond Observation In a clear night, there are more stars off-center. This is because you have more rods in the middle, while more cones elsewhere. How to express colors? Basically, the most intuitive expression is the RGB color space. But it is not a linear color space. We perfer expressing using CIE-XYZ color space, which makes the calculation much easier. ...

Definition A multinomial coefficient is: $$ \binom{n}{n_1 n_2 \cdots n_t} =\frac{n !}{n_{1} ! n_{2} ! \cdots n_{t} !} $$Here, $n_1, n_2, \ldots, n_t$ are nonnegative integers with $$ n_1+n_2+\cdots+n_t=n $$Pascal’s theorem for multinomial coefficients Pascal’s theorem for Let $n, k \in \mathbb{N}$ and $(n)_{i=1}^k$ be natural numbers so that $$ n_1+\cdots+n_k=n $$ Then, $$ \binom{n}{n_1, n_2, \ldots, n_k} = \binom{n-1}{n_1-1, n_2, \ldots, n_k} + \ldots + \binom{n-1}{n_1, n_2, \ldots, n_k-1} $$Proof ...

Unimodality of Binomial Coefficients and Sperner’s Theorem If we examine the binomial coefficients in a row of Pascal’s triangle, we notice that the numbers increase for a while and then decrease. A sequence of numbers with this property is called unimodal. Theorem Let $n$ be a positive integer. The sequence of binomial coefficients $$ {{n} \choose {0}}, {{n} \choose {1}}, \ldots, {{n} \choose {n}} $$ is a unimodal sequence. Mor precisely, ...