Что такое преобразование Уолша-Адамара и для чего оно хорошо?

19

Я пытаюсь научить себя о WHT, но, кажется, нигде в Интернете не так много хороших объяснений. Я думаю, что выяснил, как рассчитать WHT, но я действительно пытаюсь понять, почему он считается полезным в области распознавания изображений.

Что такого особенного в этом, и какие свойства он проявляет в сигнале, который не обнаруживается при классических преобразованиях Фурье или других вейвлет-преобразованиях? Почему это полезно для распознавания объектов, как указано здесь ?

ошалевший
источник
Одним из приложений являются измерительные системы, которые используют последовательности максимальной длины (MLS) в качестве возбуждения (например, mlssa.com ). Это должно быть быстрее, так как не требуется умножения. На практике это не так уж много пользы, и у MLS есть другие проблемы
Хильмар
@DilipSarwate Почему WHT полезен и / или уникален?
Спейси

Ответы:

11

НАСА использовало преобразование Адамара в качестве основы для сжатия фотографий с межпланетных зондов в 1960-х и начале 70-х годов. Адамар является в вычислительном отношении более простой заменой преобразования Фурье, поскольку он не требует операций умножения или деления (все факторы плюс или минус один). Операции умножения и деления были чрезвычайно трудоемкими на небольших компьютерах, используемых на борту этих космических кораблей, поэтому их избегание было выгодно как с точки зрения времени вычислений, так и с точки зрения потребления энергии. Но поскольку разработка более быстрых компьютеров, включающих множители одного цикла, и совершенствование новых алгоритмов, таких как быстрое преобразование Фурье, а также разработка JPEG, MPEG и других методов сжатия изображений, я считаю, что Адамар вышел из употребления. Тем не мение, Я понимаю, что это может быть возвращение для использования в квантовых вычислениях. (Использование НАСА взято из старой статьи в Технических сводках НАСА; точная атрибуция недоступна.)

Эрик Питерс
источник
Фантастический исторический рассказ, мистер Питерс, спасибо вам за это. Можете ли вы подробнее рассказать о том, что / как вы имеете в виду, что это может привести к возвращению в квантовых вычислениях? Как вы намекаете на это в своем посте?
Спейси
Согласно статье в Википедии, многие квантовые алгоритмы используют преобразование Адамара в качестве начального шага, поскольку оно отображает n кубитов в суперпозицию всех 2n ортогональных состояний в квантовом базисе с равным весом.
Эрик Питерс
Эрик, можешь дать ссылку на цитируемую статью в Википедии? Если вы это сделаете, я могу принять ваш ответ.
Спейси
Конечно. Это en.wikipedia.org/wiki/Hadamard_transform
Эрик Питерс
Эрик, я думал, что это был другой источник, о котором ты говорил. Никогда не мой. :-)
Спейси
7

Все коэффициенты преобразования Адамара равны +1 или -1. Быстрое преобразование Адамара может быть сведено к операциям сложения и вычитания (без деления или умножения). Это позволяет использовать более простое оборудование для расчета преобразования.

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

Хан
источник
1
Спасибо за ответ, но я хотел бы понять преобразование, пожалуйста? Меня сейчас не волнует быстрое внедрение. Что это за трансформация? Почему это полезно? Какую информацию он дает нам против других вейвлет-преобразований?
Спейси
5

Посмотрите на этот документ, если у вас есть доступ, я вставил здесь реферат Pratt, WK; Кейн, Дж .; Эндрюс, ХК; "Кодирование изображений с помощью преобразования Адамара", Слушания IEEE, т.57, № 1, с. 58-68, январь 1969 г., doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp /stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Аннотация Введение алгоритма быстрого преобразования Фурье привело к разработке метода кодирования изображений с преобразованием Фурье, в соответствии с которым двумерное преобразование Фурье изображения передается по каналу, а не по самому изображению. Это отклонение также привело к технологии кодирования связанных изображений, в которой изображение преобразуется матричным оператором Адамара. Матрица Адамара - это квадратный массив плюсов и минусов, строки и столбцы которого ортогональны друг другу. Был разработан высокоскоростной вычислительный алгоритм, аналогичный алгоритму быстрого преобразования Фурье, который выполняет преобразование Адамара. Поскольку при преобразовании Адамара требуются только вещественные сложения и вычитания, преимущество в скорости на порядок можно сравнить с преобразованием Фурье комплексного числа.

Charna
источник
Спасибо за эту ссылку, я обязательно прочитаю ее, но это может занять некоторое время. Просто из резюме кажется, что преобразование Адамара можно использовать как ... замену? ... для преобразования Фурье, отчасти потому, что оно очень эффективно в вычислительном отношении, но, возможно, и по другой причине? Каково было ваше общее мнение об этом?
Спейси
Используя преобразование Адамара, мы можем передать кодированную версию изображения и затем восстановить ее в приемнике. В этом конкретном случае автор использует преобразование для того, чтобы сконцентрировать энергию сигнала в более узкой полосе, чем исходное изображение, поэтому на него меньше влияют шумы, и его можно восстановить, используя обратный гадамард в приемнике.
Чарна
Хм, да, я только что закончил читать статью - похоже, преобразование Адамара - просто более быстрая альтернатива преобразованию Фурье, но больше ничего не выделяется. Это экономит энергию, энтропию и т. Д., Но более или менее похоже на БПФ.
Спейси
Достаточно ли хорошо работает преобразование Адамара (даже если не лучше) против других преобразований, таких как DFT или даже DCT? Быть быстрым - это хорошо, но может ли оно действительно обеспечить такое же хорошее сжатие, как, скажем, DCT - настоящий вопрос. Большинство обычных стандартов JPEG, MPEGx не совсем используют его, кстати.
Дипан Мехта
2

Хотелось бы добавить, что любое m-преобразование (матрица Теплица, генерируемое m-последовательностью) может быть разложено на

P1 * WHT * P2

где WHT - преобразование Уолша-Адамара, P1 и P2 - перестановки (ссылка: http://dl.acm.org/citation.cfm?id=114749 ).

m-преобразование используется для ряда вещей: (1) идентификация системы, когда система поражена шумом, и (2) виртуальным из (1) определение фазового отставания в системе, которая поражена шумом

для (1) m-преобразование восстанавливает ядро ​​(я) системы, когда стимул представляет собой m-последовательность, что полезно в нейрофизиологии (например, http://jn.physiology.org/content/99/1/367. полный и другие), потому что это высокая мощность для широкополосного сигнала.

Для (2), код Голда построен из m-последовательностей (http://en.wikipedia.org/wiki/Gold_code).

Тханг
источник
1

Я очень рад, что стал свидетелем возрождения вокруг преобразований Уолша-Пэли-Адамара (или иногда его называют Вейлимардом), см. Как мы можем использовать преобразование Адамара при извлечении объектов из изображения?

Они являются экземплярами функций Радемахера. Они формируют ортогональные преобразования, которые, без нормализации мощности, могут быть реализованы только с добавлением и вычитанием и, возможно, с двоичными сдвигами. Векторные коэффициенты составлены из , которые имитируют бинаризованную версию основ синуса или косинуса. Порядок векторов Уолша находится в последовательности (а не в частоте), которая подсчитывает количество изменений знака. Им нравятся похожие алгоритмы-бабочки для еще более быстрой реализации.±1

Последовательности Уолша длиной также можно интерпретировать как экземпляры вейвлет-пакета Хаара.2n

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

Их производительность часто считается хуже, чем у других гармонических преобразований на естественных сигналах и изображениях, из-за их блочной природы. Однако некоторые варианты все еще используются, например, для обратимых преобразований цвета (RCT) или преобразований видеокодирования с низкой сложностью (преобразование с низкой сложностью и квантование в H.264 / AVC ).

Немного литературы:

Лоран Дюваль
источник
-2

Некоторые ссылки: веб-страница

Общее описание

Для гауссовского распределения

отчет

Шон О'Коннор
источник
Будет лучше, если вы сможете объяснить, почему каждая ссылка хороша. Даже полное название связанного документа было бы лучше.
Питер К.
Я пытался, но программное обеспечение форума выходило из строя, поэтому вы получаете сводную версию. Если вы хотите в стиле вики-полиции удалить все, обязательно делайте.
Шон О'Коннор,
Я не думаю, что в данном случае это такая «вики-политика», как попытка поддерживать стандарт формата вопросов и ответов на этой доске. Его цель - не функционировать как форум. Таким образом, отзывы о вашем вкладе касаются не удаления, а принятия его на борт, а также проверки его соответствия стандарту. Это распространено в сети обмена стека. Я думаю, что стоит редактировать пост.
A_A