# Horizontal-to-Vertical Video Conversion

Tun Zhu, Daoxin Zhang, Yao Hu, Tianran Wang, Xiaolong Jiang,
Jianke Zhu , Jiawei Li  Tun Zhu and Jianke Zhu are with the College of
Computer Science, Zhejiang University, Hangzhou, China, 310027. Jianke Zhu is
also with the Alibaba-Zhejiang University Joint Research Institute of Frontier
Technologies, and Zhejiang Provincial Key Laboratory of Service Robot, College
of Computer Science, Zhejiang University.
E-mail: {ianzhu<EMAIL_ADDRESS>Daoxin Zhang, Yao Hu, Tianran Wang,
Xiaolong Jiang and Jiawei Li are with company of Alibaba, Youku Cognitive and
Intelligent Lab.
E-mail: {daoxin.zdx, yaoohu, steve.wtr, xainglu.jxl, mingong.ljw}@alibaba-
inc.com. Jianke Zhu is the Corresponding Author. The work is supported by
National Natural Science Foundation of China under Grants (61831015). Our
implementation is available at https://github.com/JackieZhangdx/H2V.

###### Abstract

At this blooming age of social media and mobile platform, mass consumers are
migrating from horizontal video to vertical contents delivered on hand-held
devices. Accordingly, revitalizing the exposure of horizontal video becomes
vital and urgent, which is hereby tackled by our automated horizontal-to-
vertical (abbreviated as H2V) video conversion framework. Essentially, the H2V
framework performs subject-preserving video cropping instantiated in the
proposed Rank-SS module. Rank-SS incorporates object detection to discover the
candidate subjects, from which we select the primary subject-to-preserve
leveraging location, appearance, and salient cues in a convolutional neural
network. In addition to converting horizontal videos vertically by cropping
around the selected subject, automatic shot detection and multi-object
tracking are integrated into the H2V framework to accommodate long and complex
videos. To develop H2V systems, we collect an H2V-142K dataset containing 125
videos (132K frames) and 9,500 cover images annotated with primary subject
bounding boxes. On H2V-142K and public object detection datasets, our method
demonstrates promising results on the subject selection comparing to the
related solutions. Furthermore, our H2V framework is industrially deployed
hosting millions of daily active users and exhibits favorable H2V conversion
performance. By making this dataset as well as our approach publicly
available, we wish to pave the way for more horizontal-to-vertical video
conversion research. Our collected H2V-142K dataset is available at H2V-142K
website.

###### Index Terms:

Video conversion, Subject selection, Primary subject dataset

##  I Introduction

Vertical videos are created for viewing in portrait mode on hand-held devices,
which are opposite from traditional horizontal formats popularized on big
screens. With the unprecedented growth of social media platforms, such as
TikTok, Instagram, and Youku, etc., vertical videos take over the focus of
mass video consumers, leaving abundant horizontal contents less exposed. To
reintegrate their exposure, the horizontal videos have been converted
vertically with manual processing and cropping, which is prohibitively labor-
intensive and time-consuming. Accordingly, there is an imperative need for
fully-automated horizontal-to-vertical video conversion solution.

Figure 1: Traditional video consumption scenarios such as Films, TV and stream
media prefer horizontal frame (e.g. 16:9 frame). With the growth of emerging
scenes like portable devices, vertical video content is in huge demand while
lacking professional producers. Our H2V framework manages to generate vertical
videos from high-quality horizontal video inventory.

Nonetheless, automated horizontal-to-vertical video conversion is an uncharted
territory, of which the key challenge is subject preservation, i.e. keeping
the main subject (mostly human) stable in the scene through the information-
losing video cropping. As illustrated in Fig. 1, conversion solutions
implement subject preservation by cropping horizontal sources around the
primary subject for producing vertical outputs. To achieve subject-preserving
conversion, one needs to develop a fully automated pipeline assembling shot
boundary detection, subject selection, subject tracking, and video cropping
components. Subject selection is of the most cardinal importance.

Achieving subject selection in horizontal-to-vertical conversion is
complicated for two reasons. Firstly, the primary subject in a video shifts
constantly from shot-to-shot, therefore accurate shot boundary detection is
indispensable as pre-processing. Secondly, in most cases, one has to select
the primary subject out of numerous foreground distractors within each frame.
To overcome this challenge, Salient Object Detection (SOD) [3, 61] and
Fixation Prediction (FP) [63] have been practiced. SOD performs the pixel-
level foreground-background binary classification to discover all objects but
fails to discriminate the primary subject from other candidates. For FP,
although being able to find the primary subject by imitating human visual
system, yet it can only provide point-like fixation response thus fail to
obtain the subject in its entirety. A comparison between these strategies and
our solution is shown in Fig. 2.

(a) Subject Selection (Ours)

(b) Object Detection

(c) Salient Object Detection

(d) Fixation Prediction

Figure 2: Comparing the results of our approach with the traditional object
detection approach and saliency approaches. The results are illustrated as red
cutting area and right images simultaneously. (a) Our method outputs subject
localization. (b) Object detection only locates objects with a specific
category. (c) Salient object detection outputs binary masks without aware of
object instances. (d) Fixation prediction computes the most eye-catching areas
ignoring boundary and object instances similarly.

In this work, we propose the H2V framework as the first automatic horizontal-
to-vertical video conversion system, which tackles the subject-preserving
video cropping effectively and compactly. As shown in Fig. 5, the H2V
framework first incorporates shot boundary detection to separate horizontal
input into disjointed shots, where each one contains its own set of subjects.
Within each shot, the primary subject is selected at the first frame with the
proposed Rank Sub-Select (Rank-SS) module. As depicted in Fig. 6, Rank-SS
employs a convolutional architecture and integrates human detection, saliency
detection, traditional as well as deep appearance features to discover and
select the primary subject. In the following frames within the shot, the
primary subject is propagated via the subject tracking module. For the
development of Rank-SS module, we start by investigating naive and deep
regression approaches emphasizing on location priors, which report inadequate
performance. Then, we extend the regression into a ranking formulation for
primary subject selection, where object-pair relation is taken into
consideration and delivers favorable performance. The detailed insights with
respect to this extension are elaborated in Section V-C.

To build and evaluate our H2V framework, as well as to encourage further
researches for horizontal-to-vertical video conversion, we collect and
publicize a large-scale dataset named as H2V-142K. H2V-142K dataset contains
132K frames from 125 video sequences, which were carefully labeled by human
annotators with bounding boxes denoting the face and torso of the primary
subject. As shown in Fig. 3, this dataset covers rich horizontal contents,
including TV series, variety shows, and user-made videos. Besides, another
9,500 video cover images with heavy distractors are provided, promoting more
robust primary subject selection. Please refer to Section III for the detailed
statistics of the dataset. On top of the H2V-142K dataset, the publicized
detection dataset such as ASR, and extensive user feedback data were collected
from Youku website. We have conducted comprehensive experiments, where our H2V
framework exhibits favorable qualitative performance, both quantitatively and
qualitatively.

In summary, we highlight three main contributions in this paper: 1) we propose
the H2V framework as the first unified solution to settle horizontal-to-
vertical video conversion, which has been successfully commercialized at a
web-scale; 2) the Sub-Select module is designed in the H2V framework, among
other well-performing components, which integrates rich visual cues to select
the primary subject in a ranking manner; 3) we construct and publicize the
H2V-142K dataset with 125 fully-annotated videos (more than 142k images),
hoping to pave the way for future endeavors in the field of horizontal-to-
vertical video conversion.

##  II Related Work

This section summarizes related works of the task, which is treated as a
content-aware video cropping problem. We firstly survey traditional cropping
methods and illustrate the limitation in this specific issue. Research on
salient object detection and fixation prediction is introduced that closely
related to subject discovery and selection. Moreover, instances localization
and ranking are required to get the most eye-catching subject.

###  II-A Image Cropping

Image cropping is a significant technique for improving the visual quality of
raw images. Early methods leverage the practical experience from
photographical experts to solve this problem, e.g rule of central, rule of
thirds, rule of grid. With the development of deep learning and arising of
large-scale aesthetic datasets, like AVA[44], AADB[25], researchers recently
solve this task in a data-driven manner and have made great progress in this
area. Modern DL-based image cropping methods could be categorized into two
streams: structure-based and aesthetic-based. 1) Structure-based methods [54,
5, 64] focus on preserving the most important or salient part after cropping.
Attention-mechanism or salient detection ideas are usually applied in these
methods. 2) Aesthetics-based methods [18, 68, 71, 10] improve the cropping
results by increasing aesthetic quality, local factors are highly considered,
which are in favor of preserving visually attractive parts. Also, there are
methods that combine both global structure and local aesthetic. [62] models
image cropping in a determining-adjusting framework, which first uses
attention-aware determining, and then applies aesthetic-based adjusting
network. [58] designs the composition-aware and saliency-aware blocks to
select more reasonable cropping.

Image cropping technique is also extended to video retargeting task, which is
the process of adapting a video from one screen resolution to another to fit
different displays [49]. Traditional methods argue that important objects in
the images like faces or text should be preserved and these algorithms are
called content-aware algorithms. Differently from single image, temporal
stability is highly relevant in frames and video flickers should try to be
avoided. Most of approaches optimize the cropping process shot by shot, and
then apply a path generation algorithm to obtain a smooth cropping result [37,
49, 59]. Although having made great efforts, to the best of our knowledge,
there are limited methods that are able to handle complex scenes stably such
as multiple distractive objects.

Figure 3: Sample images of H2V-142K Dataset. We annotate subjects (mostly one)
consisting of the face and body.

###  II-B Salient Object Detection

Salient Object Detection (SOD) has a long history date back to Itti et al’s
work [19]. The majority of SOD [3, 61] methods is designed to detect pixels
that belong to the salient objects without knowing the individual instances,
which is commonly treated as a pixel-wise binary classification problem.
Traditional heuristic SOD research experienced changes from pixel-based
methods [19, 43], patch-based approaches [40, 1] to region-based methods [7,
46]. Recently, deep learning-based methods dominantly lead the state-of-the-
art advances in SOD including Multi-Layer Perceptron-based method [73, 76],
Fully Convolutional Networks [39, 74, 66] and Capsule-based approach [41, 47].

Video salient object detection is similar to image SOD problem discussed
above. How to encode motion saliency between frames is the central issue for
video SOD. The bottom-up strategy is the common practice for heuristic methods
employing background removal [24], points tracking and clustering [14, 45],
object proposal ranking [9, 67] to tackle this problem. Based on deep leaning
model, motion encoding is achieved by optical flow [20, 6, 31] or recurrent
neural network [31, 56, 52]. In addition, co-saliency estimation [21, 28]
searches for the common salient object regions contained in an image set.

Fixation Prediction (FP) [63] is another closely related area investigating
the human visual system’s attention behavior. Prevalent datasets such as DHF1K
[63] record participants’ eye movement and save it as a fixation map. From a
task perspective, fixation prediction only calculates the fixation points or
small areas rather than inferring the primary salient objects like SOD. Thus,
FP models [22, 27, 13] care about neither object contour nor object instance.

###  II-C Salient Instance Ranking

Both SOD and FP methods demand expensive pixel-level annotation and generalize
poorly in complex scenes while inadequately being able to distinguish multiple
objects. Therefore, general Salient Object Subitizing [73, 30] methods have
been proposed to achieve this. For known object categories, object detection
[75, 32] is a more accurate solution. In our H2V framework, we employ a
detector for subject discovery as the target subject is human.

To solve the salient ranking problem, Li et al. [33] found that a strong
correlation between fixations and salient object exists. Similarly, Wang et
al. proposed ranking video SOD [65] with ranking saliency module leveraging FP
and SOD features, which presented promising results. However, the fixation
data is relatively difficult to label, which limits its application. Another
solution introduced by Amirul et al. [2] is a hierarchical representation of
relative saliency and stage-wise refinement. In their Salient Object
Subitizing dataset, prominent objects are asked to label. Furthermore,
relative rank scores are computed by averaging the degree of saliency within
the instance mask. We summarize it as Ranking by Global Average Pooling (RGAP)
scores [2, 65]. As a baseline of the subject selection problem, RGAP-based
models N-SS and D-SS (described in Section V-B) fail to rank the hard cases
with strong spatial characteristics such as side face. Our proposed RCNN-based
[48, 12] Rank-SS model leverages spatial features to achieve the better
region-based ranking.

##  III The H2V-142K Dataset

###  III-A Dataset Overview

The under-development of H2V conversion is partially attributed to the lack of
available data, to which we collect a large-scale H2V-142K dataset consists of
image set and video set. Regarding the train/test split, we randomly select
600 video covers from the image set and all videos in the video set for
testing. The remaining images are used for training.

The ground-truth of this dataset is divided into two parts. For the subject
selection task, our dataset provides the subjects’ bounding boxes, including
face and body. For the H2V conversion task, the vertical version ground-truth
is the maximum cropping rectangles with the size 9:16, which share the same
central horizontal coordinate with subjects’ bounding boxes (no pixels
tailored vertically). Visualization of sample images and annotations is shown
in Fig. 3.

Type | Amount | Avg #Subject | Avg #Person
---|---|---|---
Images | 9,500 | 1.1417 | 4.2820
Videos | 125(132k frames) | 1.0049 | 1.8272
TABLE I: Detailed statistics of H2V-142K Dataset.

Analysis. The H2V-142K dataset contains 125 videos (132K frames) and 9.5K
images. The detailed statistics are shown in Table I. The video subset covers
more general scenes with fewer subjects, while the image subset better
examines the performance of subject selection with heavier distractors.
Therefore, the average number of person and the total number of subjects are
much higher than video subset. The distribution of subjects in two subsets is
presented in Fig. 4. The majority of images or frames have only one subject.
When multiple subjects appear in ground-truth, the result matching any one of
them will be regarded as the correct prediction.

Figure 4: Distribution of subject number in our H2V-142K Dataset.

###  III-B Data Collection and Annotation

The H2V-142K dataset is collected from Youku video-sharing website and
carefully annotated by human annotators following the Sub-Select criteria, as
explained in Section IV-A. The dataset focuses on the most prevalent scenes,
i.e. character-centric scenes.

Video Subset. We collect videos with the diversified contents and subject
scales. Each video is firstly segmented into disjointed shots using TransNet
[53]. Within each shot, a group of three annotators, separately annotate every
frame with the primary subjects using pairs of the face and torso bounding
boxes after watching all frames. The ground-truth bounding boxes are
determined by cross-validating over annotators by thresholding on box
Intersection-of-Union (IoU). Should a disagreement occur on one frame, it will
be carefully reviewed and determined by a group of new annotators. Finally,
the bounding boxes are smoothed temporally by Kalman Filter [70].

Image Subset. For the majority of instances, only one subject is annotated. In
the meantime, co-subjects appear more frequently in the image subset because
of the pre-filter during data preparation. Concretely, a human detector
FreeAnchor [75] pre-trained on the COCO dataset [36] is applied to collect
images containing more than three (at least two) human candidates, and the
ground-truth subject is annotated in the same manner applied in the video
subset. Besides, non-subjects (distractors) are required to rank by the same
criterion as complementary labels. When crowds appear, annotators are asked to
rank the top six non-subjects, disregarding others to generate hard-ranking
labels.

Figure 5: Our proposed H2V framework (Section IV). It consists of four steps:
(1) Divide complete video into a series of footage. (2) Select subjects from
keyframe (Section V), which is the first frame in the shot initially. (3)
Tracking those subjects within consecutive frames until fails, then mark the
current frame as a keyframe and return to step 2 iteratively. (4) Smooth the
tracking trajectory and generate the vertical output video.

##  IV H2V Framework

H2V video conversion clips horizontal video into a vertical format while
keeping the most engaging content intact. Accordingly, one needs to identify
and preserve the primary subject in every frame efficiently. To facilitate
both the production-level accuracy and efficiency, our proposed H2V framework
executes in a shot-based fashion. Firstly, a shot boundary detector TransNet
[53] is employed to segment a horizontal input video into consecutive shots.
Other video understanding methods [38, 57] for SDB could also be considered,
which is beyond this paper’s scope. Secondly, we apply our Rank-SS module to
discover and select the primary subject within each shot. As the primary
subject is mostly shot-stable, we finally bypass the frame-by-frame Rank-SS by
tracking this subject throughout the shot with trajectory verification and
smoothing.

###  IV-A Subject Selection Criteria

Since human actors are primary subjects in most trending videos, H2V video
conversion crops horizontal videos around the primary subject to reduce the
loss of information and produce meaningful vertical content during the
conversion process. To correctly identify the most primary human subject, we
first discover all human objects in the scene using the DSFD face detector
[32] and FreeAnchor body detector [75]. Meanwhile, we prefer to utilizing a
face detector since it is easier to maintain the completeness of a face than a
body in the cropped area. Indeed, the ablation experiment in Section III
proved that the face detector is more effective than a body detector. Then,
selecting the primary subject from all is a highly empirical and subjective
task, for which we summarize the following criteria under guidance from
professional video editors:

  * •

The Central Criterion: The primary subject tends to reside in the center of
the scene.

  * •

The Focal Criterion: The primary subject appears within the focal length and
free-from out-of-the-lens blurry.

  * •

The Proportional Criterion: The primary subject tends to occupy the majority
of the scene.

  * •

The Postural Criterion: The primary subject displays a more eye-catching
posture rather than, for example, side-face or back-away.

  * •

The Stable Criterion: (Video only) Primary subject usually shows no abrupt
displacement within the same shot.

To fully practice the above criteria effectively and compactly, we design a
subject selection component, as shown in Fig. 6, which composes subject
discovery, feature extraction, and our proposed Sub-Select module. The details
are elaborated in Section V.

###  IV-B Subject Tracking

As each video shot usually focuses on the same primary subject, we refrain
from the complicated frame-by-frame subject selection and track the primary
subject selected as above throughout the shot. When professional editors
performing H2V manually, video temporal smoothness is deliberately ensured
with frame calibrating and interval smoothing. By mimicking this procedure, we
design a subject tracking component integrating object-tracking based on
SimaMask [60], verification, and temporal smoothness modules. Specifically,
this component simultaneously tracks all subjects in the scene, and should a
subject exit the scene, we re-verify the trajectory by triggering the subject
selection component to re-initialize the primary subject. Whenever a subject
disappears or is contaminated by similar distractors, the tracking confidence
might be below the threshold. A subject exits the scene, which means that the
vertical scene cannot cover all tracked subjects. All situations will trigger
the verification module to restart the sub-select module for subject re-
initialization. To further smooth the trajectory and suppress motion jitters,
a Kalman Filter based motion model [70] is incorporated.

Figure 6: An illustration of our Rank-SS module. Given an image, a detector is
employed to generate face or body bounding boxes as subject candidates
$\mathbf{c_{i}}$. Then, the RoIAlign [15] layer accepts the predicted bounding
boxes and the concatenated features extracted by three feature extractors as
input to generate fixed-size feature maps, which are fed into RCNN header.
Finally, the vectorized feature is concatenated with the location priors of
candidates and mapped to the subject prediction scores $\mathbf{s_{i}}$ by
fully-connected layers.

##  V Subject Selection

In this section we explain our subject selection component in-depth (shown in
Fig. 6), emphasizing feature extraction and the novel Sub-Select module.
Particularly, the Navie Sub-Select (N-SS), Deep Sub-Select (D-SS), and Rank
Sub-Select (Rank-SS) modules are discussed in turns to share more insights in
solving subject selection.

###  V-A Feature Extraction

To fulfill the subject selection criteria described in Section IV-A, we employ
three different feature extraction strategies, as shown in Fig. 6. For
saliency feature extraction, we adopt the cascaded Partial Decoder model (CPD
[66]) to generate a salient feature map $\mathcal{F}_{sal}$. Blur detection
aims to detect Just Noticeable Blur (JNB) caused by defocusing that spans a
small number of pixels in images. We utilize the traditional Thresholded
Gradient Magnitude Maximization algorithm (Tenengrad [55, 50]) to extract the
blur feature map $\mathcal{F}_{b}$. Additionally, we implement an ImageNet
[26] pre-trained ResNet-50 [16] to extract deep semantic embedding
$\mathcal{F}_{e}$. In summary, the feature $\mathcal{F}$ exploited in our
subject selection component is a concatenation as:
$\mathcal{F}=[\mathcal{F}_{sal},\mathcal{F}_{b},\mathcal{F}_{e}].$

###  V-B N-SS and D-SS

Depending on the extracted feature, subject selection is a problem to compute
the probability $s_{i}$ of each discovered human candidate $i$ for being the
primary subject, and H2V conversion is then resolved by cropping the video
around the most probable subject. The Naive Sub-Select (N-SS) module settles
this problem by calculating the probability as the weighted summation of
saliency and blur feature vectors. For each discovered subject candidate
bounding box $c_{i}=[x_{i},y_{i},w_{i},h_{i}]$ (where $i=1,2,...,N$), features
extracted from within are abstracted via Global Average Pooling [34] (GAP) to
produce feature vector $f_{i}$:

$f_{i}=GAP(Crop([\mathcal{F}_{sal},\mathcal{F}_{b}],c_{i})).$ (1)

N-SS calculates the probability $s_{i}$ as:

$s_{i}=NSS(f_{i},c_{i};\mathbf{w})=\mathbf{w}^{\mathrm{T}}[f_{i},c_{i}],$ (2)

where we concatenate $f_{i}$ with $c_{i}$ to incorporate position and size
information into consideration, conforming to the central and proportional
criteria. $\mathbf{w}$ is the weights of the concatenated feature set
manually. In the experiment, 0.3, 0.1, 0.3, 0.3 yields the best performance,
each representing the weight for the saliency, blur, and bounding box size and
position.

The main drawback of N-SS is the dependency on manually-set weights
$\mathbf{w}$. As an improvement, the Deep Sub-Select (D-SS) module is designed
with the same input as N-SS while adopting a Multi-Layer Perception (MLP) to
learn the optimal weights in a data-driven way. This greatly enhances the
capacity of Sub-Select module w.r.t. feature integration. Specifically, we
implement three fully-connected layers followed by ReLU activation, and adopt
Mean Squared Error (MSE) loss as the cost function to optimize D-SS, which is
commonly used in the regression problem. The formulation of D-SS is:
$s_{i}=DSS(f_{i},c_{i};\mathbf{w}).$

###  V-C Rank-SS

Both N-SS and D-SS generate unary probability while overlooking the pairwise
relationship among subject candidates. Concretely, prediction only considers
the characteristics of the candidate itself, and the final predicted subject
probability score is not related to others. In addition to larger absolute
probability values, the primary subject is more distinctive from the non-
primary ones w.r.t. higher probability ranking order. From this view, Rank
Sub-Select (Rank-SS) module extends the D-SS module from regression into a
ranking formulation, striving to select the primary subject more accurately
with pairwise ranking supervision.

In addition to the salient feature, blur feature and bounding box size and
position information as our selection basis, we design a RCNN-like [12, 48]
module (shown on the left-side in Fig. 6) with deep semantic embedding. To
better optimize the Sub-Select module in Rank-SS, we develop a new pairwise
ranking-based supervision paradigm as illustrated on the right-side in Fig. 6,
and the Siamese architecture [29] has two identical Sub-Select module branches
and is valid for pair-wise inputs. On top of a Siamese architecture, bounding
boxes for subject $i$ and $j$ are simultaneously passed onto the Rank-SS
module, together with the extracted feature $\mathcal{F}$ for the scene. Both
branches in the Siamese architecture instantiate the same Sub-Select module,
feature map $\mathcal{F}_{i}$ is pooled from bounding box $c_{i}$ on
$\mathcal{F}$ with RoIAlign operation [15].

$\mathcal{F}_{i}=RoIAlign(\mathcal{F},c_{i}),$ (3)

where $\mathcal{F}_{i}$ is further vectorized through three cascaded ResNet
[16] bottleneck blocks (followed by GAP [34]), then concatenated with the
bounding box feature vector of $c_{i}$ and $c_{j}$ separately. The regression
subject probability score $s_{i}$ is computed as:
$s_{i}=RankSS(\mathcal{I},c_{i};\mathbf{w}),$ where $RankSS$ and $\mathbf{w}$
indicate the Rank-SS network and its weights, respectively, $\mathcal{I}$
denotes the input image. To train the Rank-SS module, we implement both unary
and pairwise loss functions.

Unary loss Point-wise Mean Squared Error (MSE) loss is adopted to measure the
absolute difference between predicted and ground-truth probability score. The
MSE loss for all $N$ candidates $c_{i},i=1,2,...,N$ is calculated as:

$\mathcal{L}_{pt}(s)=\frac{1}{N}\sum_{i=1}^{N}(s_{i}-l_{i})^{2},$ (4)

$l_{i}$ represents the ground-truth label of candidate $c_{i}$, which is 1 and
0 for subjects and non-subjects, respectively.

Pairwise loss Our H2V-142K dataset is annotated with subject primality ranking
labels, enabling pairwise supervision to improve the Sub-Select module in
learning features and probabilities that better distinguish primary subject
from the non-primary ones. Concretely, we adopt the margin-ranking loss [4] on
$s_{i}$, $s_{j}$ generated from the Siamese Rank-SS module, and the associated
ranking labels. To adjust Rank-SS output ranking orders compatible the
annotation, we formulate:

$\left\\{\begin{aligned} \;s_{i}<s_{j}\quad&if\quad l_{i}<l_{j}\\\
\;s_{i}>s_{j}\quad&if\quad l_{i}>l_{j}\end{aligned}\right..$ (5)

This pair-wise loss guide the Rank-SS ranking to the orientation of the given
relative order, which is formulated as:

$\displaystyle\mathcal{L}_{pair}(s;\gamma)=$
$\displaystyle\frac{1}{N(N-1)}\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{N}\mathop{\max}(0,(s_{j}-s_{i})*\gamma_{(i,j)}+\epsilon),$
(6) $\displaystyle\left\\{\begin{aligned} \;\gamma_{(i,j)}&=-1&if\quad
l_{i}<l_{j}\\\ \;\gamma_{(i,j)}&=1&if\quad l_{i}>l_{j}\end{aligned}\right.,$

where $\gamma$ is the rank label of the candidates pair. The margin $\epsilon$
controls the distance between $s_{i}$ and $s_{j}$.

Subject probability scores $s$ of $N$ candidates are optimized with the
combination of both unary and pairwise losses:

$\displaystyle\mathcal{L}=w_{pt}\mathcal{L}_{pt}(s)+w_{pair}\mathcal{L}_{pair}(s;\gamma),$
(7)

where $w_{pt}$ and $w_{pair}$ denote the weights of $\mathcal{L}_{pt}$ and
$\mathcal{L}_{pair}$.

##  VI Experiments

In this section, we first elaborately introduce ASR dataset, and evaluation
metrics on both video and image data. On this dataset, we then present
extensive experiments results w.r.t. our H2V framework, emphasizing the Sub-
Select module with comprehensive subjective results.

###  VI-A The ASR Dataset

The ASR dataset [51] is a large-scale salient object ranking dataset based on
a combination of the widely used MS-COCO dataset [35] with the SALICON dataset
[23]. SALICON is built on top of MS-COCO to provide mouse-trajectory-based
fixations in addition to original objects’ mask and bounding box annotations.
The SALICON dataset provides two sources of fixation data: 1) fixation point
sequences and 2) fixation maps for each image. The ASR dataset exploits these
two sources to generate ground-truth saliency rank annotations. As the ASR
dataset is not human-centered, we verify the generalization ability of the
proposed method on this object-centered dataset.

###  VI-B Evaluation Metrics

To evaluate the performance on our H2V-142K dataset, we adopt the max
Intersection-over-Union (max-IoU), min Central Distance Ratio (min-CDR), min
Boundary Displacement Error (min-BDE), and mean Average Precision (mAP)
metrics. Precisely, we measure the subject selection accuracy by calculating
the max IoU over all ground-truth subject instances as: Since our new dataset
has the images with multiple annotated subjects, we evaluate our subject
selection result $c_{y}$ with each ground-truth subject by IoU. Then, we
employ the max IoU to measure whether the subject is selected

$maxIoU=\max_{i}(\frac{Area(c_{y}\cap GT_{i})}{Area(c_{y}\cup GT_{i})}).$ (8)

where $c_{y}$ and $GT_{i}$ denote the bounding box of the predicted subject
candidate and ground-truth subject instance $i$. Besides, min-CDR is employed
to evaluate the precision of predicted bounding boxes as follows:

$minCDR(y)=\min_{i}(\frac{\left\|y-\hat{y}_{i}\right\|}{w}),$ (9)

where $y$ and $\hat{y}_{i}$ indicate the center coordinates of predicted
subject candidate and ground-truth subject instance $i$, the width of image
$w$ is considered for normalization. Also, we adopt the same evaluation metric
as [62], i.e., min-BDE to measure the accuracy of predicted subject. The min-
BDE is defined as the average displacement of four edges between the predicted
subject bounding box and the ground-truth rectangle:

$minBDE=\min_{i}(\frac{\sum_{j=1}^{4}(\left\|B_{j}-\hat{B}_{j}^{i}\right\|)}{4}),$
(10)

where $j\in\\{left,right,up,bottom\\}$, and $\\{B_{j}\\}_{j}$ denote the four
edges of the predicted subject while $\\{\hat{B}_{j}^{i}\\}_{j}$ denote the
four edges of ground-truth subject $i$.

In addition to the above image-oriented metrics, we also incorporate the
average min-CDR (avg-min-CDR), Jitter Degree Ratio (JDR) and recall metrics to
evaluate performance regarding videos. For average min-CDR, instead of setting
$y$ as the center of bounding boxes, we set $y$ as the center of the cropped
vertical frame and calculating the mean value over the whole video sequence.
For JDR, we compute the sum of pair-frame pixel displacement w.r.t. the
cropped center coordinates as below:

$JDR(\mathbf{y})=\sum_{t=1}^{T-1}(\frac{\left\|y_{t+1}-y_{t}\right\|_{2}}{w}),$
(11)

where $T$ indicates the total number of frames in the whole video sequence,
and $w$ means the width of the frame. Recall metric [8] refers to the
percentage of the main subject that can be displayed on the clipping screen.
Ideally, the main subject can be entirely displayed on the screen instead of
being clipped out. The metric is described as follows:

$Recall=\sum_{t=1}^{T}(\max_{i}(\frac{Area(c_{y}\cap
GT_{i})}{Area(c_{y})}))/T.$ (12)

where $c_{y}$ and $GT_{i}$ are the same meaning as in max-IoU.

###  VI-C Experiments

On the H2V-142K dataset, we conduct extensive experiments to evaluate the
performance of our Sub-Select module and our H2V conversion framework.

####  VI-C1 Sub-Select Module

We compare our ranking-based module with the state-of-the-art salient object
detection CPD [66], fixation prediction-based competitors [17], image cropping
[42, 72], as well as our naive and deep selection-based baselines, on the
image subset of the H2V-142K dataset. For both SOD and FP methods, probability
maps are generated for input images with pre-trained released models due to a
lack of annotated data for our task. Then, the biggest contour in binarized
probability maps is selected as the subject. The result position is
represented as a bounding box and a centroid of the contour. As for image
cropping, the traditional methods discard the irrelevant content and remain
the enjoyable part of the image, but cannot output a fixed-size image. After
transformation, the detected bounding box closest to the center of the cropped
image is regarded as our selected subject.

Implementation Details. In our Rank-SS module and N-SS as well as D-SS
baseline modules, we deploy DSFD [32] and FreeAnchor [75] as the face and
torso detectors. As for the integrated feature extraction described above, CPD
[66] is attached to produce the saliency detection response, and Tenengrad
algorithm [55, 50] is used to produce blur response in three proposed subject
selection modules. In the Rank-SS module, an ImageNet pre-trained Resnet50
backbone is implemented to extract deep semantic embedding, and all feature
maps are resized to stride 16 consistent with the embedding feature size.
Input images are resized such that their shorter side is 600 pixels during
training and testing. Regional feature size pooled by RoIAlign layer is
14$\times$14.

For training modules, we employ SGD as an optimizer with an initial learning
rate of 0.01 that decays 0.1 ratios per 10 epochs. The batch size of the input
image is 4, and RoIs per image is increased to 20 by randomly perturbing
subject candidates. To warm up the subject probability predictor, $w_{pair}$
is set as zero for the first 30 epoch. Then, the pairwise loss
$\mathcal{L}_{pair}$ is added to train the Rank-SS module, which takes another
50 epochs to reach convergence.

Comparisons. In the following, N-SS and D-SS denote the naive and deep subject
selection baselines, Rank-SS is our final ranking-based module. As shown in
Table II, even our naive baseline with traditional features outperforms SOD
[66], FP [17] and image cropping [42, 72] competitors in all four metrics,
achieved at least 0.86% improvement in mAP. The deep regression baseline
further improves upon N-SS by 19.81% in max-IoU and 23.8% in mAP,
demonstrating the efficacy of deep features in the H2V conversion task. The
soft label refers to the label information that does not contain the ranking
order in the training data. We employ the correlation between the primary
subject and the non-subject to construct a relative ranking order for
training. The hard label refers to the annotated absolute ranking order
between all human proposals. Our final ranking-based subject selection module
reports the best overall selection accuracy with hard-label training data,
surpassing D-SS by 4.65%, exceeding the Rank-SS module with soft-label
training data 2.24%, and largely outperforming the SOD based model by 29.31%
in term of mAP. Also, our final ranking-based module reports the best min-CDR
and min-BDE, which means that we achieve the best accuracy in predicting the
subject bounding box. As for the speed tests, our naive baseline with
traditional features reports the best FPS cause of naive liner feature
combinations, and our ranking-based module maintains real-time processing
performance while improving the accuracy.

Method | max-IoU $\uparrow$ | min-CDR $\downarrow$ | min-BDE $\downarrow$ | mAP $\uparrow$ | FPS $\uparrow$
---|---|---|---|---|---
SOD [66] | 59.59% | 8.36% | 8.68% | 65.17% | 12.7
FP [17] | 48.16% | 9.78% | 9.26% | 43.28% | 15.6
Image Cropping [42] | 24.62% | 37.87% | 24.55% | 26.38% | 21.2
Image Cropping [72] | 15.79% | 46.39% | 30.07% | 17.24% | 18.4
N-SS (Ours) | 62.47% | 4.88% | 6.21% | 66.03% | 59.1
D-SS (Ours) | 82.28% | 2.40% | 2.13% | 89.83% | 31.3
Rank-SS/Soft (Ours) | 84.44% | 1.55% | 1.98% | 92.24% | 26.7
Rank-SS/Hard (Ours) | 92.37% | 1.01% | 1.89% | 94.48% | 26.8
TABLE II: Comparison of our proposed Sub-Select modules with state-of-the-art
Salient Object Detection, Fixation Prediction and Image Cropping methods in
H2V-142K Image Subset. Please note that $\uparrow$ means the larger value
representing the better result, while $\downarrow$ is the opposite.

In addition to testing on H2V-142K Image Subset, we conduct experiments on the
ASR dataset [51] to evaluate the modules’ generalization ability. As shown in
Table III, there are three kinds of training settings based on our training
data, which include only H2V-142K Image Subset, only ASR dataset, and both two
datasets. Our Rank-SS trained with H2V-142K Image Subset achieves 59.59% in
mAP, which significantly outperforms SOD [66], FP [17] and image cropping [42,
72] competitors. The Rank-SS trained with ASR dataset further improves upon
the module trained with H2V-142K Image Subset by 5.72% in max-IoU and 7.57% in
mAP, which benefits from the homogeneity of the dataset. The Rank-SS reports
the best overall selection accuracy with both two datasets training data,
surpassing the module trained with ASR dataset by 0.09%, and largely
outperforming the SOD based model by 19.77% in term of mAP.

Method | max-IoU $\uparrow$ | min-CDR $\downarrow$ | min-BDE $\downarrow$ | mAP $\uparrow$
---|---|---|---|---
SOD [66] | 53.3% | 11.94% | 12.31% | 47.48%
FP [17] | 23.29% | 14.49% | 19.04% | 11.41%
Image Cropping [42] | 12.19% | 42.92% | 36.25% | 10.42%
Image Cropping [72] | 17.84% | 32.82% | 28.62% | 27.22%
Rank-SS (H2V-142K) | 54.54% | 4.69% | 4.74% | 59.59%
Rank-SS (ASR) | 60.26% | 4.52% | 4.22% | 67.16%
Rank-SS (ASR-ft) | 60.42% | 4.39% | 4.13% | 67.25%
TABLE III: Comparison of the proposed Sub-Select modules with state-of-the-art
Salient Object Detection, Fixation Prediction and Image Cropping methods in
the ASR dataset [51].

Ablations. To investigate each component’s contribution in the Rank-SS module,
we provide the ablation study results on our final ranking-based module in
Table IV. The last row in the table resides the complete module, and the first
three rows show the results of ablating the blur detection (BD), saliency
detection (SD), and positional feature (PF), respectively, where each of them
shows the contribution of different degrees. Notably, the PF component
demonstrates up to 15.69% mAP decline upon ablation, proving that the spatial
position and size are the most effective clue to subject selection. BD and SD
contribute 2.93% and 3.27% in terms of mAP. The sixth row reveals that the
face detector outperforms torso detector by 9.34%, 1.92%, 1.52%, and 6.38% in
max-IoU, min-CDR, min-BDE, as well as mAP accordingly. This proves that the
human face is more reliable evidence to support accurate and precise subject
discovery. Finally, max-IoU and mAP decrease by 8.69% and 3.1% by ablating our
margin-ranking loss (MRL), demonstrating that margin-ranking loss is
especially valid in enforcing more spatially precise subject selection. The
fifth row exposes that mean squared error loss (MSE) is equally indispensable
in the Rank-SS module.

Method | max-IoU $\uparrow$ | min-CDR $\downarrow$ | min-BDE $\downarrow$ | mAP $\uparrow$
---|---|---|---|---
Rank-SS (w/o BD) | 83.79% | 1.74% | 2.02% | 91.55%
Rank-SS (w/o SD) | 83.36% | 1.75% | 2.09% | 91.21%
Rank-SS (w/o SF) | 72.26% | 5.26% | 7.34% | 78.79%
Rank-SS (w/o MRL) | 83.68% | 1.72% | 2.08% | 91.38%
Rank-SS (w/o MSE) | 83.74% | 1.83% | 2.12% | 91.55%
Rank-SS (with body) | 83.03% | 2.93% | 2.37% | 88.10%
Rank-SS (with face) | 92.37% | 1.01% | 1.89% | 94.48%
TABLE IV: Ablation study of our Rank Sub-Select module to investigate each
component’s contribution. All ablation experiments take total 80 epochs for
training. Using the face frame as the pre-selection result is better than
using the body frame as the pre-selection.

Analysis of loss weights. For our Rank-SS module, the weights of point-wise
loss and pairwise loss are crucial hyper-parameters. Therefore, we further
explore the effect of these two hyper-parameters by varying $w_{pt}$ from 0.0
to 2.0 s.t. $w_{pt}+w_{pair}=2$. Fig. 7 shows the impact of weights on the
image subset of our H2V-142K dataset. From Table II, we note that the Rank-SS
achieves the best performance while $w_{pt}$ is set to 0.5, and setting too
large or too little number of $w_{pt}$ will affect the performance of subject
selection. This is because a too large number of $w_{pt}$ cannot sufficiently
utilize the ranking order of subject candidates and too little $w_{pt}$ will
cause the prediction score to lose its meaning as the subject probability.

(a) max-IoU and<EMAIL_ADDRESS>
(b) min-CDR and min-BDE

Figure 7: Effect of the Number of Rank-SS weight $w_{pt}$ on the Image Subset
of our H2V-142K Dataset.

####  VI-C2 H2V Framework

We evaluate and compare the H2V framework on the video subset of our H2V-142K
dataset, employing different Sub-Select variants, with other H2V frameworks
based on SOD and FP subject selections, as well as video cropping framework
[11]. The video-based SOD anchor-diff [69] and FP Aclnet [63] modules are
executed on each frame to obtain the video results. The implementation is
similar to the image-based SOD and FP methods.

Comparisons. As shown in Table V, the H2V framework with the ranking-based
Sub-Select module performs much better than SOD, FP and video cropping based
approaches in both avg-min-CDR, JDR, and Recall metrics. As the FP approach is
a point-based solution free from bounding boxes, it shows superior temporal
stability and surpasses box-based SOD by 82.22% and 22.82% in terms of JDR and
Recall. Although our Rank-SS based H2V is a region-based method, it still
outperforms FP by 3.53%, 1.48% and 23.8% improvements in all avg-min-CDR, JDR,
and Recall metrics. This demonstrates the subject selection accuracy and
temporal stability of our H2V framework.

Method | avg-min-CDR $\downarrow$ | JDR $\downarrow$ | Recall $\uparrow$ | FPS $\uparrow$
---|---|---|---|---
Video SOD [69] | 14.49% | 4.939 | 22.91% | 6.3
Video FP [63] | 14.47% | 0.878 | 45.73% | 15.6
Video Cropping [11] | 15.25% | 5.382 | 20.09% | 24.9
Our Framework | 10.94% | 0.865 | 69.53% | 28.6
TABLE V: Comparison of our Rank Sub-Select module based H2V framework with the
state-of-the-art Video Salient Object Detection, Video Fixation Prediction and
Video Cropping methods in H2V-142K Video Subset.

Ablations. Table VI shows the ablation results of our H2V framework, where we
investigate the contributions of the shot boundary detection (SBD) and subject
tracking (ST) components. By ablating SBD, both avg-min-CDR, JDR and Recall
drop significantly by up to 3.24%, 61.74%, and 15.88%, which is induced by
wrongful across-shot subject selection. Especially, the ground-truth subject
varies from shot to shot, yet now the framework selects subject only once at
the initial frame, thus rendering more errors. For ablating the ST component,
on the other extreme, we execute Sub-Select at every frame, which causes FPS
to decrease from 28.6 to 9.6. Consequently, avg-min-CDR increases by 6.18% due
to more accurate subject selection, while JDR and Recall decrease by 93.06%
and 12.8% because of the absence of tracking-based temporal smoothness.

Method | avg-min-CDR $\downarrow$ | JDR $\downarrow$ | Recall $\uparrow$ | FPS $\uparrow$
---|---|---|---|---
w/o SBD | 14.18% | 2.261 | 53.65% | 33.4
w/o ST | 4.76% | 12.468 | 82.33% | 9.6
Our Framework | 10.94% | 0.865 | 69.53% | 28.6
TABLE VI: Ablation study of our H2V framework to investigate the contributions
of shot boundary detection and subject tracking modules.

###  VI-D Subjective Evaluation

####  VI-D1 One-Way Repeated Measures ANOVA

An independent sample (n=50) is recruited to complete the questionnaire, which
contains 30 subjective evaluation questions consisting of one original image
and three vertical results generated by SOD, FP, and Rank-SS, respectively.
The participants are asked to report their evaluation of the three vertical
images on Likert 5-point scale (1=bad, 5=excellent). To assess the difference
in the performance of the three methods, we conduct one-way repeated measures
ANOVA. The results are listed in Table VII, which suggests that there is a
significant difference in quality among the three methods
($F(2,98)=125,P<0.001,\eta^{2}=0.487$). The post-hoc analyses (Table VIII)
reveal that the difference between Rank-SS and SOD is significant
($T=13.295,P<0.001$), suggesting that Rank-SS is better than SOD. Besides,
there is a significant difference between Rank-SS and SOD
($T=11.015,P<0.001$), which demonstrates that Rank-SS also performs better
than FP. However, no significant result is found between SOD and FP
($T=1.953,P=0.058$), indicating that the quality of cut result generated by
SOD is similar to FP.

| Method(Mean$\pm$SD) | $F$ | $p$
---|---|---|---
SOD[66] | FP[17] | Rank-SS
Score | 2.63$\pm$0.67 | 2.76$\pm$0.70 | 4.09$\pm$0.67 | 125 | 0.000***
TABLE VII: The ANOVA experiment of Rank Sub-Select module with Salient Object Detection and Fixation Prediction methods. | Paired Difference | $t$ | $p$
---|---|---|---
Mean | SD | SEM
FP - SOD | 0.13 | 0.44 | 0.69 | 1.953 | 0.058*
RankSS - SOD | 1.46 | 0.71 | 0.11 | 13.295 | 0.000***
RankSS - FP | 1.33 | 0.78 | 0.12 | 11.015 | 0.000***
TABLE VIII: The post-hoc analyses of ANOVA experiment.

####  VI-D2 User-Feedback Results

In applications, H2V video conversion is a more user-oriented task whose
performance is better evaluated by user-feedback. After deploying our H2V
framework onto Youku video-sharing website, we have collected rich user-
feedback data generated from converted films, TV series, and variety shows,
totally covering more than 100 Occupationally-Generated Content (OGC) with 10
million views. Specifically, the audit pass rate of converted images and
videos is 98% and 94%, respectively. Image-wise, vertical video cover image
converted by H2V gains video exposure up to 1.5 million times per day. Video-
wise, efficiency indexes such as the Click Through Rate (CTR) and Bounce Rate
(BR) of vertical videos converted by H2V is on par with the ones produced
manually. In addition to online data explained as above, we invite a group of
professional video practitioners to participate in an offline survey, wherein
videos converted by H2V reports a 3% bad case rate, way past the 5-10%
available rate.

####  VI-D3 Strength and Weakness

As illustrated in the first row of Fig. 8, our H2V framework successfully
selects the primary subject from background distractors (1a and 1c). It can
also discard the pseudo-subject, who is not facing the camera directly (1d).
Moreover, H2V can incorporate human closely-located with the selected primary
subject. More visualization of results in the MSCOCO 2017 Val dataset [36],
proposed H2V-142K dataset, and ASR dataset [51] is shown in Fig. 9. As it can
be seen that our method generalizes well on common objects not limited to
humans.

The second row of Fig. 8 shows several bad cases of our framework. By large,
bad cases occur when the criteria described in Section IV-A contradict each
other. In 2a and 2b, the central criterion overwhelms the proportional
criterion, and 2d demonstrates the case when the proportional criterion
overwhelms the postural criterion. Sub-figure 2c depicts the missed detection.

Finally, the limitations of our H2V framework include: 1) it is object-
oriented method that cannot process scenery lens in documentary or contents
with rarely-seen subjects such as plants that is not able to be detected by
object detectors. 2) our framework may fail in strongly dynamic shots where
the camera moves like Dolly, Truck and Zoom are utilized, resulting in
jittering. 3) the H2V-142K dataset is a subset of H2V task containing human
subjects only. It is still worthy of exploring more general cases in future
works.

Figure 8: Visualization of results from Sub-Select Image Dataset. The blue and
yellow bounding boxes are the selected subjects and ground-truth subjects,
respectively. The final cropping area is highlighted as red. The first row
denotes correct instances, and the second row presents bad cases. Figure 9:
Visualization of results in the MSCOCO 2017 Val dataset [36], proposed
H2V-142K dataset, and ASR dataset [51]. The original input and final 9:16
frame output are on either side of the picture. It worth noticing that the
horizontal target frame can be a different value such as 1:1, 3:4, etc. As the
primary subject selected, our H2V framework is able to generate multiply
outputs with different sizes simultaneously.

##  VII Conclusions

In this work, we introduce the first fully automatic and commercialized
horizontal-to-vertical video conversion solution, which tackles subject-
preserving clipping by integrating shot detection, subject selection, object
tracking, and video cropping. Among all well-performing components, we
highlight the Sub-Select module which effectively discovers and selects the
primary subject via multi-cue feature integration and region-based object
ranking. For the development of horizontal-to-vertical solutions, we hereby
make the large-scale H2V-142K dataset publicly available, wherein 132K frames
in 125 videos and 9,500 images are carefully annotated with primary subject
building boxes. Extensive experiments with H2V are conducted on H2V-142K and
related object detection datasets, where both accuracy metrics and vast user-
feedback data reveal the efficacy and superiority of our H2V framework. Upon
the completion of this paper, our H2V framework has been successfully deployed
online hosting massive throughput, and we hope this paper can pave the way for
more successful endeavors.

## References

  * [1] R. Achanta, F. Estrada, P. Wils, and S. Süsstrunk.  Salient region detection and segmentation.  In International conference on computer vision systems, pages 66–75. Springer, 2008.
  * [2] M. Amirul Islam, M. Kalash, and N. D. Bruce.  Revisiting salient object detection: Simultaneous detection, ranking, and subitizing of multiple salient objects.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7142–7150, 2018.
  * [3] A. Borji.  Saliency prediction in the deep learning era: Successes and limitations.  IEEE transactions on pattern analysis and machine intelligence, 2019\.
  * [4] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender.  Learning to rank using gradient descent.  In ICML ’05, 2005.
  * [5] J. Chen, G. Bai, S. Liang, and Z. Li.  Automatic image cropping: A computational complexity study.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 507–515, 2016.
  * [6] J. Cheng, Y.-H. Tsai, S. Wang, and M.-H. Yang.  Segflow: Joint learning for video object segmentation and optical flow.  In Proceedings of the IEEE international conference on computer vision, pages 686–695, 2017.
  * [7] M.-M. Cheng, N. J. Mitra, X. Huang, P. H. Torr, and S.-M. Hu.  Global contrast based salient region detection.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(3):569–582, 2014.
  * [8] T. Deselaers, P. Dreuw, and H. Ney.  Pan, zoom, scan — time-coherent, trained automatic video cropping.  2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, 2008.
  * [9] A. Faktor and M. Irani.  Video segmentation by non-local consensus voting.  In BMVC, volume 2, page 8, 2014.
  * [10] C. Fang, Z. Lin, R. Mech, and X. Shen.  Automatic image cropping using visual composition, boundary simplicity and content preservation models.  In Proceedings of the 22nd ACM international conference on Multimedia, pages 1105–1108, 2014.
  * [11] N. Frey and Z. Sun.  Autoflip: An open source framework for intelligent video reframing.  2020\.
  * [12] R. Girshick.  Fast r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 1440–1448, 2015.
  * [13] S. Gorji and J. J. Clark.  Going from image to video saliency: Augmenting image salience with dynamic attentional push.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7501–7511, 2018.
  * [14] M. Grundmann, V. Kwatra, M. Han, and I. Essa.  Efficient hierarchical graph-based video segmentation.  In 2010 ieee computer society conference on computer vision and pattern recognition, pages 2141–2148. IEEE, 2010.
  * [15] K. He, G. Gkioxari, P. Dollár, and R. Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [16] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [17] S. He, H. R. Tavakoli, A. Borji, Y. Mi, and N. Pugeault.  Understanding and visualizing deep visual saliency models.  In Proceedings of the ieee conference on computer vision and pattern recognition, pages 10206–10215, 2019.
  * [18] V. Hosu, B. Goldlucke, and D. Saupe.  Effective aesthetics prediction with multi-level spatially pooled features.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9375–9383, 2019.
  * [19] L. Itti, C. Koch, and E. Niebur.  A model of saliency-based visual attention for rapid scene analysis.  IEEE Transactions on pattern analysis and machine intelligence, 20(11):1254–1259, 1998.
  * [20] S. D. Jain, B. Xiong, and K. Grauman.  Fusionseg: Learning to combine motion and appearance for fully automatic segmentation of generic objects in videos.  In 2017 IEEE conference on computer vision and pattern recognition (CVPR), pages 2117–2126. IEEE, 2017.
  * [21] B. Jiang, X. Jiang, A. Zhou, J. Tang, and B. Luo.  A unified multiple graph learning and convolutional network model for co-saliency estimation.  In Proceedings of the 27th ACM International Conference on Multimedia, pages 1375–1382, 2019.
  * [22] L. Jiang, M. Xu, T. Liu, M. Qiao, and Z. Wang.  Deepvs: A deep learning based video saliency prediction approach.  In Proceedings of the european conference on computer vision (eccv), pages 602–617, 2018.
  * [23] M. Jiang, S. Huang, J. Duan, and Q. Zhao.  Salicon: Saliency in context.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1072–1080, 2015.
  * [24] Y. J. Koh and C.-S. Kim.  Primary object segmentation in videos based on region augmentation and reduction.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 7417–7425. IEEE, 2017.
  * [25] S. Kong, X. Shen, Z. Lin, R. Mech, and C. Fowlkes.  Photo aesthetics ranking network with attributes and content adaptation.  In European Conference on Computer Vision, pages 662–679. Springer, 2016.
  * [26] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  In NIPS, 2012.
  * [27] G. Leifman, D. Rudoy, T. Swedish, E. Bayro-Corrochano, and R. Raskar.  Learning gaze transitions from depth to improve video saliency estimation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1698–1707, 2017.
  * [28] B. Li, Z. Sun, Q. Wang, and Q. Li.  Co-saliency detection based on hierarchical consistency.  In Proceedings of the 27th ACM International Conference on Multimedia, pages 1392–1400, 2019.
  * [29] B. Li, W. Wu, Q. Wang, F. Zhang, J. Xing, and J. Yan.  Siamrpn++: Evolution of siamese visual tracking with very deep networks.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 4277–4286, 2018.
  * [30] G. Li, Y. Xie, L. Lin, and Y. Yu.  Instance-level salient object segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2386–2395, 2017.
  * [31] G. Li, Y. Xie, T. Wei, K. Wang, and L. Lin.  Flow guided recurrent neural encoder for video salient object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3243–3252, 2018.
  * [32] J. Li, Y. Wang, C. Wang, Y. Tai, J. Qian, J. Yang, C. Wang, J. Li, and F. Huang.  Dsfd: dual shot face detector.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5060–5069, 2019.
  * [33] Y. Li, X. Hou, C. Koch, J. M. Rehg, and A. L. Yuille.  The secrets of salient object segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 280–287, 2014.
  * [34] M. Lin, Q. Chen, and S. Yan.  Network in network.  arXiv preprint arXiv:1312.4400, 2013.
  * [35] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [36] T.-Y. Lin, M. Maire, S. J. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick.  Microsoft coco: Common objects in context.  ArXiv, abs/1405.0312, 2014.
  * [37] D. Liu, Z. Wu, X. Lin, and R. Ji.  Towards perceptual video cropping with curve fitting.  Multimedia Tools and Applications, 75(20):12465–12475, 2016.
  * [38] K. Liu, W. Liu, C. Gan, M. Tan, and H. Ma.  T-c3d: Temporal convolutional 3d network for real-time action recognition.  In AAAI, 2018.
  * [39] N. Liu, J. Han, and M.-H. Yang.  Picanet: Learning pixel-wise contextual attention for saliency detection.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3089–3098, 2018.
  * [40] T. Liu, Z. Yuan, J. Sun, J. Wang, N. Zheng, X. Tang, and H.-Y. Shum.  Learning to detect a salient object.  IEEE Transactions on Pattern analysis and machine intelligence, 33(2):353–367, 2010.
  * [41] Y. Liu, Q. Zhang, D. Zhang, and J. Han.  Employing deep part-object relationships for salient object detection.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1232–1241, 2019.
  * [42] P. Lu, H. Zhang, X. Peng, and X. Jin.  An end-to-end neural network for image cropping by learning composition from aesthetic photos.  ArXiv, abs/1907.01432, 2019.
  * [43] Y.-F. Ma and H.-J. Zhang.  Contrast-based image attention analysis by using fuzzy growing.  In Proceedings of the eleventh ACM international conference on Multimedia, pages 374–381, 2003.
  * [44] N. Murray, L. Marchesotti, and F. Perronnin.  Ava: A large-scale database for aesthetic visual analysis.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2408–2415. IEEE, 2012.
  * [45] P. Ochs and T. Brox.  Object segmentation in video: a hierarchical variational approach for turning point trajectories into dense regions.  In 2011 International Conference on Computer Vision, pages 1583–1590. IEEE, 2011.
  * [46] F. Perazzi, P. Krähenbühl, Y. Pritch, and A. Hornung.  Saliency filters: Contrast based filtering for salient region detection.  In 2012 IEEE conference on computer vision and pattern recognition, pages 733–740. IEEE, 2012.
  * [47] Q. Qi, S. Zhao, J. Shen, and K.-M. Lam.  Multi-scale capsule attention-based salient object detection with multi-crossed layer connections.  In 2019 IEEE International Conference on Multimedia and Expo (ICME), pages 1762–1767. IEEE, 2019.
  * [48] S. Ren, K. He, R. Girshick, and J. Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [49] M. Rubinstein, D. Gutierrez, O. Sorkine, and A. Shamir.  A comparative study of image retargeting.  In ACM SIGGRAPH Asia 2010 papers, pages 1–10. 2010.
  * [50] J. F. Schlag, A. C. Sanderson, C. P. Neuman, and F. C. Wimberly.  Implementation of automatic focusing algorithms for a computer vision system with camera control.  Technical report, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST, 1983\.
  * [51] A. Siris, J. Jiao, G. K. Tam, X. Xie, and R. W. Lau.  Inferring attention shift ranks of objects for image saliency.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12133–12143, 2020.
  * [52] H. Song, W. Wang, S. Zhao, J. Shen, and K.-M. Lam.  Pyramid dilated deeper convlstm for video salient object detection.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 715–731, 2018.
  * [53] T. Souček, J. Moravec, and J. Lokoč.  Transnet: A deep network for fast detection of common shot transitions.  arXiv preprint arXiv:1906.03363, 2019.
  * [54] J. Sun and H. Ling.  Scale and object aware image thumbnailing.  International journal of computer vision, 104(2):135–153, 2013\.
  * [55] J. M. Tenenbaum.  Accommodation in computer vision.  Technical report, Stanford Univ Ca Dept of Computer Science, 1970.
  * [56] P. Tokmakov, K. Alahari, and C. Schmid.  Learning video object segmentation with visual memory.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4481–4490, 2017.
  * [57] D. Tran, L. D. Bourdev, R. Fergus, L. Torresani, and M. Paluri.  Learning spatiotemporal features with 3d convolutional networks.  2015 IEEE International Conference on Computer Vision (ICCV), pages 4489–4497, 2015.
  * [58] Y. Tu, L. Niu, W. Zhao, D. Cheng, and L. Zhang.  Image cropping with composition and saliency aware aesthetic score map.  In AAAI, pages 12104–12111, 2020.
  * [59] D. Vaquero, M. Turk, K. Pulli, M. Tico, and N. Gelfand.  A survey of image retargeting techniques.  In Applications of Digital Image Processing XXXIII, volume 7798, page 779814. International Society for Optics and Photonics, 2010.
  * [60] Q. Wang, L. Zhang, L. Bertinetto, W. Hu, and P. H. S. Torr.  Fast online object tracking and segmentation: A unifying approach.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1328–1338, 2018.
  * [61] W. Wang, Q. Lai, H. Fu, J. Shen, H. Ling, and R. Yang.  Salient object detection in the deep learning era: An in-depth survey.  arXiv preprint arXiv:1904.09146, 2019.
  * [62] W. Wang, J. Shen, and H. Ling.  A deep network solution for attention and aesthetics aware photo cropping.  IEEE transactions on pattern analysis and machine intelligence, 41(7):1531–1544, 2018.
  * [63] W. Wang, J. Shen, J. Xie, M.-M. Cheng, H. Ling, and A. Borji.  Revisiting video saliency prediction in the deep learning era.  IEEE transactions on pattern analysis and machine intelligence, 2019\.
  * [64] W. Wang, J. Shen, Y. Yu, and K.-L. Ma.  Stereoscopic thumbnail creation via efficient stereo saliency detection.  IEEE transactions on visualization and computer graphics, 23(8):2014–2027, 2016.
  * [65] Z. Wang, X. Yan, Y. Han, and M. Sun.  Ranking video salient object detection.  In Proceedings of the 27th ACM International Conference on Multimedia, pages 873–881, 2019.
  * [66] Z. Wu, L. Su, and Q. Huang.  Cascaded partial decoder for fast and accurate salient object detection.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3907–3916, 2019.
  * [67] F. Xiao and Y. Jae Lee.  Track and segment: An iterative unsupervised approach for video object proposals.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 933–942, 2016.
  * [68] J. Yan, S. Lin, S. Bing Kang, and X. Tang.  Learning the change for automatic image cropping.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 971–978, 2013.
  * [69] Z. Yang, Q. Wang, L. Bertinetto, W. Hu, S. Bai, and P. H. S. Torr.  Anchor diffusion for unsupervised video object segmentation.  2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 931–940, 2019.
  * [70] P. Zarchan and H. Musoff.  Fundamentals of kalman filtering: A practical approach.  2001\.
  * [71] H. Zeng, L. Li, Z. Cao, and L. Zhang.  Reliable and efficient image cropping: A grid anchor based approach.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5949–5957, 2019.
  * [72] H. Zeng, L. Li, Z. Cao, and L. Zhang.  Grid anchor based image cropping: A new benchmark and an efficient model.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020\.
  * [73] J. Zhang, S. Sclaroff, Z. Lin, X. Shen, B. Price, and R. Mech.  Unconstrained salient object detection via proposal subset optimization.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5733–5742, 2016.
  * [74] P. Zhang, L. Su, L. Li, B. Bao, P. Cosman, G. Li, and Q. Huang.  Training efficient saliency prediction models with knowledge distillation.  In Proceedings of the 27th ACM International Conference on Multimedia, pages 512–520, 2019.
  * [75] X. Zhang, F. Wan, C. Liu, R. Ji, and Q. Ye.  Freeanchor: Learning to match anchors for visual object detection.  In Advances in Neural Information Processing Systems, pages 147–155, 2019.
  * [76] R. Zhao, W. Ouyang, H. Li, and X. Wang.  Saliency detection by multi-context deep learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1265–1274, 2015.

