Image analysis – Pattern recognition – Classification
Reexamination Certificate
1996-03-29
2002-06-11
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Classification
C382S240000, C382S253000
Reexamination Certificate
active
06404923
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to digital image analysis and, more particularly, to a low-level digital image classification system. A major objective of the present invention is to provide for fast, effective, low-level image classification that can be implemented with reduced hardware/software requirements.
Humans engage in image classification whenever they look at an image and identify objects of interest. In images, humans readily distinguish: humans from other objects, man-made features from natural features, and text from graphics, etc. With specialized training, humans are adept at recognizing significant features in specialized images such as satellite weather images and medical tomographic images.
Suitably equipped machines can be programmed and/or trained for image classification, although machine recognition is less sophisticated than human recognition in many respects. Computerized tomography uses machine classification to highlight potential tumors in tomographic images; medical professionals examining an image for evidence of tumors take advantage of the highlighting to focus their examination. Machine classification is also used independently; for example, some color printer drivers classify image elements as either text or graphics to determine an optimal dithering strategy for simulating full-range color output using a limited color palette.
Most machine image classification techniques operate on digital images. Digital images are typically expressed in the form of a two-dimensional array of picture elements (pixels), each with one (for monochromatic images) or more (for color images) values assigned to it. Analog images to be machine classified can be scanned or otherwise digitized prior to classification.
The amount of computational effort required for classification scales dramatically with the number of pixels involved at once in the computation. The number of pixels is the product of image area and image resolution, i.e., the number of pixels per unit area. As this suggests, faster classification can be achieved using lower resolution images, and by dividing an image into small subimages that can be processed independently; the total computation involved in classifying the many subimages can be considerably less burdensome than the computation involved in classifying an image as a whole. On the other hand, if the subimages are too small to contain features required for classification, or if the resolution is too low for relevant features to be identified, classification accuracy suffers.
Successful “low-level” classification techniques depend on finding suitable tradeoffs between accuracy and computational efficiency in the selection of image resolution and in subimage area. In general, subimage area can be imposed by the classification technique, whereas resolution is typically a given. In such cases, subimage area is typically selected to be the minimum required for acceptably accurate classification. The selected subimage area then determines the number of pixels per subimage, and thus the amount of computation required for classification.
When image resolution is optimal for classification, the number of pixels required per subimage can be surprising small. For example, 8×8-pixel subimages are typically sufficient for distinguishing text from graphics; 4×4-pixel subimages are typically sufficient to distinguish man-made from natural objects in an aerial image; and 2×2-pixel subimages can be used to distinguish potential tumors from healthy tissue in a computerized tomographic image. Of course, subimages with greater numbers of pixels must be used if the image resolution is greater than optimal for classification purposes.
Low-level classification strives to assign each subimage to a class. Ideally, the assignment would be error free. When this cannot be done, the goal is to minimize the likelihood of error, or, if some errors are more costly than others, minimize the average cost of the errors. Bayes decision theory and related statistical approaches are used to achieve the goals. The computations that are required must be iterated for each block. While it is reduced relative to full-view classification, the amount of computation required for low-level classification can still be excessive.
Technological progress has provided both more powerful computers and more efficient image classification techniques. Rather than satisfy the demand for efficient image classification, these advances have fueled demand by proliferating the use of computerized images and raising expectations for real-time image processing.
Recent developments on the Internet, particularly, the World Wide Web, illustrate the demand for communication of images, particularly in high-bandwidth applications such as interactive video and video conferencing. Internet providers targeting a large audience often must transmit not only the images but also applications, e.g., browsers, for viewing and interacting with the images. The unsophisticated consumers of these images are often not tolerant of delays that might be involved in any classification activities associated with these images. Furthermore, the image providers cannot assume that their consumers will have hardware dedicated to the classification activities, nor can the providers conveniently distribute such dedicated hardware.
Thus, there is an increasing need for more efficient image classification techniques. Preferably, such techniques would achieve high performance even in software implementations that require only a fraction of the processing power available on inexpensive home and desktop computers. When embodied as software, the techniques should be readily distributed by image providers. Whether hardware or software based (or both), improved image classification techniques are desired to enhance all the applications that depend on them.
SUMMARY OF THE INVENTION
The present invention provides an image classification system comprising means for converting an image into vectors and a lookup table for converting the vectors into class indices. Each class index corresponds to a respective class of interest. Performing classification using tables obviates the need for computations, allowing higher classification rates.
The lookup table can be single-stage or multi-stage; a multi-stage lookup table permits classification to be performed hierarchically. The advantage of the multi-stage table is that the memory requirements for storing the table are vastly reduced at the expense of a small loss of classification accuracy.
Multi-stage tables typically have two to eight stages. Only the last stage table operates on blocks of the size selected to allow acceptably accurate classification. Each preceding stage operates on smaller blocks than the succeeding stage. The number of stages is thus related to the number of pixels per block.
For example, a four-stage table can be used to classify 4×4 pixel blocks. For each 4×4 image block, the first stage can process sixteen individual pixels in pairs to yield eight indices corresponding to eight respective 2×1 pixel blocks. The second stage can convert the eight 2×1 blocks indices to four 2×2 block indices. The third stage can convert the four 2×2 block indices to two 4×2 block indices. The fourth stage can convert the two 4×2 block indices to one 4×4 block classification index.
In this example, each stage processes inputs in pairs. For each 4×4 image vectors, the first stage processes eight pairs of pixels. This can be accomplished using eight first-stage tables, or by using one first-stage table eight times, or by some intermediate solution. In practice, using a single table eight times affords sufficient performance with minimal memory requirements. Likewise, for the intermediate stages, a single table can be used multiple times per image vector for fast and efficient classification. Note that the number of stages can be reduced by increasing the number of inputs per table; for example,
Chang Jon
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Table-based low-level image classification and compression... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Table-based low-level image classification and compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Table-based low-level image classification and compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925018