Brandon Cai¹, Aditya Patankar², Nilanjan Chakraborty²

Garcia Research Scholar Program

Stony Brook University, New York 11790, USA¹

​

Stony Brook University, New York 11790, USA²

Intelligent Low-Cost 3D LiDAR Tripping Hazard Scanner

March 19, 2024

brandoncai888@gmail.com,

aditya.patankar@stonybrook.edu,

nilanjan.chakraborty@stonybrook.edu

ABOUT The Speaker

Brandon Cai�Garcia Research Scholar Program, Stony Brook University, New York

I aspire to develop technologies to improve people’s lives especially for people with disabilities. Motivated by my karate grandmaster’s deteriorating eyesight due to a rare disease, my devices center on helping blind and visually impaired users navigate.

I am currently an 11^th grader at Parkland High School, Allentown, PA. Science fairs and research have served as my creative outlets. I am a finalist at the Regeneron International Science and Engineering Fair (ISEF) and the DoD, Army, Navy and Airforce sponsored JSHS science fair. With my passion in STEM and aspirations in EECS, I engaged in college level research at Garcia Research program at Stony Brook University and have been selected to attend the Research Science Institute (RSI) program at MIT this summer.

My other academic awards include a National Physics Olympiad (USAPhO) Bronze Medal, and National Junior Math Olympiad (USAJMO) qualification.

This is my first presentation at a profession conference. Part of this project benefited from my work at Stony Brook under the mentorship of Dr. Nilanjan Chakraborty and Mr. Aditya Patankar, the coauthors of this paper.

brandoncai888@gmail.com

Brandon Cai

Brandon Cai

BACKGROUND AND PROBLEM STATEMENT

• The blind and visually impaired have limited options to detect tripping hazards

White Cane

Ultrasound

Sensors

Guide Dog

This Project:

Intelligent Stereo Vision

“The main difference in traveling with a dog versus traveling with a cane is that the cane is an obstacle detector, and a dog is an obstacle avoider.”

“With a dog, you get a lot less environmental feedback. There’s a lot of trust with a dog.”

ML based

Computer

Vision

Existing Options

Options in Development

Image taken from: www.bbc.com/news/disability-34855311

Image from lhblind.org

Image from pysource.com/2021/03/11

SMALL ELEVATION CHANGE AND POTHOLE CHALLENGES

• A small elevation bump and pothole is particularly challenging
• The white cane is the only existing option to give user feedback but with limited resolution
• Swinging a white cane in a crowded area can accidentally trip other people
• Current High-Tech options do not enable ground detection
• Ultrasonic sensors aimed too low can confuse by ground reflection
• Machine Learning based Computer Vision cannot detect potholes with arbitrary shapes and colors

Image edge

extraction

Image taken from: www.bbc.com/news/disability-34855311

Images taken from: "System and Method for Detecting Potholes based on Video Data." CIS Journal, vol. 5, no. 9, Sept. 2014

PROPOSED SOLUTION: INTELLIGENT STEREO VISION

cluster (blue): pothole

minor clusters (black): noise

• Build a 3D LiDAR and generate the 3D terrain point cloud model

• Use rule-based computer vision Random Sampling Consensus (RANSAC) to detect the ground plane
• Separate outliers from ground plane containing all the obstacles

• Further process the outlier using Density-Based Spatial Clustering of Applications with Noise (DBSCAN) to separate the trapping hazard clusters
• Calculate Orientated Bounding Box (OBB) to report size and location info

PROPOSED HARDWARE: LOW COST 3D LIDAR SCANNER

• To detect low and negative elevation tripping hazards using 3D LiDAR scanning
• Combining a low cost 2D LiDAR scanner with a servo motor as the third dimension

Limited detection only in one plane

2D LiDAR Scanner

www.slamtec.com/en/Lidar/A2

https://www.sick.com/ca/en/detection-and-ranging-solutions

https://www.youtube.com/watch?v=-qQgvJ6FJdc

Even an expensive 3D LiDAR scanner >$5000

has poor vertical scan resolution. The vertical scan

angles are dictated by spinning set-angled mirrors.

Pseudo 3D LiDAR Scanner

