Lattice encoding

• US 20060143009A1
• Filed: 10/10/2003
• Published: 06/29/2006
• Est. Priority Date: 10/15/2002
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Cacon Kabushiki Kaisha
• Inventors: Jost, Uwe Helmut, Atkinson, Michael Richard
• Granted Patent: US 7,430,509 B2
• Time in Patent Office: Days
• US Class Current: 704/254
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/285 Memory allocation or algorithm optimisation to reduce hardware requirements

Abstract

Initially an embedding module (22) determines an embedding of a lattice in a two-dimensional plane. The embedding module (22) then processes the initial embedding to generate a planar graph in which no links cross. The planar graph is then simplified by a link encoding module (24) and data representing the lattice structure is generated by a shape encoding module (26)—in which the simplified planar graph is represented by a shape encoding (42) identifying the numbers of links bounding areas defined by the planar graph and data identifying the locations of those areas within the planar graph; and a link list (43) identifying the modifications made to the lattice structure by the link encoding module (24). These encodings are such that the same substructures within a lattice are represented using the same data and hence are suitable for compression using conventional techniques.

Claims

1. A method of generating recognition data, comprising:

receiving lattice data defining a lattice structure comprising a plurality of nodes connected by links, said links being associated with data identifying units;

determining for at least part of the lattice structure defined by said lattice data a plurality of areas having edges and vertices defined by the nodes and links of at least part of said lattice structure;

generating for said areas, data identifying the number of links bounding each area and data identifying the location of said areas within at least part of said lattice structure; and

outputting as recognition data;

data identifying said units associated with links and said data defining areas.

33. A method of generating recognition data in accordance with claim 1 further comprising the steps of:

determining difference data identifying the differences between said at least part of said lattice structure and the lattice structure defined by said received data; and

outputting as recognition data;

data identifying said units associated with links;

said data defining areas; and

said difference data.

126. A recording medium, storing computer implementable processor steps for causing a programmable computer to perform a method in accordance with claim 1.

2. A method of generating data defining a speech lattice comprising:

receiving data defining a first speech lattice comprising a plurality of nodes interconnected by links, said links being associated with data identifying speech units;

processing said received data to determine a second speech lattice comprising a planar graph having a number of nodes interconnected by links where none of the links cross, said links being associated with data identifying speech units, the nodes and links of said planar graph defining vertices and edges of areas in a two dimensional plane;

generating as data defining said planar graph, identifying data identifying the number of links bounding each said area defined by said planar graph and the location of said areas within said planar graph; and

outputting as data defining said second speech lattice said identifying data and data identifying speech units associated with links of the planar graph defined by said identifying data.

3. A method in accordance with claim 2, wherein:

said processing comprises;

determining an embedding in a two dimensional plane of the lattice structure defined by said received data; and

processing said determined embedding to generate said second speech lattice.

4. A method in accordance with claim 3 wherein:

said processing said determined embedding comprises;

identifying within said determined embedding portions of said embedding identifying links which cross; and

deleting some of said identified crossing links to generate said second speech lattice;

5. A method in accordance with claim 4 wherein said identifying within said determined embedding portions of said embedding identifying links which cross comprises:

determining cross links data identifying how many links each link crosses; and

utilising said cross links data to select some of said identified links which cross to be removed to eliminate crossing links from said embedding.

6. A method in accordance with claim 5 wherein the selected links comprise links crossing more links than the identified crossing links not removed.

7. A method in accordance with claim 4 wherein said some of said identified cross linkings deleted comprise crossing links removed on the basis of probability data associated with said links.

8. A method in accordance with claim 3 wherein said determining of an embedding of said lattice structure comprises:

determining an initial embedding of said lattice structure in a two-dimensional plane; and

processing said initial embedding to determine a further embedding of said lattice structure wherein the number of links which cross in said further embedding is fewer than the number of links which cross in said initial embedding.

9. A method in accordance with claim 2 wherein said generating identifying data comprises generating for each said area:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node to a selected second node defining another vertex of said area.

10. A method in accordance with claim 9 wherein each of said nodes is associated with one of a number of ordered layers, wherein said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

11. A method in accordance with claim 10 wherein each of said nodes in said lattice structure is associated with timing data, the nodes associated with the same timing data being associated with the same layers.

12. A method in accordance with claim 2 wherein said generating identifying data comprises generating for each said area data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

13. A method in accordance with claim 2 wherein said generating identifying data comprises generating data identifying a first selected area;

and

generating data identifying the remaining areas defined by said planar graph wherein the order in which said identifying data is generated is such that the areas for which identifying data is generated correspond to areas adjacent to areas for which identifying data has previously been generated.

14. A method in accordance with claim 13 wherein said data identifying a node defining a vertex of an area comprises an offset value identifying the position of said node relative to the node identifying a vertex of an area for which identifying data has previously been generated.

15. A method in accordance with claim 14 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

16. A method in accordance with claim 15 wherein said list comprises a circular list.

17. A method in accordance with claim 16 wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

18. A method in accordance with claim 15 wherein said list comprises a list of nodes identifying the vertices of the boundary of area for which identifying data has been generated.

19. A method in accordance with claim 2 wherein said identifying data comprises a concatenation of said identifying data generated for each of said area defined by said planar graph.

20. A method in accordance with claim 19 wherein said concatenation of said identifying data comprises a concatenation ordered in the order in which identifying data has been generated for said areas.

21. A method of generating a lattice comprising:

receiving shape data defining a number of areas in a two dimensional plane having vertices and edges corresponding the nodes and links in a planar graph where none of said links cross;

receiving items of hypothesis data associating links of the planar graph defined by shape data with data identifying units; and

generating a lattice comprising a plurality of nodes connected via links by;

determining the planar graph defined by said shape data; and

associating the links of said determined planar graph with units utilising said hypothesis data.

22. A method in accordance with claim 21 wherein said shape data comprises for each of said areas:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node to a selected second node defining another vertex of said area.

23. A method in accordance with claim 22 wherein each of said nodes is associated with one of a number of ordered layers, wherein said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

24. A method in accordance with claim 23 wherein each of said nodes in said lattice structure is associated with timing data, the nodes associated with the same timing data being associated with the same layers.

25. A method in accordance with claim 21 wherein said shape data comprises for each of said areas data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

26. A method in accordance with claim 22 wherein said data identifying a node defining a vertex of an area comprises an offset value identifying the position of said node relative to the node identifying a vertex of an area for which data has previously been generated.

27. A method in accordance with claim 26 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

28. A method in accordance with claim 27 wherein said list comprises a circular list.

29. A method in accordance with claim 28 wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

30. A method in accordance with claim 27 wherein said list comprises a list of nodes identifying the vertices of the boundary of area for which data has been generated.

31. A method in accordance with claim 27 wherein said identifying data comprises a concatenation of said data generated for each of said area defined by said planar graph.

32. A method in accordance with claim 31 wherein said concatenation of said identifying data comprises a concatenation ordered in the order in which identifying data has been generated for said areas.

34. A method of generating data defining a lattice structure comprising:

receiving data defining a lattice structure comprising a plurality of nodes interconnected by links;

processing the received data to determine the differences between an embedding of said lattice structure in a two dimensional plane and a planar graph comprising a number of nodes interconnected by links where none of the links cross, the nodes and links of said planar graph defining edges and vertices of areas in a two dimensional plane;

generating difference data identifying said determined differences;

generating for said areas of said two dimensional plane defined by said planar graph, identifying data identifying the number of links bounding each said area and data identifying of the location of the said area within said planar graph; and

outputting as data defining said lattice structure, said generated identifying data and said generated difference data.

35. A method in accordance with claim 34 wherein said processing comprises:

determining an embedding of said lattice structure in a two dimensional plane;

identifying within said determined embedding, portions of said embedding identifying links which cross; and

identifying for said determined embedding a planar graph having no crossing links which corresponds to said embedding in the absence of some of said identified links wherein said difference data comprises data identifying the differences between said determined embedding and said identified planar graph.

36. A method in accordance with claim 35 wherein said processing comprises:

determining an embedding of said lattice structure in a two dimensional plane;

identifying within said determined embedding, portions of said embedding identifying links which cross; and

generating a planar graph having no crossing links by removing from said determined embedding, data identifying some of said links which cross, wherein said difference data includes data identifying links removed from said determined embedding of said lattice structure.

37. A method in accordance with claim 35 wherein said identifying within said determined embedding portions of said embedding identifying links which cross comprises:

determining cross links data identifying how many links each link crosses; and

utilising said cross links data to select some of said identified links which cross to be removed to eliminate crossing links from said embedding.

38. A method in accordance with claim 37 wherein the selected links comprise links crossing more links than the identified crossing links not removed.

39. A method in accordance with claim 35 wherein said determining of an embedding of said lattice structure comprises:

determining an initial embedding of said lattice structure in a two-dimensional plane; and

processing said initial embedding to determine a further embedding of said lattice structure wherein the number of links which cross in said further embedding is fewer than the number of links which cross in said initial embedding.

40. A method in accordance with claim 35 further comprising:

receiving data associating each of said nodes of said lattice structure defined by received data with an item of timing data said items of timing data together defining a sequence of timings;

identifying nodes associated with the same timing data; and

modifying said determined embedding of said lattice structure by;

determining whether said first timing is associated with a single node; and

if said timing is not associated with a single node, generating a earlier timing in said sequence, a dummy node associated with said earlier timing, and generating links between said generated dummy node and the nodes associated with said first timing wherein said difference data includes data identifying said added node.

41. A method in accordance with claim 40, wherein said modifying said determined embedding of said lattice structure further comprises:

determining whether said last timing is associated with a single node; and

if said timing is not associated with a single node, generating a later timing in said sequence, a dummy node associated with said later timing and links between said generated dummy node and the nodes associated with said last timing, wherein said difference data includes data identifying said added node.

42. A method in accordance with claim 40, wherein said modifying said determined embedding of said lattice structure further comprises:

replacing links between nodes which are associated with non-adjacent timings in said sequence of timings with a series of links connecting dummy nodes associated with timing data for each of said timings within said sequence between said timing of said nodes identified by said removed link;

wherein said difference data includes data identifying said modified portions of said lattice structure.

43. A method in accordance with claim 40 wherein said modifying said determined embedding of said lattice structure further comprises:

determining for the nodes not associated with the earliest and latest timings of said sequence of timing, whether each said node is identified as the start node and end node of links in said embedded lattice by links not crossing other links; and

if a node is not identified as both a start node and end node, adding further links to said embedding so that all of said nodes are identified as both a start node and end node of a link;

wherein said difference data includes data identifying said added links.

44. A method in accordance with claim 40 wherein said modifying said determined embedding of said lattice structure further comprises:

determining nodes of said lattice structure linked to nodes associated with the first timing in said sequence of timings via one or more paths which do not include any dummy nodes; and

determining for nodes associated with successive timings in said sequence of timings whether any nodes are not in said determined group and identifying for said nodes a path comprising dummy nodes connecting said nodes to nodes in said determined group associated with earlier timings; and

replacing paths between nodes via dummy nodes not included in said identified paths, with links between said nodes, wherein said difference data includes data identifying the remaining dummy nodes.

45. A method in accordance with claim 35 further comprising:

modifying said determined embedding by identifying portions of said embedding defining paths between pairs of nodes wherein said portions are not linked to any other nodes of said lattice structure;

replacing said portions with data identifying a single link between said pair of nodes; and

associating said link between said pair of nodes with data identifying the nodes and links in said deleted portions;

wherein said difference data include said data associated with links.

46. A method in accordance with claim 45 wherein said portions comprise paths between pairs of nodes paths via other nodes, said other nodes being identified as the start node of a single link and the end node of a single link wherein said data associated with a generated link comprises data identifying the removal of said node and data associated with the deleted links having said node as a start node and an end node.

47. A method in accordance with claim 45, wherein said portions comprise paths between pairs of nodes comprising a pair of links between said pair of nodes;

wherein said data associated with a generated link between said nodes comprises data identifying the merger of said pair of links and the data associated with the deleted links.

48. A method in accordance with claim 47 wherein said data associated with a link replacing a pair of merged links comprises data identifying the merger of a pair of links and the concatenation of the data associated with said merged links, said data being concatenated in an order dependent upon the amount of data associated with each said link.

49. A method in accordance with claim 34 wherein said generating identifying data comprises:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node to a selected second node defining another vertex of said area.

50. A method in accordance with claim 49 wherein each of said nodes is associated with one of a number of ordered layers, wherein said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

51. A method in accordance with claim 50 wherein each of said nodes in said lattice structure is associated with timing data, the nodes associated with the same timing data being associated with the same layers.

52. A method in accordance with claim 34 wherein said generating identifying data comprises data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

53. A method in accordance with claim 34 wherein said generating identifying data comprises generating data identifying a first selected area;

and

generating data identifying the remaining areas defined by said planar graph wherein the order in which said identifying data is generated is such that the areas for which identifying data is generated correspond to area adjacent to areas for which identifying data has previously been generated.

54. A method in accordance with claim 53 wherein said data identifying a node defining a vertex of an area comprises an offset value identifying the position of said node relative to the node identifying a vertex of an area for which identifying data has previously been generated.

55. A method in accordance with claim 54 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

56. A method in accordance with claim 55 wherein said list comprises a circular list.

57. A method in accordance with claim 55 wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

58. A method in accordance with claim 55 wherein said list comprises a list of nodes identifying the vertices of the boundary of area for which identifying data has been generated.

59. A method in accordance with claim 34 wherein said identifying data comprises a concatenation of said identifying data generated for each of said area defined by said planar graph.

60. A method in accordance with claim 59 wherein said concatenation of said identifying data comprises a concatenation ordered in the order in which identifying data has been generated for said areas.

61. A method in accordance with claim 34 wherein said difference data comprises a concatenation of said generated data associated with links of a planar graph.

62. Apparatus for generating recognition data, comprising:

a receiver operable to receive lattice data defining a lattice structure comprising a plurality of nodes connected by links, said links being associated with data identifying units;

a determinator operable to determine for at least part of the lattice structure defined by lattice data received by said receiver a plurality of areas having edges and vertices defined by the nodes and links of at least part of said lattice structure;

a generator operable to generate for said areas determined by said determinator, data identifying the number of links bounding each area and data identifying the location of said areas within at least part of said lattice structure; and

an output unit operable to output as recognition data;

data identifying said units associated with links and said data defining areas.

97. Apparatus for generating recognition data in accordance with claim 62 further comprising a difference determination unit operable to determine:

difference data identifying the differences between said at least part of said lattice structure and the lattice structure defined by said received data;

wherein said output unit is operable to output as recognition data;

data identifying said units associated with links;

said data defining areas; and

said difference data.

127. A recording medium storing computer implementable processor steps for causing a programmable computer to become configured as an apparatus in accordance with claim 62.

63. Apparatus for generating data defining a speech lattice comprising:

a receiver operable to receive data defining a first speech lattice comprising a plurality of nodes interconnected by links, said links being associated with data identifying speech units;

a processing unit operable to process data received by said receiver to determine a second speech lattice comprising a planar graph having a number of nodes interconnected by links where none of the links cross, said links being associated with data identifying speech units, the nodes and links of said planar graph defining vertices and edges of areas in a two dimensional plane;

a generator operable to generate as data defining a planar graph determined by said processing unit, identifying data identifying the number of links bounding each said area defined by said planar graph and the location of said areas within said planar graph; and

an output unit operable to output as data defining said second speech lattice said identifying data generated by said generator and data identifying speech units associated with links of the planar graph defined by said identifying data received by said receiver.

64. Apparatus in accordance with claim 63, wherein:

said processing unit comprises;

an embedding unit operable to determine an embedding in a two dimensional plane of the lattice structure defined by data received by said receiver, and

an embedding processor operable to process said determined embedding to generate said second speech lattice.

65. Apparatus in accordance with claim 64 wherein:

said embedding processor is operable to identify within said determined embedding portions of said embedding identifying links which cross; and

delete some of said identified crossing links to generate said second speech lattice;

66. Apparatus in accordance with claim 65 wherein said embedding processor is operable to identify within said determined embedding portions of said embedding identifying links which cross by:

determining cross links data identifying how many links each link crosses; and

utilising said cross links data to select some of said identified links which cross to be removed to eliminate crossing links from said embedding.

67. Apparatus in accordance with claim 66 wherein the selected links comprise links crossing more links than the identified crossing links not removed.

68. Apparatus in accordance with claim 65 wherein said receiver is operable to receive probability data associating probabilities with links in said lattice;

said embedding processor being operable to delete links on the basis of probability data associated with said links.

69. Apparatus in accordance with claim 64 wherein said embedding unit is operable to:

determining an initial embedding of said lattice structure in a two- dimensional plane; and

process said initial embedding to determine a further embedding of said lattice structure wherein the number of links which cross in said further embedding is fewer than the number of links which cross in said initial embedding.

70. Apparatus in accordance with claim 63 wherein said generator is operable to generate identifying data comprising for each said area:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node and a selected second node defining another vertex of said area.

71. Apparatus in accordance with claim 70 wherein said processing unit is operable to associate each of said nodes with one of a number of ordered layers, wherein said generator is operable to generate identifying data where said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

72. Apparatus in accordance with claim 71 wherein said receiver is operable to receive data associating each of said nodes in said lattice structure is associated with timing data, the nodes associated with the same timing data being associated with the same layers.

73. Apparatus in accordance with claim 63 wherein said generator is operable to generate for each area identifying data comprising data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

74. Apparatus in accordance with claim 63 wherein said generator is operable to generate data identifying a first selected area;

and

generate data identifying the remaining areas defined by said planar graph wherein the order in which said identifying data is generated is such that the areas for which identifying data is generated correspond to area adjacent to areas for which identifying data has previously been generated.

75. Apparatus in accordance with claim 74 wherein said generator is operable to generate for each area, data identifying a node defining a vertex of said area comprising an offset value identifying the position of said node relative to the node identifying a vertex of an area for which identifying data has previously been generated.

76. Apparatus in accordance with claim 75 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

77. Apparatus in accordance with claim 76 wherein said list comprises a circular list.

78. Apparatus in accordance with claim 77 wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

79. Apparatus in accordance with claim 76 wherein said list comprises a list of nodes identifying the vertices of the boundary of area for which identifying data has been generated.

80. Apparatus in accordance with claim 63 wherein said generator is operable to generate identifying data comprising a concatenation of said identifying data generated for each of said area defined by said planar graph.

81. Apparatus in accordance with claim 80 wherein said concatenation of said identifying data comprises a concatenation ordered in the order in which identifying data has been generated for said areas.

82. Apparatus in accordance with claim 63 further comprising:

a compressor operable to compress output data defining said lattice structure output by said output unit; and

a transmitter operable to transmit said compressed data generated by said compressor.

83. Apparatus in accordance with claim 82, further comprising:

a decompressor operable to receive and decompress compressed data transmitted by said transmitter;

a regeneration unit operable to process identifying data and said difference data by said decompressor to determine said defined lattice structure.

84. Apparatus in accordance with claim 83 wherein said regeneration unit is operable to:

generate a planar graph utilising said identifying data; and

associate the links of said planar graph with data identifying speech units utilising said data identifying speech units.

85. Apparatus for generating a lattice comprising:

a receiver operable to receive shape data defining a number of areas in a two dimensional plane having vertices and edges corresponding the nodes and links in a planar graph where none of said links cross; and

items of hypothesis data associating links of the planar graph defined by shape data with data identifying units;

a generator operable to generate a lattice comprising a plurality of nodes connected via links by;

determining the planar graph defined by said shape data received by said receiver; and

associating the links of said determined planar graph with units utilising said hypothesis data received by said receiver.

86. Apparatus in accordance with claim 85 wherein said receiver is configured to receive shape data comprising for each of said areas:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node and a selected second node defining another vertex of said area.

87. Apparatus in accordance with claim 86 wherein said receiver is operable to receive data associating each of said nodes with one of a number of ordered layers, wherein said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

88. Apparatus in accordance with claim 87 wherein said receiver is operable to receive data associating each of said nodes in said lattice structure with timing data, the nodes associated with the same timing data being associated with the same layers.

89. Apparatus in accordance with claim 85 wherein said receiver is configured to receive shape data comprising for each of said areas data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

90. Apparatus in accordance with claim 86 wherein said receiver is operable to receive data identifying a node defining a vertex of an area comprising an offset value identifying the position of said node relative to the node identifying a vertex of an area for which data has previously been generated.

91. Apparatus in accordance with claim 90 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

92. Apparatus in accordance with claim 91 wherein said list comprises a circular list.

93. Apparatus in accordance with claim 92 wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

94. Apparatus in accordance with claim 91 wherein said list comprises a list of nodes identifying the vertices of the boundary of an area for which data has been generated.

95. Apparatus in accordance with claim 85 wherein said receiver is operable to receive identifying data comprising a concatenation of said data representative of each of said areas defined by said planar graph.

96. Apparatus in accordance with claim 95 wherein said concatenation of said identifying data comprises a concatenation ordered in the order in which identifying data has been generated for said areas.

98. Apparatus for generating data defining a lattice structure comprising:

a receiver operable to receive data defining a lattice structure comprising a plurality of nodes interconnected by links;

