# Mathematical Methods for IoT-Based Annotating Object Datasets with Bounding Boxes

Authors: Abdelhamid Zaidi
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Object datasets used in the construction of object detectors are typically annotated with horizontal or oriented bounding rectangles for IoT-based. The optimality of an annotation is obtained by fulfilling two conditions: (i) the rectangle covers the whole object and (ii) the area of the rectangle is minimal. Building a large-scale object dataset requires annotators with equal manual dexterity to carry out this tedious work. When an object is horizontal for IoT-based, it is easy for the annotator to reach the optimal bounding box within a reasonable time. However, if the object is oriented, the annotator needs additional time to decide whether the object will be annotated with a horizontal rectangle or an oriented rectangle for IoT-based. Moreover, in both cases, the final decision is not based on any objective argument, and the annotation is generally not optimal. In this study, we propose a new method of annotation by rectangles for IoT-based, called robust semi-automatic annotation, which combines speed and robustness. Our method has two phases. The first phase consists in inviting the annotator to click on the most relevant points located on the contour of the object. The outputs of the first phase are used by an algorithm to determine a rectangle enclosing these points. To carry out the second phase, we develop an algorithm called RANGE-MBR, which determines, from the selected points on the contour of the object, a rectangle enclosing these points in a linear time. The rectangle returned by RANGE-MBR always satisfies optimality condition (i). We prove that the optimality condition (ii) is always satisfied for objects with isotropic shapes. For objects with anisotropic shapes, we study the optimality condition (ii) by simulations. We show that the rectangle returned by RANGE-MBR is quasi-optimal for the condition (ii) and that its performance increases with dilated objects, which is the case for most of the objects appearing on images collected by aerial photography.


---

## Body

## 1. Introduction

The construction of an object detector generally goes through a learning phase, followed by a testing phase, and ends with a tuning phase. Each phase requires an independent annotated object dataset. Annotating an image IoT-based signal and image processing applications consists of locating all the objects present in this image and determining their categories. The way to locate an object varies from detector to detector. For example, mask R-CNN detector uses segmentation mask to locate objects [1], CoKe detector uses key points and landmarks to locate objects [2], and poly-YOLO detector represents objects using polygons [3]. However, the rectangle is considered to be the simplest and most used polygonal shape for locating or representing an object in many computer vision applications for IoT-based [4]. Locating an object using a rectangle consists of drawing a rectangle surrounding this object. The annotation of an object dataset is performed using free or commercial software designed for a particular annotation choice.There are two types of annotations with rectangles depending on the orientations of the objects in the images for IoT-based. To locate objects, the first type uses horizontal bounding rectangles (HBR), while the second type uses oriented bounding rectangles (OBR). Annotation with horizontal rectangles is suitable for natural scenes, where the photographer is usually in front of the object and adjusts their camera so that the objects appear aligned with the horizontal edges of the image. By contrast, for aerial photography, where images are captured by Earth observation satellites or other flying devices, objects often appear in the image with arbitrary orientations.The optimality of an annotation results in the satisfaction of two conditions: (i) the bounding rectangle must cover the whole of the object and (ii) the area of the bounding rectangle must be minimal. For a horizontal object, it is easy to reach the optimal HBR that satisfies conditions (i) and (ii) mentioned above. On the other hand, for an oriented object, it is difficult to reach the optimal OBR if the annotation method does not render account of optimality conditions (i) and (ii).In the literature, we distinguish two types of object detectors. The first type includes horizontal object detectors, which detect objects using HBR. The second type includes oriented object detectors, which detect objects using OBR. Any detector of the first class is trained, tested, and tuned on horizontal object datasets (HOD). On the other hand, some oriented object detectors are trained and tuned on HOD, such as OAOD [5] and BBAVectors [6], but others are trained tuned on to oriented object datasets (OOD), such as RoI transformer [7], R-RoI [8], RRPN [9], R2CNN++ [10], DMPNet [11], FOTS [12], RPN [13], and DDR [14]. However, all of these oriented object detectors must be tested on OOD.A large-scale HOD (OOD, respectively) is a set made up of a large number of images annotated with HBR (OBR, respectively). Each image contains objects of a wide variety of scales, orientations, and shapes. These objects are divided into classes (or categories) that vary from one dataset to another.Table1 (Table 2, respectively) presents the number of classes, instances, images, and year of creation of the most cited HOD (OOD, respectively) in the literature. To our knowledge, DOTA is the largest public Earth vision object detection dataset [27]. It contains objects exhibiting a wide variety of scales, orientations, and shapes. Moreover, images of DOTA are manually annotated by experts in aerial image interpretation.Table 1
Examples of large-scale horizontal object datasets.
NameClassesInstancesImagesYearDIOR [15]20190288234632019TUT indoor [16]74595221372018MS COCO [17]808862661232872014PASCAL VOC [18]171793658112682012ImageNet [19]2004788074565672009Table 2
Examples of large-scale oriented object datasets.
NameClassesInstancesImagesYearDOTA-v2.0 [20]171793658112682021FGSD [21]1563426122020HRSC2016 [22]1297610612016UCAS-AOD [23]21459615102015DLR 3k [24]214235202015VEDAI [25]3295012682015SZTAKI-INRIA [26]166592012


## 2. State of the Art

In order to generate a dataset for object identification, we need to gather a large number of photographs, all of which must be annotated using the same technique and organized in accordance with a set of categories that have been predetermined. The dataset has to include many photographs that match to various instances of each object class. These images must be included for each object class. The currently available annotation techniques are amenable to being split up into two primary categories. In the first class, all methods of manual annotation are grouped together, and in the second class, all techniques of semi-automatic annotation are categorized together [28].


### 2.1. Manual Annotation

There are two main methods of manually annotating objects with bounding boxes, which are used in the construction of most large-scale object datasets. The first one is called the consensus method, and the second one is called the sequential tasks method. For each instance of an object in an image, the first method asks several annotators to draw a rectangle around the object and then defines the position of the object by the rectangle elected by the majority of annotators. To annotate an object by the second method, we need at least three annotators. The first one is asked to draw a rectangle around a single instance of the object. The task of the second annotator is to validate the drawn rectangle. The third person investigates whether additional object class instances require annotation. Determining a precise bounding rectangle takes more time and resources than validating the annotation, and thus, the consensus technique is more efficient. Annotation quality affects the development of accurate object detectors. The determination of a large-scale object dataset requires expert annotators, significant working time, and remuneration in line with the desired accuracy. As examples of common use datasets, annotated with the manual methods, we cite PASCAL VOC [18], MS COCO [17], ImageNet [19], DOTA [20], etc.Although studies on the description of OOD are abundant, very few of them explain how to draw a rectangle enclosing an oriented object. The only annotation method explicitly described in the literature appears in the article [27] by Ding et al. This method consists in drawing a HBR around the object of interest and then adjusting the angle manually by rotating the rectangle with the mouse.


### 2.2. Semi-Automatic Annotation

The traditional semi-automatic approach of annotating objects with rectangles consists of four phases.First phase: in this phase, the images of the object dataset are divided into two subsets of unequal sizes. The smallest subset is annotated with rectangles by the manual method.Second phase: the second phase consists of choosing an object detector and training this detector with the images from the dataset already annotated.Third phase: once the detector is ready, it will be used to annotate the images of the second object dataset with the prediction rectangles.Fourth phase: during this phase, the annotator validates the correctly annotated objects during the third phase and manually draws the bounding rectangles of the poorly annotated objects.As this study is limited to locating objects by bounding boxes, we cite the Faster Bounding Box (FBB) as an example of semi-automatic annotation method [16]. This method was used to generate the Tampere University of Technology (TUT) Indoor dataset. The largest subset is annotated with prediction rectangles, generated by the Faster R-CNN object detector [29], trained on the smallest annotated subset.


### 2.3. Performance Measure of Detectors Using Rectangles

The evaluation of the effectiveness of the object detector is then performed on the second subset of the annotated dataset. Since we are only dealing here with annotations using bounding boxes, the most used criterion to compare two rectangles is the Jaccard’s similarity index, also known as the Intersection over Union (IoU). For each image of the testing dataset, the IoU measures the percentage of overlap between the prediction bounding rectangleA^ generated by the detector, and the ground truth bounding box A, as follows:(1)IoUA^,A=AreaA^∩AAreaA^∪A.We note that theIoU score lies in the interval 0,1. The closer this index gets to 1, the better the detection of the object. We say that an object is well detected (or true positive) if the IoU score is greater than or equal to a threshold discussed by experts. In most studies, the threshold value is set at 0.5 [30]. The IoU score causes a problem when its value is zero. This value is embarrassing since it does not explain how far is the prediction bounding rectangle from the ground truth bounding box. To work around this problem, Rezatofighi et al. [30] suggest replacing the IoU with the Generalized Intersection over Union GIoU index. The GIoU between two rectangles A^ and A is defined as follows:(2)GIoUA^,A=IoUA^,A−Areaℂ\A^∪AAreaℂ,where ℂ is the smallest convex set enclosing both A^ and A.The exact IoU computation between two HBR is simple. Much software integrates functions to calculate this index. On the other hand, the exact IoU computation between two OBR is not as simple as that between two HBR. Liu et al. (Yao et al., respectively) proposed in Ref. [31] (in [32]) heuristic to estimate the IoU between two OBR. Recently, Zaidi has shown in Ref. [28] that these heuristics give reliable results only when the centers of the rectangles are very close and the angle between the rectangles is small. Moreover, he has developed in Ref. [28] an algorithm that calculates the exact IoU value between two OBR, as well as an ε,α estimator of the IoU.The annotation method has a direct bearing on the performance measurement of an object detector. The OOD reserved for the test phase must be carefully annotated so that the IoU computation between the ground truth and prediction rectangles is not biased.


## 2.1. Manual Annotation

There are two main methods of manually annotating objects with bounding boxes, which are used in the construction of most large-scale object datasets. The first one is called the consensus method, and the second one is called the sequential tasks method. For each instance of an object in an image, the first method asks several annotators to draw a rectangle around the object and then defines the position of the object by the rectangle elected by the majority of annotators. To annotate an object by the second method, we need at least three annotators. The first one is asked to draw a rectangle around a single instance of the object. The task of the second annotator is to validate the drawn rectangle. The third person investigates whether additional object class instances require annotation. Determining a precise bounding rectangle takes more time and resources than validating the annotation, and thus, the consensus technique is more efficient. Annotation quality affects the development of accurate object detectors. The determination of a large-scale object dataset requires expert annotators, significant working time, and remuneration in line with the desired accuracy. As examples of common use datasets, annotated with the manual methods, we cite PASCAL VOC [18], MS COCO [17], ImageNet [19], DOTA [20], etc.Although studies on the description of OOD are abundant, very few of them explain how to draw a rectangle enclosing an oriented object. The only annotation method explicitly described in the literature appears in the article [27] by Ding et al. This method consists in drawing a HBR around the object of interest and then adjusting the angle manually by rotating the rectangle with the mouse.


## 2.2. Semi-Automatic Annotation

