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

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, $$ {{n} \choose {0}} < {{n} \choose {1}} < \ldots < {{n} \choose {\lfloor n/2\rfloor}} $$ and $$ {{n} \choose {\lceil n/2 \rceil}} > \ldots {{n} \choose {n-1}} > {{n} \choose {n}} $$ ...

Theorem $$ \text{For every } k \in \mathbb{N}, \text{we have } R(k)\ge 2^{k/2} $$ Before we start the proof, let’s look at 3 ingredients we need: The probabilistic method The union bound The binomial estimate The probabilistic method Let $\Omega$ be the set of all possible outcomes of an experiment. Suppose that each outcome is equally likely. Let $A \subseteq \Omega$ be an event. $$ \text{If } \operatorname{Prob}(A) < 1 \text{, then } \operatorname{Prob}(A^c) > 0 $$ ...

General Ramsey on normal graph Notation General notation for Ramsey theory: $K_n \to (K_s,K_t)$ is the assertion that for any coloring of the edges of $K_n$ with red and blue, we can always find a red $K_s$ or a blue $K_t$. $K_n \not \to (K_s,K_t)$ is the assertion that there exists a coloring of the edges of $K_n$ with red and blue with no red $K_s$ nor blue $K_t$. Notation Off-diagonal Ramsey numbers: ...

Erdos-Szekeres Theorem Given $r, s$ any sequence of distinct real numbers with length at least $(r-1)(s-1)+1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequece of length $s$. That is, given the subsequence: $a_1, a_2, …, a_{(s-1)(r-1)+1}$, we can find: Indicies $i_1 < i_2 < …< i_r$ so that $a_{i1} < a_{i2} < …< a_{ir}$ OR Indicies $j_1 < j_2 < …< j_r$ so that $a_{j1} > a_{j2} > … > a_{jr}$ Example: $s = 3, r = 3$, Sequence: $10, 11, 7, 8$ has no such property. ...

Permutation of Sets Definition permutation A permutation of a set $S$ can be thought of as a listing of the elements $S$ in some order. $P(n, r)$ denotes the number of $r$-permutations of an $n$-element set. Definition $r$-permutation An $r$-permutation of a set $S$ is a string $a_1, a_2, … a_r$ where $a_i \in S, \forall i \in [r]$ and $a_i \neq a_j$ for $i \neq j$. Note: $[r] = {1, 2, …, r}$ ...

Texture Synthesis & Hole Filling Texture 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. Another idea: ==Efros & Leung algorithm== ...

Pigeonhole Principle If $n+1$ objects are distributed into $n$ boxes, then at least one box contains two or more of the objects. Proof For each $i\in \set{1, …, n}$, let $a_i = $ number of objects in box $i$. Then, $a_1 + … + a_n = n+1$ Let $a_j = \text{max } a_i$. Then, \begin{align*} n+1 &\leq n\cdot a_j \\ \frac{n+1}{n} &\leq a_j \\ 1 < \frac{n+1}{n} &\leq a_j\\ 1 &< a_j \end{align*} Note that this conclusion doesn’t hole if you have $n$ objects or less. ...