Carnegie Mellon University

Advanced Search   
  Look in
       Title    Full-text
  Date Range
VASC Seminar: Andrew Gallagher
Putting the Pieces Together: Assembling Puzzles and Shredded Documents

Andrew Gallagher
Cornell University

November 26, 2012, 3pm-4pm, NSH 1305

In this talk, we will explore how to construct images from pieces in two different domains. In the first domain, we look at jigsaw puzzles made from square pieces of an image, and we introduce new types of square-piece jigsaw puzzles: those for which the orientation of each jigsaw piece is unknown. In the second domain, we look at reconstructing actual shredded documents from a scanned collection of shreds with a collaborative human-computer algorithm.

With a tree-based reassembly algorithm, components are greedily merged while respecting the geometric constraints of the puzzle problem. The algorithm has state-of-the-art performance for puzzle assembly, whether or not the orientation of the pieces is known. The algorithm makes fewer assumptions than past work, and success is shown even when pieces from multiple puzzles are mixed together. For solving puzzles where jigsaw piece location is known but orientation is unknown, we propose a pairwise MRF where each node represents a jigsaw piece’s orientation. Other contributions of the paper include an improved measure (MGC) for quantifying the compatibility of potential jigsaw piece matches based on expecting smoothness in gradient distributions across boundaries

For reconstructed documents, we have a semi-automatic approach for crosscut shredded document reassembly. Automatic algorithms are proposed for segmenting and orienting individual shreds from a scanned shred image, as well as for computing features and ranking potential matches for each shred. Additionally, a human-computer interface is designed to allow semiautomatic assembly of the shreds using the computed feature and match information. Our document de-shredding system was tested on puzzles from the DARPA Shredder Challenge, allowing successful reconstruction of multiple shredded documents.

Additional Information

Host: Alexei Efros

Appointments: Bernardo Pires (

Speaker Biography

Andrew Gallagher is a Visiting Research Scientist at Cornell University's School of Electrical and Computer Engineering, beginning in June 2012. Andrew earned the Ph.D. degree in electrical and computer engineering from Carnegie Mellon University in 2009, advised by Prof. Tsuhan Chen. Before that, Andrew received an M.S. degree from Rochester Institute of Technology in electrical engineering. Andrew worked for the Eastman Kodak Company at the dawn of consumer digital photography, initially developing image enhancement algorithms for digital cameras and for post-processing scanned film images. These efforts resulted in more than 90 issued U.S. Patents and Kodak's prestigious Eastman Innovation Award in 2005. More recently, Andrew's interests are in the arena of improving computer vision by incorporating context, human interactions, and unique image cues. Further, Andrew enjoy working in the areas of graphical models and image forensics, and for fun Andrew enjoys board games, sports, and hiking around Ithaca's waterfalls.