The traditional semi-automatic approach of annotating objects with rectangles consists of four phases.First phase: in this phase, the images of the object dataset are divided into two subsets of unequal sizes. The smallest subset is annotated with rectangles by the manual method.Second phase: the second phase consists of choosing an object detector and training this detector with the images from the dataset already annotated.Third phase: once the detector is ready, it will be used to annotate the images of the second object dataset with the prediction rectangles.Fourth phase: during this phase, the annotator validates the correctly annotated objects during the third phase and manually draws the bounding rectangles of the poorly annotated objects.As this study is limited to locating objects by bounding boxes, we cite the Faster Bounding Box (FBB) as an example of semi-automatic annotation method [16]. This method was used to generate the Tampere University of Technology (TUT) Indoor dataset. The largest subset is annotated with prediction rectangles, generated by the Faster R-CNN object detector [29], trained on the smallest annotated subset.


## 2.3. Performance Measure of Detectors Using Rectangles

The evaluation of the effectiveness of the object detector is then performed on the second subset of the annotated dataset. Since we are only dealing here with annotations using bounding boxes, the most used criterion to compare two rectangles is the Jaccard’s similarity index, also known as the Intersection over Union (IoU). For each image of the testing dataset, the IoU measures the percentage of overlap between the prediction bounding rectangleA^ generated by the detector, and the ground truth bounding box A, as follows:(1)IoUA^,A=AreaA^∩AAreaA^∪A.We note that theIoU score lies in the interval 0,1. The closer this index gets to 1, the better the detection of the object. We say that an object is well detected (or true positive) if the IoU score is greater than or equal to a threshold discussed by experts. In most studies, the threshold value is set at 0.5 [30]. The IoU score causes a problem when its value is zero. This value is embarrassing since it does not explain how far is the prediction bounding rectangle from the ground truth bounding box. To work around this problem, Rezatofighi et al. [30] suggest replacing the IoU with the Generalized Intersection over Union GIoU index. The GIoU between two rectangles A^ and A is defined as follows:(2)GIoUA^,A=IoUA^,A−Areaℂ\A^∪AAreaℂ,where ℂ is the smallest convex set enclosing both A^ and A.The exact IoU computation between two HBR is simple. Much software integrates functions to calculate this index. On the other hand, the exact IoU computation between two OBR is not as simple as that between two HBR. Liu et al. (Yao et al., respectively) proposed in Ref. [31] (in [32]) heuristic to estimate the IoU between two OBR. Recently, Zaidi has shown in Ref. [28] that these heuristics give reliable results only when the centers of the rectangles are very close and the angle between the rectangles is small. Moreover, he has developed in Ref. [28] an algorithm that calculates the exact IoU value between two OBR, as well as an ε,α estimator of the IoU.The annotation method has a direct bearing on the performance measurement of an object detector. The OOD reserved for the test phase must be carefully annotated so that the IoU computation between the ground truth and prediction rectangles is not biased.


## 3. Motivation for the Study

The manual or semi-automatic annotation methods described in Section2 have made it possible to build many large-scale object datasets. These datasets have given rise to very powerful object detectors. However, we cannot ignore the following concerns:(1)
According to paragraph A, accurate manual annotation is expensive, time-consuming, and requires annotation experts.(2)
In many situations, the annotator can be in front of an object with an ambiguous orientation as shown in Figure1. In this case, he will take a considerable time to decide whether the object will be annotated with a horizontal rectangle or an oriented rectangle. Moreover, in both cases, the final decision is not based on any objective argument and depends solely on the dexterity of the annotator.(3)
The semi-automatic annotation defined in paragraph B does not guarantee the optimality of the annotation rectangle, in the sense that it must have a minimum area and cover the whole of the object.(4)
According to paragraph C, the use of any approximation methods ofIoUA,B, whether to measure the accuracy of an oriented object detector or to compare the performance of two oriented object detectors, could lead to biased results. Indeed, the function gx=x/a+b−x is strictly increasing over the interval 0,a+b, where a and b denote the areas of A and B, respectively. Therefore, a large or a small ground truth bounding rectangle directly induces a bias in the computation of the IoU.Figure 1
(b) Intuitively, it seems that the horizontal rectangleB=B1,…,B4 is best suited to annotate the colored object in blue (Figure (a)). The method we propose takes as input the set ℳ6=M1,…,M6 and returns the oriented rectangle A=A1,…,A4. Since A covers the whole object and AreaA<AreaB, then it is natural to annotate the object by the rectangle A.
(a)(b)The contribution of this study is the scarcity of annotation methods motivated us to develop a robust semi-automatic annotation method of OOD. Our method is semi-automatic because it consists of a manual step followed by a computer-assisted step. In addition, this method is robust because the bounding rectangle generated by our algorithm is insensitive to the dexterity of the annotator. More precisely, the steps are as follows:(i)
We develop an algorithm called RANGE-MBR, which determines from a setℳn of the n most relevant (in the sense given by Definition 1) points picked on the object outline, a rectangle enclosing ℳn and having a quasi-minimal area, in On time.(ii)
We propose a new approach to simultaneously build HOD and OOD from a large-scale image bank, based on both the RANGE-MBR algorithm and threshold angles.(iii)
We conduct a large experimental study to quantify the performance of the RANGE-MBR algorithm.(iv)
We compare the performance of RANGE-MBR to that of the benchmark algorithm, RC-MBR, which determines the minimum rectangle enclosingℳn in Onlnn time.This study seems essential to us because it responds to a real need in the development of oriented object detectors. In addition, it allows researchers to build their own oriented object datasets in a rigorous manner.Definition 1.
(relevant point of an object) Any point located on the contour of the object is said to be relevant if it is a local maximum, a local minimum, the most right point, the most left point, a cusp of the first type, a cusp of the second type, an inflection point, and so on.
The remainder of this manuscript is structured as follows. Section4 deals with the parametrization of rectangles. Section 5 is devoted to the development of the RANGE-MBR algorithm. We explain in Section 6 how to use the RANGE-MBR (or RC-MBR) algorithm to simultaneously generate horizontal and oriented datasets from a large-scale image bank. In Section 7, we perform various numerical experiments to evaluate the performance of the RANGE-MBR algorithm.


## 4. Parametrization of Bounding Rectangles

First, we give an overview of the different types of parameterization encountered in the literature. Then, we justify the choice of the parameterization associated with the annotation method that we propose in this study. Our choice of parameterization was discussed in a previous study on the accurate computation of the IoU [28]. However, it seems useful to us to recall this choice to facilitate the reading of the manuscript.


### 4.1. Parameterization of Horizontal Rectangles

The minimum parameterization of a horizontal rectangleA=A1,A2,A3,A4 requires four parameters. The object dataset PASCAL VOC [18] annotates the rectangle A with x4,y4,x2,y2, where xi,yi are the coordinates of the vertex Ai, i=1,…,4 (cf. Figure 2). The object dataset Ms COCO [17] annotates the rectangle A with x4,y4,w,h, where w and h denote the lengths of the line segments A1,A2 and A1,A4, respectively, and x4,y4 are the coordinates of the vertex A4 (cf. Figure 2). The object dataset ImageNet [19] annotates the rectangle A with x0,y0,w,h, where w and h denote the lengths of the line segments A1,A2 and A1,A4, respectively, and x0,y0 are the coordinates of the center A0 of A (cf. Figure 2).Figure 2
Parameterization of horizontal and oriented rectangles.


### 4.2. Parameterization of Oriented Rectangles

Five parameters—b1,b2,w,h, and θ—are necessary for the minimal parameterization of an orientated rectangle denoted by the formula B=B1,B2,B3,B4; these are the only parameters that are required. The coordinates for the center B0 of B are b1,b2, which correspond to the coupling b1 and b2. The lengths of the line segments B1,B2 and B1,B4 are indicated by the parameters w and h, respectively (cf. Figure 2). The parameter θ∈0,π/2 is used to determine the acute angle that exists between the lines Δ and B1,B2, where Δ denotes the horizontal line that goes through B1. These two object datasets, HRSC2016 [22] and UCAS-AOD [23], are annotated with the help of this parametrization.The aboveθ-based parametrization is not suitable for annotating satellite image datasets. These OOD have the particularity of containing a large number of instances per image, at different scales, and whose parts overlap [20]. A simple solution that overcomes the drawbacks of the θ-based annotation consists in defining a rectangle B=B1,B2,B3,B4 using the coordinates xi,yi1≤4 of the vertices B1,…,B4, respectively. To solve the indeterminacy problem linked to the permutations of the vertices, we can sort the vertices clockwise and fix the first point according to the following rules [27]:(i)
For objects with a distinguished head and a tail (e.g., vehicles and helicopters), the annotator carefully selectsB1 to indicate the left corner of the instance head.(ii)
For other objects (e.g., tennis courts and bridges),B1 is the point at the top left of the instance.This type of parametrization was used for the annotation of the DOTA object dataset [20].


### 4.3. Our Choice of Parametrization

We use the notationℝ=R1,R2,R3,R4 to denote an oriented rectangle whose vertices are R1, R2, R3, and R4. We assume that these vertices are sorted in counterclockwise order, such that R1 is the left vertex with the smallest vertical coordinate.To sort the vertices setB1,B2,B3,B4 of the rectangle B as described above, we first consider the barycenter G of the rectangle B. Then, we calculate the polar angle of each vertex relative to the barycenter G [28]. We denote by B1,…,B4, the sorted vertices in ascending order of their polar angle. If B32≤B42, then B=B3,B4,B1,B2, else B=B4,B1,B2,B3 (cf. Figure 2). For more details on the implementation of this sorting method, we refer the reader to our article [28].In this investigation, we describe a bounding rectangleB by using the eight-tuple x1,y1,…,x4,y4, where xi,yit are the coordinates of the i-th vertex of the sorted rectangle B1,…,B4.This choice of parameterization is ideally suited to the annotation approach that we suggest since it eliminates the need for extra computations to draw rectangles or to locate the images of rectangles by applying affine transformations. This is one of the reasons why the method is so efficient. In addition, we demonstrate in Section B how to format the outputs of the annotation technique that we propose in accordance with the annotation rule of the DOTA dataset. This is done by referring to the annotation rule.


## 4.1. Parameterization of Horizontal Rectangles

The minimum parameterization of a horizontal rectangleA=A1,A2,A3,A4 requires four parameters. The object dataset PASCAL VOC [18] annotates the rectangle A with x4,y4,x2,y2, where xi,yi are the coordinates of the vertex Ai, i=1,…,4 (cf. Figure 2). The object dataset Ms COCO [17] annotates the rectangle A with x4,y4,w,h, where w and h denote the lengths of the line segments A1,A2 and A1,A4, respectively, and x4,y4 are the coordinates of the vertex A4 (cf. Figure 2). The object dataset ImageNet [19] annotates the rectangle A with x0,y0,w,h, where w and h denote the lengths of the line segments A1,A2 and A1,A4, respectively, and x0,y0 are the coordinates of the center A0 of A (cf. Figure 2).Figure 2
Parameterization of horizontal and oriented rectangles.


## 4.2. Parameterization of Oriented Rectangles

Five parameters—b1,b2,w,h, and θ—are necessary for the minimal parameterization of an orientated rectangle denoted by the formula B=B1,B2,B3,B4; these are the only parameters that are required. The coordinates for the center B0 of B are b1,b2, which correspond to the coupling b1 and b2. The lengths of the line segments B1,B2 and B1,B4 are indicated by the parameters w and h, respectively (cf. Figure 2). The parameter θ∈0,π/2 is used to determine the acute angle that exists between the lines Δ and B1,B2, where Δ denotes the horizontal line that goes through B1. These two object datasets, HRSC2016 [22] and UCAS-AOD [23], are annotated with the help of this parametrization.The aboveθ-based parametrization is not suitable for annotating satellite image datasets. These OOD have the particularity of containing a large number of instances per image, at different scales, and whose parts overlap [20]. A simple solution that overcomes the drawbacks of the θ-based annotation consists in defining a rectangle B=B1,B2,B3,B4 using the coordinates xi,yi1≤4 of the vertices B1,…,B4, respectively. To solve the indeterminacy problem linked to the permutations of the vertices, we can sort the vertices clockwise and fix the first point according to the following rules [27]:(i)
For objects with a distinguished head and a tail (e.g., vehicles and helicopters), the annotator carefully selectsB1 to indicate the left corner of the instance head.(ii)
For other objects (e.g., tennis courts and bridges),B1 is the point at the top left of the instance.This type of parametrization was used for the annotation of the DOTA object dataset [20].


## 4.3. Our Choice of Parametrization

We use the notationℝ=R1,R2,R3,R4 to denote an oriented rectangle whose vertices are R1, R2, R3, and R4. We assume that these vertices are sorted in counterclockwise order, such that R1 is the left vertex with the smallest vertical coordinate.To sort the vertices setB1,B2,B3,B4 of the rectangle B as described above, we first consider the barycenter G of the rectangle B. Then, we calculate the polar angle of each vertex relative to the barycenter G [28]. We denote by B1,…,B4, the sorted vertices in ascending order of their polar angle. If B32≤B42, then B=B3,B4,B1,B2, else B=B4,B1,B2,B3 (cf. Figure 2). For more details on the implementation of this sorting method, we refer the reader to our article [28].In this investigation, we describe a bounding rectangleB by using the eight-tuple x1,y1,…,x4,y4, where xi,yit are the coordinates of the i-th vertex of the sorted rectangle B1,…,B4.This choice of parameterization is ideally suited to the annotation approach that we suggest since it eliminates the need for extra computations to draw rectangles or to locate the images of rectangles by applying affine transformations. This is one of the reasons why the method is so efficient. In addition, we demonstrate in Section B how to format the outputs of the annotation technique that we propose in accordance with the annotation rule of the DOTA dataset. This is done by referring to the annotation rule.


## 5. Determination of the Bounding Rectangle

It is natural to annotate the object with the minimum rectangle enclosing the set of relevant points. This problem is formulated as follows:Problem 1.
Given a set of pointsℳn=Mi=xi,yit∈ℝ2;i=1,…,n, we find a rectangle with the smallest area, enclosing ℳn. Such a rectangle is called a minimum bounding rectangle of ℳn and denoted by MBR ℳn.
The solution of problem 5.1 is not unique as shown in Figure3. So, MBR ℳn denotes any solution of Problem 1.
Freeman and Shapira proved in 1975 that one edge of MBRℳn must be collinear with an edge of the convex hull (CH ℳn) of ℳn. They proposed in Ref. [33] a natural algorithm to find MBR ℳn in On2 time, based on sweeping all minimum rectangles, enclosing ℳn, and having an edge collinear with an edge of CH ℳn. In 1978, Shamos proposed in Ref. [34] the famous rotating calipers algorithm, which return all pairs of antipodal vertices of a n-sided convex polygon in On time. In 1983, Toussaint used the rotating calipers technique and developed the algorithm RC-MBR to find MBR ℳn in Onlnn time [35]. In 2006, Dimitrov et al. proposed in Ref. [36, 37] the algorithm PCA-MBR, to approximate MBR ℳn, in Onlnn time, by the minimum bounding rectangle, which is aligned with the eigenvectors of the covariance matrix of CH ℳn. They also proved that the relative error between PCA-MBR ℳn and MBR ℳn is bounded from above by 82−1≈2.36. The main drawback of the algorithm PCA-MBR is that it admits an infinite number of solutions if the covariance matrix of CH ℳn has a double eigenvalue. To overcome the problem of nonuniqueness inherent in algorithms RC-MBR and PCA-MBR, we propose the method RANGE-MBR to approximate MBR ℳn in On time.Figure 3
ℳ5=M1,…,M5. The green and red rectangles are two distinct solutions of Problem 1.


### 5.1. The Range-MBR Algorithm

Letℬ=O,i,j be a Cartesian frame of the two-dimensional affine plane. All angles we refer to here are measured counterclockwise from the positive x-axis. Let Δ be the line passing through O and making an angle θ with the axis O,i. Let Δ⊥ be perpendicular to Δ and passing through O. Let P1 and Q1 (P2 and Q2, respectively) be the extreme points of the orthogonal projection of ℳn on Δ (Δ⊥, respectively). Let A=A1,A2,A3,A4 be the minimum bounding rectangle having an edge collinear with Δ. Then, A1,…,A4 are the intersection points of the two parallel lines to Δ⊥ and passing through P1 and Q1, respectively, with the two parallel lines to Δ and passing through P2 and Q2 respectively. The area of A is given by the product of lengths of the line segments P1,Q1 and P2,Q2. From now on, the MBR A enclosing ℳn and having an edge collinear with the direction making an angle θ from the positive x-axis will be denoted by MBRℳn,θ.Letu=cosθ,sinθt, and v=−sinθ,cosθt ) be two unit direction vector of Δ and Δ⊥, respectively. Then, ℬ=O,i,j and ℬ′=O,u,v are two Cartesian frames of the two-dimensional affine plane. For all i=1,…,n, we denote by xi,yit (si,tit, respectively) the coordinates of Mi with respect to the frame ℬ (ℬ′, respectively). Let Rθ be the rotation matrix of angle θ, and then xi,yit=Rθsi,tit, where ut is the transpose of u.LetX be a random variable with mean μ and standard deviation σ. Let x1:n=x1,…,xn be n observations on the variable X. Let x1≤…≤xn be the order statistics of x1:n. We define the range of x1:n by Rangex1:n=xn−x1. Therefore, the lengths of P1,Q1 and P2,Q2 are given by:(3)P1Q1=Ranges1,…,sn=sn−s1,P2Q2=Ranget1,…,tn=tn−t1.We denote byσ^n any estimation of σ obtained from x1:n. On the basis of numerous works carried out on the estimation of the standard deviation from the sample range ([38–43]), we can assume that there is a real constant αX,n such that(4)σ^n=Rangex1:nαX,n.Besides, it is well known that(5)Varx1:n=1n∑i=1nxi−x¯,which is an estimate of σ2, where x¯=1/n∑i=1nxi. It follows that there is a real constant αX,n such that:(6)Rangex1:n2≈αX,n2Varx1:n.We assume that thex,y coordinates of the set of points ℳn are n observations of two random variables X and Y. Since the AreaA=P1Q1⋅P2Q2, then combining equations (6) and (3) gives an approximation A^n2θ of AreaA, satisfying the following relation:(7)A^n2θ=αS,n2αT,n2Vars1:nVart1:n,where S,Tt=RθtX,Yt. To alleviate notions, we will also use Vx and ℂx,y to designate Varx1:n and Covx1:n,y1:n. Since xi,yit=Rθsi,tit, we obtain(8)Vs=cos2θVx+sin2θVy+sin2θℂx,y,Vt=sin2θVx+cos2θVy−sin2θℂx,y.Using (8) and some trigonometric identities, we prove that(9)8VsVt=K−fθ,where K=Vx2+Vy2+6VxVy−4ℂx,y2 and(10)fθ=Vx2+Vy2−2VxVy−4ℂx,y2cos4θ+4ℂx,yVx−Vysin4θ.Combining equations (7), (9), and (10) gives(11)A^n2θ=αS,n2αT,n28K−fθ.Thus, the area of MBR ℳn,θ is approximately equal to(12)αS,n2αT,n28K−fθ.Therefore, we propose to approximate MBR ℳn by MBR ℳn,θ∗ such that:(13)θ∗=argminθ∈−π/2,π/2A^n2θ=argmaxθ∈−π/2,π/2fθ.The first derivative off with respect to θ is given by:(14)f˙4θ=−4λsin4θ+4δcos4θ.where(15)λ=Vx2−Vy2−4ℂx,y2,δ=4ℂx,yVx−Vy.The functionf has a unique critical point θ∗ such that(16)tan4θ∗=δλ=4ℂx,yVx−VyVx2−Vy2−4ℂx,y2.Lemma 1.
The second derivative off at the critical point θ∗ has the same sign as −λ.Proof.
The second derivative off with respect to θ is given by:(17)f¨θ=−16λcos4θ+δsin4θ.
Multiplying both sides of the relation (17) by cos4θ yields(18)cos4θf¨θ=−16λcos24θ+δsin4θcos4θ,Multiplying both sides of the relation (14) by sin4θ yields(19)sin4θf˙θ=−4λsin24θ+4δsin4θcos4θ.
Using relations (19) and (18) with θ=θ∗ (i.e., f˙θ∗=0), we obtain:(20)4δcos4θ∗sin4θ∗=4λsin24θ∗,cos4θ∗f¨θ∗=−16λ.Therefore, f¨θ∗ has the same sign as −λcos4θ∗. Since 4θ∗=arctanδ/λ∈−π/2,π/2, then cos4θ∗>0 what ever the set ℳn may be. Thus, f¨θ∗ has the same sign as −λ.
Therefore, the determination ofθ∗ goes through six cases:Case 1: ifλ>0, then θ∗=1/4arctanδ/λ.Case 2: ifλ<0 and Vx≠Vy, then θ∗ is determined through the eigen decomposition of the empirical covariance matrix of ℳn. This case is discussed below.Case 3: ifλ<0 and Vx=Vy, then θ∗=π/4.Case 4: ifλ=0 and ℂxVx−Vy>0, then θ∗=π/8.Case 5: ifλ=0 and ℂxVx−Vy>0, then θ∗=π/8.Case 6: ifλ=0 and ℂxVx−Vy>0, then it is equivalent to Vx=Vy and ℂx=0. This case is discussed below.


#### 5.1.1. Illustrative Example of Case 6

