Efficient and High-quality Ellipse Detection via Implicitly Excluding Most Useless Arc Groups and Enhancing Arc detection

1） Our contribution on arc extraction is to more reasonably connect neighboring edge pixels. For high-noise/low-contrast images, it is not easy to detect edge pixels. This would be particularly added in our limitation, though it is discussed in the limitation that our method is prevented by arc extraction.

2） In our tests, we compared with the learning-based method [15], which was published in 2022, later than ref.[21] and [22]. The results in Table 2 & 3 show the method [15] is much inferior to ours in both accuracy and efficiency. Current learning methods for ellipse detection have similar shortcomings, as discussed in the second paragraph of Section2. Thus, we only use ref. [15] as an example for comparison in the tests. In Figure 10, a learning method [25] is also compared with our method on edge extraction, showing we can more effectively detect ellipses.

Besides, the method of [21] and [22] are designed for specific data environment, like face detection and oil tank detection. Both methods regards objects that are not strictly elliptical (geometrically) as detected ellipses, which is obviously not our target. Our methods, like most previous ellipse detection methods, aims to detected geometrically elliptical contours and recover their accurate parameters.

3） For uneven arc distribution, grid resolution can be optimized, e.g., using hierarchical grid construction. This could be studied in the future. In this paper, we try to show that using a grid to support an orderly visit of grid cells for arc grouping, a lot of useless arc groups can be implicitly excluded for acceleration.

4） For the images with higher noise levels or occlusions, the difficulty is mainly about arc extraction. When arcs are well extracted, our ellipse detection can have similar performance because we try all possible arc groups for ellipse detection.

5） Theoretical bounds One of our contributions is to implicitly exclude useless arc groups. For a useless group of two arcs, say arc1 and arc2, suppose arc1 is nearer to the center of the grid than arc2. Then, arc1 would be taken as an active arc for arc grouping, and this useless group would be implicitly excluded when arc2 is not in the improved arc search region of arc1; otherwise, this useless group would be checked. Thus, our implicit exclusion of useless groups is dependent on the distribution of arcs.

It may occur that for any a useless group of two arcs, the improved arc search region of the active arc of the group contains the other arc as the inactive one. In this case, we can have no implicit exclusion of useless groups. Of course, it may also occur that for any a useless group of two arcs, the improved arc search region of the active arc of the group does not contain the other arc as the inactive one, and so we would implicitly exclude all useless groups.

In practice, there are often many ellipses in the image and the arc distribution would have our method take effect. Let’s first discuss a case that arcs are distributed evenly and each grid cell contains an arc, where all these arcs open towards the center of the grid.

Without loss of generality, suppose the grid is consisted of $k\cdot k$ cells. For an arc inside a cell, which is $i$ cells away from the center of the grid along an axis, its arc-search region would contain $k\cdot (k/2+i)$ cells at the most when the arc is very near a straight line and opens towards the center of the grid, $i=0, 1, 2, \dots$. In this case, our improved arc-search region would exclude the $2 i\cdot 2 i$ cells at center of the grid from the arc-search region. Thus, for this arc, many arcs in the excluded cells are implicitly excluded from arc grouping with the arc as an active one. Clearly, with our traversal order to visit grid cells from the center outwards, the cells containing such an arc would be in the number of $4 i$. Therefore, when all grid cells are visited, using the arc-search regions of Prasad et al. [5], grid cells to be checked for arc grouping would be in the times of $A=\sum_{i=0}^{k/2}k\cdot (k/2+i)\cdot 4 i$, while using our improved arc-search regions, the implicitly excluded grid cells for arc grouping would be in the times of $B=\sum_{i=0}^{k/2}(2 i\cdot 2 i)\cdot 4 i$. Thus, the implicit exclusion rate is $B/A=(3 k^2+12 K+12)/(5 k^2+12 k+4)$ and $\lim_{k\rightarrow \infty}⁡ B/A=3/5=0.6$.

