ELEC4622 Project 2 Solved

This is the second of three mini-projects to be demonstrated and assessed within the regular scheduled laboratory sessions. This project is due in Week 11. The project is worth a nominal 10 marks, out of the 30 marks available for the laboratory component of the course. However, there are two optional taskss which attract a lot of potential bonus marks.

In this project, you will implement and understand the Laplacian of Gaussian (LOG) filter. LOG filtering plays an important role in edge detection for image analysis. From an educational point of view, LOG filters also provide an excellent demonstration of the important connection between discrete and continuous LSI operators — derivative operators in particular. Further, the project will help to familiarize you with scale-space concepts. In the remainder of this introduction, we provide a brief overview of the theory behind LOG filtering.

1.1              The Laplacian Operator in Continuous Space

Let f (s) denote a spatially continuous signal. Throughout this treatment s≡ (s1,s2) is a two-dimensional spatial location, although everything works for any number of spatial dimensions. In continuous space, the gradient operator is well-defined. Specifically, f is the vector field

 

which measures the rate of change of intensity in each of the vertical and horizontal directions. In the Fourier domain, we know that

 

where Dˆ1 (ω) = jω1 and Dˆ2 (ω) = jω2 are the transfer functions of the horizontal and vertical derivative operators, respectively. Of course, differentiation is an LSI operator (i.e., a filter), so that differentiation is nothing other than convolution in the continuous space domain, using PSF’s D1 (s) = F−1 (jω1) and D2 (s) = F−1 (jω2), respectively.

          The Laplacian operator         2produces the scalar field

 

1

 

Figure 1: Horizontal profile of a vertical edge.

In vector calculus, the Laplacian operator is sometimes written as · . In fact, in the Fourier domain, the Laplacian operator behaves exactly like a dot product. Specifically, we have

 

Of course, the Laplacian operator is also LSI, so that the operation can also be viewed as a convolution in the space domain.

One important property of the laplacian operator is that it is isotropic. That is, the operation is invariant to rotation. This is easy to see, since

is circularly symmetric in the Fourier domain, meaning that the operator’s PSF must also be circularly  symmetric.

Together, the second derivative and isotropic properties of the Laplacian operator have useful implications for its behaviour in the presence of edges. Suppose the spatially continuous image f (s) contains a vertical edge, so that f (s1,s2) = fedge (x)|x=s2 ,

where fedge is the edge profile illustrated Figure 1. A reasonable definition for the location of the edge is the point s2 = x0 at which  edge equals 0. Now

 ,

since all vertical derivatives of a vertical edge are zero. It follows that the edge location coincides with the zero crossing of the Laplacian 2f (s). Although we have considered only horizontal edges, the rotational invariance of the Laplacian operator ensures that the same property should hold for edges of all orientations. That is, the location of an edge in any orientation is well described by the zero crossings of 2f (s).

2

1.2              The LOG Operator in Continuous Space

 One major problem with the Laplacian operator, as it stands, is that derivatives are very sensitive to noise. One way to see this is that the Laplacian operator amplifies high frequency components by. This amplification process strongly affects white noise which has constant power at all frequencies. The noise-free signal itself usually has most of its energy at lower frequencies. Even “high frequency” features such as sharp edges produce power spectra which are located at DC in the parallel direction and decay as   in the transverse direction.

To reduce the sensitivity to noise, we can think of first applying a low-pass filter to the image f (s). Gaussian filters are a natural candidate since they do not impact the circular symmetry of the Laplacian operator. The LOG operation may then be expressed in the Fourier domain as

 

Here, σ2 is the variance of the Gaussian PSF

 .

Notice that instead of low-pass filtering f and then taking the second derivatives of the result, we can just filter f directly with , where

(1)

 In fact ∇2σ is the just              2Gσ, having PSF

                                                                                                                                                       (2)

It follows that the zero crossings of the LOG filtered image, gσ (s), identify the locations of edges in the (Gaussian) low-pass filtered original image. The single parameter σ2, determines the scale of the edge detection process: large values of σ2 eliminate all but the lowest frequency components so that the edges of larger image features are detected; small values of σ2 allow more rapid changes in the filtered image, so that the smaller image features can be detected.

