Image Anal Stereol 2018;37:55-62 doi:10.5566/ias.1708 Original Research Paper A SHAPE-CONTEXT MODEL FOR MATCHING PLACENTAL CHORIONIC SURFACE VASCULAR NETWORKS ELIN FARNELLB,1, SHAWN FARNELL2, JEN-MEI CHANG3, MADISON HOFFMAN4, ROBIN BELTON5, KATHRYN KEATY6, SANFORD LEDERMAN6 AND CAROLYN SALAFIA7 1Department of Mathematics, Colorado State University, 1874 Campus Delivery, Fort Collins, CO 80523; 2Plasma Controls, 1320 C/D Engineering Research Center, Fort Collins, CO 80523; 3Department of Mathematics and Statistics, California State University, Long Beach, 1250 Bellflower Blvd, Long Beach, CA, 90840-1001; 4Department of Mathematics and Statistics, Kenyon College, 201 N College Rd, Gambier, OH 43022; 5Department of Mathematical Sciences, Montana State University, Bozeman, MT 59717; 6New York Methodist Hospital, 506 Sixth Street Brooklyn, New York 11215; 7Placental Analytics, LLC, 187 Overlook Circle, New Rochelle, NY 10804 e-mail: elinfarnell@gmail.com, shawncfarnell@gmail.com, jen-mei.chang@csulb.edu, madisonchoffman@gmail.com, robin.belton@montana.edu, katkeaty@gmail.com, sal9047@nyp.org, carolyn.salafia@gmail.com (Received February 10, 2017; revised October 4, 2017; accepted November 20, 2017) ABSTRACT Placental chorionic surface vascular networks (PCSVNs) are essential high-capacitance, low-resistance distribution and drainage networks, and are hence important to placental function and to fetal and newborn health. It was hypothesized that variations in the PCSVN structure may reflect both the overall effects of genetic and environmentally regulated variations in branching morphogenesis within the conceptus and the fetus’s vital organs. A critical step in PCSVN analysis is the extraction of blood vessel structure, which has only been done manually through a laborious process, making studies in large cohorts and applications in clinical settings nearly impossible. The large variation in the shape, color, and texture of the placenta presents significant challenges to both machine and human to accurately extract PCSVNs. To increase the visibility of the vessels, colored paint can be injected into the vascular networks of placentas, allowing PCSVNs to be manually traced with a high level of accuracy. This paper provides a proof-of-concept study to explain the geometric differences between manual tracings of paint-injected and un-manipulated PCSVNs under the framework of a shape-context model. Under this framework, paint-injected and un-manipulated tracings of PCSVNs can be matched with nearly 100% accuracy. The implication of our results is that the manual tracing protocol yields faithful PCSVN representations modulo a set of affine transformations, making manual tracing a reliable method for studying PCSVNs. Our work provides assurance to a new pre-processing approach for studying vascular networks by ways of dye-injection in medical imaging problems. Keywords: altered geometry, paint-injection, placenta, shape matching, tracing. INTRODUCTION Altered patterns of angiogenesis with resultant variation in mature vascular network structures have been correlated with functional alterations in many species and many viscera including lung (Makanya et al., 2007; Hu et al., 2011), kidney (Carev et al., 2008), pancreas (Saldeen et al., 2006) and the angiogenesis that results in neurogenesis (Vasudevan and Bhide, 2008; Vasudevan et al., 2008). Related gene families control branching morphogenesis in these “permanent” viscera (Davies, 2002) and in the placenta, a “temporary” fetal organ that is separated from the baby at birth. The placenta is an ideal organ to study fetal angiogenesis because its branching villous growth is driven by angiogenesis. Abnormal placental angiogenesis underlies a number of pregnancy complications, from preeclampsia to fetal growth restriction and pre-term birth (Herr et al., 2009; Leach et al., 2009; Barut et al., 2010). Recent research has also demonstrated connections between placental features to the health and development of newborn babies (Yampolsky et al., 2009; Chang et al., 2012; Kaneti et al., 2013; Salafia et al., 2010; 2013b). For example, placental chorionic surface shapes and vascular networks features (e.g., mean vessel thickness, mean vessel tortuosity, and number of branch points) have been linked to immediate neonatal outcomes such as birth weight after adjustment for gestational length (Yampolsky et al., 2009; Chang et al., 2012) and risk for Autism Spectrum Disorder (ASD; Salafia et al., 2012; 2013a; Shah et al., 2016; Chang et al., 2016). In particular, PCSVNs associated with placentas of high-risk ASD pregnancies generally 55 FARNELL E ET AL: Placental chorionic surface vascular networks had fewer branch points, thicker and less tortuous vessels, better extension to the surface boundary, and smaller branch angles than their population-based counterparts (Chang et al., 2017). Currently, it is difficult to conduct placenta studies in large cohorts due to the difficulty in reliably extracting PCSVN features from images of the placenta. The challenges are rooted in the nature of these digital photographs and the way the placentas were prepared for image acquisition. The low contrast between the vascular network and its damp background makes it extremely difficult to isolate the vascular features for further analysis. Therefore, to increase the visibility of the PCSVNs and consequently the feasibility to accurately extract PCSVNs, medical practitioners have highlighted the PCSVNs by injecting veins and arteries with colored paint, see, e.g., Fig. 1b. After paint-injection, small vessels (e.g., vessels that are less than 2 pixels in width) become visible under the human eye. It allows the human tracer to identify vascular structures with a much higher confidence, as illustrated in Fig. 1d. The paint-injection process increases the visibility of otherwise invisible vessels, which allows medical professionals to study PCSVNs in greater detail. Furthermore, the paint-injection process improves (a) (b) (c) (d) Fig. 1. Examples of placenta images before and after paint-injection along with corresponding tracings of arterial network (venous tracings are similar). (a) Un- manipulated placenta. (b) The same placenta as in (a) after paint-injection. (c) Tracing of arterial vascular structure drawn from image in (a). (d) Tracing of arterial vascular structure drawn from image in (b). Note that visibility of vessels is significantly increased via the paint-injection process. (a) (b) (c) (d) Fig. 2. Examples of placenta images before and after paint-injection along with the PCSVN extraction results. (a) An image patch of an un-manipulated placenta. (b) An image patch of a paint-injected placenta. (c) PCSVN extraction result of (a) after applying a multiscale method based on shearlets and Laplacian Eigenmaps. (d) PCSVN extraction result of (b) after applying a multiscale method based on shearlets and Laplacian Eigenmaps. the potential success of automated feature extraction algorithms such as those documented in Frangi et al. (1998); Almoussa et al. (2011); Chang et al. (2012). For example, Fig. 2 shows the PCSVN extraction results of applying a directional multiscale mathematical framework based on the combination of shearlets and Laplacian Eigenmaps (Yacoubou Djima et al., 2017) to images of un-manipulated (Fig. 2a) and paint-injected PCSVNs (Fig. 2b). There is a noticeable improvement in the extraction result after paint-injection, as seen in Fig. 2c,d. The benefit of the paint-injection process in studying the connections between human placental vascular networks and many adult diseases can be visualized in Fig. 3. Ultimately, we wish to decide whether an intervention is needed simply by taking a digital photograph of the placental chorionic surface vascular networks (Fig. 3a–f). In order to accomplish this, we need to precisely identify which features from the PCSVNs (Fig. 3e) are capable of differentiating placentas that are associated with a fetal outcome or adult disease from those in the general population. Extracting a detailed description of the vascular networks serves as a crucial step in this ultimate research goal. The purpose of our work is to provide a robust validation framework to the manual tracing protocol. 56 Image Anal Stereol 2018;37:55-62 Fig. 3. Medical application and implication of our work. During the paint-injection process, many important placental characteristics such as tortuosity and the number of vessel endpoints are altered. In (Shah et al., 2015), tracings of PCSVNs before and after paint-injection were shown to be comparable, with unsatisfactory matching scores. Their work concluded that the vascular networks of un-manipulated and paint-injected placentas are similar with roughly 71% confidence; however, the sources that caused the remaining 29% to mismatch were not identified. Therefore, it was unclear whether the tracing protocol used in obtaining the traced networks were accurate modulo the geometric changes that are invariant under their comparison model. MATERIALS AND METHODS DATA SET Our data is obtained from 19 singleton full- term birth placentas and is the same as that used in Shah et al. (2015). The placentas in the data set were cleaned, paint-injected, and photographed in New York-Presbyterian Brooklyn Methodist Hospital (see, e.g., Fig. 4a). The PCSVN of each placenta, before and after the paint-injection, was then traced manually by a trained expert using the software GIMP and following the protocol described in Shah et al. (2015). In short, the tracer distinguishes the placental chorionic surface arterial network from the subjacent venous network and uses different colors and pencil sizes to mark different vessel thicknesses and locations of the chorionic plate boundary and umbilical cord insertion. It takes roughly 4 to 8 hours to trace a single PCSVN. See Fig. 4b for an example of a traced image. Our data set is as follows. From each of the 19 placentas, we obtain two pairs of tracings: the arterial network before and after paint-injection, and the venous network before and after paint-injection. An example of one pair in the data set can be seen in Fig. 1 (c) and (d). We seek to design an algorithm that reflects the geometry of the tracings and that successfully matches the 38 tracing pairs, consequently demonstrating that meaningful placental features are preserved in the paint-injection process. (a) (b) Fig. 4. (a) Paint-injection process. (b) A manually traced image. Notice that the location of the umbilical cord insertion is marked with a yellow dot and the scale is given by the two blue dots on 12 and 13 of the ruler. 57 FARNELL E ET AL: Placental chorionic surface vascular networks PRE-PROCESSING Color tracings were uniformly scaled and converted to 1380× 1440 pixel binary images. One centimeter was marked with two blue dots on a ruler within the original photograph of the placenta to give scale. Roughly 35 pixels in the digital image corresponded to 1 cm on the placenta. Tracings were aligned so that the umbilical cord insertion lies at the center of the image. A one-pixel-wide skeletonization of the PCSVN tracing was created in Matlab to prepare for the computation of geometric signatures called shape contexts (Belongie et al., 2002; Zhang and Malik, 2003; Wang et al., 2007). Visual inspection of tracings shows that paint-injection can introduce variability in vessel thickness; by using a one-pixel skeleton, we remove vessel thickness from the model while preserving PCSVN structure. SHAPE CONTEXT We aim to design a model that helps explain both geometric differences introduced through the process of paint-injection and features that are preserved in that process. This model may then provide a validation framework to the manual tracing protocol and help to establish assurance to a new pre-processing approach for studying vascular networks by way of paint- injection. A shape-context model is thus particularly appropriate for this setting. We modify an approach introduced in Belongie et al. (2002) and encourage the interested reader to see this source for a comprehensive background of related methods. Our algorithm matches un-manipulated and paint- injected tracings based on comparison of points in tracings near chosen reference points. Specifically, we choose N reference points pi within a circle of radius 360 pixels (one-fourth of the width of an image) about the umbilical insertion, where p1 corresponds to the umbilical insertion and each pi, i 6= 1, is randomly selected. For each reference point, we let the positive x-axis be the ray starting at the reference point and pointing to the right. Points are represented by polar coordinates (r,θ), where r is measured in pixels from the reference point and θ is measured in degrees counterclockwise from the positive x-axis. An m×n shape-context matrix H is defined at each reference point, whose entries Ha,b are the number of points in the tracing that satisfy (a−1) · (rmax m ) < r < (a) · (rmax m ) and (b−1) · ( 360 n ) < θ < (b) · ( 360 n ) , normalized by the number of points that fall in the circle centered at pi with radius given by the parameter rmax. That is, the entries in the shape context matrix represent the relative frequency of vessel pixels within each angular and radial region partitioned by the choice of m and n in the polar grid. See Fig. 5 for a shape context example. (a)0.029 0.105 0.184 0.190 0.135 0.0630 0 0.154 0.133 0.007 0 0 0 0 0 0 0  (b) (c) Fig. 5. A shape context example. A single bin and its corresponding entry is highlighted throughout the subfigures. (a) A one-pixel skeleton tracing shown with a coarse polar mesh (m = 3,n = 6). (b) The shape context matrix H. Each entry is the relative frequency of pixels from the tracing in the corresponding bin of the mesh. (c) A visualization of H. Lighter colors correspond to higher values. ROTATION Since some movement of local placental features can occur during paint-injection, we allow for matches near a reference point pi between shape contexts of paint-injected tracings rotated about the umbilical insertion with shape contexts from tracings of un- manipulated placentas. Results are reported based on T uniformly-spaced rotations with T = 90. SCALING To model the altered geometry introduced in paint- injection, we introduce a scaling parameter at each reference point. Consider a shape context Hi with parameters m, n, and rmax for pi = (ri,θi) in a tracing U , where (ri,θi) are coordinates relative to the 58 Image Anal Stereol 2018;37:55-62 (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) Fig. 6. An illustration of the matching algorithm using shape contexts. (a) Un-manipulated tracing with umbilical insertion p1 in blue, a second reference point p2 in red, and corresponding polar meshes. Smallest diameter vessels are removed. Note that the polar meshes are 36×36; the full meshes are not shown for visual purposes. We use rmax = 432. (b) Shape context for umbilical insertion in (a). The histogram matrix accumulates the relative frequency of vessel pixels within each angular (x-axis) and radial (y-axis) bin; lighter shades represent higher values. (c) Shape context for p2 in (a). (d) Paint-injected tracing that corresponds to un-manipulated tracing in (a), with p1 in blue, p2 in red, and corresponding polar meshes. (e) and (f) Shape contexts for (d) based at p1 and p2, respectively, with s1 = s2 = 1. Note that without rotation and scaling, these do not provide a good match. (g) Rotated paint-injected tracing with scaled polar mesh that provides the best match to shape context in (b). (h) Shape context for p1 in (g). Parameters are s1 = 1.15 and angle of rotation 124◦. (i) Rotated paint-injected tracing with scaled polar mesh (and scaled location) for p2 that provides the best match to shape context in (c). (j) Shape context for p2 in (i). Parameters are s2 = 1.1 and angle of rotation 128◦. Chi-square values are approximately (e) 1.87, (f) 1.76, (h) 0.78, and (j) 0.82. 59 FARNELL E ET AL: Placental chorionic surface vascular networks umbilical insertion. We create a scaled shape context Ĥi,si with parameters m, n, and sirmax at p ′ i = (siri,θi) in the tracing I. Theoretically, si is a continuous variable that models the geometric scaling introduced during the injection process. In our algorithm, we allow si to take on values in the following discrete set: {0.95,1,1.05,1.10,1.15,1.20} . Visual inspection of the data set suggests that stretching is more common than shrinking at a local level; hence most allowed values of si are greater than or equal to one. SHAPE-CONTEXT MATCHING A distance function is needed to compare two shape contexts, H and Ĥ. Here, we follow the convention in Belongie et al. (2002), known as the chi- square test statistic: d(H, Ĥ) = m ∑ a=1 n ∑ b=1 (Ha,b− Ĥa,b)2 Ha,b + Ĥa,b , where the sum is taken over entries for which the denominator is non-zero. A tracing of an un-manipulated placenta U with shape contexts H1, . . . ,HN is matched to the tracing of a paint-injected placenta I if I yields the set of shape contexts Ĥ1,s1 , . . . , ĤN,sN , where each rotation and scaling parameter is chosen to be optimal, that minimizes the quantity ∑Ni=1 d(Hi, Ĥi,si). Note that it is possible for the rotation and scaling parameters to differ across the set of shape contexts in the above objective function. Major contributions of our work are the inclusion of several spatial reference points and the consideration of local geometric changes in PCSVNs through rotation and scaling parameters. Fig. 6 provides a visualization of shape-context matching. RESULTS AND DISCUSSION Small vessels become more visible in paint- injected tracings; therefore, a natural comparison is one where the smallest-diameter vessels are removed. Our best results are achieved with five reference points, small vessels (those with width less than 0.6 mm) removed, and local scaling. In this case, our algorithm correctly matches an average of 37.6 out of 38 pairs of tracings over 10 random trials. Note that the only aspect of the algorithm that changes over the 10 random trials is the reference points. In comparison, 27 out of 38 matches were reported in Shah et al. (2015) when small vessels are removed. The results in Table 1 suggest that our model is robust to parameter variations and capable of producing matches with a consistently high success rate. These results demonstrate a strong link between the un- manipulated and paint-injected tracings and provide an explanation for the source of differences between the two types of images. For example, improved accuracy with increased numbers of reference points implies that the paint-injection process induces non- uniform changes across the placenta and that sufficient shape information is preserved to match tracings when local information is taken into account. Additionally, improved accuracy from the inclusion of local scaling confirms that the paint-injection process stretches or shrinks the placenta at a local level, also in a non- uniform way. Since paint-injection leads to improved extraction of PCSVNs from images of placenta, it is desirable to study the PCSVNs of paint-injected placenta. The work presented here explains the nature of the geometric differences between manual tracings of paint-injected and un-manipulated PCSVNs under the framework of a modified shape-context model and Table 1. Average number of matches out of 38 possible matches over 10 random trials. N is the number of reference points and rmax is the maximum radius (in pixels) of a circle centered around a reference point for which points in the skeleton are included in the shape context. In the “No scaling” portion of the table, no scaling is allowed when comparing tracings (i.e., each si = 1). In the “Scaling allowed” portion, each si is allowed to vary incrementally between 0.95 and 1.20. Smallest vessels included Smallest vessels removed No scaling Scaling allowed No scaling Scaling allowed rmax 432 576 720 432 576 720 432 576 720 432 576 720 N 1 29.0 26.0 26.0 30.0 31.0 32.0 31.0 29.0 31.0 33.0 32.0 37.0 2 27.8 26.7 27.0 33.3 32.8 32.2 31.3 30.8 30.5 35.7 35.9 36.7 3 28.3 27.4 27.5 33.6 33.3 32.8 32.5 31.8 31.4 36.3 36.6 36.7 4 28.9 27.5 27.1 33.7 33.7 33.1 32.7 31.4 31.2 36.3 36.3 36.7 5 28.7 27.6 27.6 33.8 33.8 34.3 33.0 31.5 31.4 37.6 37.0 36.9 60 Image Anal Stereol 2018;37:55-62 confirms the validity of the tracing protocol described in Shah et al. (2015). Our work provides assurance to a new pre-processing approach for studying vascular networks by ways of dye-injection in medical imaging problems. ACKNOWLEDGEMENTS The authors wish to thank Terri Girardi, who developed the tracing protocol and vetted tracings, and Ruchit Shah for correspondence regarding Shah et al. (2015). We also wish to thank the reviewers, whose comments helped to refine and strengthen the article. REFERENCES Almoussa N, Dutra B, Lampe B, Getreuer P, Wittman T, Salafia C, Vese L (2011). Automated vasculature extraction from placenta images. Proc SPIE 7962:79621L. Barut F, Barut A, Gun B, Kandemir N, Harma M, Harma M, Aktunc E, Ozdamar S (2010). Intrauterine growth restriction and placental angiogenesis. Diagn Pathol 22:5–24. Belongie S, Malik J, Puzicha J (2002). Shape matching and object recognition using shape contexts. IEEE T Pattern Anal 24:509–22. Carev D, Saraga M, Sarage-Babic M (2008). Involvement of FGF and BMP family proteins and VEGF in early human kidney development. Histol Histopathol 23:853– 62. Chang JM, Chang YM, Han R, Hui Z, Shah R, Newschaffer C, Miller R, Katzman P, Moye J, Salafia C (2016). Whole placental chorionic surface vessel feature analysis with boruta method, and autism risk. Placenta 45:75. Chang JM, Mulgrew A, Salafia C (2012). Characterizing placental surface shape with a high-dimensional shape descriptor. Appl Math 3:954–68. Chang JM, Zeng H, Han R, Chang YM, Shah R, Salafia C, Newschaffer C, Miller RK, Katzman PJ, Moye J, Fallin M, Walker CK, Croen L (2017). Autism risk classification using placental chorionic surface vascular network features. BMC Medical Inform Decis 17:162 Davies J (2002). Do different branching epithelia use a conserved developmental mechanism? Bioessays 24:937–48. Frangi A, Niessen W, Vincken K, Viergever M (1998). Multiscale vessel enhancement filtering. In: Wells WM, Colchester A, Delp S, eds. Medical Image Computing and Computer-Assisted Intervention – MICCAI98. Lect Not Comput Sci 1496:130–7. Herr F, Baal N, Zygmunt M (2009). Studies of placental vasculogenesis: a way to understand pregnancy pathology? Z Geburtshilfe Neonatol 213:96–100. Hu G, Chen Y, Zhang L, Tong W, Cheng Y, Luo Y, Cai S, Zhang L (2011). The generation of the endothelial specific cdc42-deficient mice and the effect of cdc42 deletion on the angiogenesis and embryonic development. Chin Med J 124:4155–9. Kaneti M, LoPriore E, Schwartz N, Misra D, Salafia C (2013). Vascular network features, separate from anastomotic communications, account for birthweight discordance in monochorionic placentas. Placenta 34:A13. Leach L, Taylor A, Sciota F (2009). Vascular dysfunction in the diabetic placenta: causes and consequences. J Anat 215:69–76. Makanya A, Hlushchuk R, Baum O, Velinov N, Ochs M, Djonov V (2007). Microvascular endowment in the developing chicken embryo lung. Am J Physiol Lung C 295:L1136–46. Salafia C, Girardi T, Newschaffer C, Miller R, Walker C, Misra D, Katzan P, Moye J, Fallin M, Herz-Picciotto I, Croen L (2013a). Placental angiogenesis and ASD: measurable differences in placental vascular structure. Reproduct Sci 20:1A–60A. Salafia C, Girardi T, Yampolsky M, Shlakhter O, Newschaffer C, Fallin D, Walker C, Stodgell C, Katzman P, Culhane J, Landrigan P, Szabo S, Thieux N, Swanson J, Dole N, Varner M, Moye J, Miller R (2013b). Chorionic vascular structure and placental functional efficiency (beta) differ in high and low autism risk placental cohorts. Placenta 34:A72. Salafia C, Misra D, Golding J, Platt C, Ring S (2012). Characterization of placental growth as a biomarker of autism/ASD risk. Placenta 33:A16. Salafia C, Yampolsky M, Misra D, Shlakhter O, Haas D, Eucker B, Thorp J (2010). Placental surface shape, function, and effects of maternal and fetal vascular pathology. Placenta 31:958–62. Saldeen J, Kriz V, Agren N, Welsh M (2006). Shb and angiogenetic factors promote es cell differentiation to insulin-producing cells. Biochem Biophys Res Commun 344:517–24. Shah R, Girardi T, Chang JM, Straughen J, Newschaffer C, Misra D, Katzman P, Miller R, Moye J, Salafia C (2016). A priori specified relationships among arterial chorionic surface vessel network (PCSVN) and autism risk. Placenta 45:76. Shah R, Salafia C, Girardi T, Conrad L, Keaty K, Bartleotc A (2015). Shape matching algorithm to validate the tracing protocol of placental chorionic surface vessel networks. Placenta 36:944–6. Vasudevan A, Bhide P (2008). Angiogenesis in the 61 FARNELL E ET AL: Placental chorionic surface vascular networks embryonic cns: a new twist on an old tale. Cell Adh Migr 2:167–9. Vasudevan A, Long J, Crandall J, Rubenstein J, Bhide P (2008). Compartment-specific transcription factors orchestrate angiogenesis gradients in the embryonic brain. Nat Neurosci 11:429–39. Wang X, Doretto G, Sebastian T, Rittscher J, Tu P (2007). Shape and appearance context modeling. In: Proc IEEE 11th Int Conf Comput Vision – ICCV 2007, pp. 1–8. Yacoubou Djima K, Salafia C, Miller RK, Wood R, Katzman P, Stodgell C, Chang JM (2017). Enhancing placental chorionic surface vasculature from barium-perfused images with directional and multiscale methods. Placenta 57:292–3. Yampolsky M, Salafia C, Shlakhter O, Haas D, Eucker B, Thorp J (2009). Centrality of the umbilical cord insertion in a human placenta influences the placental efficiency. Placenta 30:1058–64. Zhang H, Malik J (2003). Learning a discriminative classifier using shape context distances. In: Proc IEEE Comput Soc Conf Comput Vision Pattern Recogn 1:I- 242–7. 62