(12) United States Patent
`Boncyk et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,463,030 B2
`*Jun. 11, 2013
`
`(54)
`
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`(65)
`
`(60)
`
`(60)
`
`IMAGE CAPTURE AND IDENTIFICATION
`SYSTEMAND PROCESS
`
`Inventors: Wayne C. Boncyk, Evergreen, CA (US);
`Ronald H. Cohen, Pasadena, CA (US)
`Assignee: Nant Holdings IP, LLC, Culver City,
`CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 171 days.
`This patent is Subject to a terminal dis
`claimer.
`
`Notice:
`
`Appl. No.: 13/069,124
`
`Filed:
`
`Mar 22, 2011
`
`Prior Publication Data
`US 2011/02281.26A1
`Sep. 22, 2011
`
`Related U.S. Application Data
`Division of application No. 13/037,317, filed on Feb.
`28, 2011, now Pat. No. 8,224,078, which is a division
`of application No. 12/333,630, filed on Dec. 12, 2008,
`now Pat. No. 7,899,243, which is a division of
`application No. 10/492.243, filed as application No.
`PCT/USO2/35.407 on Nov. 5, 2002, now Pat. No.
`7,477,780, which is a continuation of application No.
`09/992,942, filed on Nov. 5, 2001, now Pat. No.
`7,016,532.
`Provisional application No. 60/246.295, filed on Nov.
`6, 2000, provisional application No. 60/317,521, filed
`on Sep. 5, 2001.
`
`(51)
`
`Int. C.
`G06K 9/00
`
`(2006.01)
`
`(52) U.S. Cl.
`USPC .......................................................... 382/165
`(58) Field of Classification Search
`USPC ................. 382/181, 162, 165, 100, 305, 224,
`382/115-118; 705/26.1-27.2, 23: 348/239,
`348/211.2-211.6, 207.1, 460, 552; 713/186,
`713/168; 455/414.2–414.3, 412.1, 411;
`709/201-203, 217 219, 250
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,579,471 A 11/1996 Barber et al.
`5,615,324 A
`3/1997 Kuboyama
`5,625,765 A
`4/1997 Ellenby et al.
`5,682,332 A 10/1997 Ellenby et al.
`5,724,579 A
`3, 1998 Suzuki
`5,742,521 A
`4/1998 Ellenby et al.
`5,751,286 A
`5/1998 Barber et al.
`5,768,633. A
`6/1998 Allen et al.
`5,815,411 A
`9/1998 Ellenby et al.
`5,926, 116 A
`7/1999 Kitano et al.
`5,933,823. A
`8, 1999 Cullen et al.
`5,933,829 A
`8, 1999 Durst et al.
`(Continued)
`FOREIGN PATENT DOCUMENTS
`O920179
`6, 1999
`1O12725 A1
`6, 2000
`(Continued)
`Primary Examiner —Ishrat I Sherali
`(74) Attorney, Agent, or Firm — Fish & Associates, PC
`(57)
`ABSTRACT
`A digital image of the object is captured and the object is
`recognized from plurality of objects in a database. An infor
`mation address corresponding to the object is then used to
`access information and initiate communication pertinent to
`the object.
`
`EP
`EP
`
`38 Claims, 7 Drawing Sheets
`
`
`
`OAABASE
`MATCNG
`
`Patent Owner’s Ex. 2001, Page 1 of 23
`
`

`

