# Learning to Detect Touches on Cluttered Tables

Norberto Adrian Goussies Kenji Hata Shruthi Prabhakara Abhishek Amit∗
Tony Aube∗ Carl Cepress∗ Diana Chang∗ Li-Te Cheng∗
Horia Stefan Ciurdar∗ Mike Cleron∗ Chelsey Fleming∗ Ashwin Ganti∗
Divyansh Garg∗ Niloofar Gheissari∗ Petra Luna Grutzik∗ David Hendon∗
Daniel Iglesia∗ Jin Kim∗ Stuart Kyle∗ Chris LaRosa∗
Roman Lewkow∗ Peter F McDermott∗ Chris Melancon∗ Paru Nackeeran∗
Neal Norwitz∗ Ali Rahimi∗ Brett Rampata∗ Carlos Sobrinho∗
George Sung∗ Natalie Zauhar∗ Palash Nandy  Google Research, USA
∗Alphabetical Order

###### Abstract

We present a novel self-contained camera-projector tabletop system with a lamp
form-factor that brings digital intelligence to our tables. We propose a real-
time, on-device, learning-based touch detection algorithm that makes any
tabletop interactive. The top-down configuration and learning-based algorithm
makes our method robust to the presence of clutter, a main limitation of
existing camera-projector tabletop systems. Our research prototype enables a
set of experiences that combine hand interactions and objects present on the
table. A video can be found at https://youtu.be/hElC_c25Fg8.

##  1 Introduction

Figure 1: Clutter comparison. (a) Tabletops in previous papers. (b) Our
tabletop. (c) Typical tabletop. (d) Tabletops discussed in this paper.

Interactive tabletop projectors are gaining attention, with many commercial
and research prototypes being developed [29, 33, 4, 22]. To provide a natural
input mechanism, many of these tabletop projectors emulate a touchscreen by
recognizing when human fingers contact the table surface. The most common
approach commercial devices follow is to project a sheet of infrared light
just above the surface while watching for fingertips to intercept the light
from just above. For example, the Canesta device [24] is one of the first
commercial devices to implement this approach.

To extend the interactions supported by these systems, several computer vision
based approaches have been proposed [29, 30, 16, 33]. These touch systems
require the table surface to be mostly empty, which is not a common case.
Therefore, the adoption of interactive tabletop projectors has been limited
due to their inability to address challenges posed by the presence of clutter
on a tabletop. Figure 1 illustrates a typical tabletop set up. In addition,
these systems generally require expensive sensors or desktop machines with
high-end GPUs and CPUs. Thus, these approaches are impractical for commercial
devices that need to be robust to clutter on the table, portable, self-
contained, low-cost, and have limited computational resources.

In this paper we present a novel, low-cost, portable, and self-contained
tabletop projector prototype that has a lamp form factor (see Figure 2). To
interact with the system we propose a novel real-time vision-based algorithm
that is based on encoding-decoding networks with skip connections [19, 12,
17]. Our algorithm uses stereo infrared cameras to detect touches and in-air
hand gestures. The overhead cameras in the lamp make our prototype less prone
to occlusions, thereby overcoming an important limitation in most commercial
interactive tabletop projectors. By being robust to clutter and occlusion, our
system enables us to build interactive tabletop projector experiences on
realistic scenarios. To our knowledge, this is the first time an end-to-end
learning-based approach has been proposed to detect when a finger is touching
the table.

##  2 Related Work

There is a large body of work on touch detection. The problem has received
attention since it has been a key component for interactive-tabletops [33, 30,
29], semi-transparent screens [28], and wearable devices [35, 7].

A wide range of cues have been explored to detect touches on un-instrumented
surfaces. Given the difficulty of the problem, initial approaches [26, 28]
proposed relying on microphones to detect touches. Later, PlayAnywhere [29]
proposed an algorithm based on the analysis of shadows produced by the IR
illuminant. PlayAnywhere’s front-facing configuration helps to overcome many
occlusion problems, however shadows are not easy to detect on a cluttered
table.

Many approaches have been proposed to exploit the geometrical properties that
relate stereo cameras. Wren et al [32] proposed a technique based on
precomputed disparity maps, which can detect when a fingertip is between an
upper and lower plane without computing the entire depth range. TouchLight
[28] uses the homography induced by a plane to detect when objects are near a
semi-transparent screen. Visual Touchpad [14] detects the fingertips in each
camera independently and applies a disparity threshold to decide if the finger
is touching the touch-pad. Finally, Agarwal et al [1] proposed an algorithm
that aggregates stereo cues from several points at each fingertip by computing
the intersection of the finger plane and the screen plane.

Figure 2: Lamp form factor.

Compared with our approach, [32, 14] use very low-resolution images and [1]
achieves only 20 fps. Most of the approaches mentioned above are generally
divided in two stages, first they detect the fingertip and then they use a
heuristic based on the stereo images to decide if the fingertip is touching
the surface. Our end-to-end learning-based approach finds the fingertip
position and decides if the fingertip is touching the table in a single step.
Our novel method runs at 30 fps, is very accurate, and leverages the
geometrical properties of stereo cameras.

A recent trend is to leverage depth sensors to detect touches. Wilson et al.
[30] explores a method to detect touches in which a static background model is
computed during initialization. Posterior depth images are processed to
identify areas with pixels that have a depth value similar to the static
background model. Murugappan et al. [16] proposes to further refine the
conditions to detect touches in [30] by using connected component analysis to
discard blobs based on their area. Additionally, a novel method for touch-
gesture detection is proposed. Xiao et al. [33] combines depth and infrared
streams to obtain precise finger boundaries, then examines a small depth pixel
neighborhood around the fingertip to decide if it is touching the table. Their
method has a fallback mode that allows them to cope with limited clutter
conditions. Cadena et al. [2] detects the arms using k-means and, then finds
the fingertips and refines their position using IR edge detection. OmniTouch
[7] finds fingers by searching for cylinders in the depth image and performing
flood filling to detect if it is touching a surface. Desktopography [34] adds
additional constraints to [7] to reject finger-like objects. Chai et al. [4]
follows [30] but the fingertips are found using a neural network. Fujinawa et
al. [6] proposes a system in which interactions are driven by hand postures.
The closest approaches to our work use neural networks to detect fingertips or
analyze hand pose [6, 4]. The main difference to our approach is that they
rely on heuristics based on depth signals to decide if a fingertip is touching
the table.

A common limitation of these approaches is that they are not very precise in
disambiguating hover from touch. The main issue is that there are assumptions
about finger thickness. This assumption can be easily violated depending on
the angle the finger touches the surface. Additionally, finger thicknesses
vary depending on the user. In contrast, our approach can learn how to handle
these situations from the data. By using stereo pair images, our neural
network can pick additional cues other than just the ones provided by the
depth information. Finally, it is important to note that even when depth
sensors have become widely available and they are not very expensive, they are
significantly more expensive than the stereo camera pair we use.

##  3 Configuration

Figure 2 shows our lamp prototype which has two parts, a smart headlamp
attached to a normal lamp base. The prototype is designed to sit on a flat
surface such as a table or desk. The head is 48 cm above the surface and
contains a vision module, projector and the main system board where all the
computing happens. Apart from the power cable connected to the base, there are
no other cables or hardware required to use the lamp.

The vision module has two 1 MP infrared cameras (OV9282), with a 5cm baseline,
one infrared flood illuminator, and one 13MP RGB camera. Similar to other
camera-projector systems [29] we remove the projected graphics from the
infrared images using an infrared band-pass filter mounted in front of the
infrared cameras. In addition, we use BELICE dot emitters to add texture to
the scene to facilitate finding correspondences between the infrared cameras.
The vision module is similar to the one in the RealSense 435, but has a lower
cost since we do not need a dedicated ASIC to compute depth.

Our system has a projector based on the TI DLP4500/6401. The projector has a
1280x800 resolution and at 48cm over the surface has 71cm diagonal. The main
board has a Qualcomm 605 System-on-Chip (SoC), which supports up to three
cameras and can execute neural network inference on a built-in hardware
accelerator (Hexagon 685 DSP). The Qualcomm 605 processing capabilities are
similar to the ones of a Google Pixel 2. The prototype runs Android Oreo and
all the hand-user interaction events are recognized and dispatched to the OS
as if they were coming from an input device. The total cost of the device is
below the price of most smartphones.

##  4 Stereo Hand interaction

The stereo hand interaction module processes the frames from the two infrared
cameras to detect touches and in-air hand gestures. We use a two step process
to detect touches, first we detect the hands on the images from left camera,
then for each detected hand we use the stereo image pair to determine both the
fingertip locations and the subset that are touching the tabletop.

###  4.1 Calibration and Table model

We perform a one-time calibration that estimates the intrinsic and extrinsic
parameters for all the cameras in the device, using a chessboard target and
the method described in [36]. Then, we find the mapping between the projector
and the RGB camera by projecting a sequence of gray code patterns onto the
table [15].

Our touch detection algorithm requires highly accurate estimation of the
distance between the infrared cameras and the surface the user interacts with.
A common solution when using depth sensors is to clear the surface and build a
static histogram using the first frames of the depth sensor [4, 30]. Since
requesting the user to empty the table can be cumbersome, some methods
maintain a rolling window of the depth data [6, 33].

However, we do not compute a depth map and instead infer the surface plane
even through clutter, following a similar process to [28, 1, 5]. We capture
the chessboard calibration pattern when it is lying flat on the table and use
all chessboard calibration corners to estimate the homography relating the
undistorted infrared images. Finally, we compute disparity maps
$D_{x},D_{y}\in\mathbb{R}^{W\times H}$ that maps points on the plane of the
table from the left camera to the right camera. Figure 3 illustrates the image
before and after the homography is applied.

Figure 3: Parallax induced by a plane. First row: fingertip touching the
table. Second row: fingertip hovering a few millimeters above the table. Last
row: fingertip hovering a few centimeters above the table. First column:
images from the left camera. Middle column: right images remapped using
$D_{x},D_{y}$. Last column: left and remapped images blended together.

###  4.2 Hands Detection

The first step in our hand interaction algorithm is to detect hands in re-
scaled frames from the left camera
$I^{\textrm{small}}_{\textrm{left}}\in\mathbb{R}^{\frac{W}{F}\times\frac{H}{F}}$,
where $W$ is the width of the image, $H$ is the height, and $F$ is the re-
scale factor. Since the purpose of this step is to be able to obtain a rough
estimate of the hands position in the scene we heavily reduce the resolution
of the left image in this step using $F=8$.

Following [37], our neural network predicts a bounding box for each hand. Let
$b=(x_{1},y_{1},x_{2},y_{2})$ be the coordinates of the hand bounding box
corners. The center of the bounding box is given by
$p=\left(\frac{x_{1}+x_{2}}{2},\frac{y_{1}+y_{2}}{2}\right)$, and the size of
the bounding box is $s=(x_{2}-x_{1},y_{2}-y_{1})$.

Our neural network estimates $\hat{Y}\in[0,1]^{\frac{W}{F\times
R}\times\frac{H}{F\times R}}$, where $R$ is the output stride. The heatmap
$\hat{Y}$ predicts the center of the bounding box. When
$\hat{Y}_{\tilde{p_{x}},\tilde{p_{y}}}=1$ the neural network is predicting a
bounding box with center
$(\tilde{p_{x}},\tilde{p_{y}})=\left(\lfloor\frac{p_{x}}{R\times
F}\rfloor,\lfloor\frac{p_{y}}{R\times F}\rfloor\right)$ and when
$\hat{Y}_{\tilde{p_{x}},\tilde{p_{y}}}=0$ it is predicting that there is no
bounding box. During training, for each low resolution bounding box center
$(\tilde{p}_{x},\tilde{p}_{y})$, we create the corresponding heatmap
$Y\in[0,1]^{\frac{W}{F\times R}\times\frac{H}{F\times R}}$ using a Gaussian
kernel
$Y_{x,y}=\frac{1}{Z}\exp\left(-\frac{(x-\tilde{p}_{x})^{2}+(y-\tilde{p}_{y})^{2}}{2\sigma^{2}}\right)$,
where $\sigma^{2}$ depends on the size of the bounding box [25] and $Z$ is a
constant to normalize the heatmap. We define the loss for the center of the
bounding box as:

$L_{\textrm{center}}=\frac{-1}{N}\sum_{x,y}\left\\{\begin{array}[]{lr}\left(1-\hat{Y}_{xy})^{\alpha}\log(\hat{Y}_{xy}\right)&\textrm{if
}Y_{xy}=1\\\
\left(1-Y_{xy})^{\beta}\hat{Y}_{xy}^{\alpha}\log(1-\hat{Y}_{xy}\right)&\textrm{otherwise}\end{array}\right.$
(1)

where $\alpha$ and $\beta$ are hyper-parameters of the focal-loss [13] and $N$
is the number of hands in the image.

In addition, our neural network estimates
$\hat{S}\in\mathbb{R}^{\frac{W}{F\times R}\times\frac{H}{F\times R}\times 2}$.
We use $\hat{S}$ to regress the size of the bounding box, the value at the
center of the $\hat{S}$ is the predicted size of the bounding box. We define
the loss for the size as:

$L_{\textrm{size}}=\left|\hat{S}_{p_{x},p_{y}}-s\right|.$ (2)

The overall training objective is for the network is:

$L_{\textrm{hand}}=L_{\textrm{center}}+\lambda_{\textrm{size}}L_{\textrm{size}}$
(3)

where $\lambda_{\textrm{size}}$ is used to change the importance
$L_{\textrm{size}}$ in the overall training objective. In our experiments we
fix $\lambda_{\textrm{size}}=0.1$.

The neural network architecture is shown in Figure 4. This is a fully
convolutional neural network in which all layers are followed by a batch
normalization operation [9] and a ReLU non-linearity (except for the last one)
and has an encoder-decoder architecture with skip connections[19, 12, 17].
Fast inference is central to our design and we have found that our model is
robust to many design choices. We experimented with more sophisticated blocks
[8] and observed minimal improvements.

The encoding layers of the network interleaves convolutional layers (with
point-wise non-linearities) and max-pooling layers to compute semantically
meaningful features. The pooling layers reduce the spatial resolution of the
features and introduce invariance to small spatial deformations. The decoding
layers of the network increase the feature resolution, using bi-linear up-
sampling and convolution layers [31]. The resulting features are combined with
features from the encoding layers via skip connections. We decided to use
these operations since they can be hardware accelerated. The output heatmaps
$\hat{Y}$ and $\hat{S}$ share the same encoder-decoder network. To produce
each output heatmaps, the features of the encoder-decoder network are passed
through a separate $3\times 3$ convolution.

We use random flips, rotations, brightness changes, and contrast adjustment to
augment our training set. We use Adam [11] and set the learning rate to $5e-4$
to optimize the overall objective from scratch.

Figure 4: Hand detection CNN architecture.

###  4.3 Touch Detection

Deep neural network techniques to estimate hand pose [25] and person pose [17]
have gained popularity due to the impressive performance they have shown. RGB
[38, 3] and depth [25] are the most common input modalities. The number of
joints to represent hand pose vary depending on the datasets that are used for
evaluation; [25] uses 14 joints, [23] uses 16 joints, and [20] uses 21 joints.
The predicted joints are either represented using heatmaps or using their 2D
coordinates.

In our system, instead of predicting the full hand pose we train a neural
network that only predicts the position of the fingertips
$k^{1},\ldots,k^{5}\in\mathbb{R}^{2}$ and the palm $k^{6}\in\mathbb{R}^{2}$,
which are the only keypoints that we need. Our neural network estimates three
heatmaps:
$\hat{K}^{\textrm{fingertips}}\in[0,1]^{\frac{W}{Q}\times\frac{H}{Q}}$ encodes
the position of all the fingertips in the hand,
$\hat{K}^{\textrm{touch}}\in[0,1]^{\frac{W}{Q}\times\frac{H}{Q}}$ encodes
which fingertips are touching the table, and
$\hat{K}^{\textrm{palm}}\in[0,1]^{\frac{W}{Q}\times\frac{H}{Q}}$ encodes the
position of the palm, where $Q$ is the output stride for the neural network.

During training, we remap the $I_{\textrm{right}}\in\mathbb{R}^{W\times H}$
using linear interpolation:

$I_{\textrm{remapped}}=I_{\textrm{right}}(D_{x}(x,y),D_{y}(x,y)).$ (4)

We feed $I_{\textrm{remapped}}$ and $I_{\textrm{left}}$ to our neural network.
As in the previous section, we use Gaussian kernels to create the heatmaps.
For the fingertips heatmap $K^{\textrm{fingertips}}$ we use only one heatmap
to encode the position of all the fingertips since we are not interested in
which specific finger is touching:

$K^{\textrm{fingertips}}_{x,y}=\max_{i\in{1,\ldots,5}}\frac{1}{Z_{i}}\exp\left(-\frac{(x-k^{i}_{x})^{2}+(y-k^{i}_{y})^{2}}{2\sigma^{2}}\right)$
(5)

where $Z_{i}$ is a normalizing constant and $\sigma$ is a fixed parameter for
all keypoints. We create the touching heatmap $K^{\textrm{touch}}$ in the same
way we create the fingertips heatmap $K^{\textrm{fingertips}}$ but we only
consider the fingertips that are touching the table. If a keypoint is not
visible we ignore it when we create the heatmaps. We use the Mean Square Error
(MSE) loss [25, 17] to compare the predicted heatmaps with the ground-truth as
training objective:

$\begin{array}[]{ll}L&=\frac{1}{W\times
H}\sum_{x,y}\left(K^{\textrm{fingertips}}_{x,y}-\hat{K}^{\textrm{fingertips}}_{x,y}\right)^{2}\\\
&+\frac{1}{W\times
H}\sum_{x,y}\left(K^{\textrm{palm}}_{x,y}-\hat{K}^{\textrm{palm}}_{x,y}\right)^{2}\\\
&+\frac{1}{W\times
H}\sum_{x,y}\left(K^{\textrm{touch}}_{x,y}-\hat{K}^{\textrm{touch}}_{x,y}\right)^{2}.\end{array}$
(6)

During inference, for each detected hand bounding box $b$, we crop the left
image $I^{b}_{\textrm{left}}$ and use the disparity maps $D_{x},D_{y}$ to
remap the corresponding bounding box in the right image
$I^{b}_{\textrm{remapped}}$. We feed $I^{b}_{\textrm{left}}$ and
$I^{b}_{\textrm{remapped}}$ images to our neural network. Then, we decode the
fingertip positions $\hat{k}^{1},\ldots,\hat{k}^{5}$ by finding the local
maximas (and using non-maximal suppression) in
$\hat{K}^{\textrm{fingertips}}$. Once we have the local maxima coordinates we
fit a 2D Gaussian function to obtain the coordinates with sub-pixel precision.
To decide if a fingertip $i$ is touching the table, we take the maximum value
of $\hat{K}^{\textrm{touch}}$ in a window centered around the fingertip
position $\hat{k}^{i}$.

Figure 5 shows the neural network architecture for this stage, which is
similar to the neural network to detect hands but with more decoding layers.
The additional decoding layers enable us to obtain spatially accurate
positions for the predicted keypoints. It is important to note that, since our
neural network is fully convolutional, the image sizes that we use to train
the network do not need to be the same as the ones that we use when we run
inference. We train using full stereo images but we feed cropped stereo images
during inference.

Figure 5: Fingertip, palm, and touch detection CNN architecture.

The main reason our neural network can estimate $\hat{K}^{\textrm{touch}}$ is
that it can exploit geometrical constraints and other cues. A fingertip
touching the table should have a similar position in $I_{\textrm{left}}$ and
$I_{\textrm{remapped}}$. The further away a fingertip is from the table, the
further apart its position is in $I_{\textrm{left}}$ and
$I_{\textrm{remapped}}$. Figure 3 illustrates this property. By using a
learning-based approach that recognizes when a finger is touching the table,
we are able to successfully handle many cases that were found to be difficult
in previous heuristic-based approaches [35, 4]. For example, when a finger is
touching the table perpendicularly, heuristics that use connected components
struggle to detect touches because the connected component that the finger
creates is small. However, our system easily handles this case.

###  4.4 Touch Dataset

To train the touch detection CNN we need a dataset with accurate labels of
when the fingertips are touching the table. The main challenge is that
annotating whether a fingertip is touching the table using stereo images is
time consuming and error prone. Therefore, when we collected the dataset we
requested the participants to perform tasks in which we knew which fingers
were touching the table and which fingers were hovering over the table.

We collected 50 thousand stereo image pairs from 13 volunteers and 3 different
devices. Each volunteer was requested to perform 14 tasks for 20 seconds each.
The tasks consisted of moving one hand around the projected area while
performing a gesture with a pre-determined subset of fingers from that hand.
For example, some of the gestures were: touch while pinching with the thumb
and index finger, touch while performing two finger scroll, and move the hand
above the table without touching it. Also, we requested the participants to
hover their hand above the table but without touching it, while performing
similar gestures, in order to obtain samples that can help us learn an
accurate touch detector. We tried to emulate realistic tabletop scenarios by
introducing a variety of clutter into the scene. Between different tasks, we
modified the scene by adding or removing objects, as well as changing the
illumination or the surface material. After collecting the stereo images we
annotated the keypoint locations on the left image.

###  4.5 Multi-Touch Tracking

Our system can detect up to two hands and ten contact points simultaneously.
Given two consecutive frames at time $t$ and $t+1$, and the detected contact
points set $D_{t}$ and $D_{t+1}$ in each frame, we match the contact points
$p\in D_{t+1}$ to $q\in D_{t}$ if the following two conditions hold
simultaneously:

$q=\underset{q^{\prime}\in D_{t}}{\mathrm{argmin}}\|p-q^{\prime}\|_{2}^{2}$
(7) $p=\underset{p^{\prime}\in
D_{t+1}}{\mathrm{argmin}}\|q-p^{\prime}\|_{2}^{2}$ (8)

When this happens, we report a drag event if the $\|p-q\|_{2}^{2}>2.5$ mm.
When a contact point $p\in D_{t+1}$ does not match to any contact point in
$D_{t}$, we report the contact point $p$ as a touch down event to the Android
OS. Similarly, when a contact point $q\in D_{t}$ does not match to any contact
point in $D_{t+1}$ nor $D_{t+2}$ we report a touch up event. By reporting
events to the Android OS, and keeping a stable fingertip identity among
frames, many of the Android gestures (one or two finger drag, long press,
pinch-zoom, etc…) work well, allowing us to use most Android applications
without modifications.

###  4.6 In-Air Hand Gesture Detection

We use in-air gestures to replace the Android navigation bar. Our system
detects two in-air gestures: back and forward, as depicted in Figure 6. The
gestures are mapped to the back and overview buttons in the Android navigation
bar. In order to detect in-air gestures we implemented heuristics based on
speed and directionality of the user’s hand motion.

Figure 6: Navigation gestures.

##  5 Implementation Details

The CNNs in the system are run on Qualcomm’s DSP using TF-Lite’s hexagon
delegate and are trained using quantization-aware training [10]. The neural
network in the first stage takes 6ms to run and the one in the second stage
takes 12ms per hand, we process two hands at most and ignore the rest of the
hands in the scene. By offloading inference to Qualcomm’s DSP, and using only
one slow SoC core for the touch detection algorithm, we can efficiently
distribute the compute workloads on the device. The big cores and most of the
small cores on the SoC are reserved for running the Android operating system
and applications.

Figure 7: Scatterplot of touch points, plotted with 95% confidence intervals.

##  6 Experiments

We conducted experiments with our system through an evaluation of touch
accuracy, latency measurements, dealing with failure cases, and informal
testing with various experiences.

###  6.1 Touch Accuracy

To analyze the spatial and touch accuracy of the system we performed a user
study similar to the cross-hair targeting study described in [35]. We
requested 12 participants to tap once on the cross-hair targets projected on
the table. A total of 16 cross-hair targets were projected. All users were
given a training period of 10 minutes.

The targets were placed in a $4\times 4$ grid evenly spaced across a $20\times
20$ cm square area. The targets were displayed in random order, one at the
time, for three seconds each. The system recorded all the touch events. To
capture diversity of interactions, we evaluated under two different scenarios,
with the user seated in a chair, and with the user standing. Clutter was
present on the table, but not in places where the target was shown (See Figure
8).

Figure 8: Example of the cross-hair target task while clutter is present on
the table.

Across the 12 participants, we obtained 384 cross-hair trials. Of these, 10
(2.6%) reported no touch contact, 370 (96.35%) exactly one contact and 4
(1.04%) more than one contact. In the event of multiple detected contacts, we
decided to ignore the trial for the rest of the analysis. We found no
significant spatial or touch accuracy differences between the user in seated
or standing position. Figure 7 plots the touch points and the 95% confidence
intervals for the seated and standing positions. 98% of touch interactions
were detected within 1 cm of the actual target. The average Euclidean error is
0.45cm.

###  6.2 Comparison with Existing Approaches

| Camera | Sensor | Avg. Euclidean | Touch Detection | Clutter | Hardware | Cost
---|---|---|---|---|---|---|---
| Distance | Type | Error | Rate | Robustness |  |
Wilson [30] | 75cm | depth | 7mm | N/A | low | Desktop machine | medium
|  | structured-light |  |  |  | CPU |
Xiao et al [33] | 160cm | IR+depth | 4.8mm | 99.3% | medium | Desktop machine | medium
|  | time-of-flight |  |  |  | CPU |
Chai et al [4] | N/A | depth | 2.5mm | N/A | low | Desktop machine | high
|  | structured-light |  |  |  | high-end GPU |
Xiao et al [35] | 51cm | IR+depth | 5mm | 72% | medium | HoloLens | low
table condition |  | time-of-flight |  |  |  |  |
Ours | 48cm | stereo IR | 4.9mm | 96.35% | high | Qualcomm | low
|  | structured-light |  |  |  | 605 SoC |
Table 1: Comparison of touch approaches with ours.

There are many touch detection algorithms that have been proposed in the past.
Table 1 shows a comparison between our approach and closest previous systems.
We compare with approaches in which the setup is similar to our top-view
interactive tabletop projector system. There is a wide variety of setups,
costs, camera distances, and results. Our approach achieves the best touch
detection rate of the low cost systems and it is the most robust to clutter.

To obtain a rough cost estimate for each approach we considered that desktop
machines are more expensive than embedded devices and that high-end GPUs are
extremely expensive. Time-of-flight depth sensors are more expensive than
structured-light depth sensors. Stereo infrared cameras with structured-light
are the cheapest alternative.

To analyze the clutter robustness of each system we considered whether the
method supports dynamic backgrounds and, if it does, how complex the scene can
be. For example, [33, 35] have problems to detect touches in the presence of
documents like the one in Figure 11 since it is very likely that an overfill
error gets triggered.

###  6.3 Latency

We measured the end-to-end latency of the system, defined as the time between
the physical interaction and the first frame that incorporates it. This
measurement includes the time required to capture the frames, process them and
dispatch the OS event.

To measure the end-to-end latency of the system, we positioned a high-speed
camera near lamp base and we recorded 30 tap interactions with our system.
Figure 9 shows the latency distribution of the system. We observed a mean
latency of our touch system of $98$ ms and a mode of $91$ ms. Out of these 98
ms, 31 ms are spent in the touch system. The remaining 67 ms are spent in the
rest of pipeline and there are many opportunities for optimizing it.

As mentioned in [35] latency is crucial for touch inputs and is more easily
noticed in large displays because users can move their hands faster. Our
latency compares favorably to the 180 ms latency reported by [35] and even
some touchscreen latencies, which are in the (50-200ms) range [18].

Figure 9: Touch system latency distribution.

###  6.4 Failure Cases

We evaluated our system on a comprehensive set of use-cases. While we have
significantly improved upon the existing use-cases, our system still fails in
a few edge cases. One such example is objects resembling a finger can
occasionally trigger false positives. We could in the future augment the
models with RGB images (in addition to infrared) to help disambiguate these
cases. Another failure case is miss-detection when user touches are at the
edge of camera’s field of view. The main reason is that the hand is only
partially visible in the infrared cameras. This could be mitigated by using a
camera with a field of view that is wider than area of interest on a tabletop.

Figure 10: Sandbox demo application.

###  6.5 Sandbox

We developed a demo application, Sandbox, that allows the user to choose from
different dynamic backgrounds that are projected on toys to augment them with
animations, see Figure 10. The toys can be moved through the projected area
and animation will track them. The example shows a moving animated race track
background, giving the illusion that the toy car is moving. The background can
react to the position of the detected toy cars and present different
obstacles, turning the table into a race game with real toys. In this example,
we also project animated smoke behind the car, amplifying the illusion of
movement.

In order to detect when a new toy is present, the Sandbox application detects
when the user’s hand enters or leaves the projected area. By comparing the
frames associated to those events, we determine if a new object has been
placed on the table. We then use the frame the toy is detected in as a
reference to track it in following frames using optical flow.

###  6.6 Desktop

In this demo application we explore interactions with paper documents that are
on the table. In the past, many systems have explored these type of
interactions, for example Digital Desk [27] and Live Paper [21], project
information onto physical objects. In our application, we assume that we know
the structure of the document and we attach a user interface to it, making the
document interactive. The buttons allow the user to act on the information
presented by the document when they are touched. For example, tapping a phone
number could trigger the device to call the number. Tapping on the money due
could trigger the device to pay the bill. By tracking the document, using
optical flow, the user can move it through the table and have the illusion
that the graphical user interface is attached to the document. See Figure 11
for an example of a document that we can detect, track, and project a
graphical user interface on.

Figure 11: Desktop demo application.

##  7 Conclusions

In this paper we introduced a new interactive projector-camera prototype with
a lamp form factor. The prototype has a novel real-time algorithm that can
detect touches and in-air hand gestures. The low-cost prototype uses a middle-
tier SoC that is similar to a Google Pixel 2 smartphone and has a vision
module that is similar to the RealSense D435. The novel real-time algorithm
leverages the hardware acceleration SoC capabilities, that are present in many
smartphones. The low-cost prototype is robust to clutter which are important
limiting factors for the adoption of interactive tabletop projectors. We
showed how the novel prototype enables rich experiences in which the user can
interact with the tabletop and objects of interests in realistic tabletop
scenarios.

##  8 Acknowledgements

We would like to thank Rahul Sukthankar and Jay Yagnik for their support and
advice. We would also like to thank John Fitch, Eric Cuong Nguyen, Kai Yick,
and Mark Zarich for their assistance with hardware prototyping.

## References

  * [1] Agarwal, A., Izadi, S., Chandraker, M., and Blake, A. High precision multi-touch sensing on surfaces using overhead cameras.  In Second Annual IEEE International Workshop on Horizontal Interactive Human-Computer Systems (TABLETOP’07) (2007), IEEE, pp. 197–200.
  * [2] Cadena, A., Carvajal, R., Guamán, B., Granda, R., Peláez, E., and Chiluiza, K. Fingertip detection approach on depth image sequences for interactive projection system.  In 2016 IEEE Ecuador Technical Chapters Meeting (ETCM) (2016), IEEE, pp. 1–6.
  * [3] Cai, Y., Ge, L., Cai, J., and Yuan, J. Weakly-supervised 3d hand pose estimation from monocular RGB images.  In Proceedings of the European Conference on Computer Vision (ECCV) (2018), pp. 666–682.
  * [4] Chai, Z., and Shilkrot, R. Enhanced touchable projector-depth system with deep hand pose estimation.  arXiv preprint arXiv:1812.11090 (2018).
  * [5] Chan, L.-W., Kao, H.-S., Chen, M. Y., Lee, M.-S., Hsu, J., and Hung, Y.-P. Touching the void: Direct-touch interaction for intangible displays.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (2010), ACM, pp. 2625–2634.
  * [6] Fujinawa, E., Goto, K., Irie, A., Wu, S., and Xu, K. Occlusion-aware hand posture based interaction on tabletop projector.  In The Adjunct Publication of the 32nd Annual ACM Symposium on User Interface Software and Technology (2019), ACM, pp. 113–115.
  * [7] Harrison, C., Benko, H., and Wilson, A. D. OmniTouch: Wearable multitouch interaction everywhere.  In Proceedings of the 24th annual ACM symposium on User interface software and technology (2011), pp. 441–450.
  * [8] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2016), pp. 770–778.
  * [9] Ioffe, S., and Szegedy, C. Batch normalization: Accelerating deep network ttraining by reducing internal covariate shift.  arXiv preprint arXiv:1502.03167 (2015).
  * [10] Jacob, B., Kligys, S., Chen, B., Zhu, M., Tang, M., Howard, A., Adam, H., and Kalenichenko, D. Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2018), pp. 2704–2713.
  * [11] Kingma, D. P., and Ba, J. Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980 (2014).
  * [12] Lin, T.-Y., Dollár, P., Girshick, R., He, K., Hariharan, B., and Belongie, S. Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2017), pp. 2117–2125.
  * [13] Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P. Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision (2017), pp. 2980–2988.
  * [14] Malik, S., and Laszlo, J. Visual touchpad: A two-handed gestural input device.  In Proceedings of the 6th international conference on Multimodal interfaces (2004), pp. 289–296.
  * [15] Moreno, D., and Taubin, G. Simple, accurate, and robust projector-camera calibration.  In 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission (2012), IEEE, pp. 464–471.
  * [16] Murugappan, S., Elmqvist, N., Ramani, K., et al. Extended multitouch: Recovering touch posture and differentiating users using a depth camera.  In Proceedings of the 25th annual ACM symposium on User interface software and technology (2012), ACM, pp. 487–496.
  * [17] Newell, A., Yang, K., and Deng, J. Stacked hourglass networks for human pose estimation.  In European conference on computer vision (2016), Springer, pp. 483–499.
  * [18] Ng, A., Lepinski, J., Wigdor, D., Sanders, S., and Dietz, P. Designing for low-latency direct-touch input.  In Proceedings of the 25th annual ACM symposium on User interface software and technology (2012), pp. 453–464.
  * [19] Pinheiro, P. O., Lin, T.-Y., Collobert, R., and Dollár, P. Learning to refine object segments.  In European Conference on Computer Vision (2016), Springer, pp. 75–91.
  * [20] Qian, C., Sun, X., Wei, Y., Tang, X., and Sun, J. Realtime and robust hand tracking from depth.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2014), pp. 1106–1113.
  * [21] Robertson, C., and Robinson, J. Live paper: video augmentation to simulate interactive paper.  In Proceedings of the seventh ACM international conference on Multimedia (Part 2) (1999), pp. 167–170.
  * [22] Sony.  Sony Xperia Touch.  https://www.sonymobile.com/us/products/smart-products/xperia-touch/, 2018\.  [Online; accessed 19-Dec-2019].
  * [23] Tang, D., Jin Chang, H., Tejani, A., and Kim, T.-K. Latent regression forest: Structured estimation of 3d articulated hand posture.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2014), pp. 3786–3793.
  * [24] Tomasi, C., Rafii, A., and Torunoglu, I. Full-size projection keyboard for handheld devices.  Communications of the ACM 46, 7 (2003), 70–75.
  * [25] Tompson, J., Stein, M., Lecun, Y., and Perlin, K. Real-time continuous pose recovery of human hands using convolutional networks.  ACM Transactions on Graphics (ToG) 33, 5 (2014), 169.
  * [26] Wellner, P. The DigitalDesk calculator: Tangible manipulation on a desktop display.  In Proceedings of the 4th annual ACM symposium on User interface software and technology (1991), pp. 27–33.
  * [27] Wellner, P. Interacting with paper on the digitaldesk.  Communications of the ACM 36, 7 (1993), 87–96.
  * [28] Wilson, A. D. Touchlight: An imaging touch screen and display for gesture-based interaction.  In Proceedings of the 6th international conference on Multimodal interfaces (2004), ACM, pp. 69–76.
  * [29] Wilson, A. D. Playanywhere: A compact interactive tabletop projection-vision system.  In Proceedings of the 18th annual ACM symposium on User interface software and technology (2005), ACM, pp. 83–92.
  * [30] Wilson, A. D. Using a depth camera as a touch sensor.  In ACM international conference on interactive tabletops and surfaces (2010), ACM, pp. 69–72.
  * [31] Wojna, Z., Uijlings, J. R., Guadarrama, S., Silberman, N., Chen, L.-C., Fathi, A., and Ferrari, V. The devil is in the decoder.  In BMVC (2017).
  * [32] Wren, C., and Ivanov, Y. Volumetric operations with surface margins.  Computer Vision and Pattern Recognition: Technical Sketches (2001).
  * [33] Xiao, R., Hudson, S., and Harrison, C. DIRECT: Making touch tracking on ordinary surfaces practical with hybrid depth-infrared sensing.  In Proceedings of the 2016 ACM International Conference on Interactive Surfaces and Spaces (2016), ACM, pp. 85–94.
  * [34] Xiao, R., Hudson, S., and Harrison, C. Supporting responsive cohabitation between virtual interfaces and physical objects on everyday surfaces.  Proceedings of the ACM on Human-Computer Interaction 1, EICS (2017), 1–17.
  * [35] Xiao, R., Schwarz, J., Throm, N., Wilson, A. D., and Benko, H. MRTouch: Adding touch input to head-mounted mixed reality.  IEEE transactions on visualization and computer graphics 24, 4 (2018), 1653–1660.
  * [36] Zhang, Z. A flexible new technique for camera calibration.  IEEE Transactions on pattern analysis and machine intelligence 22, 11 (2000), 1330–1334.
  * [37] Zhou, X., Wang, D., and Krähenbühl, P. Objects as points.  arXiv preprint arXiv:1904.07850 (2019).
  * [38] Zimmermann, C., and Brox, T. Learning to estimate 3d hand pose from single RGB images.  In Proceedings of the IEEE International Conference on Computer Vision (2017), pp. 4903–4911.


# Museum Painting Retrieval

Òscar Lorente Ian Riera Shauryadeep Chaudhuri Oriol Catalan Víctor Casales
Master in Computer Vision Universitat Autònoma de Barcelona 08193 Bellaterra,
Barcelona, Spain {oscar.lorentec, ianpau.riera, shauryadeep.chaudhuri,
oriol.catalan<EMAIL_ADDRESS>
###### Abstract

To retrieve images based on their content is one of the most studied topics in
the field of computer vision. Nowadays, this problem can be addressed using
modern techniques such as feature extraction using machine learning, but over
the years different classical methods have been developed. In this paper, we
implement a query by example retrieval system for finding paintings in a
museum image collection using classic computer vision techniques.
Specifically, we study the performance of the color, texture, text and feature
descriptors in datasets with different perturbations in the images: noise,
overlapping text boxes, color corruption and rotation. We evaluate each of the
cases using the Mean Average Precision (MAP) metric, and we obtain results
that vary between 0.5 and 1.0 depending on the problem conditions.

###### Index Terms:

Computer vision, Image retrieval, CBIR, Color descriptors, Texture
descriptors, Local descriptors, Key points.

##  I INTRODUCTION

During the last decades, there has been a great increase in the number of
digital image databases in applications such as medical imaging, geographic
information or art collections, among others. For this reason, a method is
needed to access, annotate, and catalog all this data efficiently. This topic
has become a broad area of research interest, and one of the most studied
methods are Content based image retrieval (CBIR) systems.

CBIR is a process in which for a query example image, similar images are
obtained from a larger dataset based on the similarity in the content. There
are different ways to extract content from an image, from descriptors as
simple as color or illuminance histograms to key points and local descriptors.
Today, advances in technology allow the use of advanced techniques such as
machine learning to extract representative features from each image. However,
to understand these concepts it is first necessary to understand traditional
techniques.

In this paper, we present a query by example retrieval system for finding
paintings in a museum dataset using various descriptors and datasets with
different levels of difficulty. Regarding descriptors, we first explore color-
based histograms by testing different color spaces (Gray, RGB) and types of
histograms (1D, 3D, block or multiresolution). On the other hand, we study
texture descriptors such as Histogram of Oriented Gradients (HOG), Discrete
Cosinus Transform (DCT) or Local Binary Patterns (LBP). The names of the
paintings authors are also used as text descriptors. Finally, we analyze the
performance of the CBIR system using the Oriented FAST and Rotated BRIEF (ORB)
feature detection algorithm [1]. Regarding the level of difficulty, there are
datasets with noisy images, overlapping text boxes or more than one painting
per image (which requires us to eliminate the background). The CBIR system
architecture will need more complexity to deal with those cases.

Figure 1: Simplified scheme of the CBIR system.

##  II PROBLEM DEFINITION

Given a museum dataset and a query dataset, for each image in the query
dataset, retrieve the K most similar images in the museum dataset, ordered by
score. To do so, we first extract the features of the images from the museum
dataset using a specific descriptor. Then, for each query image, we extract
the corresponding features and compare them with those of the museum dataset
images. This comparison is carried out using a specific distance as a metric
(e.g. Euclidean). Then, we order the museum images according to these
distances. The museum image closest to the query image is the retrieved image.
In Figure 1 we can see a simplified scheme of the system.

##  III DATA

The museum dataset contains 287 images, each of a different painting and with
a unique label. The author and the name of each painting is also known.

Regarding the query datasets, they all contain 30 images with up to three
paintings per image and a background we must detect and remove. We work with
four datasets of different levels of difficulty. In Figure 2 we can see a
representative image of each dataset.

  * •

Dataset 1: Only one painting per image. All the paintings exist in the museum
database.

  * •

Dataset 2: Up to two paintings per image. In addition, semi-transparent text
boxes are superimposed to the paintings. The text boxes contain the name of
the painter and have different sizes, fonts and locations. All the paintings
exist in the museum database.

  * •

Dataset 3: Similar to dataset 2 but some images have noise and color
corruption (random Hue changes). All the paintings exist in the museum
database.

  * •

Dataset 4: Similar to dataset 3 but some paintings are rotated, and not all of
them are in the museum database.

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)
Figure 2: Representative images from (a) Dataset 1 - Simple case; (b) Dataset
2 - Multiple paintings with text boxes; (c) Dataset 3 - Noisy images; (d)
Dataset 4 - Rotated paintings

