# Efficient Parallel Connected Components Labeling with a Coarse-to-fine
Strategy

Jun Chen<EMAIL_ADDRESS>Keisuke Nonaka<EMAIL_ADDRESS>Hiroshi Sankoh<EMAIL_ADDRESS>Ryosuke Watanabe  ru-watanabe@kddi-
research.jp Houari Sabirin<EMAIL_ADDRESS>Sei Naito  sei@kddi-
research.jp Ultra-realistic Communication Group, KDDI Research, Inc.
Ohara 2-1-15, Fujimino, Saitama, Japan

###### Abstract

This paper proposes a new parallel approach to solve connected components on a
2D binary image implemented with CUDA. We employ the following strategies to
accelerate neighborhood exploration after dividing an input image into
independent blocks. In the local labeling stage, a coarse-labeling algorithm,
including row-column connection and label-equivalence list unification, is
applied first to sort out the mess of an initialized local label map; a
refinement algorithm is then introduced to merge separated sub-regions from a
single component. In the block merge stage, we scan the pixels located on the
boundary of each block instead of solving the connectivity of all the pixels.
With the proposed method, the length of label-equivalence lists is compressed,
and the number of memory accesses is reduced. Thus, the efficiency of
connected components labeling is improved. Experimental results show that our
method outperforms the other approaches between $29\%$ and $80\%$ on average.

###### keywords:

Connected components labeling, Parallel computation, Real-time image
processing, Pattern recognition

††journal: Journal of LaTeX Templates

##  1 Introduction

Connected components labeling (CCL) is a task to give a unique ID to each
connected region in a 2D/3D image. It means that the input data are clustered
as separate groups where the elements from a single group share the same ID.
As a basic data clustering method, CCL is used as a tool for object detection
and classification in the field of computer vision and image processing [1]
[2] [3]. W. Song, et al. [4] presented a motion based skin region of interest
detection method using a real-time CCL algorithm to reduce its execution time.
A fast 3D shape measurement technique using blink-dot projection patterns that
utilizes a CCL algorithm to compute the size and location of each dot on the
captured images has been reported [5] [6]. P. Guler, et al. proposed a real-
time multi-camera video analytics system [7] employing CCL to perform noise
reduction. Acting as a fundamental operation in all the applications,
especially in real-time applications, speeding up CCL is an important task [8]
[9].

Numerous studies have proposed ways to accelerate CCL. The proposed solutions
on CPU can be summarized into two classes: label propagation algorithms and
label-equivalence-based algorithms [8]. The approaches [10] [11] based on
label propagation often find an unlabeled pixel using raster scan and give it
an unused label; then, the label is propagated to all the pixels in the same
region in an irregular way, such as tracing the object’s contour [12]. These
approaches are not suitable for parallel implementation and hardware
implementation because of the existence of the irregular scan. The methods
[13] [14] [15] [16] [17] on the basis of label-equivalence solve the CCL issue
with multiple raster scans. Provisional labels, often associated with the
pixel position in the image or in a specific row, are assigned to all the
pixels in the first scan; the label-equivalence lists are constructed based on
the pixel connectivity and resolved with root-find algorithms in the other
steps. Since the pixels are processed in a regular way, it is feasible to
extend these methods into parallel implementation and hardware implementation
[18] [19]. Until recently, the use of GPUs with interfaces such as CUDA [20]
or OpenCL [21] finds countless applications in both industry and academia
areas. The parallel extension and improvement of serial CCL algorithms are
significant advances to enhance the real-time property. For the algorithms
developed on GPUs, data parallelization across multiple processors [22] [23]
plays an important role in computing with multiple processing elements in
parallel. Generally, the different data parallelization approaches lead to
different computation algorithms. According to the various ways of managing
data, the reported solutions for CCL on GPUs can be classified into three
types: pixel-based algorithms, block-based algorithms, and line-based
algorithms. The first type extends the label-equivalence-like algorithms into
parallel ones directly by considering each individual pixel or the pixels in a
small group as a computation unit. The other two types first divide images
into independent sections, blocks or lines, then perform local labeling and
section merge to solve the CCL.

In this study, we propose a block-based solution to explore the benefit of
two-dimensional pixel distribution to reduce the number of iterative
operations. Its main contributions are: (1), a row-column connection and a
label-equivalence list unification algorithm are performed using shared memory
to sort out the mess of an initialized local label map; (2), connectivity
analysis is conducted for the pixels on the block boundary instead of all the
pixels to reduce the number of memory accesses. By using our method, the
length of the label-equivalence list is compressed and the number of CUDA
threads for computation decreases. In the following sections, we will outline
our method, prove the positive effects of coarse-to-fine strategy, and
demonstrate its performance.

##  2 Previous works

###  2.1 Pixel-based CCL algorithm

Label-equivalence [25] is an algorithm that records the lowest label that each
label is equivalent to and resolves the equivalence with a small number of
iterations. Jung et al. [24] solved the CCL issue by interactively executing
six phases, including initialization, scan, analysis, link, label, and rescan.
In the scan phase and link phase, they introduce specific masks to construct
label-equivalence lists. In the analysis phase and label phase, they find the
roots by tracing each list. Kalentov et al. [26] improved the label-
equivalence technique in terms of memory consumption and required processing
steps, which removed the reference array and atomic operations in the scan
phase. Soh et al. [27] proposed a direction-based searching method that
obtains the minimum label by tracing the branches derived from a focused pixel
in eight directions. Block-equivalence [28] is another extension of label-
equivalence solution. It uses a superpixel block instead of the individual
pixel taking into consideration what the pixels located in a $2\times 2$ block
share with the same label with eight-connectivity. It is effective because the
number of candidate pixels for connectivity detection is reduced. The main
drawback of these pixel-based algorithms is that a single label-equivalence
list cannot be constructed for one connected component in one scan.
Consequently, the kernels of this algorithm are spawned several times to
guarantee that no disjoint equivalence lists exist for a single region. Even
though some of them reduce the number of iterations at some level, they still
need to scan the input image multiple times. Furthermore, the iterations might
vary dramatically in different images.

###  2.2 Block-based CCL algorithm

The parallel version of the union-find algorithm [29] is presented by Oliveria
et al. [30]. They executed two merges successively, local merge and global
merge, to overcome the drawback that it may need to follow a long path to
reach the root of two connected pixels. Although this algorithm outperforms
most of the pixel-based CCL algorithms because all the kernels are spawned
once, searching for the root of a specific pixel is computationally heavy.
Stava et al. [31] designed a solution in the similar manner. In the local
merge stage, they improved the label-equivalence algorithm by implementing all
iterations inside the kernel, such that no synchronization between host and
device is required. In the global merge stage, they use the connectivity
between all border elements of two neighboring blocks to merge their
equivalence lists. It is necessary to perform the operations of global merge
several times to guarantee that all equivalence lists are merged. Kumar et al.
[32] implemented the CCL algorithm using a divide and conquer technique [33]
on CUDA that solves the local connection using the Floyd-Warshall algorithm
[34] and merges blocks by considering three different cases. Here, the various
processing approaches for the three cases leads to thread divergence thus
limiting the performance.

###  2.3 Line-based CCL algorithm

