Time Complexity.

The bunch sampling is a fast synthesis algorithm compared to other major synthesis techniques. At the analysis stage, the running time for computing the grid parameters includes the time for both collecting the GLCHs and performing a spatial analysis of the MBIM. Similar to a un-partitioned convolution algorithm, collecting the GLCHs for all clique families inside $\mathcal{W}$ over a training image ${g}^{\circ}$ involves quadratic time complexity, proportional to $\vert{g}^{\circ}\vert\cdot\vert\mathcal{W}\vert$. Since typically a search window has a size proportional to the training image, e.g., $\vert\mathcal{W}\vert = \vert{g}^{\circ}\vert/3$, the time complexity is roughly $O({\vert{g}^{\circ}\vert}^2)$. The running time for the spatial analysis of an MBIM is $O(\vert\mathcal{W}\vert)$, which is linear to the window size. Therefore, the overall time complexity of the analysis stage is $O({\vert{g}^{\circ}\vert}^2)$.

At the synthesis stage, the running time for synthesising each pixel is constant, if a hash table is built to store signal values for each relative shift at a pre-processing stage so that the synthesis of a pixel involves only an operation of querying the hash table. So the time complexity for synthesising the entire texture is $O(\vert{g}^{syn}\vert)$. Building the hash table requires to scan the training image ${g}^{\circ}$ pixel by pixel in a raster scanline order, which has time complexity of $O(\vert{g}^{\circ}\vert)$. Usually $\vert{g}^{\circ}\vert<\vert{g}^{syn}\vert$. Therefore, the overall time complexity at the synthesis stage is still $O(\vert{g}^{syn}\vert)$, which is linearly proportional to the size of the synthetic image.

Figure 7.2: Synthesis of regular textures by bunch sampling: The sizes of training textures, MBIMs, and synthetic textures are $128\times 128$, $125\times 125$ and $360\times360$, respectively. The training textures are taken from [82,8].

MBIM
	D6

MBIM
	D14

MBIM
	D20

MBIM
	D34

MBIM
	D52

MBIM
	D101

MBIM
	D102

MBIM
	Tile07

Figure 7.3: Synthesis of stochastic textures by bunch sampling: The sizes of training textures, MBIMs, and synthetic textures are $128\times 128$, $125\times 125$ and $360\times360$, respectively. The training textures are taken from [82,8].

MBIM
	D4

MBIM
	D24

MBIM
	Bark0009

MBIM
	Water0002

MBIM
	Flower0004

MBIM
	Metal0005

MBIM
	Grass01

MBIM
	Fabric0016

Figure 7.4: Synthesis of colour textures by bunch sampling: The sizes of training textures, MBIMs, and synthetic textures are $128\times 128$, $125\times 125$ and $360\times360$, respectively. The training textures are taken from  [65].

MBIM
	Cans

MBIM
	Weave

MBIM
	Dots

MBIM
	Floor

MBIM
	Flowers

MBIM
	Flora

MBIM
	Knit

MBIM
	Design