`US 8,463,030 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`5,978,773. A 1 1/1999 Hudetz et al.
`5.991,827. A
`1 1/1999 Ellenby et al.
`6,031.545 A
`2/2000 Ellenby et al.
`6,037,936 A
`3/2000 Ellenby et al.
`6,055,536 A
`4/2000 Shimakawa et al.
`6,064,398 A
`5/2000 Ellenby et al.
`6,081,612 A
`6/2000 Gutkowicz-Krusin et al.
`6,098,118 A
`8/2000 Ellenby et al.
`6,108,656 A
`8/2000 Durst et al.
`6,144,848. A 1 1/2000 Walsh et al.
`6,173,239 B1
`1/2001 Ellenby
`6,181,817 B1
`1/2001 Zabih et al.
`6,182,090 B1
`1/2001 Peairs
`6, 199,048 B1
`3/2001 Hudetz et al.
`6,208,749 B1
`3/2001 Gutkowicz-Krusin et al.
`6.256,409 B1
`7/2001 Wang
`6,278.461 B1
`8/2001 Ellenby et al.
`6,286,036 B1
`9/2001 Rhoads
`6,307,556 B1 10/2001 Ellenby et al.
`6,307,957 B1
`10/2001 Gutkowicz-Krusin et al.
`6,393,147 B2
`5/2002 Danneels et al.
`6,396.475 B1
`5/2002 Ellenby et al.
`6,396,537 B1
`5/2002 Squilla et al.
`6,411,725 B1
`6/2002 Rhoads
`6,414,696 B1
`7/2002 Ellenby et al.
`6,430,554 B1
`8, 2002 Rothschild
`6,434,561 B1
`8/2002 Durst, Jr. et al.
`6,453,361 B1
`9, 2002 Morris
`6,522,292 B1
`2/2003 Ellenby et al.
`6.522.889 B1
`2/2003 Aarnio
`6.532.298 B1
`3/2003 Cambier et al.
`653.5210 B1
`3/2003 Ellenby et al.
`6,542.933 B1
`4/2003 Durst, Jr. et al.
`6,567,122 B1
`5/2003 Anderson et al.
`6,651,053 B1 1 1/2003 Rothschild
`6,674,923 B1
`1/2004 Shih et al.
`6,674,993 B1
`1/2004 Tarbouriech
`6,675,165 B1
`1/2004 Rothschild
`6,690,370 B2
`2/2004 Ellenby et al.
`6,691.914 B2
`2, 2004 Isherwood et al.
`6,714,969 B1
`3, 2004 Klein et al.
`6,724.914 B2
`4/2004 Brundage et al.
`6,738,630 B2
`5, 2004 Ashmore
`6,766,363 B1
`7/2004 Rothschild
`6,804,726 B1
`10/2004 Ellenby et al.
`6,842,181 B2
`1/2005 Acharya
`6,865,608 B2
`3/2005 Hunter
`6,885,771 B2
`4/2005 Takahashi
`6,993,573 B2
`1/2006 Hunter
`7,016,532 B2
`3/2006 Boncyk et al.
`7,031,536 B2
`4/2006 Kajiwara
`7,031,875 B2
`4/2006 Ellenby et al.
`7,127,094 B1
`10/2006 Elbaum et al.
`7,245,273 B2
`7, 2007 Eberlet al.
`7,362.922 B2
`4/2008 Nishiyama et al.
`7,383.209 B2
`6, 2008 Hudetz et al.
`7,430,588 B2
`9, 2008 Hunter
`7,641,342 B2
`1/2010 Eberlet al.
`7,696,905 B2
`4/2010 Ellenby et al.
`
`388 Hudetz ity al
`7,765,126 B2
`8, 2010 Pentenrieder et al.
`7,768,534 B2
`2/2011 Platonov et al.
`7.889,193 B2
`3/2011 John et al.
`7.916,138 B2
`8,218,874 B2 * 7/2012 Boncyk et al. ................ 382, 181
`2001/001 1276 A1
`8/2001 Durst, Jr. et al.
`2001/0032252 A1 10, 2001 Durst et al.
`2001/0044824 A1 11/2001 Hunter et al.
`2001/0047426 A1 11, 2001 Hunter
`2002/00 19819 A1
`2/2002 Sekiguchi et al.
`2002fOO55957 A1
`5, 2002 Ohsawa
`2002fOO895.24 A1
`7, 2002 Ikeda
`2002/0090 132 A1
`7/2002 Boncyk et al.
`2002/0102966 A1
`8, 2002 Lev et al.
`2002/0103813 A1
`8/2002 Frigon
`2002fO140988 A1 10, 2002 Cheatle et al.
`2002/0156866 A1 10, 2002 Schneider
`2002/0163521 A1 1 1/2002 Ellenby et al.
`2003/0095681 A1
`5/2003 Burg et al.
`2004/0208.372 A1 10/2004 Boncyk et al.
`2005/00 15370 A1
`1/2005 Stavely et al.
`2005.0024501 A1
`2/2005 Ellenby et al.
`2005, 0162523 A1
`7, 2005 Darrell et al.
`2005/0185060 A1
`8/2005 Neven, Sr.
`2006/0161379 A1
`7/2006 Ellenby et al.
`2006/0190812 A1
`8/2006 Ellenby et al.
`2007, 01096.19 A1
`5, 2007 Eberlet al.
`2007, 0146391 A1
`6/2007 Pentenrieder et al.
`2007/0182739 A1
`8, 2007 Platonov et al.
`2008, 0021953 A1
`1, 2008 G1
`2008. O157946 A1
`7/2008 Eberlet al.
`2010.0045933 A1
`2/2010 Eberlet al.
`2010.0188638 A1
`7/2010 Eberlet al.
`FOREIGN PATENT DOCUMENTS
`EP
`1354260 A2 10, 2003
`EP
`1355.258
`10, 2003
`EP
`2264669
`12/2010
`GB
`2407230
`4/2005
`JP
`109 1634
`4f1998
`JP
`10289243
`10, 1998
`JP
`2001101.191
`4/2001
`JP
`2001282825
`10, 2001
`WO
`97,49060
`12/1997
`WO
`98.37811
`9, 1998
`WO
`9916O24
`4f1999
`WO
`9942946 A2
`8, 1999
`WO
`9942947 A2
`8, 1999
`WO
`99.44010
`9, 1999
`WO
`O 124.050
`4/2001
`WO
`O149056
`T 2001
`WO
`O163487 A1
`8, 2001
`WO
`O171282 A1
`9, 2001
`WO
`O173603
`10, 2001
`WO
`O2/O1143
`1, 2002
`WO
`O2O59716 A2
`8, 2002
`WO
`02073818 A1
`9, 2002
`WO
`O2O82799
`10, 2002
`* cited by examiner
`
`Patent Owner’s Ex. 2001, Page 2 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 1 of 7
`
`US 8,463,030 B2
`
`0
`
`OBJECT
`MAGE
`
`SYMBOLIC
`MAGE
`
`INPUT IMAGE
`OECOMPOSTON
`
`
`
`DATABASE
`MATCHING
`
`
`
`
`
`
`
`
`
`F.G. 1
`
`SELECT BEST
`MATCH
`
`4 O
`
`4 2.
`
`Patent Owner’s Ex. 2001, Page 3 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 11, 2013
`Jun. 11, 2013
`
`Sheet 2 of 7
`Sheet 2 of 7
`
`US 8,463,030 B2
`US 8,463,030 B2
`
`
`
` Patent Owner’s Ex. 2001, Page 4 of 23
`
`Patent Owner’s Ex. 2001, Page 4 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 3 of 7
`
`US 8,463,030 B2
`
`START
`
`FOREACH NPUT IMAGE
`SEGMENT GROUP
`
`FOREACH OBJECTIN
`DATABASE
`
`FOREACH WIEW OF THIS
`OBJECT
`
`FOREACHSEGMENT
`GROUP N THIS WEW
`
`GREYSCALE
`COMPARSON
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WAVELET
`COMPARSON
`
`F.G. 3A
`
`Patent Owner’s Ex. 2001, Page 5 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 4 of 7
`
`US 8,463,030 B2
`
`CALCULATE COMBINED
`MATCHSCORE
`
`NEXTSEGMENT GROUPN
`THIS DATABASE VIEW
`
`NEXT WEW OF THIS
`DATABASE OBJECT
`
`NEXT OBJECTIN
`DATABASE .
`
`NEXT INPUT IMAGE
`SEGMENT GROUP
`
`FIG. 3B
`
`FNSE
`
`Patent Owner’s Ex. 2001, Page 6 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 5 of 7
`
`US 8,463,030 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TARGET
`OBJECT
`
`CONTENT
`SERVER
`
`02
`
`10 O
`
`1
`
`1.
`
`FIG. 4
`
`
`
`
`
`MAGE
`PROCESSING
`
`BROWSER
`
`MAGE DATA
`
`
`
`S
`
`1 O 7
`
`1.
`
`
`
`TARGET
`OBJECT
`INFORMATION
`
`
`
`OBJECT
`RECOGNITION
`
`
`
`DATABASE
`
`IDENT FICATION SERVER
`
`Patent Owner’s Ex. 2001, Page 7 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 6 of 7
`
`US 8,463,030 B2
`
`TARGET
`OBJECT
`
`
`
`CONTENT
`SERVER
`
`2.
`O 2.
`
`
`
`2 OO
`
`21
`
`FIG 5
`
`CAMERA
`
`MAGE
`PROCESSING
`
`
`
`
`
`BROWSER
`
`TERMINAL
`
`
`
`
`
`MAGE DATA
`
`
`
`2. OS
`
`TARGET
`OBJECT
`NFORMATION
`
`
`
`
`
`
`
`
`
`OBJECT
`RECOGNITION
`
`
`
`DATABASE
`
`DENTIFICATION SERVER
`
`Patent Owner’s Ex. 2001, Page 8 of 23
`
`