##  IV METHOD

In this section we explain in detail the methods used to implement a CBIR
system in each of the datasets exposed in Section III. In each case, an
attempt is made to minimize the impact of dataset disturbances and solutions
and alternatives are presented to deal with them.

###  IV-A Metrics

To compare the query images with the database, different distance metrics were
used:

  * •

Hellinger:

$K\left(h_{1},h_{2}\right)=\sum_{i=1}^{N}\sqrt{h_{1}(i)h_{2}(i)}$ (1)

  * •

Chi-squared:

$D\left(h_{1},h_{2}\right)=\sum_{i=1}^{N}\frac{\left(h_{1}(i)-h_{2}(i)\right)^{2}}{h_{1}(i)+h_{2}(i)}$
(2)

  * •

Intersection:

$I\left(h_{1},h_{2}\right)=\sum_{i}^{N}\min\left(h_{1}(i),h_{2}(i)\right)$ (3)

  * •

Correlation:

$d\left(h_{1},h_{2}\right)=\frac{\sum_{I}\left(h_{1}(I)-\bar{h}_{1}\right)\left(h_{2}(I)-\bar{h}_{2}\right)}{\sqrt{\sum_{I}\left(h_{1}(I)-\bar{h}_{1}\right)^{2}\sum_{I}\left(h_{2}(I)-\bar{h}_{2}\right)^{2}}}$
(4)

