Back to results
US 8,947,436 B2Granted
Method, apparatus and system for dense graph simplification, and recording medium for the same
AssigneeKorea Advanced Institute of Science and Technology
InventorsJunyong Noh, Yeongho Seol, Jaewoo Seo
Life of this patent
Estimating the term…
Abstract
Provided are a method, an apparatus and a system for dense graph simplification, and a recording medium for the same. The method includes receiving an original graph and extracting a plurality of salient points, which minimize a cost representing a greatest vertical distance between the original graph and each of a plurality of lines connecting two data points in a designated region on the original graph; and outputting a simplified graph in which the extracted salient points are connected. Thus, optimal results are ensured in dense graph simplification, and interactive control is allowed for a user.
Claims18
A method for dense graph simplification, comprising:
- receiving an original graph and extracting a plurality of salient points using a salient point extracting unit to minimize a cost representing a greatest vertical distance between the original graph and each of a plurality of lines connecting two data points in a designated region on the original graph by applying dynamic programming;
- outputting a simplified graph in which the extracted salient points are connected in a designated manner and a tangent is adjusted by a tangent adjusting unit;
- wherein said extracting the plurality of salient points includes:
- receiving the original graph;
- calculating, for all data points in the designated region on the original graph, the cost corresponding to a plurality of lines going to a plurality of other points located in a forward direction and the salient point corresponding to the cost, and storing the cost and the salient point in a 2-point path lookup table;
- and
- selecting the salient point corresponding to the respective cost, if the calculated cost is smaller than or equal to a designated cost threshold;
- and
- wherein said selecting the salient point includes:
- selecting the salient point corresponding to the respective cost, if the calculate cost is smaller than or equal to a designated cost threshold;
- determining whether the number of calculated salient points is greater than or equal to a designated number, if the calculated cost is greater than the designated cost threshold;
- selecting the calculated salient points, if the calculated number of the salient points is greater than or equal to the designated number;
- and
- returning to said storing the cost and the salient point in the 2-point path lookup table, if the number of the calculated salient points is smaller than the designated number.
11 more elements
An apparatus for dense graph simplification, comprising:
- a salient point extractor for receiving an original graph and extracting a plurality of salient points to minimize a cost representing a greatest vertical distance between the original graph and each of a plurality of lines connecting two data points in a designated region on the original graph by applying dynamic programming;
- and
- a tangent adjuster for outputting a simplified graph in which the extracted salient points are connected in a designated manner and a tangent is adjusted;
- wherein said extracting the plurality of salient points includes:
- receiving the original graph;
- calculating, for all data points in the designated region on the original graph, the cost corresponding to a plurality of lines going to a plurality of other points located in a forward direction and the salient point corresponding to the cost, and storing the cost and the salient point in a 2-point path lookup table;
- and
- selecting the salient point corresponding to the respective cost, if the calculated cost is smaller than or equal to a designated cost threshold;
- and
- wherein said selecting the salient point includes:
- selecting the salient point corresponding to the respective cost, if the calculate cost is smaller than or equal to a designated cost threshold;
- determining whether the number of calculated salient points is greater than or equal to a designated number, if the calculated cost is greater than the designated cost threshold;
- selecting the calculated salient points, if the calculated number of the salient points is greater than or equal to the designated number;
- and
- returning to said storing the cost and the salient point in the 2-point path lookup table, if the number of the calculated salient points is smaller than the designated number.
12 more elements
Dependencies are inferred from the claim text.