3
\$\begingroup\$

I have an implementation of the flood fill algorithm. Assume that an image is provided as a vector of vectors. It takes in parameters of a square to segment the image into two regions. It also takes in a point where mouse click is detected. Based on the point, a particular segment in the image will be filled by a custom fill_value. In order to perform this operation a queue is used to keep track of all the points in the image that are to be filled. The visited points are noted down by an unordered_map which uses a user-defined class Point as key and a bool as value. Here is the complete code:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstddef>
#include <stdexcept>

// Class representing a point(x, y)
class Point
{
    int x_cord = {0};
    int y_cord = {0};
public:
    Point()
    {

    }
    Point(int x, int y):x_cord{x}, y_cord{y}
    {

    }
    int x() const
    {
        return x_cord;
    }
    int y() const
    {
        return y_cord;
    }
    // Comparison function for collision resolution in unordered_map
    bool operator==(const Point& pt) const
    {
        return (x_cord == pt.x() && y_cord == pt.y());
    }
};

// Template specialization of std::hash for using Point as Key
namespace std
{
    template<>
    class hash<Point>
    {
    public:
        size_t operator()(const Point& pt) const
        {
            return (std::hash<int>{}(pt.x()) ^ std::hash<int>{}(pt.y()));
        }
    };
}

// Check if a particular point is within given dimensions of the image
bool check_point(Point pt, int x_dim, int y_dim)
{
    if(pt.x() >= 0 && pt.x() < x_dim && pt.y() >= 0 && pt.y() < y_dim)
    {
        return true;
    }
    return false;
}

