LeetCode High frequency questions ： Image intersection and union ratio IoU Calculation method and hand tearing code

Tips ： This topic is a series LeetCode Of 150 High frequency questions , The written examination and interview questions you will encounter in the future , They are basically adapted from this topic
Internet giants have raised a large number of people in the company ACM The big guys of the competition , After dinner, I will design test questions , Then go to test the candidates , All you have to do is learn the basic tree structure and algorithm , And then get through Ren Du's two veins , In response to the treacherous interview questions of the big factory written examination ！
If you don't learn data structures and algorithms well , Do a good job tearing up the code , Exercise problem-solving ability , You may be in the written interview process , I can't even understand the topic ！ For example, Huawei , Bytes or something , Enough to make you unable to read the question

List of articles

• LeetCode High frequency questions ： Image intersection and union ratio IoU Calculation method and hand tearing code
• • @[TOC]( List of articles )
• subject
• One 、 Examine the subject
• This question often appears in the written examination interview of Internet manufacturers
• • What is iou？
  • Calculation ideas
  • • The situation of intersection
• summary

subject

Please tell me iou How does it work , Write iou The calculation method of

One 、 Examine the subject

Example ：

The subscript of the two matrices given to you is ：
rect1： top left corner x1,y1, The lower right corner x2,y2
rect2： top left corner a1,b1, The lower right corner a2,b2

This question often appears in the written examination interview of Internet manufacturers

A very simple idea

What is iou？

IoU, namely intersection over Union,
It's two rectangular boxes Intersection area With them Union area The ratio of the .
（ In fact, it is not necessarily a rectangular box , This is illustrated with a rectangular box ）

IoU It is also an indicator of algorithm performance , For example, it will be used in semantic segmentation IoU To measure the segmentation effect .
Illustrate with examples , As shown in the figure below :

The input for you is two arrays ：
rect1： top left corner x1,y1, The lower right corner x2,y2【 Namely 0123 Location 】
rect2： top left corner a1,b1, The lower right corner a2,b2【 Namely 0123 Location 】

Then the intersecting rectangular box is assumed to be X, Set the coordinates of the upper left corner as a point A, The coordinates of the lower right corner are set as points B;

Now we have to calculate IoU = area_X / (area_1 + area_2 - area_X)

understand ？

Calculation ideas

The situation of intersection

Intersection of two rectangles , As shown in the figure above , Just rectangle A and B The coordinates of point , The area of the intersecting area can be calculated , So as to obtain IoU.

AB The idea of coordinate calculation is as follows ：【 When you interview , Just draw a picture and you're done , It's simple 】

A The abscissa of be equal to The one with the larger abscissa in the upper left corner of the two rectangular boxes , namely Ax = max(x1, a1)
A The ordinate of be equal to The one with the larger vertical coordinate in the upper left corner of the two rectangular boxes , namely Ay = max(y1, b1)
B The abscissa of be equal to The smaller abscissa of the lower right corner of the two rectangular boxes , namely Bx = min(x2, a2)
B The ordinate of be equal to The one with the smaller vertical coordinate at the lower right corner of the two rectangular boxes , namely By = min(y2, b2)

obviously ,X The width of w=Bx-Ax,X What's your length h=By-Ay
If w perhaps h There is one less than 0, It means that there is no intersection between them ！！！

that iou It must be 0

So we filter out this condition
At last I got X The area of Sx=w*h

S1 Originally, it's good to ask ：S1=（x2-x1）×（y2-y1）
S2 Originally, it's good to ask ：S2=（a2-a1）×（b2-b1）
Just multiply the length by the width

The area of the Union , Need to be reduced x The area of , because S1+S2 Repeated addition x

so iou The three elements of are all out ,Sx,S1,S2 Have it all. , It's not a big problem to tear the code by hand
Encountered input is array rect1,rect2, It is suggested that you first convert the coordinates into your familiar xy and ab, So we can correspond

Code of hand tear ：

    // Calculation  IoU = area_X / (area_1 + area_2 - area_X)

    // The input for you is two arrays ：
    //rect1： top left corner x1,y1, The lower right corner x2,y2【 Namely 0123 Location 】
    //rect2： top left corner a1,b1, The lower right corner a2,b2【 Namely 0123 Location 】
    // Transform into a familiar form 

    public static double iou(int[] rect1, int[] rect2){
    
        if (rect1 == null || rect1.length == 0 ||
        rect2 == null || rect2.length == 0) return 0;

        int x1 = rect1[0];
        int y1 = rect1[1];
        int x2 = rect1[2];
        int y2 = rect1[3];//rect1
        int a1 = rect2[0];
        int b1 = rect2[1];
        int a2 = rect2[2];
        int b2 = rect2[3];//rect2

        // Just draw a picture on the draft paper 
        //S1//S2
        double S1 = (x2 - x1) * (y2 - y1);
        double S2 = (a2 - a1) * (b2 - b1);

        //iou
        int Ax = Math.max(x1, a1);// Upper left corner of intersection 
        int Ay = Math.max(y1, b1);
        int Bx = Math.min(x2, y2);// Lower right corner of intersection 
        int By = Math.min(y2, b2);
        int w = Bx - Ax;
        int h = By - Ay;// Intersection length and width 
        if (w <= 0 || h <= 0) return 0;// No intersection 

        double Sx = w * h;
        double ans = Sx / (S1 + S2 - Sx);
        System.out.println(" Intersection area ："+ Sx);

        return ans;
    }

Test one ：

    public static void test(){
    
        int[] rect1 = {
    2,1,4,3};
        int[] rect2 = {
    1,2,3,4};
        // Draw a picture and see , intersection A,B stay 
        System.out.println(iou(rect1, rect2));
    }

    public static void main(String[] args) {
    
        test();
    }

result ：

 Intersection area ：1.0
0.14285714285714285

very OK

So the written examination and interview are easy to say , Take a picture , Just draw it directly , Not reciting formulas , It's not about memorizing code

summary

Tips ： Important experience ：

1） Written examination and interview are easy to say , Take a picture , Just draw it directly , Not reciting formulas , It's not about memorizing code
2）IoU = area_X / (area_1 + area_2 - area_X)
3） Written examination AC, Space complexity can be ignored , But the interview should consider the optimal time complexity , Also consider the optimal spatial complexity .