System and method for signature-based unsupervised clustering of data elements

• US 9,104,747 B2
• Filed: 07/18/2014
• Issued: 08/11/2015
• Est. Priority Date: 10/26/2005
• Status: Active Grant

• Current Assignee: Cortica Ltd.
• Original Assignee: Cortica Ltd.
• Inventors: Raichelgauz, Igal, Odinaev, Karina, Zeevi, Yehoshua Y.
• Primary Examiner(s): CHANG, LI WU
• Application Number:
  US14/334,903
• Publication Number:
  US 20140330828A1
• Time in Patent Office: 389 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/438 Presentation of query results
• CPC Class Codes: G06F 16/4393 Multimedia presentations, e.g. slide shows, multimedia albums
• CPC Class Codes: G06F 16/45 Clustering; Classification
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/483 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/487 using geographical or spatial information, e.g. location
• CPC Class Codes: G06F 16/51 : Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/683 : using metadata automatically derived from the content
• CPC Class Codes: G06F 16/685 : using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: G06F 16/739 : in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/783 : using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7834 : using audio features
• CPC Class Codes: G06F 16/7844 : using original textual content or text extracted from visual content or transcript of audio data
• CPC Class Codes: G06F 16/7847 : using low-level visual features of the video content
• CPC Class Codes: G06F 16/904 : Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/951 : Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 : Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9558 : Details of hyperlinks; Management of linked annotations
• CPC Class Codes: G06F 17/16 : Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 3/048 : Interaction techniques based on graphical user interfaces [GUI]
• CPC Class Codes: G06F 3/0484 : for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range
• CPC Class Codes: G06F 3/0488 : using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06F 40/134 : Hyperlinking
• CPC Class Codes: G06N 20/00 : Machine learning
• CPC Class Codes: G06N 3/045 : Combinations of networks
• CPC Class Codes: G06N 3/048 : Activation functions
• CPC Class Codes: G06N 3/063 : using electronic means
• CPC Class Codes: G06N 3/088 : Non-supervised learning, e.g. competitive learning
• CPC Class Codes: G06N 5/02 : Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/022 : Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/025 : Extracting rules from data
• CPC Class Codes: G06N 5/04 : Inference or reasoning models
• CPC Class Codes: G06N 7/01 : Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/0201 : Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0246 : Traffic
• CPC Class Codes: G06Q 30/0261 : based on user location
• CPC Class Codes: G06T 19/006 : Mixed reality object pose determination, tracking or camera calibration for mixed reality G06T7/00
• CPC Class Codes: G06V 10/764 : using classification, e.g. of video objects
• CPC Class Codes: G06V 20/40 : in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 20/46 : Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: G06V 20/48 : Matching video sequences
• CPC Class Codes: G06V 2201/10 : Recognition assisted with metadata
• CPC Class Codes: G06V 40/171 : Local features and components; Facial parts eye characteristics G06V40/18; Occluding parts, e.g. glasses; Geometrical relationships
• CPC Class Codes: G09B 19/0092 : Nutrition
• CPC Class Codes: G10L 15/26 : Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: G10L 15/32 : Multiple recognisers used in sequence or in parallel; Score combination systems therefor, e.g. voting systems
• CPC Class Codes: G10L 25/51 : for comparison or discrimination
• CPC Class Codes: H04H 20/103 : Transmitter-side switching
• CPC Class Codes: H04H 20/26 : Arrangements for switching distribution systems
• CPC Class Codes: H04H 20/93 : which locates resources of other pieces of information, e.g. URL [Uniform Resource Locator]
• CPC Class Codes: H04H 2201/90 : characterised by the use of signatures
• CPC Class Codes: H04H 60/33 : Arrangements for monitoring the users' behaviour or opinions
• CPC Class Codes: H04H 60/37 : for identifying segments of broadcast information, e.g. scenes or extracting programme ID
• CPC Class Codes: H04H 60/46 : for recognising users' preferences
• CPC Class Codes: H04H 60/49 : for identifying locations
• CPC Class Codes: H04H 60/56 : Arrangements characterised by components specially adapted for monitoring, identification or recognition covered by groups H04H60/29-H04H60/54
• CPC Class Codes: H04H 60/58 : of audio determination or detection of speech characteristics in general G10L25/00; speech recognition in general G10L15/00
• CPC Class Codes: H04H 60/59 : of video recognising characters or patterns in general G06F18/00, G06V20/00
• CPC Class Codes: H04H 60/66 : for using the result on distributors' side
• CPC Class Codes: H04H 60/71 : using meteorological information
• CPC Class Codes: H04L 51/18 : Commands or executable codes
• CPC Class Codes: H04L 51/42 : Mailbox-related aspects, e.g. synchronisation of mailboxes
• CPC Class Codes: H04L 65/75 : Media network packet handling
• CPC Class Codes: H04L 65/765 : intermediate
• CPC Class Codes: H04L 67/02 : based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/306 : User profiles
• CPC Class Codes: H04L 67/535 : Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/63 : Routing a service request depending on the request content or context
• CPC Class Codes: H04N 21/23418 : involving operations for analysing video streams, e.g. detecting features or characteristics television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 21/25891 : being end-user preferences retrieval of video data in a video database based on user preferences G06F16/739; arrangements for recognizing users' preferences H04H60/46; user profiles in network data switching protocols H04L67/306; processing of user preferences or user profiles in wireless networks H04W8/18
• CPC Class Codes: H04N 21/26603 : for automatically generating descriptors from content, e.g. when it is not made available by its provider, using content analysis techniques
• CPC Class Codes: H04N 21/2668 : Creating a channel for a dedicated end-user group, e.g. insertion of targeted commercials based on end-user profiles information retrieval from the Internet by querying with filtering and personalisation G06F16/9535; arrangements for replacing or switching information during the broadcast H04H20/10; push services over packet-switching network H04L12/1859; adaptation of message content in packet-switching networks H04L51/063
• CPC Class Codes: H04N 21/278 : Content descriptor database or directory service for end-user access details of content or meta data based information retrieval of video data in video databases G06F16/739
• CPC Class Codes: H04N 21/466 : Learning process for intelligent management, e.g. learning user preferences for recommending movies services using the results of monitoring in broadcast systems H04H60/61
• CPC Class Codes: H04N 21/8106 : involving special audio data, e.g. different tracks for different languages
• CPC Class Codes: H04N 7/17318 : Direct or substantially direct transmission and handling of requests
• CPC Class Codes: Y10S 707/99943 : Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99948 : Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and system for signature-based unsupervised clustering of data elements. The method comprises receiving a plurality of clusters; generating a triangular matrix respective of the clusters; generating a signature for each of the clusters; generating a match score between each of two different clusters; storing the match score in a cell of the triangular matrix corresponding to the two clusters; determining whether any of the match scores is above a predefined threshold value; clustering every two clusters that are determined to have a score above a predetermined threshold; and repeating the generation of a triangular matrix respective of the clusters until a single cluster is reached. The system comprises an interface; a processor; a memory for storing at least one cluster; and a memory coupled to the processor, the memory containing instructions that, when executed by the processor, configure the system to perform the steps of the method.