Chen et al. [35] proposed a two-scan approach, extended from a stripe-based
CCL method [36], to process stripe extraction and stripe union, respectively.
The first scan can run in parallel by using shared memory, while the second
scan is a sequential operation. ACCL [37] is another parallelization algorithm
that decomposes the image into rows. By defining a span as a group of pixels
that are located contiguously in a row with the same intensity, it spawns two
kernels, find spans and merge spans, to label an input image. The involvement
of dynamic parallelism means that good performance can be achieved with this
method. However, it is not suitable to process large images because there is a
limitation on the number of threads in one block [38]. Yonehara et al.
proposed a line-based solution [39] that improves the local labeling phase of
the conventional union-find algorithm [30] by conducting a row unification
using shared memory. The absence of merge algorithm makes it label an
individual section efficiently in the first scan, while the other scans cannot
make any further improvements.

\begin{overpic}[width=433.62pt]{srcImg.eps} \end{overpic} (a) Input data
\begin{overpic}[width=433.62pt]{initializedLocalLabelMap.eps} \end{overpic}
(b) Initialized local label map

Figure 1: Input data and initialized local label map.

\begin{overpic}[width=433.62pt]{listAlongRow.eps} \end{overpic} (a) Label-
equivalence list after row scan
\begin{overpic}[width=433.62pt]{listAlongRowAndColumn.eps} \end{overpic} (b)
Label-equivalence list after column scan

Figure 2: Coarse label-equivalence construction.

##  3 Algorithm and implementation

We assume that a pixel in an image has three attributes comprising position,
intensity, and label. Position means its raster scan order in row-major order,
which can be expressed by $P(x,y)=x+y*W$. Here $(x,y)$ is its 2D coordinate in
the image. $(H,W)$ is the resolution of the image plane. Intensity is the
color intensity of the pixel, which can be expressed by $I(x,y)$. In our
implementation, $I(x,y)=1$ when a pixel belongs to foreground, and $I(x,y)=0$
when it is background. Label $L(x,y)$ is what we should find to depict each
connected region.

There are three steps in our method to solve the segmentation of an image. In
the first step, we divide the input image into blocks, and perform local
labeling using a coarse-to-fine strategy. In the second step, we extract the
pixels located on the boundary of each block to be a sub-image, and construct
global label-equivalence lists. In the last step, the final label map is
obtained by solving equivalence using a root-find algorithm.

Kernel 1 Local labeling with coarse-to-fine strategy

$label_{sm}[],subimg_{sm}[]$ are on shared memory

$labelmap[]$ is on global memory

declare int $x,y,tid,temp,l,l_{x},l_{y},g_{l},label_{sm}[],dBuff_{sm}[]$

$x,y\leftarrow$ 2D global thread id

$tid\leftarrow$ 1D thread id within block

$label_{sm}[tid]\leftarrow tid$

$subimg_{sm}[tid]\leftarrow image[x,y]$

call syncthreads()

// row scan

$\textbf{if}\ \ subimg_{sm}[tid]==subimg_{sm}[tid-1]$

$label_{sm}[tid]=label_{sm}[tid-1]$

end if

call syncthreads()

// column scan

$\textbf{if}\ \ subimg_{sm}[tid]==subimg_{sm}[tid-blockdim.x]$

$label_{sm}[tid]\leftarrow label_{sm}[tid--blockdim.x]$

end if

call syncthreads()

$label_{sm}[tid]\leftarrow findroot(label_{sm}[],tid)$

// refinement (row scan)

$\textbf{if}\ \ subimg_{sm}[tid]==subimg_{sm}[tid-1]$

$merge(label_{sm}[],tid,tid-1)$

end if

call syncthreads()

$l\leftarrow findroot(label_{sm}[],tid)$

// convert local index to global index

$(l_{x},l_{y})\leftarrow(l\ /\ blockdim.x,l\ \%\ blockdim.x)$

$g_{l}\leftarrow(blockIdx.x*blockDim.x+l_{x})+(blockIdx.y*blockDim.y+l_{y})*imgwidth$

$labelmap[x,y]\leftarrow g_{l}$

###  3.1 Local labeling with coarse-to-fine strategy

The first step, local labeling with a coarse-to-fine strategy, consists of
four phases: initialization, coarse labeling, refinement, and ID conversion.

Figure 3: Label-equivalence list after row-column connection.

\begin{overpic}[width=433.62pt]{aConnectedRegion.eps} \end{overpic} (a) A
single region \begin{overpic}[width=433.62pt]{refinedLableList.eps}
\end{overpic} (b) Refined list
\begin{overpic}[width=433.62pt]{refinedLocalLabelMap.eps} \end{overpic} (c)
Refined local label map

Figure 4: Refine local label map.

####  3.1.1 Initialization

In our algorithm, each pixel should be assigned with a provisional label first
so that a connection-list can be constructed and solved. We use
$L(x,y)=P(x,y)$ for indicating the provisional label of $(x,y)$. In this way,
the root of an equivalence list is the element with the label equal to the
address of the element itself. Fig. 1 gives an illustration of this step where
(a) shows that a $16\times 16$ binary image is split into four sub-images with
a resolution of $(H,W)=(8,8)$; (b) presents an example of an initialized local
label map. The grey elements on the image, $I(x,y)=1$, express foreground
pixels. In our CUDA implementation, we dispatch the sub-images to various GPU
threads blocks where the threads can cooperate with each other using shared
memory and can be synchronized [40]. The provisional labels and pixel
positions are associated with the thread ID within a threads block as is shown
in the steps $1-6$ of Algorithm 1. Threads synchronization is necessary
because the buffer could not be initialized by multiple threads at the same
time.

####  3.1.2 Coarse labeling

In an initialized local label map, the provisional label of the left pixel and
that of the upper pixel are always smaller than the label of a target pixel,
while the upper one is always the minimum. Based on this fact, we scan row and
column successively to make a coarse label-equivalence list. In the case of a
row scan, we associate two consecutive pixels by updating the label of the
right pixel with the left label $L(x,y)=L(x-1,y)$ if both of them are
foreground $I(x,y)=I(x-1,y)=1$. Label-equivalence trees are constructed for
continuous foreground pixels of each row with the method presented in Fig. 2
(a). The scanning approach along the vertical direction is performed in the
same manner where the association between left and right is updated by the
association between up and down if all of the three pixels are foreground.
Fig. 2 (b) presents a demonstration of coarse label-equivalence lists after
column scan. The same result can be achieved by comparing the labels of the
above-mentioned three pixels directly at the same time. However, we find the
proposed method is faster because it does not involve branch divergence and
the boundary-related operations. Unlike the methods that records the entire
equivalence, this method records the lowest neighbor label that the label is
equivalent to. Its memory access complexity is reduced due to the utilization
of shared memory, while the list can be unified by a low number of iterations.
Fig. 3 illustrates the segments of a coarse local label map and the root of
each list. It was found that this step can not provide a complete segmentation
but splits a connected region into several groups. The pseudo code for this
step is listed in steps $8-17$ of Algorithm 1.

Figure 5: Label map after local labeling.

\begin{overpic}[width=433.62pt]{aGlobalConnectedRegion.eps} \end{overpic} (a)
A connected region \begin{overpic}[width=433.62pt]{aGlobalEquivalenceList.eps}
\end{overpic} (b) Global label-equivalence list

Figure 6: Global label-equivalence construction.

####  3.1.3 Refinement

This phase is a task to merge the segments that belong to a single region. As
shown in Fig. 4 (a), three isolated sub-regions exist in the one connected
region. The pixels in the ellipse are the branch dividing points that lead
pixels to different label-equivalence lists. Corresponding to the
initialization approach of the provisional label, the branch dividing points
are always in the horizontal direction. So the sub-regions can be merged
together with another row scan. If two consecutive foreground pixels have
different labels, we compare their roots and make the larger one point to the
smaller one. It should be noticed that the atomic operation is necessary here
because the same equivalence list may be updated by multiple threads at the
same time. With this method, a new label-equivalence list is available as
illustrated in the example in Fig. 4 (b). Finally, the region is unified using
a root-find algorithm as shown in Fig. 4 (c). The pseudo code for refinement
is listed in steps $19-23$ of Algorithm 1.

####  3.1.4 ID conversion

The final step of local labeling is an ID conversion that converts the local
index to global index and transfers the result to global memory. The global
index identifies the $1-$D address of a pixel in the entire image. Steps
$25-26$ of Algorithm 1 give its pseudo code.

Kernel 2 Boundary analysis

both block dimension and grid dimension are 2D

$labelmap[]$ is on global memory

declare int $id,h_{x},h_{y},v_{x},v_{y},pInLine,p_{h},p_{v}$

declare bool $b_{h},b_{v}$

$id\leftarrow$ 1D global thread id

// convert 1D global index id to 2D image index

$h_{x}\leftarrow id\ \%\ imgwidth$

$h_{y}\leftarrow id\ /\ (imgwidth*blockdim.y)$

$pInLine\leftarrow imgwidth\ /\ blockDim.x$

$v_{x}\leftarrow id\ \%\ pInLine*blockDim.x$

$v_{y}\leftarrow id\ /\ pInLine$

// boundary analysis along x-axis

$\textbf{if}\ \ image[h_{x},h_{y}]==image[h_{x}-1,h_{y}]$

$merge(labelmap,\ p_{h},\ p_{h}-1)$;

end if

// boundary analysis along y-axis

$\textbf{if}\ \ image[v_{x},v_{y}]==image[v_{x},v_{y}-imgwidth]$

$merge(labelmap,\ p_{v},\ p_{v}-imgwidth)$;

end if

###  3.2 Block merge with boundary analysis

In the block merge phase, we perform connective detection for the pixels on
the block boundary to merge the equivalence lists of the same connected
component from different blocks. Assuming the resolution of an input image is
$N\times M$ and the block configuration of Kernel 1 is
$\left\\{b_{x},b_{y},1\right\\}$, the number of border pixels along the
$x-$axis $P_{x}$ and the number of border pixels along the $y-$axis $P_{y}$
can be determined as follows:

$\displaystyle P_{x}=\left\lfloor N\ /\ b_{x}\right\rfloor*M,$ (1)
$\displaystyle P_{y}=\left\lfloor M\ /\ b_{y}\right\rfloor*N,$ (2)

Here, $\left\lfloor x\right\rfloor$ means the largest integer smaller or equal
to $x$. It is found that the candidate pixels for detection get shrunk by
$b_{x}$ times for boundary analysis along the $x-$axis and $b_{y}$ times for
boundary analysis along the $y-$axis. Similar to coarse labeling, we scan the
vertical boundary and the horizontal boundary successively. If two consecutive
foreground pixels, vertical or horizontal, are foreground, we link them with
the larger label pointing to the smaller one. Fig. 5 shows a global label map
after local labeling. The pixels in rectangles are border pixels. The arrows
show the association between two pixels. Fig. 6 (a) presents a connected
region that is composed of three sub-regions from three blocks. Fig. 6 (b)
gives a global label-equivalence list by connecting the root of each sub-
region. In our implementation, $\max\\{P_{x},P_{y}\\}$ threads should be
invoked to integrate the boundary analysis along the $x-$ and $y-$axes into
one kernel. Steps $1-9$ of Algorithm 2 illustrates how to compute the global
index of a border pixel, while steps $10-16$ indicate the merge operation.

###  3.3 Update global label map

When all blocks are merged, the independent local label maps are associated as
an entirety. The final global label map represents the complete segmentation
of an input image where every equivalence list corresponds to an unbroken
connected component. The roots of global label-equivalence lists can be
obtained by using the root-find algorithm that is the same as what was used in
Algorithm 1.

##  4 Comparative evaluation

In order to demonstrate the performance of our method, we compare it with the
following approaches.

  * -

C2FL as our proposed method.

  * -

RC2FL as a revision of our method with coarse labeling only along row.

  * -

CC2FL as a revision of our method with coarse labeling only along column.

  * -

NC2FL as a revision of our method without coarse-to-fine strategy.

  * -

LE [26] as a conventional pixel-based label equivalence solution.

  * -

BE [28] as a more recent representative of the pixel-based solution using
block equivalence technique.

  * -

SMCCL [31] as a more recent block-based method using shared memory.

  * -

UF [30] as a more recent block-based method with a union-find method.

  * -

LUF [39] as a more recent and fast representative of the line-based method.

  * -

CPUCCL [41] as a more recent implementation on CPU.

There are two kinds of comparative experiments. The first is an effectiveness
evaluation of coarse labeling which compares C2FL with RC2FL, CC2FL and NC2FL.
It should be noted that the local labeling works correctly if refinements
along both row and column are applied even without coarse labeling. When each
individual pixel is considered as a sub-region of a connected region, the
third phase, refinement, is able to generate an entire local label-equivalence
list. The significance of coarse labeling is that it allows to local merge to
be performed efficiently. The second is a comparison with existing CUDA-based
algorithms and a latest CPU-based sequential algorithm. The execution times of
C2FL, RC2FL, CC2FL, NC2FL, LE, BE, SMCCL, UF, LUF, and CPUCCL for datasets
[42] are listed.

All the experiments were performed on a PC Intel(R) Core(TM) i7-6700K CPU,
4.00 GHz $\And$ 4.00 GHz, 32.0 GB RAM, NVIDIA Geforce GTX 1070 with Windows 7
Professional Service Pack 1. All the algorithms were implemented in C++
language by use of OpenCV 2.4.13 and CUDA 8.0.

(a) The number of iteration versus the image size

(b) The number of atomic operation versus the image size

Figure 7: The number of iteration and atomic operation versus image size

(a) The number of iteration versus noise density

(b) The number of atomic operation versus noise density

Figure 8: The number of iteration and atomic operation versus noise density

\begin{overpic}[width=433.62pt]{lenaIteration-c2f.eps} \end{overpic} (a) C2FL
\begin{overpic}[width=433.62pt]{lenaIteration-c2fr.eps} \end{overpic} (b)
RC2FL \begin{overpic}[width=433.62pt]{lenaIteration-c2fc.eps} \end{overpic}
(c) CC2FL \begin{overpic}[width=433.62pt]{lenaIteration-nc2f.eps}
\end{overpic} (d) NC2FL

Figure 9: Color map of the number of iterations.

\begin{overpic}[width=433.62pt]{lenaAtomicNumbers-c2f.eps} \end{overpic} (a)
C2FL \begin{overpic}[width=433.62pt]{lenaAtomicNumbers-c2fr.eps} \end{overpic}
(b) RC2FL \begin{overpic}[width=433.62pt]{lenaAtomicNumbers-c2fc.eps}
\end{overpic} (c) CC2FL \begin{overpic}[width=433.62pt]{lenaAtomicNumbers-
nc2f.eps} \end{overpic} (d) NC2FL

Figure 10: Color map of the number of atomic operations.

###  4.1 Effectiveness of coarse labeling

