Многомерная выборка

В сигналов цифровой обработке многомерная выборка — это процесс преобразования функции многомерной переменной в дискретный набор значений функции, измеренных на дискретном наборе точек. В этой статье представлены основные результаты Петерсена и Миддлтона. об условиях идеального восстановления функции, ограниченной волновым числом , по ее измерениям на дискретной решетке точек. Этот результат, также известный как теорема Петерсена-Миддлтона , является обобщением теоремы выборки Найквиста-Шеннона для выборки одномерных функций , ограниченных полосой, в многомерные евклидовы пространства .

По сути, теорема Петерсена-Миддлтона показывает, что функция, ограниченная волновым числом, может быть идеально восстановлена ​​по ее значениям на бесконечной решетке точек, при условии, что решетка достаточно мелкая. Теорема дает условия на решетке, при которых возможна идеальная реконструкция.

Как и в случае с теоремой выборки Найквиста-Шеннона, эта теорема также предполагает идеализацию любой реальной ситуации, поскольку она применима только к функциям, выборка которых осуществляется из бесконечного числа точек. Идеальная реконструкция математически возможна для идеализированной модели, но является лишь приближением для реальных функций и методов выборки, хотя на практике часто бывает очень хорошей.

Предварительные сведения

Рис. 1: Шестиугольная решетка выборки $\Lambda$ и его базисные векторы v ₁ и v ₂

Рис. 2: Обратная решетка $\Gamma$ соответствующий решетке $\Lambda$ рис. 1 и его базисные векторы u ₁ и u ₂ (рисунок не в масштабе).

Понятие функции с ограниченной полосой пропускания в одном измерении можно обобщить до понятия функции с ограниченной волновым числом в более высоких измерениях. Напомним, что преобразование Фурье интегрируемой функции $f(\cdot )$ в n -мерном евклидовом пространстве определяется как:

${\hat {f}}(\xi )={\mathcal {F}}(f)(\xi )=\int _{\Re ^{n}}f(x)e^{-2\pi i\langle x,\xi \rangle }\,dx$

где x и ξ — n -мерные векторы , а $\langle x,\xi \rangle$ является внутренним продуктом векторов. Функция $f(\cdot )$ говорят, что волновое число ограничено набором $\Omega$ если преобразование Фурье удовлетворяет ${\hat {f}}(\xi )=0$ для $\xi \notin \Omega$.

Аналогичным образом, конфигурация равномерно расположенных точек отбора проб в одномерном измерении может быть обобщена до решетки в более высоких измерениях. Решетка – это совокупность точек $\Lambda \subset \Re ^{n}$ формы $\Lambda =\left\{\sum _{i=1}^{n}a_{i}v_{i}\;|\;a_{i}\in \mathbb {Z} \right\}$где { v ₁ , ..., v _n } — основа для $\Re ^{n}$. Обратная решетка $\Gamma$ соответствующий $\Lambda$ определяется

$\Gamma =\left\{\sum _{i=1}^{n}a_{i}u_{i}\;|\;a_{i}\in \mathbb {Z} \right\}$

где векторы $u_{i}$ выбраны для удовлетворения $\langle u_{i},v_{j}\rangle =\delta _{ij}$. То есть, если векторы $u_{i}$ формировать столбцы матрицы $A$ и $v_{i}$ столбцы матрицы $B$, затем $A=B^{-T}$. Примером решетки выборки в двумерном пространстве является гексагональная решетка, изображенная на рисунке 1. Соответствующая обратная решетка показана на рисунке 2. Обратная решетка квадратной решетки в двух измерениях представляет собой еще одну квадратную решетку. В трехмерном пространстве обратная решетка ГЦК-решетка представляет собой объемноцентрированную кубическую (ОКЦ) решетку.

Теорема

Позволять $\Lambda$ обозначим решетку в $\Re ^{n}$ и $\Gamma$ соответствующую обратную решетку. Теорема Петерсена и Миддлтона утверждает, что функция $f(\cdot )$ это волновое число ограничено набором $\Omega \subset \Re ^{n}$ может быть точно восстановлено по его измерениям на $\Lambda$ при условии, что набор $\Omega$ не пересекается ни с одной из своих сдвинутых версий $\Omega +x$ где сдвиг x — любой ненулевой элемент обратной решетки $\Gamma$. Другими словами, $f(\cdot )$ может быть точно восстановлено по его измерениям на $\Lambda$ при условии, что $\Omega \cap \{x+y:y\in \Omega \}=\emptyset$ для всех $x\in \Gamma \setminus \{0\}$.

Реконструкция

Рис. 3: Поддержка выборочного спектра ${\hat {f}}_{s}(\cdot )$ полученный путем гексагональной дискретизации двумерной функции, ограниченной волновым числом круглого диска. Синий круг представляет поддержку $\Omega$ исходного поля с ограниченным волновым числом, а зеленые кружки представляют повторения. В этом примере спектральные повторения не перекрываются и, следовательно, нет наложения спектров. Исходный спектр может быть точно восстановлен из дискретного спектра.

Обобщение формулы суммирования Пуассона на более высокие размерности можно использовать, чтобы показать, что образцы, $\{f(x):x\in \Lambda \}$, функции $f(\cdot )$ на решетке $\Lambda$ достаточны для создания периодического суммирования функции ${\hat {f}}(\cdot )$. Результат:

${\hat {f}}_{s}(\xi )\ {\stackrel {\mathrm {def} }{=}}\sum _{y\in \Gamma }{\hat {f}}\left(\xi -y\right)=\sum _{x\in \Lambda }|\Lambda |f(x)\ e^{-i2\pi \langle x,\xi \rangle },$ ( Уравнение 1 )

где $|\Lambda |$ представляет собой объем параллелепипеда , образованного векторами { v ₁ , ..., v _n }. Эту периодическую функцию часто называют дискретным спектром, и ее можно интерпретировать как аналог преобразования Фурье с дискретным временем (DTFT) в более высоких измерениях. Если исходный спектр, ограниченный волновым числом ${\hat {f}}(\cdot )$ поддерживается на съемочной площадке $\Omega$ тогда функция ${\hat {f}}_{s}(\cdot )$ поддерживается при периодических повторениях $\Omega$ сдвинутые по точкам обратной решетки $\Gamma$. Если условия теоремы Петерсена-Миддлтона выполнены, то функция ${\hat {f}}_{s}(\xi )$ равно ${\hat {f}}(\xi )$ для всех $\xi \in \Omega$, и, следовательно, исходное поле может быть точно восстановлено по выборкам. В этом случае восстановленное поле соответствует исходному полю и может быть выражено через выборки как

$f(x)=\sum _{y\in \Lambda }|\Lambda |f(y){\check {\chi }}_{\Omega }(y-x)$, ( Уравнение 2 )

где ${\check {\chi }}_{\Omega }(\cdot )$ – обратное преобразование Фурье характеристической функции множества $\Omega$. Эта интерполяционная формула является многомерным эквивалентом интерполяционной формулы Уиттекера-Шеннона .

В качестве примера предположим, что $\Omega$ представляет собой круглый диск. Рисунок 3 иллюстрирует поддержку ${\hat {f}}_{s}(\cdot )$ когда выполняются условия теоремы Петерсена-Миддлтона. Мы видим, что повторения спектров не перекрываются и, следовательно, исходный спектр может быть точно восстановлен.

Подразумеваемое

Псевдонимы

Основная статья: Псевдонимы

Рис. 4: Поддержка выборочного спектра ${\hat {f}}_{s}(\cdot )$ полученный путем гексагональной дискретизации двумерной функции, ограниченной волновым числом круглого диска. В этом примере решетка дискретизации недостаточно мелкая, и, следовательно, диски перекрываются в дискретизированном спектре. Таким образом, спектр внутри $\Omega$ представленное синим кружком, не может быть точно восстановлено из-за наложения повторений (показано зеленым), что приводит к совмещению значений.

Рис. 5: Пространственное сглаживание в виде муарового узора .

Рис. 6: Правильно выбранное изображение кирпичной стены.

