You can view the algorithms I used and their resulting peak signal-to-noise ratio, PSNR, in table 1. I have not written down specific instructions for each algorithm but if you have questions about the algorithms feel free to contact me. The equation for finding the PSNR can be found on Wikipedia here.
Before testing any algorithms I wanted to see what I could expect for the PSNR boundaries. If you calculate the PSNR of an image to itself you will get infinity because there is only signal and no noise. However, once you change an image even slightly the PSNR is almost guaranteed to drop below 100. I found that if I changed one pixel of the original image by adding 1 to it’s color value the PSNR dropped to 96.293. And after replacing the odd-numbered lines in the original image with black lines I found the PSNR was 10.187. This let me know I could not expect a PSNR above 100 or below 10. Always a good thing to start out knowing your practical boundaries.
After trying out the 11 algorithms I found the max PSNR I could get was 34.031. This was accomplished using what I call the ‘direct averaging algorithm’. The results of this algorithm can be seen in figure 3.
Direct Averaging Algorithm
- Start at the beginning of an odd-numbered line.
- Choose a black pixel.
- Take the color values of the pixels directly above and below this black pixel.
- Average the two color values.
- Replace the black pixel’s color value with this averaged value.
- Repeat for every black pixel on an odd-numbered line.
For comparison, the results of another algorithm I call the ‘direct biggest algorithm’ can be seen in figure 4. The direct biggest algorithm gives a PSNR of 29.368 and is similar to the direct averaging algorithm but instead of using the averaged color value the biggest of the two color values is used to replace the black pixel.
The direct averaging algorithm was one of the first I tried and I was happy at the time. But I am slightly disappointed I did not achieve a higher PSNR. I feel there must be a way to to get a higher PSNR and I’m frustrated I haven’t thought of how. But the only reason I think there must be a better algorithm is because the algorithm I described seems too simple. I searched a litle on google to see if I could find a way to calculate a realistic practical optimum but I didn’t find anything. So for now I just have to live with a feeling that I can do better. That’s not such a bad thing though. :)
If you have any ideas how to achieve a higher PSNR I’d like to hear them!
Figure 1 – Original Image
Figure 2 – Original Image Missing Odd-Numbered Lines
Figure 3 – Resulting Image of the Direct Average Algorithm
Figure 4 – Resulting Image of the Direct Highest Algorithm
Table 1 – Algorithms and Resulting PSNRs (higher is better)
Original Image With Blacked Out Lines
PSNR = 10.1865
Direct Averaging Algorithm
PSNR = 34.0313
Hybrid1 – Threshold = 10
If the difference between the top and bottom pixels is less than the threshold choose the highest color, otherwise blend colors.
PSNR = 33.7630
Take Median of 3 Pixels Above and 3 Below
PSNR = 33.3099
Average 3 Pixels Above and 3 Below
PSNR = 31.7530
Take All Even Lines As One Image, Resize To Original Size
PSNR = 31.0262
Hybrid2 – Threshold = 10
If the difference between the top and bottom pixels is less than the threshold blend colors, otherwise choose highest color.
PSNR = 29.4632
Take Highest From Above and Below
PSNR = 29.3676
Take Lowest From Above and Below
PSNR = 29.3251
Replace Odd Lines With Even Lines
PSNR = 29.2886
Look At Bottom 3 Pixels, Find Closest to Top Pixel, Average Pixels
PSNR = 26.5942
Take Highest From 3 Above and 3 Below
PSNR = 23.5104
