Design, Implementation and Evaluation of Multi-terminal Binary Decision Diagram based Binary Fuzzy Relations
الموضوعات :Hamid Alavi Toussi 1 , Bahram Sadeghi Bigham 2
1 - Department of Computer Science, Aarhus University, Aarhus, Denmark
2 - Department of Computer Sciences, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran
الکلمات المفتاحية: Boolean Functions , BDD, MTBDD , Binary Fuzzy Relations , Fuzzy Connectedness , Image Segmentation,
ملخص المقالة :
Elimination of redundancies in the memory representation is necessary for fast and efficient analysis of large sets of fuzzy data. In this work, we use MTBDDs as the underlying data-structure to represent fuzzy sets and binary fuzzy relations. This leads to elimination of redundancies in the representation, less computations, and faster analyses. We also extended a BDD package (BuDDy) to support MTBDDs in general and fuzzy sets and relations in particular. Representation and manipulation of MTBDD based fuzzy sets and binary fuzzy relations are described in this paper. These include design and implementation of different fuzzy operations such as max, min and max-min composition. In particular, an efficient algorithm for computing max-min composition is presented.Effectiveness of our MTBDD based implementation is shown by applying it on fuzzy connectedness and image segmentation problem. Compared to a base implementation, the running time of the MTBDD based implementation was faster (in our test cases) by a factor ranging from 2 to 27. Also, when the MTBDD based data-structure was employed, the memory needed to represent the final results was improved by a factor ranging from 37.9 to 265.5. We also describe our base implementation which is based on matrices.
[1] E. Clarke, O. Grumberg, and D. Long. Symbolic Model Checking for Sequential Circuit Verification. In IEEE Transactions on Computer Aided Design, 1994.
#[2] Marc Berndl, OndˇrejLhot´ak, FengQian, Laurie Hendren, and NavindraUmanee. Points-to analysis using BDDs. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Inplementation, pages 103–114. ACM Press, 2003.
#[3] John Whaley and Monica Lam. Clonning-based context-sensitive Pointer Alias analysis using Binary Decision Diagrams. In Proceeding of PLDI, 2004.
#[4] OndˇrejLhot´ak, Stephen Curial, and Jos´e Nelson Amaral. Using XBDDs and ZBDDs in points-to analysis. Software, Practice and Experience, 39(2):163–188, 2009.
#[5] WatisLeelapatra, KanchanaKanchanasut, and ChidchanokLursinsap. Displacement BDD and geometric transformations of binary decision diagram encoded images. Pattern Recognition Letters, 29:438–456, March 2008.
#[6] Mike Starkey, Randy Bryant, and Y Bryant. Using ordered binary-decision diagrams for compressing images and image sequences. Technical report, CMU-CS, 1995.
#[7] Edmund M.and Fujita Clarke, M., McGeer, P C., McMillan, K., Yang, J C-Y, and X Zhao. Multi-Terminal Binary Decision Diagrams: An Efficient Data-Structure for Matrix Representation. Formal Methods in System Design, 1997.
#[8] R. I. Bahar, E. A. Frohm, C. M. Gaona, E. Macii, A. Pardo, and F. Somenzi. Algebraic Decision Diagrams and Their Applications. Formal Methods in System Design, 10, 1997.
#[9] Jorn Lind-Nielsen. BuDDy library. http://sourceforge.net/projects/buddy/, 2002.
#[10] D. Bugaychenko. On application of multi-rooted binary decision diagrams to probabilistic model checking. In Verification, Model Checking, and Abstract Interpretation, pages 104–118. Springer, 2012.
#[11] Ben Hardekopf and Calvin Lin. Flow-sensitive pointer analysis for millions of lines of code. In Code Generation and Optimization (CGO), 2011 9th Annual IEEE/ACM International Symposium on, pp. 289-298. IEEE, 2011.
#[12] D. Yu. Bugaychenko and I. P. Soloviev. Application of multiroot decision diagrams for integer functions. MATHEMATICS, 43(2):92–97, 2010.
#[13] Randal E. Bryant. Graph Based Algorithm for Boolean function manipulation. In IEEE Transactions on Computers, 1985.
#[14] L. A. Zadeh. Fuzzy Sets. Information and Control, pages 338–353, 1965.
#[15] ShivaniAgarwal. UIUC Image Database for Car Detection. http://cogcomp.cs.illinois.edu/Data/Car/, April 2002. Accessed: 2012-08-20.
#[16] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics. In Proceeding of 8th International Conference on Computer Vision, volume 2, pages 416–423, July 2001.
#[17] Jayaram K. Udupa and Punam K. Saha. Fuzzy Connectedness and Image Segmentation. In Proceeding of the IEEE, volume 91, 2003.
#[18] Pedro F. Felzenszwalb. Efficient Graph-Based Image Segmentation. Journal of Computer Vision, 59(2), 2004.
#[19] M. Delgado, N. Mann, M. Martn-Bautista, D. Snchez, and M. Vila. Mining fuzzy association rules: An overview. Soft Computing for Information Processing and Analysis, 164:351–373, 2005.
#[20] Ulrich Bodenhofer, EykeHllermeier, Frank Klawonn, and Rudolf Kruse. Special issue on soft computing for information mining. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 11:397–399, 2007.
#[21] AmelBorgi and Herman Akdag. Knowledge based supervised fuzzy-classification: An application to image processing. Annals of Mathematics and Artificial Intelligence, 32(1-4):67–86, 2001.
#[22] Ariel Gmez, Carlos Len, Jorge Ropero, Alejandro Carrasco, and JoaqunLuque. Sabio: Soft agent for extended information retrieval. Applied Artificial Intelligence, 27(4):249–277, 2013.
#[23] Hamid A. Toussi and BahramSadeghiBigham, Design, Implementation and Evaluation of MTBDD based Fuzzy Sets and Binary Fuzzy Relations, preprint arXiv:1403.1279 [cs.DS], [Online]. Available: http://arxiv.org/abs/1403.1279
#[24] Hamid A. Toussi and Abbas Rasoolzadegan, Flow-sensitive points-to analysis for Java programs using BDDs, In Proceeding of 4th International Conference on Computer and Knowledge Engineering (ICCKE), pp.380,386, 29-30 Oct. 2014
#[25] Ben Hardekopf and Calvin Lin. Semi-sparse flow-sensitive pointer analysis, In ACM SIGPLAN Notices, vol. 44, no. 1, pp. 226-238. ACM, 2009.
