Gen Nishida

Adrien Bousseau

Daniel G Aliaga

Procedural Modeling of a Building from a Single Image

Keywords:

Creating a virtual city is demanded for computer games, movies, and urban planning, but it takes a lot of time to create numerous 3D building models. Procedural modeling has become popular in recent years to overcome this issue, but creating a grammar to get a desired output is difficult and time consuming even for expert users. In this paper, we present an interactive tool that allows users to automatically generate such a grammar from a single image of a building. The user selects a photograph and highlights the silhouette of the target building as input to our method. Our pipeline automatically generates the building components, from large-scale building mass to fine-scale windows and doors geometry. Each stage of our pipeline combines convolutional neural networks (CNNs) and optimization to select and parameterize procedural grammars that reproduce the building elements of the picture. In the first stage, our method jointly estimates camera parameters and building mass shape. Once known, the building mass enables the rectification of the façades, which are given as input to the second stage that recovers the façade layout. This layout allows us to extract individual windows and doors that are subsequently fed to the last stage of the pipeline that selects procedural grammars for windows and doors. Finally, the grammars are combined to generate a complete procedural building as output. We devise a common methodology to make each stage of this pipeline tractable. This methodology consists in simplifying the input image to match the visual appearance of synthetic training data, and in using optimization to refine the parameters estimated by CNNs. We used our method to generate a variety of procedural models of buildings from existing photographs.

Figure 1: Procedural modeling generation from a single image. 1) Given an image and a silhouette of a building, 2) our approach estimates the camera parameters and building mass as a first step. Then, 3) the façade image is rectified, and 4) the façade structure and 5) window styles are recognized. 6) Finally the output grammar is constructed and a corresponding 3d geometry is generated.

a) b) c) d) f) e)
Figure 1: Procedural Modeling from a Single Image. a) Given an image and a silhouette of a building, b) our approach automatically estimates the camera parameters and generates a building mass grammar as a first step. Then, c) the façade image is rectified, and d) the façade grammar is generated. e) For each window non-terminal, the best window grammar is selected by maximum vote. f) Finally the output grammar is constructed and a corresponding 3D geometry is generated.

changes. However, creating an architectural grammar can be difficult and time consuming. In this paper, we present a tool that allows the user to generate such a grammar automatically using a single example photograph.

Generating virtual models of buildings from existing imagery can be approached from several directions. On one extreme, multiview stereo focuses on accurately reconstructing buildings from a multitude of images (e.g., [SCD * 06]) but requires many images or a carefully selected set. At the other extreme, previous single-image modeling methods yield similar-looking building models but require significant user effort (e.g., [START_REF] Oh | Imagebased modeling and photo editing[END_REF]) or have very limited modeling abilities (e.g., [START_REF] Hoiem | Automatic photo popup[END_REF]). Further, none of these methods yield semantic information or a parameterized procedural model as output.

Our system combines procedural modeling with machine learning to automatically generate a parameterized 3D procedural model of a building from a single example (ground-level or aerial) photograph where the building has been outlined (Figure 1a). Our approach improves 3D content generation in at least two significant ways. First, we do not need multiple images from a variety of carefully chosen vantage points nor assume they can be found on the Internet. Second, from a single example photograph we automatically generate a family of similar style buildings by modifying parameters such as building height, window size, and even building shape.

The main challenge we faced in developing our system is the very large dimensionality of the space of camera parameters and parametric buildings. Existing inverse procedural modeling methods, using Markov Chain Monte Carlo (MCMC) (e.g., [TLL * 11]) or sequential Monte Carlo (e.g., [START_REF] Mildenhall | Controlling procedural modeling programs with stochastically-ordered sequential monte carlo[END_REF]), cannot successfully search this large space in a practical amount of time (e.g., see Table 2 and Figure 10 in our results section). Our novel methodology is based on the three following ideas.

• Our first idea to cope with the design-space complexity is to split the generation of a complete building into three, smaller stages: building-mass generation, façade generation, and windows generation. This decomposition matches the multi-scale structure of buildings and enables a sequential pipeline where each stage informs the next one: estimating the camera parameters and extracting the building mass (Figure 1b) assists in then rectifying the façades (Figure 1c), and extracting the façade layout (Figure 1d) helps to determine individual window styles (Figure 1e). • Our second idea is to combine machine learning and optimization to quickly and precisely generate the procedural model and its parameters that best fit during each stage. In particular, we train a set of convolutional neural networks (CNNs) to recognize grammars and another set to estimate grammar parameters.

We then refine these parameters with optimization methods. We found this three-step approach to be faster than popular MCMC optimization and more robust than hand-crafted heuristics. However, deep convolutional networks require a large number of annotated images for training, especially if one wants to be invariant to changes in lighting, texture, occlusion, and other sources of noise. • Our third idea is to simplify the image content, when possible, for each stage to remove a great number of such variations, ef-fectively turning the images into line drawings that capture geometric information without being polluted by photometric information. Abstracting the input image brings it to a similar visual domain as our training data, which we automatically synthesize by rendering models from the possible procedural design space. We only rely on manually-annotated training data for repetitive small-scale components of the building (e.g., floors, windows and doors), for which a relatively small number of annotations is sufficient to provide enough variety.

We show that our method successfully captures the essence of a wide variety of building styles and allows creative applications such as example building use in a virtual city. In particular, we evaluate our approach against several methods and several datasets. We automatically generate procedural building models using the first 50 office building photographs of ImageNet [RDS * 15], the first 30 office building photographs of SUN [XHE * 10], and perform comparisons for the main stages of our approach. Altogether, our method allows users to create buildings in around 20 seconds, including silhouette specification and fully automated processing.

In summary, our main contributions include:

• A complete system to generate a procedural model of a building from a single photograph with minimum user input, • Novel independent modules that combine machine learning and optimization to recover building elements from a single image.

In particular, we introduce a method to jointly estimate camera pose and building shape from a silhouette, and a method to parse façades that contain significant variety in style and sizes.

Related Work

Our work is at the intersection of image-based modeling and inverse procedural modeling of buildings. We refer readers to the survey by Musialski et al. [MWA * 13] for an extensive discussion of urban reconstruction methods.

Automatic multi-view reconstruction. Structure-from-motion and multi-view stereo algorithms offer a robust framework to accurately reconstruct real-world 3D scenes from uncalibrated images [SCD * 06]. However, multi-view stereo produces unorganized point clouds or surface meshes, while we aim to produce semanticallyrich parametric models suitable for creative editing. Kelly et al. [START_REF] Kelly | Bigsur: Large-scale structured urban reconstruction[END_REF] recently made a significant step towards this direction by fusing multiple sources of information (coarse 3D mesh, street-level imagery, footprint) to produce structured 3D urban reconstructions. In contrast, we target the creation of a plausible procedural model using as little as a single photograph of a building.

Automatic single-view reconstruction. Automatically reconstructing buildings from a single image is a highly ill-posed task. The most successful approaches rely on machine learning to predict surface orientation or depth, effectively creating a pop-up of the visible surfaces in the scene [START_REF] Hoiem | Automatic photo popup[END_REF]LZcZ14,[START_REF] Liu F | Deep convolutional neural fields for depth estimation from a single image[END_REF]. While we also employ machine learning, we train our algorithm to predict the type and parameters of procedural shapes. This procedural approach brings strong domain-knowledge that helps regularize the generation and predict occluded parts.

Part of our problem is to estimate the shape of the building, For example, recent machine learning techniques estimate camera (or object) orientation. These methods differ in their strategies to divide the orientation parameter range into discrete bins and/or perform a regression-like analysis. For example, Massa et al. [MMA16] create bins to represent different orientation values and yield errors of about 15 degrees in at most 40% of the cases (worse otherwise). Su et al. [START_REF] Su | Render for cnn: Viewpoint estimation in images using cnns trained with rendered 3d model views[END_REF] also obtain orientation estimates with errors of over 10 degrees. Hara et al. [START_REF] Hara | Designing deep convolutional neural networks for continuous object orientation estimation[END_REF] obtain rotation estimates slightly under 10 degrees and provide comparative results to multiple other methods obtaining up to 40 degrees of error. While we take inspiration from these methods we make key adaptations to achieve the level of accuracy necessary for the subsequent steps of our pipeline. In particular, we cast camera intrinsic and extrinsic parameter estimation (8 parameters), as well as building mass parameter estimation (5-18 parameters), as a joint regression task. We simplify the task of the deep network by giving it a silhouette image rather than a realistic photograph. Further, this enables us to use our procedural modeling engine to generate a very large number of training images (300,000 images per grammar). Finally, we refine the prediction of the network with an optimization to tightly fit the 3D object to the input silhouette. Taken together, these improvements allow us to achieve fast and very accurate alignment of the building model with the input image (Table 2).

Interactive image-based modeling. User annotations can greatly help recover 3D models from a single or a few photographs. Existing interactive systems often combine annotations with heuristics for a limited set of shapes, such as cuboids [ZCC * 12], generalized cylinders [CZS * 13] and symmetric architectures [JTC09]. Other approaches such as the seminal façade system [DTM96] or the single-image method of [START_REF] Oh | Imagebased modeling and photo editing[END_REF] make less assumptions at the price of more involved user workflows. In contrast, our approach only needs users to provide the outline of the target building and is agnostic to the type of shape, as long as it can be expressed by a low-dimensional parametric model. The downside of our approach is that we are limited to the range of shapes expressible by the procedural grammars we train for; nonetheless, our evaluation shows that it can handle a wide variety of real-world buildings and our set can easily be extended.