It is difficult to illustrate all the scenarios, which fall into Case 6. The special case of regular polygons is the one that the annotator may encounter when annotating regular objects such as road signs, buildings, and human faces. Moreover, we have pointed out this case to warn the user to pay attention to regularly shaped objects when using our annotation method.Proposition 1.
If the elements ofℳn are the vertices of a regular n-sided polygon, then Vx=Vy and ℂx,y=0.Proof.
In the general case, the vertices of a regular polygon are uniformly distributed over a circle with radiusr and center G equal to the barycenter of ℳn. Thus, without loss of generality, we can assume that r=1, G=0,0t, and the kth vertex of ℳn is(21)Mk=cos2πk−1n,sin2πk−1nt.
Consider the complex sequencezk0≤k≤n−1, where z=exp2π/ni and i is the imaginary unit. Then,(22)∑k=0n−1zk=nx¯+y¯i.
Since∑k=0n−1zk=1−zn/1−z=0, then x¯=y¯=0, and(23)ℂx,y=1n∑k=1nxkyk,Vx=1n∑k=1nxk2,Vy=1n∑k=1nyk2.
Sincecos2x=2cos2x−1=1−2sin2x, then(24)Vx=12+12n∑k=0n−1cos4πkn,Vy=12−12n∑k=0n−1cos4πkn.
Besides,∑k=0n−1cos4πk/n is the real part of(25)∑k=0n−1z2k=1−z2n1−z2=0.
Thus,Vx=Vy=1/2. Moreover, using 2cosxsinx=sin2x, we deduce that(26)ℂx,y=12n∑k=0n−1sin4πkn.
Since∑k=0n−1sin4πk/n is the imaginary part of(27)∑k=0n−1z2k=1−z2n1−z2=0,then ℂx,y=0.
Note that in the case where the elements ofℳn are the vertices of a regular n-sided polygon, problem 5.1 has exactly n different solutions MBRiℳn, i=1,…,n. For all i=1,…,n−1, MBRiℳn is the image of MBR0ℳn by the rotation of angle θi=2i/nπ.


#### 5.1.2. Handling of the Exceptional Cases 2 and 6

Cases 2 and 6 are indeterminate cases for which the minimum of the objective functionfθ does not exist. This is why we have thought of a trick to get out of the indeterminacy of each case, by returning to the initial definition of the solution.(i)
For Case 2, the application of an affine isometry to the set of pointsℳn makes it possible to migrate to another case for which the angle θ is well determined. We then obtain the solution of the initial problem by applying the inverse isometry to the solution of the transformed problem, since isometry preserves the areas.(ii)
For Case 6, the use of an extra pointMn+1 belonging to the convex hull of the set ℳn, allows to migrate to another case for which the angle θ is well determined. Another alternative consists in asking the user to click on a point of the object’s outline until we get out this state.Case 2:λ=Vx−Vy2−4ℂx,y2 is negative because of ℂx,y2. To get rid of ℂx,y2, we have just to follow the same reasoning on a set of points(28)ℳn′=Mi′=xi′,yi′t∈ℝ2;i=1,…,n,whose coordinates x1:n′=x1,…,xn′ and y1:n′=y1,…,yn′ are uncorrelated. Let(29)Γ=1n∑i=1nMi−M¯Mi−M¯t,be the covariance matrix of the elements of ℳn, where M¯=x¯,y¯t. Let Γ=UΔUt be an eigen decomposition of Γ, where U∈O2ℝ (the set of 2-orthogonal matrices), and Δ=diagδ1,δ2. For all i=1,…,n, set Mi′=UtMi and ℳn′=Mi′1≤n≤n. Then,t(30)Γ′=1n∑i=1nMi′−M′¯Mi′−M′¯t=Δ,where M′¯=UtM¯. Since U∈O2ℝ, then the linear map defined by LM=UtM preserves the norm and the dot product. Thus, AreaMBRℳn=AreaMBRℳn′ and MBR ℳn is the image of MBR ℳn′ under the map L.Proposition 2.
If the vectorsx1:n and y1:n are uncorrelated ℂx,y=0 and have different variances Vx≠Vy, then A^n2θ has a unique minimum at the angle θ=0.Proof.
Sincex1:n and y1:n are uncorrelated, then ℂx,y=0, and λ=Vx−Vy2 and δ=0. According to equation (16), the function f has a unique critical point θ∗=0. Using Lemma 1, fθ is the maximum of fθ.Case 6. To get out of the indeterminacy of Case 6, we propose to add to the setℳn an artificial point Mn+1 located in the convex hull of ℳn so that the empirical covariance matrix of the new set ℳn+1=ℳn∪Mn+1 is different from a scalar matrix. We assume that xn+1,yn+1t are the Cartesian coordinates of Mn+1 with respect to ℬG=G,i,j, where G=x¯,y¯t is the barycenter of ℳn. Without any loss of generality, we assume that x1:n+1 (y1:n+1, respectively) is the vector of the x-coordinates (y-coordinates, respectively) of the points of ℳn+1 with respect to ℬG=G,i,j. We denote by V˜x=Varx1:n+1 and V˜y=Vary1:n+1. Lemma 2 gives the relation between Vx,Vy,ℂx,y and V˜x,V˜y,ℂ˜x,y, respectively.Lemma 2.
IfVx=Vy and x¯=y¯=ℂx,y=0, then(31)V˜x=nn+1Vx+nn+12xn+12,V˜y=nn+1Vy+nn+12yn+12,ℂ˜x,y=nn+12xn+1yn+1.Proof.
We setx˜=1/n+1∑i=1n+1xi and x˜=1/n+1∑i=1n+1yi. Since x¯=y¯=0, then x˜=xn+1/n+1 and y˜=yn+1/n+1. On the one hand, since x¯=0, we have(32)∑i=1n+1xi−x˜2=∑i=1nxi2+xn+12−n+1x˜2=nVx+nn+1xn+12.
On the other hand, since∑i=1n+1xiyi=0, we have:(33)∑i=1n+1xi−x˜yi−y˜=∑i=1n+1xiyi−n+1x˜y˜=nn+1xn+1yn+1.
Letf˜θ be the function defined from ℳn+1 in the same way that fθ was defined from ℳn in (10). Then,(34)f˜θ=λ˜cosθ+δ˜sinθ,where(35)λ˜=V˜x2+V˜y2−2V˜xV˜y−4ℂ˜x,y2,δ˜=4ℂ˜x,yV˜x−V˜ysin4θ.Using the identities (31), we have(36)λ˜=n2n+14xn+14+xn+14−6xn+12yn+12,It follows that(1)
λ˜≠0 i.f.f Mn+1∉D1∪D2∪D3∪D4, where D1,…,D4 are the lines whose Cartesian equations are given by(37)D1:x=1+2yD2:x=1−2y,D3:x=2−1yD4:x=−1−2y.(2)
δ˜≠0 i.f.f Mn+1∉D5∪D6, where D5:x=y and D6:x=−y.
In summary, any pointMn+1=x¯+xn+1,y¯+yn+1t defined as a convex combination of M1,…,Mn, such that xn+1yn+1≠0 overcomes the indeterminacy problem posed by Case 6. However, the resulting RANGE-MBR ℳn depends on the values of xn+1 and yn+1. We tested this technique on a set ℳn composed of vertices of a regular n-sided polygon, and we observed that the choice(38)Mn+1=12Mj+Mnodj+1,4+1.
We allow our algorithm to reach MBRℳn whatever the value of n and j=1,…,n. The generalization of the technique applied to the vertices of a regular polygon requires the calculation of CH ℳn, and the determination of the midpoint, Mn+1, of any two consecutive vertices of CH ℳn, such that the product of the coordinates of Mn+1 with respect to ℬG=G,i,j, is different from 0.


### 5.2. Annotate the DOTA Dataset Using Range-MBR

To adapt our annotation method to the output format required by the DOTA dataset, it suffices to ask the annotator that the first click points to the object’s head, and to add a binary variableT equals to 1 if we can differentiate the head of the object from its tail, and zero otherwise. When we pass the set ℳn to the RANGE-MBR algorithm, we save the coordinates of the first point M1. Next, we determine the rectangle ℝ=R1,R2,R3,R4=RANGE−MBRℳn.(1)
If the binary variableT equals one, then we determine the vertex Rj of ℝ that is closest to M1, and we permute the vertices of ℝ clockwise so that Rj occupies the first position in this permutation.(2)
If the binary variableT equals zero, then we determine the top left vertex Rj of ℝ, and we permute the vertices of ℝ clockwise so that Rj occupies the first position in this permutation.


## 5.1. The Range-MBR Algorithm

Letℬ=O,i,j be a Cartesian frame of the two-dimensional affine plane. All angles we refer to here are measured counterclockwise from the positive x-axis. Let Δ be the line passing through O and making an angle θ with the axis O,i. Let Δ⊥ be perpendicular to Δ and passing through O. Let P1 and Q1 (P2 and Q2, respectively) be the extreme points of the orthogonal projection of ℳn on Δ (Δ⊥, respectively). Let A=A1,A2,A3,A4 be the minimum bounding rectangle having an edge collinear with Δ. Then, A1,…,A4 are the intersection points of the two parallel lines to Δ⊥ and passing through P1 and Q1, respectively, with the two parallel lines to Δ and passing through P2 and Q2 respectively. The area of A is given by the product of lengths of the line segments P1,Q1 and P2,Q2. From now on, the MBR A enclosing ℳn and having an edge collinear with the direction making an angle θ from the positive x-axis will be denoted by MBRℳn,θ.Letu=cosθ,sinθt, and v=−sinθ,cosθt ) be two unit direction vector of Δ and Δ⊥, respectively. Then, ℬ=O,i,j and ℬ′=O,u,v are two Cartesian frames of the two-dimensional affine plane. For all i=1,…,n, we denote by xi,yit (si,tit, respectively) the coordinates of Mi with respect to the frame ℬ (ℬ′, respectively). Let Rθ be the rotation matrix of angle θ, and then xi,yit=Rθsi,tit, where ut is the transpose of u.LetX be a random variable with mean μ and standard deviation σ. Let x1:n=x1,…,xn be n observations on the variable X. Let x1≤…≤xn be the order statistics of x1:n. We define the range of x1:n by Rangex1:n=xn−x1. Therefore, the lengths of P1,Q1 and P2,Q2 are given by:(3)P1Q1=Ranges1,…,sn=sn−s1,P2Q2=Ranget1,…,tn=tn−t1.We denote byσ^n any estimation of σ obtained from x1:n. On the basis of numerous works carried out on the estimation of the standard deviation from the sample range ([38–43]), we can assume that there is a real constant αX,n such that(4)σ^n=Rangex1:nαX,n.Besides, it is well known that(5)Varx1:n=1n∑i=1nxi−x¯,which is an estimate of σ2, where x¯=1/n∑i=1nxi. It follows that there is a real constant αX,n such that:(6)Rangex1:n2≈αX,n2Varx1:n.We assume that thex,y coordinates of the set of points ℳn are n observations of two random variables X and Y. Since the AreaA=P1Q1⋅P2Q2, then combining equations (6) and (3) gives an approximation A^n2θ of AreaA, satisfying the following relation:(7)A^n2θ=αS,n2αT,n2Vars1:nVart1:n,where S,Tt=RθtX,Yt. To alleviate notions, we will also use Vx and ℂx,y to designate Varx1:n and Covx1:n,y1:n. Since xi,yit=Rθsi,tit, we obtain(8)Vs=cos2θVx+sin2θVy+sin2θℂx,y,Vt=sin2θVx+cos2θVy−sin2θℂx,y.Using (8) and some trigonometric identities, we prove that(9)8VsVt=K−fθ,where K=Vx2+Vy2+6VxVy−4ℂx,y2 and(10)fθ=Vx2+Vy2−2VxVy−4ℂx,y2cos4θ+4ℂx,yVx−Vysin4θ.Combining equations (7), (9), and (10) gives(11)A^n2θ=αS,n2αT,n28K−fθ.Thus, the area of MBR ℳn,θ is approximately equal to(12)αS,n2αT,n28K−fθ.Therefore, we propose to approximate MBR ℳn by MBR ℳn,θ∗ such that:(13)θ∗=argminθ∈−π/2,π/2A^n2θ=argmaxθ∈−π/2,π/2fθ.The first derivative off with respect to θ is given by:(14)f˙4θ=−4λsin4θ+4δcos4θ.where(15)λ=Vx2−Vy2−4ℂx,y2,δ=4ℂx,yVx−Vy.The functionf has a unique critical point θ∗ such that(16)tan4θ∗=δλ=4ℂx,yVx−VyVx2−Vy2−4ℂx,y2.Lemma 1.
The second derivative off at the critical point θ∗ has the same sign as −λ.Proof.
The second derivative off with respect to θ is given by:(17)f¨θ=−16λcos4θ+δsin4θ.
Multiplying both sides of the relation (17) by cos4θ yields(18)cos4θf¨θ=−16λcos24θ+δsin4θcos4θ,Multiplying both sides of the relation (14) by sin4θ yields(19)sin4θf˙θ=−4λsin24θ+4δsin4θcos4θ.
Using relations (19) and (18) with θ=θ∗ (i.e., f˙θ∗=0), we obtain:(20)4δcos4θ∗sin4θ∗=4λsin24θ∗,cos4θ∗f¨θ∗=−16λ.Therefore, f¨θ∗ has the same sign as −λcos4θ∗. Since 4θ∗=arctanδ/λ∈−π/2,π/2, then cos4θ∗>0 what ever the set ℳn may be. Thus, f¨θ∗ has the same sign as −λ.
Therefore, the determination ofθ∗ goes through six cases:Case 1: ifλ>0, then θ∗=1/4arctanδ/λ.Case 2: ifλ<0 and Vx≠Vy, then θ∗ is determined through the eigen decomposition of the empirical covariance matrix of ℳn. This case is discussed below.Case 3: ifλ<0 and Vx=Vy, then θ∗=π/4.Case 4: ifλ=0 and ℂxVx−Vy>0, then θ∗=π/8.Case 5: ifλ=0 and ℂxVx−Vy>0, then θ∗=π/8.Case 6: ifλ=0 and ℂxVx−Vy>0, then it is equivalent to Vx=Vy and ℂx=0. This case is discussed below.


