Incremental image clustering

Patent metadata

Field	Value
Publication number	US-9239967-B2
Application number	US-201114234099-A
Country	US
Kind code	B2
Filing date	Jul 29, 2011
Priority date	Jul 29, 2011
Publication date	Jan 19, 2016
Grant date	Jan 19, 2016

Abstract

Methods, systems, and computer readable media with executable instructions, and/or logic are provided for incremental image clustering. An example method for incremental image clustering can include identifying, via a computing device, a number of candidate nodes from among evaluated leaf image cluster (LIC) nodes on an image cluster tree (ICT) based on a similarity between a feature of a new image and an average feature of each of the evaluated LIC nodes. The evaluated nodes include at least one node along each path from a root node to either a leaf node or a node having a similarity exceeding a first threshold. A most-similar node can be determined, via the computing device, from among the number of candidate nodes. The new image can be inserted to a node associated with the determined most-similar node, via the computing device.

First claim

What is claimed is:

1. A method for incremental image clustering, comprising:
identifying, via a computing device, a number of candidate nodes from among nodes in an image cluster tree (ICT) based on a similarity between a feature of a new image and an average feature of each of at least one node along each path from a root node to either (i) a leaf node or (ii) a node with the similarity exceeding a first threshold;
determining, via the computing device, a most-similar node from among the number of candidate nodes;
inserting, via the computing device, the new image or the feature of the new image to a node associated with the determined most-similar node based on (i) a comparison of a second threshold to the similarity between the feature of the new image and the average feature of the most-similar node, and (ii) whether the most-similar node is a leaf node.

2. The method of claim 1 , further comprising:
initiating a new leaf node containing the new image as a sibling of the root node when no candidate nodes are identified; and
initiating a new root node having child nodes being the root node and the new leaf node.

3. The method of claim 1 , further comprising splitting the determined most-similar node after inserting the new image when the resulting child nodes exceed a maximum branching threshold.

4. The method of claim 1 , further comprising updating at least one node on the ICT along a path from a root node to the most-similar node to include the feature of the new image and a number of child nodes after the new image is added.

5. The method of claim 1 , further comprising periodically re-clustering leaf nodes on the ICT having single images.

6. The method of claim 5 , wherein periodically re-clustering leaf nodes on the ICT having single images includes re-clustering leaf nodes on the ICT having single images at a time when no new image is available to be received.

7. The method of claim 5 , further comprising reassigning images from the nodes on the ICT having single images to a nearest leaf image cluster node.

8. The method of claim 1 , the feature of the new image is associated with a facial feature of a person in a photo.

9. The method of claim 1 , wherein the new image or the feature of the new image is inserted into the most-similar node when the most-similar node is a leaf node and the comparison exceeds the second threshold.

10. The method of claim 1 , wherein the new image or the feature of the new image is inserted as a sibling node of the most-similar node when the most-similar node is a leaf node and the comparison does not exceed the second threshold.

11. The method of claim 1 , wherein the new image or the feature of the new image is inserted as a child node to the most-similar node when the most-similar node is not a leaf node.

12. A method for incremental image clustering, comprising:
extracting a facial feature from a detected face of a person in a new image to be inserted into an image cluster tree (ICT);
determining an original feature vector of the facial feature;
reducing the original feature vector to a reduced feature vector of the facial feature, the reduced feature vector being the feature of the new image;
identifying, via a computing device, a number of candidate nodes from among nodes in the image cluster tree based on a similarity between the reduced feature vector and an average feature of each of at least one node along each path from a root node to either (i) a leaf node or (ii) a node with the similarity exceeding a first threshold;
determining, via the computing device, a most-similar node from among the number of candidate nodes; and
inserting, via the computing device, the reduced feature vector into a node associated with the determined most-similar node.

13. A non-transitory computer-readable medium having computer-readable instructions stored thereon, the computer-readable instructions comprising instructions that, if executed by one or more processors, cause the one or more processors to:
identify, via a computing device, a number of candidate nodes from among nodes in an image cluster tree (ICT) based on a similarity between a feature of a new image and an average feature of each of at least one node along each path from a root node to either (i) a leaf node or (ii) a node with the similarity exceeding a first threshold;
determine, via the computing device, a most-similar node from among the number of candidate nodes;
insert, via the computing device, the new image or the feature of the new image to a node associated with the determined most-similar node based on (i) a comparison of a second threshold to the similarity between the feature of the new image and the average feature of the most-similar node, and (ii) whether the most-similar node is a leaf node.

14. The non-transitory computer-readable medium of claim 13 , further having computer-readable instructions stored thereon that, if executed by one or more processors, cause the one or more processors to:
initiate a new leaf node containing the new image as a sibling of the root node when no candidate nodes are identified; and
initiate a new root node having child nodes being the root node and the new leaf node.

Assignees

• Liu ke-yan
• Sun xin-yun
• Zhang Tong
• Wang Lei
• Wang Min
• Hewlett Packard Development Co

Inventors

• Liu ke-yan
• Sun xin-yun
• Zhang Tong
• Wang Lei
• Wang Min

Classifications

• G06F18/23

  Clustering techniques · CPC title

• G06F16/583 Primary

  using metadata automatically derived from the content · CPC title

• G06F18/231

  Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram · CPC title

• G06K9/6219

  Physics · mapped topic

• G06K9/6218 Primary

  Physics · mapped topic