|  Tun Zhu received his bachelor’s degree in Computer Science and Technology
from University of Electronic Science and Technology of China in 2018. He is
currently a Master candidate in the College of Computer Science and
Technology, Zhejiang University of China. His research interests include
machine learning and computer vision.
---|---
|  Daoxin Zhang received his bachelor’s and master’s degrees in Mathematics
and Computer Science respectively both from Zhejiang University in 2016 and
2019. He is currently an Algorithm Engineer II in Alibaba Digital
Media&Entertainment Group. His research interests include multimedia, machine
learning and computer vision.
---|---
|  Yao Hu is a Senior Staff Algorithm Engineer of Alibaba, now leads the
Artificial Intelligence Department of Alibaba Digital Media&Entertainment
Group. He receives the PhD degree in machine learning from Zhejiang University
in 2015. Before joining Alibaba, he leads the machine learning team working on
DiDi’s travel business and autonomous car. His research interests include
machine learning, online learning theory and computer vision. He has published
more than 40 papers in TPAMI, SIGKDD, ICML, CVPR, ICCV, IJCAI, and AAAI.
---|---
|  Tianran Wang received his bachelor’s degree in Computer Science and
Technology from Hangzhou Dianzi University in 2018 and master’s degree in
Software Engineering from Zhejiang University in 2020. He is currently an
Algorithm Engineer of Alibaba. His research interests include machine learning
and computer vision.
---|---
|  Xiaolong Jiang received the bachelor degree in electrical engineering from
Beihang University in 2012, and acquired his master degree in computer
engineering from Columbia University in 2014. He achieved his PhD degree in
electrical engineering from Beihang University in 2019, during which he joined
CRCV in University of Central Florida as a visiting scholar. He was a research
intern at IDL lab in Baidu in 2018, and now is a researcher in Alibaba Digital
Media&Entertainment Group.
---|---
|  Jianke Zhu received the master’s degree from University of Macau in
Electrical and Electronics Engineering, and the PhD degree in computer science
and engineering from The Chinese University of Hong Kong, Hong Kong in 2008.
He held a post-doctoral position at the BIWI Computer Vision Laboratory, ETH
Zürich, Switzerland. He is currently a Professor with the College of Computer
Science, Zhejiang University, Hangzhou, China. His research interests include
computer vision and multimedia information retrieval. He is a Senior member of
the IEEE.
---|---
|  Jiawei Li received his bachelor’s degree in Computer Science from China
Agricultural University in 2012. He is currently a Staff Algorithm Engineer of
Alibaba. His research interests include machine learning and recommender
system.
---|---


#  An analog of the Furstenberg-Katznelson-Weiss theorem on triangles in sets
of positive density in finite field geometries

David Covert, Derrick Hart, Alex Iosevich and Ignacio Uriarte-Tuero
Department of Mathematics, University of Missouri, Columbia, MO 65211-4100
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We prove that if the cardinality of a subset of the $2$-dimensional vector
space over a finite field with $q$ elements is $\geq\rho q^{2}$, with
$\frac{1}{\sqrt{q}}<<\rho\leq 1$, then it contains an isometric copy of $\geq
c\rho q^{3}$ triangles.

A. Iosevich was supported by the NSF Grant DMS04-56306

##  1\. Introduction

A classical result due to Furstenberg, Katznelson and Weiss ([4]; see also
[1]) says that if $E\subset{\mathbb{R}}^{2}$ has positive upper Lebesgue
density, then for any $\delta>0$, the $\delta$-neighborhood of $E$ contains a
congruent copy of a sufficiently large dilate of every three point
configuration. An example due to Bourgain shows that if the three point
configuration in question is an arithmetic progression, then taking a
$\delta$-neighborhood is necessary and the result is not otherwise true.
However, it seems reasonable to conjecture that if the three point
configuration is non-degenerate in the sense that the three points do not lie
on the same line, then a set of positive density contains a sufficiently large
dilate of this configuration.

When the size of the point set is smaller than the dimension of ambient
Euclidean space, taking a $\delta$-neighborhood is not necessary, as shown by
Bourgain in [1]. He proves that if $E\subset{\mathbb{R}}^{d}$ has positive
upper density and $\Delta$ is a $k$-simplex with $k<d$, then $E$ contains a
rotated and translated image of every large dilate of $\Delta$. The case $k=d$
and $k=d+1$ remain open, however. See also, for example, [2], [3], [7], [11]
and [13] on related problems and their connections with discrete analogs.

In the geometry of the integer lattice ${\mathbb{Z}}^{d}$, related problems
have been recently investigated by Akos Magyar in [9] and [10]. In particular,
he proves in [10] that if $d>2k+4$ and $E\subset{\mathbb{Z}}^{d}$ has positive
upper density, then all large (depending on density of $E$) dilates of a
$k$-simplex in ${\mathbb{Z}}^{d}$ can be embedded in $E$. Once again, serious
difficulties arise when the size of the simplex is sufficiently large with
respect to the ambient dimension.

The purpose of this paper is to investigate an analog of this question in
finite field geometries. A step in this direction was taken by the second and
third listed authors in [5]. They prove that if
$E\subset{\mathbb{F}}_{q}^{d}$, the $d$-dimensional vector space over the
finite field with $q$ elements with $|E|\geq
Cq^{d\frac{k-1}{k}+\frac{k-1}{2}}$ and $\Delta$ is a $k$-dimensional simplex,
then there exists $\tau\in{\mathbb{F}}_{q}^{d}$ and $O\in
SO_{d}({\mathbb{F}}_{q})$ such that $\tau+O(\Delta)\subset E$. The result is
only non-trivial in the range $d\geq\left({}^{k}_{2}\right)$ as larger
simplexes are out of range of the methods used.

The purpose of this paper is to address the case of triangles in two-
dimensional vector spaces over finite fields. Given
$E\subset{\mathbb{F}}_{q}^{2}$, define

$T_{3}(E)=\\{(x,y,z)\in E\times E\times E\\}\ /\sim$

with the equivalence relation $\sim$ such that
$(x,y,z)\sim(x^{\prime},y^{\prime},z^{\prime})$ if there exists
$\tau\in{\mathbb{F}}_{q}^{2}$ and $O\in SO_{2}({\mathbb{F}}_{q})$, the set of
two-by-two orthogonal matrices over ${\mathbb{F}}_{q}$ with determinant $1$,
such that

$(x^{\prime},y^{\prime},z^{\prime})=(O(x)+\tau,O(y)+\tau,O(z)+\tau).$

Our main result is the following.

######  Theorem 1.1.

Let $E\subset{\mathbb{F}}_{q}^{2}$, and suppose that

$|E|\geq\rho q^{2}$

for some $\frac{C}{\sqrt{q}}\leq\rho\leq 1$ with a sufficiently large constant
$C>0$. Then there exists $c>0$ such that

$|T_{3}(E)|\geq c\rho q^{3}.$

In other words, we show that if $E$ has density $\geq\rho$, then the set of
triangles determined by $E$, up to congruence, has density $\geq c\rho$, where
$\rho$ is allowed to depend on $q$ within the parameters given above.

######  Remark 1.2.

Note that in contrast to the Furstenberg-Katznelson-Weiss result ([4]) we do
not use dilations. This is natural because there is no order in
${\mathbb{F}}_{q}$, so a reasonable analog of proving a result for
sufficiently large dilates of a three-point configuration in Euclidean space
is proving it for all dilates in finite field geometries.

######  Remark 1.3.

Observe that the density condition $|E|\geq\rho q^{2}$ immediately tells us
that the numbers of three-tuples determined by $E$, up to congruence, is

$\geq\frac{\rho^{3}q^{6}}{q\cdot q^{2}}=\rho^{3}q^{3},$

since the size of the translation group is $q^{2}$ and the size of the
rotation group is $q$. Thus our result can be viewed as shaving off two powers
of $\rho$ from this (trivial) estimate. It is conceivable that $\rho q^{3}$
may be replaced by $cq^{3}$, for some $0<c<1$, or even $(1-o(1))q^{3}$.

###  1.1. Finite field analog of Bourgain’s example

The following variant of Bourgain’s Euclidean construction (see [4]) shows
that for general subsets of ${\mathbb{F}}_{q}^{2}$ satisfying the density
assumption $|E|\geq\rho q^{2}$ for some $\rho>0$ it is not possible to recover
isometric copies of all three point configurations.

Let $A\subset{\mathbb{F}}_{q}^{*}$, the multiplicative group of
${\mathbb{F}}_{q}$, such that $|A|\geq\rho q$ for some $\rho>0$ and

$2A+2A-4A\not={\mathbb{F}}_{q}.$

We shall give an (easy) construction of such a set at the end of the argument.
Let

$E=\bigcup_{t\in A}S_{t},$

where

$S_{t}=\\{x\in{\mathbb{F}}_{q}^{2}:||x||=t\\},$

with

$||x||=x_{1}^{2}+x_{2}^{2}.$

It is not difficult to check that $|E|\geq\rho q^{2}$ using the classical fact
that a circle in ${\mathbb{F}}_{q}^{2}$ has $q\pm 1$ points. See Lemma 3.2
below. Now consider a three-tuple

$\left(x,y,\frac{x+y}{2}\right)$

such that

$||x-y||\notin 2A+2A-4A.$

We claim that such a three-tuple cannot be contained in $E$. We shall argue by
contradiction. Indeed, the parallelogram law says that

$2\left|\left|\frac{x+y}{2}\right|\right|+2\left|\left|\frac{x-y}{2}\right|\right|=||x||+||y||,$

so

$||x-y||=2||x||+2||y||-4\left|\left|\frac{x+y}{2}\right|\right|,$

which is an element of $2A+2A-4A$. By construction, $||x-y||\notin 2A+2A-4A$,
so we are done. It remains to show that the set $A$ with the desired
properties exists. Let $q$ be a large prime number and denote the elements of
the corresponding field ${\mathbb{F}}_{q}$ by

$\\{0,1,2,\dots,q-1\\}.$

Let $A$ consists of multiples of $8$ that are less than or equal to $q/32$.
This set is clearly of positive density and $2A+2A-4A\not={\mathbb{F}}_{q}$
since all of its elements are even as wrap-around is precluded from taking
place by the condition that the largest element of $A$ is $\leq q/32$.

######  Remark 1.4.

It is important to note that we do not know a single example of this type
involving a non-degenerate triangle, one whose vertices do not lie on a line.

##  2\. Proof of the main result (Theorem 1.1)

We prove Theorem 1.1 by reducing it to a statistically more precise statement
about hinges. More precisely, we observe that it suffices to show that if
$|E|\geq\rho q^{2}$, then

