replaced http://stackoverflow.com/ with https://stackoverflow.com/

edited May 23, 2017 at 12:40

Community Bot

• 1

Inline Side-by-side Side-by-side Markdown

answered Aug 7, 2015 at 15:01

Emily L.

• 16.7k
• 1
• 39
• 89

Style

Using using namespace std is bad. Same goes for using namespace cv obviously.

Your indentation is off, but I'm guessing that this is a copy paste error.

Comments

I find your comments to not be helpful. They should explain why something is done, not what is done. If you need comments to explain what you're doing, then you need to write clearer code with better variable and function names. Possibly breaking out more functions.

Combine definition and initialization

Code like this:

double upperLimit;
upperLimit = columnwiseSum.at<float>(min_loc); // this is the first upper bound

has poor readability. You should structure it like this (again better name on variables):

double upperBound = columnwiseSum.at<float>(min_loc);

See how I combined the definition and initialization of upperBound? This makes your code easier to follow, easier to verify that the variable is always initialized and also shorter to write.

There are multiple occasions of this.

Node class

The name index is wildly misleading, rather it's the position in the image. I would suggest renaming it to position. If you need to comment a member variable, its name is not good enough. Consider renaming distance to distanceFromSource.

Instead of providing the explicit comparator CompareDist you could simply provide an overload for operator > and use std::greater<Node> in your priority queue.

In summary:

struct Node
{
 Point position;
 double distanceFromSource;
 bool operator > (const Node& n) const{
 return distance > n.distance;
 }
};
...
std::priority_queue< Node, std::vector< Node >, std::greater<Node>>

But that's not infinite...

This really isn't infinity...

const int inf = 0x7F800000;

you are also assigning this to double when you want infinity:

double dist = inf; //global shortest path distance
double distTemp = inf; //shortest path distance for each dikstra run

you should just use: std::numeric_limits<double>::infinity() and while you're at it, if you need to comment what a variable is, the name is bad. How about this:

double shortestPathDist = std::numeric_limits<double>::infinity();
double shortestPathDistCurrent = std::numeric_limits<double>::infinity();

Numerical inaccuracy

You are using float to accumulate the distances, after each floating point operation you introduce a truncation error on the order of x*E-6 where x is the stored value. If you'd simply use CV_32SC1 and image.at<int32_t>() you wouldn't have to worry about truncation errors affecting your graph search. You would probably also notice a speed up.

At any rate you're comparing floats to doubles and doing a lot of type-casting which is unnecessary and can take some time if done in a hot loop.

Mat initialisation

This:

// initialize the distance of each node to infinity
Mat distance = Mat::ones(image.size(),CV_32F);
multiply(distance,inf,distance);

going with the above advice to use numeric_limits should be:

Mat distance(image.size(), CV_32F);
distance = std::numeric_limits<float>::infinity();

Dijkstra implementation

Okay the name pQueue tells me something about the type but not what it is used for. A much better name would be unvisitedNodes.

The variable first is only used once to push it into the pQueue better to just do it like this:

unvisitedNodes.emplace(source, image.at<float>(source)); 

Always strive to reduce the number of variables, this makes it easier to reason about the state of the code (but not to absurdum ofcourse). Notice that this could be more readable if we renamed source to start which is more logical.

unvisitedNodes.emplace(start, image.at<float>(start));

Now this tells me that I construct a new unvisited node from the start point. Great! Do note that dijkstra's algorithm starts with a '0' distance. But what you're doing is equivalent to starting at a node with only one edge, to the source node. So this won't affect your results.

The name tempNode again is a terrible name. Better names are currentNode or shortestPathNode.

Please do fix up your indentation:

Point nodeIndex = tempNode.index; // get element index 
if (nodeIndex == goal){ // found the path to goal
 return tempNode.distance;
 }
int newX, newY; //indices for neighborhood node
for(int i = -1; i < 2; i++) //for every neighborhood element 
 {
 newY = nodeIndex.y+1; //new row
 newX = nodeIndex.x+i; //new col

This is a proper nightmare to read. Again if you need to comment the variables, choose better names. Trust me, you'll save more time when you debug the code that you spend writing slightly longer names.

Instead of int newY, newX you should just have Point newPosition. Would simplify lots when addressing the images.

This:

 // this constrains the expansion within a diamond shape, since only certain neighboring nodes are allowed 
 if (newY <= floor(image.rows/2) && (newX >= source.x-newY && newX <= source.x+newY) || //upper half 
 (newY > floor(image.rows/2) && (newX >=source.x-(goal.y-newY) && newX <=source.x+(goal.y-newY)))) // lower half 
 {

piece of readability massacre kept me from reviewing this code for a few days.

Lets, start with floor(image.rows/2). First of image.rows is an integer type so the division by 2 will always truncate towards zero, as the size is always positive this is exactly the same behavior as removing the call to floor.

What you are actually doing is:

1. dividing by two (automatic floor here)
2. convert to float
3. call floor
4. convert newY to float
5. compare newY to result of 3.

If you just remove the floor the result will be exactly the same but the steps will reduce to:

1. divide by two (automatic floor here)
2. compare newY to result of 1.

Now after much head scratching I have managed to decipher that you limit the search to a diamond (rhomb) shape with the apex and nadir at the start and end points. The rhomb has two lines making a hat shape at the top, which the point must be below to be inside and then two lines making v shape at the bottom which the point must be above to be inside.

The code can then be expressed in a much more readable form as:

const bool insideULEdge = (source.x - newX) >= -newY;
const bool insideUREdge = (source.x - newX) <= newY;
const bool insideLLEdge = (goal.x - newX) >= image.rows - newY - 1;
const bool insideLREdge = (goal.x - newX) <= image.rows - newY - 1;
const bool insideDiamond = insideULEdge && insideUREdge && insideLLEdge && insideLREdge;
if(insideDiamond && rect.contains(Point(newX, newY)){

(note that goal.x == source.x so the above would simplify further.)

This should be extracted into a function called bool isInsideSearchSpace(const Point& start, const Point& end, const Mat& image).

Performance

You have implemented the Dijkstra's method wrong. You are visiting nodes more frequently than you have to. Please read the algorithm here: Dijkstra's algorithm.

You need to keep track of visited nodes separately from the distance to each node.