comparison of three defuzzification methods in the application of Jpeg

C. J. Wu

Dept. of Library and Information Science

Fu-Jen Catholic Univ.

Hsin-Chuang, ROC 242

E-mail: lins1022@fujens.fju.edu.tw

 

A.H. Sung

Department of Computer Science

New Mexico Tech.

Socorro, NM 87801

 

The performance of three defuzzification methods (MOI, mean of inversion; COA, center of area; and MOM, mean of maximum) with respect to accuracy and convergence speed is studied. Unlike MOM and COA, MOI defuzzifies the output of each fired rule separately instead of superimposing the outputs of fired rules before defuzzification. As a result, as suggested by our experiments, MOI is less sensitive to the contents of decision tables (or rule bases) in terms of accuracy as suggested by the experiments. The simulation results based on 15 USC pictures indicate that MOI has the best performance on accuracy. Additionally, the largest performance difference between MOI and COA is in the steep slope area where MOI is obviously superior to COA in the aspect of convergence speed. MOM has the worst performance with respect to both accuracy and convergence speed.

 

I. Introduction

Although the lossy JPEG model is one of the most widely used digital image compression techniques for both grayscale and color still images [1], the compression results are not predictable in advance due to a wide variety of image data. For a picture of MxN pixels with P grayscale levels, there are up to possible combinations. With this extremely large number of combinations, it is very difficult for any lossy compression model to predict the relation of its parameters to the compression results, e.g., mean square error. Therefore, in a sense, the compression and distortion ratios depend heavily on the source image data.

Fig. 1 shows the relation of the JPEG input parameter Quality and the distortion ratio AGE (average grayscale error) on 15 USC pictures using the JPEG model developed by Independent JPEG Group. Those 15 USC pictures include eight 256x256 pictures (Girl-1, Couple, Lady, Girl-II, House, Tree, Ball-I, and Ball-II) and seven 512x512 pictures (Splash, Girl-III, Baboon, Lena, F16, Park, and Pepper). The ratios of SNR and AGE are defined by

(1)

(2)

where G is the maximum grayscale levels of pictures. MSE (mean-square-error) is defined as

(3)

and MAE (mean-absolute-error) is defined as

(4)

where and are the corresponding frames in the original and reconstructed pictures, respectively, N is the dimension of the input vector I (or frame M), and F is the total number of frames. As seen in Fig. 1, each image has its own unique curve which can only be known via simulations.

For achieving better trade-off between distortion and compression ratios, ad-hoc methods such as trial-and-error are clearly not feasible since they may be labor-intensive and time-consuming. Another common technique uses BPP (bits-per-pixel) as the index for picture quality [1]. However, like the trial-and-error approach, the disadvantage of this technique is that human intervention is unavoidable because the actual results can vary significantly from image to image. Apparently, in order to achieve efficiency, some automatic control mechanism must be incorporated with the JPEG model to find proper input values for desired outputs.

Fuzzy logic was introduced by Zadeh in [2-3] and used by Mamdani and Assilian to control dynamic systems in [4-5]. Since then, fuzzy logic has been successfully applied to many automatic control applications (especially for non-linear ill-defined systems) [6-14]. Although the effect of fuzzy controller components on the overall performance of a controller is not entirely clear, the design of fuzzy controllers is well known for its simplicity as mentioned in [15].

Incorporating a fuzzy controller with the JPEG model to achieve the automatic control during compression process on the source side was proposed in [16-17]. The relation of JPEG (including coder and decoder) and the fuzzy controller on source side is depicted in Fig. 2. Since the image quality is our primary concern, the distortion ratio average-grayscale-error (AGE) as defined in Eq. 2 is used to indicate the reconstructed image quality.

Section II describes the structure of the designed fuzzy controller. The comparison of MOI, MOM, and COA methods in terms of accuracy and convergence speed in the application of JPEG is given in Sections III and IV. Conclusions and discussions are presented in Section V.

 

II. The fuzzy controller

As can be observed from Fig. 1, the AGE vs. (input parameter) Quality functions for the 15 USC images are all monotone, with the exception of a few images that show slight non-monotonicity toward one end of the plot. Therefore, our aim is to design a fuzzy controller that can deal with a large class of monotone functions so it is not necessary to change the controller's configuration from one function to another. Fortunately, by taking advantage of the monotone function property, convergence can be guaranteed by forcing the current feedback adjustment to be no large than the previous adjustment except in the case of overshooting where . In this application, the minimum subtraction unit u is 1.

The internal structure of the designed fuzzy controller is depicted in Fig. 3. The two inputs, and , to the fuzzy controller at the time t are defined as

(5)

(6)

The universal set of , E, is the interval of real numbers while the universal set of , Q, is the interval of integer numbers.

 

 

In general, the membership function of a fuzzy subset A, , in the universal set X is defined [18-19] as

(7)

where is the interval of real numbers with 0 and 1 being the minimum and maximum membership values, respectively. In this work, seven fuzzy subsets are used: PB (positive big), PM (positive medium), PS (positive small), ZE (zero), NS (negative small), NM (negative medium), and NB (negative big).

For an input crisp value x, the membership value of a fuzzy subset is given by the membership functions

(8)

(9)

(10)

where C, L, and R are the central value, the left boundary, and the right boundary, respectively, and A={NM, NS, ZE, PS, PM}. For example, the membership functions of the form (L, C, R) used for the input and the entries of the decision tables are

Group 0:

NB(-100, -50, -25), NM(-40, -25, -10), NS(-20, -10, 0), ZE(-5, 0, 5), PS(0, 10, 20), PM(10, 25, 40), PB(25, 50, 100)

As for the input , the membership functions used are

Group 1:

NB(-100, -6, -3), NM(-5, -3, -1), NS(-2, -1, 0),

ZE(-0.5, 0, 0.5),

PS(0, 1, 2), PM(1, 3, 5), PB(3, 6, 100)

One of the decision tables used by the fuzzy controller in this work is given in Table 1. The confidence value of a decision table entry ij, , is calculated using the fuzzy-min (or intersection) operator

(11)

where is a membership function defined in Eqs. 8-10.

 

 

In the literature [14, 20-21], the two most popular defuzzification methods are the mean-of-maximum (MOM) and the center-of-area (COA) methods [21]. For MOM, the crisp output is the mean value of all points whose membership values are maximum. In the case of the discrete universal set W, MOM is defined as

(MOM)(12)

where and n is the number of such support values. As for COA, the crisp output is the center of gravity of distribution of membership function . In the case of the discrete universal set W, COA is defined as

(COA) (13)

where n is the number of elements of the fuzzy set C, and . The comparison of these two defuzzification methods can be seen in [22-28]. Overall, COA yields better results than MOM [22-23, 28]. In addition, other defuzzification strategies can be found in [28, 29-33].

Unlike MOM and COA, MOI defuzzifies each fired rule output individually instead of superimposing fired rule outputs before defuzzification. As shown in Eq. 14, the MOI method for (the feedback from the controller to JPEG) is calculated as

(MOI) (14)

where K and L are the number of rows and columns in the decision table, respectively. is decided by the following algorithm:

Step 1. Calculate the corresponding crisp values T of the fuzzy membership value .

(15)

where is the inverse function of and A is the corresponding fuzzy subset of . Note that there might be more than one value generated by .

Step 2. Adjust each inverse value T for guaranteed convergence.

(16)

Step 3. Pick the largest absolute value of . If , ; otherwise, .

For guaranteed convergence, will be no larger than . Therefore, at step t, is adjusted (for the MOI, the COA, and the MOM methods) as follows:

(i) ,

(1) Overshooting occurred:

(2) No overshooting:

(ii) ,

where m is a positive integer, u is the measure unit of c , and in this work.

At last, the new input is calculated as

(17)

When , a special signal STOP is generated to stop the adjusting process.

III. Simulation results

Experiments were performed on 15 USC images which have been widely used in image compression experiments and include eight 256x256 images and seven 512x512 images with 256 grayscales. The JPEG package used in our experiments was developed by the Independent JPEG Group with a fuzzy controller designed by the authors [16-17]. In this work, ten random initial values (38, 58, 13, 15, 51, 27, 10, 19, 12, and 86) of q generated by the random number generation function rand() in the standard C programming environment are used to test the accuracy of the fuzzy controller. The function used to describe the behavior of JPEG is

