Une image est composée de pixels, et le problème de la synthèse d'image est de trouver quelle couleur affecter à chaque pixel pour représenter une scene donnée.

Les estimateurs de Monte Carlo sont une solution pour approximer numériquement la valeur de l'intégrale d'une fonction $f$ sur un domaine $D$. Ces estimateurs tirent des échantillons $x_i$ aléatoires dans $D$ et évaluent $f$ pour chacun d'entre eux. La moyenne de toutes ces valeurs leur donne une approximation de la valeur de l'intégrale. $$\int_D f(x)dx \approx \sum_{i=0}^{n} f(x_i)$$

C'est ce que l'on fait en pratique lors d'un rendu par méthodes dites de lancer de rayons.

On peut mesurer l'erreur commise par Monte Carlo comme la différence entre la valeur réelle de l'intégrale $\mathcal{I}$ et la valeur approximée $\mathcal{I}_n$: $$ \Delta = | \mathcal{I}_n - \mathcal{I}| $$

En théorie, plus on tire d'échantillons plus $\Delta$ diminue, sauf dans le cas où on utilise des échantilloneurs biaisés. $$ \text{Bias} := | \mathcal{I} - \langle \mathcal{I}_n \rangle | $$

On peut également mesurer, dans le cas d'échantilloneurs aléatoire, la variance dans l'approximation $$ \text{Variance} := \langle (\mathcal{I}_n)^2 \rangle - \langle (\mathcal{I}_n) \rangle^2 $$ On note que dans le cas d'échantilloneurs non biaisés, cette variance est équivalente à l'erreur. $$ MSE(\mathcal{I}_n) := \text{Bias}^2 + \text{Variance} $$

Pour des échantillons purement aléatoires, on a l'erreur suivante qui diminue avec le nombre d'échantillons $$ \Delta := O\left(\frac{\sigma_f}{n}\right) $$

On peut accélérer cette convergence en utilisant un échantillonneur déterministe dit basse discrépance $$ \Delta := O\left(\frac{ \sqrt[k]{\log(n)^d}}{n}\right) $$

Mesure l'uniformité d'une distribution de points $P_n$. Plus la discrépance est basse, plus la distribution est proche de la distribution uniforme théorique.

$$ \mathcal{D}_*(P_n) := \sup_{\vv \in [0, 1)^d} | v_1 \cdots v_d - \alpha( P_n, \vv ) | $$

Un échantillonneur est dit basse discrépance si sa discrépance décroit en $O(\frac{\log(n)^d}{n})$.

Meilleure discrépance théorique.

Le test du Zoneplate consiste à reconstruire une fonction en l'échantillonnant. La fonction choisie présente une très grande gamme de fréquences, ce qui permet de mesurer la quantité d'aliassage et de bruit en fonction de la fréquence.

$sin(x^2 + y^2)$

Augmenter le nombre d'échantillons réduit la variance

On s'est pour l'instant concentré sur les échantillonneurs éxistants. Mais il existe aussi toute une gamme de méthodes pour retravailler un ensemble de points donné.

Cranley Patterson	Digital XOR

On défini un ensemble de points stratifié comme

