Journal of Textile Institute, 90, 288-297. FIBER IMAGE ANALYSIS PART III: AUTONOMOUS SEPARATION OF FIBER CROSS SECTIONS Bugao Xu, Sihong Wang and Jie Su University of Texas at Austin Abstract One of the challenging tasks in fiber image analysis is to separate touching cross sections of fibers before extracting fiber geometrical features. This paper reports a skeleton-based segmentation algorithm that deals with this problem. A skeleton of touching objects in an image is the medial axis of the objects, and can be obtained with a sequential erosion procedure. A skeleton reflects the overall longitudinal shape of an object. When the pixels on a skeleton are weighted by the distances to the object edge, the skeleton also contains the information about the transverse shape of the object. The pixels where the distances are minimal indicate possible connecting points of two adjacent objects. A line perpendicular to the skeleton can be drawn across the touching objects at an identified connecting pixel to separate the objects. Inappropriate separations caused by small concave noises on the edge can be avoided by using pre-specified thresholds when checking the skeleton distance, and the time-efficiency can be greatly improved by eliminating iterative thickening operations. Introduction Object segmentation is an image-processing procedure to separate touching objects in a binary image. Autonomous segmentation of touching objects is crucial for the accurate measurement of object features, because touching objects will be considered as one entity that does not represent the true features of individual objects. Fiber cross-sections entail important geometrical properties of fibers, and image analysis is one of the most effective ways for automatic fiber cross-sectional measurements [Xu, et al. (1993)]. To cut a thin, smooth layer of fibers transversely, a bundle of fibers is usually jammed and embedded in the mounting medium, yielding severe touching in the image captured with a CCD camera through a light microscope. Touching fibers must be reasonably separated before taking measurements. Due to the complexity in 1
Journal of Textile Institute, 90, 288-297. touching situations, a segmentation procedure often disconnects fibers at wrong positions or is unable to detect connections. Operator’s assistance is often needed to correct false separations or missed separations. Object segmentation may be carried out in a gray-scale image by locating the edges of objects. For touching objects that have little or no contrast between their connecting portions, the final separation has to be fulfilled after the image is converted into a binary one in which specific morphological operations, such as the watershed segmentation [Russ, et al. (1988) and Xu, et al. (1996)], can be implemented. The watershed algorithm comprises two major steps: iterative erosion and conditional thickening. A gray-scale image, called the distance map, is created to register the nearest distances of sequentially eroded layers to the object periphery by assigning different levels of brightness. The touching objects are eventually disconnected as the erosion repeats. The nuclei of different objects, the last eroded pixels, are labeled with the maximum brightness in the distance map. A nucleus in the distance map represents the core of a separate object. The nuclei are then dilated layer by layer with the preset rules to ignore any pixel that makes a connection with another nucleus. A separation line between two touching objects can be formed by this conditional thickening process. However, the watershed segmentation is sensitive to small concave variations (dips) on the object edge because a dip results in two nuclei. Therefore, it is applicable only to the separation of smooth convex objects. In addition, the watershed algorithm is a slow procedure due to the iterative thickening operations in which every pixel is subject to the checking with 256 3x3 templates [Russ, et al. (1988)]. 2
Journal of Textile Institute, 90, 288-297. In the first two papers of this series, we introduced various imageprocessing algorithms effective for fiber image enhancement and measurement including both longitudinal and cross-sectional analysis [Xu, et al. (1996)]. In this paper, we will report the development of a skeleton-based segmentation algorithm and its application to the separating of touching fiber cross sections. The new algorithm aims at reducing mis-separations and improving the timeefficiency of the segmentation. One limitation of the algorithm is that it requires fiber cross sections to have a regular and uniform shape. Circular, elliptical and trilobal fibers will be used to show the results of this segmentation algorithm.
Weighted Skeleton The developed segmentation algorithm utilizes the skeletons of objects in an image. The skeleton of an object is the medial axis of the object, and it represents its longitudinal shape, but it does not contain any information about the transverse shape (thickness) of the object. Both longitudinal and transverse shapes are needed in finding a connection along the skeleton of two touching objects. Since the transverse shape of an object varies along its skeleton, it is advantageous to use a skeleton to carry both longitudinal and transverse shape information of an object. The skeleton of an object can be found by using iterative inward erosions [Dougherty et al. (1988) and Serra (1988)]. Before the outer layer or edge of an object is eroded, all these edge pixels are examined to see if this layer contains a skeleton pixel. The neighboring pixels of an edge pixel in a 3x3 region, 3
Journal of Textile Institute, 90, 288-297. including skeleton pixels found previously, are checked to find out whether the neighboring pixels are a connected group. If the neighboring pixels are not connected, this edge pixel is a skeleton pixel because removing it causes disconnection of the object. Figure 1 shows some examples of connected and disconnected neighboring pixels in a 3x3 region. One particular case is that there is only one neighbor pixel in the template. In fact, this pixel is an end point of the skeleton.
Connected Figure 1 3x3 Region ( : edge pixel,
Disconnected : neighboring pixel, : no pixel)
When the touching objects are eroded layer by layer, the number of the removed layers, or the distance (or thickness) from the current layer to the edge, can be recorded. When a skeleton pixel is found, its intensity can be used to register the transverse distance at this point. In other words, the number stored in a skeleton pixel is the shortest distance of the pixel to the edge. After the skeletonization, an object is shrunk into a number of skeleton pixels weighted by the distances (Figure 2). The weighted skeleton not only saves the storage space (no extra space is needed to register the thickness), but also associates the traverse shape of an object with its longitudinal shape, which is important in determining whether the object contains sub-touching objects and where the connecting point is on the skeleton.
4
Journal of Textile Institute, 90, 288-297.
original object
after the first erosion weighted skeleton Figure 2 Skeletonization
Detection of Connecting Pixel After a weighted skeleton is obtained, the pixels on the skeleton where the object can be split can be detected by using information from the distance profile of the skeleton. A distance profile is a curve of the distance to edge d against the skeleton length l (Figure 3). The following parameters are used to describe a skeleton: the total length L, the maximum distance dmax, the minimum distance dmin, and the dip depth D= dmax- dmin. d D
dma
L dmin l Figure 3 Distance Profile along the Skeleton If connections occur only between two circular or elliptical objects, the criteria for detecting connecting points on a skeleton are straightforward. The first step is to set a minimal length-distance ratio, because when the skeleton length L is significantly larger than the maximum distance dmax the skeleton probably connects the two objects. If L/dmax is smaller than the selected 5
Journal of Textile Institute, 90, 288-297. minimal ratio, the skeleton does not have to be checked for connections. Considering the uniformity in object size and shape, the minimal L/dmax ratio should be adjustable to accommodate for different samples. It was found out that 1.5 is a reasonable selection for the minimal ratio of L/dmax for many circular and elliptical objects. The second step is to check the dip depth D. When D is larger than a preset threshold, the object edge contains a dip that is deep enough to indicate a division for two objects. A skeleton pixel with the minimum distance dmin is the point where the skeleton should be split (Figure 4). Once the connecting point is detected, a line perpendicular to the skeleton at this point can be drawn to cut the object from edge to edge. The threshold can be adjusted based on the user’s criterion to avoid a separation at a small dip. 20
breaking point d 10
0 0
2
4
6
8
10 12 14 16 18
Skeletonized
l
Separated
Figure 4 Distance Profile When the dip is narrow and sharp the connecting point is relatively easy to determine. When two objects are connected by a long bridge, the distance profile will have a wide range of the minimum-distance pixels (Figure 5). The minimum-distance pixels are counted, and the object is cut either through the center of the minimum-distance range or at all the minimum-distance pixels.
6
Journal of Textile Institute, 90, 288-297. 20
breaking point d 10
0 0
2
4
6
8
10 12 14 16 18 20
Skeletonized
l
Separated
Figure 5 A Long Bridge Connection The third step is to consider special cases in the distance profiles, such as a one-side dip showed in Figure 6 and a thin tail in Figure 7. A one-side dip often occurs in the objects intercepted by the image frames. Incomplete objects should be separated from other objects and then deleted from the image. The connecting point on the skeleton distance profile can be detected by finding the pixel where a long flat portion starts. A thin tail is usually a residual of the embedding medium or extraneous matter attached to the object. It can be found by checking the turning point on the distance profile that leads to a long and narrow portion. 20
breaking point d 10
0 0
5
10
15
20
Skeletonized
l
Figure 6 One-Side-Dip Distance Profile
7
Separated
Journal of Textile Institute, 90, 288-297. 35 30 25
d
20
breaking point
15 10 5 0 0
10
20
30
Skeletonized
40
Separated
l
Figure 7 A Thin Tail on A Distance Profile If a skeleton connects more than two objects in a series, there will be multiple waves on the distance profile (Figure 8). The computer calculates the weighted skeleton and then sorts the distance dips along the skeleton. The dips are respectively checked in the order of their depths and cut if satisfying the criteria set for the length/distance ratio and the dip depth. 20
breaking point d 10
0 0
5
10
15
20
25
30
l
Skeletonized
Separated
Figure 8 Connection in Series Breaking the Skeleton Net When more than two objects connect together in different directions, their skeletons will cross each other, forming a net. The typical skeleton nets may include triangular nets, branch nets and polygonal nets (Figure 9). For convex objects, the intersections of their skeletons appear approximately at the centers of the objects. A skeleton net can be broken down at the intersection points to
8
Journal of Textile Institute, 90, 288-297. produce a number of separated skeletons that have only two ends. Then the same procedure described previously is applied to detect the connecting point for each broken skeleton. The first example in Figure 9 shows three objects touching each other and forming a triangular skeleton net with short branches. This triangular net can be broken into three pieces at the intersection points in a way that the lengths of the broken pieces are as uniform as possible. After the net is broken down, a connecting point is identified on each piece of the skeletons and therefore three objects are separated. If three objects overlap, the skeletons become a branch net that has only one intersection point to be broken in this case (see the second example). However, the three broken pieces are all too short to satisfy the minimal L/dmax ratio. Three edge points that are closest to the intersection point of the skeletons and spread roughly at a 120o interval can be located, and therefore the object can be cut from these edge points to the intersection point. Skeletons of touching objects may form a closed curve as seen in the third example in the figure. The skeleton is opened up first at a pixel where the skeleton has the largest distance to the edge. Along this open skeleton, several touching objects exist, and the connecting points can be sequentially detected. The last example in the figure contains four connecting objects with small concave variations on the edges. After breaking up the skeleton at the intersection point, each piece of the skeleton still has a sufficient length and a connecting point can be found to separate the surrounding object from the centered object.
9
Journal of Textile Institute, 90, 288-297. 1.
2.
3.
4.
Original
Skeletonized Separated Figure 9 Separation of Skeleton Nets
If objects are not circular or elliptical but have regular and uniform shapes, the shape information will be needed in determining where to break up the skeleton net. In Figure 10, for example, breaking the skeleton net is guided by the structure of the trilobal shape. The skeleton is split only at the intersections of three branches that spread at approximately 120o. If an intersection point is passed by only two skeleton lines, the shorter one should be cut off at this point and then deleted. Short branches arise from edge noises as seen in the figure.
10
Journal of Textile Institute, 90, 288-297.
Original Skeletonized Separated Figure 10 Separation of Trilobal Objects
Separation of Fiber Cross Sections Figures 11, 12 and 13 show three examples of separations of fiber cross sections accomplished by using this skeleton-based segmentation algorithm. After fibers are separated, the fibers touching the image frames are removed in the “separated” images. The first example, shown in Figure 11, contains circular cross-sections. All the intersections in the skeleton net are at the centers of the circular cross sections, even if one fiber is touching with several other fibers. Branches are simply broken at intersection points, and one connecting point is searched on each branch. Figure 12 shows the second example that contains elliptical cross sections. One elliptical fiber may have more than one intersection, depending upon the number of fibers it touches and the touching positions. After the skeleton is broken down at all intersections, branches shorter than the maximum distance dmax to the edge of corresponding objects are deleted before finding a connecting point on each broken skeleton. Figure 13 is the image of a trilobal nylon. A fiber center can be located at the 11
Journal of Textile Institute, 90, 288-297. intersection point of three branches of the skeleton, and the disconnecting point of two touching fibers can be found on the skeleton between the two fiber centers by checking the depth D of a dip. Double bridges are due to the small holes in fiber boundary regions, and can be broken by tracing a skeleton between two connecting centers twice.
Original Skeletonized Separated Figure 11 Separation of Circular Cross Sections
Original Skeletonized Separated Figure 12 Separation of Elliptical Cross Sections
12
Journal of Textile Institute, 90, 288-297. Original Skeletonized Separated Figure 13 Separation of Trilobal Cross Sections Representation of Fiber Cross Sections If a fiber cross section is circular or elliptical, the weighted skeleton of the fiber can be used to describe its size and shape. Also, the skeleton appropriately represents the position and orientation of the cross section in the image. After fibers are separated, the weighted skeletons of all fibers are recalculated and then fitted by straight lines to minimize the influence of noise. Assume that the maximum distance of a weighted skeleton is dmax, the skeleton length is L and the distances at the two skeleton ends are d1 and d2. The semishort axis a and the semi-long axis b of an ellipse that fits into the cross section are (Figure 14): a = d max b = ( L + d1 + d 2 ) / 2
x x’
y’ b
a
y0 skeleton y
θ
x0 Figure 14 A Fitting Ellipse If the origin of the x-y coordinate system is located at the center of the image, a fiber cross section in the image will normally not be centered at the origin and its axis will be tilted to the x-axis. Once the center coordinate and the orientation of the skeleton are know, it takes two steps to calculate an 13
Journal of Textile Institute, 90, 288-297. ellipse that fits into the cross section. First, calculate a standard ellipse in the x’-y’ coordinate system as follows:
x '2 y '2 + =1 a 2 b2 and then shift and rotate the (x’,y’) coordinates of the ellipse in the (x,y) system using the following conversions: x = ( x '− x0 ) cos θ − ( y '− y 0 ) sin θ y = −( x '− x0 ) sin θ + ( y '− y0 ) cos θ where (x0, y0) is the center of the skeleton and θ is the slope angle of the skeleton. Figure 15 shows calculated ellipses of fiber cross sections in Figures 11 and 12. Ellipses provide not only the size and shape measurements but also a way to reduce the storage space for fiber cross sections. A cross section can
Figure 15 Fitting Ellipses of Fiber Cross Sections be saved and reconstructed using the parameters of its fitting ellipse instead of all the coordinates of its boundary. Summary
The skeleton-based segmentation provides a fast and precise procedure for separating fiber cross sections in an image, because it eliminates the iterative 14
Journal of Textile Institute, 90, 288-297. thickening process required in the watershed segmentation and it reduces the mis-separations caused by small concave variations on object edges. It is particularly effective when fibers to be analyzed have regular and uniform shapes. Acknowledgement
This material is based upon work supported by the National Science Foundation of the United States under Grant DMI-9522943, and by the United States Agriculture Department under Grant 95-37500-1950. Reference Dougherty, E.R., and Giardina, C.R., 1988. Mathematical Methods for Artificial Intelligence and Autonomous Systems, Prentice-Hall, Inc., pp 351-358.
Russ, J.C. and Russ, J.C., 1988. Improved Implementation of A Convex Segmentation Algorithm, ACTA Stereol, 7/1, 33-40. Serra, J. P., 1988. Image Analysis and Mathematical Morphology, Academic Press Limited, pp 257-295. Xu, B., Pourdeyhimi, B. and Sobus, J., 1993. Fiber Cross-Sectional Shape Analysis Using Imaging Techniques, Textile Research Journal, 63, 717-730. Xu, B. and Ting, Y., 1996. Fiber Image Analysis, Part I: Fiber Image Enhancement, J. of Textile Institute, 87, 274-283. Xu, B. and Ting,Y., 1996. Fiber Image Analysis, Part II: Measurement of General Geometric Properties of Fibers, J. of Textile Institute, 87, 284-295.
15