Some theoretical challenges in digital geometry: a perspective. (English) Zbl 1186.68487
Summary: In recent years, image analysis has become a research field of exceptional significance, due to its relevance to real life problems in important societal and governmental sectors, such as medicine, defense, and security. The explicit purpose of the present perspective is to suggest a number of strategic objectives for theoretical research, with an emphasis on the combinatorial approach in image analysis. Most of the proposed objectives relate to the need to make the theoretical foundations of combinatorial image analysis better integrated within a number of well-established subjects of theoretical computer science and discrete applied mathematics, such as the theory of algorithms and problem complexity, combinatorial optimization and polyhedral combinatorics, integer and linear programming, and computational geometry.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
combinatorial image analysis; digital geometry; computational geometry; complexity theory; polyhedral reconstruction; parallel algorithm; in-place algorithm; Voronoi diagram; zone diagramReferences:
| [1] | Amihood, A.; Benson, G.; Farach, M., Optimal parallel two dimensional text searching on a CREW PRAM, Inf. Comput., 144, 1, 1-17 (1998) · Zbl 0917.68049 |
| [2] | (Apostolico, A.; Galil, Z., Pattern Matching Algorithms (1997), Oxford University Press) · Zbl 0874.68006 |
| [3] | T. Asano, L. Buzer, H. Tanaka, Constant-working-space algorithms for image processing, in: ISAAC’09 (submitted for publication); T. Asano, L. Buzer, H. Tanaka, Constant-working-space algorithms for image processing, in: ISAAC’09 (submitted for publication) |
| [4] | Asano, T.; Matousek, J.; Tokuyama, T., The distance trisector curve, Advances in Mathematics, 212, 1, 338-360 (2007) · Zbl 1185.68768 |
| [5] | Asano, T.; Matousek, J.; Tokuyama, T., Zone diagrams: existence, uniqueness and algorithmic challenge, SIAM Journal on Computing, 37, 4, 1182-1198 (2007) · Zbl 1156.68050 |
| [6] | T. Asano, H. Tanaka, Constant-working-space algorithm for Euclidean distance transform, Technical Report, Special Interest Group on Computation, IEICE of Japan, May 2008; T. Asano, H. Tanaka, Constant-working-space algorithm for Euclidean distance transform, Technical Report, Special Interest Group on Computation, IEICE of Japan, May 2008 |
| [7] | Bárány, I.; Hove, R.; Lovász, L., On integer points in polyhedra: A lower bound, Combinatorica, 12, 2, 135-142 (1992) · Zbl 0754.52005 |
| [8] | Bárány, I.; Larman, D. G., The convex hull of the integer points in a large ball, Mathematische Annalen, 312, 11, 167-181 (1998) · Zbl 0927.52020 |
| [9] | Barneva, R. P.; Brimkov, V. E., Digital geometry and its applications to medical imaging, (Tavares, J.; etal., Advances in Computational Vision and Medical Image Processing: Methods and Applications. Advances in Computational Vision and Medical Image Processing: Methods and Applications, Computational Methods in Applied Sciences (2008), Springer: Springer Berlin), 77-92, (Chapter 4) |
| [10] | Breu, H.; Gil, J.; Kirkpatrick, D.; Werman, M., Linear time Euclidean distance algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, 17, 5, 529-533 (1995) |
| [11] | Brimkov, V. E., Digital geometry for image analysis and processing, (Tavares, J.; etal., Computational Modeling of Objects Represented in Images: Fundamentals, Methods and Applications (2007), Taylor & Francis Group Pu: Taylor & Francis Group Pu London/Leiden/New York/Philadelphia/Singapore), 9-15 |
| [12] | Brimkov, V. E., Discrete volume polyhedrization: complexity and bounds on performance, (Tavares, J.; etal., Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications (Proc. of CompIMAGE 2006, Coimbra, Portugal, 20-21 October 2006) (2007), Taylor & Francis Group Pu: Taylor & Francis Group Pu London/Leiden/New York/Philadelphia/Singapore), 117-122 |
| [13] | Brimkov, V. E., Scaling of plane figures that assures faithful digitization, (Brimkov, V. E.; etal., Combinatorial Image Analysis. Combinatorial Image Analysis, LNCS, vol. 4958 (2008), Springer: Springer Berlin), 87-98 |
| [14] | Brimkov, V. E., Digitization scheme that assures faithful reconstruction of plane figures, Pattern Recognition, 42, 8, 1637-1649 (2009) · Zbl 1182.68330 |
| [15] | Brimkov, V. E.; Barneva, R., Polyhedrization of discrete convex volumes, (Bebis, G.; etal., International Symposium on Visual Computing. International Symposium on Visual Computing, LNCS, vol. 4291 (2006), Springer: Springer Berlin), 548-557 |
| [16] | Brimkov, V. E.; Barneva, R. P., On the polyhedral complexity of the integer points in a hyperball, Theoretical Computer Science, 406, 24-30 (2008) · Zbl 1151.52010 |
| [17] | Brimkov, V. E.; Dantchev, S. S., Real data-integer solution problems within the Blum-Shub-Smale computational model, Journal of Complexity, 13, 279-300 (1997) · Zbl 0880.68035 |
| [18] | Brimkov, V. E.; Coeurjolly, D.; Klette, R., Digital planarity-a review, Discrete Applied Mathematics, 155, 4, 468-495 (2007) · Zbl 1109.68122 |
| [19] | Brimkov, V. E.; Klette, R., Border and surface tracing — theoretical foundations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 4, 577-590 (2008) |
| [20] | Chen, L., Discrete Surfaces and Manifolds: A Theory of Digital-Discrete Geometry and Topology (2004), Scientific & Practical Computing: Scientific & Practical Computing Rockville |
| [21] | Coeurjolly, D.; Brimkov, V. E., Computational aspects of digital plane and hyperplane recognition, (Reulke, R.; etal., Combinatorial Image Analysis. Combinatorial Image Analysis, LNCS, vol. 4040 (2006), Springer: Springer Berlin), 291-306 |
| [22] | Coeurjolly, D.; Dupont, F.; Jospin, L.; Sivignon, I., Optimization schemes for the reversible discrete volume polyhedrization using marching cubes simplification, (Kuba, A.; etal., Discrete Geometry for Computer Imagery. Discrete Geometry for Computer Imagery, LNCS, vol. 4245 (2006), Springer: Springer Berlin), 413-424 · Zbl 1136.68561 |
| [23] | Coeurjolly, D.; Guillaume, A.; Sivignon, I., Reversible discrete volume polyhedrization using Marching Cubes simplification, (Proc. Vision Geometry XII, SPIE, vol. 5300 (2004)), 1-11 |
| [24] | Coeurjolly, D.; Hulin, J.; Sivignon, I., Finding a minimum medial axis of a discrete shape is NP-hard, Theoretical Computer Science, 406, 1-2, 72-79 (2008) · Zbl 1160.68040 |
| [25] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA · Zbl 1047.68161 |
| [26] | van der Corput, J. G., Verscharfung der Abschätzung beim Teilerproblem, Mathematische Annalen, 87, 39-65 (1922) · JFM 48.0181.01 |
| [27] | Crochemore, M.; Lecroq, T., Pattern matching and text compression algorithms, (Tucker, A. B., The Computer Science and Engineering Handbook (1997), CRC Press: CRC Press Boca-Raton), 162-202, (Chapter 8) |
| [28] | Crochemore, M.; Rytter, W., Text Algorithms (1994), Oxford University Press · Zbl 0844.68101 |
| [29] | De Vieilleville, F.; Lachaud, J.-O.; Feschet, F., Maximal digital straight segments and convergence of discrete geometric estimators, (Proc. SCIA’05 (2005)), 988-997 |
| [30] | Feschet, F.; Tougne, L., On the min DSS problem of closed discrete curves, Discrete Applied Mathematics, 151, 1-3, 139-156 (2005) · Zbl 1101.68904 |
| [31] | Friel, J. J., Practical Guide to Image Analysis (2000), ASM International |
| [32] | Garey, M.; Johnson, D., Computers and Intractability (1979), W.H. Freeman & Company: W.H. Freeman & Company San Francisco · Zbl 0411.68039 |
| [33] | Gérard, Y., Reconstructing a matrix with a given list of coefficients and prescribed row and column sums is NP-hard, (Brimkov, V.; etal., Combinatorial Image Analysis. Combinatorial Image Analysis, LNCS, vol. 4958 (2008), Springer: Springer Berlin), 363-371 |
| [34] | Hayes, A. S.; Larman, D. C., The vertices of the knapsack polytope, Discrete Applied Mathematics, 6, 2, 135-138 (1983) · Zbl 0523.90063 |
| [35] | Hirata, T., A unified linear-time algorithm for computing distance maps, Information Processing Letters, 58, 3, 129-133 (1996) · Zbl 1023.68681 |
| [36] | Jarnik, V., Über Gitterpunkte and konvex Kurven, Mathematik Zeitschrift, 24, 500-518 (1925) · JFM 51.0153.01 |
| [37] | Kenmochi, Y.; Imiya, A.; Ezquerra, N. F., Polyhedra generation from lattice points, (Miguet, S.; etal., Discrete Geometry for Computer Geometry. Discrete Geometry for Computer Geometry, LNCS, vol. 1176 (2000), Springer: Springer Berlin), 127-138 · Zbl 1541.68401 |
| [38] | Klette, R.; Rosenfeld, A., Digital Geometry-Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco · Zbl 1064.68090 |
| [39] | Klette, R.; Rosenfeld, A., Digital straightness-a review, Discrete Applied Mathematics, 139, 1-3, 197-230 (2004) · Zbl 1093.68656 |
| [40] | Landau, G. M.; Vishkin, U., Fast parallel and serial approximate string matching, Journal of Algorithms, 10, 157-169 (1989) · Zbl 0685.68033 |
| [41] | Lingas, A., The power of non-rectilinear holes, (Proc. 9th Internat. Colloquium on Automata, Languages, and Programming. Proc. 9th Internat. Colloquium on Automata, Languages, and Programming, LNCS, vol. 140 (1982), Springer: Springer Berlin), 369-383 · Zbl 0487.68033 |
| [42] | Malgouyres, R.; Moreb, M., On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology, Theoretical Computer Science, 283, 1, 67-108 (2002) · Zbl 0997.68153 |
| [43] | McInerney, T.; Terzopoulos, D., Deformable models in medical image analysis: a survey, Medical Image Analysis, 1, 2, 91-108 (1996) |
| [44] | McMullen, P., The maximum numbers of facets of a convex polytope, Mathematika, 17, 179-184 (1970) · Zbl 0217.46703 |
| [45] | Menger, K., Kurventheorie (1932), Teubner: Teubner Leipzig, Germany · JFM 58.1205.02 |
| [46] | Morse, M.; Hedlund, G. A., Symbolic dynamics II: Sturmian sequences, American Journal of Mathematics, 61, 1-42 (1940) · JFM 66.0188.03 |
| [47] | Mylopoulos, J. P.; Pavlidis, T., On the topological properties of quantized spaces, I. The notion of dimension, Journal of ACM, 18, 2, 239-246 (1971) · Zbl 0218.68024 |
| [48] | Najman, L.; Couprie, M., Building the component tree in quasi-linear time, IEEE Transactions on Image Processing, 15, 11, 3531-3539 (2006) |
| [49] | Pavlidis, T., Algorithms for graphics and image processing (1982), Computer Science Press: Computer Science Press Rockville, Maryland · Zbl 0482.68086 |
| [50] | Papadimitriou, Ch.; Steiglitz, K., Combinatorial Optimization (1982), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0503.90060 |
| [51] | Preparata, F.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer: Springer New York · Zbl 0759.68037 |
| [52] | Rosenfeld, A., Classifying the literature related to computer vision and image analysis, Computer Vision and Image Understanding, 79, 2, 308-323 (2000) |
| [53] | Rubin, D. S., On the unlimited number of faces in integer hulls of linear programs with a single constraint, Operations Research, 18, 5, 940-945 (1970) · Zbl 0206.48901 |
| [54] | Russ, J. C., The Image Processing Handbook (2006), CRC Press · Zbl 0931.68133 |
| [55] | Schmidt, W. M., Integer points on curves and surfaces, Monatshäfte für Mathematik, 99, 45-72 (1985) · Zbl 0551.10026 |
| [56] | Shevchenko, V. N., On the number of extremal points in integer programming, Kibernetika, 4, 133-134 (1981) · Zbl 0468.90050 |
| [57] | Sivignon, I.; Coeurjolly, D., Minimum decomposition of a digital surface into digital plane segments is NP-hard, Discrete Applied Mathematics, 157, 3, 558-570 (2009) · Zbl 1168.68049 |
| [58] | Sivignon, I.; Dupont, F.; Chassery, J.-M., Decomposition of three-dimensional discrete objects surface into discrete plane pieces, Algorithmica, 38, 1, 25-43 (2003) · Zbl 1072.68118 |
| [59] | P. Urysohn, Über die allgemeinen Cantorischen Kurven, Annual meeting, Deutsche Mathematiker Vereinigung, Marburg, Germany, 1923; P. Urysohn, Über die allgemeinen Cantorischen Kurven, Annual meeting, Deutsche Mathematiker Vereinigung, Marburg, Germany, 1923 |
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.
