Using Ordered Binary-Decision Diagrams for Compressing Images and Image Sequences

摘要

The Ordered Binary-Decision Diagram (OBDD) has been used to reduce the amount ofspace and computation required for verifying digital circuits by removing redundant copies of subfunctions. Similarly, image compression algorithms attempt to reduce their space requirements by finding replicated patterns or features in images. OBDDs would therefore appear to be a good candidate as a data structure for representing images. We show how images can be encoded using Ordered Binary-Decision Diagrams and compare our results to quadtrees. We also show how using this method extends naturally to compressing sequences of related images such those that comprise movies.