Direct Processing of Compressed Data 

Shahram Latifi (PI)
Electrical & Computer Engineering Department
University of Nevada, Las Vegas
Las Vegas, NV 89154-4026

Contact Information

Shahram Latifi
ECE Department
University of Nevada, Las Vegas
4505 Maryland Parkway
Las Vegas, NV 89154-4026 Phone: (702) 895-4016
Fax : (702) 895-4075
Email: latifi@ee.unlv.edu

 

Keywords

CCITT Group III/IV,  Coding scheme,  Data compression,  Document image analysis,  Image processing

Project Award Information

Duration:  3 years
Current award year:   September 1, 1998 - August 31, 1999
Name of the project:  Direct Processing of Compressed Data

Project Summary

Progress in computer and communication technologies allow a large volume of digital information to be exchanged and archived. While the need for data compression is evident, many operations may have to be performed on the uncompressed data. This research investigates the following two problems: (i) develop new algorithms for processing compressed data without fully decompressing them, and (ii) develop new compression algorithms that allow given operations to be rapidly performed on compressed data.

Significance

Data compression research mainly focuses on compression ratio and quality of images recovered from lossy compression methods. Information/image processing research traditionally deals with raw (uncompressed) data. Our project attempts to bridge between data compression and information processing, and promotes a new way of thinking. According to market research firm Gartner Group Inc, document imaging is one of the merging technologies for the upcoming years. The algorithms developed in this project can be utilized by a new generation of document image analysis systems.

Goals, Objectives, and Targeted Activities

We are currently undertaking the following tasks:

Connected component extraction is an important operation in image processing. The problem of connected component extraction directly in the Group IV domain is being investigated. The idea is to detect the corner information existing in the Group IV domain and use this information to develop a new algorithm which is expected to run faster than conventional methods running in the uncompressed domain.

The second task being explored is the conversion of raster images into vector forms. This operation is of interest in many applications ranging from cartography to character recognition. A significant part of the problem is the identification of linear or curved strokes in the binary data. Earlier efforts achieve this objective in the uncompressed domain by using different techniques. The future work can be the extension and improvement of one or more of the conventional methods which will result in a vectorization algorithm that will operate directly on the runlength data. The basic data structure used is the line adjacency graph (LAG) whose nodes correspond to dark segments in the run length code. Problems to be investigated include how to reduce the sensitivity of the thinning algorithms, how to do segmentation of touching characters, and how to use contour tracing for discrimination between characters having similar vectorization.

In the meantime, we have considered applying the emerging technology, wavelet transform, to document image processing. Most segmentations techniques rely on a priori knowledge or assumptions about the generic document layout structure and textual and graphical attributes. However, in many applications it is desirable to have segmentation methods that do not assume any a priori knowledge about document layout. Wavelet transforms have played an important role in classification of texture and abnormalities, and it is hoped they can be exploited efficiently in document image processing.

Indication of Success

We initially investigated the possibility and efficiency of direct processing of compressed data. After an extensive literature review and examining the CCITT G4 scheme, we developed a new compression scheme for binary document images, referred to as Modified G4 or MG4. Compared to other compression standards, this new coding scheme not only offers competitive compression, but also provides flexibility in processing of compressed data. Algorithms for operations such as skew detection, rotation, and connected component extraction are derived and implemented in MG4 compressed domain. These algorithms are shown to run faster than do their traditional counterparts. The MG4 has not been optimized and we are currently looking at ways to improve its efficiency and simplify its implementation.

Project Impact and Output

Human Resources:
This grant has strengthened the PhD program in our department. The following three students have been supported by this project: Ms. Shulan Deng, Ph.D. student, Mr. Bin Zhu, Ph.D. student, and Mr. Jun Zhao, Ph.D student.
Education:
The project has impacted the education within our department in a major way. One graduate course was developed and taught which was mainly based on this project. The grant is also providing interesting and challenging materials for independent research projects and class projects in data compression and image processing. The results of this project were presented in a tutorial given at the IEEE IPCCC'98 and the IEEE local section meeting in November. The results of the project have been presented at on international conference and one workshop. The work on MG4 has been submitted to a journal.
Industry:
The new scheme, once fully optimized, has the potential to revolutionalize the binary document processing in industry; for instance, the fax machine could be one application for this product.

Project References

Area Background

Processing digital images has become widespread recently due to remarkable advances in hardware and software industry. Such images can be produced by converting photographs, printed text, and other media into digital form. Direct acquisition of data in digital form has also been desirable because of the reliability and precision involved in handling digital information.

The CCITT G3/G4 standard, developed based on run-length data, is widely accepted for binary document compression in general and facsimile transmission in particular. By means of this standard, users can interchange and share information efficiently and conveniently. This also leads to the desire to process the image to satisfy specific needs. Traditional algorithms for image processing are based on pixel, which are computationally expensive. This has motivated researchers to consider processing image data in the compression domain.

The algorithms for run-length-based coding schemes are well understood and proven to be efficient. In the CCITT G4 domain, white pass modes can be used to detect skew and image matching, while vertical modes can be searched for possible bar codes. Therefore one can see that the features and structures existing in coded data can be utilized and accessed directly to facilitate image operations.

Area References

Since our research relates to both areas of data compression and information (image) processing, familiarity with data compression techniques and information processing algorithms is essential.
  • K. R. Castleman, Digital Image Processing, Prentice Hall, 1996.
  • K. Sayood, Introduction to Data Compression, Morgan Kaufmann Publishers, Inc., 1996.
  • I. H. Witten, A. Moffat, and T. C. Bell, Managing Gigabytes, Van Nostrand Reinhold, 1994

    • Potential Related Projects

    Data base operations could be done more efficiently if data were stored (perhaps in some sort of compressed form) and queried differently from the classic methods. Specific compression techniques may prove useful in improving performance of data intensive applications such as data mining.