### 5.1.1. Illustrative Example of Case 6

It is difficult to illustrate all the scenarios, which fall into Case 6. The special case of regular polygons is the one that the annotator may encounter when annotating regular objects such as road signs, buildings, and human faces. Moreover, we have pointed out this case to warn the user to pay attention to regularly shaped objects when using our annotation method.Proposition 1.
If the elements ofℳn are the vertices of a regular n-sided polygon, then Vx=Vy and ℂx,y=0.Proof.
In the general case, the vertices of a regular polygon are uniformly distributed over a circle with radiusr and center G equal to the barycenter of ℳn. Thus, without loss of generality, we can assume that r=1, G=0,0t, and the kth vertex of ℳn is(21)Mk=cos2πk−1n,sin2πk−1nt.
Consider the complex sequencezk0≤k≤n−1, where z=exp2π/ni and i is the imaginary unit. Then,(22)∑k=0n−1zk=nx¯+y¯i.
Since∑k=0n−1zk=1−zn/1−z=0, then x¯=y¯=0, and(23)ℂx,y=1n∑k=1nxkyk,Vx=1n∑k=1nxk2,Vy=1n∑k=1nyk2.
Sincecos2x=2cos2x−1=1−2sin2x, then(24)Vx=12+12n∑k=0n−1cos4πkn,Vy=12−12n∑k=0n−1cos4πkn.
Besides,∑k=0n−1cos4πk/n is the real part of(25)∑k=0n−1z2k=1−z2n1−z2=0.
Thus,Vx=Vy=1/2. Moreover, using 2cosxsinx=sin2x, we deduce that(26)ℂx,y=12n∑k=0n−1sin4πkn.
Since∑k=0n−1sin4πk/n is the imaginary part of(27)∑k=0n−1z2k=1−z2n1−z2=0,then ℂx,y=0.
Note that in the case where the elements ofℳn are the vertices of a regular n-sided polygon, problem 5.1 has exactly n different solutions MBRiℳn, i=1,…,n. For all i=1,…,n−1, MBRiℳn is the image of MBR0ℳn by the rotation of angle θi=2i/nπ.


### 5.1.2. Handling of the Exceptional Cases 2 and 6

Cases 2 and 6 are indeterminate cases for which the minimum of the objective functionfθ does not exist. This is why we have thought of a trick to get out of the indeterminacy of each case, by returning to the initial definition of the solution.(i)
For Case 2, the application of an affine isometry to the set of pointsℳn makes it possible to migrate to another case for which the angle θ is well determined. We then obtain the solution of the initial problem by applying the inverse isometry to the solution of the transformed problem, since isometry preserves the areas.(ii)
For Case 6, the use of an extra pointMn+1 belonging to the convex hull of the set ℳn, allows to migrate to another case for which the angle θ is well determined. Another alternative consists in asking the user to click on a point of the object’s outline until we get out this state.Case 2:λ=Vx−Vy2−4ℂx,y2 is negative because of ℂx,y2. To get rid of ℂx,y2, we have just to follow the same reasoning on a set of points(28)ℳn′=Mi′=xi′,yi′t∈ℝ2;i=1,…,n,whose coordinates x1:n′=x1,…,xn′ and y1:n′=y1,…,yn′ are uncorrelated. Let(29)Γ=1n∑i=1nMi−M¯Mi−M¯t,be the covariance matrix of the elements of ℳn, where M¯=x¯,y¯t. Let Γ=UΔUt be an eigen decomposition of Γ, where U∈O2ℝ (the set of 2-orthogonal matrices), and Δ=diagδ1,δ2. For all i=1,…,n, set Mi′=UtMi and ℳn′=Mi′1≤n≤n. Then,t(30)Γ′=1n∑i=1nMi′−M′¯Mi′−M′¯t=Δ,where M′¯=UtM¯. Since U∈O2ℝ, then the linear map defined by LM=UtM preserves the norm and the dot product. Thus, AreaMBRℳn=AreaMBRℳn′ and MBR ℳn is the image of MBR ℳn′ under the map L.Proposition 2.
If the vectorsx1:n and y1:n are uncorrelated ℂx,y=0 and have different variances Vx≠Vy, then A^n2θ has a unique minimum at the angle θ=0.Proof.
Sincex1:n and y1:n are uncorrelated, then ℂx,y=0, and λ=Vx−Vy2 and δ=0. According to equation (16), the function f has a unique critical point θ∗=0. Using Lemma 1, fθ is the maximum of fθ.Case 6. To get out of the indeterminacy of Case 6, we propose to add to the setℳn an artificial point Mn+1 located in the convex hull of ℳn so that the empirical covariance matrix of the new set ℳn+1=ℳn∪Mn+1 is different from a scalar matrix. We assume that xn+1,yn+1t are the Cartesian coordinates of Mn+1 with respect to ℬG=G,i,j, where G=x¯,y¯t is the barycenter of ℳn. Without any loss of generality, we assume that x1:n+1 (y1:n+1, respectively) is the vector of the x-coordinates (y-coordinates, respectively) of the points of ℳn+1 with respect to ℬG=G,i,j. We denote by V˜x=Varx1:n+1 and V˜y=Vary1:n+1. Lemma 2 gives the relation between Vx,Vy,ℂx,y and V˜x,V˜y,ℂ˜x,y, respectively.Lemma 2.
IfVx=Vy and x¯=y¯=ℂx,y=0, then(31)V˜x=nn+1Vx+nn+12xn+12,V˜y=nn+1Vy+nn+12yn+12,ℂ˜x,y=nn+12xn+1yn+1.Proof.
We setx˜=1/n+1∑i=1n+1xi and x˜=1/n+1∑i=1n+1yi. Since x¯=y¯=0, then x˜=xn+1/n+1 and y˜=yn+1/n+1. On the one hand, since x¯=0, we have(32)∑i=1n+1xi−x˜2=∑i=1nxi2+xn+12−n+1x˜2=nVx+nn+1xn+12.
On the other hand, since∑i=1n+1xiyi=0, we have:(33)∑i=1n+1xi−x˜yi−y˜=∑i=1n+1xiyi−n+1x˜y˜=nn+1xn+1yn+1.
Letf˜θ be the function defined from ℳn+1 in the same way that fθ was defined from ℳn in (10). Then,(34)f˜θ=λ˜cosθ+δ˜sinθ,where(35)λ˜=V˜x2+V˜y2−2V˜xV˜y−4ℂ˜x,y2,δ˜=4ℂ˜x,yV˜x−V˜ysin4θ.Using the identities (31), we have(36)λ˜=n2n+14xn+14+xn+14−6xn+12yn+12,It follows that(1)
λ˜≠0 i.f.f Mn+1∉D1∪D2∪D3∪D4, where D1,…,D4 are the lines whose Cartesian equations are given by(37)D1:x=1+2yD2:x=1−2y,D3:x=2−1yD4:x=−1−2y.(2)
δ˜≠0 i.f.f Mn+1∉D5∪D6, where D5:x=y and D6:x=−y.
In summary, any pointMn+1=x¯+xn+1,y¯+yn+1t defined as a convex combination of M1,…,Mn, such that xn+1yn+1≠0 overcomes the indeterminacy problem posed by Case 6. However, the resulting RANGE-MBR ℳn depends on the values of xn+1 and yn+1. We tested this technique on a set ℳn composed of vertices of a regular n-sided polygon, and we observed that the choice(38)Mn+1=12Mj+Mnodj+1,4+1.
We allow our algorithm to reach MBRℳn whatever the value of n and j=1,…,n. The generalization of the technique applied to the vertices of a regular polygon requires the calculation of CH ℳn, and the determination of the midpoint, Mn+1, of any two consecutive vertices of CH ℳn, such that the product of the coordinates of Mn+1 with respect to ℬG=G,i,j, is different from 0.


## 5.1.1. Illustrative Example of Case 6

It is difficult to illustrate all the scenarios, which fall into Case 6. The special case of regular polygons is the one that the annotator may encounter when annotating regular objects such as road signs, buildings, and human faces. Moreover, we have pointed out this case to warn the user to pay attention to regularly shaped objects when using our annotation method.Proposition 1.
If the elements ofℳn are the vertices of a regular n-sided polygon, then Vx=Vy and ℂx,y=0.Proof.
In the general case, the vertices of a regular polygon are uniformly distributed over a circle with radiusr and center G equal to the barycenter of ℳn. Thus, without loss of generality, we can assume that r=1, G=0,0t, and the kth vertex of ℳn is(21)Mk=cos2πk−1n,sin2πk−1nt.
Consider the complex sequencezk0≤k≤n−1, where z=exp2π/ni and i is the imaginary unit. Then,(22)∑k=0n−1zk=nx¯+y¯i.
Since∑k=0n−1zk=1−zn/1−z=0, then x¯=y¯=0, and(23)ℂx,y=1n∑k=1nxkyk,Vx=1n∑k=1nxk2,Vy=1n∑k=1nyk2.
Sincecos2x=2cos2x−1=1−2sin2x, then(24)Vx=12+12n∑k=0n−1cos4πkn,Vy=12−12n∑k=0n−1cos4πkn.
Besides,∑k=0n−1cos4πk/n is the real part of(25)∑k=0n−1z2k=1−z2n1−z2=0.
Thus,Vx=Vy=1/2. Moreover, using 2cosxsinx=sin2x, we deduce that(26)ℂx,y=12n∑k=0n−1sin4πkn.
Since∑k=0n−1sin4πk/n is the imaginary part of(27)∑k=0n−1z2k=1−z2n1−z2=0,then ℂx,y=0.
Note that in the case where the elements ofℳn are the vertices of a regular n-sided polygon, problem 5.1 has exactly n different solutions MBRiℳn, i=1,…,n. For all i=1,…,n−1, MBRiℳn is the image of MBR0ℳn by the rotation of angle θi=2i/nπ.


