System and method for automatic layout of images in digital albums

• US 7,340,676 B2
• Filed: 12/29/2000
• Issued: 03/04/2008
• Est. Priority Date: 12/29/2000
• Status: Expired due to Fees

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Geigel, Joseph M., Loui, Alexander C.
• Primary Examiner(s): Lo; Weilun
• Assistant Examiner(s): TRAN, MYLINH T
• Application Number:
  US09/750,858
• Publication Number:
  US 20020122067A1
• Time in Patent Office: 2,622 Days
• Field of Search: 345/776, 345/804, 345/853, 345/854, 715/517, 715/716, 715/804, 715/854, 715/853, 715/732, 715/788, 715/815, 707/3
• US Class Current: 715/716
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06V 10/771 Feature selection, e.g. selecting representative features from a multi-dimensional feature space
• CPC Class Codes: H04N 1/00132 in a digital photofinishing system, i.e. a system where digital photographic images undergo typical photofinishing processing, e.g. printing ordering
• CPC Class Codes: H04N 1/00148 Storage information retrieval G06F16/00
• CPC Class Codes: H04N 1/00172 directly from a still digital camera or from a storage medium mounted in a still digital camera H04N1/0018 takes precedence
• CPC Class Codes: H04N 1/00175 from a still image storage medium H04N1/00172, H04N1/0018 take precedence
• CPC Class Codes: H04N 1/00196 Creation of a photo-montage, e.g. photoalbum H04N1/0019 takes precedence
• CPC Class Codes: H04N 1/387 Composing, repositioning or otherwise geometrically modifying originals
• CPC Class Codes: H04N 2201/3226 of identification information or the like, e.g. ID code, index, title, part of an image, reduced-size image
• CPC Class Codes: H04N 2201/3232 of a page, copy or picture number

Abstract

A system and method for automatic creation of digital image albums. A Page Creator Module utilizes a genetic engine and a layout evaluation module. The genetic engine evolves a group of images to a plurality of album pages, based on certain layout criteria. The evaluation module calculates layout criteria and compares them with user preferences. When an acceptable image/page layout has been generated, the image/page assignments are transferred to an Image Placement Module. The Image Placement Module utilizes a second genetic engine, which evolves various criteria to generate page layouts genetic structures. These structures define the location, scale, and rotation of images placed on a given page. A layout evaluation module calculates and compares these layouts with certain other preferences and page requirements. When a suitable layout has been generated, a final album output is generated, which may be displayed, printed, or otherwise transferred for subsequent utilization.

Claims

1. A digital image album layout system comprising:

a page creator module operable to receive a set of images, a plurality of different user album preferences, and a plurality of album preference importance values, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences, and to generate album preference criteria using said user album preferences and album preference importance values, said page creator module having a first genetic engine operable to execute genetic evolution calculations on a first genetic population of album criteria, said page creator module having a page evaluation module operable to test said first genetic population for fitness to said album preference criteria, said page creator module being operable to distribute said images to a plurality of album pages responsive to said testing for fitness to said album preference criteria;

an image placement module operable to receive the set of images, a plurality of different user page preferences, and a plurality of page preference importance values, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences, and to generate page preference criteria using said user page preferences and page preference importance values, said image placement module having a second genetic engine operable to execute genetic evolution calculations on a second genetic population of page layout criteria, said image placement module having a layout evaluation module operable to test said second genetic population for fitness to said page preference criteria, said image placement module being operable to distribute said images on respective said album pages responsive to said testing for fitness to said page preference criteria;

wherein said page creator module and said image placement module operate separately.

2. The system of claim 1, wherein the genetic evolution calculations performed by at least one of the first and second genetic engines include the application of a genetic mutation function.

3. The system of claim 1, wherein the genetic evolution calculations performed by at least one of the first and second genetic engines include the application of a genetic crossover function.

4. A system for assigning and placing a plurality of images on album pages, comprising:

means for receiving a plurality of user album preferences and a plurality of album preference importance values, said user album preferences indicating parameter values including at least one of balance, emphasis, chronology, and unity, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences,

means for specifying an initial set of page assignments of the images to a first genetic population;

a first genetic engine operable to evolve said first genetic population to produce a present set of image page assignments;

