Patent Description:
It is the object of the present application to provide a computer-readable storage medium, an apparatus and a method that allow efficient cropping of digital images on mobile devices.

This object is solved by the subject matter of the independent claims <NUM>, <NUM> and <NUM>.

The explosion of digital image capture has also led to an explosion in the different usages of digital images. Aside from storing images in digital storage (e.g., on a hard-disk drive or a solid state drive) or network-based (cloud) storage, users may share images on social networks, place them in files, presentations, online, photo sharing services, and the like. Before these pictures are stored or utilized, many users will want to modify or adjust the settings of the pictures. For example, the brightness, contrast, zoom, and in some examples, cropping the image. Cropping an image is an image operation that removes a portion of the image (e.g., the outer portions) to improve framing, accentuate subject matter, or change aspect ratio. Such cropping may be useful to remove undesirable backgrounds, objects, people, or other things from the image.

These image modifications may be difficult to accomplish on a smartphone or other mobile device. For example, the limited screen real-estate and input options may make cropping manually cumbersome. Due to these frustrations, many users download the pictures to a desktop computer, and edit the digital image there using the larger display and easier input options (e.g., a mouse, keyboard, and the like). This slows down the time between capturing the image and making use of the image and provides an annoyance to the user.

Disclosed in some examples are methods, systems, computing devices, and machine readable mediums that provide for cropping systems that automatically crop digital images using one or more smart cropping techniques. Smart cropping techniques may include: cropping an image based upon emotion detection, cropping based upon facial recognition and matching, and cropping based upon landmark matching. In some examples, a single smart cropping technique may be utilized. In other examples, a combination of the smart cropping techniques may be utilized. The system utilizes the one or more smart cropping techniques to produce a proposed cropping region in the digital image. The proposed cropping region is the area of the image that will remain after the cropping operation. The computing device may then display the digital image with the proposed cropping region represented by lines (or curves) superimposed on the digital image. The user may then accept the proposed cropping region as-is or modify the proposed cropping region. User acceptance of the proposed cropping region without modifications may serve as positive reinforcement that may be utilized to refine the cropping system. User modification or rejection of the proposed cropping rectangle may serve as negative reinforcement that may be also utilized to refine one or more machine learning models. The methods and systems disclosed herein may operate on single images, or may be performed on multiple images in succession.

In some embodiments, the system crops the image based upon emotion detection of persons in the digital image. That is, the system detects one or more faces in the digital image, processes the faces to determine emotions expressed by those faces and then crops based upon the facial emotions. For example, the system may crop to (e.g., leave in the final image) all faces expressing the same (or similar) emotions. This may allow the system to differentiate between faces of a group of users that are together (e.g., posing for a photograph) vs. individuals who are simply passing by or who are otherwise not part of the group. Typically individuals posing together for a photo would display similar emotions (e.g., happiness, or other emotions).

Turning now to <FIG>, an example digital image <NUM> is shown according to some embodiments of the present disclosure. The system has detected faces <NUM>, <NUM>, <NUM>, and <NUM>. In some examples face detection may be accomplished using a genetic algorithm and an eigen-face technique. For example, possible human eye regions are detected by testing all the valley regions in a gray-level representation of the image. The genetic algorithm may then calculate candidate face regions (e.g., nose, mouth, and chin). Candidate face regions may be normalized and the fitness value of the candidates may be measured using a projection on the eigen-faces. Face candidates with a fitness value above a threshold may be selected.

Once faces are detected, they are processed to determine emotions. To determine emotions, the system utilizes a coding scheme such as the Facial Action Coding System (FACS) developed by Paul Ekman to code facial expressions and use those codes as input into a Bayesian network to determine emotions from the facial codes. Faces expressing similar emotions are clustered together. For example, a group of smiling persons may be clustered together, as a smile may be associated with happiness. The system then selects one or more of the clusters and outputs the locations of the detected faces within that cluster as areas of interest for determining a proposed cropping region. In some examples, the areas of interest are only the faces, but in other examples, the areas of interest may extend to include the body of the detected face. As noted, the proposed cropping region is a region of the original image that is the final output image. Thus, the system crops-to the proposed cropping region, deleting the image outside the cropping region and utilizing the cropping region as the new image. A controlle then produces the proposed cropping region based upon these areas of interest (and in some examples, areas of interest output by other techniques). The controller then crops to these regions of interest.

