Skip to content

Dictionary matching

sies.dictionary.descriptors

Transformation-invariant shape descriptors built from CGPT matrices.

Reference: Ammari et al., Target identification using dictionary matching of generalized polarization tensors, FoCM (2014).

ShapeDescriptor dataclass 

ShapeDescriptor(i1, i2)

Pair of invariant descriptors derived from a CGPT matrix.

Attributes:

Name Type Description
i1 (ndarray, shape(k, k))

First invariant descriptor (modulus of the normalized first complex CGPT).
i2 (ndarray, shape(k, k))

Second invariant descriptor.

order property 

order

int: Maximum CGPT order of the descriptor.

from_cgpt classmethod 

from_cgpt(cgpt)

Compute invariant descriptors from a CGPT matrix.

The CGPT is first recentered at the equivalent center of the shape (estimated from its own low-order entries), then normalized by its diagonal, which removes the dependence on translation, rotation and scaling.

Parameters:

Name Type Description Default
cgpt ndarray, shape (2k, 2k)

CGPT matrix of the shape.

 required

Returns:

Type Description
ShapeDescriptor

The invariant descriptors.

Raises:

Type Description
ValueError

If the CGPT is degenerate (vanishing leading entry or diagonal), which prevents the normalization.
Source code in src/sies/dictionary/descriptors.py 
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
@classmethod
def from_cgpt(cls, cgpt: NDArray) -> "ShapeDescriptor":
    """Compute invariant descriptors from a CGPT matrix.

    The CGPT is first recentered at the equivalent center of the
    shape (estimated from its own low-order entries), then
    normalized by its diagonal, which removes the dependence on
    translation, rotation and scaling.

    Parameters
    ----------
    cgpt : ndarray, shape (2k, 2k)
        CGPT matrix of the shape.

    Returns
    -------
    ShapeDescriptor
        The invariant descriptors.

    Raises
    ------
    ValueError
        If the CGPT is degenerate (vanishing leading entry or
        diagonal), which prevents the normalization.
    """
    n1, n2 = cgpt_to_complex(cgpt)

    # Estimated (complex) offset of the equivalent center of the shape.
    if np.isclose(np.abs(n2[0, 0]), 0.0):
        raise ValueError("Cannot infer the descriptor center: N2[0, 0] is zero.")
    center = n2[0, 1] / n2[0, 0] / 2
    t1, t2 = transform_ccgpt_inverse(n1, n2, center, 1.0, 0.0)

    # Scaling invariance: normalize by the diagonal of T2 (stable at
    # high orders).
    diag_t2 = np.abs(np.diag(t2))
    if np.any(np.isclose(diag_t2, 0.0)):
        raise ValueError("Cannot normalize the descriptor: zero diagonal in the CGPT.")
    norm = np.diag(1 / np.sqrt(diag_t2))
    s1 = norm @ t1 @ norm
    s2 = norm @ t2 @ norm
    return cls(i1=np.abs(s1), i2=np.abs(s2))

distance 

distance(other, order=None)

Frobenius distance between two descriptors up to a given order.

Parameters:

Name Type Description Default
other ShapeDescriptor

Descriptor to compare with.

 required
order int

Truncation order; the full descriptor is used by default.

 None

Returns:

Type Description
float

The combined Frobenius distance sqrt(|I1 - I1'|^2 + |I2 - I2'|^2).
Source code in src/sies/dictionary/descriptors.py 
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
def distance(self, other: "ShapeDescriptor", order: int | None = None) -> float:
    """Frobenius distance between two descriptors up to a given order.

    Parameters
    ----------
    other : ShapeDescriptor
        Descriptor to compare with.
    order : int, optional
        Truncation order; the full descriptor is used by default.

    Returns
    -------
    float
        The combined Frobenius distance
        ``sqrt(|I1 - I1'|^2 + |I2 - I2'|^2)``.
    """
    order = order or min(self.order, other.order)
    d1 = self.i1[:order, :order] - other.i1[:order, :order]
    d2 = self.i2[:order, :order] - other.i2[:order, :order]
    return float(np.sqrt(np.linalg.norm(d1) ** 2 + np.linalg.norm(d2) ** 2))

sies.dictionary.matching

Dictionary matching of shape descriptors.

ShapeDictionary dataclass 

ShapeDictionary(shapes, descriptors, cnd, pmtt)

A dictionary of shapes with precomputed invariant descriptors.

Attributes:

Name Type Description
shapes list of C2Boundary

The reference shapes.
descriptors list of ShapeDescriptor

Invariant descriptor of each shape.
cnd float

Conductivity used to compute the CGPTs.
pmtt float

Permittivity used to compute the CGPTs.

names property 

names

List of str: Names of the dictionary shapes.

build classmethod 

build(shapes, cnd, pmtt=0.0, order=5, freq=0.0)

Build a dictionary from a list of shapes.

The theoretical CGPT of each shape is computed by boundary integral equations and converted to invariant descriptors.

Parameters:

Name Type Description Default
shapes list of C2Boundary

The reference shapes (typically normalized to similar sizes).

 required