There are two significant factors, the number of iterations and the number of
atomic operations, in one threads block affect the efficiency of local
labeling seriously. Iteration refers to the process of iterating an operation
such as tracing a label-equivalence list to find its root. Most of the
algorithms that are expressed in C++ language take only a few of lines.
However, there may be thousands of instructions that are executed on hardware.
Generally, the number of iterations reflects the number of instructions and
the program′s execution time. Atomic operations are a kind of processing
performed without interference from any other threads. They are often
essential for multithreaded applications to prevent race conditions,
especially when different threads attempt to modify and write the same memory
address. If two or more threads perform an atomic operation at the same memory
address at the same time, those operations will be serialized. This means that
the more atomic operations the slower the execution.

In our evaluation, the threads block of CUDA was configured as
$\left\\{32,32,1\right\\}$. We use a set of square binary images with various
resolution and random noise to show the difference in the number of iterations
as well as the number of atomic operations among C2FL, RC2FL, CC2FL, and
NC2FL. There are nine different foreground densities, from $0.1$ to $0.9$, and
eight resolutions, from a low resolution of $32\times 32$ pixels to a maximum
resolution of $4096\times 4096$ pixels. The experiments provide us an
opportunity to evaluate the performance of coarse labeling both in terms of
scalability on the number of pixels and in terms of scalability on the density
of connected regions.

Fig. 7 shows how the the number of iterations and atomic operations of
different algorithms change with images of increasing size. Here, the label
density is $0.5$, which remains in all the images. The reported results were
the average of all the launched threads blocks of 100 runs of each algorithm.
As presented in (a) of Fig. 7, it can be seen that the iteration for coarse-
labeling, regardless of whether it is full coarse-labeling or partial coarse-
labeling, are heavier than those of NC2FL when the number of pixels is less
than $65535$ ($256\times 256$ image), while these iterations equal to or less
than those of NC2FL when the pixels of an image exceed $65535$. The phenomenon
is reasonable because a local label-equivalence list in a low-resolution image
is short. Under the circumstances, the compression by coarse labeling can not
reduce but increase the number of iterations. The linear independence of the
number of atomic operations with respect to the image size can be observed in
(b) of Fig. 7. The proposed algorithm always takes the fewest atomic
operations to segment an input image.

Fig. 8 highlights the behavior of the algorithms varying the foreground label
densities of a $2048\times 2048$ image. It can be proved that both of the
factors have a significant linear correlation with the label densities, and
our method has the best performance among all the densities. This result is
logical because coarse labeling reduces complexity and facilitates the
solution.

The third experiment demonstrates the efficiency of coarse labeling using a
binary Lena image with a size of $2048\times 2048$. Fig. 9 shows the color map
of the maximum iterations of each threads block of each algorithm where the
darker color expresses more numerous iterations. It indicates that our
proposed method solves the CCL issue with the fewest iterations. Fig. 10
expresses the number of atomic operations in the same manner. With regard of
RC2FL, CC2FL, and NC2FL, we find that most of the race conditions occur on the
blocks holding pixels from a flat foreground region. Nevertheless, there is no
risk of a race condition for the blocks in C2FL. Meanwhile, our approach
evidences that the minimum atomic operations are required for a block with an
edge area.

Table 1: Execution time in millisecond for different images Images |  | CPUCCL | LE | BE | CCLSM | UF | LUF | NC2FL | RC2FL | CC2FL | C2FL
---|---|---|---|---|---|---|---|---|---|---|---
 lena  $(\\!512\\!\times\\!512\\!)$  | min | 0.371 | 0.634 | 0.493 | 0.139 | 0.491 | 0.105 | 0.106 | 0.066 | 0.069 | 0.057
max | 0.461 | 1.170 | 0.943 | 0.152 | 0.506 | 0.119 | 0.113 | 0.070 | 0.081 | 0.063
mean | 0.382 | 0.730 | 0.594 | 0.144 | 0.497 | 0.110 | 0.109 | 0.068 | 0.073 | 0.060
| $\delta$ | 0.017 | 0.091 | 0.108 | 0.001 | 0.001 | 0.002 | 0.001 | 0.001 | 0.002 | 0.0008
 brain  $(\\!720\\!\times\\!720\\!)$  | min | 1.61 | 0.66 | 0.66 | 0.96 | 0.49 | 0.38 | 0.26 | 0.17 | 0.17 | 0.13
max | 2.11 | 0.66 | 0.66 | 1.00 | 0.56 | 0.49 | 0.26 | 0.17 | 0.17 | 0.13
mean | 1.77 | 0.66 | 0.66 | 0.97 | 0.51 | 0.40 | 0.26 | 0.17 | 0.17 | 0.13
| $\delta$ | 0.382 | 0.730 | 0.594 | 0.144 | 0.497 | 0.110 | 0.109 | 0.068 | 0.073 | 0.060
 fingerprint  $(\\!1024\\!\times\\!1024\\!)$  | min | 1.565 | 1.676 | 0.730 | 0.379 | 0.570 | 0.297 | 0.492 | 0.249 | 0.285 | 0.210
max | 1.640 | 2.310 | 1.100 | 0.465 | 0.703 | 0.370 | 0.612 | 0.316 | 0.362 | 0.259
mean | 1.584 | 1.793 | 0.797 | 0.393 | 0.583 | 0.307 | 0.504 | 0.256 | 0.293 | 0.217
| $\delta$ | 0.015 | 0.151 | 0.086 | 0.018 | 0.030 | 0.0150 | 0.026 | 0.013 | 0.015 | 0.010
 cartoon  $(\\!1024\\!\times\\!1024\\!)$  | min | 2.011 | 1.746 | 0.901 | 0.373 | 0.511 | 0.308 | 0.434 | 0.237 | 0.263 | 0.200
max | 2.203 | 2.339 | 1.324 | 0.499 | 0.629 | 0.380 | 0.542 | 0.294 | 0.327 | 0.249
mean | 2.034 | 1.949 | 0.970 | 0.397 | 0.521 | 0.316 | 0.443 | 0.243 | 0.270 | 0.205
| $\delta$ | 0.025 | 0.168 | 0.104 | 0.023 | 0.027 | 0.016 | 0.022 | 0.011 | 0.012 | 0.009
 texture  $(\\!2048\\!\times\\!2048\\!)$  | min | 7.016 | 3.608 | 1.685 | 0.656 | 0.596 | 0.676 | 0.488 | 0.447 | 0.453 | 0.438
max | 7.669 | 4.764 | 2.538 | 0.852 | 0.690 | 0.794 | 0.560 | 0.510 | 0.526 | 0.499
mean | 7.096 | 3.949 | 2.025 | 0.668 | 0.604 | 0.684 | 0.494 | 0.453 | 0.459 | 0.443
| $\delta$ | 0.100 | 0.219 | 0.182 | 0.029 | 0.015 | 0.019 | 0.012 | 0.011 | 0.011 | 0.009
 artifact  $(\\!4096\\!\times\\!4096\\!)$  | min | 125.198 | 21.620 | 6.439 | 5.186 | 5.089 | 4.099 | 3.632 | 3.280 | 3.268 | 3.097
max | 127.943 | 24.469 | 8.259 | 5.933 | 6.061 | 4.842 | 4.365 | 3.927 | 3.908 | 3.700
mean | 126.633 | 22.082 | 7.691 | 5.232 | 5.135 | 4.132 | 3.668 | 3.302 | 3.295 | 3.120
| $\delta$ | 0.887 | 0.412 | 0.390 | 0.121 | 0.163 | 0.125 | 0.079 | 0.065 | 0.062 | 0.059

(a) Execution time versus image pixels

(b) Execution time versus label density

Figure 11: Execution time versus label density and image pixels