The case discussed in the above is an expectation one. When arcs are unevenly distributed, hierarchical grids can be constructed for the cells of a higher hierarchical level all containing arcs, while the sub-trees of the hierarchical level are iteratively handled in the same way. Thus, the above analysis could be almost applied for general cases in practice, and our implicit exclusion rate may be often around 0.6 for practical cases. As the analysis is by estimating the arc-search region containing k*(k/2+i) cells very conservatively, our implicit exclusion rate could be higher than 0.6 for practical cases, as shown by the results in Table 1 of the paper.

6） hyperparameter sensitivity For the thresholds of the parameters on arc determination and valid checks, we follow the suggestions of corresponding papers, especially the suggestion of Ref. [9]. For the sensitivity of these parameters, e.g., for low-contrast or high-noise images, there are also corresponding discussions in these related papers. Our contribution in this paper is mainly on using a grid to implicitly exclude a lot of useless groups for acceleration and connecting edge pixels to extract arcs more reasonably. They are not related to the settings of these thresholds of these parameters. Of course, for high quality ellipse detection, these thresholds should be well studied, especially for low-contrast or high-noise images. Here, we provide the results on parameter selection for $\theta_{arc}$ and $L_{arc}$ in the following tables. From the statistics here, it is known that: 1. larger $\theta_{arc}$ leads to longer time consumption, and the F-1 score is the highest near $\theta_{arc}=49$ ; 2. larger $L_{arc}$ leads to less time consumption, and the F-1 score is the highest near $L_{arc}=52$. If $\theta_{arc}$ is too large, we cannot split contour into arcs successfully; if $\theta_{arc}$ is too low, the contour will be over-split. Therefore, we chose these values for our ellipse detector.

7） Runtime break down

We collected the time (second) consumption of each step of our method on 4 datases, as shown in the table below. From the statistics here, it is known that the time of grouping is largely compressed due to our new grid-based strategy. The time of arc extraction is related to the resolution of the input image. Therefore, it is lower on dataset with lower resolution such as Prasad, and higher on dataset with higher resolution such as Smartphone. Please refor to the appendices for more information of the datasets.

8） When our paper is published, we will apply for permission of our institution to open the source codes.

1. Our contribution on arc grouping is that we can further reduce the scope of arc search regions, as illustrated by our improved arc search region of arc R1 in Figure 2, and implicitly exclude a lot of useless arc groups. The results in Table 1 show that we can greatly implicitly exclude useless groups, in comparison with using arc search regions only.
2. We have compared with a learning method ref. [15] as an example in experiments. The results in Table 2 & 3 show that ours is much superior to the method of ref.[15] on both accuracy and efficiency. An example is illustrated in Figure 1. In Figure 10, a learning method [25] is also compared with our method on edge extraction, showing that we can more effectively detect ellipses.
3. Ellipse detection is belonged to the topic of computer vision, which is one of the topics interested by NeurlPS.

1. Our contribution is mainly on using a grid to support an orderly visit of grid cells, by which a lot of useless groups can be implicitly excluded for acceleration, in addition to a contribution to more reasonably connect edge pixels for arc extraction. For arc completion, like {1}, it is not our main target here. As discussed in our limitation, arc extraction would prevent our ellipse detection. This would be seriously studied.
2. In our experiments, we compared with the learning-based method [15], which was published in 2022, later than [21][22]. The results in Table 2 & 3 show the method [15] is much inferior to ours in both accuracy and efficiency. Current learning methods for ellipse detection have similar shortcomings, as discussed in the second paragraph of Section 2. Thus, we only use ref. [15] as an example of learning methods for comparison in the tests. Besides, the method of [21] and [22] are designed for handling specific data for face detection and oil tank detection. They don't care for strict ellipse detection and there are no overlapped cases for oil tanks. Our methods, like most previous ellipse detection methods, aims to detected geometrically elliptical contours and recover their corresponding ellipses.
3. In our method, we try to have two arcs in pairs as many as possible for ellipse detection, in addition to approximating an ellipse for each arc. Thus, for two ellipses overlapped very much, they can be still detected respectively when they each have respective arcs. Of course, computation errors due to limited bits to represent numbers would also prevent our performance. This is a general problem, required to be studied seriously. Our particular improvement over existing methods is to implicitly exclude a lot of useless groups for promoting ellipse detection.

