How can I detect the corner from 2D point cloud or Lidar scanned data?

Question

I want to measure the room surface area( in meter square) and want to find out the floor plan using 2D-Lidar. How can I achieve this?

In the picture, you can see lots of dots. Each dots represent angle and distance with respect to the Lidar position. Here is the data set:

angle: 0 distance: 942
angle: 0.62 distance: 3469
angle: 1.25 distance: 3350
angle: 2.5 distance: 3410
angle: 3.12 distance: 3404
angle: 3.75 distance: 3403
angle: 4.37 distance: 3464
angle: 5 distance: 3441
angle: 5.62 distance: 3445
angle: 6.25 distance: 3444
angle: 6.87 distance: 3455
angle: 7.5 distance: 3464
angle: 8.12 distance: 3464
angle: 8.75 distance: 3477
angle: 9.37 distance: 3470
angle: 10 distance: 3504
angle: 10.62 distance: 3505
angle: 11.25 distance: 3505
angle: 11.87 distance: 3516
angle: 12.5 distance: 3529
angle: 13.12 distance: 3541
angle: 13.75 distance: 3543
angle: 14.37 distance: 3552
angle: 15 distance: 3559
angle: 15.62 distance: 3565
angle: 16.25 distance: 3578
angle: 16.87 distance: 3591
angle: 17.5 distance: 3607
angle: 18.12 distance: 3624
angle: 18.75 distance: 3634
angle: 19.37 distance: 3630
angle: 20 distance: 3651
angle: 20.62 distance: 3673
angle: 21.25 distance: 3678
angle: 21.87 distance: 3697
angle: 22.5 distance: 3711
angle: 23.12 distance: 3726
angle: 23.75 distance: 3744
angle: 24.37 distance: 3765
angle: 25 distance: 3780
angle: 25.62 distance: 3796
angle: 26.25 distance: 3809
angle: 26.87 distance: 3830
angle: 27.5 distance: 3867
angle: 28.12 distance: 3881
angle: 28.75 distance: 3854
angle: 29.37 distance: 3751
angle: 30 distance: 3689
angle: 30.62 distance: 3637
angle: 31.25 distance: 3589
angle: 31.87 distance: 4029
angle: 37.5 distance: 3483
angle: 50 distance: 2734
angle: 53.75 distance: 1686
angle: 54.37 distance: 1656
angle: 55 distance: 1631
angle: 55.62 distance: 1621
angle: 56.25 distance: 1608
angle: 56.87 distance: 1600
angle: 57.5 distance: 1595
angle: 58.12 distance: 1598
angle: 58.75 distance: 1596
angle: 59.37 distance: 1604
angle: 60 distance: 1611
angle: 60.62 distance: 1622
angle: 61.25 distance: 1644
angle: 61.87 distance: 1673
angle: 65 distance: 2212
angle: 65.62 distance: 2221
angle: 66.25 distance: 1037
angle: 66.87 distance: 1299
angle: 67.5 distance: 2086
angle: 67.5 distance: 130
angle: 83.12 distance: 2002
angle: 83.75 distance: 1995
angle: 84.37 distance: 1993
angle: 85.62 distance: 2061
angle: 86.25 distance: 2043
angle: 86.87 distance: 2046
angle: 87.5 distance: 2040
angle: 89.37 distance: 2082
angle: 90 distance: 2713
angle: 90.62 distance: 2245
angle: 91.25 distance: 2046
angle: 93.75 distance: 2092
angle: 102.5 distance: 327
angle: 109.37 distance: 1349
angle: 110 distance: 4279
angle: 110.62 distance: 2177
angle: 111.25 distance: 2175
angle: 111.87 distance: 2136
angle: 113.12 distance: 2151
angle: 113.75 distance: 2170
angle: 114.37 distance: 2186
angle: 123.12 distance: 2066
angle: 123.75 distance: 2080
angle: 124.37 distance: 2087
angle: 125 distance: 2110
angle: 125.62 distance: 1778
angle: 126.25 distance: 1732
angle: 126.87 distance: 428
angle: 127.5 distance: 1650
angle: 128.12 distance: 1093
angle: 128.75 distance: 2206
angle: 129.37 distance: 2219
angle: 130 distance: 2243
angle: 130.62 distance: 2276
angle: 131.25 distance: 2317
angle: 131.87 distance: 2319
angle: 132.5 distance: 2305
angle: 133.12 distance: 2276
angle: 133.75 distance: 2253
angle: 135 distance: 2224
angle: 135.62 distance: 2202
angle: 136.25 distance: 2181
angle: 136.87 distance: 2156
angle: 137.5 distance: 2131
angle: 138.12 distance: 2108
angle: 138.75 distance: 2081
angle: 139.37 distance: 2068
angle: 140 distance: 2046
angle: 140.62 distance: 2028
angle: 141.25 distance: 1982
angle: 141.87 distance: 2001
angle: 142.5 distance: 1985
angle: 143.12 distance: 2030
angle: 152.5 distance: 1727
angle: 153.12 distance: 1728
angle: 153.75 distance: 1722
angle: 154.37 distance: 1711
angle: 155 distance: 1700
angle: 155.62 distance: 1691
angle: 156.25 distance: 1683
angle: 156.87 distance: 1672
angle: 157.5 distance: 1666
angle: 158.12 distance: 1655
angle: 158.75 distance: 1645
angle: 159.37 distance: 1637
angle: 160 distance: 1633
angle: 160.62 distance: 1622
angle: 161.25 distance: 1621
angle: 161.87 distance: 1611
angle: 162.5 distance: 1602
angle: 163.12 distance: 1597
angle: 163.75 distance: 1592
angle: 164.37 distance: 1583
angle: 165 distance: 1579
angle: 165.62 distance: 1578
angle: 166.25 distance: 1571
angle: 166.87 distance: 1564
angle: 167.5 distance: 1558
angle: 168.12 distance: 1552
angle: 168.75 distance: 1551
angle: 169.37 distance: 1550
angle: 170 distance: 1545
angle: 170.62 distance: 1543
angle: 171.25 distance: 1540
angle: 171.87 distance: 1537
angle: 172.5 distance: 1529
angle: 173.12 distance: 1527
angle: 173.75 distance: 1527
angle: 174.37 distance: 1524
angle: 175 distance: 1522
angle: 175.62 distance: 1518
angle: 176.25 distance: 1519
angle: 176.87 distance: 1517
angle: 177.5 distance: 1513
angle: 178.12 distance: 1510
angle: 178.75 distance: 1514
angle: 180 distance: 1514
angle: 180.62 distance: 1511
angle: 181.25 distance: 1519
angle: 181.87 distance: 1513
angle: 182.5 distance: 1514
angle: 183.12 distance: 1513
angle: 183.75 distance: 1513
angle: 184.37 distance: 1514
angle: 185 distance: 1518
angle: 185.62 distance: 1517
angle: 186.25 distance: 1519
angle: 186.87 distance: 1517
angle: 187.5 distance: 1526
angle: 188.12 distance: 1522
angle: 188.75 distance: 1526
angle: 189.37 distance: 1527
angle: 190 distance: 1530
angle: 190.62 distance: 1536
angle: 191.25 distance: 1536
angle: 191.87 distance: 1541
angle: 192.5 distance: 1544
angle: 193.12 distance: 1549
angle: 193.75 distance: 1553
angle: 194.37 distance: 1555
angle: 195 distance: 1553
angle: 195.62 distance: 1563
angle: 196.25 distance: 1569
angle: 196.87 distance: 1570
angle: 197.5 distance: 1581
angle: 198.12 distance: 1583
angle: 198.75 distance: 1591
angle: 199.37 distance: 1597
angle: 200 distance: 1601
angle: 200.62 distance: 1606
angle: 202.5 distance: 1615
angle: 203.12 distance: 1626
angle: 203.75 distance: 1625
angle: 204.37 distance: 1644
angle: 205 distance: 1646
angle: 205.62 distance: 1658
angle: 206.25 distance: 1663
angle: 206.87 distance: 1674
angle: 207.5 distance: 1685
angle: 208.12 distance: 1703
angle: 208.75 distance: 1703
angle: 209.37 distance: 1717
angle: 210 distance: 1732
angle: 210.62 distance: 1743
angle: 211.25 distance: 1750
angle: 211.87 distance: 1766
angle: 212.5 distance: 1776
angle: 213.12 distance: 1791
angle: 213.75 distance: 1808
angle: 214.37 distance: 1814
angle: 215 distance: 1835
angle: 215.62 distance: 1844
angle: 216.25 distance: 1854
angle: 216.87 distance: 1870
angle: 217.5 distance: 1892
angle: 218.12 distance: 1909
angle: 218.75 distance: 1918
angle: 219.37 distance: 1934
angle: 220 distance: 1952
angle: 220.62 distance: 1972
angle: 221.87 distance: 2023
angle: 222.5 distance: 2039
angle: 223.12 distance: 2059
angle: 223.75 distance: 2082
angle: 225 distance: 2101
angle: 225.62 distance: 2122
angle: 226.25 distance: 2148
angle: 226.87 distance: 2173
angle: 227.5 distance: 2190
angle: 228.12 distance: 2214
angle: 228.75 distance: 2241
angle: 229.37 distance: 2275
angle: 230 distance: 2295
angle: 230.62 distance: 2324
angle: 231.25 distance: 2348
angle: 231.87 distance: 2160
angle: 232.5 distance: 2416
angle: 233.12 distance: 2445
angle: 233.75 distance: 2479
angle: 234.37 distance: 2520
angle: 235.62 distance: 2607
angle: 236.25 distance: 2649
angle: 236.87 distance: 2156
angle: 237.5 distance: 2726
angle: 238.12 distance: 2768
angle: 238.75 distance: 2806
angle: 239.37 distance: 2865
angle: 240 distance: 2912
angle: 240.62 distance: 2962
angle: 241.25 distance: 3026
angle: 241.87 distance: 3078
angle: 242.5 distance: 3147
angle: 243.12 distance: 3210
angle: 243.75 distance: 3276
angle: 244.37 distance: 3315
angle: 245 distance: 3307
angle: 245.62 distance: 3288
angle: 246.25 distance: 3267
angle: 246.87 distance: 3253
angle: 247.5 distance: 3153
angle: 248.75 distance: 4678
angle: 249.37 distance: 4563
angle: 250 distance: 4560
angle: 250.62 distance: 4504
angle: 251.25 distance: 4523
angle: 251.87 distance: 4478
angle: 252.5 distance: 4452
angle: 253.12 distance: 4465
angle: 253.75 distance: 4434
angle: 254.37 distance: 4421
angle: 255 distance: 4391
angle: 255.62 distance: 4371
angle: 256.25 distance: 4361
angle: 256.87 distance: 4356
angle: 257.5 distance: 4348
angle: 258.12 distance: 4326
angle: 258.75 distance: 4326
angle: 259.37 distance: 4331
angle: 260 distance: 4341
angle: 260.62 distance: 4270
angle: 261.25 distance: 4263
angle: 261.87 distance: 4281
angle: 262.5 distance: 2992
angle: 263.12 distance: 2984
angle: 263.75 distance: 2976
angle: 264.37 distance: 2983
angle: 265 distance: 2971
angle: 265.62 distance: 2963
angle: 266.25 distance: 2963
angle: 266.87 distance: 2967
angle: 267.5 distance: 2968
angle: 268.12 distance: 2951
angle: 268.75 distance: 2951
angle: 270 distance: 2959
angle: 270.62 distance: 2953
angle: 271.25 distance: 2500
angle: 271.87 distance: 5514
angle: 272.5 distance: 2839
angle: 273.12 distance: 2706
angle: 273.75 distance: 2721
angle: 274.37 distance: 2693
angle: 288.12 distance: 3010
angle: 288.75 distance: 2999
angle: 289.37 distance: 2998
angle: 290 distance: 3020
angle: 290.62 distance: 3036
angle: 291.25 distance: 3083
angle: 291.87 distance: 3169
angle: 292.5 distance: 3170
angle: 293.12 distance: 3196
angle: 293.75 distance: 3212
angle: 294.37 distance: 3230
angle: 295 distance: 3234
angle: 295.62 distance: 3262
angle: 296.25 distance: 3273
angle: 296.87 distance: 3298
angle: 297.5 distance: 3318
angle: 298.12 distance: 3333
angle: 298.75 distance: 3356
angle: 299.37 distance: 3374
angle: 300 distance: 3394
angle: 300.62 distance: 3417
angle: 301.25 distance: 3427
angle: 301.87 distance: 3453
angle: 302.5 distance: 3474
angle: 303.12 distance: 3490
angle: 303.75 distance: 3516
angle: 304.37 distance: 3552
angle: 305 distance: 3571
angle: 305.62 distance: 3581
angle: 307.5 distance: 5224
angle: 308.12 distance: 5271
angle: 308.75 distance: 5316
angle: 309.37 distance: 5411
angle: 310 distance: 3843
angle: 310.62 distance: 3892
angle: 311.25 distance: 3907
angle: 311.87 distance: 3922
angle: 312.5 distance: 3985
angle: 313.12 distance: 4016
angle: 313.75 distance: 4058
angle: 315 distance: 4081
angle: 315.62 distance: 4143
angle: 316.25 distance: 4190
angle: 316.87 distance: 4230
angle: 317.5 distance: 4291
angle: 318.12 distance: 4353
angle: 318.75 distance: 4406
angle: 319.37 distance: 4460
angle: 320 distance: 4512
angle: 320.62 distance: 4563
angle: 321.25 distance: 4507
angle: 321.87 distance: 4473
angle: 322.5 distance: 4426
angle: 323.12 distance: 4398
angle: 323.75 distance: 4371
angle: 324.37 distance: 4321
angle: 325 distance: 4274
angle: 325.62 distance: 4256
angle: 326.25 distance: 4215
angle: 326.87 distance: 4194
angle: 327.5 distance: 4148
angle: 328.12 distance: 4104
angle: 328.75 distance: 4077
angle: 329.37 distance: 4051
angle: 330 distance: 4024
angle: 330.62 distance: 3995
angle: 331.25 distance: 3971
angle: 331.87 distance: 3932
angle: 332.5 distance: 3909
angle: 333.12 distance: 3898
angle: 333.75 distance: 3884
angle: 334.37 distance: 3858
angle: 335 distance: 3840
angle: 335.62 distance: 3818
angle: 336.25 distance: 3791
angle: 337.5 distance: 3765
angle: 338.12 distance: 3747
angle: 338.75 distance: 3720
angle: 339.37 distance: 3715
angle: 340 distance: 3689
angle: 340.62 distance: 3687
angle: 341.25 distance: 3635
angle: 341.87 distance: 3632
angle: 342.5 distance: 3624
angle: 343.12 distance: 3613
angle: 343.75 distance: 3613
angle: 344.37 distance: 3594
angle: 345 distance: 3595
angle: 345.62 distance: 3560
angle: 346.25 distance: 3570
angle: 346.87 distance: 3543
angle: 347.5 distance: 3555
angle: 348.12 distance: 3527
angle: 348.75 distance: 3512
angle: 349.37 distance: 3512
angle: 350 distance: 3521
angle: 350.62 distance: 3486
angle: 351.25 distance: 3496
angle: 351.87 distance: 3477
angle: 352.5 distance: 3487
angle: 353.12 distance: 3461
angle: 353.75 distance: 3460
angle: 354.37 distance: 3458
angle: 355 distance: 3453
angle: 355.62 distance: 3460
angle: 356.25 distance: 3448
angle: 357.5 distance: 998
angle: 358.12 distance: 3442 