Deep learning has recently been used to recover procedural models from line drawings in the context of sketch-based modeling [NGDA * 16, HKYM16]. In particular, we build on recognition CNNs and parameter estimation CNNs to generate procedural grammars, as originally proposed by Nishida et al. [NGDA * 16]. However, both [NGDA * 16] and [HKYM16] assume a fixed viewpoint, while we train a CNN for the more complex task of jointly estimating the parameters of the procedural shape and of the camera. In addition, Nishida et al. [NGDA * 16] require users to follow a strict multi-step modeling workflow while we only need a photograph with an outlined silhouette. Our evaluation shows that our system can generate buildings in a few seconds where Nishida et al. [NGDA * 16] needs 5-15 minutes of interaction (Figure 9). Inverse procedural modeling. Procedural modeling offers a compact and flexible representation of 3D models in the form of parameterized grammars [VAW * 10]. However, creating a procedural grammar from scratch is notoriously difficult, which motivates research in inverse procedural modeling (IPM). Some IPM methods recover both grammar and parameter values from 2D data (e.g., [ARB07, SBM * 10]) or from 3D models (e.g., [START_REF] Bokeloh | A connection between partial symmetry and inverse procedural modeling[END_REF]DAB16]). Other methods focus on extracting parameter values for a given procedural model (e.g., [TLL * 11, VGDA * 12, RMGH15]). None of these methods however focus on parameter estimation to generate a 3D model from a single building image and its silhouette with-out any further user intervention. Our approach is closer to the latter family of methods as we aim at estimating parameters for pre-defined grammars. However, we achieve high expressibility by defining a building as a combination of best-fitted grammars for mass, façade, and windows.

We have a similar goal as [START_REF] Vanegas | Building reconstruction using manhattan-world grammars[END_REF] and one of the applications of [FW16]. Vanegas et al. [START_REF] Vanegas | Building reconstruction using manhattan-world grammars[END_REF] extract textured 3D building masses from aerial photographs by extruding the provided building footprint and automatically applying floor transitions. However, they assume a Manhattan-world building and model façades as bitmap textures. Fan and Wonka [FW16] propose a parametric model of residential buildings and apply it to the reconstruction of houses from a single image. However, their approach requires the user to manually annotate all masses, façades, windows, and doors, including the selection of some geometry types (e.g., porch, garage, gable roof, hip roof, and flat roof).

Façade reconstruction. While there are many papers about façade reconstruction, most require the user to manually segment the façade and label each region (e.g., [MWW12, MG13, WYD * 14]), and only a few papers deal with the automatic segmentation and labeling of the façade. We build on the method by Müller et al. [MZWVG07], which uses mutual information to segment the façade into tiles and recursively splits each tile based on an edge map to extract windows. However, we found that this method is quite sensitive to the distortions, noise and occlusions encountered in our rectified façades. We achieve higher robustness by training a CNN to estimate the procedural layout of the façade which in turn is refined by an image-based approach. Recently, several deep network architectures have been proposed for image segmentation [RFB15, BKC17] and façade parsing [LZZH17]. While these methods can produce accurate parsing, the output is a pixelwise segmentation from which reconstructing a façade geometry is a challenging open problem.

The use of a procedural grammar to regularize façade analysis is similar in spirit to that of [KST * 09, TSKP10, TKS * 11, CSP14]. In particular, Koutsourakis et al. [KST * 09] use Markov Random Field optimization to estimate the parameter values of a shape grammar that matches a rectified façade image. However, their method only supports one non-conditional grammar that covers a particular style of façade. In a follow-up work, [TSKP10, TKS * 11] combine machine learning and procedural modeling for façade segmentation applied to Haussmannian style façades. A data-driven estimate of the segmentation is obtained using random forests trained on annotated façades, while a procedural model acts as a regularizer that penalizes labelings that do not follow the predefined rules. Cohen et al. [START_REF] Cohen | Efficient structured parsing of facades using dynamic programming[END_REF] uses dynamic programming to efficiently explore the solution space and produce higher quality solutions. These approaches can produce accurate segmentations for façade images that are similar to those in the training dataset. However, our experiments show that they make assumptions that do not generalize well to the greater variety of façades we target (see Figure 15 and Table 4). Note that all the aforementioned approaches were demonstrated on clean, well-rectified façade images. In contrast, we aim for a method that supports a wide range of façades and can be integrated into an end-to-end pipeline and as such be robust to distor-tions produced by approximate rectification and aliasing artifacts due to grazing-angle capture.

Overall, our objective is to provide a complete 3D procedural building model including the backside, façade, and window geometry from a single ground-level photograph. As far as we know, this is the first attempt to tackle this challenging problem.

Overview

Our approach automatically generates a procedural building model from a single photograph and a highlighted silhouette of the target building. Our system both estimates camera parameters and generates a grammar that yields 3D geometry similar to the target building. In this paper, we focus on street-level images because they are typically of high resolution. Nonetheless, our approach is general and is applied to aerial images as well.

Each of the three stages of our method (Figure 2) makes use of recognition CNNs to select appropriate procedural grammars and of parameter estimation CNNs to estimate their parameters. In addition, we propose dedicated simplification steps to match the visual appearance of the images with the training data and refinement steps that improve the estimated parameters with local optimizations. The recognition CNNs solve an image classification problem, for which we use AlexNet [KSH12] as it requires less training time than deeper networks like VGG16 [SZ14] and GoogLeNet [SLJ * 15], while resulting in an almost equivalent accuracy in our preliminary experiments. Prior work on viewpoint estimation also advocates the use of classification tasks for parameter estimation [SQLG15, MMA16, HVC17]. However, estimating parameters via classification does not scale well to our multi-parameter problems, since it would require predicting N × M probabilities, where N is the number of parameters to estimate and M the number of discrete values that a parameter can take. Instead, we rely on a standard regression task, for which we modify the AlexNet architecture by removing the last softmax layer, redimensioning the output to match the parameter vector, and retraining all layers (see supplemental materials for more details on network architectures). In the following, we describe the functionality of each stage.

• Building-mass generation. Using the target building silhouette as a simplification of the input photograph, this stage uses a recognition CNN to find the building mass style, and then, uses a style-dependent parameter estimation CNN to determine grammar and camera parameters. In addition, we perform an optimization to refine the alignment of the building mass geometry to the photograph, which is critical to properly rectify the façades and proceed with the next stage. Our final output combines the building mass grammar, the façade grammar, and the window/door grammars as well as all grammar parameter values. This collection of parameterized grammars is able to represent many different building configurations and can easily be used to create a city of buildings, as shown in Figure 18. More precisely, given an image of the target building I and its silhouette S, our pipeline estimates camera parameters θ C and an output grammar

G = G M (θ M ), G F (θ F ), G W i (θ W i )
, where G M denotes the building-mass grammar, G F denotes the façade grammar, and G W i denotes a set of window or door grammars. The building mass grammar contains parameters θ M that specify the detailed size of the shape. The façade grammar contains the parameters θ F to specify the floor height, width of columns, window size, margin size between windows, and style-specific parameters. The window/door grammars each have parameters θ W i that describe the 3D geometry. Please refer to the supplemental material for more details about the parameters.

Our approach and comparisons make use of several published datasets. The training images for our façade and window CNNs are created by altering images from the CMP dataset [START_REF] Tyle | Spatial pattern templates for recognition of objects with regular structure[END_REF] which contains a wide variety of façade styles. Our evaluation images are from ImageNet [RDS * 15] and from SUN [XHE * 10]. Our façade comparisons make use of the above datasets and also the ECP dataset [Teb11] (which contains Haussmanian style façades from Paris).

Building Mass Generation

The first stage of our method selects the grammar for the building mass G M (Section 4.1), and jointly estimates parameter values of the camera and building mass, θ C (Section 4.2) and θ M (Sections 4.3 and 4.4), respectively, such that the silhouette of the generated procedural building matches the silhouette in the photograph.

Our approach to estimate these parameters is inspired by the recent use of deep learning to predict viewpoint from a single image of a known object category [SQLG15, MRA15, HVC17], and to predict parameters of procedural shapes drawn from a fixed viewpoint [NGDA * 16,HKYM16]. However, predicting shape and viewpoint parameters concurrently requires significantly more training images to achieve sufficient accuracy. We discuss several strategies that we devised to filter out non-informative images from the training set. In addition, we describe how to refine the parameters estimated by the CNN using a derivative-free optimization.

Building Mass Grammar

We define grammars for 30 different building masses in a systematic way (Figure 3). We define six core building mass shapes

1) 2) 3) 4) 5) 7) 8) 9) 10) 11) 6) 12) 13) 14) 15) 16) 17) 18) 19) 20) 21) 22) 23) 24) 25) 26) 27) 28) 29) 30)
Figure 3: Building Mass Grammars. We define 30 grammars for the building mass in a systematic way. The first row defines single stack buildings with different footprints. The second row of buildings has the same footprints but have different roof shapes. The third and fourth rows show buildings with two stacks of masses, whereas the buildings in the bottom row have three stacks of building masses.

having different footprints. Then, we add parameterized grammars supporting alternative roof shapes. We further add parameterized grammars with two and three stacks of building masses. While using only a limited number of grammars to represent building masses may restrict the supported shapes, this restriction enables us to generate the shape of the building mass from a single image, which is otherwise an ambiguous problem and cannot be solved in general. Please refer to our supplemental material for more information about per-grammar building mass parameters. Each image in Figure 3 shows one example by randomly selecting parameter values. We highlight that our framework is not limited to this set of grammars. Additional grammars, and thus shapes, can be added unless it incurs significant ambiguity with the silhouette produced by other already included grammars.

Camera Model

We adopt a camera model that covers at least most street-level photographs. The projection matrix of a typical pinhole camera is

M = K[R|t].
K is the intrinsic camera matrix represented by

K =   f 0 Cx 0 0 f Cy 0 0 0 1 0  
where f is the focal length and Cx and Cy are the coordinates of the principal point on the image plane. Also, R denotes the cam-era rotation matrix, and t = [tx,ty,tz] T represents the camera position [START_REF] Hartley R | Multiple View Geometry in Computer Vision[END_REF]. There are 9 parameters in total, but the coordinates projected by M are computed up to a missing scale factor because of homogeneous coordinates. To remove the scale ambiguity, we determine the z coordinate of the camera position using the Dolly zoom as follows:

tz = L 2 tan f ov/2
where L is the assumed width of the scene at roughly the depth of the building as captured by the photograph and f ov denotes the approximate horizontal field-of-view. We fix L = 25 meters throughout the paper. As a result, we have a set of 8 parameters θ C = (φx, φy, φz, f ov,Cx,Cy,tx,ty) to estimate, where φx, φy, and φz denote the rotation angles around x, y, and z axes. Once the camera parameters are estimated, the focal length f can be easily calculated from f ov by

f = image width 2 tan f ov/2
in order to construct the intrinsic camera matrix K as well as the projection matrix M. Our camera model does not take into account lens distortion nor other kinds of distortions. We found that these types of distortions are negligible compared to the parameters that we consider in our camera model.

CNN Training

For each building mass grammar, we synthesized 300,000 images of silhouettes to train the corresponding building mass parameter estimation CNN. In addition, we randomly selected 300,000 images among all these synthesized images to train the building mass recognition CNN. Both types of CNNs were trained for 160,000 iterations each with a batch size of 256. While automatically generating procedural models and synthesizing their silhouettes is straightforward, we must consider several aspects to improve the end quality.

• First, since we only render silhouette lines, we seek to eliminate ambiguous training images from which a unique building mass shape cannot be determined. To this end, we discard training images in which the top or bottom face of the bounding box of the building mass is visible. This is reasonable because images taken from the ground level usually do not have the top or bottom faces visible. Further, for building shapes that have slanted roofs or multiple stacks of masses, we also check if at least one of the roof faces or the side faces of each stack of masses is visibleif not, then the generated image is discarded. • Second, we estimated the camera parameters of many images obtained from the Internet by using the vanishing point approach [CDR99, GMMB00], and from those estimations defined a fixed range of camera parameter values as follows:

         φx ∈ [0, 40] φy ∈ [20, 70] φz ∈ [-10, 10] f ov ∈ [20, 90]
and

         Cx ∈ [-0.8, 0.8] Cy ∈ [-0.8, 0.8] tx ∈ [-15, 15] ty ∈ [-15, 15]
This restriction is also important because some extreme parameter values that rarely occur in the street-level images may result in ambiguous silhouettes. For instance, φy = 0 means that the photograph is a front-view, which makes it difficult to infer the side shape of the building. • Third, we discard all images in which the building is too big to fit within the image canvas. This is because if only a small fraction of the building is visible in the image, there will be no way to recover the complete 3D geometry faithfully. After computing the 3D geometry from the grammar, all vertices are projected to the image plane and if at least one vertex is outside the image by more than 3% of the image resolution, then the image is discarded • Fourth, after the silhouette of the 3D geometry is rendered, the endpoints of the line segments are randomly translated within a range of [-1%, +1%] of the image resolution to train the CNN to be robust to minor errors in the input silhouette S.

Parameter Estimation

After the best building mass grammar is selected from the 30 candidates by the recognition CNN, our approach runs a dedicated parameter estimation CNN on the building silhouette to estimate the grammar parameters and calibrate the camera. While we considered using methods based on vanishing points to estimate part of the camera parameters [CDR99, GMMB00], we rejected this option for several reasons:

1. Outlining a building silhouette is an easier task than marking sets of lines converging to the same vanishing points, especially for novice users who have limited knowledge of perspective. 2. Vanishing point methods are not well suited for buildings that do not have dominant orthogonal orientations, such as cylinders (e.g., bottom left corner of Figure 7 and fourth column in Figure 8). 3. Even if we use an existing method to estimate camera parameters, this information needs to be provided in some form to the CNN in charge of estimating the building mass parameters, which is a challenge on its own.

We found that directly asking the CNN to jointly estimate camera and building parameters from the silhouette image is a simple solution to the above challenges, which proved to be very effective in practice. Nevertheless, while the parameter estimation CNN finds a good initial estimate of θ C and θ M , this estimate is often not precise enough to yield accurate façade rectification, as illustrated in Figure 11. This is reasonable considering the large parameter space of 8 camera parameters and up to 18 building mass parameters being simultaneously estimated. After multiple experiments, we found that using a numerical optimization approach is adequate to accurately refine the CNN-based parameter estimation. Hence, we define a distance metric between the input silhouette S and the silhouette Ŝ generated by the geometry using the estimated parameters. Let D = DistTrans(S) be the distance transform of the input silhouette and D = DistTrans( Ŝ) be the distance transform of Ŝ. Then, our distance metric is defined by where X(α) is an indicator function that returns 1 when α is true and return 0 otherwise, and Z is a normalization factor defined as

dist(S, Ŝ) = 1 Z ∑ x,
Z = ∑ x,y∈I X( Dx,y = 0) + ∑ x,y∈I X(Dx,y = 0).
We minimize the aforementioned distance metric by a boundoptimization-by-quadratic-approximation (BOBYQA) algorithm [START_REF] Powell | The bobyqa algorithm for bound constrained optimization without derivatives[END_REF] to refine the parameter values:

( θC , θM ) = arg min θ C ,θ M dist(S, Ŝ).
This optimization is similar in spirit to traditional model-based pose estimation methods [START_REF] Lowe | Three-dimensional object recognition from single two-dimensional images[END_REF]Mun06], where our CNN prediction acts as a very good initial guess. We show in Section 7.3 that this optimization often ends up in poor minima without proper initialization. Note also that using only the target building (boundary) silhouette instead of all interior contour lines is easier to optimize as it reduces potential mismatches between the two shapes.

Façade Generation

Once camera parameters and building mass are estimated, our method selects and rectifies a façade to be used in our façade generation process. A common strategy for façade analysis consists in first labeling image pixels into elementary classes (walls, windows, doors, balcony, etc) before estimating a façade structure that best agrees with the labels while respecting architectural constraints [TSKP10,TKS * 11,MMWVG12,CSP14,MMVG16]. However, we found that existing façade labeling algorithms trained on available datasets do not generalize well to our evaluation façade dataset (Figure 15). We propose an alternative approach that replaces the per-pixel façade labeling by a global estimation of the grid layout of the façade, and subsequently locates windows and doors within each cell of the grid (Figure 4a-d). Our experiments reveal that this coarse-to-fine approach trained on an existing dataset generalizes well to diverse façades. This process results in a simplified façade composed of windows and doors outlines, from which we estimate a façade grammar using synthetically-trained recogni-tion and parameter estimation CNNs (Figure 4e). We now detail each step of our façade parsing approach.

Façade Rectification

Our approach first rectifies the visible façades of the building and selects the best representative for façade and window processing. Since our grammars for building mass include curved shapes (e.g., cylinders), we model a façade as one or multiple vertical, planar rectangular faces { f i }. Then, a perspective transformation matrix T is calculated for each face f i to rectify it. Finally, the rectified façade image is generated by combining the rectified faces. Please refer to the supplemental material for more details.

In some cases, the rectified façade image might be distorted because of errors in the input silhouette and the building mass generation. These distortions and other aliasing artifacts are amplified when the façade is captured at grazing angle. In addition, even when multiple façade images are rectified without significant distortions, the façades of hidden sides of the building remain unknown. We address these challenges by selecting the façade with the largest projected area and use it for all sides of the building.

Façade Simplification

Following the same strategy as for building mass, in this step we convert the façade image into a simplified line drawing that captures the structure of the layout without texture and lighting. Our approach is inspired by the façade grid subdivision algorithm of [MZWVG07], which analyses gradient magnitude along image rows and columns to locate transitions between floors and columns of windows. However, we found that this gradient-based approach is very sensitive to the textures, lighting and occlusions present in our façades. Instead, we train a CNN to robustly estimate the number of floors and columns in a rectified façade and only use the gradient-based method to refine the grid.

We trained the façade grid parameter estimation CNN using images based the CMP façade dataset [START_REF] Tyle | Spatial pattern templates for recognition of objects with regular structure[END_REF], which contains 378 façade images with the numbers of floors and columns already annotated. To avoid overfitting, we convert the images to grayscale and augment the dataset with random rotations, translations, horizontal mirroring, blurring, and/or changes of brightness. In total, we generated 50,000 façade images to train our CNN, which significantly improved generalization to façades other than those in the original dataset.

Following [MZWVG07], we refine the grid by aligning its boundaries with local minima of the image gradients projected along the vertical and horizontal axis, as measured by the following functions:

V (y) = ∑ x | ∂I ∂x | H(x) = ∑ y | ∂I ∂y |
.

The local minima of V (y) correspond to floor boundaries, whereas the local minima of H(x) correspond to the vertical boundaries. However, since image gradients are often noisy, V (y) and H(x) contain many false local minima. Please refer to the supplemental materials for the visual analysis of V (y) and H(x). Müller et al.

[MZWVG07] exhaustively search among the many minima for the ones that yield the grid layout best respecting pre-defined floor height and tile width bounds. In contrast, the aforementioned CNN provides us with a good estimate of floor height and tile width automatically. We thus only perform a refinement of the grid by locally displacing the coordinates of the vertical and horizontal boundaries, x i and y j , to minimize ∑ i H(x i ) + ∑ j V (y j ) while keeping floor height and tile width within 75% and 140% of the estimated values. Figure 13 illustrates the effect of this refinement step on the recovered façade subdivision.

