Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 1 of 13 Page ID #:465
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 1of13 Page ID #:465
`
`
`
`
`
`
`
`
`
`
`EXHIBIT A
`EXHIBIT A
`
`

`

`US007881529B2
`
`(12) United States Patent
`Boncyk et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,881,529 B2
`*Feb. 1, 2011
`
`(54) DATA CAPTURE AND IDENTIFICATION
`SYSTEM AND PROCESS
`
`(75) Inventors: Wa ne C Bonc k, Fontana, CA US ;
`y
`y
`Ronald H Cohen, Pasadena, CA (Us)
`
`(73) Assignee: Evryx Technologies, Inc., Los Angeles,
`CA (U S)
`
`(58) Field of Classi?cation Search ....... .. 382/115*118,
`382/162, 165, 170, 100, 181, 305, 224, 218;
`348/239, 141414.16, 211.2*211.6, 207.1,
`348/460, 552; 7O7/1T7, 1041; 7o5/26i27,
`705/23; 455/414.2, 456.3, 556.1, 412.1,
`455/5562, 419; 709/201*203, 2174219,
`709/250
`See application ?le for complete search history.
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis-
`Claimer'
`
`_
`(21) Appl' NO" 12/505’714
`.
`_
`(22) Flled'
`
`(65)
`
`“1'20, 2009
`_
`_
`_
`Prior Publication Data
`Us 2010/0011058 A1
`Jan. 14, 2010
`
`Related US. Application Data
`(63) Continuation of application No. 11/342,094, ?led on
`Jan. 26, 2006, noW Pat. No. 7,565,008, Which is a
`connnuanon'm'pan of apphcanon NO‘ 09/992,942’
`?led on NOV' 5’ 2001’ HOW Pat' NO' 7,016,532
`(60) Provisional application No. 60/317,521, ?led on Sep.
`5, 2001, provisional application NO 60/246’295s ?led
`on NOV_ 6, 2000
`
`(51) Int, Cl,
`(2006.01)
`G06K 9/00
`(52) US. Cl. .................................................... .. 382/165
`
`(56)
`
`References Cited
`Us PATENT DOCUMENTS
`
`2/2003 Aarnio
`6,522,889 B1
`V2004 Tarbounech
`6,674,993 B1
`4/2004 Brundage et a1.
`6,724,914 B2
`7,016,532 B2* 3/2006 Boncyk et a1. ............ .. 382/165
`2002/0019819 A1
`2/2002 Sekiguchi et a1.
`2003/0095681 A1
`5/2003 Burg et a1.
`2005/0015370 A1
`1/2005 Stavely et a1.
`2005/0185060 A1
`8/2005 Neven
`2008/0021953 A1
`1/2008 Gil
`
`'
`* 't db
`C1 e y exammer
`Primary ExamineriSherali lshrat
`(74) Attorney, Agent, or FirmiFish & Associates, PC
`
`ABSTRACT
`(57)
`An identi?cation method and process for objects from digi
`tally captured images thereof that uses data characteristics to
`identify 211} Object from a Plurality of Objects in a database
`The data 1s broken doWn mto parameters such as a Shape
`Comparison, Grayscale Comparison, Wavelet Comparison,
`and Color Cube Comparison With object data in one or more
`databases to identify the actual object of a digital image.
`
`27 Claims, 4 Drawing Sheets
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 2 of 13 Page ID #:466
`
`INPUT IMAGE /1 0
`CAPTURE
`
`SYMBOLIC
`IMAGE
`
`1
`
`DEmDE
`2 s / SYMBOL
`
`OBJECT
`IMAGE
`
`‘
`
`INPUT IMAGE
`DECOMPOSITION \3 4
`l
`DATABASE
`
`2 6
`
`MATCHING \3 6
`
`3 s
`
`SELECTBEST
`MATCH
`
`i
`4 0
`\ URLLOOKUP
`
`j
`4 2 \T URLRETURN
`
`

`

`US. Patent
`
`Feb. 1, 2011
`
`Sheet 1 014
`
`US 7,881,529 B2
`
`INPUT IMAGE
`CAPTURE
`
`1 0
`
`OBJECT
`IMAGE
`
`W SYMB OLIC
`IMAGE
`
`INPUT IMAGE
`DECOMPOSITION \ 3 4
`
`2 6
`
`l
`DECODE
`2 s / SYMBOL
`
`DATABASE
`MATCHING \ 3 6
`
`4
`3 s \ SELECT BEST
`MATCH
`,___T_
`4 0
`\ URL LOOKUP
`____£___
`4 2
`\ URL RETURN
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 3 of 13 Page ID #:467
`
`

`

`US. Patent
`
`Feb. 1, 2011
`
`Sheet 2 0f 4
`
`US 7,881,529 B2
`
`@r
`
`/
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 4 of 13 Page ID #:468
`
`y
`.\ 8K
`
`

`

`US. Patent
`
`Feb. 1, 2011
`
`Sheet 3 014
`
`US 7,881,529 B2
`
`FOR EACH INPUT IMAGE
`SEGMENT GROUP
`
`E
`
`FOR EACH OBJECT IN
`DATABASE
`
`I
`
`FOR EACH VIEW OF THIS
`OBJECT
`
`__T_____
`
`FOR EA CH SEGMENT
`GROUP IN THIS VIEW
`
`GREYSCALE
`COMPARISON
`
`COLORCUBE
`COMPARISON
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 5 of 13 Page ID #:469
`
`SHAPE
`COMPARISON
`
`WAVELET
`COMPARISON
`
`4'
`
`FIG. 3A
`
`

`

`US. Patent
`
`Feb. 1, 2011
`
`Sheet 4 014
`
`US 7,881,529 B2
`
`l
`
`CALCULATE COMBINED
`MATCH SCORE
`
`NEXT SEGMENT GROUP IN *
`THIS DATABASE VIEW
`
`NEXT VIEW OF THIS
`DATABASE OBJECT
`
`NEXT OBJECT IN
`DATABASE
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 6 of 13 Page ID #:470
`
`NEXT INPUT IMAGE
`SEGMENT GROUP
`
`FIG. 3B
`
`

