System and method for image selection using multivariate time series analysis

• US 9,116,924 B2
• Filed: 01/14/2013
• Issued: 08/25/2015
• Est. Priority Date: 01/14/2013
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Marchesotti, Luca
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US13/740,442
• Publication Number:
  US 20140198986A1
• Time in Patent Office: 953 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries
• CPC Class Codes: G06V 20/35 Categorising the entire scene, e.g. birthday party or wedding scene

Abstract

An image selection method includes receiving a collection of images and optionally, filtering the collection of images. The filtering may include removing images that are near-duplicates of other images in the collection. A plurality of features is extracted from each of the images in the optionally-filtered collection. The optionally-filtered collection of images is considered as a time-ordered sequence of images and is segmented to form a sequence of segments. Each segment includes at least one of the images. The segmenting of the sequence of images is based on the extracted features and positions of the images in the sequence of images. Images from the segments are selected to form a sub-collection of the images.

Claims

1. An image selection method comprising:

receiving a collection of images;

optionally, filtering the collection of images, the filtering comprising removing images that are near-duplicates of other images in the collection;

extracting a plurality of features from each of the images in the optionally-filtered collection;

with a processor, considering the optionally-filtered collection of images as an ordered sequence of images and segmenting the sequence of images to form a sequence of segments, each segment comprising at least one image, the segmenting of the sequence of images being based on the extracted features and positions of the images in the sequence of images, the segmenting comprising fitting a step function to the image sequence, the fitting comprising minimizing an error, over all the images in the sequence of images, between normalized values of the features for each image and corresponding values of the step function, the step function being constrained to a maximum number of transition points, each transition point corresponding to a change between step function values; and

selecting images from the segments to form a sub-collection of the images.

2. The method of claim 1, wherein the segmenting of the sequence of images comprises optimizing an expression that minimizes the error while penalizing large differences between adjacent steps of the step function under a constraint which satisfies a maximum number of the transition points.

3. The method of claim 2, wherein the segmenting of the sequence of images is performed with Group Fused Lasso.

4. The method of claim 3, wherein the segmenting includes solving the expression:

5. The method of claim 1, wherein the feature extraction comprises normalizing the features to provide feature values in a common feature space for all features.

6. The method of claim 1, wherein at least one of the plurality of features is selected from the group consisting of:

temporal information;

geo-location information;

image content;

visual similarity;

photographic metadata;

and combinations thereof.

7. The method of claim 1, wherein the selecting images from the segments to form a sub-collection of the images comprises selecting a single image from each segment to form the sub-collection.

8. The method of claim 1, further comprising presenting the sub-collection of the images to a user for validation.

9. The method of claim 1, further comprising automatically flowing the sub-collection of the images into a sequence of placeholders in a digital document.

10. The method of claim 1, further comprising predefining defining a number of images to form the sub-collection and wherein the segmentation is also based on the predefined number.

11. The method of claim 1, wherein the method includes the filtering of the collection of images to remove images that are near-duplicates of other images in the collection.

12. The method of claim 11, wherein the filtering of the collection of images to remove images that are near-duplicates of other images in the collection comprises generating an image representation of each image and identifying similar images by at least one of static thresholding, dynamic thresholding, and non-linear classification.

13. The method of claim 1, wherein the selecting images from the segments to form a sub-collection of the images is performed with the processor.

14. A computer program product comprising a non-transitory recording medium storing instructions, which when executed on a computer, causes the computer to perform the method of claim 1.

15. A system comprising memory storing instructions for performing the method of claim 1 and a processor in communication with the memory for executing the instructions.

16. An image selection system comprising:

an optional filtering component for filtering an input collection of images, the filtering comprising removing images that are near-duplicates of other images in the collection;

a features extractor which extracts a plurality of features from images in the optionally-filtered collection;

a sequence segmentor which considers the optionally-filtered collection of images as a time-ordered sequence of images and which segments the sequence of images to form a sequence of segments, each segment comprising at least one image, the segmenting of the sequence of images being based on the extracted features and positions of the images in the sequence of images, the segmentation comprising identifying transition points in the sequence of images by optimizing a function which, over all images in the sequence, minimizes an error between normalized values of the features and a step function which is constrained to a maximum number of the transition points;

optionally, a representative image selector for selecting images from the segments to form a sub-collection of the images; and

a processor which implements at least the features extractor and sequence segmentor.

17. The image selection system of claim 16, further comprising and album generator which automatically flows the selected images into placeholders of a digital document.

18. The image selection system of claim 16, comprising the filtering component.

20. The method of claim 16, wherein the images are individual photographs.

21. The method of claim 20, further comprising filling an album template with photographs from the sub-collection.

19. An image selection method comprising:

receiving a collection of images;

filtering the collection of images, the filtering comprising removing images that are near-duplicates of other images in the collection;

extracting features from the images in the filtered collection; and

with a processor, considering the images as forming a time-ordered sequence and segmenting the sequence of images to form a sequence of segments, each segment comprising at least one image, the segmenting of the sequence of images being based on the extracted features, the segmentation comprising identifying transition points in the sequence of images by optimizing a function which, over all images in the sequence, minimizes an error between normalized values of the features and a step function which is constrained to a maximum number of the transition points; and

providing for selection of images from the segments to form a sub-collection of the images.