A new method for augmenting paper documents with electronic information is described that does not modify the format of the paper document in any way. Applicable to both commercially printed documents as well as documents that are output from PC?s, the technique we call Paper-Based Augmented Reality substantially improves the utility of paper. We describe the recognition technology that makes this possible as well as several applications. An implementation on a camera phone is discussed that lets users retrieve data and access links from paper documents to electronic data. Recognition is performed at 4 frames per second on a Treo 700w and support is provided for several user applications, including "clickable paper" -- printed web pages whose appearance is unchanged but that can be navigated with a camera phone.