Discrete Tomography Data Footprint Reduction via Natural Compression

• Autorzy: Fiorini R. A. , Condorelli A. , Laguteta G.
• Języki publikacji: EN

Abstrakty

EN

In Discrete Tomography (DT) by electron microscopy, 2-D projection images are acquired from various angles, by tilting the sample, generating new challenges associated with the problem of formation, acquisition, compression, transmission, and analysis of enormous quantity of data. Data Footprint Reduction (DFR) is the process of employing one or more techniques to store a given set of data in less storage space. Modern lossless compressors use classical probabilistic models only, and are unable to match high end application requirements like “Arbitrary Bit Depth” (ABD) resolution and information “Dynamic Upscale Regeneration” (DUR). Traditional \mathbbQ Arithmetic can be regarded as a highly sophisticated open logic, powerful and flexible bidirectional (LTR and RTL) formal language of languages, according to brand new “Information Conservation Theory” (ICT). This new awareness can offer competitive approach to guide more convenient algorithm development and application for combinatorial lossless compression, we named “Natural Compression” (NC). To check practical implementation performance, a first raw example is presented, benchmarked to standard, more sophisticate lossless JPEG2000 algorithm, and critically discussed. NC raw overall lossless compression performance compare quite well to standard one, but offering true ABD and DUR at no extra computational cost.

Słowa kluczowe

EN

arithmetic geometry; biomedical cybernetics; biomedical engineering; data footprint reduction; discrete tomography; healthcare; lossless compression; public health

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 3/4
• Strony: 273--284
• Opis fizyczny: Bibliogr. 57 poz., fot., wykr.

Twórcy

autor

Fiorini R. A.

• Dipartimento di Bioingegneria, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy

autor

Condorelli A.

• Dipartimento di Bioingegneria, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy

autor

Laguteta G.

• Dipartimento di Bioingegneria, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy

Bibliografia