$$ \lbrace (X + u_{XY}, Y + v_{XY}) \rbrace, X,Y \in \mathbb{N}, u,v \in [0, 1[ $$
où $(X,Y)$ identifie une strate, et où $(u_{XY}, v_{XY})$ représente la position du point dans la strate $(X, Y)$.

On part d'un motif stratifié présentant le spectre désiré et de l'ensemble de points basse discrépance défini comme $$ \lbrace (X + \phi(Y)), Y+\phi(X)) \rbrace. $$
Les deux ensembles de points sont de taille $t \times t$.

On divise les deux ensembles de points en sous blocs de taille $m \times m$.

Si on permute aleatoirement des échantillons d'un ensemble basse discrépance 1D dans des blocs de taille $m$, l'ensemble de points 1D obtenu est aussi un ensemble basse discrépance 1D.

Dans chaque ligne et chaque colonne de l'ensemble basse discrépance initial, on reordonne les échantillons de façon à ce que leurs décalages soient dans le même ordre que ceux de l'ensemble stratifié de référence.

Ce qui nous donne un ensemble de points final qui présente les même caractéristiques frequentielles que l'ensemble de points donné en entrée, tout en étant basse discrépance.

Les permutations sont calculées une fois pour un ensemble de taille $t$, puis sont stockées dans une table pour être réutilisées et permettre de generer des ensembles de toute tailles.

$$ \lbrace X + \phi(Y - Y\%m + L_X), \\ Y + \phi(X - X\%m + L_Y) \rbrace $$

• Bruit Bleu
• Basse discrépance
• => Faible erreur en intégration
• Efficacité

• 2-D
• Genere des ensembles de points
• Global (pas d'adaptivité)

On peut faire mieux !

On prend une séquence de sobol:

Comme Sobol est basse discrepance, si on subdivise le domaine, on a le même nombre de points dans chaque tuile.

Si on choisi un facteur de subdivision $K$ et qu'on subdivise hierachiquement le domaine. A chaque niveau de subdivision $\lambda$, on peut génèrer $K^{d\lambda}$ points de Sobol pour avoir $K^d$ points dans chaque tuile.

Exemple pour $K=2$

Notre méthode scramble une séquence de Sobol de façon à lui donner un spectre bruit bleu. Contrairement à Owen et LDBN, ce scrambling se fait de façon hierarchique ce qui permet de raffinner séquentiellement un ensemble de points existant.

On génère $K^d=16$ points à partir de Sobol. On note cet ensemble $\mathcal{S_0}$.

Et on les scramble en utilisant un Owen scrambling pour leur donner un spectre bruit bleu. On note le nouvel ensemble $\mathcal{P_0}$.

On génère $K^{2d}=256$ points à partir de Sobol. On note cet ensemble $\mathcal{S_1}$.

On commence par appliquer un scrambling global sur cet ensemble pour reconstruire $\mathcal{P_0}$. On note le nouvel ensemble $\mathcal{Q_1}$.

Ensuite, on scramble les points dans chaque tuile $\mathcal{T_1^{i}}$ de $\mathcal{Q_1}$ pour obtenir un spectre globalement bruit bleu.

Et ainsi de suite jusqu'à avoir généré le nombre de points souhaité.

On part de la séquence de Sobol du niveau précédent et du point set optimisé depuis cette séquence.

En faisant un XOR point à point entre ces deux séquences, on obtient l'ensemble des déplacements appliqués sur chacun des points lors des optimisations précédentes.

On peux ensuite réappliquer ces permutations à la séquence de Sobol du niveau courant pour obtenir un ensemble de points temporaire qui contiendra les points optimisés du niveau précédent.

On part de l'ensemble temporaire obtenu par la permutation globale, qui est subdivisé en tuiles de façon à avoir $K^{2d}$ points dans chaque tuile.

On va ensuite chercher de façon exhaustive quelle permutation d'Owen permet d'optimiser le spectre de cette tuile, tout en préservant la position du premier point (issu du niveau précédent).

Cette recherche est extrêmement couteuse, aussi une fois que l'on a trouvé l'optimisation d'un ensemble de points, on stocke cette optimisation dans une Look Up Table.

Possible car les séquences de Sobol sont auto-similaires.

n-D obtenu par scrambling indépendant de projections 2D.

Discrépance hors octaves ??

• Bruit Bleu
• Basse discrépance
• => Faible erreur en intégration
• Efficacité
• n-D
• Adaptativité

• Octaves
• Bruit Bleu et Basse discrépance dans les projections uniquement

Combiner bruit bleu et basse discrépance est possible sans perte de qualité

Mais pour utiliser ce genre d'échantillonneur en rendu il faudrait qu'ils soient $n$-D, aient une définition analytique, soient stochastiques ...

Il reste encore beaucoup de travail !

Gain réel observé en terme d'aliassage.

L'aliassage n'apparait que sur de images non convergées, ce type d'image n'est utilisé en production que comme previsualisation ou comme entrée pour un algorithme de débruitage.

Ces d'algorithmes ont ils plus de mal à débruiter une image présentant une erreur structurée ou une image présentant une erreur aléatoire ?

Gain réel observé en terme d'intégration ?

Difficile de conclure ... Nécessité de tester sur des scènes plus complexes, et donc d'algorithmes Bruit Bleu et Basse discrépance plus efficaces.

Release officielle du framework UTK !
Aggregation de tous les samplers et outils developpés lors de cette thèse.

https://utk-team.github.io/utk/index.html

Questions ?