AP1_03.vp 1 Overview of Q-code schemes: principles 1.1 General principles: key-ideas of qualitative shape encoding When we look at a complex image, we do not see every de- tail of the shape in order to recognize the image, but we see and identify the characteristic features and particular config- urations and register them in our memory [30]. The Q-code scheme looks at a shape and encodes only shape characteris- tics. The following general principles of shape encoding illustrate the key ideas for understanding the construction of qualitative shape encoding schemes. The first principle of a Q-code scheme is the encoding of shape characteristics on particular nodes where qualitative changes occur. The system looks at the nodes on the shape contour and captures particular distinctive geometric charac- teristics around the nodes. On each singular node, a range or landmark value for a particular design quality or shape attrib- ute is abstracted into a single symbol, a Q-code, in such a way that any value in the range is considered to be the equivalent qualitative value of the particular attribute. Consequently, we get finite numbers of Q-codes for a shape as a symbolic representation for that shape. Each Q-code is constructed in such a way that particular shape characteristics are abstracted into a combination of symbols in order to encapsulate a geo- metric phenomenon in terms of attribute class and value range. The shape characteristic captured on singular nodes greatly simplifies the shape information in representation whilst containing essential ingredients for discriminating the idiosyncrasies of a particular shape from the geometric range. The second principle of a Q-code scheme is that a shape is encoded to give an ordered sequence that provides a descrip- tive structure for the shape contour. Qualitative description of a shape forms a Q-code list as an ordered sequence of symbols in which the head and tail symbols are connected to form a circuit. This symbol order corresponds to the sequence of singular nodes scanning for the geometric characteristics from the shape contour, and this symbol circuit can be used to tell us various shape information: how complicated each shape is, what geometric patterns repeat themselves and how they repeat, and how similar two shapes are to each other. The third principle of a Q-code scheme is discretisation. This means that the encoding of a continuous shape contour yields a set of discrete symbols. It is discrete in the sense that the symbolic value for particular shape qualities captures only one status of the qualitative degree from the value set of finite numbers, and each symbol is discrete from each other. It also means that only particular points, or in other words only singular nodes, on a contour line are liable to be encoded into Q-codes. The discrete property of the qualitative symbolic shape encoding method is one of the reasons why the Q-code scheme is effective in symbolic computation such as pattern matching. The discretisation principle also makes it possible to meet the various task requirements of shape representation 6 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 Class Representation of Shapes Using Qualitative-codes Ashraf Fouad Hafez Ismail This paper introduces our qualitative shape representation formalism that is devised to overcome, as we have argued, the class abstraction problems created by numeric schemes. The numeric shape representation method used in conventional geometric modeling systems reveals difficulties in several aspects of architectural designing. Firstly, numeric schemes strongly require complete and detailed information for any simple task of object modeling. This requirement of information completeness makes it hard to apply numeric schemes to shapes in sketch level drawings that are characteristically ambiguous and have non-specific limitations on shape descriptions. Secondly, Cartesian coordinate-based quantitative shape representation schemes show restrictions in the task of shape comparison and classification that are inevitably involved in abstract concepts related to shape characteristics. One of the reasons why quantitative schemes are difficult to apply to the abstraction of individual shape information into its classes and categories is the uniqueness property, meaning that an individual description in a quantitative scheme should refer to only one object in the domain of representation. A class representation, however, should be able to indicate not only one but also a group of objects sharing common characteristics. Thirdly, it is difficult or inefficient to apply numeric shape representation schemes based on the Cartesian coordinate system to preliminary shape analysis and modeling tasks because of their emphasis on issues, such as detail, completeness, uniqueness and individuality, which can only be accessed in the final stages of designing. Therefore, we face the need for alternative shape representation schemes that can handle class representation of objects in order to manage the shapes in the early stages of designing. We consider shape as a boundary description consisting of a set of connected and closed lines. Moreover, we need to consider non-numeric approaches to overcome the problems caused by quantitative representation approaches. This paper introduces a qualitative approach to shape representation that is contrasted to conventional numeric techniques. This research is motivated by ideas and methodologies from related studies such as in qualitative formalism ([4], [6], [19], [13], [31]), qualitative abstraction [16], qualitative vector algebra ([7], [32]), qualitative shapes ([18], [23], [21]), and coding theory ([20], [25], [26], [1], [2], [3], [22]). We develop a qualitative shape representation scheme by adopting propitious aspects of the above techniques to suit the need for our shape comparison and analysis tasks. The qualitative shape-encoding scheme converts shapes into systematically constructed qualitative symbols called Q-codes. This paper explains how the Q-code scheme is developed and applied. Keywords: class representation, shape, qualitative-codes, scheme, properties of qualitative values, linguistic analogy. efficiently. Discrete symbols can take in different levels of abstraction by way of changing granularity for a symbol in order to respond in various encoding details. The fourth principle of a Q-code scheme is that all the properties of a qualitative value set of this representation scheme comply with qualitative formalism. Qualitative for- malism indicates a strict conversion process from a range of continuous numeric values into a range consisting of discrete qualitative sign values set by landmarks and intervals. This qualitative formalism will be explained later in this paper. One of the important principles of a Q-code scheme is the consistency maintenance of the relativity principle applied in measuring the geometric attributes. Qualitative shape rep- resentation works well both for absolute and relative measure- ments, yet the relative measurement of geometric attributes is only possible with a qualitative scheme, whilst absolute measurement is an encoding method that can be accom- plished equally by both quantitative and qualitative methods. The Q-code scheme looks at the geometric characteristics occurring between, or on, the singular nodes of a shape con- tour and converts them into discrete symbols. The encoding system detects the singular nodes and transforms the numeric values for particular shape attributes into discrete Q-codes that are formed in combination with a character and sign values. 1.2 Qualitative values and their properties The study of qualitative physics and qualitative reasoning suggests a rigorous formalism for setting qualitative sign val- ues for a specific quality in mechanical modeling ([4], [29], [31]). The essence of qualitative formalism lies in the setting of landmark values for the continuous range of particular numeric values and abstracting the intervals with range values in terms of signs (�, 0, +). Landmarks stand for critical points where qualitative changes occur. This qualitative formalism thus takes a specific technique on the method for setting land- marks to the numeric range. Properties of qualitative values Those qualitative values that are constructed from qualita- tive formalism correspond to numeric values whilst showing different aspects from the quantitative values. Some of the properties of qualitative values are as follows [31]: • Coverage of a quantitative value range: The qualitative value should cover all the quantitative value range for interesting phenomena. • Finite number of values: The number of qualitative values should be finite. • Quantitative-qualitative interpretation: It should be possi- ble to interpret quantitative results with qualitative values (where such quantitative results exist). • Exclusiveness of a qualitative value: Qualitative values should not overlap with other qualitative values in terms of the corresponding quantity space. • Granularity of a qualitative value: When quantitative values represent similar attributes of objects, then the qualitative values should be similar to a certain degree. • Order of a qualitative value: Qualitative values should be ordered. In addition to the properties mentioned above, there are the following additional properties: • Polarity: Instead of having an absolute scale of measure- ment as in quantity space, qualitative values are distin- guished by the relative scale of two extreme values of polarity and • Discrete sign values: Polarizing values in two contrasting qualities is symbolically denoted using sign values. The degree of discretisation can further be distinguished by more detailed granularity, which is indicated by multiple sign values. Qualitative value setting and Q-code primitives The Q-code scheme developed here represents shape contours using four sets of Q-codes that capture most basic shape attributes. The four basic shape attributes are vertex angles, relative lengths, curvature, and convexity of edges, and their numeric values are converted to Q-codes based upon relativity to landmarks. Q-codes are assigned to a set of particular nodes on a shape contour. The qualitative value for a vertex angle is assigned on a vertex node whilst length and curvature changes measured from a comparison of adjacent edges are assigned to singular nodes where qualitative change occurs. Figure 1 illustrates the nodes where qualitative values are assigned. Defining a set of discrete Q-codes for shape attributes traces the following process: Step 1: From the given continuous numeric value range of a particular shape attribute, landmarks are set to the signifi- cant value points. The landmark value set “L” is defined by a number of landmarks as: � �L � � �l l l1 0 1, , . For example, for the given numeric value ”n” whose range is 0 1� �n or [0 1], three landmark points can be assigned to L 1 ={0, 0.5, 1}. Step 2: Finite numbers of ranges are assigned to the intervals and points that are discrete to each other. Interval and point value set “I” is defined by a number of ranges as: � � � � � � �I � �� � � � � �l l l l l l l l l l1 1 1 0 0 0 0 1 1 1, , , , , , , , , where “[ ]” means the range inclusive of the limits and “( )” means the range exclusive of the limits. For example, the interval set “I1” for the above landmark set “L1” is � � � � � � �I 0, 0 0, 0.5 0.5, 0.5 0.5, 1 1, 11 � , , , , . Step 3: Qualitative values are set for the intervals and land- marks. The qualitative value set “Q” is those symbols assigned to the interval value sets as: � �Q q q q q q� � � � �2 1 0 1 2, , , , . The qualitative value set “Q1” for the interval set “I1” is © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 7 Acta Polytechnica Vol. 41 No. 3/2001 �� � Fig. 1: Nodes for qualitative value assignments � �Q1 1 2 3 4 5� � � � � �, , , , . The above process explicitly shows the principle of polarity and granularity of a qualitative value. Sign values are generally used in qualitative schemes because of their efficiency in han- dling polarity and granularity. When a significant value point is selected as a landmark for a given range of numeric values, it results in two intervals and a point, such that a landmark point separates two groups of ranges: smaller and bigger value ranges to the landmark. These two contrasting ranges necessarily construct a qualitative distinction across the land- mark value. In other words, a landmark results in two symbolic polar values around the point and this relation is best represented with sign values, {�, 0, +}, each of which can be literally interpreted as having a weaker, medium, or stronger property for a particular design quality. The simple and basic polarization can further be specified into detailed intervals. More landmarks to the value range mean higher granularity, and their corresponding sign values can be, for example, such as {� �, �0, �+, 0, +�, +0, ++} where {�0, 0, +0} refer to the landmark points whilst {� �, � +, + �, ++} refer to the intervals. These landmarks and intervals can be literally interpreted as very weak, medium weak, slightly weak, medium, slightly strong, medium strong and very strong with regard to a particular design quality. Qualitative value setting formalism can be applied for most the design values provided with a corresponding quantitative value range. Many design simulation tasks han- dle a group of design properties and attributes in terms of variables and values. Design properties and attributes can basically be grouped into three categories: those regarding function, behavior, or structure [10]. Design properties in the structure domain are represented with variables the values of which are measurable straightforwardly in a quantitative way. Those design properties in the structure domain contain vari- ables such as considering an object in terms of its shape and material: • Shape: size, geometry, spatial position and relation. • Material: color, texture, and weight. Amongst the various structural domains of design, the Q-code scheme takes shape attributes for 2-D shape contours. A continuous array of nodes and edges forms a 2-D shape. There are two kinds of nodes: singular and regular nodes [15]. Two singular nodes define an edge and in between there are continuous traces of regular nodes. Defining a shape contour with a set of finite nodes and edges has the following benefits: • Discrete description: A finite set of discrete elements separates finite segments from a continuous shape contour line. • Segmentation of shape characteristics: It is possible to conceive shape contours with segments and to compare the value for particular shape characteristics or properties to that of the neighboring segments. • Value assignment on nodes: Either rectilinear or curvilinear edge segments are defined with nodes. It is thus sufficient that values describing shape characteristics can be collected from the nodes. Shapes are described with all the values assigned to nodes. • Quantitative-qualitative correspondence: Node-based shape re- presentation is applicable either to numeric or qualitative chemes, and a set of ranges for numeric values can be assigned to nodes, which can then be converted to qualita- tive symbolic codes. Amongst the various shape attributes, four are considered the most basic because they are concerned with the definition of lines, and a shape is defined as a continuous and connected set of lines. These four shape attributes are: • Vertex angle between two edges: Shape attribute measuring an inner angle at a vertex. • Length of edge: Shape attribute measuring the traces be- tween two nodes. • Curvature of edge: Shape attribute about how an edge is curved. • Convexity of edge: Shape attribute about the convex and con- cave property of an edge. Four Q-code sets have been developed for the qualitative representation of these attributes: These are A-, L-, K- and C-codes for vertex angle, relative lengths of edges, curvature of an edge, and convexity of an edge, respectively. The relative measure of magnitude One of the advantages of the qualitative shape representa- tion scheme is that it provides a comparative and relative way of measuring for the magnitude of various kinds of geometric values. Magnitudes of geometric attributes considered in this Q-code scheme are: angle, length, curvature and convexity. Q-codes capture those magnitudes in a relative manner so that qualitative distinctions can be made amongst the shapes. Q-codes are assigned to every vertex by comparing how much smaller or bigger is the magnitude change that occurs on the vertex. One Q-code contains two parts: a character symbolizes the shape attribute that the Q-code is encoding and a combi- nation of sign values, as below. � �� �Q Char� sign value The A-code set The basic Q-code is the A-code, which covers the angle attribute so that any critical change of angular magnitude is captured with this Q-code. The major angular change occurs on a node (vertex) where two curvilinear or rectilinear edges meet. The angular landmark is initially set to the angle p, which distinguishes a convex angle from a concave angle. The scanning order for each node on a shape contour is set to be counter-clockwise and the magnitude of the vertex inner angle is measured in a clockwise direction between two edges. The vertex angle for curvilinear edges is measured to, or from, the tangential line on that vertex. Figure 2 shows how 8 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 Fig. 2: Illustration of angle measurements at nodes vertex inner angles are measured for either rectilinear or curvilinear edges. The numeric value range “N” for the magnitude of a node angle is 0 2� �N �. Within this finite numeric value range, landmarks are set for the points of particular geometric importance. The following are the sets of land- marks for vertex angles from the simplest granularity. • Mid-point in the value range: The value point “�” along with two limits of “0” or “2�” forms the important landmark that divides the numeric value range into two: acute angles (smaller than �) and obtuse angles (bigger than �). The land- mark set “L” is then L = {0, �}. • Quarter-points in the value range: Right angles are particu- larly important to designers. Thus multiples of right an- gles in the value range make important landmarks. This set of landmarks divides the range into four sub-ranges along with four point values. The landmark set “L” is now L = {0, �/2, �, 3�/2}. The landmark set determines the interval set from the numeric value range into a finite number of intervals and points. Interval sets for each landmark set are as follows (see Figure 3): • The first interval set � � � �� �I IA A1 1 0 0 0 2: , , , , ,� � �� � �� � . • The second interval set IA2 with a higher granularity: � � � � � � � � �� I A2 0 0 0 2 2 2 2 3 2 3 2 3 2 3 2 2 � , , , , , , , , , , , , , , , . � � � � � � � � � � � � � The A-code set is assigned to each interval element as follows: • The first A-code (Ax-code) set QA1: � �Q A A A AA nil1 0� � �, , , . • The second A-code (Axx-code) set QA2: � �Q A A A A A A A AA nil2 0 0 0� � � � � � � � � � �, , , , , , , . The A-code is constructed with the character “A” denoting angle and sign values {�, 0, +}. The sign value “nil” is assigned to the landmark point [0, 0] even though there is usually no practical angle measurement for zero magnitude on a vertex. A Q-code value denoting a range is set by the relativity principle such that a geometric value is compared to that of landmarks and consequently signs are assigned to the nodes. This indicates the relative magnitude of the angle to the landmarks. The A-codes in the set of � �A A A�, ,0 + are literally interpreted as angles having a smaller, equal or bigger magnitude than the landmark point “�”. Consequently, the A- code tells us about the relative angle at landmarks. This relative angular measurement is different from the absolute numeric measurement of angles. It is only concerned with the relative difference of magnitude com- pared to the critical value point. The Ax- code tells us if it is a convex or concave angle so that one single Q- code can rep- resent all the possible numeric values, for example, for the convex angle, as the Axx- code does for the acute or obtuse angles. This abstract representation is the advantage of this qualitative scheme because a single Q- code can indi- cate numerous possible individuals with common shape characteristics. The L-code set A Q-code that captures the geometric characteristics of edge length is labeled an L- code. This L- code takes the value for a relative length rather than an absolute length. Relative length means that the lengths of two adjacent edges are compared with each other resulting in the mea- surement for the change in the length magnitude on a vertex. A comparison of the lengths of two adjacent edges considers two different and one sharing nodes from two neighboring edges as shown in Figure 4. Comparison of length magnitudes results in a relative measurement, which, is indicated by signs of {�, 0, +}. Landmarks are set to the points so that a qualitative dis- tinction between two adjacent edges is possible. There can be no fixed numeric points for L- code landmarks. What matters is whether an edge is shorter or longer compared to that of the previous one. As geometric characteristics are scanned node by node in counter- clockwise direction, the magnitude of the previous edge becomes the landmark point for the next one. Thus landmarks and intervals are set each time when a new edge is compared. The following are two sets of land- marks for the relative length attribute: • Identical point landmarks: A landmark is set to the numeric point indicating a magnitude identical to the previous edge length. This landmark provides the ratio in order to distin- guish the relative difference under the labels of smaller and bigger. Thus the L- code measures the difference in lengths between the previous edge and the current edge. If there is a variable “d” measured as: d = Current edge length – Previous edge length; d = {Positive, Zero, Negative} then the identical point landmark L1 is set to the nu- meric point where d = 0. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 9 Acta Polytechnica Vol. 41 No. 3/2001 [A] 1 interval set st [B] 2 interval set nd Fig. 3: Interval sets for 1st and 2nd level A-codes 4 5 6 1 2 2 3 4 5 5 6 1 2 3 Fig. 4: Illustration of length comparisons of two adjacent edges • Half and double point landmarks: When the qualitative dis- tinction of smaller or bigger does not provide sufficient de- tail, the L-code can be extended to higher granularity so as to distinguish, for example, much smaller and slightly smaller from the label smaller. Figure 5 shows the land- marks and sign values for the L- code. Interval sets are determined by the first and second landmark sets as follows: • First interval set I1: � � �� �I1 0 0 0 0� �� �, , , , , ; • Second interval set I2: � � � � � � �� �I 2 1 1 1 1 0 0 0 0 1 1 1 1� �� � � � � �, , , , , , , , , , , , , . L- codes are assigned to those interval elements. • L-code set QL1: � �Q L L LL1 0� � �, , , each of which may be interpreted with the labels {Smaller, Equivalent, Big- ger} in terms of length. • L- code set QL2: � �Q L L L L L L LL 2 0 0 0� � � � � � � � � � �, , , , , , . Figure 6 shows an illustration of A- and L-code encod- ing of an architectural shape. The K- code set Curvilinear edges differ from rectilinear edges in two ways: changes of curvature and convexity. Curvature and convexity determine the geometric characteristics of a curvilinear edge in terms of the direction and configura- tion of the curves. Specific Q-codes are thus designed to describe the qualitative difference in the change of curva- ture and convexity for a finite number of curve segments. A curve segment is an edge bounded by two singular nodes, and the curvature k, at a node in the curve, is mea- sured as an inverse of radius r of the curve as 1/r [15]. The curvature of any node on a straight-line edge is “0”. A critical change of curve segments occurs on singular nodes. Figure 7 (a) is an example of a regular node whilst (b), (c) and (d) are examples of singular nodes: (a) Regular point; (b) Inflection point; (c) 1st cusp; (d) 2nd cusp [15]. The first type of singular node is an inflection point on which the point on the curve continues in the old direction whilst the image reverses its direction. The second type of singular node is the 1st cusp on which the point on the curve reverses its direction whilst the image continues in the old direction. The last type of singular node is the 2nd cusps on which the point on 10 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 d = 0 d = 0half double � � � � � � � � � � � � � � � � Fig. 5: Illustration of intervals and signs for L- codes Fig. 6 Illustration of Q-code encoding (a) (b) (c) (d) Fig. 7: Illustration of regular and singular nodes on curves the curve and the tangential image both reverse their direc- tion [15]. Since major changes of curve property occur on these singular nodes, Q- codes are assigned on these nodes to represent the curve characteristics in terms of curvature and convexity. Curvature is concerned with the magnitude of a particular curve property whilst convexity concerns the direction of the curve property. The relative change of curvature between two curves is represented with K- codes, which capture neither the change of convexity nor the change of direction of a contour line, but only the change of curvature. Every regular node, with no change in the direction and the image of a tangential line, has a k0 code, which means the curve segment has no curvature change. However, regular nodes are not the subjects of Q- code encoding. Singular nodes with directional change, but no change in tangential image regardless of reflection, are also encoded with k0. Only those singular nodes with dis- crete change in their curvature will be coded with other K- codes with “�” and “+” signs. Figure 8 shows examples of k0 nodes that show no curvature change regardless of either the change in direction or reflection of the image. As L- codes compare the edge property to a landmark with no fixed numeric value, K-codes are also defined in a similar manner. The qualitative difference of the curvature property is determined by taking the magnitude of this property from the previous edge and comparing it to that of the current edge. Thus the landmarks are not set to particular absolute numeric values. They are, however, set as a relative magnitude to the previous edge segment. Landmarks are set to points with significant changes in curvature. • Primary landmark: The primary K- code landmark is set to a point with any change of curvature for two adjacent edges. The degree of curvature change at a node, dk, for the curvature k is determined as follows: �d k at current node at previous node� �k k . Any node with significant curvature change will have a positive or negative dk value. A point with dk equals “0”, thus marking a landmark point. The landmark set L for the first level is L = {0} in terms of dk value. The interval sets for each landmark set are as follows: • Interval set: � � �� �I � �� �, , , , ,0 0 0 0 . A range with a negative or positive value. • Denotes an increase or decrease of curvature at a node. K- codes are assigned to each element in the interval set. K- code set: � �Q k k kk � �, ,0 + . Figure 9 illustrates the scope of K+ and K� codes. The dot- ted lines indicate two equal tangential images to the previous edge forming the boundary limits of curvature for K- codes. The C-code set Basic shape descriptions are possible with the three types of Q- codes: A-, L- and K- codes. When we deal with curves, however, there is another aspect to consider which cannot be handled with curvature alone. Apart from curvature, the con- vexity of a curve tells us about the direction in which the curve bends. This is captured by a set of C- codes. Convexity handles the direction that describes how the curves bend along a contour line. A convex curve contains no straight line that traces the outside of the shape when drawn from the inside of the shape, as shown in Figure 10 (b). Oppo- site is the concave curve that contains a straight line that traces the outside of the shape when drawn from the inside of the shape, as shown in Figure 10 (c). The convexity of a curve © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 11 Acta Polytechnica Vol. 41 No. 3/2001 Change of direction Change of direction Change of tangential K0 K0 K0 K0 Fig. 8: Illustration of nodes with k0 codes K� K� Direction Tangential line Bounding limits of curvature (for K )0 Fig. 9: Illustrations of K-codes can also be geometrically determined by the tangential line change. If the slope of a tangential line does not change when we trace the shape contour in a counter-clockwise direction, then the convexity of the line is ”0”, meaning a straight line, as in Figure 10 (a). When the slope increases during the trace, in other words if the tangential line moves in a counter-clock- wise direction, the convexity of the line is positive (convex), as in Figure 10 (b). On the contrary, if the slope decreases along the trace, or if the tangential line moves in a clockwise direc- tion along the trace, the convexity of the line is negative (con- cave), which means the line is concave, as in Figure 10 (c). Observing this, the primary convexity landmark is set to the point with zero convexity. For a slope change of the tangential line, St, as tracing shape contour in a counter- - clockwise direction, a landmark is set to the point with St “0”, which distinguishes a convex curve from a concave curve. All curves are classified into three types according to Sk: a convex curve with positive Sk, a straight line with “0” Sk, and a concave curve with negative Sk. Consequently, we have a landmark set L = {0} in terms of Sk, and an interval set is I={(� , 0), [0, 0], (0, )}. There is a transition from convexity measures to C- codes. Since convexity is a measure for an edge and a Q- code is assigned to a node, we need a set of rules for converting the convexity measures of two adjacent curves t o C - codes. Figure 11 shows some of the cases for C- code determination based upon a convexity measure. Conversion of convexity-change to C- code is also shown in the Cayley diagram in Table 1. Table 1: From convexity measures of two adjacent curves to C- codes curve 1/curve 2 – 0 + – C0 C+ C+ 0 C� C0 C+ + C� C� C0 Consequently, we have C- codes, � �Q c c cc � �, ,0 + , as- signed to the nodes between two curves. These primary C- codes are only concerned with a critical change of convex- ity, such as those between two different signs, so that any trivial change in the convexity measure under the equivalent sign produces a c0 code, as shown in Figure 11 and Table 1. A comparison of four Q-code sets We examined four types of Q- codes that capture four different shape attributes. When shape is represented with Q- codes, each code captures shape characteristics such as vertex angle, relative length, curvature change and convexity change, and assigns the information to nodes. 12 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 (a) A curve with convexity “0” Inside Tangential line Direction (b) A curve with positive convexity Inside A line drawn from the inside (c) A curve with negative convexity Fig. 10: Geometric determination of a curve convexity C0 C0 C� C� C� C� C� C� C0 �� � � �� � � � 0 �0 �0 0 0 � 0 Fig. 11: Illustration of the C-code assignment C K� � C K� � C K0 � K K0 � Fig. 12: Exceptional combinations of K- and C-codes at the node of Anil code Primary Q- code sets are � �A A A Anil 0 +, , , ,� , � �L L L� �, ,0 , � �k k k� �, ,0 and � �c c c� �, ,0 . Consequently, it is possible to combine these Q- codes on a node with few exceptions. Exceptional combinations of C- and K- codes occur at the node of Anil code, as shown in Figure 12. There are possibly five types of K- and C- code combina- tions in Anil code. c� and c+ codes can only correspond to k+ and k� codes, whilst c0 code can take all three K- codes. As for other A- codes, any L-, K- and C- codes can correspond to them, as shown in Figure 13. Consequently, a node could take one of 96 different combinations of primary A-, L-, K- and C- codes. These 96 different types become the qualitative granules from which the primary Q- code scheme distinguishes shape characteristics from the infi- nite quantitative variations. 1.3 Changing granularity of Q- codes for multiple-level descriptions Primary Q- codes describe the most basic qualitative dis- tinctions for shape attributes. Therefore, primary sets of Q- codes should to abstract shape characteristics most effi- ciently. They should also be able to expand their granularity when more detailed qualitative distinctions are required. As shown in the Q- code definitions in this section, the granularity for each set of Q- codes varies according to the in- tervals assigned to their corresponding numeric value ranges bounded by a pair of landmark points. Finer granularity pro- duces more detailed Q- codes representing smaller ranges of instances. Thus granularity and class abstraction are inversely proportional to each other. We need finer granularity for the following occasions: • Clearer distinction for similar groups of geometric patterns. • Identification of individual differences rather than abstract categorizations. • Acquiring more syntactic patterns under a particular geo- metric attribute. The changing granularity for Q- codes becomes a matter of changing landmarks and intervals. We use bisection as the generic method. With the bisection method, we can create additional landmarks in the middle of each interval. Q- code bisection is illustrated in Figure 14. Q- code bisection contains the following four steps: landmark determination, the inter- val bisection, sign value determination and Q- code creation: • Landmark determination: A single point of the interval is taken as a new landmark point, which is mostly set to the mid-point of the interval. It is sometimes the half point or the double point of a particular measure. A pair of new intervals is set to left and right ranges along the landmark point. • Interval bisection: The original interval is divided into two sub-ranges by a new landmark point. • Sign value determination: New sign values are assigned to new intervals and landmark points, whilst the sign value for the existing landmark remains unchanged. New landmark points add “0” to the signs of existing inter- vals whilst intervals of smaller and bigger values to the landmark, that are on the left- and right-hand sides of the landmark, add additional “�” and “+” to the sign value of the previous interval. • Q- code creation: Consequently, a new set of Q- codes is cre- ated with the combination of a character symbol and new sign values. Multiple-level description of shape characteristics gives the Q- code scheme advantages over other shape representa- tion methods, such as chain coding [8], and qualitative vector algebra ([32], [18]). A shape contour produces several differ- © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 13 Acta Polytechnica Vol. 41 No. 3/2001 C K� � C K� � C K� � C K� � C K0 � K K0 � C K0 � K K0 �C K+ � K K0 � C K+ � K K0 � Fig. 13: K- and C-code combinations for the A- code nodes ��� �� ��� ���� ��� �� �� � �� �� � �� � � � � � �� �� � � � � ��� �� ��� ��� �� ���� 1 set st 2 set nd 3 set rd Fig. 14: Granularity change by Q-code bisection ent qualitative geometric descriptions according to various Q - code granularities, providing the most efficient qualitative characteristics of the shape yet maintaining the class repre- sentation of common individuals. Multiple-level description is necessary for handling special cases of shape representa- tion, as follows: • Synchronous description for several discrete geometric at- tributes with varying abstractions. • Multi-level resolutions for shape patterns. • Multi-class interpretations on a group of similar shapes. Multiple-description of shape characteristics using vary- ing granularity of Q- codes makes it possible to classify, for in- stance, a group of four rectilinear shapes into a quadrilateral class or into subsequent class labels, such as square, rectangle, parallelogram, trapezoid and diamond according to how we set the A- code granularity. Repeating edge patterns, such as saw-teeth, can also be abstracted into a class or a set of sub-classes by varying the granularity of A-, L-, K- and C- codes. Varying granularity for Q- codes provides the dy- namic shape encoding capability that produces the optimum level of shape representations best suited for the expected qualitative abstraction. 2 Encoding formalism 2.1 Shape, shape elements and corresponding Q- code chunking Shape as an aggregation of closed and connected lines There is a hierarchical conceptual structure on which the Q- code scheme is based. It is assumed that a shape contains geometric characteristics that can be encoded with a symbolic representation scheme, and the shape is defined by its con- tour lines. On the contour line, there are a finite number of singular nodes on which Q- codes are assigned. Thus a shape is considered as a single complete unit that contains finite numbers of shape characteristics. The Q- code shape encod- ing scheme, therefore, has a conceptual structure in such a way that lower conceptual units aggregate together to form a higher unit and this aggregation continues to its higher conceptual units. Obviously the lowest unit for the Q- code scheme is the Q- code that takes shape information on a node. These Q- codes are ”chunked” together to form a higher conceptual unit that implies geometric patterns on a shape contour. These patterns are contained in their higher unit as a shape. A group of connected shapes, similarly, can be noted by a unit that is conceptually higher than a shape. As a complete conceptual unit, a shape becomes the target and basis for Q- code encoding and analysis. A shape nor- mally refers to any finite arrangement of lines (straight, curved, open or closed) with pictorial characteristics ([27], [28]). However, we specifically define a shape as an aggrega- tion of closed and connected lines ([11], [12], [24]) so that a shape refers to the 2-D plane contour lines which form the boundary of a shape. The terms shape and form are used, normally, in distinguishing 2-D contour images and 3-D solids. Shape is the most abstract geometric description of an object image. The shape of an object, therefore, indi- cates the essential pictorial information that excludes all the other material attributes, such as texture, line weight and color from the object description. Consequently, we use the term shape to refer to the 2-D contour of an object that is closed and connected with lines that are geometrically defined excluding all the material attributes. Complete shape and geometric patterns are represented by Q- codes. The Q- code description of a geometric pattern should be a subset of the Q- code encoding of the shape, and the difference between these two is the connection. The first and the last Q- codes of a shape encoding are conceptually connected to each other to form a circuit, whilst a geometric pattern has a Q- code encoding that does not form a circuit. Since a shape is described as a circuit of Q- codes, we consider different orders of the Q- code sequences for an identical shape to be equivalent. Q- code encoding of a design de- scription are analyzed according to chunks of encoding with different levels of shape patterns. The concept can best be understood with an analogy to natural language. Linguistic analogy of shape elements There are conceptual units according to how Q- codes are chunked. These units are hierarchical to each other and they show several discrete levels in terms of shape description. These units handle a shape configuration through Q- code chunking starting from a specific shape attribute and qualita- tive symbolic values at a node, to a set of geometric patterns on a shape contour, to a shape that is complete and discrete, and finally to the shape aggregation. The Q- code scheme suggests a set of terminology for these conceptual units. This terminology corresponds to familiar terms used in linguistics. The matching of each term in linguistics and the Q- code scheme is shown in Table 2. Table 2: Matching terms in linguistics and in the Q-code scheme Chunking Terms in linguistics Terms in Q- code scheme Primary symbol Alphabet Q- code First chunking Word Q- word Second chunking Phrase Q- phrase Third chunking Sentence Q- sentence Fourth chunking Paragraph Q- paragraph This linguistic analogy of Q- code chunking suggests that there are specific structures and definitions for different groupings of Q- codes. The variety of Q- code chunking also suggests that there could be different levels of shape analysis tasks according to different levels of cognitive processes for shapes. 2.2 Definitions of basic concepts in encoding formalism The following is the definition for four important Q- code chunking units and their meaning in shape description. We start with the definition of the Q- code, followed by the Q- sen- tence, and then the Q-word. The Q- code (�) � � � �� �� �� � � � ��i iA, L, K, C , , ,0 The Q- code “�” forms the base symbol in the encod- ing formalism. Four categories of Q- codes – A-, L-, K- and C- codes – are constructed for those geometric attributes “�” 14 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 of angle, length, curvature and convexity by combining a sin- gle character {A, L, K, C} with sign values {+, 0, –}. Q- codes are determined as relative size values by comparing numeric values from the landmarks. Table 3 shows how qualitative values are assigned to each shape attribute. The Q- sentence (�) � �� � � �� 1 2 m, , ,� where m = lenght (�) The Q- sentence refers to a discrete shape as a set of closed and connected lines. It is a finite sequence of Q- codes in the form of a circuit and it includes Q-words and Q- phrases as its syntactic subsets. The Q- sentence is represented as a loop of Q- codes such that only the order of the sequence matters. In this way, it distinguishes itself from the Q-word and the Q- phrase. The Q- word ( ) � � � � � � � � � � � � � � � � � � i i j i j k or , , , , , , i j m k j i i m 1 1 1 2� The Q-word is a sequence of Q- codes and it is a subset of the Q- sentence. Q-words do not have a structure as a circuit and they refer to the subset patterns of a shape contour with a particular design meaning. The Q-word can be as big as the length of a Q- sentence and the shortest length of a Q-word is “1”. 1 � length (Q- word) � m Table 4 shows four important Q- code units and their natural language analogy. 3 Representations of shapes 3.1 Representation of a singular shape The Q- code scheme aims to encode shapes based only upon shape information that excludes other pictorial infor- mation such as materials and spatial relations. The basic unit that completes a circuit is the shape that is indicated by a re- gion bounded by a finite set of nodes and edges. A shape is understood as a Q- sentence in the Q- code scheme and a sin- gular shape is a complete shape that is independent from other shapes around it. The Q- code encoding of a singular shape follows a series of straightforward steps. A shape, that is a Q- sentence, is a superset that contains dependent sets of Q- words and Q - phrases, which are also defined as a series of Q- codes. Consequently, a shape encoding is the primary process that is followed by detection processes for Q- words and Q- phrases. A Q- sentence is a circuit of Q- codes and each Q- code corresponds to each node of a shape. Each node is © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 15 Acta Polytechnica Vol. 41 No. 3/2001 A- code L- code/K- code/C- code Numeric value range 0 � � � 2� � � 1, k, c � Landmark set {0, �} {� , 0, } Interval set {[0, 0], (0, �), [�, �], (�, 0)} {(� , 0), [0, 0], (0,+ )} Q-code set {Anil, A�, A0, A+} {L�, L0, L+}, {K�, K0, K+}, {C�, C0, C+} Table 3: Qualitative value assignments to shape attributes A� A� 1 2 3 4 5 6 7 8 9 10 11 12 1314 15 16 A� A� A� A� A� A� A�A� A�A� A� A� A� A� Fig. 15: Singular shape representations with a sequence of A- code assignments Levels of geometricpattern description Reference to the shape Q- code The simplest symbol which refers to an atomic component of a shape attribute. Q- word A Q- code sequence which refers to a shape pattern with distinctive significance – a shape feature or shape knowledge. Q- phrase A sequence of Q- codes in which one or more Q- words show a distinctive pattern of structural arrangements. Q- sentence An aggregation of Q- codes, Q- words and Q- phrases so that it refers to a closed and complete contour of a shape. Q- paragraph A group of Q- sentences where necessary spatial relationship are described with specific connectives. Table 4: Various levels of geometric patterns analogous to natural language distinguished by a node label, and a Q- code is assigned to the node according to specific shape characteristics. When every singular node is labeled and encoded, it completes the circuit and then we have a representation of a Q- sen- tence for a shape. Thus, we follow a sequence of node la- beling, to Q- code assignment, to a complete circuit for a singular shape representation. Figure 15 illustrates this sequence of shape representation. As shown in Figure 15, every node on a shape contour is scanned in a counter-clockwise direction. As for the A- code, the inner vertex angle for a node is measured in clockwise di- rection from the preceding edge and is compared to the land- marks. Other shape attributes follow similar steps of compari- son on a node. As a result, we have a circuit of Q- code symbols as a representation of a Q- sentence that contains Q-words and Q- phrases, such as “(A + A � A +)” and the alternated al- location of Q-words expressed with shaded patterns and brackets. Q-sentence: (A � A + A � A + A � A � A + A � A � A + A � A + A � A � A + A � ) Q-phrase: (A � )<( A + A � A +)>/<(A � A � A + A � A � )(A � A � A + A � )> Q-word: ( A + A � A +) 3.2 Representation of an aggregation of shapes Shapes are grouped together to form a shape aggrega- tion. The most basic shape aggregation occurs when two sim- ple singular shapes overlap each other. When two shapes overlap, their geometric configuration takes certain spatial relationships. A spatial relationship, however, takes a different type of information such that it is mainly concerned about how spatial entities are positioned rather than their individ- ual visual characteristics. In a similar way, lyrics and melody are combined in a song; descriptions of shape characteristics and spatial relationships take different roles in the composi- tion of a visual design. Studies on spatial relationships ([5], [9], [14]) take simple symbols for shapes (the entities posi- tioned by spatial relationships) where symbols refer only to the existence of the entity, abstracting a variety of information about individual shape characteristics. The Q- code scheme, however, goes in the opposite direction in describing the visual information, focusing on encapsulating shape charac- teristics rather than spatial dispositions, thus it describes an aggregation of shapes based only upon Q- codes, exclud- ing other dimensions of visual information such as spatial relationships. The Q- code scheme represents an aggregation of shapes in terms of multiple regions sharing common nodes. Each re- gion is a complete circuit of Q- codes and is equivalent to a sin- gular shape with respect to the property that the encoding corresponds to the Q- sentence notion as a circuit. A region, however, also has a sequence of nodes that could have multi- ple scanning directions. In this way, regions with common nodes with the same labels can be combined to produce a new region. An aggregation of multiple shapes is represented with these regions. Simple aggregation of shapes Binary spatial relations occur when two shapes overlap. The overlap of two shapes produces two or more regions. Figure 16 shows possible binary spatial relationships for the overlap of two squares. The arrangements in Figure 16 can be grouped into two categories: The connected shape category includes “vertex touch”, “adjacent” and “overlap” types, whilst the discon- nected shape category includes “exclusive” and “enclosed” types. The difference between two categories of shape aggre- gation is that the connected category contains common nodes for subsequent regions whilst a disconnected category has none of these. These common nodes take multiple scanning directions and take different Q- codes for the encoding of particular regions. Figure 17 shows the regions as a result of the overlap type aggregation of two squares. The aggregation of multiple shapes forms a Q- para- graph with the regions as Q- sentences. The representation of a shape aggregation should be able to contain all these subse- quent regions in the form of Q- sentences. Shape aggregations in the disconnected category can only be represented with individual Q- sentences. There can be no common nodes between each region so that there cannot be nodes of multiple directions in “exclusive” and “enclosed” types. 3.3 Nodes with multiple directions in a shape aggregation Multi-region nodes One of the critical differences for the encoding of a shape aggregation (Q- paragraph) is the scanning of nodes. Singu- lar shapes contain only one type of nodes that have one scanning direction. A single shape corresponds to a single circuit of Q- codes. Regions in a shape aggregation in the 16 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 Exclusive Vertex touch Adjacent Overlap Enclosed Fig. 16: Possible spatial arrangements of a pair of squares Fig. 17: Possible regions as a result of the overlap of two squares connected category contain nodes that have more than one direction of scanning, which are multi-region nodes. Multi-re- gion nodes are, thus, involved in more than one region, as shown in Figure 18. Each node has been referred to by a Q- code such that a single Q- code has implicitly represented a single node in a circuit and a node has appeared only once in the representa- tion. In the case of regions in shape aggregation, a node with the same label occurs several times, as shown in Figures 19 (a), (b) and (c), which illustrate the nodes that are involved in one, two and three regions. This node with the same label takes dif- ferent Q-codes for the different regions. The labeling of nodes Labels are assigned to nodes in order to identify explic- itly all the subsequent regions from a shape aggregation. Each node is labeled with numbers one by one, circuit by circuit. A complete circuit of a path constructs the encod- ing of a region. Thus each region is identified with a series of labels, or a path of labels, that follows the counter-clock- wise scanning direction with a single Q- code assigned to a single label. A bigger region that includes two small regions has a path of labels that combine two paths of labels for the smaller regions. The coding of a region is considered invariant with respect to the initial node of labeling. Figure 19 shows the labeling of nodes for regions in shape aggregation. Each region is represented with a circuit of labels and each node is assigned with a Q- code as in Table 5. 3.4 Aggregation of multiple regions When two or more regions are connected with a pair of connection nodes, new regions are formed as new Q- sen- tences. As for an aggregation of two regions, X and Y, “X � Y” forms a new circuit composed of non-shared nodes of X and Y connected with a pair of connection nodes. The order of node labels is maintained in respect of A and B in the process. The connection of two regions occurs at a pair of connec- tion nodes. Two regions are connected into a bigger region by canceling a group of shared node labels and by connecting the chains of the group of non-shared nodes at connection nodes. Region aggregation sometimes produces invalid re- gions as a result. One of the conditions for a valid circuit is that there should be no repetitious node labels in the chain. The nodes of multiple scanning directions are located at con- nection points. The valid aggregation of regions contains no repetition of the same nodes of multiple scanning directions. The algorithm When two regions, X and Y, are provided, the aggregation, X � Y, takes labels from two regions in a particular sequence. The elements and the algorithm for the aggregation of re- gions are shown below: © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 17 Acta Polytechnica Vol. 41 No. 3/2001 1 2 3 4 5 6 7 8 9 10 X X: (1 2 3 4 5 6) Y Z Y: (3 7 5 4) Z: (3 8 9 10 5 7) Fig. 19: Labeling of nodes for multiple shapes Regions Path of labels Q-sentences Region X (1 2 3 4 5 6 ) (A� A� A� A� A� A�) Region Y (3 4 5 7) (A� A� A� A�) Region Z (3 8 9 10 5 7) (A� A� A� A� A� A�) Region X � Y (1 2 3 7 5 6) (A� A� A� A� A� A�) Region Y � Z (3 8 9 10 5 4) (A� A� A� A� A� A�) Region X � Z (2 3 8 9 10 5 6 1) (A� A� A� A� A� A� A� A�) Region X � Y � Z (2 3 8 9 10 5 6 1) (A� A� A� A� A� A� A� A�) Table 5: Regions, labels and Q-sentences 1 1 2 1 2 3 (a) (b) (c) Fig. 18: Nodes with scanning directions Following this process, the regions X and Y in Figure 19 match the results below. The order of node labels is not maintained in the process. X = {1 2 3 4 5 6} Y = {3 7 5 4} X � Y = {1 2 3 4 5 6 7} S = {3 4 5} C = {3 5} So = {1 2 6 7} X’= (X � So) = {1 2 6} Y’= (Y � So) = {7} X � Y � X' � Y' � C = {1 2 6 7 3 5}�{1 2 3 7 5 6} Constraints for a valid circuit combination The aggregation of two regions results in a new region. Out of all the combinations, only those regions that satisfy the validity constraints can then be considered as valid circuits. There are three validity constraints, as follows: • There should be, at least, a pair of connection node labels. • There should be no repetition of node labels. • There should be, at least, three node labels ( �3). 4 Assessment of qualitative shape representation Each qualitative and quantitative method is associated with unique paradigmatic perspectives that are complemen- tary to each other. They are used for different purposes. Until recently, the numeric (quantitative) method for representing shapes was the most successful because of its precision in the handling of values and its completeness in representation. There are, however, situations in design modeling where exactness and completeness are not of prime importance and are instead an obstacle to the understanding and classification of geometric information. The qualitative method, as it is complementary to the quantitative approach, should be use- ful in those tasks that are difficult using the quantitative approach. The qualitative scheme for shape representation is complementary to those adapted in conventional computer aided architectural design modeling packages in the follow- ing aspects: • Shapes are described not in terms of numbers and coordi- nates but in qualitative symbols. • Shape representation aims not for precise and complete description but for the encapsulation of shape characteris- tics. • Shape representation can handle an unclear and ambigu- ous measure with partial knowledge. • Shapes are analyzed on the basis of description and recog- nition of shape features. • Shape modeling aims at such qualitative evaluations as comparison, categorization, and qualitative search, rather than precise visualization. • Single qualitative shape description represents a range of shape individuals sharing common shape characteristics. Hence, the qualitative approach to shape shows unique methodological distinctions from the quantitative approach. The qualitative shape representation shows an advantage over the quantitative shape representation in the following aspects: • A single description of a qualitative shape refers to many descriptions of quantitative shapes in a particular range. • Qualitative shape descriptions can take several levels of abstraction by changing the granularity, which means flexi- bility and economy as well as adaptability for modeling purposes. • Qualitative shape descriptions can refer to quantitative shapes either in the conceptual stage or in the final stage of designing. The ability to handle shapes in the conceptual or early stages of designing is a significant advantage over quantitative methods. • Qualitative shape descriptions contain data for conceptual abstractions that facilitate the search for shape semantics and for building a shape knowledge base. Reference: [1] Buffart, H., Leeuwenberg, E., Restle, F.: Coding theory of visual pattern completion. J. Exp. Psychol. Hum. Percept. Perform. 7 (2)/1981, pp. 241–274 [2] Buffart, H., Leeuwenberg, E.: Observations: Analysis of am- biguity in visual pattern completion. J. Exp. Psyhol. Hum. Percept. Perform. 9 (6)/1983a, pp. 980–1000 [3] Buffart, H., Leeuwenberg, E.: Structural information the- ory. in H.-G. Geissler (ed.), Modern Issues in Perception, North-Holland, Amsterdam, 1983b, pp. 48–72 [4] de Kleer, J., Brown, J.: A qualitative physics based on conflu- ences. Artificial Intelligence 24/1984, pp. 7–83 [5] Egenhofer, M., Al-Taha, K.: Reasoning about gradual changes of topological relationships. In A. U. Frank, I. Cam- pari and U. Formentini (eds), Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Springer-Verlag, Berlin, 1992, pp. 196 –219 [6] Forbus, K. D.: Qualitative process theory. Artificial Intelli- gence 24/1984, pp. 85–168 [7] Forbus, K. D., Nielsen, P., Faltings, B.: Qualitative spa- tial reasoning: the CLOCK project. Artificial Intelligence 51/1991, pp. 417– 471 [8] Freeman, H.: Boundary encoding and processing. In B. S. Lipkin and A. Rosenfeld (eds), Pictorial Processing and Psychopictorics, Academic Press, New York, 1970, pp. 241–266 18 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 41 No. 3/2001 • X and Y: Two valid regions with two sets of node labels. • S: A set of labels for a group of shared node labels of X and Y. • So: The complementary set of S from X �Y. • C: A set for a pair of connec- tion node labels. • X’ and Y’: The non-shared node labels of X and Y. S � X S � Y C� S So � (X � Y) � S S � So = � X’ � X Y' � Y X' � (X � So) Y' � (Y � So) X � Y � X' � Y' � C [9] Freksa, C.: Qualitative spatial reasoning. In D. M. Mark and A. U. Frank (eds), Cognitive and Linguistic As- pect of Geographic Space, Kluwer, Dordrecht, 1991, pp. 361–372 [10] Gero, J. S.: Design prototypes: A knowledge representation schema for design. AI Magazine 11 (4)/1990, pp. 26 –36 [11] Gero, J., Park, S.-H.: Qualitative representation of shape and space for computer-aided architectural design. In Y.-T. Liu, J.-H. Tsou and J.-H. Hou (eds), CAADRIA ’97, Hu’s Publisher, Taipei, Taiwan, 1997a, pp. 323–334 [12] Gero, J., Park, S.-H.: Computable feature-based qualitative modeling of shape. In R. Junge (ed.), CAAD Futures ’97, Kluwer, Dordrecht, 1997b, pp. 821–830 [13] Hayes, P.: The second naive physics manifesto. In J. R. Hobbs and R. C. Moore (eds), Formal Theories of the Com- monsense World, Ablex, Norwood, 1985, pp. 1–36 [14] Hernandez, D.: Relative representation of spatial knowledge: The 2-d case. In D. M. Mark and A. U. Frank (eds), Cognitive and Linguistic Aspects of Geographic Space, Kluwer, Dordrecht, 1991, pp. 373–385 [15] Hilbert, D., Cohn-Vossen, S.: Geometry and the Imagina- tion, Chelsea Pub., New York, 1952 [16] Iwasaki, Y.: Qualitative physics. In A. Barr, P. R. Cohen and E. A. Feigenbaum (eds), The Handbook of Artificial Intelligence, 1989, pp. 323–413 [17] Jungert, E.: The observer’s point of view: An extension of symbolic projection. In A. Frank, I. Campari, and U. For- mentini (eds), Theories and Methods of Spatio-Tempo- ral Reasoning in Geographic Space, Springer-Verlag, Berlin, 1992, pp. 179–195 [18] Jungert, E.: Symbolic spatial reasoning on object shapes for qualitative matching. In A. U. Frank and I. Campari (eds), Spatial Information Theory, Springer-Verlag, Berlin, 1993, pp. 444 – 462 [19] Kuipers, B.: Qualitative simulation. Artificial Intelligence 29/1986, pp. 289 –338 [20] Leeuwenberg, E.: A perceptual coding language for vi- sual and auditory patterns. Am. J. Psychol. 84 (3)/1971, pp. 307–349 [21] Liu, J.: A method of spatial reasoning based on qualitative trig- onometry. Artificial Intelligence 98/1998, pp. 137–168 [22] Martinoli, O., Masulli, F., Riani, M.: Algorithmic informa- tion of images. In V. Cantoni, V. D. Gesu and S. Levialdi (eds), Image Analysis and Processing II, Plenum Press, New York, 1988, pp. 287–293 [23] Mukerjee, A., Agrawal, R. B., Tiwari, N.: Qualitative sketch optimization. AIEDAM 11/1997, pp. 311–323 [24] Park, S. H., Gero, J. S.: Qualitative representation and rea- soning about shapes. In J. S. Gero and B. Tversky (eds), Visual and Spatial Reasoning in Design, Key Centre of Computing and Cognition, University of Sydney, Sydney, Australia, 1999, pp. 55–68 [25] Restle, F.: Coding theory of the perception of motion configura- tions. Psychological Review 86 (1)/1979, pp. 1–24 [26] Restle, F.: Coding theory as an integration of gestalt psychol- ogy and information processing theory. In J. Beck (ed.), Organization and Representation in Perception, Law- rence Erlbaum Assoc. Pub., London, 1982, pp. 31–56 [27] Stiny, G.: Pictorial and Formal Aspects of Shape and Shape Grammars and Aesthetic Systems. Ph.D. thesis, University of California, Los Angeles, 1975 [28] Stiny, G.: Generating and measuring aesthetic forms. Hand- book of Perception, Academic press, 1978, pp. 133–152 [29] Struss, P.: Qualitative modeling of physical systems in Al re- search. In J. Calmet and J. A. Campbell (eds), Artificial Intelligence and Symbolic Mathematical Computing, Springer-Verlag, New York, 1992, pp. 20– 49 [30] Treisman A., Schmidt, H.: Illusory conjunction in the perception of objects. Cognitive Psychology 14/1982, pp. 107–141 [31] Werthner, H.: Qualitative Reasoning: Modeling and the Generation of Behavior. Springer-Verlag, Vienna, 1994 [32] Weinberg, J. B., Uckun, S., Biswas, G., Manganaris, S.: Qualitative vector algebra. In B. Faltings and P. Struss (eds), Recent Advances in Qualitative Physics, MIT Press, London, 1992, pp. 193–207 Ashraf Fouad Hafez Ismail phone: +420 602882128 fax: +420 2 6517811 e-mail: hafez@fa.cvut.cz Department of Design Theory Czech Technical University in Prague Faculty of Architecture Thákurova 7, 166 29 Praha 6, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 19 Acta Polytechnica Vol. 41 No. 3/2001 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends false /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA /BGR /CHS /CHT /DAN /DEU /ESP /ETI /FRA /GRE /HEB /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN /ITA /JPN /KOR /LTH /LVI /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR /POL /PTB /RUM /RUS /SKY /SLV /SUO /SVE /TUR /UKR /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) /CZE >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice