I am trying to create an algorithm that detects and counts dead pixels from an intensity map in .csv format. My current approach is to divide the value of the pixel I am testing by the value of the pixel immediately to the right (or, if on the far right side, the one to the left). If the dividend is less than some threshold (currently .9), then I mark it as a dead pixel.

My question is, is there a better/more efficient way to calculate if a pixel is dead?

Sample csv output:

3183    3176    3207    3183    3212
3211    3197    3198    3183    3191
3193    3177    1135    3185    3176
3175    3184    3188    3179    3181
3181    3165    3184    3187    3183

In this example, the middle pixel would be a "dead" pixel.

I am trying to create an algorithm that detects and counts dead pixels from an intensity map in .csv format. My current approach is to divide the value of the pixel I am testing by the value of the pixel immediately to the right (or, if on the far right side, the one to the left). If the dividend is less than some threshold (currently .9), then I mark it as a dead pixel.

My question is, is there a better/more efficient way to calculate if a pixel is dead?

Sample csv output:

3183    3176    3207    3183    3212
3211    3197    3198    3183    3191
3193    3177    1135    3185    3176
3175    3184    3188    3179    3181
3181    3165    3184    3187    3183

In this example, the middle pixel would be a "dead" pixel.

• javascript
• algorithm
• math
• optimization
• csv

• 2 @Jay: "[...] that detects and counts dead pixels from an intensity map". I guess he has the necessary data. How he got it and whether it's correct is subject to another question, however you can also interpret this question as "how to get fields which values are below local average". – Zeta Commented Jul 30, 2012 at 7:37
• 1 @Jay: You're probably thinking of monitor pixels; I think the OP is thinking of sensor pixels (digital camera etc.) – Tim Pietzcker Commented Jul 30, 2012 at 8:18

4 Answers 4

Efficiency

You'll need to look at each pixel at least once so there's no way your running time can ever beat the current O(n), where n is the number of pixels. Your algorithm uses a constant amount of memory, which is also optimal.

However, I'm not sure your algorithm is always correct. Do you have a way of avoiding paring consecutive dead pixels? Example input:

3183    3176    1135    1135    3212
                ^ Not detected

A More Accurate Way

I'm assuming you take the intensity of the neighboring pixel to avoid paring pixels that are in different areas of the screen since the screen's brightness might not be evenly distributed.

One approach to avoiding false negatives is to take the average of several nearby pixels, but this might not work if there are a lot of dead pixels in the area. You might try taking the max value out of all of the pixels in a small area. This way as long as a single pixel in the entire area is not dead all of the dead pixels will be detected.

How many pixels you sample would be determined by your tolerance for false negatives.

Your current approach won't help you if you have a cluster of dead pixels. It can also misinterpret a stuck pixel (pixel with 100% intensity) as valid pixel and the surrounding pixel as defect, depending on the image that was used to test the screen.

Instead calculate the overall average µ and variance σ² of your data and interpret the data as normal distributed. According to the 68-95-99.7 rule 95% of all data should be in the interval [µ-2σ,µ+2σ].

Lets have a look at your sample and determine whether this is true for your data:

var arr = "5000 3176 3207 3183 3212 3211 3197 3198 3183 3191 3193 3177 1135 3185 3176 3175 3184 3188 3179 3181 3181 3165 3184 3187 3183".split(" ");
var i = 0;
var avg = 0; // average/mean
var vri = 0; // variance
var sigma;   // sqrt(vri)

for(i = 0; i < arr.length; ++i){
    arr[i] = parseInt(arr[i]);
    avg += arr[i];
}
avg /= arr.length;

for(i = 0; i < arr.length; ++i){
    vri += (arr[i]-avg)*(arr[i]-avg);
}
vri /= (arr.length - 1);
sigma =  Math.sqrt(vri);

for(i = 0; i < arr.length; ++i){
    if(Math.abs(arr[i]-avg) > 2*sigma)
        console.log("entry "+i+" with value "+arr[i]+" probably dead");
}

This will result in the dead pixels (8% of total pixels) revealed. Note that I also added a pixel with a very high intensity, which is probably stuck:

entry 0 with value 5000 propably dead
entry 12 with value 1135 probably dead

However, there is one major drawback, as this approach will only work if the screen equally illuminated. Also stuck pixel cannot be detected if you recorded the intensity map with a plain white image. And, of course, if your data is scattered because the screen is pletely broken, this approach won't help you. Other than that it's easy to implement. You could also add a local check to filter false-positives.

Note that this algorithm has a fixed runtime of 3*n.

(The diagram has been created by Mwtoews)

It seems likely that you could have a legitimate sharp transition from light to dark or vice/versa in a real image - a sharp shadow line transitioning to bright sun or just the edge of a white object against a black background. So, looking only at the pixel to the right could easily generate some false positives.

What would be less likely to generate a false positive would be to pare a pixel to at least each of the four pixels around it (above, below, left, right). You would allow a sharp difference between one pixel and two of the four neighbors, but not a sharp difference between one pixel and all four neighbors since that one pixel singularity in a real image would be very unlikely.

You could even further eliminate false positives if you required a pixel to fail your test in multiple separate images (of different subjects).

As for the details of how to do this calculation, you can either do something like you already proposed, but pare against all four neighbors or a Google search for "dead pixel detection algorithm" yields a host of articles on various ideas.

if this is a real-life question (and we are talking about dead pixels in a camera):

take about 5 pictures. if a pixel has significantly different intensity from it's neighbors (f.e. 11x11 block's average, pare RGB separately) in most pictures, it is almost certainly dead/stuck.