Claims

1. A computerized method for signature-based unsupervised clustering of data elements, comprising:

receiving a plurality of clusters, each cluster comprising at least a data element;

generating an upper triangular matrix respective of the clusters;

generating a signature for each of the clusters, wherein a signature is generated from multiple patches of a multimedia data element, wherein multiple patches are of random length and random position within the multimedia data element;

generating a match score between each of two different clusters;

storing the match score in a cell of the upper triangular matrix corresponding to the two clusters;

determining whether any of the match scores is above a predefined threshold value;

clustering every two clusters that are determined to have a score above a predetermined threshold; and

repeating the generation of an upper triangular matrix respective of the clusters until a single cluster is reached, wherein the clustering on the respective generated signatures creates clusters that include a collection of signatures respective of the multimedia data elements.

2. The computerized method of claim 1, further comprising:

determining whether a single cluster cannot be reached; and

stopping the generation of the upper triangular matrix upon determination that a single cluster cannot be reached.

3. The computerized method of claim 1, wherein a new threshold value is utilized for each iteration.

4. The computerized method of claim 3, wherein the clustering score is determined to be below the threshold value if two clusters of the previously generated clusters include at least one overlapping data element or if a multimedia data element is matched to itself.

5. The computerized method of claim 2, wherein the single cluster cannot be reached when no two multimedia data elements have a clustering score above the threshold value or when no two previously clustered elements have a clustering score above the threshold value.

