# Automatic Classification of Web Images as UML Static Diagrams Using Machine Learning Techniques
## 4 Analysis of Graphical Characteristics of Diagrammatic Images
### Rectangle Identification  
Rectangles are used to represent classes and objects in UML static diagrams, in addition to being part of other more complex shapes such as packages, components and so on. The identification of rectangles is achieved using the vertical and horizontal segments identified according to the previous subsection. The objective is to find four cyclically connected segments whose identifiers go in ascending order (possibly with gaps among them). This last restriction is aimed at obtaining a unique representation of each rectangle as a sequence of its edges, starting with a vertical one. In addition, it is required that the segments are not discontinuous and have a minimum length of 10 pixels (another heuristic value; shorter segments usually are false positives). A programmed automaton _Ap = (Q, I, O, M, \(\delta\), q\({}_{0}\))_[32; 33] is used to recognize those sequences of segments that satisfy the mentioned restrictions, where: \begin{tabular}{l l}
**Q** & The set of states. \\
**I** & Input, the sequence of vertical and horizontal segments detected. \\
**O** & Output, the sequence of vertical and horizontal segments forming a rectangle. \\
**M** & Adjacency lists (segment connections) and other segment attributes. \\
**\(\delta\)** & \(Q\times I\times\Pi\to Q\times O\): transition function. \\
**II** & \(A_{I}\cup A_{M}\to\) {TRUE, FALSE}: transition predicate. \\
**A\({}_{I}\)** & Set of attributes of I. \\
**A\({}_{M}\)** & Set of attributes of M. \\
**M** & Adjacency lists (segment connections) and other segment attributes. \\
**\(\delta\)** & \(Q\times I\times\Pi\to Q\times O\): transition function. \\
**II** & \(A_{I}\cup A_{M}\to\) {TRUE, FALSE}: transition predicate. \\
**A\({}_{I}\)** & Set of attributes of I. \\
**A\({}_{M}\)** & Set of attributes of M. \\
**q\({}_{0}\)** & \(\in Q\) initial state. \\ \end{tabular}   
Figure 3 represents the programmed automaton, where **q\({}_{i}\)** is the state where **i** consecutive segments are recognized as potential edges of a rectangle, **q\({}_{b}\)** is the break state (i.e., the sequence of segments does not complete a rectangle) and Boolean expressions **a**, **b** and **c** are computed on the successive input segments as follows: \begin{tabular}{l l} a & = currentSegment.continuous \\  & AND (currentSegment.length \(\geq\) 10) \\  & If current segment is continuous and long enough, \\  & then jump to **q\({}_{1}\)**, else **q\({}_{b}\)**. \\  & _Left vertical edge._ \\
**b** & = a \\  & AND (previousSegment.id \(<\) currentSegment.id) \\  & AND currentSegment.connected(previousSegment) \\  & If current segment is continuous, long and connected to the previous one, \\  & then **q\({}_{2}\)** (or **q\({}_{3}\)**) else **q\({}_{b}\)**. \\  & _Upper horizontal edge and right vertical edge._ \\
**c** & = b \\  & AND currentSegment.connected(firstSegment) \\  & If current segment is continuous, long, connected to the previous one, and to the first one, \\  & then **q\({}_{4}\)** else **q\({}_{b}\)**. \\  & _Lower horizontal edge, completing the four required edges to form a rectangle._ \\ \end{tabular}   
Figure 4 illustrates the process of rectangle recognition with the defined automaton, with an example. In state q1, the automaton found a continuous vertical segment. In state q2, the automaton found a continuous horizontal segment, connected to the first segment and with a greater ID. In state q3, the automaton found a continuous vertical segment, connected to the second segment and with a greater ID. In state q4, the automaton found a continuous horizontal segment, connected to the third segment and with a greater ID, and connected to the first segment. Once all rectangles present in the image are recognized, we distinguish primary and secondary rectangles. Primary rectangles are not contained by other rectangles; secondary rectangles are contained within other (primary or secondary) rectangles, i.e., their four vertices are enclosed within the limits of another rectangle.