Image analysis – Image transformation or preprocessing – Transforming each dimension separately
Reexamination Certificate
1994-08-29
2001-10-16
Mehta, Bhavesh (Department: 2621)
Image analysis
Image transformation or preprocessing
Transforming each dimension separately
C382S260000, C708S300000
Reexamination Certificate
active
06304679
ABSTRACT:
This invention relates generally to a digital signal processing apparatus, and more particularly to the implementation of a plurality of two-dimensional digital filters using a series of one-dimensional transformations.
CROSS REFERENCE
The following related applications and patents are hereby incorporated by reference for their teachings:
“Improved Automatic Image Segmentation,” Shiau et al., Serial No. 07/722,568, filed Jun. 27, 1991;
“Method and Apparatus for Controlling the Processing of Digital Image Signals”, Williams et al., Ser. No. 07/809,807, filed Dec. 18, 1991;
U.S. Pat. No. 4,811,115 to Lin et al., Issued Mar. 7, 1989; and
U.S. Pat. No. 4,897,803 to Calarco et al., Issued Jan. 30, 1990.
COPYRIGHT NOTIFICATION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owners have no objection to the facsimile reproduction, by anyone, of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The features of the present invention may be used in the printing arts and, more particularly, in digital image processing and electrophotographic printing. In digital image processing there is a distinct advantage to being able to provide digital filtering in an efficient and low cost manner. With regard to efficiency, it is advantageous to design hardware implementations of digital filters that are efficient This efficiency has two factors, first a speed of processing factor, and second a hardware minimization factor. For example, improved processing efficiency or speed may be achieved by adding hardware, however, this may not be a practical solution when one has to consider the cost of the additional hardware. The second factor becomes increasingly important when implementing the device as an application specific integrated circuit (ASIC), where the addition of hardware elements may result in the need for a larger die package. Accordingly, the present invention provides a two-dimensional digital filter that is efficient with respect to processing speed and hardware implementation, as well.
Signal processing devices usually require filters, especially two-dimensional filters to process data in numerous ways. Well known electrophotographic systems, for example, the Xerox® Docutech Production Publisher®, usually employ digital hardware and application specific integrated circuit (ASIC) devices specifically designed to provide digital filtering capabilities. Generally, this type of system would employ hardware, software, or a combination of both to implement the digital filtering capabilities required. Various approaches have been devised for the implementation of digital filtering techniques, of which the following disclosures appear to be relevant:
U.S. Pat. No. 4,766,561
Patentee: Thompson et al.
Issued: Aug. 23, 1988
U.S. Pat. No. 4,777,612
Patentee Tomimitsu
Issued: Oct. 11, 1988
U.S. Pat. No. 4,82 1,223
Patentee: David
Issued: Apr. 11, 1989
The relevant portions of the foregoing patents may be briefly summarized as follows:
U.S. Pat. No. 4,766,561 to Thompson et al. discloses a circuit for performing a plurality of finite impulse response filtering functions. The circuit comprises a plurality of filters, each implementing a predetermined digital filter algorithm. A storage circuit stores coefficients and data operands utilized in implementing the predetermined algorithms. An arithmetic unit is coupled to the storage circuit for performing predetermined arithmetic operations with selected coefficient and data operands, and a sequencing control device sequentially selects operands from the storage circuit for input to the arithmetic unit.
U.S. Pat. No. 4,777,612 to Tomimitsu discloses a digital signal processing apparatus for providing high-speed digital filtering. The apparatus includes at least two digital filters in parallel and a multiplexer for alternatively outputting the outputs of the filters.
U.S. Pat. No. 4,821,223 to David describes a two-dimensional finite impulse response filter having a plurality of filter portions of substantially identical construction arranged in a parallel configuration A demultiplexer separates an input data signal comprising consecutive digital words and supplies each digital word in sequence to a separate filter portion. Subsequently, a multiplexer coupled to the outputs of the filter portions selectively outputs the filtered data from each filter portion in a sequence corresponding to the order of separation of the input data, thereby resulting in a filtered version of the original input data
The present invention seeks to overcome the limitations of the related references by providing a plurality of one-dimensional (1-D) transform units that may be selectively combined with an additional one-dimensional transform unit to produce a plurality of distinct two-dimensional (2-D) filters, any one of which is selectable on a pixel by pixel basis. Moreover, the present system has the added advantage of providing these two-dimensional finite impulse response filters without employing multiple, identically constructed two-dimensional filters arranged in a parallel fashion, thereby substantially reducing the complexity and cost of the filter hardware.
In accordance with one aspect of the present invention, there is provided an apparatus for implementing a plurality of two-dimensional digital filters having a plurality of first stage filters operating in a first dimension in combination with a single second stage filter, operating in a second dimension, the filter operating in the second dimension being suitable for receiving output from one of the filters operating in the first dimension. A controller, operating in conjunction with the filters is utilized for controlling the operation of all filters, as well as selection of the input source for the second dimension filter.
Pursuant to another aspect of the present invention, there is provided an apparatus for implementing the plurality of two-dimensional digital filters by separating the transformations carried out by the filters into separate elements, thereby reducing the complexity of the hardware needed to implement the filters.
Pursuant to another aspect of the present invention, there is provided a method for selectively filtering a single digital data element in a two-dimensional filter by first applying a selected one-dimensional transformation, said transformation being selected from a plurality of possible transformations. Next, storing the context associated with the single data element until the context is passed to the second one-dimensional transform, to produce the two-dimensional filtered output.
REFERENCES:
patent: 4328426 (1982-05-01), D'Ortenzio
patent: 4602285 (1986-07-01), Beaulier et al.
patent: 4667304 (1987-05-01), Hier et al.
patent: 4700324 (1987-10-01), Doi et al.
patent: 4760605 (1988-07-01), David et al.
patent: 4862403 (1989-08-01), Iwase et al.
patent: 5027423 (1991-06-01), Kawata et al.
patent: 5068905 (1991-11-01), Hackett et al.
patent: 5093632 (1992-03-01), Hietala et al.
patent: 5131059 (1992-07-01), Kobayashi et al.
patent: 5151953 (1992-09-01), Landeta
patent: 5561617 (1996-10-01), van der Wal
patent: A2632470 (1989-08-01), None
patent: A2184316 (1987-06-01), None
“Principles and Applications of Digital Electronics” by Larry D. Jones, pp. 216-217, 1986.
Clingerman Terri A.
Williams Leon C.
Mehta Bhavesh
Xerox Corporation
LandOfFree
Method and apparatus for implementing two-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing two-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing two-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611633