Median Filter
What is the project about and what is its goal?
The article below will cover an application that performs denoising on PGM P2 images (we will see below what these are and what they represent). The application was suggested to me as an optional project during university. Finding it interesting, I chose to provide a comprehensive description of how the application is designed and functions. I will approach the thought process sequentially in the following sections.
I. Theoretical Overview
- What is a median filter?
In signal processing theory, a filter is a device or process that removes an unwanted part of a signal. There are countless types of filters, but the one we will study in this topic is the median filter. This type of filter is commonly used to eliminate noise (speckles) from images.
The result of applying a median filter to an image can be seen below:
- The type of file to be processed, specifically PGM type P2
In a computer’s memory, a black-and-white image is saved by storing the gray level for each pixel, a level that is always in the range [0; 255], where 0 means black and 255 means white.
PGM is an acronym for Portable Gray Map. There are two PGM file formats – P5, which is a binary file, and P2, which is a text file. A file in P2 format has the following structure:
- The first line contains the code P2, which signals the file type.
- Any line beginning with # is considered a comment and is ignored.
- The next valid line contains two values (width and height), representing the width and height of the image.
- The next valid line contains a value representing the maximum value of a pixel to be encountered in the image (thus, the value corresponding to the white level).
- The following lines contain width x height values, separated by whitespaces, representing the gray levels for each pixel, from left to right and then from top to bottom.
Example:
- Applying a Median Filter
A median filter is always applied over an n x n window around each pixel in the original image, where n is a positive odd integer (3, 5, 7, etc.). Thus, for each pixel in the original image, all its neighbors within an n x n window around it are extracted. These pixels are placed into a vector which is then sorted. The value of the pixel in the filtered image is the middle value of the sorted vector. For a 3 x 3 window:
What do we do at the edges?
At the boundary, where the n x n window extends beyond the edge of the image, it is bordered by repeating the edge pixels. Consider the upper left corner of the original image:
If a 5 x 5 filter is applied to the upper left pixel (with value 10), then a 5 x 5 square window around it is needed:
The corner element is in bold, and to obtain the 5 x 5 window, the edge elements were replicated.
Requirement
Given a sorting algorithm between BubbleSort and MergeSort, a window size, and two PGM-P2 file names, one for input and one for output, apply a median filter of the specified size to each pixel in the input image, using the specified algorithm for window sorting, and write the filtered image to the output file. Both files are in PGM-P2 format.
Input Data
From the keyboard, the algorithm type (bubble or merge), the window size, and the names of the two files (input and output) are given on a single line, all separated by one or more whitespace characters.
Example:
merge 3 test_in.pgm test_out.pgm
II. Program Description
As mentioned, we will discuss based on the code sequentially. First, knowing that we receive a file as input, we must first open it and read the data we are interested in from it. For this, we will use a boolean function, *readPGM.*
The chosen function type. Why bool?
The bool type stores only 2 values, 0 or 1, which in logical arithmetic is True or False. For now, we are interested in checking if our file opens successfully and if we manage to read what we are interested in from it, namely its values, width, height, and maxVal.
Function arguments? Why are they declared as references? What is vector<vector <uint8_t>>& image?
Passing by reference offers us two crucial advantages for our type of application. First, we want to use the values we read when creating the output, which will obviously have the same dimensions. Thus, when calling the function within the main() function, I will need their values, which is only possible by passing by reference. If I do not declare them as references upon calling, the function would only work with local copies of the values (only inside the readPGM function), and upon exiting, I would only get arbitrary values.
Another advantage of passing by reference is efficiency. This becomes significant when we read and process the gray level values of the image using vector<vector>& image. This is, in fact, an uint8_t matrix.
The while loops read and check if what was read is valid.
Here, a sequential traversal of the vector where the values read from the file are introduced takes place. Why did I use static_cast here and not directly image[i][j]=pixel?
I declared pixel as type int because I expect to receive corrupted or wrongly written files that may contain a value greater than 255 or a negative value. It is just a safety measure. Thus, I am forced to cast back to uint8_t.
If everything went well, I return true, signaling that the reading was successful.
The writing function
Now the arguments width, height, and maxVal are no longer passed by reference because writing the file is the last step, and I no longer need their values for other operations. Otherwise, those two nested for-loops serve to treat the file as a matrix, traverse it, and write the values into it.
The function uint8_t getPixel(vector<vector>& image, int x, int y, int latime, int inaltime) and why it is important.
Its role is to correctly manage the image edges so that we do not go outside the image boundary when applying the filter.
Result: If the filter requests the pixel at coordinates (-1, 5), the function will return the value of the pixel at (0, 5). If it requests (50, 1000) in an image of height 500, it will return the value of the pixel at (50, 499).
Next come the sorting functions. We will not go into detail about them because the only difference is the difference in efficiency between them. Any sorting algorithm can be used. All I did was adhere to the requirement.
Why do we have two mergeSort functions?
The first one (the one with 3 arguments) is the recursive base function of the Merge Sort algorithm. Its role is to decompose the vector into increasingly smaller subsections and subsequently combine them back in sorted order. The second one serves to “package” it, meaning to simplify the calling method by reducing it to a single argument. It plays a role in simplifying the code.
Applying the filter
Finally, we get to the actual application of the filter.
What do we use the variable k for?
The variable k calculates the offset from the center of the window (the current pixel ($x, y$)) to the edge. If windowSize is 3, k is 1. The window extends from -1 to +1 relative to the center.
The first 2 loops start the traversal of the file.
What is the role of window?
A temporary vector is created that will store all pixel values from the filtering window.
Next is the Window Loop. Inside the innermost loop, the effective coordinates in the input image are calculated:
int pixelX = x + wx;
int pixelY = y + wy;
Then the obtained value is added to the window vector.
The problem is now finished. The main()` function only ensures the connection with the user. To run, we enter, for example, merge 3 test_in.pgm test_out.pgm. Upon execution, a file named test_out.pgm will be created in the root where the program is saved. Attention: test_in.pgm must also be located there!
III. Final Notes:
The problem was suggested to me as part of the DSA (Data Structures and Algorithms) course, at the Faculty of Electronics, Telecommunications and Information Technology within the National University of Science and Technology Polytechnic of Bucharest.
Course Coordinator: Radu Hobincu.
November 2025.
Sources: https://cppreference.com/
*I used AI to help solve the problem and understand and fix the occurrence of some bugs.
*I used AI to translate this article from its Romanian variant.