## 5.1.2. Handling of the Exceptional Cases 2 and 6

Cases 2 and 6 are indeterminate cases for which the minimum of the objective functionfθ does not exist. This is why we have thought of a trick to get out of the indeterminacy of each case, by returning to the initial definition of the solution.(i)
For Case 2, the application of an affine isometry to the set of pointsℳn makes it possible to migrate to another case for which the angle θ is well determined. We then obtain the solution of the initial problem by applying the inverse isometry to the solution of the transformed problem, since isometry preserves the areas.(ii)
For Case 6, the use of an extra pointMn+1 belonging to the convex hull of the set ℳn, allows to migrate to another case for which the angle θ is well determined. Another alternative consists in asking the user to click on a point of the object’s outline until we get out this state.Case 2:λ=Vx−Vy2−4ℂx,y2 is negative because of ℂx,y2. To get rid of ℂx,y2, we have just to follow the same reasoning on a set of points(28)ℳn′=Mi′=xi′,yi′t∈ℝ2;i=1,…,n,whose coordinates x1:n′=x1,…,xn′ and y1:n′=y1,…,yn′ are uncorrelated. Let(29)Γ=1n∑i=1nMi−M¯Mi−M¯t,be the covariance matrix of the elements of ℳn, where M¯=x¯,y¯t. Let Γ=UΔUt be an eigen decomposition of Γ, where U∈O2ℝ (the set of 2-orthogonal matrices), and Δ=diagδ1,δ2. For all i=1,…,n, set Mi′=UtMi and ℳn′=Mi′1≤n≤n. Then,t(30)Γ′=1n∑i=1nMi′−M′¯Mi′−M′¯t=Δ,where M′¯=UtM¯. Since U∈O2ℝ, then the linear map defined by LM=UtM preserves the norm and the dot product. Thus, AreaMBRℳn=AreaMBRℳn′ and MBR ℳn is the image of MBR ℳn′ under the map L.Proposition 2.
If the vectorsx1:n and y1:n are uncorrelated ℂx,y=0 and have different variances Vx≠Vy, then A^n2θ has a unique minimum at the angle θ=0.Proof.
Sincex1:n and y1:n are uncorrelated, then ℂx,y=0, and λ=Vx−Vy2 and δ=0. According to equation (16), the function f has a unique critical point θ∗=0. Using Lemma 1, fθ is the maximum of fθ.Case 6. To get out of the indeterminacy of Case 6, we propose to add to the setℳn an artificial point Mn+1 located in the convex hull of ℳn so that the empirical covariance matrix of the new set ℳn+1=ℳn∪Mn+1 is different from a scalar matrix. We assume that xn+1,yn+1t are the Cartesian coordinates of Mn+1 with respect to ℬG=G,i,j, where G=x¯,y¯t is the barycenter of ℳn. Without any loss of generality, we assume that x1:n+1 (y1:n+1, respectively) is the vector of the x-coordinates (y-coordinates, respectively) of the points of ℳn+1 with respect to ℬG=G,i,j. We denote by V˜x=Varx1:n+1 and V˜y=Vary1:n+1. Lemma 2 gives the relation between Vx,Vy,ℂx,y and V˜x,V˜y,ℂ˜x,y, respectively.Lemma 2.
IfVx=Vy and x¯=y¯=ℂx,y=0, then(31)V˜x=nn+1Vx+nn+12xn+12,V˜y=nn+1Vy+nn+12yn+12,ℂ˜x,y=nn+12xn+1yn+1.Proof.
We setx˜=1/n+1∑i=1n+1xi and x˜=1/n+1∑i=1n+1yi. Since x¯=y¯=0, then x˜=xn+1/n+1 and y˜=yn+1/n+1. On the one hand, since x¯=0, we have(32)∑i=1n+1xi−x˜2=∑i=1nxi2+xn+12−n+1x˜2=nVx+nn+1xn+12.
On the other hand, since∑i=1n+1xiyi=0, we have:(33)∑i=1n+1xi−x˜yi−y˜=∑i=1n+1xiyi−n+1x˜y˜=nn+1xn+1yn+1.
Letf˜θ be the function defined from ℳn+1 in the same way that fθ was defined from ℳn in (10). Then,(34)f˜θ=λ˜cosθ+δ˜sinθ,where(35)λ˜=V˜x2+V˜y2−2V˜xV˜y−4ℂ˜x,y2,δ˜=4ℂ˜x,yV˜x−V˜ysin4θ.Using the identities (31), we have(36)λ˜=n2n+14xn+14+xn+14−6xn+12yn+12,It follows that(1)
λ˜≠0 i.f.f Mn+1∉D1∪D2∪D3∪D4, where D1,…,D4 are the lines whose Cartesian equations are given by(37)D1:x=1+2yD2:x=1−2y,D3:x=2−1yD4:x=−1−2y.(2)
δ˜≠0 i.f.f Mn+1∉D5∪D6, where D5:x=y and D6:x=−y.
In summary, any pointMn+1=x¯+xn+1,y¯+yn+1t defined as a convex combination of M1,…,Mn, such that xn+1yn+1≠0 overcomes the indeterminacy problem posed by Case 6. However, the resulting RANGE-MBR ℳn depends on the values of xn+1 and yn+1. We tested this technique on a set ℳn composed of vertices of a regular n-sided polygon, and we observed that the choice(38)Mn+1=12Mj+Mnodj+1,4+1.
We allow our algorithm to reach MBRℳn whatever the value of n and j=1,…,n. The generalization of the technique applied to the vertices of a regular polygon requires the calculation of CH ℳn, and the determination of the midpoint, Mn+1, of any two consecutive vertices of CH ℳn, such that the product of the coordinates of Mn+1 with respect to ℬG=G,i,j, is different from 0.


## 5.2. Annotate the DOTA Dataset Using Range-MBR

To adapt our annotation method to the output format required by the DOTA dataset, it suffices to ask the annotator that the first click points to the object’s head, and to add a binary variableT equals to 1 if we can differentiate the head of the object from its tail, and zero otherwise. When we pass the set ℳn to the RANGE-MBR algorithm, we save the coordinates of the first point M1. Next, we determine the rectangle ℝ=R1,R2,R3,R4=RANGE−MBRℳn.(1)
If the binary variableT equals one, then we determine the vertex Rj of ℝ that is closest to M1, and we permute the vertices of ℝ clockwise so that Rj occupies the first position in this permutation.(2)
If the binary variableT equals zero, then we determine the top left vertex Rj of ℝ, and we permute the vertices of ℝ clockwise so that Rj occupies the first position in this permutation.


## 6. Robust Semi-Automatic Annotation

In this section, we provide a new approach for building object detection datasets based on both MBR algorithm and threshold angles. This method is semi-automatic because it consists of a manual step followed by a computer-assisted step. In addition, this method is robust because the bounding rectangle generated by our algorithm is insensitive to the dexterity of the annotator.(i)
The problem of MBR was dealt with in Section5. If the user needs an optimal annotation in the sense given by Definition 2, then he calls the RC-MBR algorithm. Otherwise, he calls the RANGE-MBR algorithm for quasi-optimal annotation. However, optimality and complexity are inversely proportional.(ii)
By default, the threshold angle is equal to zero. It can also be adjusted by experts in object detection, or it can be defined experimentally as the largest angle between the ground truth bounding box and the positivex-axis that gives no significant difference between the performance of horizontal and oriented detectors when tested on oriented objects. The experimental determination of the threshold angle requires horizontal and oriented object detectors, as well as the already existing oriented object datasets.


### 6.1. Properties of the Robust Semi-Automatic Annotation Method

By construction, the robust semi-automatic annotation method ensures the following properties:(1)
The bounding rectangle generated by our approach is quasi-optimal in the sense that it covers the whole object, and its area is close to the area of the MBR enclosing the object.(2)
The angle of the rectangle is determined by an algorithm based on some relevant points collected on the contour of the object.(3)
The bounding rectangle is insensitive to annotators provided all relevant points on the object have been selected.(4)
The determination of the bounding rectangle requiresOn elementary operations, where n is the number of relevant points.(5)
It allows the user to build simultaneously, from an image bank, two databases: one for horizontal objects and another for oriented objects.In summary, the robust semi-automatic annotation provides a simple solution to all the drawbacks mentioned in paragraph III, which are inherent in the old annotation methods.Let:(i)
θ0 be a threshold angle fixed by the user (by default, θ0=0),(ii)
ℳn be the set of relevant points selected on the contour of the object,(iii)
H-MBRℳn be the horizontal minimum bounding rectangle enclosing ℳn,(iv)
O-MBRℳn be the minimum bounding rectangle enclosing ℳn,(v)
θ be the angle of O-MBR ℳn,then, the Algorithm 1, and the flowchart shown in Figure4 summarize the stages of construction of horizontal and oriented datasets, from a large-scale image bank.Figure 4
Our approach consists in choosing between O-MBRℳn and H-MBR ℳn). If the angle of O-MBR ℳn is less than or equal to a threshold angle, then we annotate the object using H-MBR ℳn instead of O-MBR ℳn.Algorithm 1: Robust semi-automatic annotation
Input: An image; threshold angle; HOD and OOD datasetsOutput: Annotated image assigned to HOD or OOD(1)
for (each object in the image) do(2)
Determine the class of the object(3)
Ask the annotator to click on the most relevant pointsℳn of the object as defined in Definition 1(4)
Determine the RANGE-MBRA=A1,A2,A3,A4 enclosing ℳn as described in Section A(5)
Setα the angle between the positive x-axis and A1A2⟶(6)
ifα>threshold angle then(7)
Assign (image, object,A, class) to the OOD dataset(8)
else(9)
Determine the horizontal MBRA=A1,A2,A3,A4 enclosing the relevant points, as shown in Figure 5, by setting θ=0(10)
Assign (image, object,A, class) to the HOD dataset(11)
end if(12)
end for


## 6.1. Properties of the Robust Semi-Automatic Annotation Method

