Automatic detection and removal of static shadows

HOU Tao，WU Hai-ping

(School of Automation and Electrical Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China)

Abstract： In case of complex textures, existing static shadow detection and removal algorithms are prone to false detection of the pixels. To solve this problem, a static shadow detection and removal algorithm based on support vector machine (SVM) and region sub-block matching is proposed. Firstly, the original image is segmented into several superpixels, and these superpixels are clustered using mean-shift clustering algorithm in the superpixel sets. Secondly, these features such as color, texture, brightness, intensity and similarity of each area are extracted. These features are used as input of SVM to obtain shadow binary images through training in non-operational state. Thirdly, soft matting is used to smooth the boundary of shadow binary graph. Finally, after finding the best matching sub-block for shadow sub-block in the illumination region based on regional covariance feature and spatial distance, the shadow weighted average factor is introduced to partially correct the sub-block, and the light recovery operator is used to partially light the sub-block. The experimental results show the number of false detection of the pixels is reduced. In addition, it can remove shadows effectively for the image with rich textures and uneven shadows and make a natural transition at the boundary between shadow and light.

Key words： shadow detection； shadow removal； feature extraction； support vector machine(SVM)； block matching； light recovery operator

0 Introduction

Image shadow is an inevitable optical phenomenon in various scenes. Its existence has a significant negative effect on computer vision tasks such as target recognition, image segmentation, scene analysis, scene tracking and so on. Removing shadows before performing these tasks can improve their performance[1-2]. However, due to the complexity of different types of shadows, it is a challenging job to remove shadows from a single image because it involves many factors such as illumination condition the type of shadow surface, the structure of occluded objects and the performance of capture device. According to the characteristics of different shadows, researchers have proposed various algorithms to solve these problems, such as the type and number of light sources, the structure of shadow surface, etc. As shown below, there are several algorithms which are now commonly used.

A selective update model based on geometric was proposed[3], which eliminated shadows by brightness variation, where the range of brightness variation was taken as a threshold factor for shadow detection to adaptively adjust the threshold. A multi-level hybrid multi-objective expert method (HMOE) based on semi-supervised learning (SSP-HMOE) was proposed[4], which used a two-stage MOE system for shadow detection. A shadow detection method with surface descriptors based on color was proposed[5], the color-light descriptors were introduced into the conditional random field model to obtain the same light pairs and coherent shadow regions. The local color constancy calculation method was improved, and the local light source of each pixel in the shadow was estimated by the anisotropic diffusion to remove the shadow.

In order to generate a smooth shadow mask, multiple convolutional neural networks were used to learn the features of relevant shadow automatically at the super-pixel level and along the main boundaries of the image, and then the shadow would be removed[6]. Based on the fact that the illumination invariant image is a shadow-free image, a shadow removal method by using the illumination invariant method was proposed[7]. The shadow-free chromaticity image was obtained from the illumination invariant image by calculating the logarithmic chromaticity and one-dimensional invariant image of the image. By analysis of illumination model, it has been proved that the normalized eigenvalue of image block is illumination invariant. Histogram[8]was used to calculate shadow pixels and distinguish shadow pixels from non-shadow pixels by calculating their mean value and variance. In Ref.[9], segmentation and removal of shadows were based on the features of foreground different from the background texture. At the same time, shadow texture was almost the same as background texture and was uniformly distributed. However, this method can only give accurate results under constant illumination conditions. In order to realize the accurate detection and removal of shadows, a method of selecting candidate shadow pixels or areas based on edge was used, combining with the usage of color and texture features of direction and distance[10].

Aiming at the existing problems of shadow detection and removal algorithms, by analyzing the pixel characteristics of shadow and illumination region, support vector machines (SVMs) with multiple images are trained, and then boundary pixels are processed using soft matting technology to obtain shadow binary image, with a shadow weighted average factor being introduced to equalize the illumination recovery effect of the sub-block. This method can reduce the false detection rate of shadow pixels and is robust to environmental changes, especially,it reduces the edge effect of shadow significantly.

