Filter <---- My Project!
What does it even mean to filter an image? You can think of filtering an image as taking the pixels of some original image, and modifying each pixel in such a way that a particular effect is apparent in the resulting image.
Grayscale
One common filter is the āgrayscaleā filter, where we take an image and want to convert it to black-and-white. How does that work?
Recall that if the red, green, and blue values are all set to 0x00 (hexadecimal for 0), then the pixel is black. And if all values are set to 0xff (hexadecimal for 255), then the pixel is white. So long as the red, green, and blue values are all equal, the result will be varying shades of gray along the black-white spectrum, with higher values meaning lighter shades (closer to white) and lower values meaning darker shades (closer to black).
So to convert a pixel to grayscale, we just need to make sure the red, green, and blue values are all the same value. But how do we know what value to make them? Well, itās probably reasonable to expect that if the original red, green, and blue values were all pretty high, then the new value should also be pretty high. And if the original values were all low, then the new value should also be low.
Reflection
Some filters might also move pixels around. Reflecting an image, for example, is a filter where the resulting image is what you would get by placing the original image in front of a mirror. So any pixels on the left side of the image should end up on the right, and vice versa.
Note that all of the original pixels of the original image will still be present in the reflected image, itās just that those pixels may have rearranged to be in a different place in the image.
Blur
There are a number of ways to create the effect of blurring or softening an image. For this problem, weāll use the ābox blur,ā which works by taking each pixel and, for each color value, giving it a new value by averaging the color values of neighboring pixels.
Edges
In artificial intelligence algorithms for image processing, it is often useful to detect edges in an image: lines in the image that create a boundary between one object and another. One way to achieve this effect is by applying the Sobel operator to the image.
Like image blurring, edge detection also works by taking each pixel, and modifying it based on the 3x3 grid of pixels that surrounds that pixel. But instead of just taking the average of the nine pixels, the Sobel operator computes the new value of each pixel by taking a weighted sum of the values for the surrounding pixels. And since edges between objects could take place in both a vertical and a horizontal direction, youāll actually compute two weighted sums: one for detecting edges in the x direction, and one for detecting edges in the y direction.
Implementation
Implement a program that applies the filters grayscale, reflection, blur, and edges to BMPs.
Recover <---- My Project!
In anticipation of this problem, we spent the past several days taking photos of people we know, all of which were saved on a digital camera as JPEGs on a memory card. (Okay, itās possible we actually spent the past several days on Facebook instead.) Unfortunately, we somehow deleted them all! Thankfully, in the computer world, ādeletedā tends not to mean ādeletedā so much as āforgotten.ā Even though the camera insists that the card is now blank, weāre pretty sure thatās not quite true. Indeed, weāre hoping (er, expecting!) you can write a program that recovers the photos for us!
Even though JPEGs are more complicated than BMPs, JPEGs have āsignatures,ā patterns of bytes that can distinguish them from other file formats. Specifically, the first three bytes of JPEGs are
0xff 0xd8 0xff
from first byte to third byte, left to right. The fourth byte, meanwhile, is either 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, or 0xef. Put another way, the fourth byteās first four bits are 1110.
Odds are, if you find this pattern of four bytes on media known to store photos (e.g., my memory card), they demarcate the start of a JPEG. To be fair, you might encounter these patterns on some disk purely by chance, so data recovery isnāt an exact science.
Fortunately, digital cameras tend to store photographs contiguously on memory cards, whereby each photo is stored immediately after the previously taken photo. Accordingly, the start of a JPEG usually demarks the end of another. However, digital cameras often initialize cards with a FAT file system whose āblock sizeā is 512 bytes (B). The implication is that these cameras only write to those cards in units of 512 B. A photo thatās 1 MB (i.e., 1,048,576 B) thus takes up 1048576 Ć· 512 = 2048 āblocksā on a memory card. But so does a photo thatās, say, one byte smaller (i.e., 1,048,575 B)! The wasted space on disk is called āslack space.ā Forensic investigators often look at slack space for remnants of suspicious data.
The implication of all these details is that you, the investigator, can probably write a program that iterates over a copy of my memory card, looking for JPEGsā signatures. Each time you find a signature, you can open a new file for writing and start filling that file with bytes from my memory card, closing that file only once you encounter another signature. Moreover, rather than read my memory cardās bytes one at a time, you can read 512 of them at a time into a buffer for efficiencyās sake. Thanks to FAT, you can trust that JPEGsā signatures will be āblock-aligned.ā That is, you need only look for those signatures in a blockās first four bytes.
Realize, of course, that JPEGs can span contiguous blocks. Otherwise, no JPEG could be larger than 512 B. But the last byte of a JPEG might not fall at the very end of a block. Recall the possibility of slack space. But not to worry. Because this memory card was brand-new when I started snapping photos, odds are itād been āzeroedā (i.e., filled with 0s) by the manufacturer, in which case any slack space will be filled with 0s. Itās okay if those trailing 0s end up in the JPEGs you recover; they should still be viewable.
Now, I only have one memory card, but there are a lot of you! And so Iāve gone ahead and created a āforensic imageā of the card, storing its contents, byte after byte, in a file called card.raw. So that you donāt waste time iterating over millions of 0s unnecessarily, Iāve only imaged the first few megabytes of the memory card. But you should ultimately find that the image contains 50 JPEGs.