After the façade is subdivided into tiles and refined, our approach tests for the existence of a window (or door) in each tile, and locates the position of the window's (or door's) bounding box. While edge information is often used to detect a window/door boundary (e.g., [LN04,MZWVG07]), we found that the edges extracted from the rectified façade image are usually very noisy. Instead, our approach uses a window recognition CNN to check for the existence of a window/door, and if it exists, a window parameter estimation CNN to estimate four parameters: the 2D relative coordinates of the top left corner of the window/door bounding box and its width and height. For these CNNs, we obtain the training images from the same grayscale CMP façade images as we use for the grid parameter estimation CNN. By subdividing the façade images into tiles, we extracted over 10,000 tile images, and manually annotated the position and size of the window in each tile. We further augment the training images with random rotation, translation, blurring, horizontal mirroring, and change of brightness. Note that when the tile image is rotated, translated, or mirrored horizontally, the coordinates of the window boundary are updated accordingly. These modifications significantly increase the variation in the training images and avoid overfitting. For the window recognition CNN, since there are severe unbalance in the number of tiles between those that contain a window (i.e., positive example) and those that do not contain a window (i.e., negative example), we augmented more negative examples to balance. Altogether, we generated 100,000 positive examples and 100,000 negative examples for training the window recognition CNN. The positive examples are also used for training the window parameter estimation CNN. Our results show that the trained CNNs can precisely detect windows/doors in our rectified façades (Figures 4c and14).

Note that the floor heights and window tile widths computed in this step are not the final façade dimensions and might not be regular, if such is expected. During the next step, the façade structure will be regularized, if so discovered, in terms of floor heights and tile widths.

Façade Grammar

Once the simplified façade image F is computed (Figure 4d), we use a façade recognition CNN to recognize the best façade grammar and a façade parameter estimation CNN to estimate the parameter values. We define 16 façade grammars in a systematic way (Figure 5). The first four grammars have some variation vertically but no difference horizontally. The next four grammars have different styles in both axes. The next four grammars have different styles in the middle, and the last four grammars have different styles on both sides and in the middle. The same window color represents the Similarly to the building mass grammars, each grammar G F contains many parameters θ F to specify the details of the façade structure, such as the floor height, tile width, the position and size of the windows, and so on. Please refer to the supplemental material for more details about the parameters and their description. After parameters θ F are estimated by the CNN, the BOBYQA algorithm is used to refine the parameter estimation based on the simplified façade image F in a similar manner to the mass parameter estimation.

To train the façade recognition and parameter estimation CNNs, we synthesized 160,000 images in total, each of which show only window boundaries. Since the size and location of the detected windows in the simplified façade image may contain some noise and error, we perturbed the size and location of the windows in the synthesized images by adding a uniform noise that is up to 10% of the range of each parameter value. Then, the CNNs were trained with the synthesized images for 40,000 iterations.

Façade Color

Once the façade structure is identified and the façade is subdivided, we estimate the dominant color of the façade itself as a façade color. To do so, we run a k-means color clustering on the pixels that lie outside of the detected windows, and keep the centroid of the largest cluster as the façade color. We use k=10 clusters for all our results, and perform the color clustering in the perceptually uniform L*a*b color space.

We also considered computing one dominant color for each nonterminal node of the façade grammar. However, we found this local color computation to be sensitive to shadows and occlusions, which often cover significant parts of the façade (see supplemental materials for successful and failure cases).

Window Generation

To finish the building generation process, we use the estimated façade grammar to decompose the image into windows and doors tiles, and select for each tile a window/door grammar out of 31 6). We then select the best window style for each non-terminal G W i by maximum vote among the corresponding tiles. This voting strategy makes our approach robust to local variations within similar tiles.

To generate the training images, we use the same tile images that are extracted from the CMP façade dataset as described in Section 5.2. This dataset results in over 10,000 tile images, for which we manually annotated the window type. To further increase the variation in the training dataset, we apply a similar augmentation as in Section 5.2 to generate 100,000 tile images in total. Then, the window style recognition CNN is trained for 40,000 iterations with the batch size of 256 using the generated images.

Note that while our method recovers procedural grammars for the windows and doors, we currently keep the parameters of these grammars fixed. While estimating the parameters of each window to best fit a given image would further improve the quality of the end model, it would require annotating a large number of images for each window type. We keep the recovery of such details, as well as other façade elements such as balcony, for future work.

Results

We implemented our approach on an i7-based PC workstation with 16 GB of memory and NVidia GTX980 graphics card. Our tool was implemented in C++ using OpenGL/GLSL. We used the Caffe library [JSD * 14] as the framework to train the CNNs using GPUs and to generate building mass, façade and window geometries at run-time.

Our implementation includes 31 CNNs for building mass generation, 20 CNNs for façade generation, and 1 CNN for window generation. The input image for all CNNs is resized to 227 x 227 to enable using the pretrained weights of [KSH12] as initial values. Starting with pretrained weights quickens convergence and avoids overfitting during our training.

Generated 3D Buildings

Figure 7 shows some of the 3D building models generated by our approach. To evaluate the quality of our end-to-end system, we pro-Table 1: Accuracy of the Trained CNNs. The trained CNNs were evaluated against the test dataset. The second column shows the classification accuracy, whereas the third column shows the average RMSE of parameter estimation. For #floors and #columns, the RMSE was calculated based on the predicted #floors and #columns, but for other parameter estimation CNNs, the RMSE was calculated based on the predicted parameter values that are normalized between 0 and 1. The last column shows the computation time. Then, our system automatically generated 3D building grammars and the corresponding 3D geometry. While some complex details are not captured, our approach generates a grammar that contains the prominent characteristics of the building in the input image. Please refer to our supplemental materials for the full set of results.

Accuracy RMSE Time

We also applied our approach to aerial images (Figure 8), for which we changed the range of the camera parameter φx to [10,60] to train the CNNs. We observed a lower accuracy in camera parameter estimation on aerial images, which we attribute to the weaker perspective of such images, which are often captured from far away. Nevertheless, our approach manages to produce plausible building shapes and façades on these challenging cases.

Accuracy Evaluation

To evaluate the accuracy of the trained CNNs, we split each set of synthesized images into 80% for training and 20% for test datasets. For instance, we synthesized 300,000 images for each building mass grammar as described in Section 4.3. We randomly selected 80% of them as the training images to train the building mass parameter estimation CNNs. Then, the remaining images were used for evaluating the accuracy of the trained CNNs (Table 1). For other CNNs, please refer to the corresponding sections for the details about the image synthesis (Section 5.2 for the numbers of floors and columns, window existence, and window position and size, Section 5.3 for façade, and Section 6 for window style). Our results indicate that the trained CNNs generalize well to the test datasets without overfitting. Note that the computation time for window existence, window position and size, and window style is for each tile image. Thus, the total computation time depends on the number of tiles on a façade image, but for all selected building photographs, the total computation time was within 10 seconds.

ImageNet SUN

Figure 7: Generated 3D Buildings. For each building, a photograph and highlighted target building silhouette are provided to our system (odd rows), and a procedurally-generated 3D building (even rows) is automatically generated. Left side of figure has images from ImageNet and right side has images from SUN dataset. Please refer to the supplemental materials for a complete set of input photographs and generated 3D buildings.

Figure 8: Aerial Images. We applied our approach on aerial images by changing the range of camera parameters appropriately.

In particular, we set φx ∈ [10,60] for training the CNNs.

Building Mass Comparison

We first compare our approach to [NGDA * 16] (Figure 9) using the executable from the authors' website. Since [NGDA * 16] uses a fixed viewpoint, the user has to mentally rotate the target building in the photograph to sketch. In addition, the user needs to draw each building element (building mass, roof, windows, and ledges) in a fixed order, which takes around 4 minutes and multiple sketches.

In contrast, our approach supports photographs from an arbitrary viewpoint, and it requires only a few mouse clicks followed by automatic processing to produce a visually similar result in much less time.

We also compare the building mass portion of our approach to other non-CNN-based methods (i.e., coordinate descent, nonlinear bound-constrained optimization, and MCMC) in terms of the accuracy and computation time (Table 2). In this comparison, we use for each of the non-CNN-based approaches the vanishing point method [CDR99, GMMB00] to estimate the camera parameters. Note that the relative position of the camera with respect to the * 16] requires the user to draw each element (i.e., building mass, roof, and windows), which takes around 4 minutes, and the fixed viewpoint makes it difficult for the user to sketch a target building. In contrast, our approach needs only a few user drawn lines and then computes a result fully automatically.

building cannot be recovered by the vanishing point approach, so the camera position tx and ty has to be estimated by the non-CNNbased method. As expected, camera parameter estimation using the vanishing point method is very accurate given precise user input. However, the estimation for building mass parameters (i.e., width, depth, height) takes a lot of time for coordinate descent and for MCMC algorithms, and the accuracy of all the non-CNN-based approaches is very poor. In contrast, our approach can estimate both the camera parameters and the building mass parameters accurately within three seconds or less. Even though the accuracy of our estimation of camera parameters is inferior to the one by the vanishing point approach, our distance metric (Table 2) and visual comparison (Figure 10) indicate that it is sufficiently accurate for façade generation.

Building Mass Refinement

Figure 11 shows how the refinement of the building mass estimation improves the rectified façade image. While the building mass parameter estimation CNN can provide a good initial estimate for the camera parameters and the parameters of the building mass, the rectified façade image without refinement still shows some notice- able error (e.g., the cropped top floor and left side). The refinement by BOBYQA improves the parameter estimation for the building mass.

The accuracy of the provided building silhouette benefits our method (Figure 1). However, our building mass stage is robust to some silhouette inaccuracy and discontinuity (see Figure 12a andb). While the quality of façade image rectification is more sensitive to inaccurate silhouettes (see Figure 12c), our façade stage is heavily guided by window layout which is less affected by the silhouette errors. Thus, the final result is still a good representation of the captured building (Figure 12d). In addition, the constrained space of the building mass and façade grammars also contributes to the overall robustness of our system.

Façade Subdivision Evaluation

