5
\$\begingroup\$

I'm trying to implement the fast median filter developed by T.S.Huang (HUANG, T.S. 1981. Two-Dimensional Signal Processing II: Transforms and Median Filters. Berlin: Springer-Verlag, pp. 209-211.).
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1163188&tag=1
Please review my code.
My most important issue here is speed and I'm will to pay for optimization with more memory. I would like to use later on Cilk plus or Intel TBB in order to optimize the speed more.

Header file:

class TOOLBOX_EXPORT Preprocessor
{

public: 
    void Process(uint16_t*& data, int width, int height);
private:

    typedef enum
    {
        FORWARD,
        BACKWARD
    } TDirection;   

    void AddHist(uint16_t value,std::map<uint16_t, int> &histogram);
    void RemoveHist(uint16_t value,std::map<uint16_t,int>::iterator medianIter, std::map<uint16_t, int> &histogram);
    int GetPixelIndex(int row, int col,int width, int height);

};

.cpp file:

    void Preprocessor::AddHist(uint16_t value,std::map<uint16_t, int> &histogram)
    {   
        std::map<uint16_t,int>::iterator iter = histogram.find(value);
        if(iter != histogram.end())
        {
            iter->second++;
        }
        else
        {
            histogram.insert(std::pair<uint16_t,int>(value,1));
        }
    }

    void Preprocessor::RemoveHist(uint16_t value,std::map<uint16_t,int>::iterator medianIter,std::map<uint16_t, int> &histogram)
    {   
        std::map<uint16_t,int>::iterator iter = histogram.find(value);
        if(iter != histogram.end())
        {
            if(iter->second == 1)
            {
                if(medianIter != iter)
                {
                    histogram.erase(iter);
                }
                else
                {
                    iter->second =0;
                }
            }
            else
            {
                iter->second--;
            }
        }   
    }

    int Preprocessor::GetPixelIndex(int row, int col,int width, int height)
    {
        while(!((row >= 0) && (row < height) && ((col >= 0) && (col < width))))
        {
            if(row < 0)
                row++;
            else if(row >= height)
                row--;
            if(col < 0)
                col++;
            else if(col >= width)
                col--;
        }
        return (row*width) +col;
    }


    void Preprocessor::Process(uint16_t*& data, int width, int height)
    {
        int sizeOfChannel = width* height;
        uint16_t* outputImage = new uint16_t[sizeOfChannel];
        TDirection direction = FORWARD;
        int medianWindowX = 7;  // number of columns in filter window
        int medianWindowY = 7;  // number of rows in filter window
        int sum =0;
        int dl;
        int middle = (medianWindowX * medianWindowY)/2 +1;
        int halfMedianWindowX = medianWindowX/2;
        int halfMedianWindowY = medianWindowY/2;
        std::map<uint16_t,int> histogram;
        std::map<uint16_t,int>::iterator medianIter;
        uint16_t av, dv;
        int row = 0;
        int col = 0;

        for(row = -halfMedianWindowY; row <= halfMedianWindowY; row++)
        {
            for(col = -halfMedianWindowX; col <= halfMedianWindowX; col++)
            {
                av = data[GetPixelIndex(row,col,width,height)];     
                //look inside the histogram for the value or add it the binary tree
                AddHist(av,histogram);
            }
        }
        for (medianIter = histogram.begin(); medianIter!= histogram.end() ; medianIter++)
        {
            sum += medianIter->second;
            if(sum >= middle)
            {
                break;
            }
        }
        outputImage[0] = medianIter->first;

        dl = sum - medianIter->second;

        bool directionChanged = false;
        row = 0; 
        row = 0; 
        col = 0;
        do
        {
            if (directionChanged)
            {
                for (int c2 = -halfMedianWindowX; c2 < halfMedianWindowX; c2++)
                {
                    dv = data[GetPixelIndex(row - halfMedianWindowY-1,col + c2,width,height)];
                    av = data[GetPixelIndex(row - halfMedianWindowY  ,col + c2,width,height)];
                    if(av != dv)
                    {
                        RemoveHist(dv,medianIter,histogram);
                        if(dv < medianIter->first)
                        {
                            dl--;
                        }
                        AddHist(av,histogram);
                        if(av < medianIter->first)
                        {
                            dl++;
                        }
                    }
                }
                directionChanged = false;
            }
            else
            {           
                for (int r2 = -halfMedianWindowY; r2 <= halfMedianWindowY; r2++)
                {               
                    dv = data[ GetPixelIndex(row + r2 ,col + (direction == FORWARD ? -halfMedianWindowX-1 : halfMedianWindowX+1),width,height)] ;
                    av = data[GetPixelIndex(row + r2 ,col + (direction == FORWARD ? -halfMedianWindowX : halfMedianWindowX),width,height)] ;
                    if(av != dv)
                    {
                        RemoveHist(dv,medianIter,histogram);
                        if(dv < medianIter->first)
                        {
                            dl--;
                        }
                        AddHist(av,histogram);
                        if(av < medianIter->first)
                        {
                            dl++;
                        }
                    }
                }
            }

            if(dl>= middle)
            {
                while( dl >= middle)
                {
                    medianIter--;
                    dl -= medianIter->second;
                }
            }
            else
            {
                while(dl+ medianIter->second < middle)
                {
                    dl += medianIter->second;
                    medianIter++;
                }
            }
            outputImage[(row * width) +col ] = medianIter->first;
            if(direction == FORWARD)
            {
                col++;
            }
            else
            {
                col--;
            }

            if(col < 0 || col >= width)
            {
                //reverse the direction
                if(direction == FORWARD)
                {
                    direction = BACKWARD;
                }
                else
                {
                    direction = FORWARD; 
                }
                if(col >= width)
                {
                    col = width-1;
                }
                else
                {
                    col = 0;
                }
                row++;
                directionChanged = true;
            }
        }
        while(row < height);

        printf("done");
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.