cnd float

Common conductivity of the shapes.

 required
pmtt float

Common permittivity.

 0.0
order int

Maximum CGPT order of the descriptors.

 5
freq float

Working frequency.

 0.0

Returns:

Type Description
ShapeDictionary

The assembled dictionary.

Raises:

Type Description
ValueError

If shapes is empty.
Source code in src/sies/dictionary/matching.py 
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
@classmethod
def build(
    cls,
    shapes: list[C2Boundary],
    cnd: float,
    pmtt: float = 0.0,
    order: int = 5,
    freq: float = 0.0,
) -> "ShapeDictionary":
    """Build a dictionary from a list of shapes.

    The theoretical CGPT of each shape is computed by boundary
    integral equations and converted to invariant descriptors.

    Parameters
    ----------
    shapes : list of C2Boundary
        The reference shapes (typically normalized to similar
        sizes).
    cnd : float
        Common conductivity of the shapes.
    pmtt : float, default 0.0
        Common permittivity.
    order : int, default 5
        Maximum CGPT order of the descriptors.
    freq : float, default 0.0
        Working frequency.

    Returns
    -------
    ShapeDictionary
        The assembled dictionary.

    Raises
    ------
    ValueError
        If `shapes` is empty.
    """
    if not shapes:
        raise ValueError("`shapes` must contain at least one reference shape.")
    lam = contrast(cnd, pmtt, freq)
    descriptors = [
        ShapeDescriptor.from_cgpt(theoretical_cgpt(shape, lam, order)) for shape in shapes
    ]
    return cls(shapes=shapes, descriptors=descriptors, cnd=cnd, pmtt=pmtt)

match 

match(descriptor, order=None)

Rank the dictionary shapes by similarity with a descriptor.

Parameters:

Name Type Description Default
descriptor ShapeDescriptor

Descriptor of the unknown shape.

 required
order int

Truncation order used for the comparison.

 None

Returns:

Name Type Description
errors ndarray

Distance to each dictionary element.
ranking ndarray

Dictionary indices sorted by increasing distance.
Source code in src/sies/dictionary/matching.py 
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
def match(
    self, descriptor: ShapeDescriptor, order: int | None = None
) -> tuple[NDArray, NDArray]:
    """Rank the dictionary shapes by similarity with a descriptor.

    Parameters
    ----------
    descriptor : ShapeDescriptor
        Descriptor of the unknown shape.
    order : int, optional
        Truncation order used for the comparison.

    Returns
    -------
    errors : ndarray
        Distance to each dictionary element.
    ranking : ndarray
        Dictionary indices sorted by increasing distance.
    """
    return match_descriptor(descriptor, self.descriptors, order)

identify 

identify(descriptor, order=None)

Return the name of the best-matching dictionary shape.

Parameters:

Name Type Description Default
descriptor ShapeDescriptor

Descriptor of the unknown shape.

 required
order int

Truncation order used for the comparison.

 None

Returns:

Type Description
str

Name of the identified shape.
Source code in src/sies/dictionary/matching.py 
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
def identify(self, descriptor: ShapeDescriptor, order: int | None = None) -> str:
    """Return the name of the best-matching dictionary shape.

    Parameters
    ----------
    descriptor : ShapeDescriptor
        Descriptor of the unknown shape.
    order : int, optional
        Truncation order used for the comparison.

    Returns
    -------
    str
        Name of the identified shape.
    """
    _, ranking = self.match(descriptor, order)
    return self.names[ranking[0]]

match_descriptor 

match_descriptor(descriptor, dictionary, order=None)

Rank dictionary elements by similarity with a query descriptor.

Parameters:

Name Type Description Default
descriptor ShapeDescriptor

Descriptor of the unknown shape.

 required
dictionary list of ShapeDescriptor

Descriptors of the dictionary shapes.

 required
order int

Truncation order used for the comparison.

 None

Returns:

Name Type Description
errors (ndarray, shape(len(dictionary)))

Distance between the query and each dictionary element.
ranking (ndarray, shape(len(dictionary)))

Indices of the dictionary elements sorted by increasing distance; ranking[0] is the identified shape.
Source code in src/sies/dictionary/matching.py 
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def match_descriptor(
    descriptor: ShapeDescriptor,
    dictionary: list[ShapeDescriptor],
    order: int | None = None,
) -> tuple[NDArray, NDArray]:
    """Rank dictionary elements by similarity with a query descriptor.

    Parameters
    ----------
    descriptor : ShapeDescriptor
        Descriptor of the unknown shape.
    dictionary : list of ShapeDescriptor
        Descriptors of the dictionary shapes.
    order : int, optional
        Truncation order used for the comparison.

    Returns
    -------
    errors : ndarray, shape (len(dictionary),)
        Distance between the query and each dictionary element.
    ranking : ndarray, shape (len(dictionary),)
        Indices of the dictionary elements sorted by increasing
        distance; ``ranking[0]`` is the identified shape.
    """
    errors = np.array([descriptor.distance(item, order) for item in dictionary])
    return errors, np.argsort(errors)