title: Algorithm for software keystone correction
body: <p>As part of my software I'm looking to write a keystone correction filter to avoid the tombstone / keystone effect you can get when projectors are displayed at an angle not perpendicular to the screen.</p>
  
  <p>At present I've got something working, but it's incredibly slow (~100ms for the whole image) and ideally I'd want something a lot faster (preferably in the 10ms range.) I'm essentially just looping over the whole image pixel by pixel and copying the pixels I want into a new array, then setting the new image's rgb contents to this new array:</p>
  
  <pre><code>public BufferedImage getCorrectedImage() {
      double width = originalImage.getWidth(null) * 0.5;
      double increment = (originalImage.getWidth(null) - width)/originalImage.getHeight();
  
      BufferedImage ret = new BufferedImage(originalImage.getWidth(null), originalImage.getHeight(null), BufferedImage.TYPE_INT_ARGB);
  
      for (int h = 0; h &lt; originalImage.getHeight(); h++) {
          int[] arr = new int[originalImage.getWidth()];
          for (int w = 0; w &lt; originalImage.getWidth(); w++) {
              arr[w] = originalImage.getRGB(w, h);
          }
          int[] newPixels = getShortLine(arr, (int) (width + 0.5));
  
          for (int w = 0; w &lt; originalImage.getWidth(); w++) {
              ret.setRGB(w, h, newPixels[w]);
          }
          width += increment;
      }
  
      return ret;
  }
  
  private int[] getShortLine(int[] original, int newSize) {
      int[] newArr = new int[original.length];
      double scale = original.length / newSize;
      int start = (original.length - newSize) / 2;
      int end = original.length - ((original.length - newSize) / 2);
      for (int i = start; i &lt; end-1; i++) {
          newArr[i] = original[(int) ((i - start) * scale)];
      }
      return newArr;
  }
  </code></pre>
  
  <p>What would be the best way about doing this? A custom affine transform was initially what I was going to look at but I couldn't find any code / examples around to point me in the right direction. Is there a better way of achieving the result I want than the above?</p>