Patent Description:
Several computer-automated systems are presently available with which end users or consumers of products may design, preview, and order custom-manufactured products that incorporate images or graphics. Examples of products include wearing apparel, beverage vessels, and accessory items. In a typical system, an end user or consumer uses a general purpose computer terminal, such as a personal computer with a browser, to connect over a public network to a server computer. The user selects a stored graphic image, or uploads a digital image that the user obtained or made. The user selects a type of product to which the graphic image is to be applied and specifies various parameter values relating to the product such as color, size, image placement location, or others. The server computer or terminal generates a rendered image showing how the product will appear after custom manufacture with the specified image applied. The user approves the rendered image and places an order for the product. A manufacturer receives the order data, manufactures the product as specified and provides the custom manufactured product to the user.

<CIT> describes systems and methods for facilitating the decoration of an area, and particularly a surface such as a wall in a room, are provided. A user may view a virtual impression of the placement of selected artwork on a particular wall. The user provides an image of the area to be decorated, along with a reference scale associated with the area, to a server. The user views and selects an image of an artwork object from an available selection of artwork images, the artwork image having a corresponding size of the artwork object. The image of the artwork is scaled such that the ratio of the size of the artwork object and the size of the artwork image substantially corresponds to the ratio of the size of the area to be decorated and the size of the area image. The scaled artwork image is then overlayed on the area image and may be viewed by the user to provide a simulated image of the area and artwork.

<CIT> describes a method for viewing images of one or more items which a user may be interested in buying and displaying candidate items with one or more images provided by the user, such as a room image, an image of a person, or an image of a car.

<CIT> describes a system and method for modeling a piece of apparel.

<CIT> describes a system and method for changing attributes of an image-based product in which an attribute of a first image is automatically identified and a new value for a product attribute of the image-based product is automatically selected based on the image attribute.

One type of product of interest-not offered in typical prior systems-is framed or mounted materials. A frame may comprise wood molding, metal pieces, or plastics. The mounting may include one or more mats or may comprise float mounting. The materials may include digital images of film photographs, original digital art, prints, paintings, animation cells, or any other graphical work or work of the visual arts. Individualized online design and custom manufacture of such framed and mounted material is either impossible or imperfect using existing systems.

The object to be solved is to enable ensuring that geometry of a visualized product is accurate in the characterized environment. The object is achieved by the present invention in the aspects of a method, a special-purpose computing device and a computer system having the features of the independent claims. Additional features for advantageous embodiments are provided in the dependent claims.

The terms "comprising," "comprises," and "comprise," as used herein, which are synonymous with "including," "containing," or "characterized by," are meant to be inclusive or open-ended and not meant to exclude additional, unrecited elements or method steps.

An embodiment of the approaches herein may be used in the context of a computer-based system that can receive and store digital images, receive a request to manufacture a custom framed product including an identification of an image to be framed and a type of mat and/or frame, and display a preview image of the custom framed product that simulates the actual appearance of the product as closely as possible. With such a system, the preview image may be highly realistic under idealized lighting and display conditions. However, the appearance of actual framed images may vary widely in different environments. For example, custom framed products typically are displayed by hanging on a wall, but the appearance of the product may vary greatly in environments such as interior rooms with different levels of lighting, kinds of lighting, kinds of walls, wallpaper, reflective surfaces, or other background environment.

Frame elements and mats are represented in 3D models with parameterized values to permit resizing and use with different visual material. For example, 3D models of frame elements may be prepared by placing actual frame stick material in a fixed rig adjacent to a first surface mirror; a laser is projected at a known angle against the surface of the frame stick material and a digital image is formed of the molding together with the laser line and a programmed computer deduces, from the laser line, a geometry of a front surface of the frame stick material and the rear profile is obtained from the first surface mirror. A subsequent image is taken with the laser line shuttered off, to capture an actual surface texture of the molding. The resulting perspective view of the molding surface texture is flattened to permit subsequent mapping of the flattened texture onto a computer-generated 3D model of the molding. For mats, actual thickness may be manually measured and entered as a parameter value, and a flat plan view digital image of the mat texture may be taken and used in 3D texture mapping.

In an embodiment, the preview image of a custom framed product may be modified in a way that closely simulates the actual appearance that the custom framed product will have in a particular environment.

The approaches herein offer numerous benefits in comparison to prior approaches. For example, the design of the example markers shown herein and the nature of recognition is different for characterizing the geometry of the space. The design of the example markers and the processing logic described herein allows for both the characterization of the geometry and also the lighting. This robust characterization enables ensuring that geometry of a visualized product is accurate in the characterized environment. In addition, the logic herein can adjust the nature of the rendering to compensate for the color or lighting of the user environment based on a user image of a single marker and single user-provided photograph.

Further, the system(s) herein accommodate the dynamic nature of custom manufactured products, which can be configured both in the nature of the assembly as well as the nature of the embellishment. The system(s) contemplate the sharing of these characterized environments in an online marketplace together with configured/designed product to be visualized in-situ. The "complete" nature of the system(s) contemplate the characterization of product for configuration/embellishment, enabling users to configure/embellish and visualizing the resultant embodiments in characterized environments.

For purposes of illustrating the in-situ visualization system and method, embodiments described herein refer to a custom framed product. However, the in-situ visualization system and method may also be used to visualize other mountable or displayable custom products for which it is desirable to provide an in-situ visualization of the custom product to users. Examples of other custom products to which the in-situ visualization system and method may be applied include custom manufactured products with user provided images or text such as a customized skateboard, a customized globe, a customized baseball bat, a customized car top and products on which a customized embroidery has been placed such as, for example, customized clothing or other embroider-able product.

With reference to <FIG>, in an embodiment, a data processing process comprises the following general steps:
A digital representation of a marker is transmitted (block <NUM>) to a user. For example, the user, who may be an end consumer of a commercial custom manufactured product service, uses a computer terminal to connect to a server computer associated with the service. The user either establishes an account with the service or logs into an existing account. The user initiates a process of designing a custom product. The user is prompted to download or print a digital file, such as a PDF document or graphical image file, containing the representation of the marker.

The user prints (block <NUM>) the marker on a sheet of paper. In an embodiment, the printed size of the sheet of paper is stored in the service in association with data describing the marker. For example, the service may store metadata indicating that a particular marker is <NUM>½ x <NUM> inches, or metric size A4, or any other suitable size, and the user will be prompted or otherwise required to print the marker on a sheet of that size.

The user positions (block <NUM>) the paper with marker in their environment at a location at which the user wishes to visualize the custom manufactured product. For example, the user attaches the sheet of paper to a wall on which the user plans to mount or display a customizable product.

The user takes (block <NUM>) a digital photo of the marker in-situ. In this context, "in situ" means at the actual location in the environment at which a custom product is to be used or displayed.

The user transmits (block <NUM>) the photo to an In-Situ Visualization service.

As further described herein, the service uses the marker to characterize (block <NUM>) the position, orientation and lighting of the user photograph.

The service produces (block <NUM>) a digital asset that visualizes a custom product in-situ. The digital asset may be produced such that the custom product, as visualized by the digital asset, reflects the detected position and orientation of the marker in the user photograph and the lighting at the actual location of the marker. For example, the digital asset may be a digital graphic image that the service can cause to be displayed on the user computer terminal to give the user a simulated view of a realistic appearance of the custom manufactured product as if actually mounted or displayed in the user environment at the location where the user previously positioned the sheet. Instead of a digital image, the digital asset may be digital video, digital audio/visual program, or graphical model of the custom product.

Aspects of components of the preceding general process are now described.

In an embodiment, a marker may have the following characteristics. The marker may have one or more linear components that may be recognized, using image recognition techniques, as lines in a photograph taken by a digital camera. For example, in an embodiment the marker comprises a plurality of lines that are typically <NUM>" to <NUM>" inches in width or thickness. Linear components of these sizes are expected to appear sufficiently thick or bold in a user image to permit computer-based recognition of the lines in the user image, even in the presence of background user environmental elements such as wall textures, other mounted materials, doors, wall corners, floors, and other elements. Lines that are too thin may be difficult to recognize as part of the marker, whereas lines that are too thick may be difficult to accurately position in space in relation to the environment.

In an embodiment, the marker has a border when printed and photographed, so that the linear components are isolated from other picture elements in the environment. The border may be a blank margin. Thus, in an embodiment, a blank border separates the linear components from an edge of a printed sheet showing the marker. Therefore, the border enables better recognition of the marker from the environment and breaks or separates the connectivity of the linear components from other image elements that are not part of the marker.

In an embodiment, the linear components are arranged to form a connectivity graph. The connectivity graph is any association of arcs that are connected at points termed nodes to form a plurality of enclosed regions termed polytopes. In an embodiment, each particular marker has a particular connectivity graph with different connectivities as compared to other marker instances as determined by a plurality of features. Example features that may differentiate one connectivity graph from another include aspects of line intersections, number of lines, and number of enclosed regions. Embodiments do not require use of any particular marker format or style; for example, while one example disclosed herein has the general appearance of a rectangular grid, many other geometric arrangements may be used. What is important is that the service has stored metadata describing a reference connectivity graph that is expected to be seen in the user's digital image of the marker and environment.

