# US 2013/0093852 A1 · Portable robotic device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0093852 A1
- Document ID: US20130093852A1
- Status: Published application
- Kind: A1
- Application number: 13/651,206
- Filed: 2012-10-12
- Published: 2013-04-18
- Earliest claimed: 2011-10-12
- Assignees: Board of Trustees of the University of Arkansas
- Inventors: Cang Ye
- Web page: https://patentgrep.com/patent/US20130093852A1

## CPC

- A61H 3/061: {with electronic detecting or guiding means}
- A61H 3/068: {Sticks for blind persons}
- A61H 2003/063: {with tactile perception}
- A61H 2201/5007: computer controlled
- A61H 2201/5048: Audio interfaces, e.g. voice or music controlled
- A61H 2201/5058: Sensors or detectors
- A61H 2201/5084: Acceleration sensors
- A61H 2201/5092: Optical sensor
- A61H 2201/5097: wireless
- G01S 17/894: Three-dimensional [3D] imaging with simultaneous measurement of time-of-flight at a two-dimensional [2D] array of receiver pixels, e.g. time-of-flight cameras or flash lidar
- G06T 2207/10016: Video; Image sequence
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2207/20076: Probabilistic image processing
- A61H: PHYSICAL THERAPY APPARATUS, e.g. DEVICES FOR LOCATING OR STIMULATING REFLEX POINTS IN THE BODY; ARTIFICIAL RESPIRATION; MASSAGE; BATHING DEVICES FOR SPECIAL THERAPEUTIC OR HYGIENIC PURPOSES OR SPECIFIC PARTS OF THE BODY (electrotherapy, magnetotherapy, radiation therapy or ultrasound therapy A61N)
- G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A portable robotic device (PRD) as well as related devices and methods are described herein. The PRD includes a 3-D imaging sensor configured to acquire corresponding intensity data frames and range data frames of the environment. An imaging processing module configured to identify a matched feature in the intensity data frames, obtain sets of 3-D coordinates representing the matched feature in the range data frames, and determine a pose change of the PRD based on the 3-D coordinates; and perform 3-D data segmentation of the range data frames to extract planar surfaces.

## Claims

### Claim 1

A portable robotic device (PRD), comprising:
a 3-D imaging sensor configured to acquire first and second intensity data frames and first and second range data frames of an environment of the 3-D imaging sensor, the first intensity data frame corresponding to the first range data frame, the second intensity data frame corresponding to the second range data frame; and
an imaging processing module configured to
identify a first feature in the first intensity data frame and a second feature in the second intensity data frame that match each other,
obtain a first set of 3-D coordinates representing the first feature in the first range data frame and a second set 3-D coordinates representing the second feature in the second range data frame, and determine a pose change of the PRD based on the first and second sets of 3-D coordinates; and
perform 3-D data segmentation of at least one of the first and second range data frames to extract planar surfaces from the at least one range data frame.

### Claim 2 (depends on 1)

The device of claim 1, wherein the imaging processing module comprises a Scale-Invariant Feature Transform (SIFT) feature detector configured to extract SIFT features in the first and second intensity data frames, wherein the imaging processing module is configured to identify the first and second features that are SIFT features and that match each other.

### Claim 3 (depends on 2)

The device of claim 2, wherein the SIFT feature detector is configured to identify N SIFT features in the first intensity data frame and N SIFT features in the second intensity data frame that match to each other, wherein the imaging processing module is configured to obtain first 3-D data set {pi} representing the N SIFT features from the first range data frame and second 3-D data set {p′i} representing the N SIFT features from the second range data frame, i=1, . . . , N, N being an integer greater than 1; and
wherein the imaging processing module is configured to determine rotation and translation matrices, R and T, between the first and second intensity data frames by minimizing the error residual e2=Σi=1i=N∥pi−Rqi−T∥2.

### Claim 4 (depends on 3)

The device of claim 3, wherein the SIFT feature detector is configured to execute a transformation procedure including:
randomly selecting four associated SIFT features from the first and second data sets to form {pk} and {p′k}, k=1, . . . , 4;
finding the least-square rotation and translation matrices ({circumflex over (R)}k and {circumflex over (T)}k) for {pk} and {p′k}; and
projecting the first data set {pi} onto the second data set {p′i} using the found transformation ({circumflex over (R)}k and {circumflex over (T)}k) and computing the error
ei2=∥p′i−{circumflex over (R)}kpi−{circumflex over (T)}k∥2
for each data-pair i=1, . . . , N, wherein a threshold ε is used to score Sk and Sk is incremented once for each ei2<ε.