1 Binary shadow mask

1.1 Image preprocessing

Firstly, the original image is segmented into several superpixels[11]. The collection of superpixels consists of a series of adjacent pixels with similar color, brightness and texture, and it is expressed asS={S1,S2,…,Sn}, wherendenotes the number of segmentations,Si(i=1,2,…,n) denotes the segmented superpixel, Most of effective information is retained for further image segmentation, and generally the boundary information of objects in the image is not destroyed. By comparing the segmentation results of several experiments, the number of segmentationsn=300 is selected. The segmentation effect is shown in Fig.1(b).

Fig.1 Result of segmentation

Then mean-shift clustering method[12]is used to cluster the superpixels, andldifferent clusters are obtained, that is,C(j) (j=1,2,…,l), where each cluster has its cluster centerCcent(j), cluster radiusRc(j) and number of superpixelsCnum.

1.2 Training classifier

1.2.1 Regional features

1) Color and texture features

When the area is shadowed, it will be darker than the surrounding area and the texture will be relatively reduced[13]. Therefore, the features of the color histogram and texture histogram of each pixel block can be assisted to judge whether the region is in the shaded region, which can be obtained in the experimental space.

2) Characteristics of regional difference

According to the obtained color and texture features, the difference between two regions can be obtained by calculating the color and texture chi-square distance. The greater the chi-square distance, the greater the difference. It can be expressed as

(1)

whereAiandBjrepresent different area blocks;aiandbjrepresent the pixels belonging to regionAiandBj, respectively.

3) Brightness characteristics

There is a significant boundary at the junction of shadow and shadow-free due to the strong scattering of blue sky light components in the environment, which increases the proportion of blue components in all regions[14]. The boundary of the shadow and the illumination area can be separated by calculating the proportion of blue components. The formula can be expressed as

(2)

whereρRrepresents the average value of the red channel in the first block.Ravg1is the average value of the red channel for the shadow region,Ravg2is the average value of the red channel for the illumination region. For a shadow/non-shadow pair with the same material, the non-shadow region has a higher value in all three channels.

4) Similarity coefficient characteristics

It is necessary to find a regional correlation coefficient to measure the similarity between the two regions. The larger the distance, the greater the similarity. Thus it can be expressed as

(3)

After four features of the region are obtained, an appropriate classifier is selected for off-line data training. SVM is selected as a classifier because of its excellent performance on two-class classification. The obtained features are used as input of the classifier and output as confidence values of regional shadows.

1.2.2 Objective function

According to the confidence value of region shadow obtained previously, the objective function[15]can be expressed as

(4)

2 Removal of static shadow

2.1 Illumination model

(5)

Shor et al[17]believed that there is a linear relationship between the observed values of the pixels in the shadow area and their shadow-free values. Thus Eq.(5) can be rewritten as

(6)

(7)

From Eqs.(5)-(7), we can get

(8)

(9)

According to Eq.(9), shadows can be removed by finding areas with similar texture features between shadow and illumination areas and restoring illumination. However, shadow removal model can only be applied to the images with single texture features, but not to the images with complex texture features. Moreover, the results show that in the natural scene, there are no sharp edges in the shadow and non shadow areas, which gradually changes along the shadow boundary. Therefore, using the previous shadow binary results as the value of shadow coefficient to restore the shadow area will produce strong boundary effect, as shown in Fig.2.

Fig.2 Result of shadow removal in Ref.[15]

2.2 Boundary smoothing

In order to obtainyaccuratly, soft matting method[18]is used to obtain more accurate shadow boundary detection results. The image can be regarded as the proportional combination of foreground image and background image, then

Ix=βFx+(1-β)Bx,

(10)

whereFxis foreground image,Bxis background image, andβis proportional coefficient. Eq.(10) is further expressed as

