Dynamic clustering for adaptive prediction filters

• US 8,358,857 B2
• Filed: 10/03/2008
• Issued: 01/22/2013
• Est. Priority Date: 10/03/2008
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Demirci, Oguz, Paniconi, Marco
• Primary Examiner(s): Chawan, Sheela
• Application Number:
  US12/245,664
• Publication Number:
  US 20100086224A1
• Time in Patent Office: 1,572 Days
• Field of Search: 382/225, 382/276, 382/295, 382/305, 382/238, 382/224, 716/119, 716/118, 716/122, 716/123, 716/135, 716/124, 716/132, 716/154, 700/121, 706/12, 706/45, 706/921, 706/123, 706/52, 370/338, 370/344, 707/758, 707/741, 348/700, 345/589, 345/443, 455/447, 455/429, 455/446, 455/448, 455/426.1, 455/12.1, 375/232, 324/207.21, 324/252, 324/207.25, 313/407, 313/405, 313/404
• US Class Current: 382/225
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06V 10/776 Validation; Performance evaluation
• 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

Abstract

An initial value is assigned to a center point for each cluster in a plurality of clusters. Each point in a point space is assigned to a closest cluster based on the distance between the each point and the center of nearest cluster. A first-assignment value is determined for each center point using the clusters the points are assigned to. A first-assignment dynamic validity index of a current cluster configuration is evaluated. Each point in the point space is reassigned to the closest cluster based on the first-assignment value of each center. A second-assignment value is determined for the center of each cluster according to the reassigning. A second-assignment dynamic validity index is evaluated using the second-assignment values. The current cluster configuration is selected if the difference between the dynamic validity indices is less than a threshold.

Claims

1. A computerized method comprising:

assigning, by a processor, an initial value to a center point for each cluster in a plurality of clusters;

assigning each point in a point space to a closest cluster in the plurality of clusters based on the distance between each point and the center point of the closest cluster;

determining a first-assignment value for the center point for each cluster in the plurality of clusters using the assigning;

evaluating a first-assignment dynamic validity index of a current cluster configuration using the first-assignment values;

reassigning each point in the point space to the closest cluster based on the first-assignment value of each center;

determining a second-assignment value for the center for each cluster using the reassigning;

evaluating a second-assignment dynamic validity index of the current cluster configuration using the second-assignment values;

selecting the current cluster configuration if a difference between the first-assignment dynamic validity index and the second-assignment dynamic validity index is less than a threshold, wherein the current cluster configuration defines clusters of pixel classes.

2. The computerized method of claim 1, wherein each dynamic validity index is calculated from an intra-cluster term and an inter-cluster term, the intra-cluster term being an average distance of each point to its corresponding center point and the inter-cluster term being a distance between a pair of clusters that are closest to each other among all pairs of clusters.

3. The computerized method of claim 2, wherein the intra-cluster term is calculated as

4. A non-transitory computer-readable storage medium storing instructions which when executed by a data processing system cause the data processing system to perform operations that process data, the operations comprising:

assigning an initial value to a center point for each cluster in a plurality of clusters;

assigning each point in a point space to a closest cluster in the plurality of clusters based on the distance between each point and the center point of the closest cluster;

determining a first-assignment value for the center point for each cluster in the plurality of clusters using the assigning;

evaluating a first-assignment dynamic validity index of a current cluster configuration using the first-assignment values;

reassigning each point in the point space to the closest cluster based on the first-assignment value of each center;

determining a second-assignment value for the center for each cluster using the reassigning;

evaluating a second-assignment dynamic validity index of the current cluster configuration using the second-assignment values;

selecting the current cluster configuration if a difference between the first-assignment dynamic validity index and the second-assignment dynamic validity index is less than a threshold, wherein the current cluster configuration defines clusters of pixel classes.

5. The non-transitory computer-readable storage medium of claim 4, wherein each dynamic validity index is calculated from an intra-cluster term and an inter-cluster term, the intra-cluster term being an average distance of each point to its corresponding center point and the inter-cluster term being a distance between a pair of clusters that are closest to each other among all pairs of clusters.

6. The non-transitory computer-readable storage medium of claim 5, wherein the intra-cluster term is calculated as

7. A system comprising:

a processor coupled to a bus;

a memory coupled to the processor through the bus; and

instructions executed by the processor from the memory to cause the processor to

assigning an initial value to a center point for each cluster in a plurality of clusters;

assign each point in a point space to a closest cluster in the plurality of clusters based on the distance between each point and the center point of the closest cluster;

determine a first-assignment value for the center point for each cluster in the plurality of clusters using the assigning;

evaluate a first-assignment dynamic validity index of a current cluster configuration using the first-assignment values;

reassign each point in the point space to the closest cluster based on the first-assignment value of each center;

determine a second-assignment value for the center for each cluster using the reassigning;

evaluate a second-assignment dynamic validity index of the current cluster configuration using the second-assignment values;

select the current cluster configuration if a difference between the first-assignment dynamic validity index and the second-assignment dynamic validity index is less than a threshold, wherein the current cluster configuration defines clusters of pixel classes.

8. The system of claim 7, wherein each dynamic validity index is calculated from an intra-cluster term and an inter-cluster term, the intra-cluster term being an average distance of each point to its corresponding center point and the inter-cluster term being a distance between a pair of clusters that are closest to each other among all pairs of clusters.

9. The system of claim 8, wherein the intra-cluster term is calculated as

10. A data processing system comprising:

means for assigning an initial value to a center point for each cluster in a plurality of clusters;

means for assigning each point in a point space to a closest cluster in the plurality of clusters based on the distance between each point and the center point of the closest cluster;

means for determining a first-assignment value for the center point for each cluster in the plurality of clusters using the assigning;

means for evaluating a first-assignment dynamic validity index of a current cluster configuration using the first-assignment values;

means for reassigning each point in the point space to the closest cluster based on the first-assignment value of each center;

means for determining a second-assignment value for the center for each cluster using the reassigning;

means for evaluating a second-assignment dynamic validity index of the current cluster configuration using the second-assignment values;

means for selecting the current cluster configuration if a difference between the first-assignment dynamic validity index and the second-assignment dynamic validity index is less than a threshold, wherein the current cluster configuration defines clusters of pixel classes.