# US 2014/0152660 A1 · Method for creating 3-d models by stitching multiple partial 3-d models

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

- Number: US 2014/0152660 A1
- Document ID: US20140152660A1
- Status: Published application
- Kind: A1
- Application number: 13/705,013
- Filed: 2012-12-04
- Published: 2014-06-05
- Earliest claimed: 2012-12-04
- Assignees: Fuji Xerox Co., Ltd.
- Applicants: Fuji Xerox Co., Ltd.
- Inventors: David LEE; Donald KIMBER; James VAUGHAN
- Web page: https://patentgrep.com/patent/US20140152660A1

## CPC

- G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts
- G06T 3/4038: Image mosaicing, e.g. composing plane images from plane sub-images
- G06T 7/55: from multiple images
- G06T 11/60: Creating or editing images; Combining images with text
- G06T 2207/10016: Video; Image sequence
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2207/20076: Probabilistic image processing
- G06T 2219/2004: Aligning objects, relative positioning of parts
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method of creating a 3-D model by capturing partial 3-D models each comprising a sequence of 2-D images, analyzing each of the partial 3-D models to identify image features in the sequence of 2-D images of each of the partial 3-D models, identifying pairs of overlapping image features between the 2-D mages of each of the partial 3-D models by identifying image features in each 2-D image in the sequence of 2-D images of each of the partial 3-D models that overlaps image features in 2-D images of the sequence of 2-D images of the other partial 3-D models and selecting a 2-d image from each of the partial 3-D models, computing an initial transformation between 3-D coordinates of individual pairs of identified image features between the selected 2-D image from each of the partial 3-D models; and generating a final 3-D model based on the initial transformation.

## Claims

### Claim 1

A method of creating a 3-D model by combining multiple partial 3-D models, each partial 3-D model comprising a sequence of 2-D images, each 2-D image associated with 3-D coordinates mapped onto the 3-D model, the method comprising:
analyzing each of at least three partial 3-D models to identify image features in the sequence of 2-D images of each of the partial 3-D models;
identifying pairs of overlapping image features between the 2-D images of each of the partial 3-D models by identifying image features in each 2-D image in the sequence of 2-D images of each of the partial 3-D model that overlaps or matches image features in 2-D images of the sequence of 2-D images of the other partial 3-D models and selecting a 2-D image from each of the partial 3-D models;
computing an initial global transformation between 3-D coordinates of individual pairs of the identified overlapping image features between the selected 2-D image from each of the at least three partial 3-D models; and
generating a final 3-D model based on the initial global transformation.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the initial global transformation is computed using a spanning tree to propagate transformations between the overlapping pairs of the at least three partial 3-D models to establish connections between the at least three partial models through a single partial 3-D model that overlaps with a largest number of the other partial 3-D models.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the initial global transformation is refined by optimizing distances between the 3-D coordinates associated with all corresponding pairs of identified overlapping image features across all of the at least three partial 3-D models.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the generating a final 3-D model comprises:
refining, the initial global transformation by optimizing distances between the 3-D coordinates associated with at least 3 pairs of identified overlapping features extracted across all of the at least three partial 3-D models;
computing a final global transformation using iterative analysis to minimize the distance between at least one pair of points in at least two of the partial 3-D models, the pair of points not corresponding to an identified pair of overlapping image features; and
generating the final 3-D model based on the final global transformation.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the computing the final global transformation comprises performing iterative closest points analysis on all points of the at least three partial 3-D models.

### Claim 6 (depends on 4)

The method according to claim 4, wherein the refining the initial global transformation comprises minimizing the function:
min
R
,
t

∑
(
u
,
v
)
∈
pair

∑
(
i
,
j
)
∈
match
u
,
v

(
(
R
u

x
u
,
i
+
t
u
)
-
(
R
v

x
v
,
j
+
t
v
)
)
2
Where:
(u, v) denotes the at least two partial 3-D models having overlapping features,
(i, j) denotes a pair of overlapping features,
xu,i denotes the 3-D coordinate of image feature i of partial model u,
Ru denotes the global rotation of partial model u, and
tu denotes the global translation of partial model u.

### Claim 7 (depends on 1)

The method according to claim 1, wherein the identifying pairs of image features from the sequence of 2-D images of each the partial 3-D models comprises performing principal component analysis on the 3-D coordinates of image features identified as matching between the two or more partial 3-D models.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the selecting the 2-D image from each of the partial 3-D models comprises selecting the 2-D image from the sequence of 2-D images of each of the partial 3-D models, which has the largest value of the image's smallest (3rd) eigenvalue based on a covariance matrix of the 3-D coordinates associated with the image features.

### Claim 9 (depends on 1)

The method according to claim 1, wherein the identifying pairs of image features that overlap or match further comprises performing scale-invariant feature transform image recognition on each 2-D image to identify image features that appear in images of at least two of the partial 3-D models.

### Claim 10

A computer-readable medium having stored therein executable instructions for performing a method of creating a 3-D Model by combining multiple partial 3-D models, each partial 3-D model comprising a sequence of 2-D images, each 2-D image associated with 3-D coordinates mapped onto the 3-D model, the method comprising:
analyzing each of at least three partial 3-D models to identify image features in the sequence of 2-D images of each of the partial 3-D models;
identifying pairs of overlapping image features between the 2-D images of each of the partial 3-D models by identifying image features in each 2-D image in the sequence of 2-D images of each of the partial 3-D models that overlaps or matches image features in 2-D images of the sequence of 2-D images of the other partial 3-D models and selecting a 2-D image from each of the partial 3-D models;
computing an initial global transformation between 3-D coordinates of individual pairs of the identified overlapping image features between the selected 2-D image from each of the at least three partial 3-D models; and
generating a final 3-D model based on the initial global transformation.

