×

Ghosts in discrete tomography. (English) Zbl 1343.68267

Summary: Switching components, also named as bad configurations, interchanges, and ghosts (according to different scenarios), play a key role in the study of ambiguous configurations, which often appear in Discrete Tomography and in several other areas of research. In this paper we give an upper bound for the minimal size bad configurations associated to a given set \(S\) of lattice directions. In the special but interesting case of four directions, we show that the general argument can be considerably improved, and we present an algebraic method which provides such an improvement. Moreover, it turns out that finding bad configurations is in fact equivalent to finding multiples of a suitable polynomial in two variables, having only coefficients from the set \(\{-1,0,1\}\). The general problem of describing all polynomials having such multiples seems to be very hard [P. Borwein and T. Erdélyi, Ill. J. Math. 41, No. 4, 667–675 (1997; Zbl 0906.30005)]. However, in our particular case, it is hopeful to give some kind of solution. In the context of Digital Image Analysis, it represents an explicit method for the construction of ghosts, and consequently might be of interest in image processing, also in view of efficient algorithms to encode data.

MSC:

68U10 Computing methodologies for image processing
05D05 Extremal set theory
11H71 Relations with coding theory
15A06 Linear equations (linear algebraic aspects)
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 0906.30005

Software:

TVR-DART
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Borwein, P., Erdélyi, T.: On the zeros of polynomials with restricted coefficients. Ill. J. Math. 41(4),667-675 (1997). http://projecteuclid.org/euclid.ijm/1256068987 · Zbl 0906.30005
[2] Gardner, R.J.: Geometric Tomography, Second edn. Cambridge University Press, New York (1995). 2006
[3] Herman, G.T., Kuba, A.: Advances in Discrete Tomography and Its Applications. Appl. Numer. Harmon. Anal.,Birkhäuser Boston, Boston (2007) · Zbl 1117.65004 · doi:10.1007/978-0-8176-4543-4
[4] Batenburg, K.J., Palenstijn, W.J., Balázs, P., Sijbers, J.: Dynamic angle selection in binary tomography. Comput. Vis. Image Underst. 117(4), 306-318 (2013). doi:10.1016/j.cviu.2012.07.005 · doi:10.1016/j.cviu.2012.07.005
[5] Witheya, D.J., Pedryczb, W., Kolesb, Z.J.: Dynamic edge tracing: boundary identification in medical images. Comput. Vis. Image Underst. 113(10), 1039-1052 (2009). doi:10.1016/j.cviu.2009.07.003 · doi:10.1016/j.cviu.2009.07.003
[6] Gregor, J., Benson, T.: Computational analysis and improvement of SIRT. IEEE Trans. Med. Imaging 27(7), 918-924 (2008). doi:10.1109/TMI.2008.923696 · doi:10.1109/TMI.2008.923696
[7] Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P.: Special issue on discrete geometry for computer imagery. Comput. Vis. Image Underst. 117(4), 305 (2013). doi:10.1016/j.cviu.2013.01.009 · doi:10.1016/j.cviu.2013.01.009
[8] van Aert, S., Batenburg, K.J., Rossell, M.D., Erni, R., van Tendeloo, G.: Three-dimensional atomic imaging of crystalline nanoparticles. Nature 470, 374-377 (2011). http://www.nature.com/nature/journal/v470/n7334/abs/nature09741.html · Zbl 1160.68042
[9] Andersen, A.H., Kak, A.C.: Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm. Ultrason. Imaging 6, 81-94 (1984). doi:10.1016/0161-7346(84)90008-7 · doi:10.1016/0161-7346(84)90008-7
[10] Kak, A.C., Slaney M.: Principles of computerized tomographic imaging. SIAM (2001). doi:10.1137/1.9780898719277 · Zbl 0984.92017
[11] Gordon, R., Herman, G.T.: Reconstruction of pictures from their projections. Commun. ACM 14, 759-768 (1971). doi:10.1145/362919.362925 · Zbl 0225.68053 · doi:10.1145/362919.362925
[12] Herman, G.T.: Image Reconstruction from Projections: The Fundamentals of Computerized Tomography. Academic Press, New York (1980) · Zbl 0538.92005
[13] Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Probl. 24(4) (2008). doi:10.1088/0266-5611/24/4/045011 · Zbl 1161.68825
[14] Batenburg, K.J., Sijbers, J.: DART: a practical reconstruction algorithm for discrete tomography. IEEE Trans. Image Process. 20(9), 2542-2553 (2011). doi:10.1109/TIP.2011.2131661 · Zbl 1372.94020 · doi:10.1109/TIP.2011.2131661
[15] Varga, L., Nyúl, L.G., Nagy, A., Balázs, P.: Local uncertainty in binary tomographic reconstruction. In: Proceedings of the IASTED International Conference on Signal Processing, Pattern Recognition and Applications, pp. 490-496. Innsbruck (2013). doi:10.2316/P.2013.798-067 · Zbl 0079.01102
[16] Varga, L., Balázs, P., Nagy, A.: Direction-dependency of binary tomographic reconstruction algorithms. Graph. Model. 73, 365-375 (2011). doi:10.1016/j.gmod.2011.06.006 · doi:10.1016/j.gmod.2011.06.006
[17] Varga, L., Balázs, P., Nagy, A.: Projection selection dependency in binary tomography. Acta Cybern. 20(1), 167-187 (2011). http://dl.acm.org/citation.cfm?id=2336107.2336118 · Zbl 1240.94017
[18] Zheng, Z., Mueller, K.: Identifying sets of favorable projections for few-view low-dose cone-beam CT scanning. In: 11th International Meeting on Fully Three-Dimensional Image Reconstruction in Radiology and Nuclear Medicine, pp. 314-317 (2011)
[19] Katz, M.B.: Questions of Uniqueness and Resolution in Reconstruction from Projections. Lecture Notes in Biomathematics, vol. 26. Springer, Berlin (1978) · Zbl 0385.92002
[20] Fishburn, P.C., Lagarias, J.C., Reeds, J.A., Shepp, L.A.: Sets uniquely determined by projections on axes II. Discrete case. Discret. Math. 91, 149-159 (1991). doi:10.1016/0012-365X(91)90106-C · Zbl 0752.44002 · doi:10.1016/0012-365X(91)90106-C
[21] Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Can. J. Math. 9, 371-377 (1957). doi:10.4153/CJM-1957-044-3 · Zbl 0079.01102 · doi:10.4153/CJM-1957-044-3
[22] Chang, S.K.: The reconstruction of binary patterns from their projections. Commun. ACM 14, 21-24 (1971). doi:10.1145/362452.362471 · Zbl 0214.42603 · doi:10.1145/362452.362471
[23] Lorentz, G.G.: A problem of plane measure. Am. J. Math. 71, 417-426 (1949). http://www.jstor.org/stable/2372255 · Zbl 0032.19701
[24] Gardner, RJ; Gritzmann, P.; Herman, GT (ed.); Kuba, A. (ed.), Uniqueness and complexity in discrete tomography, 85-113 (1999), Boston · Zbl 0964.65146 · doi:10.1007/978-1-4612-1568-4_4
[25] Hajdu, L., Tijdeman, R.: Algebraic aspects of discrete tomography. J. Reine Angew. Math. 534, 119-128 (2001). doi:10.1515/crll.2001.037 · Zbl 1058.92029 · doi:10.1515/crll.2001.037
[26] Dulio, P., Peri, C.: Discrete tomography for inscribable lattice sets. Discret. Appl. Math. 161, 1959-1974 (2013). doi:10.1016/j.dam.2013.03.025 · Zbl 1286.05027 · doi:10.1016/j.dam.2013.03.025
[27] Brunetti, S., Dulio, P., Peri, C.: On the non-additive sets of uniqueness in a finite grid. DGCI 2013. LNCS 7749, 288-299 (2013). doi:10.1007/978-3-642-37067-0_25 · Zbl 1339.68256
[28] Brunetti, S., Dulio, P., Peri, C.: Characterization of \[\{-1,0,1\}\]{-1,0,1} valued functions in discrete tomography under sets of four directions. DGCI 2011. LNCS 6607, 394-405 (2011). doi:10.1007/978-3-642-19867-0_33 · Zbl 1272.92032
[29] Brunetti, S., Dulio, P., Peri, C.: Discrete tomography determination of bounded lattice sets from four X-rays. Discret. Appl. Math. 161(15), 2281-2292 (2013). doi:10.1016/j.dam.2012.09.010 · Zbl 1278.05051 · doi:10.1016/j.dam.2012.09.010
[30] Hajdu, L.: Unique reconstruction of bounded sets in discrete tomography. Electron. Notes Discret. Math. 20, 15-25 (2005). doi:10.1016/j.endm.2005.04.002 · Zbl 1179.94010 · doi:10.1016/j.endm.2005.04.002
[31] Gardner, R.J., Gritzmann, P.: Discrete tomography: determination of finite sets by X-rays. Trans. Am. Math. Soc. 349, 2271-2295 (1997). doi:10.1090/S0002-9947-97-01741-8 · Zbl 0873.52015 · doi:10.1090/S0002-9947-97-01741-8
[32] Gardner, R.J., McMullen, P.: On Hammer’s X-ray problem. J. Lond. Math. Soc. 21(2), 171-175 (1980). doi:10.1112/jlms/s2-21.1.171 · Zbl 0417.52005 · doi:10.1112/jlms/s2-21.1.171
[33] Brunetti, S., Daurat, A.: An algorithm reconstructing convex lattice sets. Theor. Comput. Sci. 304, 35-57 (2003). doi:10.1016/S0304-3975(03)00050-1 · Zbl 1044.68157 · doi:10.1016/S0304-3975(03)00050-1
[34] Dulio, P.: Convex decomposition of \[UU\]-polygons. Theor. Comput. Sci. 406(1-2), 80-89 (2008). doi:10.1016/j.tcs.06.008 · Zbl 1160.68042 · doi:10.1016/j.tcs.06.008
[35] Dulio, P., Peri, C.: On the geometric structure of lattice \[UU\]-polygons. Discret. Math. 307(19-20), 2330-2340 (2007). doi:10.1016/j.disc.2006.09.044 · Zbl 1123.52008 · doi:10.1016/j.disc.2006.09.044
[36] Huck, C., Spieß, M.: Solution of a uniqueness problem in the discrete tomography of algebraic Delone sets. J. Reine Angew. Math. 677, 199-224 (2013). doi:10.1515/crelle.2012.026 · Zbl 1268.52002 · doi:10.1515/crelle.2012.026
[37] Matoušek, J., Přívětivý, A., S̆kovroň, P.: How many points can be reconstructed from \[k\] k projections? SIAM J. Discret. Math. 22(4), 1605-1623 (2008). doi:10.1137/080715706 · Zbl 1179.05111 · doi:10.1137/080715706
[38] Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: X-rays characterizing some classes of discrete sets. Linear Algebra Appl. 339, 3-21 (2001). doi:10.1016/S0024-3795(01)00431-1 · Zbl 0994.65142 · doi:10.1016/S0024-3795(01)00431-1
[39] Bianchi, G., Longinetti, M.: Reconstructing plane sets from projections. Discret. Comput. Geom. 5, 223-242 (1990). doi:10.1007/BF02187787 · Zbl 0703.52002 · doi:10.1007/BF02187787
[40] Gardner, R.J.: X-rays of polygons. Discret. Comput. Geom. 7, 281-293 (1992). doi:10.1007/BF02187842 · Zbl 0748.52003 · doi:10.1007/BF02187842
[41] Svalbe, I., Chandra, S.: Growth of discrete projection ghosts created by iteration. DGCI 2011. LNCS 6607, 406-416 (2011). doi:10.1007/978-3-642-19867-0_34 · Zbl 1272.68447
[42] Svalbe, I., Normand, N.: Properties of minimal ghosts, DGCI 2011. LNCS 6607, 417-428 (2011). doi:10.1007/978-3-642-19867-0_35 · Zbl 1272.68448
[43] Svalbe, I., Nazareth, N., Chandra, S.: On constructing minimal ghosts. In: DICTA 2010, Sydney, pp. 276-281 (2010). doi:10.1109/DICTA.2010.56 · Zbl 1160.68042
[44] Chandra, S., Svalbe, I., Guédon, J.P.: An Exact Non-iterative Mojette Inversion Technique Utilising Ghosts. LNCS, vol. 4992. Springer, Berlin (2008) · Zbl 1138.68572
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.