Hough transform algorithm - Idiomatic c++

Question

I've got some working code to compute the Hough transform for circles:

#include <stdio.h>
#include <opencv/cv.hpp>
#include <math.h>
#include <string>
#include <iostream>

int *** allocate3DArray(int y, int x, int r)  {
    int ***array = (int***)malloc(sizeof(int**)*y);
    for (int i = 0; i < y; i++)  {
        array[i] = (int**)malloc(sizeof(int*)*x);
        for (int j = 0; j < x; j++)  {
            array[i][j] = (int*)malloc(sizeof(int)*r);
            for(int k = 0; k < r; k++) {
                array[i][j][k] = 0;
            }
        }
    }
    return array;

}

void free3d(int ***arr, int y, int x, int r)  {
    for (int i = 0; i < y; i++)  {
        for (int j = 0; j < x; j++)  {
            free(arr[i][j]);
        }
        free(arr[i]);

    }
    free(arr);

}

vector<Circle> HoughTransformCircles(Mat image, Mat &gradient_mag, Mat &gradient_dir)  {
    //Maximum circle radius is rLen = image.width / 2
    int rLen = image.rows/2;
    int ***houghSpace = allocate3DArray(image.rows, image.cols, rLen);
    for (int y = 0; y < image.rows; y++) {
        for (int x = 0; x < image.cols; x++) {
            for (int r = 0; r < rLen; r++)     {
                int x0 = x - (int)(r*cos(gradient_dir.at<double>(y, x)));
                int y0 = y - (int)(r*sin(gradient_dir.at<double>(y, x)));
                if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                    houghSpace[y0][x0][r]++;
                }
                x0 = x + (int)(r*cos(gradient_dir.at<double>(y, x)));
                y0 = y + (int)(r*sin(gradient_dir.at<double>(y, x)));
                if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                    houghSpace[y0][x0][r]++;
                }

            }
        }
    }
    vector<Circle> circles;
    for (int y = 0; y < image.rows; y++)    {
        for (int x = 0; x < image.cols; x++)  {
            for (int r = 0; r < rLen; r++)  {
                if (houghSpace[y][x][r] > 30)  {
                    Circle temp  = Circle(x, y, r);
                    circles.push_back(temp);
                }
            }
        }
    }

    free3d(houghSpace, image.rows, image.cols, rLen);

   return circles;
}

How do I make this as idiomatic as possible? I am not allowed to use C++ 11 unfortunately.

Answer 1

Here are some suggestions for improving the code.

Use all required #includes

The code uses vector but doesn't include the corresponding header. The code should have

#include <vector>

Use <cmath> instead of <math.h>

The difference between the two forms is that the former defines things within the std:: namespace versus into the global namespace. Language lawyers have lots of fun with this, but for daily use I'd recommend using <cmath> (and also <cstdio>). See this SO question for details.

Avoid malloc and free

The old C-style calls still work, of course, but are not recommended. They are error prone and tend to require more code to do correctly (i.e. checking the return value of malloc for NULL). Instead, the modern C++ idiom is to use RAII which stand for "Resource Acquisition Is Initialization). See R.10 and R.1 for details.

Use objects

The 3D array would be much better implemented as an object. While you could, of course, write one (and I'd encourage you to try that as a learning exercise), there's an even smarter way to do that in the next suggestion.

Know your libraries

The code is already using the OpenCV Mat class, so what would make sense would be to also use that for the Hough space as well. So this line:

int ***houghSpace = allocate3DArray(image.rows, image.cols, rLen);

would be written instead like this:

int dims[] = { image.rows, image.cols, rLen };
Mat houghSpace(3, dims, CV_8UC(1), Scalar::all(0));

Since that's a properly designed C++ class, it will automatically allocate memory as needed and also de-allocate it when the houghSpace object's destructor is called. Using it is almost a simple:

houghSpace.at<cv::Vec3i>(y0,x0)[r]++;

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, gradient_mag in HoughTransformCircles and r in free3d are unused. Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. It also appears you've got using namespace cv; somewhere as well and it's also not a good idea for similar reasons.

Use variables to clarify your code

The code currently has this nested set of loops:

for (int y = 0; y < image.rows; y++) {
    for (int x = 0; x < image.cols; x++) {
        for (int r = 0; r < rLen; r++)     {
            int x0 = x - (int)(r*cos(gradient_dir.at<double>(y, x)));
            int y0 = y - (int)(r*sin(gradient_dir.at<double>(y, x)));
            if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                houghSpace[y0][x0][r]++;
            }
            x0 = x + (int)(r*cos(gradient_dir.at<double>(y, x)));
            y0 = y + (int)(r*sin(gradient_dir.at<double>(y, x)));
            if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                houghSpace[y0][x0][r]++;
            }
        }
    }
}

