CS 143 / Project 1 / Image Filtering and Hybrid Images

Compositive image of a cat (high) and a dog (low)

Human observers have different sensitivities for different spatial frequencies. In particular, the frequency band of an image that we perceive the most, depends on the viewing distance. This effect is exploited by composite images: By moving further away from the image (or equivalently making the image smaller) we become more sensitive to the lower spatial frequencies (which are increased in the process of rescaling) By moving further away from the image we become more sensitive to the higher frequencies (which are lowered in the process of rescaling)

Composite images are generated by filtering and composition: Applying a low pass filter to the image we would like to place at the low frequencies removes the high frequencies. To generate the component of the image corresponding to the high frequencies we first apply a low pass filter and then subtract the resulting image from the original image, leaving us with the high frequencies. Subsequently, we simply superimpose the images by element-wise adding the matrices representing the images. We do not need to normalize, as in the process of filtering already some of the brightness of the images is lost.

Implementation in Octave/Matlab

To filter an image with a kernel, we need to iterate over all pixels in the image and for each pixel element-wise multiply its neighborhood with the kernel and assign the sum to the current pixel. The number of computations is on the order of complexity of the product of the size of the image and the size of the Kernel. As Octave/Matlab is designed for matrix multiplication, we can easily perform element-wise multiplication, using the '.*' operator. The main loop of the filtering algorithm is designed as follows: 


% filtering algorithm in Octave/Matlab
	for ii = 1:height_of_image
		for jj = 1:width_of_image
			for kk = 1:depth_of_image % i.e. number of color channels
				conv = kernel .* padded_image(ii:ii+hf-1, jj:jj+wf-1, kk);
				result(ii,jj,kk) = sum(conv(:));	
		end
	end

Results in a table

The following table shows the generated composite images: (The respective cutoff frequencies have been determined by manual tuning)

The upper row shows the images provided for the project. Starting from the left, the are composed of:

  1. Marilyn Monroe (high) and Albert Einstein (low)
  2. A fish (high) and a submarine (low)
  3. An airplane (high) and a bird (low)
  4. A bicycle (high) and a motorbike (low)

Additionally, the lower row shows composite images from material found on the web:

  1. An average human face (high) a human skull (low)
  2. A dolphin (high) and a cow (low)
  3. An sea urchin (high) and a sea mine (low)
  4. A lightning (high) and a neuron (low)

Computational optimizations

Due to the fact that filtering operations are inherently computationally expensive, I have implemented the algorithm in the C programming language, using a MEX file, which allows Matlab to dyn amically link object files. As the C programming language does not provide matrix operations, we need to implement the filtering operation from first principles using a 5-fold nested for-loop: 


/* C-implementation of filtering algorithm */
int idx = 0;
for(k=0; k < ds; k++){
	for(j=0; j < aws; j++){
		for(i=0; i < ahs; i++){
			// reset the accumulator
			acc = 0.0;
			for(x=0; x < wf; x++){
				for(y=0; y < hf; y++){
					acc += signal[k*ws*hs+(j+x)*hs+(i+y)] * filter[x*hf+y];
				}
			}
		 result[idx] = acc; 
		 idx++; 
		}
	}
}

To exploit the memory architecture's caches, we need to be mindful of Matlab's column-major order: In order to maximize efficiency, we need to work with adjacent elements of an array. When writing the results back to another array, we simply use a globally incremented index to facilitate the localization of the appropriate memory location.

Benchmarking

In order to evaluate the efficiency of the C implementation (which very intuitively speaking performs very fast) we perform the filtering operation on all images used with Matlab's build-in 'imfilter', the initial Octave/Matlab implementation 'my_imfilter', as well as the improved C implementation 'my_imfilter_c'. We see that the C-implementation of our filtering algorithm is about 10 times fast than the Octave/Matlab implementation, which is an entire order of magnitude! The build-in 'imfilter' function of Matlab, however, is yet faster, by a factor of about 3.