Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
ONLINE SHOPPING SYSTEM AND, METHOD USING 3D RECONSTRUCTION
CROSS-REFERENCE TO RELATED APPLICATION
[0001] The present application claims the benefits of U.S. provisional patent
application No. 60/935,765 filed August 30, 2007, which is hereby incorporated
by
reference.
TECHNICAL FIELD
[0002] The present invention relates to an online shopping system and
method using 3D reconstruction. The present invention further relates to a 3D
reconstruction method.
BACKGROUND
[0003] Users are increasingly expecting web-enabled software to be free to
use. It is therefore desirable to pay for the development and operating costs
through other means, such as advertising, which should be finely targeted to
the
actual needs and preferences of each user.
[0004] Common web ad placement services currently rely on a variety of
profiling information to select one or more advertisement for a specific user
at a
specific time and place. This profiling information includes primarily textual
hints
(e.g. the presence of specific words in the text of the website), personal
information entered by the user (e.g. the age and gender), geography (inferred
from the IP address of the client computer) and previous internet browsing
history
(often identified through client-side cookies).
[0005] However, these methods lack the ability to identify new trends, by
exploiting other sources of information such as information contained in
pictures.
[0006] Humans live in a 3D environment and often have to imagine,
compare and communicate ways to improve that environment. This occurs
whenever renovating a home, planning a new office layout, buying new furniture
or
trying to sell a house. Although many tools exist to facilitate these
activities, they
typically require operators to have artistic skills, to learn complex
procedures, to
use non-standard hardware or to spend significant time to reproduce or create
new
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
2
realistic, useful results. As a result, no web-enabled software presently
provides
functionalities supporting such activities and thus or web ad placement
services do
not benefiting from such a source information.
[0007] Some of common tools include computer aided design (CAD)
software and design tools, photogrammetric tools and 3D scanners.
[0008] CAD software and design tools such as AutoCADT'", Punch
SoftwareTM and Googie Sketch-UpTM, which can be used to reconstruct an
existing
environment. These tools require the operator to enter detailed measurements
and
to learn a complex 3D system to use effectively. It therefore takes
significant time
and effort to reconstruct an environment in details.
[0009] Photogrammetric tools, such as PhotomodelerTM from Eos Systems
Inc., allow an operator to interactively recreate a 3D object or environment
using
pictures instead of manual measurements. However, the system requires the
operator to calibrate cameras and manually match correspondence points
between images. This is tedious and repetitive, and requires too much time and
expertise for typical consumers.
[0010] 3D scanners such as the ZScannerTM product line from Z Corp, can
acquire detailed and precise 3D environments. However, compared with standard
digital cameras, these special hardware solutions are expensive, bulky and
hard to
operate. Due to the active nature of the commercial 3D scanners (e.g. the use
of
lasers or light projectors), only the largest and most powerful 3D scanners
can
acquire large scale environments.
[0011] Some automatic 3D reconstruction systems using pictures, with no
operator intervention, can combine the information from a plurality of
pictures to
reconstruct a point cloud and present these pictures interactively. However,
reconstructing a precise 3D textured mesh from this point cloud is non-trivial
and
not demonstrated. Furthermore, these systems suffer from the limitation that,
once
acquired, an environment cannot be edited by the user.
SUMMARY
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
3
[0012] The present invention relates to a system and method that enable
users to reconstruct a precise and realistic virtual 3D representation of an
existing
environment, such as their home, office or other interior, from visual media
such as
photos or video. Once the environment is reconstructed, the user can perform
activities such as visualizing and collaboratively planning virtual
renovations,
seeing and purchasing new furniture and accessories, listing his or her house
for
sale, or share their 3D models and designs, renovation and shopping tips with
friends and the general public. This enables advertisers to advertise to
specific
segments of consumers, according to the content of their environment.
BRIEF DESCRIPTION OF THE FIGURES
[0013] Embodiments of the invention will be described by way of example
only with reference to the accompanying drawings, in which:
[0014] Figure 1 is a schematic view of computing devices connected to a
online shopping and 3D reconstruction system through a network;
[0015] Figure 2 is a flow diagram depicting the process of a user accessing
the online shopping and 3D reconstruction system;
[0016] Figure 3 is a schematic diagram of the online shopping and 3D
reconstruction system;
[0017] Figure 4 is a flow diagram depicting a process used to automatically
reconstruct a 3D environment or 3D products from standard visual media; and
[0018] Figure 5 is a flow diagram depicting a feature matching process used
by the process of Figure 4.
DETAILED DESCRIPTION
[0019] Generally stated, the non-limitative illustrative embodiment of the
present invention provides a system and method that allows a user to
automatically reconstruct an annotated virtual 3D environment from a real
environment, to personalize this environment and to shop, communicate and get
entertained within it. To this end, an online shopping and 3D reconstruction
system
is described which includes a 3D reconstruction algorithm that can reconstruct
one
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
4
or more 3D models precisely and realistically from visual media (e.g. standard
photos or video), with or without human intervention. The system further
includes a
recognition algorithm capable of recognizing 3D objects in a 2D image or 3D
scene, and inferring an entire 3D scene from one or more images. The system
also includes a search engine capable of matching complex visual, textual and
other type of data applicable to searches, automatic recommendation and
advertisement selection.
[0020] Referring to Figure 1, a user using a personal computer 112, laptop
computer 114, a cell phone 115, a tablet computer 116, a personal assistant
device 117, a kiosk or any other such computing device, on which runs a
browser
application, may access the online shopping and 3D reconstruction system 130
through connection server 132 via an Internet connection 120 such as, for
example, Ethernet (broadband, high-speed), wireless WiFi, cable Internet,
satellite
connection, cellular or satellite network, etc. Further to the connection
server 132,
the online shopping and 3D reconstruction system 130 includes a 3D server 134,
a
user database 136 and a 3D content database 138, all of which will be detailed
further below.
[0021] In the following description, for the purpose of clarity, the use of a
personal computer 112 should be construed as to comprise as well a laptop
computer 114, a cell phone 115, a tablet computer 116, a personal assistant
device 117, a kiosk or any other such computing device, on which may run a
browser application.
[0022] In order to interact with the online shopping and 3D reconstruction
system 130, a user's personal computer 112 should run a browser application
compatible with a custom client plug-in that may be automatically downloaded
when the user first connects to the online shopping and 3D reconstruction
system
130. Before the client plug-in is downloaded, the user may be prompted to
accept
the installation on their personal computer 112. The user may then be asked
where to download the plug-in or it may be automatically installed in a
default
location. The plug-in may be automatically updated when necessary, e.g. during
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
visits to the online shopping and 3D reconstruction system 130 or according to
a
given schedule.
[0023] The client plug-in may be a Flash component or a Javascript
implementation, Alternatively, the client plug-in may be replaced by an applet
implemented, for example, in Java.
[0024] In an alternative embodiment, the 3D reconstruction part of the online
shopping and 3D reconstruction system 130 may be implemented as a stand-
alone 'application driven, for example, by DVD-Rom on a personal computer, a
video game console such as the Playstation 3, or a peer-to-peer application.
[0025] Users accessing the online shopping and 3D reconstruction system
130 may be categorized in various classes, each class having a typical usage
scenario, for example:
Guest; a user that has not logged in yet and that can use a
limited subset of the features of the and use the
entertained features of the online shopping and 3D
reconstruction system 130:
Consumer: a user that has logged in and may create a virtual
environment, personalize it, shop within it,
communicate with other users and use the entertained
features of the online shopping and 3D reconstruction
system 130;
Advertiser: a user that can create and monitor advertising
campaigns;
Merchant: a user that can manage and promote an online store
within the online shopping and 3D reconstruction
system 130; and
Professional: a user that has access to special features (e.g. export
plans to AutoCAD).
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
6
[0026] Although each of the above user classes are described separately, it
is to be understood, that a user may belong to more than one class. For
example,
merchants and professionals may also want to advertise their services and
products, in which case a user may belong to the merchant or professional
class
as well as the advertiser class, thus having access to the features of all the
classes the user belongs to. It is also to be understood that some classes may
be
omitted or that additional classes may be added.
[0027] Some features may be restricted to specific user classes (e.g.
merchant, advertiser, etc.). Some features may be charged, e.g. a user may
have
to pay on a per-use basis, using a subscription model or as a reward for
completing some task such as watching advertising or recommending the online
shopping and 3D reconstruction system 130 to some friends and having them
register.
[0028] Users connecting to the online shopping and 3D reconstruction
system 130 may authentify themselves through password, biometrics or other
means. Session information may be stored on the connection server 132, on the
user personal computer 112 or in a combination of both.
[0029] Referring now to Figure 2, there is shown a flow diagram of an
illustrative example of a process 200 executed when a user accesses the online
shopping and 3D reconstruction system 130. The steps of the process 200 are
indicated by blocks 202 to 228.
[0030] The process 200 starts at block 202 where the user connects to the
connection server 132 using a personal computer 112 on which runs a browser
application with the custom client plug-in_ If the user is connecting to the
online
shopping and 3D reconstruction system 130 for the first time, as mentioned
previously, the custom client plug-in may be automatically downloaded or the
user
may be prompted to accept the download.
[0031] At block 204, the user is given the opportunity to log into the online
shopping and 3D reconstruction system 130 using an assigned login and
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
7
password (or by any other means such as, for example, biometrics). If the user
logs in the connection server 132 validates the login and password of the user
by
querying the user database 136 which, if the user is registered, sends back
information associated with the user such as, for example, the user profile,
preferences, class or classes, etc., and then proceeds to block 212,
[0032] If the user does not log in he is given the opportunity, at block 206,
to
register into online shopping and 3D reconstruction system 130. If the user
chooses to register, the process 200 proceeds to block 210 where the user
registers into the online shopping and 3D reconstruction system 130 after
which
the process 200 proceeds to block 212. If the user chooses not to register,
the
process 200 enables, at block 208, the guest activities for that user and then
proceeds to block 228.
[0033] At block 212, the process 200 verifies if the user belongs to the
consumer class. If so, at block 214, the process 200 enables the consumer
activities for that user. The process 200 then proceeds to block 216.
[0034] At block 216, the process 200 verifies if the user belongs to the
professional class. If so, at block 218, the process 200 enables the
professional
activities for that user. The process 200 then proceeds to block 220.
[0035] At block 220, the process 200 verifies if the user belongs to the
advertiser class. If so, at block 222, the process 200 enables the advertiser
activities for that user. The process 200 then proceeds to block 224.
[0036] At block 224, the process 200 verifies if the user belongs to the
merchant class. If so, at block 226, the process 200 enables the merchant
activities for that user. The process 200 then proceeds to block 228.
[0037] Then, at block 228, the process 200 displays a menu of activities
available to the user depending on the class(es) the user belongs to through a
user interface (UI) which will be further detailed below.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
a
[0038] Referring to Figure 3. the user may then interact with the online
shopping and 3D reconstruction system 130 through the UI 27 using the
available
list of activities determined at block 228 of Figure 2. The UI 27 is composed
of a
dynamic website on the connection server 132 and a 3D engine 28 (possibly
included in a plug-in) that allows the user to interactively navigate and
personalize
aspects of a 3D environment 38 or 3D products 39 offered for sale or display
using
a web browser on his or her personal computer 112 (see Figure 1). These 3D
environments 38 and 3D products 39 may be created by some process 32 external
to the online shopping and 3D reconstruction system 130, e.g. by a specialized
artist or 3D scanner imported from external applications or devices through
the
import module 31. They may also be created manually by a user of the consumer
class through a process used to personalize an existing environment, i.e. the
personalize function 15 of the consumer activities module 14.
[0039] The previously mentioned creation techniques can produce results of
acceptable quality given enough time and money, but are too complicated, too
labor-intensive and too costly for most users. For this reason, the online
shopping
and 3D reconstruction system 130 also includes a 3D reconstruction module 11
that can automatically reconstruct a 3D environment 38 or 3D products 39 from
standard visual media 10, such as a few pictures or a short video, submitted
through the UI 27. The 3D reconstruction module 11 can also accept user
commands to increase its precision, robustness or performance. Additionally, a
recognition module 12 may be used in order to recognize 3D products 39 present
in the 3D environment 38 or map products identified in the input visual media
10 to
3D models that have been learnt from other input visual media or from other
environments. This also allows the recognition module 12 to automatically
reconstruct a precise 3D environment 38, including individual 3D products 39
with
their associated 3D poses, from a single image. The recognition module 12 may
also compare an image with any object currently in the 3D content database 138
and return a probability that the object is present in the image. The 3D
reconstruction 11 and recognition 12 modules with be further detailed below.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
9
(0040] Once a 3D environment 38 has been created, a user, for example a
consumer (we will thereon suppose that the user is of the consumer class), may
personalize various aspects of it such as, for example, the color of the
walls,
furniture placement, etc, using the personalize function 15 of the consumer
activities module 14. To add new furniture, the consumer may initiate a search
or
ask the system for a recommendation, which ultimately will result in one or
more
queries to the search engine 37 with criteria that may include text, images,
colors
and texture. The results of some of these queries may be retrieved directly
from
the 3D content database 138. Others may be evaluated using the inference
engine
43 which applies inference rules 44 to perform data mining on known
information,
e.g. the colors of objects present in a room or the probabilities returned by
the
recognition module 12, to produce new probabilistic results.
[0041] The consumer may also use the shop function 16 to shop for new
products within a 3D environment 38. To find products of interest, the
consumer
may use the search capability provided by the search engine 37, ask the online
shopping and 3D reconstruction system 130 for recommendations that would fit
his
or her taste, follow a link seen through an advertisement or through another
3D
environment, or browse through the available 3D products 39 and compare by
category, price or other criteria. Once found, a product can be added in the
selected 3D environment 38 and, if the product is available for sale, the
consumer
may select an appropriate merchant from the merchant data 40 of the user
database 136 and place an order which may be fulfilled by the selected
merchant
through the online shopping and 3D reconstruction system 130 itself or through
a
third party. The consumer may enter his or her personal data 41 (e.g. name,
address, payment information) in the user database 136 only once, e.g. at the
time
of his or her first order. For external merchants (merchants that operate
their own
e-commerce website), the online shopping and 3D reconstruction system 130
regularly imports through the import module 31 internal merchant data 40 (e.g.
price, product availability and new products). Orders to external merchants
are
submitted through the export module 30.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
[0042] Consumers may also use the communication 17 function of the
consumer activities module 14 to communicate with each other through common
means (e.g. message boards, chat, reviews) and other means such as 3D chat
and by collaboratively designing shared 3D environments 38. Special versions
of
the UI 27 may also be integrated in other websites, applications or devices,
allowing, for example, a retailer to host a branded version of the 3D
technology on
their website. In another example, consumers who participate in social
websites
could integrate their personal 3D environment 38 in their personal web page
within
the social website, or have their friends from the social website be notified
of
actions such as creating a new 3D environment 38 or purchasing new 3D products
39.
[0043] Any activity (e.g. clicks, selections, modifications) performed by a
consumer may be collected in the corresponding consumer data 41 of the user
database 136, e.g. to be used as input to the inference engine 43, to
reproduce
problems or to allow the user to undo recent steps. It is to be understood
that
activities performed by other types of users, e.g. merchants, advertisers and
professionals, may also be collected in the corresponding merchant 40,
advertiser
42 and professional 45 data of the user database 136 for the same purpose.
[0044] Consumers may also get entertained using the entertainment
function 18 of the consumer activities module 14. For example, they may play
games in a virtual environment. They may also export and/or integrate the 3D
environment 38 inside games and other applications and devices such as, for
example, The SimsTM, Google EarthTM, real-estate sites such as MLS, etc.
[0045] Other uses could include performing scientific and engineering
simulations, such as simulating a fire or an earthquake in an environment,
Users
belonging to the professional class of users, such as professional interior
architects and designers, may perform more advanced design activities, such as
designing the air conditioning or electrical subsystem inside a given 3D
environment 38 or printing poster-quality renders of a 3D environment 38.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
11
[0046] The 3D engine 28 may communicate with the 3D content database
138 directly, or may request data from one or more 3D content server 29 to
increase the overall system's performance and robustness. In the illustrative
embodiment, a 3D content server 29 stores 3D data in a file format
semantically
similar to COLLADA, which may optionally be binarized, compressed and
encrypted. Multiple 3D content servers 29 containing read-only copies of a
given
3D object (e.g. 3D environments 38 or 3D products 39) may be used, allowing
multiple 3D engines to read data from any server. For each 3D object, one 3D
content server 29 is then defined as authoritative and handles write
operations
such as modification and creation of new 3D objects. The 3D content servers 29
are updated asynchronously, using a low-priority process. When a 3D content
server 29 goes down or is overloaded, the authority for its 3D objects is
transferred
to another 3D content server 29, providing load balancing.
[0047] Special functions may be offered to some user classes such as the
advertiser and merchant classes. For example, advertiser related functions
from
the advertiser activities module 20 and merchant related functions from the
merchant activities module 23. Advertisers have access to an expanded UI 27
that
allows them to use the manage campaigns function 21 and the monitor campaigns
function 22. Likewise, merchants may use the manage stores function 24 and
monitor stores function 25.
[0048] Another class of users which may have access to special functions is
the professional class. For example, a professional may have access to,
through
the professional activities module 54, functions such as the personalize
function
55, the design function 56, the communicate function 57 and the import/export
files
function 58. The personalize 55 and communicate 57 functions may be similar to
those already described for the consumer class of users, i.e. 15 and 17. As
for the
design function 56, as mentioned previously, this function may be used to
perform
advanced design activities, such as designing the air conditioning or
electrical
subsystem inside a given 3D environment 38. As for the import/export files
function 58, it may be used, for example, to import a 3D environment 38
through
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
12
the import module 31, modify it and then exporting it to another system,
application
or device using the export module 30-
(0049] Data stored in the 3D content database 138 may be imported via the
import module 31 using a combination of techniques such as manual entry by a
user, import from external sources of data using web services, XML databases,
web crawling and screen-scraping, etc.
Scenegraph and 3D engine
[0050] Displayable objects. such as 3D environments 38 and 3D products
39, include attributes such as:
= local 3D transform, e.g. allowing an object to be moved and oriented;
= reference to children objects, allowing a hierarchical scenegraph to be
built and maintained, e.g. a door typically has a handle;
= reference to a material;
= texture coordinates, imported or generated automatically, e.g. by the 3D
reconstruction tool 11;
= attributes specific to the given object, e.g. a door may have options such
as whether or not it includes a window. When the window option is
enabled, a child window is automatically created and parented under the
window object. A rule-based system also allows an attribute to affect
other attributes and children attributes, e.g. a sofa may be available in
several standard dimensions and colors.
Material
[00511 The overall look of 3D products 39 (excluding fighting effects) is
called the material. A material includes variations of color, texture, fabric,
paint,
finish, etc.
[0052] Displayable objects, e.g. 3D products 39, typically have one or more
materials assigned to them. Optionally, it can also have standard material
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
13
variations. For example, the type of wood and the finish of a piece of
furniture may
be selected by the consumer from some list.
[0053] Additional materials can be applied on top of an existing material by a
consumer (or professional). For example, a chair could be covered with paint
or
even with carpet, tinfoil or cement. These materials can be created from
scratch or
they can be copied from other 3D products 39, from a material library, etc.
[0054] Materials have properties such as:
= shaders, e.g. Phong or programmable;
= numerical values, e.g. reflectivity, diffuse and specular color:
= one or more texture maps (optional); and
= animation parameters (optional).
3D engine
[0055] The 3D engine 28 takes a scenegraph representation as input and
produces one or more image. The 3D engine 28 may also include an input
mechanism, e.g. to allow users to select, move and personalize objects. The 3D
engine 28 may also support state-of-the-art features such as global
illumination,
subsurface scattering, tone mapping in order to produce a photorealistic
result at
interactive rate- To prevent lag when loading models, the 3D engine 28 may use
pre-loading, e.g. when doing a search for 3D products 39, the 3D engine 28 may
immediately start downloading the visible results from a 3D content server 29
since it is likely that a consumer will want to examine and possibly add one
of
them.
3D environment
10056] A user has several options in order to create a 3D environment 38.
For example, the user may use the personalization function 15 (see Figure 3)
to
create a 3D environment 38 from scratch, by first drawing floor plans, then
placing
windows, doors, etc. Other systems known in the art may also be used for this
purpose, for example US Patent No. 7,277,572 entitled "Three-dimensional
interior
design system".
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
14
Create a 3D environment from scratch
[00571 First, a 2D floor layout is created. This may be accomplished using a
feature sets similar to those of other 2D illustration tools such as Adobe
IllustratorTM. The user can draw individual edges or polygons that are
completed
automatically. A brush is selected to change mode between drawing walls,
doors,
windows, etc. Doors and windows are given standard dimensions that can
optionally be overridden by the user. Rooms and other objects can be named and
the name, as well as automatically computed dimensions, are automatically
displayed in the center of each room. Typical visual ruler and grid snapping
tools
are provided. Default units are selected according to the user's geography.
Optionally, an image may be used as a background, e.g. blueprint of a room.
Optionally as well, snap edge orientation to 10/20130/45/90 degrees and snap
to
closest corner/edge may be used.
[0058] Fill up walls with windows and doors, floor with carpet and wood.
Wall height can be specified by user; otherwise a default height is used.
Lengths
may be specified numerically.
[0059] Special tools may be provided to build parametric fixtures such as
staircases, kitchen cabinets, etc. Features that are common in home design
tools
such as Punch!TM and Home ArchitectTM can also be integrated within the online
shopping and 3D reconstruction system 130. For example, the exterior of the
house may be specified using a similar interface as the interior. The ideas
described herein may also be applied to designing other 3D environments
including but not limited to cars, boats, airplanes, gardens, factories,
schools,
hospitals, restaurants, etc.
Other ways of creating a 3D environment
[0060] Instead of starting from scratch, a user may select one or more
existing 3D environment 38. Users can locate an existing 3D environment 38
through a variety of means including the search engine 37, links to external
websites or emails. Elements of a specific 3D environment 38 can be cut-and-
pasted into a different one. Links to existing 3D environment 38 may be
provided
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
by other users, e.g. fellow consumers or professionals (for example real-
estate
agents).
[0061] A 3D Environment 38 may also be acquired through other sources of
3D data, such as traditional 3D active scanners, stereoscopic rigs, data
captured
from a 3D software (e.g. OpenGL driver) or hardware.
3D reconstruction module
[0062] Referring now to Figure 4, there is shown a flow diagram of an
illustrative example of a process 300 used by the 3D reconstruction module 11
to
automatically reconstruct a 3D environment 38 or 3D products 39 from standard
visual media. The steps of the process 300 are indicated by blocks 301 to 319.
[0063] The process 300 starts at block 301 where the 3D reconstruction
module 11 is provided visual media data consisting of at least one image, in
the
form of an unsorted sequence of images, or at least one video. Optionally, at
block
302, the 3D reconstruction module 11 may be provided with additional
information
to increase the reconstruction speed, precision or robustness. The additional
information may include, for example:
= EXIF tags, which are automatically written by most digital cameras,
typically include camera parameter such as field of view, GPS and
compass data, presence of options such as flash, etc. These
parameters may be used as priors by further modules, e.g. to
compute an approximate intrinsic or extrinsic matrix; and
= user-provided hints (for example the user could provide
measurements such as the ceiling height and could also click on a
wall on a picture to indicate that the stated wall is facing North).
[0064] Optionally, the process 300 may perform, at block 303, distortion and
blur correction. The correction may be performed using one or more algorithms.
For example, the distortion correction may be performed by using the EXIF tags
directly. Alternatively, an optimization technique may be used to maximize
straight
edges. To this end, the user could provide pictures of a calibration rig (e.g.
a grid)
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
16
from which the distortion parameters may be robustly estimated. A database of
known lenses parameters could also be consulted and updated on demand by first
identifying the camera and lens name. Motion blur due to camera shake may be
reduced using, for example, the technique described in the paper entitled
"Removing camera shake from a single image" by Rob Fergus, Barun Singh,
Aaron Hertzmann, Sam T. Roweis and William T. Freeman [1]. This step may be
omitted if the distortion and blur are considered negligible, e.g. by using a
tripod
and corrective lenses. The result of this step may take the form of a
corrected
image and/or a transformation function that maps input pixels in output pixels
and
vice-versa.
[00651 Optionally, at block 304, an automatic or user-provided 2D
segmentation step may be performed, which may make the feature matching of
upcoming block 305 more robust, e.g. to background clutter. The result of this
segmentation process is a list of layers (optionally with partial
transparency). Each
layer can then be fed separately to the feature matching of block 305, to
produce
points and region descriptors for each layer, eliminating the impact of
background
clutter. A number of automatic segmentation and low-level object detection
algorithms could be used, such as the algorithms described in "Background
cutout
with automatic object discovery" by David Liu and Tsuhan Chen [2] and in
"TextonBoost for Image Understanding: Multi-Class Object Recognition and
Segmentation by Jointly Modeling Texture, Layout, and Context" by J. Shotton,
J.
Winn, C. Rother, and A. Criminisi [3].
[0066] The user may also provide additional information to assist the
segmentation algorithm, e.g. draw simple marks or an approximate box over
different layers, which may then be used as input for a semi-interactive
algorithm,
such as described in, for example, "Lazy Snapping" by Yin Li, Jian Sun, Chi-
Keung
Tang, and Heung-Yeung Shum [4] and "GrabCut - Interactive Foreground
Extraction using Iterated Graph Cuts" by Rother, Kolmogorov and Blake [5].
[0067] At block 305, feature matching is applied, which may use one or
more types of features to identify correspondence points and edges in order to
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
17
estimate camera calibration parameters. Pairs of images are considered in an
order, e.g. provided by the user, by their time EXIF tag or by sorting them
according to the similarity of their image or detected features. The feature
matching process then returns of probable features, expressed in pixel and/or
relative 3D space, a list of camera matrices (possibly including intrinsic and
extrinsic matrix) and a probability that the two images were matched properly.
The
feature matching process will be further detailed below.
[0068] At block 306, bundle adjustment or another type of global
optimization algorithm may be performed in order to combine more than two
matched images to further refine the 3D reconstruction and reduce the
reconstruction error. The frequency of this process may vary to balance
between
quality and reconstruction speed. For example, the bundle adjustment may be
performed after every pair of image has been matched, every few images, or
once
at the end. Several successive passes of feature matching and bundle
adjustment
can be performed to find more features of correspondences and match pairs of
images that may otherwise have been impossible to match without knowing the
approximate camera pose.
[0069] Then, at block 307A, a deeper reconstruction, e.g. deep stereo
reconstruction, may then be applied to produce many more feature matches. For
example the algorithm described in "Accurate, Dense, and Robust Multi-View
Stereopsis" by Yasutaka Furukawa and Jean Ponce [6] may be used. The
application of such an algorithm may result in a dense reconstruction in an
intermediate output form such a depth or disparity maps, or to a dense patch
cloud. Although it may be possible to display many of these formats
interactively, it
may be advantageous to convert the reconstruction into a standard textured
mesh
using mesh generation, which will be performed at block 308, since most
rendering
algorithms are designed to function with this type of data.
[0070] Optionally, at block 307B, a 3D segmentation may be performed. The
end result is one or more segmented 3D data (e.g. patches or meshes if the
operation was performed after the mesh generation of block 308) that
correspond
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
18
to semantically different parts, e.g. a floor, walls, ceiling and individual
pieces of
furniture. To perform this function, recognition and isolation of parts is
first
attempted using the recognition module. Parts that are not recognized may then
be inputted into a general-purpose 3D segmentation algorithm such as, for
example, the one described in "Partitioning 3D Surface Meshes Using Watershed
Segmentation" by Alan P. Mangan and Ross T. Whitaker M.
[0071] At block 308, the mesh generation may vary in implementation
according to the type of data output by the dense stereo reconstruction. In
this
example, a point cloud is generated by the dense stereo reconstruction
algorithm
and a Poisson Surface Reconstruction is performed to produce an optimal
surface.
An optional sub-step would be to fill holes by examining the nearby geometry
and
local curvature, matching some standard shapes such as piece-wise planar
intersections and conics, and filling up the missing geometry accordingly.
This
would allow, for example, pipes sections to be rendered perfectly cylindrical.
[0072] Then, at block 309, texture coordinates may be generated
automatically, e.g. using, for example, Bruno Levy's "Least Squares Conformal
Maps for Automatic Texture Atlas Generation" [8]. Colors and textures may be
interpolated from source points or projected back from source images. Holes in
the
texture space (e.g. due to missing data, such as part of the surface of the
floor
hidden below a carpet) may be filled (e.g. using an inpainting technique such
as
described, for example, in "Image Inpainting" by M. Bertalmlo, G. Sapiro, V.
Caselles and C. Ballester [9] or may be flagged (e.g. in a high-contrast
color) to
indicate to the user the locations where more pictures should be taken.
[0073] At block 310, the illumination, albedo and reflectance can then be
estimated by proceeding with lighting estimation. For example, this may be
achieved using the algorithm described in "Sparse Lumigraph Relighting by
Illumination and Reflectance Estimation from Multi-View Images" by Tianli Yu,
Hongcheng Wang, Narendra Ahuja and Wei-Chao Chen [10]. The final result is a
mesh with albedo and reflectance texture that may be used directly by the
online
shopping and 3D reconstruction system 130 or other 3D applications, to
reproduce
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
19
a 3D environment 38 or 3D products 39. This step may optionally produce a
detailed bump map that can further increase the realism of the reconstructed
object.
[0074] For the 3D reconstruction to be scaled and oriented properly,
additional data may be provided by the user, at block 311, to a 3D alignment
process at block 312. This process may also infer the alignment directly from
the
reconstructed 3D data or from the input images. As an example, a rule-based
approach could combine simple rules such as assuming that the ceiling
generally
points up in pictures, that the ceiling lies on the smallest axis when
measured
against the width or height of a room, or that the ceiling has little or no
furniture or
fixtures on it, and conversely that floors have furniture on them. The scale
may be
probabilistically inferred from furniture size, door size, beds (since four
standard
sizes exist in the USA and they can be readily recognized from their
proportions),
etc. These rules can be learnt probabilistically from existing rooms, e.g.
through
Bayesian or Markovian techniques, allowing the 3D reconstruction process 300
to
get better at guessing dimensions and orientation.
[0075] As another example, the north facing wall may be assumed to be the
wall directly in front of the first picture, or could be inferred by comparing
the
brightness of different windows and by estimating the sun's general direction
according to the time of day at which the picture was taken. The user may also
provide more information, such as georeferenced coordinates of specific points
or
additional distance measures, to further increase the reconstruction precision
and
to allow the environment to be positioned precisely relative to other
georeferenced
environments or objects.
[0076] The 3D environment 38 and/or 3D products 39 are then produced at
blocks 313 and 314, respectively.
[0077] The 3D products 39 may then be provided to block 315 where a
recognition engine may use one or more image-based or geometry-based
algorithms to produce partial or complete matches and/or to identify
significant
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
hierarchical parts and variations. For example, two algorithms may be used:
one
using 2D images an input, the other using a 3D mesh.
[0078] The recognition may be performed directly from 2D images using
automatic image recognition algorithms such as, for example, Fabien Scalzo's
"Learned Hierarchical models" [11] or algorithms designed for the Pascal VOC
challenge [12]. Accessing, at block 316, the 3D products 39 in the 3D content
database 138 and given enough sample images, the algorithm automatically
learns a hierarchical image-based recognition model for each of the 3D
products
39 in the 3D content database 138. Given sets of sample images in different
poses, the algorithms can identify 3D products 39 from the 3D content database
138 in a given image, returning, at block 319, a match probability and
optionally, at
block 318, a 3D pose.
[0079] Running a recognition algorithm on each input image may increase
the robustness and precision. For example, if three images agree that it is
highly
probable that a specific chair is present in the image with similar poses,
this
information may be combined (e.g. minimize error using least square methods)
to
identify a more precise 3D pose. To identify the precise 3D pose, a pose
estimation may then be performed using the random sample consensus
(RANSAC) algorithm in a manner analogous to camera pose estimation. Provided
that enough representative objects have been learnt, the algorithm described
can
reconstruct a complex 3D scene using a single image.
[0080] The recognition engine may also perform a 3D recognition using a
3D shape matching algorithm such as, for example, the algorithm described in
"Symmetry descriptors and 3D shape matching" by Kazhdan, M,, Funkhouser, T.
and Rusinkiewicz, S [13], using as shapes the 3D products 39 from the 3D
content
database 138.
[0081] Even in cases where the recognition engine is not able to return
exact matches, as long as it produces probabilistic matches that are more
frequently right than wrong the matched probability provides valuable
information
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
21
for some types of applications. For example, the most probable matches could
be
used as a criteria for choosing advertisements or to populate a list of
products that
are likely to interest the user, e.g. when he fills up a room. The
advertisements
selected this way would likely be more focused on their target market than
completely random selections, and therefore have more value for advertisers.
[0082] It should be noted that a large variety of other algorithms, methods
and apparatus may be used to produce suitable 3D meshes or may be used as
input to the recognition engine of block 315. The implementation described
above
can robustly reconstruct and recognize a large variety of 3D environments 38
and
3D products 39 with uncalibrated wide-baseline images from a normal camera,
with minimal user input. With the use of special equipment or of more
laborious
manual processes, other possible 3D reconstruction algorithms, methods or
apparatus, for example 3D , modeling software such as AutoCADTM or
PhotomodelerTM, or apparatus such as a 3D scanner or a calibrated stereoscopic
rig, could be included at block 311.
Feature matching
[0083] Referring to Figure 5, there is shown a flow diagram of an illustrative
example of a feature matching process 400 that may be used at block 305 of
Figure 4. The steps of the process 400 are indicated by blocks 401 to 410.
[0084] The process 400 starts by detecting common feature descriptors
such as points and regions (e.g. local invariant feature algorithms such as
SIFT
and MSIER), at block 401, and edges, at block 402.
[0085] At block 403, putative features are detected and then matched, e.g.
through cross-correlation using various distance functions. This process may
be
optimized using high-dimensional acceleration structures such as K-D trees.
Putative edges can be further matched using approximate parallel and vanishing
point constraints.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
22
[0086] At block 404, through a projection process, matched edges can
produce intersection points that may not be visible in the original images
(e.g.
occluded or outside of the original image) but may provide additional
precision for
the outliers elimination process of block 406.
[0087] The putative feature points obtained, at block 405, will generally
generate a large number of outliers (i.e. false matches) which may be
eliminated,
at block 406 by applying an outliers elimination process. This process may be
implemented by minimizing the fundamental matrix estimation error, e.g. using
a
RANSAC algorithm or more involved algorithms such as degenerate sample
consensus (DEGENSAC) or quasi-degenerate sample consensus (QDEGSAC)
algorithms, for increased robustness to (quasi-)planar scenes.
[0088] Once an acceptable consensus has been found (e.g. with an error
lower than a pre-determined setting), the process 400 may proceed back to
block
403 for a new pass of feature matching, taking into consideration the
approximate
epipolar constraint to find new matches and eliminate incorrectly matched but
otherwise similar features. This loop may occur until convergence or after a
pre-
determined number of iterations or a predetermined time period has elapsed. If
the
error is still too large, the matching process may have insufficient or
incorrect input
data, e.g. if the two images have no points in common. This specific image
pair
can be ignored accordingly since the individual images are likely to match
others if
the user has taken enough pictures covering the entire object or environment
of
interest.
[0089] Once a good number of inlier matches have been identified, at block
407, a camera estimation process estimates the relative camera position and
orientation corresponding to the second image. Details of the process may be
found, for example, in "Multiple View Geometry in Computer Vision, 2"d
edition" by
Richard Hartley and Andrew Zisserman [14]. Other types of features, such as
detected curve segments, may be used to produce more correspondences that
could increase the quality of reconstruction. If successful, the final output
of the
feature matching process 400 is a list of probable features, at block 408,
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
23
expressed in pixel and/or relative 3D space, a list of camera matrices, at
block
409, (possibly including intrinsic and extrinsic matrix), and a probability,
at block
410, that the two images were matched properly.
[0090] If the 3D reconstruction process 300 executed by the 3D
reconstruction module 11 is expected to take a noticeable time to perform
(e.g.
more than one second), the user may be notified of its progress or completion,
e.g.
by email, using a progress bar or through an audio notification. A visual
preview
may be shown to the user as the 3D reconstruction process 300 progresses. This
visual preview may be displayed in a combination of 2D (e.g. top or elevation
view), in 3D or using a stereoscopic display. The 3D reconstruction process
300
may also be done in-line, while recording a video or taking pictures, and the
online
shopping and 3D reconstruction system 130 may notify the user once enough data
has been recorded and analyzed.
[0091] Multiple options may be provided to the user or may be adjusted
automatically to control the level of realism and precision versus processing
time.
The 3D reconstruction process 300 may be implemented in an iterative approach,
wherein each iteration may increase the reconstruction precision. For example,
this may allow users to get a fast, draft-quality reconstruction in a few
seconds,
and to automatically update to a high-precision reconstruction at a later
time.
[0092] For the sake of simplicity, the illustrative embodiment disclosed
herein describes the 3D reconstruction process 300 operations as sequential.
It is
to be understood that many of the operations may be optional, may be run more
than once or in parallel (including on more than one computing device, such as
CPUs and GPUs), or be ordered differently. For example, the 3D segmentation
process at block 307B may be performed before or after the mesh generation at
block 308, and after the recognition engine at block 315. Furthermore, new
optional operations may be inserted in between. Without limiting the scope of
the
present invention, the 3D reconstruction process 300 may be integrated inside
a
device (e.g. embedded inside a digital camera or cell phone) or exposed as a
web
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
24
service, as a peer-to-peer or as stand-alone application, or as a plug-in to a
CAD
application-
Viewing and selecting objects
[0093] Users can select one or more 3D products 39 (e.g. wall, furniture,
accessory) through several mechanism, e.g. by clicking its surface in a 2D or
3D
view, by searching by name or by selecting scenegraph nodes in a tree-view.
[0094] To view a specific wall, two navigation modes are presented to the
user: orthogonal (2D projection) and perspective. The orthogonal view is by
default
oriented to face the planar surface and allows the user to zoom, pan and
rotate the
camera in 2D (similarly to IllustratorTM). The perspective view is in complete
control
of the user and can be used to manipulate non-planar surfaces, e.g. curved
walls,
[0095] Several mechanisms allow the user to show and hide specific 3D
products 39 according to context. For example, 3D products 39 can be assigned
manually by the user to a "user display layer" and the display layers can be
enabled/disabled to show/hide many objects. A "category display layer" allows
users to globally hide specific 3D products 39 such as furniture, accessories,
etc.
An "isolate selected" mode is also available, with several possible settings:
isolate
selected, isolate selected and neighbors. Isolate selected only shows the
selected
object, e.g. wall. Isolate selected with neighbors shows neighboring sections
of
connected walls, ceiling and floor to allow the user to visualize the selected
wall in
context. Finally, if the option is disabled, all 3D products 39, including
furniture, are
shown.
Modifying walls, ceiling and floor
[0096] Walls, ceiling and floor (e.g. portions of a 3D environment 38) may be
modified in similar ways and will described globally as "room surfaces". Most
of
these surfaces are roughly flat and can be described with a closed polygon.
Optionally, the surfaces can also be curved in 3D space and described with a
parametric surface representation (e.g. nonuniform rational B-splines
(NURBS)).
Any representation may be used as long as the positions in 3D space can be
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
picked and the representation subdivided using constructive solid geometry
(CSG).
[0097] There are many ways to modify the properties of a room surface. The
three most common options are:
manually subdivide a room surface (e.g. by drawing a line or curve
that divides an object in two), then modify attributes on a subdivided
surface;
drag-and-drop an object onto a wall (some objects, such as windows
and doors, will trigger an automatic subdivision operation, others,
such as paintings and blinds, will simply attach to the wall); and
= subdivide implicitly for hierarchical objects (many objects are defined
hierarchically, for example a wall can have optional borders on top
and at the bottom, when one of these borders are enabled the
central wall surface is automatically divided and the user can then
further modify the parameters of one of the borders, e.g. the profile,
material or dimensions.
Modifying furniture, accessories and lights
[0098] Furniture (e.g. 3D products 39) may be found and selected by a user
in many ways, e.g.: from lists, by drag-and-dropping from other rooms, and
through search queries.
[0099] Furniture can generally be personalized. For example, the material of
most 3D products 39 can be overridden by the user to simulate adding a coat of
paint or covering it with a fabric.
[00100] Some furniture are defined hierarchically and contain several parts.
some of which are optional. For example, a chair may contain a seat, one or
several legs, a back, arm rests and a cushion.
(00101] Other furniture are "generic": they are used when no real-life
equivalent exists in the 3D content database 138, and their material and
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
26
.dimensions are customizable by the user. A generic sofa has parameters to
adjust
its width, height, the shape and material of cushions, etc.
3D products placement
[00102] 3D products 39 can be positioned and oriented using visual
manipulators similar to those of Maya TM or 3ds MaxTM.
[00103] Many 3D products 39, such as pieces of furniture, can "snap" onto
other specific 3D products 39. Optionally, the 30 products 39 may snap in
specific
locations and/or re-orient themselves. For example, a bookshelf snaps to the
closest nearby wall (so its back touches it) and snaps vertically onto the
floor.
Accessories snap vertically to stand on the floor, on a piece of furniture,
etc.
Lights and environment
[00104] Some 3D products 39 can be modeled to include light sources. For
example, the light bulb in a table lamp can be modeled as a point light source
or
spot light source parented under the lamp. The illumination of the sun, the
moon or
other environment lighting can be simulated. The rendering quality can be
adjusted
and multiple renderers can be used to produce more realistic results.
Search, inference and advertising
[00105] Many user activities and modules rely on the capability to find 3D
products 39 of a given type with desired characteristics. For example, user-
requested searches, user-requested recommendations and advertisement
selection functionalities all benefit from this capability. This capability is
largely
handled by the search engine 37 (see Figure 3).
[00106] Users can search for 3D objects 39 using a simple text string (since
each product has associated text strings such as, for example, a name, a
description, an author name, etc.), or may use more complex search criteria
types
such as desired colors, dimensions, desired rating (derived from user
reviews),
manufacturer name, etc.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
27
[00107] Each search criteria type may have one or more special visual
interfaces exposed through the Ul 27. For example, a color histogram could be
specified using a color wheel or a color histogram curve.
[00108] Many search criteria types may be converted from another type. For
example, a color histogram may be computed from a user-provided picture. Color
histograms may be converted to and from textual color names using a look-up
table, possibly in a language-specific way.
[00109] Queries are handled using an extended version of SQL. Parameters
may come directly from the 3D content database 138 or be computed by the
inference engine 43. Special comparison operators may exist for some criteria
types- For example, the colors may be compared using a histogram difference in
hue-saturation-value (HSV) color space, allowing different objects (e.g. a
lamp and
a carpet) to be compared color-wise.
[00110] To produce arbitrarily complex search queries, the search engine 37
can be combined with the inference engine 43. The inference engine 43 uses
inference rules 44 to discover new patterns in the existing data of the 3D
content
database 138. The inference rules 44 may be hard-coded (e.g. comparison based
on color harmony theory [15] or "Color Harmonization" by Cohen-Or, D.,
Sorkine,
0., Gal, R. Leyvand, T. and Y. Xu [16]), data-driven (e.g. inputted textually
by a
user or through a graphical user interface) or learnt from existing data. The
inference rules 44 may take many forms including a standard programming
expression, a regular expression, or a Bayesian or Markovian network.
[00111] Rules defined using Bayesian or Markovian networks may be learnt
from patterns found in the 3D content database 138 to produce highly precise
findings with little or no human intervention. For example, some consumers may
both fill in a census that asks them whether they have children or not, and
reconstruct their home. Assuming a sufficient number of samples, a Bayesian or
Markovian network can identify that the presence of a child's bed or a child's
toy
(detected by the recognition engine 12) makes it very probable that a child
lives in
the house. By testing relationships between random attributes in a background
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
28
process, the online shopping and 3D reconstruction system 130 can learn a wide
range of causal relationships with little or no human intervention.
[00112] Like most modules in the online shopping and 3D reconstruction
system 130, the inference engine 43 and the recognition engine 12 may run in
parallel, in the background or in a low-priority thread. Information generated
by
these engines may be cached to increase performance.
Advertising
[00113] Advertising can take the form of any number of media, including text,
images, audio, animations, video, video games and promotional items.
Advertising
may be passive or interactive. The advertisement may be distributed it a
variety of
ways including inside the online shopping and 3D reconstruction system 130
website, in emails and newsletters, in third-party websites, in regular mail
or on
interactive displays in regular stores.
[00114] Examples of advertising may include:
= static or animated banner in the online shopping and 3D
reconstruction system 130 website;
= advertised products shown in search results, in 2D or with 3D
preview;
= product placement directly within the virtual environment, e.g. beer
bottles of a specific brand shown next to a BBQ grill;
= animated character demonstrating a product, e.g. Hollywood star
demonstrating a new exercise machine;
= advertiser-sponsored games that are played inside a virtual home;
and
= preferred placement in search and recommendation results for
professional services, brick-and-mortar stores, etc.
[00115] Advertising may be charged to advertisers in a variety of ways
including per click, per thousands of impressions or per total broadcasts
time.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
29
Advertisers may also be charged when a user performs a task, e.g. answers a
questionnaire for a chance to win some prize. Advertisements may be selected
according to a scheduling algorithm, e.g. highest bidder or round-robin.
Advertisement placement may also be optimized using machine learning
techniques.
[00116] To create an ad, an advertiser may first proceed with one or more
search queries that will match the target market. These search queries can
refer to
any attribute stored in the user database 136, the 3D content database 138 or
resulting from an inference rule 44. To respect user privacy, queries can be
filtered, e.g. so that criteria like names, street address and phone numbers
are not
accepted, and returned search results must match a preset minimum of matches
(e.g. 10000). The advertiser may get a preview of the search results, e.g. 10
typical results in random order.
[00117] Examples of criteria that can be combined in a query are as follows:
= user personal information, such as country of residence, age, gender
(for example, when searching for a merchant, the online shopping
and 3D reconstruction system 130 may only return merchants that
are operating in the same country as the user);
= usage history, e.g. purchase, search, view, review history (for
example, an advertiser may want to only advertise to consumers who
have purchased or searched for a vacuum cleaner in the past year);
e objects that are present in rooms and input pictures, recognized by
the recognition engine 12;
= criteria specified by the user, e.g. colors, patterns and desired price
range;
= explicit consumer preferences, e.g. the consumer may request
recommendations for specific types of objects and may provide
additional constraints and rules, e.g. allergies to specific materials,
dislike for specific colors, etc., these may be extracted through
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
3D
questionnaires or in some cases, through learning and classification
techniques;
community information:
= reviews contributed by users of the consumer and
professional classes;
= complementary websites, such as consumer reports website;
usage history from other consumers (that may or may not be a
member of the online shopping and 3D reconstruction system
130) that may have similar taste (for example the consumer
could ask for a gift recommendation for a father in law using a
few additional information such as "father in law is 55 years
old", "works as a banker," etc., the search 37 and inference 43
engines can then identify items bought or viewed regularly by
consumers that fit the profile;
merchant information:
= price, availability, delivery, warranty information;
= rebates, special sales, new products or products being
discontinued;
= merchant cross-selling recommendations, e.g. a merchant
may suggest that product A would complement product B; and
= time of year, e.g. Christmas and Halloween decorations, or BBQ
during spring-
[00118] For example, an advertiser may target women aged 21 to 30 with
young children, in specific geographies, during specific time periods (e.g.
afternoon in local time), that used specific search queries. The advertiser
may also
specify a maximum advertising budget for the campaign, e.g. $1000 per day. The
online shopping and 3D reconstruction system 130 may allow advertisers to
specify several advertisements to test concurrently, and automatically adopt
the
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
31
most popular, e.g. after it has been shown a pre-determined number of times.
Learning techniques may be applied to automatically refine the criteria used
to
define the target market, e.g. by letting the advertiser select sample search
results
which are of particular interest or which are not interesting at all.
[00119] The online shopping and 3D reconstruction system 130 may also
support third-party advertising solutions, e.g. by automatically converting
the
available information into a suitable format, such as a text tags stored in a
temporary HTML document for Google AdsenseTM. This conversion -nay be done
using any number of algorithms, for example, by simply concatenating the names
of 3D products 39 present in a 3D environment 38, i.e. "chair, wooden table,
blue
carpet". Depending on the target format used by the third-party advertising
solution, the text strings could be sorted or repeated to attach a higher
importance,
e.g. using a distinctiveness criteria (lower frequency items first) or
according to the
importance or probability inferred from the environment. Furthermore, more
important text tags may be converted into HTML headers, repeated or shown in
meta tags, while less important text tags corresponding could be converted
into
regular text or written in smaller font.
[00120] The search engine 37 can return any number of outputs, including
possible combinations of:
= Advertisements;
= products, possibly of a specific category;
= attributes, e.g. colors, textures, materials;
= merchants or service providers, e.g. local merchants; and
= textual material, e.g. links from another website or generated on
the fly.
[00121] The output can be presented in a variety of ways, including:
= table to compare similar products; and
= real-time preview inside a room.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
32
Track results and view reports
[00122] Advertisers and merchants may request usage reports and may be
granted access to information contained in the user 136 and/or 3D content 138
databases, in its entirety or in some condensed format. To respect consumer
privacy, the information may be filtered, e.g. to remove the names, address
and
credit card information. Reports may be accessed on demand or at specific
times,
e.g. generated once a day. An advertiser can specify which fields and filter
rules
he may be interested in. For example, these filter rules could be converted
into
appropriate SQL queries.
[00123] Usage statistics may also be grouped to produce condensed reports.
For example, this could allow an advertiser or a merchant to find the most
popular
products in a specific category, to compute the average purchase price for
wooden
furniture in a given time period or geography, or to find products that are
frequently
searched for by a specific segment of the consumer market. Like any features
of
the online shopping and 3D reconstruction system 130, any aspect of this
operation could be offered at additional charge or restricted to a subset of
user
classes.
Shopping, merchant activities and external integrations
[00124] Shopping is integrated within the online shopping and 3D
reconstruction system 130. A consumer first add 3D products 39, e.g. by
searching, by asking for a recommendation, by following a link for an
advertised
product, or by cut-and-pasting from other 3D environments 38 or from lists
compiled by other users. Once a user is satisfied, he or she simply clicks an
order
button. The order menu allows a consumer to compare between several
merchants for each product, showing information such as price, applicable
taxes,
shipping cost, total cost and estimated delivery time- If a merchant is
present more
than once, the consumer may combine two products in one order, e.g. to reduce
shipping costs. A recommend button finds a compromise in total price and
delivery
time while reducing risks by choosing local and well-rated merchants.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
33
[001251 Once the consumer has chosen the merchant(s) he or she wants to
order from, he or she may order through the online shopping and 3D
reconstruction system 130 or, if applicable, through the merchant(s)' official
website. The online shopping and 3D reconstruction system 130 may distinguish
between three major types of merchants: external merchants, partner merchants
and consumer merchants.
[00126] An external merchant is a merchant that operates its own official
website outside of the online shopping and 3D reconstruction system 130 and
typically has an affiliate program. For example, an external merchant may
offer a
commission, for example 5%, on each sale that is forwarded through the online
shopping and 3D reconstruction system 130. The plug-in on the user's personal
computer 112 (see Figure 1) may operate the transaction automatically by
sending
the appropriate HTTP requests directly, or may open a web page for the user to
review and confirm the order transaction. In either case, personal, shipping
and
payment information may be filled automatically from the consumer data 41 of
the
user database 136. Typically, external merchants may or may not manage their
own merchant data 40 within the user database 136. The reconstruction of the
3D
products 39 and the data entry may be handled by some other party, such as the
online shopping and 3D reconstruction system 130 staff.
[00127] A partner merchant is a merchant that manages its own virtual store
within the online shopping and 3D reconstruction system 130. The partner
merchant uses the 3D reconstruction module 11 to reconstruct goods for sale.
This
type of merchant also keeps 3D products 39 descriptions, pricing and
availability
up-to-date. When a consumer pays for a purchase ordered from such a merchant,
the online shopping and 3D reconstruction system 130 processes the payment
and notifies the merchant, e.g. through email, phone, SMS or other means.
[00128] The third common type of merchant is a consumer that may want to
sell a second hand product. A consumer may become a merchant by selecting 3D
objects 39 that he or she wants to sell. The consumer merchant may ask the
online shopping and 3D reconstruction system 130 for a comparison with similar
3D products 39 available for sale, to get a better feel on the street price to
be
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
34
expected. He or she may then select "sell" to set the desired starting price,
indicate
whether the sale should operate at a fixed price or as an auction, the time
limit, the
acceptable buyer geographies, etc.
[00129] It should be noted that the three types of merchants described above
are examples and that many other types or variations thereof may exist.
[00130] For example, the plug-in that is usually installed on the user's
personal computer 112 (see Figure 1) may be integrated in external websites,
allowing these external websites to embed the online shopping and 3D
reconstruction system 130 content in web pages of their choice. This would
allow
the online shopping and 3D reconstruction system 130 content to be visible on
other websites, possibly with extra buttons such as "buy now" and "see in your
home", that may re-direct to appropriate pages on the online shopping and 3D
reconstruction system 130 pages.
[00131] Likewise, it is possible to build a branded version of the online
shopping and 3D reconstruction system 130 experience to allow-a tihiid party
to
restrict the search and shopping activities to products available from that
specific
merchant.
[00132] Finally, since interaction with the online shopping and 3D
reconstruction system 130 is through a plug-in, it is possible have it
permanently
loaded on a user's personal computer 112 and have it applied to any website,
regardless of whether or not the website uses or is aware of the online
shopping
and 3D reconstruction system 130 plug-in. For example, any static image
presented through the browser could be automatically augmented to a 3D model
compatible with the online shopping and 3D reconstruction system 130 by
matching it with 3D products 39 from the 3D content database 138.
Further uses of the 3D reconstruction module
[00133] The process 300 of Figure 4, used by the 3D reconstruction module
11, may be further used in third party applications as a stand-alone
application or
may also be used to provide further services within the online shopping and 3D
reconstruction system 130. Sample applications are listed below, though it is
to be
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
understood that this is not a limitative list and that other applications may
also
incorporate the 3D reconstruction process 300 of Figure 4.
[00134] Printing applications, e.g. on regular paper or in 3D models, to make
custom doll houses.
[00135] Non-photorealistic rendering and geometry modification applications,
e.g. to make personalized lego-block sets or aquarel paintings.
[00136] Simulation applications, e.g. by integrating a physics or fluid
simulation engine it may be possible to simulate an earthquake or fire.
Results
may be visualized and recommendations may be shown to the user, e.g. to use
fire-proof drapes or to install an emergency staircase. Results may also be
exported in other applications and shared with others, e.g. government
officials.
[00137] Moving applications with automatic re-layout (e.g. through relaxation
alaorithms), allowino users to easily see and load obiects from one room to
another. Automatically plan the move from one location to another by
contacting
movers electronically, booking a time, calculating costs, etc. Objects that
are not
expected to fit in the new room may be automatically listed and sold on a
classified
or an auction site on the online shopping and 3D reconstruction system 130 or
outside (e.g. eBayTM).
[00138] Environment recognition applications, e.g. the 3D recognition can be
extended to an entire environment. For example, if a toilet is detected it
increases
the chance that toilet paper is nearby or other related articles. These rules
could
be learnt from models tagged by humans. It may also be possible to infer the
manufacturer, the model number, the year a furniture was made (useful for
antiques) and style (e.g. modern, roccoco). Recommendations could match a
painting with a room or authentic accessories with an antique. The
recommendation could find products available from partner merchants
(registered
with the on the online shopping and 3D reconstruction system 130) or from
external services (e.g. eBayTM).
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
36
[00139] Environment mapping applications, e.g. finding specific objects (e.g.
lost keys), helping a robot navigate, advertising real-estate for sale or for
rent,
teleconference/3D chat, children surveillance.
[00140] Inspection applications, e.g. by applying 3D reconstruction at
different time intervals, thus enabling the comparison and the identification
of
structural problems, e.g. new cracks that could indicate structural damage,
damage assessment for insurance claims, etc.
[00141] It is to be understood that although throughout the disclosure
reference is made to separate servers 132 and 134 as well as separate
databases
136 and 138, these may be implemented on one or more physical device and/or
may be combined.
[00142] Although the present invention has been described by way of
particular embodiments and examples thereof, it should be noted that it will
be
apparent to persons skilled in the art that modifications may
_be..applie.d..to.the ___ ._. -----
present particular embodiment without departing from the scope of the present
invention.
REFERENCES
[1] Rob Fergus, Barun Singh, Aaron Hertzmann, Sam T. Roweis and William T.
Freeman, "Removing camera shake from a single image", presented at
SIGGRAPH 2006, Boston.
[2] David Liu and Tsuhan Chen, "Background cutout with automatic object
discovery", IEEE International Conference on Image Processing (ICIP), 2007.
[3] J. Shotton, J. Winn, C. Rother, and A. Criminisi, "TextonBoost for Image
Understanding: Multi-Class Object Recognition and Segmentation by Jointly
Modeling Texture, Layout, and Context", which can be found at
http:]/jamie.shotton.org/work/publications/ijcvD7a.pdf.
[4] Yin Li, Jian Sun, Chi-Keung Tang, and Heung-Yeung Shum, "Lazy
Snapping", SIGGRAPH 2004.
CA 02735680 2011-02-28
WO 2009/026726 PCT/CA2008/001551
37
[5] Rother, Kolmogorov and Blake, "GrabCut - Interactive Foreground
Extraction using Iterated Graph Cuts", SIGGRAPH 2004.
[6] Yasutaka Furukawa and Jean Ponce, "Accurate, Dense, and Robust Multi-
View Stereopsis", CVPR 2007.
[7] Alan P. Mangan and Ross T. Whitaker, "Partitioning 3D Surface Meshes
Using Watershed Segmentation", IEEE Transactions on Visualization and
Computer Graphics, Volume 5, Number 4, Pages 308-3211, 1999.
[8] Bruno Levy, "Least Squares Conformal Maps for Automatic Texture Atlas
Generation", http://www.loria.fr/%7Elevy/.
[9] M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester. "Image Inpainting",
Proceedings of SIGGRAPH 2000, New Orleans, USA, July 2000.
[10] Tianll Yu, Hongcheng Wang, Narendra Ahuja and Wei-Chao Chen, "Sparse
Lumigraph Relighting by Illumination and Reflectance Estimation from Multi-
View Images", Eurographics Symposium on Rendering (EGSR), 2006.
[11] F. Scalzo, J. Piater, "Adaptive patch features for object class
recognition with
learned hierarchical models", 2nd Beyond Patches Workshop, CVPR 2007.
[12] http://www.pascal-network.org/challenges/VOC/voc2007/workshop/index.html
[13] Kazhdan, M., Funkhouser, T. and Rusinkiewicz, S, "Symmetry descriptors
and 3D shape matching 2004 Symposium on Geometry Processing, 116-
125.
[14] Richard Hartley and Andrew Zisserman, "Multiple View Geometry in
Computer Vision, 2nd edition" Cambridge University Press; 2nd edition, April
19. 2004.
[15] http://www.websiteoptimization.com/speed/tweak/color-harmony/.
[16] Cohen-Or, D., Sorkine, 0., Gal, R. Leyvand, T. and Y. Xu, "Color
Harmonization", Proceedings of ACM Siggraph 2006.