`

`U.S. Patent
`
`Jun. 11, 2013
`
`Sheet 7 Of 7
`
`US 8,463,030 B2
`
`TARGET
`OBJECT
`
`SPACECRAFT
`DATA SYSTEM
`
`3 O 2
`
`3 O O
`
`31 O
`
`
`
`CAMERA
`
`MAGE
`PROCESSING
`
`F.G. 6
`
`MAGE DATA
`
`
`
`TARGET
`OBJECT
`INFORMATION
`
`305
`3 O 7
`
`3 O 9
`
`308
`
`
`
`3 O 6
`
`
`
`
`
`OBJECT
`RECOGNITION
`
`DATABASE
`
`DENTIFICATION SERVER
`
`Patent Owner’s Ex. 2001, Page 9 of 23
`
`

`

`US 8,463,030 B2
`
`1.
`IMAGE CAPTURE AND IDENTIFICATION
`SYSTEMAND PROCESS
`
`This application is a divisional of Ser. No. 13/037,317 filed
`Feb. 28, 2011 which is a divisional of Ser. No. 12/333,630
`filed Dec. 12, 2008 which is a divisional of Ser. No. 10/492,
`243 filed Apr. 9, 2004 which is a National Phase of PCT/
`US02/35.407 filed Nov. 5, 2002. These and all other refer
`enced patents and applications are incorporated herein by
`reference in their entirety. Where a definition or use of a term
`in a reference that is incorporated by reference is inconsistent
`or contrary to the definition of that term provided herein, the
`definition of that term provided herein is deemed to be con
`trolling.
`
`10
`
`15
`
`TECHNICAL FIELD
`
`The invention relates an identification method and process
`for objects from digitally captured images thereof that uses
`image characteristics to identify an object from a plurality of
`objects in a database.
`
`BACKGROUND ART
`
`2
`wireless device and then execution of communications or
`transactions between the mobile wireless device and the
`machine;
`identification of objects or parts in a factory, Such as on an
`assembly line, by capturing an image of the objects or parts,
`and then providing information pertinent to the identified
`objects or parts;
`identification of a part of a machine. Such as an aircraft part,
`by a technician pointing and clicking on the part with a
`camera-equipped mobile wireless device, and then Supplying
`pertinent content to the technician, such maintenance instruc
`tions or history for the identified part;
`identification or screening of individual(s) by a security
`officer pointing and clicking a camera-equipped mobile
`wireless device at the individual(s) and then receiving iden
`tification information pertinent to the individuals after the
`individuals have been identified by face recognition software:
`identification, Screening, or validation of documents, such
`as passports, by a security officer pointing and clicking a
`camera-equipped device at the document and receiving a
`response from a remote computer;
`determination of the position and orientation of an object in
`space by a spacecraft nearby the object, based on imagery of
`the object, so that the spacecraft can maneuver relative to the
`object or execute a rendezvous with the object;
`identification of objects from aircraft or spacecraft by cap
`turing imagery of the objects and then identifying the objects
`via image recognition performed on a local or remote com
`puter;
`watching movie previews streamed to a camera-equipped
`wireless device by "pointing and clicking with such a device
`on a movie theatre sign or poster, or on a digital video disc box
`or videotape box:
`listening to audio recording samples streamed to a camera
`equipped wireless device by “pointing and clicking with
`Such a device on a compact disk (CD) box, Videotape box, or
`print media advertisement;
`purchasing movie, concert, or sporting event tickets by
`"pointing and clicking on a theater, advertisement, or other
`object with a camera-equipped wireless device;
`purchasing an item by "pointing and clicking on the
`object with a camera-equipped wireless device and thus ini
`tiating a transaction;
`interacting with television programming by “pointing and
`clicking at the television screen with a camera-equipped
`device, thus capturing an image of the screen content and
`having that image sent to a remote computer and identified,
`thus initiating interaction based on the screen content
`received (an example is purchasing an item on the television
`screen by "pointing and clicking at the screen when the item
`is on the screen);
`interacting with a computer-system based game and with
`other players of the game by “pointing and clicking on
`objects in the physical environment that are considered to be
`part of the game;
`paying a bus fare by “pointing and clicking with a mobile
`wireless camera-equipped device, on a fare machine in a bus,
`and thus establishing a communications link between the
`device and the fare machine and enabling the fare payment
`transaction;
`establishment of a communication between a mobile wire
`less camera-equipped device and a computer with an Internet
`connection by pointing and clicking with the device on the
`computer and thus providing to the mobile device an Internet
`address at which it can communicate with the computer, thus
`establishing communications with the computer despite the
`
`25
`
`30
`
`40
`
`45
`
`There is a need to provide hyperlink functionality in known
`objects without modification to the objects, through reliably
`detecting and identifying the objects based only on the
`appearance of the object, and then locating and Supplying
`information pertinent to the object or initiating communica
`tions pertinent to the object by Supplying an information
`address, such as a Uniform Resource Locator (URL), perti
`nent to the object.
`There is a need to determine the position and orientation of
`known objects based only on imagery of the objects.
`The detection, identification, determination of position and
`35
`orientation, and Subsequent information provision and com
`munication must occur without modification or disfigure
`ment of the object, without the need for any marks, symbols,
`codes, barcodes, or characters on the object, without the need
`to touch or disturb the object, without the need for special
`lighting other than that required for normal human vision,
`without the need for any communication device (radio fre
`quency, infrared, etc.) to be attached to or nearby the object,
`and without human assistance in the identification process.
`The objects to be detected and identified may be 3-dimen
`sional objects, 2-dimensional images (e.g., on paper), or 2-di
`mensional images of 3-dimensional objects, or human
`beings.
`There is a need to provide such identification and hyperlink
`services to persons using mobile computing devices, such as
`Personal Digital Assistants (PDAs) and cellular telephones.
`There is a need to provide such identification and hyperlink
`services to machines, such as factory robots and spacecraft.
`Examples include:
`identifying pictures or other art in a museum, where it is
`desired to provide additional information about such art
`objects to museum visitors via mobile wireless devices;
`provision of content (information, text, graphics, music,
`Video, etc.), communications, and transaction mechanisms
`between companies and individuals, via networks (wireless
`or otherwise) initiated by the individuals “pointing and click
`ing with camera-equipped mobile devices on magazine
`advertisements, posters, billboards, consumer products,
`music or video disks or tapes, buildings, vehicles, etc.;
`establishment of a communications link with a machine,
`Such a vending machine or information kiosk, by pointing
`and clicking on the machine with a camera-equipped mobile
`
`50
`
`55
`
`60
`
`65
`
`Patent Owner’s Ex. 2001, Page 10 of 23
`
`

`

`US 8,463,030 B2
`
`3
`absence of a local network or any direct communication
`between the device and the computer;
`use of a mobile wireless camera-equipped device as a
`point-of-sale terminal by, for example, "pointing and click
`ing on an item to be purchased, thus identifying the item and
`initiating a transaction.
`
`DISCLOSURE OF INVENTION
`
`The present invention solves the above stated needs. Once
`an image is captured digitally, a search of the image deter
`mines whether symbolic content is included in the image. If
`so the symbol is decoded and communication is opened with
`the proper database, usually using the Internet, wherein the
`best match for the symbol is returned. In some instances, a
`symbol may be detected, but non-ambiguous identification is
`not possible. In that case and when a symbolic image can not
`be detected, the image is decomposed through identification
`algorithms where unique characteristics of the image are
`determined. These characteristics are then used to provide the
`best match or matches in the database, the “best determina
`tion being assisted by the partial symbolic information, if that
`is available.
`Therefore the present invention provides technology and
`processes that can accommodate linking objects and images
`to information via a network such as the Internet, which
`requires no modification to the linked object. Traditional
`methods for linking objects to digital information, including
`applying a barcode, radio or optical transceiver or transmitter,
`or some other means of identification to the object, or modi
`fying the image or object so as to encode detectable informa
`tion in it, are not required because the image or object can be
`identified solely by its visual appearance. The users or devices
`may even interact with objects by “linking to them. For
`example, a user may link to a vending machine by “pointing
`and clicking on it. His device would be connected over the
`Internet to the company that owns the vending machine. The
`company would in turn establish a connection to the vending
`machine, and thus the user would have a communication
`channel established with the vending machine and could
`interact with it.
`The decomposition algorithms of the present invention
`allow fast and reliable detection and recognition of images
`and/or objects based on their visual appearance in an image,
`no matter whether shadows, reflections, partial obscuration,
`and variations in viewing geometry are present. As stated
`above, the present invention also can detect, decode, and
`identify images and objects based on traditional symbols
`which may appear on the object, Such as alphanumeric char
`acters, barcodes, or 2-dimensional matrix codes.
`When a particular object is identified, the position and
`orientation of an object with respect to the user at the time the
`image was captured can be determined based on the appear
`ance of the object in an image. This can be the location and/or
`identity of people scanned by multiple cameras in a security
`system, a passive locator system more accurate than GPS or
`usable in areas where GPS signals cannot be received, the
`location of specific vehicles without requiring a transmission
`from the vehicle, and many other uses.
`When the present invention is incorporated into a mobile
`device. Such as a portable telephone, the user of the device can
`link to images and objects in his or her environment by
`pointing the device at the object of interest, then "pointing and
`clicking to capture an image. Thereafter, the device trans
`mits the image to another computer (“Server”), wherein the
`image is analyzed and the object or image of interest is
`detected and recognized. Then the network address of infor
`
`4
`mation corresponding to that object is transmitted from the
`(“Server) back to the mobile device, allowing the mobile
`device to access information using the network address so
`that only a portion of the information concerning the object
`need be stored in the systems database.
`Some or all of the image processing, including image?
`object detection and/or decoding of symbols detected in the
`image may be distributed arbitrarily between the mobile (Cli
`ent) device and the Server. In other words, some processing
`may be performed in the Client device and some in the Server,
`without specification of which particular processing is per
`formed in each, or all processing may be performed on one
`platform or the other, or the platforms may be combined so
`that there is only one platform. The image processing can be
`implemented inaparallel computing manner, thus facilitating
`Scaling of the system with respect to database size and input
`traffic loading.
`Therefore, it is an object of the present invention to provide
`a system and process for identifying digitally captured
`images without requiring modification to the object.
`Another object is to use digital capture devices in ways
`never contemplated by their manufacturer.
`Another object is to allow identification of objects from
`partial views of the object.
`Another object is to provide communication means with
`operative devices without requiring a public connection
`therewith.
`These and other objects and advantages of the present
`invention will become apparent to those skilled in the art after
`considering the following detailed specification, together
`with the accompanying drawings wherein:
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic block diagram top-level algorithm
`flowchart;
`FIG. 2 is an idealized view of image capture;
`FIGS. 3A and 3B are a schematic block diagram of process
`details of the present invention;
`FIG. 4 is a schematic block diagram of a different expla
`nation of invention;
`FIG. 5 is a schematic block diagram similar to FIG. 4 for
`cellular telephone and personal data assistant (PDA) applica
`tions; and
`FIG. 6 is a schematic block diagram for spacecraft appli
`cations.
`
`BEST MODES FOR CARRYING OUT THE
`INVENTION
`
`The present invention includes a novel process whereby
`information Such as Internet content is presented to a user,
`based solely on a remotely acquired image of a physical
`object. Although coded information can be included in the
`remotely acquired image, it is not required since no additional
`information about a physical object, other than its image,
`needs to be encoded in the linked object. There is no need for
`any additional code or device, radio, optical or otherwise, to
`be embedded in or affixed to the object. Image-linked objects
`can be located and identified within user-acquired imagery
`solely by means of digital image processing, with the address
`of pertinent information being returned to the device used to
`acquire the image and perform the link. This process is robust
`against digital image noise and corruption (as can result from
`lossy image compression/decompression), perspective error,
`rotation, translation, Scale differences, illumination varia
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Patent Owner’s Ex. 2001, Page 11 of 23
`
`

`

`5
`tions caused by different lighting Sources, and partial obscu
`ration of the target that results from shadowing, reflection or
`blockage.
`Many different variations on machine vision “target loca
`tion and identification' exist in the current art. However, they
`all tend to provide optimal solutions for an arbitrarily
`restricted search space. At the heart of the present invention is
`a high-speed image matching engine that returns unambigu
`ous matches to target objects contained in a wide variety of
`potential input images. This unique approach to image match
`ing takes advantage of the fact that at least Some portion of the
`target object will be found in the user-acquired image. The
`parallel image comparison processes embodied in the present
`search technique are, when taken together, unique to the
`process. Further, additional refinement of the process, with
`the inclusion of more and/or different decomposition-param
`eterization functions, utilized within the overall structure of
`the search loops is not restricted. The detailed process is
`described in the following. FIG. 1 shows the overall process
`ing flow and steps. These steps are described in further detail
`in the following sections.
`For image capture 10, the User 12 (FIG. 2) utilizes a com
`puter, mobile telephone, personal digital assistant, or other
`similar device 14 equipped with an image sensor (Such as a
`CCD or CMOS digital camera). The User 12 aligns the sensor
`of the image capture device 14 with the object 16 of interest.
`The linking process is then initiated by Suitable means includ
`ing: the User 12 pressing a button on the device 14 or sensor;
`by the Software in the device 14 automatically recognizing
`that an image is to be acquired; by Uservoice command; or by
`any other appropriate means. The device 14 captures a digital
`image 18 of the scene at which it is pointed. This image 18 is
`represented as three separate 2-D matrices of pixels, corre
`sponding to the raw RGB (Red, Green, Blue) representation
`of the input image. For the purposes of standardizing the
`analytical processes in this embodiment, if the device 14
`Supplies an image in other than RGB format, a transformation
`to RGB is accomplished. These analyses could be carried out
`in any standard color format, should the need arise.
`If the server 20 is physically separate from the device 14,
`then user acquired images are transmitted from the device 14
`to the Image Processor/Server 20 using a conventional digital
`network or wireless network means. If the image 18 has been
`compressed (e.g. via lossy JPEG DCT) in a manner that
`introduces compression artifacts into the reconstructed image
`18, these artifacts may be partially removed by, for example,
`applying a conventional despeckle filter to the reconstructed
`image prior to additional processing.
`The Image Type Determination 26 is accomplished with a
`discriminator algorithm which operates on the input image 18
`and determines whether the input image contains recogniz
`able symbols, such as barcodes, matrix codes, or alphanu
`meric characters. If Such symbols are found, the image 18 is
`sent to the Decode Symbol 28 process. Depending on the
`confidence level with which the discriminator algorithm finds
`the symbols, the image 18 also may or alternatively containan
`object of interest and may therefore also or alternatively be
`sent to the Object Image branch of the process flow. For
`example, if an input image 18 contains both a barcode and an
`object, depending on the clarity with which the barcode is
`detected, the image may be analyzed by both the Object
`Image and Symbolic Image branches, and that branch which
`has the highest success in identification will be used to iden
`tify and link from the object.
`The image is analyzed to determine the location, size, and
`nature of the symbols in the Decode Symbol 28. The symbols
`are analyzed according to their type, and their content infor
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 8,463,030 B2
`
`10
`
`15
`
`6
`mation is extracted. For example, barcodes and alphanumeric
`characters will result in numerical and/or text information.
`For object images, the present invention performs a
`“decomposition', in the Input Image Decomposition 34, of a
`high-resolution input image into several different types of
`quantifiable salient parameters. This allows for multiple inde
`pendent convergent search processes of the database to occur
`in parallel, which greatly improves image match speed and
`match robustness in the Database Matching 36. The Best
`Match 38 from either the Decode Symbol 28, or the image
`Database Matching 36, or both, is then determined. If a spe
`cific URL (or other online address) is associated with the
`image, then an URL Lookup 40 is performed and the Internet
`address is returned by the URL Return 42.
`The overall flow of the Input Image Decomposition pro
`cess is as follows:
`
`Radiometric Correction
`Segmentation
`Segment Group Generation
`FOR each segment group
`Bounding Box Generation
`Geometric Normalization
`Wavelet Decomposition
`Color Cube Decomposition
`Shape Decomposition
`Low-Resolution Grayscale Image Generation
`FOREND
`
`Each of the above steps is explained in further detail below.
`For Radiometric Correction, the input image typically is
`transformed to an 8-bit per color plane, RGB representation.
`The RGB image is radiometrically normalized in all three
`channels. This normalization is accomplished by linear gain
`and offset transformations that result in the pixel values
`within each color channel spanning a full 8-bit dynamic range
`(256 possible discrete values). An 8-bit dynamic range is
`adequate but, of course, as optical capture devices produce
`higher resolution images and computers get faster and
`memory gets cheaper, higher bit dynamic ranges, such as
`16-bit, 32-bit or more may be used.
`For Segmentation, the radiometrically normalized RGB
`image is analyzed for “segments, or regions of similar color,
`i.e. near equal pixel values for red, green, and blue. These
`segments are defined by their boundaries, which consist of
`sets of (x, y) point pairs. A map of segment boundaries is
`produced, which is maintained separately from the RGB
`input image and is formatted as an x, y binary image map of
`the same aspect ratio as the RGB image.
`For Segment Group Generation, the segments are grouped
`into all possible combinations. These groups are known as
`“segment groups' and representall possible potential images
`or objects of interest in the input image. The segment groups
`are sorted based on the order in which they will be evaluated.
`Various evaluation order schemes are possible. The particular
`embodiment explained herein utilizes the following “center
`out' scheme: The first segment group comprises only the
`segment that includes the center of the image. The next seg
`ment group comprises the previous segment plus the segment
`which is the largest (in number of pixels) and which is adja
`cent to (touching) the previous segment group. Additional
`segments are added using the segment criteria above until no
`segments remain. Bach step, in which a new segment is
`added, creates a new and unique segment group.
`For Bounding Box Generation, the elliptical major axis of
`the segment group under consideration (the major axis of an
`ellipse just large enough to contain the entire segment group)
`
`Patent Owner’s Ex. 2001, Page 12 of 23
`
`

`

`US 8,463,030 B2
`
`7
`is computed. Then a rectangle is constructed within the image
`coordinate system, with long sides parallel to the elliptical
`major axis, of a size just large enough to completely contain
`every pixel in the segment group.
`For Geometric Normalization, a copy of the input image is
`modified Such that all pixels not included in the segment
`group under consideration are set to mid-level gray. The result
`is then resampled and mapped into a 'standard aspect' output
`test image space Such that the corners of the bounding box are
`mapped into the corners of the output test image. The standard
`aspect is the same size and aspect ratio as the Reference
`images used to create the database.
`For Wavelet Decomposition, a grayscale representation of
`the full-color image is produced from the geometrically nor
`malized image that resulted from the Geometric Normaliza
`tion step. The following procedure is used to derive the gray
`scale representation. Reduce the three color planes into one
`grayscale image by proportionately adding each R, G, and B
`pixel of the standard corrected color image using the follow
`ing formula:
`
`10
`
`15
`
`8
`image is produced by weighted averaging of pixels within
`each 3x3 cell. The result is contrast binned, by reducing the
`number of discrete values assignable to each pixel based upon
`substituting a “binned average value for all pixels that fall
`within a discrete (TBD) number of brightness bins.
`The above discussion of the particular decomposition
`methods incorporated into this embodiment are not intended
`to indicate that more, or alternate, decomposition methods
`may not also be employed within the context of this invention.
`In other words:
`
`FOR each input image segment group
`FOR each database object
`FOR each view of this object
`FOR each segment group in this view of this database
`object
`Shape Comparison
`Grayscale Comparison
`Wavelet Comparison
`Color Cube Comparison
`Calculate Combined Match Score
`END FOR
`END FOR
`END FOR
`END FOR
`
`Each of the above steps is explained in further detail below.
`FOR Each Input Image Segment Group
`This loop considers each combination of segment groups
`in the input image, in the order in which they were sor