- After practicing my JPEG reading kung fu,
I worked on the actual problem
of finding one image within another.
An image is a grid of pixels, rows and columns.
A subimage is a smaller portion of that same image.
To begin the search,
I needed to plot out every potential location
for that subimage.
Specifically, I would match the upper left corner
of the subimage to every potential starting location
in the primary image.
So the code had to calculate the difference in size
between the two images.
The result was to obtain a grid
in which to perform the search.
The subimage could start at any pixel in that grid.
To expedite searching,
the images are converted to gray scale.
For each location within the grid,
a row of pixels from the subimage
is compared with the same row of pixels
in the primary image.
Because JPEG is a lossy compression,
the comparison doesn't need to have to match exactly.
It can be fuzzy or within a given range
and within a given number of mismatches.
So with all that, if the rows of the subimage
match the rows of a patch in the primary image,
the subimage is deemed found.
In my code I create an image structure
which is used to hold data from a JPEG file.
The image structure is defined here
in the subimage.h header file.
It stores the images width, height, bytes per pixel value
and it has a pointer to storage for the images raw data.
In the subimage source code file,
the read_jpeg function uses an image structure
as an argument.
It attempts to read the file referenced in that structure.
The external, or global variable reduction factor,
determines how much to scale the image.
The variable is set to five earlier in the code,
so I reduce my image by 4/5
or down to 20% of its original size.
I made this value as a variable
so that the code could more easily be modified in the future
perhaps to accept a scaling factor
as a command-line argument.
I also set a local air handler
for the JPEG reading function.
The handler is called my_error_exit.
This function is initialized by using a set jump statement
back in the read_jpeg function.
That way my code handles any problems, not libjpeg.
If libjpeg handled the problems,
it would exit in a very messy fashion
before the program was finished.
The rest of the read_jpeg function stores information
about the file read,
specifically the raw data.
Space for the image is allocated
and assigned to the raw member of the image structure.
Libjpeg reads image data row by row
using the jpeg_read_scanline function.
I prefer that that information were saved as a single buffer
which I call raw.
To make that work,
I created an array of row pointers,
each of which references a memory location
inside the raw buffer.
So the jpeg_read_scanlines function
then reads in successive rows of uncompressed image data
saving them sequentially in the buffer.
The rest of the information is then stored in the structure
as shown in these lines.
Once data for the two images is in memory,
then the comparison begins.
The compare function chomps through
each potential starting location
in the main image for the subimage.
Variables line and offset
control the grid searching nested loop.
At each pixel position, the check_row function is called.
It returns 1 or 0 depending on how well the two rows match.
If they match, the while loop keeps spinning
until all the rows have been read.
Otherwise the code keeps searching through the grid.
The routine that compares the two rows of pixels
is relatively short.
Check_row compares data from pointers *a and *b.
The difference between the variables is calculated
and then compared to see how close the difference is
plus or minus.
Because of the lossy nature of JPEG,
I use a fuzz factor in the variable variation.
It's set to 24 which I believe is pretty high,
but I achieve that value through experimentation.
Being outside the range doesn't terminate the comparison,
instead, mismatches are tracked and then compared
with a threshold value.
These variables are external or global
and I chose to keep them that way
so that their values could be set
by using command-line arguments
if I wanted to make that change.
In the next movie, I'll describe the round robin process
by which each file in a directory is tested
against every other file.