10-07-2012, 03:33 PM
Two-Dimensional Rank Order Filter
2-d rank order filter.pdf (Size: 431.22 KB / Downloads: 17)
Summary This application note describes the implementation of a two-dimensional Rank Order filter. The
reference design includes the RTL VHDL implementation of an efficient sorting algorithm. The
design is parameterizable for input/output precision, color standards, filter kernel size,
maximum horizontal resolution, and implementation options. The rank to be selected can be
modified dynamically, and the actual horizontal resolution is picked up automatically from the
input synchronization signals. The design has a fully synchronous interface through the ce, clk,
and rst ports.
Introduction Rank order filtering is a class of operators that use neighborhood pixels to perform
comparisons and ranking. The median filter, a sub-class of the rank order filter [Ref 1][Ref 2]
[Ref 3], sorts the pixels in a region by luminance, finds the median value and replaces the
central pixel with that value. Used to remove noise from images, this operation completely
eliminates extreme values from the image. Rank operations also include the maximum and
minimum operators, which find the brightest or darkest pixels in each neighborhood and place
that value into the central pixel. By loose analogy to the erosion and dilation operations on
binary images, these are sometimes called grey scale erosion and dilation [Ref 4].
One important variable in the use of a rank operator is the size of the neighborhood. Generally,
rectangular (for convenience of computation) or circular (to minimize directional effects) shapes
are used. As the size of the neighborhood is increased, however, the computational effort in
performing the ranking increases rapidly. Also, these ranking operations cannot be easily
programmed into specialized hardware, such as array processors, or programmable DSP
processors [Ref 5][Ref 6][Ref 7][Ref 8].
Rank order filtering or Median filtering is used extensively in smoothing and de-noising
applications for images and video [Ref 9]. It is a cost-effective solution used predominantly in
video pre- and post-processing systems. It is also deployed extensively in real-time vision
systems and automatic target recognition (ATR) systems [Ref 10].
[/i][i]rst - Synchronous Clear
Pulling rst High results in resetting all internal registers and keeps pix_en_out Low until valid
samples are available on the output channels (cc0_out, cc1_out, and cc2_out). Output
channels (cc0_out, cc1_out, and cc2_out) are not cleared. Previous pixels might appear on the
output; however, these pixels are invalidated by pix_en_out = 0.
Figure 1: rank_2d Symbol
rank2d
cc0_out
hs_out
cc1_out
cc2_out
vs_out
pix_en_out
rank
cc0_in
cc1_in
cc2_in
hs_in
vs_in
pix_en_in
clk
ce
rst
x953_01_082806
Table 1: Symbol Pinout
Port Name Port Width Direction Description
cc0_in DATA_WIDTH_CH0 Input Color Channel input 0 (R for RGB, Y for YUV or YCrCb)
cc1_in DATA_WIDTH_CH1 Input Color Channel input 1 (G for RGB, U for YUV, Cr for YCrCb)
cc2_in DATA_WIDTH_CH2 Input Color Channel input 2 (B for RGB, V for YUV, Cb for YCrCb)
cc0_out DATA_WIDTH_CH0 Output Color Channel output 0 (R for RGB, Y for YUV or YCrCb)
cc1_out DATA_WIDTH_CH1 Output Color Channel output 1 (G for RGB, U for YUV, Cr for YCrCb)
cc2_out DATA_WIDTH_CH2 Output Color Channel output 2 (B for RGB, V for YUV, Cb for YCrCb)
rank log2(WHvirt*WW)1 Input Designates which sample to select from the ordered list
hs_in 1 Input Horizontal Sync input
vs_in 1 Input Vertical Sync input
pix_en_in 1 Input Pixel Enable input
hs_out 1 Output Horizontal Sync output
vs_out 1 Output Vertical Sync output
pix_en_out 1 Output Pixel Enable output
clk 1 input System clock
ce 1 input Clock Enable
rst 1 input Synchronous Clear Input
Notes:
1. WW is the width, WHvirt(7) is the vertical size of the virtual filter kernel. See Figure 6.
Signal Descriptions
XAPP953 (v1.1) September 21, 2006 www.xilinx.com 3
R
ce - Clock Enable
Pulling ce Low suspends all operations of the design. Input signals are not sampled, except for
reset (rst takes precedence over ce).
cc0_in, cc1_in, cc2_in - Data inputs
Input pixels are presented to the reference design through the color channel inputs (cc0_in,
cc1_in, cc2_in). The reference design caters to RGB, YUV, and YCrCb color representations.
The width of channel inputs should be positive (non-zero) integers. For RGB representation,
connect channel R to cc0_in, channel G to cc1_in, and channel B to cc2_in. For YUV or YCrCb
signals connect channel Y to cc0_in, U or Cr to cc1_in, V or Cb to cc2_in.
pix_en_in - Pixel Enable Input
Input pixels are validated by pix_en_in. When pix_en_in is Low and ce is High, the sorting core
of the filter keeps working. However, no new pixels are latched into the line buffer. Pix_en_in
basically facilitates working with a core clock rate higher than of the pixel clock rate, as the filter
core might need multiple clock cycles to process input pixels. The duty cycle of pix_en_in has
to be set so the filter core has sufficient extra cycles to perform sorting.
hs_in - Horizontal Sync Input
A strobe on this input signals the beginning of a new line. As the two-dimensional filter operates
on multiple lines, it is crucial that pixels in the same column are aligned. Pixel rows are stored
in programmable length line-buffers, which are concatenated at the end of each line, deduced
from hs_in signal.
vs_in - Horizontal Sync Input
A strobe on this input signals the beginning of a new frame. This signal is necessary to avoid
carrying forward information from one frame to the next. After a pulse is detected on vs_in, the
contents of the line buffer are invalidated.
cc0_out, cc1_out, cc2_out - Data Outputs
Output pixels are presented on the color channel outputs (cc0_out, cc1_out, and cc2_out) in a
fashion similar to the data inputs. The width of channel outputs equal those of the
corresponding input channels.
pix_en_out – Pixel Enable Output
Output pixels are validated by pix_en_out.
hs_out – Horizontal Sync Output
A strobe on this output indicates the beginning of a new output line. This signal is a delayed
version of hs_in.
vs_out – Horizontal Sync Output
A strobe on this output indicates the beginning of a new output frame. This signal is a delayed
version of vs_in.
Generic Parameters
XAPP953 (v1.1) September 21, 2006 www.xilinx.com 4
R
Generic
Parameters
The design parameters are listed in Table 2.
Theory of
Operation
Rank order filtering is a non-linear filtering technique which orders the contents of a filter kernel
and selects the sample indexed by rank from the magnitude ordered samples. In the twodimensional
(2D) case, contents of a two-dimensional window (which slides across the image)
are filtered. Every time the window is shifted by one pixel, a set of obsolete pixels are discarded
and a set of new pixels are inserted. The samples within the window are sorted and the element
with the specified rank replaces the center element of the window in the output. Most typical
ranks are median, minimum, and maximum.
Compared to linear filters, such as FIR or IIR, rank filters can effectively remove impulse-like
noises while preserving the edges of the original image. This can be very useful for various
applications, such as pre-processing before edge detection or removing certain types of
transmission noises.
The hardware architecture presented here is tailored to high performance color video
processing.
Architecture
Let TAP=WW·WH denote the number of taps, where WW (WINDOW_WIDTH) and WH
(WINDOW_HEIGHT) are the vertical and the horizontal size of the filter window. Also, let DW
(DATA_WIDTH) denote the width of the complete per-pixel information (e.g., R, G, and B
values), and DWF (DATA_WIDTH_FILTER) denote the width of the data used for ordering. This
value can be any function of the complete pixel information. For instance, many applications
may find using luminance (Y) useful for ordering pixels. This is trivial when the input is in the
YCbCr or YUV color space; otherwise, it can be easily derived from RGB components.
Table 2: Design Parameters
Name Type Range Description
DATA_WIDTH_CH0 Integer 1 to 16 Bit width of color channel 0.
DATA_WIDTH_CH1 Integer 1 to 16 Bit width of color channel 1.
DATA_WIDTH_CH2 Integer 1 to 16 Bit width of color channel 2.
DATA_WIDTH_FILTER Integer 4 to 24 Width of the magnitude value, generated from the 3 color.
channel values, on which sorting is performed.
WINDOW_WIDTH Integer 3 to 9 Horizontal size of filter kernel.
WINDOW_HEIGHT Integer 3 to 9 Vertical size of filter kernel.
NEW_INPUTS Integer 1 to
WINDOW_HEIGHT
Number of pixels entered into the filter kernel from the line
buffers per clk cycle.
MAX_HORIZONTAL_RES
Integer 2048
Maximum length of a scan line. This value controls line
buffer memory allocation. The actual horizontal resolution
is controlled by the horizontal sync signals.
Y_GENERATOR_TYPE(1)
Integer 0 to 2
0: magnitude value = cc0+cc1+cc2.
1: magnitude value = 0.51*cc0+cc1+0.19*cc2
2: magnitude value = cc0
FAMILY String - Spartan™-3, Spartan-3E, Virtex™-II, Virtex-II Pro,
Virtex-4, Virtex-5
Notes:
1. See “Basic Filter Architecture” for more information.
Theory of Operation
XAPP953 (v1.1) September 21, 2006 www.xilinx.com 5
R
The most important difference between 2D and 1D rank filtering beyond larger tap numbers is
WH input image samples are inserted into the 2D filter core for each new output sample. This
reference design targets applications with rectangular filter kernels, scanning the image left to
right, top to bottom. Figure 2 presents the sliding window moving across the input image from
left to right. Smaller, grey squares represent pixels. The light grey block outlined with white
correspond to the current filter window; the black dotted line outlines the next window. Darker
squares illustrate new pixels entering the kernel.
1D filters can be trivially extended to 2D by operating the filter at WH multiple of the pixel clock,
reading new input pixels every clock cycle, but generating valid output pixels only once in every
WH clock cycle. Depending on the filter size and the targeted FPGA family, this solution is
viable for a wide range of applications.
If pixel clock frequencies are prohibitively high to run the filter core at a multiple of the pixel
clock frequency, parallel instances of some key filter components can be used so the filter may
accept WH number of new input samples every clock cycle. However, for most applications a
fully parallel implementation is suboptimal due to inefficient resource utilization.
Hybrid solutions spanning between fully parallel (WH input samples per clock cycle) and word
serial (one input sample per clock cycle) allow tuning the filter core to the maximum clock
frequency allowed by the target chip while minimizing resource counts. From the vertical size of
the filter window (WH), the sampling (pixel) frequency of the input (FS), and the number of new
input samples (NI) the required operating frequency of the filter core (FOmax) can be
determined:
Equation 1
Basic Filter Architecture
The architecture consists of five main components, illustrated on Figure 3. The Line Buffer
stores WH-1 lines of the input frame. If required, the Y Generator computes magnitude values,
such as luminance, from RGB for magnitude ordering. The Delay Line block stores full pixel
information (all 3 color components) for the pixels currently being processed by the Filter Core,
which does the actual rank filtering. The Control block generates optional data switching,
masking and output valid signals.