Shooting in the dark When a camera records a black-and-white image in difficulty

Question

Shooting in the dark When a camera records a black-and-white image in difficulty conditions, for example when it is quite dark, the raw image may have a lot of noise, as in the example below: How to recover the denoised image (on the right) from a noisy raw image (it-ft)? That is, how to predict assignments of 0 (black) or 1 (white) to each pixel? We can assume that recorded raw pixels are correct more often than not. Also, we can make an assumption that neighboring pixels should often have the same value: for example, if we have one white pixel surrounded by black pixels, probably that is the effect of noise, and the pixel should be black. These two assumptions can be turned into a method for predicting the best 0/1 (black/white) assignment P(x) for each pixel x, by designing a scheme that assigns a penalty to every possible predicted denoised image, and picks the image with lowest penalty: 0 If two neighboring pixels x and V have different predictions of their color, that is, if P(x)¢P(y), there will be a mismatch penalty M({x,y}). The value of M({x,y}) may be different for each unordered pair of neighboring pixels {x,y}. For pairs of pixels that are not neighbors, penalty is not defined: we do not care if they predict the same color or different colors. 0 For any pixel x, predicting value 0 (black) will lead to penalty B(x), and predicting value 1 (white) will lead to penalty W(x). That is, the penalty is B(x) if we predict P(x)-O and W(x) if we predict P(x)=1 in the denoised image. For example, if the raw recorder color for pixel x was 0 (black), we may set up penalties for that pixel as B(x)=1 and W(x)-20, that is, a much higher penalty for predicting x to be 1 (white). Penalties for different pixels may differ. Now, assume you make a prediction of the denoised image by assigning P(x) for every pixel x. You can judge how good that prediction is by calculating the aggregated penalty M+B+W based on the predictions P(x). That is, you would calculate the sum of all penalties M({x,y}) over all neighboring pixels x, y, plus sum of penalties B(x)+W(x) over all pixels x. The best denoised image, the one that will be returned to the user, is the one that has the lowest aggregated penalty M+B+W. You will be given penalty values M({x,y}) for all neighboring pairs of pixels x, y in the picture (for most pairs {x,y} there will be no penalty specified on input; you should conclude that these pixels are not neighbors), and penalty values B(x) and W(x) for all pixels x in the picture. Your task is to make, for every pixel x, an assignment P(x). The set of assignments over all pixels should lead to the lowest possible aggregated penalty M+B+W. All individual penalties M((x,y}), B(x) and W(x) are non'negative integers not exceeding 100. Input The first line specifies the number of pixels in the image, 2<=n<=200. Second line specifies the number of pairs of neighboring pixels, 1<=m<=10000. The next n lines describe the pixel penalties B and W. Each line has three numbers separated by spaces: pixel number x (in the range 1,....,n), followed by B(x), followed by W(X). The following m lines specify the pairs of neighboring pixels, and the associated mismatch penalties. Each line has three numbers separated by spaces: pixel number x, then pixel number y, and then the mismatch penalty value M({x,y}). Output Two numbers characterizing the best denoised image: number of pixels that have assignment P(x)=0 (i.e., black), followed by the total penalty M+B+W of the best denoised image. Sample Input 3 2 1 10 50 2 50 0 3 10 50 1 2 30 2 3 30 Sample Output 3 70 Raw and best denoised image corresponding to sample input/output Noisy raw image Best denoised image X: 1 2 3 X: 1 2 3 M+B+W=80

Explanation / Answer

Solution: See the code below:

------------------------------------------------

package imagenoiseprediction;

import java.util.Scanner;

/**
* ImageNoisePredictor class
*
*/
public class ImageNoisePredictor {
  
   private int whitePixel=1; //value for white pixel (1)
   private int blackPixel=0; //value for black pixel (0)
   private static int n; //number of pixels in the image
   private static int m; //number of pairs of neighboring pixels
   private static int pixels[]; //pixels in the image
   private static int P[]; //prediction for every pixel x
   private static int M[][]; //Mismatch penalty if P is mismatched for two pixel x and y. y is neighbouring pixel of x.
   private static int B[]; //penalty if prediction Px is for black pixel (0)
   private static int W[]; //penalty if prediction Px is for white pixel (1)
   private static int penaltySum[];
  
   //function to get input
   static void getInput() throws Exception
   {
       Scanner input = new Scanner(System.in);
      
       //read number of pixels
       n=input.nextInt();
       input.nextLine();
      
       //read number of pairs of neighbouring pixels
       m=input.nextInt();
       input.nextLine();
      
       //check if n is ok. If ok, then create B, W and pixels
       if(n>=2 && n<=200)
       {
           B=new int[n+1];
           W=new int[n+1];
           pixels=new int[n+1];
           P=new int[n+1];
           penaltySum=new int[n+1];
       }
       else
           throw new Exception("value out of range. Should be in >=2 and <=200.");
      
       //check if m is ok. If ok, then create M.
       if(m>=1 && m<=10000)
       {
           M=new int[m+1][n+1];
       }
       else
           throw new Exception("value out of range. Should be in >=1 and <=10000.");
      
       //read next n lines for x, B and W.
       for(int i=1;i<=n;i++)
       {
           String line=input.nextLine();
           String[] tokens=line.split(" ");
           pixels[i]=Integer.parseInt(tokens[0]);
           B[pixels[i]]=Integer.parseInt(tokens[1]);
           W[pixels[i]]=Integer.parseInt(tokens[2]);          
       }
      
       //read next m lines for x,y and M
       for(int i=1;i<=m;i++)
       {
           String line=input.nextLine();
           String[] tokens=line.split(" ");
           int x=Integer.parseInt(tokens[0]);
           int y=Integer.parseInt(tokens[1]);
           M[x][y]=Integer.parseInt(tokens[2]);                      
       }
      
   }
  
   //function to predict P
   //function to predict P
   static void calculateP()
   {
       //calculate P based on value of B and W
       for(int i=1;i<=n;i++)
       {
           if(B[pixels[i]] > W[pixels[i]])
               P[pixels[i]]=1;
           else if(B[pixels[i]] < W[pixels[i]])
               P[pixels[i]]=0;          
       }
      
       //update P based on value of M
       for(int i=1;i<=m;i++)
       {
           for(int j=1;j<=n;j++)
           {
               if(M[pixels[i]][pixels[j]] > 0)
               {
                   P[pixels[i]]=P[pixels[j]];
               }
           }
       }
   }
  
   //function to evaluate P
   static void evaluateP()
   {
       int totalM=0,totalPenalty=0,minPenalty=0, minPixel = 0;
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m;j++)
           {
               totalM+=M[j][i];
           }
           penaltySum[pixels[i]]=totalM+B[pixels[i]]+W[pixels[i]];
           minPenalty=penaltySum[pixels[i]];
           if(penaltySum[pixels[i]] < minPenalty)
           {
               minPenalty=penaltySum[pixels[i]];
               minPixel=pixels[i];
           }
           System.out.println(minPixel+" "+penaltySum[minPixel]);
       }
              
   }
   /**
   * @param args
   */
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       try {
           ImageNoisePredictor.getInput();
           ImageNoisePredictor.calculateP();
           ImageNoisePredictor.evaluateP();
       } catch (Exception e) {
           // TODO Auto-generated catch block
           e.printStackTrace();
       }

   }

}

---------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.