Skip to content

Instantly share code, notes, and snippets.

@BurntPizza
Last active April 26, 2018 13:35
Show Gist options
  • Save BurntPizza/a3830c2d25f0b0be6120 to your computer and use it in GitHub Desktop.
Save BurntPizza/a3830c2d25f0b0be6120 to your computer and use it in GitHub Desktop.
Quick seam carving demo -- https://en.wikipedia.org/wiki/Seam_carving
import java.awt.*;
import java.awt.event.ComponentAdapter;
import java.awt.event.ComponentEvent;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.concurrent.*;
import javax.imageio.ImageIO;
import javax.swing.JComponent;
import javax.swing.JFrame;
//
// Note this isn't seam carving proper, as it only greedily computes 1 low-cost seam at a time and immediately removes it,
// rather than computing all of them and picking the lowest cost one.
//
// Also only does horizontal shrinking.
// Uses regular bilinear scaling for 'preview' while actual carving happens.
//
@SuppressWarnings("serial")
public class Carving extends JComponent {
public static void main(String[] a) {
JFrame frame = new JFrame();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(new Carving());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
private BufferedImage image;
private volatile BufferedImage current;
private volatile int cw, ch;
private ExecutorService requestService = Executors.newSingleThreadExecutor();
{
try {
image = ImageIO.read(new File("image.jpg"));
BufferedImage newImage = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_INT_ARGB);
Graphics g = newImage.getGraphics();
g.drawImage(image, 0, 0, null);
g.dispose();
image = newImage;
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
addComponentListener(new ComponentAdapter() {
@Override
public void componentResized(ComponentEvent e) {
if (current == null) {
current = new BufferedImage(image.getWidth(), image.getHeight(), image.getType());
cw = image.getWidth();
ch = image.getHeight();
}
// only doing horizontal scaling atm
else if (current.getWidth() != getWidth()) {
request(image, Math.min(image.getWidth(), getWidth()), getHeight());
}
}
});
setSize(image.getWidth(), image.getHeight());
setMaximumSize(getSize());
setPreferredSize(getSize());
seamCarve(image, Math.min(image.getWidth(), getWidth()), getHeight());
}
@Override
public void paint(Graphics g) {
g.clearRect(0, 0, getWidth(), getHeight());
((Graphics2D) g).setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
g.drawImage(current.getSubimage(0, 0, cw, ch), 0, 0, getWidth(), getHeight(), null);
}
private volatile Future<?> currentTask;
private void request(BufferedImage img, int nw, int nh) {
if (currentTask != null) {
currentTask.cancel(true);
}
currentTask = requestService.submit(() -> seamCarve(img, nw, nh));
}
public void seamCarve(BufferedImage img, int nw, int nh) {
if (current != null && current.getWidth() == nw) {
return;
}
long time = System.nanoTime();
final int[] imgData = Util.getIntBuffer(img);
final byte[] e = (byte[]) Util.alloc(imgData.length, byte.class);
Util.energyThreaded(imgData, e, img.getWidth());
final int[] tData = (int[]) Util.alloc(imgData.length, int.class);
System.arraycopy(imgData, 0, tData, 0, imgData.length);
if (loop(nw, img, e, tData)) {
cw = nw;
ch = nh;
System.arraycopy(tData, 0, Util.getIntBuffer(current), 0, tData.length);
System.out.println((System.nanoTime() - time) / 1000000);
repaint();
}
Util.free(e);
Util.free(tData);
}
// greedy
private boolean loop(int nw, BufferedImage img, byte[] e, int[] imgData) {
final int w = img.getWidth();
int[] minSeam = (int[]) Util.alloc(image.getHeight(), int.class);
int[] scratchSeam = (int[]) Util.alloc(image.getHeight(), int.class);
int iWidth = image.getWidth();
boolean returnVal = true;
// compute a bunch of seams, remove one with lowest cost
outer: while (nw < iWidth) {
int numSeams = 0;
int rowsChecked = 0;
final int nwo = nw - 1;
int minCost = Integer.MAX_VALUE;
// cheating a bit: only try seams every 3rd column,
// doesn't affect too much since they usually merge anyway
xloop: for (int x = 1; x < nw; x += 3) {
if (Thread.interrupted()) { // in case of currentTask.cancel() from above
returnVal = false;
break outer;
}
numSeams++;
int cx = x;
int cost = e[cx] & 0xFF;
for (int y = 0; y < img.getHeight() - 1; ++y) {
scratchSeam[y] = cx;
int a = cx > 0 ? e[y * w + w + cx - 1] & 0xFF : Integer.MAX_VALUE;
int b = e[y * w + w + cx] & 0xFF;
int c = cx < nwo ? e[y * w + w + cx + 1] & 0xFF : Integer.MAX_VALUE;
int v = Math.min(a, Math.min(b, c));
assert v != Integer.MAX_VALUE;
int sx = cx + (v == b ? 0 : v == a ? -1 : 1);
cx = sx;
cost += v;
rowsChecked++;
if (cost >= minCost) {
continue xloop;
}
}
// found a new lowest-cost seam
minCost = cost;
System.arraycopy(scratchSeam, 0, minSeam, 0, minSeam.length);
}
iWidth--;
removeVertical(minSeam, imgData, w, iWidth);
removeVertical(minSeam, e, w, iWidth);
//System.out.println(rowsChecked / (float) (numSeams * img.getHeight()));
}
Util.free(minSeam);
Util.free(scratchSeam);
return returnVal;
}
// note, we're not updating the energy array, probably getting a quality loss for that
private static void removeVertical(int[] seam, Object array, int width, int shift) {
for (int i = 0; i < seam.length; ++i) {
int x = seam[i];
System.arraycopy(array, width * i + x + 1, array, width * i + x, shift - 1 - x);
}
}
}
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferInt;
import java.lang.reflect.Array;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.RecursiveAction;
//
// Some utilities such as memory management and single and multi threaded ways of
// computing the energy function, in this case the Sobel Operator.
// See https://en.wikipedia.org/wiki/Sobel_operator
//
// There was some more stuff for experiments, but it wasn't relevant.
//
public class Util {
private static final Map<Point, Object> mem = new HashMap<>();
public static final Object alloc(int size, Class<?> type) {
Point p = new Point(size, type.hashCode()); // didn't feel like making a Pair class
Object o = mem.get(p);
return (o == null || Array.getLength(o) < size) ? Array.newInstance(type, size) : mem.remove(p);
}
public static final void free(Object array) {
Point p = new Point(Array.getLength(array), array.getClass().getComponentType().hashCode());
mem.put(p, array);
}
public static final void energyThreaded(int[] argb, byte[] energy, int width) {
assert argb.length <= energy.length;
final int start = width + 1;
final int end = argb.length - width - 1;
new EnergySubAction(argb, energy, width, start, end).fork().join();
}
/**
* Fills energy[] with the energy function of argb[]
*/
public static final void energy(int[] argb, byte[] energy, int width) {
assert argb.length <= energy.length;
final int end = argb.length - width - 1;
for (int i = width + 1; i < end; i += 1) {
energy[i] = energy(i, argb, width);
}
}
public static final byte energy(int i, int[] argb, int width) {
int nw = luma(argb[i - width - 1]);
int n = luma(argb[i - width]) << 1;
int ne = luma(argb[i - width + 1]);
int w = luma(argb[i - 1]) << 1;
int e = luma(argb[i + 1]) << 1;
int sw = luma(argb[i + width - 1]);
int s = luma(argb[i + width]) << 1;
int se = luma(argb[i + width + 1]);
int sumX = ne + e + se - nw - w - sw;
int sumY = nw + n + ne - sw - s - se;
return (byte) Math.max(0, Math.min(Math.abs(sumX) + Math.abs(sumY), 255));
}
private static final int luma(int rgb) {
int r = (rgb >> 16) & 0xFF;
int g = (rgb >> 8) & 0xFF;
int b = (rgb) & 0xFF;
// approximate
return ((r << 1) + r + b + (g << 2)) >> 3;
}
public static final int[] getIntBuffer(BufferedImage img) {
if (img.getType() != BufferedImage.TYPE_INT_ARGB && img.getType() != BufferedImage.TYPE_INT_ARGB_PRE) {
throw new IllegalArgumentException("Image must be of INT type");
}
return ((DataBufferInt) img.getRaster().getDataBuffer()).getData();
}
// still not sure about this whole fork join api
// wanted to try something different than the usual y-axis slicing into a thread pool
@SuppressWarnings("serial")
private static final class EnergySubAction extends RecursiveAction {
private static final int THRESHOLD = (1 << 16);
private final int[] argb;
private final byte[] energy;
private final int width, start, end;
EnergySubAction(int[] argb, byte[] energy, int width, int start, int end) {
assert start <= end;
this.argb = argb;
this.energy = energy;
this.width = width;
this.start = start;
this.end = end;
}
@Override
protected void compute() {
if (end - start <= THRESHOLD) {
for (int i = start; i < end; i += 1) {
energy[i] = energy(i, argb, width);
}
} else {
int mid = (start + end) >>> 1;
invokeAll(
new EnergySubAction(argb, energy, width, start, mid),
new EnergySubAction(argb, energy, width, mid, end));
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment