Acta Polytechnica CTU Proceedings doi:10.14311/APP.2018.15.0142 Acta Polytechnica CTU Proceedings 15:142–147, 2018 © Czech Technical University in Prague, 2018 available online at http://ojs.cvut.cz/ojs/index.php/app IMAGE SYNTHESIS OF METAL FOAM MICRO-STRUCTURE WITH THE USE OF WANG TILES Lukáš Zrůbeka,∗, Martin Doškářa, Anna Kučerováa, Marcela Meneses-Guzmánb, Francisco Rodríguez-Méndezc, Bruno Chinéc a Department of Mechanics, Faculty of Civil Engineering, Czech Technical University in Prague, Thákurova 7, 166 29 Prague 6, Czech Republic b School of Industrial Production Engineering, Costa Rica Institute of Technology, Cartago, Costa Rica c School of Materials Science and Engineering, Costa Rica Institute of Technology, Cartago, Costa Rica ∗ corresponding author: lukas.zrubek@fsv.cvut.cz Abstract. In this paper we present our recent work focused on the analysis of the abilities of Wang Tiles method and Automatic tile design method to synthesize the micro-structure of cellular materials, especially particular type of metal foam. Wang Tiles method stores and compress the micro-structure in a set of Wang Tiles and by the means of stochastic tiling algorithms the planar domain is reconstructed. The used tiles are created by the Automatic tile design method from respective number of small specimens extracted from the original micro-structure image. As an additional step the central areas of automatically designed tiles are patched to suppress the influence of repeating tile edges (and relevant tile quarters) on inducing artifacts. In the presented analysis the performance of raw and patched tiles of different sizes in conjunction of various tile sets is investigated. Keywords: Heterogeneous micro-structure, Wang tiles, synthesis, cellular materials, metal foam. 1. Introduction Detailed understanding and insight in the character- istic behaviour of real world processes are integral part to withstand the continuously increasing pres- sure to the ultimate materials performance. Usually the key information are hidden in details and there- fore the research attention is typically focused on the micro-structural level of materials. As the majority of materials is random and heterogeneous the appro- priate modelling techniques are required. (a) (b) (c) Figure 1. Periodic Unit Cell concept, a) heteroge- neous micro-structure with regular lattice, b) unit cell, c) reconstructed micro-structure. For simply heterogeneous materials with regular lattice (Fig. 1a) the common concept in multi-scale modelling called Periodic Unit Cell (PUC) can be used. This method compress the regular micro-structure into the single cell (Fig. 1b) corresponding to the representative volume element (RVE). By duplicating the PUC in cardinal directions, the original micro- structure is reconstructed (Fig. 1c). On the other hand, the Statistically Equivalent Pe- riodic Unit Cell (SEPUC) method can be used for het- erogeneous materials with random micro-structures. In this case the unit cell holds the same properties described by statistical descriptors as the original micro-structure [1]. Despite the utility of these methods (PUC or SEPUC) in cases like numerical homogenization [2] both apply the concept of single cell which leads to pe- riodic patterns in reconstructed domains. To preserve stochastic layout, other method is needed utilizing set of RVEs, such as Wang tiles method. Contrary to unit cell frameworks, the Wang tiles are capable to reproduce non-periodic micro-structural patterns. 2. Wang Tiles Method The Wang tiles method was first presented by logician and mathematician Hao Wang in 1961 [3, 4]. The method has a conformable concept as the classic game domino (Fig. 2a) or the jigsaw puzzle (Fig. 2b). It is modelled visually by square tiles with particular information (usually colour, but for purposes of this paper, colours are visualized as patterns) stored on each of the four edges (Fig. 2c). A group of these tiles is called set and copies of the tiles from set are placed side by side in cardinal directions, such as the edge information of two adjacent tiles are coincident. Rotating or mirroring the tiles is forbidden. 142 http://dx.doi.org/10.14311/APP.2018.15.0142 http://ojs.cvut.cz/ojs/index.php/app vol. 15/2018 Wang Tiles and Metal Foam Micro-structure Synthesis (a) (c) (b) Figure 2. Wang tiles concept, a) domino game, b) jig- saw puzzle, c) Wang tiles. One of the significant research topics based on the Wang tiles is aimed on discovery of a set with the smallest number of tiles, such that domain tiled with these tiles is aperiodic. During the years the number of tiles in smallest set was reduced from first set of 20 426 tiles discovered by R. Berger [5] to the latest findings by E. Jeandel [6] to 11 tiles. In our work we utilize tiles sets that are not ape- riodic by itself but enable creation of domain with stochastic layout of tiles. Such kind of sets are pre- sented by M. F. Cohen and his colleagues in [7] for generating stochastic graphic patterns. 2.1. Tiling algorithms The planar domain covered with copies of tiles from set is called tiling and when there are no missing pieces (i.e. holes) and all the touching edges of tiles are corresponding to each other, the tiling is valid. The process of laying down tile after tile to create the tiling is in row–column order. In other words the desired number of tiles is placed side by side horizontally from left to right followed by next row of tiles below the previous one. This inevitably leads to situation that tile will be placed in corner where its top edge (N as North) will have to correspond to the bottom edge (S as South) of tile above and its left edge (W as West) will have to correspond to the right edge (E as East) of the tile on the left. This is so-called NW (North–Western) corner position (see Fig. 3). ? N W (a) (b) Figure 3. Planar domain tiling, a) edge labels, b) North–Western corner position with two candidate tiles. To ensure the final tiling is not only valid but also stochastic the tiling algorithm presented in [7] and called by us CSHD (Cohen-Shade-Hiller-Deussen) has to be used. This algorithm defines simple rule, that for each NW position have to be at least two valid candidate tiles (Fig. 3b) from which single tile is ran- domly selected and placed in the corner position. This give quite strict requirements on the used tile sets - see Section 2.2. The random selection from two candidates can some- times lead to occurrence of groups of same tiles in tiling. The above described CSHD algorithm can be improved to prevent this grouping, by allowing to repeat the random selection, if the current selec- tion would lead to identical neighbouring tiles. The repetition is limited to k many attempts, so group- ing can still occur in the tiling. To distinguish the two algorithms in later text, we denote the one with improvement as modified CSHD [8]. 2.2. Tile sets As described in Section 2 groups of tiles are called sets. To differentiate between various sets the following labelling Wnt/nc i−nc i is used. Where W means Wang, nt indicates number of tiles in set and nc i denotes number of unique colours on horizontal edges (i = 1) and on vertical edges (i = 2) [9]. Tile set with nc i = 1 corresponds to W1/1-1 and the PUC (Section 1) which is the primary concept we are trying to substitute. The sequent choice is set for nc i = 2. All admis- sible unique combinations of tiles with two different horizontal and two different vertical edges are showed on Fig. 4a. Set of tiles that contain all combinations is called complete set and in this case it is labelled W16/2-2. W E N S 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 (a) (b) Figure 4. Wang tile set with nc i = 2, a) all possible combinations, i.e. complete set W16/2-2, b) mini- mal set W8/2-2 with particularly selected tiles for nNW = 2. The number of tiles in complete set is equal to ncs = (nc i · nc i )2 for(i) ∈ {1, 2}. (1) To comply with the requirements of CSHD algorithm (Section 2.1) the minimal number of tiles in set is equal to nt = nNW · √ ncs, (2) where nNW is the number of required candidate tiles in the NW position (2 ≤ nNW ≤ √ ncs). 143 L. Zrůbek, M. Doškář, A. Kučerová et al. Acta Polytechnica CTU Proceedings 2.3. Design of Tiles The tiles used in practical examples stick to the un- derlying schema of edge codes and sets depicted in previous section but the tiles must contain the real micro-structure. One of the methods to design tiles is the the multi- criteria optimization of tile morphology according to statistical descriptors [9]. Nevertheless this approach has extreme requirements on time and computational performance. Method that is used for purposes of this work is called Automatic Tile Design and its application can be found in [7]. The process is extensively described in [8] and therefore only brief explanation follows. The process starts by extracting randomly √ ncs many square samples with the edge size l from the orig- inal micro-structure (Fig. 5a). For the each tile from set the respective samples are arranged into rhombus such that they are overlapping by ω (Fig. 5b). Then the samples are stitched together by means of Image Quilting Algorithm (IQA) [10] which searches for path in the overlap ω with minimal square difference be- tween pixel values. Finally the square tile of size h is cut-out (Fig. 5c). 1 2 4 (a) (b) (c) 2 1 4 3 3 l ω h Figure 5. Automatic Tile Design, a) √ ncs many square samples with the edge size l, b) arranged sam- ples overlapping by ω, c) final cut-out tile created by IQA. As an enrichment for the Automatic tile design process, the central area of created tiles can be patched to suppress the influence of repeating tile edges (and relevant tile quarters) on inducing artifacts [8]. For each tile a unique patch is extracted from original micro-structure. This patch is placed over the centre of tile and by means of the same IQA glued in. For the purpose of following text the tiles created by the standard way are called raw and tiles with patch enrichment are denoted as patched. 3. Metal Foam The investigated cellular material is particular type of metal foam manufactured in Laboratorio Macchine Utensili e Sistemi di Produzione (MUSP), at Politec- nico di Milano, Italy and examined in the laboratories of the Institute of Technology in Costa Rica (ITCR). The manufacturing process is described in detail in [11] therefore only a brief description follows. 1 3 4 5 6 7 8 2 Figure 6. Photo image of the produced aluminum foam [11] cut into 8 samples designated for scan- ning (Fig. 7) and other experiments. 3.1. Manufacturing process The foam specimens were produced from the precursor composed of AlSi10 alloy mixed with a 0.80wt% of titanium hydride (TiH2) which was cut into cuboids of dimensions 2.0 × 4.0 × 16.5 cm. These were put in the steel mould with approximate internal dimen- sions 4.0× 16.5× 16.5 cm such as the largest faces are perpendicular to the direction of gravity. 0 10 20 30 [mm] 1 2 3 4 5 6 7 8 Figure 7. Binary scans of existent samples (Fig. 6) of aluminum foam [11]. The order of images corresponds to the order of subsequent cuts of larger piece. The mould was then situated in the laboratory con- vection oven and heated to start the expansion process. During that the temperature and heating rate was controlled until the value of 680° C was reached. The process ended when the titanium hydroxide (TiH2) re- leased the H2 gas into the molten alloy of AlSi10 + Ti and by regulated solidification process the aluminum foam was created. The outcome of the procedure is irregularly porous cellular metal, with a variable density throughout its volume. 4. Image synthesis The reconstruction of material micro-structure starts with the original micro-structure scan. As eight differ- ent scans (image size 7000× 14 000 px) were available 144 vol. 15/2018 Wang Tiles and Metal Foam Micro-structure Synthesis a simple comparison of them was performed. Each scan was subjected to image analysis when all the pores and their area were measured. From the ob- tained data we created a histogram showing the counts of pores according to their area in all eight samples (Fig. 8). From this perspective all the samples can be considered as equally suitable for further use as the distributions are almost identical. Therefore for further use only the sample 1 (Fig. 6 and Fig. 7) was chosen. Figure 8. Histogram showing the counts of different size pores in the original samples (Fig. 7). 4.1. Data As outlined in previous reading, for creating the syn- thesized micro-structure many different configurations can be used. To cover most of the options the micro- structures with further described settings were created (Table 1). Raw and patched tiles (Section. 2.3) with two different sizes h and five different overlaps ω were created for each one of three used set types (Sec- tion. 2.2). The overlap sizes were set to h 10 , 2h 10 , 4h 10 , 8h 10 and h. Therefore for each set type was obtained 10 sets of raw tiles and 10 sets of patched tiles, in total 60 different tile sets. Set Tile size h [px] Overlap ω [px] W8/2-2 1000 100 200 400 800 1000 2000 200 400 800 1600 2000 W16/2-2 1000 100 200 400 800 1000 2000 200 400 800 1600 2000 W18/3-3 1000 100 200 400 800 1000 2000 200 400 800 1600 2000 Table 1. Preview of used combinations of settings. Every single one of created tile set was used to syn- thesize 5 domains using the standard CSHD algorithm and 5 domains with use of the modified CSHD algo- rithm (number of repetitions k = 5) (Section. 2.1). As a result, we obtained 600 synthesized micro-structures (image size 7000× 14 000 px) in groups of five, where each group has different settings. 4.2. Results Because of the large amount of obtained outputs the micro-structures were analyzed at first only visually to eliminate clearly faulty results and by exclusion method get to the best results. 7 4 8 7 3 2 5 4 6 6 7 4 8 5 2 6 7 2 8 8 8 6 6 6 5 1 3 3 3 1 2 8 8 8 8 5 1 2 7 2 8 8 3 2 8 8 7 3 4 7 1 4 5 3 4 7 7 4 8 7 1 3 1 1 1 2 7 4 5 2 2 6 7 1 2 8 5 2 5 4 6 5 4 8 8 6 5 1 3 4 8 8 7 2 5 3 1 4 Table 2. Tiling map generated by the original CSHD algorithm with highlighted groups of same tiles. As first we compared the original CSHD and mod- ified CSHD algorithms. The Table 2 shows the un- derlying tiling map with highlighted unwanted groups of same tiles. Tiling map generated by means of the modified CSHD algorithm is presented for comparison in the Table 3. The further described phenomena can be observed in almost all reconstructed domains, hence all further presented results are those that used the modified CSHD algorithm. 1 2 8 7 4 8 6 5 4 8 7 3 4 8 6 8 7 1 2 7 2 7 2 7 2 7 1 3 1 3 1 2 7 2 8 5 4 5 3 1 2 8 2 8 5 3 2 7 3 4 6 7 4 6 8 7 8 7 3 4 7 1 4 5 2 6 5 1 3 1 7 2 7 2 6 5 1 3 4 5 3 2 7 2 5 4 5 4 5 4 5 4 5 3 4 7 1 3 Table 3. Tiling map generated by the modified CSHD algorithm. Another finding that can be stated from the visual observation is that the tile size of 1000px seems not sufficient for raw tiles. The tiles contain opened and very damaged pores (Fig. 9) from the quilting process and the synthesized micro-structure is very unlike the original (Fig. 10). Figure 9. Wang tile set W8/2-2, tile size h = 1000 px, overlap ω = 100 px, raw tiles. The increasing value of overlap ω improves the results as the quilting algorithm is able to find superior paths. However, if compared with tiles of size 2000 px the better visual appearance of bigger tiles is clear. In subsequent results the tiles of size 2000px and with higher values of overlaps are used. 145 L. Zrůbek, M. Doškář, A. Kučerová et al. Acta Polytechnica CTU Proceedings Figure 10. Synthesized domain utilizing the modified CSHD algorithm and tiles from Fig. 9) with underlying tiling map from Table 3. Next, we compared the raw and patched tiles. As previously stated in [8] the repeating tile edges and especially the relevant tile quarters induces repeating artifacts in the reconstructed domain. The repeated tile quarters can be seen in Fig. 11a. This can be par- tially avoided by usage of the patched tiles (Fig. 11b). a) b) Figure 11. Wang tile set W8/2-2, tile size h = 2000px, overlap ω = 200px, a) raw tiles, b) patched tiles. Because each tile contains unique patch the only repeated artifacts in the domain are exactly these patches. Frequency of these artifacts can be even more decreased by means of larger sets. Therefore, the patched tiles should be the preferred choice. Figure 12. Histogram showing the counts of different size of pores in the original scan and in the synthesized samples for three different sets W8/2-2, W16/2-2 and W18/3-3. Although the visual observation can be quite sub- jective, we managed to withdraw the presumably best setting (from the analyzed range of options) to obtain the best results. In the following we compare the orig- inal scan 1 with synthesized domains using the tile size 2000px, overlap 2000px, patched tiles, modified CSHD algorithm and three different tile sets W8/2-2, W16/2-2 and W18/3-3 (Fig. 12). As shown in the figure the distribution of pores in synthesized domains and the original scan are almost equal. Three selected examples of synthesized domains for different tile sets are presented in Fig. 13. a) b) c) Figure 13. Examples of synthesized domains by means of tile sets, a) W8/2-2, b) W16/2-2 and c) W18/3-3. 5. Conclusion The above presented approach and results show a few limitations for reconstructing the micro-structure of aluminum foam by the means of Wang tiles (Section 2) and Automatic tile design (Section 2.3) . Firstly, because of the manufacturing process and the influence of gravity force the character of the alu- minum micro-structure is progressively changing along the direction of the gravity. As the H2 gas is released in the molten mixture it tends to rise up and thus larger pores are created at the surface while at the bottom the foam density is much higher (Fig. 7). This fluctuating layout cannot be achieved by the Wang 146 vol. 15/2018 Wang Tiles and Metal Foam Micro-structure Synthesis tiles as the tiles are selected randomly (Section 2.1) and the density of synthesized micro-structure is ap- proximately equal in all directions. Secondly, the Automatic tile design utilize the Im- age quilting algorithm for creating the tiles samples of the original micro-structure. This algorithm works quite well for mono-disperse media [8] but for media with high porosity like foams the quilting path search sometimes hit the borders of the overlap and visible errors like unclosed pores or completely unconnected pieces may occur. This could be improved by uti- lizing the max-flow or in other words min-cut [12] graph cutting method and enhanced by additional enrichments [13]. However, quite satisfying results can be obtained (Fig. 13) when the modified CSHD algorithm and patched, sufficiently large tiles with a relevant overlap are used. Furthermore, the visually noticeable repeti- tions can be decreased by means of larger sets with more edge variety. Acknowledgements The authors gratefully acknowledge the financial support from the Grant Agency of the Czech Technical Univer- sity in Prague, the grant No. SGS18/036/OHK1/1T/11 (Modelling Heterogeneous Materials and Identification of Parameters of Macroscopic Material Models) (L. Zrůbek, M. Doškář and A. Kučerová). Authors would also like to thank for the support from Vicerrectoría de Investigación y Extensión, project No. 1351022 (Application of Non- destructive Techniques for Control of Properties of Porous and Cellular Materials) (L. Zrůbek, M. Meneses-Guzmán, F. Rodríguez-Méndez and B. Chiné-Polito). References [1] H. Lee, M. Brandyberry, A. Tudor, K. Matouš. Three-dimensional reconstruction of statistically optimal unit cells of polydisperse particulate composites from microtomography. Phys Rev E 80:061301, 2009. doi:10.1103/PhysRevE.80.061301. [2] F. Fritzen. Microstructural modeling and computational homogenization of the physically linear and nonlinear constitutive behavior of micro-heterogeneous materials, vol. 1. KIT Scientific Publishing, 2011. [3] H. Wang. Proving theorems by pattern recognition–II. Bell System Technical Journal 40(1):1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x. [4] H. Wang. Games, logic and computers. Scientific American 213(5):98–106, 1965. [5] R. Berger. The undecidability of the domino problem. 66. American Mathematical Soc., 1966. doi:10.1090/memo/0066. [6] E. Jeandel, M. Rao. An aperiodic set of 11 wang tiles. arXiv preprint arXiv:150606492 2015. [7] M. F. Cohen, J. Shade, S. Hiller, O. Deussen. Wang tiles for image and texture generation. ACM Trans Graph 22(3):287–294, 2003. doi:10.1145/882262.882265. [8] M. Doškář, J. Novák, J. Zeman. Aperiodic compression and reconstruction of real-world material systems based on wang tiles. Phys Rev E 90:062118, 2014. doi:10.1103/PhysRevE.90.062118. [9] J. Novák, A. Kučerová, J. Zeman. Compressing random microstructures via stochastic wang tilings. Phys Rev E 86:040–104, 2012. doi:10.1103/PhysRevE.86.040104. [10] A. A. Efros, W. T. Freeman. Image quilting for texture synthesis and transfer. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’01, pp. 341–346. ACM, New York, NY, USA, 2001. doi:10.1145/383259.383296. [11] B. Chiné, M. Meneses-Guzmán, F. Rodríguez- Méndez. Characterization of aluminium foams produced via a powder metallurgy route. In Proceedings of the 1st Iberic Conference on Theoretical and Experimental Mechanics and Materials / 11th National Congress on Experimental Mechanics. INEGI/FEUP (2017), Porto, Portugal, 2018. Accepted for publishing. [12] Y. Boykov, O. Veksler, R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on pattern analysis and machine intelligence 23(11):1222–1239, 2001. doi:10.1109/34.969114. [13] V. Kwatra, A. Schödl, I. Essa, et al. Graphcut textures: image and video synthesis using graph cuts. ACM Transactions on Graphics (ToG) 22(3):277–286, 2003. doi:10.1145/1201775.882264. 147 http://dx.doi.org/10.1103/PhysRevE.80.061301 http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x http://dx.doi.org/10.1090/memo/0066 http://dx.doi.org/10.1145/882262.882265 http://dx.doi.org/10.1103/PhysRevE.90.062118 http://dx.doi.org/10.1103/PhysRevE.86.040104 http://dx.doi.org/10.1145/383259.383296 http://dx.doi.org/10.1109/34.969114 http://dx.doi.org/10.1145/1201775.882264 Acta Polytechnica CTU Proceedings 15:142–147, 2018 1 Introduction 2 Wang Tiles Method 2.1 Tiling algorithms 2.2 Tile sets 2.3 Design of Tiles 3 Metal Foam 3.1 Manufacturing process 4 Image synthesis 4.1 Data 4.2 Results 5 Conclusion Acknowledgements References