`
`
`
`
`
`
`
`UNITED STATES DEPARTMENT OF COMMERCE
`
`United States Patent and Trademark Office
`
`
`
`
`
`
`November 01, 2018
`
`
`
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY FROM THE
`
`RECORDS OF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`OF:
`
`APPLICATION NUMBER: 09/736,825
`
`FILING DATE: December 14, 2000
`
`PATENT NUMBER: 6,654,507
`
`ISSUE DATE: November 25, 2003
`
`By Authority of the
`
`
`
`
`
`
`
`
`
`
`
`
`_ ~ ‘
`Under Secretary of Commerce for Intellectual Property
`and Director of the United States Patent and Trademark Office E
`?
`
`
`
`
`M/Z/
`
`M. TARVER
`
`Certifying Officer
`
`PART (/ ) OF 92) PART(S)
`
`Page 1 of 263
`
`BOSCH EXHIBIT 1002 Part 1 of 2
`
`Page 1 of 263
`
`BOSCH EXHIBIT 1002 Part 1 of 2
`
`

`

`
`
`6654507
`
`'.T=?-=-.—‘\-
`
`
`
`fl__.-.43-:--_:-;_.-:,.—_
`
`—.A-—
`
` I I
`I
`III.
`
`fillgsax mmmInna:
`DIESEIB‘BGJH
`
`—=.
`
`_"'-'
`=n—
`=—
`_'—'
`
`
`
`5*
`Ina
`la:6
`9°{mlat
`"I
`In
`In
`
`Mnm.
`
`\I
`PD
`3!
`
`ISSUING CLASSIFICATION
`CROSS REFEFIENCE(S)
`
`mm?
`
`
`PATENT NUMBER
`
`
`ISSUECLASSIFICATION
`
`
`
`
`IIII III III
`
`
`.azaaetso-EHIUIIII-.'
`
`bEEIdfiTSGT81pl“Mm
`
`SO-TO-E—dTGB-BT—B-‘IB—Sb—I»!‘N“"95“”
`
`
`nasltlzi948991988833‘
`llllllllllllllllllllllll
`
`
`arrillfltIn!9182/12/6831“]
`
`
`28888
`SUBCLASS (ONE SUBCLASS PER BI Amount Due
`
`IIIIII
`
`
`
`-~"-=-W“-—-Féengjmfizs—w
`
`TITLE F INVENTION:
`
`TERMINAL
`ISCLAIMER
`
`
`
`
`I The term of this patent
`bsequent to
`‘
`has been dieolaimed.
`
`
`
`
` The term of this patent shall
`
`. APPLICANT(S): ~"um-mm-
`
`not extend beyond the expiration date
`of U.S Patent. No.
`
`months of
`If] The terminal
`this patent have been disclaimed.
`
`WARNING.
`The Information disclosed herein may be restricted. Unauthorized disclosure may be prohibited by the United States Code Title 35, Sections 122.181 and 368.
`Possession outside the U.S. Patent 8- Trademark Ofllce ls restricted to authorized employees and contractors only.
`Form PTO-436A
`;'
`(Flev. 6/99)
`
`FILED WITH: [:l DISK (CRF) D FICHE |:| CD—ROM
`(Attached in packet on right inside flap)
`
`issue FEEIII FILE
`
`Page 2 of 263
`
`(FACE)
`
`Page 2 of 263
`
`

`

`PATENT APPLICATION SERIAL NO.
`
`US. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`12/20/2000 ms ooooom «was
`moo w
`144.00 cu
`
`8% Ffiflgé
`
`09735825
`
`PTO-1556
`
`(5/87)
`'U.S. GPO: 2000-468-987/39595
`
`Page 3 of 263
`
`Page 3 of 263
`
`

`

`Page 1 of 1
`
`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`HIIIIHIIIIIIIIIIIHIIIIIIIIIIIIIIIIIIII|l|||l|H||II|II
`
`.17 Data Sheet
`.—
`
`COMMISSIONER FOR PATENTS
`UNITED STATES PATENT AND TRADEMARK OFFICE
`VVASHINGTDN. D C 2023I
`www.uspto.gov
`
`CONFIRMATION No. 8670
`
`I
`.
`I SERIAL NUMBER
`09/736,825
`
`FILING DATE
`12/14/2000
`RULE
`
`'
`- PPLICANTS
`Jiebo Luo, Rochester, NY;
`
`He CONTINUING DATA mkkiuhfli'flltfiifikiikfiitnlxl
`
`* FOREIGN APPLICATIONS ******W*****W*******
`
`IF REQUIRED, FOREIGN FILING LICENSE
`GRANTED ** 02/06/2001
`
`F
`
`'nPrioity [aimed
`“"9
`r
`c
`
`D m
`Yes
`D yes
`
`"0
`no DMet afler
`
`Patent Legal Staff
`Eastman Kodak Company
`343 State Street
`
`Rochester ,NY 14650-2201
`
`GROUP ART UNIT
`2621
`
`.
`
`ATTORNEY
`DOCKET NO.
`81595WFN
`
`STATE 0R SHEETS
`COUNTRY DRAWING
`
`TOTAL
`CLAIMS
`28
`
`INDEPENDENT
`CLAIMS
`2
`
`
`
`D All Fees
`
`CI 1.16 Fees ( Filing)
`
`D 1.17 Fees ( Processing Ext. of
`to charge/credit DEPOSIT ACCOUNT time D
`'— for followmg:
`:I 1.18 Fees (Issue)
`
`Cl Other
`
`3 Credit
`
`
`Page 4 of 263
`
`Page 4 of 263
`
`

`

`
`
`To:
`
`Box Patent Application
`Washington, DC. 20231
`
`AUTOMATICALLY PRODUCING AN IMAGE
`OF A PORTION OF A PHOTOGRAPHIC IMAGE
`
`
` UTILITY PATE ” PLICATION
`At .
`.NEY DOCKET 81595WFN
`
`
`Customer No. 01333
`TRANSMITTAL U1 - ml 37 CFR 1.530))
`
`
`
`
`Commissioner for Patents
`Express Mail Label No.
`
`
`lilllllllillllI1
`ul1]“ill
`ll
`“Illi
`mm
`
`EL267106180US
`
`Date: (flag fljfi-GJ‘L) at rm
`
`U
`
`013
`a“:
`:r‘h-
`
`6%
`jc
`
`First Named Inventor (or Application Identifier):
`
`Jiebo Luo
`
`
`
`
`
`
`Enclosed are:
`
`1.
`
`Specification
`
`2. IE] Sheet(s) of drawing(s)
`
`6.
`
`Assignment of the invention to
`
`
`copy of a p
`
`3. l:| Information Disclosure StatementUnder37 CFR
`
`1.97.
`
`8. D aggiigiglietPower ofAttorney
`
`4.
`
`Combined Declaration for Patent Application and Power of Attorney:
`4a.
`New
`
`4b. - Copy from a prior application (37 CFR 1.63(d) (for continuation/divisional with Box 11 completed)
`
`9. El Deletion of Inventor! s).
`5. El Inco orationb Reference useable if Box 4b is
`
`Signed statement attached deleting inventor(s) named
`checked! The entire disclosure of the prior application, from
`in the prior application, see 37 CFR 1.63(d)(2) and
`which a copy of the Oath or declaration is supplied under Box 4b,
`1.33(b).
`is considered as being part of the disclosure of the accompanying
`
`application and is hereby incorporated by reference therein.
`10.
`If'a ] I M. application prior to examination ofthe above-identified application, amend the specification at Page 1,
`after the title, by inserting the following:
`--CROSS REFERENCE TO RELATED APPLICATION
`
`Reference is made to and priority claimed from US. Provisional Application Serial No. ,
`filed , entitled.
`If a CONTINUING APPLICATION, check appropriate box and supply the requisite information:
`11. El Continuation El Divisional D Continuation—impart (CIP)
`ofprior application No: ,
`12.
`Please address all written communications to Thomas H. Close, Patent Legal Staff,
`Eastman Kodak Company, 343 State Street, Rochester, NY 14650—2201.
`Please Direct all telephone calls to William F. Nova] at (716) 477-5272.
`
`The filing fee has been calculated as shown below:
`
`
`
`
`
`Please charge my Eastman Kodak Company Deposit Account No. 05-0225 in the amount of
`A duplicate copy of this sheet is enclosed
`The Commissioner is hereby authorized to charge any additional filing fees required under
`
`37 CFR 1.16 or credit any overpayment to Eastman Kodak Company Deposit Account No. 05—0225.
`A duplicate copy of this sheet is enclosed.
`
`$ 854 .
`
`William F. Noval/law
`Telephone: (716) 477-5272
`Facsimile: (716) 477-4646
`
`WM§%.W
`
`Attorney for Applicants
`Registration No. 22,049
`
`Page 5 of 263
`
`Page 5 of 263
`
`

`

`PATENT APPLICATION BASED ON:
`
`Docket No:
`
`81595/WFN
`
`Inventors:
`
`Attorney:
`
`Jiebo Luo
`
`William F. Noval
`
`
`AUTOMATICALLY PRODUCING AN IMAGE OF A PORTION OF A
`PHOTOGRAPHIC IMAGE
`
`Commissioner for Patents
`
`Attn: Box Patent Application
`
`Washington, DC 20231
`
`Express Mail Label No: 5L0? <0 7/(3 [a A575“) 05
`numeral) #401000
`
`Page 6 of 263
`
`Page 6 of 263
`
`