By construction, the robust semi-automatic annotation method ensures the following properties:(1)
The bounding rectangle generated by our approach is quasi-optimal in the sense that it covers the whole object, and its area is close to the area of the MBR enclosing the object.(2)
The angle of the rectangle is determined by an algorithm based on some relevant points collected on the contour of the object.(3)
The bounding rectangle is insensitive to annotators provided all relevant points on the object have been selected.(4)
The determination of the bounding rectangle requiresOn elementary operations, where n is the number of relevant points.(5)
It allows the user to build simultaneously, from an image bank, two databases: one for horizontal objects and another for oriented objects.In summary, the robust semi-automatic annotation provides a simple solution to all the drawbacks mentioned in paragraph III, which are inherent in the old annotation methods.Let:(i)
θ0 be a threshold angle fixed by the user (by default, θ0=0),(ii)
ℳn be the set of relevant points selected on the contour of the object,(iii)
H-MBRℳn be the horizontal minimum bounding rectangle enclosing ℳn,(iv)
O-MBRℳn be the minimum bounding rectangle enclosing ℳn,(v)
θ be the angle of O-MBR ℳn,then, the Algorithm 1, and the flowchart shown in Figure4 summarize the stages of construction of horizontal and oriented datasets, from a large-scale image bank.Figure 4
Our approach consists in choosing between O-MBRℳn and H-MBR ℳn). If the angle of O-MBR ℳn is less than or equal to a threshold angle, then we annotate the object using H-MBR ℳn instead of O-MBR ℳn.Algorithm 1: Robust semi-automatic annotation
Input: An image; threshold angle; HOD and OOD datasetsOutput: Annotated image assigned to HOD or OOD(1)
for (each object in the image) do(2)
Determine the class of the object(3)
Ask the annotator to click on the most relevant pointsℳn of the object as defined in Definition 1(4)
Determine the RANGE-MBRA=A1,A2,A3,A4 enclosing ℳn as described in Section A(5)
Setα the angle between the positive x-axis and A1A2⟶(6)
ifα>threshold angle then(7)
Assign (image, object,A, class) to the OOD dataset(8)
else(9)
Determine the horizontal MBRA=A1,A2,A3,A4 enclosing the relevant points, as shown in Figure 5, by setting θ=0(10)
Assign (image, object,A, class) to the HOD dataset(11)
end if(12)
end for


## 7. Experimental Study

This experimental study was carried out exclusively with the Matlab R2007b software. We implemented the RC-MBR, PCA-MBR, and RANGE-MBR algorithms in MATLAB language, and we wrote a script (see the Appendix), which(1)
reads the image then displays it(2)
ask the annotator to click on the most relevant points of the object (ℳn is a 2×n matrix)(3)
determine the rectangleA corresponding to RC-MBR ℳn(4)
determine the rectangleB corresponding to RANGE-MBR ℳn(5)
draw the two rectangles with the colors red and green, respectivelyFigure 5
Whenθ is fixed, the minimum bounding rectangle enclosing the blue polygon (object) is the rectangle A whose vertices A1,…,A4 are the intersection points of the two parallel lines to Δ⊥ and passing through P1 and Q1, respectively, with the two parallel lines to Δ and passing through P2 and Q2, respectively. A is the rectangle whose edges pass through the red dotted segments.The images used in experiments B,…,D are free of rights and collected on the net. Moreover, the optimality criterion of an annotation is given in Definition2.Definition 2.
(optimal annotation) A rectangleA=A1,…,A4 enclosing an object is said to be optimal, if it fulfills the conditions (i) and (ii):(i)
the rectangleA covers the whole object,(ii)
the area ofA is minimal.


### 7.1. Experiment 1

This experiment consists of studying the optimality condition (ii) of the RANGE-MBR algorithm. Equation (28) describes how to generate the coordinates of the vertices Mn=xk,yk;k=1,…,n of a random n-sided polygon where each rand is call of a generator of uniform random numbers on the interval 0,1. The parameter vy, called the factor of dilation, controls the aspect ratio of the polygon as shown in Figure 6. The more vy is greater than 1, the more the polygon is dilated in the direction of the y-axis. Note that such a polygon is not necessarily convex as shown in Figure 7. This is also the case for any polygon whose vertices are defined by the relevant points of an object.Figure 6
The original object is the regular blue colored heptagon. The black, red, and green polygons correspond to the dilation of the blue polygon by a factorvy=2,3,4, respectively, in the vertical direction.Figure 7
P1 and P2 are two random heptagons, generated according to Equation (28) with vy=4. P1 is concave, while P2 is convex.Since(1)
the optimal annotation criterion that we have chosen results in a rectangle which has a minimum area and which covers the maximum of visible parts of the object,(2)
RC-MBR is the fastest algorithm that determines the smallest rectangle enclosing a set of points,it seems natural to consider this algorithm as a reference in the comparative study that we carried out.(39)xk=1+randcos2πkn+2πnrand,yk=1+vyrandsin2πkn+2πnrand.For each value of the pairn,vy, we generate r=10000 random n-sided polygons. For each polygon ℳni, i=1,…,r, we determine the relative error ei, between the areas of RANGE-MBR ℳni and RC-MBR ℳni, as well as the CPU times t^i and ti, used by the algorithms RANGE-MBR and RC-MBR to compute RANGE-MBR ℳni and RC-MBR ℳni, respectively. Finally, we denote by e¯, t^¯, t¯, and Stde, the means and the standard deviation of the sequences ei1≤i≤r, t^i1≤i≤r, ti1≤i≤r, and ei1≤i≤r respectively.Figure8 and 9 represent e¯ and Stde versus n and vy for n∈4,…,20 and vy∈1,…,4. We have retained the ranges of values 4,20 for n and 1,4 for vy, because in our estimation, they are those which correspond most to reality. In practice, rare are objects that have more than 20 relevant points or less than 4 relevant points.Figure 8
Mean ofei1≤i≤r versus n and vy.Figure 9
Standard deviation ofei1≤i≤r versus n and vy.We deduce from Figures8 and 9 that:(1)
The more the polygon is dilated in one direction, the more the algorithm RANGE-MBR is accurate and precise(2)
The more vertices the polygon has, the more the algorithm RANGE-MBR is accurate and preciseWe ran other simulations with larger values ofn and vy, and we got the same previous conclusion. The parameter vy controls the dilation of the polygon in the vertical direction. In fact, we could choose any other direction, since the RANGE-MBR algorithm is not sensitive to the direction of expansion. On the other hand, it is sensitive to the number of vertices of the polygon and to its dilation.Out of the 680000 generated polygons, we do not encounter any case for whichVx=Vy and ℂx,y=0. In addition, the algorithm RANGE-MBR is 9 times faster than algorithm RC-MBR. The mean CPU times of RANGE-MBR and CR-MBR are both independent of n and vy. It is about 1.38×10−4 seconds for the algorithm RANGE-MBR, and 1.20×10−3 seconds for the algorithm RC-MBR. Since the complexity of the algorithm RANGE-MBR is On, and that of the algorithm RC-MBR is Onlnn, then the difference in CPU time, for each algorithm, is only observed if n is large enough. Based on the response time per click given in [44] and considering the mean CPU time of the RANGE-MBR algorithm, we can state that determining a bounding rectangle requires 2.5+1.5n−1 seconds, where n is the number of relevant points collected on the contour of the image.


### 7.2. Experiment 2

We made a comparison between RANGE-MBR and PCA-MBR based on sets of vertices of regularn-sided polygons, with n=4,…,20. We observe that the relative error of the algorithm RANGE-MBR is always equal to 0, while that of the algorithm PCA-MBR is different from 0 for the values of n reported in Table 3. Although Case 6 does not contain only regular polygons, this experiment shows that the RANGE-MBR method achieves optimality on regular polygons, but for the other shapes (which go in Case 6), it offers a better solution than that obtained by PCA-MBR.Table 3
Relative errore of PCA-MBR on regular n-sided polygon.
n46891214151620100e1006.617.20.80.71.30.34.02.5


### 7.3. Experiment 3

This experiment consists in studying the effect of the dilation factor on the performance of the RANGE-MBR algorithm. Figure10 represents a basic experiment. The relevant points ℳn are colored in yellow. We observe that RANG-MBR ℳn is close to RC-MBR ℳn. Although the bird on the left is smaller than the bird on the right, the relative error e equals 0.65% for the bird on the right, and 3.12% for the bird on the left. These scores are expected, since the bird on the right has a more elongated shape than the bird on the left, and RANGE-MBR is more effective on dilated objects.Figure 10
Illustration of the semi-automatic annotation using RC-MBR and RANGE-MBR algorithms.


### 7.4. Experiment 4

This experiment consists in confirming the conclusion obtained in the experiment D. Figure11 contains two mangoes. The one on the left is almost circular, while the one on the right is clearly elongated. The relevant points ℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn. The relative error e equals 6.93% for the left mango and 1.86% for the right mango. This real example agrees with the simulation results shown in Figure 8. The mango on the right is more dilated than the one on the left that is why the relative error for the circular mango is greater than relative error for the oval mango.Figure 11
The relevant pointsℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn.


### 7.5. Experiment 5

In order to verify the robustness of our annotation method with respect to the annotator, we asked a colleague to click on the relevant points of the two mangoes. Figure12 illustrates the result of this experiment. The relative error e equals 8.92% for the left mango, and 2.32% for the right mango. The relative errors reported in Figure 12 are larger than those reported in Figure 11. We explain this difference by the number of points used in each experiment: the more points we use, the more the RANGE-MBR algorithm reduces the relative error. This real example agrees with the simulation results shown in Figure 8.Figure 12
The relevant pointsℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn.


### 7.6. Experiment 6

This experiment consists in comparing our annotation method to the FBB method introduced in Section B. For this, we have chosen a random image from the TUT indoor dataset, and we have annotated the objects it contains with FBB, RC-MBR, and RANGE-MBR. Note that the FBB annotation uses blue rectangles, RC-MBR annotation uses green rectangles, RANGE-MBR annotation uses red rectangles, and the relevant points are marked in yellow.Based on Figure13 and Table 4, it can be seen that the annotation by the FBB method is not optimal. Indeed,(i)
For the upper extinguisher and the exit sign, condition (i) is violated(ii)
For the lower extinguisher, condition (ii) is violatedFigure 13
Annotation of an image with FBB, RANGE-MBR, and RC-MBR.Table 4
Areas of bounding rectangles in Figure13.
MethodObjectFBBRANGE-MBRRC-MBRUpper fire extinguisher722782958046Lower extinguisher217261991719844Exit sign490269276146In addition, the annotation by the RANGE-MBR method satisfies condition (i) and the relative error between the area of RANGE-MBR and RC-MBR is12% for the exit sign, 3% for the upper extinguisher, and 0.3% for the lower extinguisher. We can conclude that condition (ii) is almost satisfied by the RANGE-MBR method.(i)
The values of the relative error are in agreement with the simulation results presented in Figure8. Indeed, in terms of dilation, the lower extinguisher is the most dilated, followed by the upper extinguisher, then the exit sign.(ii)
The exit sign and the upper extinguisher have regular shapes, while the lower extinguisher has an irregular shape. We have already underlined in Section1 and that the RANGE-MBR method is sensitive to regular forms. This example then illustrates the situation of Case 6.For all these reasons, the annotation of the lower extinguisher by the RANGE-MBR method is the best.


### 7.7. Experiment 7

