A document image analysis toolbox, including a collection of data structures and algorithms to support a variety of applications, is described in this paper. An experimental environment is built to allow developers to develop, test and optimize their algorithms and systems. The Document Attribute Format Specification (DAFS) is used as the internal data representation in the environment. The architecture allows for convenient experimentation to evaluate the performance of different algorithms and sequences of modules. Appropriate and quantitative performance metrics for each kind of information a document analysis technique infers have been developed. The toolbox provides a set of algorithms from which the document image analysis applications can be constructed. The performance of each algorithm has been evaluated based on those metrics and the UW-III document image database which contains a total of 1600 English document images randomly selected from scientific and technical journals. We have constructed a prototype of the document analysis system and demonstrated its flexibility and functionality on different applications.