Prior to implementing a BloomFilter along the lines of the interface described in the Guava project issue tracker, I’ve reviewed my sprawling personal collection of Java libraries to identify the all of the ad-hoc bit-processing related code I’ve written with a view to unifying it all into something more reusable.
To my surprise, much of the code didn’t actually deal with tricky bitwise processing, but with the practicalities of efficiently moving bit data between different (bytes, ints, longs, byte arrays, IO streams, Strings, BigIntegers etc). All of those bits have to come from somewhere I guess.
Of course, there was plenty of bit twiddling, but another obvious sticking point was supporting competing requirements for mutability and immutability, as is common when one is seeking to design APIs that are both robust and efficient.
So I’ve spent a bit of time combining everything I need for various binary processing tasks (bitwise operations, (im)mutability control, conversion to standard Java types) and the result is a single stand-alone class called BitVector.
The source code for the class is available under the Apache 2.0 licence from:
The class is mostly complete for my needs, though I haven’t yet begun to employ it in any of my projects.
For a better idea of what the class provides, the class Javadoc is included below.
BitVector stores fixed-length bit sequences of arbitrary length and provides a number of bit-wise operations, and methods for exposing the bit sequences as established java types.
In keeping with Java standards, bits are operated-on and exposed as big-endian. This means that, where bit sequences are input/output from methods, the least-significant bit is always on the right and the most significant bit is on the left. So, for example, the toString() method will contain the most significant bit in the character at index 0 in the string. Naturally, In the cases where this class is used without externalizing the bit representation, this distinction is irrelevant.
A consequence of this is that, in methods that are defined over ranges of bits, the from and to parameters define the rightmost and leftmost indices respectively. As per Java conventions, all from parameters are inclusive and all to parameters are exclusive.
Instances of this class may be aligned (see isAligned() and aligned(). Many operations will execute more efficiently on aligned instances. Instances may also be immutable (see isMutable(), mutable() and immutable()). In addition to a number of copying operations, the class also supports views; views create new BitVector instances that are backed by the same bit data, this allows applications to expose mutable BitVector instances ‘safely’ via immutable views.
The class extends Number which allows it to be treated as an extended length numeric type (albeit, one that doesn’t support any arithmetic operations). In addition to the regular number value methods on the interface, an bigIntValue() method is available that returns the BitVector as a positive, arbitrarily sized integer. Combined with the fromBigInteger() method, this allows, with some loss of performance, a range of arithmetic calculations to be performed.
The class also implements Iterable and provides methods to obtain ListIterator as one would for a List, but stops short of implementing the List interface. This allows a BitVector to be used with a range of Java language constructs and standard library classes.
The class is Serializable and Cloneable too (clones are shallow and essentially behave as a view of the original instance). For instances where more control over serialization is needed, read(InputStream) and write(OutputStream) methods are available, though better performance may result from calling toByteArray() and managing the writing outside this class.
In addition to all of the above methods outlined above, a full raft of bitwise operations are available, including:
Most such methods are available in both an operation specific version and operation parameterized version to cater for different application needs.
Performance should be adequate for most uses. There is scope to improve the performance of many methods, but none of the methods operate in anything more than linear time and inner loops are mostly ‘tight’. An implementation detail (which may be important on some platforms) is that, with some exceptions, none of the methods perform any object creation. The exceptions are: methods that require an object to be returned, floatValue(), doubleValue(), and situations where an operation is applied with overlapping ranges of bits, in which case it may be necessary to create a temporary copy of the BitVector.
The class is marked as final to ensure that immutable instances can be safely used in security sensitive code (eg. within a PrivilegedAction).
Building on the perfect minimal hash I’ve developed for Java String objects, I’ve developed an memory efficient implementation of Java’s Map interface.
View the map source code in SVN
The map implementation is not general purpose, it’s specifically targeted to situations where:
Even given these constraints, I frequently encounter situations where all of these apply:
Map for substitution into a query.Proxy implementations of setter/getter interfaces that are backed by a Map of values.The implementation stores the set of valid keys in an object that can be shared between ‘like’ maps. The keys are hashed perfectly so that the map values can be stored directly into a single object array; no entry objects are required. This means that the memory required to store large numbers of similar maps can . Furthermore, none of the basic map operations (put/get/contains etc.) performs any memory allocation. This means that for many applications both memory overhead and object churn is minimal.
From the javadocs:
Unlike regular
Mapimplementations, there is no default, or copy, constructor. Instead the map must be constructed around a set of possibleStringkeys. Only the keys supplied to a constructor may be used in the maps it constructs. Re-using constructors (by repeatedly using them to createParameterMapinstances) minimizes the memory required to store the map. Furthermore, the only map operations that allocate new objects are those methods that required to do so by theMapinterface; in-short, object creation strictly minimized. This makes the class ideal for environments where reducing GC overhead is important.
The source code is under the Apache 2.0 licence, built with Maven, and is available from my website’s google code project:
A minimal perfect hash is simply a bijection between a set of N objects and the first N integers. See the wikipedia page about perfect hashing for more information.
I’m looking to produce a fast and memory efficient map implementation over String keys and I want to use a perfect hash to pack values without risking collisions.
Casting around online for a Java implementation led me to Sux4J (this rather unpromising sounding library looks excellent and I’m going to take a closer look at it soon) but the implementations are too generic for my purposes.
So I’ve fashioned my own minimal perfect hashing algorithm for Java strings.I don’t know anything about the theory of such algorithms, but my approach was to build a data-structure as follows:
The gist of this approach is outlined visually in the following diagram. Here, the hashes for the strings “cat” and “dog” collide, so a small decision tree needs to be consulted in the case that either of these two are hashed to confirm which value should be returned.
There are some nuances in the actual implementation. For example, Strings are actually ordered by length and character sequence too; this assists the building of fast decision trees. Also each duplicated string stores its offset within the span to avoid scanning back to find the start of the span (I think there are better space/time trade-offs around this that I may investigate in the future.).
However, these complexities only come into play when there are collisions of the String hash function. The common case, even for fairly large numbers of strings, is that there are no collisions. This reduces the time complexity to a binary search over the integer array of hashcodes — not as fast as only taking the hashcode, but still fast. And even the exceptional case is still fairly fast since it typically needs to test candidate string’s length to determine which minimal hash value it should be assigned.
Note that the algorithm is designed to examine as little about the string as is necessary to determine the perfect hash value (this helps to make it fast). Furthermore, the algorithm does not keep a reference to the list of potential candidates for hashing (this helps to reduce memory overhead). As a consequence, the algorithm cannot necessarily distinguish valid candidates; though they are frequently identified as such, invalid string arguments may generate valid hashes.
The source code for this implementation is fully documented and is under the Apache 2.0 licence. It is available through my website’s Google code project
The project that’s been taking up so much of my time recently is to architect a complex B2B e-commerce system. This naturally requires some form of “monetary abstraction” which is something that Java doesn’t provide (quite a surprise really, when you think about some of the classes that have made it into the system libraries over the years).
This is also something that the Java community doesn’t appear to have addressed in any significant way. Faced with this situation on the current project, I contributed my own small collection of classes for dealing with monetary amounts via the expedient of open-sourcing them and then treating them as I would any other third-party library.
This is a one line example that just about sums-up the whole library. Here’s how you make $100:
new MoneyType(Locale.US).money(10).calc().multiply(BigDecimal.TEN).money();
A page containing all relevant links to downloads, documentation etc. is available on my website:
With just 30 minutes of coding, I knocked out a small - but pretty inefficient - class to generate an Ulam spiral. In my plot, dot radius increases with fewer unique prime factors; brightness increases with the total number of prime factors.
The source code, should anyone want it, is public domain and can be found at:
It’s surprising how fast Java can be for one-shot bespoke graphics tasks like this.
Reading posts on the android developer group prompted me to reread the Java Language Specification and confirmed that I had forgotten something very important about Java, specifically:
Thread contention for Java synchronized blocks is not guaranteed to be fair.
This matters, because if you have a situation where a ‘producer’ is delivering data to a ‘consumer’ via a synchronized data structure, the producer may be permanently blocked while the consumer polls for data even though the consumer is repeatedly taking and releasing the lock.
In the context of an Android application: if the producer is the event thread delivering events to an application created thread for processing, then it’s a potential (and surprising!) source of ANRs. This is exactly what was happening to me when I filed an issue I titled: “ANR arising from touch event dispatch”. If only I’d remembered that Java threads aren’t guaranteed to be fair, I wouldn’t have wasted hours producing a (mostly) reproducible test case.
You can avoid the problem by using a fair lock, but this is relatively expensive if you’re aiming to create a high performance application, like a game say, which I was (and still am). So instead I wrote a simple event queue for delivering motion events to a thread other than the main application thread based on a synchronization-free fixed-size circular buffer that uses volatiles to manage concurrency.
I’ve been using the class below, for a while now and haven’t encountered any issues with it. Then again, I could once have said that of the code it replaced…
import android.view.MotionEvent;
/**
* <p>
* A simple event queue for delivering motion events to a thread other
* than the main application thread. The implementation is based on a
* synchronization-free fixed-size circular buffer that uses volatiles
* to manage concurrency. Adding an event to the queue is allocation
* free. Removing an event from the queue is only allocation free if
* the event object has been recycled.
* </p>
*
* <p>
* The implementation assumes that calls to the add (resp. next) method
* are single threaded (ie. made on just one thread, or externally
* synchronized).
* </p>
*
* <p>
* NOTE: Mapping of the MotionEvent fields is incomplete and does not
* include historical data; this is easily addressed by modifying the
* implementation.
* </p>
*
* @author Tom Gibara
*/
// NOTE: The safe concurrency reliability of this implementation is based on:
// 1. Calls to the add and next methods are single threaded.
// 2. The mHead and mTail fields are volatile.
// 3. The mHead (resp. mTail) field is only modified in the next (resp. add) method.
// 4. Updates to the mHead and mTail methods are the last operations in any method.
public class MotionEventQueue {
private final int mSize;
private final long[] mDownTimes;
private final long[] mEventTimes;
private final int[] mActions;
private final float[] mXs;
private final float[] mYs;
private volatile int mHead;
private volatile int mTail;
public MotionEventQueue(int size) {
mSize = size;
mDownTimes = new long[size];
mEventTimes = new long[size];
mActions = new int[size];
mXs = new float[size];
mYs = new float[size];
mHead = 0;
mTail = 0;
}
public boolean addEvent(MotionEvent event) {
final int head = mHead;
final int tail = mTail;
int nextTail = tail + 1;
if (nextTail == mSize) nextTail = 0;
if (nextTail == head) return false;
mDownTimes[tail] = event.getDownTime();
mEventTimes[tail] = event.getEventTime();
mActions[tail] = event.getAction();
mXs[tail] = event.getX();
mYs[tail] = event.getY();
mTail = nextTail;
return true;
}
public MotionEvent nextEvent() {
int head = mHead;
if (head == mTail) return null;
MotionEvent event = MotionEvent.obtain(mDownTimes[head], mEventTimes[head], mActions[head], mXs[head], mYs[head], 0);
mHead = head == mSize - 1 ? 0 : head + 1;
return event;
}
}
This code is now available from my code repository
Okay, this has to be the ugliest class in my private sprawling Java computer vision library (and that really is an achievement). Everything I want to forget about Java image processing is in this class. One day I might come back here and document it.
In practice, it’s incredibly useful and will repay any kindness you show it; it’s just very raw.
package com.tomgibara.vision.image;
import java.awt.Container;
import java.awt.Graphics2D;
import java.awt.Insets;
import java.awt.RenderingHints;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
public class ImageUtil {
public enum IntensityModel {
AVERAGE, RED, GREEN, BLUE;
byte combine(int r, int g, int b) {
switch (this) {
case AVERAGE: return (byte) ((r + b + g) / 3);
case RED: return (byte) r;
case GREEN: return (byte) g;
case BLUE: return (byte) b;
default: throw new IllegalStateException();
}
}
byte combine(byte r, byte g, byte b) {
return combine( r & 0xff, g & 0xff, b & 0xff);
}
}
public static byte[] toByteIntensity(BufferedImage image, IntensityModel model, byte[] bytes) {
if (model == null) model = IntensityModel.AVERAGE;
int width = image.getWidth();
int height = image.getHeight();
switch(image.getType()) {
case BufferedImage.TYPE_BYTE_GRAY :
{
image.getData().getDataElements(0, 0, width, height, bytes);
return bytes;
}
case BufferedImage.TYPE_3BYTE_BGR :
{
byte[] data = (byte[]) image.getData().getDataElements(0, 0, width, height, null);
int i = 0;
for (int j = 0; j < data.length; j += 3) {
//TODO WTF!
//work around for bug 4886732
bytes[i++] = model.combine(data[j], data[j+1], data[j+2]);
//bytes[i++] = model.combine(data[j+2], data[j+1], data[j]);
}
return bytes;
}
case BufferedImage.TYPE_4BYTE_ABGR:
case BufferedImage.TYPE_4BYTE_ABGR_PRE:
{
byte[] data = (byte[]) image.getData().getDataElements(0, 0, width, height, null);
int i = 0;
for (int j = 0; j < data.length; j += 4) {
bytes[i++] = model.combine(data[j+3], data[j+2], data[j+1]);
}
return bytes;
}
case BufferedImage.TYPE_INT_ARGB:
case BufferedImage.TYPE_INT_ARGB_PRE:
case BufferedImage.TYPE_INT_RGB:
{
int[] data = (int[]) image.getData().getDataElements(0, 0, width, height, null);
for (int i = 0; i < data.length; i++) {
int d = data[i];
bytes[i] = model.combine((d >> 16) & 0xff, (d >> 8) & 0xff, d & 0xff);
}
return bytes;
}
case BufferedImage.TYPE_USHORT_GRAY:
{
short[] data = (short[]) image.getData().getDataElements(0, 0, width, height, null);
for (int i = 0; i < data.length; i++) {
bytes[i] = (byte) (data[i] >> 8);
}
return bytes;
}
default: throw new IllegalArgumentException("Unsupported image type: " + image.getType());
}
}
public static byte[] toByteIntensity(BufferedImage image, IntensityModel model) {
return toByteIntensity(image, model, new byte[image.getWidth() * image.getHeight()]);
}
public static BufferedImage fromByteIntensity(BufferedImage image, byte[] bytes) {
int width = image.getWidth();
int height = image.getHeight();
switch(image.getType()) {
case BufferedImage.TYPE_BYTE_BINARY:
case BufferedImage.TYPE_BYTE_GRAY :
{
image.getWritableTile(0,0).setDataElements(0, 0, width, height, bytes);
return image;
}
case BufferedImage.TYPE_INT_ARGB:
case BufferedImage.TYPE_INT_ARGB_PRE:
case BufferedImage.TYPE_INT_RGB:
{
int[] data = new int[width * height];
for (int i = 0; i < bytes.length; i++) {
int b = bytes[i] & 0xff;
data[i] = (((((0xff << 8) | b) << 8) | b) << 8) | b;
}
image.getWritableTile(0,0).setDataElements(0, 0, width, height, data);
return image;
}
case BufferedImage.TYPE_3BYTE_BGR:
{
byte[] data = new byte[width * height * 3];
int offset = 0;
for (int i = 0; i < bytes.length; i++) {
byte b = bytes[i];
data[offset++] = b;
data[offset++] = b;
data[offset++] = b;
}
image.getWritableTile(0,0).setDataElements(0, 0, width, height, data);
return image;
}
default: throw new IllegalArgumentException("Unsupported image type: " + image.getType());
}
}
public static BufferedImage fromByteIntensity(int width, int height, int imageType, byte[] bytes) {
BufferedImage image = new BufferedImage(width, height, imageType);
return fromByteIntensity(image, bytes);
}
public static BufferedImage fromByteRGB(BufferedImage image, byte[] reds, byte[] greens, byte[] blues) {
int width = image.getWidth();
int height = image.getHeight();
int size = width * height;
if (image.getType() != BufferedImage.TYPE_3BYTE_BGR) throw new IllegalArgumentException();
byte[] combined = new byte[3 * size];
int offset = 0;
for (int i = 0; i < size; i++) {
//Work around for bug 4886732
combined[offset++] = reds[i];
combined[offset++] = greens[i];
combined[offset++] = blues[i];
}
// System.arraycopy(reds, 0, combined, 0, size);
// System.arraycopy(greens, 0, combined, size, size);
// System.arraycopy(blues, 0, combined, 2*size, size);
image.getWritableTile(0,0).setDataElements(0,0,width,height,combined);
return image;
}
public static BufferedImage fromByteRGB(int width, int height, byte[] reds, byte[] greens, byte[] blues) {
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_3BYTE_BGR);
return fromByteRGB(image, reds, greens, blues);
}
public static int[] intFromByteRGB(byte[] reds, byte[] greens, byte[] blues) {
int[] pixels = new int[reds.length];
for (int i = 0; i < pixels.length; i++) {
pixels[i] = ((reds[i] & 0xff) << 16) | ((greens[i] & 0xff) << 8) | (blues[i] & 0xff);
}
return pixels;
}
public static int[] toIntRGB(BufferedImage image, int[] ints) {
int width = image.getWidth();
int height = image.getHeight();
switch(image.getType()) {
case BufferedImage.TYPE_BYTE_GRAY :
{
byte[] data = (byte[]) image.getData().getDataElements(0, 0, width, height, null);
for (int i = 0; i < data.length; i++) {
int v = data[i] & 0xff;
ints[i] = (v << 16) | (v << 8) | v;
}
return ints;
}
case BufferedImage.TYPE_3BYTE_BGR :
{
byte[] data = (byte[]) image.getData().getDataElements(0, 0, width, height, null);
int i = 0;
for (int j = 0; j < data.length; j += 3) {
//TODO WTF!
//work around for bug 4886732
ints[i++] = ((data[j] & 0xff) << 16) | ((data[j+1] & 0xff) << 8) | (data[j+2] & 0xff);
}
return ints;
}
case BufferedImage.TYPE_4BYTE_ABGR:
case BufferedImage.TYPE_4BYTE_ABGR_PRE:
{
byte[] data = (byte[]) image.getData().getDataElements(0, 0, width, height, null);
int i = 0;
for (int j = 0; j < data.length; j += 3) {
//TODO WTF!
//work around for bug 4886732
ints[i++] = ((data[j+1] & 0xff) << 16) | ((data[j+2] & 0xff) << 8) | (data[j+3] & 0xff);
}
return ints;
}
case BufferedImage.TYPE_INT_ARGB:
case BufferedImage.TYPE_INT_ARGB_PRE:
case BufferedImage.TYPE_INT_RGB:
{
image.getData().getDataElements(0, 0, width, height, ints);
return ints;
}
case BufferedImage.TYPE_USHORT_GRAY:
{
short[] data = (short[]) image.getData().getDataElements(0, 0, width, height, null);
for (int i = 0; i < data.length; i++) {
int v = (data[i] & 0xffff) >> 8;
ints[i] = (v << 16) | (v << 8) | v;
}
return ints;
}
default: throw new IllegalArgumentException("Unsupported image type: " + image.getType());
}
}
public static int[] toIntRGB(BufferedImage image) {
return toIntRGB(image, new int[image.getWidth() * image.getHeight()]);
}
public static BufferedImage fromIntRGB(BufferedImage image, int[] rgb) {
//TODO must support more types
if (image.getType() != BufferedImage.TYPE_INT_RGB) throw new IllegalArgumentException();
image.getWritableTile(0, 0).setDataElements(0, 0, image.getWidth(), image.getHeight(), rgb);
return image;
}
public static BufferedImage fromIntRGB(int width, int height, int[] rgb) {
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
return fromIntRGB(image, rgb);
}
public static byte[][] splitIntRGB(int[] rgb) {
byte[] rs = new byte[ rgb.length ];
byte[] gs = new byte[ rgb.length ];
byte[] bs = new byte[ rgb.length ];
for (int i = 0; i < rgb.length; i++) {
int p = rgb[i];
rs[i] = (byte) (p >> 16);
gs[i] = (byte) (p >> 8);
bs[i] = (byte) (p );
}
return new byte[][] { rs, gs, bs };
}
public static BufferedImage convertImage(BufferedImage source, int type) {
BufferedImage target = new BufferedImage(source.getWidth(), source.getHeight(), type);
Graphics2D g = target.createGraphics();
g.drawImage(source, null, null);
g.dispose();
return target;
}
public static JFrame showImage(String title, BufferedImage image) {
final JFrame f = new JFrame(title);
Container pane = f.getContentPane();
JButton display = new JButton(new ImageIcon(image));
display.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
f.dispose();
}
});
display.setMargin(new Insets(50, 50, 50, 50));
pane.add(display);
f.pack();
f.setLocationRelativeTo(null);
f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
f.setVisible(true);
return f;
}
public static BufferedImage duplicateImage(BufferedImage image) {
BufferedImage dup = new BufferedImage(image.getWidth(), image.getHeight(), image.getType());
image.copyData(dup.getWritableTile(0, 0));
dup.releaseWritableTile(0, 0);
return dup;
}
public static BufferedImage scaleImage(BufferedImage image, int width, int height) {
return scaleImage(image, image.getType(), width, height);
}
public static BufferedImage scaleImage(BufferedImage image, int type, int width, int height) {
BufferedImage scaled = new BufferedImage(width, height, type);
Graphics2D g = scaled.createGraphics();
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
g.drawImage(image, 0, 0, width, height, null);
g.dispose();
return scaled;
}
public static BufferedImage fromIntIntensity(int width, int height, int[] data, int shift) {
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_GRAY);
byte[] bytes = new byte[data.length];
for (int i = 0; i < bytes.length; i++) {
int v = Math.abs(data[i]);
v = v >> shift;
if (v > 255) v = 255;
bytes[i] = (byte) v;
}
image.getWritableTile(0, 0).setDataElements(0, 0, width, height, bytes);
image.releaseWritableTile(0, 0);
return image;
}
public static BufferedImage fromIntIntensityScaled(int width, int height, int[] data) {
int max = 0;
for (int d : data)
if (d > max) max = d;
else if (-d > max) max = -d;
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_GRAY);
byte[] bytes = new byte[data.length];
if (max > 0) {
for (int i = 0; i < bytes.length; i++) {
bytes[i] = (byte) (Math.abs(data[i]) * 255 / max);
}
}
image.getWritableTile(0, 0).setDataElements(0, 0, width, height, bytes);
image.releaseWritableTile(0, 0);
return image;
}
public static BufferedImage fromBooleans(int width, int height, boolean[] bools) {
byte[] data = new byte[width * height];
for (int i = 0; i < data.length; i++) {
data[i] = bools[i] ? (byte)255 : 0;
}
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_GRAY);
image.getWritableTile(0, 0).setDataElements(0, 0, width, height, data);
image.releaseWritableTile(0, 0);
return image;
}
public static int[][] bytesToInts(byte[][] bytes) {
int[][] ints = new int[bytes.length][];
for (int a = 0; a < bytes.length; a++) {
byte[] bs = bytes[a];
int[] is = new int[bs.length];
ints[a] = is;
for (int i = 0; i < bs.length; i++) {
is[i] = bs[i] & 0xff;
}
}
return ints;
}
public static byte[][] intsToBytes(int[][] ints) {
byte[][] bytes = new byte[ints.length][];
for (int a = 0; a < ints.length; a++) {
int[] is = ints[a];
byte[] bs = new byte[is.length];
bytes[a] = bs;
for (int i = 0; i < is.length; i++) {
int v = is[i];
if (v < 0) v = 0;
else if (v > 255) v = 255;
bs[i] = (byte) v;
}
}
return bytes;
}
public static void unscaledYUVToRGB(int[][] yuv) {
int length = yuv[0].length;
final int[] ys = yuv[0];
final int[] us = yuv[1];
final int[] vs = yuv[2];
for (int i = 0; i < length; i++) {
int y = ys[i];
int u = us[i];
int v = vs[i];
int g = (y-u-v) >> 2;
us[i] = g;
ys[i] = v + g;
vs[i] = u + g;
}
}
public static void rgbToUnscaledYUV(int[][] rgb) {
int length = rgb[0].length;
final int[] rs = rgb[0];
final int[] gs = rgb[1];
final int[] bs = rgb[2];
for (int i = 0; i < length; i++) {
int r = rs[i];
int g = gs[i];
int b = bs[i];
rs[i] = r + 2*g + b;
gs[i] = b-g;
bs[i] = r-g;
}
}
public static void rgbToScaledYUV(byte[][] rgb) {
int length = rgb[0].length;
final byte[] rs = rgb[0];
final byte[] gs = rgb[1];
final byte[] bs = rgb[2];
for (int i = 0; i < length; i++) {
int r = rs[i] & 0xff;
int g = gs[i] & 0xff;
int b = bs[i] & 0xff;
rs[i] = (byte) ((r + (g << 1) + b) >> 2);
gs[i] = (byte) ((b-g)/2);
bs[i] = (byte) ((r-g)/2);
}
}
public static void scaledYUVToRGB(byte[][] yuv) {
int length = yuv[0].length;
final byte[] ys = yuv[0];
final byte[] us = yuv[1];
final byte[] vs = yuv[2];
for (int i = 0; i < length; i++) {
int y = ys[i] & 0xff;
int u = us[i];
int v = vs[i];
int g = y - ((u+v)/2);
int r = g + (v*2);
int b = g + (u*2);
//TODO verify why these overflows occur
if (b < 0) b = 0;
if (r < 0) r = 0;
us[i] = (byte) g;
ys[i] = (byte) r;
vs[i] = (byte) b;
}
}
}
Spent a couple of hours this evening knocking out a quick TSP solver (greedily chooses shortest edges and then applies 2-opt). Solving for 500 cities requires about half a second. Visual inspection: looks okay. NEOS gives an optimal length of 1632 (not 568 as I first thought in my confusion), whereas this one has a length of 1800 (about 10% longer).
The result of a little experiment I conducted a while back: a simple algorithm that attempts to identify scenes in a video file that will combine to produce a mosaic of a target image.
It works surprisingly well for such a poor algorithm: lots of quality data + lots of time + low quality algorithm = acceptable results.
Observe that the algorithm attempts to match detail within each frame in an attempt to increase the effective resolution of the resulting mosaic.
Interestingly, the tendency of the algorithm to favour a good overall luminance match gives rise to its greatest weakness: a tendency to repeatedly use the same frames.
I’ve just finished reading this. It makes me wonder whether similarly segmenting the heap could be a fruitful approach for a garbage collector in Android. Using heuristics to target smaller collections at the most fruitful looking segment might keep pauses lower and improve throughput.
