Подход Папулиса-Маркса-Чунга
Теорема в теории выборки

Подход Папулиса-Маркса-Ченга [1] — это теорема в многомерной теории выборки Шеннона, которая показывает, что плотность выборки двумерной функции с ограниченной полосой пропускания может быть сведена к поддержке преобразования Фурье функции . Применяя многомерное обобщение теоремы Атанасиоса Папулиса , [2] подход был впервые предложен Робертом Дж. Марксом II и Квангом Фаем Ченгом. [3] [4] Подход был назван «элегантным», [5] «замечательно» закрытым, [6] и «интересным». [7]

Теорема

Двумерное преобразование Фурье , или частотный спектр, функции имеет  вид [8] где  и  — пространственные частоты, соответствующие  и . Когда  и — длины, пространственная частота имеет единицы циклов на единицу длины. ф ( х , у ) {\displaystyle f(x,y)} Ф ( ты х , у у ) = ∬ х , у ф ( х , у ) е − я 2 π ( х ты х + у ты у ) г х г у {\displaystyle F(u_{x},y_{y})=\iint \limits _{x,y}f(x,y){\rm {e}}^{-i2\pi (xu_{x}+yu_{y})}\operatorname {d} \!x\operatorname {d} \!y} ты х {\displaystyle u_{x}} ты х {\displaystyle u_{x}} х {\displaystyle x} у {\displaystyle у} х {\displaystyle x} у {\displaystyle у}

Прели и Нойхофф [1] описывают подход Папулиса-Маркса-Ченга следующим образом.

«Маркс и Чунг сосредоточились на изображениях с заданной спектральной областью поддержки и исходной базовой решеткой выборки, такой, что индуцированные спектральные реплики этой области поддержки не перекрываются. Затем они показали, что смежные классы некоторой подрешетки могут быть удалены из базовой решетки до тех пор, пока плотность выборки не станет минимальной… или не приблизится к минимальной… [Это] позволяет уменьшить частоту выборки до тех пор, пока она не сравняется или не приблизится к … [минимуму]». В этом контексте пределом является область поддержки спектра.

При получении своего результата Маркс и Чунг опирались на обобщенное выборочное расширение Папулиса. [2] [9]

Объяснение

Рисунок 1: (Слева) Спектральная поддержка полукруга . За пределами полукруга спектр тождественно равен нулю. (Справа) Неперекрывающаяся неалиасированная прямоугольная репликация поддержки спектра слева.

Подход Папулиса-Маркса-Ченга лучше всего объяснить на примере. Рассмотрим полукруг, показанный на рисунке 1 в правой полуплоскости. Спектр сигнала, , равен нулю вне полукруга. Внутри круга спектр' произволен, но ведет себя хорошо. [9] Полукруг с единичным радиусом имеет площадь   (циклов на единицу длины) в квадрате. Ф ( ты х , ты у ) {\displaystyle F(u_{x},u_{y})} π / 2 = 1.5708 {\displaystyle \пи /2=1,5708}

Согласно подходу Папулиса-Маркса-Ченга, плотность выборки для изображения  может быть уменьшена до выборок на единицу площади. Подход Папулиса-Маркса-Ченга информирует, как это сделать. ф ( х , у ) {\displaystyle f(x,y)} 1.5708 {\displaystyle 1.5708}

Справа на рисунке 1 изображена прямоугольная реплика полукруга, которая получается при дискретизации двумерной функции в пространственных точках, показанных на рисунке 2.

Рисунок 2: Такая геометрия выборки приводит к спектральной репликации справа на рисунке 1.

Эта репликация является следствием теоремы многомерной выборки , которая показывает, что выборка двумерного сигнала в пространственной  области приводит к репликации спектра в области Фурье. Если бы равномерная плотность выборки была ниже, репликации перекрывались бы, и попытка реконструкции исходной функции привела бы к наложению спектров . Плотность выборки для достижения этого равна площади прямоугольной ячейки решетки репликации спектра. Соответствующая площадь прямоугольника, используемого в репликации, равна (циклов на единицу длины) в квадрате. Как подтверждается рисунком 2, плотность выборки, необходимая для достижения спектральной репликации, составляет, таким образом, выборок на единицу площади. Подход Папулиса-Маркса-Ченга гласит, что эта плотность выборки может быть уменьшена до площади полукруга, а именно с до выборок на единицу площади. ( х , у ) {\displaystyle (x,y)} 2 {\displaystyle 2} 2 {\displaystyle 2} 2 {\displaystyle 2} 1.5708 {\displaystyle 1.5708}

Рисунок 3: Спектр полукруга, разделенный на 32 квадрата.

Чтобы увидеть, как происходит это сокращение, рассмотрим рисунок 3, где прямоугольная ячейка решетки разделена на идентичные квадраты. Обратите внимание, что два из этих квадратов полностью лежат в области, где спектральная репликация тождественно равна нулю. Эти квадраты закрашены светло-зеленым цветом. Представьте себе каждый из квадратов как спектры различных двумерных сигналов. Все выборки для сигналов, соответствующих светло-зеленым областям, равны нулю и не должны учитываться. Площадь двух зеленых квадратов равна . Поскольку выборки, соответствующие этим квадратам, не должны учитываться (они все равны нулю), общая плотность выборки уменьшается с выборок на единицу площади до выборок на единицу площади. 1 × 2 {\displaystyle 1\times 2} 32 {\displaystyle 32} 32 {\displaystyle 32} 32 {\displaystyle 32} 2 / 32 = 1 / 16 = 0,0625 {\displaystyle 2/32=1/16=0,0625} 2 {\displaystyle 2} 2 − 0,0625 = 1.9375 {\displaystyle 2-0.0625=1,9375}

