Stay 😎. Be 😊. Keep 📚

Definition Problem: Given $n$ points $P = \set{p_1, \ldots, p_n} \subset \mathbb{R}^2$, compute $\text{CH}(P) = $ smallest convex set contining $P$. Input: a list of points all the points in $P$. Output: a list of points in $P$ that belongs to this convex set in CCW, starting from the left most point. Applications Given a huge point cloud, convex hull helps find the “shape”. Bounding volume. Makes ray shooting tasks faster....

I know this name for a long time. But never learnt it. Now it’s time. Recap Previously, Karatsuba’s algorithm for integer multiplication. It computes the result in $O(n^{\log_2 3})$ where $n$ is the number of digits. Another recap: polynomial representation: $$ p(x) = \sum_{i = 0}^{n}p_ix^i $$ And we can represent this polynomial using an array of size $n$. Evaluations and additions of polynomials are straightforward computation. Can be done in $O(n)$ time....

⚠️THIS NOTE IS NOT FINISHED YET TODO: stirling number definitions stirling number of the first and the second type bell number 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!...

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

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

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

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