Le suréchantillonnage avant la corrélation croisée est-il inutile?

12

Prenons un cas simple où deux signaux provenant de deux capteurs différents sont corrélés de manière croisée et le temps de retard d'arrivée calculé à partir de l'absisse du pic de leur fonction de corrélation croisée.

Supposons maintenant qu'en raison des contraintes de dimensionnalité des deux antennes et des contraintes sur le taux d'échantillonnage maximum possible, le retard maximum possible est , correspondant à 10 échantillons. $D$

Le problème:

En raison de ces contraintes, votre retard calculé peut varier de toute valeur entière comprise entre 0 et 10 échantillons, c'est-à-dire: . C'est problématique parce que ce que je veux vraiment, c'est une discrimination à retard fractionnaire du retard entre les deux signaux entrant sur mes antennes, et changer les dimensions ou la fréquence d'échantillonnage n'est pas une option. $0 \le D \le 10$

Quelques idées:

Naturellement, la première chose à laquelle je pense dans ce cas est le suréchantillonnage des signaux avant d'effectuer une corrélation croisée. Cependant, je pense que cela «triche» d'une manière ou d'une autre, car je n'ajoute pas vraiment de nouvelles informations dans le système.
Je ne comprends pas comment le suréchantillonnage ne «triche» pas dans un sens. Oui, nous reconstruisons notre signal sur la base de ses informations de fréquence actuellement observées, mais comment cela permet-il de savoir où un signal a réellement commencé entre, disons, et ? Où était cette information contenue dans le signal d'origine qui a déterminé que le véritable début de retard fractionnaire du signal était réellement à ? $D=7$ $D=8$ $D=7.751$

Questions):

Est-ce vraiment de la «tricherie»?
- Sinon, d'où viennent ces nouvelles «informations»?
- Si oui, quelles sont les autres options disponibles pour estimer les temps de retard fractionnaire?
Je suis conscient du suréchantillonnage du résultat de la corrélation croisée, dans le but de recueillir des réponses de sous-échantillon au retard, mais n'est-ce pas aussi une forme de «tricherie»? Pourquoi est-ce différent du suréchantillonnage avant la corrélation croisée?

S'il est en effet vrai que le suréchantillonnage n'est pas de la «tricherie», alors pourquoi aurions-nous besoin d'augmenter notre taux d'échantillonnage? (N'est-ce pas toujours mieux d'avoir un taux d'échantillonnage plus élevé que d'interpoler un signal échantillonné bas?)

Il semblerait alors que nous pourrions simplement échantillonner à un taux très faible et interpoler autant que nous voulons. Cela ne rendrait-il donc pas inutile d'augmenter la fréquence d'échantillonnage à la lumière d'une simple interpolation d'un signal selon le désir de notre cœur? Je me rends compte que l'interpolation prend du temps de calcul et que commencer simplement avec un taux d'échantillonnage plus élevé ne le serait pas, mais est-ce alors la seule raison?

Merci.

filters cross-correlation peak-detection Spacey
la source

3

Je doute qu'il y ait une différence de précision, car la quantité d'informations est la même dans les deux cas, mais il est certainement moins cher d'interpoler après la corrélation croisée que dans la région d'intérêt que de tout suréchantillonner d'abord, puis de faire toutes ces multiplications supplémentaires.

endolith

@endolith Bon (s) point (s). Je suis maintenant plus clair quant à pourquoi / comment cela fonctionne, et oui, un suréchantillonnage du résultat serait la voie à suivre dans ce cas.

Spacey

12

Ce n'est pas de la triche, et cela n'ajoute pas non plus de nouvelles informations. Ce que vous faites est la même chose que n'importe quel LPF suréchantillonnant: ajouter des zéros puis reconstruire la forme d'onde avec les informations de fréquence déjà connues. Ainsi, il n'y a pas de nouvelles informations, mais la résolution temporelle est encore plus fine.

Le suréchantillonnage du résultat est similaire - pas de nouvelles informations mais une résolution temporelle plus fine. Vous pouvez faire quelque chose de très similaire grâce à l' interpolation quadratique .

Toutes ces méthodes - suréchantillonnage et interpolation polynomiale - obtiennent leurs informations sur la provenance du pic fractionnaire à la fois du pic lui-même et de ses voisins. Un exemple pictural rapide. Pic équilibré

La ligne bleue dans l'image ci-dessus est mes données de corrélation croisée simulées (bien qu'il puisse s'agir de n'importe quel résultat, pas seulement d'une corrélation croisée). C'est ce que j'appelle un pic "équilibré" car les voisins sont symétriques. Comme vous pouvez vous y attendre, l'interpolation quadratique résultante (ligne rouge) indique que le vrai pic est à zéro.

En revanche, l'image ci-dessous montre un pic déséquilibré. Veuillez noter que rien n'a changé dans le résultat, à l'exception des valeurs des deux voisins les plus proches. Cependant, l'interpolateur modifie son estimation du pic fractionnaire. entrez la description de l'image ici

Un avantage intéressant de ces méthodes (interpolation polynomiale et suréchantillonnage) est qu'elles vous donnent également une estimation de la valeur de crête réelle, bien que nous soyons généralement plus intéressés par l'emplacement.

S'il est en effet vrai que le suréchantillonnage n'est pas de la «tricherie», alors pourquoi aurions-nous besoin d'augmenter notre taux d'échantillonnage?

Satisfaire au critère de Nyquist.

N'est-ce pas toujours mieux d'avoir un taux d'échantillonnage plus élevé que d'interpoler un signal échantillonné bas?

Non. D'un point de vue théorique, tant que le critère de Nyquist est satisfait, peu importe le taux d'échantillonnage. D'un point de vue pratique, vous utilisez généralement un taux d'échantillonnage aussi bas que possible pour réduire les exigences de stockage et la charge de calcul, ce qui réduit à son tour les ressources nécessaires et la consommation d'énergie.

Jim Clay
la source

1

F_{s}

$F_s$

1

@Mohammad Oui et non. Le bruit - soit des résultats eux-mêmes, soit du bruit de quantification - rendra finalement inutile l'augmentation de la résolution temporelle. Jusque-là, cependant, oui, un suréchantillonnage supplémentaire devrait améliorer la précision de l'estimation.

Jim Clay

1

notes et exemple de code pour l'interpolation quadratique / parabolique: gist.github.com/255291#file_parabolic.md et quelques autres méthodes d'interpolation: dspguru.com/dsp/howtos/how-to-interpolate-fft-peak

endolith

2

@JimClay J'ai eu la chance de dormir dessus. Il est clair maintenant - l'information est toujours là - c'est juste codé dans la relation entre les échantillons pour ainsi dire. Et c'est ce que le poly-raccord utilise en fait dans son interpolation. Et comme le signal est limité en bande (c'est-à-dire qu'il ne peut changer que si rapidement dans un laps de temps), il existe seulement de nombreuses manières d'exister entre les échantillons.

Spacey

8

