News Column

Patent Issued for Scalable Architecture for Rank Order Filtering

May 14, 2014



By a News Reporter-Staff News Editor at Electronics Newsweekly -- From Alexandria, Virginia, VerticalNews journalists report that a patent by the inventors Szanto, Peter (Budapest, HU); Szedo, Gabor (Longmont, CO); Feher, Bela (Budakeszi, HU); Chung, Wilson C. (Menlo Park, CA), filed on July 12, 2011, was published online on April 29, 2014.

The patent's assignee for patent number 8713082 is Xilinx, Inc. (San Jose, CA).

News editors obtained the following quote from the background information supplied by the inventors: "Programmable logic devices ('PLDs') are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array ('FPGA'), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks ('IOBs'), configurable logic blocks ('CLBs'), dedicated random access memory blocks ('BRAMs'), multipliers, digital signal processing blocks ('DSPs'), processors, clock managers, delay lock loops ('DLLs'), and so forth. Notably, as used herein, 'include' and 'including' mean including without limitation.

"One such FPGA is the Xilinx Virtex.RTM. FPGA available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. Another type of PLD is the Complex Programmable Logic Device ('CPLD'). A CPLD includes two or more 'function blocks' connected together and to input/output ('I/O') resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays ('PLAs') and Programmable Array Logic ('PAL') devices. Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, for example, using fuse or antifuse technology. The terms 'PLD' and 'programmable logic device' include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable.

"For purposes of clarity, FPGAs are described below though other types of PLDs may be used. FPGAs may include one or more embedded microprocessors. For example, a microprocessor may be located in an area reserved for it, generally referred to as a 'processor block.'

"Linear filters, such as Finite Impulse Response ('FIR') and Infinite Impulse Response ('IIR') filters, have known limitations regarding effectively removing impulse-like noises while preserving the edges of an original image. Non-linear filters, such as rank order filters, in contrast may be effective for removing impulse-like noises while preserving the edges of an original image. Accordingly, use of rank order filters may be useful for image pre-processing before edge detection or removing impulse-like transmission noises.

"A rank order filter conventionally orders contents of a filter kernel ('window') and selects a sample indexed by rank. Conventionally, samples are rank ordered according to magnitude. A sample or pixel with a target rank may be selected for output. For example, the sample with a target rank may replace a center sample in such filter window in a filter output. Examples of ranks include median, minimum, and maximum, among other known examples of ranking. Thus, for these three specific examples, the median value, the minimum value, and the maximum value, respectively, would be selected in each of the different types of rank ordering for output from a rank order filter. Thus, it should be appreciated that sample size may affect image quality.

"Accordingly, it would be desirable and useful to provide a scalable architecture for rank order filters extended to two-dimensional ('2D') filters for image and video processing."

As a supplement to the background information on this patent, VerticalNews correspondents also obtained the inventors' summary information for this patent: "One or more aspects of the invention generally relate to integrated circuits and, more particularly, to a scalable architecture for rank order filtering.

"An aspect of the invention relates generally to a rank order filter. A delay line is coupled to receive pixel information. A filter core is coupled to receive at least a portion of the pixel information. The filter core includes: a first stage of registers for registering data, where the first stage of registers is configured as a first shift register for shifting the data in the filter core; a comparator stage coupled to receive output from the first stage of registers and configured to compare a newly registered portion of the data registered in the first stage of registers with each previously registered portion of the data registered in the first stage of registers to provide comparison results; a second stage of registers coupled for receiving and configured for registering the comparison results; a third stage of registers coupled for receiving the comparison results; a first register portion of the third stage of registers configured to invert the comparison results, to register the comparison results inverted as first Most Significant Bits, and to include a first Least Significant Bit as a self-compare bit, where the first register portion is configured for providing a first output including the first Most Significant Bits and the first Least Significant Bit; a second register portion of the third stage of registers coupled to the first register portion of the third stage of registers as a shift register, where the first register portion is coupled to the second register portion to shift first Least Significant Bits of the first register portion into the second register portion as second Most Significant Bits; and a conversion stage coupled to receive a rank value, the first output and a second output. The first Least Significant Bits include the first Least Significant Bit. The second register portion is coupled to receive a comparison result of the comparison results as a second Least Significant Bit to provide the second output. The second register portion is configured for providing the second output including the second Most Significant Bits and the second Least Significant Bit. The conversion stage is configured to bit sum each of the first output and the second output for respectively generating a first value and a second value. The conversion stage is configured to compare each of the first value and the second value to the rank value for generating a one-hot result. The conversion stage is configured to convert the one-hot result to an associated address. The address is associated with a portion of the data in the filter core associated with the one-hot result. The delay line is coupled to receive the address for accessing the pixel information associated with the one-hot result.

"Another aspect of the invention generally relates to a method for instantiating a rank order filter in programmable logic. A maximum filter core frequency is determined for a filter window width, a filter window height, and a number of input samples. The maximum filter core frequency is greater than the sampling frequency times the filter height divided by the number of new samples. The maximum filter core frequency is insufficient for a word serial instantiation of the rank order filter in the programmable logic. The maximum filter core frequency is excessive for a fully parallel instantiation of the rank order filter in the programmable logic. A partially parallel filter core is instantiated for the rank order filter. The partially parallel filter core is configured to process multiple new samples at one clock cycle, and complete the processing of window height number of samples in one or more clock cycles of the maximum filter core frequency and for producing a single address output on each clock cycle of the maximum filter core frequency.

"Yet another aspect of the invention relates to a rank order filter associated with a virtual filter window. The virtual filter window is a number NZ+1 concatenated real filter windows. The number NZ is a height of the virtual filter window minus a height of the real filter windows, wherein each of the real filter windows are of a same dimension. A filter core includes a stage of data registers, a stage of comparison blocks configured for registering compare results, and a stage of shift registers. The virtual filter window is configured to accommodate an integer multiple input of NI samples to the filter core. The filter core is configured for input of the NI samples on a clock cycle of a filter core clock. The filter core inputs the integer multiple of the NI samples for a number of clock cycles of the filter core clock, where the number of the clock cycles is equivalent to the integer multiple. The virtual filter window spans padding samples, and the padding samples are capable of being part of the NI samples. The NI samples are capable of including both real samples and the padding samples, where the real samples are associated with actual pixel information. The filter core is configured to make available all of the compare results for the stage of shift registers for generating NZ+1 outputs on each clock cycle of the filter core clock."

For additional information on this patent, see: Szanto, Peter; Szedo, Gabor; Feher, Bela; Chung, Wilson C.. Scalable Architecture for Rank Order Filtering. U.S. Patent Number 8713082, filed July 12, 2011, and published online on April 29, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=24&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1154&f=G&l=50&co1=AND&d=PTXT&s1=20140429.PD.&OS=ISD/20140429&RS=ISD/20140429

Keywords for this news article include: Xilinx Inc, Electronics, Programmable Logic Device.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Electronics Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters