The paper is devoted to the implementation of case-based reasoning in reverse engineering of graphical user interfaces. In particular, web interfaces are considered. We suggest automating HTML/CSS markup building with aggregation of code samples from previous cases. The proposal is based on the hypothesis that analogy is employed to conceptualize HTML markup construction. The article considers the original theory of building an image structure, the modification of the case-based reasoning approach and the results of practical experiments.
Web-technology is one of the most developed areas of modern computer science. It is used not only in website development but also as an important node of any IT-infrastructure. Consequently, the whole information technology industry uses web-development in one form or another.
Nevertheless, automation of web-development itself remains incomplete. One of the key tasks – creation of html/css markups – does not have an extensive solution yet. Some properties of this process prevents using classical methods of automation. These properties are: nonformalized requirements for a layout, variability of industrial standards for code writing, and, finally, cross-browser and cross-platform compatibility.
The impact of automation of html/css markups building is not limited to speeding up a process of web-applications development. It also makes the development more flexible allowing to scale results, verify hypotheses and help testing applications.
We can expand the results of the work to a more general domain: any kind of technologies where markup languages are used for building GUI.
A methodological basis of the work is the Case-Based Reasoning (CBR) approach (Kolodner 1992). Briefly describing its essence, one can say it is a way of solving problems with adaptation of similar problems from the past to a current situation. This approach has been chosen due to the hypothesis that formalization of images (which is, in fact, creation of html markup) using transductive reasoning, or reasoning by analogy, produces a result, the most similar to what a human does. Also, such a scheme can solve the problems with the automation described above.
The state of the art solutions offer to generate code without human involvement. They work as black boxes, where the final result totally depends on the collected dataset. The CBR approach is to fill this gap with the acquisition of experts’ knowledge in case storage. The ultimate role of CBR, therefore, is to help specialists to formalize their knowledge in a relatively small dataset and then automatically combine complex interfaces in such a way as if the specialists did it manually.
To fill a gap in knowledge for readers who are not familiar with the field, we overview two types of related work. The first one is the papers about interfaces reverse engineering: they are the benchmarks which we compare our approach with. The second one is an outline of CBR. Since this is a core of the given approach, this information is crucial for understanding the paper.
We consider two types of interfaces that are typical objects of the reverse engineering task: mobile interfaces and web interfaces.
Mobile interfaces Mobile development is supposed to be a more common area for interfaces reengineering than web. It can be explained by the fact that mobile interfaces are usually relatively simplier and more unified, while web pages have a great variance of different layouts. Here we point at a few mobile interface reverse engineering researches that we consider as robust baselines in terms of comparing OCR and code generation parts.
The framework of
Based on REMAUI,
The work of
Web interfaces Further, we would like to focus on web reverse engineering, because in the case of solving this task, a possible outcome can be more considerable, as web technologies are applied in an extremely wide range of domains. Researches in this field are not so numerous, however.
Asiroglu in
The most recent successful case of solving the problem in
the industry is the result of UIzard Technologies company
As you can see above, there are many points of view on the interface reverse engineering problem. Each of them is suitable for specific conditions and goals. The contribution of the given paper is building a reverse engineering framework more as an expert system rather than an automation tool. It means that compared with alternatives, it can eventually generate less accurate results in terms of pixel-to-pixel similarity, but an important thing is that specialists can contribute their knowledge in a case storage, thereby managing a style or methodology that they expect to see in the final result.
As mentioned above, case-based reasoning is a core of the approach. This section outlines basics of CBR.
The origin of CBR is the work of Roger Schank
A lot of works devoted to this approach were written
in the 1990s
In short, CBR is a method of solving a problem by adaptation of solutions to similar problems in the past to a current situation.
The core concept in CBR is a case. A case is a threesome of elements:
Problem is a state of the world when the case occurs. Solution is a suitable answer for the problem in the given context.
Outcome is a state of the world after the problem is solved.
The process of finding the solution is called a CBR-cycle that consists of 4 stages (Kolodner 1992): 1. Retrieve. The best matching case is extracted from the case base. 2. Reuse. The solution to the case retrieved is adapted to solve the current problem. 3. Revise. The adapted solution is tested: if it is not satisfactory, then either additional cases are retrieved, or the retrieved solution must be adapted again. 4. Retain. The case with the give solution is added to the case base.
When defining the task, we aim to reproduce the way that a
human performs HTML markup building. All criteria,
constrains and conditions given below are based on how the
industry operates. For more information, see
The following life-cycle of interaction with the system is suggested. In the very beginning, an expert (or a group of experts) populates a case storage with code templates to setup the system. Or, they can use a ready case storage populated with someone else. This step is required to be done only once. Then, the system is used to get a design of interface as an input and generate code automatically. At this point, we don’t expect an absolutely accurate result. A specialist, in the end, makes final improvements in the code, or uses it as a basis for more high-level tasks.
Consequently, the main requirements to an image processing part are that the algorithm must recognize an image structure, find as many features (color, type, margins, etc.) of objects as possible, and generate the code implementing the structure recognized. Wherein, it is not necessary to recognize all features recreate the picture pixel-to-pixel
The introduction and related work sections contain conditions that should be considered in solving the task. It is necessary to make a set of requirements for the system such that it would be possible to get positive results in these conditions.
itself does not contain complete information about what should be a final HTML-markup. Therefore, it must be available to include additional knowledge about the requirements for the system.
writing the code. There are a few methodologies of HTML-markups (adaptive, BEM (block-elementmodificator), bootstrap and so on). Moreover, as a rule, each developer’s team has its own standards. Thus, the system must generate code in several styles and standards.
patibility. HTML-code must be not only valid, but also identically processed in all modern browsers and operating systems.
In addition, we set input constraints on the current stage. An image must not include gradient background animation elements popup elements
In the future, we intend to make an algorithm working beyond these conditions.
The basis of the architecture is an attempt to recreate the process of writing code by a human. The hypothesis is, a human uses transductive reasoning when formalizing visual information: one extracts structures of different levels from an image and describes this structure by analogy with one’s own or others’ previous experience.
In particular, such a situation is observed in writing HTML-code. Meeting an unknown layout pattern, a specialist finds in the literature, how to implement it on HTML. Further, referrals to directories are becoming less and less, but the principle remains the same: facing another pattern, a human extracts from memory a suitable example and adapts it to a current situation.
The process is implemented in the following way (Fig. 2): 1. The elements are extracted from the image (text, pictures, blocks, etc.). 2. The extracted images are combined in a tree-like structure according to a special algorithm. 3. A prefix tree traversal is performed; on each iteration, there is a request to the case base to find a suitable HTML description of an architectural pattern in the tree node. 4. Artifacts received on the previous step are saved in files.
The next sections are devoted to the description of these steps.
The goal of this step is to receive a so-called structure of
a bitmap, i.e. a mathematical object describing a mutual
arrangement of image parts. In
Remember that generation of code is performed with the prefix tree traversal, where a tree is an image structure. On each iteration, the CBR-cycle runs. We need to define the problem, solution, and outcome in the context of the task. In other words, to describe a case format.
Problem is a features vector of a node and its children. Solution is templates of HTML and CSS code, that implement markup of the structure described.
Outcome is HTML/CSS code generated from the template applied to a specific context.
Thus, when each node of a tree is processed, a “problem” is formed: description of the current element and elements on a lower level in an image structure. In storage, there are cases in which problems are typical cases of elements layout, and solutions are typical ways of markup. The task of a CBR-cycle is to get HTML/CSS code to build a markup of a current structure using the solution stored. Let us describe the cycle in detail. As a notation, denote the case processed as new case. Further terms will be included as they appear. Algorithm 2 Search for a suitable node (findNode) Require: nodei – a node for that a suitable node is being found, nodex1 ; nodey1 – a left top coordinate, nodex2 ; nodey2 – a right bottom coordinate Require: orientation – a direction of joining nodes Ensure: nodej is a node demanded or NULL if there is no such a node 1: if orientation is HOR then 2: nodej the next node to the right of the nodei 3: else if orientation is VERT then 4: nodej the next node to the bottom of the nodei 5: x1 min(nodeix1 ; nodejx1 )
1 1 6: y1 min(nodeiy ; nodejy ) 7: x2 max(nodeix2 ; nodejx2 )
2 2 8: y2 max(nodeiy ; nodejy )) 9: R rectangle (x1, y1) (x2, y2) 10: for all nodek 2 nodes do 11: if nodek \ R 6= ; then 12: nodej NULL Retrieval phase A new case has a problem but no solution and outcome. The task of this stage is to retrieve cases, which are the most similar to the problem of a new case. In general, it is a task of n-class classification, where n is the number of cases in storage. On the proof-of-concept stage, we choose the method of k-nearest neighbors with Euclid distance. For this purpose, we vectorize and normalize problems. This means that first, all categorial features are transformed to a numerical type, second, absolute values are replaced with relative ones by the formula: xi = xmaxxixmin . Then, calculate a distance between the given vector and vectors in a case base d(x; y) = pPin=1(xi yi)2 and select the case, where distance is minimal. In terms of CBR, this case is called retrieved.
Adaptation phase The adaptation stage is performed with an algorithm, receiving a problem of a new case and a solution of a retrieved case and returning an outcome. A case containing a problem of a new case, solution of a retrieved case and the generated outcome is a solved case, and the solution is called suggested.
In the current work, a derivative type of adaptation is suggested, that means an old solution is to be regenerated in new conditions. Since a solution is a code template, a result is built with using templating language. The difficulty is that the results of different cases may conflict with each other during the processing. It is especially true for conflicts in CSS code: situations when different results describe the same class differently. That is why conflict resolution is an important part of the adaptation stage.
The base of conflict resolution is a resolving of three cases: 1) absence of conflict; 2) a complete conflict, that is classes describe incompatible styles; 3) one class is a special case of another. The following strategies are applied accordingly: 1) the code is saved as is; 2) different classes with own styles are created, and appropriate replacements in an HTML-document are made; 3) a new class is added to a styles set, which is a special case, and appropriate inserts in an HTML-document are made.
Evaluation phase In the classic CBR, an evaluation step serves as validation of the suggested result. A case that passed the test is called tested, and the solution is approved. Regarding this work, the task of evaluation of the quality of HTML/CSS code deserves a separate study. In the current state of the research, this step is skipped, and validation of the result is resolved for the whole document and not on each iteration of a CBR-cycle.
Updating phase The goal of the last step of the cycle is to save an approved solution in case storage so that it can be reused in the future. In the current work, this step differs from the classic approach. Unlike using a centralized case storage, the CBR-system developed maintains a “global” and few “local” case storages (see table 1). The global case storage is used for all images. The local ones are used only in processing a specific document. We can say that a “local” storage is a context of a document: it contains the results of solved problems during its processing.
Specifically, a tested case is always saved only into a local storage. Wherein, on a retrieval step, a search is performed in both global and local repositories, where local ones have priority. This approach has several advantages: 1. A risk of different code generation for the same blocks of an image is decreased. The system may process identical blocks differently, because noise on an image can affect retrieval of a suitable case. At the same time, the size limitation of a local storage prevents generating redundant solutions. 2. System performance is increased: (a) a global storage is located in external memory, while a local one is in RAM; as a result, the number of requests to a hard disk reduces (b) graphical user interfaces have a property to contain a lot of similar blocks; when processing the next block, a search in a relatively small local storage, which already contains a suitable case, is performed much faster than a repeating search in a global storage; also, an adaptation stage requires less resources than initial adaptation of an “unprepared” case. 3. There is no “clogging” of a global storage with specific cases, which, first, positively influences the size of global storage, and second, it reduces a level of overfitting of the system.
In other words, a global storage serves as a source of cases that have solutions of code generation of a typical layout. Then, local storage is used for accurate and rapid adaptation of these solutions in the context of a specific document. Case storage population The case storage is populated by experts with a share of automation. Namely, a set of cases with their problem parts is built automatically, and corresponding solution parts are filled by specialists. The following are the steps for generating cases: 1. A list of real websites is collected. 2. DOM-trees of random pages are saved. 3. Trees are split by sub-trees with prefix traversal of a whole tree and selecting each node with its children. 4. A given set of sub-trees is clustered with DBSCAN algorithm, when tree-edit distance is used to define the similarity between objects. (See tree-edit distance overview in the section below.) 5. From each cluster, a random object is selected. The selected objects form the case storage, where each object is a problem part of a single case.
While managing parameters eps and min samples of DBSCAN, one can control the size of a case storage. The bigger the case storage, the more accurate the system, but there is more work for experts. One must find a right balance between these two criteria to set up the system adequately to the existing conditions. Then, when the set of cases with their problems is built, experts can populate it with solutions - HTML/CSS codes.
Before the experiment evaluation, let us illustrate how the system works in practice.
As an example, let us consider a page of Novosibirsk State University site.
As an output of the first stage of image processing, elements were extracted and grouped into nodes (Fig. 3). Then, the algorithm (described earlier in the paper) created a treelike structure (Fig. 4). We estimate that the result is of good quality, because despite of some mistakes (wrong font was selected, some pictures were missing, tiny errors in size existed), the system managed to solve the main task: to recreate a structure of elements and generate human-like code (Fig. 5).
The question of evaluation is open. What should we compare to estimate the result? One option is to compare images: an initial screenshot and a screenshot of the interface generated by the system. It is probably the most obvious way but as we stated in the task definition part, we do not aim to recreate an interface by pixel-to-pixel: it is much more important to recognize the idea of the layout. Another option is to compare source codes. We can collect a base of real applications with their source codes, make screenshots, generate a code, and find the difference between the texts. This way is too sensitive to implementation specificity. There are numerous ways to write a code for the same interface and there is no argument to consider the result incorrect if the generated code differs from the real one.
We believe the best way is to compare tree models of the source codes, because a tree model represent the way how a code is organized. We collect the data with crawling web pages so that among the screenshots we get HTML code and extract the DOM model from them. As a rule (except some tricky cases), the DOM model adequately describes elements structure. The idea is to map structures received by our algorithm with DOM trees and roughly estimate their similarity. Such a procedure allows us to evaluate our approach, although we understand that it is limited only on a specific subset of images (only web interfaces) and also some technical tricks of web technologies can affect the correctness of DOM trees and thereby decrease the estimates. Nevertheless, it is the best way of evaluating the method so far, which can prove the viability of the solution and outline the next steps.
The crucial thing is the selection of a quality measure. There are few approaches to comparing trees: some of them count operations needed for the transformation of one tree to another; others compare the longest common paths from a root to a tree node; also there are variable-length doesn’t care (VLDC) based methods.
We select two measures: edit distance and bottom-up distance.
Tree edit distance. The review of edit distance methods can be found in the survey of Philip Bille. This is how he defines the problem:
Given T is a labelled ordered tree (ordered means that order among siblings matters). Define tree operations as follows:
Delete. Delete a non-root node v in T with parent v’ keeping children of v order.
Insert. Insert a node v as a child of v’ in T making v the parent of a consecutive subsequence of the children of v’.
Assume there is an edit cost is c : V V ! R. c(v; w) denotes relabel, c(v; ?) denotes delete and c(?; w) denotes insert operations. Given an edit script S between T1 and T2 is a sequence of edit operations s1; s2; : : : ; sn, si 2 V V and cost of S is d(S) = Pin=1 c(si). Denote an optimal edit script between T1 and T2 is Sopt(T1; T2) : d(Sopt) = minSt d(St) and d(Sopt) is a tree edit distance. (Bille 2005)
Based on the survey
In our case, we suggest the following edit cost function. First, we denote a fixed finite alphabet containing values for labels:
= ft; p; ig where t stands for an element with text, p stands for an element with an embedded picture, and i stands for an internal node.
We denote edit cost as follows: c(v; w) = 81; if v 6= ? ^ w = ? > ><0:8; if v = ? ^ w 6= ? >0:1; if v 6= ? ^ w 6= ? ^ v; w 2 fp; tg >:0; otherwise (1)
Also, denote that a tree received by our algorithm would be the first parameter, and a tree from a data set would be the second one.
This edit cost function penalizes the method the most if a resulted tree misses any node, a little less if it contains an extra node and very little if it mixes up a text with a picture. You can mention that it does not penalize for mixing up an internal node with no internal, because in this case the algorithm either misses or adds an extra node, which already implies a big penalty.
Bottom-up distance. This method is presented in the work of Valentie (Valiente ). The complexity of the algorithm is O(jT1jjT2j log(T1 + T2)). For two trees T1 and T2 the bottom-up distance equals 1 f = max(jT1j; jT1j), where f is the size of the largest common forest in T1 and T2. We slightly change this formula and make it asymmetric: basym(T1; T2) = 1 f =jT2j (2)
Edit and bottom-up distances as defined above can be roughly interpreted as “precision” and “recall” respectively in terms of machine learning evaluation. Technically, they are not the same, but it gives us a good idea of how to read an experiment results. Indeed, for a tree that correctly represents a part of another tree but completely does not contain another part, edit distance would be relatively low, while bottom-up distance would be relatively high. Otherwise, if a tree contains all nodes of another tree, but the structure is different and some extra nodes exist, edit distance would be relatively high and bottom-up distance would be relatively low.
To estimate the approach from different points of view we use both measures as well as the F -score that generalizes a common penalty. The problem of aggregating the scores is that they have different scales: [0; +1) for an edit distance and [0; 1] for a bottom-up one. We solve this problem by transforming an edit distance measure. In the beginning, we normalize its value by the size of a sample tree: dnorm(T1; T2) = d(Sopt(T1; T2)) jT2j
It allows us to compare edit distance for trees of different sizes but the measure is still not limited from above. Therefore, we apply the logarithm to the measure: (3) dlog(T1; T2) = log(
1 1 + dnorm(T1; T2) ) (4)
As d is always positive, the domain of dlog is [0; 1). Moreover, the logarithmic form of the measure perfectly suites our idea about estimating the method: we assume that the more trees differ, the less important the exact value of the difference.
Finally, we can denote the F -measure. In order to move from cost scores to measure quality, we subtract distances from one.
F = 2 (1 (1 b) (1 b) + (1 dlog) dlog) = 2 (1 2 b) (1 b
dlog) dlog (5)
We used Alexa service 1 to get a list of 1000 the most popular websites. Then we made screenshots of the main and two random pages of each website. Also, we crawled HTML/CSS codes of each page and transformed them into trees using DOM parser in Python. Due to technical restrictions in some cases, we were only able to collect a dataset of 2640 examples.
In addition, to make the experiment more useful and get more insights we scored each web page with a measure “Text-to-Image ratio”: tti =
T T + I (6) where T is the number of nodes with text content and I is the number of nodes with embedded pictures.
The reason why we use this score is to estimate how a share of text and images affects the result and to define the next steps. It is important to understand which part of the method is the most problematic, and where efforts should be focused to increase the quality as much as possible.
In general, results are as follows (see Table 2):
The mean of F-score is 0.78, and the variance is 0.033, which appears to be a good result. Note, that the bottomup distance is much better than the edit distance. It means that the recognition part, on average, works better than the structure building part.
Let us analyze the dependence of scores on “Text-toImage ratio” (figures 7 and 8).
We see that the biggest issues are with the cases when an image has both text and embedded pictures, approximately in a proportion of seven to three. Comparing extreme cases, when an image consists of mainly embedded pictures or mainly text, in the first case the approach works far better than in the second one. Herewith, edit distance is decreasing when moving from mixed cases to more text-based, while for the bottom-up distance this effect is not so strong.
Also note the heteroskedasticity of the data: the variance is bigger in “mixed” cases and smaller in extreme cases. That is, the method is more unpredictable when a picture has diverse content.
Based on these outputs, we make the following conclusions:
The results can be advanced by applying forces in the following areas: – enhancement of the text detection part – improvement of the processing of the cases when an image has diverse content In addition to making improvements from the previous section, the next steps include: 1. Development of a procedure of automatic filling of case storage.
The current paper considers the development of a system where case storage is populated manually by experts. As explained above, this approach has strong advantages. However, in general, we would like to collect cases automatically, because it would be less time-consuming and less prone to human errors. Our suggestion is to analyze existing web-sites elements with one of the methods of clustering and use centers of clusters as reference cases. 2. Development of a better similarity measure.
One of the crucial elements of a case-based reasoning solution is the selection of an appropriate similarity measure. The current version uses a simple KNN principle. Consequently, there is room for optimizing the measure construction, because the nearest neighbors algorithm is insensitive to categorical features. As categorical features are the majority of elements properties processed, we are planning to use classifier models based on decision trees. 3. Development of a revise stage in the CBR-cycle.
When building a CBR cycle, the revising stage has been skipped, because the evaluation of HTML document correctness is an unsolved problem. This question should be investigated to make the cycle complete.
In conclusion, we developed a system that generates markup language source code for a given interface screenshot. The feature of the approach is using experts’ knowledge that is kept in a specific case storage. The experiments demonstrated the satisfactory quality of the current solution and provided grounds for the further development.
He, W. 2013. Improving user experience with case-based reasoning systems using text mining and Web 2.0. Expert Systems with Applications 40(2):500–507.
Klein, P. N. 1998. Computing the edit-distance between unrooted ordered trees. In ESA.
Kolodner, J. L. 1992. An introduction to case-based reasoning. Artificial Intelligence Review 6(1):3–34.