`

`US 7,881,529 B2
`
`1
`DATA CAPTURE AND IDENTIFICATION
`SYSTEM AND PROCESS
`
`This application is a Continuation of US. application Ser.
`No. 11/342,094 ?led Jan. 26, 2006 now US. Pat. No. 7,565,
`008, Which is a CIP of US. application Ser. No. 09/992,942
`?led Nov. 5, 2001 now US. Pat. No. 7,016,532, Which claims
`priority to US. Provisional Application No. 60/317,521 ?led
`Sep. 5, 2001, and US. Provisional Application No. 60/246,
`295 ?led Nov. 6, 2000. These and all other extrinsic refer
`ences are incorporated herein by reference in their entirety.
`Where a de?nition or use of a term in an incorporated refer
`ence is inconsistent or contrary to the de?nition of that term
`provided herein, the de?nition of that term provided herein
`applies and the de?nition of that term in the reference does not
`apply.
`This application is a continuation-in-part of US. applica
`tion Ser. No. 09/992,942 ?led Nov. 5, 2001 Which claims the
`bene?t of US. Provisional Application No. 60/317,521 ?led
`on Sep. 5, 2001 and US. Provisional Application No. 60/ 246,
`295 ?led on Nov. 6, 2000.
`
`20
`
`FIELD OF THE INVENTION
`
`The invention relates an identi?cation method and process
`for objects from digitally captured images thereof that uses
`data characteristics to identify an object from a plurality of
`objects in a database.
`
`25
`
`BACKGROUND OF THE INVENTION
`
`There is a need to identify an object that has been digitally
`captured from a database of images Without requiring modi
`?cation or dis?guring of the object. Examples include:
`identifying pictures or other art in a large museum, Where
`it is desired to provide additional information about objects in
`the museum by means of a mobile display so that the museum
`may display objects of interest in the museum and ensure that
`displays are not hidden or croWded out by signs or computer
`screens;
`establishing a communications link With a machine by
`merely taking a visual data of the machine; and
`calculating the position and orientation of an object based
`on the appearance of the object in a data despite shadoWs,
`re?ections, partial obscuration, and variations in vieWing
`geometry, or other obstructions to obtaining a complete
`image. Data capture hardWare such as a portable telephones
`With digital cameras included are noW coming on the market
`and it is desirable that they be useful for duties other than
`picture taking for transmission to a remote location. It is also
`desirable that any identi?cation system uses available com
`puting poWer e?iciently so that the computing required for
`such identi?cation can be performed locally, shared With an
`Internet connected computer or performed remotely, depend
`ing on the database siZe and the available computing poWer.
`In addition, it is desirable that any such identi?cation system
`can use existing identi?cation markings such as barcodes,
`special targets, or Written language When such is available to
`speed up searches and data information retrieval.
`
`SUMMARY OF THE INVENTION
`
`The present invention solves the above stated needs. Once
`a data is captured digitally, a search of the data determines
`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
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`match for the symbol is returned. In some instances, a symbol
`may be detected, but non-ambiguous identi?cation is not
`possible. In that case and When a symbolic data can not be
`detected, the data is decomposed through identi?cation algo
`rithms Where unique characteristics of the data are deter
`mined. These characteristics are then used to provide the best
`match or matches in the data-base, the “best” determination
`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 modi?cation 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 identi?cation to the object, or modi
`fying the data or object so as to encode detectable information
`in it, are not required because the data or object can be
`identi?ed 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, re?ections, 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 identi?ed, the position and
`orientation of an object With respect to the user at the time the
`data Was captured can be determined based on the appearance
`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 speci?c 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 data to another computer (“Server”), Wherein the
`data is analyZed and the object or data of interest is detected
`and recogniZed. Then the netWork address of information
`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
`needs to be stored in the systems database.
`Some or all of the data processing, including image/ obj ect
`detection and/or decoding of symbols detected in the data,
`may be distributed arbitrarily betWeen the mobile (Client)
`device and the Server. In other Words, some processing may
`be performed in the Client device and some in the Server.
`Additionally the processing may be performed Without speci
`?cation of Which particular processing is performed in each.
`HoWever all processing may be performed on one platform or
`the other, or the platforms may be combined so that there is
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 7 of 13 Page ID #:471
`
`

`

`US 7,881,529 B2
`
`3
`only one platform. The data processing can be implemented
`in a parallel computing manner, thus facilitating scaling of the
`system With respect to database size and input tra?ic loading.
`Therefore, it is an object of the present invention to provide
`a system and process for identifying digitally captured
`images Without requiring modi?cation to the object.
`Another object is to use digital capture devices in Ways
`never contemplated by their manufacturer.
`Another object is to alloW identi?cation of objects from
`partial vieWs of the object.
`Another object is to provide communication means With
`operative devices Without requiring a public connection
`thereWith.
`Another object is to alloW the telephony device to transmit
`information and data derived from the captured data to the
`server.
`Still another object of the invention is to provide a tele
`phony device that may transmit motion imagery to the server.
`Another object is to provide a communication means
`Wherein the telephony device may transmit information/data
`derived from the data to the server, as opposed to transmitting
`the data itself.
`Yet another object of the present invention is to alloW the
`telephony device to transmit either motion imagery and/or
`still images to the server.
`Another object of the present invention is to alloW the
`server to send an item of information to another distal device.
`Yet another object of the present invention is to alloW the
`system to perform data processing, data contrast enhance
`ment, noise removal and de-blurring thereof.
`Yet another object of the present invention is to alloW the
`system to perform data processing prior to the recognition
`and/ or search process.
`Still another object of the present invention is to alloW the
`system to perform data processing even if the data recognition
`and/or search process fails.
`Another object of the present invention is to alloW the
`system to perform data processing after a prior data recogni
`tion and/or search process fails.
`These and other objects and advantages of the present
`invention Will become apparent to those skilled in the art after
`considering the folloWing detailed speci?cation, together
`With the accompanying draWings Wherein:
`
`20
`
`25
`
`30
`
`35
`
`40
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`45
`
`FIG. 1 is a schematic block diagram top-level algorithm
`?owchart;
`FIG. 2 is an idealized vieW of data capture;
`FIGS. 3A and 3B are a schematic block diagram of process
`details of the present invention.
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 8 of 13 Page ID #:472
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`The present invention includes a novel process Whereby
`information such as Internet content is presented to a users
`based solely on a remotely acquired data of a physical object.
`Although coded information can be included in the remotely
`acquired image, it is not required since no additional infor
`mation 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 a?ixed to the object. Image-linked objects
`can be located and identi?ed Within user-acquired imagery
`solely by means of digital data processing, With the address of
`pertinent information being returned to the device used to
`
`50
`
`55
`
`60
`
`65
`
`4
`acquire the data and perform the link. This process is robust
`against digital data noise and corruption (as can result from
`lossy data compression/ decompression), perspective error,
`rotation, translation, scale differences, illumination varia
`tions caused by different lighting sources, and partial obscu
`ration of the target that results from shadoWing, re?ection or
`blockage.
`Many different variations on machine vision “target loca
`tion and identi?cation” 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 data matching engine that returns unambiguous
`matches to target objects contained in a Wide variety of poten
`tial input images. This unique approach to data matching
`takes advantage of the fact that at least some portion of the
`target object Will be found in the user-acquired image. Addi
`tionally, another unique approach is to alloW for data process
`ing by either the capturing device or the server prior to iden
`ti?cation and transmission. The parallel data comparison
`processes embodied in the present search technique are, When
`taken together, unique to the process. Further, additional
`re?nement of the process, With the inclusion of more and/or
`different decomposition-parameterization functions, utilized
`Within the overall structure of the search loops is not
`restricted. The detailed process is described in the folloWing
`FIG. 1 shoWing the overall processing How and steps. These
`steps are described in further detail in the folloWing sections.
`For data capture 10, the User 12 (FIG. 2) utilizes a com
`puter, mobile telephone, personal digital assistant, or other
`similar device 14 equipped With a data sensor (such as a CCD
`or CMOS digital camera). The User 12 aligns the sensor of the
`data capture device 14 With the object 16 of interest. The
`linking process is then initiated by suitable means including:
`the User 12 pressing a button on the device 14 or sensor; by
`the softWare in the device 14 automatically recognizing that a
`data is to be acquired; by User voice command; or by any
`other appropriate means. The device 14 captures a digital data
`18 of the scene at Which it is pointed. This data 18 is repre
`sented as three separate 2-D matrices of pixels, corresponding
`to the raW RGB (Red, Green, Blue) representation of the input
`image. For the purposes of standardizing the analytical pro
`cesses in this embodiment, if the device 14 supplies a data in
`other than RGB format, a transformation to RGB is accom
`plished. These analyses could be carried out in any standard
`color format, should the need arise.
`If the Data/ Server 20 is physically separate from the device
`14, then user acquired images are transmitted from the device
`14 to the Data/ Server 20 using a conventional digital netWork
`or Wireless netWork means. HoWever, prior to transmitting the
`data to the data/ server 20, the device 14 used to capture the
`data may ?rst conduct data processing, such as contrast
`enhancement, noise removal, de-blurring and the like. This
`procedure of data processing may be done prior to transmis
`sion of the data to the data/ server 20, or after search results
`have been returned to the device 14.
`If the data 18 has been compressed (eg via lossy JPEG
`DCT) in a manner that introduces compression artifacts into
`the reconstructed data 18, these artifacts may be partially
`removed by, for example, applying a conventional despeckle
`?lter to the reconstructed data prior to additional processing.
`Additionally, the device 14 may transmit motion imagery,
`such as, for example, video transmissions. The motion imag
`ery may be transferred to the server instead of; or in conjunc
`tion With one or more still images.
`The Data Type Determination 26 is accomplished With a
`discriminator algorithm Which operates on the input data 18
`and determines Whether the input data contains recognizable
`
`

`

`US 7,881,529 B2
`
`5
`symbols, such as barcodes, matrix codes, or alphanumeric
`characters. If such symbols are found, the data 18 is sent to the
`Decode Symbol 28 process. Depending on the con?dence
`level With Which the discriminator algorithm ?nds the sym
`bols, the data 18 also may or alternatively contain an object of
`interest and may therefore also or alternatively be sent to the
`Object Data branch of the process How. For example, if an
`input data 18 contains both a barcode and an object, depend
`ing on the clarity With Which the barcode is detected, the data
`may be analyzed by both the Object Data and Symbolic Data
`branches, and that branch Which has the highest success in
`identi?cation Will be used to identify and link from the object.
`The data may be 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 con
`tent information 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 Data Decomposition 34, of a
`high-resolution input data into several different types of
`quanti?able salient parameters. This alloWs for multiple inde
`pendent convergent search processes of the database to occur
`in parallel, Which greatly improves data match speed and
`match robustness in the Database Matching 36. As illustrated
`above, a portion of the decomposition may be divided arbi
`trarily betWeen the device 14 and the server 20. The Best
`Match 38 from either the Decode Symbol 28, or the data
`Database Matching 36, or both, is then determined. If a spe
`ci?c 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. Additionally, dur
`ing processing, the server may send an item of information to
`another distal device (not shoWn). For example, if an data of
`a TV listing in a magazine is transmitted to the server 20, the
`server may recognize the data as a TV listing Wherein the
`server 20 may send a command to a Intemet-connected tele
`vision to change to the channel in the listing.
`The overall How of the Input Data Decomposition process
`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
`FOR END
`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 de?ned by their boundaries, Which consist of
`
`Case 2:20-cv-07872-GW-PVC Document 40-1 Filed 11/11/20 Page 9 of 13 Page ID #:473
`
`6
`sets of (x, y) point pairs. A map of segment boundaries is
`produced, Which is maintained separately from the KGB
`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 represent all 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 ?rst 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. Each 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)
`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
`modi?ed 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 comers of the bounding box are
`mapped into the comers 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 Norrnaliza
`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:
`
`then round to nearest integer value. Truncate at 0 and 255,
`if necessary. The resulting matrix L is a standard grayscale
`image. This grayscale representation is at the same spatial
`resolution as the full color image, With an 8-bit dynamic
`range. A multi-resolution Wavelet Decomposition of the
`grayscale image is performed, yielding Wavelet coef?cients
`for several scale factors. The Wavelet coel?cients at various
`scales are ranked according to their Weight Within the image.
`For Color Cube Decomposition, an image segmentation is
`performed (see “Segmentation” above), on the RGB image
`that results from Geometric Normalization. Then the RGB
`image is transformed to a normalized Intensity, In-phase and
`Quadrature-phase color image (Y IQ). The segment map is
`used to identify the principal color regions of the image, since
`each segment boundary encloses pixels of similar color. The
`average Y, I, and Q values of each segment, and their indi
`vidual component standard deviations, are computed. The
`folloWing set of parameters result, representing the colors,
`color variation, and size for each segment:
`Y.sub.avg:Average Intensity
`I.sub.avg:Average In-phase
`Q. sub.avg:Average Quadrature
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 7,881,529 B2
`
`7
`Y.sub.sigma:Intensity standard deviation
`I.sub.sigma:In-phase standard deviation
`Q.sub.sigma:Quadrature standard deviation
`N.sub.pixels:number of pixels in the segment
`The parameters comprise a representation of the color
`intensity and variation in each segment. When taken together
`for all segments in a segment group, these parameters com
`prise points (or more accurately, regions, if the standard
`deviations are taken into account) in a three-dimensional
`color space and describe the intensity and variation of color in
`the segment group.
`For Shape Decomposition, the map resulting from the seg
`mentation performed in the Color Cube Generation step is
`used and the segment group is evaluated to extract the group
`outer edge boundary, the total area enclosed by the boundary,
`and its area centroid. Additionally, the net ellipticity (semi
`major axis divided by semi-minor axis of the closest ?t ellipse
`to the group) is determined.
`For LoW-Resolution Grayscale Image Generation, the full
`resolution grayscale representation of the image that Was
`derived in the Wavelet Generation step is noW subsampled by
`a factor in both x and y directions. For the example of this
`embodiment, a 3:1 subsampling is assumed. The subsampled
`image is produced by Weighted averaging of pixels Within
`each 3 .times.3 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:
`
`20
`
`25
`
`30
`
`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 Gray
`scale Comparison Wavelet Comparison Color Cube Com
`parison Calculate Combined Match Score END FOR END
`40
`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 sorted in
`the “Segment Group Generation” step. Each segment group,
`as it is considered, is a candidate for the object of interest in
`the image, and it is compared against database objects using
`various tests.
`One favored implementation, of many possible, for the
`order in Which the segment groups are considered Within this
`loop is the “center-out” approach mentioned previously in the
`“Segment Group Generation” section. This scheme considers
`segment groups in a sequence that represents the addition of
`adjacent segments to the group, starting at the center of the
`image. In this scheme, each neW group that is considered
`comprises the previous group plus one additional adjacent
`image segment. The neW group is compared against the data
`base. If the neW group results in a higher database matching
`score than the previous group, then neW group is retained. If
`the neW group has a loWer matching score then the previous
`group, then it is discarded and the loop starts again. If a
`particular segment group results in a match score Which is
`extremely high, then this is considered to be an exact match
`and no further searching is Warranted; in this case the current
`group and matching database group are selected as the match
`and this loop is exited.
`
`8
`FOR Each Database Object
`This loop considers each object in the database for com
`parison against the current input segment group.
`FOR Each VieW Of This Object
`This loop considers each vieW of the current database
`object for comparison against the current input segment
`group. The database contains, for each object, multiple vieWs
`from different vieWing angles.
`FOR Each Segment Group In This VieW Of This Database
`Object
`This loop considers each combination of segment groups
`in the current vieW of the database object. These segment
`groups Were created in the same manner as the input image
`segment groups.
`Shape Comparison
`Inputs
`For the input image and all database images:
`I. Segment group outline
`I. Segment group area
`III. Segment group centroid location
`IV. Segment group bounding ellipse ellipticity
`Algorithm
`V. Identify those database segment groups With an area
`approximately equal to that of the input segment group,
`Within TBD limits, and calculate an area matching score for
`each of these “matches.”
`VI. Within the set of matches identi?ed in the previous
`step, identify those database segment groups With an elliptic
`ity approximately equal to that of the input segment group,
`Within TBD limits, and calculate an ellipticity position
`matching score for each of these “matches.”
`VII. Within the set of matches identi?ed in the previous
`step, identify those database segment groups With a centroid
`position approximately equal to that of the input segment
`group, Within TBD limits, and calculate a centroid position
`matching score for each of these “matches.”
`VIII. Within the set of matches identi?ed in the previous
`step, identify those database segment groups With an outline
`shape approximately equal to that of the input segment group,
`Within TBD limits, and calculate an outline matching score
`for each of these “matches.” This is done by comparing the
`tWo outlines and analytically determining the extent to Which
`they match.
`Note: this algorithm need not necessarily be performed in
`the order of Steps 1 to 4. It could alternatively proceed as
`folloWs:
`
`2 FOR each database segment group IF the group passes Step
`1 IF the group passes Step 2 IF the group passes Step 3 IF the
`group passes Step 4 Successful comparison, save result END
`IF END IF END IF END IF END FOR
`Grayscale Comparison
`Inputs
`For the input image and all database images:
`IX. LoW-resolution, normalized, contrast-binned, gray
`scale image of pixels Within segment group bounding box,
`With pixels outside of the segment group set to a standard
`background color.
`Algorithm
`Given a series of concentric rectangular “tiers” of pixels
`With