(2.1) $|\\{(a,b,c)\in{\mathbb{F}}_{q}^{3}:|T_{a,b,c}(E)|>0\\}|\geq c\rho
q^{3},$

where

$T_{a,b,c}(E)=\\{(x,y,z)\in E\times E\times
E:||x-y||=a,||x-z||=b,||y-z||=c\\},$

with

$||x||=x_{1}^{2}+x_{2}^{2}.$

This follows from the following simple lemma from [5], which we prove at the
end of the paper for the sake of completeness.

######  Lemma 2.1.

Let $P$ be a (non-degenerate) simplex with vertices $V_{0},V_{1},\dots,V_{k}$,
with $V_{j}\in{\mathbb{F}}_{q}^{d}$. Let $P^{\prime}$ be another (non-
degenerate) simplex with vertices
$V^{\prime}_{0},V^{\prime}_{1},\dots,V^{\prime}_{k}$. Suppose that

(2.2) $||V_{i}-V_{j}||=||V^{\prime}_{i}-V^{\prime}_{j}||$

for all $i,j$. Then there exists $\tau\in{\mathbb{F}}_{q}^{d}$ and $O\in
SO_{d}({\mathbb{F}}_{q})$ such that $\tau+O(P)=P^{\prime}$.

The key estimate is the following result about hinges, which is interesting in
its own right.

######  Theorem 2.2.

Suppose that $E\subset{\mathbb{F}}_{q}^{2}$ and let $a,b\not=0$. Then

$|\\{(x,y,z)\in E\times E\times
E:||x-y||=a,||x-z||=b\\}|={|E|}^{3}q^{-2}+O(q|E|).$

We can use this result as follows. If $|E|>>q^{\frac{3}{2}}$, then

$|\\{(x,y,z)\in E\times E\times
E:||x-y||=a,||x-z||=b\\}|={|E|}^{3}q^{-2}(1+o(1)).$

By the pigeon-hole principle, there exists $x\in E$ such that

$|\\{(y,z)\in E\times E:||x-y||=a,||x-z||=b\\}|\geq{|E|}^{2}q^{-2}.$

Suppose that the number of elements of $SO_{2}({\mathbb{F}}_{q})$ that leave
$x$ fixed and keep $(y,z)$ inside the pinned hinge is $\leq\rho q$. Then
recalling our assumption that

$|E|\geq\rho q^{2}\;,$

we get that the number of distinct distances $c$ from $\\{y\in E:||x-y||=a\\}$
to $\\{z\in E:||x-z||=b\\}$ is at least

${|E|}^{2}q^{-2}\;\frac{1}{\rho q}\geq\frac{1}{2}\rho q,$

and hence, since there are $(q-1)$ possible choices for $a$ and $b$, (2.1)
follows.

If the number of elements of $SO_{2}({\mathbb{F}}_{q})$ that leave $x$ fixed
and keep $(y,z)$ inside the pinned hinge is $>\rho q$, then both the circle of
radius $a$, centered at $x$, and the circle of radius $b$, centered at $x$,
contain more than $\rho q$ elements of $E$. The following simple lemma, whose
proof is given at the end of this paper, shows that this implies that the
number of distinct distances $c$ from

$\\{y\in E:||x-y||=a\\}\ \text{to}\ \\{z\in E:||x-z||=b\\}$

is $\geq\frac{1}{4}\rho q$, and thus (2.1) follows.

######  Lemma 2.3.

Suppose that $a,b,c\not=0$. Let
$w=(w_{1},w_{2})\in\\{y\in{\mathbb{F}}_{q}^{2}:||x-y||=a\\}$. Consider the set

$I=\\{z\in{\mathbb{F}}_{q}^{2}:||x-z||=b\\}\cap\\{u\in{\mathbb{F}}_{q}^{2}:||w-u||=c\\}\;.$

For at least $\frac{q-3}{2}$ different values of $c$, we have that
$I\neq\emptyset$.

Thus the proof of Theorem 1.1 has been reduced to Theorem 2.2.

###  2.1. Fourier analysis used in this paper

Let $\mathbb{F}_{q}^{d}$ be the $d$-dimensional vector space over the finite
field ${\mathbb{F}}_{q}$. The Fourier transform of a function

$f:\mathbb{F}_{q}^{d}\rightarrow\mathbb{C}$

is given by

$\widehat{f}(m)=q^{-d}\sum_{x\in{\mathbb{F}}_{q}^{d}}f(x)\chi(-x\cdot m),$

where $\chi$ is an additive character on $\mathbb{F}_{q}$.

The orthogonality property of the Fourier Transform says that

$q^{-d}\sum_{x\in\mathbb{F}_{q}^{d}}\chi(-x\cdot m)=1$

for $m=(0,\dots,0)$ and $0$ otherwise. This property yields many of the
standard properties of the Fourier Transform. We summarize the basic
properties of the Fourier Transform used in this paper as follows.

######  Lemma 2.4.

Let

$f,g:\mathbb{F}_{q}^{d}\rightarrow\mathbb{C}.$

Then

$\hat{f}(0,\dots,0)=q^{-d}\sum_{x\in\mathbb{F}_{q}^{d}}f(x),$
$q^{-d}\sum_{x\in\mathbb{F}_{q}^{d}}f(x)\overline{g(x)}=\sum_{m\in\mathbb{F}_{q}^{d}}\hat{f}(m)\overline{\hat{g}(m)},$

and

$f(x)=\sum_{m\in\mathbb{F}_{q}^{d}}\hat{f}(m)\chi(x\cdot m).$

##  3\. Proof of Theorem 2.2

Let

$D_{a}=\\{(x,y)\in E\times E:||x-y||=a\\}$

and identify $D_{a}$ with its indicator function. We need the following result
from [6], proved at the end of this paper for the sake of completeness.

######  Theorem 3.1.

Let $E\subset{\mathbb{F}}_{q}^{d}$ and suppose that $t\not=0$. Then

$\sum_{x,y}D_{t}(x,y)={|E|}^{2}q^{-1}+O(q^{\frac{d-1}{2}}|E|).$

Let

$S_{a}=\\{x\in{\mathbb{F}}_{q}^{d}:x_{1}^{2}+\dots+x_{d}^{2}=a\\}$

and identify $S_{a}$ with its indicator function. Now setting $d=2$ and using
Lemma 2.4 we see that

$|\\{(x,y,z)\in E\times E\times E:||x-y||=a,||x-z||=b\\}|$
$=\sum_{x,y,z}D_{a}(x,y)E(z)S_{b}(x-z)$

(3.1) $=q^{6}\sum_{m}\widehat{D}_{a}(m,0,0)\widehat{E}(m)\widehat{S}_{b}(m).$

We need the following results about the Fourier transform of the sphere which
we state in the $d$-dimensional context.

######  Lemma 3.2.

Let $d\geq 2$ and define
$S_{b}=\\{x\in{\mathbb{F}}_{q}^{d}:x_{1}^{2}+\dots+x_{d}^{2}=b\\}.$ Suppose
that $b\not=0$ and $m\not=(0,\dots,0)$.

(3.2) $|\widehat{S}_{b}(m)|\leq 2q^{-\frac{d+1}{2}}.$

For any $a\in{\mathbb{F}}^{*}_{q}$,

(3.3) $|S_{a}|=q^{d-1}+o(q^{d-1}).$

We postpone the proof of the lemma until the end of the paper. In the
meantime, we see that Lemma 2.4 implies that the expression in (3.1) equals

$|D_{a}||E||S_{b}|q^{-2}$
$+q^{6}\cdot\sum_{m\not=(0,0)}\widehat{D}_{a}(m,0,0)\widehat{E}(m)\widehat{S}_{b}(m)=I+R(a,b).$

In view of Lemma 3.2 and Theorem 3.1,

$I={|E|}^{3}q^{-2}(1+o(1)).$

We have

$R(a,b)=q^{6}\sum_{m\not=(0,0)}\widehat{D}_{a}(m,0,0)\widehat{E}(m)\widehat{S}_{b}(m).$

Using Lemma 3.2 once again and applying Cauchy-Schwartz followed by Lemma 2.4,
we see that

${|R(a,b)|}^{2}\leq 4q^{-3}\cdot
q^{12}\sum_{m}{|\widehat{E}(m)|}^{2}\cdot\sum_{m}{|\widehat{D}_{a}(m,0,0)|}^{2}$

(3.4) $=4q^{9}\cdot q^{-2}|E|\cdot\sum_{m}{|\widehat{D}_{a}(m,0,0)|}^{2},$

and thus the matter is reduced to bounds for

$\sum_{m}{|\widehat{D}_{a}(m,0,0)|}^{2}.$

By definition,

$\widehat{D}_{a}(m,0,0)=q^{-4}\sum_{x,y}\chi(-x\cdot m)E(x)E(y)S_{a}(x-y)$
$=q^{-2}\cdot q^{-2}\sum_{x}\chi(-x\cdot m)E(x)|E\cap S_{a}(x)|,$

where

$S_{a}(x)=\\{y\in{\mathbb{F}}_{q}^{2}:||x-y||=a\\}.$

It follows from above and Lemma 2.4 that

$\sum_{m}{|\widehat{D}_{a}(m,0,0)|}^{2}=q^{-4}\sum_{m}{|\widehat{f}(m)|}^{2}$
(3.5) $=q^{-4}\cdot q^{-2}\sum_{x}{|f(x)|}^{2},$

where

$f(x)=E(x)|E\cap S_{a}(x)|,$

and matters are reduced to the estimation of

$\sum_{x}{|f(x)|}^{2}.$

######  Lemma 3.3.

With the notation above, if $q$ is sufficiently large, then

$\sum_{x\in E}{|E\cap S_{a}(x)|}^{2}\leq 8q|E|.$

To prove the result, we write

$|E\cap S_{a}(x)|=\sum_{y}E(y)S_{a}(x-y)$
$=|E||S_{a}|q^{-2}+q^{2}\sum_{m\not=(0,0)}\chi(x\cdot
m)\widehat{E}(m)\widehat{S}_{a}(m)$ $=A+B(x).$

It is easy to see that plugging in $A$ leads to a better estimate than
claimed. Now,

$\sum_{x\in E}{|B(x)|}^{2}\leq\sum_{x\in{\mathbb{F}}_{q}^{2}}{|B(x)|}^{2}$
$=q^{4}\sum_{m,m^{\prime}\not=(0,0)}\widehat{E}(m)\overline{\widehat{E}(m^{\prime})}\widehat{S}_{a}(m)\overline{\widehat{S}_{a}(m^{\prime})}\sum_{x}\chi(x\cdot(m-m^{\prime}))$
$=q^{6}\sum_{m\not=(0,0)}{|\widehat{E}(m)|}^{2}{|\widehat{S}_{a}(m)|}^{2},$

and by Lemma 3.2 this quantity is

$\leq 4q^{6}\cdot q^{-3}\sum_{m\not=(0,0)}{|\widehat{E}(m)|}^{2},$

which, by Lemma 2.4 is

$\leq 4q|E|,$

as claimed.

Plugging everything back into (3.5) and then (3.4), we see that

(3.6) ${|R(a,b)|}^{2}\leq 32q^{9}\cdot q^{-2}\cdot|E|\cdot q^{-6}\cdot q|E|$
$=32q^{2}{|E|}^{2}.$

Recall that

$|\\{(x,y,z)\in E\times E\times E:||x-y||=a,||x-z||=b\\}|=I+R(a,b),$

where

$I={|E|}^{3}q^{-2}(1+o(1))$

and

$|R(a,b)|\leq 8q|E|$

for $q$ sufficiently large by (3.6) above.

It follows that

$|\\{(x,y,z)\in E\times E\times
E:||x-y||=a,||x-z||=b\\}|={|E|}^{3}q^{-2}(1+o(1))$

if $|E|>Cq^{\frac{3}{2}}$ with a sufficiently large constant $C>0$, as
claimed.

##  4\. Proof of Theorem 3.1

We have

$\sum_{x,y}D_{t}(x,y)=\sum_{x,y}E(x)E(y)S_{t}(x-y).$

Applying Fourier inversion to the sphere,

