From: Spyros <olivia@acci.gr>
Subject: Re: Median Filters
Date: 14 Feb 1999 00:00:00 GMT
Message-ID: <36C6A8A9.78B47732@acci.gr>
References: <36C60633.22F68264@hotmail.com>
To: sunny nani <sunnynani@hotmail.com>
Content-Type: multipart/alternative; boundary="------------1EFA3C47FCF407D2C73EF0AA"
X-Complaints-To: abuse@otenet.gr
X-Trace: ns1.otenet.gr 918989542 25064 195.170.15.180 (14 Feb 1999 10:52:22 GMT)
Organization: -
Mime-Version: 1.0
NNTP-Posting-Date: 14 Feb 1999 10:52:22 GMT
Newsgroups: comp.graphics.algorithms


--------------1EFA3C47FCF407D2C73EF0AA
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

 Median filtering may not be a convolution, but there is a fast
algorothm which exploits the (n-1) x n overlap of two consecutive
windows. The algorithm (Huang's algorithm) consists of the following
steps:


1. Store the first window data in a n x n array Window. Compute the
local histogram and find the median, using the quicksort algorithm.
Compute the number ltmdn of poins whose intensity is less than that of
the median.
2. Move on to the next window, updating the n elements. Update the
histogram (decrease the values for then replaced elements, increase the
values for the n new elements). Compute the number ltmdn of poins whose
intensity is less than that of the median of the previous window med.
3. Start from point med. If  ltmdn<= (n2+1)/2 (condition 1) then
med=med+1 else med=med-1. Update ltmdn. Repeat until condition 1
changes.
4. If end of line is reached, go to step 1 (next line) else go to step
2.



Here 's some Pascal code for this algorithm:

procedure MedFilter(radius:integer);
var x,y,i,k,l:integer;
    xs,ys,xe,ye:integer;
    med:integer;
    size,size2:integer;
    ltmdn:integer;
    hist:array[0..255] of integer;
    ar,sar:array[0..6561] of integer;
begin

  size:=2*radius+1;
  size2:=size*size;

  for y:=0 to ImageHeight-1 do
   begin
    ltmdn:=0;
    for i:=0 to 255 do hist[i]:=0;
    for x:=0 to ImageWidth-1 do
     begin
      if x=0 then
       begin
        for k:=-radius to radius do
         for l:=-radius to radius do
          begin
           if (x+k>=0) and (x+k<=ImageWidth-1) and (y+l>=0) and
(y+l<=ImageHeight-1) then
            ar[size*(radius+k)+(radius+l)]:=Image[t,x+k,y+l]
           else ar[size*(radius+k)+(radius+l)]:=0;
           Inc(hist[ar[size*(radius+k)+(radius+l)]]);
          end;
        qsort(ar,sar,size2);
        med:=sar[size2 div 2];
        for i:=0 to med-1 do ltmdn:=ltmdn+hist[i];
       end
      else
       begin
        for l:=-radius to radius do
         begin
          Dec(hist[ar[size*((x-1) mod size)+radius+l]]);
          if ar[size*((x-1) mod size)+radius+l]<med then ltmdn:=ltmdn-1;

          if (x+radius<=ImageWidth-1) and (y+l>=0) and
(y+l<=ImageHeight-1) then
           ar[size*((x-1) mod size)+radius+l]:=Image[t,x+radius,y+l]
          else ar[size*((x-1) mod size)+radius+l]:=0;
          Inc(hist[ar[size*((x-1) mod size)+radius+l]]);
          if ar[size*((x-1) mod size)+radius+l]<med then Inc(ltmdn);
         end;
        if (ltmdn<=size2 div 2) then
         begin
          repeat
           ltmdn:=ltmdn+hist[med];
           Inc(med);
          until (ltmdn>size2 div 2) or (med=255);
          ltmdn:=ltmdn-hist[med-1];
          Dec(med);
         end
        else
         repeat
          ltmdn:=ltmdn-hist[med-1];
          Dec(med);
         until (ltmdn<=size2 div 2) or (med=0);
       end;
       NewImage[x,y]:=med;
     end;
   end;
end;


sunny nani wrote:

> Hi!
>
> Does anyone know how to update the median as the center of the n x n
> neighborhood moved from pixel to pixel in an image.
>
> Thanks
> --sunny nani