where:

$\bar{h}_{k}=\frac{1}{N}\sum_{j}^{N}h_{k}(j)$ (5)

is the mean of the N histograms $h_{k}$.

Additionally, after retrieving the K most similar images from the museum
database, the precision of the system is evaluated using the mAP@K (mean
Average precision at K) metric of the complete query data set:

$AP@K=\frac{\sum_{i=1}^{K}P@i}{K}$ (6)

where P@i is the precision obtained after retrieving i images. In this paper,
the mAP@1 is used to calculate the results.

Finally, to evaluate the method to detect text bounding boxes, we use the mean
Intersection over Union (mIoU). The IoU is computed dividing the area of
overlap between the predicted and groundtruth text boxes by its area of union.

###  IV-B Dataset 1

In the first dataset we have to solve two unknowns: what descriptors to obtain
from the images and how to detect the background.

Figure 3: Background removal steps, from top to bottom: convert image to
grayscale, detect edges with Canny, apply morphological closing, find contours
and fill the masks.

####  IV-B1 Background removal

Before applying query retrieval we need to obtain the paintings (foreground)
from the images. Various techniques can be used to detect and remove the
background from an image. We have implemented a background detector using the
painting contours and morphological operations, which is divided into the
following steps:

  1. 1.

Convert the image to the gray color space

  2. 2.

Use Canny edge detector [2]

  3. 3.

Apply morphological closing with a rectangle

  4. 4.

Find painting contours using [3]

  5. 5.

Fill the mask

In this way, we detect the background accurately and we can extract the
painting of interest from the image. These steps are visually represented in
Figure 3. To evaluate the performance of the background removal system, we
calculate the precision, recall and F1-score comparing the results to the
groundtruth masks.

####  IV-B2 Color Descriptors

The information of an image can be represented by color histograms. Using
different color spaces and dimensionalities of the histogram, we can generate
a great variety of descriptors of the same image. In this paper, we have
tested the system using 1D histograms in the grayscale and 3D histograms in
the RGB, LAB, HSV and YCrCb color spaces. The results are presented in Table
I.

Figure 4: Two different images with the same histogram. TABLE I: mAP comparison between descriptors using different color spaces and metrics on dataset 1. Color Space | Distance Metric
---|---
Correlation | $Chi^{2}$ | Intersection | Hellinger
Gray | 0.23 | 0.22 | 0.09 | 0.26
RGB | 0.33 | 0.16 | 0.21 | 0.53
LAB | 0.39 | 0.22 | 0.23 | 0.49
YCrCb | 0.34 | 0.21 | 0.19 | 0.47
HSV | 0.32 | 0.19 | 0.15 | 0.45

