Granted Patent B2

US 12,618,678 · App. 18/567,490 · Granted May 5, 2026

Inventors: Peng Ren (Santa Cruz, CA); Fatemeh Elyasi (Santa Cruz, CA); Roberto Manduchi (Santa Cruz, CA)

Assignee: THE REGENTS OF THE UNIVERSITY OF CALIFORNIA

G01C21/16G06N3/044G06N3/08

Abstract

Claims (72)

1 . A navigation system determining turns in a user's trajectory, comprising:

a smartphone comprising a display and one or more sensors and at least comprising or coupled to one or more processors; one or more memories; and one or more programs stored in the one or more memories, wherein the one or more programs executed by the one or more processors carry out the following acts:

receiving input data, comprising orientation data and acceleration from the one or more sensors carried by a user taking steps along a trajectory;

detecting a plurality of n straight sections in the trajectory, where n is an integer, each of the straight sections corresponding to the user walking along a substantially straight or linear path;

generating and tracking an orientation of the user in each of the n straight sections, wherein the orientation comprises an estimated orientation taking into account drift of the input data outputted from the one or more sensors;

detecting one or more turns in the trajectory, wherein each of the turns is a change in the estimated orientation of the user in the n th one of the straight sections as compared to the estimated orientation in the (n−1) th one of the straight sections; and

providing navigation instructions from the smartphone to the user using the trajectory generated using the one or more turns; and

wherein detecting the straight sections further comprises the one or more programs:

storing the input data in a database;

transforming the input data into trajectory detection data processable by a first machine learning module;

classifying the trajectory detection data as representing motion in one of the straight sections or in a non-straight section using the first machine learning module; and

labelling one or more values of the trajectory detection data as being associated with one of the straight sections if the one or more values are classified by the first machine learning module as being associated with the one of the straight sections.

2 . The system of claim 1 , wherein the first machine learning module is trained using training data comprising at least WeAllWalk™ data, or the acceleration and the orientation of pedestrians comprising blind or visually impaired persons walking using a walking aid.

3 . The system of claim 1 , wherein the first machine learning module comprises a GRU neural network.

4 . The system of claim 1 , wherein the first machine learning module comprises a recurrent neural network trained to identify, from the acceleration and the orientation data comprising an azimuthal angle, each of the straight sections comprising one or more time intervals during which the user walks regularly or substantially on a straight path.

5 . The system of claim 1 , wherein the first machine learning module is trained to disregard changes in the orientation resulting from the user comprising a visually impaired user stopping and rotating their body to re-orient or swerving to avoid a perceived obstacle.

6 . The system of claim 1 , further comprising detecting each of the straight sections after the one or more programs sample the orientation data for no more than 1 second.

7 . The system of claim 1 , wherein the turn by an angle of 90° is tracked as two consecutive turns by 45°.

8 . The system of claim 1 , wherein the trajectory is determined without reference to a map of an environment in which the user is moving.

9 . The system of claim 1 , wherein the one or more programs:

receive a map of an environment in which the user is moving, the map identifying one or more impenetrable walls, and

determine the trajectory by comparing the trajectory to the map and eliminating one or more paths in the trajectory that traverse the one or more impenetrable walls.

10 . The system of claim 9 , wherein the one or more programs:

receive or obtain velocity vectors of the user from the input data or another source;

generate posterior locations of the user from the velocity vectors using a particle filtering module; and

generate a mean shift estimating locations of the user corresponding to highest modes of the posterior locations to obtain estimated locations; and

generate the trajectory by linking pairs of the estimated locations that share the largest number of the highest modes.

11 . A navigation system determining turns in a user's trajectory, comprising:

a smartphone comprising a display and one or more sensors and at least comprising or coupled to one or more processors; one or more memories; and one or more programs stored in the one or more memories, wherein the one or more programs executed by the one or more processors carry out the following acts:

receiving input data, comprising orientation data and acceleration from the one or more sensors carried by a user taking steps along a trajectory;

detecting a plurality of n straight sections in the trajectory, where n is an integer, each of the straight sections corresponding to the user walking along a substantially straight or linear path;

generating and tracking an orientation of the user in each of the n straight sections, wherein the orientation comprises an estimated orientation taking into account drift of the input data outputted from the one or more sensors;

