Median filter in Verilog

[john]

Hi all,
I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).

Any suggestions? Thanks.....

 

[Mike Treseler]

john wrote:

I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications.

Any suggestions? Thanks.....

I like to prototype that sort of thing in python
before writing rtl. If python suits you
there is a python package called MyHDL that
can generate verilog code. Related example:
http://myhdl.jandecaluwe.com/doku.php/cookbook:bitonic


-- Mike Treseler

 

[glen herrmannsfeldt]

john wrote:

I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).

My favorite architecture for such processors is the
systolic array, which may or may not be useful in this case.

First thought is that, given an already sorted array you
remove one point and add the new one in the appropriate position.
(Note that http://en.wikipedia.org/wiki/Median_filter says
you should have an odd number, and 100 isn't odd.)

The sort/insert should be done in a fixed number of clock
cycles, like one or two. That would seem to require N
comparators, and N bit priority encoder, and N multiplexers
to shift and insert as appropriate. That sounds like a lot
of logic, but it shouldn't be hard in a reasonable sized
ASIC or FPGA to fit it in. It requires signals going
long distances across the array, which might slow it
down too much.

My first thought on seeing Median was an algorithm
in Knuth, "The Art of Computer Programming," vol. 3,
on an O algorithm for median that doesn't sort
the whole array.

A systolic array solution isn't immediately obvious,
but that might work better for high speed processing.
It might be that the algorithm in Knuth could be
implemented in some type of parallel array not
requiring long distance communication.

-- glen

 

[Jonathan Bromley]

On Tue, 24 Jun 2008 11:05:34 -0800, glen herrmannsfeldt wrote:

john wrote:

I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).

A systolic array solution isn't immediately obvious

I believe there is a quasi-systolic solution, but it isn't simple.

Consider an array of cells, each of which holds a 14-bit data value
and a 7-bit link value. The cells are maintained in order sorted
on the data value, and therefore the median is trivially the
data value of the middle cell. Each cell's link value contains
the cell number of the next cell in arrival-time order, forming
a linked list. Two additional 7-bit registers hold the cell
numbers of the oldest and newest points (head and tail pointers
of the linked list).

On arrival of a new data point, you must...
- locate the oldest cell, pointed-to by the head pointer;
this cell's value will be lost
- locate the position in the sorted array that will be
occupied by the new data point - this is simple enough,
requiring a 14-bit magnitude comparator at each cell
- for every cell, shift its contents
right, left or remain in place, depending on where it
is relative to the new datum's insertion point, the
oldest cell and the newest cell (tail pointer)
- for every cell, decrement or increment its link value
depending on where the link points to relative to those
three critical positions
- finally, update the head and tail pointers to reflect
the new arrangements.

The majority of the logic and routing in this scheme is
highly localised to individual cells and their immediate
neighbours. However, some values must be distributed to
every cell, and some information (the location at which
the new data point is to be inserted) must be inferred
from a thermometer code that's spread over the whole
array (a single-bit output from each cell).
So it's not truly systolic, but I think it's workable
for ~100 points. I guess it would be very much easier
to do if you had three or four clock cycles to handle
each new data point.

The resource cost appears to be, for the OP's problem:
- one data register per point (14 bits)
- one link register per point (7 bits), with an
incrementer/decrementer on it
- one data value comparator per point (14-bit magnitude comp)
- two link value comparators per point (7-bit magnitude)
- a very small amount of local control logic per point
- 7-bit head and tail pointer registers
- a global 100-to-7 thermometer coder to compute the
location at which the new value will be inserted
- buffers to distribute the input value, head and tail
pointers, and new value location to all cells

I'll try to work through this, because it's fun; but I
don't have too much free time right now, so no promises.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[john]

On Jun 24, 7:38 pm, Mike Treseler <mike_trese...@comcast.net> wrote:

john wrote:
I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications.
Any suggestions? Thanks.....