Instead, I'd write it like this:

for (int y = 0; y < image.rows; y++) {
    for (int x = 0; x < image.cols; x++) {
        for (int r = 0; r < rLen; r++)     {
            int a = r * std::cos(gradient_dir.at<double>(y, x));
            int b = r * std::sin(gradient_dir.at<double>(y, x));
            int x0 = x - a;
            int y0 = y - b;
            if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                houghSpace.at<cv::Vec3i>(y0,x0)[r]++;
            }
            x0 = x + a;
            y0 = y + b;
            if(x0 >= 0 && x0 < image.cols && y0 >= 0 && y0 < image.rows )  {
                houghSpace.at<cv::Vec3i>(y0,x0)[r]++;
            }
        }
    }
}

In C++11, I'd use a range-for.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used.

Use const where possible

The HoughTransformCircles routine does not alter the image passed to it, and so it should be declared as taking const Mat& image as an argument.

Answer 2

In addition to what was mentioned in the review by @nivag.

With the exception of the use of std::vector the code looks a lot more like C than any version of C++.

Proper Include Headers

The code under review does not require stdio.h.

Please note that in C++ C programming include files can be included by inserting 'c' before the header name and removing the dot h.

#include <cstdio>
#include <cmath>

Lack Of Error Checking

In C++ the new operator has replaced the call to malloc(size_t size), and the delete operator has replaced the call to free(void *object). One of the benefits of the new operator is that it throws an exception when the memory allocation fails, the call to malloc(size_t size) only returns NULL (in C) or nullptr (in C++). Accessing memory through a null pointer causes unknown behavior, the return value of malloc(size_t size) should always be checked before usage.

int *** allocate3DArray(int y, int x, int r)  {
    int ***array = (int***)malloc(sizeof(int**)*y);
    if (array == nullptr)
    {
        std::cerr << "In allocate3DArray allocation of array failed\n";
        return array;
    }
    for (int i = 0; i < y; i++)  {
        array[i] = (int**)malloc(sizeof(int*)*x);
        if (array[i] == nullptr)
        {
            std::cerr << "In allocate3DArray allocation of array[" << i << "] failed\n";
            return nullptr;
        }
        for (int j = 0; j < x; j++)  {
            array[i][j] = (int*)malloc(sizeof(int)*r);
            if (array[i][j] == nullptr)
            {
                std::cerr << "In allocate3DArray allocation of array[" << i << "][" << j <<  "] failed\n";
                return nullptr;
            }
            for(int k = 0; k < r; k++) {
                array[i][j][k] = 0;
            }
        }
    }
    return array;
}

For the reasons listed above, new should be preferred over malloc.

Use C++ Container Classes over C Style Arrays

As mentioned in another review there are clear benefits of using C++ Container Classes over C Style Arrays. In addition to the proper type of memory being allocated with less code, container classes provide iterators which provide safer ways to iterate through the objects in the container, it is much more difficult to iterate off the end of an array when the iterators and container.begin() and container.end() are used.

Answer 3

There are a number of things I would change here:

• gradient_mag is unused in HoughTransformCircles and should be removed.

• Mat will presumably normally be a relatively large array so relatively expensive to copy, additionally you don't modify image or gradient_dir in the code. These can both be passed in as const Mat &.

• You should make variables that shouldn't change e.g. rLen, const. This prevents you accidentally modifying them later.

• Similarly you should prefer size_t to int for variables that can't be <0. In your case all the counters in the loops and rLen.

• Avoid c style casts e.g. (int)(r*cos(gradient_dir.at<double>(y, x), prefer explicit static_cast<int>() instead. The c style cast will do a const cast or re-interpret cast if it thinks it needs to which can lead to unexpected results if you are not careful.

• I would avoid using c style arrays to store houghSpace. What you have done looks correct, but would be easy to break if you want to extend the code. In modern c++ the obvious replacement for this is std::array, but if you are not using c++11 that is not an option. Another option is to use std::vector. You can initialise the vector to zeros of the desired size. This option might have some memory overhead, but it should be small (would need testing). A third option as you are already using opencv would be to make houghSpace another Mat. I'm not sure what the memory/performance characteristics of Mat are, but this seems like the natural solution.