If I plot these data, they look like the bellow picture. Now is there any algorithm that could help me to detect the corner or wall. I want to detect the corner or wall so that I could easily find out the room surface. For example distance from corner to corner or distance between walls help me to find out the surface area. Later on, I could create the floor plan using OpenCV maybe. I do not know should I chose point cloud library or image processing.

So far I came across with RNSAC method and Haris corner detection.

• With RANSAC can I detect multiple lines and their intersection? If it's possible then I might find the corner of the room and can draw the floor plan based on the corner.
• Will Haris corner detection detect all the corners?

which way should I proceed? Is there any better solution?

Answer 1

Treat this answer as a "work in progress". Anyone else is welcome to take, use, develop and improve any aspect of it.

I am using ImageMagick in the Terminal, just for speed, but the same techniques are available in OpenCV and scikit-image.

First things first, I want to get rid of annotations and clean up the data. Others may choose to take the CSV data from the OP's question:

magick lidar.png -fuzz 20% -fill black +opaque "rgb(53,255,255)" -colorspace gray -auto-level -threshold 50% clean.png

That gives us a clean image of the data in clean.png:

My first instinct is to try and use the "Hough Transform" to find the walls, i.e. straight lines:

magick clean.png -colorspace RGB \( +clone -background none -fill red -stroke red -strokewidth 2 -hough-lines 9x9+30 \) -composite result.png