`

`-1-
`
`AUTOMATICALLY PRODUCING AN IMAGE OF A PORTION OF A
`
`PHOTOGRAPHIC IMAGE
`
`CROSS REFERENCE TO RELATED APPLICATION
`
`Reference is made to commonly assigned US. Patent Application
`\\
`Serial No.097490,915, filed January 25, 2000, entitled “Method for Automatically
`
`Creating Cropped and Zoomed Versions of Photographic images” by Jiebo Luo et
`al., and assigned US. Patent Application Serial No. 057223360, filed December
`31, 1998, entitled “Method for Automatic Determination o\fMain Subjects in
`
`Photographic Images”, by Jiebo Luo et al., the disclosures of which are
`
`incorporated herein by reference.
`
`FIELD OF THE INVENTION
`
`This invention relates in general to producing an image of a portion
`
`of a photographic image by using digital image processing.
`
`BACKGROUND OF THE INVENTION
`
`For many decades, traditional commercial photofinishing systems
`
`have placed limits on the features offered to consumers to promote mass
`
`production. Among those features that are unavailable conventionally, zooming
`
`and cropping have been identified by both consumers and photofinishers as
`
`extremely useful additional features that could potentially improve the quality of
`
`the finished photographs and the subsequent picture sharing experiences. With
`
`the advent of, and rapid advances in digital imaging, many of the technical
`
`barriers that existed in traditional photography no longer stand insurmountable.
`
`Hybrid and digital photography provide the ability to crop
`
`undesirable content from a picture, and magnify or zoom the desired content to fill
`
`the entire photographic print. In spite of the fact that some traditional cameras
`
`with zoom capability provide consumers greater control over composing the
`
`desired scene content, studies have found that photographers may still wish to
`
`perform a certain amount of cropping and zooming when Viewing the finished
`
`photograph at a later time. Imprecise viewfinders of many point-and-shoot
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Page 7 of 263
`
`Page 7 of 263
`
`

