Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DefaultConvergenceCriteria::setFailureAfterMaximumIterations() appears broken #1598

Closed
Chungzuwalla opened this issue Apr 26, 2016 · 11 comments

Comments

@Chungzuwalla
Copy link

Code to reproduce:

pcl::IterativeClosestPoint<PCLCloud::PointType, PCLCloud::PointType> icp;
icp.setInputSource(...);
icp.setInputTarget(...);
icp.setMaximumIterations(1);
icp.getConvergeCriteria()->setFailureAfterMaximumIterations(true);
icp.align(...);

Expected result: after 1 iteration, alignment should be abandoned and icp.align() should return, and icp.hasConverged() should be false.

Actual result: icp.align() enters an endless loop and will never return.

The enclosing loop in icp.hpp is:

// Repeat until convergence
do
{
 ...
 converged_ = static_cast<bool> ((*convergence_criteria_));
}
while (! converged_);

which loops until pcl::registration::DefaultConvergenceCriteria::hasConverged() returns true. However, pcl::registration::DefaultConvergenceCriteria::hasConverged() starts with:

pcl::registration::DefaultConvergenceCriteria<Scalar>::hasConverged ()
{
  // 1. Number of iterations has reached the maximum user imposed number of iterations
  if (iterations_ >= max_iterations_)
  {
    if (failure_after_max_iter_)
      return (false);
  ...

Once iterations_ >= max_iterations_, hasConverged () immediately returns false, without testing other convergence criteria, causing an endless loop.

@SergioRAgostinho
Copy link
Member

Thanks for looking into it. Given the in-depth analysis you already did, it would be great if you could submit a pull request addressing the issue. For additional info on how to contribute, please check this.

@WraithKim
Copy link
Contributor

WraithKim commented Feb 11, 2019

I had a problem with this issue too.

And I think the major problem is hasConverged() looks like "Getter" of convergence state, but it implements like "Setter" of convergence state.

It returns a boolean state of convergence, but also asign the detail reason to convergence_state_.

Therefore, this issue becomes "will be hasConverged() as Getter or Setter?"
And then, there are following considerations.

First, getConvergenceState() is also public.
PCL User now can check the convergence state from both getConvergenceState() and hasConverged(). Especially, getConvergenceState() returns more detail. Even if hasConverged() will be fixed to "Getter", it just needs for old compatibility. So it needs to be considered for further update.

Second, hasConverged() must handle the failure after maximum iterations. (cf. ConvergenceState::CONVERGENCE_CRITERIA_NO_CORRESPONDENCES)
NO_CORRESPONDENCES is treated differently from all other state, of course, cause the correspondence needs to be checked before ICP loop.
Like that, this failure may be treated to other function. But it can't. If handling this failure at the other function, all modules using DefaultConvergenceCriteria must use this function with hasConverged(). Because, both functions deal with the iteration check. It is not right in the view of software design.

Third, Why FAILURE_AFTER_MAX_ITER is not state?
Speak of NO_CORRESPONDENCES, the failure after maximum iterations an user-defined exception too. It deserve to be state, not just return (false). and PCL User can know why the registation has failed.

Finally, as issue author said, there is no further test when (iterations_ >= max_iterations_).
I just thought that move the iteration test to the last of code, but if more failure conditions has added, this design makes dirty. However, Considering a bug that not happen yet is far away question and I have no idea of this.

This is all of my analysis, and sorry for uncleaned. Anyway, I just share my answers.
The solution for current version is

if (failure_after_max_iter_)
    return (false);

to

return (true);

and add state CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_ITER

This is not work well, if user try to check the failure using hasConverged(). But it fix the bug, and getConvergenceState() can give correct state to user, and may not damage to all PCL-based working applications.

And the solution for next major version(if PCL API will have huge change.)
Make hasConverged() hidden and change name. And use getConvergenceState() instead. The reasons are come from my analysis. Change hasConverged() as "Setter" and leave "Getter" to getConvergenceState().

This is only my idea, so may be I am wrong. So please let me know if you have another idea or further discussion about this issue. Thanks.

@taketwo
Copy link
Member

taketwo commented Feb 18, 2019

I certainly agree with you about the misleading name of DefaultConvergenceCriteria::hasConverged() and the fact that it's not a getter. I think we can implement your solution, but we should also address your other (valid) concern:

This is not work well, if user try to check the failure using hasConverged().

Just to clarify, we are talking about different function here, Registration::hasConverged(), right? It returns the value of the converged_ member field, which is set inside loop to the output of DefaultConvergenceCriteria::hasConverged():

converged_ = static_cast<bool> ((*convergence_criteria_));
}
while (!converged_);

Now with your proposal we will get out of the loop by setting converged_ to true. But in fact, there is no convergence, so once we are out of the loop we need to check if the state is FAILURE_AFTER_MAX_ITER, and, if so, reset converged_ to false.

What do you think?

@WraithKim
Copy link
Contributor

You are right, user checks failure using Registration::hasConverged() not DefaultConvergenceCriteria. I misunderstood that.

Yes, you can check FAILURE_AFTER_MAX_ITER after out of the loop. It's like a CONVERGENCE_CRITERIA_NO_CORRESPONDENCES. This state also set converged_ to false manually.

So I agree with your solution but this upcomming problem should be concerned.
All classes which has DefaultConvergenceCriteria as a public attribute must implement testing FAILURE_AFTER_MAX_ITER in their code.

Because DefaultConvergenceCriteria::setFailureAfterMaximumIterations() is also public. If class has DefaultConvergenceCriteria, FAILURE_AFTER_MAX_ITER also can be set, and testing failure is also needed. But it looks like DefaultConvergenceCriteria leaves his test to his owner.

If they are an inheritance, this makes sense. But they are a component. That makes further expansion of code tricky, and software design will be bad.

Anyway, I agree with your idea and I would like you fix it as you said. but what do you think about the upcomming problem I explained above? I just ask to you because I have no idea of that problem. If you too, just leave it as remained problem. If you think it doesn't make concerns, just ignore it.


To solve that problem, I got a different idea: ICP has DefaultConvergenceCriteria but not his parent(Registration). So ICP override Registration::hasConverged() to like:

hasConverged() 
{
    switch(convergence_criteria_)
    {
        case FAILURE_AFTER_MAX_ITER:
            return false;
            ...
    }
}

But this idea maybe not compatible with original Registration::hasConverged() and converged_ . Also it can break up whole system and needs huge change, so it is not a good idea. I just add what I was thinking.

@taketwo
Copy link
Member

taketwo commented Feb 20, 2019

I think you are totally right with your concerns. The DefaultConvergenceCriteria class has serious issues with design and it would be nice if we could address at least some of them in backwards-compatible manner.

The problem with your idea is that Registration::hasConverged() is not virtual, so we will shadow it by defining another hasConverged inside ICP, which is not nice.

I have some half-baked ideas how to improve the situation. I haven't thought them through yet, but I'll share them already so we can start a discussion.

First, we add an explicit state for the failure after max iterations (as you already proposed):

enum ConvergenceState
{
  CONVERGENCE_CRITERIA_NOT_CONVERGED,                // group 1: no convergence, no failure
  CONVERGENCE_CRITERIA_ITERATIONS,                   // group 2: convergence
  CONVERGENCE_CRITERIA_TRANSFORM,                    // group 2: convergence
  CONVERGENCE_CRITERIA_ABS_MSE,                      // group 2: convergence
  CONVERGENCE_CRITERIA_REL_MSE,                      // group 2: convergence
  CONVERGENCE_CRITERIA_NO_CORRESPONDENCES,           // group 3: failure
  CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_ITERATIONS  // group 3: failure
};

Then in DefaultConvergenceCritera::hasConverged() we set this state, but still return false as before (because we haven't converged indeed):

if (failure_after_max_iter_)
{
  convergence_state_ = CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_ITERATIONS;
  return (false);
}

Note the comments in the first snippet. The enum values can be semantically divided into three groups. With this in mind, the condition for while loop in registration classes can be changed to:

  ...
}
while (convergence_criteria_->getConvergenceState() == CONVERGENCE_CRITERIA_NOT_CONVERGED)

So for the purposes of controlling the loop we will ignore what hasConverged() returned. But the value will still be recorded in the converged_ field and can be checked by the user.

What do you think?

@WraithKim
Copy link
Contributor

That's brilliant! I agree with your idea. Also thank you for your kind explanations. I think there is no more consideration about infinite ICP loop.

But I missed one thing that Chungzuwalla(the issue opener) said.
Even if other criteria is met, if (iterations_ >= max_iterations_) makes convergence failure. Because testing maximum iterations is in front of other criteria test.(Check out what he/she said at the end)

At the beginning, I thought just move failure test after all pass tests. But this is not a good idea. Because, after that, other contributers consider about this order every times they append new failure state and its test.

Instead, I found another idea that remove all return false except the one at the end of the function. This makes test all criteria until find any convergence, then return false.

To implement this idea, there is one more thing to do. Even though DefaultConvergenceCriteria::hasConverged() found two or more criteria has met, iterations_similar_transforms_ should be counted up only 1.
Please check out this code and see what iterations_similar_transforms_ is. You can understand what I said.

if (iterations_similar_transforms_ < max_iterations_similar_transforms_)
{
// Increment the number of transforms that the thresholds are allowed to be similar
++iterations_similar_transforms_;
return (false);
}

Therefore, there needs a boolean variable which stores whether iterations_similar_transforms_ needs to count up or not. Because if not converged, it can be just 'not converged yet' or 'failed'.

The code below is what I said. I omitted detail code.

pcl::registration::DefaultConvergenceCriteria<Scalar>::hasConverged ()
{
    bool is_similar = false;

    // maximum iterations check
    if (failure_after_max_iter_)
    {
        convergence_state_ = CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_ITERATIONS;
    }
    else
    {
        convergence_state_ = CONVERGENCE_CRITERIA_ITERATIONS;
        return (true);
    }

    // transformation difference check
    if (iterations_similar_transforms_ < max_iterations_similar_transforms_)
    {
        is_similar = true;
        // remove return (false);
    }
    else
    {
        // if converged, just return (true) now.
        iterations_similar_transforms_ = 0;
        convergence_state_ = CONVERGENCE_CRITERIA_TRANSFORM;
        return (true);
    }

    // relative sum of error check
    if (iterations_similar_transforms_ < max_iterations_similar_transforms_)
    {
        // It just works, when it is duplicated.
        is_similar = true;
        // remove return (false);
    }
    else
    ...
    
    if (is_similar)
    {
        ++iterations_similar_transforms_;
    }
    // leave last return (false);
    return (false);
}

Is there anything wrong? Feel free to tell me.

Additionally, I thought about showing multiple convergence state using std::bitset. But it needs many changes. And test every criteria is slower than just return at any convergence met. So I didn't think about it further.

@taketwo
Copy link
Member

taketwo commented Feb 21, 2019

Good points, agree with your proposal. There are a few things that I suspect are currently wrong with iterations_similar_transforms_ though:

  1. In case of a failure it is not reset to zero. So if our ICP alignment fails and then we run another alignment with the same ICP object, iterations_similar_transform_ will continue from the same state it was in the end of last run.
  2. What if there are a few iterations when transform is similar, but then it becomes large? The counter should be reset I think.

Regarding std::bitset it's interesting idea, however I'm not sure for the effort it needs to be implemented how much value it brings to the user. Somehow I feel it's only of academical interest if only a single or multiple convergence criteria were satisfied. For practical uses it does not usually matter as long as alignment converged.

@WraithKim
Copy link
Contributor

WraithKim commented Feb 24, 2019

Yes, std::bitset is too much. I agree that it has no meaning with pratical use. Thanks you for your advice.

About iterations_similar_transforms_, Yes, in case of a failure, we need to reset to zero. But there is a problem that the failure state can be set in DefaultConvergenceCriteria or out of this instance.
(ex. CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_ITERATIONS and CONVERGENCE_CRITERIA_NO_CORRESPONDENCES)
DefaultConvergenceCriteria can reset when maximum iterations, but it can't reset when no correspondences.

I don't understand well your second consideration. But I think you talk about CONVERGENCE_CRITERIA_ITERATIONS. It doesn't reset to zero even though there were a few similar transforms(less than threshold). This can be handle by just adding reset when 'maximum iterations' too. But this is not the only case, so we need to go broad.

I have two options to solve it. Manual reset or automatic reset, but both are not quite good ideas. Manual reset means doing reset by ICP, and automatic reset means doing reset by DefaultConvergenceCriteria so ICP don't care about it. I don't like manual reset because, as I said before, it ruins a software design. But my automatic reset also has a side effect. So I think there is a controversy.

Manual reset is just make a public reset method, so let ICP deal with it. When ICP starts new alignment, ICP call DefaultConvergenceCriteria::reset() to reset the counter. Or, just reinitialize its convergence_criteria_ at the beginning of new alignment. But these are not a good ideas...

My automatic reset is doing in DefaultConvergenceCriteria::hasConverged(). You said that CONVERGENCE_CRITERIA_NOT_CONVERGED is neither the failure nor the convergence.
So we can't reset when NOT_CONVERGED, because it doesn't finish. When it finished, whatever it is, the state isn't NOT_CONVERGED. So the code can be like this.

pcl::registration::DefaultConvergenceCriteria<Scalar>::hasConverged ()
{
    // the start of this function.
    if (convergence_state_ != CONVERGENCE_CRITERIA_NOT_CONVERGED)
    {
        iterations_similar_transforms_ = 0;
        convergence_state_ = CONVERGENCE_CRITERIA_NOT_CONVERGED;
    }
    ...

So, ICP doesn't care about iterations_similar_transforms_ and it works when new alignment with same object.

But this has a flaw. We start this discussion with that DefaultConvergenceCriteria::hasConverged() has too many roles than its original intent. In my suggestion, now it has reset, set, get. This is why I feel there are side effects. For example, if someone call this function to cast convergence_criteria_ type as boolean, this will reset the previous state. This can be wrong. Furthermore, we need to divide this function, but dividing DefaultConvergenceCriteria::hasConverged() is really hard work. I won't ask you to solve this.

Anyway, I recommend the latter than the former. But if you have better idea, let me know please.

@taketwo
Copy link
Member

taketwo commented Feb 28, 2019

For the "automatic reset" approach we may use the fact that iterations_ == 1 when a new alignment is started. Using ICP as an example, in the beginning of computeTransform() the counter is set to zero:

Then in the loop it is first incremented and then hasConverged() is called:

++nr_iterations_;
// Update the vizualization of icp convergence
//if (update_visualizer_ != 0)
// update_visualizer_(output, source_indices_good, *target_, target_indices_good );
converged_ = static_cast<bool> ((*convergence_criteria_));
}
while (!converged_);

So in the very beginning of hasConverged() we can check if it is the first iteration and reset counters as needed.

As for my second point, I meant the following hypothetical situation:

  • iteration 1, large transform, iterations_similar_transform_ == 0
  • iteration 2, small transform, iterations_similar_transform_ == 1
  • iteration 3, small transform, iterations_similar_transform_ == 2
  • iteration 4, large transform, iterations_similar_transform_ == ?

@WraithKim
Copy link
Contributor

Yes, you right. Only consecutive similar transforms is allowed. There needs a reset when the transform becomes large.
So, when you add a reset, would you mind adding a little explanation about your second point at docs DefaultConvergenceCriteria::setMaximumIterationsSimilarTransforms()? Maybe old description confuses beginners.
And thank you for fixing this bug.

@taketwo
Copy link
Member

taketwo commented Mar 5, 2019

Unfortunately I'm quite busy with other things and don't have an estimate on when I would have time (if ever) to implement the discussed fixes myself. So if you want this to be fixed, prepare a pull request!

WraithKim added a commit to WraithKim/pcl that referenced this issue Mar 6, 2019
- Exit loop with convergence state instead of `converged_` in icp
- Add new convergence state `CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_
ITERATIONS`
- When `failure_after_max_iter_` is set true, `hasConverged()` checks
all similarity before returning a failure.
- Even though one iteration has several similar conditions, counts
`iterations_similar_transforms_` up only 1.
- If transform becomes large, `iterations_similar_transforms_` reset
to 0. Only consecutive similar iterations are allowed to converge.
- Edit a description about the change above in API docs.
- When new alignment restarts after a convergence or a failure,
`iterations_similar_transforms_` also reset to 0.
taketwo pushed a commit that referenced this issue Apr 9, 2019
Fix misbehavior in the "failure after maximum iterations" mode

This updates `ICP` and `DefaultConvergenceCriteria` classes to fix misbehavior in the "failure after maximum iterations" mode. (Prior to this change the registration loop would hang in an infinite loop #1598). It also refines "maximum iterations similar transforms" option to mean **consequtive** transforms.

A new convergence state `CONVERGENCE_CRITERIA_FAILURE_AFTER_MAX_
ITERATIONS` is added.
@taketwo taketwo closed this as completed Apr 9, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants