DEVICE AND COMPUTERIZED METHOD FOR PICTURE BASED COMMUNICATION

• US 20170337191A1
• Filed: 01/26/2017
• Published: 11/23/2017
• Est. Priority Date: 08/14/2014
• Status: Active Grant

• Current Assignee: Avaz, Inc. (Invention Labs Engineering Products Pvt., Ltd.)
• Original Assignee: Avaz, Inc. (Invention Labs Engineering Products Pvt., Ltd.)
• Inventors: Narayanan, Ajit
• Granted Patent: US 10,140,292 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232
• CPC Class Codes: G06F 40/55 Rule-based translation
• CPC Class Codes: G06F 40/56 Natural language generation
• CPC Class Codes: G06F 40/58 Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation

Abstract

The embodiments herein achieve a picture based communication system. The system allows users option to select one or more pictures, and any associated attributes. The selection of one or more pictures, and any associated attributes is taken as input. The selected words and attributes are converted to a graph representation, and subsequently the graph representation is converted to a sentence in target language. The method further involves predicting new relations, words, and attributes for further selection by user.

Claims

1. A computerized method for picture based communication, the method comprising:

presenting, by a user interface module, picture words to a user on a screen of a device;

receiving, by said user interface module, at least one picture word selected by said user;

receiving, by said user interface module, one or more attributes of at least one picture word selected by said user;

constructing, by a graph generation module, at least one connected graph in semantic interlingua, wherein said at least one connected graph is made of words and relationships with said selected at least one picture word;

generating, by a sentence generation module, a sentence in at least one target language based on said at least one connected graph; and

communicating, by an output module, said sentence in said at least one target language to a party receiving said communication on said device in a mode as configured by the user, wherein said at least one target language is based on an input representing mode of communication received from said user.

2. The method of claim 1, wherein said method further comprising:

predicting, by a prediction module, relations, words and attributes based on said sentence, wherein the prediction comprising;

determining feasible attributes to a selected word from said sentence;

determining feasible relations to said selected word; and

determining feasible words for at least one relation from said feasible relations, wherein said predicted relations, words, and attributes are presented to the user for further selection to construct a sentence.

3. The method of claim 1, wherein generating, by said sentence generation module, said sentence in said at least one target language based on said at least one connected graph comprises:

generating a graph representation from said connected graph in said semantic interlingua using at least one graph rule applied by a rule engine;

generating separate tree representations for each node in said graph representation, wherein said tree representation is generated based on at least one graph-to-tree rule applied by said rule engine;

generating a cumulative tree representation based on said separate tree representations, wherein said separate tree representations are analyzed based on at least one graph to tree rule, and cumulative tree representation is analyzed by at least one tree rule, applied by said rule engine; and

transforming said cumulative tree representation into said sentence in said at least one target language, wherein said tree representation is transformed based on at least one sequence transformation rule applied by said rule engine.

4. The method of claim 3, wherein said graph representation comprises a plurality of graph nodes indicating at least one of a word sense with annotations, a set of attributes, a special identifier indicating a sub-graph, and a list of edges.

5. The method of claim 4, wherein each said graph node is associated with a dictionary entry, wherein said dictionary entry comprises at least one of root form of said word sense, morphological properties, parts of speech, semantic attributes, and framing structure.

6. The method of claim 3, wherein generating said graph representation from said connected graph in said semantic interlingua using at least one graph rule from the rule engine comprises:

enumerating all sub-graphs;

creating an empty graph for each said sub-graph;

converting each unique node of an edge of the connected graph into a corresponding unique node of the graph representation;

converting each node of an edge into a unique node when either endpoints are pronouns, wherein each said edge comprises at least two nodes;

creating a map for mapping node identifiers to each said node;

setting an entry point for each sub-graph; and

adding said edge as a relation to said two nodes.