I thank the authors for their response.

However, based on:

• The reluctance from the authors to improve the comparison with previous existing methods (despite being one of the main request of most reviewers),
• The poor complexity analysis: the grid constructed is uniform over the image and there's no reason that ellipses should also be uniformly distributed over the entire image, so the complexity is very likely not in $O(N)$ as claimed by the authors). This is also linked with the lack of clear theoretical model that would lead to guarantees as pointed out by an other reviewer.
• The clear limitations of the method: the methods show clear limitations and the answer from the authors is that it's the arc detection part's fault. In that case, the proposed method is mostly an acceleration of the search region block, thus with a limited impacted.

I'm inclined to decrease my rating to reject. As I stated, the work is potentially interesting but the presentation is too flawed in it's current state.

1) Implicit exclusion rate

For the implicit exclusion rate of our method against the method of ref.[5]，we have a discussion as follows.

For a useless group of two arcs, say arc1 and arc2, suppose arc1 is nearer to the center of the grid than arc2. Then, arc1 would be taken as an active arc for arc grouping, and this useless group would be implicitly excluded when arc2 is not in the improved arc search region of arc1; otherwise, this useless group would be checked. Thus, our implicit exclusion of useless groups is dependent on the distribution of arcs.

It may occur that for any a useless group of two arcs, the improved arc search region of the active arc of the group contains the other arc as the inactive one. In this case, we can have no implicit exclusion of useless groups. Of course, it may also occur that for any a useless group of two arcs, the improved arc search region of the active arc of the group does not contain the other arc as the inactive one, and so we would implicitly exclude all useless groups.

In practice, there are often many ellipses in the image and the arc distribution would have our method take effect. Let’s first discuss a case that arcs are distributed evenly and each grid cell contains an arc, where all these arcs open towards the center of the grid.

Without loss of generality, suppose the grid is consisted of $k\cdot k$ cells. For an arc inside a cell, which is $i$ cells away from the center of the grid along an axis, its arc-search region would contain $k\cdot (k/2+i)$ cells at the most when the arc is very near a straight line and opens towards the center of the grid, $i=0, 1, 2, \dots$. In this case, our improved arc-search region would exclude the $2 i\cdot 2 i$ cells at center of the grid from the arc-search region. Thus, for this arc, many arcs in the excluded cells are implicitly excluded from arc grouping with the arc as an active one. Clearly, with our traversal order to visit grid cells from the center outwards, the cells containing such an arc would be in the number of $4 i$. Therefore, when all grid cells are visited, using the arc-search regions of Prasad et al. [5], grid cells to be checked for arc grouping would be in the times of $A=\sum_{i=0}^{k/2}k\cdot (k/2+i)\cdot 4 i$, while using our improved arc-search regions, the implicitly excluded grid cells for arc grouping would be in the times of $B=\sum_{i=0}^{k/2}(2 i\cdot 2 i)\cdot 4 i$. Thus, the implicit exclusion rate is $B/A=(3 k^2+12 K+12)/(5 k^2+12 k+4)$ and $\lim_{k\rightarrow \infty}⁡ B/A=3/5=0.6$.

The case discussed in the above is an expectation one. When arcs are unevenly distributed, hierarchical grids can be constructed for the cells of a higher hierarchical level all containing arcs, while the sub-trees of the hierarchical level are iteratively handled in the same way. Thus, the above analysis could be almost applied for general cases in practice, and our implicit exclusion rate may be often around 0.6 for practical cases. As the analysis is by estimating the arc-search region containing k*(k/2+i) cells very conservatively, our implicit exclusion rate could be higher than 0.6 for practical cases, as shown by the results in Table 1 of the paper.

