Automated cropping of electronic images

• US 7,133,571 B2
• Filed: 12/20/2001
• Issued: 11/07/2006
• Est. Priority Date: 12/22/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Cheatle, Stephen Philip
• Primary Examiner(s): Miriam, Daniel
• Assistant Examiner(s): Rosario, Dennis
• Application Number:
  US10/169,841
• Publication Number:
  US 20020191861A1
• Time in Patent Office: 1,783 Days
• Field of Search: 382/282
• US Class Current: 382/282
• CPC Class Codes: G06T 3/04 Context-preserving transformations, e.g. by using an importance map panospheric to cylindrical image transformations G06T3/12
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/44 using image operators, e.g. filters, edge density metrics or local histograms
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: H04N 1/3872 Repositioning or masking

Abstract

The present invention relates to the automated and semi-automated cropping of electronic images, and in particular to an apparatus and a method of using an electronic camera to capture and crop such electronic images. An electronic imaging processing device (1) for cropping an electronic image comprises an image processing means (6,8), the image processing means including an electronic processor (6) and firmware and/or software for processing the electronic image. The device (1) processes the electronic image to identify one or more features relevant to the composition of the electronic image, each such feature having one or more compositionally significant properties from amongst a plurality of different predetermined compositional properties, and each such feature occupying a sub-region of the electronic image. Then the device (1) selects one or more compositional rules from a set of predetermined compositional rules, based on the relevance of the compositional rule(s) to the compositionally significant properties of one or more of the identified features. Then the device (1) determines one or more suitable crop boundaries by applying one or more of the selected compositional rules.

Claims

1. An electronic image processor for cropping an electronic image, the image processor adapted to:

a) process the electronic image to identify one or more features relevant to the composition of the electronic image;

b) select at least one compositional rule from a plurality of predetermined compositional rules, based on the relevance of the compositional rule(s) to one or more of the identified features;

c) determine one or more suitable crop boundaries by applying the selected compositional rules;

d) generate a number of crop candidates corresponding to said crop boundaries;

e) generate minimum and maximum crop limits for each of the crop candidates;

f) evaluate suitable candidate crop boundaries between the minimum and maximum crop limits by generating a measure of quality for each candidate crop boundary in accordance with at least one quality metric; and

g) select a reduced number of crop candidates as output candidates based on the measure of quality generated in the evaluating step.

2. An electronic image processor as claimed in claim 1, wherein the image processor includes at least one of firmware and software for processing an image.

3. An electronic image processor as claimed in claim 1 wherein the processor is arranged to analyse the image in order to produce a saliency map.

4. An electronic image processor as claimed in claim 3, wherein the image comprises a plurality of pixels and the image processor is arranged to cluster similar pixels in the image into regions and the regions are analysed to determine a measure of unusualness within the image.

5. An electronic image processor as claimed in claim 4, in which regions which are unusual are rated as more salient than regions which occur more commonly.

6. An electronic image processor as claimed in claim 3, wherein the image processor searches the image for shapes which according to a predetermined rule are regarded as relevant features, such features including faces of people.

7. An electronic image processor as claimed in claim 3, wherein the image processor searches the image for shapes which according to a predetermined rule are regarded as relevant features, such features including tagged objects.

8. An electronic camera system for capturing an electronic image of a scene, comprising, a detector array for capturing the electronic image, an optical imaging system arranged to image the scene onto the detector array, and an image processor for cropping the captured image, wherein the image processor is as claimed in claim 1.

9. An electronic camera as claimed in claim 8, in which the camera includes means by which a user of the camera may tag one or more features relevant to the composition of the electronic image, said tagged feature(s) then being associated with a compositional rule that includes said tagged feature(s) in the cropped image.

10. An electronic image processor as claimed in claim 1, wherein the minimum crop limit for a respective crop candidate corresponds to a first rectangular region that encompasses a region in the electronic image that includes all of a particular contiguous feature, and the maximum crop limit for the respective crop candidate corresponds to a second rectangular region that encompasses the first rectangular region and that abuts respective minimum crop limits of other crop candidates that correspond to adjacently positioned regions in the electronic image and that respectively include all of other particular contiguous features.

11. An electronic image processor method, comprising:

processing an electronic image to identify compositionally significant features within the image,

sorting the compositionally significant features according to at least one compositional rule into those features which are to be included within cropped versions of the image and those features which are to be excluded from cropped versions of the image,

automatically generating a plurality of candidate crops based on the sorted compositionally significant features, wherein each of the candidate crops is not merely the smallest crop that encloses a feature which is to be included,

generating minimum and maximum crop limits for each of the candidate crops,

identifying suitable crop candidate boundaries between the minimum and maximum crop limits for each of the candidate crops, by generating a measure of quality in accordance with at least one quality metric, and