Concept of High Resolution 3D LiDAR with Tilt Angle Sweeping

Limitations for Existing LiDAR Scanners

Solution to higher 3D resolution

HYPOTHESIS AND DESIGN GOALS

If a 3rd dimension of freedom is added to a low cost 2D LiDAR scanner, an effective 3D scan algorithm can be established with superior centimeter LiDAR ranging accuracy, detecting very small elevation changes like a doorstep, pothole, bump, curb, and sudden drop at the top of a staircase.

At shoulder level (1.5 meters), object 2 meters away:

• 3.7cm resolution in direction of travel with 0.5° servo motor increment
• 2.0cm resolution in lateral direction based on 2D LiDAR scanning resolution spec of 0.45°

Estimating the Resolutions as the Engineering Goals

Estimating the 3D Scanning Speed as Engineering Goal

• Low cost 2D LiDAR scan rate: 10Hz rate (0.1s)
• Tilt angle increment time: 0.05s
• Theoretically can scan 40 tilt angles in 6 seconds
• Adequate for warning of potholes 2~3 meters ahead of a slow walking visually impaired user

DESIGN AND BUILD 3D LIDAR SYSTEM

• Integrating the 3D scanner into a hardware system with LiDAR attached to servo motor on a tripod
• Calibrating LiDAR base’s 0° level using iPhone’s built-in tilt angle detection sensor, and programming the constant offset for the motor

Tripod

Serial Port to USB

Adaptor for Servo Motor

2D LiDAR Scanner

Slamtec

RPLiDAR A2

Servo Motor

LewanSoul

LX-224

Mini Computer Raspberry Pi 4

Design and 3D Print LiDAR Mounting Base

4 recessed screw holes

for LiDAR attachment

Plug in ¼ inch hex nut for camera base screw

Design with Tinker CAD

3D print

Calibrate LiDAR

Base’s 0°

Level

WRITING THE 3D SCANNER SOFTWARE IN PYTHON

Four modules developed:

• LiDAR data acquisition

and optional save to a csv

file for post processing

• Servo motor angle sweep
• Coordinate transformation

- (θ, φ, r) to (x, y, z)

• 3D color mapped plots:

- Scatter plot (more details)

- Surface plot (high contrast)

Python code for coordinate transformation

Input and out data format snapshots

If θi sweep

in range

Y

Move servo motor to θi plane

Initiate Servo, LiDAR, graphing parameters, time stamped data file

LiDAR scan the θi plane

Transform spherical (φ, θ, r) to

Cartesian (x, y ,z) coordinates

Filter data in desired range

Store the data in .csv file

(if desired)

N

Scatter plot or Surface plot

Scatter

Surface

Filter data in desired range

Creating linear interpolated grid from irregularly spaced data coordinates

Generate color mapped

3D scatter plot using matplotlib

Generate color mapped

3D surface plot using matplotlib

DEVELOPING COORDINATE TRANSFORMATION ALGORITHM

LiDAR data referenced around its tilted local polar (φ, r) frame and projected to ground frame (x, y, z)

Shifted origin used by LiDAR relative to the user’s frame

Adding error correction algorithm developed to account for off-axle LiDAR rotation

OUTDOOR FUNCTIONAL TEST RESULTS

3D LiDAR scan of the stairs successfully detected elevation changes, and scatter plot rendering showed details down to the handrail, with colors to highlight the elevation change.

To generate high contrast surface plots, the data which is irregularly spaced in the x-y plane must be postprocessed using 3D linear interpolation to form a uniform grid.

3D surface plot provides high contrast views suitable for navigation. With the complete 3D terrain model, x-y, x-z and y-z cross section views are possible.

Increase in elevation

from bottom of the

stairs (1.25m away)

Stairs

Scatter Plot

3D view

Deepest point 6cm

30cm

Pothole

1.25 meter

x-y top view

x-z cross section

y-z cross section

Surface Plot

A small shallow pothole (1.68m away)

OUTDOOR FUNCTIONAL TEST RESULTS (CONTINUED)

MINIMUM RESOLUTION TEST SETUP

