Stochastic Conformity Improvement - akilmarshall/procedural-image-generation GitHub Wiki

This algorithm directly builds on the ideas from MCI, with the goals of:

  • producing "good" images quickly
  • maintaining a high rate of improvement over the life of the algorithm, terminating otherwise.

MCI started with random images and attempted to manipulate them into better images. In retrospect beginning with a random input is not conducive to the algorithms performance, instead of "building" an image it is instead "correcting" the error present in the stochastic start state. [introduce sparse image and undefined tiles]

Stochastic Conformity Improvement (SCI) will instead use two distinct operations on images expand and refine. expand selects from the undefined tiles and makes informed decisions while refine select from the defined tiles and improves image fitness.

expand

Consider the set $U_\mathbb{I}=\{t_{x,y}\mid t=\empty, t\in\mathbb{I}\}$ of undefined tiles in $\mathbb{I}$. The goal of the expand operation is to identify $t\in U$ such that $t$ maximizes/minimizes $\mathcal{P}(t)\in (0, |\mathbb{T}|]$. That tile is then conformed (with the potential $\mathcal{P}$ function).

potential function

the potential function $\mathcal{P}:U\to \{t\mid t\in \bigcap{}_k; t\in T\}$ analyzes a tiles neighbors and returns a set containing the max/min (denoted $\mathcal{P}_+$ and $\mathcal{P}_-$ respectively) number of tiles that can be placed at $(x, y)$ using as many neighbors as possible to do the inference.

Additionally I must introduce the function $\mathcal{H}_\mathbb{I}:\mathbb{T}\to \left\{(t_{i, j}, d)\mid i = x + 1\text{ or } i = x - 1\text{ or }j = y + 1\text{ or } j = y - 1;d\in\mathbb{D}\right\}$ that takes a tile and computes a list of it's neighbors with the direction from the neighbor's vantage (simplifies the expression of the potential function, however this is the first time another point of view has been introduced)

case $|\mathcal{H}(t_{x, y})|=0$

Degenerate case

\mathcal{P}(t_{x,y}) = \{\}

case $|\mathcal{H}(t_{x, y})|=1$

Base case

\mathcal{P}(t_{x,y}) = \bigcap_{\mathcal{H}(t_{x, y})} \mathcal{N}(t, d)

case $|\mathcal{H}(t_{x, y})|=n$

General case. Let

\bigcap_n=\bigcap_{\mathcal{H}(t_{x, y})} \mathcal{N}(t, d)

then,

\mathcal{P}(t_{x,y}) = 
\begin{cases}
\bigcap_n &\text{if } \bigcap_n \neq \empty \\
\bigcap_{n-1} &\text{otherwise}
\end{cases}.

In the otherwise case, over the $n$ options of $\bigcap_{n-1}$ (1 neighbor omitted) identify the neighbor $(t, d)$ that (maximizes/minimizes) the available tiles in the interval $[1, |\mathbb{T}|]$.

Conformity from potential

For undefined tiles the notion of conformity comes directly from the potential function $\mathcal{P}$.

\mathbb{C}(\empty_{x, y})=\sigma(\mathcal{P}(\empty_{x, y})).

($\sigma$ picks a tile weighted by some distribution)

refine

Consider the dual set to $U_\mathbb{I}$, the defined set of tiles $D_\mathbb{I}=\{t\mid t\neq \empty;t\in\mathbb{I}\}$. Identify the tile $t\in D_\mathbb{I}$ that has a minimal conformity ratio (ratio used to allow all tiles to equally compared). That tile is made to conform to it's local conditions, improving the fitness of the image $\mathcal{Fit}(\mathbb{I})$

conformity ratio

A value $\frac{\mathbb{C}(t_{i,j})}{|\mathcal{H}(t_{i, j})|}\in[0, 1]$

SCI Algorithm

With expand and refine defined the SCI algorithm can now be described:

  1. begin with a sparse input image $I\in\mathbb{M}_{n\times m}(\mathbb{T})$
  2. expand and refine $I$
  3. if expand or refine took an action go to 2

Specifically there are two variants of the algorithm $\text{SCI}_{\text{max}}$ and $\text{SCI}_{\text{min}}$, in which the maximum or minimum potential $\mathcal{P}$ in the expand and refine operations.