Figure 13 shows the improvement of façade subdivision by our approach compared to pure CNN-based and image-based approaches. The pure CNN-based approach estimates the floor height and column width, and this information is used to uniformly subdivide the façade. Our approach uses this result as an initial estimate but refines the boundaries based on the gradient magnitude. As a result, it can handle different floor heights and column widths in the same façade. We also compare our approach with an image-based approach [MZWVG07] that uses predefined ranges for floor height and column width as constraints and performs an exhaustive search to find the best set of boundaries based on the gradient magnitude. For this image-based approach, we obtained the a priori constraints by computing the average numbers of floors and columns of the CMP façade images, and deduce the floor height and column width for each façade. As a result, since the computed floor height and column width is approximate, the resulting subdivision may detect false boundaries or miss some boundaries -its performance depends highly on the accuracy and tightness of the a priori constraints. Table 3 shows a quantitative evaluation of the number of floors and windows estimated by our method. The root-meansquare errors (RMSE) are all less than 1, indicating relatively good estimates.

Window Detection Comparison

Figure 14 shows a comparison of window detection between an edge-based method and our approach. The edge-based method relies solely on the edges. For each tile image, the edge-based method runs a Canny edge detector, and the smallest rectangle that contains all the edges is detected as a window boundary. This method is not sufficient to precisely extract a window boundary especially given many false edges or blurry/occluded window boundaries. As a result, an edge-based method alone may fail to find window boundaries correctly (top row of Figure 14). In contrast, our approach uses a CNN that exploits not only the edges but also other features such as color and texture to find window boundaries, which significantly improves window detection (bottom row of Figure 14).

We also compare our approach with previous façade parsing

orange), roof (blue), sky (sky blue), and shop (green). Our approach detects only the windows, so the results show only two classes: window (red) and wall (yellow). While existing approaches perform well on the ECP dataset, they mis-classify many windows on our office building façades (see supplemental materials for more results) and tend to hallucinate shops at the ground level. In contrast, our approach produces results of similar quality on both dataset.

techniques [WFP10,TKS * 11] (Figures 15). In addition, we include a comparison to the fully-convolutional segmentation approaches, U-Net [START_REF] Ronneberger | U-net: Convolutional networks for biomedical image segmentation[END_REF] and DeepFacade [LZZH17]. We cropped the ECP façade images [Teb11] by removing the roof region since our approach extracts only the façade region excluding the roof. We also used our office building images, which consists of 80 rectified façade images, for this comparison. The dataset of the façade images and the ground truth labels are provided as the supplemental materials. For [TKS * 11], we used the trained random forest provided by the authors for the initial parsing and ran Q-learning for 5,000 episodes to obtain the results. For U-Net and DeepFacade, the model was trained for 100 epochs using randomly selected 80 Table 4: Pixel-Wise Accuracy of Façade Parsing. For the ECP dataset, the images are cropped to remove the roof region since our building mass stage extracts only the façade region. Also, since previous approaches classify façade elements in more classes than ours, we convert window, door, and shop classes to window, and all other classes to wall. For each approach, F1-score and accuracy of classification is measured. In the supplemental document, the precision and recall are also shown in Table A. Overall, while previous approaches outperform ours on the ECP dataset, their accuracy degrades significantly on our more general office façades. In contrast, our approach achieves a similar accuracy of around 0.75 on both datasets. The pictorial quality of accuracy 0.75 can be appreciated in Figure 15. While the façade grammar works as constraints to improve the parsing, the limited number of epochs often results in a poor local minimum unless a good initial parameter estimation is provided. In contrast, our approach uses the façade parameter estimation CNN to quickly get a good initial parameter estimation, which enables our approach to work well for both the ECP dataset and more general office building façade images. The fullyconvolutional approaches [RFB15, LZZH17] obtain accurate parsing on the ECP dataset, but produce noisy results on our façades which contain windows at many different scales.

Window Style Recognition

Figure 16 shows a qualitative evaluation of our window generation stage. We generated the tile images as described in Section 6, and trained the window style recognition CNN using the 80% of the tile images. Then, the other 20% of the tile images were used for evaluating the accuracy of the trained CNN. The results indicate that our augmented training images allow the CNN to robustly recognize the window style without overfitting.

Variation

Since the output of our approach is a grammar, our system can easily generate a wide variety of 3D buildings by randomly changing the parameter values and grammar selections (Figure 17). Using only a few photographs, the user can generate many 3D building models with some variation without any knowledge of procedural modeling. As one of the applications, we created a virtual city by generating many buildings using the grammars that were obtained by our system (Figure 18). We also generated the other elements of the city, including roads and sidewalks, using procedural modeling.

Limitations

Figure 19 illustrates the main limitations of our approach. While the currently implemented building mass grammars support a wide variety of building shapes, some buildings may not be supported.

In such a case, our approach finds the closest shape using the implemented grammars. Notice that the camera parameters are estimated nicely even for this case. With regard to façade generation, some façade images may not have any clear horizontal and verti-Figure 18: Virtual City Corner. Some of the generated 3D building grammars were used to generate many buildings in a virtual city. Other elements of the city including roads and sidewalks were also generated by procedural modeling.

Conclusions and Future Work

Procedural modeling is a popular approach to synthesize urban environments, but requires writing suitably parameterized grammars. We proposed an approach to significantly automate the generation of procedural buildings by taking a photograph as example input. Our system does not aim at an exact reproduction of a building, but rather at capturing its overall shape, the layout of its façade, and the style of its windows. To do so, we decompose the problem into logical stages (mass, façade, windows) and treat each stage with a common methodology that consists in simplifying the input to make it amenable to analysis by CNNs trained with synthetic data, and refining the output with custom optimizations. The resulting pipeline can generate a diversity of procedural buildings with no user intervention.

There are several interesting avenues for future work. First, our system relies on a number of recognition CNNs and parameter estimation CNNs, each trained separately. Since many of these CNNs perform a similar task, it is likely that they could share some of their weights, which would significantly reduce the memory consumption of our method. However, identifying which parts of the CNN could be shared among multiple tasks and which parts need to be specific to each task would require intensive experimentation. Second, while AlexNet produced satisfying parameter estimations for our problem (Table 1 and2), there are newer architectures such as ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] for even easier training and higher accuracy. Third, we would like to explore automatically obtaining the silhouette of many buildings in a single photograph -this might enable generating in place multiple buildings from one image.

Figure 2 :

 2 Figure 2: Our Pipeline. a) Given a single image with the target building's silhouette highlighted, b) our system automatically estimates camera parameters and building mass shape. c) Then, one of the façade images is rectified and d) subdivided into tiles. e) For each tile image, the size and location of windows is estimated to create a simplified façade image. f) This image is used to generate a façade grammar.g) The tile images are also used to recognize the window type. h) The final output is a 3D building grammar and a corresponding building geometry that looks similar to the input photo.

  y∈I Dx,yX( Dx,y = 0) + ∑ x,y∈I Dx,yX(Dx,y = 0) c 2018 The Author(s) Computer Graphics Forum c 2018 The Eurographics Association and John Wiley & Sons Ltd.

Figure 4 :Figure 4 :

 44 Figure4: Window detection and façade reconstruction. 1) Given the façade image, 2) our approach uses the imagebased approach to subdivide it into tiles. 3) Then, the window detection CNNs are used to detect windows, and 4) a simplified façade image that contains only the window rectangles without any other types of texture is generated. 5) Finally, the façade CNNs recognize the façade style and estimate the parameter values for the selected façade grammar snippet.

Figure 5 :

 5 Figure 5: Façade Grammar. The first four grammars have variation in a vertical direction but no variation horizontally. The next four grammars (5-8) have different styles at building edges. The first four grammars in the bottom row (9-12) have different styles in the building middle. The last four grammars (13-16) have different styles in building sides and in building middle.same non-terminal. For instance, all the windows of façade grammar 1 are the same non-terminal. But, façade grammar 3 has three different non-terminals for the windows: a first one for the ground floor, a second one for the top floor, and a third one for other floors. Similarly to the building mass grammars, each grammar G F contains many parameters θ F to specify the details of the façade structure, such as the floor height, tile width, the position and size of the windows, and so on. Please refer to the supplemental material for more details about the parameters and their description. After parameters θ F are estimated by the CNN, the BOBYQA algorithm is used to refine the parameter estimation based on the simplified façade image F in a similar manner to the mass parameter estimation.

Figure 9 :

 9 Figure9: Building Generation Comparison. [NGDA * 16] requires the user to draw each element (i.e., building mass, roof, and windows), which takes around 4 minutes, and the fixed viewpoint makes it difficult for the user to sketch a target building. In contrast, our approach needs only a few user drawn lines and then computes a result fully automatically.

Figure 11 :Figure 12 :

 1112 Figure 11: Effect of Building Mass Refinement. a) Without refinement of the building mass estimation, there is a noticeable error in the rectified façade image. b) Our refinement optimization suitably improves the resulting façade image for the subsequent façade generation stage.Robustness

Figure 13 :

 13 Figure 13: Comparison of Façade Subdivision. The top row shows the façade subdivision by a CNN-based method, which uniformly subdivides the façade based on the estimated floor height and column width. The second row shows the results by an imagebased method using predefined numbers of floors and columns to estimate the floor height and column width. The bottom row shows improved subdivision by our approach.

Figure 11 :

 11 Figure 11: Comparison of the window detection. The top row shows the detected windows by the edgebased approach, whereas the bottom row shows the results by our approach.

Figure 14 :Figure 15 :

 1415 Figure 14: Comparison of Window Detection. The top row shows the windows detected by an edge-based approach, whereas the bottom row shows our more accurate results.Updated

Figure 19 :

 19 Figure 19: Failure Cases. a) Our currently implemented grammars may not support some complicated building shapes. b) However, our CNN-based approach does find the closest shape and still estimates camera parameters well. Also, our façade generation approach does not work well if the façade does not have clear horizontal and vertical boundaries. From left to right, c) the rectified façade image, d) façade subdivision, e) detected windows, and f) generated façade structure are shown. cal edges. In this case, subdividing the façade into tiles does not work well, and the window detection fails. Nonetheless, our façade CNNs still select a grammar and estimate parameter values that produce a plausible façade structure.

