Дискретная томография

Дискретная томография ^[1]^[2] основное внимание уделяется проблеме восстановления бинарных изображений (или конечных подмножеств целочисленной решетки ) по небольшому числу их проекций .

В общем, томография занимается проблемой определения информации о форме и размерах объекта по набору проекций. С математической точки зрения объект соответствует функции , и поставленная задача состоит в том, чтобы восстановить эту функцию по ее интегралам или суммам по подмножествам ее области определения . В общем, задача томографической инверсии может быть непрерывной или дискретной. В непрерывной томографии и область определения, и диапазон функции являются непрерывными, и используются линейные интегралы. В дискретной томографии область определения функции может быть дискретной или непрерывной, а диапазон функции представляет собой конечный набор действительных, обычно неотрицательных чисел. В непрерывной томографии, когда доступно большое количество проекций, точные реконструкции могут быть выполнены с помощью множества различных алгоритмов. Для дискретной томографии характерно использование лишь нескольких проекций (сумм линий). В этом случае все традиционные методы неэффективны. Частный случай дискретной томографии связан с задачей восстановления бинарного изображения по небольшому числу проекций. Имя Дискретная томография связана с Ларри Шеппом , который организовал первую встречу, посвященную этой теме ( DIMACS Mini-Symposium on Discrete Tomography, 19 сентября 1994, Университет Рутгерса ).

Теория

Дискретная томография тесно связана с другими математическими областями, такими как теория чисел , ^[3]^[4]^[5] дискретная математика , ^[6]^[7]^[8] теория сложности вычислений ^[9]^[10] и комбинаторика . ^[11]^[12]^[13] Фактически, ряд задач дискретной томографии впервые обсуждался как комбинаторные задачи. В 1957 году Х. Дж. Райзер нашел необходимое и достаточное условие того, что пара векторов является двумя ортогональными проекциями дискретного множества. В доказательстве своей теоремы Райзер также описал алгоритм реконструкции — самый первый алгоритм восстановления общего дискретного множества по двум ортогональным проекциям. В том же году Дэвид Гейл нашел те же условия согласованности, но в связи с проблемой сетевого потока . ^[14] Другим результатом Райзера является определение операции переключения, с помощью которой дискретные множества, имеющие одинаковые проекции, могут быть преобразованы друг в друга.

Задача восстановления бинарного изображения по небольшому количеству проекций обычно приводит к большому количеству решений. Класс возможных решений желательно ограничить только теми, которые характерны для класса изображений, содержащего восстанавливаемое изображение с использованием априорной информации, такой как выпуклость или связность.

Теоремы

Реконструкция (конечных) плоских решеточных множеств по их одномерным рентгеновским лучам является NP-трудной задачей, если рентгеновские лучи взяты из $m\geq 3$ направления решетки (для $m=2$ проблема в П). ^[9]
Задача реконструкции весьма неустойчива для $m\geq 3$ (это означает, что небольшое возмущение рентгеновских лучей может привести к совершенно другим реконструкциям) ^[15] и стабильный для $m=2$ , видеть. ^[15]^[16]^[17]
Раскраска сетки с помощью $k$ цветов с ограничением, что каждая строка и каждый столбец имеет определенное количество ячеек каждого цвета, называется $(k-1)$ -проблема атома в сообществе дискретной томографии. Задача NP-трудна для $k\geq 3$ , видеть. ^[10]

Дополнительные результаты см. ^[1]^[2]

Алгоритмы

Среди методов реконструкции можно найти методы алгебраической реконструкции (например, DART ^[18]^[19] или ^[20]), жадные алгоритмы (см. ^[21] для гарантий аппроксимации) и алгоритмы Монте-Карло . ^[22]^[23]

Приложения

применяются различные алгоритмы При обработке изображений . ^[18] медицина , проблемы защиты трехмерных статистических данных, компьютерная томография и проектирование, электронная микроскопия ^[24]^[25] и материаловедение , включая микроскоп 3DXRD . ^[22]^[23]^[26]

Форма дискретной томографии также лежит в основе нонограмм — типа логической головоломки , в которой информация о строках и столбцах цифрового изображения используется для восстановления изображения. ^[27]

См. также

Геометрическая томография

Ссылки

