title: Whats wrong with this nearest neighbor algorithm for image scaling?
body: <p>I've been hunkered for days trying to find out what's wrong with my nearest neighbor interpolation when scaling an image half its size. Im using Rust but I don't think it matters as much as the algorithm:</p>
  
  <pre><code>/// Interpolate using nearest neighbor.
  pub fn nearest(mut src: &amp;mut Image, w2: i32, h2: i32) -&gt; RasterResult&lt;()&gt; {
  
      // Compute scale
      let x_scale: f64 = src.width as f64 / w2 as f64;
      let y_scale: f64 = src.height as f64 / h2 as f64;
  
      // Create destination image
      let mut dest = Image::blank(w2, h2);
  
      // Loop thru destination image's pixels
      for y2 in 0..h2 {
          for x2 in 0..w2 {
  
              // Get location from src using nearest neighbor
              let x1: i32 = ( x2 as f64 * x_scale ).floor() as i32;
              let y1: i32 = ( y2 as f64 * y_scale ).floor() as i32;
              let pixel = try!(src.get_pixel(x1, y1));
  
              // Apply the pixels
              try!(dest.set_pixel(x2, y2, pixel));
          }
      }
  
      // Update the source image
      src.width = dest.width;
      src.height = dest.height;
      src.bytes = dest.bytes;
  
      Ok(())
  }
  </code></pre>
  
  <p>My calling code:</p>
  
  <pre><code>// Open
  let mut image = raster::open(r"test.png").unwrap();
  
  // Resize to half
  raster::interpolate::nearest(&amp;mut image, 256, 128).unwrap();
  
  // Save
  raster::save(&amp;image, r"out.png").unwrap();
  </code></pre>
  
  <p>It works fine for regular images but not on special cases. 
  Here is the test image:
  <a href="https://i.stack.imgur.com/XQX3j.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XQX3j.png" alt="test image"></a></p>
  
  <p>Scaled to half with my code:</p>
  
  <p><a href="https://i.stack.imgur.com/EUJsf.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/EUJsf.png" alt="scaled to half with my code"></a></p>
  
  <p>For comparison here is Photoshop's:</p>
  
  <p><a href="https://i.stack.imgur.com/0pP6d.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/0pP6d.png" alt="Scaled to half with Photoshop&#39;s"></a></p>
  
  <p>I tested with GD and it yields similar results to Photoshop.</p>
  
  <p>My investigation leads me to think that my computation of the source pixel (red squares) is off by one as compared to the others (green squares):</p>
  
  <p><a href="https://i.stack.imgur.com/qdTc6.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qdTc6.png" alt="zoom of problem area"></a></p>
  
  <p>I also tried looking <a href="https://github.com/libgd/libgd/blob/00bbb69cc3fd7223e9fc7f01dd3d87c2956de93b/src/gd.c#L3229" rel="nofollow noreferrer">into GD's source code</a> to get a clue, but I don't fully understand what it does.</p>
  
  <p>To clarify, I am not talking about using a different interpolation method such as bilinear and bicubic. I am comparing my nearest neighbor algorithm and its result to the result of Photoshop and GD's nearest neighbor algorithm. I am not asking why my results in Photoshop are ugly because I used nearest neighbor algorithm.</p>
  
  <p>(Test image courtesy of Jonas Berlin via <a href="https://web.archive.org/web/20160112115812/http://www.4p8.com/eric.brasseur/gamma.html" rel="nofollow noreferrer">Eric Brasseur</a> )</p>