In an embodiment, the form of the connectivity graph of the marker is distinct in orientation. For example, each marker is provided with one or more features such that changing an orientation or rotation of the marker yields a different visual appearance. This characteristic enables computer analysis of the user digital image to determine the actual orientation that was used for the marker when it was placed in the user environment.

In an embodiment, the spatial relationships of the connectivity graph are recorded, and used as a means of detecting the position and orientation of the marker in the photograph. For example, detecting may involve seeking to recognize known features of nodes, lines, and polytopes in a reference marker that match the same features in the user digital image.

In an embodiment, features of nodes include a count of nodes in the entire marker graph, a count of arcs connecting at a given node, and an adjacency of a node to polytopes having a given count of nodes. These features of nodes can be used to differentiate one connectivity graph from another. That is, if the count of nodes, count of arcs connecting at a given node, and an adjacency to a count of polytopes of a given node count are known, then the same features can be identified when the user's digital image is processed, and the marker can be recognized in the user's digital image only when the counts and adjacency match.

In an embodiment, features of lines also may be used for detection and differentiation. In an embodiment, relevant features include the number of lines (arcs) or count of arcs in the marker graph, and the adjacency of each line to polytopes of a given arc count.

In an embodiment, features of enclosed regions or polytopes also may be used for detection and differentiation. In an embodiment, features relevant to the number of enclosed regions (polytopes) include a count of polytopes in the marker graph and a count of the nodes in each polytope.

In certain embodiments, the connectivity graph of lines may also be user-readable as a symbol, graphic, or legend, such as a company's brand or trademark.

In an embodiment, one or more open spaces are provided in the printed marker and may be unprinted or printed with light colors or tones that provide a means of detecting the lighting of the user site. The open spaces may be termed "light sampling points". Additionally, full printing areas of the line graph of the marker are known, and may be termed "dark sampling points". If the "light sampling points" and "dark sampling points" are detected in a user image of the marker in the environment, then based on luminance values or other data representing the sampling points, the computer can determine a lighting gradient that exists between the sampling points and can modify the appearance of a digital asset to simulate the actual lighting in the user environment.

Colors may comprise black, white, and gray, in one embodiment and can facilitate different types of image analysis. For example, if the computer cannot detect a gray space in a candidate marker in the user image, then the computer can determine that the user image has excessive white level or is "blown out" and needs to be retaken to permit accurate recognition.

The lighting in an environment can appear to have a color bias when recorded by a digital device such as a digital camera. This bias results because the light illuminating the environment may be one or more of a variety of different types including sunlight, incandescent, mercury vapor, fluorescent, etc. that have particular spectral distributions that the human eye sees as white, but that the digital device records as a particular color.

In one embodiment, the marker includes a medium tone gray area that permits accurate recognition of a lighting bias in the user image. Additionally or alternatively, pastel color tones may be used to assist user recognition of color bias in the lighting of the user environment. For example it may be useful to include a known green tone or pink tone in selected areas of the reference marker to aid in recognizing whether the user environment is principally illuminated using fluorescent lamps or incandescent lamps and applying a similar color bias to the digital asset that simulates the custom manufactured product in the environment under the same lighting.

<FIG> and <FIG> illustrate examples of markers. Referring first to <FIG>, in one embodiment, a marker resembles a trademark of a business entity, in this case, the Z logo of Zazzle Inc. , Redwood City, California. Marker <NUM> comprises a plurality of arcs <NUM>. Example nodes 206A, 206B are at intersections of arcs, and the marker defines a plurality of polytopes of which polytopes 208A, 208B, 208C are examples. Corner portions <NUM> of the marker <NUM> are non-uniform with respect to the manner of arc intersection so that an orientation of the marker may be detected using computer image analysis techniques.

The count of arcs associated with a particular node also varies; for example, node 206A is at an intersection of four (<NUM>) arcs whereas node 206B is at an intersection of three (<NUM>) arcs. Therefore when the marker <NUM> is recognized in a user image the marker may be characterized in terms of the number of nodes and the count of arcs at each node and compared to reference data describing a reference marker to determine if a match occurs. The marker <NUM> also may be characterized by the number of adj acent polytopes associated with a node; for example, node 206A is associated with four (<NUM>) adjacent polytopes whereas node 206B has three (<NUM>) adjacencies. Further, the characterization data for a particular marker enables efficient image processing; for example, an image recognition algorithm may be configured to reject a candidate item recognized in a user image as a potential matching marker at the earliest time at which it is determined that a characterization of the item does not match a reference marker. For example, as the computer proceeds to recognize a candidate item, as soon as the computer determines that the candidate item has too few or too many arcs, nodes, or polytopes, the candidate item may be rejected and the process may move on to considering another candidate item.

