Browse Prior Art Database

Automatic diagram clustering and search for user sketch query

IP.com Disclosure Number: IPCOM000233547D
Publication Date: 2013-Dec-12
Document File: 5 page(s) / 94K

Publishing Venue

The IP.com Prior Art Database

Abstract

The invention provides a novel method & apparatus to automatically fill the initial/ uncompleted / sketched diagrams. It is a breakthrough as no existing work has enable such sketch based diagram completion function, which will release the huge labor. Compared with text based search and recommendation, can achieve more accurate relevance. The first step of the invention is transforming the diagram into a graph representation. Then, having build the set of graphs from raw ppt diagram, clustering is performed to enhance search efficiency. To efficiently find the structural similar diagram, the clustering shall be firstly based on the structural aspect, leaving the appearance to the sub layer. In the second layer, we shall capture more style level topic. While pure appearacnce based clustering cannot capture such semantic meaning. While it is not difficult to collect some diagrams tagged with explict style information. E.g. a ppt from a counsulting company may be a good labeled sample as business formal. Such labeled samples serve as the seeds in the 'super' graph for propogating their label to other nodes (diagram graphs) in a super-graph where each node is a graph and the graph simialrity can be measured by pairwise graph matching.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 78% of the total text.

Page 01 of 5

Automatic diagram clustering and search for user sketch query

A


A. . Diagram feature extraction module


1. Component-wise feature -> node features in the graph


1.1 Appearance: color, transparency, texture, shape, rotation, size


1.2 Layout: position in the chart


1.3 Type: textbox, image, comment text, etc


2. Component-to-component relational feature -> edge features in the graph


2.1 layout relation: connect line distance (between two part centers , and between the boundaries ); connect line direction, which can be further vectorized to e.g. 8 intervals: 0,45,90,135,180,225,270,315,360; explicit connection mark : (left/right/double) arrow, comment arrow etc


2.2 geometric relation: the size ratio of the two parts (homothetic); the shape consistency of the two parts


2.3 appearance relation: pairwise color similarity ; transparency similarity; texture similarity (if have)

B


B.

 . Graph converting module
the features can form a vector each dimension denotes an aspect of the similarity . Note the similarity is node -to-node and edge-to-edge

1



Page 02 of 5

C


C. . Structure driven clustering module
use the structrual/layout features excluding appearance features to perform clustering among the graphs to build indexs for various structures

2



Page 03 of 5

D


D. . Style driven clustering in the second layer


1. given a hand of taged diagram with explicit mark : business formal, entertainment, for children, etc


2. we treat is as a label proporgation problem , label the unknown dia...