I like to prototype that sort of thing in python
before writing rtl. If python suits you
there is a python package called MyHDL that
can generate verilog code. Related example:http://myhdl.jandecaluwe.com/doku.php/cookbook:bitonic

-- Mike Treseler

I tested the verilog code in the bitonic example and works fine. I
would like to do some mods on the MyHDL implementation
and simulate the results with my verilog simulator. Is there an easy
way to use this Python package? I am not familiar with Python at all.
Thank you Verymuch. Much appreciated.
John

 

[Jonathan Bromley]

On Thu, 26 Jun 2008 06:54:36 -0700 (PDT), john wrote:

I do not get why the arrival-time order information is
important here and where it is used in the scheme
you are proposing.

The idea I have (and it's only an idea at present) is to
keep the most recent 100 data points as a sorted array.
In this way, when each new point arrives it's only necessary
to find where to put it in the sorted array, because the
other 99 points are already sorted; it seems like a crazy
waste of resources to do all the sorting all over again.
Inserting one new item in an already-sorted array is
quite easy to do in hardware, if the array is not too big.

However, when each new point arrives you also need
to throw away the oldest (100th) point. But the points
have been sorted into the array - so you don't know which
entry in the array holds the oldest point. That was the
problem I was trying to solve with the linked-list idea,
but I now think I perhaps have a simpler way to do it...
when you get to my age the wheels go round quite a bit
slower than they used to, so you'll have to wait awhile
for the result of that "I now think" !!!

I have 10 clock cycles to sort each new data point.

That should be plenty, if what I'm planning can be
made to work.

Your current idea seems to be keeping the most recent
100 data points in a bunch of 100 registers, and feeding
them all into a sorting network. This is a very
extravagant way of doing it. The classic bitonic sort
needs 24 compare/swap elements to sort 8 data points;
using Batcher's ingenious modification of the sort,
you can get that down to 19 compare/swaps. Batcher's
algorithm requires - wait for it - 1077 compare/swap
elements to sort 100 points. That's BIG. That's why
I've been trying to think of more compact methods
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jonathan Bromley]

On Thu, 26 Jun 2008 08:34:20 -0700 (PDT), john wrote:

It seems like I did not explain my problem clearly since the very
beginning. I need to sort an array of 100 points. I am receiving each
data point every 10 clock cycles. When I have 101 points in the array,
I output the median value and clear the array to start all over again.
This will probably be simpler than what you were thinking - no arrival
time order info required.

Whoa! That's not a median filter, in any sense that I'm
familiar with. However, if that's what you want to do then it's
MUCH easier. Unless your clock is rather fast, you can probably
do one sample per clock quite easily.

Build an array of 101 registers. Each register has a comparator
that compares the current register contents with the incoming
data bus.

Initialise all these registers to the lowest possible value (zero?).

When each new value arrives, each register's comparator compares
the new value with the register's contents and yields a "greater
than" result - call that GT for element , where is in
the range [0:100]. If the incoming number is bigger than the
register, then GT is true.

Each register now behaves in the following way:

if (GT && GT[i+1])
register <= register[i+1];
else if (GT && !GT[i+1])
register <= incoming_value;
// else (!GT), hold the value of register

The result of this is that the register array is always
in sorted order. After you've received the 101st incoming
value, you can pick off the median from register[50]
before clearing all registers back to zero again.

The only tiny wrinkle is what happens at the highest-numbered
element; that's actually quite easy - you just create an extra
signal GT[101] that is stuck at false.

I've used this insertion-sort mechanism many times. It's
nice and scalable, except that you need to distribute the
incoming value to all 101 registers and comparators. You
can probably trust your synthesis tool to make a reasonable
job of that, but it will certainly create some buffering.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[john]

On Jun 26, 1:13 pm, Jonathan Bromley <jonathan.brom...@MYCOMPANY.com>
wrote:

On Tue, 24 Jun 2008 11:05:34 -0800, glen herrmannsfeldt wrote:
john wrote:

I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).
A systolic array solution isn't immediately obvious

I believe there is a quasi-systolic solution, but it isn't simple.

Consider an array of cells, each of which holds a 14-bit data value
and a 7-bit link value. The cells are maintained in order sorted
on the data value, and therefore the median is trivially the
data value of the middle cell. Each cell's link value contains
the cell number of the next cell in arrival-time order, forming
a linked list. Two additional 7-bit registers hold the cell
numbers of the oldest and newest points (head and tail pointers
of the linked list).

On arrival of a new data point, you must...
- locate the oldest cell, pointed-to by the head pointer;
this cell's value will be lost
- locate the position in the sorted array that will be
occupied by the new data point - this is simple enough,
requiring a 14-bit magnitude comparator at each cell
- for every cell, shift its contents
right, left or remain in place, depending on where it
is relative to the new datum's insertion point, the
oldest cell and the newest cell (tail pointer)
- for every cell, decrement or increment its link value
depending on where the link points to relative to those
three critical positions
- finally, update the head and tail pointers to reflect
the new arrangements.

The majority of the logic and routing in this scheme is
highly localised to individual cells and their immediate
neighbours. However, some values must be distributed to
every cell, and some information (the location at which
the new data point is to be inserted) must be inferred
from a thermometer code that's spread over the whole
array (a single-bit output from each cell).
So it's not truly systolic, but I think it's workable
for ~100 points. I guess it would be very much easier
to do if you had three or four clock cycles to handle
each new data point.

The resource cost appears to be, for the OP's problem:
- one data register per point (14 bits)
- one link register per point (7 bits), with an
incrementer/decrementer on it
- one data value comparator per point (14-bit magnitude comp)
- two link value comparators per point (7-bit magnitude)
- a very small amount of local control logic per point
- 7-bit head and tail pointer registers
- a global 100-to-7 thermometer coder to compute the
location at which the new value will be inserted
- buffers to distribute the input value, head and tail
pointers, and new value location to all cells

I'll try to work through this, because it's fun; but I
don't have too much free time right now, so no promises.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.brom...@MYCOMPANY.comhttp://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

Thanks for your explanation Jonathan. I do not get why the arrival-
time
order information is important here and where it is used in the scheme
you are proposing. I have 10 clock cycles to sort each new data point.

 

[Jonathan Bromley]

On Thu, 26 Jun 2008 16:52:33 +0100, Jonathan Bromley wrote:

Build an array of 101 registers.
[...]
Each register now behaves in the following way:
[...]

Afterthought, for algorithm wonks: This is an O(N^2)
sort with the interesting property that it is O(N) in
size and O(N) in time - to sort an array of N elements
you need N comparators and registers, and it takes
N clock cycles to do the sort.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Mike Treseler]

john wrote:

I tested the verilog code in the bitonic example and works fine. I
would like to do some mods on the MyHDL implementation
and simulate the results with my verilog simulator.

Check out Jan's manual:
http://www.jandecaluwe.com/Tools/MyHDL/manual/MyHDL.html
Logical simulation is built in.

Is there an easy way to use this Python package?

Not without reading the docs and working an example.

I am not familiar with Python at all.

It's worth learning.

56 Thu Jun 26 /evtfs/home/tres> python
Type "help", "copyright", "credits" or "license" for more information.

2**32
4294967296L
hex(4294967296)
'0x100000000L'

-- Mike Treseler

 

[john]

On Jun 26, 4:25 pm, Jonathan Bromley <jonathan.brom...@MYCOMPANY.com>
wrote:

On Thu, 26 Jun 2008 06:54:36 -0700 (PDT), john wrote:
I do not get why the arrival-time order information is
important here and where it is used in the scheme
you are proposing.

