利用OBDD编码的快速二值图算法

doi:10.3778/j.issn.1673-9418.2009.03.008

计算机科学与探索 ›› 2009, Vol. 3 ›› Issue (3): 303-308.DOI: 10.3778/j.issn.1673-9418.2009.03.008

利用OBDD编码的快速二值图算法

吕关锋¹,苏开乐²,陈清亮³⁺,徐旭东¹

1. 北京工业大学计算机学院，北京 100022
2. 北京大学高可信软件技术教育部重点实验室，北京 100871
3. 暨南大学计算机科学系，广州 510632

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-05-15 发布日期:2009-05-15
通讯作者: 陈清亮

Fast Operations on Binary Images Encoded by OBDDs

LV Guanfeng¹, SU Kaile², CHEN Qingliang³⁺, XU Xudong¹

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

摘要/Abstract

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

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

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

吕关锋1 ,苏开乐2 ,陈清亮3+ ,徐旭东1 . 利用OBDD编码的快速二值图算法[J]. 计算机科学与探索, 2009, 3(3): 303-308.

LV Guanfeng¹, SU Kaile², CHEN Qingliang³⁺, XU Xudong¹. Fast Operations on Binary Images Encoded by OBDDs[J]. Journal of Frontiers of Computer Science and Technology, 2009, 3(3): 303-308.

利用OBDD编码的快速二值图算法

Fast Operations on Binary Images Encoded by OBDDs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics