Shapes: Implementing a Freehand Pencil Tool (Vectorizers)

If you google "how to implement a pencil tool in Java" you get a few results that basically tell you how to implement the right MouseListeners to record the mouse points. Then you have a giant polygon. (Or polyline, technically).

The problem is: this is ugly. It's acceptable for beginners, or prototypes: but we can do better.

What I want to do is smooth out this data. To replace the series of lines with attractive bezier curves. To the right is an image of what I'm looking for.

I'm not entirely sure what to call this project. (Is there an official word for this? Does anyone know?) It's a mix between "Vectorization" and "Beautification"? For now I created a simple interface called Vectorizer:

public interface Vectorizer {
 public void add(float x,float y,long t);
 public void reset();
 public GeneralPath getShape();
 public void getShape(GeneralPath path);
 public boolean isEmpty();
}

Results

I ended up with the following applet.




You can download this applet here (source included).

Implementation

The applet above demos the BasicVectorizer. In pseudocode it goes likes this:

currentPoint = 0;
while more points remain:
 lastPoint = currentPoint + 1;
 create cubic arc from currentPoint to lastPoint
 while arc is within the allowed error:
  lastPoint++;
  create cubic arc from currentPoint to lastPoint
 write arc
 currentPoint = lastPoint;

This seems to work well for far-away points, but it starts to suffer when several points are clustered together. The problem (for me) is it's hard to guess what the user is trying to do when the mouse moves in a small area: is the user drawing a sharp corner? Just drawing slowly? They might not be using a mouse at all -- maybe an assistive device doesn't track the way mice do?

So there's room for improvement, but it's a start.

Other Resources

The only other open-source pencil tool I'm familiar with is Werner's in JHotDraw. (The license is LGPL. I believe the classes involved are org.jhotdraw.geom.Bezier and org.jhotdraw.geom.BezierPath.)

Does anyone have other examples handy on the subject?

For now this meets my immediate needs, but maybe in the future I'll touch it up a little.

Images: BMPs and Thumbnails

This article address the subject: how do I quickly create a BMP thumbnail?

In my last article I presented an architecture that included a memory-efficient model for scaling images. This article will use that architecture to kick some scaling butt.

Surely (?) developers have come before me that tackled this issue, right? This sounds like something ImageIO might have addressed already, but when I googled "ImageIO to create BMP thumbnail" I didn't find any promising leads. (I did find this page which mentions the BMP reader doesn't support thumbnails.)

Reading BMPs

The trickiest part of this subject is: we need to be able to read BMPs. Yes, there is existing code that can do this. Mostly I'm thinking of ImageIO classes, but I'm sure there are other options too. The problem is: these interface with BufferedImages, and my goal here is interface with my new PixelIterator class.

So I dusted off the file specifications and wrote my own BMP decoder.

As of this writing: this decoder is not fully featured. It supports 1, 4, 8, 24 and 32-bit uncompressed BMPs, but nothing else. It is my experience that the vast majority of BMPs in the world are uncompressed, though.

This functionality is nicely wrapped up in a few static classes in the BmpDecoder.

Creating Thumbnails

With a BytePixelIterator to work with, and the previously established ScalingIterator: it's incredibly easy to scale BMP data on-the-fly.

public static BufferedImage createThumbnail(InputStream bmp,
Dimension maxSize) throws IOException {
   PixelIterator i = BmpDecoderIterator.get(bmp);
   int srcW = i.getWidth();
   int srcH = i.getHeight();

   float widthRatio = ((float)maxSize.width)/((float)srcW);
   float heightRatio = ((float)maxSize.height)/((float)srcH);
   float ratio = Math.min(widthRatio, heightRatio);

   if(ratio<1) {
     i = ScalingIterator.get(i, ratio);
   }
   return BufferedImageIterator.create( i, null );
}

Writing BMPs

Also for good measure: I included a BmpEncoder. The motivation for this class was actually for a separate project I may discuss later, but since it's related I'll include it here.

Results

So far you might be underwhelmed by this article: there's nothing especially clever or innovative here.

But consider this example. I have a folder on my computer called "bigpix". (A QA guy at work put this folder together.) I don't know where these files came from -- so I'm probably not legally allowed to distribute any of them -- but there's a file here called "ElPerroDelMar-Portratt.bmp". It's 2,469 pixels by 3,234 pixels.

If I wanted to create a thumbnail of this file that fit inside a 128x128 image, my first reaction is simply to use ImageIO to read the file and then scale that image to the appropriate size. This requires creating an image that is 2469*3234*(3 colors) bytes (22 MB). I just allocated 22 MB to create an eventual 48 KB image.