•

  Façade generation. This stage proceeds with two main parts. The first part simplifies the largest area façade into a grid and locates within each grid tile the location and size, if any, of a window or door. Then, an image-based refinement is used. The second part feeds the aforementioned grid-based simplification of façades and windows/doors to a recognition CNN in order to determine the façade grammar style. The grammar parameters are then estimated using a style-dependent parameter estimation CNN. A subsequent optimization-based refinement improves the parameter values based on the simplified façade image. It is worth noting that we came up with this novel façade generation approach after extensive experiments with existing approaches (see Figures13 and 15and Table4for details). None of the existing approaches could handle the wide variety of façade images we target.• Window generation. Using the tiled procedurally-generated façade, a recognition CNN straightforwardly estimates the window style. Finally, we use a custom method to estimate façade colors.

  qualitative evaluation in the form of 80 buildings generated from external image collections. We selected the first 50 office building photographs from ImageNet [RDS * 15] and the first 30 office building photographs from SUN [XHE * 10] excluding aerial images and images that show only a part of the building, and highlighted the silhouette of a target building in each image.

				[sec]
	Camera parameters Building mass	-99 %	0.006 0.004	2.6
	#floors, #columns	-	0.25	0.02
	Window existence	93 %	-	0.02
	Window position and size	-	0.058	0.02
	Façade	95 %	0.006	0.04
	Window style	91 %	-	0.02
	vide an extensive

Table 2 :

 2 Comparison of Computation Time and Accuracy forBuilding Mass Generation. Each cell shows the average estimation error (100 trials) as a percentage of the parameter value range. We compare our approach to coordinate descent, BOBYQA, and MCMC for building mass estimation, using vanishing points to estimate the camera parameters except the camera position. We use the distance metric defined in Section 4.4 to evaluate accuracy.

	Ground truth	VP + Coord. desc.	VP + BOBYQA	VP + MCMC	Our approach
	Figure 10: Visual Comparison of Building Mass Generation.
	Given a silhouette of the ground truth image, the estimation results
	are compared between our approach and other non-CNN based ap-
	proaches. Estimation by other approaches is very poor even though
	the camera parameters are precisely estimated by the vanishing
	point approach.
			VP +	VP +	VP +		Ours
			Coord. desc. BOBYQA MCMC
		φx	0.002 %	0.002 %	0.002 % 0.08 %
		φy	0.004 %	0.004 %	0.004 %	0.1 %
	Camera	φz f ov Cx Cy	0.005 % 0.003 % 0.19 % 0.13 %	0.005 % 0.003 % 0.19 % 0.13 %	0.005 % 0.003 % 0.01 % 0.2 % 0.19 % 2 % 0.13 % 1 %
		tx	0.3 %	0.3 %	0.2 %		0.2 %
		ty	0.3 %	0.8 %	0.2 %		0.1 %
	Building	W D H	8 % 10 % 5 %	35 % 10 % 25 %	8 % 8 % 8 %		2 % 2 % 1 %
	dist(S, Ŝ)	7657	14922	3103		0.85
	Time [sec]	95.5	1.8	9531.8		2.6

Table 3 :

 3 Quantitative Evaluation of Façade Subdivision. Our façade stage accurately estimates the number of floors and the number of windows per floor.

		ECP		Office building
		#floors #windows #floors #windows
	RMSE	0.10	0.22	0.55	0.50

  Window Style Recognition. Given a tile image, our window style recognition CNN selects the best window grammar. Given an input photo and the silhouette line, our system yields not only a 3d building grammar that is generated based on the input but also a wide variety of 3d geometry by randomly changing parameter values and snippets.-10.736, -47.192, -0.375, 53.796, 0.079744, -0.11257, 4.142, 2.857, 49.282Figure 17: Variation. Our system yields not only a 3D building grammar that is generated based on the input but also a wide variety of 3D geometry by randomly changing parameter values and grammar selections.

		Input tile images	Selected grammar
			Door
	Figure 16: Input photo	Output	Variation

Figure 14: Variation.

c 2018 The Author(s) Computer Graphics Forum c 2018 The Eurographics Association and John Wiley & Sons Ltd.

Acknowledgements

We would like to thank the authors of DeepFacade [LZZH17] for helping us generate façade parsing results, and the anonymous reviewers for their constructive suggestions. This research was partially funded by the ERC starting grant D 3 (ERC-2016-STG 714221), NSF CBET 1250232 and IIS 1302172, and by research and software donations from Adobe and Google.


Galvao Flavio
email: flavio.calhau@ufba.br

Calhau

Alysson Pezzutti
email: pezzuttinho@gmail.com

Joberto S B Martins
email: joberto.martins@unifacs.br

On Evaluating Power Loss with HATSGA Algorithm for Power Network Reconfiguration in the Smart Grid

Keywords: Power Network Reconfiguration, Smart Grid, "R" Language, HATSGA, Tabu Search, Genetic Algorithm, IEEE 14-Bus

This paper presents the power network reconfiguration algorithm HATSGA with a "R" modeling approach and evaluates its behavior in computing new reconfiguration topologies for the power network in the Smart Grid context. The modelling of the power distribution network with the language "R" is used to represent the network and support computation of distinct algorithm configurations towards the evaluation of new reconfiguration topologies. The HATSGA algorithm adopts hybrid Tabu Search and Genetic Algorithm strategy and can be configured in different ways to compute network reconfiguration solutions. The evaluation of power loss with HATSGA uses the IEEE 14-Bus topology as the power test scenario. The evaluation of reconfiguration topologies with minimum power loss with HATSGA indicates that an efficient solution can be reached with a feasible computational time. This suggests that HATSGA can be potentially used for computing reconfiguration network topologies and, beyond that, it can be used for autonomic selfhealing management approaches where a feasible computational time is required.

I. INTRODUCTION

Smart Grid represents a modern vision of a dynamic electricity grid, in which electricity and related information flow together in real time, allowing near-zero economic losses in the event of outages and power quality disturbances. All of this being supported by a new energy infrastructure built on top of communication channels, distributed intelligence and possibly clean power [START_REF] Sarvapali | Putting the 'smarts' into the smart grid: a grand challenge for artificial intelligence[END_REF].

Outages on power supply are inevitable, whether for system components preventive maintenance interventions or operation of a protective device in the presence of a failure, among other possibilities. A maneuver plan must exist to deal with the effects resulting from interruptions, to minimize the affected area and restore power supply of such areas as soon as possible.

The computation of distribution network reconfiguration consists basically in finding, among all possible combinations, a set of configurations that (i) minimize the number of switching operations while keeping the radial structure of the network, (ii) reduce the energy loss and (iii) reduce the number of consumers without electricity supply. In addition, it is necessary to safeguard voltage levels restrictions at the point of load, maximize current flow in the branches and safeguard lines flow capacity and nominal power of the transformers [START_REF] Kumar | Implementation of genetic algorithm for distribution systems loss minimum re-configuration[END_REF].

In brief, this work aims to evaluate HATSGA algorithm behavior for the problem of distribution power network reconfiguration.

II. RELATED WORK

In recent years, significant research has been done to minimize power loss in the process of reconfiguring distribution power systems.

The reconfiguring of distribution power system has a combinatorial nature [START_REF] Carreno | An Efficient Codification to Solve Distribution Network for Loss Reduction Problem[END_REF] and the search of the best computational time for supporting the decision-making process in real time has been focused on recent research [START_REF] Thomas | Distribution Automation Leading to a Smarter Grid[END_REF], [START_REF] Haughton | Smart distribution system design: Automatic reconfiguration for improved reliability[END_REF], [START_REF] Merdan | Multi-Agent system for selfoptimizing power distribution grids[END_REF].

Tabu search algorithm has been used for several combinatorial optimization solutions [START_REF] Gallego | Optimal Capacitor Placement in Radial Distribution Networks[END_REF], [START_REF] Cherkaoui | Optimal configuration of electrical distribution networks using heuristic methods[END_REF]. In [START_REF] Thakur | Application of Tabu-Search Algorithm for Network Reconfiguration in Radial Distribution System[END_REF] Tabu search is shown as a meta-heuristic method for network reconfiguration problem in radial distribution systems. In [START_REF] Abdelaziz | Distribution system reconfiguration using a modified Tabu Search algorithm[END_REF] proposed a method of reconfiguring networks through a Tabu search algorithm which was modified focusing on reducing the opening and closing keys and minimizing the loss of active system. The proposed HATSGA algorithm enhanced the Tabu list to have more data-related computation and reduce the computation time avoiding exhaustive computation.

In [START_REF] Hong | Genetic algorithm based network reconfiguration for loss minimization in distribution systems[END_REF] a method based on genetic algorithms (GAs) is used to minimize loss in distribution systems by using encoding/decoding vertices to determine network configuration. The number based on the vertices was used in GAs for encoding/decoding of chromosomes and the system topology is radial. In general, using methods based on AI (Artificial Intelligence) proved to be valuable in a variety of applications [START_REF] Kiran | State Of Art For Network Reconfiguration Methodologies Of Distribution System[END_REF]. HATSGA does use a distinct genetic algorithmic approach by using elitism to choose among potential solutions. This is effectively different from using AI techniques to compute the entire reconfiguration solution.

Methods based on hybrid algorithms are indicated as having the potential to significantly reduce computational time of solutions [START_REF] Kiran | State Of Art For Network Reconfiguration Methodologies Of Distribution System[END_REF].

III. MODELING THE IEEE 14-BUS WITH "R" FOR POWER LOSS COMPUTATION

Graphs are used to model the structure of electrical grids for various purposes, and to verify its resilience to outages. In this 1 work the distribution network being reconfigured is modeled using graphs theory with language "R".