2) Parameter selection

Our method has some parameters.

• For the grid resolution, it is determined by an ideal expectation. Actually, it is motivated by the work of “Borut Zalik and Ivana Kolingerova. A cell-based point-in-polygon algorithm suitable for large sets of points. Computers & Geosciences, 27(10):1135–1145, 2001” to generate O(N) grid cells for a polygon with N edges, so that a cell is expected to have O(1) edge. In general, such a grid resolution can achieve good performance. With such a grid resolution, each cell is expected to contain O(1) arcs, and an arc is expected to cross O(1) cell.
• For the thresholds of the parameters on arc determination and valid checks, we follow the suggestions of corresponding papers, especially the suggestion of Ref. [9]. For the sensitivity of these parameters, e.g., for low-contrast or high-noise images, there are also corresponding discussions in these related papers. Our contribution in this paper is mainly on using a grid to implicitly exclude a lot of useless groups for acceleration and connecting edge pixels to extract arcs more reasonably. They are not related to the settings of these thresholds of these parameters, which are mostly related to detection of edge pixels. Of course, for high quality ellipse detection, these thresholds should be well studied, especially for low-contrast or high-noise images. Here, we provide the results on parameter selection for $\theta_{arc}$ and $L_{arc}$ in the following tables. From the statistics here, it is known that: 1. larger $\theta_{arc}$ leads to longer time consumption, and the F-1 score is the highest near $\theta_{arc}=49$ ; 2. larger $L_{arc}$ leads to less time consumption, and the F-1 score is the highest near $L_{arc}=52$. If $\theta_{arc}$ is too large, we cannot split contour into arcs successfully; if $\theta_{arc}$ is too low, the contour will be over-split. Therefore, we chose these values for our ellipse detector.

3) Time complexity

Our grid is constructed to expect $O(N)$ cells for $N$ arcs, so that each cell is expected to contain $O(1)$ arc and an arc is expected to cross $O(1)$ cell. Thus, our expected memory complexity for the grid is $O(N)$. As for the time complexity of our method on ellipse detection, it is mainly determined on the number of extracted arcs, not the number of pixels. This is because the pixels are only used for arc extraction in our method, in $O(n)$ time when there are $n$ pixels. Our time complexity for ellipse detection should be over $O(N)$ because each arc is used as the active arc once for arc grouping. For the arcs in the improved arc search region of an active arc, each of them would be used for arc grouping with the active arc for ellipse detection, so that our time complexity is mainly determined by the size of the expected improved arc search region of an arc. For a cell with $i$ cells away from the center of the grid, which has $k\cdot k =O(N)$ cells, its contained arc would have its improved arc search region contain $O(k\cdot (k/2+i)-(2 i)\cdot (2 i))$ cells at the most, as discussed in answer 1). Thus, under the expected situation with $O(N)$ cells generated and each cell containing $O(1)$ arc, our time complexity would be $O(\sum_{i=0}^{k/2}((k\cdot (k/2+i)-4i^2)\cdot 4i)=O(k^2\cdot (7 k^2+12 k-4)/24)=O(N^2)$. Clearly, an arc can be grouped with all other arcs respectvely, and so in a time complexity of $O(N^2)$. This is the time complexity of our method. Fortunately, we can actually exclude a lot of useless groups implicitly, and so achieving acceleration over existing methods.

4) Limitations

Limitations would be more deeply discussed, as arc extraction is much dependent on the image quality, such as those with high level noises or low contrasts. Of course, due to computation errors from limited bits to represent numbers, we may fail in handing the ellipses that are overlapped very much. Some failure examples would be provided. Due to policy restrictions, we are unable to provide images here. They will be added to the revised paper.

As suggested, hierarchical grid construction would be studied for further improvement when there is an uneven arc distribution. As for extension to high-dimensional parameter spaces, it is very interesting and would be studied.

5）Negative societal impact

Thanks for suggestion. For negative societal impact, we will have a discussion in the revised paper.