### Claim 5 (depends on 4)

The device of claim 4, wherein the SIFT feature detector is configured to
repeat the transformation procedure for a predetermined number of times and identify the executed transformation having the highest score Sk;
select the corresponding data sets {pj} and {p′j}; j=1, . . . , Sk, wherein each data-pair satisfy the threshold test in the projecting step, and use the selected corresponding data sets to compute the maximum likelihood transformation estimate {circumflex over (R)} and {circumflex over (T)} by the SVD least-square fitting method; and
determine a rotation of the PRD from {circumflex over (R)} and a translation of the PRD from {circumflex over (T)}.

### Claim 6 (depends on 1)

The device of claim 1, wherein the imaging processing module is configured to
execute a construction procedure for a given point in the at least one range data frame including:
mapping the given point to a corresponding point in a color space in accordance with a predetermined rule; and
generating a pixel for the given point using a color represented by the corresponding point in the color space.

### Claim 7 (depends on 6)

The device of claim 6, wherein the imaging processing module is configured to
execute the construction procedure for each point in the at least one range data frame; and
construct a color image using the generated pixel for each point of the at least one range data frame.

### Claim 8 (depends on 7)

The device of claim 7, wherein the imaging processing module is configured to apply a Normalized Cuts method to the color image.

### Claim 9 (depends on 7)

The device of claim 7, wherein the imaging processing module is configured to cluster a color image into a plurality of homogeneous regions by using a Mean Shift method.

### Claim 10 (depends on 9)

The device of claim 9, wherein the imaging processing module is configured to construct a graph by treating each of the plurality of homogeneous regions as a node and recursively partition the graph into two segments using the Normalized Cuts method until each segment is planar or contains only one homogeneous region.

### Claim 11 (depends on 10)

The device of claim 10, wherein the imaging processing module is configured to
fit a Least-Square Plane (LSP) to data points of a given segment, wherein a normal to the LSP is denoted by {right arrow over (N)}=(nx, ny, nz), and a residual of the fit is computed by Δ=√{square root over (Σk=1Pdk2)}/P, wherein P denotes the number of pixels in the given segment and dk is a distance from the kth data point (xk, yk, zk) to the LSP, wherein the LSP is found by a Singular Value Decomposition (SVD) method that minimizes Δ; and
determine that the given segment is a planar segment when Δ is smaller than a predetermined value δ.

### Claim 12 (depends on 11)

The device of claim 11, wherein the imaging processing module is configured to execute a Recursive Cuts procedure comprising:
determining whether a maximum distance between the data points and the LSP is below a threshold δ, and
in response to a determination that the maximum distance is below the threshold δ, exiting the Recursive Cuts procedure.

### Claim 13 (depends on 12)

The device of claim 12, wherein the Recursive Cuts procedure further comprises constructing a graph G=(V,E) by taking each planar homogeneous region as a node and calculate similarities between nodes i and j as:
w
i
,
j
=

-

F

(
i
)
-
F

(
j
)

2
2
σ
F