^ Jump up to: ^а ^б Герман Г.Т. и Куба А. Дискретная томография: основы, алгоритмы и приложения, Birkhäuser Boston, 1999.
^ Jump up to: ^а ^б Герман Г.Т. и Куба А., Достижения в области дискретной томографии и ее приложений, Birkhäuser Boston, 2007 г.
^ Р. Дж. Гарднер, П. Грицманн, Дискретная томография: определение конечных множеств с помощью рентгеновских лучей, Trans. амер. Математика. Соц. 349 (1997), вып. 6, 2271–2295.
^ Л. Хайду, Р. Тейдеман, Алгебраические аспекты дискретной томографии , Дж. Рейн Ангью. Математика. 534 (2001), 119-128.
^ А. Альперс, Р. Тайдеман, Двумерная проблема Пруэ-Тэрри-Эскотта, Журнал теории чисел, 123 (2), стр. 403-412, 2007 [1] .
^ С. Брунетти, А. Дель Лунго, П. Грицманн, С. де Врис, О восстановлении бинарных матриц и матриц перестановок при (бинарных) томографических ограничениях . Теория. Вычислить. наук. 406 (2008), вып. 1-2, 63-71.
^ А. Альперс, П. Грицманн, О стабильности, исправлении ошибок и компенсации шума в дискретной томографии, SIAM Journal on Discrete Mathematics 20 (1), стр. 227-239, 2006 [2]
^ П. Грицманн, Б. Лангфельд, Об индексе сеток Зигеля и его применении к томографии квазикристаллов. Европейский Дж. Комбин. 29 (2008), вып. 8, 1894–1909.
^ Jump up to: ^а ^б Р. Дж. Гарднер, П. Грицманн, Д. Прангенберг, О вычислительной сложности восстановления решетчатых множеств по их рентгеновским лучам . Дискретная математика. 202 (1999), вып. 1-3, 45-71.
^ Jump up to: ^а ^б К. Дюрр, Ф. Гиньес, М. Матамала, Реконструкция трехцветных сеток по горизонтальным и вертикальным проекциям NP-сложна . ЕКА 2009: 776-787.
^ HJ Ryser, Матрицы нулей и единиц, Bull. амер. Математика. Соц. 66 1960 442-464.
^ Д. Гейл, Теорема о потоках в сетях , Pacific J. Math. 7 (1957), 1073–1082.
^ Э. Баркуччи, С. Брунетти, А. Дель Лунго, М. Ниват, Реконструкция решетчатых множеств по их горизонтальным, вертикальным и диагональным рентгеновским лучам , Дискретная математика 241 (1-3): 65-78 (2001).
^ Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том. 108. Кембридж: Издательство Кембриджского университета . п. 27 . ISBN 978-0-521-86565-4 . Установить 1106.05001 .
^ Jump up to: ^а ^б А. Альперс, П. Грицманн, Л. Торенс, Устойчивость и нестабильность в дискретной томографии , Конспект лекций по информатике 2243; Цифровая и графическая геометрия (продвинутые лекции), Г. Бертран, А. Имия, Р. Клетт (ред.), стр. 175–186, Springer-Verlag, 2001.
^ А. Альперс, С. Брунетти, Об устойчивости восстановления наборов решеток по рентгеновским лучам в двух направлениях , Конспект лекций по информатике 3429; Цифровая геометрия для компьютерных изображений, Э. Андрес, Г. Дамианд, П. Линхардт (ред.), стр. 92–103, Springer-Verlag, 2005.
^ Б. ван Дален, Результаты устойчивости для однозначно определенных множеств с двух направлений в дискретной томографии , Discrete Mathematics 309 (12): 3905-3916 (2009).
^ Jump up to: ^а ^б Батенбург, Йост; Сийберс, Январь - DART: Практический алгоритм реконструкции для дискретной томографии - В: Транзакции IEEE по обработке изображений, Vol. 20, №. 9, с. 2542-2553, (2011). два : 10.1109/TIP.2011.2131661
^ В. ван Орле, К. Дж. Батенбург и Дж. Сийберс, Автоматическая оценка параметров для метода дискретной алгебраической реконструкции (DART), Транзакции IEEE при обработке изображений, 2012 [3]
^ К. Дж. Батенбург и Дж. Сийберс, «Общие итеративные алгоритмы подмножества для дискретной томографии», Discrete Applied Mathematics, vol. 157, нет. 3, стр. 438-451, 2009 г.
^ П. Грицманн, С. де Врис, М. Вигельманн, Аппроксимация бинарных изображений по дискретным рентгеновским лучам , SIAM J. Optim. 11 (2000), вып. 2, 522–546.
^ Jump up to: ^а ^б А. Альперс, Х. Ф. Поулсен, Э. Кнудсен, Г. Т. Херман, Алгоритм дискретной томографии для улучшения качества карт зерен 3DXRD, Журнал прикладной кристаллографии 39, стр. 582-588, 2006 [4] .
^ Jump up to: ^а ^б Л. Родек, Х. Ф. Поулсен, Э. Кнудсен, Г. Т. Герман, Стохастический алгоритм восстановления карт зерен умеренно деформированных образцов на основе дифракции рентгеновских лучей , Журнал прикладной кристаллографии 40: 313-321, 2007.
^ С. Балс , К. Дж. Батенбург, Дж. Вербек, Дж. Сийберс и Г. Ван Тендело, «Количественная 3D-реконструкция частиц катализатора для бамбукоподобных углеродных нанотрубок», Nano Letters, Vol. 7, нет. 12, с. 3669-3674, (2007) два : 10.1021/nl071899m
^ Батенбург Дж., С. Балс , Сийберс Дж., К. Кубель, П.А. Миджли, Дж.К. Эрнандес, У. Кайзер, Э.Р. Энсина, Э.А. Коронадо и Г. Ван Тендело, «3D-изображение наноматериалов с помощью дискретной томографии», Ультрамикроскопия , Том 109, с. 730-740, (2009) дои : 10.1016/j.ultramic.2009.01.009
^ К. Дж. Батенбург, Дж. Сийберс, Х. Ф. Поулсен и Э. Кнудсен, «DART: надежный алгоритм для быстрой реконструкции трехмерных карт зерен», Журнал прикладной кристаллографии, том. 43, стр. 1464-1473, 2010 г.
^ Журнал Games представляет игру «Раскраска по номерам» . Случайный дом . 1994. ISBN 978-0-8129-2384-1 .

