Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T16:35:57.527Z Has data issue: false hasContentIssue false
  • English
  • Français

Application of the Maximum Flow–Minimum Cut Algorithm to Segmentation and Clustering of Materials Datasets

Published online by Cambridge University Press:  18 June 2019

Alexander F. Brust ,
Eric J. Payton ,
Toren J. Hobbs  and
Stephen R. Niezgoda
Alexander F. Brust
Affiliation:
Department of Materials Science and Engineering, The Ohio State University, Columbus, OH 43210, USA
Eric J. Payton
Affiliation:
Air Force Research Laboratory, Materials and Manufacturing Directorate, Dayton, OH 45433, USA
Toren J. Hobbs
Affiliation:
Department of Materials Science and Engineering, The Ohio State University, Columbus, OH 43210, USA
Stephen R. Niezgoda*
Affiliation:
Department of Materials Science and Engineering, The Ohio State University, Columbus, OH 43210, USA Department of Mechanical and Aerospace Engineering, The Ohio State University, Columbus, OH 43210, USA
*
*Author for correspondence: Stephen R. Niezgoda, E-mail: [email protected]
Get access

Abstract

Problems involving image segmentation, atomic cluster identification, segmentation of microstructure constituents in images and austenite reconstruction have seen various approaches attempt to solve them with mixed results. No single computational technique has been able to effectively tackle these problems due to the vast differences between them. We propose the application of graph cutting as a versatile technique that can provide solutions to numerous materials data analysis problems. This can be attributed to its configuration flexibility coupled with the ability to handle noisy experimental data. Implementation of a Bayesian statistical approach allows for the prior information, based on experimental results and already ingrained within nodes, to drive the expected solutions. This way, nodes within the graph can be grouped together with similar, neighboring nodes that are then assigned to a specific system with respect to calculated likelihoods. Associating probabilities with potential solutions and states of the system allows for quantitative, stochastic analysis. The promising, robust results for each problem indicate the potential usefulness of the technique so long as a network of nodes can be effectively established within the model system.

Keywords

atomic clusteringBayesian statisticsgraph cuttingsegmentation
Type
Software and Instrumentation
Information
Microscopy and Microanalysis , Volume 25 , Issue 4 , August 2019 , pp. 924 - 941
Copyright
Copyright © Microscopy Society of America 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abbasi, M, Nelson, T, Sorensen, C & Wei, L (2012). An approach to prior austenite reconstruction. Mater Charact 66, 1–8.Google Scholar
Artan, Y (2011). Interactive Image Segmentation Using Machine Learning Techniques, 2011 Canadian Conference on Computer and Robot Vision, 264–269.Google Scholar
Bachmann, F, Hielscher, R & Schaeben, H (2010). Inferential statistics of electron backscatter diffraction data from within individual crystalline grains. J Appli Crys 43, 1338–1355.Google Scholar
Bae, E, Shi, J & Tai, X (2011). Graph cuts for curvature based image denoising. IEEE Trans Image Process 20, 1199–1210.Google Scholar
Banerji, S, McMahonCJ, J CJ, J & Feng, H (1978). Intergranular fracture in 4340-type steels: Effects of impurities and hydrogen. Metall Trans A 9A, 237–247.10.1007/BF02646706Google Scholar
Beheshti, M, Faichney, J & Gharipour, A (2015). Bio-Cell Image Segmentation using Bayes Graph-Cut Model.Google Scholar
Bernier, N, Bracke, L, Malet, L & Godet, S (2014). An alternative to the crystallographic reconstruction of austenite in steels. Mater Charact 89, 23–32.10.1016/j.matchar.2013.12.014Google Scholar
Bovik, A (2000). Handbook of Image and Video Processing. New York: Academic.Google Scholar
Boykov, Y & Kolmogorov, V (2004). An experimental comparison of Min-Cut/Max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal Mach Intell (PAMI) 26, 1124–1137.Google Scholar
Boykov, Y & Veksler, O (2006). Graph Cuts in Vision and Graphics: Theories and Applications, In Paragios, N, Chen, Y & Faugeras, O (eds), Handbook of Mathematical Models in Computer Vision. Boston, MA: Springer.Google Scholar
Brust, A, Niezgoda, S, Yardley, V & Payton, E (2019). Analysis of misorientation relationships between austenite parents and twins. Metall Mater Trans A 50, 837–855.Google Scholar
Campbell, A, Murray, P, Yakushina, E, Marshall, S & Ion, W (2018). New methods for automatic quantification of microstructural features using digital image processing. Mater Des 141, 395–406.Google Scholar
Cayron, C (2007). ARPGE: A computer program to automatically reconstruct the parent grains from electron backscatter diffraction data. J Appl Crystallogr 40, 1183–1188.Google Scholar
Chan, R, Ho, C & Nikolova, M (2005). Salt-and-pepper noise removal by median-type noise detectors and detail-preserving regularization. IEEE Trans Image Process 14, 1479–1485.10.1109/TIP.2005.852196Google Scholar
Chuang, H & Comer, M (2010). A New Method for Segmentation of Noisy, Low-Contrast Image Sequences. Processions on IEEE International Conference on Circuits and Systems.Google Scholar
Cluff, S, Nelso, T, Song, R & Fullwood, D (2018). Crystallographic reconstruction of parent austenite twin boundaries in a lath martensitic steel. Int Conf Ser: Mat Sci Eng 375, 1–11.Google Scholar
Comer, M & Delp, E (1994). Parameter Estimation and Segmentation of Noisy or Textured Images Using the EM Algorithm and MPM Estimation. IEEE International Conference on Image Processing, 650–654.Google Scholar
Comer, M & Delp, E (2000). The EM/MPM algorithm for segmentation of textured images: Analysis and further experimental results. IEEE Trans Image Process 9, 1731–1744.Google Scholar
Cook, WJ, Cunningham, WH, Pulleyblank, WR & Schriver, A (1998). Combinatorial Optimization. New York: John Wiley & Sons.Google Scholar
Davies, R (1978). Influence of martensite composition and content on the properties of dual phase steels. Metall Trans A 9, 671–679.Google Scholar
Despotović, I, Jelač, V, Vansteenkiste, E & Philips, W. (2010). Noise-Robust method for image segmentation. International Conference on Advanced Concepts for Intelligent Vision Systems, Springer, Berlin, Heidelberg, Dec 13, 2010. pp. 153–162.Google Scholar
Duval, L, Moreaud, M, Couprie, C, Jeulin, D, Talbot, H & Angulo, J (2014). Image processing for materials characterization: Issues, challenges and opportunities, 2014. IEEE International Conference on Image Processing (ICIP), 4862–4866.10.1109/ICIP.2014.7025985Google Scholar
El-Bagoury, N & Mohsen, Q (2011). Gamma prime and TCP phases and mechanical properties of thermally exposed nickel-base superalloy. Phase Transitions 84, 1108–1122.Google Scholar
Faessel, M & Jeulin, D (2010). Segmentation of 3D microtomographic images of granular materials with the stochastic watershed. J Microsc 239, 17–31.Google Scholar
Felfer, P, Ceguerra, A, Ringer, S & Cairney, J (2015). Detecting and extracting clusters in atom probe data: A simple, automated method using voronoi cells. Ultramicroscopy 150, 30–36.Google Scholar
Ford, L & Fulkerson, D (1962). Flows in Networks. Princeton, NJ: Princeton University Press.Google Scholar
Girault, E, Jacquest, P, Harlet, P, Mols, K, Humbeeck, JV, Aernoudt, E & Delannay, F (1998). Metallographic methods for revealing the multiphase microstructure of TRIP-assisted steels. Mater Charact 40, 111–118.Google Scholar
Gnäupel-Herold, T & Creuziger, A (2011). Diffraction study of the retained austenite content in TRIP steels. Mater Sci Eng: A 528, 3594–3600.Google Scholar
Goldberg, A & Tarjan, R (1988). A new approach to the maximum-flow problem. J Assoc Comp Mach 35, 921–940.Google Scholar
Greig, D, Porteous, B & Seheult, A (1989). Exact Maximum A posteriori estimation for binary images. J Roy Stats Soc 51, 271–279.Google Scholar
Greninger, AB & Troiano, AR (1949). The mechanism of martensite formation. Metals Transactions 185, 590–598.Google Scholar
Hata, K, Wakita, M, Fujiwara, K & Kawano, K (2017). Development of a Re-construction method of prior austenite microstructure using EBSD data of martensite. Nippon Steel and Sumitomo Metal Technical Report 114, 26–31.Google Scholar
Heimann, T & Meinzer, H (2009). Statistical shape models for 3D medical image segmentation: A review. Med Image Anal 13, 543–563.Google Scholar
Hong, S & Yu, J (1989). Effect of prior austenite grain size on creep properties and on creep crack growth in 3.5-Ni-Cr-Mo-V steel. Scr Mater 23, 1057–1062.Google Scholar
Horn, R & Ritchie, R (1978). Mechanisms of tempered martensite embrittlement of low alloy steels. Metall Trans A 9A, 1039–1053.Google Scholar
Hutchinson, B, Ryde, L, Lindh, E & Tagashira, K (1998). Texture in hot rolled austenite and resulting transformation products. Mater Sci Eng A 257, 9–17.Google Scholar
Hyde, J & English, C (2000). An Analysis of the Structure of Irradiation Induced Cu-Enriched Clusters in Low and High Nickel Welds. Symposium of Microstructural Processes in Irradiated Materials, 27–30.Google Scholar
Imre, E, Guillemaut, JY & Hilton, A (2010). Moving Camera Registration for Multiple Camera Setups in Dynamic Scenes. Proceedings of the British Machine Vision Conference, 38.1–38.12, BMVA Press.Google Scholar
Iyer, G, Chanussot, J & Bertozzi, A (2017). A graph-based approach for feature extraction and segmentation of multimodal images, 2017. IEEE International Conference on Image Processing (ICIP), 3320–3324.Google Scholar
Johansen, T (1997). On Tikhonov regularization, bias and variance in nonlinear system identification. Automatica 33, 441–446.Google Scholar
Kang, J, Kim, D, Baik, S, Ahn, T, Kim, Y, Han, H, Oh, K, Lee, H & Han, S (2011). Phase analysis of steels by grain-averaged EBSD functions. Iron Steel Inst Japan Int 51, 130–136.Google Scholar
Keller, R, Roshko, A, Geiss, R, Bertness, K & Quinn, T (2004). EBSD measurement of strains in GaAs due to oxidation of buried AlGaAs layers. Microelectron Eng 75, 96–102.Google Scholar
Kelly, P, Jostons, A & Blake, R (1990). The orientation relationship between lath martensite and austenite in low carbon, low alloy steels. Acta Metall Mater 38, 1075–1081.Google Scholar
Kimura, K, Ohi, N, Shimazu, K & Matsuo, T (1987). Effect of prior austenite grain size on high temperature creep properties of Cr-Mo-V rotor steel. Scr Mater 21, 19–22.Google Scholar
Kitahara, H, Ueji, R, Tsuji, N & Minamino, Y (2006). Crystallographic features of lath martensite in low-carbon steel. Acta Mater 54, 1279–1288.Google Scholar
Kurdjumow, G & Sachs, G (1930). Ü ber der Mechanismus der Stahlhärtung (On the mechanism of hardening of steel). Z Physik 64, 325–343.Google Scholar
LaPera, F (1978). Improved etching technique for the determination of percent martensite in high-strength, dual-phase steels. Metallography 12, 263–268.Google Scholar
Lee, C & Han, J (2013). Learning Markov Random Field Image Prior for Pixelation Removal of Fiber Microscopy Using Sparse Coding Based on Bayesian Framework. International Winter Workshop on Brain-Computed Interface (BCI).Google Scholar
Leskó, M, Kato, Z & Nagy, A (2010). Live Cell Segmentation in Fluorescence Microscopy via Graph Cut, 1485–1488.Google Scholar
Lloyd, S (1982). Least squares quantization in PCM. IEEE Trans Inf Theory 28, 129–137.Google Scholar
MacSleyne, J, Uchic, M, Simmons, J & Graef, MD (2009). Three-dimensional analysis of secondary γ' precipitates in René-88 DT and UMF-20 superalloys. Acta Mater 57, 6251–6267.Google Scholar
Marroquin, J, Mitter, S & Poggio, T (1987). Probabilistic solution of Ill-posed problems in computational vision. J Am Stats Assoc 82, 76–89.Google Scholar
McInerney, T & Terzopoulos, D (1999). Topology adaptive deformable surfaces for medical image volume segmentation. IEEE Trans Med Imaging 18, 840–850.Google Scholar
Mondal, P, Vicidomini, G & Diaspro, A (2007). Markov random field aided Bayesian approach for image reconstruction in confocal microscopy. J Appl Phys 102, 044701.Google Scholar
Morito, S, Tanaka, H, Konishi, R & Maki, T (2003). The morphology and crystallography of lath martensite in Fe-C alloys. Acta Mater 51, 1789–1799.Google Scholar
Neubauer, A (1989). Tikhonov regularisation for non-linear ill-posed problems: Optimal convergence rates and finite-dimensional approximation. Inverse Prob 5, 541–557.Google Scholar
Otsu, N (1979). A threshold selection method from gray-level histograms. IEEE Trans Syst 9, 62–66.Google Scholar
Payton, E, Aghajani, A, Otto, F, Eggler, G & Yardley, V (2012). On the nature of internal interfaces in a tempered martensite ferritic steel and their evolution during long-term creep. Scr Mater 66, 1045–1048.Google Scholar
Payton, EJ & Nolze, G (2013). The backscatter electron signal as an additional tool for phase segmentation in EBSD. Microsc Microanal 19, 929–941.Google Scholar
Payton, EJ, Phillips, PJ & Mills, MJ (2010). Semi-automated characterization of the gamma prime phase in Ni-based superalloys via high-resolution backscatter imaging. Mater Sci Eng A 527, 2684–2694.Google Scholar
Payton, EJ, Phillips, PJ & Mills, MJ (2011). Stereology of backscatter electron images of etched surfaces for characterization of particle size distributions and volume fractions: Estimation of imaging bias Via monte carlo simulations. Mater Charact 62, 563–574.Google Scholar
Petrov, R, Kestens, L, Wasilkowska, A & Houbaert, Y (2007). Microstructure and texture of a lightly deformed TRIP-assisted steel characterized by means of the EBSD technique. Mater Sci Eng A 447, 285–297.Google Scholar
Poggio, T, Voorhees, H & Yuille, A (1988). A regularized solution to edge detection. J Complex 4, 106–123.Google Scholar
Preethi, S & Narmadha, D (2012). A survey on image denoising techniques. Int J Comput Appl 58, 27–30.Google Scholar
Ramírez, A, Porcayo-Calderon, J, Mazur, Z, Salinas-Bravo, V & Martinez-Gomez, L (2016). Microstructural changes during high temperature service of a cobalt-based superalloy first stage nozzle. Adv Mater Sci Eng 2016, 1–7.Google Scholar
Rodríguez, P (2013). Total variation regularization algorithms for images corrupted with different noise models: A review. J Elect Comput Eng 2013, 1–18.Google Scholar
Sandvik, B & Wayman, C (1983). Characteristics of lath martensite: Part 1. Crystallographic and substructural features. Metallurgical Transactions: A 14A, 809–822.Google Scholar
Shibata, A, Morito, S, Furuhara, T & Maki, T (2009). Substructures of lenticular martensites with different martensite start temperatures in ferrous alloys. Acta Mater 57, 483–492.Google Scholar
Shigeta, H, Mashita, T, Kaneko, T, Kikuta, J, Senoo, S, Takemura, H, Matsuda, H & Ishii, M (2014). A Graph Cuts Image Segmentation Method for Quantifying Barrier Permeation in Bone Tissue, 16–19.Google Scholar
Shinozaki, T, Nakanishi, T, Suzuki, K & Miura, H (2016). Measurement of the strength of a grain boundary in electroplated copper thin-film interconnections by using micro tensile-test, 2016. IEEE 37th International Electronics Manufacturing Technology (IEMT) 18th Electronics Materials and Packaging (EMAP) Conference, 1–5.Google Scholar
Simmons, J, Chuang, P, Comer, M, Spowart, J, Uchic, M & Graef, M (2009). Application and further development of advanced image processing algorithms for automated analysis of serial section image data. Mod Sim Mat Sci Eng 17, 1–22.Google Scholar
Soni, M, Khare, A & Jain, S (2014). Problem of denoising in digital image processing and its solving techniques. Int J Emerging Technol Adv Eng 4, 244–250.Google Scholar
Sosa, JM, Huber, DE, Welk, B & Fraser, HL (2014). Development and application of MIPART m : A novel software package for Two- and three-dimensional microstructural characterization. Integrating Mat Manuf Innovation 3, 10.Google Scholar
Soubies, E, Weiss, P & Descombes, X (2015). Graph Cut Based Segmentation of Predefined Shapes: Applications to Biological Imaging, In Fred A & De Marsico M (eds), Pattern Recognition Applications and Methods. Advances in Intelligent Systems and Computing, vol 318. Cham, Switzerland: Springer International Publishing. pp. 153–170.Google Scholar
Stephenson, L, Moody, M, Liddicoat, P & Ringer, S (2007). New techniques for the analysis of fine-scaled clustering phenomena within atom probe tomography (APT). Microstruct Microanal 13, 448–463.Google Scholar
Tan, W (2017). Investigations of phase transformations in AISI 5160 steel and partially stabilized zirconia via electron backscatter diffraction based techniques. PhD Thesis. Alfred University.Google Scholar
Tan, W, Lipke, D, Dziaszyk, S & Payton, E (2018). On Quantitatively Identifying Different Constituents in Multicomponent Steel Microstructures in EBSD, Manuscript submitted for publication.Google Scholar
Tibshirani, R (1996). Regression shrinkage and selection via the LASSO. J R Statistical Soc Ser B (Methodological) 58, 267–288.Google Scholar
Tolba, A & Raafat, H (2015). Multiscale image quality measures for defect detection in thin films. Int J Adv Manuf Technol 79, 113–122.Google Scholar
Torre, V & Poggio, TA (1986). On Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8, 147–163.Google Scholar
Uchic, M & MacSleyne, J (2006). Ground Truth Segmentation Image, http://www.bluequartz.net/binaries/Data/Rene88DT-GT.zip, [Online; accessed 08-August-2018].Google Scholar
Veksler, O (2003). Extracting dense features for visual correspondence with graph cuts, 2003. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings, vol. 1, I689–I694.Google Scholar
Waggoner, J, Zhou, Y, Simmons, J, Graef, MD & Wang, S (2013). 3D materials image segmentation by 2D propagation: A graph-Cut approach considering homomorphism. IEEE Trans Image Process 22, 5282–5293.Google Scholar
Waggoner, J, Zhou, Y, Simmons, J, Graef, MD & Wang, S (2014). Graph-Cut based interactive segmentation of 3D materials-science images. Mach Vis Appl 25, 1615–1629.Google Scholar
Wayman, C (1975). Shear transformations and microstructure. Metallography 8, 105–130.Google Scholar
Wills, J, Agarwal, S & Belongie, S (2003). What went where [motion segmentation], Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, vol. 1, I–I, IEEE.Google Scholar
Wright, S, Nowell, M & Fields, D (2011). A review of strain analysis using electron backscatter diffraction. Microsc Microanal 17, 316–329.Google Scholar
Wu, J, Wray, P, Garcia, C, Hua, M & DeArdo, A (2005). Image quality analysis: A new method of characterizing microstructures. ISIJ Int 45, 254–262.Google Scholar
Yardley, V, Fahimi, S & Payton, E (2015). Classification of creep crack and cavitation sites in tempered martensite ferritic steel microstructures. Mater Sci Technol 31, 547–553.Google Scholar
Yardley, V, Payton, E, Matsuzaki, T, Sugiura, R Jr., Tsurekawa, AY, S & Hasegawa, Y (2012). EBSD analysis of creep cracking in a 12 wt.% Cr tempered martensite ferritic steel. Proceedings of the 12th international conference on creep and fracture of engineering materials and structures, Kyoto, Japan.Google Scholar
Zaefferer, S, Romano, P & Friedel, F (2008). EBSD as a tool to identify and quantify bainite and ferrite in low-alloyed Al-TRIP steels. J Microsc 230, 499–508.Google Scholar
Zelenty, J, Dahl, A, Hyde, J, Smith, G & Moody, M (2017). Detecting clusters in atom probe data with Gaussian mixture models. Microstruct Microanal 23, 269–278.Google Scholar
Zhang, J, Modestino, W & Langan, D (1994). Maximum-Likelihood parameter estimation for unsupervised stochastic model-based image segmentation. IEEE Trans. Image Process 3, 404–420.Google Scholar
Zhu, Y, Wang, A & Ma, J (2013). Two-Phase image segmentation with the competitive learning based chan-vese (CLCV) model. In Intelligent Computing Theories, Huang, D, Bevilacqua, V, Figueroa, J & Premaratne, P (Eds.), pp. 183–191. Berlin, Heidelberg: Springer Berlin Heidelberg.Google Scholar