7. The method of claim 3, wherein at least one of said word sense, annotations, set of attributes, special identifier indicating sub-graph, and list of edges associated with each said graph node in said graph representation defines a transformation of said graph node, wherein said graph node or graph structure is modified based on at least one graph rule.

8. The method of claim 7, wherein said graph rule comprises of a pattern that specifies that an attribute is one of, exactly one of, or a maximum of one of a given list of attributes.

9. The method of claim 7, wherein said graph rule comprises graph pattern, constraints on said pattern, and output operation.

10. The method of claim 3, wherein modifying said graph representation based on said analysis of said graph representation comprises:

traversing said graph representation node-by-node, wherein said graph representation is traversed from an entry node and proceeding outwards along edges;

selecting edges in said graph representation from among those which

create a cycle in the graph, or which cause an entry node to have at least one input edge,

cause a node that is not an entry node to have two or more input edges, and

cause a node to have more than one input edges of give type; and

forming said selected edges, breaking edges having a start node, an end node, and a relation.

11. The method of claim 10, wherein breaking an edge having a start node, an end node, and a relation comprises:

removing said relation from said graph representation;

duplicating said end node of said edge;

marking said duplicate node with a pronoun attribute or a relative clause attribute,

depending on whether the resulting graph is connected or a fragment;

connecting said duplicate node to said start node, wherein said edge is broken into said start node and said duplicate, and said end-node along with rest of said graph representation; and

determining whether resulting graph representation is one of connected and broken into two fragments by the edge-breaking.

12. The method of claim 3, wherein said separate tree representation comprises:

a tree structure representing a syntactic structure for each graph node, wherein said tree structure comprises a maximal projection node, at least one of an intermediate projection node, and a head node;

pointers to children nodes; and

properties for said tree representation.

13. The method of claim 3, wherein said separate tree representation comprises a trace pointer to another part, wherein said trace pointer to another part is represented by a trace maximal projection node.

14. The method of claim 3, wherein operations performed on said separate tree representation comprises at least one of initializing with a pattern, substitution of another separate tree representation, adjunction of another separate tree representation, detachment and movement of a sub-tree from one location to another using at least one movement rule, leaf traversal and application of a function to all the traversed leaves with accumulation of result of the function.

15. The method of claim 3, wherein said at least one graph to tree rule is defined using at least one of an edge pattern in said graph representation, two node patterns in said graph representation, an output pattern in said tree representation, and an output variable in said tree representation.

16. The method of claim 3, wherein said at least one graph to tree rule is applied by traversing said graph representation in an order of edge types, and checking each said edge against a list of patterns of all possible graph to tree rules.

17. The method of claim 3, wherein said graph to tree rules pairwise coalesce separate tree representations associated with each graph node in said graph representation to create said cumulative tree representation that comprise all the sub-trees in various substitution and adjunction positions.

18. The method of claim 3, wherein said cumulative tree is transformed by:

searching for a pattern in said cumulative tree representation, wherein said pattern is in a given chain within the tree representation, and which matches given constraints on the pattern; and

performing a tree transformation operation on said sentence.

19. The method of claim 18, wherein performing said tree transformation pattern operation on said sentence comprises at least one of:

performing no operation;

moving a node from one location to another location of said sub-tree; and

creating a new segment of the cumulative tree with given template.

20. The method of claim 14, wherein said at least one movement rule comprises pattern to find source of movement, pattern to find destination of movement, and operation to be performed if both source and destination patterns are found.

21. The method of claim 20, wherein operation to be performed on cumulative tree representation if both source and destination patterns are found is one of:

movement of sub-tree to a given vacant node;

movement of head to a given head node;

copying properties from one tree structure to another;

setting properties on given tree structure;

removal of sub-tree; and

changing the word of a sub-tree.

22. The method of claim 1, wherein transforming said cumulative tree representation into a sentence of said target language comprises:

generating a sequence of words representing said sentence based on said cumulative tree representation, wherein said sequence of words is generated by in-order traversal of the leaves of said cumulative tree representation; and

converting said sequence of words into a sentence of said target language using said at least one sequence transformation rule, wherein said sequence transformation rule operates on the sequence of words.

23. The method of claim 3, wherein said sequence transformation rule comprises pattern to search, and at least one output operation, wherein said pattern to search consists of a regular expression matching at least one element of the sequence, and wherein output operation is at least one of substitution of a word or set of words in the sequence by another word, deletion of a word or set of words in the sequence, addition of at least one word to the sequence, and rearrangement of words in the sequence.

24. A device for picture based communication, the device comprising:

a user interface module connected to said processing module for;

presenting picture words to a user on a screen of a device;

receiving at least one picture word selected by said user;

receiving at least one attribute of at least one picture word selected by said user;

a processing module comprising;

a graph generation module connected to said processing module for constructing at least one connected graph in semantic interlingua, wherein said at least one connected graph is made of words and relationships with said selected at least one picture word;

a sentence generation module for generating a sentence in at least one target language based on said at least one connected graph; and

an output module for communicating said sentence in said at least one target language to a party receiving said communication on said device in a mode as configured by the user, wherein said at least one target language is based on an input representing mode of communication received from said user.

25. The device of claim 24, wherein said apparatus further comprises a prediction module for:

predicting relations, words and attributes based on said sentence, wherein the prediction comprising;

determining feasible attributes to a selected word from said sentence,

determining feasible relations to said selected word, and determining feasible words for at least one relation from said feasible relations, wherein said predicted relations, words, and attributes are presented to the user for further selection to construct a sentence.

26. The device of claim 24, wherein generating said sentence from said at least one connected graph comprises:

generating a graph representation from said connected graph in said semantic interlingua using at least one graph rule applied by a rule engine;

generating separate tree representations for each node in said graph representation, wherein said tree representation is generated based on at least one graph-to-tree rule applied by said rule engine;

generating a cumulative tree representation based on said separate tree representations, wherein said separate tree representations are analyzed based on at least one graph to tree rule, and cumulative tree representation is analyzed by at least one tree rule, applied by said rule engine; and

transforming said cumulative tree representation into said sentence in said at least one target language, wherein said tree representation is transformed based on at least one sequence transformation rule applied by said rule engine.

27. The device of claim 26, wherein said graph representation comprises a plurality of graph nodes indicating at least one of a word sense with annotations, a set of attributes, a special identifier indicating a sub-graph, and a list of edges.

28. The device of claim 27, wherein each said graph node is associated with a dictionary entry, wherein said dictionary entry comprises at least one of root form of said word sense, morphological properties, parts of speech, semantic attributes, and framing structure.

29. The device of claim 26, wherein generating said graph representation from said connected graph in said semantic interlingua using at least one graph rule from the rule engine comprises:

enumerating all sub-graphs;

creating an empty graph for each said sub-graph;

converting each unique node of an edge of the connected graph into a corresponding unique node of the graph representation;

converting each node of an edge into a unique node when either endpoints are pronouns, wherein each said edge comprises at least two nodes;

creating a map for mapping node identifiers to each said node;

setting an entry point for each sub-graph; and

adding said edge as a relation to said two nodes.

30. The device of claim 26, wherein at least one of said word sense, annotations, set of attributes, special identifier indicating sub-graph, and list of edges associated with each said graph node in said graph representation defines a transformation of said graph node, wherein said graph node or graph structure is modified based on at least one graph rule.

31. The device of claim 30, wherein said graph rule comprises of a pattern that specifies that an attribute is one of, exactly one of, or a maximum of one of a given list of attributes.

32. The device of claim 30, wherein said graph rule comprises graph pattern, constraints on said pattern, and output operation.

33. The device of claim 26, wherein modifying said graph representation based on said analysis of said graph representation comprises:

traversing said graph representation node-by-node, wherein said graph representation is traversed from an entry node and proceeding outwards along edges;

selecting edges in said graph representation from among those which

create a cycle in the graph, or which cause an entry node to have at least one input edge,

cause a node that is not an entry node to have two or more input edges, and

cause a node to have more than one input edges of give type; and

forming said selected edges, breaking edges having a start node, an end node, and a relation.

34. The device of claim 33, wherein breaking an edge having a start node, an end node, and a relation comprises:

removing said relation from said graph representation;

duplicating said end node of said edge;

marking said duplicate node with a pronoun attribute or a relative clause attribute,

depending on whether the resulting graph is connected or a fragment;

connecting said duplicate node to said start node, wherein said edge is broken into said start node and said duplicate, and said end-node along with rest of said graph representation; and

determining whether resulting graph representation is one of connected and broken into two fragments by the edge-breaking.

35. The device of claim 26, wherein said separate tree representation comprises:

a tree structure representing a syntactic structure for each graph node, wherein said tree structure comprises a maximal projection node, at least one of an intermediate projection node, and a head node;

pointers to children nodes; and

properties for said tree representation.

36. The device of claim 26, wherein said separate tree representation comprises a trace pointer to another part, wherein said trace pointer to another part is represented by a trace maximal projection node.

37. The device of claim 26, wherein operations performed on said separate tree representation comprises at least one of initializing with a pattern, substitution of another separate tree representation, adjunction of another separate tree representation, detachment and movement of a sub-tree from one location to another using at least one movement rule, leaf traversal and application of a function to all the traversed leaves with accumulation of result of the function.

38. The device of claim 26, wherein said at least one graph to tree rule is defined using at least one of an edge pattern in said graph representation, two node patterns in said graph representation, an output pattern in said tree representation, and an output variable in said tree representation.

39. The device of claim 26, wherein said at least one graph to tree rule is applied by traversing said graph representation in an order of edge types, and checking each said edge against a list of patterns of all possible graph to tree rules.

40. The device of claim 26, wherein said graph to tree rules pairwise coalesce separate tree representations associated with each graph node in said graph representation to create said cumulative tree representation that comprise all the sub-trees in various substitution and adjunction positions.

41. The device of claim 26, wherein said cumulative tree is transformed by:

searching for a pattern in said cumulative tree representation, wherein said pattern is in a given chain within the tree representation, and which matches given constraints on the pattern; and

performing a tree transformation operation on said sentence.

42. The device of claim 41, wherein performing said tree transformation pattern operation on said sentence comprises at least one of:

performing no operation;

moving a node from one location to another location of said sub-tree; and

creating a new segment of the cumulative tree with given template.

43. The device of claim 37, wherein said at least one movement rule comprises pattern to find source of movement, pattern to find destination of movement, and operation to be performed if both source and destination patterns are found.

44. The device of claim 43, wherein operation to be performed on cumulative tree representation if both source and destination patterns are found is one of:

movement of sub-tree to a given vacant node;

movement of head to a given head node;

copying properties from one tree structure to another;

setting properties on given tree structure;

removal of sub-tree; and

changing the word of a sub-tree.

45. The device of claim 24, wherein transforming said cumulative tree representation into a sentence of said target language comprises:

generating a sequence of words representing said sentence based on said cumulative tree representation, wherein said sequence of words is generated by in-order traversal of the leaves of said cumulative tree representation; and

converting said sequence of words into a sentence of said target language using said at least one sequence transformation rule, wherein said sequence transformation rule operates on the sequence of words.

46. The device of claim 26, wherein said sequence transformation rule comprises pattern to search, and at least one output operation, wherein said pattern to search consists of a regular expression matching at least one element of the sequence, and wherein output operation is at least one of substitution of a word or set of words in the sequence by another word, deletion of a word or set of words in the sequence, addition of at least one word to the sequence, and rearrangement of words in the sequence.