`

`_2_
`
`cameras, as well as simply second-guessing their initial compositions, are factors
`
`in the desirability of zoom and crop. In addition, it may be desirable to use some
`
`other regular border templates such as ovals, heart shapes, squares, etc. In another
`
`scenario, some people commonly referred to as “scrapbookers” tend to perform
`
`more aggressive crop in making a scrapbook, e.g., cutting along the boundary of
`
`objects.
`
`There are significant differences in objectives and behaviors
`
`between“these’twotypesofcropping; namelyalbum-making and-scrapbookwv
`
`making, with the latter more difficult to understand and summarize. The
`
`invention described below performs automatic zooming and cropping for making
`
`photographic prints. One customer focus group study indicated that it would be
`
`beneficial to provide customers a double set of prints —- one regular and one zoom.
`
`Moreover, it is preferred that the cropping and zooming be done automatically.
`
`Most customers do not want to think about how the zooming and cropping is
`
`being done as long as the content and quality (e.g., sharpness) of the cropped and
`
`zoomed pictures is acceptable.
`
`There has been little research on automatic zoom and crop due to
`
`the apparent difficulty involved in performing such a task. None of the known
`
`conventional image manipulation software uses scene content in determining the
`
`automatic crop amount. For example, a program entitled “XV”, a freeware
`
`package developed by John Bradley at University of Pennsylvania, USA
`
`(Department of Computer and Information Science), provides an "autocrop"
`
`function for manipulating images and operates in the following way:
`
`the program examines a border line of an image, in all of the four
`
`10
`
`15
`
`20
`
`25‘
`
`directions, namely fi‘om the top, bottom, left and right sides;
`
`the program checks the variation within the line. In grayscale
`
`images, a line has to be uniform to be cropped. In color images, both the spatial
`
`correlation and spectral correlation have to be low, except for a small percentage
`
`of pixels, for the line to be qualified for cropping. In other words, a line will not
`
`30
`
`be cropped if it contains a significant amount of variation;
`
`if a line along one dimension passes the criterion, the next line
`
`(row or colunm) inward is then examined; and
`
`Page 8 of 263
`
`Page 8 of 263
`
`

`

`I?“
`
`5"“)
`
`-3-
`
`the final cropped image is determined when the above recursive
`
`process stops.
`
`This program essentially tries to remove relatively homogeneous
`
`margins around the borders of an image. It does not examine the overall content of
`
`5
`
`the image. In practice, the XV program is effective in cropping out the dark
`
`border generated due to imprecise alignment during the scanning process.
`
`However, disastrous results can often be produced due to the apparent lack of
`
`scene understanding. In some extreme cases, the entire image can be cropped.
`
`Another conventional system, described by Bollman et al. in US.
`
`10
`
`Patent 5,978,519 provides a method for cropping images based upon the different
`
`intensity levels within the image. With this system, an image to be cropped is
`
`scaled down to a grid and divided into non—overlapping blocks. The mean and
`
`variance of intensity levels are calculated for each block. Based on the
`
`distribution of variances in the blocks, a threshold is selected for the variance. All
`
`15
`
`blocks with a variance higher than the threshold variance are selected as regions
`
`of interest. The regions of interest are then cropped to a bounding rectangle.
`
`However, such a system is only effective when uncropped images contain regions
`
`where intensity levels are uniform and other regions where intensity levels vary
`
`considerably. The effectiveness of such a system is expected to be comparable to
`
`20
`
`that of the XV program. The difference is that the XV program examines the
`
`image in a line by line fashion to identify uniform areas, while Bollman examines
`
`the image in a block by block fashion to identify uniform areas.
`In summary, both techniques cannot deal with images with non—
`
`uniform background.
`
`25
`
`In addition, in the earlier invention disclosed in US. Patent
`
`Application Serial No. 09/490,915, filed January 25, 2000, the zoom factor needs
`
`to be specified by the user. There is, therefore, a need for automatically
`
`determining the zoom factor in order to automate the entire zoom and crop
`
`process.
`
`30
`
`Some optical printing systems have the capability of changing the
`
`optical magnification of the relay lens used in the photographic copying process.
`
`In US. Patent 5,995,201, Sakaguchi describes a method of varying the effective
`
`Page 9 of 263
`
`Page 9 of 263
`
`

`

`o
`a,
`
`— 4 —
`
`m
`
`magnification of prints made from film originals utilizing a fixed optical lens
`
`instead of zoom lens. In US. Patent 5,872,619, Stephenson et al. describe a
`
`method of printing photographs from a processed photographic filmstrip having
`
`images of different widths measured longitudinally of the filmstrip and having
`
`heights measured transversely of the filmstrip. This method uses a photographic
`
`printer having a zoom lens and a printing mask to provide printed images having a
`
`selected print width and a selected print height. In US. Patent 4,809,064, Amos et
`
`al. describe an apparatus for printing a selected region of a photographic negative
`
`onto a photosensitive paper to form an enlarged and cropped photographic print.
`
`This apparatus includes means for projecting the photographic negative onto first
`
`and second zoom lenses, each of the zoom lenses having an adjustable
`
`magnification. In US. Patent 5,872,643, Maeda et al. describe a film reproducing
`
`apparatus that can effectively perform zoom and crop. This apparatus includes an
`
`image pick-up device which picks up a film frame image recorded on a film to
`
`generate image data, an information reader which reads information about
`
`photographing conditions of the film frame image, and a reproducing area
`
`designator which designates a reproducing area of the film fi'ame image.
`
`However, the reproducing area of the film frame image is determined based on
`
`pre-recorded information about the position of the main object, as indicated by
`
`which zone of the photograph the automatic focusing (AF) operation in the
`
`camera was on — part of the recorded information about photographing conditions.
`
`In all the above-mentioned optical printing systems, the position of the
`
`photographic film sample and magnification factor of the relay lens are pre-
`
`selected.
`
`SUMMARY OF THE INVENTION
`
`According to the present invention, there is provided a solution to
`
`the problems of the prior art. It is an object of the present invention to provide a
`
`method for producing a portion of a photographic image by identifying the main
`
`subject of the photographic image.
`
`According to a feature of the present invention, there is provided
`
`a method of producing an image of at least a portion of a digital image,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Page 10 of 263
`
`Page 10 of 263
`
`

`

`(‘1.
`
`A
`
`comprising the steps of:
`
`a) providing a digital image having pixels;
`
`b) computing a belief map of the digital image, by using the pixels
`
`of the digital image to determine a series of features, and using such features to
`
`5
`
`assign the probability of the location of a main subject of the digital image in the
`
`belief map;
`
`c) determining a crop window having a shape and a zoom factor,
`
`the shape and zoom factor determining a size of the crop window; and
`
`d) cropping the digital image to include a portion of the image of
`
`10
`
`high subject content in response to the belief map and the crop window.
`
`ADVANTAGEOUS EFFECT OF THE INVENTION
`
`One advantage of the invention lies in the ability to automatically
`
`crop and zoom photographic images based upon the scene contents. The digital
`
`image processing steps employed by the present invention includes a step of
`
`15
`
`identifying the main subject within the digital image. The present invention uses
`
`the identified main subject of the digital image to automatically zoom and crop the
`
`image. Therefore, the present invention produces hi gh—quality zoomed or cropped
`
`images automatically, regardless whether the background is uniform or not.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`20
`
`The foregoing and other objects, aspects and advantages will be better
`
`understood from the following detailed description of a preferred embodiment of
`
`the invention with reference to the drawings, in which:
`
`F1g\1 is a schematic diagram of a system embodiment of the invention;
`
`Fig. 2 is a schematic architectural diagram of an embodiment of the
`
`25
`
`invention;
`
`\
`
`Fig. 3. is a schematic architectural diagram of an embodiment of the invention;
`
`Fig. Z is a schematic architectural diagram of an embodiment of the
`
`invention;
`
`Fig. 5 illustrates the application of the invention to a simulated
`
`30
`
`photograph;
`
`Page 11 of 263
`
`Page 11 of 263
`
`

`

`-6-
`
`F1g‘6 illustrates the application of the invention to a simulated
`
`photograph;
`F1E7 illustrates the application ofthe invention to a simulated
`photograth‘
`Fig. 8 illustrates the application of the invention to a simulated
`
`5
`
`photograph;
`Fig‘.‘9rillustrates the application of the invention to a simulated
`photograph;
`
`Fig; 10 illustrates the application of the invention to a simulated
`
`10
`
`photograph;
`
`Fig."1-;1 illustrates the application of the invention to a simulated
`
`.a-
`
`photograph;
`
`
`
`
`
`Fig‘an illustrates the application of the invention to a simulated
`
`15
`
`photograph;
`Fi‘gNS is an exemplary uncropped photograph;
`Figs,“ is a belief map of the image shown in FIG. 13;
`
`Figlfilj is a cropped version of the image shown in FIG. 13;
`
`Fig.= 17 is a belief map of the image shown in FIG. 16; and
`Fig. 1‘8 is a cropped version ofthe image shown in FIG. 16.
`
`20
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`25
`
`The invention automatically zooms and crops digital images
`according to an analysis of the main subject in the scene. Previously, a system for
`detecting main subjects (e.g., main subject detection or “MSD”) in a consumer-
`
`type photographic image from the perspective of a third-party observer has been
`developed and is described in US. Patent Application Serial No. 09/223,860, filed
`December 31, 1998, the disclosure of which is incorporated herein by reference.
`Main subject detection provides a measure of saliency'or relative importance for
`different regions that are associated with different subjects in an image. Main
`subject detection enables a discriminative treatment of the scene content for a
`
`30
`
`number of applications related to consumer photographic images, including
`automatic crop and zoom.
`
`Page 12 of 263
`
`Page 12 of 263
`
`

