Соответствующее преследование

Сигнал и его вейвлет-представление. Каждый пиксель на тепловой карте (вверху) представляет собой атом (вейвлет, центрированный во времени в соответствии с положением по горизонтали и с частотой, соответствующей высоте). Цвет пикселя дает внутренний продукт соответствующего вейвлет-атома с сигналом (внизу). Согласованное преследование должно представлять сигнал всего нескольких атомов, таких как три в центре четко видимых эллипсов.

Поиск совпадения (MP) - это алгоритм разреженной аппроксимации , который находит «наиболее подходящие» проекции многомерных данных на диапазон сверхполного (т. Е. Избыточного) словаря . Основная идея состоит в том, чтобы приблизительно представить сигнал из гильбертова пространства как взвешенную сумму конечного числа функций (называемых атомами), взятых из . Приближение с атомами имеет вид ${\ displaystyle D}$ ${\ displaystyle f}$ ${\ displaystyle H}$ ${\ displaystyle g _ {\ gamma _ {n}}}$ ${\ displaystyle D}$ ${\ displaystyle N}$

{\ displaystyle f (t) \ приблизительно {\ hat {f}} _ {N} (t): = \ sum _ {n = 1} ^ {N} a_ {n} g _ {\ gamma _ {n}} (t)}

где - й столбец матрицы, а - скалярный весовой коэффициент (амплитуда) для атома . Обычно в этой сумме используется не каждый атом . Вместо этого поиск совпадения выбирает атомы по одному, чтобы максимально (жадно) уменьшить ошибку аппроксимации. Это достигается путем нахождения атома, имеющего наивысший внутренний продукт с сигналом (при условии, что атомы нормализованы), вычитания из сигнала приближения, в котором используется только этот один атом, и повторения процесса до тех пор, пока сигнал не будет удовлетворительно разложен, т. Е. норма невязки мала, где невязка после вычисления и обозначается ${\ displaystyle g _ {\ gamma _ {n}}}$ ${\ displaystyle \ gamma _ {n}}$ ${\ displaystyle D}$ ${\ displaystyle a_ {n}}$ ${\ displaystyle g _ {\ gamma _ {n}}}$ ${\ displaystyle D}$ ${\ displaystyle \ gamma _ {N}}$ $a_{N}$

R_{N+1}=f-{\hat {f}}_{N}

.

Если быстро сходится к нулю, то требуется всего несколько атомов, чтобы получить хорошее приближение . Такие разреженные представления желательны для кодирования и сжатия сигналов. Точнее, проблема разреженности, которую приближенно решает поиск совпадений, имеет вид $R_{n}$ $f$

\min _{x}\|f-Dx\|_{2}^{2}\ {\text{ subject to }}\ \|x\|_{0}\leq N,

где - псевдонорма (т.е. количество ненулевых элементов ). В предыдущих обозначениях ненулевыми элементами являются . Точное решение проблемы разреженности является NP-трудным , поэтому используются методы аппроксимации, такие как MP. $\|x\|_{0}$ $L_{0}$ $x$ $x$ $x_{\gamma _{n}}=a_{n}$

Для сравнения рассмотрим представление сигнала с помощью преобразования Фурье - это можно описать с помощью терминов, приведенных выше, где словарь строится из синусоидальных базисных функций (наименьший возможный полный словарь). Основным недостатком анализа Фурье при обработке сигналов является то, что он извлекает только общие характеристики сигналов и не адаптируется к анализируемым сигналам . Взяв чрезвычайно избыточный словарь, мы можем искать в нем атомы (функции), которые лучше всего соответствуют сигналу . $f$ $f$

Алгоритм [ править ]

Пример извлечения неизвестного сигнала (серая линия) из нескольких измерений (черные точки) с использованием алгоритма поиска по ортогональному совпадению (фиолетовые точки показывают извлеченные коэффициенты).

Если содержит большое количество векторов, поиск наиболее разреженного представления вычислительно неприемлем для практических приложений. В 1993 году Маллат и Чжан ^[1] предложили жадное решение, которое они назвали «Matching Pursuit». Для любого сигнала и любого словаря алгоритм итеративно генерирует отсортированный список индексов атомов и весовых скаляров, которые образуют субоптимальное решение проблемы разреженного представления сигнала. $D$ $f$ $f$ $D$

