Wolfram Cloud Resource Object

Function Resource

Function Repository Resource:

 ChamferDistance

Source Notebook

Measures the Chamfer distance between two point clouds

Contributed by: Seth J. Chandler

ResourceFunction["ChamferDistance"][list1,list2]

computes the "Chamfer distance" between list1and list2.

The Chamfer distance is the sum of two means: (1) the mean of the distances between every item in list2 to its closest neighbor in list1 and (2) the mean of the distances between every item in list1 to its closest neighbor in list2.
Some explanations of Chamfer distance use sums instead if means: the sum of the distances between every item in list2 to its closest neighbor in list1 and the distances between every item in list1 to its closest neighbor in list2. You can use this alternative definition by setting the "Definition" option to "Total" instead of its default value of "Mean".
By default, the distance metric is the SquaredEuclideanDistance.

Examples

Basic Examples (2) 

Compute the Chamfer distance between two lists:

In[1]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][{0, 4, 7, 8}, {2, 1, 11, 3, 7}]
Out[1]=

Compute the Chamfer distance between two three-dimensional lists (point clouds):

In[2]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][{{0, 8, 1}, {5, 3, 5}, {7, 10, 1}, {4, 4, 1}, {6, 6, 4}, {0, 1, 1}, {8, 6, 0}, {0, 2, 9}, {1, 6, 2}, {4, 7, 7}, {3, 1, 0}, {1, 1, 5}}, {{10, 10, 12}, {5, 10, 2}, {7, 12, 12}, {11, 12, 10}, {6, 11, 11}, {8, 11, 6}, {3, 6, 7}}]
Out[2]=

Set "Definition" to "Sum" to compute the sum of the distances to the nearest points:

In[3]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][{0, 4, 7, 8}, {2, 1, 11, 3, 7}, "Definition" -> "Total"]
Out[3]=

Use the ManhattanDistance to measure the distance between point clouds:

In[4]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][{0, 4, 7, 8}, {2, 1, 11, 3, 7}, DistanceFunction -> ManhattanDistance]
Out[4]=

By changing the distance metric to EditDistance, you can obtain the Chamfer distance between texts:

In[5]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][ TextSentences[ExampleData[{"Text", "CodeOfHammurabiEnglish"}]][[ 1 ;; 4]], TextSentences[ExampleData[{"Text", "USConstitution"}]][[1 ;; 6]], DistanceFunction -> EditDistance]
Out[5]=

By changing the distance metric to GeoDistance, you can obtain the Chamfer distance between two lists of geographic locations:

In[6]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][ EntityClass["City", "UnitedStatesCapitals"][ EntityProperty["City", "Position"]], EntityValue[ EntityValue[ Entity["GeographicRegion", "Europe"][ EntityProperty["GeographicRegion", "Countries"]], EntityProperty["Country", "CapitalCity"]], EntityProperty["City", "Position"]], DistanceFunction -> GeoDistance]
Out[6]=

ChamferDistance supports the same Method option values as Nearest:

In[7]:=
Map[RepeatedTiming[ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][{0, 4, 7, 8}, {2, 1, 11, 3, 7}, Method -> #]] &, {Automatic, "Scan", "KDtree", "Octree"}]
Out[7]=

See how the Chamfer Distance between the outputs of twoNormal distributions as one changes the mean of one of the distributions:

In[8]:=
ListLinePlot[ResourceFunction[ ResourceObject[<|"Name" -> "PairMap", "ShortName" -> "PairMap", "UUID" -> "87f7da87-fdae-4ad1-b9d2-29f9d7301b45", "ResourceType" -> "Function", "Version" -> "1.0.0", "Description" -> "Map a function to pairs formed from a list and another function", "RepositoryLocation" -> URL[ "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"], "SymbolName" -> "FunctionRepository`$5102f3194eac409286d2e9feed3857c1`PairMap", "FunctionLocation" -> CloudObject[ "https://www.wolframcloud.com/obj/cc05e3d5-ab17-4abb-8fc5-250eb95b9ae6"]|>, ResourceSystemBase -> Automatic]][\[Mu] |-> ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][ RandomVariate[NormalDistribution[0, 1], 1000], RandomVariate[NormalDistribution[\[Mu], 1], 1000]], Range[-2, 2, 0.1]], AxesLabel -> {"mean of second distribution\n(n=1000)", "Chamfer distance"}]
Out[8]=

Changing the order of the points in the point clouds does not affect the Chamfer distance:

In[9]:=
SameQ @@ Flatten[Outer[ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]], Permutations[{0, 4, 7, 8}], Permutations[{2, 1, 11, 3, 7}], 1, 1]]
Out[9]=

Create a neural network based on Distilbert that extracts the "meaning" of various passages in texts:

In[10]:=
distilbertCLS = NetAppend[ NetModel[ "DistilBERT Trained on BookCorpus and English Wikipedia Data"], {SequenceReverseLayer[], SequenceLastLayer[]}]
Out[10]=

Map the network onto several sentences from a legal opinion:

In[11]:=
passages = TextSentences[ "The State therefore has power to prevent the individual from making certain kinds of contracts, and, in regard to them, the Federal Constitution offers no protection. If the contract be one which the State, in the legitimate exercise of its police power, has the right to prohibit, it is not prevented from prohibiting it by the Fourteenth Amendment. Contracts in violation of a statute, either of the Federal or state government, or a contract to let one's property for immoral purposes, or to do any other unlawful act, could obtain no protection from the Federal Constitution as coming under the liberty of person or of free contract. Therefore, when the State, by its legislature, in the assumed exercise of its police powers, has passed an act which seriously limits the right to labor or the right of contract in regard to their means of livelihood between persons who are sui juris (both employer and employee), it becomes of great importance to determine which shall prevail -- the right of the individual to labor for such time as he may choose or the right of the State to prevent the individual from laboring or from entering into any contract to labor beyond a certain time prescribed by the State. This court has recognized the existence and upheld the exercise of the police powers of the States in many cases which might fairly be considered as border ones, and it has, in the course of its determination of questions regarding the asserted invalidity of such statutes on the ground of their violation of the rights secured by the Federal Constitution, been guided by rules of a very liberal nature, the application of which has resulted, in numerous instances, in upholding the validity of state statutes thus assailed."];
In[12]:=
DistanceMatrix[Map[distilbert, passages], DistanceFunction -> ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]]] // MatrixPlot[#, PlotLegends -> Automatic] &
Out[12]=

Use to find the Chamfer distance between two sets of expressions:

In[13]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][ Map[ExpressionTree, {2 Cos[i \[Pi]], 2 Sin[j \[Pi]], Solve[a x^2 + b x + c == 0, x]}], Map[ExpressionTree, {2 Cos[i \[Pi] + 5], Sin[j \[Pi]]/Tan[i j], Solve[a x^3 + b x^2 + c x + d == 0, x]}], DistanceFunction -> ResourceFunction[ ResourceObject[<|"Name" -> "TreeEditDistance", "ShortName" -> "TreeEditDistance", "UUID" -> "617debbc-1afb-4052-b6fc-4349e292463b", "ResourceType" -> "Function", "Version" -> "1.0.0", "Description" -> "Calculate the edit distance between two Tree objects", "RepositoryLocation" -> URL[ "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"], "SymbolName" -> "FunctionRepository`$9db68ed5f71648ed9c2485c82cd104a9`TreeEditDistance", "FunctionLocation" -> CloudObject[ "https://www.wolframcloud.com/obj/303f2997-37c5-4439-a034-246a675dbd1c"]|>, ResourceSystemBase -> Automatic]]]
Out[13]=

Get the Chamfer distance between the brightest stars in the constellation Orion and the brightest stars in Ursa Major (a/k/a the Big Dipper). First get the brightest stars in Orion:

In[14]:=
orion = EntityList[ FilteredEntityClass[EntityClass["Star", "OrionStar"], EntityFunction[c, c["ApparentMagnitude"] < 2]]]
Out[14]=

Then get the brightest stars in Ursa Major:

In[15]:=
bigdipper = EntityList[ FilteredEntityClass[EntityClass["Star", "UrsaMajorStar"], EntityFunction[c, c["ApparentMagnitude"] < 2]]]
Out[15]=

Compute the Chamfer distance as of January 4, 2023. You need to add QuantityMagnitude to the DistanceFunction pipeline:

In[16]:=
ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][orion, bigdipper, DistanceFunction -> ((AstroAngularSeparation[#1, #2, DateObject[{2023, 1, 4}, "Day"]] &)/*QuantityMagnitude)]
Out[16]=

Imagine a tree of all possible concepts (an ontology):

In[17]:=
rt = (SeedRandom[202301015]; RandomTree[20])
Out[17]=

Compute the distances between concepts in the undirected version of the tree but reduce the dimensionality of the resulting matrix using "MultidimensionalScaling":

In[18]:=
(gdm = DimensionReduce[GraphDistanceMatrix[UndirectedGraph[rt]], 8, Method -> "MultidimensionalScaling"]) // Dimensions
Out[18]=

Now imagine seven texts each of which address certain concepts within the tree; each text does not have to address the same number of concepts:

In[19]:=
texts = {{2, 14, 13}, {6, 7, 10, 15}, {5, 19}, {2, 15, 13, 18}, {1, 2, 14}, {15, 12, 1, 3}, {7, 13, 10, 9, 8, 5}};

Create a DistanceMatrix using the Chamfer distance:

In[20]:=
dm = DistanceMatrix[texts, DistanceFunction -> (ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/schandler/DeployedResources/Function/ChamferDistance"]][gdm[[#1]], gdm[[#2]]] &)]
Out[20]=

Construct a nearest neighbor graph:

In[21]:=
nng = Graph[Flatten[ResourceFunction[ ResourceObject[<|"Name" -> "MapSlice", "ShortName" -> "MapSlice", "UUID" -> "f3da3843-eca4-49a1-a10f-ae495c5a085e", "ResourceType" -> "Function", "Version" -> "1.0.0", "Description" -> "Provide the part specifications to a mapped function as a sequence of arguments after the first one", "RepositoryLocation" -> URL[ "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"], "SymbolName" -> "FunctionRepository`$fc34d7cb86b4477286abcf1aeedb1cac`MapSlice", "FunctionLocation" -> CloudObject[ "https://www.wolframcloud.com/obj/2edb34b0-5ba9-472e-9991-7a8746a6c7a5"]|>, ResourceSystemBase -> Automatic]][{d, index} |-> Thread[DirectedEdge[index, (Take[Ordering[d], {2, 3}])]], dm]], VertexLabels -> Placed["Name", Center], VertexSize -> 0.4]
Out[21]=

Now do a "search" on text 7 to find those texts that are closest to it:

In[22]:=
VertexOutComponent[nng, 7, {1}]
Out[22]=