`

`_ 7 _
`
`Conventional wisdom in the field of computer Vision, which
`
`reflects how a human observer would perform such tasks as main subject
`
`detection and cropping, calls for a problem-solving path Via object recognition and
`
`scene content determination according to the semantic meaning of recognized
`
`5
`
`objects. However, generic object recognition remains a largely unsolved problem
`
`despite decades of effort from academia and industry.
`
`The MSD system is built upon mostly low-level vision features
`
`with semantic information integrated whenever available. This MSD system has a
`
`number of sub-tasks, including region segmentation, perceptual grouping, feature
`
`10
`
`extraction, and probabilistic and semantic reasoning. In particular, a large number
`
`of features are extracted for each segmented region in the image to represent a
`
`wide variety of visual saliency properties, which are then input into a tunable,
`
`extensible probability network to generate a belief map containing a continuum of
`
`values.
`
`15
`
`Using MSD, regions that belong to the main subject are generally
`
`differentiated from the background clutter in the image. Thus, automatic zoom
`
`and crop becomes possible. Automatic zoom and crop is a nontrivial operation
`
`that was considered impossible for unconstrained images, which do not
`
`necessarily contain uniform background, without a certain amount of scene
`
`20
`
`understanding. In the absence of content-driven cropping, conventional systems
`
`have concentrated on simply using a centered crop at a fixed zoom
`
`(magnification) factor, or removing the uniform background touching the image
`
`borders. The centered crop has been found unappealing to customers.
`
`The output of MSD used by the invention is a list of segmented
`
`25
`
`regions ranked in descending order of their likelihood (or belief) as potential main
`
`subjects for a generic or specific application. This list can be readily converted
`
`into a map in which the brightness of a region is proportional to the main subject
`
`belief of the region. Therefore, this map can be called a main subject “belief”
`
`map. This “belief ’ map is more than a binary map that only indicates location of
`
`30
`
`the determined main subject. The associated likelihood is also attached to each
`
`region so that regions with large values correspond to regions with high
`
`confidence or belief of being part of the main subject.
`
`Page 13 of 263
`
`Page 13 of 263
`
`

`

`f“
`
`m.
`
`-8—
`
`To some extent, this belief map reflects the inherent uncertainty for
`
`humans to perform such a task as MSD because different observers may disagree
`
`on certain subject matter while agreeing on other subject matter in terms of main
`
`subjects. However, a binary decision, when desired, can be readily obtained by
`
`5
`
`using an appropriate threshold on the belief map. Moreover, the belief
`
`information may be very useful for downstream applications. For example,
`
`different weighting factors can be assigned to different regions (subject matters) in
`
`determining the amount of crop.
`
`For determination of crop, the invention uses the main subject
`
`10
`
`belief map instead of a binarized version of the map to avoid making a bad
`
`cropping decision that is irreversible. Furthermore, using the continuous values of
`
`the main subject beliefs helps trade—off different regions under the constraints
`
`encountered in cropping. A binary decision on what to include and what not to
`
`include, once made, leaves little room for trade-off. For example, if the main
`
`15
`
`subject region is smaller than the crop window, the only reasonable choice, given
`
`a binary main subject map, is to leave equal amounts of margin around the main
`
`subject region. On the other hand, secondary main subjects are indicated by lower
`
`belief values in the main subject belief map, and can be included according to a
`
`descending order of belief values once the main subject of highest belief values
`
`20
`
`are included. Moreover, if an undesirable binary decision on what to
`
`include/exclude is made, there is no recourse to correct the mistake.
`
`Consequently, the cropping result becomes sensitive to the threshold used to
`
`obtain the binary decision. With a continuous-valued main subject belief map,
`
`every region or object is associated with a likelihood of being included or a belief
`
`25
`
`value in its being included.
`
`To reduce the degrees of freedom in determining the amount of
`
`crop, and to limit the amount of resolution loss incurred in the zoom process, in
`
`particular for making photographic prints, in one embodiment, the invention
`
`restricts the set of allowable zoom factors to the range of [1.2, 4]. This is based on
`
`30
`
`the findings in the customer focus studies. Those skilled in the art would
`
`recognize that the present invention could be used with any the zoom factor.
`
`Page 14 of 263
`
`Page 14 of 263
`
`

