Andrew Lewis

Andrew Lewis

I completed my PhD in multimedia security in the security group of the Computer Laboratory in 2011. My work was supervised by Dr Markus Kuhn.

My interests include forensic analysis and reconstruction of compressed image and video bit-streams, tampering detection and information hiding. My work so far has focussed on the JPEG and H.264/AVC standards.

I am a contributing lecturer for Topics in security – forensic signal analysis, part of the MPhil in Advanced Computer Science (slides on JPEG compression history).

I run a multimedia forensics bibliography which includes many papers in the field.

I ran the computer lab's security seminars from November 2007 to January 2009.

To contact me, please email first name.last name @ cl.cam.ac.uk. My personal home page contains up-to-date information.

Projects

September 2009

Exact JPEG recompression (paper | poster | download implementation)

Andrew B. Lewis and Markus G. Kuhn

We present a variant of the JPEG baseline image compression algorithm optimized for images that were generated by a JPEG decompressor. It inverts the computational steps of one particular JPEG decompressor implementation (Independent JPEG Group, IJG), and uses interval arithmetic and an iterative process to infer the possible values of intermediate results during the decompression, which are not directly evident from the decompressor output due to rounding. We applied our exact recompressor on a large database of images, each compressed at ten different quality factors. At the default IJG quality factor 75, our implementation reconstructed the exact quantized transform coefficients in 96% of the 64-pixel image blocks. For blocks where exact reconstruction is not possible, our implementation can output transform-coefficient intervals, each guaranteed to contain the respective original value. Where different JPEG images decompress to the same result, we can output all possible bit-streams. At quality factors 90 and above, exact recompression becomes infeasible due to combinatorial explosion; but 68% of blocks still recompressed exactly.

Presented at SPIE Electronic Imaging 2010, San Jose CA, US: Visual Information Processing and Communication

July 2009

Towards copy-evident JPEG images (paper | slides | demonstration)

Andrew B. Lewis and Markus G. Kuhn

We present a technique for adding a high-frequency pattern to JPEG images that is imperceptible to the unaided eye, but turns into a clearly readable large-letter warning if the image is recompressed with some different quality factor. Our technique aims to achieve a goal similar to copy-evident security-printing techniques for paper documents, namely to have an easily recognizable text message appear in lower-quality copies, while leaving the visual appearance of the original unharmed. We exploit non-linearities in the JPEG process, in particular the clipping of the result of the inverse discrete cosine transform.

Presented at Informatik 2009, Lübeck, DE: Workshop Digitale Multimedia-Forensik

August 2008

Multimedia forensics bibliography (link)

My multimedia forensics bibliography contains many papers in the field categorised, with abstracts and BibTeX data.

July 2008

Exact JPEG recompression and forensics using interval arithmetic (slides | poster)

Andrew B. Lewis and Markus G. Kuhn

The standard JPEG compression algorithm was only designed to process images as they were acquired by camera sensors. In practice, however, photographic images are often compressed and decompressed multiple times. Here, image quality can be preserved better with special recompression algorithms designed for input that has been compressed and decompressed before. Our new JPEG recompressor represents the exact arithmetic operations of the preceding decompression as an overdetermined system of equations. It then uses interval arithmetic and iterative refinement to invert decompression steps in a way that takes into consideration all possible rounding effects. This results in a set of possible compression results, which will include the actual result of the last compression. We have also extended our recompression algorithm into a forensic tool that identifies those regions of a raw image that cannot possibly have been the result of a previous JPEG decompression step.

Presented at ACM MM&Sec08, Oxford, UK (rump session) and Microsoft Research Summer School 2008, Cambridge, UK

Supervisions

I supervised some courses in the undergraduate computer science tripos.

Here are some Part II project ideas.