Tout signal à bande limitée peut être interpolé. Les informations supplémentaires "entre les échantillons" sont contenues dans les échantillons adjacents, plus le fait que le signal a été limité en bande avant l'échantillonnage (ce qui tend à diffuser les informations entre les échantillons adjacents). Si deux signaux sont limités en bande, la corrélation croisée le sera, de sorte que la corrélation croisée peut également être interpolée. Le suréchantillonnage n'est qu'une autre forme d'interpolation, une forme d'interpolation très précise pour les signaux à bande limitée; mais vous pouvez également utiliser l'interpolation Sinc (les deux pouvant être plus précises que l'interpolation quadratique ou parabolique).

L'interpolation peut montrer un pic entre les échantillons. Donc peut-être pas inutile.

Si vous avez un signal contenant un spectre plus large, il peut contenir plus d'informations. L'échantillonnage à un taux plus élevé fournira donc plus d'informations, mais seulement jusqu'à un peu moins de la moitié de la nouvelle fréquence limite de bande, et seulement si le signal contenait un contenu de fréquence spectrale utile réel supérieur à l'ancienne limite de bande, et si vous pouvez maintenant obtenir ce supplément spectre en utilisant un nouveau processus ou filtre de limitation de bande plus large bande, au lieu de l’ancien plus avec perte. L'échantillonnage de données à une fréquence beaucoup plus élevée d'un signal qui était déjà limité en bande à une fréquence bien inférieure à Fs / 2 ne vous procurera qu'une interpolation, pas plus de contenu d'information.

Si l'échantillonnage est quantifié, l'échantillonnage à un taux plus élevé peut vous permettre d'acheter une fraction d'un LSB de plus d'informations, en raison du tramage ou de la mise en forme du bruit de l'erreur de quantification. Mais cela dépend du rapport S / B et de la précision de l'échantillonneur et du processus de quantification exact utilisé dans l'échantillonnage.

Si deux signaux ne sont pas correctement limités en bande avant l'échantillonnage et la corrélation croisée, non seulement le suréchantillonnage ou l'interpolation pourraient vous procurer un résultat de poubelle, mais il pourrait en être de même de la corrélation croisée non interpolée d'origine.

hotpaw2
la source

1

Merci hotpaw2. Il est donc correct de dire que cela n'a pas vraiment d'importance si vous suréchantillonnez les deux signaux, puis corrélez, ou corrélez puis suréchantillonnez le résultat? En raison de la limitation de bande, les deux méthodes devraient vous donner les mêmes résultats?

Spacey

@Mohammad: Je pense qu'il contient les mêmes informations de toute façon, mais comme l'interpolation n'est pas parfaite, les résultats seront légèrement différents selon la mise en œuvre.

endolith

3

Je pense que la meilleure réponse que je puisse vous donner est: vous avez tous les moyens de le découvrir par vous-même. Construisez un exemple "à l'envers". En utilisant Matlab, commencez avec deux signaux échantillonnés avec de très petites périodes d'échantillonnage (de sorte qu'il s'agit de signaux à temps quasi continu). Calculez la corrélation croisée et trouvez le pic (si c'est ce que vous voulez), ce que vous pourrez faire avec une grande précision. Ensuite, sous-échantillonnez les deux signaux et répétez le processus. Comparez l'emplacement et la hauteur du deuxième pic avec le premier. Je suis sûr que la seconde sera pire. L'amélioration du deuxième au premier est ce que vous gagnez, si vous suréchantillonnez avant la corrélation croisée.

Pour suréchantillonner dans le bon sens, les deux signaux doivent être limités en bande et vous devez connaître ces bandes passantes. Les "nouvelles" informations que vous mentionnez dans votre question proviennent des échantillons adjacents et du fait que les signaux sont limités en bande.

Telaclavo
la source

Merci Telaclavo. Une chose qui n'est vraiment pas claire pour moi, c'est la terminologie de «bande limitée». Je sais ce que cela signifie, mais je ne comprends pas pourquoi cela est mentionné ici. N'IMPORTE QUEL système, sauf peut-être que le bruit est «à bande limitée», alors pourquoi est-il mentionné à plusieurs reprises dans ce sens?

Spacey

3

Pour ajouter un peu aux réponses précédentes, vous pouvez obtenir l'équivalent d'une corrélation croisée limitée par bande suréchantillonnée en faisant de votre variable de corrélation un entier non.

$\tau$

τ = \arg max_{τ} \sum_{n = 0}^{N - 1} f (n) g (n + τ)

$\tau = \arg \max_{\tau}\sum_{n=0}^{N-1}f\left(n\right)g\left(n+\tau\right)$

Autrement dit, il trouve le maximum de la corrélation croisée.

Les variables d'entrée aet bdécrivent et pour et sont toutes deux supposées être limitées en bande et périodiques avec la période (le décalage est implémenté dans le domaine de Fourier discret). est dans la plage . $f\left(n\right)$ $g\left(n\right)$ $n = \{0, 1, ... , N-1\}$ $N$ $\tau$ $[-N+1, N-1]$

L'intention est de montrer comment la corrélation croisée peut être effectuée pour un non entier , qui est défini par la fermeture . Celui-ci utilise le tableau, qui décrit la rotation du phaseur complexe à chaque fréquence discrète correspondant à un décalage temporel . ensuite à l'échelle cela pour chaque quart de travail. Il doit être évident que pour maintenir un signal en temps réel, les rotations des fréquences négatives sont juste fois les rotations des fréquences positives (pour les paires de fréquences correspondantes). $\tau$ correlate_pointomega $\tau=1$ $\tau$ $-1$