This is ridiculous. And if the user is trying to navigate a folder of two dozen similar images (and you're creating thumbnails on-the-fly for all of them): you just used over 512 MB of RAM.

The Bmp.jar (source included) compares the cost of creating a thumbnail using the ImageIO approach and the BmpDecoder class. Also (without scaling) it pits the encoding ability of ImageIO against BmpDecoder. Here is the output when I ask the Bmp.jar to work with the ElPerroDelMar image:

OS = Mac OS X (10.5.8), i386
Java Version = 1.5.0_24
apple.awt.graphics.UseQuartz = false

Running Thumbnail Tests...
BmpThumbnail: 72 ms, 332944 bytes RAM
ImageIO: 1065 ms, 23317200 bytes RAM

Running Encode Tests...
BmpEncoder: 585 ms, 332952 bytes RAM, 22987298 bytes file
ImageIO: 649 ms, 14932160 bytes RAM, 22987326 bytes file

As expected: the thumbnail generation is a huge improvement. The BmpDecoder takes less than 1.5% of the memory ImageIO uses, and less than 7% of the time.

I was surprised (but pleased) to see such a substantial advantage in the encoding tests, too. I'm not entirely sure what causes this, but the huge memory allocation suggests the ImageIO classes are extracting all the image data before writing anything (instead of efficiently piping the image data).

Images: Scaling Down

It's easy to create thumbnails of BufferedImages:

BufferedImage thumb = new BufferedImage( (int)(source.getWidth()*scale), (int)(source.getHeight()*scale), BufferedImage.TYPE_INT_ARGB );
Graphics2D g = thumb.createGraphics();
g.scale(scaleFactor, scaleFactor);
g.drawImage(source, 0, 0, null);
g.dispose()

... but when scaleFactor is small enough, the image quality really suffers. Sure I tried adding the right RenderingHints -- interpolation, quality, etc -- but they only barely made an improvement.

Here is a screenshot of the example that brought this to my attention:

As a sidenote: I should mention that this is only a problem using Sun's rendering engine. If we use Quartz on Mac: the scaling is great. However I swore of Quartz a long time ago (for this and that, among other reasons).

So if I'm not using Quartz, and I don't like how Java2D handles scaling: I wanted to explore other approaches to get better results.

Filthy Rich Clients

I really appreciate Laszlo pointing this out to me in the comments: Romain Guy already addressed the subject of smooth scaling in Filthy Rich Clients.

He clearly identified the problem: bilinear interpolation starts to fall apart when the scaling factor is less than 50%. (Which is often the case when you're creating thumbnails.) But at 50% it still looks good.

His solution was brilliantly simple: just scale multiple times. So if you want to scale to 25%: scale your source image at 50% twice. The code he uses (without comments/javadocs) is less than 50 lines. I found a copy here under an LGPL or BSD license.

The downside to this approach, though, is it's very wasteful. Consider creating a thumbnail of an image that is 4,000 x 3,000 pixels. We'd first scale it to 2,000 x 1,500. Then 1,000 x 750. Then 500 x 375. At 4 bytes per pixel: the intermediate two images add up to 14.3 MB of memory. Although these would be quickly discarded for garbage collection: I'd rather not rely on a spare 14 MB of memory to get the job done.

A Different Solution

In this immediate context I'm only interested in scaling BufferedImages. However in the long-term I want a slightly more abstract model. The ImageProducer class comes to mind, but it's too abstract; I want something that iterates up or down an image in rows at a time. Nothing more, nothing less.

So I wrote the PixelIterator, and it's two specific subclasses: BytePixelIterator and IntPixelIterator.

These classes iterate over an image -- either top-to-bottom or bottom-to-top -- reading entire rows at a time. The BufferedImageIterator iterates over the pixels in a BufferedImage -- which is all we need for this example.

The ScalingIterator is what took the longest time to write in this project. This is a subclass of PixelIterator that acts as a filter for incoming data. It reads one row from the source filter at a time, and then it combines color channels for the destination pixels. Then optionally other rows are also read: eventually the sums are averaged into the filtered (scaled) row. So it may read several rows from the source image and collapse them into one row, and it collapses multiple x-values (columns) into a single x-value.

This doesn't strictly follow any particular scaling algorithm, but it gets the job done quickly. (And although the original implementation of this class only supported scaling down, I've since revised it to scale up, too.)

The Scaling class offers a few convenient static methods for scaling that use the ScalingIterator.

Before and After

Visually the results (when using the Scaling class) are great:

Here's a closer look (the Graphics2D-based version is on the left, the Scaling version is on the right):



The grass, the clouds, and the border are a lot less jagged when the Scaling class is used.

Performance Comparison

How does this class perform? I needed to compare my new Scaling methods against other antialiased approaches. Here are the three possible scaling models I came up with:

Scaling: using the static methods in the Scaling class.

GraphicsUtilities: using Romain Guy's GraphicsUtilities class.

Image.getScaledInstance: calling Image.getScaledInstance() on a BufferedImage.

The ScalingDemo app compares these three methods by scaling an image of increasing size to 25%. Here are the results on my Mac 10.5 machine running Java 1.6:

The getScaledInstance() method is clearly the loser in this race. This is unfortunately because it's the only method that's built-in, but developers have been warning against using this method for years: it's practically deprecated.

Of the other two methods: they're practically the same regarding speed. More importantly: I'm confident that the Scaling approach is more efficient when it comes to memory allocation than the GraphicsUtilities approach: so these facts combined validate this experiment for me.

The results here may not dazzle you at first, but this undertaking is a stepping stone for a couple of other scaling projects: see this article about JPEGs and PNGs and this article about BMPs for details.

All the classes mentioned here are available in this jar (source included).