Journal of Frontiers of Computer Science and Technology ›› 2009, Vol. 3 ›› Issue (3): 303-308.DOI: 10.3778/j.issn.1673-9418.2009.03.008

• 学术研究 • Previous Articles     Next Articles

Fast Operations on Binary Images Encoded by OBDDs

LV Guanfeng1, SU Kaile2, CHEN Qingliang3+, XU Xudong1   

  1. 1. College of Computer Science and Technology, Beijing University of Technology, Beijing 100022, China
    2. Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
    3. Department of Computer Science, Jinan University, Guangzhou 510632, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-05-15 Published:2009-05-15
  • Contact: CHEN Qingliang



  1. 1. 北京工业大学 计算机学院,北京 100022
    2. 北京大学 高可信软件技术教育部重点实验室,北京 100871
    3. 暨南大学 计算机科学系,广州 510632
  • 通讯作者: 陈清亮

Abstract: The ordered binary decision diagram (OBDD) is proposed to encode binary images, which can lead to a considerable amount of storage-saving. Based on it, various operations on binary images encoded as OBDDs are presented, i.e., decoding and set operations (union, intersection, difference, symmetric-difference, inclusion and complement). Experimental results show that those OBDD-based operations are faster than other schemes used to encode binary images.

Key words: ordered binary decision diagram (OBDD), binary images, set operations

摘要: 对利用有序二元判定图OBDD编码二值图像进行了研究,该方法可以节约大量的空间,并在此基础上,提出了各种二值图的算法,包括解码和集合运算(并、交、差、对称差、包含和互补)。实验结果表明这种基于OBDD编码的方法比现有的二值图编码方法效率更高。

关键词: 有序二元判定图, 二值图, 集合运算