Sometimes I need a Lossless Screenshot Resizer

Question

Sometimes I need to write more documentation than just comments in code. And sometimes, those explanations need screenshots. Sometimes the conditions to get such a screenshot are so weird that I ask a developer to take a screenshot for me. Sometimes the screenshot does not fit my specifications and I have to resize it so that it looks nicely.

As you can see, the circumstances for a need for the magic "Lossless Screenshot Resizer" are very unlikely. Anyway, for me it seems I need it every day. But it doesn't exist yet.

I've seen you here on PCG solve awesome graphical puzzles before, so I guess this one is rather boring for you...

Specification

• The program takes a screenshot of a single window as input
• The screenshot does not make use of glass effects or similar (so you don't need to deal with any background stuff that shines through)
• The input file format is PNG (or any other lossless format so that you don't have to deal with compression artifacts)
• The output file format is the same as the input file format
• The program creates a screenshot of different size as output. Minimum requirement is shrinking in size.
• The user shall specify the expected output size. If you can give hints about the minimum size your program can produce from the given input, that's helpful.
• The output screenshot must not have less information if interpreted by a human. You shall not remove text or image content, but you shall remove areas with background only. See examples below.
• If it is not possible to get the expected size, the program should indicate that and not simply crash or remove information without further notice.
• If the program indicates the areas which will be removed for verification reasons, that should increase its popularity.
• The program may need some other user input, e.g. to identify the starting point for optimization.

Rules

This is a popularity contest. The answer with most votes on 2015-03-08 gets accepted.

Examples

Windows XP screenshot. Original size: 1003x685 pixels.

Example areas (red: vertical, yellow: horizontal) that can be removed without losing any information (text or images). Note that the red bar isn't contiguous. This example doesn't indicate all possible pixels that could potentially be removed.

Losslessly resized: 783x424 pixels.

Windows 10 screenshot. Original size: 999x593 pixels.

Example areas which can be removed.

Losslessly resized screenshot: 689x320 pixels.

Note that it is ok that the title text ("Downloads") and "This folder is empty" are not centered any more. Of course, it would be nicer if it is centered, and if your solution provides that, it should become more popular.

Answer 1

Python

the function delrows deletes all but one duplicate rows and returns the transposed image, applying it twice also deletes the columns and transposes it back. Additionally threshold controls how many pixels can differ for two lines to be still considered the same

from scipy import misc
from pylab import *

im7 = misc.imread('win7.png')
im8 = misc.imread('win8.png')

def delrows(im, threshold=0):
    d = diff(im, axis=0)
    mask = where(sum((d!=0), axis=(1,2))>threshold)
    return transpose(im[mask], (1,0,2))

imsave('crop7.png', delrows(delrows(im7)))
imsave('crop8.png', delrows(delrows(im8)))

Flipping the comparator in mask from > to <= will instead output the removed areas which are mostly blank space.

golfed (because why not)
Instead of comparing each pixel it only looks at the sum, as a side effect this also converts the screenshot to greyscale and has trouble with sum-preserving permutations, like the down-arrow in the address bar of the Win8 screenshot

from scipy import misc
from pylab import*
f=lambda M:M[where(diff(sum(M,1)))].T
imsave('out.png', f(f(misc.imread('in.png',1))),cmap='gray')

Answer 2

Java: Try lossless and fallback to content-aware

(Best lossless result so far!)

When I first looked at this question I thought this is not a puzzle or challenge just someone desperately in need of a program and it's code ;) But it is in my nature to solve vision problems so I could not stop my self from trying this challenge!

I came up with the following approach and combination of algorithms.

In pseudo-code it looks like this:

function crop(image, desired) {
    int sizeChange = 1;
    while(sizeChange != 0 and image.width > desired){

        Look for a repeating and connected set of lines (top to bottom) with a minimum of x lines
        Remove all the lines except for one
        sizeChange = image.width - newImage.width
        image = newImage;
    }
    if(image.width > desired){
        while(image.width > 2 and image.width > desired){
           Create a "pixel energy" map of the image
           Find the path from the top of the image to the bottom which "costs" the least amount of "energy"
           Remove the lowest cost path from the image
           image = newImage;
        }
    }
}

int desiredWidth = ?
int desiredHeight = ?
Image image = input;

crop(image, desiredWidth);
rotate(image, 90);
crop(image, desiredWidth);
rotate(image, -90);

Used techniques:

• Intensity grayscale
• Dilation
• Equal column search and remove
• Seam-carving
• Sobel edge detection
• Thresholding

---

The Program

The program can crop screenshots lossless but has an option to fallback to content-aware cropping which is not 100% lossless. The arguments of the program can be tweaked to achieve better results.

Note: The program can be improved in many ways (I don't have that much spare time!)

Arguments

File name = file
Desired width = number > 0
Desired height = number > 0
Min slice width = number > 1
Compare threshold = number > 0
Use content aware = boolean
Max content aware cycles = number >= 0

Code

import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.ColorModel;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JOptionPane;

/**
 * @author Rolf Smit
 * Share and adapt as you like, but don't forget to credit the author!
 */
public class MagicWindowCropper {

    public static void main(String[] args) {
        if(args.length != 7){
            throw new IllegalArgumentException("At least 7 arguments are required: (file, desiredWidth, desiredHeight, minSliceSize, sliceThreshold, forceRemove, maxForceRemove)!");
        }

        File file = new File(args[0]);

        int minSliceSize = Integer.parseInt(args[3]); //4;
        int desiredWidth = Integer.parseInt(args[1]); //400;
        int desiredHeight = Integer.parseInt(args[2]); //400;

        boolean forceRemove = Boolean.parseBoolean(args[5]); //true
        int maxForceRemove = Integer.parseInt(args[6]); //40

        MagicWindowCropper.MATCH_THRESHOLD = Integer.parseInt(args[4]); //3;

        try {

            BufferedImage result = ImageIO.read(file);

            System.out.println("Horizontal cropping");

            //Horizontal crop
            result = doDuplicateColumnsMagic(result, minSliceSize, desiredWidth);
            if (result.getWidth() != desiredWidth && forceRemove) {
                result = doSeamCarvingMagic(result, maxForceRemove, desiredWidth);
            }

            result = getRotatedBufferedImage(result, false);


            System.out.println("Vertical cropping");

            //Vertical crop
            result = doDuplicateColumnsMagic(result, minSliceSize, desiredHeight);
            if (result.getWidth() != desiredHeight && forceRemove) {
                result = doSeamCarvingMagic(result, maxForceRemove, desiredHeight);
            }

            result = getRotatedBufferedImage(result, true);

            showBufferedImage("Result", result);

            ImageIO.write(result, "png", getNewFileName(file));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static BufferedImage doSeamCarvingMagic(BufferedImage inputImage, int max, int desired) {
        System.out.println("Seam Carving magic:");

        int maxChange = Math.min(inputImage.getWidth() - desired, max);

        BufferedImage last = inputImage;
        int total = 0, change;
        do {
            int[][] energy = getPixelEnergyImage(last);
            BufferedImage out = removeLowestSeam(energy, last);

            change = last.getWidth() - out.getWidth();
            total += change;
            System.out.println("Carves removed: " + total);
            last = out;
        } while (change != 0 && total < maxChange);

        return last;
    }

    private static BufferedImage doDuplicateColumnsMagic(BufferedImage inputImage, int minSliceWidth, int desired) {
        System.out.println("Duplicate columns magic:");

        int maxChange = inputImage.getWidth() - desired;

        BufferedImage last = inputImage;
        int total = 0, change;
        do {
            BufferedImage out = removeDuplicateColumn(last, minSliceWidth, desired);

            change = last.getWidth() - out.getWidth();
            total += change;
            System.out.println("Columns removed: " + total);
            last = out;
        } while (change != 0 && total < maxChange);
        return last;
    }


    /*
     * Duplicate column methods
     */

    private static BufferedImage removeDuplicateColumn(BufferedImage inputImage, int minSliceWidth, int desiredWidth) {
        if (inputImage.getWidth() <= minSliceWidth) {
            throw new IllegalStateException("The image width is smaller than the minSliceWidth! What on earth are you trying to do?!");
        }

        int[] stamp = null;
        int sliceStart = -1, sliceEnd = -1;
        for (int x = 0; x < inputImage.getWidth() - minSliceWidth + 1; x++) {
            stamp = getHorizontalSliceStamp(inputImage, x, minSliceWidth);
            if (stamp != null) {
                sliceStart = x;
                sliceEnd = x + minSliceWidth - 1;
                break;
            }
        }

        if (stamp == null) {
            return inputImage;
        }

        BufferedImage out = deepCopyImage(inputImage);

        for (int x = sliceEnd + 1; x < inputImage.getWidth(); x++) {
            int[] row = getHorizontalSliceStamp(inputImage, x, 1);
            if (equalsRows(stamp, row)) {
                sliceEnd = x;
            } else {
                break;
            }
        }

        //Remove policy
        int canRemove = sliceEnd - (sliceStart + 1) + 1;
        int mayRemove = inputImage.getWidth() - desiredWidth;

        int dif = mayRemove - canRemove;
        if (dif < 0) {
            sliceEnd += dif;
        }

        int mustRemove = sliceEnd - (sliceStart + 1) + 1;
        if (mustRemove <= 0) {
            return out;
        }

        out = removeHorizontalRegion(out, sliceStart + 1, sliceEnd);
        out = removeLeft(out, out.getWidth() - mustRemove);
        return out;
    }

    private static BufferedImage removeHorizontalRegion(BufferedImage image, int startX, int endX) {
        int width = endX - startX + 1;

        if (endX + 1 > image.getWidth()) {
            endX = image.getWidth() - 1;
        }
        if (endX < startX) {
            throw new IllegalStateException("Invalid removal parameters! Wow this error message is genius!");
        }

        BufferedImage out = deepCopyImage(image);

        for (int x = endX + 1; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                out.setRGB(x - width, y, image.getRGB(x, y));
                out.setRGB(x, y, 0xFF000000);
            }
        }
        return out;
    }

    private static int[] getHorizontalSliceStamp(BufferedImage inputImage, int startX, int sliceWidth) {
        int[] initial = new int[inputImage.getHeight()];
        for (int y = 0; y < inputImage.getHeight(); y++) {
            initial[y] = inputImage.getRGB(startX, y);
        }
        if (sliceWidth == 1) {
            return initial;
        }
        for (int s = 1; s < sliceWidth; s++) {
            int[] row = new int[inputImage.getHeight()];
            for (int y = 0; y < inputImage.getHeight(); y++) {
                row[y] = inputImage.getRGB(startX + s, y);
            }

            if (!equalsRows(initial, row)) {
                return null;
            }
        }
        return initial;
    }

    private static int MATCH_THRESHOLD = 3;

    private static boolean equalsRows(int[] left, int[] right) {
        for (int i = 0; i < left.length; i++) {

            int rl = (left[i]) & 0xFF;
            int gl = (left[i] >> 8) & 0xFF;
            int bl = (left[i] >> 16) & 0xFF;

            int rr = (right[i]) & 0xFF;
            int gr = (right[i] >> 8) & 0xFF;
            int br = (right[i] >> 16) & 0xFF;

            if (Math.abs(rl - rr) > MATCH_THRESHOLD
                    || Math.abs(gl - gr) > MATCH_THRESHOLD
                    || Math.abs(bl - br) > MATCH_THRESHOLD) {
                return false;
            }
        }
        return true;
    }


    /*
     * Seam carving methods
     */

    private static BufferedImage removeLowestSeam(int[][] input, BufferedImage image) {
        int lowestValue = Integer.MAX_VALUE; //Integer overflow possible when image height grows!
        int lowestValueX = -1;

        // Here be dragons
        for (int x = 1; x < input.length - 1; x++) {
            int seamX = x;
            int value = input[x][0];
            for (int y = 1; y < input[x].length; y++) {
                if (seamX < 1) {
                    int top = input[seamX][y];
                    int right = input[seamX + 1][y];
                    if (top <= right) {
                        value += top;
                    } else {
                        seamX++;
                        value += right;
                    }
                } else if (seamX > input.length - 2) {
                    int top = input[seamX][y];
                    int left = input[seamX - 1][y];
                    if (top <= left) {
                        value += top;
                    } else {
                        seamX--;
                        value += left;
                    }
                } else {
                    int left = input[seamX - 1][y];
                    int top = input[seamX][y];
                    int right = input[seamX + 1][y];

                    if (top <= left && top <= right) {
                        value += top;
                    } else if (left <= top && left <= right) {
                        seamX--;
                        value += left;
                    } else {
                        seamX++;
                        value += right;
                    }
                }
            }
            if (value < lowestValue) {
                lowestValue = value;
                lowestValueX = x;
            }
        }

        BufferedImage out = deepCopyImage(image);

        int seamX = lowestValueX;
        shiftRow(out, seamX, 0);
        for (int y = 1; y < input[seamX].length; y++) {
            if (seamX < 1) {
                int top = input[seamX][y];
                int right = input[seamX + 1][y];
                if (top <= right) {
                    shiftRow(out, seamX, y);
                } else {
                    seamX++;
                    shiftRow(out, seamX, y);
                }
            } else if (seamX > input.length - 2) {
                int top = input[seamX][y];
                int left = input[seamX - 1][y];
                if (top <= left) {
                    shiftRow(out, seamX, y);
                } else {
                    seamX--;
                    shiftRow(out, seamX, y);
                }
            } else {
                int left = input[seamX - 1][y];
                int top = input[seamX][y];
                int right = input[seamX + 1][y];

                if (top <= left && top <= right) {
                    shiftRow(out, seamX, y);
                } else if (left <= top && left <= right) {
                    seamX--;
                    shiftRow(out, seamX, y);
                } else {
                    seamX++;
                    shiftRow(out, seamX, y);
                }
            }
        }

        return removeLeft(out, out.getWidth() - 1);
    }

    private static void shiftRow(BufferedImage image, int startX, int y) {
        for (int x = startX; x < image.getWidth() - 1; x++) {
            image.setRGB(x, y, image.getRGB(x + 1, y));
        }
    }

    private static int[][] getPixelEnergyImage(BufferedImage image) {

        // Convert Image to gray scale using the luminosity method and add extra
        // edges for the Sobel filter
        int[][] grayScale = new int[image.getWidth() + 2][image.getHeight() + 2];
        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                int rgb = image.getRGB(x, y);
                int r = (rgb >> 16) & 0xFF;
                int g = (rgb >> 8) & 0xFF;
                int b = (rgb & 0xFF);
                int luminosity = (int) (0.21 * r + 0.72 * g + 0.07 * b);
                grayScale[x + 1][y + 1] = luminosity;
            }
        }

        // Sobel edge detection
        final double[] kernelHorizontalEdges = new double[] { 1, 2, 1, 0, 0, 0, -1, -2, -1 };
        final double[] kernelVerticalEdges = new double[] { 1, 0, -1, 2, 0, -2, 1, 0, -1 };

        int[][] energyImage = new int[image.getWidth()][image.getHeight()];

        for (int x = 1; x < image.getWidth() + 1; x++) {
            for (int y = 1; y < image.getHeight() + 1; y++) {

                int k = 0;
                double horizontal = 0;
                for (int ky = -1; ky < 2; ky++) {
                    for (int kx = -1; kx < 2; kx++) {
                        horizontal += ((double) grayScale[x + kx][y + ky] * kernelHorizontalEdges[k]);
                        k++;
                    }
                }
                double vertical = 0;
                k = 0;
                for (int ky = -1; ky < 2; ky++) {
                    for (int kx = -1; kx < 2; kx++) {
                        vertical += ((double) grayScale[x + kx][y + ky] * kernelVerticalEdges[k]);
                        k++;
                    }
                }

                if (Math.sqrt(horizontal * horizontal + vertical * vertical) > 127) {
                    energyImage[x - 1][y - 1] = 255;
                } else {
                    energyImage[x - 1][y - 1] = 0;
                }
            }
        }

        //Dilate the edge detected image a few times for better seaming results
        //Current value is just 1...
        for (int i = 0; i < 1; i++) {
            dilateImage(energyImage);
        }
        return energyImage;
    }

    private static void dilateImage(int[][] image) {
        for (int x = 0; x < image.length; x++) {
            for (int y = 0; y < image[x].length; y++) {
                if (image[x][y] == 255) {
                    if (x > 0 && image[x - 1][y] == 0) {
                        image[x - 1][y] = 2; //Note: 2 is just a placeholder value
                    }
                    if (y > 0 && image[x][y - 1] == 0) {
                        image[x][y - 1] = 2;
                    }
                    if (x + 1 < image.length && image[x + 1][y] == 0) {
                        image[x + 1][y] = 2;
                    }
                    if (y + 1 < image[x].length && image[x][y + 1] == 0) {
                        image[x][y + 1] = 2;
                    }
                }
            }
        }
        for (int x = 0; x < image.length; x++) {
            for (int y = 0; y < image[x].length; y++) {
                if (image[x][y] == 2) {
                    image[x][y] = 255;
                }
            }
        }
    }

    /*
     * Utilities
     */

    private static void showBufferedImage(String windowTitle, BufferedImage image) {
        JOptionPane.showMessageDialog(null, new JLabel(new ImageIcon(image)), windowTitle, JOptionPane.PLAIN_MESSAGE, null);
    }

    private static BufferedImage deepCopyImage(BufferedImage input) {
        ColorModel cm = input.getColorModel();
        return new BufferedImage(cm, input.copyData(null), cm.isAlphaPremultiplied(), null);
    }

    private static final BufferedImage getRotatedBufferedImage(BufferedImage img, boolean back) {
        double oldW = img.getWidth(), oldH = img.getHeight();
        double newW = img.getHeight(), newH = img.getWidth();

        BufferedImage out = new BufferedImage((int) newW, (int) newH, img.getType());
        Graphics2D g = out.createGraphics();
        g.translate((newW - oldW) / 2.0, (newH - oldH) / 2.0);
        g.rotate(Math.toRadians(back ? -90 : 90), oldW / 2.0, oldH / 2.0);
        g.drawRenderedImage(img, null);
        g.dispose();
        return out;
    }

    private static BufferedImage removeLeft(BufferedImage image, int startX) {
        int removeWidth = image.getWidth() - startX;

        BufferedImage out = new BufferedImage(image.getWidth() - removeWidth,
                image.getHeight(), image.getType());

        for (int x = 0; x < startX; x++) {
            for (int y = 0; y < out.getHeight(); y++) {
                out.setRGB(x, y, image.getRGB(x, y));
            }
        }
        return out;
    }

    private static File getNewFileName(File in) {
        String name = in.getName();
        int i = name.lastIndexOf(".");
        if (i != -1) {
            String ext = name.substring(i);
            String n = name.substring(0, i);
            return new File(in.getParentFile(), n + "-cropped" + ext);
        } else {
            return new File(in.getParentFile(), name + "-cropped");
        }
    }
}

---

Results

---

XP screenshot lossless without desired size (Max lossless compression)

Arguments: "image.png" 1 1 5 10 false 0

Result: 836 x 323

---

XP screenshot to 800x600

Arguments: "image.png" 800 600 6 10 true 60

Result: 800 x 600

The lossless algorithm removes about 155 horizontal lines than the algorithm falls back to content-aware removal therefor some artifacts can be seen.

---

Windows 10 screenshot to 700x300

Arguments: "image.png" 700 300 6 10 true 60

Result: 700 x 300

The lossless algorithm removes 270 horizontal lines than the algorithm falls back to content-aware removal which removes another 29. Vertical only the lossless algorithm is used.

---

Windows 10 screenshot content-aware to 400x200 (test)

Arguments: "image.png" 400 200 5 10 true 600

Result: 400 x 200

This was a test to see how the resulting image would look after severe use of the content-aware feature. The result is heavily damaged but not unrecognizable.

---

Answer 3

C#, algorithm like I would do it manually

This is my first image processing program and it took a while to implement with all that LockBits stuff etc. But I wanted it to be fast (using Parallel.For) to get an almost instant feedback.

Basically my algorithm is based on observations on how I remove pixels manually from a screenshot:

• I am starting from the right edge, because chances are higher that unused pixels are there.
• I define a threshold for edge detection in order to capture the system buttons correctly. For the Windows 10 screenshot, a threshold of 48 pixels works well.
• After the edge is detected (marked in red color below), I am looking for pixels of the same color. I take the minimum number of pixels found and apply it to all rows (marked violet).
• Then I start over again with edge detection (marked red), pixels of the same color (marked blue, then green, then yellow) and so forth

At the moment I do it horizontally only. The vertical result can use the same algorithm and operate on a 90° rotated image, so in theory it's possible.

Results

This is a screenshot of my application with detected regions:

And this is the result for the Windows 10 screenshot and 48 pixels threshold. The output is 681 pixels wide. Unfortunately it's not perfect (see "Search Downloads" and some of the vertical column bars).

And another one with 64 pixels threshold (567 pixels wide). This looks even better.

Overall result applying rotation to crop from all bottom as well (567x304 pixels).

For Windows XP, I needed to change the code a bit since the pixels are not exactly equal. I am applying a similarity threshold of 8 (difference in RGB value). Note some artifacts in the columns.

Code

Well, my first attempt on image processing. Doesn't look very good, does it? This only lists the core algorithm, not the UI and not the 90° rotation.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Threading.Tasks;

namespace LosslessScreenshotResizer.BL
{
    internal class PixelAreaSearcher
    {
        private readonly Bitmap _originalImage;

        private readonly int _edgeThreshold;
        readonly Color _edgeColor = Color.FromArgb(128, 255, 0, 0);
        readonly Color[] _iterationIndicatorColors =
        {
            Color.FromArgb(128, 0, 0, 255), 
            Color.FromArgb(128, 0, 255, 255), 
            Color.FromArgb(128, 0, 255, 0),
            Color.FromArgb(128, 255, 255, 0)
        };

        public PixelAreaSearcher(Bitmap originalImage, int edgeThreshold)
        {
            _originalImage = originalImage;
            _edgeThreshold = edgeThreshold;

            // cache width and height. Also need to do that because of some GDI exceptions during LockBits
            _imageWidth = _originalImage.Width;
            _imageHeight = _originalImage.Height;            
        }

        public Bitmap SearchHorizontal()
        {
            return Search();
        }

        /// <summary>
        /// Find areas of pixels to keep and to remove. You can get that information via <see cref="PixelAreas"/>.
        /// The result of this operation is a bitmap of the original picture with an overlay of the areas found.
        /// </summary>
        /// <returns></returns>
        private unsafe Bitmap Search()
        {
            // FastBitmap is a wrapper around Bitmap with LockBits enabled for fast operation.
            var input = new FastBitmap(_originalImage);
            // transparent overlay
            var overlay = new FastBitmap(_originalImage.Width, _originalImage.Height);

            _pixelAreas = new List<PixelArea>(); // save the raw data for later so that the image can be cropped
            int startCoordinate = _imageWidth - 1; // start at the right edge
            int iteration = 0; // remember the iteration to apply different colors
            int minimum;
            do
            {
                var indicatorColor = GetIterationColor(iteration);

                // Detect the edge which is not removable
                var edgeStartCoordinates = new PixelArea(_imageHeight) {AreaType = AreaType.Keep};
                Parallel.For(0, _imageHeight, y =>
                {
                    edgeStartCoordinates[y] = DetectEdge(input, y, overlay, _edgeColor, startCoordinate);
                }
                    );
                _pixelAreas.Add(edgeStartCoordinates);

                // Calculate how many pixels can theoretically be removed per line
                var removable = new PixelArea(_imageHeight) {AreaType = AreaType.Dummy};
                Parallel.For(0, _imageHeight, y =>
                {
                    removable[y] = CountRemovablePixels(input, y, edgeStartCoordinates[y]);
                }
                    );

                // Calculate the practical limit
                // We can only remove the same amount of pixels per line, otherwise we get a non-rectangular image
                minimum = removable.Minimum;
                Debug.WriteLine("Can remove {0} pixels", minimum);

                // Apply the practical limit: calculate the start coordinates of removable areas
                var removeStartCoordinates = new PixelArea(_imageHeight) { AreaType = AreaType.Remove };
                removeStartCoordinates.Width = minimum;
                for (int y = 0; y < _imageHeight; y++) removeStartCoordinates[y] = edgeStartCoordinates[y] - minimum;
                _pixelAreas.Add(removeStartCoordinates);

                // Paint the practical limit onto the overlay for demo purposes
                Parallel.For(0, _imageHeight, y =>
                {
                    PaintRemovableArea(y, overlay, indicatorColor, minimum, removeStartCoordinates[y]);
                }
                    );

                // Move the left edge before starting over
                startCoordinate = removeStartCoordinates.Minimum;
                var remaining = new PixelArea(_imageHeight) { AreaType = AreaType.Keep };
                for (int y = 0; y < _imageHeight; y++) remaining[y] = startCoordinate;
                _pixelAreas.Add(remaining);

                iteration++;
            } while (minimum > 1);


            input.GetBitmap(); // TODO HACK: release Lockbits on the original image 
            return overlay.GetBitmap();
        }

        private Color GetIterationColor(int iteration)
        {
            return _iterationIndicatorColors[iteration%_iterationIndicatorColors.Count()];
        }

        /// <summary>
        /// Find a minimum number of contiguous pixels from the right side of the image. Everything behind that is an edge.
        /// </summary>
        /// <param name="input">Input image to get pixel data from</param>
        /// <param name="y">The row to be analyzed</param>
        /// <param name="output">Output overlay image to draw the edge on</param>
        /// <param name="edgeColor">Color for drawing the edge</param>
        /// <param name="startCoordinate">Start coordinate, defining the maximum X</param>
        /// <returns>X coordinate where the edge starts</returns>
        private int DetectEdge(FastBitmap input, int y, FastBitmap output, Color edgeColor, int startCoordinate)
        {
            var repeatCount = 0;
            var lastColor = Color.DodgerBlue;
            int x;

            for (x = startCoordinate; x >= 0; x--)
            {
                var currentColor = input.GetPixel(x, y);
                if (almostEquals(lastColor,currentColor))
                {
                    repeatCount++;
                }
                else
                {
                    lastColor = currentColor;
                    repeatCount = 0;
                    for (int i = x; i < startCoordinate; i++)
                    {
                        output.SetPixel(i,y,edgeColor);
                    }
                }

                if (repeatCount > _edgeThreshold)
                {
                    return x + _edgeThreshold;
                }
            }
            return repeatCount;
        }

        /// <summary>
        /// Counts the number of contiguous pixels in a row, starting on the right and going to the left
        /// </summary>
        /// <param name="input">Input image to get pixels from</param>
        /// <param name="y">The current row</param>
        /// <param name="startingCoordinate">X coordinate to start from</param>
        /// <returns>Number of equal pixels found</returns>
        private int CountRemovablePixels(FastBitmap input, int y, int startingCoordinate)
        {
            var lastColor = input.GetPixel(startingCoordinate, y);
            for (int x=startingCoordinate; x >= 0; x--)
            {
                var currentColor = input.GetPixel(x, y);
                if (!almostEquals(currentColor,lastColor)) 
                {
                    return startingCoordinate-x; 
                }
            }
            return startingCoordinate;
        }

        /// <summary>
        /// Calculates color equality.
        /// Workaround for Windows XP screenshots which do not have 100% equal pixels.
        /// </summary>
        /// <returns>True if the RBG value is similar (maximum R+G+B difference is 8)</returns>
        private bool almostEquals(Color c1, Color c2)
        {
            int r = c1.R;
            int g = c1.G;
            int b = c1.B;
            int diff = (Math.Abs(r - c2.R) + Math.Abs(g - c2.G) + Math.Abs(b - c2.B));
            return (diff < 8) ;
        }

        /// <summary>
        /// Paint pixels that can be removed, starting at the X coordinate and painting to the right
        /// </summary>
        /// <param name="y">The current row</param>
        /// <param name="output">Overlay output image to draw on</param>
        /// <param name="removableColor">Color to use for drawing</param>
        /// <param name="width">Number of pixels that can be removed</param>
        /// <param name="start">Starting coordinate to begin drawing</param>
        private void PaintRemovableArea(int y, FastBitmap output, Color removableColor, int width, int start)
        {
            for(int i=start;i<start+width;i++)
            {
                output.SetPixel(i, y, removableColor);
            }
        }

        private readonly int _imageHeight;
        private readonly int _imageWidth;
        private List<PixelArea> _pixelAreas;

        public List<PixelArea> PixelAreas
        {
            get { return _pixelAreas; }
        }
    }
}

Answer 4

Haskell, using naive removal of duplicate sequential lines

Unfortunately, this module only provides a function with the very generic type Eq a => [[a]] -> [[a]], since I have no idea how to edit image files in Haskell, however, I'm certain it's possible to tranform a PNG image to a [[Color]] value and I'd imagine instance Eq Color to be easily definable.

The function in question is resizeL.

Code:

import Data.List

nubSequential []    = []
nubSequential (a:b) = a : g a b where
 g x (h:t)  | x == h =     g x t
            | x /= h = h : g h t
 g x []     = []

resizeL     = nubSequential . transpose . nubSequential . transpose

Explanation:

Note: a : b means element a prefixed to list of type of a, resulting in a list. This is the fundamental construction of lists. [] denotes the empty list.

Note: a :: b means a is of type b. For example, if a :: k, then (a : []) :: [k], where [x] denotes a list containing things of type x.
This means that (:) itself, without any arguments, :: a -> [a] -> [a]. The -> denotes a function from something to something.

The import Data.List simply gets some work some other people did for us and lets us use their functions without rewriting them.

First, define a function nubSequential :: Eq a => [a] -> [a].
This function removes subsequent elements of a list that are identical.
So, nubSequential [1, 2, 2, 3] === [1, 2, 3]. We will now abbreviate this function as nS.

If nS is applied to an empty list, nothing can be done, and we simple return an empty list.

If nS is applied to a list with contents, then actual processing can be done. For this, we need a second function, here in a where-clause, to use recursion, as our nS doesn't keep track of an element to compare to.
We name this function g. It works by comparing its first argument to the head of the list it's been given, and discarding the head if they match and calling itself on the tail with the old first argument. If they don't, it appends the head onto the tail, passed through itself with the head as the new first argument.
To use g, we give it the head of the argument of nS and the tail as its two arguments.

nS is now of type Eq a => [a] -> [a], taking a list and returning a list. It requires that we can check for equality between the elements as this is done in the function definition.

Then, we compose the functions nS and transpose using the (.) operator.
Composing functions means the following: (f . g) x = f (g (x)).

In our example, transpose rotates a table 90°, nS removes all sequential equal elements of the list, in this case other lists (that's what a table is), transpose rotates it back and nS again removes sequential equal elements. This is essentially removing subsequent duplicate rows an columns.

This is possible because if a is checkable for equality (instance Eq a), then [a] is, too.
In short: instance Eq a => Eq [a]