Теорема дает условия для решеток выборки для идеального восстановления выборки. Если решетки недостаточно мелкие, чтобы удовлетворить условию Петерсена-Миддлтона, то поле вообще невозможно точно восстановить по образцам. В этом случае мы говорим, что образцы могут иметь псевдонимы . Еще раз рассмотрим пример, в котором $\Omega$ представляет собой круглый диск. Если условия Петерсена-Миддлтона не выполняются, поддержка дискретного спектра будет такой, как показано на рисунке 4. В этом случае спектральные повторения перекрываются, что приводит к наложению спектров при реконструкции.

Простую иллюстрацию алиасинга можно получить, изучая изображения с низким разрешением. Изображение в оттенках серого можно интерпретировать как функцию в двумерном пространстве. Пример наложения псевдонимов показан на изображениях кирпичных узоров на рисунке 5. На изображении показаны эффекты наложения псевдонимов, когда условие теоремы выборки не выполняется. Если решетка пикселей недостаточно мелкая для сцены, возникает алиасинг, о чем свидетельствует появление муарового узора на полученном изображении. Изображение на рисунке 6 получено, когда сглаженная версия сцены выбрана с той же решеткой. В этом случае условия теоремы выполняются и наложения спектров не происходит.

Оптимальные решетки выборки

Одним из объектов интереса при разработке схемы отбора проб для полей с ограниченным волновым числом является определение конфигурации точек, приводящей к минимальной плотности отбора проб, т. е. плотности точек отбора проб на единицу пространственного объема в $\Re ^{n}$. Обычно стоимость проведения и хранения измерений пропорциональна используемой плотности выборки. Часто на практике естественным подходом к выборке двумерных полей является выборка в точках прямоугольной решетки . Однако это не всегда идеальный выбор с точки зрения плотности выборки. Теорему Петерсена и Миддлтона можно использовать для определения оптимальной решетки для полей выборки, которые ограничены по волновому числу заданным набором. $\Omega \subset \Re ^{d}$. Например, можно показать, что решетка в $\Re ^{2}$ с минимальной пространственной плотностью точек, допускающей идеальное восстановление полей, ограниченных волновым числом круговым диском в $\Re ^{2}$ представляет собой шестиугольную решётку. Как следствие, гексагональные решетки предпочтительны для выборки изотропных полей в $\Re ^{2}$.

Оптимальные решетки выборки изучались в более высоких размерностях. Как правило, оптимальные решетки упаковки сфер идеально подходят для выборки гладких случайных процессов, в то время как оптимальные решетки, покрывающие сферы, идеально подходят для выборки гладких случайных процессов. идеально подходят для выборки грубых случайных процессов.

Поскольку оптимальные решетки, как правило, неразделимы, разработка фильтров интерполяции и реконструкции требует механизмов проектирования фильтров без тензорного произведения (т. е. неразделимых). Коробчатые сплайны обеспечивают гибкую основу для разработки таких неразделимых КИХ- фильтров реконструкции, которые можно геометрически адаптировать для каждой решетки. Шестигранные шлицы являются обобщением B-сплайнов для двумерных гексагональных решеток. Аналогично, в 3D и более высоких измерениях сплайны Вороного обеспечить обобщение B-сплайнов , которое можно использовать для разработки неразделимых КИХ-фильтров, геометрически адаптированных для любой решетки, включая оптимальные решетки.

Явное построение идеальных фильтров нижних частот (т.е. функций sinc ), обобщенных на оптимальные решетки, возможно путем изучения геометрических свойств зон Бриллюэна (т.е. $\Omega$ выше) этих решеток (которые являются зонотопами ). Этот подход обеспечивает явное представление в замкнутой форме. ${\check {\chi }}_{\Omega }(\cdot )$ для общих решеток, включая оптимальные решетки выборки. Эта конструкция обеспечивает обобщение фильтра Ланцоша на многомерную настройку для оптимальных решеток. одномерного

Приложения

Теорема Петерсена-Миддлтона полезна при разработке эффективных стратегий размещения датчиков в приложениях, связанных с измерением пространственных явлений, таких как сейсмические исследования, мониторинг окружающей среды и измерения пространственного звукового поля.