about backward function about rotated_iou HOT 3 CLOSED

@orkunozturk Thank you for the question!
The function SortVertices return the INDICES of sorted vertices of the overlapping polygon of two rectangles in anti-clockwise order. Since the return value is discrete (integer number) but not continuous (float number), this function is not differentiable and thus has no backward pass. (functions which return indices are typically non-differentiable, like torch.argmax )

However, the calculation of IoU is still differentiable. The basic idea is to use shoelace formula to calculate the area of a convex polygon (the overlapping area of two rectangles). Given the unsorted coordinates of the polygon vertices and the sorted indices of the vertices, one can use the torch.gather to get the sorted vertices. Then, one can calculate the polygon area by applying the shoelace formula.

The process can be illustrated with this figure. The operations are orange. The tensors are blue. Note the sort operation is not differentiable, but the gradient from area to unsorted indices are guaranteed. Because gather is differentiable by definition and shoelace formula is basically some multiplication and addition.

from rotated_iou.

@orkunozturk
The paper was written in about 2018/2019. The torch.gather function might not exist at that time. So I think the authors might have implemented something similar by themselves.

There are two different types of max ops. The one type returns the max VALUE, and the other type return the INDEX (in this case, it's usually called argmax). The first type is differentiable, because the return value is continuous. The g-iou code uses the first type.

The built-in sorting function of Pytorch sorts the elements of a tensor just by value. But for shoelace formula, one needs to sort some points by their coordinates in anti-clockwise. Thus, the built-in function torch.sort doesn't solve the problem. Generally speaking, one key component of a sorting algo is the definition of compare. In the case of sorting points in anti-clockwise, one has to define the spatial relationship of points and how to compare them according to the coordinates. Usually, a sorting algo (like std::sort in C++ or sort in normal Python) allows users to define their own compare function. But the pytorch.sort doesn't provide this opportunity. So, instead of defining the costume data structure and compare function and then using template libraries (like what people always do with std::sort), I have to implement the sorting algo from scratch.

I think the code works as well (this code just likes good to me, but I've never tested it). Pytorch uses dynamic graph and thus allows user to use normal Python flow control with Pytorch-Ops. The advantage of this implementation its readability and simplicity. But its speed is probably lower than my implementation (still, just my assumption ...) because of the bad performance of Python. By the way, I chose to use CUDA just because I wanted to learn it 😆

from rotated_iou.

Thanks for the great answer!

The reason why i asked this question is in the paper it says (4.2.2 Backward) "Especially, there exist some custom operations (intersection of two edges and sorting the vertexes etc.) whose derivative functions have not been implemented in the existing deep learning frameworks" (I know you are not one of the authors of the paper and this is an unofficial implementation). For this reason i thought there should be an implementation for the backward function.

But there is one point that i don't understand. Standard iou loss also has non-differentaible ops like max and its implementations only using pytorch python code and there is no extra custom autograd/ cuda cpp code (like g-iou). Can't we just resort to sort method of pytorch to sort vertices and not implement custom autograd functions and/or cuda. In short, i am trying to understand why we are using custom autograd class and cuda to sort vertices.

In addition, i came accross this python pytorch code for the rotated iou calculation. Do you think can it be used for loss calculation?

from rotated_iou.