`

`.r
`
`_,
`
`_ 9 _
`
`To reduce the degrees of freedom in determining the amount of
`
`crop, in particular for making photographic prints, in one embodiment, the
`
`invention restricts the set of allowable zoom factors to the range of [1.2, 4.0].
`
`This is based on the findings in the customer focus studies. In addition, an
`
`5
`
`extremely large zoom factor usually leads to blurry and unacceptable picture due
`
`to the limit imposed by the resolution of the original image. If a zoom factor
`
`determined by the present invention falls within the range of acceptable zoom
`
`factors (e.g., between 1.2 and 4.0), it will be used in the subsequent cropping
`
`process. Otherwise, the zoom factor is clipped to 1.2 at the lower end and 4.0 at
`
`10
`
`the higher end.
`
`General Description ofDigital and Optical Printer System
`
`Referring to Fig. 1, the following description relates to a digital
`
`printing system. A source digital image 10 is received by a digital image
`
`processor 20. The digital image processor 20 may be connected to a general
`
`15
`
`control computer 40 under operator control from an input control device 60. The
`
`monitor device 50 displays diagnostic information about the digital printing
`
`system. The general digital image processor 20 performs the needed image
`
`processing to produce a cropped and zoomed digital image 99.
`
`Referring to Fig. la, the following description relates to an optical
`
`20
`
`printing system. A photographic film sample 31 is received by a film scanner 32
`
`which produces a source digital image 10 relating to the spatial density
`
`distribution of the photographic film sample. This source digital image is
`
`received by a digital image processor 20. The digital image processor 20 may be
`
`connected to a general control computer 40 under operator control from an input
`
`25
`
`control device 60. The monitor device 50 displays diagnostic information about
`
`the optical printing system. The general control computer 40 keeps track of the
`
`lens magnification setting.
`
`Referring to Fig. 2, a zoom factor 11, which corresponds to the lens
`
`magnification setting may also received by the image processor 20 from the
`
`30
`
`general control computer 40 under operator control. The image processor 20
`
`receives the source digital image 10 and uses the zoom factor 11 and the source
`
`digital image 10 to calculate the proper position for the photographic film sample
`
`Page 15 of 263
`
`Page 15 of 263
`
`

`

`(MK:
`
`I:
`
`.i
`
`_1()_
`
`in the form of a film sample position 9. The photographic film sample is
`
`positioned in a gate device 36 which holds the film negative in place during the
`
`exposure. The gate device 36 receives the film sample position 9 to position the
`
`photographic film sample to adjust which portion of the imaging area of the
`
`photograph will be printed.
`
`Referring to Fig. la, a lamp house 34 provides the illumination
`
`source which is transmitted through the photographic film sample 31 and focused
`
`by a lens 12 onto photographic paper 38. The time integration device 13 opens
`
`and closes a shutter for a variable length of time allowing the focused light from
`
`the lamp house 34 to expose the photographic paper 38. The exposure control
`
`device 16 receives a brightness balance value from the digital image processor 20.
`
`The exposure control device 16 uses the brightness balance value to regulate the
`
`length of time the shutter of the time integration device stays open.
`
`A block diagram of the inventive cropping process (e. g., the digital
`
`image understanding technology) is shown in Fig. 3, which is discussed in relation
`
`to Figs. 5-12. Figs. 5—12 illustrate the inventive process being applied to an
`
`original image shown in Fig. 5.
`
`In item 200, the belief map is created using MSD. The present
`
`invention automatically determines a zoom factor (e. g. 1.5X) and a crop window
`
`80 (as shown in Fig. 7), as referred to in item 201 of Fig. 3. This zoom factor is
`
`selected by an automatic method based directly on the main subj ect belief map
`
`(e.g., an estimate of the size of the main subject). The crop window is typically a
`
`rectangular Window with a certain aspect ratio. After the zoom factor is
`
`determined by the digital image processor 20, the value of the zoom factor is used
`
`subsequently by the digital image processor 20 shown in Fig. 1. In Fig. la, the
`
`zoom factor is used to communicate with the lens 12 to adjust the lens
`
`magnification setting. This adjustment allows the lens 12 to image the appropriate
`
`size of the photographic film sample 31 onto the photographic paper 38.
`
`In item 201, regions of the belief map are clustered and the lowest
`
`belief cluster (e.g., the background belief) is set to zero using a predefined
`
`threshold. As discussed in greater detail below, sections of the image having a
`
`belief value below a certain threshold are considered background sections. In
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`Page 16 of 263
`
`Page 16 of 263
`
`

`

`m
`._~__
`
`:4“?
`-._
`
`-11-
`
`item 202 such sections are given a belief of zero for purposes of this embodiment
`
`of the invention.
`
`Then, in item 202 the centroid, or center—of—mass (used
`
`interchangeably hereon forth), of nonzero beliefs are computed. More
`
`5
`
`specifically, in Fig. 5 the subject having the highest belief in the belief map is the
`
`woman and the stroller. Fig—.7 illustrates that the centroid of this subject is
`
`approximately the top of the baby's head.
`
`The centroid ()2, )9) of a belief map is calculated using the following
`
`procedure:
`
`10
`
`5c = 2x.bel(x,..y.-). 9 = Zy.bez(x,..y,.),
`
`where xi and y,. denote that coordinates of a pixel in the belief map
`
`and bel(x,. , yi) represents the belief value at this pixel location.
`
`Before the crop window is placed, a proper crop window is
`
`determined in item 203. Referring to Fig. 4, there is shown a block diagram of a
`
`15
`
`method that automatically determines a zoom factor in response to the belief map.
`
`In item 301, two second—order central moments, cXX and cm with respect to the
`
`center—of—mass, are computed using the following procedure:
`;
`
`Zea,- —2)2 xbeleny.)
`
`20.— —r)2 xbel(x.-,y.-)
`
`Note that these two terms are not the conventional central moments
`
`20
`
`that are computed without any weighting functions. In the preferred embodiment,
`
`a linear weighting function of the belief values is used. However, the
`
`conventional central moments, or central moments by a nonlinear function of the
`
`belief values, can also be used.
`
`An effective bounding rectangle (MBR) of the regions of high
`
`25
`
`subject content can be calculated using the following procedure, where the
`
`dimensions of the MBR are calculated by:
`
`DX =2x 3><cu ,D}, =2x .Bxcyy
`
`Page 17 of 263
`
`Page 17 of 263
`
`

