the localmaximum filter bug

[xq198109]

the localmaxmum fliter has an error in flitered point indces, the Points in the neighborhood of a previously identified local max can not be added to indces. the code can be modified as follow:

if (point_is_visited[iii] && !point_is_max[iii])
    {
        if (negative_)
        {
            if (extract_removed_indices_)
            {
                (*removed_indices_)[rii++] = iii;
            }
            continue;
        }
      indices[oii++] = iii;
      continue;
}

the code which check to see if a neighbor is higher than the query point assume the radius_indices is sorted, the searcher_ should be set sorted, the code can be modified as follow:

  searcher_->setInputCloud (cloud_projected);
  searcher_->setSortedResults(true);

[tin1254]

I just take a look at the code and @xq198109 is right

This marks the point visited

pcl/filters/include/pcl/filters/impl/local_maximum.hpp

Lines 161 to 167 in cd99687

	if (point_is_max[iii])
	{
	for (std::size_t k = 1; k < radius_indices.size (); ++k) // k = 1 is the first neighbor
	{
	point_is_visited[radius_indices[k]] = true;
	}
	}

And this skips those points without adding them to the result

pcl/filters/include/pcl/filters/impl/local_maximum.hpp

Lines 122 to 125 in cd99687

	if (point_is_visited[iii] && !point_is_max[iii])
	{
	continue;
	}

But I think whether radius_indices is sorted or not won't affect the result though. As long as it finds any neighbor point is higher than the current point, and it doesn't matter which higher point is found first

pcl/filters/include/pcl/filters/impl/local_maximum.hpp

Lines 147 to 157 in cd99687

	// Check to see if a neighbor is higher than the query point
	float query_z = (*input_)[iii].z;
	for (std::size_t k = 1; k < radius_indices.size (); ++k) // k = 1 is the first neighbor
	{
	if ((*input_)[radius_indices[k]].z > query_z)
	{
	// Query point is not the local max, no need to check others
	point_is_max[iii] = false;
	break;
	}
	}

[xq198109]

the iteration skips the first point(k=0), which compare Z value. the indce of Query point is also in the radius_indices , if radius_indices is not sorted, the first point may be not the Query point, that could cause wrong judgment. At 2021-10-28 06:09:38, "tin1254" ***@***.***> wrote: I just take a look at the code and @xq198109 is right This marks the point visited https://github.com/PointCloudLibrary/pcl/blob/cd99687bd1f332d77aee06a8e9fbad4fb08c0a44/filters/include/pcl/filters/impl/local_maximum.hpp#L161-L167 And this skips those points without adding them to the result https://github.com/PointCloudLibrary/pcl/blob/cd99687bd1f332d77aee06a8e9fbad4fb08c0a44/filters/include/pcl/filters/impl/local_maximum.hpp#L122-L125 But I think whether radius_indices is sorted or not won't affect the result though. As long as it finds any neighbor point is higher than the current point, and it doesn't matter which higher point is found first https://github.com/PointCloudLibrary/pcl/blob/cd99687bd1f332d77aee06a8e9fbad4fb08c0a44/filters/include/pcl/filters/impl/local_maximum.hpp#L147-L157 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android.

[mvieth]

Thank you @xq198109 for reporting this and @tin1254 for looking into it further.
The first thing we should do is to create one or more new tests in test/filters/test_local_maximum.cpp, since the one that is there apparently did not catch these problems. I think if we copy the test and simply reorder the points, we should at least catch the bug about points/indices not getting added to the result when they have been marked as visited. After that, we can discuss the solution.
Regarding the question whether the results have to be sorted or not: I think they don't have to be sorted, but the loops should start at k = 0, not k = 1. Requesting the results to be sorted likely means that the algorithm will be slower, so we should avoid that if possible. Even if the index of the query point itself is in radius_indices, this shouldn't be a problem because the operation is "greater than" (>), not "greater or equal" (>=), and the z value of the query point can't be greater than itself.
Would one of you be interested in starting a pull request?

[ArkaprabhaChakraborty]

@mvieth I want to work on this issue.

[tin1254]

I've been very busy lately, it would be great if @ArkaprabhaChakraborty can work on this

[ArkaprabhaChakraborty]

@mvieth Can I get a head start?

[mvieth]