1.3          Discrete LOG Filters

As discussed in Chapter 2 of your lecture notes, and also in lectures, Gaussian filtering can be implemented directly by discrete convolution with PSF

Gσ [n] = Gσ (s)|s=n ,

 so long as the variance is sufficiently large to ensure that Gσ is effectively Nyquist bandlimited — i.e., Gσ (ω) ≈ 0 for ω∈/ [−π,π]2. According to equation (1), ∇f2σ (ω) also decays exponentially, but grows only quadratically, so the same argument shows that the LOG operator can be implemented with high accuracy,f by discrete convolution with

,

so long as σ2 is sufficiently large.

You should expand equation (2), both for your practical implementation in this project and also to convince yourself that  can be well approximated by an FIR filter. You need to make your own

(sensible) judgements concerning the region of support for this FIR filter.

1           Tasks
The tasks presented below build progressively on one another. For demonstration purposes, you may like to create a separate project for each task, within a single workspace. You can do this by using the “File → New → Project” option in Visual C++, replacing the “Create new solution” option with “Add to solution”.

Task 1: (3 marks) Write a C/C++ program which can perform LOG filtering on a monochrome or colour BMP image, writing the result to a new BMP image.

•    Your program should accept the value of σ as one of its command-line arguments, for testing purposes. This means that the program should dynamically adjust its filter coefficients (and filter region of support) according to the value of σ.

•    For this task, you should implement the FIR filter directly, using floating point arithmetic.

•    Your program should accept a real-valued scaling factor α as another of its command-line arguments, that allows the LOG filtered values to be scaled prior to writing them to the output image file, so as to facilitate visual inspection.

•    Noting that the sample values output by your LOG filter are naturally centred about 0, you should add 128 to all values prior to writing the output file.

•    Be prepared to comment on the images you recover using the algorithm.

Task 2: (2 marks) The LOG filter itself is not separable; however, it is a sum of two separable filters. In this task, you modify the program created in Task 1 to exploit this separability for a more efficient implementation.

•    Processing should still be performed in floating point arithmetic, for simplicity.

•    Use release builds to compare the speed of your two implementations (Task 1 and Task 2). Make an electronic record of your results, but also be prepared to demonstrate the timing during the laboratory demonstration in Week 10.

Task 3: (2 marks) Modify your program to write a sequence of output images, corresponding to progressively larger values of σ, so that you can put this image sequence into a single (MFLEX) video file with the Media Interface tools and play it back. The resulting sequence of images is a type of scale space. Your modified program should accept arguments that identify minimum and maximum values for σ, i.e., σmin and σmax, along with the total number of scales Nσ, producing Nσ images whose scales σ are spaced logarithmically between σmin and σmax.

Task 4: (3 marks) Modify your program from Task 2 or Task 3 (your choice) to produce a candidate edge map for each scale σ — only one scale if you modify Task 2.

4

•    The output from your program should be an image with only two values: 0 or 255, where 255 corresponds to a potential edge location.

•    Notionally, the value 255 should be written to locations that correspond to zero crossing in the underlying spatially continuous LOG-filtered image. However, since you only have a discrete LOG-filtered image you will have to come up with (or research) an appropriate heuristic based on the immediate neighbours of each pixel, to determine whether a zero-crossing is likely to occur nearby.

•    It is acceptable for your program to work only with monochrome input images, but to support colour images in this task it is sufficient to perform the same operation on each colour plane, producing a colour edge map where a non-zero value (255) in any colour plane corresponds to a potential zero-crossing in the plane’s LOG-filtered sample values.

Task 5: (optional, up to 2 bonus marks) Modify your program from Task 2 to work with integer sample values and all integer arithmetic — additions, multiplications and shifts.

Task 6: (optional, up to 2 bonus marks) Modify your program from Task 4 to add a simple morphological dilation stage, in which the potential zero-crossings are considered to be the foreground pixels, and the structuring set for the dilation operation is the 3 × 3 cross

 

It is important that you be able to quickly show the edge maps you obtain both before and after dilation, so both images should be output by your program.