\begin{overpic}[width=433.62pt]{naturalLena.eps} \end{overpic} (a) Lena
\begin{overpic}[width=433.62pt]{naturalBrain.eps} \end{overpic} (b) Brain
\begin{overpic}[width=433.62pt]{naturalFinger.eps} \end{overpic} (c)
Fingerprint \begin{overpic}[width=433.62pt]{naturalManga.eps} \end{overpic}
(d) Cartoon \begin{overpic}[width=433.62pt]{naturalTexture.eps} \end{overpic}
(e) Texture

\begin{overpic}[width=433.62pt]{naturalArtifacts.eps} \end{overpic} (f)
Artifact

Figure 12: Six representative images.

###  4.2 Comparisons with existing algorithms

For the evaluation of execution time, the minimum, maximum, mean, and standard
deviation, over 100 runs are collected to remove any fluctuations caused by
the other tasks executed by the operation system. All the algorithms were
implemented based on four-neighbor connection, except BE and CPUCCL. BE
assumes that the pixels in a $2\times 2$ block share the same label such that
it is infeasible to perform with four-connectivity. CPUCCL performs CCL using
a pixel prediction strategy to avoid repeatedly scanning the same pixels
multiple times. The code for its implementation is borrowed from [42].

We first evaluate the algorithms using the same synthetic images. Fig. 11 (a)
shows how the algorithms work with images of increasing size. The execution
time of all algorithms increases linearly with the expansion of input images.
Our method is proved to be scalable and able to outperform all the other
methods. Another experimental result, shown in Fig. 11 (b), highlights the
efficiency of the algorithms with images of various label densities. It
indicates that the computation is efficient regardless of the label density is
low or high while the worst case appears around the middle densities. Lower or
higher densities present simple connections and consequently less computation,
while the middle densities present complex connections. It can be inferred
that our approach has the best performance among all the densities. It is able
to label a $2048\times 2048$ image with arbitrary density within $1.2~{}$ms

We also selected the six images shown in Fig. 12, comprising a natural image,
medical image, texture, and artifact image, to prove the performance of our
proposed method. The resolution and experimental results of the six images are
listed in Tab. 1. The comparison among NC2FL, RC2FL, CC2FL, and C2FL states
the effectiveness of the coarse-to-fine strategy. NC2FL always takes longer to
complete one segmentation than the other three methods. Meanwhile, C2FL is
always more efficient than RC2FL and CC2FL. The comparison among all the
algorithms is evidence that our approach outperforms all the others for all
the images. It should also be noted that the standard deviation of the
execution time of our approach is quite small for all the images, which
demonstrates stable computation.

##  5 Conclusion

In this paper, we proposed a novel parallel approach with a coarse-to-fine
strategy to accelerate the solution of CCL issues. Our method first employs
coarse labeling to reduce the complexity of a local block, and then applies a
refinement to solve the local labeling. In the block merge stage, we launch a
low number of threads to analyze the connectivities along block boundary. As a
result, the proposed method is sufficiently capable of performing CCL with
CUDA on GPU. We evaluated the effectiveness of the coarse-to-fine strategy and
compared it with existing GPU and CPU implementations. Experimental results
show that our method outperforms all existing parallel approaches between
$29\%$ and $80\%$ on average. Meanwhile, it proved that our method has good
scalability in term of various image sizes and stability in terms of various
label densities. The reference code for the method is available at
https://github.com/sevenlovechen/parallel_CCL.

## References

  * [1] G. A. Baxes, Digital image processing: principles and applications, Wiley New York, 1994.
  * [2] K. Suzuki, S. G. Armato, F. Li, S. Sone, et al., Massive training artificial neural network (mtann) for reduction of false positives in computerized detection of lung nodules in low-dose computed tomography, Medical physics 30 (7) (2003) 1602–1617.
  * [3] K. Suzuki, H. Yoshida, J. Näppi, S. G. Armato, A. H. Dachman, Mixture of expert 3d massive-training anns for reduction of multiple types of false positives in cad for detection of polyps in ct colonography, Medical physics 35 (2) (2008) 694–703.
  * [4] W. Song, D. Wu, Y. Xi, Y. W. Park, K. Cho, Motion-based skin region of interest detection with a real-time connected component labeling algorithm, Multimedia Tools and Applications 76 (9) (2017) 11199–11214.
  * [5] J. Chen, Q. Gu, H. Gao, T. Aoyama, T. Takaki, I. Ishii, Fast 3-d shape measurement using blink-dot projection, in: Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on, IEEE, 2013, pp. 2683–2688.
  * [6] J. Chen, Q. Gu, T. Aoyama, T. Takaki, I. Ishii, Blink-spot projection method for fast three-dimensional shape measurement, Journal of Robotics and Mechatronics 27 (4) (2015) 430–443.
  * [7] P. Guler, D. Emeksiz, A. Temizel, M. Teke, T. T. Temizel, Real-time multi-camera video analytics system on gpu, Journal of Real-Time Image Processing 11 (3) (2016) 457–472.
  * [8] L. He, X. Ren, Q. Gao, X. Zhao, B. Yao, Y. Chao, The connected-component labeling problem: A review of state-of-the-art algorithms, Pattern Recognition 70 (2017) 25–43.
  * [9] L. Cabaret, L. Lacassagne, L. Oudni, A review of world’s fastest connected component labeling algorithms: Speed and energy estimation, in: Design and Architectures for Signal and Image Processing (DASIP), 2014 Conference on, IEEE, 2014, pp. 1–6.
  * [10] L. He, Y. Chao, K. Suzuki, Two efficient label-equivalence-based connected-component labeling algorithms for 3-d binary images, IEEE Transactions on Image Processing 20 (8) (2011) 2122–2134.
  * [11] J. Martín-Herrero, Hybrid object labelling in digital images, Machine Vision and Applications 18 (1) (2007) 1–15.
  * [12] F. Chang, C.-J. Chen, C.-J. Lu, A linear-time component-labeling algorithm using contour tracing technique, computer vision and image understanding 93 (2) (2004) 206–220.
  * [13] L. He, Y. Chao, K. Suzuki, K. Wu, Fast connected-component labeling, Pattern Recognition 42 (9) (2009) 1977–1987.
  * [14] L. He, Y. Chao, K. Suzuki, A run-based two-scan labeling algorithm, IEEE Transactions on Image Processing 17 (5) (2008) 749–756.
  * [15] L. He, Y. Chao, K. Suzuki, An efficient first-scan method for label-equivalence-based labeling algorithms, Pattern Recognition Letters 31 (1) (2010) 28–35.
  * [16] C. Grana, D. Borghesani, R. Cucchiara, Optimized block-based connected components labeling with decision trees, IEEE Transactions on Image Processing 19 (6) (2010) 1596–1609.
  * [17] L. He, X. Zhao, Y. Chao, K. Suzuki, Configuration-transition-based connected-component labeling, IEEE Transactions on Image Processing 23 (2) (2014) 943–951.
  * [18] C. T. Johnston, D. G. Bailey, Fpga implementation of a single pass connected components algorithm, in: Electronic Design, Test and Applications, 2008. DELTA 2008. 4th IEEE International Symposium on, IEEE, 2008, pp. 228–231.
  * [19] Q. Gu, T. Takaki, I. Ishii, Fast fpga-based multiobject feature extraction, IEEE Transactions on Circuits and Systems for Video Technology 23 (1) (2013) 30–45.
  * [20] M. Manohar, H. Ramapriyan, Connected component labeling of binary images on a mesh connected massively parallel processor, Computer vision, graphics, and image processing 45 (2) (1989) 133–149.
  * [21] R. Dewar, C. Harris, Parallel computation of cluster properties: application to 2d percolation, Journal of Physics A: Mathematical and General 20 (4) (1987) 985\.
  * [22] J. Nickolls, I. Buck, M. Garland, K. Skadron, Scalable parallel programming with cuda, Queue 6 (2) (2008) 40–53.
  * [23] J. Sanders, E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming, Portable Documents, Addison-Wesley Professional, 2010.
  * [24] I.-Y. Jung, C.-S. Jeong, Parallel connected-component labeling algorithm for gpgpu applications, in: Communications and Information Technologies (ISCIT), 2010 International Symposium on, IEEE, 2010, pp. 1149–1153.
  * [25] K. A. Hawick, A. Leist, D. P. Playne, Parallel graph component labelling with gpus and cuda, Parallel Computing 36 (12) (2010) 655–678.
  * [26] O. Kalentev, A. Rai, S. Kemnitz, R. Schneider, Connected component labeling on a 2d grid using cuda, Journal of Parallel and Distributed Computing 71 (4) (2011) 615–620.
  * [27] Y. Soh, H. Ashraf, Y. Hae, I. Kim, Fast parallel connected component labeling algorithms using cuda based on 8-directional label selection, Int. J. Latest Res. Sci. Technol 3 (2) (2014) 187–190.
  * [28] S. Zavalishin, I. Safonov, Y. Bekhtin, I. Kurilin, Block equivalence algorithm for labeling 2d and 3d images on gpu, Electronic Imaging 2016 (2) (2016) 1–7.
  * [29] T. H. Cormen, Introduction to algorithms, MIT press, 2009.
  * [30] V. Oliveira, R. Lotufo, A study on connected components labeling algorithms using gpus, in: SIBGRAPI, Vol. 3, 2010, p. 4.
  * [31] O. Stava, B. Benes, Connected component labeling in cuda, Hwu., WW (Ed.), GPU Computing Gems.
  * [32] P. Kumar, A. Singhal, S. Mehta, A. Mittal, Real-time moving object detection algorithm on high-resolution videos using gpus, Journal of Real-Time Image Processing 11 (1) (2016) 93–109.
  * [33] J.-M. Park, C. G. Looney, H.-C. Chen, Fast connected component labeling algorithm using a divide and conquer technique., Computers and Their Applications 4 (2000) 4–7.
  * [34] T. H. Cormen, C. E. Leiserson, R. L. Rivest, The floyd-warshall algorithm, Introduction to Algorithms (1990) 558–565.
  * [35] P. Chen, H. Zhao, C. Tao, H. Sang, Block-run-based connected component labelling algorithm for gpgpu using shared memory, Electronics letters 47 (24) (2011) 1309–1311.
  * [36] H. Zhao, Y. Fan, T. Zhang, H. Sang, Stripe-based connected components labelling, Electronics letters 46 (21) (2010) 1434–1436.
  * [37] F. N. Paravecino, D. Kaeli, Accelerated connected component labeling using cuda framework, in: International Conference on Computer Vision and Graphics, Springer, 2014, pp. 502–509.
  * [38] Q. Xu, H. Jeon, M. Annavaram, Graph processing on gpus: Where are the bottlenecks?, in: Workload Characterization (IISWC), 2014 IEEE International Symposium on, IEEE, 2014, pp. 140–149.
  * [39] K. Yonehara, K. Aizawa, A line-based connected component labeling algorithm using gpus, in: Computing and Networking (CANDAR), 2015 Third International Symposium on, IEEE, 2015, pp. 341–345.
  * [40] C. Nvidia, Toolkit documentation v7. 0, Nvidia Corporation.
  * [41] C. Grana, L. Baraldi, F. Bolelli, Optimized connected components labeling with pixel prediction, in: International Conference on Advanced Concepts for Intelligent Vision Systems, Springer, 2016, pp. 431–440.
  * [42] C. Grana, F. Bolelli, L. Baraldi, R. Vezzani, Yacclab-yet another connected components labeling benchmark, in: Pattern Recognition (ICPR), 2016 23rd International Conference on, IEEE, 2016, pp. 3109–3114.


