Fast and Robust Segmentation of Natural Color Scenes

Fast and Robust Segmentation of Natural Color ScenesV olker Rehrmann and Lutz PrieseImage Recognition LabUniversity of Koblenz-LandauRheinau1,56075KoblenzGermany1IntroductionOne of the most important tasks of an image analysis system is image segmentation,the identification of homogeneous regions in an image.In the literature several methods for segmentation are distinguished. Common are edge detection,split and merge,region growing and clustering techniques.Most of the extensive research on image segmentation in the last three decades has been done for gray scale images. However,as the technical equipment for color image acquisition becomes cheaper and more common, color image analysis becomes more and more important.Nearly all techniques for gray scale image segmentation have been transferred to color images.A survey on color image segmentation can be found in[SK94].Most papers on color segmentation follow the clustering method.Here the pixels are mapped to feature vectors in a feature space.Now statistical methods are applied tofind some clusters in this feature space. These clusters,re-mapped to the image,form the color segments.A well-known clustering technique is recursive histogram splitting([Oht85]),applied by many researchers([Cel90],[Tom90]).The advantage of clustering methods is the global view of the data often in form of histograms.However,although histograms provide a global view of the feature data,they do not reflect the spatial information of the underlying image.The extension of clusters in feature space is often ambiguous and the statistical methods trying to solve this problem are computationally expensive.Hanson and Riseman([HR78]) discuss the advantages and disadvantages of clustering in detail.Region growing techniques start with initial cells,pixels or small regions and let them grow by sequential merging with neighbored,similar regions.The pure local methods tend to chaining mismatches by merging differently colored segments.The centroid-linkage techniques are sequential methods and are therefore dependent on the choice of starting point and the order in which the pixels are processed(s. [HS85]).We tried to develop a new method combining the advantages of local(simplicity and fastness)and global (robustness and accuracy)techniques.It is a hierarchical region growing method that is inherently paral-lel and therefore independent of the choice of the starting point and the order of processing.It uses local and global information and achieves very robust segmentation results in natural color scenes which is also explained by the use of a newly developed color similarity measure.Our idea wasfirst published in [PR93].Since then a lot of improvements have been applied.This paper describes our entire color seg-mentation system,called CSC(Color Structure Code),in detail.In section2we introduce the hexagonal, hierarchical island structure on which our method is based.Section3describes the actual segmentation method.In Section4the new color similarity measure is presented.Section5discusses the complexity of our approach.The system is very fast and thus applicable in real world problems.Finally we present some results and conclusions in section6.12Hexagonal,hierarchical island structureOur segmentation method follows a hierarchical region growing on a special hexagonal topology(firstly introduced by Hartmann[Har87]).This hierarchical topology is formed by so–called islands of different levels.One island of level0consists of seven neighbored pixels in the hexagonal topology.The partition of the image is organised in such a way that the islands are overlapping.One island of level n+1consists of seven overlapping islands of level n(s.Fig.1).Repeating this until one island covers the whole image,4.the number of islands decreases from level to level by a factorOperating on a hexagonal topology leads to some difficulties in practice.Nearly all imaging devices scan the pixels in an orthogonal scheme.One possibility to get the desired hexagonal raster is calculating it from the orthogonal raster.Due to the equal distance between pixels in the hexagonal raster,the horizontal distance between the pixels is times bigger than the vertical distance.The ratio of the vertical to the horizontal extension should therefore be1:in the initial orthogonal image(e.g.512 rows x600columns).In order to avoid additional efforts we use the hexagonal island hierarchy only as a logical structure on an orthogonal raster.Figure2shows the partition of an image in orthogonal topology into islands of level within the hexagonal island hierarchy.An island consists again of seven pixels and is overlapping with its six neighbor islands in exactly one pixel.The hierarchy is continued on the higher levels in the same way as in the hexagonal raster.The only problem with this approach is the different definition of a pixels neighborhood.Since we are using the same algorithms(both on the orthogonal raster and the hexagonal raster)the same neighborhood relations are holding within an island of level.Thus,the central pixel in an island is neighbored with the other six pixels in the same island. These neighborhood relations are represented by edges connecting neighbored pixels infigure2.These 6-neighbors are not the same for pixels in an even and pixels in an odd row.All pixels in an even row (where the central pixels are)have a neighborhood relation according tofigure2(b)and all pixels in an odd row according to(c).Thus,a one pixel wide diagonal line will never be connected.However,all regions connected by the orthogonal4-neighborhood are as well connected when using the hexagonal hierarchical island structure on an orthogonal raster.Although such a non-uniform neighborhood relation seems to be artificially complicated,its inherent smooth logical structure of an hexagonal hierarchy pays off.2(a)(b)(c)Figure2:(a)The hexagonal island structure on an orthogonal raster.(b)Neighborhood relations in an even row.(c)Neighborhood relations in an odd row.3Color Structure CodeThe generation of the CSC(Color Structure Code)operates essentially in four phases.In the prepro-cessing phase noise suppression is accomplished by the use of a nonlinearfilter which,in addition, strengthens the sharpness of contours.In an initialization phase the image is partitioned into small, atomar color regions within an island of level.These small color regions are growing in the linking phase in a hierarchical manner to complete regions.Within the linking phase it is possible to detect that color regions connected by a chain of smoothly changing colors have to be split again.This is done in the splitting phase.3.1Preprocessing PhaseIn real images noise arises which has to be suppressed by appropriate techniques.Simple linearfilters that replace a central pixel by a weighted average of its neigh-borhood pixels have the drawback of blurring the edges.To protect the edges fromblurring while smoothing a non-linearfilter has to be used that adapts to local changes in the structure of the underlying image signal.We investigated threefilters with the desired properties:the median-filter,the k-nearest-neighborfilter(knn)and the symmetric nearest neighborfilter(snn).C 0 C 1 C 6C 2 C 3C 4 C 5 Figure3Figure3shows a central pixel with its simple neighborhood in a hexagonal raster.The position of each neighbor is denoted by.denotes the(R,G,B)value at position.The input to eachfilter is a color image in RGB-space with8bit quantization.When using the term color difference in this section we do mean the Euclidean distance in RGB color space.Letand be two color vectors in RGB-space.Thensuch thatThenk–Nearest–Neighbor FilterIn knn-filtering,all the color values in the neighborhood are compared with the central pixels color value. Those k pixels are determined having the closest color values.The central pixel isfinally replaced by the equally weighted average of the k nearest neighbors.Let be the color values of the simple,hexagonal neighborhood of a central pixel with.ThenDiscussionThe two crucial criteria for the choice of the rightfilter are its complexity and the improvement of the segmentation results.The following table shows the number of color distance calculations,comparisons, additions and multiplications resp.divisions.The fastestfilter is obviously the snn–filter.Filter Color Distance Additions6021333The estimation of thefilters influence on the segmentation results is much more difficult.A subjective judgement with several hundred of images has shown that the snn and the knn–filter lead to comparable4results which are better than those of the color median–filter.This is confirmed by the results of a concrete application(traffic sign recognition),where the influence of thefilters on the recognition rates has been analyzed with more than5000images([Reh94]).Thus,the choice of thefilter is clear.The snn-filter is not only the fastest but also the one leading to the best segmentation results.3.2Initialization PhaseIn the initialization phase color homogeneous regions in level islands of seven pixels are detected and mapped to initial code elements(s.Fig.4).Such an initial code element consists of those pixels of level islands that are neighbored and whose mutual color distance lies below a certain threshold.The pixels are linked in the same way as in single-linkage region-growing schemes(s.[HS85]).A code element is a data structure describing color regions within an island.In Figure4two examples are shown:A homogeneous island resulting in one code element and another island,where an edge goes through it, resulting in two code elements that describe two differently colored small regions in the island.Hence,a code element of level describes a small colored region within an island of level.Note,this operation is a pure local operation within one island,whose processing can be done independently for each island. Instead of starting with one seed pixel,the CSC starts concurrently in all islands of the image.The result of the initialization phase is a set of code elements,each one describing a small color patch.In the following linking phase these small color patches are checked for continuity and grow hierarchically to complete,connected color segments.Figure4:Two examples for the initialization of code elements.3.3Linking PhaseIn the linking phase code elements of level are linked to new code elements of level in seven, neighbored overlapping islands of the hexagonal island structure(s.Fig.5).Code elements will be linked if the regions represented by them are connected and similar in color.The connectivity of code elements can easily be determined within the hexagonal island structure:two code elements are connected if they share a common subregion in their common sub island.On level1this simply means that they share a common pixel.The linking operations are repeated for all islands on every level,starting from level and ending on the topmost level,where only one island covers the whole image(level8with512x512 pixel images).By repeated linking those code elements form a code tree.A new code element on level is stored together with pointers to the code elements on level from which was formed(s.Fig.5), the so called sub code elements.Code elements that do notfind any partner for linking on some level n form the root of such a code tree.Thus,a connected homogeneous region is represented by a tree in our CSC data structure.The larger a region is the higher is its root level in the hierarchical data structure. The root contains raw information about the size,location,and mean color of a region.More details can be obtained by descending the tree.5Figure5:An example for the link-ing of code elements.The opposite Figure shows a zoom on part of thisexample.level n level n+1 Figure6:The four marked overlap-ping code elements of level form a new code element on level.The linking of code elements within one island is similar to the operation in the initialization phase.Instead of linking single pixels,regions are linked.Again all operations within one island can be doneindependently of the other islands.The segmentation results are not depending on the order of execu-tion.All small color regions of the initialization phase are growing concurrently within one level.Theoverlapping of the islands leads to efficient connectivity checks of code elements.The hexagonal islandstructure assures that the regions are growing in all directions in contrast to quad-tree-like structures.The regions in each level therefore have approximately the same size,which is also an advantage incomparison to common region-growing techniques.3.4Splitting PhaseA typical error in local region growing techniques is the linking of differently colored regions due toa chain of connected pixels with smoothly changing colors.Such chaining mismatches often refer toan outflow of a region that cannot be detected locally.Segmentation algorithms that only use localinformation are unable to detect region boundaries with low contrast(s.Fig.10).A good segmentationalgorithm has to use local and global information.We solve this problem by additional color similaritychecks between connected code elements on every linking level.If the color distance lies above a certainthreshold the two code elements won’t be linked although they are connected by a chain of color similarpixels.Note,two connected regions in the CSC structure are always connected by a chain of color similarpixels.Consider the example in Figure7.If the color distance between and is too high,they won’tbe linked,although all their subregions on level are locally homogeneous.It is the global viewat this level that makes it possible to detect the smooth transition of one color to the other.The factthat and won’t be linked results in two different complete segments(so called roots).Due to theoverlapping structure they possess a common subregion,thus.Therefore and have to be explicitly separated,which means the common subregion has to be partitioned between and.This subsequent splitting due to a more global view can be done in an elegant way in the overlappinghierarchical island structure.Consider the general case of Figure8.Two connected code elements and are not color similar.They possess the common sub code element.has to be partitioned between and.Atfirst,thecolor value of is compared with those of and.is assigned to that code element that is closerin color which means has to be deleted from the other code element,say.This is simply a pointer612Figure7:Two neighbored islands, with their common sub island and the common subregion of and.Level n Figure8:Splitting of two code elements and.deletion.This does not mean that the whole region represented by is assigned to.This may not be an accurate border between and.Although has been deleted from it is still connected with the region represented by via and due to the overlapping structure.Now,has to be separated from and.This is done in a recursive procedure in the same way as with and.The only difference is that the color values to compare with are those of and as they represent the most global information.When splitting and it is possible that their common subregion is assigned to. That is why not necessarily the entire region of is assigned to.can loose some subregions in the recursive descent.The recursion stops at level.With this simple and elegant recursive algorithm(main operation is deletion of pointers)very accurate borders can be found(s.Fig.10).There is one technical difficulty with this algorithm.There are some integrity constraints in the data structure of the CSC.A code element always represents a connected region.In some rare situations it is possible that the splitting leads to an unconnected code element.Unfortunately the repairing of this rare case requires complicated,technical algorithms.4Color SimilarityThe color similarity measure is of particular importance for the quality of the segmentation results.The color similarity measure in the CSC is a color predicate.Given two colors in a three–dimensional color space,is defined by:Most published color similarity predicates are measures calculating the ratio of the mean colors distances and their variances.The color features are usually RGB,recently CIELAB and CIELUV.The measures are more oriented on statistical properties than on human color sensations.As those measures often don’t correspond to human judgement,we developed a new color predicate in the HSV color space.In the HSV color model a color is described by the three attributes hue,saturation and value.A description of HSV and other color models and a conversion from and to RGB can be found e.g.in[FvDFH90].Perez and Koch([PK94])discussed the advantages and disadvantages of color spaces using hue,saturation and7intensity.The main advantages are:Thus,the hue value remains constant if the intensity of illumination changes or if the saturation of a color is decreasing.These advantages make the hue feature so valuable in the segmentation of natural scenes,where illumination can’t be controlled and is often changing.The drawback of the HSV space is an unremovable singularity at the V axis,where R=G=B(saturation=0).At low intensities and at low saturations the hue value is very unstable.Because of these problems many researchers recommended other color spaces,but we think it is worth using the HSV space and taking special consideration of the drawbacks.It is clear from this fact that the HSV-space is not suited for Euclidean distance measures.It is impossible to use a constant threshold over the entire HSV color space to decide about the similarity of colors.With well saturated,bright colors the hue value is an excellent discrimination feature,while bigger differences in saturation and intensity can be tolerated to become invariant against the variations in illumination.On the other hand,the hue value is useless with unsaturated and dark colors as it is either undefined or very unstable.In this range of colors the most important feature is intensity.From color metric we know that the sensed hue difference becomes lower as the saturation and intensities are decreasing.To imitate this human color sensation the allowable thresholds for the color similarity predicate have to be chosen dependent on the color location in HSV space.Our realization of this idea is to use a table of color thresholds.The valid thresholds are determined depending on the saturation and intensity of the actually analyzed colors.Therefore we quantized saturation and intensity into16steps. For each of the16x16different locations in color space we developed thresholds for hue,saturation and value.The thresholds have been empirically determined in a large number of experiments.A graphical representation of the table entries for the three color attributes is shown in Figure9.The access to the table and the definition of the color predicate using the tables are as follows:D is defined by:=TRUEhue threshold=huetab[min][max]andsat threshold=sattab[min][max]andval threshold=valtab[min][max]Of course,the values for saturation and value have to be shifted into the range0..15before accessing the table.In the calculation of the absolute hue difference the special modular arithmetic must be used:Note,that the viewpoints are different for the three tables in Figure9.They have been changed to better visualize the shape of the particular thresholds.It can be seen that the hue thresholds for the upper quarter of the table(saturation¿7,value¿7)are nearly constant.The thresholds are changing when approaching low saturation and intensity.The extremal value for the hue threshold is reached when s=0or v=0,resulting in a hue threshold of360which simply means ignoring hue.The thresholds for saturation are increasing from low saturated to high saturated colors with the exception of very dark colors(black),where due to noise the saturation can vary a lot.The thresholds for value are low for low saturated and dark colors and increase with increasing saturation and intensity.These tables of thresholds work very well for natural color scenes.Yet,we use different sensitivities on different levels in the linking phase.The thresholds on low levels are more tolerant than those on high levels.8051015051015050100150200250300350400value saturation051005101520253035404550556065value saturation 051015051015152025303540455055value saturation Figure 9:A graphical representation of the tables of thresholds (hue,sat.and value from left to right).5ComplexityLet us briefly discuss the complexity of our approach.In the preprocessing phase each pixel is filteredregarding the simple hexagonal neighborhood of a pixel.Letdenote the number of pixels.Then times the number of operations for the processing of one pixel (see table in 3.1)is the complexity for the preprocessing phase.The two main operations in the initialization and linking phase are the comparison of color similarity and the check of connectivity of two color regions.In the initialization phase all neighbored pixels have to be compared resulting insplitting call(separation of two code elements)depends on the actual linking level and the length of the common border.The number of all splitting calls depends on the nature of the input image.In a typical natural color scene(s.Fig.12)the time of the splitting phase can be neglected(less than5%of the total processing time)because the number of splitting calls is small.In artificial images like the one in Figure 11the required time can reach up to30%of the total processing time.The overall runtime depends as well on appropriate implementation techniques.As all operations are local operations(a small number of operations are performed a lot of times)it is worthwhile to optimize these operations by standard programming tricks(e tables instead of calculations whenever possi-ble).The CSC was implemented in C and runs on different platforms.The runtime on a SUN ULTRA SPARC I with167MHz including color space conversion is on average700msec for512x512images, and180msec for256x256images.The CSC is easy to parallelize due to its inherent parallelism and we are expecting a close to video real time version on symmetric multiprocessor architectures of the next generation(e.g.4P II processors with300MHz).6Results and ConclusionsFigures11and12show two examples of color segmentation with the CSC.On the left side are the original scenes and on the right the corresponding segmentation results.Each color segment is drawn in its mean color and with its boundary for better visualization.Figure11is an artificial image showing a spectrum of smoothly changing colors.There is very low color contrast in the image.A pure local segmentation method segments the image into one large region.This is a very good example for the use of global information in the CSC and intensive splitting action.Only global methods like clustering are able to achieve comparable segmentation results.In Figure12we see a typical natural color scene with sunshine and shadows.Due to the color similarity measure there are very smooth regions.Especially in the tree area,the red traffic signs and the red roof of the house it can be seen that the results are very tolerant against variations in brightness.Pure global techniques like clustering result in a lot of different small regions in the tree and roof area.Up to now the CSC proved to be a reliable scene segmenter in two larger applications.Thefirst appli-cation is the recognition of traffic signs from a moving car.The traffic sign recognition system is based on the CSC and was successfully integrated into a prototype of an autonomous vehicle by Daimler-Benz ([PRSL93],[PKL94]).The system operates close to real-time with excellent recognition rates.The second application is a new research project using color segments as features in the analysis of motion in natural color image sequences([RR97]).The efficient CSC segmentation allows for the processing of color image sequences and the stability of color segments along with elaborate matching techniques leads to promising results in difficult tasks like tracking of objects in color outdoor scenes and motion segmentation.Our future work will focus on the application of the CSC in the analysis of color image sequences.References[Cel90]M.Celenk.A color clustering technique for image puter Vision,Graphics,and Image Processing,52:145–170,1990.[FvDFH90]J.D.Foley,A.van Dam,S.K.Feiner,and puter Graphics:principles and practice.Addison Wesley Publishing Company,second edition,1990.10[Har87]G.Hartmann.Recognition of Hierarchically Encoded Images by Technical and Biological Systems.Biological Cybernetics,57:73–84,1987.[HR78] A.R.Hanson and E.R.Riseman.Segmentation of natural scenes.In Hanson and Riseman,editors, Computer Vision Systems,pages129–163.Academic Press,New York,1978.[HS85]R.M.Haralick and L.G.Shapiro.Image segmentation puter Vision,Graphics,and Image Processing,29:100–132,1985.[Oht85]Y.Ohta.Knowlege-based Interpretation of Outdoor Natural Color Scenes.Pitman Advanced Pub-lishing Program,Boston,Massachusetts,1985.[PH86]M.Pietik¨a inen and D.Harwood.Segmentation of color images using edge-preservingfilters.In V.Cappellini and R.Marconi,editors,Advances in Image Processing and Pattern Recognition,pages94–99.North-Holland,1986.[PK94] F.Perez and C.Koch.Toward color image segmentation in analog VLSI:Algorithm and Hardware.International Journal of Computer Vision,12(1):17–42,1994.[PKL94]L.Priese,J.Klieber,kmann,V.Rehrmann,and R.Schian.New Results on Traffic Sign Recog-nition.In Proceedings of the Intelligent Vehicles Symposium,pages249–254.IEEE,1994.Paris,Oct.24-26.[PR93]L.Priese and V.Rehrmann.A Fast Hybrid Color Segmentation Method.In S.J.P”oppl and H.Han-dels,editors,Mustererkennung1993,pages297–304.Springer Verlag,1993.15.DAGM-Symposium,L”ubeck,27.-29.Sept.1993.[PRSL93]L.Priese,V.Rehrmann,R.Schian,and kmann.Traffic Sign Recognition Based on Color Image Evaluation.In Proceedings of the Intelligent Vehicles Symposium,pages95–100.IEEE,1993.Tokyo,July14-16.[Reh94]V.Rehrmann.Stabile,echtzeitf¨a hige Farbbildauswertung.Verlag F¨o lbach,Koblenz,1994.[RR97]V.Rehrmann and M.Rothhaar.Detection and Tracking of Moving Objects in Color Outdoor Scenes.In30th ISATA:Dedicated Conference on Robotics,Motion and Machine Vision in the AutomotiveIndustry,1997.Florence,16-19th June1997.[SK94]W.Skarbek and A.Koschan.Color Image Segmentation-A Survey-.Technical report94-32, Computer Science Department,TU Berlin,1994.[Tom90]S.Tominaga.A color classification method for color images using a uniform color space.In Proceed-ings of the Tenth International Conference on Pattern Recognition,pages803–807,1990.AtlanticCity,NJ,June16-21.11。