by Jon Byous
August 1, 2001-- Looking for a way to zoom across hundreds of digital images quickly? Digital image library zooming is here in a new downloadable application.
Back in 1999 we interviewed Dr. Ben Bederson, assistant professor of computer science, and director of the Human-Computer Interaction Lab at the University of Maryland, in a Face to Face Java Technology Hero story. At that time, Bederson was introducing two downloadable Java technology-based platforms -- one for zoomable user interfaces, and the other for simultaneous multiuser, single-machine interfaces.
But recently, stuck at home with an illness, Bederson leveraged this earlier work to build a powerful and exciting replacement for the traditional digital image photo browser: PhotoMesa. The application, and its open source algorithms, are now available to you for download.
If Necessity Is the Mother of Invention, Frustration Is Its Father
Bederson was dismayed by the disarray of dozens of folders containing almost a thousand photos taken with his digital camera. He decided there must be a better way of sorting and viewing images without having to recategorize, rename, or annotate the image files.
Further, as a developer of child-computer interfaces, he was interested in devising a simple way to view images on-screen while being directed by his two-year-old daughter, sitting at his side.
Building on his original Jazz framework for Zoomable User Interfaces, and his work devising computer interfaces for children, Bederson developed PhotoMesa: a downloadable pure Java 2 application for Java technology developers that functions as a zoomable digital image browser.
What Would a Dream Photo Viewer Look Like?
Bederson describes four things he feels are wrong with traditional photo viewing systems, which he wanted to correct with PhotoMesa:
First: Even though the commercial image browsers are relatively easy to use, they are based on standard, "windows-y" interfaces, which means you spend a good deal of time dealing with scroll bars, resizing windows, closing pop-up windows, and stair-stepping through pull-down menus. "These are all operations that get in the way of the primary task: looking at images," says Bederson. A zoomable interface lets you fly over a two-dimensional "topology" of your file contents very quickly without having to manage small interface elements.
Second: Bederson wanted an image browser that would encourage his two-year-old daughter to collaborate with him in navigating through hundreds of images in dozens of files. "I wanted her to be able to point at the screen and say, `That one,' and see me move the mouse to zoom in and expand the thumbnail to a full-size image. I wanted her to understand what was happening, which would help keep her involved."
Third: Traditional image browsers don't support what Bederson calls "serendipitous photo finding" -- discovering other interesting or related photos while zooming in on a chosen image. For example, as you zoom in on a selected thumbnail image, you also see other images in the periphery that may be of interest.
Fourth: Bederson felt the application had to support the images and metadata people already had on their hard drives. "Most people wouldn't spend time annotating their thousands of stored images simply to import them into a new image browser," says Bederson. "So a fundamental goal was that the user wouldn't have to spend any time organizing or preparing their image library for PhotoMesa. You just run PhotoMesa, open up a directory of images, and that's it."
A View From the Top of the Hierarchy
The PhotoMesa web page explains: "The name PhotoMesa derives from the Spanish word `mesa,' which means table, but is commonly used in the U.S. southwestern states to describe the natural volcanic plateaus which are high and have flat tops. Standing atop a mesa, you can see the entire valley below, much as you can see an overview of many photos in PhotoMesa."
To accomplish this view, there are two technically novel components in PhotoMesa: Quantum Strip Treemaps for layout and a new kind of interaction for Bederson's already novel zoomable user interfaces. The treemaps are used to group photos by whatever metadata is available (directory, creation date, file name, etc.), and the zoomable user interface allows many images to be shown simultaneously with the mesa-like view.
Treemaps are a family of algorithms that are space-filling partitions of a two-dimensional area. They take as input, a list of n numbers and a rectangle. They then partition the rectangle into n subrectangles, one per input number. The subrectangles are guaranteed to fill the input rectangle, and the rectangles are proportional in area to the list of input numbers. Treemaps are designed to be applied hierarchically, so any given resulting rectangle can itself contain a treemap, and so on, recursively.
While a number of treemap algorithms have been around for a while, they have gained popularity recently with applications such as SmartMoney's Map of the Market. However, the existing treemap algorithms have two problems: 1) They are unordered, making it difficult to quickly find a specific item; and 2) they are designed for representing a number, not for holding images.
To address the ordering problem, Bederson created "Strip Treemaps." He says, "Strips are a natural way to break up space while maintaining order. Your eye naturally follows them left-to-right, top-to-bottom, and with some careful calculation and the use of variable-height strips, each strip holds just the right sized rectangles."
The harder problem, though, was to use the treemaps to store images. Normal treemap-generated rectangles can have any aspect ratio, which often isn't well-suited to contain images. To solve this, Bederson says, "You basically have two choices -- shrink the images to fit whatever rectangles you have, or resize the rectangles to match image aspect ratios nicely." With Quantum Treemaps, Bederson chose the latter. He stretched the generated rectangles just enough so that each dimension is always an integral multiple of the dimensions of each image thumbnail. This way, the PhotoMesa rectangles can dynamically accommodate any number of groups of any number of thumbnails while keeping all the thumbnails the same size, laid out on a single grid.
However, Bederson didn't stop there. "Once I developed the Treemap scheme," he says, "I realized that the layout was not aesthetically pleasing to me -- they're just rectangles. And it didn't optimize the space within the browser. There was some wasted space between the rectangles."
The Bubblemap Solution
Bederson realized that with a different algorithm, he could fill the space more efficiently and make the overall layout more visually pleasing (although perhaps harder to use). So he came up with a very simple algorithm he calls "Bubblemaps."
"While Quantum Treemaps work well, they have the disadvantage of wasting some space," says Bederson. "It's impossible to lay out images in a rectangle without leaving some unused space (in general) if the images are all the same size. An alternative approach is to give up on the idea that the space must be divided into rectangles, and instead allow more complex shapes."
Bubblemaps lay out groups of quantum-sized objects in an ordered position with no wasted space per group, although there is a small amount of wasted space for the entire area.
In general, a Bubble partitions space into arbitrary regions that are each just big enough to enclose the images you have selected to display as a group. "I used a recursive paint algorithm, similar to that used in the earliest paint programs, to fill out the image space," says Bederson.
PhotoMesa's bubble layout isn't a perfect grid because of the space needed to separate each folder of displayed photos, highlight a selected group, and enlarge a selected photo, each with a surrounding texture or color.
Zoom Straight to Your Image
Bederson has been exploring Zoomable User Interfaces (ZUIs) for a number of years. Basically, a ZUI is an interface where all of the data are presented on a single, huge two-dimensional surface. The surface can contain graphical objects of different sizes such, as images, documents, or interactive interface elements. Over the years, Bederson has developed a number of ZUI-based applications, including a web-browser history tool and CounterPoint, a presentation tool that works as a Microsoft PowerPoint plug-in.
PhotoMesa's zoomable interface was built using Bederson's Jazz technology. The downloadable Java 2 platform-based Jazz platform is a technology developed by Bederson and his staff at the Human-Computer Interaction Lab. Jazz is a toolkit for supporting structured two-dimensional data, zooming, and event handling. Jazz supports structured two-dimensional graphics, and offers a canvas that can hold these graphics that can be used wherever a Java Foundation Classes/Swing widget can be used.
Jazz's zoom capabilities, applicable to a wide variety of applications, were ideal for PhotoMesa's layout of hundreds of small images in a two-dimensional graphical plane. But the real innovation for PhotoMesa was the simplified interaction. In the past, ZUIs were somewhat difficult to navigate. They used a kind of flying interface similar to what you might find in a three-dimensional game. To make PhotoMesa work well, Bederson says, "I realized if I wanted this to really work for home users, it had to be no harder than a single click to use. So I created an interaction where a red rectangle shows where you will zoom into when you click -- and the red rectangle is designed to always zoom in about a factor of two, and to never clip off images. If you want to zoom out, you just press the right button (or the Enter key for one-button mouse users)."
Designed for User Convenience and System Resources
"Another thing I wanted PhotoMesa to do was provide a transition or learning path for people who were only used to traditional photo viewer interfaces," explains Bederson.
"I started with the basic `file open' menu and then developed a file-viewer pane on the left which displays the user's hierarchy of photo folders and files," he says. "If you click on a folder, the interface loads all of the photos in the folder. Click on a superfolder and it loads all of the photos in it and its subfolders."
Soon, Bederson began seeing PhotoMesa as a way to browse multiple directories of images. "Another way to think about directories of images is that you're browsing a large set of images clustered or grouped by directory name -- which could be any metadata," he says. "Most people haven't added much metadata to their images -- just file name, file size, and last change date. So I designed PhotoMesa with the ability to open several directories and, from the View menu, to group them by month. That way, you can see images across directories, arranged by time."
To save on memory use, PhotoMesa automatically creates four sizes of thumbnail images and stores them on disk to use as you zoom in or out, giving you the right size image for your viewing perspective. As you zoom in, you see fewer images, but they're larger. Zoom out, and you see more images, which are smaller. By creating images ahead of time, it keeps the memory usage roughly constant.
File Name Grouping for Relevancy
In addition, PhotoMesa lets you group images by names using a capability Bederson calls "File Name Words."
"While many people don't rename their image files, some do and PhotoMesa gives an advantage to those people. When people name their photos, they often use multiple words, combining things such as content, context, and date in the file name," he says. "So PhotoMesa will parse the file names and group the photos by each word in the file name."
The File Name Words function might place a photo called "Dana Zoo," for instance, in two groups, one called "Dana" and another called "Zoo." The next image, named "Kangaroo Zoo," would appear in both a new "Kangaroo" group and the existing "Zoo" group.
This functionality paves the way for a new way to view image search results grouped by their metadata. It could allow large image databases, such as online stock photo houses and even Google.com, to produce search results clustered by whatever metadata is available, rather than producing a single grid of all the results.
Educational Tools for Kids
As a measure of the browser's success, Bederson's two-year-old daughter is now able to navigate the interface to select photos by pointing at them and saying, "elephant" or "cat."
It is easy to imagine that a zoomable image viewer such as this has many applications in word-image association for young kids. In fact, Bederson and his wife, Allison Druin, also a professor at the University of Maryland, have begun development on this interface as a visual digital library interface for children. The original "SearchKids" interface they developed in 1999 is now able to visually zoom across query results, allowing ever-younger kids to interact with computers.
Taking PhotoMesa to the Next Step
Bederson points to a limitation of PhotoMesa that he intends to change. "PhotoMesa is an image viewer, not a file management tool. At present, you can't delete images, change file names, or manipulate the image's content with it, but that is a limitation I want to address." To do so, he is currently looking for one or more partners to further develop and integrate these technologies.
"Even though I developed PhotoMesa to browse images in my own collection, I realized that it is potentially useful for browsing thumbnail search results from professional stock photo houses," says Bederson. He is hoping to convert PhotoMesa into a professional tool.
For downloadable code and further reading, visit the PhotoMesa web page. It offers a paper by Bederson that describes the two new algorithms for laying out groups of images or other fixed-size visual objects.
The algorithms are available for download as open source software. The PhotoMesa application itself is also available for download so you can begin zooming through your images immediately.
PhotoMesa Image Browser
Quantum Treemaps and Bubblemaps for a Zoomable Image Browser
SearchKids: Digital Libraries for Children
Face to Face With Dr. Ben Bederson