{

-
d
i
,
j
σ
D
if


V
i


and


V
j


are


neighbors
0
otherwise
,
wherein σF and σD are positive constants, F(p) is the L*u*v color vector of node p for p=i,j, and di,j is a Euclidean distance between the LSPs of the nodes i and j.

### Claim 14 (depends on 12)

The device of claim 12, wherein the Recursive Cuts procedure further comprises:
constructing a graph G=(V,E) including H nodes by taking each planar homogeneous region as a node and calculate similarities between nodes i and j as:
w
i
,
j
=

-

M
i
-
M
j

2
2
σ
M

{

-
d
i
,
j
σ
D
if


V
i


and


V
j


are


neighbors
0
otherwise
,
wherein H is an integer greater than 0, i and j are integers greater than 0 and no greater than H, Mi and Mj are Distance-Weighted Mean Colors, di,j is a Euclidean distance between the LSPs of the nodes i and j,
wherein
M
i
=
∑
k
=
1
n
i


-
d
k
ij

p
k
i
n
i
,
and
M
j
=
∑
k
=
1
n
i


-
d
k
ij

p
1
j
n
l
wherein pki represents the color vector of the kth pixel in node i, wherein Plj represents the color vector of the lth pixel in node j, wherein dkij for k=1, . . . , ni is computed from the kth pixel of node i to cj, and dlji for l=1, . . . , nj is computed from the lth pixels of node j to ci, wherein ni and nj are the numbers of image pixels in node i and node j, respectively, and wherein ci and cj are centroid locations of node i and node j, respectively.

### Claim 15 (depends on 14)

The device of claim 14, wherein the imaging processing module is configured to
apply the Recursive Cuts procedure to the graph G with W as an input to recursively partition the graph G to a set of planar segments S={s1, s2, . . . , sN}, each of which contains a number of homogeneous regions;
construct a binary matrix K to record neighborhood relationships of the segments in S; and
extract entire planar surfaces by merging those segments whose k values equal one.

### Claim 16 (depends on 6)

The device of claim 6, wherein the imaging processing module is configured to map the given point to the corresponding point by using the values of three primary colors of the corresponding point to represent the x, y components of a surface normal {right arrow over (N)}[nx, ny, nz] at the given point and a depth information of the given point.

### Claim 17 (depends on 16)

The device of claim 16, wherein the imaging processing module is configured to use RGB values to represent the given point in accordance with
{
R
=
k
1

cos
-
1

n
x
G
=
k
2

cos
-
1

n
y
B
=
k
3

Y
wherein Y is a depth at the given point, and wherein k1, k2 and k3 are positive constants that scale the RGB values into a range of 0 to 255.

### Claim 18 (depends on 17)

The device of claim 17, wherein the imaging processing module is configured to
execute the construction procedure for each point in the at least one range data frame;
construct a color image using the generated pixel for each point of the at least one range data frame; and
covert the color image to L*U*V color space.

### Claim 19

A smart cane system, comprising
a cane;
a 3-D imaging sensor attached to the cane and configured to acquire intensity data frames and range data frames of an environment of the 3-D imaging sensor, the intensity data frames corresponding to the range data frames;
a portable computing device configured to process the intensity data frames and range data frames as well as detect a pose of the imaging sensor and an obstacle in the environment based on the processing results;
a headset in communication with the portable computing device and configured to output an audio instruction indicting information associated with the pose or the obstacle; and
a tactile device in communication with the portable computing device and configured to output a tactile instruction indicting information associated with the pose or the obstacle.

### Claim 20 (depends on 19)

The smart cane system of claim 19, wherein the 3-D imaging sensor is configured to acquire first and second intensity data frames and first and second range data frames of the environment of the 3-D imaging sensor, the first intensity data frame corresponding to the first range data frame, the second intensity data frame corresponding to the second range data frame;
wherein the portable computing device is configured to
identify a first feature in the first intensity data frame and a second feature in the second intensity data frame that match each other;
obtain a first set of 3-D coordinates representing the first features in the first range data frame and a second set 3-D coordinates representing the second feature in the second range data frame, determine a pose change of the PRD based on the first and second sets of 3-D coordinates; and
perform 3-D data segmentation of at least one of the first and second range data frames to extract planar surfaces from the at least one range data frame.

### Claim 21 (depends on 20)

The smart cane system of claim 20, wherein portable computing device comprises a Scale-Invariant Feature Transform (SIFT) feature detector configured to extract SIFT features in the first and second intensity data frames, wherein portable computing device is configured to identify the first and second features that are SIFT features and that match each other;
wherein the SIFT feature detector is configured to identify N SIFT features in the first intensity data frame and N SIFT features in the second intensity data frame that match to each other, wherein portable computing device is configured to obtain first 3D data set {pi} representing the N SIFT features from the first range data frame and second 3D data set {p′i} representing the N SIFT features from the second range data frame, i=1, . . . , N, N being an integer greater than 1;
wherein the portable computing device is configured to determine rotation and translation matrices, R and T, between the first and second intensity data frames by minimizing the error residual e2=Σi=1i=N∥pi−Rqi−T∥2.

### Claim 22 (depends on 21)

The smart cane system of claim 21, wherein the portable computing device is configured to execute a construction procedure for a given point in the at least one range data frame, the construction procedure including:
mapping the given point to a corresponding point in a color space in accordance with a predetermined rule; and
generating a pixel for the given point using a color represented by the corresponding point in the color space.

### Claim 23 (depends on 22)

The smart cane system of claim 22, wherein the portable computing device is configured to:
execute the construction procedure for each point in the at least one range data frame;
construct a color image using the generated pixel for each point of the at least one range data frame;
cluster the color image into a plurality of homogeneous regions by using a Mean Shift method; and
recursively partition the color image into two segments using a Normalized Cuts method until each segment is planar or contains only one homogeneous region.

### Claim 24

A method of navigation utilizing a navigational device including a 3-D imaging sensor and an imaging processing module, comprising:
acquiring, at the 3-D imaging sensor, first and second intensity data frames and first and second range data frames of an environment of the 3-D imaging sensor, the first intensity data frame corresponding to the first range data frame, the second intensity data frame corresponding to the second range data frame;
identifying a first feature in the first intensity data frame and a second feature in the second intensity data frame that match each other;
obtaining a first set of 3-D coordinates representing the first feature in the first range data frame and a second set 3-D coordinates representing the second feature in the second range data frame, and determine a pose change of the PRD based on the first and second sets of 3-D coordinates; and
performing 3-D data segmentation of at least one of the first and second range data frames to extract planar surfaces from the at least one range data frame.

### Claim 25 (depends on 24)

The method of claim 24, comprising:
extracting, at a Scale-Invariant Feature Transform (SIFT) feature detector, SIFT features in the first and second intensity data frames, and identifying the first and second features that are SIFT features and that match each other;
identifying, at the SIFT feature detector, N SIFT features in the first intensity data frame and N SIFT features in the second intensity data frame that match to each other, wherein the imaging processing module is configured to obtain first 3-D data set {pi} representing the N SIFT features from the first range data frame and second 3-D data set {p′i} representing the N SIFT features from the second range data frame, i=1, . . . , N, N being an integer greater than 1; and
determining, at the imaging processing module, rotation and translation matrices, R and T, between the first and second intensity data frames by minimizing the error residual e2=Σi=1i=N∥pi−Rqi−T∥2.

### Claim 26 (depends on 24)

The method of claim 24, comprising:
executing, at the imaging processing module, a construction procedure for each point in the at least one range data frame, wherein the construction procedure for a given point in the at least one range data frame includes:
mapping the given point to a corresponding point in a color space in accordance with a predetermined rule, and
generating a pixel for the given point using a color represented by the corresponding point in the color space;
constructing a color image using the generated pixel for each point of the at least one range data frame;
clustering the color image into a plurality of homogeneous regions by using a Mean Shift method; and
recursively partitioning the color image into two segments using a Normalized Cuts method until each segment is planar or contains only one homogeneous region.

### Claim 27 (depends on 26)

The method of claim 26, comprising:
fitting, at the imaging processing module, a Least-Square Plane (LSP) to data points of a given segment, wherein a normal to the LSP is denoted by {right arrow over (N)}=(nx, ny, nz), and a residual of the fit is computed by Δ=√{square root over (Σk=1Pdk2)}/P, wherein P denotes the number of pixels in the given segment and dk is a distance from the kth data point (xk, yk, zk) to the LSP, wherein the LSP is found by a Singular Value Decomposition (SVD) method that minimizes Δ; and
determining that the given segment is a planar segment when Δ is smaller than a predetermined value δ.

### Claim 28 (depends on 27)

The method of claim 27, comprising executing a Recursive Cuts procedure including
determining whether a maximum distance between the data points and the LSP is below a threshold λ, and
in response to a determination that the maximum distance is below the threshold λ, exiting the Recursive Cuts procedure;
wherein the Recursive Cuts procedure further comprises (a):
constructing a graph G=(V,E) by taking each planar homogeneous region as a node and calculate similarities between nodes i and j as:
w
i
,
j
=

-

F

(
i
)
-
F

(
j
)

2
2
σ
F

{

-
d
i
,
j
σ
D
if


V
i


and


V
j


are


neighbors
0
otherwise
,
wherein σF and σD are positive constants, F(p) is the L*u*v color vector of node p for p=i,j, and dij is a Euclidean distance between the LSPs of the nodes i and j;
or (b):
constructing a graph G (V,E) including H nodes by taking each planar homogeneous region as a node and calculate similarities between nodes i and j as:
w
i
,
j
=

-

M
i
-
M
j

2
2
σ
M

{

-
d
i
,
j
σ
D
if


V
i


and


V
j


are


neighbors
0
otherwise
,
wherein H is an integer greater than 0, i and j are integers greater than 0 and no greater than H, Mi and Mj are Distance-Weighted Mean Colors, di,j is a Euclidean distance between the LSPs of the nodes i and j,
wherein
M
i
=
∑
k
=
1
n
i


-
d
k
ij

p
k
i
n
i
,
and
M
j
=
∑
k
=
1
n
i


-
d
k
ij

p
1
j
n
l
wherein pki represents the color vector of the kth pixel in node i, wherein Plj represents the color vector of the lth pixel in node j, wherein dkij for k=1, . . . , ni is computed from the kth pixel of node i to cj, and dlji for l=1, . . . , nj is computed from the lth pixels of node j to ci, wherein ni and nj are the numbers of image pixels in node i and node j, respectively, and wherein ci and cj are centroid locations of node i and node j, respectively.
