Digitization

Digitization Dr. Rocio Gonzalez-Diaz rogo[email protected] Department of Applied Math, University of Seville, Spain Dr. Peer Stelldinger [email protected]burg.de Computer Science Department, University of Hamburg, Germany Professor Longin Jan Latecki latec[email protected] Department of Computer and Information Sciences, Temple University, USA 1 Definition Digitization is a mathematical model of converting continuous subsets of the plane or space (representing real objects) to digital sets in Z2or Z3or similar grids (representing segmented images of these objects). This definition can be generalized to any dimension n > 3: Digitization converts (transforms) continuous subsets of Rnto digital sets in Znor, equivalently, to functions from Zn to {0,1}. 2 Background A fundamental task of knowledge representation and processing is to infer properties of real objects or situations given their representations. In spatial knowledge representation and, in particular, in computer vision and medical imaging, real objects are represented in a pictorial way as finite and discrete sets of pixels or voxels. The discrete sets result by a quantization process, in which real objects are approximated by discrete sets. In computer vision, this process is called sampling or digitization and is naturally realized by technical devices like computer tomography scanners, CCD cameras or document scanners. Digital images obtained by digitization are suitable to estimate the real object properties like volume and surface area. Therefore, a fundamental question addressed in spatial knowledge representation is: Which properties inferred from discrete representations of real objects correspond to properties of their originals, and under what conditions this is the case? While this problem is well-understood in the 2D case with respect to topology [1, 2, 3, 4, 5], it is not as simple in 3D, as shown in [7]. Only recently a first comprehensive answer to this question with 1 respect to important topological and geometric properties of 3D objects has been presented in [8, 9]. Some recent works done for the general case are shown below. It is proven in [10] that although Gauss digitized boundaries of subsets of Rn, for n≥3 may not be manifolds, non-manifoldness may only occur in places where the normal vector is almost aligned with some digitization axis, showing that although an object and its digitization are close in the Hausdorff sense through the projection map, they may not be homemomorphic. Nevertheless, in that paper, the authors prove the validity of the digital surface integral as a multigrid convergent integral estimator of subsets of Rn, for n≥3, as long as the digital normal estimator is also multigrid convergent. In addition, [11] is a short survey on digital analytical geometry where the main idea is to analytically characterize digital sets to describe its continuous counterpart in Rn, for n≥3 and related transform. This way, digital subsets of Znare defined by a list of inequalities and not by an enumeration of points in Zn. Finally, in [12], a modus operandi is proposed to model a digital subset of Znas a cubical complex proving that the digital fundamental group of a digital subset of Znis isomorphic to the fundamental group of its corresponding cubical complex, ensuring the topological correctness of the approach. Thus, properties of digital subsets of Zncan be computed on their corresponding cubical complexes using powerful Algebraic Topological tools. Observe that this last approach ‘closes’ a loop: starting from a continuous subset of Rn, a digital subset of Znis obtained and used to compute a cubical complex whose embedding in Rnis again a continuous subset of Rn. The description of geometric and, in particular, topological features in discrete structures is based on graph theory, which is widely accepted in the computer science community. A graph is obtained when a neighborhood relation is introduced into a discrete set, e.g., a finite subset of Z2or Z3, where Zdenotes the integers. On the one hand, graph theory allows investigation into connectivity and separability of discrete sets (for a simple and natural definition of connectivity see [13, 21], for example). On the other hand, a finite graph is an elementary structure that can be easily implemented on computers. Discrete representations are analyzed by algorithms based on graph theory, and the properties extracted are assumed to represent properties of the original objects. Since practical applications, for example in image analysis, show that this is not always the case, it is necessary to relate properties of discrete representations to the corresponding properties of the originals. Since such relations can describe and justify the algorithms on discrete graphs, their characterization contributes directly to the computational investigation of algorithms on discrete structures. This computational investigation is an important part of the research in computer science, and in particular, in computer vision (Marr [14]), where it can contribute to the development of more suitable and reliable algorithms for extracting required shape properties from discrete representations. It is clear that no discrete representation can exhibit all features of the real original. Thus one has to accept compromises. The compromise chosen depends on the specific application and on the questions which are typical for that application. Real objects and their spatial relations can be characterized 2 using geometric features. Therefore, any useful discrete representation should model the geometry faithfully in order to avoid false conclusions. Topology deals with the invariance of fundamental geometric features like connectivity and separability. Topological properties play an important role, since they are the most primitive object features and human visual system seems to be welladapted to cope with topological properties. However, one does not have any direct access to spatial properties of real objects. Therefore, real objects are represented as bounded subsets of the Euclidean space R3, and their 2D views (projections) as bounded continuous subsets of the plane R2. Hence, from the theoretical point of view of knowledge representation, the goal is to relate two different pictorial representations of objects in the real world: a discrete and a continuous representation. Already two of the first books in computer vision deal with the relation between the continuous object and its digital images obtained by modeling a digitization process. Pavlidis [1] and Serra [2] proved independently in 1982 that an r-regular continuous 2D set S(the definition follows below) and the continuous analog of the digital image of Shave the same shape in a topological sense. Pavlidis used 2D square grids and Serra used 2D hexagonal sampling grids. In 3D this problem is much more complicated. In 2005 it has been shown in [7] that the connectivity properties are preserved when digitizing a 3D r-regular object with a sufficiently dense sampling grid, but the preservation of connectivity is much weaker than topology. Stelldinger and K¨othe [7] also found out that topology preservation can even not be guaranteed with sampling grids of arbitrary density if one uses the straightforward voxel reconstruction, since the surface of the continuous analog of the digital image may not be a 2D manifold. The question how to guarantee topology preservation during digitization in 3D remained unsolved until 2007. The solution was provided in [8], where the same digitization model as Pavlidis and Serra is used, also r-regular sets (but in R3) are used to model the continuous objects. As already shown in [7] the generalization of Pavlidis’ straightforward reconstruction method to 3D fails since the reconstructed surface may not be a 2D manifold. For example, Figure 1 shows a continuous object and its digital reconstruction whose surface is not a 2D manifold. However, it is possible to use several other reconstruction methods that all result in a 3D object with a 2D manifold surface. Moreover it is also shown in [8] that these reconstructions and the original continuous object are homeomorphic and their surfaces are close to each other. The first reconstruction method, Majority interpolation, is a voxel-based representation on a grid with doubled resolution. It always leads to a wellcomposed set in the sense of Latecki [15], which implies that a lot of problems in 3D digital geometry become relatively simple. The second method is the most simple one. It just uses balls with a certain radius instead of cubical voxels. When choosing an appropriate radius the topology of an r-regular object will not be destroyed during digitization. The third method is a modification of the well-known Marching Cubes algo- 3 Figure 1: The digital reconstruction (b) of an r-regular object (a) may not be well-composed, i.e., its surface may not be a 2D manifold as can be seen in the magnification rithm [16]. The original Marching Cubes algorithm does not always construct a topologically sound surface due to several ambiguous cases [17, 18]. As shown in [8, 9] most of the ambiguous cases can not occur in the digitization of an r-regular object and that the only remaining ambiguous case always occurs in an unambiguous way, which can be dealt with by a slight modification of the original Marching Cubes algorithm. Thus the generated surface is not only topologically sound, but it also has exactly the same topology as the original object before digitization. Moreover it is shown that one can use trilinear interpolation and that one can even blend the trilinear patches smoothly into each other such that one gets smooth object surfaces with the correct topology. Each of these methods has its own advantages making the presented results applicable to many different image analysis algorithms. In the general case, well-composed digital subsets of Zndo not present topological paradoxes. They also have very interesting properties and practical applications. Different “flavors” of well-composedness (WC) are present in the literature: WC based on equivalence of connectivities (EWC), digital WC (DWC), WC in the Alexandrov sense (AWC) and WC in the continuous sense (CWC). All these definitions are equivalent in 2D. For the 3D case, we have: DWC ⇔AWC ⇔CWC. For the nD case, n≥3, we have: EWC ⇐DWC. The rest of equivalences for the case n > 3 are open problems nowadays. The definition of well-composedness has also been extended to arbitrary grids and multivalued images (AGWC), see [19]. Methods for repairing digital subsets of Zn, for n > 3, to convert them in well-composed ones is a complicated open problem. A first step in this direction is done in [20] in which a combinatorial method is given for computing a simplicial complex homotopy equivalent to the cubical complex associated to a given 4 Figure 2: We start from I= (Zn, FI) being FIa digital subset of Zn(in fact, FI⊂4Zn). The digital subset FJof Znencodes the cells of the associated cubical complex Q(I) (blue is used for 0-cells, red for 1-cells and green for 2- cells). Now, we ‘repair’ FJto obtain the digital subset FLof Znby ‘thickening’ the critical points of FJ. Then, we compute the simplicial complex PS(I) whose set of vertices is FL, satisfying that there exists a face-connected path of nsimplices in PS(I) joining any two n-simplices incident to a common vertex in PS(I), that is, PS(I) is weakly well-composed, see [20]. digital subset of Zn. This simplicial complex is continuously well-composed for n≤3 and weakly well-composed for n > 3 in the sense that for any two nsimplices incident to a common vertex v, there always exists a face-connected path of n-simplices incident to v. A graphical diagram of the method is given in 2. Observe that cubical and simplicial complexes derived from that method are also stored as digital subsets of Zn, so that later calculations on the elements of the complex can be done efficiently. 3 Theory The (Euclidean) distance between two points xand yin Rnis denoted by d(x, y), and the (Hausdorff) distance between two subsets of Rnis the maximal distance between each point of one set and the nearest point of the other. Let A⊂Rn and B⊂Rmbe sets. A function f:A→Bis called homeomorphism if it is bijective and both it and its inverse are continuous. If fis a homeomorphism, then Aand Bare homeomorphic. Let A,Bbe two subsets of Rn(particularly, n= 2 or 3). Then a homeomorphism f:Rn→Rnsuch that f(A) = B and d(x, f(x)) ≤r, for all x∈Rn, is called an r-homeomorphism of Ato B and Aand Bare r-homeomorphic. A Jordan curve is a set J⊂Rnwhich is homeomorphic to a circle. Let Abe any subset of Rn. The complement of Ais denoted by Ac. All points in Aare foreground while the points in Ac are called background. The open ball in Rnof radius rand center cis the set 5 Figure 3: For each boundary point of a 2D/3D r-regular set exists an outside and an inside osculating open r-disc/ball Figure 4: (a) Critical configuration (C1). (b) Critical configuration (C2). For the sake of clarity, only the voxels of foreground or background points are shown B0 r(c) = {x∈Rn|d(x, c)< r}, and the closed ball in Rnof radius rand center cis the set Br(c) = {x∈Rn|d(x, c)≤r}. The boundary of A, denoted ∂A, consists of all points x∈Rnwith the property that if Bis any open set of Rn such that x∈B, then B∩A6=∅and B∩Ac6=∅. An open ball B0 r(c) is tangent to ∂A at a point x∈∂A if ∂A∩∂B0 r(c) = {x}. An open ball B0 r(c) is an osculating open ball of radius rto ∂A at point x∈∂A if B0 r(c) is tangent to ∂A at xand either B0 r(c)⊆A0or B0 r(c)⊆(Ac)0, where A0is a maximal open subset of A, i.e., Awithout its boundary. Definition 1 A set A⊂Rnis called r-regular if, for each point x∈∂A, there exist two osculating open balls of radius rto ∂A at xsuch that one lies entirely in Aand the other lies entirely in Ac. Examples illustrating 2D and 3D cases are shown in 3. Note that the boundary of a 3D r-regular set is a 2D manifold surface. Any set Swhich is a translated and rotated version of the set 2·r0 √3Z3is called a cubic r0-grid and its elements are called sampling points. Note that the distance d(x, p) from each point x∈R3to the nearest sampling point s∈Sis at most r0. The voxel VS(s) of a sampling point s∈Sis its Voronoi region R3: 6 VS(s) = {x∈R3|d(x, s)≤d(x, q),∀q∈S}, i.e., VS(s) is the set of all points of R3which are at least as close to sas to any other point in S. In particular, note that VS(s) is a cube whose vertices lie on a sphere of radius r0and center s. Definition 2 Let Sbe a cubic r0-grid, and let Abe any subset of R3. The union of all voxels with sampling points lying in Ais the digital reconstruction of Awith respect to S,ˆ A=Ss∈(S∩A)VS(s). This method for reconstructing the object from the set of included sampling points is the 3D generalization of the 2D Gauss digitization (see [21]) which has been used by Gauss to compute the area of discs and which has also been used by Pavlidis [1] in his sampling theorem. For any two points pand qof S,VS(p)∩VS(q) is either empty or a common vertex, edge or face of both. If VS(p)∩VS(q) is a common face, edge, or vertex, then VS(p) and VS(q) are face-adjacent,edge-adjacent, or vertex-adjacent, respectively. Two voxels VS(p) and VS(q) of ˆ Aare connected in ˆ Aif there exists a sequence VS(s1), . . . , VS(sk), with k∈Zand k > 1, such that s1=p,sk=q, and si∈A(or equivalently, VS(si)⊂ˆ A), for each i∈ {1, . . . , k}, and VS(sj) and VS(sj+1) are face-adjacent, for each j∈ {1, . . . , k −1}. A (connected) component of ˆ Ais a maximal set of connected voxels in ˆ A. Definition 3 Let Sbe a cubic r0-grid, and let Tbe any subset of S. Then St∈TVS(t)is well-composed if ∂(St∈TVS(t)) is a surface in R3, or equivalently, if for every point x∈∂(St∈TVS(t)), there exists a positive number rsuch that the intersection of ∂(St∈TVS(t)) and B0 r(x)is homeomorphic to the open unit disk in R2,D={(x, y)∈R2|x2+y2<1}. Well-composed digital reconstructions can be characterized by two local conditions depending only on voxels of points of S. Let s1, . . . , s4be any four points of Ssuch that T4 i=1 VS(si) is a common edge of VS(s1), . . . , VS(s4). The set {VS(s1), . . . , VS(s4)}is an instance of the critical configuration (C1) with respect to St∈TVS(t) if two of these voxels are in St∈TVS(t) and the other two are in (St∈TVS(t))c, and the two voxels in St∈TVS(t) (resp. (St∈TVS(t))c) are edge-adjacent, as shown in Figure 4a. Now, let s1, . . . , s8be any eight points of Ssuch that T8 i=1 VS(si) is a common vertex of VS(s1), . . . , VS(s8). The set {VS(s1), . . . , VS(s4)}is an instance of the critical configuration (C2) with respect to St∈TVS(t) if two of these voxels are in St∈TVS(t) (resp. (St∈TVS(t))c) and the other six are in (St∈TVS(t))c(resp. St∈TVS(t)), and the two voxels in St∈TVS(t) (resp. (St∈TVS(t))c) are vertex-adjacent, as shown in Figure 4b. The following theorem from [15] establishes an important equivalence between well-composedness and the (non)existence of critical configurations (C1) and (C2). Theorem 1 ([15]) Let Sbe a cubic r0-grid and let Tbe any subset of S. Then, St∈TVS(t)is well-composed iff the set of voxels {V(s)|s∈S}does not contain any instance of the critical configuration (C1) nor any instance of the critical configuration (C2) with respect to St∈TVS(t). 7 Figure 5: The surface of an object only needs to have an arbitrarily small, but nonzero curvature in order to make occurrences of the critical configuration (C1) possible in the digital reconstruction A simple consequence of the 2D digitization theorem by Pavlidis [1] is that the reconstruction of an r0-regular set is well-composed. The main difficulty of 3D digitization as compared to 2D lies in the fact that digital reconstruction ˆ Aof Awith respect to Sis not guaranteed to be well-composed. An example is provided in 5. Therefore, it is necessary to repair ˆ Ain order to ensure the topological equivalence between Aand repaired ˆ A. The first topology preserving repairing method has been proposed in [8], where also the following theorem is proven. It is an interesting observation that it took 25 years to obtain this 3D theorem. Theorem 2 ([8]) If Ais an r-regular object and Sis a cubic r0-grid with 2r0< r, then the result of the topology preserving repairing of the reconstruction ˆ Ais r-homeomorphic to A. 4 Application A complete understanding of the loss of information due to the digitization process is fundamental for the justification of any computer vision application. If the relevant information is not contained in the digital image, there is no way to reconstruct it without using context knowledge. Thus, whenever one needs to have guarantees for the correct behavior of some computer vision algorithm one has to be aware of what happens during digitization. This article gives an exemplary insight to the topic, the related problems and the way to solve them. 8 5 Open Problems The analysis of the effect of digitization to the information being extractable from an image is a challenging research area. Newest results approximate real acquisition processes and thus give direct implications for many computer vision algorithms which rely on precise information of the structures being approximated by the digital image. However, in reality the digitization process is still more complicated than the models which are used for topological or geometric sampling theorems. The goal is to derive guarantees for digitization models approximating real digitization processes. For the case n≥3, the equivalences between the different definitions of well-composedness (EWC, DWC, AWC, EWC, AGWC) is an open problem together with a general method for repairing non-well-composed digital sets in Zn. Besides, the study of which properties well-composed images own in Zn that reflect the continuous world is a promising line of research, such as, the link between critical points and Morse theory [23] or topological persistence [24] and tree of shapes. A more exhaustive list can be consulted in [19, Section 10]. References [1] Pavlidis T (1982) Algorithms for graphics and image processing. Computer Science Press, Cambridge [2] Serra J (1982) Image analysis and mathematical morphology. Academic, San Diego [3] Latecki LJ, Conrad C, Gross A (1998) Preserving topology by a digitization process. J Math Imaging Vis 8:131–159 [4] Latecki LJ (1998) Discrete representation of spatial objects in computer vision. Viergever M (ed) Series on computational imaging and vision. Kluwer, Dordrecht [5] Tajine M, Ronse C (2002) Topological properties of hausdorff discretization, and comparison to other discretization schemes. Theor Comput Sci 283(1):243–268 [6] Stelldinger P, K¨othe U (2003) Shape preservation during digitization: tight bounds based on the morphing distance. In: Pattern recognition, DAGM 2003, Munich, pp 108–115 [7] Stelldinger P, K¨othe U (2005) Towards a general sampling theory for shape preservation. Image Vis Comput J 23(2):237–248 [8] Stelldinger P, Latecki LJ, Siqueira M (2007) Topological equivalence between a 3D object and the reconstruction of its digital image. IEEE Trans Pattern Anal Mach Intell 29(1):126–140 9