a page evaluation module operable to generate an album fitness function using said user album preferences and album preference importance values and to test said present set of image page assignments according to said album fitness function to determine an album score;

means for outputting said present set of image page assignments if said album score meets an album threshold value;

means for receiving a plurality of user page preferences and a plurality of page preference importance values, said user page preferences indicating parameter values including at least one of white space, overlap, rotation, spatial balance, rotational balance, border symmetry, and emphasis, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences,

means for specifying an initial set of placement parameters of the images to a second genetic population in accordance with said outputted set of image page assignments;

a second genetic engine operable to evolve said second genetic population to produce a present set of image placement parameters;

a layout evaluation module operable to generate a page fitness function using said user page preferences and page preference importance values and to test said present set of image placement parameters with a said page fitness function to determine a page score, and

means for outputting said image placement parameters if said page score meets a page threshold value.

5. A method of assigning a plurality of images, having image parameters, to one or more pages in an album, comprising the steps of:

receiving a plurality of different user album preferences and a plurality of album preference importance values, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences;

specifying an initial set of page assignments defining the album page assignment for each of the plurality of images;

initializing a genetic population by assigning said initial set of page assignments to genes within an album genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of page assignments within said album genome structure;

calculating a present set of page criteria according to said present set of page assignments, the image parameters, and a set of album page parameters;

generating an album fitness function using said user album preferences and album preference importance values;

testing said present set of page criteria according to said album fitness function to determine an album score;

repeating said evolving and calculating steps if said album score fails to meet an album threshold value, and

outputting image page assignments according to said present page assignment if said album score meets said album threshold value.

6. The method of claim 5 wherein said image parameters include an image event value, image chronology value, and image emphasis value.

7. The method of claim 5 wherein said genome structure is a tree structure.

8. The method of claim 5 wherein said genome structure is selected from one of a tree structure, an array structure, or a list structure.

9. The method of claim 5 wherein calculation of said page criteria includes calculation of an emphasis value range, a page count value, and a balance threshold value.

10. A method of assigning a plurality of images, having image parameters, to one or more pages in an album, comprising the steps of:

receiving a plurality of user album preferences and a plurality of album preference importance values, said user album preferences indicating parameter values including at least one of balance, emphasis, chronology, and unity, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences,

specifying an initial set of page assignments defining the album page assignment for each of the plurality of images;

initializing a genetic population by assigning said initial set of page assignments to genes within an album genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of page assignments within said album genome structure;

calculating a present set of page criteria according to said present set of page assignments, the image parameters, and a set of album page parameters;

generating an album fitness function using said user album preferences and album preference importance values;

testing said present set of page criteria according to said album fitness function to determine an album score;

repeating said evolving and calculating steps if said album score fails to meet an album threshold value, and

outputting image page assignments according to said present page assignment if said album score meets said album threshold value;

wherein said evolution step genetic function includes a genetic mutation function and a genetic crossover function.

11. A method of assigning a plurality of images, having image parameters, to one or more pages in an album, comprising the steps of:

receiving a plurality of different user album preferences and a plurality of album preference importance values, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences,

specifying an initial set of page assignments defining the album page assignment for each of the plurality of images;

initializing a genetic population by assigning said initial set of page assignments to genes within an album genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of page assignments within said album genome structure;

calculating a present set of page criteria according to said present set of page assignments, the image parameters, and a set of album page parameters;

generating an album fitness function using said user album preferences and album preference importance values;

testing said present set of page criteria according to an album fitness function to determine an album score;

repeating said evolving and calculating steps if said album score fails to meet an album threshold value, and

outputting image page assignments according to said present page assignment if said album score meets said album threshold value;

wherein said testing step further comprises the steps of;

comparing said present set of page criteria and respective said user album preferences to generate preliminary album scores and

scaling said preliminary album scores in accordance with respective said album preference importance values to produce a final album score.

12. The method of claim 11 wherein said page criteria include balance, emphasis, chronology, and unity.

13. A method of arranging one or more images, having image parameters, on an album page, comprising the steps of:

receiving a plurality of different user page preferences and a plurality of page preference importance values, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences,

specifying an initial set of positioning parameters for each of the one or more images;

initializing a genetic population by assigning said initial set of positioning parameters as genes in a page genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of positioning parameters within said page genome structure;