$\displaystyle\sum_{x,y}D_{t}(x,y)=\sum_{x,y}E(x)E(y)\sum_{m}\widehat{S}_{t}(m)\chi(m\cdot(x-y))$
$\displaystyle=q^{2d}\sum_{m}{|\widehat{E}(m)|}^{2}\widehat{S}_{t}(m)$
$\displaystyle={|E|}^{2}\cdot
q^{-d}\cdot|S_{t}|+q^{2d}\sum_{m\not=(0,\dots,0)}{|\widehat{E}(m)|}^{2}\widehat{S}_{t}(m)$
$\displaystyle=M+R.\,$

By Lemma 3.2,

$M=\frac{{|E|}^{2}}{q}+|E|^{2}o(q^{-1}),$

and using Lemma 3.2 once again, along with Lemma 2.4, we have

$\displaystyle|R|$ $\displaystyle\leq 2q^{2d}\cdot
q^{-\frac{d+1}{2}}\cdot\sum_{m}{|\widehat{E}(m)|}^{2}$
$\displaystyle=2q^{\frac{d-1}{2}}\cdot|E|.$

This completes the proof.

##  5\. Proof of Lemma 3.2

For any $l\in{\mathbb{F}}^{d}_{q}$, we have

(5.1)
$\begin{array}[]{llllll}\widehat{S}_{t}(l)&=&q^{-d}\sum_{x\in{\mathbb{F}}^{d}_{q}}q^{-1}\sum_{j\in{\mathbb{F}}_{q}}\chi(j(\|x\|-t))\chi(-x\cdot
l)\\\ \hfill\\\
&=&q^{-1}\delta(l)+q^{-d-1}\sum_{j\in{\mathbb{F}}^{*}_{q}}\chi(-jt)\sum_{x}\chi(j\|x\|)\chi(-x\cdot
l),\\\ \end{array}$

where the notation $\delta(l)=1$ if $l=(0\ldots,0)$ and $\delta(l)=0$
otherwise.

Now

$\widehat{S}_{t}(l)=q^{-1}\delta(l)+Q^{d}q^{-\frac{d+2}{2}}\sum_{j\in{\mathbb{F}}^{*}_{q}}\chi\left(\frac{\|l\|}{4j}+jt\right)\eta^{d}(-j).$

In the last line we have completed the square, changed $j$ to $-j$, and used
$d$ times the Gauss sum equality (see e.g. [8])

(5.2)
$\sum_{c\in{\mathbb{F}}_{q}}\chi(jc^{2})=\eta(j)\sum_{c\in{\mathbb{F}}_{q}}\eta(c)\chi(c)=\eta(j)\sum_{c\in{\mathbb{F}}_{q}^{*}}\eta(c)\chi(c)=Q\sqrt{q}\,\eta(j),$

where the constant $Q$ equals $\pm 1$ or $\pm i$, depending on $q$, and $\eta$
is the quadratic multiplicative character (or the Legendre symbol) of
${\mathbb{F}}_{q}^{*}$.

The conclusion to the first and second parts of Lemma 3.2 now follows from
standard Gauss sum estimates (see e.g. [8]) and the following classical
estimate due to A. Weil ([12]).

######  Theorem 5.1.

Let

$K(a)=\sum_{s\not=0}\chi(as+s^{-1})\psi(s),$

where $\psi$ is a multiplicative character on ${\mathbb{F}}_{q}^{*}$. Then, if
$a\not=0$,

$|K(a)|\leq 2\sqrt{q}.$

##  6\. Proof of Lemma 2.1

Let $\pi_{r}(x)$ denote the $r$th coordinate of $x$. Taking translations into
account, we may assume that $V_{0}=(0,\dots,0)$. We may also assume that
$V_{1},\dots,V_{k}$ are contained in ${\mathbb{F}}_{q}^{k}$. The condition
(2.2) implies that

(6.1)
$\sum_{r=1}^{k}\pi_{r}(V_{i})\pi_{r}(V_{j})=\sum_{r=1}^{k}\pi_{r}(V_{i}^{\prime})\pi_{r}(V_{j}^{\prime}).$

Let $T$ be the linear transformation uniquely determined by the condition

$T(V_{i})=V^{\prime}_{i}.$

In order to prove that $T$ is orthogonal, it suffices to show that

$||Tx||=||x||$

for any $x\not=(0,\dots,0)$. We give this (standard) reduction below for the
sake of reader’s convenience.

Since $V_{j}$s form a basis, by assumption, we have

$x=\sum_{i}t_{i}V_{i},$

so it suffices to show that

$||x||=\sum_{r}\sum_{i,j}t_{i}t_{j}\pi_{r}(V_{i})\pi_{r}(V_{j})$
$=\sum_{r}\sum_{i,j}t_{i}t_{j}\pi_{r}(V^{\prime}_{i})\pi_{r}(V^{\prime}_{j})=||Tx||,$

which follows immediately from (6.1).

Observe that we used the fact that orthogonality of $T$, the condition that
$T^{t}\cdot T=I$ is equivalent to the condition that $||Tx||=||x||$. To see
this observe that to show that $T^{t}\cdot T=I$ it suffices to show that
$T^{t}Tx=x$ for all non-zero $x$. This, in turn, is equivalent to the
statement that

$<T^{t}Tx,x>=||x||,$

where

$<x,y>=\sum_{i=1}^{k}x_{i}y_{i}.$

Now,

$<T^{t}Tx,x>=<Tx,Tx>$

by definition of the transpose, so the stated equivalence is established. This
completes the proof of Lemma 2.1.

##  7\. Proof of Lemma 2.3

After a translation, we may assume without loss of generality that $x=(0,0)$.
We are looking for solutions $(s,t)$ to the system of equations

(7.3) $\displaystyle\left\\{\begin{array}[]{l}(s-w_{1})^{2}+(t-w_{2})^{2}=c\\\
s^{2}+t^{2}=b\end{array}\right.$

with the assumption that $w_{1}^{2}+w_{2}^{2}=a$. Then (7.3) is equivalent to

(7.6) $\displaystyle\left\\{\begin{array}[]{l}w_{1}\cdot s+w_{2}\cdot
t=\frac{a+b-c}{2}\\\ s^{2}+t^{2}=b\end{array}\right.$

Now $w_{1}$ and $w_{2}$ cannot be simultaneously zero since $a\neq 0$. If
$w_{1}\neq 0$, from the first equation in (7.6) we get that

(7.7) $s=\frac{1}{w_{1}}\left\\{\frac{a+b-c}{2}-w_{2}\cdot t\right\\}\;,$

which substituted into the second equation in (7.6) gives

(7.8)
$\left\\{\left(\frac{w_{2}}{w_{1}}\right)^{2}+1\right\\}t^{2}-\left\\{\frac{a+b-c}{w_{1}}\;\frac{w_{2}}{w_{1}}\right\\}t+\left(\frac{a+b-c}{2w_{1}}\right)^{2}-b=0\;.$

(If $w_{1}=0$ so that $w_{2}\neq 0$, the resulting equation is the same as
(7.8) but interchanging the roles of $w_{1}$ and $w_{2}$ among themselves and
the roles of $s$ and $t$ among themselves.)

However, notice now that the condition $w_{2}=\pm i\;w_{1}$ is incompatible
with the hypothesis that $w_{1}^{2}+w_{2}^{2}=a\neq 0$. Consequently,
$\left(\frac{w_{2}}{w_{1}}\right)^{2}\not=-1$, and hence the equation (7.8)
has at most 2 solutions. We still have to prove that the equation (7.8) has
indeed a solution under our hypotheses. The discriminant of equation (7.8) is

(7.9)
$\displaystyle\Delta=\left\\{\frac{a+b-c}{w_{1}}\;\frac{w_{2}}{w_{1}}\right\\}^{2}-4\left\\{\left(\frac{w_{2}}{w_{1}}\right)^{2}+1\right\\}\left[\left(\frac{a+b-c}{2w_{1}}\right)^{2}-b\right]$
$\displaystyle=$
$\displaystyle\frac{4b\left[w_{1}^{2}+w_{2}^{2}\right]-\left(a+b-c\right)^{2}}{w_{1}^{2}}=$
$\displaystyle=$
$\displaystyle\frac{4ab-\left(a+b-c\right)^{2}}{w_{1}^{2}}\;.$

Hence equation (7.8) has a solution precisely when there exists a
$k\in\mathbb{F}_{q}$ such that

(7.10) $4ab-\left(a+b-c\right)^{2}=k^{2}\;,$

which happens precisely when $c$ is of the form

(7.11) $c=a+b\pm\sqrt{4ab-k^{2}}\;,$

i.e. whenever there exists a $\tau\in\mathbb{F}_{q}$ such that

(7.12) $k^{2}+\tau^{2}=4ab\;.$

We now repeat, for the convenience of the reader, the well-known known
argument that every element of $\mathbb{F}_{q}$ is a sum of $2$ squares.
Namely, by (5.2), and recalling that $\eta^{2}(t)=1$ and that
$\sum_{t\in\mathbb{F}_{q}}\chi(-4abt)=0$ if $t\neq 0$, and that $Q=\pm 1$ or
$\pm i$ depending on $q$,

(7.13) $\displaystyle|\\{(k,\tau):k^{2}+\tau^{2}=4ab\\}|$ $\displaystyle=$
$\displaystyle\frac{1}{q}\sum_{t\in\mathbb{F}_{q}}\;\sum_{k,\tau\in\mathbb{F}_{q}}\chi(t(k^{2}+\tau^{2}-4ab))=$
$\displaystyle=$ $\displaystyle q+\frac{1}{q}\sum_{t\neq
0}\;\sum_{k,\tau\in\mathbb{F}_{q}}\chi(t(k^{2}+\tau^{2}-4ab))=$
$\displaystyle=$ $\displaystyle q+\frac{1}{q}\sum_{t\neq
0}\chi(-4abt)\;Q^{2}\;q\,\eta^{2}(t)=q-Q^{2}\;.$

Hence equation (7.8) has a solution for at least $\frac{q\pm 1}{2}$ different
values of $c$, since by (7.11) and (7.12) each value of $c$ for which equation
(7.8) has a solution corresponds precisely to one value of $\tau$, and each
value of $\tau$ is accounted for at most twice in (7.13) since for each such
value of $\tau$, there are at most $2$ values of $k$ satisfying (7.12).

Since it is conceivable (depending on the value of $q$) that $c=0$ yields a
solution to (7.3), accounting for that possibility, we can assert that (7.3)
has a solution for at least $\frac{q-3}{2}$ different values of $c\neq 0$.

## References

  * [1] J. Bourgain, A Szemer di type theorem for sets of positive density, Israel J. Math. 54 (1986), no. 3, 307-331.
  * [2] V. Bergelson, Ergodic Ramsey theory an update, Ergodic Theory of Zd -Actions (Warwick, 1993 1994) (M. Pollicott and K. Schmidt, eds.), London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, (1996).
  * [3] H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, M. B. Porter Lectures, Princeton Univ. Press, Princeton, NJ, (1981).
  * [4] H. Furstenberg, Y. Katznelson, and B. Weiss, Ergodic theory and configurations in sets of positive density Mathematics of Ramsey theory, 184-198, Algorithms Combin., 5, Springer, Berlin, (1990).
  * [5] D. Hart and A. Iosevich, Ubiquity of simplices in subsets of vector spaces over finite fields, Analysis Mathematika, 34, (2007).
  * [6] A. Iosevich and M. Rudnev, Erdős distance problem in vector spaces over finite fields. Trans. Amer. Math. Soc. (2007).
  * [7] B. Kra, Ergodic methods in additive combinatorics, Centre de Recherches Mathematiques Proceedings and Lecture Notes (2007).
  * [8] R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, (1997).
  * [9] A. Magyar, On distance sets of large sets of integers points, Israel Math J. (to appear) (2006).
  * [10] A. Magyar, $k$-point configurations in sets of positive density of ${\mathbb{Z}}^{n}$, Duke Math J. (to appear), (2007).
  * [11] T. Tao and V. Vu. Additive Combinatorics. Cambridge University Press, 2006.
  * [12] A. Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948) 204-207.
  * [13] T. Ziegler, An application of ergodic theory to a problem in geometric Ramsey theory, Israel Journal of Math. 114 (1999) 271-288.