Language "R" was adopted due to its capability to semantically represent with flexibility the basic components of a distribution network (switches, branches, feeders, operational parameters, among others). In addition to that,"R" does present a series of programming flexibility aspects such as powerful data types representation and manipulation together with an attractive set of tools that are necessary for graph computation [START_REF] Calhau | HATSGA -An Hybrid Algorithm using Tabu search and Genetic Strategy with R Modeling for Network Reconfiguration[END_REF], [START_REF] Calhau | The "R" Approach for Modeling a Reconfiguration Problem in Smart Grid Networks[END_REF].

A. Generic modelling a distribution network with graphs and "R"

A power distribution network is composed by a set of elements where the main element is the bus. The buses are interconnected by connection lines. Generators, loads and synchronous compensators are also attached to the buses in the network defining their characteristics as slack, load bus or generator bus (Figure 1). In the distribution network the connection lines may include switches. These switches can be on (closed -tie switch) or off (open sectionalizing switch) to either have an effective connection through the line between buses or not [START_REF] Calhau | HATSGA -An Hybrid Algorithm using Tabu search and Genetic Strategy with R Modeling for Network Reconfiguration[END_REF]. Fig. 2: Network Generic Graph Mapping [START_REF] Calhau | HATSGA -An Hybrid Algorithm using Tabu search and Genetic Strategy with R Modeling for Network Reconfiguration[END_REF].

In terms of the graph theory, a power distribution network is generically mapped as a connected graph G = {N z , E m } with a set of nodes N , N = {N 1 , N 2 , ...N z }, and a set of edges E, E = {E 1 , E 2 , ...E m } (Figure 5). Nodes in the graph (vertex) have degree N D i ≥ 1 and the network has a topology that may include loops or be radial with no loops. Edges interconnect nodes in the graph mapped topology -

(E i = {V i , V i } / ∈ G).
The modelling of the power distribution network with language "R" basically takes the nodes and edges used in the generic graph topology representing the network and adds a set of more specific mappings and powerful parameter representation as follows (Figure 3): -Connection lines (network) are mapped to "edges" (as in graph representation); -For each "edge", it is defined using "R" an entry (value) at the "Edge Parameters Matrix EPM" (Figure 3a); -Connection lines with either tie switch (switch closed) or sectionalizing switch (switch open) behaviors are modeled as distinct type of edges (connecting or not vertexes); and -Vertex degrees, as in graph representation, are modeled with "n" distinct edges between vertexes and associated EPMs entries. -Buses (network) are mapped to vertex; -For each vertice, it is defined using "R" an entry (value) at the "Vertex Parameters Matrix -VPM" (Figure 3b); -Slack bus, load bus and generator bus (modeling generators/feeders) behaviors are modeled as different types of vertex using VPM; The Vertex Parameters Matrix (VPM) (Figure 3b) shows that data format for input the parameters at each bus in the power system. Thus, at all the buses, the Voltage magnitude and angle, the loads (P-Load & Q-Load), generation (P-Gen & Q-Gen), reactive power limits (Q-min & Q-max), and Shunt Capacitance should be specified (usually set to zero when not needed).

VPM is composed by a set of N-dimensional vectors or lists using "R" data types representation. Each entry on the matrix (vector or list) stores all parameters or attributes associated with the vertex modeled as a specific bus (including its behavior as slack, generator or load bus). Parameters values, attributes, properties and parameter descriptions represented in the matrix include fundamentally all electrical parameters relevant (or not) for the computation. In addition, a set of user defined parameters is included in the matrix. In effect, the adopted approach supported by "R" modelling allows a rather general description of the bus parameters and, beyond that, can be easily adjusted or updated by including new elements. For "R" computation, any additional adjustment in the matrix modelling corresponds to redefining the dimension of the matrix and vectors used together with the description of the parameters.

The Edge Parameters Matrix (EPM) (Figure 3a) stores and represents transmission line parameters and data to be used by HATSGA. Parameters like R (resistance), X (reactance) and Line Charging (1/2B) are electrical properties of the line, while the tap ratio represents the transformer tap settings and line limit represents the thermal rating of the line.

The Edge Parameters Matrix (EPM) is equivalent to VPM and includes all edge parameters, attributes and properties relevant to the computation of network reconfiguration. In terms of the "R" computation it is important to mention that each individual element of the matrix entry can, in turn, have a multi-dimensional representation allowing very powerful representation of the modeled network. In addition to that, various data types may be used when modelling the network with VPM and EPM and on-the-fly modifications are allowed facilitating the computation.

B. Modeling the IEEE 14-bus with "R"

Figure 4(a) depicts the IEEE 14 bus system with 14 bus bars, and 20 links connecting them that will be used in the HATSGA simulation. Figure 4(b) is the corresponding graph mapped from the original IEEE 14 bus system.

The HATSGA algorithm uses in this implementation the minimum power loss as the objective function but allows the use of other general objectives like "priority" (previewed in the EPM matrix) in addition to the minimum loss. This, for instance, can be helpful in cases where we want to reconfigure a network keeping certain areas with some priorities.

IV. HATSGA ALGORITHM

The hybrid algorithm HATSGA computes a reconfiguration topology for a radial power distribution network modeled in "R" language having as its basic constraint to minimize the power losses. In terms of the calculation, HATSGA algorithm adopted the Newton-Rapson method [START_REF] Ben-Israel | A Newton-Raphson method for the solution of systems of equations[END_REF] that, in turn, is based on the minimum power loss equation illustrated in equation 1. The values of the parameters of the matrices EPM and VPM (Figure 3a and 3b) are used. Where

minf = n i=1 k i r i P 2 i + Q 2 i V 2 i (1)
• n represents total numbers of branches (edges).

• r i -resistance of edge i.

• Q i -reactive power of edge i.

• P i -active power of edge i.

• V i -voltage on head node of branch i.

• k i -switch on branch i, 1 can equal to closed, 0 can equal to open. HATSGA's strategy minimizes the search space solution by eliminating topology configurations that do not comply with constraints criteria like radial configuration, resistance and reactance, among others.

In terms of the genetic algorithm strategy, HATSGA uses "elitism", a technique inspired by evolutionary biology and natural selection. In this case, elitism is used to select potential topologies that can be used to compute new reconfiguration solutions by selecting the best or most adequate electrical parameter(s) that may lead to the best possible result in the computation of new minimal solutions for power loss.

The Tabu Search algorithmic approach within HATSGA uses a list to store found solutions that should not be considered in the computation (forbidden). That is used to do not visit solutions that were previously considered (illegal movements). Conventional Tabu List implementations consider all topologies but only stores the minimal power loss for the best solution found while computing. The Tabu List conventional implementations also uses a temporary list, meaning that after computation the Tabu list is deleted.

HATSGA uses a modified Tabu Search algorithm by introducing to the conventional "tabu list" a set of associated parameters. In effect, the HATSGA Tabu List is a twodimensional matrix composed by a list of open switches and the power loss computed for all the resulting topologies. Another aspect differentiating the conventional tabu list from the HATSGA's one is that the list is always kept during computation to allow some optimizations in terms of the computational time.

Distribution systems commonly operate with a radial topology. HATSGA imposes radiality constraint to compute solutions, and the summary of the strategic phases of the algorithm are as follows:

• The algorithm always starts with a radial topology obtained by the PRIM's algorithms that creates a spanning tree for the network topology;

• From the initial trigger topology, it is calculated the minimum power loss and the HATSGA Tabu List is initialized with its first entry (topology -set of open switches -power loss);

• HATSGA now takes the list of open switches (available at the modified Tabu List) and starts closing the switches creating, as such, sectorial loops (as a resulting property of the spanning tree algorithm and topology);

• For each sectorial loop found, HATSGA finds a new set of open switches that generates new sector set of radial topologies;

• For each sectorial loop found and set of derived radial topologies, HATSGA uses the elitism method to select the set of topologies for computing the power loss;

• This approach represents in effect a new embedded heuristic that effectively minimizes the set of possible solutions and reduces the overall computation time for the minimum power loss calculation;

• For each sectorial loop and topologies chosen by elitism the power loss is computed and the HATSGA modified Tabu List is updated with eventual new minimum power loss values;

• The process continues with the next open switches creating new loop sectors that are minimized in terms of topologies using elitism and so on till the entire list of open switches if sequentially considered.

V. HATSGA OPERATIONAL MODEL

The HATSGA algorithm starts with a graph topology representing the power network (IEEE 14-bus in this example) supported by the "R" language mappings (VPM, EPM matrixes and other relevant aspects of the mapping) as described in section III (Figure 5).

HATSGA basic requirement is to start with a radial topology. Figure 6 illustrates a possible radial topology (the initial trigger topology) obtained from the IEEE 14-bus graph with R mapping by using the Prim's algorithm. The Prim algorithm generates a minimal tree topology in which the sum of all edges is minimized keeping all vertices interconnected without loops. Fig. 5: The IEEE-14 bus test system graph map (nodes) with language "R" support. Fig. 6: An example of radial topology obtained with Prim algorithm (initial trigger topology). I) that will drive the remaining execution steps of the HATSGA algorithm. The minimal loss topology search realized by HATSGA uses a "sector-based" graph approach with an associated heuristic. The sector-based approach is effectively a partitioning strategy adopted in this graph-based computation that, in turn, makes use of the basic properties of the spanning-tree algorithms. The heuristic used for each sector computation will contribute to minimize the total computation time required to obtain the results and, as such, contributes to a more scalable algorithm execution.