Внешние ссылки

[ref4-1] Jump up to: ^а ^б Герман Г.Т. и Куба А. Дискретная томография: основы, алгоритмы и приложения, Birkhäuser Boston, 1999.

[ref5-2] Jump up to: ^а ^б Герман Г.Т. и Куба А., Достижения в области дискретной томографии и ее приложений, Birkhäuser Boston, 2007 г.

[ref11-3] Р. Дж. Гарднер, П. Грицманн, Дискретная томография: определение конечных множеств с помощью рентгеновских лучей, Trans. амер. Математика. Соц. 349 (1997), вып. 6, 2271–2295.

[ref9-4] Л. Хайду, Р. Тейдеман, Алгебраические аспекты дискретной томографии , Дж. Рейн Ангью. Математика. 534 (2001), 119-128.

[ref10-5] А. Альперс, Р. Тайдеман, Двумерная проблема Пруэ-Тэрри-Эскотта, Журнал теории чисел, 123 (2), стр. 403-412, 2007 [1] .

[ref14-6] С. Брунетти, А. Дель Лунго, П. Грицманн, С. де Врис, О восстановлении бинарных матриц и матриц перестановок при (бинарных) томографических ограничениях . Теория. Вычислить. наук. 406 (2008), вып. 1-2, 63-71.

[ref13-7] А. Альперс, П. Грицманн, О стабильности, исправлении ошибок и компенсации шума в дискретной томографии, SIAM Journal on Discrete Mathematics 20 (1), стр. 227-239, 2006 [2]

[ref12-8] П. Грицманн, Б. Лангфельд, Об индексе сеток Зигеля и его применении к томографии квазикристаллов. Европейский Дж. Комбин. 29 (2008), вып. 8, 1894–1909.

[ref15-9] Jump up to: ^а ^б Р. Дж. Гарднер, П. Грицманн, Д. Прангенберг, О вычислительной сложности восстановления решетчатых множеств по их рентгеновским лучам . Дискретная математика. 202 (1999), вып. 1-3, 45-71.

[ref16-10] Jump up to: ^а ^б К. Дюрр, Ф. Гиньес, М. Матамала, Реконструкция трехцветных сеток по горизонтальным и вертикальным проекциям NP-сложна . ЕКА 2009: 776-787.

[ref17-11] HJ Ryser, Матрицы нулей и единиц, Bull. амер. Математика. Соц. 66 1960 442-464.

