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

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

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

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

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

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

Существует огромный объем знаний, касающихся фильтрации дискретизированных сигналов во временной области; фильтры во временной области реализованы в виде фильтров с конечной импульсной характеристикой , где текущая выходная выборка вычисляется как взвешенная сумма предыдущих 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 , еще пара моментов.

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

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

• Mitra Digital Signal Processing - это хорошая книга для изучения (в MATLAB!) Основ дискретного времени, фильтров, преобразований и т. Д., Которые в значительной степени являются обязательными знаниями для создания любых приличных технических алгоритмов.

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

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

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