Поиск совпадения алгоритмов Вход: Сигнал:, словарь с нормализованными столбцами . $f(t)$  $D$  $g_{i}$  Выход: Список коэффициентов и индексов для соответствующих атомов . $(a_{n})_{n=1}^{N}$  $(\gamma _{n})_{n=1}^{N}$  Инициализация:  $R_{1}\,\leftarrow \,f(t)$ ; ; $n\,\leftarrow \,1$  Повторение: Найдите с максимальным внутренним продуктом ; ; ; ; $g_{\gamma _{n}}\in D$  $|\langle R_{n},g_{\gamma _{n}}\rangle |$  $a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle$  $R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}$  $n\,\leftarrow \,n+1$  До остановки состояния (например: ) $\|R_{n}\|<\mathrm {threshold}$  возвращаться

«←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
« return » завершает алгоритм и выводит следующее значение.

В обработке сигналов концепция согласованного преследования связана со статистическим преследованием проекции , в котором обнаруживаются «интересные» проекции; те, которые больше отклоняются от нормального распределения , считаются более интересными.

Свойства [ править ]

Алгоритм сходится (т.е. ) для любого, что находится в пространстве, охватываемом словарем. $R_{n}\to 0$ $f$
Погрешность монотонно уменьшается. $\|R_{n}\|$
Поскольку на каждом шаге невязка ортогональна выбранному фильтру, уравнение сохранения энергии выполняется для каждого : $N$

\|f\|^{2}=\|R_{N+1}\|^{2}+\sum _{n=1}^{N}{|a_{n}|^{2}}

.

В случае, когда векторы в являются ортонормированными, а не избыточными, тогда MP является формой анализа главных компонент. $D$

Приложения [ править ]

Поиск соответствия применялся к кодированию сигналов, изображений ^[2] и видео, ^[3]^[4] представлению и распознаванию форм, ^[5] кодированию трехмерных объектов ^[6] и в междисциплинарных приложениях, таких как мониторинг состояния конструкций. ^[7] Было показано, что оно работает лучше, чем кодирование на основе DCT, для низких скоростей передачи данных как по эффективности кодирования, так и по качеству изображения. ^[8]Основная проблема с поиском соответствия - вычислительная сложность кодировщика. В базовой версии алгоритма поиск в большом словаре нужно искать на каждой итерации. Улучшения включают использование приблизительных словарных представлений и неоптимальных способов выбора наилучшего соответствия на каждой итерации (извлечение атомов). ^[9] Алгоритм согласованного преследования используется в MP / SOFT, методе моделирования квантовой динамики. ^[10]

MP также используется в изучении словарей . ^[11]^[12] В этом алгоритме атомы изучаются из базы данных (как правило, естественные сцены, такие как обычные изображения), а не выбираются из общих словарей.

Расширения [ править ]

Популярным расширением Matching Pursuit (MP) является его ортогональная версия: Orthogonal Matching Pursuit ^[13]^[14] (OMP). Основное отличие от MP состоит в том, что после каждого шага все коэффициенты, извлеченные на данный момент, обновляются путем вычисления ортогональной проекции сигнала на подпространство, охватываемое набором выбранных на данный момент атомов. Это может привести к результатам лучше, чем стандартный MP, но требует больше вычислений. Было показано, что OMP имеет гарантии стабильности и рабочих характеристик при определенных ограниченных условиях изометрии . ^[15]

Такие расширения, как Multichannel MP ^[16] и Multichannel OMP ^[17], позволяют обрабатывать многокомпонентные сигналы. Очевидным расширением Matching Pursuit является использование нескольких позиций и масштабов за счет дополнения словаря до словаря вейвлет-основы. Это можно эффективно сделать с помощью оператора свертки без изменения основного алгоритма. ^[18]

Поиск совпадений связан с областью сжатого зондирования и был расширен исследователями в этом сообществе. Известными расширениями являются ортогональное согласование (OMP), ^[19] поэтапное согласование OMP (StOMP), ^[20] сжатое отслеживание согласования выборки (CoSaMP), ^[21] обобщенное OMP (gOMP), ^[22] и многолучевое согласование (MMP). ^[23]

См. Также [ править ]

ЧИСТЫЙ алгоритм
Анализ главных компонентов (PCA)
Проекционное преследование
Обработка изображений
Обработка сигналов
Разреженное приближение

Ссылки [ править ]