a processing unit operable to process data received by said receiver to determine the differences between an embedding of said lattice structure in a two dimensional plane and a planar graph comprising a number of nodes interconnected by links where none of the links cross, the nodes and links of said planar graph defining edges and vertices of areas in a two dimensional plane;

a difference generator operable to generate difference data identifying differences;

a shape encoder operable to generate for said areas of a two dimensional plane defined by a planar graph, identifying data identifying the number of links bounding each said area and data identifying of the location of the said area within said planar graph; and

an output unit operable to output as data defining said lattice structure, said identifying data generated by said shape encoder and said difference data generated by said difference generator.

99. Apparatus in accordance with claim 98 wherein said processing unit comprises:

an embedding unit operable to determine an embedding of a lattice structure defined by data received by said receiver in a two dimensional plane; and

a planar graph identification unit operable to identify within said determined embedding, portions of said embedding identifying links which cross; and

to identify for an embedding determined by said embedding unit a planar graph having no crossing links which corresponds to said embedding in the absence of some of said identified links wherein said difference data generated by said difference generator comprises data identifying the differences between said embedding and said planar graph identified by said planar graph.

100. Apparatus in accordance with claim 98 wherein said processing unit comprises:

an embedding unit operable to determine an embedding of a lattice structure defined by data received by said receiver in a two dimensional plane; and

a planar graph identification unit operable to identify within an embedding determined by said embedding, portions of said embedding identifying links which cross; and

to generate a planar graph having no crossing links by removing from said determined embedding, data identifying some of said links which cross, wherein said difference data generated by said difference generator includes data identifying links removed from said determined embedding of said lattice structure by said planar graph identification unit.

101. Apparatus in accordance with claim 99 wherein said planar graph identification unit comprises:

a cross link identifier operable to determine cross links data identifying how many links each link crosses of an embedding; and

a link selection unit operable to utilise said cross links data to select some of said identified links which cross to be removed to eliminate crossing links from a said embedding.

102. Apparatus in accordance with claim 101 wherein said link selection unit is 30 operable to select as links to be removed links crossing more links than the identified crossing links not removed.

103. Apparatus in accordance with claim 99 wherein said embedding unit comprises:

an embedding determinator operable to determine an initial embedding of said lattice structure in a two-dimensional plane; and

an embedding processor operable to process an initial embedding determined by said embedding determinator to determine a further embedding of said lattice structure wherein the number of links which cross in said further embedding is fewer than the number of links which cross in said initial embedding.

104. Apparatus in accordance with claim 99 wherein said receiver is operable to receive:

data associating each of said nodes of said lattice structure defined by received data with an item of timing data said items of timing data together defining a sequence of timings;

said apparatus further comprising;

a layering unit operable to identify nodes associated with the same timing data; and

a modifying unit operable to modifying an embedding determined by said embedding unit by;

determining whether said first timing is associated with a single node; and

if said timing is not associated with a single node, generating a earlier timing in said sequence, a dummy node associated with said earlier timing, and generating links between said generated dummy node and the nodes associated with said first timing wherein said difference generator is operable to generate difference data including data identifying said added node.

105. Apparatus in accordance with claim 104, wherein said modifying unit is further operable to modify an embedding determined by said embedding unit by:

determining whether said last timing is associated with a single node; and

if said timing is not associated with a single node, generating a later timing in said sequence, a dummy node associated with said later timing and links 30 between said generated dummy node and the nodes associated with said last timing, wherein difference generator is operable to generate said difference data including data identifying said added node.

106. Apparatus in accordance with claim 104, wherein said modifying unit is operable to modify an embedding determined by said embedding unit by:

replacing links between nodes which are associated with non-adjacent timings in said sequence of timings with a series of links connecting dummy nodes associated with timing data for each of said timings within said sequence between said timing of said nodes identified by said removed link;

wherein said difference generator is operable to generate said difference data including data identifying said modified portions of said lattice structure.

107. Apparatus in accordance with claim 104 wherein said modifying unit is operable to modify an embedding determined by said embedding unit by:

determining for the nodes not associated with the earliest and latest timings of said sequence of timing, whether each said node is identified as the start node and end node of links in said embedded lattice by links not crossing other links; and

if a node is not identified as both a start node and end node, adding further links to said embedding so that all of said nodes are identified as both a start node and end node of a link;

wherein said difference generator is operable to generate said difference data including data identifying said added links.