# Polynomials Consisting of Quadratic Factors with Roots Modulo Any Positive
Integer

Bhawesh Mishra

###### Abstract

We give an infinite family of polynomials that have roots modulo every
positive integer but fail to have rational roots. Each polynomial in this
family is made up of monic quadratic factors that do not have linear term. The
proofs in this note are accessible to anyone with basic knowledge of
undergraduate elementary number theory.

##  1 Introduction.

We concern ourselves with polynomials $f$ with integer coefficients such that
$f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptm)$ is solvable for
every positive integer $m$. If a polynomial $f$ has an integer root then $f$
clearly has roots modulo every positive integer. However, there exist
polynomials that have roots modulo every positive integer but do not have any
rational root. Such polynomials provide counterexamples to the local-global
principle in number theory (see [Gou20, pp. 99 – 108] for more details on the
local-global principle).

Given a cube-free integer $n\neq 1$, Hyde, Lee, and Spearman proved in [HLS14]
that

$g(x)=(x^{3}-n)(x^{2}+3)$

has no rational roots but has roots modulo every positive integer if and only
if $n\equiv 1\hskip 2.84526pt(\text{mod}\hskip 2.84526pt9)$ and all prime
factors of $n$ are equivalent to $1$ modulo $3$.

It is well known that if $p,q$ are distinct odd primes such that $p\equiv
q\equiv 1($mod $4)$ and $p$ is a square modulo $q$, then the polynomial

$h(x)=(x^{2}-p)(x^{2}-q)(x^{2}-pq)$

has no rational roots but has roots modulo every positive integer (see [JJ98,
pp 139–140]). Let $c$ and $d$ be square-free integers not equal to $1$, let
$c_{1}=\frac{c}{\text{gcd}(c,d)}$ and $d_{1}=\frac{d}{\text{gcd}(c,d)}$. Hyde
and Spearman obtained necessary and sufficient conditions for the polynomial

$p(x)=(x^{2}-c)(x^{2}-d)(x^{2}-c_{1}d_{1})$

to have a root modulo every integer but have no rational root [HS13]. We
obtain necessary and sufficient conditions for polynomials, made up of any
number of similar quadratic factors, to have roots modulo every integer but
have no rational root.

Note that the equation $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip
2.84526ptm)$ is solvable for every positive integer $m$ if and only if the
equation $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{b})$ is
solvable for each prime number $p$ and each positive integer $b$. This is a
consequence of the Chinese remainder theorem.

Given a prime $p$ and an integer $n$, we denote the Legendre symbol of $n$
with respect to $p$ by $\big{(}\frac{n}{p}\big{)}$. When $p\nmid n$,
$\big{(}\frac{n}{p}\big{)}=+1$ if $n$ is a square modulo $p$ and
$\big{(}\frac{n}{p}\big{)}=-1$ otherwise. When $p\mid n$,
$\big{(}\frac{n}{p}\big{)}=0$. Given a prime $p$ and a non-zero integer $l$,
$p^{a}\mid\mid l$ will denote that $p^{a}(a\geq 1)$ is the highest power of
$p$ dividing $l$. Our main result is the following theorem.

######  Theorem 1.

Let $n\geq 3$, $a_{1},a_{2},\ldots,a_{n}$ be distinct nonzero square-free
integers, none of which is $1$. Then the polynomial
$f(x)=(x^{2}-a_{1})(x^{2}-a_{2})\cdots(x^{2}-a_{n})$ has roots modulo every
positive integer if and only if the following conditions are satisfied:

  1. 1.