The idea I have (and it's only an idea at present) is to
keep the most recent 100 data points as a sorted array.
In this way, when each new point arrives it's only necessary
to find where to put it in the sorted array, because the
other 99 points are already sorted; it seems like a crazy
waste of resources to do all the sorting all over again.
Inserting one new item in an already-sorted array is
quite easy to do in hardware, if the array is not too big.

However, when each new point arrives you also need
to throw away the oldest (100th) point. But the points
have been sorted into the array - so you don't know which
entry in the array holds the oldest point. That was the
problem I was trying to solve with the linked-list idea,
but I now think I perhaps have a simpler way to do it...
when you get to my age the wheels go round quite a bit
slower than they used to, so you'll have to wait awhile
for the result of that "I now think" !!!

I have 10 clock cycles to sort each new data point.

That should be plenty, if what I'm planning can be
made to work.

Your current idea seems to be keeping the most recent
100 data points in a bunch of 100 registers, and feeding
them all into a sorting network. This is a very
extravagant way of doing it. The classic bitonic sort
needs 24 compare/swap elements to sort 8 data points;
using Batcher's ingenious modification of the sort,
you can get that down to 19 compare/swaps. Batcher's
algorithm requires - wait for it - 1077 compare/swap
elements to sort 100 points. That's BIG. That's why
I've been trying to think of more compact methods
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.brom...@MYCOMPANY.comhttp://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

It seems like I did not explain my problem clearly since the very
beginning. I need to sort an array of 100 points. I am receiving each
data point every 10 clock cycles. When I have 101 points in the array,
I output the median value and clear the array to start all over again.
This will probably be simpler than what you were thinking - no arrival
time order info required. I am just trying to get a good solution in
terms of area and power. Thanks a million. John.

 

[glen herrmannsfeldt]

john wrote:
(snip)

It seems like I did not explain my problem clearly since the very
beginning. I need to sort an array of 100 points. I am receiving each
data point every 10 clock cycles. When I have 101 points in the array,
I output the median value and clear the array to start all over again.
This will probably be simpler than what you were thinking - no arrival
time order info required. I am just trying to get a good solution in
terms of area and power. Thanks a million. John.

Much easier. (Though you want to sort all 101.)

Still, you might look at the algorithm in Knuth.

-- glen

 

[glen herrmannsfeldt]

Jonathan Bromley wrote:

(snip, I wrote)

A systolic array solution isn't immediately obvious

I believe there is a quasi-systolic solution, but it isn't simple.

How about a binary tree shaped systolic array. Not that
I completely see it yet, but since 10 clock cycles
are allowed for each data point, it would seem that
one could get through a log2(100) level tree in less
than 10 cycles. (with the small complication that
100 is not a power of two.)

-- glen

 

[john]

On Jun 26, 5:56 pm, Jonathan Bromley <jonathan.brom...@MYCOMPANY.com>
wrote:

On Thu, 26 Jun 2008 16:52:33 +0100, Jonathan Bromley wrote:
Build an array of 101 registers.
[...]
Each register now behaves in the following way:

[...]

Afterthought, for algorithm wonks: This is an O(N^2)
sort with the interesting property that it is O(N) in
size and O(N) in time - to sort an array of N elements
you need N comparators and registers, and it takes
N clock cycles to do the sort.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.brom...@MYCOMPANY.comhttp://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

Thanks a million for your help. 25 comparators with a mux for my 100
points seems to be working
fine in 4 clock cycles whiile saving some are.

 

[gupta]

On Jun 24, 5:37 pm, john <alcar...@hotmail.com> wrote:

Hi all,
I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).

Any suggestions? Thanks.....

Hello John,

I saw one of your posts in google groups regarding design of median
filter in verilog. I am also working on the same topic and i need your
help. If u are already completed the task, is it possbile to send me
the code and please specify a book to study more about median filter
( regarding the behavior or working of the filter)

Thanks in Advance.

Gupta.

 

Please tell me about the code of median sorting of numbers in vhdl. it will help my project.I tried and searched but I am getting only sorting of numbers. Please help me