^ Маллат, SG; Чжан, З. (1993). «Сопоставление целей с частотно-временными словарями» . Транзакции IEEE по обработке сигналов . 1993 (12): 3397–3415. Bibcode : 1993ITSP ... 41.3397M . DOI : 10.1109 / 78.258082 .
^ Perrinet, Л. (2015). «Разреженные модели для компьютерного зрения» . Биологически вдохновленное компьютерное зрение . 14 : 319–346. arXiv : 1701.06859 . DOI : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.
^ Bergeaud, F .; Маллат, С. (1995). «Согласованная погоня за изображениями». Proc. Международная конференция по обработке изображений . 1 : 53–56. DOI : 10,1109 / ICIP.1995.529037 . ISBN 978-0-7803-3122-8.
^ Neff, R .; Захор, А. (1997). «Кодирование видео с очень низкой скоростью передачи данных на основе поиска совпадений» . IEEE Transactions on Circuits and Systems for Video Technology . 7 (1): 158–171. DOI : 10.1109 / 76.554427 .
^ Mendels, F .; Vandergheynst, P .; Тиран, JP (2006). «Сопоставление представления формы на основе поиска и распознавания с использованием масштабного пространства» . Международный журнал систем и технологий обработки изображений . 16 (5): 162–180. DOI : 10.1002 / ima.20078 .
^ Тошич, I .; Frossard, P .; Вандергейнст, П. (2005). «Прогрессивное кодирование 3D-объектов на основе сверхполных декомпозиций» . IEEE Transactions on Circuits and Systems for Video Technology . 16 (11): 1338–1349. DOI : 10.1109 / tcsvt.2006.883502 .
^ Чакраборти, Дебеджио; Коввали, Нараян; Вэй, Цзюнь; Папандреу-Супапаппола, Антония; Кокран, Дуглас; Чаттопадхьяй, Адити (2009). «Классификация повреждений Структурный мониторинг состояния в болтовых конструкциях с использованием частотно-временных методов». Журнал интеллектуальных материальных систем и структур . 20 (11): 1289–1305. DOI : 10.1177 / 1045389X08100044 .
^ Perrinet, LU; Samuelides, M .; Торп, С. (2002). «Разреженное кодирование спайков в асинхронной многоуровневой нейронной сети с прямой связью с использованием Matching Pursuit» . Нейрокомпьютеры . 57С : 125–34. DOI : 10.1016 / j.neucom.2004.01.010 .^{[ постоянная мертвая ссылка ]}
^ Линь, Цзянь-Лян; Хван, Вэнь-Лян; Пей, Су-Чанг (2007). «Быстрое согласование и кодирование видео путем объединения словарного приближения и извлечения атомов». IEEE Transactions on Circuits and Systems for Video Technology . 17 (12): 1679–1689. CiteSeerX 10.1.1.671.9670 . DOI : 10.1109 / tcsvt.2007.903120 .
^ Ву, Инхуа; Батиста, Виктор С. (2003). «Согласование-преследование для моделирования квантовых процессов» . J. Chem. Phys . 118 (15): 6720–6724. Bibcode : 2003JChPh.118.6720W . DOI : 10.1063 / 1.1560636 .
^ Perrinet, LP (2010). «Роль гомеостаза в обучении разреженным представлениям» . Нейронные вычисления . 22 (7): 1812–1836. arXiv : 0706.3177 . DOI : 10.1162 / neco.2010.05-08-795 . PMC 2929690 . PMID 20235818 .
^ Aharon, M .; Elad, M .; Брукштейн, AM (2006). "K-SVD: алгоритм проектирования переполненных словарей для разреженного представления". Транзакции IEEE по обработке сигналов . 54 (11): 4311–4322. Bibcode : 2006ITSP ... 54.4311A . DOI : 10.1109 / tsp.2006.881199 .
^ Пати, Y .; Rezaiifar, R .; Кришнапрасад, П. (1993). «Ортогональное согласование: приближение рекурсивной функции с применением к вейвлет-разложению». Asilomar Conf. О сигналах, системах и вычислениях : 40–44. CiteSeerX 10.1.1.348.5735 . DOI : 10,1109 / acssc.1993.342465 . ISBN 978-0-8186-4120-6.
^ Дэвис, G .; Маллат, S .; Чжан, З. (1994). «Адаптивные частотно-временные разложения с поиском согласования». Оптическая инженерия . 33 (7): 2183. Bibcode : 1994OptEn..33.2183D . DOI : 10.1117 / 12.173207 .
^ Дин, Дж .; Chen, L .; Гу, Ю. (2013). "Анализ возмущений поиска ортогонального согласования" . Транзакции IEEE по обработке сигналов . 61 (2): 398–410. arXiv : 1106.3373 . DOI : 10.1109 / TSP.2012.2222377 . ISSN 1941-0476 .
^ "Кусочно-линейное разделение источников", R. Gribonval, Proc. SPIE '03, 2003 г.
^ Тропп, Джоэл ; Гилберт, А .; Штраус, М. (2006). "Алгоритмы одновременных разреженных приближений; Часть I: Жадное преследование". Сигнал Proc. - Разреженные приближения в обработке сигналов и изображений . 86 (3): 572–588. DOI : 10.1016 / j.sigpro.2005.05.030 .
^ Perrinet, Лоран У. (2015). «Разреженные модели для компьютерного зрения». Биологически вдохновленное компьютерное зрение . С. 319–346. arXiv : 1701.06859 . DOI : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.
^ Тропп, Джоэл А .; Гилберт, Анна К. (2007). "Восстановление сигнала из случайных измерений с помощью ортогонального согласования" (PDF) . IEEE Transactions по теории информации . 53 (12): 4655–4666. DOI : 10,1109 / tit.2007.909108 .
^ Донохо, Дэвид Л .; Цайг, Яаков; Дрори, Иддо; Жан-люк, Старк (2006). «Разреженное решение недоопределенных линейных уравнений путем поэтапного поиска ортогонального согласования» . IEEE Transactions по теории информации . 58 (2): 1094–1121. DOI : 10,1109 / tit.2011.2173241 .
^ Needell, D .; Тропп, Дж. А. (2009). «CoSaMP: Итеративное восстановление сигнала из неполных и неточных выборок». Прикладной и вычислительный гармонический анализ . 26 (3): 301–321. arXiv : 0803.2392 . DOI : 10.1016 / j.acha.2008.07.002 .
^ Wang, J .; Kwon, S .; Шим, Б. (2012). «Обобщенное ортогональное согласование». Транзакции IEEE по обработке сигналов . 60 (12): 6202–6216. arXiv : 1111.6664 . Bibcode : 2012ITSP ... 60.6202J . DOI : 10.1109 / TSP.2012.2218810 .
^ Kwon, S .; Wang, J .; Шим, Б. (2014). «Преследование с многолучевым согласованием». IEEE Transactions по теории информации . 60 (5): 2986–3001. arXiv : 1308,4791 . DOI : 10.1109 / TIT.2014.2310482 .

[Mallat1993-1] Маллат, SG; Чжан, З. (1993). «Сопоставление целей с частотно-временными словарями» . Транзакции IEEE по обработке сигналов . 1993 (12): 3397–3415. Bibcode : 1993ITSP ... 41.3397M . DOI : 10.1109 / 78.258082 .

[Perrinet15sparse-2] Perrinet, Л. (2015). «Разреженные модели для компьютерного зрения» . Биологически вдохновленное компьютерное зрение . 14 : 319–346. arXiv : 1701.06859 . DOI : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.

[Mallat1995-3] Bergeaud, F .; Маллат, С. (1995). «Согласованная погоня за изображениями». Proc. Международная конференция по обработке изображений . 1 : 53–56. DOI : 10,1109 / ICIP.1995.529037 . ISBN 978-0-7803-3122-8.

[Neff1997-4] Neff, R .; Захор, А. (1997). «Кодирование видео с очень низкой скоростью передачи данных на основе поиска совпадений» . IEEE Transactions on Circuits and Systems for Video Technology . 7 (1): 158–171. DOI : 10.1109 / 76.554427 .

[Mendels2006-5] Mendels, F .; Vandergheynst, P .; Тиран, JP (2006). «Сопоставление представления формы на основе поиска и распознавания с использованием масштабного пространства» . Международный журнал систем и технологий обработки изображений . 16 (5): 162–180. DOI : 10.1002 / ima.20078 .

[Frossard2005-6] Тошич, I .; Frossard, P .; Вандергейнст, П. (2005). «Прогрессивное кодирование 3D-объектов на основе сверхполных декомпозиций» . IEEE Transactions on Circuits and Systems for Video Technology . 16 (11): 1338–1349. DOI : 10.1109 / tcsvt.2006.883502 .

[debejyo2009-7] Чакраборти, Дебеджио; Коввали, Нараян; Вэй, Цзюнь; Папандреу-Супапаппола, Антония; Кокран, Дуглас; Чаттопадхьяй, Адити (2009). «Классификация повреждений Структурный мониторинг состояния в болтовых конструкциях с использованием частотно-временных методов». Журнал интеллектуальных материальных систем и структур . 20 (11): 1289–1305. DOI : 10.1177 / 1045389X08100044 .

[Perrinet2002-8] Perrinet, LU; Samuelides, M .; Торп, С. (2002). «Разреженное кодирование спайков в асинхронной многоуровневой нейронной сети с прямой связью с использованием Matching Pursuit» . Нейрокомпьютеры . 57С : 125–34. DOI : 10.1016 / j.neucom.2004.01.010 .^{[ постоянная мертвая ссылка ]}

[Lin2007-9] Линь, Цзянь-Лян; Хван, Вэнь-Лян; Пей, Су-Чанг (2007). «Быстрое согласование и кодирование видео путем объединения словарного приближения и извлечения атомов». IEEE Transactions on Circuits and Systems for Video Technology . 17 (12): 1679–1689. CiteSeerX 10.1.1.671.9670 . DOI : 10.1109 / tcsvt.2007.903120 .

[10] Ву, Инхуа; Батиста, Виктор С. (2003). «Согласование-преследование для моделирования квантовых процессов» . J. Chem. Phys . 118 (15): 6720–6724. Bibcode : 2003JChPh.118.6720W . DOI : 10.1063 / 1.1560636 .

[11] Perrinet, LP (2010). «Роль гомеостаза в обучении разреженным представлениям» . Нейронные вычисления . 22 (7): 1812–1836. arXiv : 0706.3177 . DOI : 10.1162 / neco.2010.05-08-795 . PMC 2929690 . PMID 20235818 .

[12] Aharon, M .; Elad, M .; Брукштейн, AM (2006). "K-SVD: алгоритм проектирования переполненных словарей для разреженного представления". Транзакции IEEE по обработке сигналов . 54 (11): 4311–4322. Bibcode : 2006ITSP ... 54.4311A . DOI : 10.1109 / tsp.2006.881199 .

[13] Пати, Y .; Rezaiifar, R .; Кришнапрасад, П. (1993). «Ортогональное согласование: приближение рекурсивной функции с применением к вейвлет-разложению». Asilomar Conf. О сигналах, системах и вычислениях : 40–44. CiteSeerX 10.1.1.348.5735 . DOI : 10,1109 / acssc.1993.342465 . ISBN 978-0-8186-4120-6.

[14] Дэвис, G .; Маллат, S .; Чжан, З. (1994). «Адаптивные частотно-временные разложения с поиском согласования». Оптическая инженерия . 33 (7): 2183. Bibcode : 1994OptEn..33.2183D . DOI : 10.1117 / 12.173207 .

[15] Дин, Дж .; Chen, L .; Гу, Ю. (2013). "Анализ возмущений поиска ортогонального согласования" . Транзакции IEEE по обработке сигналов . 61 (2): 398–410. arXiv : 1106.3373 . DOI : 10.1109 / TSP.2012.2222377 . ISSN 1941-0476 .

[16] "Кусочно-линейное разделение источников", R. Gribonval, Proc. SPIE '03, 2003 г.

[17] Тропп, Джоэл ; Гилберт, А .; Штраус, М. (2006). "Алгоритмы одновременных разреженных приближений; Часть I: Жадное преследование". Сигнал Proc. - Разреженные приближения в обработке сигналов и изображений . 86 (3): 572–588. DOI : 10.1016 / j.sigpro.2005.05.030 .

[18] Perrinet, Лоран У. (2015). «Разреженные модели для компьютерного зрения». Биологически вдохновленное компьютерное зрение . С. 319–346. arXiv : 1701.06859 . DOI : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.

[19] Тропп, Джоэл А .; Гилберт, Анна К. (2007). "Восстановление сигнала из случайных измерений с помощью ортогонального согласования" (PDF) . IEEE Transactions по теории информации . 53 (12): 4655–4666. DOI : 10,1109 / tit.2007.909108 .

[20] Донохо, Дэвид Л .; Цайг, Яаков; Дрори, Иддо; Жан-люк, Старк (2006). «Разреженное решение недоопределенных линейных уравнений путем поэтапного поиска ортогонального согласования» . IEEE Transactions по теории информации . 58 (2): 1094–1121. DOI : 10,1109 / tit.2011.2173241 .

[21] Needell, D .; Тропп, Дж. А. (2009). «CoSaMP: Итеративное восстановление сигнала из неполных и неточных выборок». Прикладной и вычислительный гармонический анализ . 26 (3): 301–321. arXiv : 0803.2392 . DOI : 10.1016 / j.acha.2008.07.002 .

[22] Wang, J .; Kwon, S .; Шим, Б. (2012). «Обобщенное ортогональное согласование». Транзакции IEEE по обработке сигналов . 60 (12): 6202–6216. arXiv : 1111.6664 . Bibcode : 2012ITSP ... 60.6202J . DOI : 10.1109 / TSP.2012.2218810 .

[23] Kwon, S .; Wang, J .; Шим, Б. (2014). «Преследование с многолучевым согласованием». IEEE Transactions по теории информации . 60 (5): 2986–3001. arXiv : 1308,4791 . DOI : 10.1109 / TIT.2014.2310482 .

[1]