### Claim 11 (depends on 10)

The computer readable medium according to claim 10, wherein the generating a final 3-D model comprises:
refining the initial global transformation by optimizing distances between the 3-D coordinates associated with at least 3 pairs of identified overlapping features extracted across all of the at least three partial 3-D models;
computing a final global transformation using iterative analysis to minimize the distance between at least one pair of points in at least two of the partial 3-D models, the pair of points not corresponding to an identified pair of overlapping image features; and
generating the final 3-D model based on the final global transformation.

### Claim 12 (depends on 10)

The computer readable medium according to claim 10, wherein the identifying pairs of image features from the sequence of 2-D of each of the partial 3-D models comprises performing principal component analysis on the 3-D coordinates of image features identified as matching between the partial 3-D models.

### Claim 13 (depends on 10)

The computer readable medium according to claim 10, wherein the selecting the 2-D image comprises selecting the 2-D image from the sequence of 2-D images of each of the partial 3-D models, which has the largest value of the image's smallest (3rd) eigenvalue based on a covariance matrix of the 3-D coordinates associated with the image features.

### Claim 14 (depends on 10)

The method according to claim 10, wherein the identifying pairs of image features that overlap or match further comprises performing scale-invariant feature transform image recognition on each image to identify image features that appear in 2-D images of at least two of the partial 3-D models.

### Claim 15

An apparatus for creating a 3-D Model by combining multiple partial 3-D models, each partial 3-D model comprising a sequence of 2-D images, each 2-D image associated with 3-D coordinates mapped onto the 3-D model, the apparatus comprising:
an image feature analyzer that analyzes each of at least three partial 3-D models to identify image features in the sequence of 2-D images of each of the partial 3-D models;
an overlapping image feature identification device that identifies pairs of overlapping image features between the 2-D images of each of the partial 3-D models by identifying image features in each 2-D image in the sequence of 2-D images of each of the partial 3-D models that overlaps or matches image features in 2-D images of the sequence of 2-D images of the other partial 3-D models and selecting a 2-D image from each of the partial 3-D models;
a controller configured to compute an initial global transformation between 3-D coordinates of individual pairs of the identified overlapping image features between the selected 2-D image from each of the at least three partial 3-D models; and
a display to display a final 3-D model generated based on the initial global transformation.

### Claim 16 (depends on 15)

The apparatus according to claim 15, wherein the controller is configured to refine the initial global transformation by optimizing distances between the 3-D coordinates associated with at least 3 pairs of identified overlapping features extracted across all of the at least three partial 3-D models;
wherein the controller computes a final global transformation using iterative analysis to minimize distance between at least one pair of points in at least two of the partial 3-D models, the pair of points not corresponding to an identified pair of overlapping image features; and
wherein the display displays the final 3-D model generated based on the final global transformation.

### Claim 17 (depends on 15)

The apparatus according to claim 15, wherein the identifying pairs of image features from the sequence of 2-D images that overlap or match comprises performing principal component analysis on the 3-D coordinates of image features identified as matching between the partial 3-D models.

### Claim 18 (depends on 15)

The apparatus according to claim 15, the selecting the 2-D image comprises selecting the 2-D image from the sequence of 2-D images of each of the two or more partial 3-D models which has the largest value of the image's smallest (3rd) eigenvalue based on a covariance matrix of the 3-D coordinates associated with the image features.

### Claim 19 (depends on 15)

The apparatus according to claim 15, wherein the identifying pairs of image features that overlap or match further comprises performing scale-invariant feature transform image recognition on each 2-D image to identify image features that appear in images of at least two of the partial 3-D models.

### Claim 20

A method of providing a viewable 3-D model, the method comprising:
receiving a plurality of 2-D images, each encoded with associated 3-D coordinates in a 3-D space;
analyzing each of the plurality of 2-D images to identify image features in each of the plurality of 2-D images;
identifying pairs of overlapping image features between the 2-D images of each of the partial 3-D models by identifying image features in each 2-D image in the sequence of 2-D images of each of the partial 3-D models that overlaps or matches image features in 2-D images of the sequence of 2-D images of the other partial 3-D models and selecting a 2-D image from each of the partial 3-D models;
computing, by a processor, an initial global transformation between 3-D coordinates of individual pairs of the identified overlapping image features between the selected 2-D image from each of the at least three partial 3-D models; and
providing the final 3-D model in a browsable format based on the initial global transformation.

### Claim 21 (depends on 20)

The method according to claim 20, wherein the providing the final 3-D model comprises:
refining the initial global transformation by optimizing distances between the 3-D coordinates associated with at least 3 pairs of identified overlapping features extracted across all of the plurality of images;
computing a final global transformation using iterative analysis to minimize the distance between at least one pair of points in at least two of plurality of images, the pair of points not corresponding to an identified pair of overlapping image features to create a final 3-D model; and
providing the final 3-D model in the browsable format based on the final global transformation.