108. Apparatus in accordance with claim 104 wherein said modifying unit is operable to modify an embedding determined by said embedding unit by:

determining nodes of said lattice structure linked to nodes associated with the first timing in said sequence of timings via one or more paths which do not include any dummy nodes; and

determining for nodes associated with successive timings in said sequence of timings whether any nodes are not in said determined group and identifying for said nodes a path comprising dummy nodes connecting said nodes to nodes in said determined group associated with earlier timings; and

replacing paths between nodes via dummy nodes not included in said identified paths, with links between said nodes, wherein said difference generator is operable to generate difference data including data identifying the remaining dummy nodes.

109. Apparatus in accordance with claim 99 further comprising:

a link encoder operable to modify said determined embedding by identifying portions of said embedding defining paths between pairs of nodes wherein said portions are not linked to any other nodes of said lattice structure;

replacing said portions with data identifying a single link between said pair of nodes; and

associating said link between said pair of nodes with data identifying the nodes and links in said deleted portions;

wherein said difference generator is operable to generate difference data including said data associated with links.

110. Apparatus in accordance with claim 109 wherein said link encoder is operable to identify portions comprising paths between pairs of nodes paths via other nodes, said other nodes being identified as the start node of a single link and the end node of a single link wherein said data associated with a generated link comprises data identifying the removal of said node and data associated with the deleted links having said node as a start node and an end node.

111. Apparatus in accordance with claim 109, wherein said link encoder is operable to identify portions comprising paths between pairs of nodes comprising a pair of links between said pair of nodes;

wherein said data associated with a generated link between said nodes comprises data identifying the merger of said pair of links and the data associated with the deleted links.

112. Apparatus in accordance with claim 111 wherein said link encoder is operable to associate with a link replacing a pair of merged links comprising data identifying the merger of a pair of links and the concatenation of the data associated with said merged links, said data being concatenated in an order dependent upon the amount of data associated with each said link.

113. Apparatus in accordance with claim 98 wherein said shape encoder is operable to generate identifying data for each area, comprising:

data identifying one node forming a vertex of said area; and

a first and a second number identifying the number of links in a pair of paths from said first node to a selected second node defining another vertex of said area.

114. Apparatus in accordance with claim 113 wherein said processing unit is operable to associate each of said nodes with one of a number of ordered layers, wherein said first node of an area comprises the node defining a vertex in one layer and said second node comprises a node defining a vertex associated with a layer further removed from said layer associated with said first node than the layers associated with other nodes defining vertices of said area.

115. Apparatus in accordance with claim 114 wherein said receiver is operable to receive data to associate each of said nodes in said lattice structure with timing data, the nodes associated with the same timing data being associated by said processing unit with the same layers.

116. Apparatus in accordance with claim 98 wherein said shape encoder is operable to generate identifying data for each area comprising data identifying one node forming a vertex of said area, data identifying the total number of links bounding said area;

and data identifying the number of links said area shares with areas for which data has already been generated.

117. Apparatus in accordance with claim 98 wherein said shape encoder is operable to generate data identifying a first selected area;

and

data identifying the remaining areas defined by said planar graph wherein the order in which said identifying data is generated is such that the areas for which identifying data is generated correspond to area adjacent to areas for which identifying data has previously been generated.

118. Apparatus in accordance with claim 117 wherein said shape encoder is operable to generate for each area data identifying a node defining a vertex of said area comprising an offset value identifying the position of said node relative to the node identifying a vertex of an area for which identifying data has previously been generated.

119. Apparatus in accordance with claim 118 wherein said offset value comprises an offset value identifying the relative positions of said nodes in a list of nodes.

120. Apparatus in accordance with claim 119 wherein said list comprises a circular list.

121. Apparatus in accordance with claim 119wherein said offset values comprise positive or negative numbers identifying offsets in different directions in said list.

122. Apparatus in accordance with claim 119 wherein said list comprises a list of nodes identifying the vertices of the boundary of area for which identifying data has been generated.

123. Apparatus in accordance with claim 98 wherein said shape encoder is operable to generate identifying data comprising a concatenation of said identifying data generated for each of said area defined by said planar graph.

124. Apparatus in accordance with claim 123 wherein said shape encoder is operable to generate said concatenation of said identifying data ordered in the order in which identifying data is generated for said areas.

125. Apparatus in accordance with claim 98 wherein said difference generator is operable to generate data comprising a concatenation of said generated data associated with links of a planar graph.