Sobel Operator by Yasser Naji

Instructions

• Open a terminal and navigate to the root directory of this repository

• Compile the project: cargo build

• Run the executables with two arguments.

  • The first is the path to the input image.
  • The second is the desired output path.

  Note: The compiled executable will be located in the target/debug directory.

  Execution examples:

  • Unix:

    ./target/debug/sobel path/to/input/file path/to/output/file

  • Windows:

    target\debug\sobel.exe path\to\input\file path\to\output\file

• Alternatively, you can build and run the program in a single step

  cargo run path/to/image/file path/for/output/file

Example

The following example uses a test image, kodim08.png, which can be downloaded from https://r0k.us/graphics/kodak/.

It is currently saved in the root of this repository as input.png.

While in the repository directory, you can run the following commands in your terminal:

cargo build
./target/debug/sobel input.png results/edge_map.png

This will generate an image in results/edge_map.png, shown below:

results/edge_map.png is also included in this repository.

Unit tests

You can run the unit tests from the root of the repository with the following command:

cargo test

Machine Specifications

The code has been compiled and run with the following specifications:

Rust version: 1.88.0
Machine: Macbook Air 2019 Dual-Core Intel Core i5
Architecture: x86_64
OS: MacOS Sonoma v14.7.3

Approach

• The codebase is organised into two files:

  • utils.rs - contains all the functions necessary to perform the Sobel operation
  • main.rs - serves as the entry point and handles program execution

• The input image is converted to grayscale to simplify processing, as the Sobel operator is more straightforward to apply on a 1-dimensional tensor. This conversion preserves edge information.

• The convolution step has been parallelised to improve performance. Each pixel’s gradient magnitude is computed in parallel, and the results are then inserted into the image buffer sequentially.

• I avoided parallelising the data input into the grayscale vector and image buffer to prevent potential data races. While this could be handled using Mutex, incorporating it would complicate the code. Additionally, using a Mutex may not lead to performance improvements and could even have an adverse impact.

• Instead of extending the image with a border of zeros, I designed the convolution calculation to detect when it is processing border pixels and apply the appropriate weights accordingly. This approach simplifies the arrangement of the grayscale array and avoids adding a potentially large number of extra pixels, which could negatively impact performance.

• A threshold value of 200 has been chosen: if a pixel’s magnitude exceeds this value, it is set to white; otherwise, it is set to black. This value can be modified by the user in main.rs.

• The unit tests are included as a separate module within utils.rs, alongside the functions they test. This organisation keeps the repository structure simple.

• The pixel data undergoes the following type casts during processing:

  • u8 -> f32 - during grayscale conversion
  • f32 -> i32 - for convolution calculations
  • i32 -> f32- when computing the gradient magnitude

• Arguably, the second and third casts can be omitted, allowing the convolution to be performed directly with f32 values. However, the Sobel operator is traditionally applied to integer pixel data, and relying on floating-point arithmetic throughout may introduce unnecessary rounding errors.

Potential Improvements

• When calculating the magnitude, applying the square root can be computationally expensive. To improve performance, several approximation methods may be considered, including:

  • Using the Taylor series expansion of $\sqrt{x+1}$
  • Applying the Newton-Raphson method to solve $x^2 - n = 0$ to find $\sqrt{n}$
  • Employing the Brent-Dekker root-finding algorithm, known for its fast convergence, to solve the previous equation
  • Adapting the famous Quake III fast inverse square root technique

• A faster alternative to calculating the square root is to use the sum of the absolute values of the kernel calculations, as described in this OpenCV tutorial expressed as $\lvert G\lvert = \lvert G_x \lvert + \lvert G_y\lvert$.

• When converting the image to grayscale, each RGB intensity is first cast to f32 and then again to i32. Since this conversion happens for every pixel, reducing the number of type casts could lead to performance improvements.