calculating a set of present layout criteria, according to said present set of positioning parameters, the image parameters, and a set of page layout parameters;

generating a page fitness function based upon said user page preferences and said page preference importance values;

testing said present set of layout criteria according to said page fitness function to determine a page score;

repeating said evolving and calculating steps if said page score fails to meet a page threshold value; and

outputting a page layout according to said present set of positioning parameters if said page score meets said page threshold value.

14. The method of claim 13 wherein said image parameters include an image emphasis value.

15. The method of claim 13 wherein said genome structure is an array.

16. The method of claim 13 wherein said genome structure is selected from one of a tree structure, an array structure or a list structure.

17. The method of claim 13 wherein calculation of said layout criteria includes calculation of at least one of white space area, image overlap, image rotation, spatial balance, rotational balance, border symmetry, and image emphasis values.

18. The method of claim 13 wherein said page criteria include at least one of page size, maximum image rotation, scaling range, white space range, overlap range, and border deviation.

19. A method of arranging one or more images, having image parameters, on an album page, comprising the steps of:

receiving a plurality of different user page preferences and a plurality of page preference importance values, said user page preferences indicating parameter values including at least one of white space, overlap, rotation, spatial balance, rotational balance, border symmetry, and emphasis, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences,

specifying an initial set of positioning parameters for each of the one or more images;

initializing a genetic population by assigning said initial set of positioning parameters as genes in a page genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of positioning parameters within said page genome structure;

calculating a set of present layout criteria, according to said present set of positioning parameters, the image parameters, and a set of page layout parameters;

generating a page fitness function based upon said user page preferences and said page preference importance values;

testing said present set of layout criteria according to a page fitness function to determine a page score;

repeating said evolving and calculating steps if said page score fails to meet a page threshold value; and

outputting a page layout according to said present set of positioning parameters if said page score meets said page threshold value;

wherein said evolution step genetic function includes a genetic mutation function and a genetic crossover function.

20. A method of arranging one or more images, having image parameters, on an album page, comprising the steps of:

receiving a plurality of different user page preferences and a plurality of page preference importance values, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences,

specifying an initial set of positioning parameters for each of the one or more images;

initializing a genetic population by assigning said initial set of positioning parameters as genes in a page genome structure;

evolving said genetic population in accordance with a genetic function to produce a present set of positioning parameters within said page genome structure;

calculating a set of present layout criteria, according to said present set of positioning parameters, the image parameters, and a set of page layout parameters;

generating a page fitness function based upon said user page preferences and said page preference importance values;

testing said present set of layout criteria according to said page fitness function to determine a page score;

repeating said evolving and calculating steps if said page score fails to meet a page threshold value; and

outputting a page layout according to said present set of positioning parameters if said page score meets said page threshold value;

wherein said testing step further comprises the steps of;

comparing said layout criteria to layout preference criteria and generating a preliminary page score and

scaling said preliminary page score in accordance with page importance parameters to produce a final page score.

21. The method of claim 20 wherein said layout preference criteria are based upon user preferences.

22. A method of assigning and placing a plurality of images on album pages, comprising the steps of:

receiving a plurality of different user album preferences and a plurality of album preference importance values, each said album preference importance value indicating a weighting of a corresponding one of said user album preferences relative to the other said user album preferences,

specifying an initial set of page assignments of the images to a first genetic population;

evolving said first genetic population to produce a present set of image page assignments;

generating an album fitness function based upon said user album preferences and said album preference importance values;

testing said present set of image page assignments according to said album fitness function to determine an album score;

outputting said present set of image page assignments if said album score meets an album threshold value;

receiving a plurality of different user page preferences, and a plurality of page preference importance values, each said page preference importance value indicating a weighting of a corresponding one of said user page preferences relative to the other said user page preferences,

specifying an initial set of placement parameters of the images to a second genetic population in accordance with said outputted set of image page assignments;

evolving said second genetic population to produce a present set of image placement parameters;

generating a page fitness function based upon said user page preferences and said page preference importance values;

testing said present set of image placement parameters with a page fitness function to determine a page score; and

outputting said image placement parameters if said page score meets a page threshold value;

wherein said evolving of said first genetic ponulation, said generating of said album fitness function, and said testing according to said album fitness function are senarate from said evolving of said second genetic population, said generating of said page fitness function, and said testing with said page fitness function.