If more than one cluster of similar emotions are present, to select one or more of the clusters (wherein the faces in the clusters are the areas of interest identified by the smart cropping based upon emotion detection), various algorithms may be utilized. For example, the system may select the cluster that is closest to the center of the image. For example, in <FIG>, the system may cluster faces <NUM>-<NUM> into one group and face <NUM> into another group. In other examples, the cluster with the highest number of detected faces may be selected. In an embodiment that forms part of the present invention, a facial recognition matching algorithm may be utilized to select clusters. That is, the system determines a match between a face in a cluster of the digital image and stored images from an image library of the user. The algorithms used to achieve this are the same or similar as the algorithms utilized in the smart cropping using facial recognition matching discussed elsewhere in the present disclosure. The system may select all clusters including a face that match a face in a photo in a user's photo library (e.g., online or locally stored) or a face that matches a face in a photo posted by them to their social networking account or by their friends (i.e., connections) on their social networking accounts may be selected and used to determine the regions of interest.

In some examples, just the faces are returned as areas of interest, but in other examples, the entire person corresponding to the selected faces are included as areas of interest. This allows for wider shots. Whether the face or whether the entire body of the user is included may be a selectable option that the user may select.

In some examples, to determine areas of interest used to determine a cropping region a library of images or photos posted to a social networking service (either to the user's profile or to the profiles of the user's connections) may be used to recognize faces of people familiar to the user. Facial recognition techniques such as principal component analysis using eigen-faces, linear discriminant analysis, elastic bunch graph matching, hidden Markov models, and the like may be utilized. For example, the algorithm may identify facial features by extracting landmarks (e.g., size and shape of the eyes, position of the mouth, and shape of the jaw) from an image of the subject's face. These features may be utilized to search for other images in a library of images that have similar features.

The presence of a matching face in a library of pictures or posted to a social networking page or site corresponding to the user suggests that the user knows the person and would like that person in the final cropped image. In addition to a personal library of a user's pictures, the system may have a library of pictures of famous persons. Thus, if the user meets a famous person and takes a picture, the system may recognize the famous person as someone that should be included in the cropped photo.

As noted, the system may select one or more of the recognized faces for outputting as areas of interest. For example, in <FIG>, if the system determines that faces <NUM>-<NUM> are in previous pictures in the user's library, but not face <NUM>, the system may output the rectangles around the faces as areas of interest to a controller that may then determine the final proposed cropping rectangle (or other shape). In some examples, all faces that are recognized are returned as areas of interest, but in other examples, some recognized faces may be returned as areas of interest while others are ignored. For example, the facial recognition algorithm may have a confidence value that numerically represents the confidence that the algorithm has that the face in the digital image matches a face in a picture in the user's digital library or on social media. Faces with confidence scores above a predetermined threshold may be returned as areas of interest, whereas faces with confidence scores below the predetermined threshold may be ignored. In other examples, in cases where multiple faces are detected, other algorithms may be used to select from multiple recognized faces. For example, emotion detection may be applied to select recognized faces with similar emotions. In some examples, a predetermined number of recognized faces nearest the center of the image may be chosen.

As noted above, the areas of interest may be returned to a controller that may then determine a cropping region based upon the identified areas of interest. As with the emotion detection smart cropping, in some examples, just the faces are returned as areas of interest, but in other examples, the entire person corresponding to the selected faces are included as areas of interest. This allows for wider shots. Whether the face or whether the entire body of the user is included may be a selectable option that the user may change. While facial recognition matching was described, in other examples, an entire body may be matched and detected. For example, a person's body shape may be matched to a body shape of a person that is in a different picture in a picture library.

In addition to facial detection, the system may compare the digital image to a plurality of stored images of various famous landmarks. Example landmarks may include the Statute of Liberty, the Eiffel Tower, the Washington Monument, Lincoln Memorial, and more. The landmarks may be manmade, natural, or the like. In some examples, the system may utilize metadata about the image (e.g., geolocation) to determine likely landmarks. The system may select one of the recognized landmarks for outputting as areas of interest.

Methods may utilize machine learning. For example, photos may utilize multiple layers of clustering to first cluster images based on geolocation, then each geolocation cluster may be clustered based upon visual appearance. Each of these clusters may then be a model specific to a particular landmark. A new digital image may be compared to each of these models to determine the closest fit (e.g., using k-nearest neighbor). The algorithm may then assign the landmark to the image based upon determining that a confidence score is above a predetermined threshold. The bounding box for the landmark may be utilized as the area of interest.

For instances in which multiple landmarks may be present, the landmark detection may utilize all landmarks as areas of interest. In other examples, one or more of the landmarks may be selected. For example, landmarks nearest identified faces or nearest a group of faces displaying similar emotions, or the like.

The above methods may be utilized alone, or in combination. For example, as already mentioned, some methods may be utilized to refine the above methods and assist them in selecting from multiple options. In other examples, methods may be run separately and the areas of interest identified by each method may be utilized to create the proposed cropping region. In some examples, the proposed cropping region may include all the areas of interest identified by the various cropping techniques. In other examples, the areas of interest may have a corresponding confidence score that reflect a numerical indication of the confidence that the technique has that the area of interest is valid. Areas of interest with confidence scores above a predetermined threshold may be utilized to create the proposed cropping region. In other examples, the confidence scores may be multiplied by a weighting factor that reflects a perceived accuracy of the technique to produce a weighted score for that area of interest. The weighting factors may be predetermined or may be based upon a machine learned model (e.g., a regression model, a neural network) that learns and/or adjusts weightings for each of the techniques based upon user feedback. Multiple techniques may identify the same, or overlapping areas of interest. In some examples, the areas of interest are clustered based upon their proximity in the image. Each cluster's associated weighted scores are summed to produce a cluster score. The proposed cropping region may be the smallest rectangle that includes all clusters with scores above a predetermined threshold.

Turning now to <FIG> a diagram of a cropping system <NUM> is shown according to some examples of the present disclosure. Cropping system <NUM> may be implemented on one or more computing devices (e.g., a mobile device). The components of cropping system <NUM> shown in <FIG> may be implemented as software (e.g., software modules) or hardware (e.g., dedicated processing components). Cropping system <NUM> may include a controller <NUM>, and one or more cropping determiners that apply different cropping methods, such as facial recognition determiner <NUM>, emotion detection determiner <NUM>, and landmark detection determiner <NUM>. Cropping system <NUM> may interface with external systems, such as first image library <NUM>. First image library <NUM> may be a storage location on a computing device of the user (e.g., where the cropping system <NUM> is also running or a different system), a cloud storage system (e.g., a network based image storage system), and the like. The first image library <NUM> may be specific to a particular user or group of users - e.g., in contrast to image libraries that store images from unrelated or unaffiliated persons. Cropping system <NUM> may also interface with a social networking service <NUM>. Cropping system <NUM> may retrieve or scan pictures shared by the user, or by the user's connections for purposes of facial matching using the facial recognition determiner <NUM>. The cropping system <NUM> may provide for user privacy controls and may be permission based such that the cropping system <NUM> only accesses files and images with user consent. The cropping system <NUM> may also interface with a second image library <NUM> which may contain a library of images of landmarks that may be utilized by the landmark detection determiner <NUM> to determine if any landmarks are present in a digital image.

A digital image, such as digital image <NUM> is received by the controller <NUM>. The controller <NUM> may include a dispatcher <NUM>. Dispatcher <NUM> may send the digital image <NUM> to one, more than one, or all of the cropping determiners, such as facial recognition determiner <NUM>, emotion detection determiner <NUM>, landmark detection determiner <NUM>, and other cropping determiners that are not shown. In some examples, the cropping determiners may be plug-ins that may be added, removed, updated, or otherwise modified without having to change the code of the cropping system <NUM> other than to change or add the plug-in.

Cropping determiners may search for one or more areas of interest in the digital image and output those areas of interest back to the controller <NUM>. Combiner may receive the areas of interest from the various cropping determiners. In some examples, each cropping determiner may return one or more areas of interest. In some examples, areas of interest may include associated confidence levels that quantify how confident the cropping determiners are that the returned areas of interest are areas of interest to the user.

Combiner <NUM> may take these areas of interest and produce a proposed cropping region. The proposed cropping region may be a cropping area, such as a cropping rectangle, a cropping circle, or other area. This proposed cropping region, as previously explained, is the region of the image that is left after the cropping region. That is, regions of the image outside the cropping region are cropped out. For example, the combiner <NUM> may select one, multiple, or all of the areas of interest returned by the cropping determiners and crop such that these areas of interest are included in the proposed cropping region. In the process, the combiner <NUM> may crop-out (e.g., remove) one or more of the areas of interest that were not selected, and/or areas of the image that were not identified as areas of interest. In the present disclosure, the proposed cropping region refers to the area left in the image after the crop is completed (e.g., the image is cropped to the cropping region). In some examples, the combiner may select all the returned areas and determine a proposed cropping region that may include all the areas of interest. In some examples, the cropping region may be a rectangle that is a size that is of a minimum size (or within a predetermined amount of pixels to a minimum size) to encompass all the areas of interest. In some examples, the cropping region may be another shape that may encompass one or more of the areas of interest.

In other examples, the combiner <NUM> may not include all of the areas of interest and instead may select some, but not others. For example, the combiner <NUM> may utilize a weighting function that may weigh the confidence values of each area of interest returned by the cropping determiners to produce a score for each area of interest. Areas of interest that score above a predetermined threshold score may be included in the cropping region. Areas of interest that score below a predetermined threshold may not be considered in the determination of the cropping region. That is, they may end up in the cropping region by virtue of being in a location that is included as a result of determining the cropping area based upon other regions of interest, but those areas of interest are not used to determine the cropping region. The weights used may be machine-learned weights (e.g., using a regression algorithm). The weights may be trained using manually labelled example images. As an example method of determining a cropping region, the combiner may iterate through all the areas of interest to find the topmost, leftmost, rightmost, and bottommost points of interest and then set the cropping area to be a rectangle with a top, left, right, and bottom lines corresponding to these points.

Once a proposed cropping region is determined by combiner <NUM>, in some examples, the GUI <NUM> may output the image with the cropping region identified. The GUI may be displayed on a computing device of the user. In some examples, the computing device of the user may be a computing device executing the cropping system <NUM>, but in other examples, may be a different computing device. For example, the cropping system <NUM> may be a network-based service and the GUI may be sent by the cropping system <NUM> to a computing device of a user over a network. The user may then provide input <NUM> accepting, rejecting, or adjusting the cropping region. In some examples, the input <NUM> may be utilized to refine the machine learned weights of the combiner <NUM>, or machine learned algorithms that are used by the cropping determiners.

Cropper <NUM> applies the proposed cropping region (in some examples, as potentially modified by GUI <NUM> as a result of user input <NUM>) to crop the image such that the areas outside the cropped region of the digital image <NUM> are removed to produce cropped image <NUM>.

Turning now to <FIG>, a method <NUM> for automatically cropping an image is shown according to an embodiment of the present disclosure. Method <NUM> may be performed by a cropping system (e.g., cropping system <NUM>) that is instantiated by a computing device. At operation <NUM> the system receives a digital image. The digital image may be received over a network from another computing device, from another component or application on the computing device (e.g., from an image capture program or driver), from a storage location, or the like. At operation <NUM> the cropping system determines one or more areas of interest. For example, by applying one or more methods, such as facial recognition matching, emotion detection, and landmark detection to produce areas of interest. At operation <NUM> the system determines the cropping area based upon the areas of interest. For example, selecting one, more than one, or all of the areas of interest and determining a cropping rectangle that includes the selected areas of interest. In some examples, the cropping area is the smallest rectangle (or other geometric shape) that includes all the areas of interest.

At operation <NUM> the cropping system <NUM> may optionally present a graphical user interface (GUI) which may allow the user to make modifications to the cropping area. At operation <NUM> the cropping system <NUM> may optionally receive modifications, input indicating an acceptance of the cropping region, input indicating a rejection of the cropping region, or the like from the user. At operation <NUM>, the cropping system may crop to the cropping region (which may have been modified in some examples by the input received in operation <NUM>).

Turning now to <FIG>, a method <NUM> of cropping based upon emotion detection is shown according to some examples of the present disclosure. Method <NUM> may be an example of operation <NUM> from <FIG>. At operation <NUM> the system utilizes a face detection algorithm to detect faces in the digital image. For example, by utilizing genetic algorithms. At operation <NUM> the system detects emotions from the detected faces. For example, the system may employ the FACS to code facial expressions and then utilize a Bayesian network to determine the emotions based upon one or more of the FACS codings assigned to the facial expression. At operation <NUM> the system clusters the images based upon the emotions, and in some examples, based upon the location of the detected faces in the image. For example, similar emotions (as determined by a predetermined list of similar emotions) within a predetermined proximity of each other may be clustered into a group of faces.

At operation <NUM>, the system selects a cluster of faces. The selection may be based upon number - e.g., the system may select the cluster with the greatest number of faces, the selection may be based upon location in the image (e.g., faces in the center of the image), and the like. In some examples, more than one (or all) of the clusters may be selected. At operation <NUM> the faces of the selected cluster are returned as areas of interest that are utilized to determine a cropping region (e.g., such as at operation <NUM>).

Turning now to <FIG> a method <NUM> of cropping using facial recognition is shown according to some examples of the present disclosure. Method <NUM> may be an example of operation <NUM> from <FIG>. At operation <NUM> the faces in the received digital image are detected. This may be done utilizing a face detection algorithm such as a genetic algorithm. At operation <NUM> the system utilizes a face matching algorithm to determine whether a similar face appears in a digital image in the collection of digital images belonging to the user. As noted, facial recognition techniques may be utilized such as principal component analysis using eigen-faces, linear discriminant analysis, elastic bunch graph matching, hidden Markov models, and the like. For example, the algorithm may identify facial features by extracting landmarks (e.g., size and shape of the eyes, position of the mouth, and shape of the jaw) from an image of the subject's face. These features may be utilized to search for other images that have similar features. At operation <NUM> the system selects one, more than one, or all of the matching faces to return as areas of interest. For example, if a single face matches, that location of that face may be returned. If multiple faces match, multiple areas of interest may be returned that correspond to the matched faces. In some examples, the system may select one or more (but not all) of the matching faces to return.

Turning now to <FIG>, a method <NUM> of a landmark detection cropping algorithm is shown according to some examples of the present disclosure. Method <NUM> may be an example of operation <NUM> from <FIG>. At operation <NUM> the system may compare the image to stored images of landmarks to detect matches <NUM>. For example, the system may utilize a machine learning algorithm to determine if a landmark is present in the digital image. For example, a genetic algorithm, principal component analysis, linear discriminant analysis, elastic bunch graph matching, hidden Markov models, and the like. At operation <NUM> the system may select one, more than one, or all of the landmarks that are matched to return as areas of interest.

Turning now to <FIG>, a method <NUM> of combining multiple cropping methods to produce an automatic cropping is shown according to an embodiment of the present disclosure. Method <NUM> may be an example of operation <NUM> from <FIG>. At operation <NUM>, the cropping system dispatches the digital image to multiple cropping determiners (that apply different cropping methods to determine areas of interest in the image). For example, emotion detection and facial recognition matching, and, optionally, landmark detection, and the like. In other examples, the system may also dispatch the digital image to other cropping determiners not herein discussed. At operation <NUM> the cropping determiners return, and the cropping system may receives, areas of interest determined by each of the cropping determiners.

At operation <NUM>, the system determines regions of interest to utilize for determining a cropping region based upon the returned areas of interest. In some examples, the areas of interest received at operation <NUM> may be clustered based upon location - that is, areas of interest that are near each other may be clustered. Clusters that contain over a predetermined threshold of areas of interest, or the top predetermined number or percent of areas of interest may be selected. In other examples, the areas of interest may have a corresponding confidence score. The system may select areas of interest for inclusion in the cropping region based upon the confidence scores. For example, areas of interest that have corresponding confidence scores above a predetermined threshold may be selected. In some examples, the top predetermined number or percentage of areas of interest (as ranked by confidence score) may be selected. In some examples, the confidence scores may be multiplied by a weighting factor to produce a score for each area of interest. The weighting factors may be predetermined, may be determined based upon a machine learning algorithm, or the like.

<FIG> illustrates a block diagram of an example machine <NUM> upon which any one or more of the techniques (e.g., methodologies) discussed herein may perform. The machine <NUM> may be a personal computer (PC), a tablet PC, a set-top box (STB), a personal digital assistant (PDA), a mobile telephone, a smart phone, a web appliance, a network router, switch or bridge, or any machine capable of executing instructions (sequential or otherwise) that specify actions to be taken by that machine. For example, the machine <NUM> may be a computing device that may implement the cropping system <NUM>, social networking service <NUM>, first image library <NUM>, second image library <NUM>, and the methods of <FIG>.

The term "machine readable medium" may include any medium that is capable of storing, encoding, or carrying instructions for execution by the machine <NUM> and that cause the machine <NUM> to perform any one or more of the techniques of the present disclosure, or that is capable of storing, encoding or carrying data structures used by or associated with such instructions. Non-limiting machine readable medium examples may include solid-state memories, and optical and magnetic media. Specific examples of machine readable media may include: non-volatile memory, such as semiconductor memory devices (e.g., Electrically Programmable Read-Only Memory (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM)) and flash memory devices; magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; Random Access Memory (RAM); Solid State Drives (SSD); and CD-ROM and DVD-ROM disks. In some examples, machine readable media may include non-transitory machine readable media. In some examples, machine readable media may include machine readable media that is not a transitory propagating signal.

Claim 1:
A computer-readable storage medium including instructions, which when executed by a computer, cause the computer to perform operations comprising:
receiving (<NUM>) a digital image;
detecting (<NUM>) three or more faces (<NUM>, <NUM>, <NUM>, <NUM>) in the digital image; and
automatically cropping (<NUM>) the digital image to areas of interest;
characterized in that for each particular face in the three or more faces (<NUM>, <NUM>, <NUM>, <NUM>), determining (<NUM>) an emotion displayed by the particular face;
clustering (<NUM>) the three or more faces (<NUM>, <NUM>, <NUM>, <NUM>) into two or more clusters, each particular cluster comprising faces displaying emotions that are similar as determined by utilizing a coding scheme to code facial expressions and then determining emotions by inputting said facial expressions into a Bayesian network and that are within a predetermined proximity of each other;
selecting (<NUM>) a cluster of the two or more clusters by utilizing a facial recognition matching algorithm that determines a match between a face in the two or more clusters and stored images from an image storage of a user and outputting locations (<NUM>) of the detected faces within said selected cluster as the areas of interest.