Photoshop Sleuths
An algorithm sniffs out digital alterations

Context: Photographs used to be a reliable source of evidence, but the advent of digital cameras and photo-editing software has made every picture a potential scam. The skillful user of Adobe Photoshop and other tools can produce realistic images of imaginary scenes. As Dartmouth University computer scientists Alin Popescu and Hany Farid note, the Los Angeles Times unwittingly ran an altered photograph from the war in Iraq on its front page. To help defend against these types of forgeries, Popescu and Farid have published a new image-processing algorithm that detects photographic fakery.

Methods and Results: When forgers modify an image, they often insert elements taken from other photographs or from other sections of the same photograph; these insertions need to be distorted, resized, or rotated to fit in with the rest of the image. Even when no new elements are added, digital manipulations may leave telltale signs of “re-sampling.” For example, to double an image’s size, software inserts a new pixel between every pair of neighboring pixels in the original image. The new pixels are a combination of the pixels surrounding them in the original image – the result of interpolation. Such regularity rarely occurs in natural images and often produces patterns that Popescu and Farid’s software can detect, even when they’re unapparent to the naked eye. In trials employing 50 images selected at random from a database of 200, Popescu and Farid’s method found nearly all cases of enlargement greater than 1 percent and most cases of rotation that required interpolation. Some cases of shrinking could also be detected.

Why it Matters: Current forgery detection techniques, which are vital for screening news items and intelligence, leave much to be desired. Digital watermarking works only when someone has had the foresight to insert hidden information into an image file to prevent tampering. In contrast, Popescu and Farid’s method can be applied automatically to any image file. However, the method is not foolproof: for example, it cannot detect cases of shrinking without interpolation. Also, data compression, used in JPEG files, and noise interfere with the algorithm. Nonetheless, the new software makes it harder for a digital photograph to lie.

Source: Popescu, A. C. and H. Farid. 2005. Exposing digital forgeries by detecting traces of re-sampling. IEEE Transactions on Signal Processing (in press).

Once More, with Volume
Hand gestures control computer graphics

Context: Video games, design software, and scientific visualization technologies routinely use 3-D graphics. Typically, users interact with 3-D graphics on flat computer screens and cannot grab, move, or rotate graphical representations as they can real physical objects. Even the most advanced stereoscopic displays, like those used in virtual-reality systems, require head-mounted displays, which restrict viewers’ range of motion, obstruct peripheral vision, and cause discomfort. Now, researchers at the University of Toronto have created a system that frees 3-D graphics from such constraints.

Methods and Results: Key to the system is a “volumetric” display, one that lets multiple users view graphics from any ­angle without wearing headgear. Tovi Grossman and his colleagues used a swept-volume display, which spins a series of 2-D images around an axis fast enough that humans perceive them as a 3-D image. The researchers created a way for users to manually interact with their display, which is housed in a clear plastic dome. Cameras track special rings worn by the users, who can select 3-D objects by pointing at them and drag them by moving their fingers across the display sphere. Using both hands, users can stretch or shrink objects, or specify the axis about which an object should rotate.

Why it Matters: While the new display does not provide sensory feedback, it permits the control of 3-D graphics through hand gestures similar to those whereby people manipulate real objects. The technology eliminates the need for joysticks or virtual representations of users and paves the way for 3-D graphics applications that anyone can use with minimal training. Volu­metric displays, once found only in expensive research prototypes, have become commercially available. The Toronto researchers’ interface could hasten the day that they are routinely used by scientists designing drug molecules, doctors planning surgeries, architects, engineers, and, of course, gamers.

Source: Grossman, T., D. Wigdor, and R. Balakrishnan. 2004. Multi-finger gestural interaction with 3D volumetric displays. Proceedings of the ACM Symposium on User Interface Software and Technology, pp. 61-70.

Model Sensors
Statistics yields better data with less battery power

Context: Sensor networks are collections of small devices that measure local conditions like temperature or light intensity. The devices, sometimes called sensor “motes,” transmit data wirelessly to moni­toring stations. Sensor networks could let soldiers track enemy tanks remotely, engineers gauge the structural integrity of buildings, or scientists monitor animals in their natural habitats. But one barrier to their widespread use is the difficulty of coaxing reliable information from motes whose batteries are low or whose connectivity is intermittent. Motes tend to be widely scattered and often malfunction; but a sensor network that represents the world inaccurately or incompletely is of limited use. Now researchers at Intel Research Berkeley and their collaborators have shown that new statistical techniques can compensate for some of these flaws.

Methods and Results: A statistical model based on previous data from a sensor network can correct for biases caused by malfunctioning or poorly placed sensors. It can also tailor the network’s performance to specific tasks: someone querying the network can specify the accuracy of the response, and the model will automatically determine which data are needed. Pulling in just the required data means that precious battery power is not wasted on extra measurements and transmissions. Amol Deshpande and his colleagues developed a query system enhanced with statistical techniques and tested it in sensor motes deployed over a redwood tree in Berkeley, CA. The system answered queries – such as what the temperature at a certain spot was – highly accurately (95 percent confidence), often performing only one-­fortieth the number of observations previously required.

Why it Matters: Sensor networks promise to transform environmental monitoring, military surveillance, and inventory management. Now, the data that a sensor network gathers can be interpreted and used with more confidence. When high accuracy is necessary, a network using a statistical model like Intel’s will collect more data. When rougher estimates are acceptable, using statistical models reduces the battery power consumed by sensor motes. A longer battery life for sensor motes is a great boon, especially for motes distributed in hostile or inaccessible terrains. Although Intel’s models and methods can still be improved, its technique greatly expands sensor networks’ utility in the real world.

Source: Deshpande, A. et al. 2004. Model-driven data acquisition in sensor networks. Proceedings of the 30th International Conference on Very Large Data Bases, pp. 588-599.