Anti-aliasing: manières de déterminer la fréquence préférée maximale?

Question

J'ai lu un peu sur l'anti-aliasing et il semble logique, mais il y a une chose que je ne suis pas trop sûr. Comment trouvez-vous exactement la fréquence maximale d'un signal (dans le contexte de graphiques).

Je me rends compte qu'il ya plus d'un cas, donc je suppose qu'il ya plus d'une réponse. Mais d'abord, je voudrais dire un algorithme simple que je pense représenterait la fréquence maximale pour que quelqu'un puisse me dire si je suis conceptualiser dans le mauvais sens.

Supposons que ce soit pour une image tridimensionnelle 1, finie, et niveaux de gris (en pixels). Ai-je raison en supposant que vous pourrait simplement balayer toute la ligne de pixels (dans le domaine spatial) pour la recherche d'une oscillation minimale et l'inverse de cette oscillation la plus petite serait la fréquence maximale?

Les valeurs Ex {} 23,26,28,22,48,49,51,49

Fréquence: Qualifie pour définir {}

(1/2) = 0,5: {} 28,22

(1/4) = .25: {22,48,49,51}

Il en serait de 0,5 la fréquence maximale?

Et quel serait le moyen idéal pour calculer ce pour une ligne de pixel similaire à celui ci-dessus?

Et sur une note plus théorique, si votre entrée d'échantillonnage était infini (plus comme le monde réel)? Est-ce qu'un processus valide est un peu comme:

Predetermine a decent interval for point sampling
Determine max frequency from point sampling
while(2*maxFrequency >  pointSamplingInterval)
{
pointSamplingInterval*=2
Redetermine maxFrequency from point sampling (with new interval)
}

Je sais que ces algorithmes sont lourdes de manque d'efficacité, donc ce sont quelques-unes des façons préférées? (Ne cherchez pas quelque chose de fou optimisé, à des concepts fondamentalement mieux)

Answer 1

La bonne façon d'aborder ce utilise une transformée de Fourier (dans la pratique, une FFT ou transformée de Fourier rapide )

La théorie fonctionne comme suit: si vous avez un ensemble de pixels avec la couleur / niveaux de gris, alors on peut dire que l'image est représentée par des pixels dans le « domaine spatial »; qui est, chaque numéro spécifie l'image en un emplacement spatial particulier.

Cependant, ce que nous voulons vraiment est une représentation de l'image dans le « domaine de fréquence ». Au lieu de spécifier chaque numéro individuel de chaque pixel, chaque nombre représente l'amplitude d'une fréquence particulière dans l'image dans son ensemble.

L'outil qui convertit du « domaine spatial » au « domaine de fréquence » est la transformée de Fourier. La sortie du FT sera une séquence de numéros spécifiant la contribution relative des différentes fréquences.

Afin de trouver la fréquence maximale, vous effectuez le FT, et regardez les amplitudes que vous obtenez pour les hautes fréquences - alors il est juste une question de recherche de la plus haute fréquence vers le bas jusqu'à ce que vous frappez votre « amplitude minimum significative «seuil.

Vous pouvez coder votre propre FFT, mais il est beaucoup plus facile dans la pratique d'utiliser une bibliothèque pré-emballés comme

Answer 2

Vous ne numérisez pas un signal pour la plus haute fréquence et choisissez votre fréquence d'échantillonnage: Vous choisissez une fréquence d'échantillonnage est suffisamment élevé pour capturer les choses que vous voulez capturer, puis vous filtre la signal supprimer hautes fréquences. Vous jetez tout supérieur à la moitié du taux d'échantillonnage avant échantillonner.

  

Ai-je raison en supposant que possible   simplement balayer toute la ligne de pixels (en   le domaine spatial) pour la recherche d'un   l'oscillation minimum et la   inverse de cette oscillation plus petite   serait la fréquence maximale?

Si vous avez une ligne de pixels, l'échantillonnage est déjà fait. Il est trop tard pour appliquer un filtre anti-repliement. La fréquence la plus élevée qui pourrait être présent est la moitié de la fréquence d'échantillonnage ( « 1 / 2px », je suppose).

  

Et sur une note plus théorique, ce   si votre entrée d'échantillonnage était infinie   (Plus comme le monde réel)?

Oui, c'est lorsque vous utilisez le filtre. Tout d'abord, vous avez une fonction continue, comme une image de la vie réelle (taux d'échantillonnage infini). Ensuite, vous filtrer pour enlever tout ce qui précède fs / 2, alors vous goûter à fs (numériser l'image en pixels). Caméras ne font en réalité aucun filtrage, ce qui est la raison pour laquelle vous obtenez moiré lorsque vous photographiez des briques, etc.

Si vous êtes infographies anti-aliasing, vous devez penser à la fonction mathématique continue idéale d'abord et réfléchir à la façon dont vous le filtrer et le numériser pour produire la sortie à l'écran.

Par exemple, si vous voulez générer une onde carrée avec un ordinateur, vous ne pouvez pas naïvement alterner entre les valeurs maximales et minimales. Ce serait comme l'échantillonnage d'un signal réel de la vie sans filtrage en premier. Les harmoniques supérieures enveloppent de nouveau dans la bande de base et provoquent beaucoup de pointes parasites dans le spectre. Vous devez générer des points comme si elles ont été échantillonnés à partir d'une fonction mathématique continue filtrée:

Je pense que cet article sur le site O'Reilly pourrait également être utile pour vous ... http://www.onlamp.com/pub/a/python/2001/01/31/numerically.html ... là ils se réfèrent à la fréquence analyse des fichiers sonores, mais vous il vous donne l'idée.

Je pense que ce dont vous avez besoin est une application de Fourier Analyse ( http://en.wikipedia.org / wiki / Fourier_analysis ). J'ai étudié cela, mais jamais utilisé prendre donc avec une pincée de sel, mais je crois que si vous l'appliquez correctement à votre ensemble de nombres, vous obtiendrez un ensemble de fréquences qui sont des composants de la série et vous pouvez enlever la plus élevé.

Je ne peux pas vous pointer un morceau de code qui fait cela, mais je suis sûr que ce serait là quelque part.

Answer 3

Vous ne numérisez pas un signal pour la plus haute fréquence et choisissez votre fréquence d'échantillonnage: Vous choisissez une fréquence d'échantillonnage est suffisamment élevé pour capturer les choses que vous voulez capturer, puis vous filtre la signal supprimer hautes fréquences. Vous jetez tout supérieur à la moitié du taux d'échantillonnage avant échantillonner.

  

Ai-je raison en supposant que possible   simplement balayer toute la ligne de pixels (en   le domaine spatial) pour la recherche d'un   l'oscillation minimum et la   inverse de cette oscillation plus petite   serait la fréquence maximale?

Si vous avez une ligne de pixels, l'échantillonnage est déjà fait. Il est trop tard pour appliquer un filtre anti-repliement. La fréquence la plus élevée qui pourrait être présent est la moitié de la fréquence d'échantillonnage ( « 1 / 2px », je suppose).

  

Et sur une note plus théorique, ce   si votre entrée d'échantillonnage était infinie   (Plus comme le monde réel)?

Oui, c'est lorsque vous utilisez le filtre. Tout d'abord, vous avez une fonction continue, comme une image de la vie réelle (taux d'échantillonnage infini). Ensuite, vous filtrer pour enlever tout ce qui précède fs / 2, alors vous goûter à fs (numériser l'image en pixels). Caméras ne font en réalité aucun filtrage, ce qui est la raison pour laquelle vous obtenez moiré lorsque vous photographiez des briques, etc.

Si vous êtes infographies anti-aliasing, vous devez penser à la fonction mathématique continue idéale d'abord et réfléchir à la façon dont vous le filtrer et le numériser pour produire la sortie à l'écran.

Par exemple, si vous voulez générer une onde carrée avec un ordinateur, vous ne pouvez pas naïvement alterner entre les valeurs maximales et minimales. Ce serait comme l'échantillonnage d'un signal réel de la vie sans filtrage en premier. Les harmoniques supérieures enveloppent de nouveau dans la bande de base et provoquent beaucoup de pointes parasites dans le spectre. Vous devez générer des points comme si elles ont été échantillonnés à partir d'une fonction mathématique continue filtrée:

Answer 4

Je pense que cet article sur le site O'Reilly pourrait également être utile pour vous ... http://www.onlamp.com/pub/a/python/2001/01/31/numerically.html ... là ils se réfèrent à la fréquence analyse des fichiers sonores, mais vous il vous donne l'idée.

Answer 5

Je pense que ce dont vous avez besoin est une application de Fourier Analyse ( http://en.wikipedia.org / wiki / Fourier_analysis ). J'ai étudié cela, mais jamais utilisé prendre donc avec une pincée de sel, mais je crois que si vous l'appliquez correctement à votre ensemble de nombres, vous obtiendrez un ensemble de fréquences qui sont des composants de la série et vous pouvez enlever la plus élevé.

Je ne peux pas vous pointer un morceau de code qui fait cela, mais je suis sûr que ce serait là quelque part.