The initial trigger topology has an associated list of open switches (Table

The HATSGA algorithm uses the list of open switches obtained from the initial trigger topology (Table I) to create sectors with loops. Figure 7 illustrates switch S1 being closed and, as such, creating a sector loop in the previously loop-free topology. Fig. 7: Sector loop generated by closing S1 switch.

Once the loop is created, HATSGA gets the list of edges belonging to this sector loop (cluster) and, following that, will compute new reconfiguration topologies for this cluster applying a new heuristic (COH -Cluster Optimization Heuristic) based on "elitism" (Figure 8). In "elitism" at least one copy of the best solution is passed onto the new population (possibilities of solutions) so that the best solution can survive successive generations. Table II exemplifies the possible edges that might be used to eliminate loops (LoopList) in the graph and the edges selected (filtered) by the elitism heuristics (LoopElitism). Based on the "LoopElitism" switches (edges) list the HATSGA algorithm computes the minimal power loos for this cluster. Figure 9 illustrates a topology obtained after computing the minimal power loss.

VI. HATSGA TEST SCENARIOS AND RESULTS

The objectives of the HATSGA test scenarios are:

• Evaluate HATSGA behavior regard minimum power loss computation results for distinct initial topologies generated by the PRIM's algorithm with different edge "priorities";

• To evaluate the computational time required to compute the solutions.

A. HATSGA Test Scenarios

HATSGA test scenarios uses the IEEE-14 test system, modeled on graph with 14 vertexes and 20 edges (Figure 5) as the power system.

• HATSGA evaluated metrics:

-System power loss; o HATSGA system power loss computational time.

• HATSGA System Parameters:

-Initial radial topology algorithm -Prim; -Heuristic algorithm for Search Solution -Tabu Search and Elitism; -Power flow method -Newton-Raphson;

-Priority (used effectively as edge weight in the computed Prim topology).

• Power Distribution Workload Parameters:

-EPM Matrix; -VPM Matrix.
The results were obtained on a Macbook with an Intel Core i7 2.6 Ghz CPU and 8 GB RAM.

The power loss computation time was measured by the function (proc.time) available with the "R" programming environment. This function determines how much computational time (in seconds) the currently running R process (HATSGA code) has already taken. The proc.time function essentially works as a stop-watch: you initialize it to a starting time, run all the desired code, and then stop it by subtracting the starting time from the ending time.

The overall expected result of the HATSGA algorithm is that it minimizes computation and keep at the same time the quality of the solution by using elitism with a set of electrical parameters that, potentially, lead to a minimum power loss.

Table III shows the computed power system loss and computational time (in seconds) for 50 simulation runs where all initial trigger topologies are guaranteed to be distinct. The priority used (weight) for the initial topology edges are generated randomly with values from 1 to 1000.

In terms of the computational time required to compute the power loss, the mean value obtained for IEEE 14-bus was 1.99 seconds with 95% of confidence interval.

In terms of the power loss, the minimum value obtained was 4,25 with a mean computed value of 5.07.

In terms of the power loss computation, HATSGA gets similar results (minimal loss: 4,25; mean: 5,07; 95% confidence interval) for distinct initial trigger topologies. In terms of the numbers involved in the simulation runs, there are for IEEE 14-bus 3909 possible of minimum spanning tree topologies and HATSGA, using its heuristics (Prim, Tabu and Genetic) reduces the number of generation trees to a number around 50 effectively possible and considered topologies.

In terms of the minimal power loss computed or, in other words, the quality of the solution, HATSGA algorithm behaves better than most algorithms found and documented in the literature obtaining the second-best quality result (Table IV [START_REF] Nachimuthu R D ; Basha | Reactive Power Loss Optimization For An Ieee 14-Bus Power System Using Various Algorithms[END_REF]). To the extent of our knowledge, no further detailed comparison can be made in relation to these referred solutions because there is no explicit information how they compute their results. Being so, the comparison is only in terms of the result obtained.

VII. CONCLUSION

The hybrid algorithm (HATSGA) models the distribution network using the language "R". The "R" modelling allowed a simple and efficient way to represent and compute minimal spanning tree algorithms with the radial topologic solutions required for the reconfiguration problem. "R" language also allows the introduction of some semantics for network graphs representation that are essential for computing more elaborate, complex and qualified topologies in which various user requirements are considered.

HATSGA simulation results obtained for the IEEE 14-bus topology show a feasible response time of 1.9 seconds on a typical top-desk computer. That suggest firstly, that this algorithm can be used for computing reconfiguration network topologies nearly on-the-fly, at least, for networks as complex as IEEE 14-bus. Secondly, this suggests that HATSGA be used for autonomic self-healing management approaches in the Smart Grid reconfiguration network scenario where a feasible computational time is required.

In terms of the minimal loss achieved, HATSGA algorithm got results that are among the best ones found in the literature (second best) and, as such, does places this solution as an effective approach to compute power loss and find reconfiguration topologies. The elitism heuristics used within HATSGA proven to have a double positive aspect. Firstly, it minimizes the computational time required to compute the minimum loos topology that is essential for large scale and more complex topologies. Secondly, it drives the scalability of the computation based on real and effective electrical parameters configured in the algorithm itself. In other words, the "expertise" of the engineers is, fundamentally, the driver for the proposed heuristic.

The scalability of HATSGA for very large power distribution networks, although suggested as possible in this simulation run for IEEE 14-bus, is an aspect not fully addressed at this stage of the research and, as such, next step will include simulations using more complex and large-scale topologies.

Fig. 1 :

 1 Fig. 1: Power distribution network elements.

Fig. 3 :

 3 Fig. 3: Mappings parameter representation

Fig. 4 :

 4 Fig. 4: (a) IEEE-14 bus test system, (b) Computational mapping model (graph) of IEEE-14 bus.

Fig. 8 :

 8 Fig. 8: The Cluster Optimization Heuristic (COH).

Fig. 9 :

 9 Fig. 9: Example of graph resulting from loop elimination computation generated in Figure 7.

TABLE I :

 I Open Switches lists obtained with the Initial Trigger Topology

	Initial Trigger Topology (from IEEE-14bus)
	Open Switches	S1; S4; S5; S8; S9; S12; S13

TABLE II :

 II Possibilities of eliminating loops (with and without elitism) by manipulating the status of edges.

	Loop Switches
	(cluster example in Figure 7)
	LoopList	S1; S2; S3; S6; S7
	LoopElitism	S1; S6; S7

TABLE III :

 III Hatsga simulation results

	Simulation	Opened	System	Computational
	Run	Switch(es)	Loss	Time
	1	5-1-3-9-7-13-17	42.506	2.14
	2	1-3-4-7-13-15-17	56.688	1.991
	3	5-7-6-15-1-13-17	57.801	2.084
	4	6-7-1-8-4-13-17	42.506	1.921
	5	1-3-4-7-17-13-15	42.506	1.987
	6	5-7-6-9-1-13-17	42.506	1.958
	7	1-3-4-9-7-13-17	42.506	2.002
	8	1-3-4-13-15-7-17	62.429	1.936
	9	7-1-3-9-4-13-17	57.801	2.013
	10	1-3-7-4-9-13-17	42.506	2.239
	11	1-3-4-7-13-15-17	42.506	1.958
	12	7-5-6-1-9-13-17	42.506	1.991
	13	1-3-7-9-4-13-17	42.506	1.959
	14	6-7-1-9-4-13-12	42.506	1.868
	15	1-4-5-7-13-15-17	42.506	1.997
	16	1-3-7-8-4-13-17	57.801	2.048
	17	1-3-7-9-4-17-13	42.506	2.292
	18	1-3-7-9-4-17-13	42.506	1.955
	19	2-3-4-9-7-17-13	56.688	1.921
	20	2-3-4-8-13-7-17	42.506	2.011
	21	6-7-1-9-4-13-12	69.753	1.965
	22	1-3-4-7-9-13-17	42.506	1.932
	23	5-7-6-15-13-1-17	56.688	1.891
	24	6-7-1-9-4-13-12	56.688	2.075
	25	2-3-4-7-9-13-17	50.252	2.061
	26	6-1-7-8-4-13-17	42.506	2.088
	27	1-3-4-7-13-15-17	42.506	1.914
	28	1-3-7-9-13-4-17	42.506	1.943
	29	1-3-7-9-4-13-17	69.753	2.011
	30	1-3-4-7-9-13-17	42.506	1.906
	31	1-3-4-8-7-13-17	42.506	2.059
	32	6-7-5-1-9-13-17	42.506	1.858
	33	1-3-7-8-13-4-17	42.506	1.93
	34	1-3-4-7-15-13-17	42.506	2.005
	35	1-3-4-7-13-15-17	56.688	2.075
	36	1-3-4-7-17-13-15	50.252	2.021
	37	1-3-4-7-8-13-17	42.506	2.311
	38	1-3-4-7-17-13-15	69.753	2.059
	39	1-3-4-8-7-13-17	69.753	1.884
	40	1-3-7-8-13-4-17	42.506	2.016
	41	1-3-4-7-8-13-17	69.753	2.048
	42	5-7-6-1-9-13-17	42.506	1.957
	43	2-3-4-7-9-13-17	56.688	2.006
	44	1-4-3-7-13-15-17	42.506	1.98
	45	1-4-5-7-13-15-17	56.688	1.843
	46	2-3-4-7-9-13-17	57.801	1.876
	47	1-4-5-7-9-17-13	42.506	1.918
	48	6-1-7-8-13-4-17	42.506	1.884
	49	1-3-7-9-13-4-17	70.828	1.769
	50	1-3-4-7-13-15-17	42.506	2.013
		Mean	5.068	1.991
	Standard Deviation	1.038	0.104
	Confidence Interval 95%	[4.761 -5.374]	[1.961 -2.022]

TABLE IV :

 IV Power Loss computed with other algorithms.

	Algorithm	Power Loss (MW)
	Original Network (IEEE-14)	13.436
	PSO Algorithm	9.9159
	MPSO Algorithm	8.5053
	ABC Algorithm	6.4611
	FSS Algorithm	7.8457
	HATSGA	4.2796
	GSA Algorithm	3.2764