The number of characterization items for a marker preferably is relatively small to avoid requiring unnecessarily large amounts of data processing time. For example it is known that when a marker is complex and has a large number of arcs, nodes and polytopes, the processing time and storage space needed to accurately recognize the marker may become prohibitive. Therefore, markers having relatively simple connectivity graphs are preferred.

As another example, in <FIG>, a marker resembles a grid of rectangles. The arrangement of <FIG> offers the benefit of fitting a rectangular letter sized sheet of paper well.

In both <FIG>, <FIG>, the marker includes a blank border around the perimeter of the marker, lines that are large enough to detect in a user image, and other features such as lines, intersections, and enclosed regions that are uniquely recognizable against a background. Further, <FIG>, <FIG> represent markers that incorporate shapes or graphs that are otherwise uncommon in a natural setting, which improves the performance of the recognition process herein.

In various embodiments, the service may provide a marker that is particular to the end user or customer, or may provide a plurality of different markers that the end user may select from and download. For example, different markers may be associated with or tied to different products, services, users, or classes of products. For example, different products may have different sizes and the user may wish to visualize two different products of different sizes in the same general environment; in such a case the service may provide two different markers of different sizes. Different products of different types also may warrant the use of different markers. For example, a custom painted or printed stretch canvas product might use a different kind of marker than a custom decorated skateboard deck.

In an embodiment, a computer-based in-situ visualization service comprises one or more computer programs or other software elements that are configured to perform the following general tasks: characterizing the user site with the marker; building a visual asset using the found user site data and a photograph or other digital image; rendering the digital asset.

In an embodiment, characterizing the user site with the marker generally comprises digitally recognizing a connected graph based on a reference graph using a process illustrated in flowchart form in <FIG>.

First, assume that as described above, a user has produced a printed (block <NUM>) copy of a marker, placed (block <NUM>) the printed marker in the user environment at a location at which a custom product will be displayed or mounted, taken (block <NUM>) a digital photograph or image of the environment including the marker, and uploaded (block <NUM>) the user photograph to the service. For example, the user photograph could be a digital image of a portion of the interior of a room in which the marker has been attached to a wall.

The process of <FIG> may be implemented in computer logic to recognize the marker in the user photograph, for example, as part of using (block <NUM>) the user photograph of the marker to characterize the user photo, the location and orientation of the marker, and lighting at the marker location:.

A linear image is produced by filtering (block <NUM>) the user photograph so that linear features in the size range of the marker lines are left and other linear and non-linear features are filtered out. For example, a thresholded bandpass filter or an edge filter may be used. The result is an output image which when displayed comprises only linear features in the size range of the marker lines as black on a white background.

The linear image is further filtered (block <NUM>) into a Boolean array of pixels using cellular automata, so that linear elements are one (<NUM>) pixel in width, and each line is represented in the image by its pixels being set to true. Example value tables for cellular automata are provided in the pseudo-code example below. The cellular automata approach uses a rule-based system with threshold neighborhood inputs. In the cellular automata approach, neighbor pixels of a particular pixel under consideration form instructions or opcodes to an automaton that produces a result pixel value based on the input, and the particular pixel is then replaced with the result pixel value. Unlike prior applications of cellular automata, in the present approach, cellular automata are applied to line thinning. A pseudo-code example of the cellular automata approach is provided below.

The array of pixels is traversed (block <NUM>). When a true pixel is found, a candidate graph is built by traversing connected pixels. For example, when connected pixels are identified then a node is recognized. If no true pixels are found, the algorithm ends. As the candidate graph is created and stored in memory, if the node, arc or polytope counts are greater that of the reference graph, the candidate graph is disposed, and stored values for all connected pixels of the current line network are set to false. In one embodiment, the candidate graph and the reference graph are represented in a computer using a winged edge data structure. Other data structures and models may be used to represent candidate connectivity graph and the reference connectivity graph and the invention is not limited to a winged edge data structure.

By building and using connectivity graphs, the process may rapidly discard candidate graphs that do not meet one or more connectivity criteria of the reference graph. This process is unlike other approaches in which complete recognition and characterization of a candidate graph in the user image may be needed. For example, in the present approach there is no need to complete the recognition of a candidate graph that grows excessively large; it is simply discarded at the earliest opportunity, increasing performance and reducing time to recognize the marker. On completion of the candidate graph, if the node, arc or polytope counts are less than those of the reference graph, the candidate graph is disposed.

