CUDA, весна 2009, 06 лекция (от 31 марта)

Материал из eSyr's wiki.

Сегодняшняя лекция посвязена нерег. параллелизму, в частности, к обрю цифрю. сигналов.

На самом деле, это большая тема, и здесь лектор хочет рассказать о том, как адаптивные алгоритмы, требующие большого бранчинга и иже, перекладываются на CUDA. Это будет больше расскза об опыте.

Сегодняняя лекция опять будет про обр. изобр. и сигналов.

Начнём с преобр. Фурье.

Преобр. Фурье, его по-разному вводят, лектору нравится опред. через линейный оператор: ... . Сущ. обр. Ф-преобр. Но они сущ., только если вып. опр. условия: если интеграл сходящийся, есть конеч. кол. устр. разрывов и нет неустранимых.

Далле принято говорить о спектре Фурье.

Какие свойства ПФ:

• Сепарабельность. Вероятно, самое важное свойство: если функцию можно разл. как произв. функций независ. аргументов, то ПФ можно считать по отдельности ля каждой
• ПФ для сопр. функции.
• Свойство отражения
• Свойство масштабирования
• Поворот
• Связь свёртки и ПФ: если есть свёртка двух функций, то ПФ их есть просто произв. образов
• ФП произв. есть свёртка
• ФП для оператора. Лапласа
• Фурье — сепарабельная ф-ция

Зачем нам про Фурье знать: потому что мы будем говорить про фильтры. Есть low-pass и high-pass фильтры (высокочаст. и низкочаст. функции). Низкочаст. фильтр ост. только низк. частоты, высокочаст. — толкьо высокие.

ПАрименение низкочаст. фильтра приводит к появл. эффекта Гиббса.

При применении высокочаст. ост. высокие границы и шум.

Шум.

Шум бывает двух видов:

• Аддитивный шум — откл. по яркости/цвету
• Импульсный шум — когда часть информации пропала

Для подавл. имп. шума исп. рангоаые флиьтры:

• У нас есть сигнал, сколько-то отсчётов, выбираем его окрестность и сортируем их, выбираем определённое.
• Медиана — ранговый фильтр с N=0.5 (выбирается серидина)

Далее, сканируем гистограмму (гист. разбю на bean(?)'ы)

Рассм. реализацию:

• Выдаём каждому локу по куску сигнала
• Подгружаем кусок с фартуком в shmem
• Для каждого элемента строится маленький вектор, маленькая гистограмма. Таких векторов столько же, сколько потоков

Размытие — low-pass фильтр. Любое размытие удаляет высокие частоты. Поэтому при размытии удаляется не только шум, но и массу полезной информации (границы).

Как с этим можно бороться:

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

Идеологич. фильтром является произведение экспонент: считается произв. экспонент, одна расстояние, другая — цветовое расстояние.

Параметр h характеризует шумность картинки. Если её получается оценить для каждого блока, то этим можно пользоваться.

Почему размытие зорошо подавляет шум гауссовый и равномерный? Потому что матожидание такого шума равно нулю.

Изменения в коде по сравнению с гауссианой: минимальны. добавилось вычисление второй экспоненты

Какие можно сделать оптимизации:

• Фильтр не сепарабельный. Тем не менее, его можно разрещать, и делать сначала по столбцам, потом по строкам
• Можно складывать исх. изобр. с фильтрованым. Но хорошо бы считать коэф. окрестности: если много ненудевых, то обл. гладкая и лучше сохр. новое изобр. Если же много нулевых, то лучше исп. пикселы исх. изобр.

Почему плохо будет разб. на блоки 8x8: потому что в полуварпе 8 потоков пишут в одно место, 8 — в другое. В резульатте coalescing вообще не будет.

Так как для каждого кусочка необх. фартук ещё в половину размера. Что тут эффективно использовать? И shmem, и текст. память. Shmem исп. для элементов в блоке, текстурную для остальных, она это быстро хакэширует.

Другая идеология: оцнивать расстояния между блоками. При этом, нетрудно заметить, что для выч. одного веса n*n вычисл, и на фильтрацию — n*n*r*r.

Рассм. след. задачу: масштабирование изображений.

Что такое масштабирование: увелич. изобр., при этом возн. разл. эффекты: гиббс, размытие, алиасинг.

Методы фильтрации:

• Билинейная
• Бикубическая

Адаптивные алгоритмы:

• Расчёт границы в обл. 3*3
• NEDI. Для расчёта исп. лин. комбинация окрестности, причём веса её берутся из ещё большей окрестности. Получается 16 уравнений (окрестность 4*4) и 4 неизвестных, псевдорешение ишется методом минимальных квадратов. Что можно улучшить в NEDI: известны чёрные элементы. Можно попробовать интерп. не один элемент, а 4. Но тогда соотв. шаблон для изв. пикселов может быть слишком весик, поэтому можно попробовать искать вдвое меньший шаблон, получив неизв. значения другим методом интерполирования. Другой вариант — использовать большее количество пикселов и коэфициентов.

Недостатки NEDI: очень медленно работает на ЦПУ. Поскольку на каждвый пиксел произв. умножение матриц 4*16 и обращ. матриц. Казалось бы, хорошая задача для CUDA, но это не совсем так, поск. большой объём данных на тред. Большое количество регистров, сложно использовать shmem, получается много ветвлений.

Можно отправить задание позже, но пока лекторы не решили, что делать с такими людьми.

Втоорое задание — обр. изображений и работа с shmem.