selecting a reduced number of crop candidates as output candidates based on the measure of quality generated in the identifying step.

12. An electronic image processor as claimed in claim 11, wherein suitable crop boundaries are identified by applying a plurality of constraints to the image, the constraints generated from at least one compositional rule.

13. An electronic image processor method as claimed in claim 11, wherein the minimum crop limit for a respective crop candidate corresponds to a first rectangular region that encompasses a region in the electronic image that includes all of a particular contiguous feature, and the maximum crop limit for the respective crop candidate corresponds to a second rectangular region that encompasses the first rectangular region and that abuts respective minimum crop limits of other crop candidates that correspond to adjacently positioned regions in the electronic image and that respectively include all of other particular contiguous features.

14. An electronic image processor, comprising:

an analyzer unit configured to analyse an image to identify compositionally significant features therein;

a compositional rule application unit configured to apply at least one composition rule so as to generate a plurality of constraints;

a candidate crop generation unit configured to apply the constraints to the image to generate a plurality of minimum and maximum candidate crops each one having a measurement associated therewith indicating the extent to which the constraints are violated;

an identifying unit configured to identify suitable crop candidate boundaries between the minimum and maximum crop limits for each of the candidate crops, by generating a measure of quality in accordance with at least one quality metric; and

a presenting unit configured to present at least one of the candidate crops to a user, in accordance with the generated measure of quality.

15. An electronic image processor as claimed in claim 14, wherein the minimum crop limit for a respective crop candidate corresponds to a first rectangular region that encompasses a region in the electronic image that includes all of a particular contiguous feature, and the maximum crop limit for the respective crop candidate corresponds to a second rectangular region that encompasses the first rectangular region and that abuts respective minimum crop limits of other crop candidates that correspond to adjacently positioned regions in the electronic image and that respectively include all of other particular contiguous features.

16. A method of using an electronic image processing device for cropping an electronic image, the image processing device comprising an image processing means, the image processing means including at least one of an electronic processor, firmware and software for processing the electronic image, wherein the method comprises the steps of using the image processing means to:

i) process the electronic image to identify at least one feature relevant to the composition of the electronic image each such feature occupying a sub-region of the electronic image;

ii) select at least one compositional rule from a set comprising a plurality of predetermined compositional rules, based on the relevance of the compositional rule(s) to at least one of the identified features; and

iii) determine at least one suitable crop boundary for a plurality of crop candidates by applying one or more of the selected compositional rules,

in which;

step (i) includes identifying features which constitute non-overlapping segmented regions of interest;

step (iii) is achieved by first selecting alternative divisions of said identified regions of interest into those which will be included by the crop boundary and those which will be excluded by the crop boundary;

each such alternative division of regions of interest is used to determine an inner crop boundary limit and an outer crop boundary limit such that the inner crop boundary limit is the smallest boundary which circumscribes the regions of interest to be included and the outer crop boundary limit is the largest boundary which excludes the regions of interest to be excluded; and

said one or more suitable crop boundaries are determined between the limits of the inner and outer crop boundary limits for each of said alternative divisions of regions of interest.

17. A method as claimed in claim 16, in which each identified feature has at least one compositionally significant property from amongst a plurality of different predetermined compositional properties, and at least one compositional rule is selected from a set of predetermined compositional rules, based on the relevance of the compositional rule(s) to the compositionally significant properties of one or more of the identified features.

18. A method as claimed in claim 16, in which step (iii) comprises the steps of:

iv) generating a plurality of alternative candidate crop boundaries for each of the plurality of crop candidates, the alternative candidate crop boundaries including minimum and maximum crop boundaries;

v) generating a measure of composition quality for each alternative minimum and maximum candidate crop boundary by using a set of picture composition metrics; and

vi) selecting a reduced number of crop candidates having a relatively high measure of composition quality.

19. A method as claimed in claim 18, in which only one crop candidate is selected.

20. A method as claimed in claim 18, wherein the minimum crop boundary for a respective crop candidate corresponds to a first rectangular region that encompasses a region in the electronic image that includes all of a particular contiguous feature, and the maximum crop boundary for the respective crop candidate corresponds to a second rectangular region that encompasses the first rectangular region and that abuts respective minimum crop limits of other crop candidates that correspond to adjacently positioned regions in the electronic image and that respectively include all of other particular contiguous features.

21. A method as claimed in claim 16, in which step (iii) comprises the steps of:

vii) implementing the compositional rules as constraints that may be satisfied to a greater or lesser degree, each constraint having an associated cost function that increases the less well the constraint is satisfied;

viii) defining an overall cost metric as a function of crop coordinates in the image, by forming a combination of the separate cost functions associated with each individual constraint;

ix) applying an optimisation method to find at least one best crop locations by finding minima in the overall cost metric; and

x) selecting as output a reduced number of crop candidates for said best crop locations.

22. A method as claimed in claim 21, in which only one crop candidate is selected.

23. A method as claimed in claim 16, in which the crop boundary of the cropped image has a plurality of crop edges, and the steps of the method are performed separately for each crop edge to generate the crop boundary.

24. A method as claimed in claim 16 in which said inner crop boundary limit and said outer crop boundary limit has a plurality of edges and one or more suitable crop boundaries are determined by evaluating an edge quality metric for each possible edge placement between the inner and outer crop boundary limits, the selection of best crop boundary being at least in part dependent on the separate edge quality metrics of each of the boundary'"'"'s edges, each possible edge placement corresponding to a particular pixel row or pixel column in the electronic image.

25. A method as claimed in claim 16, in which one or more of said suitable crop boundaries are presented to a user of the device for manual selection by the user for cropping of the electronic image.

26. A method as claimed in claim 17, in which in step (i) blank or uninteresting areas are detected as some of the features relevant to the composition and in steps (ii) and (iii) one or more of the compositional rules cause the image to be cropped according to the arrangement of said blank or uninteresting areas relative to other identified features relevant to the composition of the electronic image.

27. A method as claimed in claim 16, in which the image is a colour image and at least one feature is identified by segmenting the image into areas of similar colour and/or texture.

28. A method as claimed in claim 16, in which in step (i) features relevant to the composition of the electronic image are identified by a process of:

segmenting the image into regions;

denoting certain regions as more salient than others;

grouping salient regions into larger regions separated by relatively non-salient regions;

identifying said groups of salient regions as features with a region of interest property.

29. A method as claimed in claim 28, in which the image is segmented into regions by segmenting the image into homogenous sub-areas, the measure of homogeneity being based on some combination of colour, intensity and texture.

30. A method as claimed in claim 28, in which certain regions are denoted as more salient than others by allocating high salience to regions on the basis of at least one of:

relative unusualness of at least one of the colour, intensity and texture of the region to other adjacent regions; and

/or

relative unusualness of at least one of the colour, intensity and texture of the region relative to a substantial portion of the image.

31. A method as claimed in claim 16, in which the compositional rule for features identified at the centre of the image is to include such features in the cropped image.

32. A method as claimed in claim 16, further comprising a step (0) prior to step (i) of determining, independently of capture of the electronic image, specific features or objects of interest, and wherein step (i) further comprises attempted identification of said specific features or objects of interest and designation of successfully identified specific features or objects of interest as features relevant to the composition of the electronic image.

33. A method as claimed in claim 32, wherein step (0) comprises identification of specific features or objects prior to capture of the electronic image.

34. A method as claimed in claim 32, wherein step (0) comprises provision of at least one identifier tag and of rules for identification of identifier tags, and wherein step (i) comprises use of said rules for identification of said identifier tags.

35. A method as claimed in claim 34, wherein said identifier tags are infra-red transmitters.

36. A method of cropping an electronic image, comprising the steps of:

i) processing the image to identify at least one distinct feature within the image,

ii) selecting at least two compositional rules relevant to the at least one feature, the compositional rules determining the possible inclusion and placement of the feature within a cropped version of the image;

iii) determining at least one minimum and at least one maximum crop boundary for a cropped version of the image in accordance with the selected compositional rules; and

iv) determining an appropriate crop boundary between the minimum and maximum crop boundary for the image, based on at least one of;

a) lowest brightness level as compared to adjacent regions, b) smallest color activity as compared to adjacent regions, and c) lowest saliency as compared to adjacent regions, the appropriate crop boundary corresponding to a particular column of the image, the adjacent regions corresponding to left and right columns of the image abutting the particular column.

37. A method as claimed in claim 36, in which the selected compositional rules are used to define a set of constraints, and then candidate crop boundaries are determined in accordance with the constraints.

38. A method as claimed in claim 37, in which the constraints are implemented as soft constraints, such that the degree of non compliance with each constraint is used to form a penalty measurement.

39. A method as claimed in claim 38, in which the crop with the lowest penalty associated therewith is selected for presentation to a user.

40. A method as claimed in claim 39, in which a user can impose their choices into the compositional rules.

41. A method as claimed in claim 36, wherein the minimum crop boundary for a respective crop candidate corresponds to a first rectangular region that encompasses a region in the electronic image that includes all of a particular contiguous feature, and the maximum crop boundary for the respective crop candidate corresponds to a second rectangular region that encompasses the first rectangular region and that abuts respective minimum crop limits of other crop candidates that correspond to adjacently positioned regions in the electronic image and that respectively include all of other particular contiguous features.