(18)

where g is the generated AGE, and q is the value of parameter Quality. To measure the performance of the fuzzy controller, we now define successful trials and unsuccessful trials.

Definition 1. Successful Trials: We say the fuzzy controller succeeds at a trial if either of two conditions is met:

(1) The final value is in the target range, that is, where T is the TGE and is the tolerance.

(2) If no value of is inside the interval of target range, and the closest values on both sides of target range are and , respectively, then either or where is the final value of q after convergence.

Definition 2. Unsuccessful Trials: Any trial which does not satisfy the conditions above.

Initially, Table 1 is used as the decision table. For the target grayscale error (TGE) 1.5, the simulation results of the configuration above on those 15 USC images for MOI, MOM, and COA are given in Table 2. As shown in Table 2, based on those 15 images, only the fuzzy controller using MOI has no failure for all 150 trials; thus, MOI has the best performance on accuracy. The unsuccessful trials (UST) of MOM and COA are 134 and 41 (out of 150), respectively.

 

 

To test the performance of the fuzzy controller in the lower distortion area, we repeat the same experiment with . The simulation results for MOI, MOM, and COA are given in Table 3. According to Table 3, MOI still has the best performance in terms of accuracy while MOM has the worst performance.

 

 

As for the convergence speed, in the case of TGE=1.5, the average loops per trial of MOI, MOM, and COA are 8.26, 2.62, and 5.293, respectively. Clearly, the slow convergence of MOI is the price paid for its accuracy. However, this disadvantage of MOI is dramatically offset when a small amount of tolerance is used, as shown in Tables 4 and 5. More specifically, in the case of TGE=1.5 with tolerance 0.025, the average loops per trial of MOI and COA are 5.38 and 4.7, respectively. Although COA has slightly faster convergence, it has 27 unsuccessful trials out of 150 while MOI has no failure. In addition, based on Tables 2-5, MOI is the best choice if the accuracy is the primary concern.

 

 

By closely examining the failure of COA on accuracy, we hypothesize that arise the failure coming from the combined effects of the numerator using a sum (or an integral in the case of continuous distribution) in Eq. 13 and too many fuzzy subset ZE's in Table 1. As a result, sometimes the numerator becomes 0, and the adjustment process will be forced to stop when q gets close to the target range.

 

 

In order to overcome this problem for COA, Table 6 is used to rerun the simulations to test our hypothesis. As seen in Table 6, those fuzzy subsets ZE's in the upper part of column 3 in Table 1 are replaced with the fuzzy subset PS's while those in the lower part of column 4 are replaced with the fuzzy subsets NS's.

 

 

As can be seen in Table 7, there is no failure for COA using Table 6 in both cases of TGE=1.5 and TGE=1.0 with tolerance 0.025. This example clearly shows that decision tables can affect the controller performance and are closely related to defuzzification methods. Note that MOI also has no failure when it uses Table 6. This indicates that MOI is less sensitive to the design of decision tables than COA.

 

 

 

 

Although the revised decision table is able to help COA achieve 100% accuracy as shown in Table 7 in both cases of TGE=1.5 and TGE=1.0, it has little impact on MOM in terms of accuracy, as shown in Table 8. MOM has 132 and 140 unsuccessful trials in the cases of TGE=1.5 and 1.0, respectively. This suggests that MOM is not suitable in the application of JPEG.

 

 

IV. performance comparison of the MOI and the COA methods for different membership functions

To show how the choice of membership function affects the performance of the COA and the MOI methods, another three groups of membership functions for the input are used for this experiment while the other components of the designed controller remain unchanged.

Group 2:

NB(-100, -3, -1.5), NM(-2.5, -1.5, -0.5), NS(-1, -0.5, 0), ZE(-0.25, 0, 0.25), PS(0, 0.5, 1), PM(0.5, 1.5, 2.5), PB(1.5, 3, 100).

Group 3:

NB(-100, -12, -6), NM(-10, -6, -2), NS(-4, -2, 0), ZE(-1, 0, 1), PS(0, 2, 4), PM(2, 6, 10), PB(6, 12, 100).

Group 4:

NB(-100, -1.5, -0.75), NM(-1.25, -0.75, -0.25), NS(-0.5, -0.25, 0), ZE(-0.125, 0, 0.125), PS(0, 0.25, 0.5), PM(0.25, 0.75, 1.25), PB(0.75, 1.5, 100).

As seen above, the relation of these 3 groups of membership functions and Group 1 is that Groups 2 and 4 of membership functions for the input are moved close to the center of input distribution 0 while Group 4 of membership functions are moved away from the center 0. In addition, the bases of those triangular membership functions are changed from group to group. In addition, unless specified otherwise, COA uses Table 6 while MOI uses Table 1 because COA can yield more accurate results under Table 6 and MOI has faster convergence using Table 1.

The simulation results are given in Table 9 for the case of tolerance 0.025. As seen in Table 9, the convergence speed will be affected by the groups of membership functions used. For example, there are around 4 loops difference between Groups 2 and 3 of membership functions for both of MOI and COA in the case of TGE=1.0.

 

In order to compare the performance of MOI and COA in the steep slope area, another test point (5.0 of AGE) is selected. As seen in Fig. 1, 5.0 of AGE is in a very steep area. The following fuzzy subsets are used for and, respectively.

Group Q: (for)

NB(-100, -50, -20), NM(-45, -25, -15), NS(-20, - 10, 0), ZE(-5, 0, 5), PS(0, 10, 20), PM(5, 25, 45), PB(20, 50, 100).

Group 5:

NB(-100, -6, -2.5), NM(-5.25, -3, -0.75), NS(-2, -1, 0), ZE(-0.5, 0, 0.5), PS(0, 1, 2), PM(0.75, 3, 5.25), PB(2.5, 6, 100).

As shown in Table 10, MOI is faster than COA at around 4.5 loops. This indicates that MOI is certainly superior to COA in the steep slope curve.

 

V. Conclusions and Discussions

JPEG is currently one of the widely used image compression techniques for grayscale and color still pictures. However, the large variety of image source data makes the prediction of control parameters vis-a-vis reconstructed image quality very difficult for lossy models. To lower the cost and achieve efficiency, a kind of automatic control mechanism must be incorporated into JPEG.

From the design point of view, the fuzzy controller is well known for its simplicity as shown in this work. However, since we are dealing with a collection of functions, it is worthwhile to point out that the following two special design restrictions are needed to simultaneously achieve the guaranteed convergence and good performance for this application of JPEG.

(1) The present adjustment is no larger than the previous adjustment except in the case of overshooting, that is, .

(2) The present adjustment is smaller than the previous adjustment in the case of overshooting, that is, where the minimum subtraction unit u is 1 in this application.

The first criterion contributes to good performance while the second guarantees convergence.

The summary of the comparisons among MOI, COA, and MOM methods on the application of JPEG and those 15 USC images is as follows:

(1) There is a close relation between decision tables and defuzzification methods; however, the degree of dependency varies from defuzzification method to defuzzification method. Clearly, the less sensitive method is preferred if accuracy is the primary concern. MOI can yield more accurate results since it is the least sensitive defuzzification method with respect to the contents of the decision tables.

(2) MOM performed badly in terms of accuracy, it does not seem suitable for this application, JPEG.

(3) When COA is used, the fuzzy subset ZE should be used judiciously because COA is sensitive to the ZE's in the decision table.

(4) MOI is superior to COA in the steep slope curve as shown in Fig. 1 at 5.0 of AGE.

As seen in Fig. 1, in the application of JPEG, the input-output relation can be treated as monotone functions most of the time. For monotone functions, as shown in [34-35], the convergence and accuracy can be guaranteed under the MOI defuzzification method. Some remarks related to this works are as follows:

(1) As mentioned above, it has been proved that the fuzzy controller with MOI can achieve guaranteed accuracy which, as far as we can determine, has not been shown to be true with COA.

(2) It is also clear that with the proof of guaranteed accuracy on the MOI method, the single most important advantage of conventional PID controllers is no longer unmatched, at least for monotone functions.

(3) The MOI method is less sensitive to the configuration of controller than conventional PID (proportional-integral-derivative) controllers as suggested by simulation results in [36]. In general, the decision making in a fuzzy controller is made by all its components. Hence, the fuzzy controller may be hard to analyze but less sensitive to the change of each component. On the other hand, PID controllers only rely on few coefficients; therefore, as mentioned in [37], PID controllers are usually very sensitive to their coefficients.