[ref18-12] Д. Гейл, Теорема о потоках в сетях , Pacific J. Math. 7 (1957), 1073–1082.

[ref19-13] Э. Баркуччи, С. Брунетти, А. Дель Лунго, М. Ниват, Реконструкция решетчатых множеств по их горизонтальным, вертикальным и диагональным рентгеновским лучам , Дискретная математика 241 (1-3): 65-78 (2001).

[CMC27-14] Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том. 108. Кембридж: Издательство Кембриджского университета . п. 27 . ISBN 978-0-521-86565-4 . Установить 1106.05001 .

[ref23-15] Jump up to: ^а ^б А. Альперс, П. Грицманн, Л. Торенс, Устойчивость и нестабильность в дискретной томографии , Конспект лекций по информатике 2243; Цифровая и графическая геометрия (продвинутые лекции), Г. Бертран, А. Имия, Р. Клетт (ред.), стр. 175–186, Springer-Verlag, 2001.

[ref24-16] А. Альперс, С. Брунетти, Об устойчивости восстановления наборов решеток по рентгеновским лучам в двух направлениях , Конспект лекций по информатике 3429; Цифровая геометрия для компьютерных изображений, Э. Андрес, Г. Дамианд, П. Линхардт (ред.), стр. 92–103, Springer-Verlag, 2005.

[ref25-17] Б. ван Дален, Результаты устойчивости для однозначно определенных множеств с двух направлений в дискретной томографии , Discrete Mathematics 309 (12): 3905-3916 (2009).

[ref8-18] Jump up to: ^а ^б Батенбург, Йост; Сийберс, Январь - DART: Практический алгоритм реконструкции для дискретной томографии - В: Транзакции IEEE по обработке изображений, Vol. 20, №. 9, с. 2542-2553, (2011). два : 10.1109/TIP.2011.2131661

[19] В. ван Орле, К. Дж. Батенбург и Дж. Сийберс, Автоматическая оценка параметров для метода дискретной алгебраической реконструкции (DART), Транзакции IEEE при обработке изображений, 2012 [3]

[ref8b-20] К. Дж. Батенбург и Дж. Сийберс, «Общие итеративные алгоритмы подмножества для дискретной томографии», Discrete Applied Mathematics, vol. 157, нет. 3, стр. 438-451, 2009 г.

[ref22-21] П. Грицманн, С. де Врис, М. Вигельманн, Аппроксимация бинарных изображений по дискретным рентгеновским лучам , SIAM J. Optim. 11 (2000), вып. 2, 522–546.

[ref20-22] Jump up to: ^а ^б А. Альперс, Х. Ф. Поулсен, Э. Кнудсен, Г. Т. Херман, Алгоритм дискретной томографии для улучшения качества карт зерен 3DXRD, Журнал прикладной кристаллографии 39, стр. 582-588, 2006 [4] .

[ref21-23] Jump up to: ^а ^б Л. Родек, Х. Ф. Поулсен, Э. Кнудсен, Г. Т. Герман, Стохастический алгоритм восстановления карт зерен умеренно деформированных образцов на основе дифракции рентгеновских лучей , Журнал прикладной кристаллографии 40: 313-321, 2007.

[ref6-24] С. Балс , К. Дж. Батенбург, Дж. Вербек, Дж. Сийберс и Г. Ван Тендело, «Количественная 3D-реконструкция частиц катализатора для бамбукоподобных углеродных нанотрубок», Nano Letters, Vol. 7, нет. 12, с. 3669-3674, (2007) два : 10.1021/nl071899m

[ref7-25] Батенбург Дж., С. Балс , Сийберс Дж., К. Кубель, П.А. Миджли, Дж.К. Эрнандес, У. Кайзер, Э.Р. Энсина, Э.А. Коронадо и Г. Ван Тендело, «3D-изображение наноматериалов с помощью дискретной томографии», Ультрамикроскопия , Том 109, с. 730-740, (2009) дои : 10.1016/j.ultramic.2009.01.009

[ref21b-26] К. Дж. Батенбург, Дж. Сийберс, Х. Ф. Поулсен и Э. Кнудсен, «DART: надежный алгоритм для быстрой реконструкции трехмерных карт зерен», Журнал прикладной кристаллографии, том. 43, стр. 1464-1473, 2010 г.

[27] Журнал Games представляет игру «Раскраска по номерам» . Случайный дом . 1994. ISBN 978-0-8129-2384-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]