Pourquoi un échantillonnage aléatoire de Monte Carlo au lieu d'un échantillonnage uniforme?

8

Pourquoi est-il si courant d'utiliser des emplacements d'échantillonnage randomisés Monte Carlo, au lieu d'un échantillonnage uniforme?

Je suppose que le prélèvement d'échantillons randomisés donne certains avantages, mais je ne sais pas ce qu'ils pourraient être.

Quelqu'un peut-il expliquer l'avantage des emplacements d'échantillonnage randomisés par rapport aux emplacements d'échantillonnage uniformes?

Alan Wolfe
la source
Habituellement, pour éviter d'obtenir des motifs uniformes partout, si vous utilisez des échantillons uniformes également espacés, vous obtiendrez des effets de motif moiré lorsque certains pixels frappent et manquent des fonctionnalités à intervalles réguliers. Idéalement, un échantillonnage d'importance devrait être utilisé pour biaiser les directions d'échantillonnage.
PaulHK
J'ai récemment lu que l'échantillonnage stratifié et les séquences à faible écart (comme halton, sobol, etc.) sont un juste milieu entre l'échantillonnage aléatoire (qui crée du bruit) et l'échantillonnage uniforme (qui crée l'aliasing).
Alan Wolfe

Réponses:

7

Les emplacements d'échantillonnage avec un motif uniforme créeront un aliasing dans la sortie, chaque fois qu'il y a des caractéristiques géométriques de taille comparable ou inférieure à la grille d'échantillonnage. C'est la raison pour laquelle les "jaggies" existent: parce que les images sont faites d'une grille de pixels carrés uniforme, et lorsque vous restituez (par exemple) une ligne inclinée sans anticrénelage, elle traverse des rangées / colonnes de pixels à intervalles réguliers, créant un motif régulier de artefacts de marche d'escalier dans l'image résultante.

Le suréchantillonnage sur une grille uniforme plus fine améliorera les choses, mais l'image aura toujours des artefacts similaires, mais moins mal. Vous pouvez le voir avec MSAA, comme dans cette image de comparaison d'une présentation NVIDIA sur l'anticrénelage temporel:

comparaison d'absence d'AA, de MSAA à grille uniforme et d'AA temporel

L'image 8x MSAA (qui n'est pas tout à fait une grille mais a toujours un motif répétitif) contient toujours clairement des jaggies, bien que ce soient des jaggies anti-crénelés. Comparez-le au résultat TXAA, qui à la fois a un nombre d'échantillons effectif plus élevé (en raison de la réutilisation temporelle) et utilise un filtre gaussien plutôt que de type boîte pour accumuler les échantillons.

En revanche, l'échantillonnage aléatoire produit du bruit au lieu du repliement. Il n'y a pas de modèle pour les emplacements d'échantillonnage, donc pas de modèle pour les erreurs résultantes. Le crénelage et le bruit sont des erreurs en raison du manque d'échantillons pour former une image propre, mais le bruit est sans doute l'artefact le moins gênant visuellement.

D' autre autre part, l' échantillonnage parfaitement aléatoire (dans le sens des variables aléatoires iid ) a tendance à présenter un certain niveau de agglomérante. Par pur hasard, certaines zones du domaine auront des amas d'échantillons plus denses que la moyenne, et d'autres zones manqueront d'échantillons; ces zones seront respectivement surreprésentées et sous-représentées dans l'estimation qui en résulte.

Le taux de convergence du processus de Monte-Carlo peut souvent être amélioré en utilisant des éléments comme l' échantillonnage stratifié , les séquences à faible écart ou le bruit bleu . Ce sont toutes des stratégies pour générer des échantillons «désagrégés» qui sont espacés un peu plus uniformément que les échantillons iid, mais sans créer de motifs réguliers qui pourraient conduire à un aliasing.

Nathan Reed
la source
Ah. Et le bruit bleu empêche l'agglutination en ayant moins de données à basse fréquence dans le modèle d'échantillonnage.
Alan Wolfe
6

Les méthodes de Monte-Carlo reposent sur la loi des grands nombres , qui stipule que la moyenne d'un événement aléatoire répété un grand nombre de fois converge vers la valeur attendue (si vous lancez une pièce un gazillion de fois, vous obtiendrez en moyenne de chaque côté la moitié du temps). L'intégration Monte Carlo utilise cette loi pour évaluer une intégrale en faisant la moyenne d'un grand nombre d'échantillons aléatoires.

L'utilisation d'une distribution uniforme briserait l'algorithme car la loi sur laquelle il est basé ne s'appliquerait plus.

Julien Guertault
la source
Oui mais surtout cela peut se résumer comme ceci pour un problème inconnu, le ramdom est la meilleure stratégie. puisque la contribution est inconnue ...
joojaa
@joojaa: oh, je me rends compte que vous et moi avons lu la question différemment. Oui, Monte Carlo est une stratégie qui fonctionne lorsque la solution analytique est inconnue (même si un mathématicien aurait probablement une façon beaucoup plus précise de l'exprimer).
Julien Guertault
Autrement dit: même si la solution est inconnue, il est prouvé que Monte Carlo converge vers elle.
Julien Guertault