There exists $T\subseteq\\{1,2,\ldots,n\\}$ of odd cardinality such that:

    1. (a)

the product $\prod_{j\in T}a_{j}$ is a perfect square;

    2. (b)

for every $j\in T$ and for every odd prime $p$ dividing $a_{j}$, there exists
$i\in\\{1,\ldots,n\\}$, $i\neq j$, such that
$\big{(}\frac{a_{i}}{p}\big{)}=+1$ .

  2. 2.

One of the $a_{i}$ is of the form $8m+1$ for some $m\in\mathbb{Z}$ and $m\neq
0$.

We note that the polynomial $f(x)=\prod_{i=1}^{n}(x^{2}-a_{i})$ in Theorem $1$
cannot have a rational root, since none of the $a_{i}$ is a perfect square.

##  2 Results on Quadratic Residues.

In this section, we collect some results on quadratic reciprocity that will be
used to prove Theorem $1$.

  1. 1.

Let $p$ be an odd prime, $e\geq 1$, and $a\in\mathbb{Z}$ such that $p\nmid a$.
Then $a$ is a square modulo $p^{e}$ if and only if
$\big{(}\frac{a}{p}\big{)}=+1.$
Since $p\nmid a$, the proof of this statement is an immediate consequence of
Hensel’s Lemma applied to the polynomial $q(x)=(x^{2}-a)$ (See [JJ98, p. 135]
for a proof).

  2. 2.

    1. (a)

Let $a\in\mathbb{Z}$ be an odd number. Then $a$ is a square modulo $2^{i}$ for
every $i\geq 1$ if and only if $a=8m+1$ for some $m\in\mathbb{Z}$(See [JJ98,
p. 136]) .

    2. (b)

Let $a$ be a square-free integer not equal to $1$. Then $a$ is a square modulo
$2^{i}$ for every $i\geq 1$ if and only $a=8m+1$ for some $m\in\mathbb{Z}$ and
$m\neq 0$ (See [HS13, Lemma 2.5]).

###### Proof.

If $a$ is odd then the result follows from 2(a). On the other hand, if $a$ is
even, then $a\equiv 2\hskip 2.84526pt(\text{mod }4)$ because it is square-
free. Since $2$ is not a square modulo $2^{2}$, $a$ cannot be a square modulo
$2^{2}$. ∎

##  3 Some Useful Lemmas.

We will also use the following lemma, a proof of which appears in [FR89].

######  Lemma 1.

Let $a_{1},a_{2},...,a_{n}$ be finitely many nonzero integers. Then the
following conditions are equivalent:

  1. 1.

For each prime $p$ that does not divide $\prod_{i=1}^{n}a_{i}$ , at least one
of the $a_{i}$ is a square modulo $p$.

  2. 2.

There exists $T\subset\\{1,2,\cdots,n\\}$ of odd cardinality such that
$\prod_{j\in T}a_{j}$ is a perfect square.

######  Lemma 2.

Let $p$ be an odd prime and $a\in\mathbb{Z}$ be a square-free integer. If
$\big{(}\frac{a}{p}\big{)}\neq+1$, then $a$ cannot be a square modulo $p^{2}$.

###### Proof.

If $p\nmid a$ then $\big{(}\frac{a}{p}\big{)}\neq+1$, along with result $1$ on
quadratic reciprocity, gives that $a$ is not a square modulo $p^{2}$.

If $p\mid a$ then $p\mid\mid a$ because $a$ is square-free. Assume that $a$ is
a square modulo $p^{2}$, i.e., $x^{2}\equiv a\hskip 2.84526pt(\text{mod}\hskip
2.84526ptp^{2})$ for some $x\in\mathbb{Z}$. Then we have $p^{2}\mid(x^{2}-a)$,
i.e., $p\mid(x^{2}-a)$.

Since $p\mid a$ and $p\mid(x^{2}-a)$, we have that $p\mid x^{2}$ implying
$p^{2}\mid x^{2}$. However,
$p^{2}\mid(x^{2}-a)$ and $p^{2}\mid x^{2}$ gives that $p^{2}\mid a$,
contradicting that $a$ is square-free. Therefore, $a$ cannot be a square
modulo $p^{2}$. ∎

######  Lemma 3.

Let $p$ be a prime number, $k,n\in\mathbb{N}$, and
$f(x)=\prod_{i=1}^{n}(x^{2}-a_{i})\in\mathbb{Z}[x]$. If $(x^{2}-a_{i})\equiv
0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{k})$ is not solvable for any
$1\leq i\leq n$, then $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip
2.84526ptp^{kn})$ is not solvable.

###### Proof.

For the sake of contradiction, assume that $f(x)\equiv 0\hskip
2.84526pt(\text{mod}\hskip 2.84526ptp^{kn})$ is solvable for some
$x\in\mathbb{Z}$, i.e., $p^{kn}\mid(x^{2}-a_{1})\cdots(x^{2}-a_{n})$. Then we
must have $p^{k}\mid(x^{2}-a_{j})$, for some $j\in\\{1,2,\ldots,n\\}$.

However $p^{k}\mid(x^{2}-a_{j})$ implies that $(x^{2}-a_{j})\equiv 0\hskip
2.84526pt(\text{mod}\hskip 2.84526ptp^{k})$ is solvable, a contradiction to
the fact that $(x^{2}-a_{i})\equiv 0\hskip 2.84526pt(\text{mod}\hskip
2.84526ptp^{k})$ is not solvable for any $i$. Therefore, we have the result. ∎

##  4 Proof of Theorem 1.

###  4.1 Proof of Necessity:

The necessity of the condition $1(a)$ immediately follows from Lemma $1$. Now
we will show that if condition $1(b)$ or condition $2$ fails then $f(x)$ fails
to have root modulo some integer.

Assume that the condition $1(b)$ in Theorem $1$ fails: if $T$ is a subset of
$\\{1,2,\ldots,n\\}$ of odd cardinality for which $\prod_{j\in T}a_{j}$ is a
perfect square, then there exists $j\in T$ and an odd prime $p\mid a_{j}$ such
that $\big{(}\frac{a_{i}}{p}\big{)}\neq+1$ for any $i\neq j$. Since each
$a_{i}$ is square-free, Lemma $2$ implies that for any $i\neq j$,
$(x^{2}-a_{i})\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{2})$ is
not solvable. Similarly, $(x^{2}-a_{j})\equiv 0\hskip
2.84526pt(\text{mod}\hskip 2.84526ptp^{2})$ is not solvable because
$\big{(}\frac{a_{j}}{p}\big{)}=0\neq+1$.

Since $(x^{2}-a_{i})\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{2})$
is not solvable for any $1\leq i\leq n$, Lemma $3$ for $k=2$ implies that the
equation $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{2n})$ is
not solvable.

If the condition $2$ in the statement of Theorem 1 fails, then none of the
$a_{i}$ is equal to $(8m+1)$ for any nonzero $m\in\mathbb{Z}$. Since each of
the $a_{i}$ is square-free, result $2(b)$ on quadratic reciprocity implies for
any $i\in\\{1,2,\ldots,n\\}$, $(x^{2}-a_{i})\equiv 0\hskip
2.84526pt(\text{mod}\hskip 2.84526pt8)$ is not solvable. Then applying Lemma
$3$ for $p=2$ and $k=3$ gives that the congruence $f(x)\equiv 0\hskip
2.84526pt(\text{mod}\hskip 2.84526pt8^{n})$ is not solvable.

###  4.2 Proof of Sufficiency:

As a consequence of the Chinese remainder theorem, it suffices to show that
$f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{b})$ is solvable
for every prime $p$ and every integer $b\geq 1$.

If $p$ is an odd prime that does not divide $\prod_{j\in T}a_{j}$, an
application of Lemma $1$ for $\\{a_{j}\\}_{j\in T}$ implies that for some
$j_{0}\in T$, $a_{{}_{j_{0}}}$ is a square modulo $p$. Since
$p\nmid\prod_{j\in T}a_{j}$, result $1$ on quadratic reciprocity implies that
$a_{{}_{j_{0}}}$ is a square modulo every positive power of $p$. Therefore,
$f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526ptp^{b})$ is solvable
for every integer $b\geq 1$.

If $p$ is an odd prime dividing $\prod_{j\in T}a_{j}$, then $p\mid a_{j}$ for
some $j\in T$. Condition $1(b)$ of Theorem $1$ ensures that there exists
$i\neq j$ such that $\big{(}\frac{a_{i}}{p}\big{)}=+1$. Since
$\big{(}\frac{a_{i}}{p}\big{)}=+1$, we have that $p\nmid a_{i}$. Therefore,
$a_{i}$ is a square modulo all powers of $p$, using result $1$ on quadratic
reciprocity. Hence, $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip
2.84526ptp^{b})$ is solvable for every integer $b\geq 1$.

If $p=2$ then condition $2$ of the theorem ensures that for some
$k\in\\{1,2,\ldots,n\\}$ and for some nonzero integer $m$, $a_{k}=8m+1$. Then
$(x^{2}-a_{k})\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526pt2^{b})$ is
solvable for every $b\geq 1$, by result $2(b)$ on quadratic reciprocity.
Therefore, $f(x)\equiv 0\hskip 2.84526pt(\text{mod}\hskip 2.84526pt2^{b})$ is
solvable for every integer $b\geq 1$.

##  5 Corollaries and Examples.

The first corollary gives a necessary and sufficient condition for the
polynomial $(x^{2}-p)(x^{2}-q)(x^{2}-pq)$ to have roots modulo every positive
integer. Here $p$ and $q$ are distinct odd primes.

######  Corollary 1.

Let $p$ and $q$ be distinct odd primes. The polynomial

$f(x)=(x^{2}-p)(x^{2}-q)(x^{2}-pq)$

has roots modulo every positive integer if and only if
$\big{(}\frac{p}{q}\big{)}=\big{(}\frac{q}{p}\big{)}=+1$.

###### Proof.

Note that $p\times q\times pq=(pq)^{2}$ and that one of $p$ or $q$ or $pq$ has
to be of the form $(8m+1)$ for $0\neq m\in\mathbb{Z}$. So the result follows
by applying Theorem $1$ to $a_{1}=p$, $a_{2}=q$, and $a_{3}=a_{1}a_{2}=pq$. ∎

When $p$ and $q$ are distinct primes such that $p\equiv q\equiv 1\hskip
2.84526pt(\text{mod}\hskip 2.84526pt4)$, $\big{(}\frac{p}{q}\big{)}=+1$ if and
only if $\big{(}\frac{q}{p}\big{)}=+1$. Hence the polynomial
$h(x)=(x^{2}-p)(x^{2}-q)(x^{2}-pq)$ has roots modulo every integer when
$p\equiv q\equiv 1\hskip 2.84526pt(\text{mod}\hskip 2.84526pt4)$ and
$\big{(}\frac{p}{q}\big{)}=+1$, as mentioned in the Introduction.

######  Corollary 2.

Let $c$ and $d$ be two square-free integers not equal to $1$,
$c_{1}=\frac{c}{\text{gcd}(c,d)}$, and $d_{1}=\frac{d}{\text{gcd}(c,d)}$. Then
$f(x)=(x^{2}-c)(x^{2}-d)(x^{2}-c_{1}d_{1})$ has roots modulo every integer if
and only if the following conditions are satisfied:

  1. 1.

For each odd prime $p$ dividing $c$, $\big{(}\frac{d}{p}\big{)}=+1$ or
$\big{(}\frac{c_{1}d_{1}}{p}\big{)}=+1$ and for each odd prime $p$ dividing
$d$, $\big{(}\frac{c}{p}\big{)}=+1$ or
$\big{(}\frac{c_{1}d_{1}}{p}\big{)}=+1$.

  2. 2.

At least one of $c$, $d$ and $c_{1}d_{1}$ is of the form $(8m+1)$ for some
nonzero integer $m$.

Necessary and sufficient conditions for the polynomial in above corollary to
have a root modulo every positive integer were obtained by Hyde and Spearman
in [HS13]. In our Corollary $2$, there are fewer conditions to check compared
to the result obtained in [HS13].

###### Proof.

Apply Theorem $1$ for three square-free integers $a_{1}=c$, $a_{2}=d$, and
$a_{3}=c_{1}d_{1}$ and note that $a_{1}\times a_{2}\times a_{3}=c\times
d\times c_{1}d_{1}=(rc_{1}d_{1})^{2}$, where $r=$ gcd $(c,d)$. ∎

It is instructive to see some examples of application of Theorem $1$. The
polynomials listed below are obtained from different values of $n$ and square-
free integers $a_{1},a_{2},\ldots,a_{n}$ in Theorem $1$.

  1. 1.

$(x^{2}-13)(x^{2}-17)(x^{2}-221)$ has roots modulo every integer because

$13\times 17\times 221=(221)^{2}$, $\big{(}\frac{13}{17}\big{)}=+1$,
$\big{(}\frac{17}{13}\big{)}=+1$, and $17=8(2)+1$.

  2. 2.

$(x^{2}-7)(x^{2}-11)(x^{2}-19)(x^{2}-31)(x^{2}-209)$ has roots modulo every
integer because

$11\times 19\times 209=(209)^{2}$, $\big{(}\frac{31}{11}\big{)}=+1$,
$\big{(}\frac{7}{19}\big{)}=+1$, and $209=8(26)+1$.

  3. 3.

$(x^{2}-7)(x^{2}-11)(x^{2}-19)(x^{2}-31)(x^{2}-45353)$ has roots modulo every
integer because

$7\times 11\times 19\times 31\times 45353=(45353)^{2}$,
$\big{(}\frac{11}{7}\big{)}=+1$, $\big{(}\frac{31}{11}\big{)}=+1$,
$\big{(}\frac{7}{19}\big{)}=+1$, $\big{(}\frac{19}{31}\big{)}=+1$, and
$45353=8(5669)+1$.

######  Acknowledgment.

This research was partly supported by the NSF, under grant DMS-1812028.

## References

  * [FR89] A. M. Filaseta and R. D. Richman, _Sets which Contain a Quadratic Residue Modulo $p$ for Almost All $p$_, Math. J. Okayama Univ. 39 (1989), 1–8.
  * [Gou20] F. Q. Gouvêa, _p-adic Numbers, An Introduction._ , Springer Nature, Cham, Switzerland, 2020.
  * [HLS14] A.M. Hyde, D.P. Lee, and K.B. Spearman, _Polynomials (x 3-n)(x2+3) Solvable Modulo Any Integer _, Amer. Math. Monthly 121:4 (2014), 355–358.
  * [HS13] A.M. Hyde and B.K. Spearman, _Products of Quadratic Polynomials with Roots Modulo Any Integer_ , Int. Math. Forum 8 (2013), 1225–1231.
  * [JJ98] A. G. Jones and J. M. Jones, _Elementary Number Theory_ , Springer-Verlag, London, 1998.