Tomografía discreta

Reconstrucción de imágenes binarias a partir de un pequeño número de sus proyecciones

Problema de reconstrucción tomográfica discreta para dos direcciones verticales y horizontales (izquierda), junto con su solución (no única) (derecha). La tarea consiste en colorear algunos de los puntos blancos de negro de modo que la cantidad de puntos negros en las filas y columnas coincida con los números azules.

La tomografía discreta ^{[1] [2]} se centra en el problema de la reconstrucción de imágenes binarias (o subconjuntos finitos de la red entera ) a partir de un pequeño número de sus proyecciones .

En general, la tomografía se ocupa del problema de determinar la forma y la información dimensional de un objeto a partir de un conjunto de proyecciones. Desde el punto de vista matemático, el objeto corresponde a una función y el problema planteado es reconstruir esta función a partir de sus integrales o sumas sobre subconjuntos de su dominio . En general, el problema de inversión tomográfica puede ser continuo o discreto. En la tomografía continua, tanto el dominio como el rango de la función son continuos y se utilizan integrales de línea. En la tomografía discreta, el dominio de la función puede ser discreto o continuo, y el rango de la función es un conjunto finito de números reales, generalmente no negativos. En la tomografía continua, cuando se dispone de un gran número de proyecciones, se pueden realizar reconstrucciones precisas mediante muchos algoritmos diferentes. Es típico de la tomografía discreta que solo se utilicen unas pocas proyecciones (sumas de línea). En este caso, todas las técnicas convencionales fallan. Un caso especial de tomografía discreta se ocupa del problema de la reconstrucción de una imagen binaria a partir de un pequeño número de proyecciones. El nombre de tomografía discreta se debe a Larry Shepp , quien organizó la primera reunión dedicada a este tema ( Mini-Simposio DIMACS sobre Tomografía Discreta, 19 de septiembre de 1994, Universidad Rutgers ).

Teoría

La tomografía discreta tiene fuertes conexiones con otros campos matemáticos, como la teoría de números , ^{[3] [4] [5]} las matemáticas discretas , ^{[6] [7] [8]} la teoría de la complejidad computacional ^{[9] [10]} y la combinatoria . ^{[11] [12] [13]} De hecho, varios problemas de tomografía discreta se discutieron por primera vez como problemas combinatorios. En 1957, HJ Ryser encontró una condición necesaria y suficiente para que un par de vectores sean las dos proyecciones ortogonales de un conjunto discreto. En la prueba de su teorema, Ryser también describió un algoritmo de reconstrucción, el primer algoritmo de reconstrucción para un conjunto discreto general a partir de dos proyecciones ortogonales. En el mismo año, David Gale encontró las mismas condiciones de consistencia, pero en conexión con el problema del flujo de red . ^[14] Otro resultado de Ryser es la definición de la operación de conmutación por la cual los conjuntos discretos que tienen las mismas proyecciones se pueden transformar entre sí.

El problema de reconstruir una imagen binaria a partir de un pequeño número de proyecciones generalmente conduce a un gran número de soluciones. Es deseable limitar la clase de soluciones posibles únicamente a aquellas que sean típicas de la clase de imágenes que contiene la imagen que se está reconstruyendo utilizando información a priori, como la convexidad o la conectividad.

Teoremas

• La reconstrucción de conjuntos reticulares planos (finitos) a partir de sus rayos X unidimensionales es un problema NP-difícil si los rayos X se toman desde direcciones reticulares (ya que el problema está en P). ^[9] ${\displaystyle m\geq 3}$ ${\displaystyle m=2}$
• El problema de reconstrucción es altamente inestable para (lo que significa que una pequeña perturbación de los rayos X puede llevar a reconstrucciones completamente diferentes) ^[15] y estable para , ver. ^{[15] [16] [17]} ${\displaystyle m\geq 3}$ ${\displaystyle m=2}$
• En la comunidad de tomografía discreta , la coloración de una cuadrícula con colores con la restricción de que cada fila y cada columna tenga una cantidad específica de celdas de cada color se conoce como el problema del átomo. El problema es NP-hard para , ver. ^[10] ${\displaystyle k}$ ${\displaystyle (k-1)}$ ${\displaystyle k\geq 3}$