This experiment highlights the importance of the annotation method on the calculation of the IoU. Figure14 corresponds to image P1128 from the DOTA dataset. The objects of interest in these images are the airplanes. We use the BBAVectors detector [6] to generate the red prediction bounding boxes. Ground truth bounding boxes used in [6] are colored green. The blue rectangles correspond to the annotations of the airplanes by the RANGE-MBR method. For all i=1,2,3, we denote by IoUig (IoUib, respectively) the Intersection over Union between the green (blue, respectively) rectangle enclosing the airplane Ai and the corresponding red rectangle. The results of this experiment are reported in Table 5. The use of minimum ground truth rectangles best reflects the performance of an object detector. In view of the results of Table V, it is reasonable to rely on the results of the second row rather than those of the first row.Figure 14
RANGE-MBR allows to build quasi-minimum bounding rectangles.Table 5
IoU computation for the objects in Figure14.
Airplane123IoUig0.52300.51140.7252IoUib0.62220.61860.7087


## 7.1. Experiment 1

This experiment consists of studying the optimality condition (ii) of the RANGE-MBR algorithm. Equation (28) describes how to generate the coordinates of the vertices Mn=xk,yk;k=1,…,n of a random n-sided polygon where each rand is call of a generator of uniform random numbers on the interval 0,1. The parameter vy, called the factor of dilation, controls the aspect ratio of the polygon as shown in Figure 6. The more vy is greater than 1, the more the polygon is dilated in the direction of the y-axis. Note that such a polygon is not necessarily convex as shown in Figure 7. This is also the case for any polygon whose vertices are defined by the relevant points of an object.Figure 6
The original object is the regular blue colored heptagon. The black, red, and green polygons correspond to the dilation of the blue polygon by a factorvy=2,3,4, respectively, in the vertical direction.Figure 7
P1 and P2 are two random heptagons, generated according to Equation (28) with vy=4. P1 is concave, while P2 is convex.Since(1)
the optimal annotation criterion that we have chosen results in a rectangle which has a minimum area and which covers the maximum of visible parts of the object,(2)
RC-MBR is the fastest algorithm that determines the smallest rectangle enclosing a set of points,it seems natural to consider this algorithm as a reference in the comparative study that we carried out.(39)xk=1+randcos2πkn+2πnrand,yk=1+vyrandsin2πkn+2πnrand.For each value of the pairn,vy, we generate r=10000 random n-sided polygons. For each polygon ℳni, i=1,…,r, we determine the relative error ei, between the areas of RANGE-MBR ℳni and RC-MBR ℳni, as well as the CPU times t^i and ti, used by the algorithms RANGE-MBR and RC-MBR to compute RANGE-MBR ℳni and RC-MBR ℳni, respectively. Finally, we denote by e¯, t^¯, t¯, and Stde, the means and the standard deviation of the sequences ei1≤i≤r, t^i1≤i≤r, ti1≤i≤r, and ei1≤i≤r respectively.Figure8 and 9 represent e¯ and Stde versus n and vy for n∈4,…,20 and vy∈1,…,4. We have retained the ranges of values 4,20 for n and 1,4 for vy, because in our estimation, they are those which correspond most to reality. In practice, rare are objects that have more than 20 relevant points or less than 4 relevant points.Figure 8
Mean ofei1≤i≤r versus n and vy.Figure 9
Standard deviation ofei1≤i≤r versus n and vy.We deduce from Figures8 and 9 that:(1)
The more the polygon is dilated in one direction, the more the algorithm RANGE-MBR is accurate and precise(2)
The more vertices the polygon has, the more the algorithm RANGE-MBR is accurate and preciseWe ran other simulations with larger values ofn and vy, and we got the same previous conclusion. The parameter vy controls the dilation of the polygon in the vertical direction. In fact, we could choose any other direction, since the RANGE-MBR algorithm is not sensitive to the direction of expansion. On the other hand, it is sensitive to the number of vertices of the polygon and to its dilation.Out of the 680000 generated polygons, we do not encounter any case for whichVx=Vy and ℂx,y=0. In addition, the algorithm RANGE-MBR is 9 times faster than algorithm RC-MBR. The mean CPU times of RANGE-MBR and CR-MBR are both independent of n and vy. It is about 1.38×10−4 seconds for the algorithm RANGE-MBR, and 1.20×10−3 seconds for the algorithm RC-MBR. Since the complexity of the algorithm RANGE-MBR is On, and that of the algorithm RC-MBR is Onlnn, then the difference in CPU time, for each algorithm, is only observed if n is large enough. Based on the response time per click given in [44] and considering the mean CPU time of the RANGE-MBR algorithm, we can state that determining a bounding rectangle requires 2.5+1.5n−1 seconds, where n is the number of relevant points collected on the contour of the image.


## 7.2. Experiment 2

We made a comparison between RANGE-MBR and PCA-MBR based on sets of vertices of regularn-sided polygons, with n=4,…,20. We observe that the relative error of the algorithm RANGE-MBR is always equal to 0, while that of the algorithm PCA-MBR is different from 0 for the values of n reported in Table 3. Although Case 6 does not contain only regular polygons, this experiment shows that the RANGE-MBR method achieves optimality on regular polygons, but for the other shapes (which go in Case 6), it offers a better solution than that obtained by PCA-MBR.Table 3
Relative errore of PCA-MBR on regular n-sided polygon.
n46891214151620100e1006.617.20.80.71.30.34.02.5


## 7.3. Experiment 3

This experiment consists in studying the effect of the dilation factor on the performance of the RANGE-MBR algorithm. Figure10 represents a basic experiment. The relevant points ℳn are colored in yellow. We observe that RANG-MBR ℳn is close to RC-MBR ℳn. Although the bird on the left is smaller than the bird on the right, the relative error e equals 0.65% for the bird on the right, and 3.12% for the bird on the left. These scores are expected, since the bird on the right has a more elongated shape than the bird on the left, and RANGE-MBR is more effective on dilated objects.Figure 10
Illustration of the semi-automatic annotation using RC-MBR and RANGE-MBR algorithms.


## 7.4. Experiment 4

This experiment consists in confirming the conclusion obtained in the experiment D. Figure11 contains two mangoes. The one on the left is almost circular, while the one on the right is clearly elongated. The relevant points ℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn. The relative error e equals 6.93% for the left mango and 1.86% for the right mango. This real example agrees with the simulation results shown in Figure 8. The mango on the right is more dilated than the one on the left that is why the relative error for the circular mango is greater than relative error for the oval mango.Figure 11
The relevant pointsℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn.


## 7.5. Experiment 5

In order to verify the robustness of our annotation method with respect to the annotator, we asked a colleague to click on the relevant points of the two mangoes. Figure12 illustrates the result of this experiment. The relative error e equals 8.92% for the left mango, and 2.32% for the right mango. The relative errors reported in Figure 12 are larger than those reported in Figure 11. We explain this difference by the number of points used in each experiment: the more points we use, the more the RANGE-MBR algorithm reduces the relative error. This real example agrees with the simulation results shown in Figure 8.Figure 12
The relevant pointsℳn are colored in yellow. The red rectangle corresponds to RANG-MBR ℳn, while the green rectangle corresponds to RC-MBR ℳn.


## 7.6. Experiment 6

This experiment consists in comparing our annotation method to the FBB method introduced in Section B. For this, we have chosen a random image from the TUT indoor dataset, and we have annotated the objects it contains with FBB, RC-MBR, and RANGE-MBR. Note that the FBB annotation uses blue rectangles, RC-MBR annotation uses green rectangles, RANGE-MBR annotation uses red rectangles, and the relevant points are marked in yellow.Based on Figure13 and Table 4, it can be seen that the annotation by the FBB method is not optimal. Indeed,(i)
For the upper extinguisher and the exit sign, condition (i) is violated(ii)
For the lower extinguisher, condition (ii) is violatedFigure 13
Annotation of an image with FBB, RANGE-MBR, and RC-MBR.Table 4
Areas of bounding rectangles in Figure13.
MethodObjectFBBRANGE-MBRRC-MBRUpper fire extinguisher722782958046Lower extinguisher217261991719844Exit sign490269276146In addition, the annotation by the RANGE-MBR method satisfies condition (i) and the relative error between the area of RANGE-MBR and RC-MBR is12% for the exit sign, 3% for the upper extinguisher, and 0.3% for the lower extinguisher. We can conclude that condition (ii) is almost satisfied by the RANGE-MBR method.(i)
The values of the relative error are in agreement with the simulation results presented in Figure8. Indeed, in terms of dilation, the lower extinguisher is the most dilated, followed by the upper extinguisher, then the exit sign.(ii)
The exit sign and the upper extinguisher have regular shapes, while the lower extinguisher has an irregular shape. We have already underlined in Section1 and that the RANGE-MBR method is sensitive to regular forms. This example then illustrates the situation of Case 6.For all these reasons, the annotation of the lower extinguisher by the RANGE-MBR method is the best.


## 7.7. Experiment 7

This experiment highlights the importance of the annotation method on the calculation of the IoU. Figure14 corresponds to image P1128 from the DOTA dataset. The objects of interest in these images are the airplanes. We use the BBAVectors detector [6] to generate the red prediction bounding boxes. Ground truth bounding boxes used in [6] are colored green. The blue rectangles correspond to the annotations of the airplanes by the RANGE-MBR method. For all i=1,2,3, we denote by IoUig (IoUib, respectively) the Intersection over Union between the green (blue, respectively) rectangle enclosing the airplane Ai and the corresponding red rectangle. The results of this experiment are reported in Table 5. The use of minimum ground truth rectangles best reflects the performance of an object detector. In view of the results of Table V, it is reasonable to rely on the results of the second row rather than those of the first row.Figure 14
RANGE-MBR allows to build quasi-minimum bounding rectangles.Table 5
IoU computation for the objects in Figure14.
Airplane123IoUig0.52300.51140.7252IoUib0.62220.61860.7087


## 8. Conclusion

In this piece, we provide a novel approach that is both resilient and semi-automatic in nature for the annotation of objects. According to the results of the experimental research, we are able to assert that(1)
Robust semi-automatic annotation is quasi-optimal in the sense that Definition2 describes, and that its optimality increases with dilated objects, which is the case for the majority of the objects that appear on the images that were collected by the use of aerial photography.(2)
Robust semi-automatic annotation is quick and reliable in the sense that the bounding rectangle does not have any gaps, and is oblivious to the skill of the person doing the annotation.(3)
Robust semi-automatic annotation is simple to put into action and might be easily incorporated into platforms for annotating text.(4)
Robust semi-automatic annotation is sensitive to the annotation of items displaying symmetry, with respect to one or more directions. Given this scenario, it is not appropriate for the relevant points to follow the same symmetry in order for the created rectangle to be somewhat close to the ideal rectangle.Thqe critical angle, as described in Section6, would look somewhat like this: the emphasis on experimental research using large-scale collected data on horizontal and oriented object datasets, as well as detectors of state-of-the-art oriented objects. Once a good estimate of the threshold angle has been made, the robust semi-automatic annotation technique is the one that allows the simultaneous construction, from the same image library, of two different data sets: one for the elements horizontal and another for oriented objects.



---

*Source: 3001939-2022-08-23.xml*