La seule subtilité réside dans la façon dont vous traitez l' échantillon (la fréquence de nyquist), car elle est partagée entre les bandes positives et négatives. La solution utilisée ici consiste à interpoler entre le phaseur à rotation positive et le phaseur à rotation négative (qui sont des réflexions sur l'axe réel), qui consiste à projeter l'un ou l'autre des phaseurs à rotation unitaire sur l'axe réel, qui est une fonction cos ( c'est parce que cela est la valeur de correspondant à la fréquence de nyquist). Il est clair que cette valeur doit être réelle pour maintenir un signal de domaine en temps réel. $\frac{N}{2}$ piomega

Vous pouvez l'utiliser pour calculer la corrélation croisée pour toute valeur arbitrairement précise de . Appelez simplement la fermeture (qui peut être retournée comme appelable) avec la valeur de vous souhaitez. $\tau$ $\tau$

import numpy
from numpy import fft
from scipy import optimize

def arg_max_corr(a, b):

    if len(a.shape) > 1:
        raise ValueError('Needs a 1-dimensional array.')

    length = len(a)
    if not length % 2 == 0:
        raise ValueError('Needs an even length array.')

    if not a.shape == b.shape:
        raise ValueError('The 2 arrays need to be the same shape')

    # Start by finding the coarse discretised arg_max
    coarse_max = numpy.argmax(numpy.correlate(a, b, mode='full')) - length+1

    omega = numpy.zeros(length)
    omega[0:length/2] = (2*numpy.pi*numpy.arange(length/2))/length
    omega[length/2+1:] = (2*numpy.pi*
            (numpy.arange(length/2+1, length)-length))/length

    fft_a = fft.fft(a)

    def correlate_point(tau):
        rotate_vec = numpy.exp(1j*tau*omega)
        rotate_vec[length/2] = numpy.cos(numpy.pi*tau)

        return numpy.sum((fft.ifft(fft_a*rotate_vec)).real*b)

    start_arg, end_arg = (float(coarse_max)-1, float(coarse_max)+1)

    max_arg = optimize.fminbound(lambda tau: -correlate_point(tau), 
            start_arg, end_arg)

    return max_arg

Henry Gomersall
la source

1

Je vais devoir déterminer si votre question est correcte (et je n'ai pas le temps pour l'instant). La façon dont je pense à cela est que vous modifiez le retard de groupe de votre signal, ce que vous pouvez faire à tout moment. Ceci est exactement équivalent à une convolution circulaire avec une fonction sinc dans le domaine temporel, avec le sinc décalé de (mais toujours échantillonné aux mêmes endroits que le signal d'origine). Il convient de noter qu'avec un entier , tous les passages à zéro du sinc s'alignent sur les temps d'échantillonnage, sauf pour (où il est ), c'est pourquoi le signal est trivialement décalé.

τ

$\tau$

τ

$\tau$

τ

$\tau$

1

$1$

Henry Gomersall

Oh, ta question a disparu! Je laisse quand même la réponse.

Henry Gomersall

t a u

$tau$

N^{2}

$N^2$

N (\log N + 1)

$N\left(\log N + 1\right)$

De plus, je trouve que la réflexion dans le domaine de Fourier est beaucoup plus simple. Mais ce n'est peut-être pas normal!

Henry Gomersall

2

Il existe une preuve intuitive que le suréchantillonnage avant la corrélation croisée équivaut à le faire par la suite:

La corrélation croisée est une convolution avec l'autre signal inversé dans le temps. L'inversion du temps n'affecte pas la bande passante. La convolution est une multiplication dans le domaine fréquentiel, qui n'augmente pas non plus la bande passante. Si les signaux d'origine sont correctement limités en bande, à la moitié de la fréquence d'échantillonnage, le résultat de la corrélation croisée le sera aussi. Aucun aliasing n'est introduit pour ruiner le résultat. L'interpolation économise ensuite du travail.

Olli Niemitalo
la source

Le suréchantillonnage avant la corrélation croisée est-il inutile?

Réponses: