Реализация алгоритмов технических работ на C ++ или MATLAB

14

Я студент электротехники. Я читал много технических статей об алгоритмах обработки сигналов и изображений (реконструкция, сегментация, фильтрация и т. Д.). Большинство алгоритмов, показанных в этих статьях, определены для непрерывного времени и непрерывной частоты, и часто дают решения в терминах сложных уравнений. Как бы вы внедрили технический документ с нуля в C ++ или MATLAB, чтобы повторить результаты, полученные в указанном документе?

Более конкретно, я смотрел на статью «Общий алгоритм восстановления конусных лучей» Ван и др. ( IEEE Trans Med Imaging. 1993; 12 (3): 486-96 ), и мне было интересно, как мне вообще начать реализует их алгоритм? Уравнение 10 дает вам формулу восстановленного изображения в. Как бы вы это написали? Будет ли у вас цикл for, проходящий через каждый воксель и вычисляющий соответствующую формулу? Как бы вы закодировали функции функций в этой формуле? Как бы вы оценили функции в произвольных точках?

Я прочитал книгу «Цифровая обработка изображений» Гонсалеса и Вудса, но все еще в растерянности. Я также читал о серии книг «Численные рецепты». Будет ли это правильный путь?

Каков ваш опыт программирования алгоритмов из исследовательских работ? Любые советы или предложения?

Damian
источник
1
Я посмотрю на газету, когда у меня будет шанс. Но я считаю, что это все о точках XYZ на данном графике. Вы определяете вершину, а затем работаете оттуда.
2
Как правило, дискретизируют сигналы путем выборки, а затем преобразуют интегралы в суммы.
nibot
Итак, я читал о выборке и преобразовании интегралов в суммы, но как вы оцениваете подынтегральное выражение в каждой точке выборки, если функции в подынтегральном выражении хранятся в виде матриц?
1
Дамиан, ты видел, как преобразование радона инвертируется с помощью обратной проекции? Это немного более простой пример, который я мог бы объяснить, если он заинтересует вас. Он используется для томографии с использованием плоских волн, а не конической выборки, описанной в опубликованной вами статье. en.wikipedia.org/wiki/Radon_transform
нибот
1
@ mr-crt, можно ли вместо этого перейти на dsp.SE?
nibot

Ответы:

15

Алгоритмы обработки сигналов, определенные в непрерывном времени / пространстве / частоте, обычно реализуются путем выборки сигнала на дискретной сетке и преобразования интегралов в суммы (и производные в разности). Пространственные фильтры реализуются посредством свертки с ядром свертки (то есть взвешенной суммой соседей).

Существует огромный объем знаний, касающихся фильтрации дискретизированных сигналов во временной области; фильтры во временной области реализованы в виде фильтров с конечной импульсной характеристикой , где текущая выходная выборка вычисляется как взвешенная сумма предыдущих N входных выборок; или фильтры с бесконечной импульсной характеристикой, где токовый выход является взвешенной суммой предыдущих входов и предыдущих выходов . Формально фильтры дискретного времени описываются с использованием z-преобразования , которое является аналогом дискретного времени преобразования Лапласа . Билинейное преобразование отображает один к другим ( c2dи d2cв Matlab).

Как бы вы оценили функции в произвольных точках?

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

В Matlab вы можете использовать interp1или interp2для интерполяции 1D или 2D-данных с регулярной выборкой (соответственно), или griddataдля интерполяции 2D-данных с нерегулярной выборкой.

Будет ли у вас цикл for, проходящий через каждый воксель и вычисляющий соответствующую формулу?

Да, точно.

Matlab избавляет вас от необходимости делать это через явные циклы for, потому что он предназначен для работы с матрицами и векторами (то есть многомерными массивами). В Matlab это называется «векторизация». Определённые интегралы могут быть аппроксимированы sum, cumsum, trapz, cumtrapzи т.д.

Я прочитал книгу «Цифровая обработка изображений» Гонсалеса и Вудса, но все еще в растерянности. Я также читал о серии книг «Численные рецепты». Будет ли это правильный путь?

Да, Численные Рецепты были бы отличным началом. Это очень практично и охватывает большинство численных методов, которые вам в конечном итоге понадобятся. (Вы обнаружите, что Matlab уже реализует все, что вам нужно, но Числовые Рецепты обеспечат отличную подготовку.)

Я взял класс «алгоритмы и структуры данных», но не вижу связи между представленным там материалом и реализацией научных алгоритмов.

Материал, рассматриваемый в курсах «Алгоритмы и структуры данных», имеет тенденцию концентрироваться на таких структурах, как списки, массивы, деревья и графики, содержащие целые числа или строки, а также операции, такие как сортировка и выбор: проблемы, для которых обычно существует единственный правильный результат. Когда дело доходит до научных алгоритмов, это только половина истории. Другая половина касается методов оценки действительных чисел и аналитических функций. Вы найдете это в курсе «Численные методы» (или «Численный анализ»; например, этот).- прокрутите вниз для слайдов): как оценивать специальные функции, как оценивать интегралы и производные и т. д. Здесь одна из основных задач - оценить точность вашего результата, а один общий шаблон - повторять процедуру, которая улучшает оценивать, пока оно не станет достаточно точным. (Вы можете спросить себя, как Matlab знает, как сделать что-то столь же простое, как оценить значение sin(x)для некоторых x.)


В качестве простого примера приведу короткий скрипт, который вычисляет радоновое преобразование изображения в Matlab. Радоновое преобразование принимает проекции изображения на множество углов проекции. Вместо того, чтобы пытаться вычислить проекцию вдоль произвольного угла, я вместо этого поворачиваю все изображение, используя imrotate, чтобы проекция всегда была вертикальной. Тогда мы можем взять проекцию, просто используя sum, поскольку sumматрица возвращает вектор, содержащий сумму по каждому столбцу.

Вы можете написать свой собственный, imrotateесли хотите, используя interp2.

%%# Home-made Radon Tranform

%# load a density map (image).  
A = phantom;

n_pixels = size(A, 1);  %# image width (assume square)

%# At what rotation angles do we want to take projections?
n_thetas = 101;
thetas = linspace(0, 180, n_thetas);

result = zeros(n_thetas, n_pixels);

%# Loop over angles
for ii=1:length(thetas)
    theta = thetas(ii);
    rotated_image = imrotate(A, theta, 'crop');
    result(ii, :) = sum(rotated_image);
end

%# display the result
imagesc(thetas, 1:n_pixels, result.');
xlabel('projection angle [degrees]');

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

nibot
источник
Вау @nibot, спасибо за такой подробный ответ. Я взял класс «алгоритмы и структуры данных», но не вижу связи между представленным там материалом и реализацией научных алгоритмов. Я прочитаю ссылки, которые вы мне дали, и начну практиковаться с более простыми алгоритмами (из книг вместо бумаг). Еще раз спасибо
Дамиан
Привет, Дамиан, я отредактировал свой ответ на свой комментарий. Я думаю, что вы найдете то, что вы ищете в курсе или книге о численных методах / численном анализе.
нибот
На протяжении всего ответа!
Виктор Сорокин
@nibot: спасибо за редактирование. Мне очень нравится курс численного анализа, который вы связали. Почему «фильтры с конечной импульсной характеристикой» связаны с интерполяцией? Интересно, почему это не является частью учебной программы для студентов EE. Ну что ж. Благодарность!
Дамиан
@Damian: теория выборки, интерполяция / децимация, Z-преобразования, билинейное преобразование и фильтры FIR / IIR преподаются в классах / лабораториях EE студентов, таких как сигналы и системы, системы связи, линейные системы управления и введение в DSP. Я взял численные методы как часть программы двойного диплома в компьютерной инженерии; Я не думаю, что это должно требоваться от ЭЭ в целом.
Eryk Sun
3

В добавление к отличному объяснению nibot , еще пара моментов.

  • Среды числовых вычислений, такие как MATLAB, Octave или SciPy / NumPy, сэкономят вам много усилий по сравнению с выполнением всего этого самостоятельно на общем языке программирования, таком как C ++. Жонглирование doubleмассивами и циклами просто не сравнить с наличием типов данных, таких как комплексные числа, и операций, таких как интегралы, у вас под рукой. (Это точно выполнимо, и хороший код на C ++ может быть на порядок быстрее, с хорошими абстракциями и шаблонами библиотеки он может быть даже достаточно чистым и понятным, но определенно легче начать, например, с MATLAB.)

  • MATLAB также имеет «инструментарии» для , например , обработки изображений и цифровой обработки сигналов , которые могут помочь много, в зависимости от того, что вы делаете.

  • Mitra Digital Signal Processing - это хорошая книга для изучения (в MATLAB!) Основ дискретного времени, фильтров, преобразований и т. Д., Которые в значительной степени являются обязательными знаниями для создания любых приличных технических алгоритмов.
Joonas Pulakka
источник
Да, я прочитал документацию Toolboox для обработки изображений. Я кажется чрезвычайно полезным, но мой вопрос был направлен на реализацию чего-то подобного. По сути, я хотел знать, как взять математический алгоритм / формулу и реализовать его (как Mathworks сделал с IPT). Я хотел знать о шаблоне мышления или некоторых руководящих принципах. Я посмотрю на книгу Митры. Благодарность!
Дамиан
1
Чтобы добавить ответ к вышеприведенному ответу, инструментарий C ++, такой как Armadillo, может значительно упростить преобразование кода Matlab в быстрый код C ++. Синтаксис броненосца похож на Matlab. Вы также можете смешивать коды Matlab и C ++ с помощью mex-интерфейса Armadillo.
mtall
2

Численные методы. Обычно это университетский курс высшего образования и учебник.

DSP обычно находится вблизи пересечения численных методов и эффективной реализации. Если вы игнорируете эффективность, то вам может понадобиться любой метод численного приближения, который может дать «достаточно точный» результат для интересующего уравнения технической статьи. Иногда можно иметь дело с выборочными данными, где теоремы выборки наложат некоторые ограничения как на метод сбора данных (предварительная фильтрация), так и на диапазон или качество результатов, которые вы можете получить, учитывая эти данные.

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

hotpaw2
источник