Para más resultados, véase ^{[1] [2]}

Algoritmos

Entre los métodos de reconstrucción se pueden encontrar técnicas de reconstrucción algebraica (por ejemplo, DART ^{[18] [19]} o ^[20] ), algoritmos voraces (ver ^[21] para garantías de aproximación) y algoritmos de Monte Carlo . ^{[22] [23]}

Aplicaciones

Se han aplicado varios algoritmos en el procesamiento de imágenes , ^[18] medicina , problemas de seguridad de datos estadísticos tridimensionales, ingeniería y diseño asistidos por tomógrafos computarizados, microscopía electrónica ^{[24] [25]} y ciencia de materiales , incluido el microscopio 3DXRD . ^{[22] [23] [26]}

Una forma de tomografía discreta también constituye la base de los nonogramas , un tipo de rompecabezas lógico en el que se utiliza información sobre las filas y columnas de una imagen digital para reconstruir la imagen. ^[27]

Véase también

• Tomografía geométrica

Referencias

1. Herman, GT y Kuba, A., Tomografía discreta: fundamentos, algoritmos y aplicaciones, Birkhäuser Boston, 1999
2. Herman, GT y Kuba, A., Avances en tomografía discreta y sus aplicaciones, Birkhäuser Boston, 2007
3. RJ Gardner, P. Gritzmann, Tomografía discreta: determinación de conjuntos finitos mediante rayos X, Trans. Amer. Math. Soc. 349 (1997), n.º 6, 2271-2295.
4. L. Hajdu, R. Tijdeman, Aspectos algebraicos de la tomografía discreta, J. reine angew. Math. 534 (2001), 119-128.
5. A. Alpers, R. Tijdeman, El problema bidimensional de Prouhet-Tarry-Escott, Journal of Number Theory, 123 (2), págs. 403-412, 2007 [1].
6. S. Brunetti, A. Del Lungo, P. Gritzmann, S. de Vries, Sobre la reconstrucción de matrices binarias y de permutación bajo restricciones tomográficas (binarias). Theoret. Comput. Sci. 406 (2008), núm. 1-2, 63-71.
7. A. Alpers, P. Gritzmann, Sobre estabilidad, corrección de errores y compensación de ruido en tomografía discreta, SIAM Journal on Discrete Mathematics 20 (1), pp. 227-239, 2006 [2]
8. P. Gritzmann, B. Langfeld, Sobre el índice de las rejillas de Siegel y su aplicación a la tomografía de cuasicristales. European J. Combin. 29 (2008), núm. 8, 1894-1909.
9. RJ Gardner, P. Gritzmann, D. Prangenberg, Sobre la complejidad computacional de la reconstrucción de conjuntos reticulares a partir de sus rayos X. Matemáticas discretas. 202 (1999), núm. 1-3, 45-71.
10. C. Dürr, F. Guiñez, M. Matamala, Reconstruir cuadrículas de tres colores a partir de proyecciones horizontales y verticales es NP-difícil. ESA 2009: 776-787.
11. HJ Ryser, Matrices de ceros y unos, Bull. Amer. Math. Soc. 66 1960 442-464.
12. D. Gale, Un teorema sobre flujos en redes, Pacific J. Math. 7 (1957), 1073-1082.
13. E. Barcucci, S. Brunetti, A. Del Lungo, M. Nivat, Reconstrucción de conjuntos reticulares a partir de sus rayos X horizontales, verticales y diagonales, Discrete Mathematics 241(1-3): 65-78 (2001).
14. Brualdi, Richard A. (2006). Clases de matrices combinatorias. Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . pág. 27. ISBN. 978-0-521-86565-4.Zbl 1106.05001  .
15. A. Alpers, P. Gritzmann, L. Thorens, Estabilidad e inestabilidad en tomografía discreta, Notas de clase en Ciencias de la Computación 2243; Geometría digital y de imágenes (Conferencias avanzadas), G. Bertrand, A. Imiya, R. Klette (Eds.), págs. 175-186, Springer-Verlag, 2001.
16. A. Alpers, S. Brunetti, Sobre la estabilidad de la reconstrucción de conjuntos reticulares a partir de rayos X en dos direcciones, Lecture Notes in Computer Science 3429; Geometría digital para imágenes por computadora, E. Andres, G. Damiand, P. Lienhardt (Eds.), págs. 92-103, Springer-Verlag, 2005.
17. B. van Dalen, Resultados de estabilidad para conjuntos determinados de forma única desde dos direcciones en tomografía discreta, Matemáticas discretas 309(12): 3905-3916 (2009).
18. Batenburg, Joost; Sijbers, Jan - DART: Un algoritmo práctico de reconstrucción para tomografía discreta - En: Transacciones IEEE sobre procesamiento de imágenes, Vol. 20, Nr. 9, p. 2542-2553, (2011). doi :10.1109/TIP.2011.2131661
19. W. van Aarle, K J. Batenburg y J. Sijbers, Estimación automática de parámetros para la técnica de reconstrucción algebraica discreta (DART), IEEE Transactions on Image Processing, 2012 [3]
20. KJ Batenburg y J. Sijbers, "Algoritmos de subconjuntos iterativos genéricos para tomografía discreta", Discrete Applied Mathematics, vol. 157, n.º 3, págs. 438-451, 2009
21. P. Gritzmann, S. de Vries, M. Wiegelmann, Aproximación de imágenes binarias a partir de rayos X discretos, SIAM J. Optim. 11 (2000), no. 2, 522-546.
22. A. Alpers, HF Poulsen, E. Knudsen, GT Herman, Un algoritmo de tomografía discreta para mejorar la calidad de los mapas de granos 3DXRD, Journal of Applied Crystallography 39, págs. 582-588, 2006 [4].
23. L. Rodek, HF Poulsen, E. Knudsen, GT Herman, Un algoritmo estocástico para la reconstrucción de mapas de granos de muestras moderadamente deformadas basado en difracción de rayos X, Journal of Applied Crystallography 40:313-321, 2007.
24. S. Bals , KJ Batenburg, J. Verbeeck, J. Sijbers y G. Van Tendeloo, "Reconstrucción cuantitativa en 3D de partículas catalizadoras para nanotubos de carbono similares al bambú", Nano Letters, vol. 7, n.° 12, pág. 3669-3674, (2007) doi :10.1021/nl071899m
25. Batenburg J., S. Bals , Sijbers J., C. Kubel, PA Midgley, JC Hernandez, U. Kaiser, ER Encina, EA Coronado y G. Van Tendeloo, "Imágenes tridimensionales de nanomateriales mediante tomografía discreta", Ultramicroscopy, vol. 109, pág. 730-740, (2009) doi :10.1016/j.ultramic.2009.01.009
26. KJ Batenburg, J. Sijbers, HF Poulsen y E. Knudsen, "DART: un algoritmo robusto para la reconstrucción rápida de mapas de granos en 3D", Journal of Applied Crystallography, vol. 43, págs. 1464-1473, 2010
27. La revista Games presenta la pintura por números. Random House . 1994. ISBN 978-0-8129-2384-1.

Enlaces externos

• Euro DT (un sitio Wiki de Tomografía Discreta para investigadores)
• Aplicación de tomografía de Christoph Dürr
• Tesis doctoral sobre tomografía discreta (2012): Segmentación tomográfica y tomografía discreta para el análisis cuantitativo de datos de tomografía de transmisión