Rather than drawing them on in red, you can also get the coordinates of the detected lines like this:

magick clean.png -hough-lines 9x9+30 mvg:-

Output:

# Hough line transform: 9x9+30
viewbox 0 0 929 761
# x1,y1 x2,y2 # count angle distance
line 0,30.8401 929,47.0559  # 58 91 315        <--- THIS LINE EXPLAINED BELOW
line 178.597,0 165.314,761  # 42 1 364
line 0,553.92 929,570.136  # 182 91 838

By way of clarification, the line above that looks like this:

line 0,30.8401 929,47.0559  # 58 91 315

means there is a red line from coordinates [0,30] to [929,47] where the x-coordinate comes first and there are 58 points that make up that line. Note also that there are two lines at an angle of 91 degrees - this is a good hint that they are parallel - like room walls are likely to be.

The right side wall is rather harder to find... still thinking and working. If/when we get all four walls, we can solve analytically for the intersection of the line to get the corners of the room.

---

As regards looking for corners, if you plot the radial distance from the centre at each angle, you should find 4 peaks of distance which should be the corners since they must be furthest from the sensor. So, that might look like this - note that I smooth the data heavily in the code to remove the outliers.

#!/usr/bin/env python3

from scipy import ndimage as ndi
import matplotlib.pyplot as plt
import datetime
import numpy as np
import pandas as pd

# Load CSV
df = pd.read_csv('lidar.csv',delimiter=',')
xdata = df.values[:,0]
rdata = df.values[:,1]

# Condition distance data
smoothed = ndi.gaussian_filter(rdata,sigma=5)

plt.plot(xdata,smoothed,'b.')    # blue circle

plt.title('Lidar')
plt.xlabel('angle')
plt.ylabel('distance')
plt.grid(True)
plt.show()

A quick reading of that implies the corners are at Lidar angles of:

25, 130, 260, 320 degrees

Note that I edited the distractions out of your CSV file, so it now looks like this:

0,942
0.62,3469
1.25,3350
2.5,3410
...
...

---

Do you control the positioning of the lidar sensor? If so, you can maybe think about asking the operator to always start the scanning with it pointing at a corner, then you would have a good reference point for where the first corner should appear in your data. You could also maybe do 2 scans, maybe at different heights, to reduce random noise from reflections.