EXHIBIT 1059
`
`U.S. PATENT NO. 5,773,810 TO HUSSEY et al.
`
`(“the ‘810 Patent)
`
`TRW Automotive U.S. LLC: EXHIBIT 1059
`PETITION FOR INTER PARTES REVIEW
`OF U.S. PATENT NUMBER 8,599,001
`IPR2015-00436
`
`

`
`Ulllted States Patent [19]
`Hussey et al.
`
`US005773810A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,773,810
`Jun. 30, 1998
`
`[54] METHOD FOR GENERATING REAL TIME
`
`4,877,949 10/1989 Daneilson et al. .................... .. 235/462
`
`DEGREE ()E FOCUS SIGNAL FOR
`
`4,920,255
`
`4/1990 Gabeler . . . . . . . . . . . . .
`
`. . . . . .. 235/472
`
`HANDHELD IMAGING DEVICE
`
`[75] Inventors: Robert M. Hussey, Liverpool; Andrew
`llsloélgacres Jr» Skaneateles> both of
`
`'
`'
`[73] Asslgnee: geYlch Allyn’ Inc" Skaneateles Falls’
`'
`'
`
`[21] Appl' N05 625,111
`[22] Filed:
`Man 29, 1996
`
`[51] Int. Cl.6 ..................................................... .. G06K 7/10
`[52] US. Cl. .............. ..
`235/472; 250/201.7; 235/462
`58
`Field of Search ................................... .. 235/462 472
`[
`l
`,
`,
`235/454; 250/2017
`
`[56]
`
`References Cited
`
`U'S' PATENT DOCUMENTS
`3/1986 Williams ............................... .. 235/472
`4/1989 Drucker ..
`..
`5/1989 Drucker ................................ .. 235/462
`
`4,578,571
`4,818,886
`4,831,275
`
`250/201.7
`3/1991 Sarfati et a1. .
`5,003,165
`5/1995 Longacre, Jr. et a1. .............. .. 235/462
`5,420,409
`Primary Examiner_p_ L_ Evans
`Attorney, Agent, or Firm—Wall Marj ama & Bilinski
`
`[57]
`ABSTRACT
`A method for generating, substantially in real time, a user
`perceptible indication of the degree to Which the distance
`betWeen a handheld imaging device and a target object
`approximates the in-focus distance therebetWeen. A stored
`image of the target object is sampled, in accordance With a
`pattern of sampling addresses, to determine the magnitude
`of the slopes of the transitions of the stored image, The
`stored image is also sampled to determine the contrast value
`Of the Stored ima e. The hi hest Ina nitude slo e values and
`g
`g
`g
`p
`the image contrast value are combined to produce a focus
`metric signal that is indicative of the degree to Which the
`imaging device approximates an in-focus condition. The
`focus metric signal is then used to generate a user percep
`tible signal that can be utilized by an operator to move the
`imaging device toward its in-focus distance.
`
`50 Claims, 5 Drawing Sheets
`
`<— ——>
`D
`
`rl6
`
`|MAGE
`OPTICS —-> SENSOR
`
`36
`/
`
`l4
`/
`
`—P
`
`NO
`
`/
`
`S
`
`| I
`LED <—&—
`\ 12
`
`l3
`
`IO
`/
`
`r34
`-—-—————> BEEP
`
`PROGRAMMABLE
`GATE
`ARRAY
`
`<—> V0
`
`K32
`
`MICRO
`PROCESSOR
`
`\
`20
`
`K
`3o
`
`DRAM
`
`ROM
`
`J
`22
`
`\24
`
`1059-001
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 1 0f5
`
`5,773,810
`
` ON
`
`om
`
`m._m<s__2<moomn_
`
`m._.<G
`
`><mm<
`
`nomo_s_
`
`mowmmooma
`
`mm
`
`Q\<mowzmm
`
`mo<s__
`
`m._To
`
`1059-O02
`
`1059-002
`
`
`
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 2 of5
`
`5,773,810
`
`INITIALIZE IMAGER / IOO
`USING DEFAULT EXP.
`TIME AND/OR GAIN
`
`TAKE AND STORE
`CENTER ED IMAGE
`
`ScAN REGION OF INTEREST;
`coNsTRucT RISTOGRAM; /‘| l5
`SToRE IN LARGEST DIFFS.
`WMAX AND WMIN
`
`UPDATE
`ExPoSuRE P '42
`TIME
`T
`
`EXECUTE
`EXPOSURE TIME [I40
`CORRECTION ROUTINE
`
`
`
`DETERMINE lN-FOCUS
`
`/\
`
`METRIC VALUE FM
`
`OUTPUT SIGNAL
`
`
`
`INDICATING DEGREE OF FOCUS
`
`/‘
`
`DETERMINE WHITE
`LEVEL WL AND
`WL — WT
`
`IS
`FM > FMIN
`?
`
`DECODE
`|5O
`v IMAGE
`
`DECODE
`
`SUCCESSFUL?
`
`1059-003
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 3 of5
`
`5,773,810
`
`200
`
`SET
`KcoRR = ‘25
`
`N
`205
`
`YES
`
`220
`f
`
`f 225
`SET
`WT
`KCOHR = w|_+1
`
`/
`
`KcoRR = 4-0
`
`SET
`
`KcoRR = ( KCORR — 1'0) KDAMP + 1-0
`
`SET EXPOSURE TIME = f 2K)
`
`PRIOR EXPOSURE TIME x KCORR
`
`FIG. 3
`
`1059-004
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 4 of5
`
`5,773,810
`
`FIG. 40 ‘AV
`
`T(O,l)
`
`X0 X1
`
`\
`X2 X3 X4 X5
`
`X6 X7
`
`FIG. 4b XI
`
`T(O,l)
`
`YO‘
`
`_
`
`112,3)
`
`IG. 4
`
`\
`
`CB
`
`X0 X1
`
`X2 X3 X4 X5 X6 X7
`
`FIG. 4c Xv
`
`no,”
`
`CC //
`
`N252 %
`
`’ T(4.5)
`
`YO I
`
`1059-005
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 5 of5
`
`5,773,810
`
`FIG. 50
`
`A“
`
`\\\\\\\\
`C2 C3 C4 C5 C6 C7 C8 C9
`
`Cl
`
`FIG. 5b
`MSI—\'
`\DIFF. llDIFF. 2 IDIFF. 3 IDIFF. 4IDIFF. 5IDIFF. GIDIFF. YIDIFF. sj
`
`FIG. 56 MS2-——->
`
`FIG. 5
`
`N.OCCUR.
`
`WMIN
`
`.
`o
`
`:
`s
`
`:
`240
`
`:
`245
`
`‘
`
`|
`:
`250
`
`WMAX.
`W>
`255
`
`1059-006
`
`

`
`1
`METHOD FOR GENERATING REAL TIME
`DEGREE OF FOCUS SIGNAL FOR
`HANDHELD IMAGING DEVICE
`
`5,773,810
`
`2
`adjust the focal length of an adjustable lens assembly.
`Focusing systems of this type may be classi?ed on the basis
`of differences betWeen the devices that are used to measure
`distance and/or the devices that are used to adjust the focal
`length of the lens assembly.
`An example of a focusing system that uses an ultrasonic
`transducer to measure distance is described in US. Pat. No.
`4,920,255 (Gabeler). An example of a focusing system that
`uses the position of a spotter beam to measure distance is
`described in US. Pat. No. 5,378,883 (Batterman, et al). An
`example of a focusing system that uses a lens assembly
`having a mechanically adjustable focal length includes US.
`Pat. No. 4,877,949 (Danielson, et al).
`Another approach to achieving an acceptable degree of
`focus is to use a reader having a ?xed focal length and to
`take advantage of the ability of the operator to recogniZe a
`distance Which is equal to that focal length. Since, in most
`cases, readers are not equipped With displays that provide
`their operators With images of the ?eld of vieW thereof, the
`ability of an operator to recogniZe the proper distance must
`be learned from experience. In readers that are not equipped
`With such displays, the gaining of this experience may be
`accelerated by providing the operator With an audible feed
`back signal Which indicates When the target symbol is at a
`distance that is close enough to its ?xed focal length that the
`target symbol may be successfully read and decoded. In such
`readers the feedback signal is produced by a beeper Which
`beeps When a symbol has been successfully decoded.
`Prior to the present invention, readers of the above
`mentioned feedback type have had a number of de?ciencies
`Which limit their usefulness. One of these is that the feed
`back signal is not instantaneous. With 2D bar code symbols,
`for example, the decode time may be on the order of 400 ms
`or more, a time Which is suf?ciently long that the user/
`operator may have dif?culty correlating the focal length of
`the reader With the distance Which resulted in a successful
`decode.
`Another of these de?ciencies is that readers With a ?xed
`focal length have a depth of ?eld Which is designed to be as
`large as possible. As a result, so long as symbols are
`successfully decoded, the user is not provided With any
`guidance as to Whether the reader-to-target distance Was
`optimal or barely suf?cient. This, in turn, can prolong the
`time required for the user to learn exactly Which reader-to
`target distance corresponds to the optimal in-focus condition
`of the reader.
`While the effect of these de?ciencies can be reduced by
`incorporating distance measuring devices, such as ultrasonic
`transducers, proximity detecting circuits, etc., the incorpo
`ration of these devices and/or circuits can substantially
`increase the cost of the reader, as Well as reducing its
`mechanical reliability. In addition, the small amount of
`space available Within hand held imaging devices may make
`the incorporation of such devices or circuits more dif?cult.
`In vieW of the foregoing, it Will be seen that, prior to the
`present invention, there has existed a need for a method for
`generating a user perceptible degree of focus feedback
`signal Which is not subject to the foregoing de?ciencies. It
`Will also be seen that there has existed a need for an
`improved method for automatic exposure control Which is
`not subject to the foregoing de?ciencies.
`
`BACKGROUND OF THE INVENTION
`The present invention relates to handheld imaging
`devices, including but not limited to bar code readers, and is
`directed more particularly to a method for generating, sub
`stantially in real time, a user perceptible feedback signal for
`facilitating the manual positioning of the imaging device at
`a distance that corresponds to the focal length thereof.
`Handheld imaging devices such as bar code readers,
`optical character readers, digital cameras, and the like have
`come into Widespread use in large numbers of retail, indus
`trial and medical applications. Such imaging devices are
`used to perform routine data entry functions, such as pricing,
`inventory updating, etc., With an accuracy and reliability that
`far exceeds the accuracy and reliability of manual data entry.
`These and other advantages, such as high data throughput
`rates and direct compatibility With data processing devices
`and systems, assures that imaging devices Will be used to
`read ever increasing quantities and densities of optically
`encoded data.
`In accommodating the need for these increasing quantities
`and densities of data, tWo-dimensional (2D) matrix
`symbologies, such as MaxiCode, and stacked symbologies,
`such as PDF417 and Code 49, have been developed to take
`advantage of the higher information per unit area and
`poWerful error correcting capabilities thereof. 2D solid state
`image sensors, such as CCD image sensors, are able to
`receive and convert into electrical signals images Which
`optically encode data in tWo mutually perpendicular direc
`tions. Provided that these image sensors are provided With
`optical imaging systems that provide properly exposed and
`sharply focused images of their target objects or symbols,
`and With signal processors that include suitable decoding
`softWare, these image sensors are able to read data from
`various types and in many shapes and siZes of bar code and
`other symbols.
`When one or both of the exposure time and focus of an
`image sensor do not have their optimum values, the asso
`ciated reader Will fail to realiZe its full potential. In the case
`of exposure time, this failure manifests itself as images
`Which are too bright (overexposed) or too dark
`(underexposed) to provide the signal contrast necessary for
`a high signal-to-noise ratio. In the case of focus, this failure
`manifests itself as images Which lack the high resolution or
`sharpness necessary for the device to distinguish betWeen
`densely packed image data elements.
`Prior to the present invention, many different attempts
`have been made to solve the above-mentioned problems. In
`the case of exposure time, these attempts have usually
`involved the inclusion of an automatic exposure control
`circuit or program Which measures the light intensity at the
`target symbol and adjusts the exposure time of the image
`sensor as necessary to achieve a predetermined target value
`for the peak-to-peak output voltage thereof. An example of
`a hardWare approach to automatic exposure control is
`described in US. Pat. No. 4,538,060 (Sakai et al). An
`example of a softWare approach to automatic exposure
`control is described in copending, commonly assigned US.
`patent application Ser. No. 08/574,386, ?led Dec. 18, 1995.
`In the case of focus, the methods used to achieve an
`acceptable degree of focus prior to the present invention
`have involved the measurement of the distance betWeen the
`reader and its target, and the use of this measurement to
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`SUMMARY OF THE INVENTION
`
`65
`
`In accordance With one feature of the present invention
`there is provided an improved method for generating a user
`perceptible degree of focus signal Which is not subject to the
`
`1059-007
`
`

`
`5,773,810
`
`3
`de?ciencies of previously known methods for generating
`such signals. More particularly, the present invention pro
`vides a method for generating a degree of focus signal Which
`gives a substantially instantaneous indication of the degree
`to Which the position of an optical reader or digital camera
`corresponds to the position at Which the reader or camera is
`at its optimal focal distance.
`Generally speaking, the method of the invention com
`prises the steps of taking and storing an image of a target
`object, symbol or character, sampling the stored image to
`derive therefrom a degree of focus signal having a magni
`tude that varies in accordance With the slopes of a prede
`termined number of the sharpest transitions of the stored
`image, comparing the magnitude of the degree of focus
`signal to a reference focus signal indicative of the degree of
`focus value that corresponds to the optimum in-focus dis
`tance of the reader, and generating, substantially
`instantaneously, a user perceptible signal that the user may
`use in establishing that in-focus distance. Because of the
`speed With Which the feedback signal is generated, a user is
`able to make an apparently continuous guided adjustment of
`the distance betWeen the reader and its target and to thereby
`rapidly converge on the distance that corresponds to an
`in-focus condition. This not only greatly decreases the time
`necessary to establish the in-focus condition, it also greatly
`decreases the time necessary for the operator to learn Where
`to initially position the reader. This decrease in learning time
`is particularly important With optical readers that have a
`short depth of ?eld.
`One important advantage of the method of the invention
`is that it may be practiced Without increasing the number of
`optical or electrical elements that are included in the reader
`With Which it is used. This is because all of the circuit
`components necessary for the use of the method of the
`invention are already present. Stated differently, the method
`of the invention is implemented by changing the Way that
`already present optical and electrical elements cooperate and
`interact, and not by changing their numbers or types. As Will
`be explained more fully later, this is accomplished by
`changing the instructions included in the stored program of
`the reader. Thus, the present invention may be practiced
`Without increasing either the cost or the amount of space
`occupied by the reader.
`In generating the desired degree of focus signal, the
`method of the invention contemplates a sampling step in
`Which proximately located pairs of image data elements are
`selected in accordance With a sampling pattern or grid that
`encompasses enough of the stored image data to assure that,
`Without regard to the orientation betWeen the reader and the
`target object, the sampling step produces a set of signal
`values that provide a representative indication of the sharp
`ness of the transitions of the target object as a Whole. Since
`the transitions of a printed target object may be assumed to
`be sharp, any lack of sharpness in the transitions of the
`stored image data representing the same may be assumed to
`be the result of an out of focus condition in the imaging
`process. As a result, the sampled sharpness values may be
`used as a direct measure of the degree of focus of the reader.
`In accordance With another feature of the invention, the
`generation of the degree of focus signal includes the step of
`correcting or normaliZing the sampled image data for the
`effect of image contrast. In particular, the sampling step of
`the invention includes the sampling of the image data to
`determine the gray scale Whiteness values of the brightest
`and darkest image data elements sampled. These extreme
`Whiteness values are then used, as an indication of overall
`image contrast, to correct or normaliZe the above-mentioned
`
`15
`
`25
`
`35
`
`40
`
`45
`
`55
`
`65
`
`4
`sharpness values for the effect of image contrast. This, in
`turn, alloWs the method of the invention to be used With
`target objects having a Wide range of contrast values.
`Advantageously, it has been found that, in the course of
`sampling the image data, the inclusion of a feW additional
`instructions alloWs a Whiteness distribution plot, such as a
`histogram, to be constructed for the parts of the image data
`Which coincide With the sampling grid. The availability of
`this histogram, in turn, makes possible the generation of a
`Whiteness signal that may be used as a direct measure of the
`light level at the target object. In accordance With an
`important feature of the present invention, the availability of
`this Whiteness signal, in conjunction With the degree of focus
`signal, alloWs the focus and the exposure time of the reader
`to be adjusted substantially concurrently, as complementary
`parts of a single sampling and adjustment process. As in the
`case of the focusing feature of the invention, the exposure
`control feature of the invention is provided, not by including
`additional optical and electrical elements, but rather by
`making different and more effective use of already present
`optical and electrical elements.
`Generally speaking, the exposure time control method of
`the invention includes the steps of determining, from the
`above-mentioned Whiteness distribution, a Whiteness signal
`value that is representative of the illumination level of the
`target as a Whole and determining, from this measured
`Whiteness value and a reference Whiteness value, Whether
`the difference therebetWeen exceeds predetermined accept
`able limits. If the difference is Within acceptable limits, no
`exposure time adjustment is made; if the difference is not
`Within acceptable limits, the exposure time is adjusted in
`accordance With an adjustment process that is designed to
`result in an acceptable Whiteness level Within a relatively
`short time.
`
`DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of an optical reader suitable for
`use in practicing the method of the invention;
`FIGS. 2 and 3 are flow charts Which illustrate the opera
`tion of the method of the invention;
`FIGS. 4A through 4C illustrate image data patterns of the
`type sampled by the method of the invention; and
`FIGS. 5A through 5C and 6 illustrate an exemplary
`sampling pattern and exemplary data structures that may be
`used in practicing the invention.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`Referring to FIG. 1 there is shoWn a block diagram of one
`type of optical reader 10 that is suitable for use in practicing
`the method of the invention. This reader includes an illu
`mination assembly 12 for illuminating a target object, such
`as a 2D bar code symbol S, and an imaging assembly 14 for
`receiving an image of the object, via an optical imaging
`assembly 16, and generating an electrical output signal
`indicative of the printed symbol and the data optically
`encoded therein. Illumination assembly 12 may, for
`example, comprise one or more LED’s together With one or
`more re?ectors for directing light in the direction of object
`S. Illumination assembly 12 may be eliminated if ambient
`light levels are high enough to alloW high quality images to
`be taken. Imaging assembly 14 may comprise a 2D image
`sensor of any of a variety of types, such as a CCD or CMOS
`image sensor, and may in particular comprise a VVL-1060B
`image sensor of the type manufactured by VLSI Vision, Ltd.
`
`1059-008
`
`

`
`5,773,810
`
`5
`Optical reader 10 of FIG. 1 also preferably includes a
`microprocessor 20, a dynamic random access data memory
`(DRAM 22), a ROM 24, and a bus 26 for communicating
`data, address and control signals therebetWeen. Optical
`reader 10 also preferably includes a programmable gate
`array or application speci?c integrated circuit (ASIC) con
`taining specialiZed circuitry, such as frame DMA circuitry,
`for controlling the addressing and storage of image data in
`DRAM 22 so that microprocessor 20 can devote most of its
`time to tasks such as analyZing and decoding data stored in
`DRAM 22. Reader 10 also includes an I/O channel 32
`through Which it may communicate With external circuitry,
`such as a host processor (not shoWn), and a “beeper” or
`similar signaling device 34 for generating user perceptible
`signals for use by a human operator. In the preferred
`embodiment, all of the circuitry shoWn in FIG. 1 Will be
`enclosed in a suitable housing (not shoWn) Which is adapted
`to be held in a human hand.
`In operation, ASIC 30 controls the operation of illumi
`nating assembly 12 and imaging assembly 14, via control
`lines 11 and 13, under the overall control of microprocessor
`20 Which, in turn, operates under the control of a program
`stored in ROM 24. ASIC 30 also controls the operation of an
`A/D converter circuit 36 Which converts the analog output
`signal of imaging assembly 14 into a digital form suitable for
`storage in DRAM 22. With the previously mentioned VVL
`1060B image sensor, and an 8 bit A/D converter, the result
`Will be a series of 8 bit Words, or image data elements, each
`of Which represents the 8 bit gray scale value for a respective
`pixel of image sensor 14. Thus, each 8 bit Word output by
`A/D converter 36 speci?es the Whiteness or light intensity
`value of one pixel of sensor 14 by specifying Which of 256
`possible Whiteness values is associated thereWith.
`The 8 bit image data Words received from AID converter
`36 are stored in data memory 22 in accordance With a
`storage scheme Which assures that there is a one-to-one
`correspondence betWeen a pixel of the image sensor and an
`address in data memory 22. In other Words, the image data
`stored in data memory 22 takes the form of a memory
`mapped representation of the object of interest, each image
`data element comprising a gray scale value that represents
`the Whiteness value thereof. With the above-mentioned
`image sensor, there Will be a total of 768x574 of such image
`data elements for each imaged frame of the object of
`interest. This assures that the reader has a suf?ciently high
`resolution to read bar code symbols and other indicia or
`characters of any of a variety of knoWn siZes and types,
`provided that the distance D betWeen the reader and its target
`is such that the image formed on sensor 14 is approximately
`in focus, and provided that the exposure time of the image
`sensor 14 is not too long or too short to assure good signal
`contrast.
`In accordance With the present invention, there is pro
`vided a method of using an optical reader of the type shoWn
`in FIG. 1 that assures that acceptable degrees of focus and
`signal contrast are achieved and, moreover, are achieved
`Without increasing the cost, complexity or siZe of the reader.
`In the preferred embodiment, this is accomplished by select
`ing a set of representative image data addresses and deter
`mining from the image data stored at those addresses,
`substantially in real time, signal values or metrics indicative
`of the degree of focus and the degree of Whiteness of the
`image on image sensor 14. The degree of focus signal is then
`used to generate a user perceptible but non-obtrusive feed
`back signal, such as an audible tick, for use in helping a user
`in establishing the reader-object distance that is associated
`With an in-focus condition, and the degree of Whiteness
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6
`signal is used to adjust the exposure time of the image sensor
`as necessary to produce an acceptable Whiteness value.
`Taken together, these steps assure the rapid availability of
`stored image data Which has both an acceptable degree of
`focus and an acceptable signal contrast, and Which can
`therefore be decoded more easily and rapidly than Would
`otherWise be the case.
`To the end that the above-summariZed method may be
`practiced, the stored program of the reader of FIG. 1
`includes instructions of the type shoWn in the How charts of
`FIGS. 2 and 3. As Will be explained more fully presently, the
`embodiment of FIGS. 2 and 3 is arranged so that the
`focusing and exposure adjusting phases of the method of the
`invention proceed concurrently and cooperatively, and so
`that no attempt is made to decode stored image data until
`acceptable results are achieved for both of these phases or,
`optionally, until a predetermined time has elapsed. In
`addition, the relationship betWeen and sequence of the steps
`of the method is arranged so that a neW set of image data is
`taken and is stored as soon as possible after it has been
`determined that an acceptable illumination level or an
`acceptable focus has not been achieved. Together, these
`features assure that the beginning of the decoding process is
`not delayed any more than is actually necessary to simul
`taneously satisfy the focus and illumination requirements of
`the reader.
`Referring ?rst to FIG. 2, the method of the invention
`begins With the step of initialiZing the reader, as called for
`by block 100. This block causes the initial exposure time
`and/or gain of image sensor 14 to be set to their default
`values, thereby alloWing the reading process to begin. When
`this has been accomplished, the reader is instructed to take
`and store an image of the object of interest Which is centered
`in the ?eld of vieW thereof, as called for by block 110. The
`centering of the object of interest in the ?eld of vieW is the
`responsibility of the user/operator, although the latter may
`?nd the feedback signal of the invention helpful in accom
`plishing this centering. Since the operations called for by
`blocks 100 and 110 are of a type knoWn to those skilled in
`the art, they Will not be described in detail herein.
`The next steps of the method of the invention are those
`called for by block 115. These include, ?rstly, the
`establishment, for the selected region of interest, of a
`sampling grid or pattern that de?nes a set of addresses Which
`alloW that region to be sampled in systematic Way, Without
`addressing each image data element Within the boundaries of
`that region. An exemplary one of such sampling patterns is
`shoWn in FIG. 5A as an array or grid 116 made up of seven
`roWs R1, R2, etc. and 9 columns C1, C2, etc. Which are
`mutually orthogonal to one another in address space.
`Because the orientation of the stored image With respect to
`this address space is at this time unknoWn, it is assumed not
`to bear any simple relationship to the orientation of grid 116.
`Because of the mutual orthogonality of the roWs and
`columns, hoWever, it may be assumed that any image
`features, such as black-White transitions, that are not easily
`readable With respect to the roWs, Will be easily readable
`With respect to the columns.
`In the embodiment of FIG. 5A the roWs and columns
`divide the interior of grid 116 into a plurality of square
`“blocks”, each of Which includes 48 sampling addresses.
`While these sampling addresses are knoWn to have a one to
`one correspondence With the pixels of image sensor 14, they
`have no knoWn relationship With respect to the transitions of
`the image of the object of interest. In other Words, a set of
`samples that includes only data elements Which have
`addresses that lie on grid 116 Will provide a representative
`
`1059-009
`
`

`
`10
`
`15
`
`35
`
`25
`
`7
`indication of the parameters of the image data even though
`most image data elements are not sampled.
`This should not be understood, hoWever, to mean that it
`is necessary to take a sample at each of the addresses that lie
`on the sampling grid. This is because the use of a less than
`a 100% sampling rate, e.g., the sampling of the data at every
`second, third or Nth available sampling address on the
`sampling grid, is highly likely to provide data Which is as
`useful for purposes of the invention as the use of a 100%
`sampling rate. It Will therefore be understood that the present
`invention is not restricted to the use of any speci?c sampling
`rate or density, or to the use of the same sampling rate for
`both focus and illumination level determinations. It Will also
`be understood that the present invention is not restricted to
`the use of a sampling grid having any particular number
`roWs and columns, or any particular con?guration.
`During the sampling of the selected region of interest the
`image data is arbitrarily addressed ?rst on a roW-at-a-time
`basis and then on a column-at-a-time basis until the entire
`sampling grid has been covered. In the preferred
`embodiment, the sampling necessary to produce the degree
`of focus metric of the invention may be performed at the
`same time as the sampling necessary to produce the White
`ness metric of the invention. More particularly, as sampling
`proceeds, the reader is instructed to store, in data structures
`such as those shoWn as memory spaces MS1 and MS2 in
`FIGS. 5B and 5C, data indicative of the sharpness of the
`transitions of the stored image data. At substantially the
`same time the reader is instructed to construct a histogram,
`such as that shoWn in FIG. 6, in Which there is stored, for
`each of the gray scale values encountered during sampling,
`a number equal to the number of times that value has
`occurred. As a result, at the conclusion of a sampling
`operation, the reader has stored all of the information it
`needs to determine the values of both the focus metric and
`the Whiteness metric.
`The manner in Which sampled image data is used to
`determine the magnitude of the degree of focus metric is best
`understood With reference to the Waveforms of FIGS. 4A
`through 4C and the data structures of FIGS. 5B and 5C.
`40
`Referring ?rst to FIGS. 4A—4C there are shoWn continuous
`Whiteness curves CA, CB and CC Which approximate the
`sequences of discrete gray scale values Which are stored at
`the addresses indicated by the X axes of those Figures.
`(Whether these X axes correspond to the roWs or columns of
`grid 116 is not important for present purposes). Also shoWn
`in FIGS. 4A—4C are pairs of addresses X0-X1, X2—X3, etc.
`Which de?ne the boundaries of the sampling intervals at
`Which pairs of gray scale values are read from memory 22.
`These pairs of sampling addresses are preferably in prox
`imity to one another in address space, although they are not
`necessarily immediately adjacent to one another. Stated
`differently, the sampling intervals are relatively narroW. In
`the preferred embodiment sampling address X1 is tWo
`address units greater than X0, although it might be as small
`as one unit greater or as large as N units greater, depending
`upon the particular application. Thus, the method of the
`invention is not limited to sampling intervals of any par
`ticular Width.
`For each pair of addresses sampled as shoWn in FIG. 4,
`there is produced a pair of values, such as Y0 and Y1, Which
`specify the intensities or Whiteness values of the addressed
`image data. If the siZes of all Whiteness increments are equal,
`i.e., if a linear Whiteness scale is used, the differences
`betWeen Whiteness values, such as Y1-Y0, divided by the
`differences betWeen the associated X values, such as X1-X0,
`Will result in numbers that are approximately indicative of
`
`45
`
`55
`
`65
`
`5,773,810
`
`8
`the slopes or steepness values of the tangents to the White
`ness curves at locations corresponding to respective sam
`pling intervals. In FIG. 4 these tangents are labelled T (0,1),
`T (2,3), etc., to indicate the sampling intervals that are
`associated thereWith. It Will therefore be seen that the
`above-described sampling steps approximate the effect of
`taking the derivative of Whiteness curves CA, CB and CC at
`a succession of sampling points. It Will also be seen that, if
`all sampling intervals are of the same Width, division by the
`differences betWeen the X values becomes unnecessary
`since the differences in the Y values Will themselves provide
`direct indications of the steepness or sharpness of the image
`data transitions.
`Because the number of transitions of the image data and
`the number of difference values produced during sampling is
`relatively large, at least a substantial number of image data
`transitions Will, by chance, coincide or otherWise be asso
`ciated With particular ones of the sampling intervals. In the
`case of FIG. 4A, Which shoWs image data for an image
`having high image contrast (i.e., high peak to peak values)
`and sharp image transitions, for example, transitions that
`occur during a sampling interval Will be associated With high
`Whiteness differences, such as Y1-Y0. In the case of FIG.
`4C, Which shoWs image data for an image having high image
`contrast but relatively less sharp image transitions, on the
`other hand, transitions that occur during a sampling interval
`Will be associated With loW Whiteness differences, such as
`Y1“-Y0“. Finally, in FIG. 4B, there is shoWn image data
`Which is the same as that shoWn in FIG. 4A, but Which has
`a loWer image contrast value. Signi?cantly, if the difference
`values for the image data of FIGS. 4A and 4B are each
`divided by the respective signal contrast values, the result
`Will be difference or sl