`

`N-
`
`t"?
`
`-12-
`
`Fig. 6 illustrates that the effective bounding rectangle 70 is
`
`centered at approximately the top of the boy’s head and approximately
`
`encompasses the region of high subject content. In general, the aspect ratio of the
`
`original image is maintained. Therefore, a crop window 80 is determined in item
`
`5
`
`303 such that it is the smallest rectangle of the original aspect ratio that
`
`encompaSSes the effective MBR 70.
`
`In item 204, the initial position of the crop window p 80 is centered
`
`at the centroid, as shown in Fig. 7.
`
`The crop window is 80 then moved so that the entire crop window
`
`10
`
`is within the original image (e.g. item 205) as shown in Fig. 8. In item 206, the
`
`crop window 80 is moved again so that all the regions of the highest belief values
`
`(“main subject”) are included within the crop window and to create a margin 81,
`
`as shown in FIG. 9. This process (e. g., 206) captures the entire subject of interest.
`
`Therefore, as shown in Fig. 9, the top of the woman's head is included in the crop
`
`15
`
`window. Compare this to Fig. 8 where the top of the woman's head was outside
`
`the crop window.
`
`Decision box 207 determines whether an acceptable solution has
`
`been found, i.e., whether it is possible to include at least the regions of the highest
`
`belief values in the crop window.
`
`20
`
`If an acceptable solution exists, the window is again moved, as
`
`shown in item 208, to optimize a subject content index for the crop Window. The
`
`preferred embodiment of the present invention defines the subject content index as
`
`the sum of belief values within the crop window. It should be noted that the
`
`present invention specifies higher numerical belief values corresponding to higher
`
`25
`
`main subject probability. Therefore, finding a numerical maximum of the sum of
`
`the belief values is equivalent to finding an optimum of the subject content index.
`
`This is shown in Fig. 10 where the secondary objects (e.g. flowers) are included
`
`within the crop window 80 to increase the sum of beliefs. The sum of beliefs for a
`
`crop window is computed as follows.
`
`30
`
`sum(w)= Z 1781050)),
`(x,v)sw
`
`Page 18 of 263
`
`Page 18 of 263
`
`

`

`”A“
`
`V
`
`_13_
`
`where bel(x, y) represents the belief value at a given pixel location
`
`(x, y) within the crop Window w.
`
`Provided that the primary subjects are included, moving the crop
`
`window so that more of the secondary subjec