Ix=β(LdRx+LaRx)+(1-β)LaRx.

(11)

The energy equation is minimized as

(12)

2.3 Sub-block matching

In order to remove the shadows of complex texture regions well, the sub-block matching model is put forward. Its establishment depends on the texture similarity matching between the shadow area and the illumination area, that is, a shadow-free sub-block with similar material or texture to the shadow sub-block is found near the illumination area, and the shadow sub-block is removed by the illumination recovery operation. The following problems need to be considered: 1) If the shadow of each subblock is removed separately, the results may be inconsistent and visually unnatural, therefore it should ensure that the adjacent shadows are sub-blocks are removed naturally; 2) For each sub-block in the shadow area, the corresponding matching sub-blocks should be found effectively in the bright area to improve the efficiency of shadow removal.

2.3.1 Image decomposition

The input image is decomposed by overlapped sub-blocks with a size ofw×wpixels (w>10). The set blocks should overlap sufficiently with each other to ensure that a given pixel can be affected by multiple sub-blocks at the same time, as shown in Fig.3. This not only can make the transition between adjacent blocks smoothly and naturally, but also can reduce the error rate when a sub-block is matched inaccurately. The decomposed image consists of a set of shadow sub-blocks and a set of illumination sub-blocks, where {S(k)}k=1,2,…,Nrepresents the set of shadow sub-blocks, {L(k)}k=1,2,…,Lrepresents the set of illumination sub-blocks. When the best sub-blockL(i) in set {L(k)} is found to matchS(j) in set {S(k)}. The shadow ofS(j) in the matching sub-block {L(i),S(j)} is removed by using the illumination recovery operator, as shown in Fig.3.

Fig.3 Decomposition of input image

2.3.2 Candidate sub-block search

For each shadow sub-block, an effective texture matching measure is used to find the nearest sub-block in the illumination region. In our work, the matching sub-blocks are searched by using the regional covariance feature and spatial distance. The matching principle is that only when the illuminations are the same, the textures and colors of two sub-blocks with the same reflectivity will be similar; if the illuminations are different, the colors and intensities of the two windows may be different. Therefore, the local matching measure should be illumination independent and robust in the case of changing illumination. Because of the large difference of lights between shadow and illumination regions, in order to overcome this problem, these two matching features are constrained by each other for local region search.

1) Region covariance feature is an effective feature description method for a region in an image[19]. It has a strong recognition ability when distinguishing local texture and image structure. Its region covariance matrix is expressed as

(13)

CR=VVT,

(14)

Because the operation of covariance matrix in Euclidean space is not closed, the covariance matrix is transformed into

(15)

whereVirepresents columniof lower triangular matrixV. In order to find the best sub-block in the illumination region, theCRof each sub-block in the illumination region is calculated. The similarity calculation between the shadow sub-block and the illumination sub-block is calculated, that is, the similarity distance between two covariance matrices are expressed as

(16)

whereμSandμLare the means of the pixel features in shadow sub-block and illumination sub-block, respectively,f(CS) is the covariance matrix of shadow sub-block, andf(CL) is the covariance matrix of illumination sub-blocks. The smaller theDSL, the higher the similarity. In fact, more candidate sub-blocks contribute to more accurate region matching, which requires higher computational costs. In order to achieve a good trade-off between efficiency and accuracy in the matching process, five candidate sub-blocks are selected.

2) As for spatial distance, since the adjacent regions in space usually have similar illumination information, the best sub-blocks are selected from five candidate sub-blocks for shadow removal by using spatial distance measure in the shadow regions with similar texture. The spatial distance is the sum of squares of the difference between the center pixels of the illumination sub-block and the center pixels of the shadow sub-block as

(17)

wherexSandySarexandycoordinates of the pixel in shadow region, respectively.

2.3.3 Illumination unification processing

There is enough overlaping between the sub-block sets in image segmentation when a pixel may be contained in more than one shadow block. Shadow pixels in overlapping regions have different shadow-free values for different sub-blocks. Intuitively speaking, in order to achieve consistent removal between adjacent blocks, each pixel should consider all possible shadow-free values. Here the overlapping region pixels are assigned weightωito represent the weighting factor of the pixel as

(18)

(19)

3 Simulation and analysis

In order to illustrate the effectiveness of the proposed algorithm, the original shadow image, original shadow-free image and original actual shadow image in natural scene provided by Ref.[15] are used in the Matlab2016B programming environment. In Ref.[15], the appearance and characteristics of the segmented areas are used to predict the relative illumination conditions of the shadow and light areas, and then the detection results are refined by image extinction. Finally, each pixel is re-illuminated to restore the shadow-free image according to the light model. The image includes 335×500 pixels. The results are shown in Fig.4.

Fig.4 Results of shadow detection

It can be seen from Fig.4 that under the interference of a series of factors such as complex environment, illumination change, similar foreground, background, complex texture and so on, the method in Ref.[15] is prone to false detection of shadow pixels while the algorithm in this paper can reduce false detection of shadow pixels to a certain extent.

In order to quantitatively verify the proposed algorithm, shadow error detection rateηis used to reflect it, which is defined as[15]

(20)

whereTtdenotes the correct image pixel for detection;Tfdenotes the error pixel for detection(missed or mistaken detection). Using manual segmentation, the correct shadow pixels are divided, and the proportions of the numbers of pixels in the shadow area in the original image and the shadow pixels obtained by various detection algorithms are calculated, as listed in Table 1..

Table 1 Comparison of shadow detection

Shadow removal results are shown in Fig.5. The first column is original image, the second column is result of Ref.[15], and the third column is shadow removal results of our algorithm.

Fig.5 Results of shadow removal

In order to show the shadow removal results of the proposed algorithm clearly, the results of shadow removal are magnified and compared locally, as shown in Fig.6.

Fig.6 Comparison of shadow removal partially

In order to analyze the results of shadow removal quantitatively, the deviation between the observed value and the true value can be calculated by means of root-mean-square error(RMSE).

It can be seen from the results that the smaller the value, the better the recovery. The values of RMSE are shown in Table 2.

Table 2 RMSE of shadow removal

4 Application in actual scene

In order to verify the effectiveness of the proposed algorithm in other scenes, shadow detection and removal experiments are conducted on some railway shadow images. In the railway scene, there are usually some objects around the railway, such as noise-proof trees around the railway track, or some objects that in nature appear in the scope of railway monitoring, which will have a certain effect on the safety of the railway. Therefore the detection and removal of these shadows become particularly important. Shadow removal results are shown in Fig.7.

In static shadow detection and removal experiments in railway scenes, the algorithm can remove the shadows in natural environment very well. In Fig.7, the shadow is lighter than that of previous experiments, but it has no significant effect on the removal effect. Therefore, this algorithm can be used in railway monitoring technology to remove the shadow which has an effect on railway operation in advance and to ensure the safe operation of trains.

5 Conclusion

In this paper, a static automatic shadow detection and removal algorithm based on SVM and region sub-block matching is proposed. Mean-shift clustering after super-pixel segmentation can reduce the false detection rate of negative pixels. In order to eliminate the obvious boundary effect in shadow removal, the soft matting technique is used to optimize the detected shadow binary image. In addition, the shadow weighted average factor is introduced to uniformize the illumination in the overlapping area. Finally, the shadow removal image with natural boundary transition is obtained.

Compared with the existing shadow removal algorithms, the proposed algorithm can efficiently reduce the false detection rate of shadow pixels. For the shadow images with rich texture types and uneven shadows, the effect of shadow removal is obvious, and the performance of shadow edges is good. This method has been applied to the actual railway scene and has achieved good results. It proves that the proposed algorithm has good robustness and wide application range, and it has highly practical significance for generalization.