The 3D RGB histograms using the Hellinger distance (see Equation 1) is the
configuration with the best mAP results. Note that we use 3D histograms
instead of concatenating the 1D histograms of each of the 3 channels, as it
represents the number of pixels that have the same R, G and B values at the
same time.

Despite the results, this configuration is not robust, since the lack of
spatial information can lead to paintings erroneously paired, as shown in
Figure 4.

To better preserve spatial information and thus improve the system we use
block-based histograms. This method consists of dividing the image into blocks
and obtaining the color histogram of each of the blocks, which results in a
more representative descriptor.

Figure 5: Representation of a multiresolution histogram, which concatenates
block-based histograms at different levels.

Another alternative is the multiresolution histograms, which allow obtaining a
spatial pyramid representation of the image. Specifically, the block-based
histograms method is applied at different levels, to later concatenate the
histogram at each level (Figure 5).

The results of each method are presented in Table II. We use 16x16 blocks for
the block-based method and 4 levels (1x1, 4x4, 8x8 and 16x16) for the
multiresolution histogram. The best results are obtained with the block-based
descriptor. For this reason, when the color descriptor is mentioned in this
paper, it will be referring to 16x16 blocks-based histogram.

TABLE II: mAP comparison between color descriptors (histograms methods) on dataset 1. Color Descriptor | mAP
---|---
3D RGB | 0.53
Block-based | 0.83
Multiresolution | 0.8

###  IV-C Dataset 2

In the second dataset, the background removal method must be used to extract
up to two paintings per image. Moreover, we also need to detect and remove the
superimposed text bounding boxes to ensure that they do not affect the result.

####  IV-C1 Text bounding box detection

The overlapping text bounding boxes are semi-transparent and have different
colors in each image. To detect them, we propose a robust method that works on
all three channels of the LAB color space.

First, for each channel (L, A and B) we apply the morphological operators of
top hat and black hat separately.

  * •

Top hat: difference between the image and the opening of the image. The
opening removes the small bright elements, so the result of top hat highlights
these small bright elements (e.g. bright letters).

  * •

Black hat: difference between the closing of the image and the image.
Completely opposite, the closing eliminates the small dark elements, so the
result of black hat highlights these small dark elements (e.g. dark letters).

Whether the letters of the text are dark or light, when applying the top hat
and black hat operations separately, they are highlighted and thus easier to
detect. The next step is to apply a closing operator using a rectangle to
connect the letters and then apply [3] to detect the contours. This process is
shown in Figure 6a.

|
---|---
(a) | (b)
Figure 6: (a) Text boxes detection steps, from left to right: convert image to
LAB color space, apply top hat and black hat for each channel, apply
morphological closing, find contours and return the best box candidate using
the distance score system; (b) Text boxes scores: X center point (red line), Y
center point (green lines) and symmetry of the box with respect to 1/5 and 5/6
of the image width (blue lines).

With the presented method, both top hat and black hat operations are applied
separately, so we have more than one candidate to be the text bounding box. To
decide whether to keep the detection of the top hat or that of the black hat,
we define a scoring system that compares all the candidates and returns the
best one (Figure 6b).

We use the following indicators to calculate the distance score:

  * •

X Center point: Distance between the bounding box center and the x center of
the image

  * •

Y Center point: The boxes are usually at the bottom or top of the image, so we
take the 1/5 and 4/5 of the image height as reference points.

  * •

Symmetry of the box with respect to the center x line.

  * •

Symmetry of the box with respect to 1/5 and 5/6 of the image width. The boxes
borders are usually at the 1/6 and 5/6 of the image width, so we take them as
reference points.

  * •

Aspect ratio of the bounding box: $width\approx 4*height$

Each of this indicators is weighted and added. The bounding box with the
minimum resulting distance is returned as the detected box.

By applying this method for each LAB channel, we can obtain up to three final
candidates to be the detected text bounding box. Again, the scoring system is
used to get the best of the three detections. To evaluate the performance of
our method, we use the mean intersection over union to compare the predicted
text box with the groundtruth.

###  IV-D Dataset 3

In the third dataset, we have to remove the noise added to some random images.
Moreover, since there are images with color corruption, we cannot depend on
the color descriptors anymore, so we need to define some new descriptors for
the CBIR system.

####  IV-D1 Noise removal

Noise affects only certain random images in the dataset, so we have two
unknowns to solve: how to detect which images are noisy and how to remove
their noise.

For each image, we apply a median filter and check if the Peak Signal-to-Noise
Ratio (PSNR) of the resulting image with respect to the original one is higher
than a threshold. If that is the case, then the median filter is improving the
image quality, so the image contains noise that needs to be removed (Figure
7). Otherwise, if the PSNR is lower than the threshold, the original image is
preserved.

|
---|---
(a) | (b)
Figure 7: (a) Noisy image; (b) Denoised image

####  IV-D2 Texture descriptors

The corruption on the colors of some images cannot be corrected, so we need
descriptors not related to color. Our first approach is to use the following
texture descriptors:

  * •

Local Binary Patterns (LBP): For each pixel, LBP compares its value to the
values of its surrounding neighbouring pixels and labels the pixel with a
decimal number based on this comparison. By concatenating the labels of each
pixel, we obtain a feature vector with which to compare the paintings.

  * •

Discrete Cosine Transform (DCT): It expresses an image in terms of a sum of
cosine functions oscillating at different frequencies, which helps us to
obtain representative coefficients of the image.

  * •

Histogram of Oriented Gradients (HOG): This technique divides an image in
portions (i.e. blocks) and calculates the gradient and orientation for each
portion to further count gradients occurrences.

Figure 8: Rotation correction algorithm using Hough lines transform. TABLE III: Comparison between texture descriptors on dataset 3. Texture Descriptor | mAP
---|---
LBP | 0.44
DCT | 0.49
HoG | 0.72

The results are presented in Table III. The HOG descriptor is the one that
provides better results. For this reason, when the texture descriptor is
mentioned in this paper, it will be referring to HoG.

####  IV-D3 Text descriptors

Taking advantage of the detections of the text bounding boxes, an alternative
to the texture descriptors is to detect the text inside the bounding boxes,
which contains the name of the painter. In this way, knowing a priori the
author of each painting in the museum dataset, the names detected in the query
image can be used to obtain the corresponding museum image.

To extract the text from the bounding box, we first binarize the content and
then apply Optical Character Recognition (OCR) techniques [4] from the
Pytesseract library. Then, the resulting text is compared with the painters
names in the database to see which one is more similar.

The problem with this descriptor is that there might be more than one painting
with the same author name in the museum’s database. Therefore, with the text
descriptors we cannot directly obtain the painting of interest, but we can use
them as complementary help to the other descriptors.

####  IV-D4 Combining descriptors

Another approach is to combine all the aforementioned descriptors: color,
texture and text. When combining descriptors, we first compute the distances
for each descriptor (e.g. Hellinger distance for color descriptor). Then,
these distances are weighted and added to obtain a final distance result. The
image with the smaller distance is the retrieved most similar painting.

###  IV-E Dataset 4

Finally, the fourth dataset presents two additional problems: some paintings
are rotated and not all of them are in the museum database.

####  IV-E1 Rotation of the images

In order to apply some of the preprocessing methods presented in this paper
(e.g. text box detection), we need to find the rotation angle of each image
and revert the rotation. To do so, we design two different methods.

For the first one, we apply Canny edge detection and morphological closing to
detect the paintings contours. Then, we find the rotated rectangles of the
minimum area enclosing the contours of interest. From the two lower
coordinates of each painting, we calculate the slope of the line that connects
them and obtain the angle of rotation as the arc-tangent of the slope.

The second method is based on the Hough transform. In the gray color space, we
apply Canny to detect the edges, and then use Hough to obtain the larger
lines. As we are interested in the rotation with respect to the x axis, the
vertical lines are discarded. After removing outliers, we compute the mean
rotation angle using the remaining horizontal lines. This process is shown in
Figure 8.