(4) The strength of fuzzy controllers is its ease of design. Thus, we didn't specifically discuss how we chose those configurations--they were chosen based on common sense and simple experience with image compression. In other words, they are two possible choices out of hundreds of thousands possible configurations which can always yield 100% accuracy as proved in [34-35].

References

  1. G. K. Wallace, "The JPEG still Picture Compression Standard," Communications of the ACM, vol. 34, no. 4, pp. 30-44, 1991.
  2. L.A. Zadeh, "Fuzzy Sets," Inform. Contr., vol. 8, pp. 338-353, 1965.
  3. L.A. Zadeh, "Outline of a New Approach to the Analysis of Complex Systems and Decision Processes," IEEE Trans. Syst. Man. Cybern., vol. 3, no. 1, pp. 28-44, 1973.
  4. E.M. Mamdani, "Applications of Fuzzy Algorithms for Simple Dynamic Plants," Proc. IEEE, vol. 21, no. 12, pp.1585-1588, 1974.
  5. S. Assilian, "Artificial Intelligence in the control of Real Dynamic Systems," Ph.D. Thesis, Queen Mary College, London, 1974.
  6. M. Sugeno, editor. Industrial Applications of Fuzzy Control. Amsterdam: North-Holland, 1985.
  7. T. Shingu and E. Nishimori, " Fuzzy Based Automatic Focusing System for Compact Camera," Proc. of the Third International Fuzzy Systems Association (IFSA), pp. 436-439, 1989.
  8. S. Yasunobu and G. Hasegawa, " Evaluation of an Automatic Crane Operation System Based on Predictive Fuzzy Control," Control Theory and Advanced Technology, vol. 2, pp. 419-432, 1986.
  9. H. Takahashi, K. Ikeura, and T. Yamamori, "5-speed Automatic Transmission Installed Fuzzy Reasoning," Proc. of International Fuzzy Engineering Symposium '91 (IFES'91), pp. 1136-1137, 1991.
  10. W.I.M. Kickert and H.R. Van Nauta Lemke, "Application of a Fuzzy Controller in a Warm Water Plant," Automatica, vol. 12, pp. 301-308, 1976.
  11. C.P. Pappis and E.H. Mamdani, " A Fuzzy Logic Controller for a Traffic Function," IEEE Trans. Syst. Man. Cybern., vol. 7, no. 10, pp. 707-717, 1977.
  12. G.A. Carter and D.A. Rutherford, "A Heuristic Adaptive Controller for a Sinter Plant," IFAC Symp. on Automation in Mining, Met and Met Processing, Johannesburg, pp. 315-324, 1976.
  13. R.M. Tong, "A Control Engineering Review of Fuzzy Systems, " Automatica, vol. 13, pp. 559-568, 1977.
  14. C.C. Lee, "Fuzzy Logic in Control Systems: Fuzzy Logic Controller," IEEE Trans. Syst. Man. Cybern., vol. 20, no. 2, pp. 404-435, 1990.
  15. E.M. Mamdani, "Twenty Years of Fuzzy Control: Experiences Gained and Lessons Learnt," Proc. IEEE International Conf. on Fuzzy Systems, pp. 339-344, 1993.
  16. C.J. Wu and A.H. Sung, "The Application of Fuzzy Controller to JPEG," Electronics Letters, vol. 30, no. 17, pp. 1375-1376, 1994.
  17. C.J. Wu and A.H. Sung, "The Application of Fuzzy Logic to JPEG," IEEE Trans. Consumer Electronics, vol. 40, no. 4, pp. 976-984, 1995.
  18. G. J. Klir and T. A. Folger, Fuzzy Sets, Uncertainty, and Information, Englewood Cliffs, NJ: Prentice-Hall, 1988.
  19. B. Kosko, Neural Networks and Fuzzy Systems: A Dynamical Systems Approach to machine Intelligence, Englewood Cliffs, NJ: Prentice-Hall, 1992.
  20. W. Pedrycz, Fuzzy Control and Fuzzy Systems, Somerset, England: Research Studies Press Ltd., 1993.
  21. H.R. Berenji, "Fuzzy Logic Controllers," in An Introduction to Fuzzy Logic Applicatons in Intelligent Systems, R.R. Yager and L.A. Zadeh, Boston: Kluwer Academic Publishers, pp. 69-96, 1992.
  22. M. Braae and D.A. Rutherford, "Fuzzy Relations in a Control Setting," Kybernetes, vol. 7, no. 3, pp. 185-188, 1978.
  23. L.I. Larkin, "A Fuzzy Logic Controller for Aircraft Flight Control," in Industrial Applications of Fuzzy Control, M. Sugeno, Ed., Amsterdam: North-Holland, pp. 87-104, 1985.
  24. E.M. Scharf and N.J. Mandic, "The Application of a fuzzy controller to the control of a multi-degree-freedom robot arm," in Industrial Applications of Fuzzy Control, M. Sugeno, Ed., Amsterdam: North-Holland, pp. 41-62, 1985.
  25. W.J.M. Kickert and E.H. Mamdani, "Analysis of a fuzzy logic controller," Fuzzy Sets Syst., vol. 1, no. 1, pp. 29-44, 1978.
  26. J.B. Kiszka, M.E. Kochanska, and D.S. Sliwinska, "The Influence of Some Parameters on the Accuracy of Fuzzy Model," in Industrial Applications of Fuzzy Control, M. Sugeno, Ed., Amsterdam: North-Holland, pp. 187-230, 1985.
  27. R.M. Tong, "Synthesis of Fuzzy Models for Industrial Processes," Int. Gen. Syst., vol. 4, pp. 143-162, 1978.
  28. T.A. Runkler and M. Glesner, "A Set of Axioms for Defuzzification Strategies Towards a Theory of Rational Defuzzification Operators," Proc. IEEE International Conf. on Fuzzy Systems, pp. 1161-1166, 1993.
  29. S. Mabuchi, "A Proposal for a Defuzzification Strategy by the Concept of Sensitivity Analysis," Fuzzy Sets Syst., 55, pp. 1-14, 1993.
  30. R. R. Yager and D. Filev, "On the Issue of Defuzzification and Selection Based on a Fuzzy Set," Fuzzy Sets Syst., 55, pp. 255-274, 1993.
  31. D. Filev and R. R. Yager, "An Adaptive Approach to Defuzzification Based on Level Sets," Fuzzy Sets Syst., 54, pp. 355-360, 1993.
  32. D. Filev and R. R. Yager, "Generalized Defuzzification Method nia BADD Distribution," Internat. J. Intelligent Systems, vol. 6, pp. 687-697, 1991.
  33. O. Song and G. Bortolan, "Some Properties of Defuzzification Neural Networks," Fuzzy Sets Syst., 61, pp. 83-89, 1994.
  34. C.J. Wu and A.H. Sung, "A General Purpose Fuzzy Controller for Monotone Functions," IEEE Trans. Syst. Man. Cybern, vol. 26, no. 5, pp. 803-808, 1996.
  35. C.J. Wu, "A General Purpose Fuzzy Controller for JPEG and Monotone functions," Ph.D. Thesis, New Mexico Tech., Socorro, New Mexico, 1995.
  36. C.J. Wu, "Performance Comparison of Fuzzy and Proportional Controllers in the Application of Image Compression," Proc. of IEEE Int. Conference on Systems, Man and Cybernetics (Beijing, PRC), pp. 378-383, 1996.
  37. D. A. Cassell, Microcomputer and Modern Control Engineering, Reston, Virginia:Reston Publishing Company, 1983.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cheng-Juei Wu was born in Tainan, Taiwan, ROC, in 1962. He received the M.S. and Ph.D. degrees in Computer Science from the New Mexico Inst. of Mining & Technology in 1991 and 1995, respectively. He is currently an Associate Prof. of Library & Information Science at Fu-Jen Univ., Taiwan, ROC. His current research interests are Information Retrieval, Fuzzy Systems, Neural Networks, and Image Compression. He is a member of IEEE and ACM.

 

 

 

Andrew H. Sung is currently an Associate Prof. of Computer Science at New Mexico Inst. of Mining and Technology.