• [1] http://www.imagecompression.info/test_images, title = The New Test Images for Image Compression Benchmark, year = 2008,.
• [2] ISO/IEC 14492:2001, Information technology - Lossy/lossless coding of bi-level image, http://www.iso. org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=22394.
• [3] ISO/IEC 11544:1993: Information technology - Coded representation of picture and audio information - Progressive bi-level image compression, http://www.iso.org/iso/iso_catalogue/catalogue_tc/ catalogue_detail.htm?csnumber=19498,1993.
• [4] DICOM: Digital imaging and communications in medicine, The DICOM standard, 2009, http://dicom. nema.org/dicom/2009/.
• [5] Ader, H.J. Mellenbergs, G.: Advising on Research Methods: A consultant’s companion, 2008, 271-304.
• [6] Atamturk, A., Savelsbergh, M.: Integer-programming software systems, Annals of Operations Research, 140, 2005, 67-124.
• [7] Balas, E.: Disjunctive programming: Properties of the convex hull of feasible points, Discrete Appl, Mathematics, 89, 1998, 3-44.
• [8] Batenburg, K. J., Bals, S., Sijbers, J., Kubel, C., Midgley, P. A., Hernandez, J. C., Kaiser, U., Encina, E. R., Coronado, E. A., Tendeloo, G. V.: 3D imaging of nanomaterials by discrete tomography, Ultramicroscopy, 109, 2009, 730-740.
• [9] Bazaraa, M., Sherali, H., Shetty, C.: Nonlinear Programming Theory and Algorithms, Wiley, 2006.
• [10] Bekenstein, J. D.: Information in the Holographic Universe; Reality-Bending Black Holes, Scientific American Digital, 2003, 59-65, http://www.sciamdigital.com/index.cfm?fa=Products. ViewIssuePreview&ARTICLEID_CHAR=0E90201A-2BB-6BBEB44296C90AAD.
• [11] Bertsekas, D. P.: Nonlinear Programming, Athena Scientific, Cambridge, 2004.
• [12] Bottou, L., Haffner, P., Howard, P. G., Simard, P., Bengio, Y., Cun, Y. L.: High Quality Document Image Compression with DjVu, J. of Elect Imaging, 7(3), 1998, 410-425.
• [13] Boyd, S., Vandenberghe, L.: Convex Optimization, Cambridge University Press, Cambridge, 2004.
• [14] Chandler, B. M.: The history of combinatorial group theory: A case study in the history of ideas, studies in the history of mathematics and physical sciences (1st ed.), Springer, 1982, 387-90749.
• [15] Cook, S.: The complexity of theorem proving procedures, 1971, 151-158.
• [16] Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., Schrijver, A.: Combinatorial Optimization, John Wiley & Sons;, 12(1997), November 1997.
• [17] Curtis, C. W.: Pioneers of Representation Theory: Frobenius, Burnside, Schur, and Brauer, History of Mathematics, Providence, R, American Mathematical Society, 2003.
• [18] von Dyck, W.: Gruppentheoretische Studien (Group-theoretical Studies), , Mathematische Annalen, 20(1), 1882, 1-44.
• [19] Fiorini, R. A.: Discrete Tomography Data Footprint Reduction by Information Conservation, submitted to ’’Principia Informaticae” Journal, 2012.
• [20] Fiorini, R. A., Santacroce, G.: Systems Science and Biomedical Cybernetics for Healthcare Safety Management, Proc. International Symposium, The Economic Crisis: Time For A Paradigm Shift - Towards a Systems Approach, Universitat de Valencia, January 24-25, 2013.
• [21] Fortnow, L.: The status of the P versus NP problem, Communications of the ACM 52, no. 9, 2009, 78-86.
• [22] Goberna, M. A., Lopez, M. A.: Linear Semi-Infinite Optimization, John Wiley, New York, 1998.
• [23] Hamilton, S. W. R.: Memorandum respecting a new System of Roots of Unity, Philosophical Magazine, 12(446), 1856.
• [24] Herman, G. T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, Springer, 2009.
• [25] Herman, G. T., Kuba, A.: Discrete tomography in medical imaging, Proceedings of the IEEE, 91, 2003, 1612-1626.
• [26] Hoffman, K. L., Padberg, M. W.: Improving LP-representations of zero-one linear programs for branch and cut, ORSA Journal on Computing, 3, 1991, 121-134.
• [27] Hoffman, K.L. Ralphs, T. K.: Integer and Combinatorial Optimization, Encyclopedia of Operations Research and Management Science, 2011, Website:http://ebooks6.com/ Integer-and-Combinatorial-Optimization-pdf-e16426.pdf.
• [28] Huffman, D. A.: A Method for the Construction of Minimum-Redundancy Codes, Proc. I.R.E., Sept. 1952, 1098-1102.
• [29] ISO: Information technology - JPEG 2000 image coding system, 2002.
• [30] Jinschek, J. R., Batenburg, K. J., Calderon, H. A., Kilaas, R., Radmilovic, V., Kisielowski, C.: 3-D reconstruction of the atomic positions in a simulated gold nanocrystal based on discrete tomography, Ultramicroscopy, 108, 2008, 589-604.
• [31] Junger, M. Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L.: Fifty Years of Integer Programming: 1958-2008, Springer, Berlin, 2010.
• [32] Kieffer, J. C., Yang, E.-H.: Grammar-based codes: A new class of universal lossless source codes,, IEEE Trans Inform. Theory, 46(3), 2000, 737-754.
• [33] Kieffer, J. C., Yang, E.-H., Nelson, G. J., Cosman, P.: Universal lossless compression via multilevel pattern matching, IEEE Trans Inform. Theory, 46(4), 2000, 1227-1245.
• [34] Kim, T.J. Lee, K., Kim, B., et al.: Regional variance of visually lossless threshold in compressed chest CT images: lung versus mediastinum and chest wall, Eur J Radiol, 69(3), 2009,483-488.
• [35] Koff, D. A., Shulman, H.: An overview of digital compression of medical images: Can we use lossy image compression in radiology?, Can. assoc. of radiologists jour., 57, 2006, 211-217.
• [36] Kryder, Mark H., C. S. K.: After Hard Drives - What Comes Next?, IEEE Transactions on Magnetics, 45(10), October 2009, http://www.dssc.ece.cmu.edu/research/pdfs/After_Hard_Drives.pdf.
• [37] Larsson, N. J., Moffat, A.: Offline Dictionary-Based Compression, IEEE, 88(11), 2000, 1722-1732.
• [38] Licata, I.: La logica aperta della mente, Codice edizioni, Torino, 2008.
• [39] Linderoth, J., Ralphs, T.: Noncommercial software for mixed-integer linear programming, In J. Integer Programming: Theory and Practice, CRC Press, 2005, 253-303.
• [40] van Lint, H., J., Wilson, R. M.: A Course in Combinatorics (Paperback), 2dn edition, Cambridge University Press, 2001.
• [41] MacKay, D. J. C.: Information Theory, Inference, and Learning Algorithms, Cambridge: Cambridge University Press, 2003.
• [42] Martin, A.: Computational issues for branch-and-cut algorithms, in: editors, Computational Combinatorial Optimization, (M. Juenger, D. Naddef, Eds.), Springer, Berlin, 2001.
• [43] Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1988.
• [44] Nevill-Manning, C. G., Witten, I. H.: Identifying Hierarchical Structure in Sequences: A linear-time algorithm, Journal of Artificial Intelligence Research, 7(4), 1997, 67-82.
• [45] Nocedal, J., Wright, S. J.: Numerical Optimization, Springer, New York, 1999.
• [46] Padberg, M. W., Rinaldi, G.: A branch and cut algorithm for the solution of large scale traveling salesman problems, SIAM Review, 33, 1991, 60-100.
• [47] Rissanen, J.: Generalized Kraft Inequality and Arithmetic Coding, IBM J of Res. and Dev, (3), 1976, 198203.
• [48] Schrijver, A.: A Course in Combinatorial Optimization, (2006-2012), http://homepages.cwi.nl/lex/ files/dict.pdf.
• [49] Shannon, C. E.: A Mathematical Theory of Communication, Bell Syst Tech. Journal, 27(3), 1948, 379-423.
• [50] Solitar, Donald, M., Wilhelm, Karrass, A.: Combinatorial group theory: presentations of groups in terms of generators and relations, New York: Dover, 1976.
• [51] Stillwell, J.: Mathematics and its history, Springer, 2002.
• [52] Sun, W., Lu, Y., Wu, F., Li, S.: Level Embedded Medical Image Compression Based On Value Of Interest, IEEE, ICIP, pp, 2009, 1769-1772.
• [53] Weyl, H.: Elementare theorie der konvexen polyheder, Comm, 1935, 290-306.
• [54] Witten, Ian H. Neal, R., Cleary, J.: Arithmetic Coding for Data Compression, Communications of the ACM, 30(6), 1987, 520-540.
• [55] Yang, E.-H., Kaltchenko, A., Kieffer, J. C.: Universal lossless data compression with side information by using a conditional mpm grammar transform,, IEEE Trans Inform. Theory, 47(6), 2001, 2130-2150.
• [56] Yang, E.-H., Kieffer, J. C.: Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform-part one: Without context models, IEEE Trans Inform. Theory, 46(3), 2000, 755-777.
• [57] Zukoski, M. J., Boult, T., Iyriboz, T.: A novel approach to medical image compression, Int. J. of Bioinf. Research and Applications, 2006, 89-103.