Basically what I described in my comment above: Write more tests to show that the current behaviour is wrong, then fix the wrong behaviour so that the new tests pass. I think the apparent problem(s) are sufficiently explained in the other comments

[kunaltyagi]

@mvieth k=0 is the query point itself, right? This would be because the (projected) point closest to a query point (from the projected cloud) is... the (projected) point itself

How does looping from k=0 change anything? What am I missing here?

Current code with inline comments marked with <---

    point_is_max[iii] = true;
    point_is_visited[iii] = true;

    // find neighbors (code skipped)
    
    // Check to see if a neighbor is higher than the query point
    float query_z = (*input_)[iii].z;
    for (std::size_t k = 1; k < radius_indices.size (); ++k)  // k = 1 is the first neighbor
    {
      if ((*input_)[radius_indices[k]].z > query_z)  // <--- this would be false for k=0, so we just skip onto k=1
      {
        // Query point is not the local max, no need to check others
        point_is_max[iii] = false;
        break;
      }
    }

    // If the query point was a local max, all neighbors can be marked as
    // visited, excluding them from future consideration as local maxima
    if (point_is_max[iii])
    {
      for (std::size_t k = 1; k < radius_indices.size (); ++k)  // k = 1 is the first neighbor
      {
        point_is_visited[radius_indices[k]] = true;  // <--- this is already true for k = 0
      }
    }

[larshg]

I just debugged a little and as already mentioned the radius search returns the points unordered ie:

So the first point is not necessarily the query point.

[kunaltyagi]

It might be a bigger issue in that case. I've seen this assumption in a lot of places.

~/workspace/pcl$ grep '\[0\] should be' -nri
features/include/pcl/features/impl/our_cvfh.hpp:127:      for (std::size_t j = 1; j < nn_indices.size (); ++j) // nn_indices[0] should be sq_idx
recognition/include/pcl/recognition/impl/hv/hv_go.hpp:99:      for (std::size_t j = 1; j < nn_indices.size (); ++j) // nn_indices[0] should be sq_idx
segmentation/include/pcl/segmentation/extract_clusters.h:154:        for (std::size_t j = 1; j < nn_indices.size (); ++j)             // nn_indices[0] should be sq_idx
segmentation/include/pcl/segmentation/extract_clusters.h:274:        for (std::size_t j = 1; j < nn_indices.size (); ++j)             // nn_indices[0] should be sq_idx
segmentation/include/pcl/segmentation/impl/extract_labeled_clusters.hpp:111:           ++j) // nn_indices[0] should be sq_idx
segmentation/include/pcl/segmentation/impl/seeded_hue_segmentation.hpp:99:      for (std::size_t j = 1; j < nn_indices.size (); ++j)             // nn_indices[0] should be sq_idx
segmentation/include/pcl/segmentation/impl/seeded_hue_segmentation.hpp:176:      for (std::size_t j = 1; j < nn_indices.size (); ++j)             // nn_indices[0] should be sq_idx

Checked the source code of difference search providers.

Good assumption (Checkedstill not sure on these. The rabbit hole goes deep):

• kdtree_flann/flann_search: (good assumption if the tree is created inside the algorithm. sorted-ness is a parameter)
• voxel_grid_covariance: indirectly calls kdtree_flann search

Bad assumption:

• organized_neighbor_search: bad assumption
• brute-force: bad assumption
• kdtree: purely virtual implementation
• octree: bad assumption

This is valid for both cpu and cuda/gpu implementations. Flann's code is a big foreign to me, but it doesn't seem promising because it's using omp (which definitely wouldn't guarantee order)

TL;DR: fix is correct, but we might have a bigger problem at hand

[larshg]

Actually I also saw this when I worked with the extract_clusters and GPU/CUDA with @FabianSchuetze, but here it didn't matter because it was already added to the cluster, except a bit of processing time ofc.

I guess we should investigate in found cases supplied by your search @kunaltyagi.

[kunaltyagi]

Also found that FLANN might not be a good assumption in all cases. I think we should create a separate issue to track this mess

[sourav25998]

Hello @mvieth . Is this issue still available? I would like to work on it. Can you please assign this to me and give me a head start?

[mvieth]

@sourav25998 I believe this issue is more complex than it initially appeared. So it might not qualify as a "good first issue" and you may want to look for another issue to work on.