6. The computerized method of claim 1, wherein each of the data elements is at least one of:

audio, image, video, a video frame, fragment of audio, fragment of image, fragment of video, a fragment of a video frame, and an image of a signal.

7. The computerized method of claim 6, wherein the image of a signal is at least one of:

a medical signal, a geophysical signal, a subsonic signal, a supersonic signal, an electromagnetic signal, and an infrared signal.

8. The computerized method of claim 1, wherein each signature is generated by a plurality of computational cores enabled to receive a plurality of multimedia data elements, each computational core having properties that are independent from properties of the other the computational cores.

9. The computerized method of claim 8, wherein each computational core generates a respective first signature element and a respective second signature element responsive to a data element, the first signature element being a robust signature.

10. The computerized method of claim 8, further comprising:

setting the properties of each of the plurality of computational cores to have at least some statistical independence from other of the plurality of computational cores, the properties being set independently of each other core.

11. A non-transitory computer readable medium containing instructions that, when executed, perform the method of claim 1.

13. The apparatus of claim 1, further comprising:

a signature generator configured to generate a signature for each of the clusters responsive to the at least one processing unit.

14. The apparatus of claim 13, wherein the signature generator further comprises:

a plurality of computational cores enabled to receive a plurality of multimedia data elements, each computational core having properties that are independent from properties of other of the computational cores.

15. The apparatus of claim 14, wherein each computational core generates a respective first signature element and a respective second signature element responsive to a data element, the first signature element being a robust signature.

16. The apparatus of claim 14, wherein the properties of each of the plurality of computational cores are set independently of each other core to have at least some statistical independence from other of the plurality of computational cores.

17. The apparatus of claim 14, wherein the apparatus is further configured to:

determine whether a single cluster cannot be reached; and

stop the generation of the new cluster upon determination that a single cluster cannot be reached.

18. The apparatus of claim 14, wherein a new threshold value is utilized at each iteration.

19. The apparatus of claim 14, wherein the clustering score is determined to be below the threshold if two clusters of the previously generated clusters include at least one overlapping multimedia data element or a multimedia data element is matched to itself.

20. The apparatus of claim 2, wherein the clustering score is determined to be below the threshold if two clusters of the previously generated clusters include at least one overlapping multimedia data element or a multimedia data element is matched to itself.

21. The apparatus of claim 16, wherein each of the data elements is at least one of:

audio, image, video, a video frame, fragment of audio, fragment of image, fragment of video, a fragment of a video frame, and an image of a signal.

22. The apparatus of claim 21, wherein the image of a signal is at least one of:

a medical signal, a geophysical signal, a subsonic signal, a supersonic signal, an electromagnetic signal, and an infrared signal.

12. An apparatus for performing unsupervised clustering of data elements, comprising:

an interface for allowing access to a plurality of data elements;

at least one processing unit;

a storage unit for storing at least one cluster of data elements; and

a memory coupled to the at least one processing unit, the memory containing instructions that, when executed by the at least one processing unit, configure the apparatus to;

receive a plurality of clusters, each cluster comprising a data element;

generate an upper triangular matrix respective of the clusters, the upper triangular matrix stored in the memory;

generate a signature for each of the clusters, wherein a signature is generated from multiple patches of a multimedia data element, wherein multiple patches are of random length and random position within the multimedia data element;

generate a match score between each of two different clusters;

store the match score in a cell of the upper triangular matrix corresponding to the two clusters of the match score;

determine whether any of the match scores is above a predefined threshold value;

cluster every two clusters that are determined to have a score above a predetermined threshold; and

repeat the generation of the upper triangular matrix respective of the clusters until a single cluster is reached, wherein the clustering on the respective generated signatures creates clusters that include a collection of signatures respective of the multimedia data elements.