Patent Publication Number: US-8121358-B2

Title: Method of grouping images by face

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to methods for grouping images by face, and more particularly, to a method of grouping images by face based on group photo information. 
     2. Description of the Prior Art 
     Digital photography has revolutionized both professional and consumer photography. Elimination of physical film in digital cameras makes photography more cost effective by reducing film and photo development costs. Further, hundreds or thousands of digital images captured by the digital camera may be stored in a single flash memory card, such as a CompactFlash (CF) card, a Secure Digital (SD) card, or a Memory Stick (MS) device. Thus, digital photography has increased the number of people taking digital pictures, and also increased the number of pictures taken by each person, leading to a massive increase in the number of digital images generated by users. 
     Due to this increased amount of digital images generated and stored by users of digital cameras, organization of the digital images in a way that makes it easy for the user to locate and view a desired image becomes necessary. For example, the digital images may be timestamped, such that the digital images may be organized by date, month, or year. The digital images may also be tagged by the user, though this requires an inconvenient amount of manual input by the user. 
     More recently, face extraction algorithms have been developed for extracting face pixels from digital images, and face recognition algorithms may be utilized for grouping of images by face. In other words, face pixels from one image may be compared with face pixels from another image to determine similarity between the face pixels from these two images. If the face pixels from both images are sufficiently similar, the face recognition algorithm may group the images together. This is illustrated in  FIG. 1 . As shown, eleven face regions may be grouped into a first group  100 , a second group  110 , and a third group  120 , respectively. Thus, the face recognition algorithm may determine who appears in the digital image, and multiple digital images may be linked by which people appear in the digital images. However, the face recognition algorithms used for comparing the face pixels of the multiple digital images often provide ambiguous results. In other words, even if the same person appears in two images, the algorithm may determine the same person is two different people if he/she is wearing a new set of glasses, or has put on make-up. 
     SUMMARY OF THE INVENTION 
     According to an embodiment of the present invention, a method of browsing face regions in digital images in a photo displaying system comprises detecting a plurality of face regions from a plurality of images, grouping the face regions into a plurality of clusters based on similarities of the face regions, determining a degree of connection between the clusters, modifying the degree of connection between the clusters according to a relationship of the face regions, and displaying the face regions according to the degree of connection between the clusters. 
     According to a second embodiment, a method of handling similar clusters comprises analyzing a plurality of images to generate a plurality of face regions, calculating facial similarity for each pair of face regions in the plurality of images, and grouping the plurality of face regions into a plurality of clusters based on the facial similarities. The clusters comprise a first cluster, a second cluster, and a third cluster. A first condition result is generated when a first face region of the first cluster appears with a third face region of the third cluster in a first image of the plurality of images, and a second face region of the second cluster appears with a fourth face region of the third cluster in a second image of the plurality of images. A second condition result is generated when degree of connection of the first cluster and the second cluster is greater than a connection threshold. 
     According to another embodiment, a photo displaying system comprises a detecting module, a grouping module, a social networking analyzing module, a modifying module, and a display. The detecting module is for detecting a plurality of face regions from a plurality of images. The grouping module is for grouping the face regions into a plurality of clusters based on a similarity of the face regions. The social networking analyzing module is for determining a degree of connection between the clusters according to the similarity between the face regions. The determining module is for modifying the degree of connection between the clusters based on a relationship between the clusters. And, the display is for outputting the face regions according to the degree of connection. 
     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a diagram illustrating grouping face regions into groups according to the prior art. 
         FIG. 2  is a diagram illustrating an example of identifying a first person and a second person in a first digital image and a second digital image. 
         FIG. 3  is a flowchart of a process for browsing face regions in digital images in a photo displaying system according to a first embodiment. 
         FIG. 4  is a diagram illustrating matching clusters based on group photo information according to a second embodiment. 
         FIG. 5  is a flowchart of a process for handling similar clusters according to the second embodiment. 
         FIG. 6  is a diagram illustrating displaying clusters according to the second embodiment. 
         FIG. 7A  is a diagram of a table linking face region, image, album, and cluster according to one embodiment. 
         FIG. 7B  is a diagram illustrating the face regions, images, and clusters of the table of  FIG. 7A . 
         FIG. 8  is a diagram of a photo displaying system according to one embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     Please refer to  FIG. 2  and  FIG. 3 .  FIG. 2  is a diagram illustrating an example of identifying a first person and a second person in a first digital image  200  and a second digital image  210  of a plurality of images according to a first embodiment.  FIG. 3  is a flowchart of a process  30  for browsing face regions in digital images in a photo displaying system according to the first embodiment. In the process  30  shown in  FIG. 3  and illustrated in  FIG. 2 , likelihood exists that people appearing in one group photo together tend to appearing in other group photos together. In other words, a person&#39;s group photo history may provide information that aids identification of other people in group photos with the person. 
     In  FIG. 2 , the first digital image  200  includes a first face region  201  and a second face region  202 . Likewise, the second digital image  210  includes a third face region  211  and a fourth face region  212 . Initially, the first face region  201 , the second face region  202 , the third face region  211 , and the fourth face region  212  may be detected from the plurality of images (Step  300 ). Each face region may be a copy of pixels determined by a face extraction algorithm to correspond to a face of a member of each digital image. The face regions may also be compressed, or shrunken, copies of the pixels. If the second face region  202  corresponding to the first person is very similar to the fourth face region  212 , it may be assumed that the fourth face region  212  also corresponds to the first person. Thus, the second face region  202  and the fourth face region  212  may be grouped into a cluster of a plurality of clusters, and likewise for each face region of the plurality of face regions (Step  302 ). Facial similarity may be calculated for each pair of face regions, such as the second face region  202  and the fourth face region  212 , by comparing features, such as eyes, nose, mouth, etc. of the pair of face regions. If the facial similarity is high, e.g. greater than a facial similarity threshold, then a match may be generated. Although the first face region  201  and the third face region  211  may only be somewhat similar, e.g. not similar enough to match the two face regions under normal conditions, because they appear in the first digital image  200  and the second digital image  210  with the second face region  202  and the fourth region  212 , which are very similar, probability that the first face region  201  and the third face region  211  correspond to the same cluster is greatly increased. 
     At this point, a degree of connection may be determined between the clusters (Step  304 ) and be modified according to a relationship for the face regions (Step  306 ). The degree of connection may be determined by selecting one of the similarities of the face regions. The relationship of the face regions may be created according to the face regions detected from the same image. In one embodiment, the relationship of a first face region and a second face region may be created if the first face region and the second face region are detected from the same image. Taking  FIG. 2  as an example, a relationship may be established between the first face region  201  and the second face region  202 , and a relationship may be established between the third face region  211  and the fourth region  212 . The degree of connection between the clusters may be determined as follows. First, the similarity for each pair of face regions could be calculated by comparing the characteristic vectors of the face regions in the grouping Step  302 . Furthermore, the degree of connection between the first cluster and the second cluster could be determined according to the similarity between one face region of the first cluster and one face region of the second cluster in Step  304 . For example, the similarity between the first cluster and the second cluster may be representative of the most similar pair of the face regions of the clusters, the least similar pair of the face regions of the clusters, or the average of all similarity of each pair of face regions of the clusters. In another embodiment, the similarity between the first cluster and the second cluster may be obtained by comparing the average characteristic values of the face regions in the first cluster with the average characteristic values of the face regions in the second cluster. In other words, the degree of connection between the clusters is determined according to the similarity between the first cluster and the second cluster in Step  304 . In order to optimize the degree of connection between the clusters, the degree of connection would be modified according to the relationship between the face regions in Step  306 . In the current embodiment, a first image comprising a first face region belonging to a first cluster and a second face region not belonging to the first cluster are identified. A second image comprising a third face region belonging to a second cluster and a fourth face region not belonging to the second cluster are also identified. If the second face region from the first image and the fourth face region from the second image are grouped into the same cluster, e.g. a third cluster, the degree of connection between the first cluster and the second cluster may be modified (Step  306 ), e.g. according to the determining result being true. For example, the degree of connection between the first cluster and the second cluster may be increased when the first face region and the second face region are grouped into the third cluster. In another embodiment, if the second face region from the first image is similar with the fourth face region from the second image, the degree of connection between the first cluster and the second cluster may be modified (Step  306 ), e.g. according to the determining result being true. In another embodiment, the degree of connection between the first cluster and the second cluster may be increased when the first face region and the third face region are similar. For example, if the similarity between the first face region and the third face region is determined to be greater than a threshold, the degree of connection between the first cluster and the second cluster may be modified accordingly. In another embodiment, if similarity between the face regions in the first cluster and the face regions in the second cluster is determined to be greater than a threshold, the degree of connection between the first cluster and the second cluster may be modified (Step  306 ). For example, the degree of connection between the first cluster and the second cluster may be increased when the similarity between the face regions in the first cluster and the second cluster is determined to be greater than the threshold. In another embodiment, if the degree of connection between the first cluster and the second cluster is greater than a connection threshold, the first cluster and the second cluster may be merged. 
     During browsing, the plurality of face regions may be displayed organized by the plurality of clusters. Thus, the face regions may be displayed according to the degree of connection between the clusters (Step  308 ). In one embodiment, the face regions may be displayed in descending order of the degree of connection between the clusters. For example, if the first cluster is very similar to the second cluster, and the first cluster is slightly similar to the third cluster, the face regions of the second cluster may be displayed before the face regions of the third cluster when browsing the first cluster. 
     Please refer to  FIG. 4  and  FIG. 5 .  FIG. 4  is a diagram illustrating matching clusters based on group photo information according to a second embodiment.  FIG. 5  is a flowchart of a process  50  for handling similar clusters according to the second embodiment. Initially, a plurality of digital images in a database are analyzed to generate a plurality of face regions (Step  500 ). Then, facial similarity is calculated for each pair of face regions in the plurality of digital images (Step  502 ). Based on the facial similarities, the face regions are grouped into a plurality of clusters (Step  504 ). For example, as shown in  FIG. 4 , eleven face regions may be grouped into a first cluster  400 , a second cluster  410 , and a third cluster  420  based on the facial similarities. 
     For any two clusters of the plurality of clusters, e.g. the first cluster  400  and the second cluster  410 , two conditions may be met. First, a first face region  401  of the first cluster  400  appears with a third face region  421  of the third cluster  420  in a first image  430 , and a second face region  411  of the second cluster  410  appears with a fourth face region  422  of the third cluster  420  in a second image  440  (Condition 1). Second, the first cluster  400  and the second cluster  410  are sufficiently similar (Condition 2). If a first condition result (Condition 1) and a second condition result (Condition 2) are both true (Step  506 ), the following actions may be taken: 
     Step  508 A: Merge the first cluster  400  and the second cluster  410 . 
     Step  508 B: Increase degree of connection between the first cluster  400  and the second cluster  410 . 
     Step  508 C: Decrease separation between the first cluster  400  and the second cluster  410  when displaying the first cluster  400  and the second cluster  410 . 
     In the above, degree of connection, which may be calculated to determine how similar any two clusters are to each other, may be incorporated as a condition for taking any of the three actions when the first face region  401  of the first cluster  400  appears with the third face region  421  of the third cluster  420  in the first image  430 , and the second face region  411  of the second cluster  410  appears with the fourth face region  422  of the third cluster  420  in the second image  440 . 
     Furthermore, a connection threshold may be set for comparing the degree of connection with the connection threshold to determine whether the degree of connection meets Condition 2. For example, if the degree of connection for the first cluster  400  and the second cluster  410  is greater than or equal to the connection threshold, Condition 2 is met, and the first cluster  400  and the second cluster  410  may be merged, e.g. by merging the second cluster  410  into the first cluster  400  or vise versa, or by generating a new cluster comprising the respective face regions of the first cluster  400  and the second cluster  410  (Step  508 A). The degree of connection between the first cluster  400  and the second cluster  410  may also be increased in response to meeting Condition 1 and Condition 2 (Step  508 B). And, the first cluster  400  and the second cluster  410  may be displayed in closer proximity (Step  508 C). In the current embodiment, the displaying of the clusters will be refreshed in response to the degree of connection. In other words, the visual separation between the first cluster and the second cluster is decreased while the degree of connection between the first cluster and the second cluster is increased. In one embodiment, the plurality of clusters may be displayed in descending order of degrees of connections between the first cluster and each of the plurality of clusters. Though initially one or more intervening clusters may separate the first cluster  400  and the second cluster  410  during display. By sorting based on the degree of connection, the second cluster  410  may be displayed closer to the first cluster  400  than any of the intervening clusters if the degree of connection between the first cluster  400  and the second cluster  410  is higher than that between the first cluster  400  and any intervening cluster. In other words, the second cluster  410  may move up in line, being displayed more closely following the first cluster  400  than the initial intervening clusters. 
     Again, taking the first cluster  400  and the second cluster  410  as an example, if a fifth face region  402  of the first cluster  400  is very similar with a sixth face region  412  of the second cluster  410 , and if the first cluster  400  has a sufficiently high degree of connection with the second cluster  410 , a number of actions may be taken. First, the first cluster  400  and the second cluster  410  may be merged. The degree of connection for the first cluster  400  and the second cluster  410  may be increased. And, when displaying the first cluster  400  and the second cluster  410 , the first cluster  400  and the second cluster  410  may be displayed in closer proximity. 
     From another perspective, all face regions appearing in group photos with the face regions of the first cluster  400  may be analyzed, and all face regions appearing in group photos with the face regions of the second cluster  410  may be analyzed. One face region appearing in a group photo with a face region of the first cluster  400  may have very high facial similarity with another face region appearing in a group photo with a face region of the second cluster  410 . In this situation, a degree of connection between the first cluster  400  and the second cluster  410  correspond to the same person may be increased (Step  508 B). For example, the third face region  421  of the first cluster  400  and the fourth face region  422  of the second cluster  410  may be highly similar. Thus, the degree of connection between the first cluster  400  and the second cluster  410  may be increased. Likewise, if the third face region  421  and the fourth face region  422  are assigned to the same group, e.g. the third cluster  420 , the degree of connection may be increased. Then, if the degree of connection of the first cluster  400  and the second cluster  410  is sufficiently high, and if the degree of connection is greater than a threshold, the first cluster  400  and the second cluster  410  may be merged. Finally, during display, the first cluster  400  and the second cluster  410  may be pulled closer together by a distance or number of clusters proportional to the degree of connection. 
     Please refer to  FIG. 6 , which is a diagram illustrating display of face groups based on the above embodiments. When a user is organizing or browsing photos, the user may initially select a first cluster  610 , so as to browse all images in which a person P 1  appears. Then, in a browser window, the first cluster  610 , a second cluster  620 , a third cluster  630 , a fourth cluster  640 , a fifth cluster  650 , and a sixth cluster  660  may be displayed. The first cluster  610  and the second cluster  620  may already be identified as corresponding to the person P 1  based on degree of connection, and form a first category  61 . The third, fourth, and fifth clusters  630 ,  640 ,  650  may initially be grouped together into a second category  62  based on lower degree of connection with the first cluster  610 , and likewise the sixth cluster  660  may form a third category  63 . The first category  61  may be for face groups having degree of connection with the first cluster  610  above a first threshold, the second category  62  may be for face groups having degree of connection with the first cluster  610  above a second threshold, and so on. Of course, it is not necessary to categorize the clusters  610 ,  620 ,  630 ,  640 ,  650 ,  660  into the first category  61 , the second category  62 , and the third category  63 . The clusters  620 ,  630 ,  640 ,  650 ,  660  may also be displayed below the first cluster  610  in order of decreasing degree of connection with the first cluster  610 . 
     At this point, the user may easily label the first category  61  with name of the person P 1 , thereby applying the name to both the first cluster  610  and the second cluster  620 . Then, if the user determines that the fourth cluster  640  also contains face regions corresponding to the person P 1 , the user may group the fourth cluster  640  with the first and second clusters  610 ,  620  by labeling the fourth cluster  640  with the name of the person P 1 . 
     Please refer to  FIG. 7A  and  FIG. 7B .  FIG. 7A  is a diagram of a table  7  linking face region, image (index), album (path), and cluster according to one embodiment.  FIG. 7B  is a diagram illustrating the face regions, images, and clusters of the table  7 . The table  7  includes a face region field  700 , an image field  710 , an album field  720 , and a cluster field  730 . Rows  70 - 79  of the table store information linking each face region to an image, an album, and a cluster. The cluster could be obtained according to the previous methods of the current invention. For example, there are three Images, i.e. Image A, Image B and Image D, from Album I, and one image, Image C, from Album II. In cooperation with the method shown in the first embodiment, the face regions R 1  and R 2  are extracted from Image A, the face regions R 3  and R 4  are extracted from Image B, face regions R 5 , R 6  and R 7  are extracted from Image C, and face regions R 8 , R 9  and R 10  are extracted from Image D after executing the detecting step  200  shown in  FIG. 3 . After executing the grouping step  202  shown in  FIG. 3 , the face regions R 1 , R 3  are grouped into the same cluster “Person A” because the face region R 1  is similar to the face region R 3 . Similarly, the face regions R 2 , R 5  are grouped into the cluster “Person B”, the face regions R 4 , R 8  are grouped into the cluster “Person C”, the face regions R 6 , R 9  are grouped into the cluster “Person D”, and the face regions R 7 , R 10  are grouped into the cluster “Person E” based on the similarities of the face regions R 1 -R 10 . The degrees of connection between the clusters are determined based on the similarity analysis on the face regions in Step  304  shown in  FIG. 3 . In Step  306  shown in  FIG. 3 , a relationship between the cluster “Person B” and the cluster “Person C” is determined from the social information of the group photos. Because specific groups of people, such as friends, classmates, or family members, will take photos together, the face regions from the cluster “Person B” and the cluster “Person C” are from photos with the other face regions that are grouped in the common clusters. More particularly, the face regions from the clusters “Person B” and “Person A” appear in the same Image A, and the face regions from the clusters “Person C” and “Person A” appear in the same Image B. Although the clusters “Person B” and “Person C” are not identified as the same cluster in the previous analysis, the social information obtained from the group photos infer that the cluster “Person B” and the cluster “Person C” represent the same person. In Step  306  shown in  FIG. 3 , the degree of connection between any two clusters is modified according to the relationship of the face regions. Similarly, the face regions from the cluster “Person B”, “Person D” and “Person E” appear in the same Image C, and the face regions from the clusters “Person C”, “Person D” and “Person E” appear in the same Image D. Higher number of common faces in two clusters represents a higher degree of connection. Higher number of common persons from the same images, e.g. the face region R 6  and the face region R 7  are from the same Image C, may also represent higher degree of connection. In other words, the probability of the two clusters representing the same person is increased. Similarly, if faces of common clusters are from the same album, this may also represent higher degree of connection. Although the characteristics of persons would be changed as time passes, the cluster “Person B” and “Person C” are not identified as the same person according to the similarities of the face regions. However, the embodiment of current invention will improve the clustering result according to the social information of the group photos. 
     Please refer to  FIG. 8 , which is a diagram of a photo displaying system  80  according to one embodiment. The photo displaying system  80  comprises a detecting module  800 , a modifying module  810 , a grouping module  820 , a social networking analyzing module  830 , a display  840 , and a cluster merging module  850 . The respective modules of the photo displaying system  80  may be implemented as software codes executable in an x86 computer platform, or as the logic modules in an FPGA, ASIC, or other kind of hardware to perform the respective method disclosed by the current invention. In the embodiment according to the current invention, the detecting module  800  may detect a plurality of face regions from a plurality of images. The grouping module  810  may group the face regions into a plurality of clusters based on similarity of the face regions. The social networking analyzing module  820  is for determining the degree of connection between the clusters according to the similarity between the face regions. The modifying module  830  may modify the degree of connection between the clusters based on the relationship of the clusters. The display  840  outputs the face regions according to the degree of connection. An identifying module  860  may identify a first image and a second image from the images. The first image comprises a first face region belonging to a first cluster and a second face region not belonging to the first cluster. The second image comprises a third face region belonging to a second cluster and a fourth face region not belonging to the second cluster. The modifying module  830  may modify the degree of connection between the first cluster and the second cluster if the second face region and the fourth face region are grouped into the same cluster. The modifying module  830  may also modify the degree of connection between the first cluster and the second cluster if the second face region is similar to the fourth face region. The modifying module  830  may increase the degree of connection between the first cluster and the second cluster if the second face region is similar to the fourth face region. The modifying module  830  may also modify the degree of connection between the first cluster and the second cluster if the similarity between the first face region and the third face region is greater than a similarity threshold. The cluster merging module  850  is for merging a first cluster and a second cluster of the plurality of clusters when the degree of connection between the first cluster and the second cluster is greater than a connection threshold. 
     By utilizing group photo history to increase the odds of correctly grouping multiple face regions of multiple digital images, the embodiments of the present invention reduce the likelihood that two different people will be assigned to the same cluster, and that the same person will be assigned to two or more different clusters. 
     Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention.