Open Issues and Chances for Topological Pyramids

Computer Vision Winter Workshop 2009, Adrian Ion and Walter G. Kropatsch (eds.) Eibiswald, Austria, February 4–6 Publisher: PRIP, Vienna University of Technology, Austria Open Issues and Chances for Topological Pyramids ∗ Walter G. Kropatsch 1and Helena Molina-Abril 1,2 1Vienna University of Technology, Faculty of Informatics, Pattern Recognition and Image Processing Group. 2University of Sevilla, Applied Math Department I, Spain. [email protected], [email protected] Abstract High resolution image data require a huge amount of computational resources. Image pyramids have shown high performance and flexibility to reduce the amount of data while preserving the most relevant pieces of information, and still allowing fast access to those data that have been considered less important before. They are able to preserve an existing topological structure (Euler number, homology generators) when the spatial partitioning of the data is known at the time of construction. In order to focus on the topological aspects let us call this class of pyramids “topological pyramids”. We consider here four open problems, under the topological pyramids context: The minimality problem of volumes representation, the “contact”-relation representation, the orientation of gravity and time dimensions and the integration of different modalities as different topologies. 1 Introduction Visual data are characterized with a large quantity of information and high redundancy. These data require a huge amount of computational resources (see Fig. 1). What is still true in 2D becomes even more demanding in 3D (e.g. CT and MR images in medicine; and image and video sequences in surveillance applications). The combination of 3D and time brings us quickly into a four dimensional discrete space where online performance is not yet achieved. Figure 1: A 2D, 3D and 4D visual data, and the storage capacity needed for each one of them. ∗Partially supported by the Austrian Science Fund under grant P20134- N13, the “Computational Topology and Applied Mathematics” PAICYT research project FQM–296 and the “Andalusian research project” PO6-TIC- 02268 Image pyramids are a stack of images with decreasing resolutions [4]. Such pyramids present the following interesting properties within the Image Processing and Analysis framework ([2]): •Reducing the influence of noise by eliminating less important details in lower-resolution versions of the image. •Making the processing independent of the resolution of the regions of interest in the image. •Converting global features to local ones. •Reducing the computational cost using the divide-and- conquer principle. •Finding regions of interest for plan-guided analysis at low cost in low-resolution images, ignoring irrelevant details. •Visual inspection of large images. •Increasing speed and reliability of image matching techniques by applying coarse-to-fine strategy. Figure 2: Pyramid structure Topology aims at studying properties of objects which are independent of geometrical transform. Some of these topological properties are useful in many applications, for example in matching and indexation of structured objects. A topological pyramid is an image pyramid where each level is a topologically equivalent representation of the initial data. The construction of the pyramid hierarchy follows the philosophy to reduce the data amount at each higher level 121 Open Issues and Chances for Topological Pyramids 1 of the hierarchy by a reduction factor λ > 1while preserving important topological properties like connectivity and inclusion. There are topological representations for structured objects that can be used in the hierarchical framework of topological pyramids. These representations are plane graphs, combinatorial maps and generalized maps [12]. The paper is structured as follows. Basic notions on irregular graph pyramids, combinatorial and generalized-map pyramids, and topological pyramids are recalled in Sections 1.1, 1.2 and 1.3. The four proposed open problems are presented in the following sections. The minimality problem of volumes representation is presented in Section 2, the “contact”-relation representation in Section 3, the orientation of gravity and time dimensions in Section 4, and the integration of different modalities as different topologies in Section 5. A summary is found in Section 6. 1.1 Irregular graph Pyramids Irregular graph pyramids are defined as a stack of successively reduced graphs [11]. In irregular pyramids, each level represents an arbitrary partition of the pixel set into cells, i.e. connected subsets of pixels. The construction of an irregular pyramid is iteratively local [15][8]. This means that we use only local properties to build the hierarchy of the pyramid. On the base level (level 0) of an irregular image pyramid the cells represent single pixels and the neighborhood of the cells is defined by the connectivity of the pixels. A cell on level k+1 (parent) is a union of neighboring cells on level k (children). This union is controlled by so called contraction kernels (decimation parameters [13]). Every parent computes its values independently of other cells on the same level. This implies that an image pyramid is built in O[log(d)] parallel steps being dthe image diameter. A level of a dual graph pyramid consists of a pair (Gk, Gk)of plane graphs (see Fig. 3), Gkand its geometric dual Gk, in order to correctly represent the embedding of the graph in the image plane [7]. Figure 3: A plane graph Gand its dual Gk The vertices of Gkrepresent the cells on level kand the edges of Gkrepresent the neighborhood relations of the cells. The edges of Gkrepresent the borders of the cells on level k, including so called pseudo edges needed to represent neighborhood relations to a cell completely enclosed by another cell. Finally, the vertices of Gk, represent junctions of border segments of Gk. 1.2 Combinatorial and Generalized-map Pyramids Combinatorial maps and generalized maps, define a general framework which allows to encode any subdivision of nD topological spaces orientable or non-orientable with or without boundaries. Combinatorial maps were introduced in [6], at first as a planar graph representation model, and extended in [14] in dimension nto represent orientable or not-orientable quasimanifolds. In dimension na combinatorial map is a (n+ 1)-tuple M= (D, β1, β2, ..., βn)such that Dis the set of abstract elements called darts, β1is a permutation on Dand the other βiare involutions on D(see Fig. 4). An involution is a permutation whose cycle has the length of two or less. The differences between combinatorial and generalized maps is that in the case of combinatorial maps, for each dimension, there is more than one way of attributing the permutations, but the number of permutations used for a certain dimension and how many of them are involutions is fixed. Figure 4: Combinatorial map where D = (1, -1, 2, -2, 3, - 3, 4, -4, 5, -5, 6, -6, 7, -7), β1(d) = −d∀d∈D,β2= (2,1)(−1,−4,3)(−2,6,5,4)(−5,7,−3)(−6,−7) A Combinatorial pyramid is a hierarchical stack of combinatorial maps. The definition is analogous for generalized pyramid and generalized maps [3]. 1.3 Topological Pyramids As mentioned before, a topological pyramid is a stack of topological encodings (graphs or maps). The basic operations to construct these hierarchies are edge contraction and edge removal. Some restrictions have been defined in order to preserve topology while applying these operations [9]. In that way connectivity, holes, Euler number and Betti number are preserved along the hierarchy. 122 Walter G. Kropatsch and Helena Molina-Abril This preservation allows topological pyramids to be a useful tool in many analysis and image processing applications, where this topological information is crucial. They are a useful i.e. to distinguish between different parts of an object, between solid objects and objects that enclose other objects, etc. As is shown in [16] topological information like homology generators is computed efficiently on the top level of a topological pyramid, since the number of cells is small. There are some open problems, in which analyzing and processing large amounts of data is necessary, and topological information need to be preserved. Organization and aggregation principles are needed in order to cope with the computational complexity. Topological pyramids promise to be very useful in order to solve this mega-data problems, in an efficient way. 2 Non-unique minimal configurations The extension of the pyramidal concept from 2D to 3D is a difficult issue dealing with dual graphs. On the other hand, the combinatorial map formalism has been defined in any dimensions. That is why the 3D pyramidal extension has been treated using this topological representations [9]. But although this mathematical model allows the construction of a 3D pyramid, the problem of non-unique minimal configurations arises. Combinatorial maps encode space subdivisions and all incidence relations [5][1]. The underlying representation of cellular complexes is based on so-called bounding relations. Each i-cell with i > 0is bounded by at least one (i-1)- cell; a volume is bounded by surfaces, a surface is bounded by curves and a curve is bounded by points. Consequently the smallest volumetric description consists of at least one volume (|V| ≥ 1), one surface (|S| ≥ 1), one curve (|C| ≥ 1) and one point (|P| ≥ 1). A combinatorial map will be considered minimal if it has the minimal possible number of i-cells. The top level of a combinatorial pyramid is the minimal topological equivalent representation of the initial data. To ensure that applying an operation on an i-cell will produce consistent combinatorial map topologically equivalent, some conditions need to be imposed [9]. Let us consider the minimal representation of the simplest 2D object (Fig. 5). It exists only one possible minimal configuration, as is shown in Fig. 5. This configuration contains a single face and one cell of each lower dimension [9]. Figure 5: 2D minimal configuration The simplest object in 3D, a filled sphere must satisfy the boundary representational constraint but also the Euler number (number of points minus number of curves plus number of surfaces minus number of vertices) must be one: |P|−|C|+|S|−|V|= 1. There are two possible solutions that also resulted as toplevel solution in 3D combinatorial pyramids [9]: either the number of points is two (|P|= 2,|C|= 1,|S|= 1,|V|= 1) or the number of surfaces is two (|P|= 1,|C|= 1,|S|= 2,|V|= 1), and all the other cells appear only once. These two configurations are shown in Fig. 6. Figure 6: 3D minimal configurations Different representations at the top of the pyramid occur in the simplest case of a 3D object, but also in many other 3D and 4D configurations. This non-uniqueness of the top of a combinatorial pyramid restricts the potential uses of combinatorial pyramids in pattern recognition, classification or identification applications. How can we deal with this two different descriptions of the same object? 3 Contact versus connectivity In most current representations connectivity is the main relation forming the structure of the composite objects. To introduce the concept of connectivity within the image context, we first need to introduce what is considered as a digital binary picture. In digital topology, following the terminology given in [10], a 3D digital binary-valued picture space (or, briefly, DPS) is a triple (V, β, ω).Vis the set of grid points in a 3D grid and the set β(resp. the set ω) determines the neighborhood relations between black points (resp. white points) in the grid. A 3D digital binary-valued picture is a quadruple I= (V, β, ω, B), where (V, β, ω)is a DPS and B(the set of black points) is a finite subset of V. Given a digital binary picture P, a black path (resp. white) in Pis a sequence p1, ..., pnof n≥1black points in P, in which each piis β(ω)-adjacent to pi−1(1 < i ≤n). Two black points p, q ∈Pare connected if there exist a black path in Pfrom pto q. Under this path connectivity concept, representation of cellular complexes is based on bounding relations; bounding surfaces separate volumes, bounding curves separate surfaces, and bounding points separate curves. In several real situations there is a variant of connectivity where cells are in contact but no real connectivity is established. If two people shake hands parts of the surface of their hands are in close contact without creating a connec- 123 Open Issues and Chances for Topological Pyramids 2 tivity between their bodies. Geometrically the two touching surfaces are aligned but their surface structure (e.g. texture) is not. It occurs also, when for example we put some clothes one over the other. Both surfaces are in contact, but not connected. In terms of cell complexes this corresponds to a surface being a neighbor of another surface contradicting the requirement that a surface always separates two volumes. Is it possible to model these two realities without any contradiction? 4 Oriented versus non-oriented dimensions There are important applications in which temporal behavior is critical. Treating time representation just as another dimension, we allow multiple configurations that are not plausible in real situations (see Fig. 7). For example, the age of objects is constantly increasing, and a consistent representation of this reality should not allow time decreasing configurations. A similar situation to time dimension occurs with gravity. The water in a glass of water remains there only if the glass is placed on a horizontal surface. Any rotation would change this state. Figure 7: A plausible and a not plausible situation If our representation allows this configurations that can not occur in practise, we need highly complex processes to recognized them, in order to distinguish between these configurations and all possible ones. To what extent can topological pyramids take thus oriented dimensions into account such that impossible configurations are excluded from being represented? 5 Different modalities, different topologies A window of a room physically separates the inside of the room from the outside. However it lets light go through creating pleasant and un-wanted visual artefacts on the surfaces of the inside objects while allowing the inside observer to see a part of the surrounding of the house. In terms of topology the window can be a solid part separating the inside of the room from the outside or it can be seen as a tunnel (a 1D hole) allowing light to enter the room. There are many more modalities (e.g. CT, MR, US in medicine; other frequency bands of the electro-magnetic spectrum) that can produce measurements that have different topologies but describe the same (part of) reality (see Fig. 8). Figure 8: Different pictures describing the same reality Modeling and integrating data from these different measurements will allow us to better represent the reality. How can we deal with this integration and modelization? Is there a “multi-modal” topology of which the different views are just a type of projection? Can we learn more about the properties of real world by combining and integrating the individual views? 6 Summary Four open problems are presented here: The minimality problem of volumes representation, the “contact”-relation representation, the orientation of gravity and timedimensions, and the integration of different modalities as different topologies. We propose topological pyramids, as a representation which has the chance to efficiently cope with the mega-data problem. In a future work, we plan to study possible solutions to these problems and how would topological pyramids be used to address them. References [1] Y. Bertrand, G. Damiand, and C. Fiorio. Topological encoding of 3d segmented images. In International Conference on Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, volume 1953, pages 311–324. Springer-Verlag, 2000. [2] M. Bisterand, J. Cornelis, and A. Rosenfeld. A critical view of pyramid segmentation algorithms. In PRL, pages 605–617, 1990. [3] L. Brun and W.G. Kropatsch. Introduction to combinatorial pyramids. In Digital and Image Geometry, Lecture Notes in Computer Science, volume 2243, pages 108–128. Springer-Verlag, 2001. [4] P. Burt, T-H. Hong, and A. Rosenfeld. Segmentation and estimation of image region properties through cooperative hierarchial computation. In IEEE Transactions on Systems, Man and Cybernetics, pages 802–809. IEEE, December 1981. [5] G. Damiand and P. Resch. Topological map based algorithms for 3d image segmentation. In DGCI 2002 Lecture Notes in Computer Science, volume 2301, pages 220–231. Springer-Verlag, 2002. 124 Walter G. Kropatsch and Helena Molina-Abril [6] J. Edmonds. A combinatorial representation of polyhedral surfaces. In Notices of the American Mathematical Society, page 646, 1960. [7] R. Glantz and W. G. Kropatsch. Plane embedding of dually contracted graphs. In Discrete Geometry for Computer Imagery, DGCI2000, Lecture Notes in Computer Science, pages 348–357, December 2000. [8] Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. G. Kropatsch. Logarithmic tapering graph pyramid. In L. van Gool, editor, Proceedings of 24th DAGM Symposium, pages 117–124, 2002. [9] T. Illetschko. Minimal combinatorial maps for analyzing 3d data. In Technical Report PRIP-TR-110,. Institute f. Automation 183/2, Dept. for Pattern Recognition and Image Processing, TU Wien, Austria, November 2006. [10] T.Y. Kong, A.W. Roscoe, and A. Rosenfeld. Concepts of digital topology. In Topology and its Applications, volume 46, pages 219–262, 1992. [11] W.G. Kropatsch. Equivalent contraction kernels and the domain of dual irregular pyramids. In Technical Report PRIP-TR-42. Institute f. Automation 183/2, Dept. for Pattern Recognition and Image Processing, TU Wien, Austria, 1995. [12] W.G. Kropatsch, Y. Haxhimusa, and P. Lienhardt. Hierarchies relating topology and geometry. In Cognitive Vision Systems, pages 199–220. Springer, October 2003. [13] W. G. Kropatsch. Building irregular pyramids by dual graph contraction. In IEE-Proc. Vision, Image and Signal Processing, pages 336–374, December 1995. [14] P. Lienhardt. Subdivisions of n-dimensional spaces and n-dimensional generalized maps. In Symposium on Computational Geometry, pages 228–236, 1989. [15] P. Meer. Stochastic image pyramids. In Computer Vision, Graphics, and Image Processing, pages 269–294, March 1989. [16] S. Peltier, A. Ion, W.G. Kropatsch, G. Damiand, and Y. Haxhimusa. Directly computing the generators of image homology using graph pyramids. Image and Vision Computing, December 2008. 125