• Quantitatively analyze achieved resolution to predict minimum detectable obstacle size vs distance
• Inspired by technique for evaluating photography image sharpness, 3D imaging of sharp edges of long wood boards was used with automatic edge detection Python code developed to maximize the number of edge points to be included in the evaluation.

Each 2D slice contains sharp changes

in elevation

(∆z) for edge

detection

Edge #1

#2

#3

#4

6cm gap

One slice for illustration

Raw data top view

Edges detected

Lateral Resolution Measurement

Direction of Travel

Resolution Measurement

An unexpected artifact impacted the LiDAR accuracy likely caused by relatively large vertical laser beam size and the partial obstruction range near the edge.

Elevation Resolution

Measurement

Use a board standing at a 45° angle to produce a consistent elevation increase. Deviation in z direction from the linear curve fit is the error.

linear curve fit

MINIMUM RESOLUTION TEST RESULTS

• Quantify resolution to predict minimum detectable obstacle size
• X and Z direction resolutions met design targets
• Y direction resolution is worse than expected when detecting an edge nearly parallel to the laser scanning direction

Lateral Resolution

Max lateral measurement error is better than the design target, and gradually increase from 1.1cm (1-2m range) to 2.2cm (in 3-4m range).

Determined by 2D LiDAR scanning

angle resolution spec

Elevation Resolution

Very good resolution is achieved in the elevation measurement with 1.1cm (1m range), 2.2cm (2m range) to 5.5cm (4m range).

Determined by LiDAR distance measurement accuracy spec

Direction of Travel Resolution

The max error is slightly worse than the design target but adequate for pothole detection, and gradually increase from 5.2cm (1m range), to +7.3cm (2m range).

An unexpected artifact impacted the LiDAR accuracy likely caused by relatively large vertical laser beam size and the partial obstruction range near the edge.

Determined by servo motor scan angle resolution and the artifact issue

Analyze each object and find tripping hazards in path to alert the user

Point cloud in ground frame

Detect ground plane using RANSAC algorithm

​

​

Highlight the direction of travel on the ground as walkpath

Separate the obstacle detected using cluster DBSCAN algorithm

​

RANSAC inlier

RANSAC outlier

Generate Orientated Bounding Box (OBB) for each obstacle detected using Rotating Calipers algorithm

RULE-BASED COMPUTER VISION ALGORITHM DEVELOPED

• A simplified data processing flow visualized

GROUND PLANE DETECTION & OBSTACLES ISOLATION

• Ground plane detection using Random Sampling Consensus (RANSAC)
• Separate outliers from ground plane containing all the obstacles
• Further process the outlier using Density-Based Spatial Clustering of Applications with Noise (DBSCAN) to separate the clusters

1) Select a random set of points (3 points forming a plane) and derive the plane equation.

2) Calculate the deviation of all the points

in the point cloud from the plane. If the distance is within the THRESHOLD then add the point as an inlier.

3) Iterate the process to maximize number of inliers as the ground plane.

inlier

outlier

A= core

B, C= bounder

N=noise

DBSCAN:

Count the number of “reachable neighbors” to find the boundary of each cluster

RANSAC:

Images from medium.com/@ajithraj_gangadharan

Image from https://en.wikipedia.org/wiki/DBSCAN

GENERATING ORIENTED BOUNDING BOX (OBB)

• Rotating Calipers algorithm developed in Python is the key to accurate location and size reporting
• Calculate convex hull, and then rotate the hull to find the tightest fit for OBB

Overestimated by standard

Axis Aligned Bounding Box

- using min and max x/y/z values

Optimal Orientated Bounding Box

- projected to horizontal plane, Convex Hull, and Rotating Calipers

Rotating Calipers OBB

All self Generated Images

All self Generated Images

TEST RESULT: POTHOLE DETECTION

• Demonstrated effective negative elevation change tripping hazard detection

1.68 meter

3D view

xy top view

STEP 1: VOXEL DOWNSIZE OF THE LIDAR POINT CLOUD

3D Point Cloud

STEP 2: FINDING GROUND PLANE USING RANDOM SAMPLING CONSENSUS

TEST RESULT: MULTIPLE OBJECTS ISOLATION

• Multiple object clusters isolated: curb & fire hydrant, a small indent, road surface

TEST RESULT: MULTIPLE OBJECTS ISOLATION

• A more complex case with many obstacles detected by the LiDAR equipped with computer vision capability abstracted the surrounding into 5 objects.

CONCLUSION

• Inspired by autonomous driving and robotic vision technologies, an automatic object detection and dimension estimation algorithm has been developed in Python.
• As demonstrated, the ground in the 3D terrain model was removed using Random Sample Consensus (RANSAC) to create segmented point clouds of each tripping hazard, followed by finding an Oriented Bounding Box (OBB) using Convex Hull and Rotating Calipers techniques. In this way, each obstacle is not only isolated from the background with its clear location marked, but also the dimensions and orientation are quantified in 3 dimensions using an OBB.
• A new high-resolution 3D LiDAR was developed with fully functional software to generate 3D terrain profile with spatial resolution of <2cm in elevation for small elevation change tripping hazards such as potholes, curbs, and doorsteps.
• This new 3D LiDAR technique opens the door to ground level tripping hazard detection that challenged sonar, 2D LiDAR or single camera-based computer vision.
• The LiDAR unexpectedly requires repetitive disconnect/connect action in between every consecutive data acquisitions causing a 50s long scan time (too slow to be used for computer vision purposes).

ACKNOWLEDGEMENT

In the summer of 2023, the coauthor Brandon Cai was fortunate enough to find a research opportunity at Dr. Nilanjan Chakraborty’s Interacting Robotic System Laboratory at Stony Brook University through the Garcia Research Scholar Program. After Brandon created the Rotating Calipers based OBB algorithm for robot manipulation planning, it inspired Brandon to introduce the computer vision technologies to his independent project in building assistive device for the visually impaired. In 2022 before the work at Stony Brook, Brandon already constructed the 3D LiDAR with the software developed for spatial transformation and graphing. For the early stage of LiDAR development, Brandon would like to acknowledge the support from Dr. Luis Rodriguez from the Naval Surface Warfare Center Dahlgren Division for suggestions on general practice in data collection and possible sun glare on the LiDAR sensor. This suggestion also inspired the idea of using this LiDAR sensor as a night vision device.

REFERENCES

"About the UltraCane." UltraCane, ultracane.com/about_the_ultracane.

​

Arnon, Dennis S., and John P. Gieselmann. "A Linear Time Algorithm for the Minimum Area Rectangle Enclosing a Convex Polygon." Computer Science Department, Purdue U, 7 Dec. 1983. Purdue e-Pubs, docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1381&context=cstech.

​

Burger, Patrick, and Hans Jaochim Wuensche. "Fast Multi-Pass 3D Point Segmentation Based on a Structured Mesh Graph for Ground Vehicles." IEEE Intelligent Vehicle Symposium, 2018, ieeexplore.ieee.org/abstract/document/8500552.

​

Chang, Chia Tche, et al. "Fast oriented bounding box optimization on the rotation group SO(3,ℝ)." ACM Transactions on Graphics, vol. 30, no. 5, 22 Oct. 2011, dl.acm.org/doi/10.1145/2019627.2019641.

​

EdjeElectronics, Evan. "How to Run TensorFlow Lite Object Detection Models on the Raspberry Pi (with Optional Coral USB Accelerator)." GitHub, github.com/EdjeElectronics/TensorFlow-Lite-Object-Detection-on-Android-and-Raspberry-Pi/blob/master/deploy_guides/Raspberry_Pi_Guide.md.

​

"How Dangerous Are White Canes?" BBC, 18 Nov. 2015, www.bbc.com/news/disability-34855311.

​

Hyun-je. pyrplidar. GitHub, 5 Oct. 2019, github.com/Hyun-je/pyrplidar.

​

Kim, Taehyeong, and Seung Ki Ryu. "System and Method for Detecting Potholes based on Video Data." Journal of Emerging Trends in Computing and Information Sciences, vol. 5, no. 9, Sept. 2014, citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.676.4928&rep=rep1&type=pdf.

​

Naujoks, Benjamin, and Hans Joachim Wuensche. "An Orientation Corrected Bounding Box Fit Based on the Convex Hull under Real Time Constraints." IEEE Intelligent Vehicle Symposium, 2018, ieeexplore.ieee.org/document/8500692.

