Минимизация вычислений в алгоритме объемной реконструкции
При реализации обратного проецирования в алгоритме объемной реконструкции предложено использовать предварительную интерполяцию свернутых проекционных данных. Приведены результаты анализа сложности реализации различных способов интерполяции, дана оценка погрешности из-за наличия в спектре сигнала сос...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2008
|
| Назва видання: | Реєстрація, зберігання і обробка даних |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/7543 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Минимизация вычислений в алгоритме объемной реконструкции / А.И. Закидальский // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 44-48. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-7543 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-75432025-02-23T18:09:02Z Минимизация вычислений в алгоритме объемной реконструкции Мінімізація обчислень в алгоритмі об'ємної реконструкції Minimization of Calculations in the Algorithm of Volume Reconstruction Закидальский, А.И. Математичні методи обробки даних При реализации обратного проецирования в алгоритме объемной реконструкции предложено использовать предварительную интерполяцию свернутых проекционных данных. Приведены результаты анализа сложности реализации различных способов интерполяции, дана оценка погрешности из-за наличия в спектре сигнала составляющих выше частоты Найквиста. Предложено использовать усеченную sinc-интерполяцию с окном Ланцоша, обеспечить точность, сравнимую с интерполяцией на основе быстрого преобразования Фурье, но на порядок меньшей вычислительной сложности. Запропоновано при реалізації зворотного проектування в алгоритмі об’ємної реконструкції використовувати попередню інтерполяцію згорнутих проекційних даних. Наведено результати аналізу складності реалізації різних способів інтерполяції, дано оцінку похибки із-за наявності в спектрі сигналу складових з частотою, що вища за частоту Найквіста. Запропоновано використовувати скорочену sink-інтерполяцію з вікном Ланцоша, забезпечити точність, порівнянну з точністю інтерполяції на основі швидкого перетворення Фур’є, але на порядок меншої обчислювальної складності. It is suggested to use preliminary interpolation of convolute projection data during realization of inverted projection in the algorithm of volume reconstruction. Analysis results of difficulty of different ways for interpolation realization are prеsented, the estimation of error because of presence in the spectrum of a signal of constituents higher than Nyquist frequency is given. It is suggested to use the truncated sinc-interpolation with Lanczos window, to provide exactness comparable with interpolation on the basis of the fast Fourier transform, but with computational complexity by an order lesser. 2008 Article Минимизация вычислений в алгоритме объемной реконструкции / А.И. Закидальский // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 44-48. — Бібліогр.: 4 назв. — рос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/7543 519.68; 620.179.15; 681.3 ru Реєстрація, зберігання і обробка даних application/pdf Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Закидальский, А.И. Минимизация вычислений в алгоритме объемной реконструкции Реєстрація, зберігання і обробка даних |
| description |
При реализации обратного проецирования в алгоритме объемной реконструкции предложено использовать предварительную интерполяцию свернутых проекционных данных. Приведены результаты анализа сложности реализации различных способов интерполяции, дана оценка погрешности из-за наличия в спектре сигнала составляющих выше частоты Найквиста. Предложено использовать усеченную sinc-интерполяцию с окном Ланцоша, обеспечить точность, сравнимую с интерполяцией на основе быстрого преобразования Фурье, но на порядок меньшей вычислительной сложности. |
| format |
Article |
| author |
Закидальский, А.И. |
| author_facet |
Закидальский, А.И. |
| author_sort |
Закидальский, А.И. |
| title |
Минимизация вычислений в алгоритме объемной реконструкции |
| title_short |
Минимизация вычислений в алгоритме объемной реконструкции |
| title_full |
Минимизация вычислений в алгоритме объемной реконструкции |
| title_fullStr |
Минимизация вычислений в алгоритме объемной реконструкции |
| title_full_unstemmed |
Минимизация вычислений в алгоритме объемной реконструкции |
| title_sort |
минимизация вычислений в алгоритме объемной реконструкции |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2008 |
| topic_facet |
Математичні методи обробки даних |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/7543 |
| citation_txt |
Минимизация вычислений в алгоритме объемной реконструкции / А.И. Закидальский // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 44-48. — Бібліогр.: 4 назв. — рос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT zakidalʹskijai minimizaciâvyčislenijvalgoritmeobʺemnojrekonstrukcii AT zakidalʹskijai mínímízacíâobčislenʹvalgoritmíobêmnoírekonstrukcíí AT zakidalʹskijai minimizationofcalculationsinthealgorithmofvolumereconstruction |
| first_indexed |
2025-11-24T08:13:30Z |
| last_indexed |
2025-11-24T08:13:30Z |
| _version_ |
1849658714920845312 |
| fulltext |
44
УДК 519.68; 620.179.15; 681.3
А. И. Закидальский
Институт проблем регистрации информации НАН Украины
ул. Н. Шпака, 2, 03113 Киев, Украина
Минимизация вычислений в алгоритме
объемной реконструкции
При реализации обратного проецирования в алгоритме объемной ре-
конструкции предложено использовать предварительную интерполя-
цию свернутых проекционных данных. Приведены результаты анализа
сложности реализации различных способов интерполяции, дана оцен-
ка погрешности из-за наличия в спектре сигнала составляющих выше
частоты Найквиста. Предложено использовать усеченную sinc-ин-
терполяцию с окном Ланцоша, обеспечить точность, сравнимую с
интерполяцией на основе быстрого преобразования Фурье, но на поря-
док меньшей вычислительной сложности.
Ключевые слова: объемная реконструкция, обратное проецирование,
свертка, интерполяция, алгоритм восстановления.
Оценка полных вычислительных затрат приводится к количеству операций с
плавающей точкой, необходимых для вычисления одного вклада. Приведем от-
дельные оценки количества операций на всех этапах реконструкции.
Угол, соответствующий половине углового размера зоны реконструкции,
примем равным 2γmax. Процесс реконструкции состоит из ряда этапов: преобразо-
вания конусных проекционных данных, свертки, интерполяции свернутых проек-
ций и обратного проецирования.
Приведенное значение количества операций на преобразование конусных
проекций зависит от угла охвата объекта сканирующей системой. Для реальных
значений угла они не превышают нескольких сотых долей операции с плавающей
точкой.
Выполнение быстрой свертки с использованием ортогональных преобразова-
ний при реконструкции матриц требует порядка 0,1–0,2 операции с плавающей
точкой. Основные вычислительные затраты связаны с обратным проецированием
и интерполяцией при определении вклада.
При организации вычислений с простейшей интерполяцией во внутреннем
цикле на обратное проецирование потребуется не менее 4-х операций на вклад
(при линейной интерполяции — 2 умножения и 2 сложения).
Использование подробной предварительной интерполяции свернутых проек-
ционных данных позволяет примерно вдвое сократить количество операций во
© А. И. Закидальский
Минимизация вычислений в алгоритме объемной реконструкции
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 45
внутреннем цикле. Кроме того, учитывая небольшие затраты на предварительную
интерполяцию, вместо линейной можно применить более совершенную интерпо-
ляцию по многим точкам. В (1) дается количество операций (на 1 вклад) при ис-
пользовании различных методов интерполяции:
(1)
где q2 — коэффициент интерполяции; p2 — длина последовательности.
В табл. 1 приведены затраты операций на вклад при линейной интерполяции
(clin.int), интерполяции по 2n точкам (c2n.int), а также sinc-интерполяции с использо-
ванием быстрого преобразования Фурье (cFFT.int).
Таблица 1
c2n.intp 2q clin.int
n = 1 n = 2 n = 3
cFFT.int
4 0,005 0,006 0,015 0,023 0,200
8 0,009 0,014 0,034 0,055 0,49310
16 0,017 0,029 0,073 0,117 1,118
Качество предварительной интерполяции свернутых проекций зависит от вида
интерполирующего множителя, ширины требуемого спектра для его реализации.
Как известно, sinc-интерполяция требует наименьшей ширины спектра, одна-
ко она весьма трудоемка в реализации.
Интерполирующий множитель представляет собой четную функцию. Для
действительных сигналов, симметричных относительно вертикальной оси, вычис-
ление спектров можно свести к интегрированию действительных величин:
dtfttdtetfФ ftI
0
2 )2cos()(2)()( . (2)
В случае кусочно-постоянного интерполирующего множителя ( )(t = 1) на
интервале времени t = –Ti/2…Ti/2 частотный спектр, очевидно, равен
f
fTi
dtftfФ
Ti
)sin(
)2cos(2)(
2/
0
. (3)
(Здесь и далее Ti — шаг дискретизации Ti = 1).
Спектр ограниченного по времени сигнала не ограничен по частоте. В каче-
стве примера на рис. 1 представлены спектр (а) и энергия спектра (б) для случая
),13(
2
)12(
,
21
15
2
)12(
,
2
12
int.2
int.
int.
nc
q
pc
c
p
q
n
qp
q
FFT
p
q
lin
А. И. Закидальский
46
одноточечной интерполяции.
Рис. 1
С другой стороны, корректная дискретизация предполагает отсутствие в сиг-
нале гармоник с частотой f ≥ 1/2Ti. Наложение частот приведет к появлению
ошибки интерполяции, величина которой связана с частью энергии спектра за
пределами полосы пропускания (f ≥ 1/2Ti). График энергии (квадрат спектра) при-
веден на рис. 2б. Мерой ошибки может служить относительное значение энергии
спектра за пределами полосы пропускания:
.0
5.0
dfE
dfE
E . (4)
Для одноточечной интерполяции энергия пропорциональна величине
2
)sin(
f
fTi
E
. (5)
Выполнив необходимые преобразования, получим оценку относительной по-
грешности одноточечной интерполяции:
226,0E (6)
Линейная интерполяция. Линейная (двухточечная) интерполяция дает воз-
можность существенно повысить точность представления промежуточных значе-
ний функции по ее дискретным отсчетам. В качестве интерполирующего множи-
теля на интервале времени t = –Ti…Ti используется четная функция вида:
Ti
t
t 1)( . (7)
а) б)
Минимизация вычислений в алгоритме объемной реконструкции
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 47
Тогда, с учетом (2), после интегрирования получим спектр линейного интер-
полирующего множителя:
Tif
Tif
fФ
22
2 )(sin
)(
. (8)
Ниже на рис. 2 представлен спектр (а) и распределение энергии по частоте (б)
для линейного интерполирующего множителя (7).
Рис. 2
Как видно из графика энергии спектра
4
)sin(
f
fTi
E
, вне полосы пропуска-
ния (f > 0,5) сосредоточена сравнительно небольшая ее часть.
Выполнив необходимые преобразования с учетом (4) и (8), получим оценку
относительной погрешности линейной интерполяции:
.051,0E (9)
Окно Дирихле. Sinc-интерполяция. Известно, что спектр интерполирующе-
го множителя вида
Tit
Tit
t
/
/sin
)(
(10)
при неограниченном времени (t >> Ti) ограничен частотой f ≤ 1/2Ti.
При общей длине интерполирующего множителя 2n периодов (|t| = nTi) его
спектр определяется выражением:
TiTifnSiTifnSi
fФ
))12(())12((
)( . (11)
На рис. 3. показаны спектры (а) и энергия спектров (б) sinc(πfTi) при учете 2n
периодов (n = 1, 2, 3, 30, Ti = 1).
а) б)
А. И. Закидальский
48
Рис. 3
В табл. 2 для интерполирующего множителя вида φ(t) = sinc(πt/Ti) приведены
значения «энергии ошибки», полной энергии спектра и величины относительной
погрешности в зависимости от ширины окна Дирихле.
Таблица 2
n en En δ = en/En
1 0,0360 0,9028 0,040
2 0,0208 0,9500 0,022
3 0,0146 0,9664 0,015
30 0,0016 0,9966 0,0016
Примерно такие же результаты для sinc-интерполяции можно получить в
случае применения окна Ланцоша. В отличие от простого усечения sinc-ряда ок-
ном Дирихле, в данном случае при той же вычислительной сложности получается
более гладкая интерполяция.
В заключение отметим целесообразность применения подробной предвари-
тельной интерполяции проекционных данных с применением усеченного sinc-
ряда по 4–6 отсчетам. При этом обеспечивается требуемая точность, и резко сни-
жается приведенное к одному вкладу число операций (с 4 до 2,1) на обратное про-
ецирование.
1. Терновой К.С., Синьков М.В., Закидальский А.И., Яник А.Ф., Тарасенко-Зеленая Л.И. Вве-
дение в современную томографию. ― К.: Наук. думка, 1983. ― 232 с.
2. Ланцош К. Практические методы прикладного анализа / Пер. с англ. / Под ред. А.М. Лоп-
шица. — М.: Гос. изд-во. физ.-мат. лит., 1961 — 524 с.
3. Закидальский А.И. О вопросах развития алгоритмов объемной реконструкции в компью-
терной томографии // Реєстрація, зберігання і оброб. даних. — 2002. — Т. 4, № 4. — С. 30–34.
4. Синьков М.В., Закидальский А.И. Объемная реконструкция «больших» объектов на томо-
графах с ограниченной по размерам матрицей детекторов // Реєстрація, зберігання і оброб. даних.
— 2003. — Т. 5, № 3. — С. 18–25.
Поступила в редакцию 11.03.2008
а)
б)
|