In both cases, after obtaining the rotation angle, we revert the rotations and
then apply the preprocessing methods: background removal, denoising and text
box removal.

####  IV-E2 Feature descriptors

In all the previous descriptors, we calculate the distances between a query
image and all the database images and retrieve the image with the minimum
distance, closest to the query one. Therefore, an image is always retrieved
even if the query image and the database one are completely different. To be
able to compare images properly and detect paintings non existent in the
museum dataset, the features of the images (corners, gradients, key points)
are extracted and compared. Two images are considered similar if a minimum
number of features matches is achieved. If this minimum threshold is never
exceeded, the query image is considered non existent in the museum database.

Figure 9: ORB method: (a) FAST to obtain keypoints and BRIEF to vectorize the
features; (b) Painting matching example

In this paper, the Oriented FAST and Rotated BRIEF (ORB) feature detection
algorithm [1] is used. This method (Figure 9a) relies on the FAST keypoint
extraction, which given a pixel p compares the brightness of p to the
surrounding 16 pixels in a circle. Pixels in the circle are then sorted into
three classes: lighter than p, darker than p or similar to p. If more than 8
pixels are darker or brighter than p, then it is selected as a keypoint.

Keypoints found by FAST give us information of the location of determining
edges in an image. BRIEF takes all these keypoints and convert them into a
binary feature vector so that together they can represent an object. The
paintings keypoints are compared and considered as a match if the distance
between them is smaller than a threshold. If there are 4 or more matches
between two images (Figure 9b), then they are considered similar. The most
similar image (i.e. with more matches) is retrieved as the corresponding
museum image.

The ORB algorithm is invariant to rotation, so there is no need to revert the
rotation of the paintings. However, it is not invariant to noise, background
and superimposed text boxes. For example, if the text boxes are not removed,
the algorithm would detect unwanted keypoints on the text. Therefore, the
system performs better with the complete preprocessing pipeline.

##  V RESULTS

TABLE IV: Evaluation of the background removal method on each dataset. Dataset | Precision | Recall | F1-score | mAE
---|---|---|---|---
1 | 0.90 | 1.0 | 0.94 | -
2 | 0.91 | 0.99 | 0.94 | -
3 | 0.91 | 1.0 | 0.95 | -
4 | 0.90 | 0.99 | 0.94 | 0.43º

Regarding the background detector method, in Table IV we present the results
obtained when comparing the detected backgrounds with the corresponding
groundtruth. As can be seen, we obtain a full recall in the four datasets,
which means that all the paintings are correctly detected. In global terms,
the implemented background removal method is robust and performs
satisfactorily.

For the last dataset, the mean Angular Error (mAE) between the estimated
angles of rotation of the paintings and the groundtruth is presented. The
results are satisfactory, since an error of only 0.43º allows us to confirm
that the method has been implemented correctly.

On the other hand, we have evaluated the performance of the descriptors
presented in this paper for each of the four datasets. Specifically, we
present the results obtained in datasets 1, 2, 3 and 4 using descriptors of
color, texture, text, a combination of these and finally features. A mAP@1 is
used at all times.

The results are presented in Table V. As can be seen, the color descriptors
work fairly well except in the datasets where there are paintings with color
corruption (datasets 3 and 4). In these cases, the texture descriptors provide
better results. On the other hand, using only text descriptors we cannot
detect the paintings of interest properly, as there are ambiguous cases in
which different paintings are from the same painter. Combining the three
descriptors, the performance of the system improves remarkably in each of the
cases. However, it continues to fail in dataset 4, since we cannot identify
the paintings that are not in the museum dataset with only this information.
This problem is solved using the feature descriptors, which not only allow
detecting these cases, but also improve the results in each one of the
datasets.

TABLE V: Evaluation of the descriptors on each dataset. Descriptor | Dataset
---|---
1 | 2 | 3 | 4
Color | 0.83 | 0.7 | 0.64 | 0.42
Texture | 0.93 | 0.89 | 0.72 | 0.53
Text | - | 0.21 | 0.16 | 0.13
Combined | 0.97 | 0.86 | 0.78 | 0.46
Feature | 0.97 | 0.9 | 0.92 | 0.98

##  VI CONCLUSIONS

In this paper, we have explored some traditional techniques that can be used
in a CBIR system, and we have seen the advantages and disadvantages of using
some descriptors compared to others. From the results obtained, we can draw
the following conclusions.

First of all, color descriptors are not efficient in cases where images
present color corruption. In those cases, texture descriptors provide better
results, as they are invariant to the color corruption. Additionally, in
datasets 1 and 2, texture descriptors also improve the performance of the
system with respect to the color ones, so we can conclude that texture can
better represent the information of the image.

Secondly, in our specific case, text descriptors are not enough to retrieve
the paintings correctly, as there might be more than one painting per author.
However, it can be combined with the color and texture descriptors to improve
the overall system performance.

Finally, feature descriptors are the ones that provide the best results, since
they represent the information of the images accurately, at the cost of using
more complex and time consuming algorithms.

In terms of background detection, the overall results are satisfactory. The
precision is high but could we improved, as with the current method the shades
under the paintings frames are wrongly detected.

We have also implemented methods for solving problems such as noisy images,
superimposed text bounding boxes or image rotation. By designing and using the
proper preprocessing algorithms, the performance of the resulting CBIR system
is greatly improved.

##  VII IMAGE CLUSTERING

Using the descriptors explained in this paper, we present an online museum
exhibition by clustering the paintings of the museum dataset. We use the
K-means algorithm to cluster the images into 10 different groups. K-means
analyzes the data to find organically similar data points and assigns each
point to a cluster with similar characteristics. Each cluster can then be used
to label the data into different classes based on its characteristics.

The images are first clustered by colour into two sets of clusters: bright and
dark images. Then, both sets are clustered by texture (using HOG descriptor)
into 5 more clusters, resulting in 10 different clusters. For each of the
bright and dark clusters, with the texture clustering we obtain a range from
plain to highly detailed images. The resulting 10 clusters are labeled
conveying a distinct mood. Feel free to visit our online exhibition [5].

## References

  * [1] Ethan Rublee, Vincent Rabaud, Kurt Konolige, and Gary Bradski.  Orb: an efficient alternative to sift or surf.  pages 2564–2571, 11 2011.
  * [2] Z. Xu, X. Baojie, and W. Guoxin.  Canny edge detection based on open cv.  In 2017 13th IEEE International Conference on Electronic Measurement Instruments (ICEMI), pages 53–56, 2017.
  * [3] Satoshi Suzuki and KeiichiA be.  Topological structural analysis of digitized binary images by border following.  Computer Vision, Graphics, and Image Processing, 30(1):32 – 46, 1985.
  * [4] D. Berchmans and S. S. Kumar.  Optical character recognition: An overview and an insight.  In 2014 International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT), pages 1361–1365, 2014\.
  * [5] Shaurya, Oriol, Oscar, Ian, and Victor.  Automated museum exhibition using image clustering.  https://docs.google.com/presentation/d/1POYzxvVLKLn9I27U3vv9iEXRbN1QAXQP.


* Tiwari [2018] V. Tiwari, Estimation of the sensitive volume for gravitational-wave source populations using weighted Monte Carlo integration, Classical and Quantum Gravity 35, 145009 (2018), arXiv:1712.00482 [astro-ph.HE] .

  *[NS]: Neutron Star
  *[BH]: Black Hole
  *[GW]: gravitational wave
  *[PE]: Parameter Estimation
  *[MCMC]: Markov Chain Monte Carlo
  *[GWs]: gravitational wave
  *[PDF]: Probability Density Function
  *[MC]: Monte Carlo
  *[EDF]: empirical distribution function
  *[CDF]: cumulative distribution function
  *[SNR]: Signal to Noise Ratio
  *[BNS]: Binary Neutron Star
  *[BBH]: Binary Black Hole