If a candidate graph's full set of connectivity characteristics matches (block <NUM>) the reference graph, the algorithm continues at block <NUM>. If a candidate graph is discarded or disposed and there are more true pixels in the array of pixels (block <NUM>), then the traversal of the array of pixels continues at block <NUM>. Otherwise, the algorithm ends (block <NUM>) possibly with a notification to the user that the marker could not be detected in the user photograph.

Once there is a matching candidate graph, the orientation and position of the matching graph in the user photograph is found by calculating (block <NUM>) a marker transform, which maps known nodes in the reference graph to found nodes in the matching graph. Thus, when a matching connectivity graph is identified, the pixel coordinates within the user image of nodes, arcs and polytopes are known, and may be mapped using the marker transform to the reference graph. Point mapping techniques using singular value decomposition may be used, for example, to determine the marker transform.

Once the marker transform is determined, light sampling points may be found (block <NUM>) in the photograph. These points are used to determine a white point for the image, and a luminance gradient or map for rendering the visual asset. For example, the coordinates in reference space of a first light sampling point may be transformed, using the marker transform, to equivalent points in user image space; at those points, pixel values may be sampled or obtained to determine a baseline white value for the user image. In an embodiment, the luminance gradient is a set of values representing a range of the magnitude of reflected light across the user environment, and may be represented by a set of delta values in image space, for example, Δu and Δv values.

The marker transform may also be used (block <NUM>) to find the dark sampling points in the user image, which are used to set a black point for rendering the visual asset. Thus, information may be extrapolated about the user environment including its geometry and lighting, and appropriate changes may be applied in to the image in terms of chroma spectrum, luminance, brightness, and other attributes so that the image appears, on the user's computer screen, as similar as possible to the actual appearance of the custom manufactured product when it is installed in the user environment.

In an embodiment, building a visual asset using the found user site data and a photograph or other digital image may involve the steps illustrated in the flowchart of <FIG>.

Initially, a visual asset is built using layers as follows. The user photograph is adjusted (block <NUM>) using the data obtained from the light sampling points and the dark sampling points.

A custom product reference is placed (block <NUM>) into the user photograph using the marker transform for placement; the custom product reference may comprise a unique name or identifier, a geometric place holder such as a rectangle within a coordinate system, and that coordinate system transformed using the marker transform, which represents the custom manufactured product in which the user is interested.

The luminance gradient is applied (block <NUM>) to modify the luminance of the custom product to match the light gradient of the user photograph based on a point of known luminance in the user image space.

Second, the custom product is displayed (block <NUM>) using the following steps. In an embodiment, the user chooses the custom product and its attributes by interacting with the service. In an embodiment, the user's in-situ visual asset is loaded. In an embodiment, the rendering asset for the custom product is configured. In an embodiment, the custom product reference is set to the Custom Product asset.

Finally, in an embodiment, the in-situ asset is rendered and sent to the user display unit or browser.

For example, <FIG> is a block diagram that illustrates a computer system <NUM>.

The input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. Thus, the sole and exclusive indicator of what is the invention, and is intended by the applicants to be the invention, is the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Any definitions expressly set forth herein for terms contained in such claims shall govern the meaning of such terms as used in the claims. Hence, no limitation, element, property, feature, advantage or attribute that is not expressly recited in a claim should limit the scope of such claim in any way. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Claim 1:
A method for characterizing a user site with a marker, the method comprising:
uploading a user digital image including a marker;
filtering (<NUM>) a user image to produce a linear image so that linear features in the size range of the marker lines are left and other linear and non-linear features are filtered out;
filtering (<NUM>) the linear image into an array of pixels using a cellular automata approach;
traversing (<NUM>) the array of pixels to create a candidate connectivity graph by traversing connected pixels;
determining (<NUM>) whether the candidate connectivity graph matches a reference connectivity graph by discarding the candidate connectivity graph that do not meet one or more connectivity criteria of the reference connectivity graph, wherein metadata describe one or more reference connectivity graphs that are expected to be seen in a user's digital image, wherein linear components are arranged to form the reference connectivity graph;
in response to determining that the candidate graph matches the reference connectivity graph:
calculating (<NUM>) a marker transform which maps known nodes in the reference connectivity graph to found nodes in the matching graph;
using the marker transform to find (<NUM>) a plurality of light sampling points in the user image;
using the marker transform to find (<NUM>) a plurality of dark sampling points in the user image;
extrapolating information about the user environment to apply appropriate changes to the user digital image.