detecting one or more turns in the trajectory, wherein each of the turns is a change in the estimated orientation of the user in the n th one of the straight sections as compared to the estimated orientation in the (n−1) th one of the straight sections; and

providing navigation instructions from the smartphone to the user using

the trajectory generated using the one or more turns,

wherein the one or more programs:

transform coordinates of the input data into a heading agnostic reference frame, to obtain heading agnostic data;

detect the steps as detected steps by associating impulses in the heading agnostic data with heel strikes using a machine learning module;

count a number of the detected steps by associating the steps with a stride length, so as to output step data;

determine the trajectory using the detected steps and the turns; and

the trajectory comprises:

one or more step displacement vectors defined at each of the detected steps as having a first length equal to the stride length and a direction comprising an azimuthal angle obtained from the input data; and

one or more turn displacement vectors defined as having a second length equal to the step length and with the direction determined from the turns detected.

12 . The system of claim 11 , further comprising the one or more programs:

transforming the heading agnostic data into trajectory detection data processable by the machine learning module; and at least

classifying or recognizing one or more values of the trajectory detection data as being associated with the steps using the machine learning module, or

counting the steps using the machine learning module.

13 . The system of claim 12 , wherein the machine learning module is trained using reference trajectory data outputted from another machine learning module identifying the user's trajectory.

14 . The system of claim 12 , wherein the machine learning module comprises an LSTM neural network comprising no more than 2 layers and a hidden unit size of no more than 6.

15 . A method for determining turns in a user's trajectory, comprising, using a smart phone comprising a display and one or more sensors and at least comprising or coupled to a computer comprising one or more processors; one or more memories; and one or more programs stored in the one or more memories:

capturing input data, comprising orientation data and acceleration data from the one or more sensors in the smartphone carried by a user taking steps along a trajectory;

detecting a plurality of n straight sections in the trajectory, each of the straight sections corresponding to the user walking along a substantially straight path or a linear path;

generating and tracking an orientation of the user in each of the n straight sections, wherein the orientation comprises an estimated orientation taking into account drift of the input data outputted from the one or more sensors; and

detecting one or more turns in the trajectory, wherein each of the turns is a change in the estimated orientation of the user in the n th one of the straight sections as compared to the estimated orientation in the (n−1) th one of the straight sections;

storing the input data in a database on the computer;

transforming the input data into trajectory detection data processable by a first machine learning module;

classifying the trajectory detection data as representing motion in one of the straight sections or in a non-straight section using the first machine learning module;

labelling one or more values of the trajectory detection data as being associated with one of the straight sections if the one or more values are classified by the first machine learning module as being associated with the one of the straight sections; and

providing navigation instructions from the smartphone to the user using the trajectory generated from the one or more turns.

16 . The method of claim 15 , further comprising training the first machine learning module for detecting at least one of the straight sections or the turns in the trajectory, comprising:

collecting a set of first pedestrian data, the first pedestrian data comprising the orientation data and the acceleration data for one or more walking pedestrians;

applying one or more transformations to the first pedestrian data including smoothing to create a modified set of pedestrian data;

creating a first training set from the modified set, comprising labelled straight walking sections and labeled non-straight walking sections; and

training the first machine learning module using the first training set to identify the straight sections in the trajectory detection data using the orientation data and the acceleration data, the straight sections each corresponding to the user walking along the linear path.

17 . The method of claim 16 , wherein the first training set comprises the modified set comprising data for the walking pedestrians comprising blind or visually impaired persons walking using a walking aid comprising at least one of a cane or a guide dog.

18 . The method of claim 17 , wherein the first pedestrian data comprises a WeAllWalk™ data set.

19 . The method of claim 16 , wherein:

the applying of the transformations comprises removing data, from the first pedestrian data, associated with a single 45° turn or 90° turns associated with a 45° turn; and

the training comprises training the first machine learning module, or another machine learning module, to detect, identify, or classify the turns in the trajectory comprising 90° turns.

20 . The method of claim 16 , further comprising:

creating a second training set from the modified set, the second training set comprising orientation turns between adjacent ones of the straight sections;

training the first machine learning module, or another machine learning module, to detect, classify, or identify the turns in the trajectory using the second training set.

Assignments (1)

Continuity (3)

References Cited (21)