Privacy Preserving Morphological Operations for Digital Images

Image processing operations require complex computations. The emerging cloud technologies provide businesses and individuals with the possibility to outsource these computations on a remote platform with large resources and high availability. This approach substantially reduces the costs, but raises privacy concerns. To address these concerns, the data (i.e. the images) owned by the user could be encrypted, sent to the cloud and processed there by taking advantage from the properties of a homomorphic encryption scheme. The result of the computation performed on encrypted data is sent back to the user to be decrypted.

In the paper the authors study the possibility of performing some morphological operations on encrypted digital images. The chosen operations, when represented as plaintext operations in the field $\mathbb {F} _{2}$ are modelled by very sparse polynomials of large degree. This makes them very suitable to be performed homomorphically using the certSGN scheme.

The authors of the paper have implemented these operations using the certSGN, the BGV and the BFV schemes. The results are discussed and compared.

Morphological primitives

Morphology refers to the description of the properties concerning the shape and structure of an object. In the context of image processing, this is related to the description of properties of shapes of areas in an image.

So-called morphology operators are used to extract properties of the image, useful for its descriptions (such as the contour, skeletons or convex hulls). One has to input two parameters: a binary image and a structural element which describes some geometrical shape and is much smaller than the processed image.

Binary images

The pixels in a binary image are partitioned in two disjoint sets: objects and background. Morphological operations between a chosen structural element and the image can be expressed as classical set-theoretic operations (such as intersections and unions).

A black and white image can be represented as a binary matrix, where value $0$ represents the background pixels and value $1$ represents pixels that are associated to objects.

Structring elements

A structural (or structuring) element consists of a description of a certain shape, typically much smaller than the processed image. The most common elements have a special nume: box (rectangle of a given size), disk or ring.

Elements of a structuring element $S$ can be viewed as pairs of integers which are measured with respect to the ``origin" $(0,0)$ of the element, a pixel which is usually crossed in diagram representations.

Generally, the origin of the structuring element is chosen to be the pixel located at the center.

An operation commonly used to compute the result of a certain morphological primitive is the translation. If $p\in \mathbb {Z} ^{2}$ is a fixed vector, then the translation of $S$ by $p$ is $S_{p}=\{s+p\mid s\in S\}$, where $+$ represents the vector addition in $\mathbb {Z} ^{2}$.

The erosion operation

We see images $I$ and structural elements $S$ as finite subsets of $\mathbb {Z} ^{2}$.

The erosion $E(I,S)$ is the set of pixels $p$ for which the translated structural element $S_{p}$ is contained in the image $I$. That is,

$E(I,S)=I\ominus S=\{p\in I\mid S_{p}\subseteq I\}$.

Intuitively, after an erosion operation is performed, the set $E(I,S)$ retains only the positions in the image for which all pixels of the translated structural element belong to the object set.

Below we see an example of erosion operation.

Images $I$ can be represented by binary matrices $A$, where we represent $1$ as an object in the image and $0$ as background. To compute the eroded image $I'$, represented by a matrix $A'$ one must check whether for all elements $p\in I$, the equality $A[x][y]=1$ holds for all pixels $s=(x,y)\in S_{p}$.

If it holds, then the pixel $p\in I$ is kept in the image $I'$ and the corresponding element from the matrix $A'$ is set to be equal $1$.

One can see that for each $p=(i,j)\in I$, the entry $(i,j)$ in the eroded matrix $A'$ can be computed as

$A'[i][j]=\prod \limits _{s\in S_{p}}A[s_{x}][s_{y}].$

This computation can be done in an encrypted manner if the encryption scheme is homomorphic with respect to multiplication, like the certSGN scheme.

The dilation operation

The dilation of $I$ with the structural element $S$ is defined as $D(I,S)=I\oplus S=\{p=(x,y)\in \mathbb {Z} ^{2}\mid S_{p}\cap I\neq \emptyset \}.$

That is, the dilation retains all the pixels $p$ for which the translated structured element $S_{p}$ intersects non-trivially with the image. Below we see the effects of a dilation with a structured element $S$.

Using the notations in the previous subsection, the entries of a binary matrix associated to a dilated image can be computed from the following equality.

$1-A'[i][j]=\prod _{s\in S_{p}}(1-A[s_{x}][s_{y}]).$

This expression can be simplified if one represents binary images as matrices whose $0$ entries represent objects and $1$ represents background.

Other morphological operations

Using the primitives described above one can perform edge dection, as the $\mathbb {F} _{2}$ difference between the initial image and its eroded version. This is described in the image below.

Opening and closing are other morphological operations.

The opening of $I$ with $S$ is performed in the following way:

1. $I_{0}$ is the erosion of $I$ by $S$.

2. Let $S'=\{-s\mid s\in S\}$ the symmetric of $S$ with respect to the origin (its center).

3. The opening $I'$ is the dilation of $I_{0}$ with the structural element $S'$.

The erosion carried out first eliminates the noise and shrinks the object shape, while the next dilation expands the object back, but without the eliminated noise.

A similar operation, the closing of $I$ with $S$ is performed as:

1. $I_{0}$ is the dilation of $I$ by $S$.

2. $S'$ is the symmetric of $S$ defined above.

3. The closing $I$ is the erosion of $I_{0}$ with the structural element $S'$.

Experiments and conclusions

The authors used an implementation of the certSGN encryption scheme to compute morphological primitives over an encrypted image, and also compared their results with other LWE based schemes such as BGV (HElib) and BFV (Microsoft SEAL).

The experiments show that for certian structural elements the certSGN implementation presents optimizations of 300x up to 10000x in execution times of morphological primitives and in 2.87x to 55x in memory optimization over the LWE schemes. The details of the experiments can be found in the paper.