Рисунок 4: Снижение плотности отбора проб: красные точки — это места, где нет необходимости брать пробы.

Соответствующее снижение плотности выборки показано на рисунке 4, где красные точки — это места, где образцы брать не нужно. Отдельная ячейка, содержащая одну красную точку, показана затененной. Площадь ячейки составляет Соответствующее снижение плотности выборки показано на рисунке 4, где красные точки — это места, где образцы брать не нужно. Отдельная ячейка, содержащая одну красную точку, показана затененной. Площадь ячейки составляет единиц. Таким образом, плотность выборки, как также видно из площадей двух зеленых квадратов на рисунке 3, уменьшается на количество образцов на единицу площади. 16 {\displaystyle 16} 1 / 16 {\displaystyle 1/16}

Расширение

В предыдущем примере квадраты на рисунке 3 можно сделать произвольно малыми и увеличить их число так, чтобы асимптотически покрыть всю область, равную нулю. Таким образом, плотность выборки можно свести к поддержке спектра, т. е. к области, где спектр не является тождественно равным нулю.

Подход Папулиса-Маркса-Ченга может быть напрямую обобщен на более высокие измерения. Кроме того, геометрия репликации не обязательно должна быть прямоугольной, но может быть любой формой, которая будет замощать всю  плоскость, например параллелограммы и шестиугольники. [10] ( х , у ) {\displaystyle (x,y)}

Более подробное математическое описание подхода Папулиса-Маркса-Ченга доступно в оригинальной статье Маркса и Ченга [4] и их производных работах. [11] [9]

Ссылки

  1. ^ ab Prelee, Matthew A.; Neuhoff, David L. (май 2016 г.). «Многомерная выборка и реконструкция Манхэттена». IEEE Transactions on Information Theory . 62 (5): 2772– 2787. arXiv : 1502.01694 . doi : 10.1109/TIT.2016.2542081 . ISSN  0018-9448. S2CID  3199882.
  2. ^ ab Papoulis, A. (ноябрь 1977 г.). «Обобщенное расширение выборки». IEEE Transactions on Circuits and Systems . 24 (11): 652– 654. doi :10.1109/TCS.1977.1084284. ISSN  0098-4094.
  3. ^ Маркс, Роберт Дж. (1986-02-01). «Зависимость выборки многомерного сигнала при плотностях Найквиста». JOSA A. 3 ( 2): 268– 273. Bibcode : 1986JOSAA...3..268M. doi : 10.1364/JOSAA.3.000268. ISSN  1520-8532.
  4. ^ ab Cheung, Kwan F.; Marks, Robert J. (1990-01-01). «Выборка изображений ниже плотности Найквиста без наложения спектров». JOSA A. 7 ( 1): 92– 105. Bibcode : 1990JOSAA...7...92C. doi : 10.1364/JOSAA.7.000092. ISSN  1520-8532.
  5. ^ Гардос, ТР; Мерсеро, РМ (1991). "КИХ-фильтрация изображений на решетке с периодически удаляемыми образцами". [Труды] ICASSP 91: 1991 Международная конференция по акустике, речи и обработке сигналов . стр. 2873–2876, том 4. doi :10.1109/ICASSP.1991.151002. ISBN 0-7803-0003-3. S2CID  121408946.
  6. ^ Бреслер, И.; Фэн, Пин (1996). "Спектрально-слепая минимальная скорость выборки и реконструкция двумерных многополосных сигналов". Труды 3-й Международной конференции IEEE по обработке изображений . Том 1. С. 701–704, том 1. DOI : 10.1109/ICIP.1996.559595. ISBN 0-7803-3259-8. S2CID  44441155.
  7. ^ Херли, Кормак; Вонг, Пинг Ва; Член, старший (1999). «Дискретизация с минимальной скоростью и реконструкция сигналов с поддержкой произвольной частоты». IEEE Trans. Inform. Theory . 45 (5): 1555– 1564. CiteSeerX 10.1.1.83.8638 . doi :10.1109/18.771158. 
  8. ^ Коэн, Леон (1995). Анализ частоты времени . Энглвуд Клиффс, Нью-Джерси: Prentice Hall PTR. ISBN 0-13-594532-1. OCLC  31516509.
  9. ^ abc Marks, Robert J. II (2009). Справочник по анализу Фурье и его приложениям . Оксфорд: Oxford University Press. ISBN 978-0-19-533592-7. OCLC  227191901.
  10. ^ Даджен, Дэн Э. (1984). Многомерная цифровая обработка сигналов . Рассел М. Мерсеро. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. ISBN 0-13-604959-1. OCLC  9282699.
  11. ^ Cheung, Kwang F. (6 декабря 2012 г.). «Многомерное расширение обобщенного выборочного расширения Папулиса с применением в минимальной плотности выборки». В Marks, Robert J. II (ред.). Advanced Topics in Shannon Sampling and Interpolation Theory . Springer Science & Business Media. ISBN 978-1-4613-9757-1.
Взято с "https://en.wikipedia.org/w/index.php?title=Papoulis-Marks-Cheung_Approach&oldid=1214430838"