IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
959
Fuzzy Random Impulse Noise Removal From Color Image Sequences Tom Mélange, Mike Nachtegael, and Etienne E. Kerre
Abstract—In this paper, a new fuzzy filter for the removal of random impulse noise in color video is presented. By working with different successive filtering steps, a very good tradeoff between detail preservation and noise removal is obtained. One strong filtering step that should remove all noise at once would inevitably also remove a considerable amount of detail. Therefore, the noise is filtered step by step. In each step, noisy pixels are detected by the help of fuzzy rules, which are very useful for the processing of human knowledge where linguistic variables are used. Pixels that are detected as noisy are filtered, the others remain unchanged. Filtering of detected pixels is done by blockmatching based on a noise adaptive mean absolute difference. The experiments show that the proposed method outperforms other state-of-the-art filters both visually and in terms of objective quality measures such as the mean absolute error (MAE), the peak-signal-to-noise ratio (PSNR) and the normalized color difference (NCD). Index Terms—Circuits and systems, computers and information processing, computational and artificial intelligence, filtering, filters, fuzzy logic, image denoising, logic, nonlinear filters.
I. INTRODUCTION MAGES and videos belong to the most important information carriers in today’s world (e.g., traffic observations, surveillance systems, autonomous navigation, etc.). However, the images are likely to be corrupted by noise due to bad acquisition, transmission or recording. Such degradation negatively influences the performance of many image processing techniques and a preprocessing module to filter the images is often required. Among those filters, more and more fuzzy techniques start to appear in literature [7], [11]–[18], [33], [41], [43], [44]–[47], [49], [52], [53]. Fuzzy set theory was introduced by Zadeh in 1965 [24] and is a generalization of classical set theory. A classical crisp set over a universe can be modelled by a mapping (characteristic function): an element belongs to the set or does not belong to it. Fuzzy sets are now modelled as mappings (membership functions). So the characteristic function is extended to a membership function where also membership degrees between zero and one are allowed. An elcan now also belong to some degree to the set, ement
I
Manuscript received March 25, 2010; revised July 12, 2010; accepted August 31, 2010. Date of publication September 20, 2010; date of current version March 18, 2011. This work was supported by the GOA project B/04138/01 of Ghent University. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Kenneth K. M. Lam. The authors are with the Fuzziness and Uncertainty Modeling Research Unit, Department of Applied Mathematics and Computer Science, Ghent University, 9000 Ghent, Belgium (e-mail:
[email protected]; mike.nachtegael @ugent.be;
[email protected]; http://www.fuzzy.ugent.be). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIP.2010.2077305
which allows a more gradual transition between belonging to and not belonging to. Such gradual transition makes fuzzy sets very useful for the processing of human knowledge in terms of linguistic variables (e.g., large, small, etc.). There is for example no need to use a threshold to decide whether a difference in color component value between two pixels is large or not. Two differences that differ only one unit (which is not noticeable by the human eye) could then be respectively large and not large. It is better to allow a difference to be large to some intermediate degree. For a larger difference, this degree will be higher than that of a smaller difference. For an illustration of the effectiveness of fuzzy set theory in image processing, we refer to, e.g., [25]. Most filters in literature, that are developed for video, are intended for sequences corrupted by additive Gaussian noise (e.g., [3]–[7]). Only few video filters for the impulse noise case can be found (e.g., [19]–[23], [30], [31], [45], [46]). However, several impulse noise filters for still images exist. The best known among them are the median based rank-order filters (e.g., [8]–[10], [32], [34]–[40], [48]. But also some fuzzy techniques can be found [11]–[18], [33], [41]. Such 2-D filters could be used to filter each of the frames of a video successively. However, temporal inconsistencies will arise due to the neglection of the temporal correlation between successive frames. A better alternative would be to use 3-D filtering windows, in which also pixels from neighboring frames are taken into account [19]–[23], [30], [31], [45], [46]. The main problem in using neighboring frames is motion between them. Using pixels at corresponding spatial positions in neighboring frames for noise removal may introduce ghosting artifacts in the presence of camera and object motion. In the method proposed in this paper, we will therefore only in non-moving areas assign a temporal impulse between two corresponding spatial positions to noise (detection phase) and for the replacement of a noisy pixel (filtering phase) motion compensation will be applied to find the most reliable pixel in the previous frame. Analogously, a distinction between filters intended for greyscale images and for color images needs to be made. Filters for greyscale images could be used for color images by applying them on each of the color bands of the image separately. In this paper, we consider the images to be modeled in the RGB color space and we thus have three color bands: red, green and blue. However, such approach will generally introduce many color artefacts, especially in textured areas, due to the neglection of the correlation between the different color bands. To incorporate this correlation, vector-based methods were introduced. Most of these methods are based on ordering the vectors in a predefined filtering window. The output for a given color pixel is then the pixel in the window around the given pixel, that has
1057-7149/$26.00 © 2011 IEEE
960
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
the smallest accumulated distance (Euclidean distance, angular distance, etc.) to all other vectors in the window [32], [34]–[40], [30], [31], [43], [51], [44], [52], [45], [50], or which is the most similar to all window pixels [41], [53]. To avoid blurring due to the filtering of noise-free pixels, this filtering framework has been further refined by weighted filtering techniques [38], [10], [20] and switching schemes where the filter is only used for detected noisy pixels [31], [32], [34], [39], [41], [48], [30], [45], [43], [51], [44], [52]. The drawback of vector-based methods, however, is that their performance is highly reduced for higher noise levels. Consider for example a neighborhood, in which all pixels have one noisy component, and the other components are noise-free. So, although a lot of the components are still noise-free, no noise-free vector will be found for the output of the vector-based methods. It would be better to filter the color bands separately, but by using information from the other color bands. However, not much alternatives for the vector-based approach can be found in literature. Some examples developed for still images are, e.g., [12], [13], [33]. In this paper, we present a filter for the removal of random impulse noise in color image sequences, in which each of the color components is filtered separately based on fuzzy rules, in which information from the other color bands is integrated. To preserve the details as much as possible, the noise is removed by three successive filtering steps. Only pixels that have been detected to be noisy are filtered. This filtering is done by blockmatching, a technique used for video compression that has already been adopted in video filters for the removal of Gaussian noise (e.g., [4]–[6]), but that has not really found its way to impulse noise filters yet. The correspondence between blocks is usually calculated by a mean absolute difference (MAD), that is heavily subject to noisy impulses. Therefore, we introduce a MAD measure that is adaptive to detected noisy pixels components. To benefit as much as possible from the spatial and temporal information available in the sequence, the search region for corresponding blocks contains pixel blocks both from the previous and current frame. The experiments show that the proposed method outperforms other state-of-the-art filters both visually and in terms of objective quality measures such as the MAE, PSNR and NCD. The paper is structured as follows. The successive filtering steps of the proposed filter are discussed in Section II. In Section III, values for the used parameters are determined and a comparison to other state-of-the-art filters is carried out. The paper is concluded in Section IV. II. THE PROPOSED ALGORITHM The filtering framework presented in this paper is intended for color video corrupted by random impulse noise. If we respectively denote the original (noise-free) sequence by , the th and the red, green and blue comframe of that sequence by ponent of the color of the pixel at the th row and th and column in that frame by (i.e., ), then is determined as follows [1], [2]: the noisy sequence
Fig. 1. Overview of the different steps in the proposed algorithm.
where and denotes the probability that a pixel component value is corrupted and replaced by a identically distributed independent random noise value coming from a uniform distribution on the interval of possible color component values. For the color videos used in the experiments of this paper, 8 bits are used for the storage of the color component values and we work with a uniform distribution on the interval [0, 255]. Further, the probability that a given color component value is corrupted is independent on whether the neighboring values or the values in the other color components are corrupted or not. The proposed filtering framework consists of three successive filtering steps as depicted in Fig. 1. By removing the noise step by step, the details can be preserved as much as possible. Indeed, if a considerable part of the noise has already been removed in a previous step, and more noise-free neighbors to compare to are available, it will be easier to distinguish noise from small details. In the first step (Section II-A) (with output denoted by ), we calculate for each pixel component a degree to which it is considered noise-free and a degree to which it is considered noisy. If the noisy degree is larger than the noise-free degree, the pixel component is filtered, otherwise it remains unchanged. The determination of both degrees is mainly based on temporal information (comparison to the corresponding pixel component in the previous frame). Note, however, that only in non-moving areas can large temporal differences be assigned to noise. In areas where there is motion, such differences might also be caused by that motion. As a consequence, and as can be seen in Fig. 2, impulses in moving areas will not always be detected in this step. They can, however, be detected in the second step (Section II-B) (output ). Analogously as to the first step, again a noise-free degree and a noisy degree are calculated. However, the detection is now mainly based on color information. A pixel component can be seen as noisy if there is no similarity to its (spatio-temporal) neighbors in the given color, while there is in the other color bands. The third step (Section II-C) (output ), finally, removes the remaining noise and refines the result by using as well temporal as spatial and color information. For example, homogeneous areas can be refined by removing small impulses that are relatively large in that region, but are not large enough to be detected in detailed regions and that thus have not been detected yet by the previous general detection steps. The results of the different successive filtering steps are illustrated for the 20th frame of the “Salesman” sequence in Fig. 2. A. First Filtering Step 1) Detection: In this detection step, we calculate for each of the components of each pixel a degree to which it is considered noise-free and a degree to which it is thought to be noisy. A
MÉLANGE et al.: FUZZY RANDOM IMPULSE NOISE REMOVAL FROM COLOR IMAGE SEQUENCES
961
Fig. 3. The membership function
of the fuzzy set large positive.
(
AND (
and ) for which is NOT LARGE POSITIVE OR are NOT LARGE POSITIVE)))
THEN the red component FREE.
Fig. 2. The original 20th frame of the “Salesman” sequence (a), the frame corrupted by 20% random impulse noise (b) (PSNR = 15:05 dB) and the result after the first (c) (PSNR = 23:72 dB), second (d) (PSNR = 29:42 dB) and refinement step (e) (PSNR = 36:78 dB) respectively.
component for which the noisy degree is larger than the noisefree degree, i.e., that is more likely to be noisy than noise-free, will be filtered. Other pixel components will remain unchanged. The noise-free degree and the noisy degree are determined by fuzzy rules as follows. We consider a pixel component to be noise-free if it is similar to the corresponding component of the pixel at the same spatial location in the previous or next frame and to the corresponding component of two neighboring pixels in the same frame. In the case of motion, the pixels in the previous frames can not be used to determine whether a pixel component in the current frame is noise-free. Therefore, more confirmation (more similar neighbors or also similar in the other color components) is wanted instead. For the noise-free degree of the red component (and analogously for the other components), this is achieved by the following fuzzy rule. is NOT Fuzzy Rule 1: IF(( LARGE POSITIVE OR is NOT LARGE POSITIVE) AND there are two neighbors ( and ) for which is NOT LARGE POSITIVE) ( OR (there are four neighbors and ) for which is NOT LARGE POSITIVE OR (there are two neighbors
is considered NOISE-
To represent the linguistic value large positive in the above as rule, a fuzzy set is used, with a membership function depicted in Fig. 3 (see Section III-A for the determination of the parameters). For the conjunctions (AND), disjunctions (OR) and negations (NOT) in fuzzy logic, triangular norms, triangular conorms and involutive negators [26] are used. In this paper, we will use the minimum operator, the maximum operator and the respectively. standard negator Those operators are simple in use and yielded the best results, but the difference compared to the results for another choice of operators is neglectible. The outcome of the rule, i.e., the degree is to which the red component of the pixel at position considered noise-free, is determined as the degree to which the antecedent in the fuzzy rule is true:
where
and where and respectively denote the degree to which there are two (respectively four) neighbors for which the absolute difference in the red component value is not large positive, that is determined as the second (respectively fourth) largest element in the set
and denotes the degree to which there are two neighbors for which the absolute differences in the red component and one of the two color components are not large positive, determined as the second largest element in the set
962
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
Analogously, a degree to which the component of a pixel is considered noisy is calculated. In this step, we consider a pixel component to be noisy if the absolute difference in that component is large positive compared to the pixel at the same spatial location in the previous frame and if not for five of its neighbors the absolute difference in this component and one of the other two color bands is large positive compared to the pixel at the same spatial location in the previous frame (which means that the difference is not caused by motion). Further, we also want a confirmation either by the fact that in this color band, there is a direction in which the differences between the considered pixel and the two respective neighbors in this direction are both large positive or large negative and if the absolute difference between those two neighbors is not large positive (i.e., there is an impulse between two pixels that are expected to belong to the same object) or by the fact that there is no large difference between the considered pixel and the pixel at the same spatial location in the previous frame in one of the other two color bands. For the red component (and analogously the other components) this leads to the following fuzzy rule. Fuzzy Rule 2: IF( is LARGE POSITIVE AND NOT (for five neighbors ( and ) is LARGE POSITIVE AND ( OR is LARGE POSITIVE))) AND ((in one of the four directions (the differences AND are both LARGE POSITIVE OR both LARGE NEGATIVE) AND the absolute differis NOT LARGE ence is NOT LARGE POSITIVE) OR ( POSITIVE OR is NOT LARGE POSITIVE)) THEN the red component
Fig. 4. The membership function
of the fuzzy set large negative.
frame is large positive and five of its neighbors do not show motion, is then given by
Further, the degree to which there is no large difference between the considered pixel and the pixel at the same spatial location in the previous frame in one of the other two color bands is given by
Finally, the degree to which there is a direction in which the is an impulse, denoted by , is pixel at position determined as the maximum value in the set
where
is considered noisy.
Analogously to the linguistic term large positive, also large negative is represented by a fuzzy set, characterized by the membership function given in Fig. 4 (see Section III-A for the determination of the parameters). The degree to which for five neighbors the absolute differences in the red component and one of the other two components are large positive compared to the corresponding pixels in the previous frame, denoted by , is determined as the fifth largest value in the set Combining the above, we get
The degree to which the absolute difference between the pixel and the corresponding pixel in the previous at position
2) Filtering: In this subsection, we discuss the filtering for the red color band. The filtering of the other color bands is analogous. We decide to filter all red pixel components that are considered more likely to be noisy than noise-free, i.e., for . The red components which of the other pixels remain unchanged to avoid the filtering of noise-free pixels (that might have been uncorrectly assigned a
MÉLANGE et al.: FUZZY RANDOM IMPULSE NOISE REMOVAL FROM COLOR IMAGE SEQUENCES
low noisy degree, but for which the high noise-free degree assures us that it is noise-free) and thus detail loss. On the other hand, noisy pixel components might remain unfiltered due to an uncorrect high noise-free degree, but those pixels can still be detected in the next filtering step.
is thus a vector that gives information on whether the respective should be filtered. color component of the color pixel denotes the th frame of deAnalogously as notes the 2-D array of vectors that gives information about the pixel components of the th frame of the sequence . To exploit the spatial and temporal information in the sequence as much as possible, the filtering is performed by blockmatching. To do this, a noise-adaptive mean absolute difference (MAD) is used to calculate the correspondence between the color components blocks of image pixels (where of two is a general parameter that determines the block size):
963
and ) and their absolute difference is large and positive (i.e., ). In these cases, the , such that the noise-adaptive MAD is changed to the value block will not be used for the filtering. in this first For the filtering of a red component step of our algorithm, we determine the displacement vectors and for the best block in a search region matching of size in respectively the previous and the current frame (due to large frame motion, sometimes no corresponding block might be found in the previous frame, but the region around the given pixel in the current frame might be similar) as follows (for the optimization and , refer to Section III-A): of the parameters
The minimum value itself is denoted by . We have used the identity function Id for the binary function corresponding to the previous frame, since this frame has already been filtered and should be noise-free.
with
and
In the above equations, and are the two frames (2-D color images), to which the blocks belong, and indicate the spatial coordinates of the central pixel of the considered block in , and and respectively stand for the vertical and horizontal coordinates of the displacement vector, i.e., the block that is considered as the central pixel. The binary functions in has and indicate whether the pixel comand are reliable and should be used ponents , respectively ) or not ( , ( ). Using only noise-free pixel comporespectively nents allows us to calculate a more reliable measure to estimate whether two blocks would correspond in the red component if they were both noise-free. If , the noise adaptive MAD is assigned the value . Further, the noise adaptive MAD is not considered reliable if not for at least half of the positions in the blocks, both compared values are and ) reliable ( or not for half of the reliable positions the absolute difference is not large positive (i.e., ). It is also not considered reliable if both the green and blue component of the central pixels are reliable (i.e.,
The minimum value itself is denoted by . We have , for which restricted ourselves here to pixels , since only noise-free pixels should be used to replace the noisy pixel component . , for which A pixel component , is then filtered as the noise-free center of the best corresponding block in the search region, if it exists . Otherwise, , the pixel a spatial filtering is performed. If component remains unchanged in this step. Summarized, the is output of this first step for the red component given as follows. , then If
else if
, then
with (in a general notation)
964
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
where the spatial filtering framework is given by
If , which is unlikely to happen in practical situations, then the output is given by . B. Second Filtering Step In our aim to preserve the details as much as possible, the noise is removed in successive steps. In this step, the noise is . Also in detected based on the output of the previous step this second filtering step, a degree to which a pixel component is expected to be noise-free and a degree to which a pixel component is expected to be noisy, is calculated. In the calculation of those degrees, we now take into account information from the other color bands. A color component of a pixel is considered noise-free if the difference between that pixel and the corresponding pixel in the previous frame is not large in the given component and also not large in one of the other two color components. It is also considered noise-free if there are two neighbors for which the difference in the given component and one of the other two components are not large. So, the other color bands are used here as a confirmation for the observations in the considered color band to make those more reliable. For the red component (and analogously the other color components), this gives the following fuzzy rule. is NOT Fuzzy Rule 3: IF( LARGE POSITIVE AND( is NOT LARGE POSITIVE OR is NOT LARGE POSITIVE) OR(for two neighbors ) POSITIVE AND( LARGE POSITIVE OR NOT LARGE POSITIVE)) THEN the red component FREE.
(
and is NOT LARGE is NOT is
and
is the second largest element in the set
A pixel component is considered noisy if there are three neighbors that differ largely in that component, but are similar (not a large difference) in the other two components. It is also considered noisy if in the considered color band, its value is larger or smaller than the component values of all its neighbors, and this is not the case in both of the other color bands. For the red component of a pixel (and analogously for the other components), this corresponds to the following fuzzy rule. ( Fuzzy Rule 4: IF (for three neighbors and ) is LARGE POSITIVE AND is NOT LARGE POSITIVE AND is NOT LARGE POSITIVE) ( and OR (((for all neighbors ) is LARGE ( POSITIVE) OR (for all neighbors and ) is LARGE NEGATIVE)) AND NOT (((for all neighbors ( and ) is LARGE POSITIVE) OR (for all neighbors ( and ) is LARGE NEGATIVE)) AND ((for all neighbors ( and ) is LARGE POSITIVE) OR (for all neighbors ( and ) is LARGE NEGATIVE)))) THEN the red component
is considered NOISY.
The noisy degree for the red component of the pixel at position is then calculated as follows:
where is considered NOISE-
The degree to which the red component of the pixel at position is considered noise-free, is then given by and where
where
is the third largest element in the set
MÉLANGE et al.: FUZZY RANDOM IMPULSE NOISE REMOVAL FROM COLOR IMAGE SEQUENCES
965
and if
with . All red (and analogously green and blue) components are filtered for which , the other red components remain un: changed
Analogously to the first step, for the filtering of the red components (and analogously the green and blue components) for , we search for the noise-free center which of the best corresponding block in the search region in the current and previous frame.
The minimum value itself is denoted by
.
The minimum value itself is denoted by . , the is filtered as If
and , then the red component is considered to be noisy . The last check is to prevent noise propagation in the case that the pixel in the previous frame would not have been filtered correctly. • Very small impulses might not have been detected by the algorithm. In homogeneous areas however, such impulses might be relatively large and can be detected more and respectively denote easily. Let the second largest and second smallest red component value among the eight neighbors in a 3 3 neighbor. If hood around (homogeneous neighborhood) and further also or (the red component is clearly larger or smaller than the is neighborhood), then the red component considered to be noisy . • Based on color information, the red component is considered to be noisy if in a 3 3 neighborhood two neighbors can be found for which and . In all other cases the red component value is considered to be noise-free and should not be adapted anymore . Analogously as in the previous steps, for the filtering of the , we search for red components for which the noise-free center of the best corresponding block in the search region in the current and previous frame.
Red pixel components that are considered noise-free remain unchanged: The minimum value itself is denoted by
.
The minimum value itself is denoted by for which A red component is filtered as
.
C. Third Filtering Step The result from the previous steps is further refined based on temporal, spatial and color information. Namely, the red component (and analogously the green and blue component) of a pixel is refined in the following cases: • In non-moving areas, pixels will correspond to the pixels in the previous frame, which allows us to detect remaining isolated noisy pixels. If lies in a non-moving 3 3 neighborhood, i.e., (with )
Otherwise
, it remains unchanged:
,
966
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
III. EXPERIMENTAL RESULTS To be able to judge the performance of the proposed method, we will use the mean absolute error (MAE), the peak-signal-tonoise ratio (PSNR) and the normalized color difference (NCD) as objective measures of similarity and dissimilarity between a and the original one , each containing filtered frame rows and columns of pixels. The MAE is given by
TABLE I DETERMINATION OF THE PARAMETERS par AND par (ARITHMETIC MEAN OF THE AVERAGE PSNR (dB) VALUES AROUND THE MAXIMUM)
W
The lower the MAE, the more similar (less dissimilar) the images. The PSNR value is defined as
where denotes the maximum possible value of a pixel com). The higher the PSNR value, the more ponent (here similar (less dissimilar) the images. Finally, the NCD, between an original and a filtered frame, is calculated as
where
is the Euclidean norm and and respectively denote the -transform [42] of the original and the filtered frame. The lower the NCD value, the more similar (less dissimilar) the images. The remainder of this section is structured as follows. The parameter values for the membership functions and the window sizes are determined in Section III-A. The proposed filtering framework is compared to other state-of-the-art noise reduction methods in Section III-B. Some notes on the complexity are discussed in Section III-C. A. Parameter Selection
and that determine the memFirst the parameters bership functions and in Figs. 3 and 4 are determined. and of To do this, we have fixed the window sizes the pixel neighborhood and the search region in the filtering as (5 5 neighborhood) and (11 11 search region) and we have let the parameters and run over a
W
TABLE II DETERMINATION OF THE PARAMETERS AND (ARITHMETIC MEAN OF THE AVERAGE PSNR (dB) VALUES)
range of possible values. The parameter values were then deter, for which the arithmetic mean mined as the couple of the PSNR result of the nine sequences “Salesman”, “Bus” and “Tennis”, each corrupted with respectively 5%, 15% and 25% random impulse noise in each of the color bands, reached its maximum. The obtained values, which we will also use in the (Table I). remaining experiments, are and are set. For the above Next, the window sizes selected parameter values for and , we now let the and run over a range of possible values. As parameters can be seen in Table II, from the couple on, the arithmetic mean of the PSNR values of the nine test sequences hardly increases. Although we have focused in this paper on the noise filtering capability of the filter and not on its complexity, it should be mentioned that most of the computation time needed by the method goes to the filtering of detected pixels, i.e., the search for the best matching block. The size of a block (the number of pixels that has to be handled for each block) and the size of the search region (the number of blocks to which a given block should be compared) increases and . Therefore, quadratic with respect to respectively for the we have decided to use the couple remaining experiments. With respect to the complexity, we also remark that the higher the noise level, the more noisy pixels, and thus the more pixels that need to be filtered, i.e., the more pixels for which the block matching is performed. A first possibility to reduce the computation time would be to use faster block matching techniques such as those presented in [27]–[29]. Further, it can also be remarked that the detection (respectively filtering) of a pixel is independent of the detection (respectively filtering) of the other pixels in the frame and could thus be performed in parallel.
MÉLANGE et al.: FUZZY RANDOM IMPULSE NOISE REMOVAL FROM COLOR IMAGE SEQUENCES
Fig. 5. MAE results for the different methods applied on (a) “Salesman” (p = 5%), (b) “Tennis” (p = 10%), (c) “Bus” (p = 15%), (d) “Foreman” (p = 20%), (e) “Chair” (p = 25%) and (f) “Deadline” (p = 30%).
B. Comparison to Other State-of-the-Art Filters In this subsection, the performance of the proposed method is compared to that of the adaptive vector median filter (AVMF) from [31] and [32], the video adaptive vector directional median filter (VAVDMF) with 3-D filtering window from [30] and the 2-D fuzzy impulse noise reduction method for color images (INRC) from [33]. The adaptive vector median filter [31], [32] orders the pixels (color vectors) in the 3-D filtering window based on increasing accumulated (Euclidean) distance to the other pixels in the window. If the Euclidean distance between the central pixel in the window and the mean of a given number of vectors that have the lowest accumulated distance, is greater than a given threshold, then the central pixel is filtered as the pixel with the lowest accumulated distance, otherwise, it remains unchanged. In the video adaptive vector directional median filter [30], the vectors are first ordered based on increasing angular distance. If the absolute distance between the central pixel in the window and the mean of a given number of vectors that have the lowest accumulated angular distance, is greater than a given threshold, then the central pixel is filtered as the pixel with the lowest accumulated absolute distance (magnitude), otherwise, it remains unchanged.
967
Fig. 6. PSNR results for the different methods applied on (a) “Salesman” (p = 5%), (b) “Tennis” (p = 10%), (c) “Bus” (p = 15%), (d) “Foreman” (p = 20%), (e) “Chair” (p = 25%) and (f) “Deadline” (p = 30%).
To show that the proposed filter takes real advantage from the temporal information, we have also compared the proposed filter to the 2-D fuzzy impulse noise reduction method for color images. As shown in [33], the INRC filter outperforms all other compared state-of-the-art 2-D methods and can thus be accepted as a good representative for the 2-D impulse noise filters. Further, this filter is also a representative of a non-vector-based filter, in which the color bands are filtered separately. However, in the detection of noisy pixel components, also information from the other components is used. All methods have been processed on the “Salesman”, “Bus”, “Tennis”, “Deadline”, “Chair” and “Foreman” sequences, for random impulse noise levels (in each color band) ranging from % to %. The results of these experiments in terms of MAE, PSNR and NCD are respectively presented in Figs. 5 and 7, from which it is can be concluded that the proposed method outperforms all other methods. It is however well known that the above measures do not always correspond to human perception. Recent research (e.g., [54], [55]) has resulted in quality assessment criteria that accord better to subjective human judgment. An even better alternative would be to compare the processed sequences visually. Therefore, the results of the different compared methods performed
968
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
Fig. 8. 110th frame of the “Tennis” sequence (top-left to bottom-right): original, noisy (p = 5%), INRC, AVMF, VAVDMF and Proposed.
Fig. 7. NCD results for the different methods applied on (a) “Salesman” (p = 5%), (b) “Tennis” (p = 10%), (c) “Bus” (p = 15%), (d) “Foreman” (p = 20%), (e) “Chair” (p = 25%) and (f) “Deadline” (p = 30%).
on the noisy “Tennis” % , “Deadline” % and “Salesman” % sequences, can be found on http://www.fuzzy.ugent.be/tmelange/results/colourimpulse. Figs. 8 and 9 respectively show for the 110th frame of the “Tennis” sequence and the 20th frame of the “Deadline” sequence, the original frame, the noisy frame and the result obtained by the different compared methods. We see that the VAVDMF removes the noise very well. However, too many noise-free pixels are filtered as well, which results in both spatial and temporal inconsistencies, especially around edges. Further, the filter also performs less well in the case of motion (e.g., “Salesman” (arms), “Tennis” (ball), “Chair”, “Bus”), due to the fact that the pixels in the filtering window from the previous and next frame will then not always correspond to the same object. The other vector-based method, i.e., the AVMF, preserves the details very well. However, it fails to remove the noise adequately. Even for lower noise levels, small impulses remain visible. Analogously as the VAVDMF, it also performs less well in the case of motion. Next, the INRC results in very good noise removal, even for high noise levels. At the cost of this, however, too much detail gets lost (e.g., side lines on the table in “Tennis”) and the images become a little blurry. Further, several temporal inconsistencies
in non-moving areas can be detected, especially when they are detailed (e.g., background “Deadline”, “Salesman”). This is no surprise, since the 2-D filter does not benefit from the available extra temporal information in such non-moving areas. Finally, the proposed fuzzy filter combines very good detail preservation to very good noise removal and clearly outperforms all compared filters. The filter benefits very well from the extra information coming from similar regions in a spatio-temporal neighborhood. C. Some Notes on the Complexity As shown in the previous subsection, the proposed filtering framework outperforms other state-of-the-art filters for video corrupted by random impulse noise. However, it also needs to be said that in the development of our filtering framework, the main focus was the filtering result and not the complexity, as it was more the case for the compared methods. Note that the largest computational cost of the proposed filter can be attributed to the block matching in the filtering stage. Since only pixels that are detected as noisy are filtered, the number of pixels that are filtered, and thus the running time of the algorithm, will increase with increasing noise level. As an illustration, Table III gives the running time for the processing of the “Salesman” sequence corrupted by different noise levels by the proposed algorithm. The algorithm was implemented in Matlab in combination with the mex-function and executed on an Intel® Xeon® CPU X3360 @ 2.83 GHz. Some suggestions to reduce the computation time needed by the proposed filter could be the following. First, the block matching in the filtering
MÉLANGE et al.: FUZZY RANDOM IMPULSE NOISE REMOVAL FROM COLOR IMAGE SEQUENCES
969
is based on fuzzy rules in which information from spatial and temporal neighbors as well as from the other color bands is used. Detected noisy components are filtered based on blockmatching where a noise adaptive mean absolute difference is used and where the search region contains pixels blocks from both the previous and current frame. The experiments showed that the proposed method outperforms other state-of-the-art methods both in terms of objective measures such as MAE, PSNR and NCD and visually. REFERENCES
Fig. 9. 20th frame of the “Deadline” sequence (top-left to bottom-right): original, noisy (p = 25%), INRC, AVMF, VAVDMF and Proposed.
TABLE III AVERAGE RUNNING TIME (SECONDS PER FRAME) FOR THE PROCESSING OF THE “SALESMAN” SEQUENCE
stage could be sped up by using fast motion estimation techniques such as those presented in [27]–[29]. Next, for higher noise levels, it might be useful to do the block matching for blocks of pixels and to filter each of the noisy pixels in the blocks at the same time instead of applying the block matching for each noisy pixel separately. Further, in each of the successive steps in the algorithm, the detection and filtering of a pixel does not depend on the detection and filtering of the other pixels in the frame, such that the algorithm could be further sped up by performing this detection and filtering for several pixels in parallel. IV. CONCLUSION In this paper, we have presented a new filtering framework for color videos corrupted with random valued impulse noise. In order to preserve the details as much as possible, the noise is removed step by step. The detection of noisy color components
[1] E. Abreu, M. Lightstone, S. K. Mitra, and K. Arakawa, “A new efficient approach for the removal of impulse noise from highly corrupted images,” IEEE Trans. Image Process., vol. 5, no. 6, pp. 1012–1025, 1996. [2] R. H. Chan, C. Hu, and M. Nikolova, “An iterative procedure for removing random-valued impulse noise,” IEEE Signal Process. Lett., vol. 11, no. 12, pp. 921–924, 2004. [3] S. M. M. Rahman, M. O. Ahmad, and M. N. S. Swamy, “Video denoising based on inter-frame statistical modelling of wavelet coefficients,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 2, pp. 187–198, 2007. [4] L. Jovanov, A. Pizurica, V. Zlokolica, S. Schulte, P. Schelkens, A. Munteanu, E. E. Kerre, and W. Philips, “Combined wavelet-domain and motion-compensated video denoising based on video codec motion estimation methods,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 3, pp. 417–421, 2009. [5] H. B. Yin, X. Z. Fang, Z. Wei, and X. K. Yang, “An improved motion-compensated 3-D LLMMSE filter with spatio-temporal adaptive filtering support,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 12, pp. 1714–1727, 2007. [6] L. Guo, O. C. Au, M. Ma, and Z. Liang, “Temporal video denoising based on multihypothesis motion compensation,” IEEE Trans. Circuits Syst. Video Technol, vol. 17, no. 10, pp. 1423–1429, 2007. [7] T. Mélange, M. Nachtegael, E. E. Kerre, V. Zlokolica, S. Schulte, V. De Witte, A. Pizurica, and W. Philips, “Video denoising by fuzzy motion and detail adaptive averaging,” J. Electron. Imaging, vol. 17, no. 4, pp. 043005–, 2008. [8] T. Chen, K. K. Ma, and L. H. Chen, “Tri-state median filter for image denoising,” IEEE Trans. Image Process., vol. 8, pp. 1834–1838, 1999. [9] R. C. Hardie and C. G. Boncelet, “LUM filters: A class of rank-order-based filters for smoothing and sharpening,” IEEE Trans. Signal Process., vol. 41, pp. 1061–1076, 1993. [10] S. J. Ko and Y. H. Lee, “Center weighted median filters and their applications to image enhancement,” IEEE Trans. Circuits Syst., vol. 38, pp. 984–993, 1991. [11] S. M. Guo, C. S. Lee, and C. Y. Hsu, “An intelligent image agent based on soft-computing techniques for color image processing,” Expert Systems With Appl., vol. 28, pp. 483–494, 2005. [12] S. Schulte, V. De Witte, M. Nachtegael, D. Van der Weken, and E. E. Kerre, “Fuzzy random impulse noise reduction method,” Fuzzy Sets Syst., vol. 158, pp. 270–283, 2007. [13] S. Schulte, M. Nachtegael, V. De Witte, D. Van der Weken, and E. E. Kerre, “A fuzzy impulse noise detection and reduction method,” IEEE Trans. Image Process., vol. 15, no. 5, pp. 1153–1162, 2006. [14] F. Russo, “Fire operators for image processing,” Fuzzy Sets Syst., vol. 103, no. 2, pp. 265–275, 1999. [15] F. Russo, “Hybrid neuro-fuzzy filter for impulse noise removal,” Pattern Recognit., vol. 32, pp. 1843–1855, 1999. [16] H. K. Kwan, “Fuzzy filters for noise reduction in images,” in Fuzzy Filters for Image Processing, M. Nachtegael, D. Van der Weken, D. Van De Ville, and E. E. Kerre, Eds. Heidelberg, Germany: Springer, 2003, pp. 54–71. [17] J. H. Wang, W. J. Liu, and L. D. Lin, “An histogram-based fuzzy filter for image restoration,” IEEE Trans. Syst. Man Cybern. B, Bern., vol. 32, no. 2, pp. 230–238, 2002. [18] H. Xu, G. Zhu, H. Peng, and D. Wang, “Adaptive fuzzy switching filter for images corrupted by impulse noise,” Pattern Recognit. Lett., vol. 25, pp. 1657–1663, 2004. [19] F. Cocchia, S. Carrato, and G. Ramponi, “Design and real-time implementation of a 3-D rational filter for edge preserving smoothing,” IEEE Trans. Consum. Electron., vol. 43, no. 4, pp. 1291–1300, 1997. [20] J.-S. Kim and H. W. Park, “Adaptive 3-D median filtering for restoration of an image sequence corrupted by impulse noise,” Signal Process.: Image Commun., vol. 16, pp. 657–668, 2001.
970
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 4, APRIL 2011
[21] P. S. Windyga, “Fast impulsive noise removal,” IEEE Trans. Image Process., vol. 10, no. 1, pp. 173–179, 2001. [22] R. Lukac and S. Marchevsky, “LUM smoother with smooth control for noisy image sequences,” EURASIP J. Appl. Signal Process., vol. 2001, no. 2, pp. 110–120, 2001. [23] M. El Hassouni, H. Cherifi, and D. Aboutajdine, “HOS-based image sequence noise removal,” IEEE Trans. Image Process., vol. 15, no. 3, pp. 572–581, 2006. [24] L. A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, pp. 338–353, 1965. [25] , E. E. Kerre and M. Nachtegael, Eds., “Fuzzy techniques in image processing,” in Studies in Fuzziness and Soft Computing. Heidelberg, Germany: Physica-Verlag, 2000, vol. 52. [26] S. Weber, “A general concept of fuzzy connectives, negations and implications based on t-norms and t-conorms,” Fuzzy Sets Syst., vol. 11, no. 2, pp. 115–134, 1983. [27] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 313–317, 1996. [28] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast blockmatching motion estimation,” IEEE Trans. Image Process., vol. 9, no. 2, pp. 287–290, 2000. [29] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349–355, 2002. [30] V. Ponomaryov, A. Rosales-Silva, and V. Golikov, “Adaptive and vector directional processing applied to video colour images,” Electron. Lett., vol. 42, no. 11, pp. 623–624, 2006. [31] R. Lukac, “Vector order-statistics for impulse detection in noisy color image sequences,” in Proc. 4th EURASIP-IEEE Region 8 Int. Symp. Video/Image Process. Multimedia Commun., Zadar, Croatia, 2002. [32] R. Lukac, “Adaptive vector median filtering,” Pattern Recognit. Lett., vol. 24, pp. 1889–1899, 2003. [33] S. Schulte, S. Morillas, V. Gregori, and E. E. Kerre, “A new fuzzy color correlated impulse noise reduction method,” IEEE Trans. Image Process., vol. 16, no. 10, pp. 2565–2575, 2007. [34] R. Lukac, K. N. Plataniotis, A. N. Venetsanopoulos, and B. Smolka, “A statistically-switched adaptive vector median filter,” J. Intell. Robot. Syst., vol. 42, no. 4, pp. 361–391, 2005. [35] J. Camacho, S. Morillas, and P. Latorre, “Efficient impulse noise suppression based on statistical confidence limits,” J. Imag. Sci. Technol., vol. 50, no. 5, pp. 427–436, 2006. [36] S. Hore, B. Qiu, and H. R. Wu, “Improved vector filtering for color images using fuzzy noise detection,” Opt. Eng., vol. 42, no. 6, pp. 1656–1664, 2003. [37] R. Lukac and K. N. Plataniotis, “A taxonomy of color image filtering and enhancement solutions,” Adv. Imag. Electron. Phys., vol. 140, pp. 187–264, 2006. [38] R. Lukac, “Adaptive color image filtering based on center-weighted vector directional filters,” Multidimen. Syst. Signal Process., vol. 15, no. 2, pp. 169–196, 2004. [39] Z. H. Ma, H. R. Wu, and B. Qiu, “A robust structure-adaptive hybrid vector filter for color image restoration,” IEEE Trans. Image Process., vol. 14, no. 12, pp. 1990–2001, 2005. [40] V. Chatzis and I. Pitas, “Fuzzy scalar and vector median filters based on fuzzy distances,” IEEE Trans. Image Process., vol. 8, no. 5, pp. 731–734, 1999. [41] S. Morillas, V. Gregori, G. Peris-Fajarns, and P. Latorre, “A fast impulsive noise color image filter using fuzzy metrics,” Real-Time Imag., vol. 11, no. 5–6, pp. 417–428, 2005. [42] S. J. Sangwine and R. E. N. Horne, The Colour Image Processing Handbook. London, U.K.: Chapman & Hall, 1998. [43] J. G. Camarena, V. Gregori, S. Morillas, and A. Sapena, “Fast detection and removal of impulsive noise using peer groups and fuzzy metrics,” J. Vis. Commun. Image Represent., vol. 19, no. 1, pp. 20–29, 2008. [44] S. Morillas, V. Gregori, and A. Hervs, “Fuzzy peer groups for reducing mixed Gaussian-impulse noise from color images,” IEEE Trans. Image Process., vol. 18, no. 7, pp. 1452–1466, 2009. [45] V. Ponomaryov, A. Rosales, and F. Gallegos, “3D filtering of colour video sequences using fuzzy logic and vector order statistics,” in Proc. Advanced Concepts for Intelligent Vision Systems, LNCS 5807, 2001, pp. 210–221. [46] V. F. Kravchenko, V. I. Ponomaryov, and V. I. Pustovoit, “Three-dimensional filtration of multichannel video sequences on the basis of fuzzy-set theory,” Doklady Phys., vol. 55, no. 2, pp. 58–63, 2010. [47] V. Ponomaryov, F. Gallegos-Funes, and A. Rosales-Silva, “Fuzzy directional (FD) filter to remove impulse noise from colour images,” IEICE Trans. Fundament. Electron., Commun. Comput. Sci., vol. E93-A, no. 2, pp. 570–572, 2010.
[48] Z. Xu, H. R. Wu, B. Qiu, and X. Yu, “Geometric features based filtering for suppression of impulse noise in color images,” IEEE Trans. Image Process., vol. 18, no. 8, pp. 1742–1759, 2009. [49] C.-C. Kang and W.-J. Wang, “Fuzzy reasoning-based directional median filter design,” Signal Process., vol. 89, no. 3, pp. 344–351, 2009. [50] V. I. Ponomaryov, “Real-time 2D-3D filtering using order statistics based algorithms,” J. Real-Time Image Process., vol. 1, no. 3, pp. 173–194, 2007. [51] J. G. Camarena, V. Gregori, S. Morillas, and A. Sapena, “Some improvements for image filtering using peer group techniques,” Image Vis. Comput., vol. 28, no. 1, pp. 188–201, 2010. [52] S. Morillas, V. Gregori, and G. Peris-Fajarns, “Isolating impulsive noise pixels in color images by peer group techniques,” Comput. Vis. Image Underst., vol. 110, no. 1, pp. 102–116, 2008. [53] S. Morillas, V. Gregori, G. Peris-Fajarns, and A. Sapena, “Local self-adaptive fuzzy filter for impulsive noise removal in color images,” Signal Process., vol. 88, no. 2, pp. 390–398, 2008. [54] Q. Ma, L. Zhang, and B. Wang, “New strategy for image and video quality assessment,” J. Electron. Imaging, vol. 19, no. 011019, 2010. [55] H. R. Sheikh and A. C. Bovik, “A visual information fidelity approach to video quality assessment,” in Proc. 1st Int. Workshop on Video Process. and Quality Metrics for Consumer Electron., 2005, pp. 23–25.
Tom Mélange was born in Kortrijk, Belgium, in 1984. He received the M.Sc. degree in mathematics from Ghent University, Ghent, Belgium, in 2006. In October 2006, he joined the Department of Applied Mathematics and Computer Science, Ghent University, where he is a member of the Fuzziness and Uncertainty Modeling Research Unit. In 2010 he received the Ph.D. degree with a thesis on fuzzy techniques for noise reduction in video and interval-valued fuzzy mathematical morphology, under Prof. Dr. E. E. Kerre.
Mike Nachtegael was born on February 16, 1976. He received the M.Sc. degree in mathematics from Ghent University, Ghent, Belgium, in 1998. In the same year he joined the Department of Applied Mathematics and Computer Science, where he is a member of the Fuzziness and Uncertainty Modeling Research Unit. In May 2002 he received the Ph.D. in mathematics, on the topic of fuzzy techniques in image processing. In 2002, he became an Assistant Professor in his Department and since 2008 he has held the position of Guest Professor.
Etienne E. Kerre was born in Zele, Belgium, on May 8, 1945. He received the M.Sc. degree in mathematics and the Ph.D. in mathematics from Ghent University, Ghent, Belgium, in 1967 and 1970, respectively. Since 1984, he has been a Lector, and since 1991, a full Professor at Ghent University. He is a referee for more than 30 international scientific journals, and a member of the editorial board of international journals and conferences on fuzzy set theory. He has been an honorary chairman at various international conferences. In 1976, he founded the Fuzziness and Uncertainty Modeling Research Unit (FUM) and since then his research has been focused on the modeling of fuzziness and uncertainty, and has resulted in a great number of contributions in fuzzy set theory and its various generalizations. Especially the theories of fuzzy relational calculus and of fuzzy mathematical structures owe a great deal to him. Over the years he has also been a promotor of 29 Ph.D.s on fuzzy set theory. His current research interests include fuzzy and intuitionistic fuzzy relations, fuzzy topology, and fuzzy image processing. He has authored or co-authored 25 books, and more than 450 papers in international refereed journals and proceedings.