​

Shaul, Yorai. "A Full Autonomous Stack, a Tutorial | ROS + Raspberry Pi + Arduino + SLAM." Yoraish, 8 Sept. 2021, yoraish.wordpress.com/2021/09/08/a-full-autonomous-stack-a-tutorial-ros-raspberry-pi-arduino-slam.

​

Spiess, Andreas. " The ugly truth about LIDARs for obstacle avoidance (RPLIDAR A1, Arduino, ESP8266)." Youtube, 27 Sept. 2018, youtube.com/watch?v=AERfie9wlWM.

​

Yoo, H.W., et al. " MEMS-based lidar for autonomous driving." E&I Elektrotechnik Und Informationstechnik, original series, vol. 135, 31 July 2018, pp. 408-415.

Future research will focus on pushing forward a practical wearable assistive device by using sensor fusion and stereo vision. I envision a wearable device mounted under the visor of a cap that can both direct the user towards his or her target location and scan the ground in front to report tripping hazards.

• First is to improve the scanning speed by replacing the LiDAR with a stereo vision camera for a faster response time and lighter weight.
• Generate an algorithm to automatically detect the camera pose from 3D accelerometers to offset camera movement.
• After applying OBB around detected objects, use text-to-speech to announce each object’s location and size.
• A GPS sensor will be added to enable long-range navigation.

Future Research Directions

Brandon Cai

Creating Digital Eyes For Visually Impaired

Using Sensor Fusion and Stereo Vision

DESIGN AND BUILD THE “DIGITAL EYES” SYSTEM

• Built as a wearable device mounted under the visor of the cap
• Use stereo vision camera to map the 3D terrain
• Use sensor fusion with accelerometer to detect camera pose and GPS to detect location

or

APPLY CAMERA POSE CORRECTION TO WEARABLE DEVICE

• Use IMU to detect camera pose (gravitational force vector = straight down)
• Transform point cloud from camera frame to ground frame

### Function to calculate directional angles from IMU accel data ###

def direction_angle_from_accel():

global angle_x, angle_y, angle_z

angle_x = angle_y = angle_z = 0.0

angle_z = np.arctan2(ax, np.sqrt(ay**2 + az**2)) * 180 / np.pi;

angle_x = np.arctan2(ay, az) * 180 / np.pi + 90;

angle_y = 0 # Not possible to get angle_y from acceleration only

• Gravitation force sensed by IMU projected to x, y, z axes
• Read back accelerometer’s 3D components (ax, ay, az)
• Calculate Euler Angles describing the camera pose

OBSTACLE ANALYSIS AND DESCRIPTIVE AUDIO ALERTS

• Analyze all obstacles detected with their OBB vertices to determine if any of them are blocking the walk path
• Only obstacles found in the direct path colored in purple will have their locations and sizes reported as audio alerts

### Audio Alert through text-to-speech ###

…

if obj_in_path_count==0:

engine.say("Walk path is clear.")

else:

j = 0

engine.say(str(obj_in_path_count)+" objects in path")

for j in range(obj_in_path_count):

engine.say("Object "+str(j+1)+" "+ alert_list_w_dist[j][1])

engine.runAndWait()

“New scan in centimeter, 2 objects in path”,

“Object 1 on path: 30 high, 120 away, block center with room on 0 right, -20 left from center”

“Object 2 on path: 30 high, 130 away, 30 right to off path”

Color code: warmer color indicate a closer object.

TEST RESULTS: DYNAMIC OBB TRACKING ON MOVING TARGET

• 3D Display with live camera angle and bounding box update
• Non-blocking Visualizer is created using Open3D package allowing “added geometries” to a scene to be updated after each new 3D image process, with visualizer polling for update status and re-render the image once an update is detected
• Bounding box tracking the person walk back and forth at 4 frame per second refresh rate achieved

THANK YOU!

• I would like to thank the CSUN AT Conference committee and reviewers for giving me this opportunity to present and publish.
• To the professionals at the conference, I would greatly appreciate it if you have suggestions to help with my research project or need an intern like me for your research.

Brandon Cai

brandoncai888@gmail.com