// Collect all the valid neighbors of a point and push it to the queue for fill candidates
void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val, std::unordered_map<Point, bool>& visited)
{
    std::vector<Point> neighbors;
    int x_dim = image.size();
    int y_dim = 0;
    if(x_dim > 0)
    {
        y_dim = image[0].size();
    }
    Point pt_n{curr_point.x(), curr_point.y() - 1};
    Point pt_s{curr_point.x(), curr_point.y() + 1};
    Point pt_e{curr_point.x() + 1, curr_point.y()};
    Point pt_w{curr_point.x() - 1, curr_point.y()};
    if(check_point(pt_n, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val && visited[pt_n] == false)
    {
        q.push(pt_n);
        visited[pt_n] = true;
    }
    if(check_point(pt_s, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val && visited[pt_s] == false)
    {
        q.push(pt_s);
        visited[pt_s] = true;
    }
    if(check_point(pt_e, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val  && visited[pt_e] == false)
    {
        q.push(pt_e);
        visited[pt_e] = true;
    }
    if(check_point(pt_w, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val && visited[pt_w] == false)
    {
        q.push(pt_w);
        visited[pt_w] = true;
    }
}

// Visit elements in the queue and perform fill (change pixel value) on them
void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val, int x_dim, int y_dim)
{
    int old_val = image[clicked.x()][clicked.y()];
    std::unordered_map<Point, bool> visited;
    std::queue<Point> q;
    q.push(clicked);
    visited[clicked] = true;
    while(!q.empty())
    {
        Point curr_point = q.front();
        get_neighbors(curr_point, q, image, old_val, visited);
        image[curr_point.x()][curr_point.y()] = new_val;
        q.pop();
    }
}

// Draw a square to segment image to two regions
void draw_square(std::vector<std::vector<int>>& image, Point top_left_corner, int length)
{
    int x_0 = top_left_corner.x();
    int y_0 = top_left_corner.y();
    int x;
    int y;
    for(x = x_0; x < x_0 + length; x++)
    {
        image[x][y_0] = 1;
        image[x][y_0 + length - 1] = 1;
    }
    for(y = y_0; y < y_0 + length; y++)
    {
        image[x_0][y] = 1;
        image[x_0 + length - 1][y] = 1;
    }
}

void print_image(std::vector<std::vector<int>>& image, int x_dim, int y_dim)
{
    for(int i = 0; i < x_dim; i++)
    {
        for(int j = 0; j < y_dim; j++)
        {
            std::cout << image[i][j] << "\t";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

int main()
{
    try
    {
        int x_dim = 0;
        int y_dim = 0;
        int x = 0;
        int y = 0;
        int c_x = 0;
        int c_y = 0;
        int length;
        int fill_value = 0;
        // Obtain image dimensions
        std::cout << "Enter the dimensions of the image: \n";
        std::cin >> x_dim >> y_dim;
        std::vector<std::vector<int>> image(x_dim, std::vector<int>(y_dim, 0));
        // Obtain parameters to draw the square
        std::cout << "Enter the top left point coordinates and length for the square: \n";
        std::cin >> x >> y >> length;
        Point top_left_corner{x, y};
        // Check if parameters are valid
        if(!check_point(top_left_corner, x_dim, y_dim) || !check_point(Point{top_left_corner.x() + length - 1, top_left_corner.y() + length - 1}, x_dim, y_dim))
        {
            throw std::out_of_range{"Invalid Access"};
        }
        draw_square(image, top_left_corner, length);
        // Print the image before Flood Fill
        std::cout << "Before Flood Fill: \n";
        print_image(image, x_dim, y_dim);
        // Obtain the clicked point
        std::cout << "Enter point to be clicked: \n";
        std::cin >> c_x >> c_y;
        Point clicked{c_x, c_y};
        // Check if the clicked point is valid
        if(!check_point(clicked, x_dim, y_dim))
        {
            throw std::out_of_range{"Invalid Access"};
        }
        // Obtain fill_value
        std::cout << "Enter value to be filled: \n";
        std::cin >> fill_value;
        // Flood Fill
        flood_fill(image, clicked, fill_value, x_dim, y_dim);
        // Print image after Flood Fill
        std::cout << "After Flood Fill: \n";
        print_image(image, x_dim, y_dim);
    }
    catch(std::out_of_range& e)
    {
        std::cerr << e.what() << "\n";
    }
    return 0;
}
  1. I have used a template specialization of std::hash and an operator== function inside Point to enable the use of Point as a key in unordered_map. Is this enough to resolve collision? Please see this link for the detailed question.

  2. How can I improve the efficiency?

  3. Have I picked optimal data structures, except for image?

\$\endgroup\$
4
\$\begingroup\$

I'll ignore questions 1 and 5 regarding hashing, because you don't need a hash function at all.

Storing image data

A std::vector<std::vector<int>> is, in general, not a good way to store an image. For every pixel lookup this requires finding the column in one array, then following a pointer to another part of the memory where the pixel data for the column is stored, and finding the indexed value there. That is, there are two memory lookups involved. Furthermore, pixels are potentially stored non-consecutively, which is harder on the cache. Note also that allocating a small image of 1k x 1k pixels requires 1k + 1 allocations.

It is always best to keep things together in memory. Use a single memory block for your image: std::vector<int>. Here, allocating a small image of 1k x 1k pixels requires 1 allocation.

Instead of indexing image[x][y], you now need to do image[x+y*width]. This simple computation seems expensive, but it is not at all expensive compared to the additional memory fetch that you do in a vector of vectors. Since you have a nice Point class, you can make a method Point::index(step) that performs this computation. Now indexing is image[pt.index(width)], which is quite nice for code like the following:

Point pt_n{curr_point.x(), curr_point.y() - 1};
if(check_point(pt_n, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val && visited[pt_n] == false)
   // ...

where you write the neighbor's location (x,y-1) twice. This is error-prone. With the new method you can write:

Point pt_n{curr_point.x(), curr_point.y() - 1};
if(check_point(pt_n, x_dim, y_dim) && image[pt_n.index(witdh)] == old_val && visited[pt_n] == false)
   // ...

Another advantage is that we can now use pointer arithmetic to access neighbors. Given a pixel at p = image.data() + pt.index(width), the neighbor to the left is *(p-1), the neighbor to the top is *(p-width), etc. This can significantly simplify the logic for flood filling and many other algorithms that depend on neighborhood relations between pixels (see below).

Pixel type

Consider if int is the pixel type you really want. int has a fixed meaning in all modern 32-bit and 64-bit computers that I know of, but the standard only says it should have at least 16 bits. I would suggest being more specific, and using e.g. std::uint8_t or std::uint32_t depending on what you want your pixels to look like.

Recording visited pixels

Instead of a hash function, you can very simply use a second image to record this information. When you access a pixel in the image you know its index. Looking up a value at the same index in a second array is trivial compared to computing a hash function and doing the hash lookup. Basically, an image is the ideal data structure to map an integer coordinate to a value. There will never be any hash collision here, each point has a unique location. Yes, this takes up more space, but an array of a few million bytes is trivial. Plus, you can use the same array for another speedup. Read on.

Testing for neighbors

The check_point function is called 4 times for every pixel being processed, but it returns false for neighbors of only a very small subset of them (the pixels at the edge of the image). Most pixels have 4 neighbors. However, this test is a significant part of the execution time.

If you could test a pixel not being on the image edge, you could skip testing if its 4 neighbors exist for most pixels in the image. In my experience, the best way to do so, rather than testing for coordinates, is to use another boolean image where the edge pixels are set, and the rest are not.

Since you already use a visited image, you could add this neighborhood information to it. For example,

visited[i] & 1     // true if visited
visited[i] & 2     // true if pixel on left edge of image (doesn't have a neighbor to the left)
visited[i] & 4     // true if pixel on right edge of image
visited[i] & 8     // true if pixel on top edge of image
visited[i] & 16    // true if pixel on bottom edge of image

Now the logic in get_neighbors becomes:

if(!(visited[i] & 2) && image[i-1] == old_val && !(visited[i-1] & 1)) {
   q.push(i);
   visited[i] |= 1;
}
if(!(visited[i] & 4) && image[i+1] == old_val && !(visited[i+1] & 1))
   // ...
if(!(visited[i] & 8) && image[i-width] == old_val && !(visited[i-width] & 1))
   // ...
if(!(visited[i] & 16) && image[i+width] == old_val && !(visited[i+width] & 1))
   // ...

It would be nice to encapsulate some of that into helper functions for readability:

inline bool has_left_neighbor(ImgUInt8 const& visited, int i) {
   return !(visited[i] & 2);
}
inline int left_neighbor(int i) {
   return i-1;
}
// etc.

inline bool is_visited(ImgUInt8 const& visited, int i) {
   return visited[i] & 1;
}

Now it's more difficult to make mistakes:

if(has_left_neighbor(visited, i) && image[left_neighbor(i)] == old_val
                                 && !is_visited(visited, left_neighbor(i))) {
   //...
}

Note that in the code above we don't use coordinates at all any more. The whole flood fill operation can be written using only 1D indices to pixels.

Code smells

  1. Your function check_point does:

    if(condition) {
       return true;
    }
    return false;
    

    This can be better written as:

    return condition;
    
  2. You default constructor for Point has an empty body. Prefer to write:

    Point() = default;
    
  3. The function get_neighbors declares a std::vector<Point> neighbors that you don't use. The compiler should have given you a warning for this. Make sure that you always compile with all possible warnings turned on, and that you fix all warnings reported.

  4. Your main function catches exceptions, writes out what(), then returns 0. On POSIX systems, it is customary for a program to return with a different exit value if there was an error. Furthermore, an uncaught exception will cause the what() message to be written and a non-zero exit value to be used. So it is better in general to not catch exceptions at all. return 0; is also superfluous, as the compiler will generate that one for you. main is the only function that returns a value but needs no return statement.

\$\endgroup\$
  • \$\begingroup\$ The reason why I picked hash map is due to this (around 11:30). I assumed that the reason could be use of extra space. \$\endgroup\$ – skr_robo Sep 4 '18 at 9:05
  • \$\begingroup\$ @skr_robo: He’s wrong, sorry. The easiest way to prove so is to write this algorithm and replace the hash with an image (which is a small change in the code because the lookup and assignment are written the same way for both data structures), and compare timings. This is the nice thing about programming: you don’t have to take anyone’s word for what is best, you can test! \$\endgroup\$ – Cris Luengo Sep 4 '18 at 13:55
  • 1
    \$\begingroup\$ If the region to fill is small w.r.t. the image, you’ll save space, but the hash table is a lot more expensive in time. There are always trade-offs. \$\endgroup\$ – Cris Luengo Sep 4 '18 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.