A Pragmatic Qualitative Approach for Juxtaposing Shapes

A Pragmatic Qualitative Approach for Juxtaposing Shapes Lledó Museros (Universitat Jaume I, Castellón, Spain [email protected]ji.es) Luis González-Abril (Universidad de Sevilla, Sevilla, Spain luisg[email protected]) Francisco Velasco (Universidad de Sevilla, Sevilla, Spain [email protected]) Zoe Falomir (Universitat Jaume I, Castellón, Spain [email protected]) Abstract: This paper presents a qualitative shape description scheme which has been defined in order to have a formal theory to allow the construction of new shapes from a set of given shapes by using a juxtaposition operation. Specifically, the qualitative shape description scheme defined is a pragmatic scheme since it has been defined in order to be applied in the automatic and intelligent assembling of trencadís mosaics. Keywords: Qualitative Shape Description, Shape Description Scheme, Trencadís Categories: I.2.4, I.2.1, I.4.10 1 Introduction Shape description is now a major field of study in the disciplines of computer vision, robotics, pattern analysis and recognition, computer graphics, image processing and computer-aided design and manufacture. Although there are studies for describing the shape of an object, shape description is still challenging. This is due to the fact that it is particularly difficult to describe computationally a shape, because when a three dimensional object is projected from the real world onto a two-dimensional image plane, one dimension of the object information is lost. Therefore, the shape extracted from a digital image of the object only represents the projected object partially. Moreover, digital images are often corrupted with noise, defects, arbitrary distortion and occlusion. Because of the numerical properties of digital images, most of the image processing in computer vision has been carried out by applying mathematical models and other quantitative techniques to describe and identify the shape of the objects contained in an image ([Mehtre, Kankanhalli and Lee, 1997; Rucklidge, 1997; Peura Journal of Universal Computer Science, vol. 16, no. 11 (2010), 1410-1424 submitted: 5/1/10, accepted: 28/5/10, appeared: 1/6/10 © J.UCS and Iivarinen, 1997; Belongie, Malik, and Puzicha, 2001; Zhang and Lu, 2002; Lu and Sajjanhar, 1999; Morse, 1994]). Most of these quantitative approaches for shape description have succeeded in the task for which they were designed. However, we have decided to tackle the problem of shape description and identification qualitatively because from a cognitive point of view visual knowledge about shape is qualitative in nature, and therefore we believe that, in this way, we are using a process closer to that which human beings use to describe shapes. Moreover, qualitative approaches describe the shape of objects by focusing only on its relevant information, and therefore they are able to manage uncertainty better than the quantitative ones. They also can speed up the description and recognition processes because they do not rely in complex mathematical functions to describe the objects. In [Museros and Escrig 04a], a qualitative theory able to describe different types of shapes is presented. It can describe regular and non-regular closed shapes, whose boundaries can be completely straight, or curved, or a mixture of both. These shapes may also contain holes whose shape and location can also be described by our approach. To be precise, it is based on qualitative representations of: angles, types of curvature, length of the edges, convexities, and concavities. This theory has been applied to different domains, as the industrial domain [Museros 06] or the mobile robot navigation domain [Museros and Escrig 04b]. These applications provide evidence for the effectiveness of using qualitative information to describe and identify shapes. But, given some new applications where for instance it is necessary to create new shapes from two other given shapes, we have found the need of extending the theory developed in [Museros and Escrig 04a]. To create a new shape we need to define the operations of juxtaposition, addition, intersection and difference of shapes. For instance, in order to create a cognitive map of the environment of a robot it is usually necessary the description of a new shape from other given shapes. Another example arises in the industrial domain, as in the case of trencadís ceramic mosaics, where it is necessary to create a design with prior unknown shapes. Trencadís (figure 1) is a type of ceramic artistic mosaic which involves using broken tile shards to create the mosaics. The trencadís manufacturing process, accomplished manually, requires extensive labor to align and adjust the pieces of tile during the assembly. Currently, the pieces are barely placed onsite, but a set of predefined patches with different measures (so-called meshes or blankets, typically 0.5 m in size) are prefabricated and afterwards mounted onsite. The unstructured task of producing trencadís patches needs intelligent methods and sophisticated perceptual capabilities to be automated. Indeed, human operators apply a whole set of situationsensitive rules to decide on the next piece to place, its position within the current mosaic border, and how to fit it. Moreover, the way in which the geometry of the piece is perceived is also situation dependent. The key to construct a good trencadís is to choose pieces with similar sizes, ordered in a way that they seem a puzzle leaving a space between each piece in order to fix them with cement. 1411 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... Figure 1: Example of trencadís mosaic at Güell Park (Barcelona) This paper presents an extension of the qualitative shape description theory in [Museros 06] in order that it will be able to construct new shapes from a set of given shapes by juxtaposing two of them. In fact, the new theory is a qualitative shape description scheme. Moreover, the approach presented here is our first approximation for juxtaposing shapes which will be suitable to be used in the trencadís industrial application, because in order to be able to assembly a trencadís it is necessary to define how we are going to juxtapose shapes. The theory presented can be also applied in other applications, such as the selfassembling of structures in nano-technology and robotics. Next section presents a brief state of the art about shape description schemes, section 3 describes an overview of the qualitative shape description theory presented in [Museros 06]. Then, the extension of this theory in order to be able to juxtapose two shapes in a suitable way to apply it on the trencadís assembling problem is described. Finally, our conclusions and future work are explained. 2 State of the art about shape description schemes A shape description scheme is a notational system for expressing the shapes of objects, just as we use notation to express music or electronic circuitry. In the study of shape description schemes we can observe two trends: • The pure approach in which the study of the subject is regarded as a selfsufficient exercise in pure thought. In this approach, the studies deal primarily with the question of “what” rather than “how”. The studies are often very rigorous and logically well-connected with each other, but cannot be readily applied to solve practical problems. • The pragmatic approach in which a method or scheme is conceived as a response to the needs of a particular problem (an application in the real world). In this approach, the studies deal primarily with the question of “how” rather than “what”. The studies are useful for the purpose of practical application, but are highly intuitive and, therefore they often lack rigor. 1412 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... Therefore, as the pragmatic approaches are purpose-oriented, the choice of a description scheme must be guided by the problem context. In literature we can find shape descriptions schemes which have been used with much success to study and represent past and contemporary architectural and other designs [Ahmad and Chase 04; Andaroodi et al. 06; Chase 89; Knight 94; Lebigre 01; Stiny 80a], and they have been used also into the education and practice field [Halatsch et al. 08; Stiny 80b; Wang and Duarte 98]. In this paper we develop a new qualitative shape description scheme which, to the best of our knowledge, is the first pragmatic and qualitative approach which is able to juxtapose shapes in order to solve the problem of automatically assembling a trencadís mosaic. Therefore, it is not possible to carry out any comparative study with our approach. 3 Overview of the qualitative shape description theory To make this paper self-contained we now explain the qualitative shape description theory presented in [Museros 06], where a fuller explanation can be found. Shape description using reference-points information will have to make use of some reference points. As reference points we understand these points which completely specify the boundary. For polygonal boundaries we have chosen the vertices as reference points. For circular shapes and curvilinear segments in a shape we have chosen three points: the starting and the end point of the curve and its point of maximum curvature. The qualitative description of a reference point, named j, is determined using the previous reference point, named i, and following reference point, named k. The order of the reference points is given by the natural cyclic order of the vertices of closed objects. We only have to determine the sense in which we visit or describe each reference point, which should be the same for the description of all the objects. We have chosen to visit the vertices in a counter-clock sense. The description of each reference point is given by a set of three elements (triple) which can differ if these elements are from straight segments of curvilinear ones: • In the case of straight segments the triple is <Aj,Cj,Lj>, where Aj means the angle for the reference point j, Cj means the type of convexity of point j and Lj means the compared relative length of the edges associated to reference point j (edge formed by vertices i and j versus edge formed by vertices j and k), where: Aj ∈{right-angle, acute, obtuse}; Cj ∈ {convex, concave} and Lj belongs to the compared Length Reference System (LRS), where LRS = {smaller, equal, bigger}. The suitable label is associated to each reference point or vertex by comparing the Euclidean distance of the edges sharing the vertex. • In the case of curvilinear segments the triple is <Curve,Cj,TCj>, where the symbol Curve means that the node in the description string is describing a curve, Cj means the type of convexity of point j and TCj means the type of curvature of the curve associated to the point j, where: Cj ∈ {convex, concave} and TCj ∈ {plane, semicircle, acute} 1413 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... To describe the objects with holes the topological concept of Completely Inside Inverse (CIi) is used [Isli, Museros et al. 00], due to the fact that the hole is always Completely Inside (CI) the boundary of the closed objects. The cardinal reference system by Frank [Frank 91] is used in order to relate the orientation of the hole inside the object. Determining the orientation of each hole inside the container is necessary because we can have an object with a hole which the boundaries of containers are equal and boundaries of the holes too, but the hole is placed in other position of the container and then they are not the same object. The orientation is fixed using Frank’s Cardinal Reference System (CRF). The CRF is defined by placing its origin into the centroid of the object. Then once the CRF is placed in the centroid of the object the orientation of the hole with respect to the container is calculated, for instance figure 2 calculates the orientation of the hole with respect to the container, obtaining that the hole is [NE,E,SE] oriented inside the container. We call centre (C) to the orientation that occurs when the hole is placed around the centroid, and all orientations hold. Figure 2: Example of the Orientation Calculation of a hole with respect to its container in which we observe the CRF placed in its centroid. Color is also stored in the description as RGB coordinates for later comparisons when matching objects. Therefore, the complete description of a shape of a 2D object is defined by the following tuple: [type_hole, type_curve, [Color, [A1, C1, L1 | Curve, C1, TC1] … [An, Cn, Ln | Curve, Cn, TCn]], CIi, Orientation, [type_curve, [AH1, CH1, LH1 | Curve, CH1, TCH1] … [AHj, CHj, LHj | Curve, CHj, TCHj]], where n is the number of vertices (reference points) of the container and j is the number of vertices (reference points) of the hole. The type_hole symbol may have one of the following values [without holes, with holes], and the symbol type_curve may adopt one of the following values [without curves, with curves, only curves]; both symbols are introduced to accelerate the correspondence or recognition process. Color is the RGB color of the figure described by the three basic components, the Red, Green, and Blue coordinates. Each vector, [Ai, Ci, Li | Curve, Ci, TCi], represents a qualitative description node, which may be the description of a vertex of a straight line segment, then taking on the form [Ai,Ci,Li], with i=1,..,n, where A1, …, An, are the qualitative angles of each vertex; C1, …, Cn are the types of convexity of each vertex and L1, …, Ln are the relative lengths of each pair of adjacent edges to each of the vertices of the straight line segments of the container; or second tuple [Curve, Ci, TCi] which represents the qualitative description of a curvilinear segment and is formed first by the Curve symbol to indicate that this is a curvilinear segment and 1414 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... then by the labels C1, …, Cn, and TC1, …, TCn, which are the qualitative description of the type of convexity and the type of curvature, respectively. The same occurs with the hole container: AH1, …, AHj, CH1, …, CHj and LH1, …LHj, are the qualitative angle, type of convexity, and relative length of the adjacent edges of each of the vertices of the straight line segments of the hole and CH1, …, CHj, and TCH1, …, TCHj are the type of convexity and type of curvature of the curvilinear segments of the hole. CIi is the topological relation that relates the hole to its container, as already explained in the foregoing section. Finally, the Orientation is one or a set of orientation relations given by the CRF, in order to provide the relative position of the hole in regard to its container. CIi, the Orientation, and the description of the hole boundaries only appear when the object is of the type with holes and will appear as many times as is the number of holes in the figure Figure 3 shows an example of the complete description of a shape with a hole, rectilinear and curvilinear segments and its qualitative shape description, formally named QualShape(S), being S the reference to the object described. Thus, the complete description of the shape in Figure 3 is: QualShape(S)=[with-holes, with-curves, [[0,0,0], [right-angle, convex, bigger], [curve, convex, acute], [right-angle, convex, bigger], [right-angle, convex, smaller], [right-angle, convex, bigger]], CIi, C,[[right-angle, convex, smaller], [right-angle, convex, bigger],[right-angle, convex, smaller], [right-angle, convex, bigger]]]. Figure 3: Example of the Orientation Calculation of a hole with respect to its container in which we observe the CRF placed in its centroid. It is worth noting that an advantage of the theory is its lineal computational cost. The temporal computational cost for the worst case need for the construction of a qualitative description of the figures is of the order O(N+M*K), where N is the number of vertices of the container, M is the number of vertices of the holes and K is the number of holes ([Museros 06]). 4 The pragmatic qualitative scheme for juxtaposing shapes For extending the theory presented previously we define a qualitative shape description scheme. A shape description scheme is a notational system for expressing the shape of objects. Our approach uses the definition of shape description scheme given in [Ghosh and Deguchi 08] in order to create a qualitative shape description scheme. A shape description scheme is defined by a 4-tuple as follows: (P, *, C, A), 1415 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... where: • P is a set of primitive shapes, • * is a set of functions/operations, called shape operators, • C is a set of production rules, which specifies how the shape operators are to be used to construct new shapes from the already existing shapes, • And A is a set of explicit axioms, which specify conditions that each constructed shape must satisfy. In a sense, A is a set of constraints or restrictions. In a shape description scheme, the set A may or may not be present. Figure 4 shows a graphical example of the process of juxtaposing two shapes. Figure 4: Graphic example of the juxtaposing operation between two shapes. The symbol “*” in figures specifies the edges that should be considered during the juxtaposing operation. Next we define the 4-tuple for our qualitative shape description scheme. In section 4.1 the set of primitives is defined, section 4.2 establishes the shape operators, and in sections 4.3 and 4.4 the set of production rules and explicit axioms are respectively described. Finally, in section 4.5 an example of the application of the new qualitative shape scheme to juxtapose two shapes is presented and section 4.5 characterizes this scheme. 4.1 The set of primitives P The set of primitives P is the set of the regular and non-regular polygonal shapes described by the qualitative shape description theory presented in section 3. Therefore the shapes to be juxtaposed can contain convex and concave segments. In this approach we have not considered shapes with holes or shapes with curvilinear segments due to the application to which it is oriented. In fact, when assembling a trencadís mosaic, it is not lightly to have broken tiles with holes or with curvilinear segments. 4.2 The shape operators * The set * contains the qualitative juxtaposition operator, named +q. In order to juxtapose two shapes it is necessary to indicate the related edges in +q. For instance if we want to juxtapose shape in Figure 5a) with shape in Figure 5b) we have to indicate that the juxtaposition has to be done considering the edge going from vertex 2 to 3 in 1416 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... Figure 5a) and the edge going from vertex 4 to 1 in Figure 5b). Therefore we have defined next notation for the qualitative juxtaposition operation: A(i) +q B(m) (1) Where A, B are shapes to be juxtaposed, and i and m indicates the first vertex of the edge (in a counter-clock sense) to be considered in the juxtaposition operation. For instance the result of A(2) +q B(4) is graphically shown in figure 6. Figure 5: a) First operand in an adding operation, b) second operand. Figure 6: Shape C, resulting of A(2) +q B(4), given figures A and B in figure 5. The operator +q accomplish the commutative law. In fact A(2) +q B(4) = B(4) +q A(2). Moreover, for +q the identity element is the empty set, which means that there is no shape to juxtapose. 4.3 The set of production rules C The set of production rules C describes how to apply the juxtaposition operator. This set is defined by the following Extended Backus-Naur Form (EBNF) production rules: Regioni::= Vertex+ (minimum 3 vertices) Vertex::= <A, C, L> A ::= obtuse | right | acute C ::= concave | convex L ::= smaller | equal | bigger Then, when computing the +q operation of 2 vertices we obtain: <A1,C1,L1> +q <A2,C2,L2> = <A3, C3, L3> where: A3 ⊆ {obtuse, right-angle, acute, ∅} C3 ⊆ {convex, concave, ∅} L3 ⊆ {smaller, equal, bigger, ∅}. 1417 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ... When juxtaposing two vertices it can happen that in the resulting shape these vertices disappear (figure 6 is an example, where vertices 2 and 3 in figure A and 1 and 4 in figure B disappear). If this happens then the symbol ∅ is used. To compute A3, C3, and L3 we have to define three tables. The first table (table 1) is applied to calculate the angle A3 knowing the angle A1 and A2. For instance, if A1 is acute and A2 is right, using table 1 we can determine that the new angle A3 will be obtuse. In the case that there are several possibilities when adding A1 and A2 then the set of possible angles is given. A2 A1 Acute Right Obtuse Acute {Acute, Right, Obtuse} Obtuse Obtuse Right Obtuse Obtuse Obtuse Obtuse Obtuse Obtuse Obtuse Table 1: +q angle table. Table 2 is used to calculate the new convexity C3. Convexity information depends on the angle information too, therefore table 2 computes C3 considering the convexity of C1 and C2 and angles A1, and A2. Note that it is not possible to create a new shape by adding two concave vertices. Table 3 is used to calculate the compared length L3 of the new shape. To calculate this table, following the constraints defined in set A, we have considered that the edges being juxtaposed have approximately the same length. Using this tables, a region R3 is the +q of regions R1(i) and R2(j) if: • It has a minimum of |R1| + |R2| -4 vertices, and a maximum of |R1| + |R2| -2, being |R1| the number of vertices in R1 and |R2| the number of vertices in R2; • Each vertex vi in R3 must be: o Equal to one of the original vertices in R1 and R2, o or the result of applying the +q operation to one vertex of R1 and another of R2 C2 C1 Concave (any angle) Convex + Acute Angle Convex + Right Angle Convex + Obtuse Angle Concave (any angle) Not Possible Concave Concave Concave Convex + Acute Angle Concave Convex Convex {Convex, ∅} Convex + Right Angle Concave Convex ∅ Concave Convex + Obtuse Angle Concave {Convex, ∅} Concave Concave Table 2: +q convexity table. 1418 Museros L., Gonzalez L., Velasco F., Falomir Z.: A Pragmatic Qualitative Approach ...