Visualizing a custom product in situ
Contents
1. Computer system 600 may implement the techniques described herein using customized hard wired logic one or more ASICs or FPGAs firmware and or program logic which in combination with the computer system causes or programs computer system 600 to be a special purpose machine According to one embodiment the techniques herein are performed by computer system 600 in response to processor 604 executing one or more sequences of one or more instruc tions contained in main memory 606 Such instructions may beread into main memory 606 from another storage medium such as storage device 610 Execution of the sequences of instructions contained in main memory 606 causes processor 604 to perform the process steps described herein In alterna tive embodiments hard wired circuitry may be used in place of or in combination with software instructions The term storage media as used herein refers to any non transitory media that store data and or instructions that cause a machine to operation in a specific fashion Such storage media may comprise non volatile media and or vola tile media Non volatile media includes for example optical or magnetic disks such as storage device 610 Volatile media includes dynamic memory such as main memory 606 Com mon forms of storage media include for example a floppy disk a flexible disk hard disk solid state drive magnetic tape orany other magnetic data storage medium a CD ROM any other optical data stor2. 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 causeto be displayed on the user computer terminal to give the user a simulated view ofa realistic appearance ofthe custom manu factured 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 In an embodiment displaying the digital asset as described in this paragraph may be implemented in part as described in U S application Ser No 11 925 716 filed Oct 6 2007 the entire contents of which are hereby incorporated by reference for all purposes as if fully set forth herein Aspects of components of the preceding general process are now described Marker In an embodiment a marker may have the following char acteristics The marker may have one or more linear compo nents that may be recognized using image recognition tech niques 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 0 25 to 0 5 inches in width or thickness
3. is performed by one or more comput ing devices 2 The method of claim 1 wherein the first data indicates one or more of a count of the nodes of the reference connectivity graph a count of arcs connecting at a particular node of the ref erence connectivity graph a count of lines or arcs of the reference connectivity graph acount of polytopes ofthe reference connectivity graph or a count of nodes of a particular polytope of the reference connectivity graph 3 The method of claim 1 wherein the second data indi cates one or more of a count of the nodes of the reference connectivity graph a count of arcs connecting at a particular node of the ref erence connectivity graph a count of lines or arcs of the reference connectivity graph acount of polytopes ofthe reference connectivity graph or a count of nodes of a particular polytope of the reference connectivity graph 4 The method of claim 1 wherein the marker comprises one or more colored open spaces for aiding a digital image analysis technique applied to the digital image in detecting lighting in the environment in which the marker was photo graphed 5 The method of claim 4 wherein at least one of the one or more colored open spaces is colored in a medium tone gray or a pastel color tone for aiding the digital image analysis tech nique in detecting color bias of lighting in the environment in which the marker was photographed 6 The method of claim 1 furt
4. pixels For example when connected pixels are iden tified 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 net work 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 beused 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 pro cess is unlike other approaches in which complete recogni tion 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 connect
5. 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 102 the marker on a sheet of paper In an embodiment the printed size of the sheet of paper is 20 25 30 35 40 45 50 55 60 65 4 stored in the service in association with data describing the marker For example the service may store metadata indicat ing that a particular marker is 82x11 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 103 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 104 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 105 the photo to an In Situ Visualization service As further described herein the service uses the marker to characterize block 106 the position orientation and lighting of the user photograph The service produces block 107 a digital asset that visu alizes a custom product in situ The
6. product for configuration embellish ment 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 pro vide an in situ visualization of the custom product to users Examples of other custom products to which the in situ visu alization system and method may be applied include custom manufactured products with user provided images or text see for example related U S patent application Ser No 12 546 582 and a product on which a customized embroi dery has been placed see for example related U S patent application Ser No 12 257 016 A Process for Visualizing a Custom Product In Situ With reference to FIG 1 in an embodiment a data pro cessing process comprises the following general steps A digital representation of a marker is transmitted block 101 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 com puter 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
7. spaces may be termed light sam pling 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 ofthe 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 sam 30 40 45 50 55 65 6 pling 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 analy sis For example ifthe 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 rec ognition 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 fluo rescent 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 med
8. 08 0069451 A1 3 2008 Ikeda 382 199 2008 0247674 Al 10 2008 382 305 2008 0285854 Al 11 2008 Kotake etal 382 190 2009 0109214 Al 4 2009 Harvill et al 2009 0177551 Al 7 2009 Cue et al 9 2006 Neal 3 2007 Kerr et al 5 2007 Fiala 45i eetemenn 382 120 5 2007 Simmons 2009 0195538 Al 8 2009 Ryu etal oe 345 419 2009 0289955 Al 11 2009 Douris etal 345 630 2009 0317010 Al 12 2009 Gerhard et al 2009 0324100 Al 12 2009 Kletter etal 382 217 2010 0036753 Al 2 2010 Harvill et al 2010 0048290 Al 2 2010 Baseley et al 463 25 2010 0066750 Al 3 2010 Yuetal 345 581 2010 0092079 Al 4 2010 Aller seese 382 165 2010 0106283 Al 4 2010 Harvill et al 2010 0185309 Al 7 2010 Ohiaeri et al 2010 0185529 Al 7 2010 Chesnutetal 705 27 2010 0189316 Al 7 2010 Walch 382 125 2010 0238166 A1 9 2010 Tamstorf et al 345 420 2010 0287511 A1 11 2010 Meier etal 715 848 2011 0098837 Al 4 2011 Yucel et al 2011 0280447 A1 11 2011 Conwell oo 382 103 2011 0292451 Al 12 2011 Harvill 2011 0305368 A1 12 2011 Osako e 382 103 2012 0218300 A1 8 2012 Hayakawa 345 633 2013 0057549 Al 2013 0060801 Al 3 2013 Beaver et al 3 2013 Beaver et al OTHER PUBLICATIONS Hirokazu Kato and Mark Billinghurst Marker tracking and hmd calibration for a videobased augmented reality c
9. 5 0258234 Al 11 2005 Silverbrook et al Continued FOREIGN PATENT DOCUMENTS EP 1124200 A2 1 2001 EP 1365358 A2 11 2003 WO WO 2009 094724 Al 8 2009 OTHER PUBLICATIONS Hirokazu Kato and Mark Bilinghurst ARToolkit User Manual Human Interface Technology Lab University of Washington 2000 Continued Primary Examiner David T Welch Assistant Examiner Jin Ge 74 Attorney Agent or Firm Hickman Palermo Truong Becker Bingham Wong LLP 57 ABSTRACT Techniques are described for visualizing a product at the actual location in the environment at which the product is to be used or displayed An embodiment of the approaches described 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 light ing and display conditions 26 Claims 7 Drawing Sheets INPUT DEVICE 814 CURSOR CONTROL 18 604 PROCESSOR COMMUNICATION INTERFACE US 8 654 120 B2 Page2 56 References Cited U S PATENT DOCUMENTS 2006 0197775 Al 2007 0067179 Al 2007 0098234 Al 2007 0124215 Al 2007 0143082 Al 6 2007 Degnan 20
10. 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 ele ments 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 environ ment and breaks or separates the connectivity of the linear components from other image elements that are not part of the marker US 8 654 120 B2 5 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 con nectivity graph with different connectivities as compared to other marker instances as determined b
11. RAWINGS FIG 1 is a flowchart of a process for visualizing a custom product in situ FIG 2 illustrates an example marker FIG 3 illustrates an example marker FIGS 4A B collectively FIG 4 is a flowchart ofa process for characterizing a user site with a marker FIG 5 is a flowchart of a process for building a digital asset with found user site data FIG 6 is a block diagram that illustrates a computer system with which the techniques herein may be implemented DESCRIPTION OF EXAMPLE EMBODIMENTS In the following description for the purposes of explana tion numerous specific details are set forth in order to provide a thorough understanding of the present invention It will be apparent however that the present invention may be prac ticed without these specific details In other instances well known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention Visualizing a Custom Product In Situ 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 cus tom 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 sucha system the preview image may be highly realistic unde
12. S W3dvd OL S353 VIN SINIdd d3Sn YSN OL H359IHVIALLIASNV SL 401 901 01 VOL 01 Aun LOL Old U S Patent Feb 18 2014 Sheet 2 of 7 US 8 654 120 B2 N LL U S Patent Feb 18 2014 Sheet 3 of 7 US 8 654 120 B2 e LL US 8 654 120 B2 Sheet 4 of 7 Feb 18 2014 U S Patent yoyda S T3XId HdV3S EI 39N333334 3HON SAHOLVW HaVs9 POP 31VGIQNVO VY Sls HdVH9 ALVGIGNVS ASILNAGI OL S13Xld 40 AVHSV 3SH3AVMH L cor HOWOUdd Vv YLYWOLNY YY1N1139 ONISN S 13XId 40 AVSSV OLNI JOVI YVSNIT 831113 zOb ADVI HV3NIT3Of1008d OL JOVI S3sf HALTS LOr US 8 654 120 B2 Sheet 5 of 7 Feb 18 2014 U S Patent 39VNI YASN NI SLNIOd ONITIdWVS 3VO NI OL WHOJSNVS L 38V ISN 60t J YNI YSN NI SLNIOd NNdNWYS LH9 ANIJ OL IWHOJSNVH L YIMYYN ISN 80v WHOJSNYHL YJMYYN 31V109 1V9 L0v gr Sls US 8 654 120 B2 Sheet 6 of 7 Feb 18 2014 U S Patent 19naosd WOLSND AV 1dSIG 19naouyd NOLSno OL LN3lQvH9 39NVNIN TA 1ddV 39VWI YASN NI 39N33333M ondqoyd WOLSND 39V ld OL INHO3JSNVM L S354 VIN ASN SLNIOd ONIIdNVS 3v ANY SLNIOd ONIIdWVS LH9TT INOW3 GANIVLEO VIVO NO Q3 V8 39VMWI YISN LSNPAV vos 0S C09 LOS g Sls US 8 654 120 B2 Sheet 7 of 7 Feb 18 2014 U S Patent Z4 1SOH 029 NI MYOMLAN SOMISN 1v201 929 829 09 MH3A3 009 30V JH3LNI 09 NOILVOINNWWOD JJO0SS300yd 208 sn
13. acement 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 503 to modify the luminance of the custom product to match the light gra dient of the user photograph based on a point of known luminance in the user image space Second the custom product is displayed block 504 using the following steps In an embodiment the user chooses the custom product and its attributes by interacting with the ser vice In an embodiment the user s in situ digital 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 In an embodiment displaying the custom product as described in this paragraph may be implemented as described in U S application Ser No 11 925 716 filed Oct 26 2007 the entire contents of which are hereby incorporated by reference for all purposes as if fully set forth herein Implementation Mechanism Hardware Overview According to one embodiment the techniques described herein are implemented by one or more special purpose com put
14. ademark Office patent file or records but otherwise reserves all copyright rights whatso ever APPENDIX DATA This application includes a transmittal under 37 C F R 1 52 e of a Computer Program Listing Appendix The Appendix which comprises the below listed text file that is IBM PC XT AT compatible and MS Windows compatible All ofthe material disclosed in the Computer Program Listing Appendix can be found at the U S Patent and Trademark Office archives and is hereby incorporated by reference into the present application for all purposes as if fully set forth herein Object Description ThinningByCellularAutomata txt size 41 902 Bytes created Aug 25 2011 BACKGROUND Certain approaches described in certain sections of this disclosure and identified as background or prior approaches are approaches that could be pursued but not necessarily approaches that have been previously conceived or pursued Therefore unless otherwise indicated it should not be assumed that any of the approaches that are so described actually qualify as prior art merely by virtue of identification as background or prior approaches Several computer automated systems are presently avail able 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 sys
15. age medium any physical medium with patterns of holes a RAM a PROM and EPROM a FLASH EPROM NVRAM any other memory chip or car tridge Storage media is distinct from but may be used in conjunc tion with transmission media Transmission media partici pates in transferring information between storage media For example transmission media includes coaxial cables copper wire and fiber optics including the wires that comprise bus 602 Transmission media can also take the form of acoustic or light waves such as those generated during radio wave and infra red data communications US 8 654 120 B2 11 Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor 604 for execution For example the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer The remote computer can load the instructions into its dynamic memory and send the instructions over a tele phone line using a modem A modem local to computer system 600 can receive the data on the telephone line and use an infra red transmitter to convert the data to an infra red signal An infra red detector can receive the data carried in the infra red signal and appropriate circuitry can place the data on bus 602 Bus 602 carries the data to main memory 606 from which processor 604 retrieves and executes the instruc tions The instructions received by main memory 606 may optionally be sto
16. and orientation of the marker and lighting at the marker location A linear image is produced by filtering block 401 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 sizerange ofthe marker lines as black on a white background The linear image is further filtered block 402 into a Bool ean array of pixels using cellular automata so that linear elements are one 1 pixel in width and each line is repre sented in the image by its pixels being set to true Example value tables for cellular automata are attached in the Appen dix The cellular automata approach uses a rule based system 0 an 5 20 35 40 45 50 65 8 with threshold neighborhood inputs In the cellular automata approach neighbor pixels of a particular pixel under consid eration 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 The array of pixels is traversed block 403 When a true pixel is found a candidate graph is built by traversing con nected
17. arker graph a count ofarcs 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 andan adjacency to a count of polytopes ofa 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 fea tures 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 poly topes 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
18. az United States Patent Beaver III et al US008654120B2 US 8 654 120 B2 Feb 18 2014 10 Patent No 45 Date of Patent 54 75 73 21 22 65 63 60 51 52 58 56 2001 0034668 Al VISUALIZING A CUSTOM PRODUCT IN SITU Inventors Robert Irven Beaver III San Francisco CA US Leslie Young Harvill Half Moon Bay CA US Richard Harold Bean Cupertino CA US Assignee Zazzle com Inc Redwood City CA US Notice Subject to any disclaimer the term of this patent is extended or adjusted under 35 U S C 154 b by 0 days Appl No 13 604 059 Filed Sep 5 2012 Prior Publication Data US 2013 0050205 A1 Feb 28 2013 Related U S Application Data Continuation of application No 13 539 788 filed on Jul 2 2012 Provisional application No 61 529 883 filed on Aug 31 2011 Int Cl G06T 15 00 U S CI USPC deeper tert ene dene 345 419 Field of Classification Search USPC GS au suu a Ausia ba kunki 345 419 See application file for complete search history 2011 01 References Cited U S PATENT DOCUMENTS 6 591 011 B1 7 2003 Nielsen 382 218 8 090 461 B2 1 2012 Ohiaeri et al 8 174 521 B2 5 2012 Harvill et al 10 2001 Whitworth DISPLAY 612 2003 0080978 A1 5 2003 Navabetal 345 633 2004 0017595 Al 1 2004 Ikeda 2004 0133081 Al 7 2004 Teller et al 2005 0226498 Al 10 2005 Lee 200
19. ce of the custom product to match the lighting gradient 14 One or more non transitory computer readable media storing instructions which when executed by one or more processors cause performance of a method for visualizing a custom product in situ the method comprising storing first data that represents a reference connectivity graph of a marker obtaining a digital image of at least the marker analyzing the digital image to generate second data that represents a candidate connectivity graph based at least in part upon first data and the second data determining whether the candidate connectivity graph matches the reference connectivity graph in response to determining that the candidate connectivity graph matches the reference connectivity graph gener ating third data that at least maps nodes ofthe reference connectivity graph to nodes of the candidate connectiv ity graph using at least the third data to build a digital asset that visualizes the custom product in the digital image wherein using at least the third data to build a digital asset that visualizes the custom product in the digital image comprises determining an adjustment to a color bright ness or luminance ofat least a portion of an image ofthe custom product based at least in part on the third data that at least maps nodes of the reference connectivity graph to nodes of the candidate connectivity graph 15 The one or more non transitory computer readabl
20. d Reality Washington DC USA Dated 2008 IEEE Computer Society 4 pages Johannes Kohler Alain Pagani and Didier Stricker Detection and Identification Techniques for Markers Used in Computer Vision Digital Object Identifier 10 4230 OASics VLUDS 2010 36 dated 2010 9 pages Homayoun Bagherinia O Roberto Manduchi Robust Real Time Detection of Multi Color Markers on a Cell Phone J Real Time Image Proc Dated Jun 3 2011 17 pages Jun Rekimoto Matrix A Realtime Object Identication and Regis tration Method for Augmented Reality Computer Human Interac tion Dated 1998 Proceedings 3 Asia Pacific Jul 15 17 1998 6 pages Jun Rekimoto and Yuji Ayatsuka CyberCode Designing Aug mented Reality Environments with Visual Tags Proceedings of DARE 2000 on Designing Dated Apr 2000 10 pages Martin Hirzer Marker Detection for Augmented Reality Applica tions Graz University of Technology Austria Dated Oct 27 2008 27 pages W Lee and W Woo Real time Color Correction for Marker Based Augmented Reality Applications International Workshop on Ubiq uitous VR IWUVR2009 dated 2009 4 pages US 8 654 120 B2 Page3 56 References Cited OTHER PUBLICATIONS Nima Soltani Mehmet Yilmax Using Augmented Reality on Pla nar Surfaced for Previewing D cor Changes Stanford University EE368 Class Project Spring dated 2010 5 pages Pantida Patirupanusara Marker Based Augmented Reality Magic Boo
21. e media of claim 14 wherein the first data indicates one or more of a count ofthe nodes of the reference connectivity graph a count of arcs connecting at a particular node of the ref erence connectivity graph acount oflines or arcs ofthe reference connectivity graph acount of polytopes ofthe reference connectivity graph or a count of nodes of a particular polytope of the reference connectivity graph 20 25 30 40 45 50 14 16 The one or more non transitory computer readable media of claim 14 wherein the second data indicates one or more of a count of the nodes of the reference connectivity graph a count of arcs connecting at a particular node of the ref erence connectivity graph a count of lines or arcs of the reference connectivity graph acount of polytopes ofthe reference connectivity graph or a count of nodes of a particular polytope of the reference connectivity graph 17 The one or more non transitory computer readable media of claim 14 wherein the marker comprises one or more colored open spaces for aiding a digital image analysis tech nique applied to the digital image in detecting lighting in the environment in which the marker was photographed 18 The one or more non transitory computer readable media of claim 17 wherein at least one of the one or more colored open spaces is colored in a medium tone gray or a pastel color tone for aiding the digital image analysis tech nique in det
22. ecting color bias of lighting in the environment in which the marker was photographed 19 The one or more non transitory computer readable media of claim 14 the method further comprising applying a thresholded bandpass filter or an edge filter to the digital image to produce a digital image that comprises linear fea tures in a size range of lines of the marker as black on a white background 20 The one or more non transitory computer readable media of claim 19 the method further comprising using a rule based cellular automata with thresholded neighborhood inputs to thin at least one of the linear features 21 The one or more non transitory computer readable media of claim 14 the method further comprising determin ing an orientation or position of the marker in the digital image using the third data 22 The one or more non transitory computer readable media of claim 21 the method further comprising using a point mapping technique involving singular value decompo sition to determine the third data 23 The one or more non transitory computer readable media of claim 14 the method further comprising using the third data to transform coordinates ofa light sampling point in a coordinate space of the marker to an equivalent point in a coordinate space of the digital image 24 The one or more non transitory computer readable media of claim 23 the method further comprising sampling pixel values at the equivalent point to determine a basel
23. fore markers having relatively simple connec tivity graphs are preferred As another example in FIG 3 a marker resembles a grid of rectangles The arrangement of FIG 3 offers the benefit of fitting a rectangular letter sized sheet of paper well In both FIG 2 FIG 3 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 recog nizable against a background Further FIG 2 FIG 3 repre sent markers that incorporate shapes or graphs that are oth erwise 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 envi ronment 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 k
24. g 019 809 909 3ol aad ANHOWSN 3OVMOLS WOU NIV 919 TOYNLNOOD JoOSsydno 7 r9 301430 LNANI alg AV 1dSIG 9 Sl US 8 654 120 B2 1 VISUALIZING A CUSTOM PRODUCT IN SITU CROSS REFERENCE TO RELATED APPLICATIONS This application claims under 35 U S C 120 the benefit as a Continuation of application Ser No 13 539 788 filed Jul 2 2012 which claims the benefit under 35 U S C 119 e of Provisional Application No 61 529 883 filed Aug 31 2011 the entire contents of each of which is hereby incorporated by reference as if fully set forth herein The applicant s hereby rescind any disclaimer of claim scope in the parent applica tion s or the prosecution history thereof and advise the USPTO that the claims in this application may be broader than any claim in the parent application s This application is related to U S application Ser No 11 925 716 filed Oct 26 2007 U S application Ser No 12 257 016 filed Oct 23 2008 and U S application Ser No 12 546 582 filed Aug 24 2009 the entire contents of each of which are hereby incorporated by reference for all purposes as if fully set forth herein COPYRIGHT STATEMENT A portion of the disclosure of this patent document con tains material which is subject to copyright protection The copyright owner has no objection to the facsimile reproduc tionby anyone ofthe patent document or the patent disclosure as it appears in the Patent and Tr
25. her comprising applying a thresholded bandpass filter or an edge filter to the digital image to produce a digital image that comprises linear fea tures in a size range of lines ofthe marker as black on a white background 7 The method of claim 6 further comprising using a rule based cellular automata with thresholded neighborhood inputs to thin at least one of the linear features US 8 654 120 B2 13 8 The method of claim 1 further comprising determining an orientation or position of the marker in the digital image using the third data 9 The method of claim 8 further comprising using a point mapping technique involving singular value decomposition to determine the third data 10 The method of claim 1 further comprising using the third data to transform coordinates ofa light sampling point in a coordinate space of the marker to an equivalent point in a coordinate space of the digital image 11 The method of claim 10 further comprising sampling pixel values at the equivalent point to determine a baseline white value 12 The method of claim 1 wherein building the digital asset comprises placing a custom product reference into the digital image using the third data for placement 13 The method of claim 1 further comprising analyzing the digital image to detect one or more light sampling points and one or more dark sampling points determining a lighting gradient that exists between sam pling points modifying luminan
26. ind of marker than a custom decorated skateboard deck In Situ Visualization Service 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 follow ing general tasks characterizing the user site with the marker building a digital asset using the found user site data and a photograph or other digital image rendering the digital asset A Process for Characterizing the User Site with a Marker In an embodiment characterizing the user site with the marker generally comprises digitally recognizing a con nected graph based on a reference graph using a process illustrated in flowchart form in FIG 4 First assume that as described above a user has produced a printed block 102 copy ofa marker placed block 103 the printed marker in the user environment at a location at which a custom product will be displayed or mounted taken block 104 a digital photograph or image ofthe environment includ ing the marker and uploaded block 105 the user photograph to the service For example the user photograph could be a digital image ofa portion ofthe interiorofa room in which the marker has been attached to a wall The process of FIG 4 may be implemented in computer logic to recognize the marker in the user photograph for example as part of using block 106 the user photograph of the marker to characterize the user photo the location
27. ine white value 25 The one or more non transitory computer readable media of claim 14 wherein building the digital asset com prises placing a custom product reference into the digital image using the third data for placement 26 The one or more non transitory computer readable media of claim 14 the method further comprising analyzing the digital image to detect one or more light sampling points and one or more dark sampling points determining a lighting gradient that exists between sam pling points moditying luminance of the custom product to match the lighting gradient
28. ing devices The special purpose computing devices may be hard wired to perform the techniques or may include digital electronic devices such as one or more application specific integrated circuits ASICs or field programmable gate arrays FPGAs that are persistently programmed to perform the techniques or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware memory other storage or a combination Such special pur pose computing devices may also combine custom hard wired logic ASICs or FPGAs with custom programming to accomplish the techniques The special purpose computing devices may be desktop computer systems portable com puter systems handheld devices networking devices or any other device that incorporates hard wired and or program logic to implement the techniques For example FIG 6 is a block diagram that illustrates a computer system 600 Computer system 600 includes a bus 602 or other communication mechanism for communicating information and a hardware processor 604 coupled with bus 602 for processing information Hardware processor 604 may be for example a general purpose microprocessor 20 25 30 35 40 45 50 55 60 65 10 Computer system 600 also includes a main memory 606 such as a random access memory RAM or other dynamic storage device coupled to bus 602 for storing information and instruction
29. it the scope of such an 5 20 40 45 50 55 65 12 claim in any way The specification and drawings are accord ingly to be regarded in an illustrative rather than a restrictive sense What is claimed is 1 A method for visualizing a custom product in situ the method comprising storing first data that represents a reference connectivity graph of a marker obtaining a digital image of at least the marker analyzing the digital image to generate second data that represents a candidate connectivity graph based at least in part upon first data and the second data determining whether the candidate connectivity graph matches the reference connectivity graph in response to determining that the candidate connectivity graph matches the reference connectivity graph gener ating third data that at least maps nodes ofthe reference connectivity graph to nodes of the candidate connectiv ity graph using at least the third data to build a digital asset that visualizes the custom product in the digital image wherein using at least the third data to build a digital asset that visualizes the custom product in the digital image comprises determining an adjustment to a color bright ness or luminance of at least a portion of an image ofthe custom product based at least in part on the third data that at least maps nodes of the reference connectivity graph to nodes of the candidate connectivity graph wherein the method
30. ital data streams The signals through the various networks and the signals on network link 620 and through communication interface 618 which carry the digital data to and from computer system 600 are example forms of transmission media Computer system 600 can send messages and receive data including program code through the network s network link 620 and communication interface 618 In the Internet example a server 630 might transmit a requested code for an application program through Internet 628 ISP 626 local network 622 and communication interface 618 The received code may be executed by processor 604 as it is received and or stored in storage device 610 or other non volatile storage for later execution Extensions and Alternatives In the foregoing specification embodiments of the inven tion have been described with reference to numerous specific details that may vary from implementation to implementa tion Thus the sole and exclusive indicator of what is the invention and is intended by the applicants to be the inven tion is the set of claims that issue from this application in the specific form in which such claims issue including any sub sequent 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 lim
31. ium 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 fluores cent lamps or incandescent lamps and applying a similar color bias to the digital asset that simulates the custom manu factured product in the environment under the same lighting Example Markers FIG 2 and FIG 3 illustrate examples of markers Referring first to FIG 2 in one embodiment a marker resembles a trademark of a business entity in this case the Z logo of Zazzle Inc Redwood City Calif Marker 202 comprises a plurality of arcs 204 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 210 of the marker 202 are non uniform with respect to the manner of arc intersection so that anorientation 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 4 arcs whereas node 206B is at an intersection of three 3 arcs Therefore when the marker 202 is recogni
32. ivity characteris tics matches block 404 the reference graph the algorithm continues at block 407 If a candidate graph is discarded or disposed and there are more true pixels in the array of pixels block 405 then the traversal of the array of pixels continues at block 403 Otherwise the algorithm ends block 406 pos sibly 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 407 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 decomposi tion may be used for example to determine the marker trans form Once the marker transform is determined light sampling points may be found block 408 in the photograph These points are used to determine a white point for the image and a luminance gradient or map for rendering the digital asset For example the coordinates in reference space of a first light sampling point may be transformed using the marker trans form to equivalent points in user image space at those points pixel values may be sampled
33. k for Anatomical Education International Conference on Com puter and Communication Technologies ICCCT 2012 May 26 27 2012 Phuket 3 pages Paul L Rosin Training Cellular Automata for Image Processing SCIA 2005 LNCS 3540 dated 2005 10 pages Omar Choudary Vincent Charvillat Romulus Grigoras and Pierre Gurdjos MARCH Mobile Augmented Reality for Cultural Heri tage MM 09 Dated Oct 19 24 2009 Beijing China 2 pages Pakemon AR Marker in Sep 2001 http pokemasters net forums showthread php t 24845 17 pages Zhang et al Visual Marker Detection and Decoding in AR Systems A Comparative Study IEEE dated 2002 10 pages Internatioanal Searching Authority Search Report in application No PCT 2012 053536 dated Nov 9 2012 10 pages Current Claims PCT 2012 053536 dated Nov 2012 5 pages International Searching Authority Search Report in application No PCT US12 53535 dated Feb 5 2013 12 pages Current Claims in application No PCT US12 53535 dated Feb 2013 5 pages U S Appl No 13 539 788 filed Jul 2 2013 Final Office Action Jun 5 2013 cited by examiner US 8 654 120 B2 Sheet 1 of 7 Feb 18 2014 U S Patent NLIS NI LONGONd WOLSNOD V SAZIIVNSIA LVH L L3SSV TW LISIG 39na08d NOILV2OT ANY OLOHd AZIYSLOVYVHO OL YSAMYVW dO OLOHd WLISIG ASN YJMYYN dO OLOHd TV1ISIG 3AI393H ALIS NI 358 VIA dO OLOHd WLISIG S35IV L YISN NOILYOO1 LY H3dVd SNOILISOd 93
34. ning Aug mented Reality Environments with Visual Tags Proceedings of DARE 2000 on Designing Apr 2000 Martin Hirzer Marker Detection for Augmented Reality Applica tions Graz University of Technology Austria Oct 27 2008 W Lee and W Woo Real time Color Correction for Marker based Augmented Reality Applications International Workshop on Ubiq uitous VR IWUVR2009 pp 32 55 2009 Nima Soltani Mehmet Yilmax Using Augmented Reality on Pla nar Surfaces for Previewing D cor Changes Stanford University EE368 Class Project Spring 2010 Pantida Patirupanusara Marker Based Augmented Reality Magic Book for Anatomical Education International Conference on Com puter and Communication Technologies ICCCT 2012 May 26 27 2012 Phuket Paul L Rosin Training Cellular Automata for Image Processing SCIA 2005 LNCS 3540 pp 195 204 2005 Omar Choudary Vincent Charvillat Romulus Grigoras and Pierre Gurdjos MARCH Mobile Augmented Reality for Cultural Heri tage MM 09 Oct 19 24 2009 Beijing China Pakemon AR Marker in Sep 2001 http www pokemasters net forums showthread php t 24845 AR tool lets you bring home a virtual Sony Bravia dated Aug 29 2011 1 page Schalkoff R J Syntactic Pattern Recognition Syntrp Overview Pattern Recognition Statistical Structural ad Neural Approaches Wiley 68 pages European Patent Office Office Action in application N
35. o 12181208 5 1238 dated Dec 6 2012 7 pages Current Claims in application No 12181208 5 1238 dated Dec 2012 4 pages U S Appl No 13 604 059 filed Sep 5 2012 Office Action Jan 2 2013 U S Appl No 13 539 788 filed Jul 2 2012 Office Action Jan 17 2013 U S Appl No 12 790 711 filed May 28 2010 Office Action Jan 3 2013 Hirokazu Kato and Mark Billnghurst ARToolkit User Manual Human Interface Technology Lab University of Washington dated 2000 44 pages Hirokazu Kato and Mark Billinghurst Marker Tracking and HMD Calibration for a Videobased Augmented Reality Conferencing Sys tem In Proceedings of the 2 International Workshop on Aug mented Reality IWAR 1999 San Francisco USA Dated Oct 1999 10 pages Mark Fiala Artag A Fiducial Marker System Using Digital Tech niques In CVRP 05 Proceedings of the 2005 IEEE Computer Society Conference on Computer vision and Pattern Recognition CVPR 2 590 596 IEEE Computer Society dated 2005 7 pages Ryan A Beasley Semiautonomous Medical Image Segmentation Using Seeded Cellular Automation Plus Edge Detector Interna tional Scholarly Research Network ISRN Signal Processing Volume dated 2012 Article ID 914232 9 pages Daniel Wagner Tobias Langlotz and Dieter Schmalstieg Robust and Unobtrusive Marker Tracking on Mobile Phones In ISMAR 08 Proceedings of the 7 IEEE ACM International Symposium on Mixed and Augmente
36. onferencing system In Proceedings of the 2nd International Workshop on Augmented Reality IWAR 99 San Francisco USA Oct 1999 Mark Fiala Artag a fiducial marker system using digital techniques In CVPR 05 Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR 05 2 590 596 IEEE Computer Society 2005 Ryan A Beasley SemiautonomousMedical Image Segmentation Using Seeded Cellular Automaton Plus Edge Detector Interna tional Scholarly Research Network ISRN Signal Processing vol 2012 Article ID 914232 9 pages Daniel Wagner Tobias Langlotz and Dieter Schmalstieg Robust and unobtrusive marker tracking on mobile phones In ISMAR 08 Pro ceedings of the 7th IEEE ACM International Symposium on Mixed and Augmented Reality pp 121 124 Washington DC USA 2008 IEEE Computer Society Johannes Kohler Alain Pagani and Didier Stricker Detection and Identification Techniques for Markers Used in Computer Vision Digital Object Identifier 10 4230 0ASIcs VLUDS 2010 36 Homayoun Bagherinia o Roberto Manduchi Robust real time detection of multi color markers on a cell phone J Real Time Image Proc Jun 3 2011 Jun Rekimoto Matrix A Realtime Object Identication and Regis tration Method for Augmented Reality Computer Human Interac tion 1998 Proceedings 3rd Asia Pacific Jul 15 17 1998 pp 63 68 Jun Rekimoto and Yuji Ayatsuka CyberCode Desig
37. 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 environ ment and may be represented by a set of delta values in image space for example A and A values The marker transform may also be used block 409 to find the dark sampling points in the user image which are used to US 8 654 120 B2 9 set a black point for rendering the digital asset Thus infor mation 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 Iuminance 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 A Process for Building a Digital Asset with Found User Site Data In an embodiment building a digital asset using the found user site data and a photograph or other digital image may involve the steps illustrated in the flowchart of FIG 5 Initially a digital asset is built using layers as follows The user photograph is adjusted block 501 using the data obtained from the light sampling points and the dark sam pling points A custom product reference is placed block 502 into the user photograph using the marker transform for pl
38. r idealized lighting and display conditions However the appearance of actual framed images may vary widely in dif ferent environments For example custom framed products typically are displayed by hanging on a wall but the appear ance of the product may vary greatly in environments such as interior rooms with different levels of lighting kinds of light ing 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 mate rial 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 US 8 654 120 B2 3 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
39. red on storage device 610 either before or after execution by processor 604 Computer system 600 also includes a communication interface 618 coupled to bus 602 Communication interface 618 provides a two way data communication coupling to a network link 620 that is connected to a local network 622 For example communication interface 618 may be an integrated services digital network ISDN card cable modem satellite modem or a modem to provide a data communication con nection to a corresponding type of telephone line As another example communication interface 618 may be a local area network LAN card to provide a data communication con nection to a compatible LAN Wireless links may also be implemented In any such implementation communication interface 618 sends and receives electrical electromagnetic or optical signals that carry digital data streams representing various types of information Network link 620 typically provides data communication through one or more networks to other data devices For example network link 620 may provide a connection through local network 622 to a host computer 624 or to data equip ment operated by an Internet Service Provider ISP 626 ISP 626 in turn provides data communication services through the world wide packet data communication network now com monly referred to as the Internet 628 Local network 622 and Internet 628 both use electrical electromagnetic or opti cal signals that carry dig
40. s to be executed by processor 604 Main memory 606 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 604 Such instructions when stored in non transitory storage media accessible to processor 604 render computer system 600 into a special purpose machine that is customized to perform the operations specified in the instructions Computer system 600 further includes a read only memory ROM 608 or other static storage device coupled to bus 602 for storing static information and instructions for processor 604 A storage device 610 such as a magnetic disk or optical disk is provided and coupled to bus 602 for storing informa tion and instructions Computer system 600 may be coupled via bus 602 to a display 612 such as a cathode ray tube CRT for displaying information to a computer user An input device 614 includ ing alphanumeric and other keys is coupled to bus 602 for communicating information and command selections to pro cessor 604 Anothertype ofuser input device is cursor control 616 such as a mouse a trackball or cursor direction keys for communicating direction information and command selec tions to processor 604 and for controlling cursor movement on display 612 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
41. tem an end user or consumer uses a general purpose computer terminal such as a personal com puter 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 0 35 40 45 50 2 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 manufac tures the product as specified and provides the custom manu factured product to the user Onetypeofproduct ofinterest not offered in typical prior systems is framed or mounted materials A frame may com prise wood molding metal pieces or plastics The mounting may include one or more mats or may comprise float mount ing The materials may include digital images of film photo graphs original digital art prints paintings animation cells or any other graphical work or work of the visual arts Indi vidualized online design and custom manufacture of such framed and mounted material is either impossible or imper fect using existing systems BRIEF DESCRIPTION OF D
42. 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 compari son 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 ofthe rendering to compen sate for the color or lighting ofthe 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 con figured both in the nature ofthe assembly as wellas the nature ofthe embellishment The system s contemplate the sharing ofthese 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
43. y a plurality of fea tures Example features that may differentiate one connectiv ity graph from another include aspects of line intersections number of lines and number of enclosed regions Embodi ments 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 Inanembodiment the form ofthe connectivity graph ofthe 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 connec tivity graph are recorded and used as a means of detecting the position and orientation ofthe 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 m
44. zed 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 202 also may be characterized by the number of adjacent polytopes associated with a node for example node 206A is associated with four 4 adjacent polytopes whereas node 206B has three 3 adjacencies Fur ther the characterization data for a particular marker enables efficient image processing for example an image recogni tion 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 characteriza tion 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 prefer ably 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 US 8 654 120 B2 7 needed to accurately recognize the marker may become pro hibitive There
Download Pdf Manuals
Related Search