Change-Point Detection for Multi-Way Tensor-Based Frameworks

Abstract

Graph-based change-point detection methods are often applied due to their advantages for using high-dimensional data. Most applications focus on extracting effective information of objects while ignoring their main features. However, in some applications, one may be interested in detecting objects with different features, such as color. Therefore, we propose a general graph-based change-point detection method under the multi-way tensor framework, aimed at detecting objects with different features that change in the distribution of one or more slices. Furthermore, considering that recorded tensor sequences may be vulnerable to natural disturbances, such as lighting in images or videos, we propose an improved method incorporating histogram equalization techniques to improve detection efficiency. Finally, through simulations and real data analysis, we show that the proposed methods achieve higher efficiency in detecting change-points.

1. Introduction

Videos or images are common in real life. Examples include images of traffic lights to regulate traffic, videos recorded by electronic traffic cameras to track vehicles that violate regulations, and webcams in smart agriculture to monitor the ripening stage of vegetables or fruits and automatically estimate the harvest time. Videos or images include huge amounts of information, but not all are useful. Therefore, extracting useful information from videos or a sequence of images, which can be regarded as a change-point detection problem, is important. The authors of [1] proposed a distribution-free, consistent graph-based change-point detection method for recorded videos tracking cell division. After that, a non-Euclidean graph-based change-point test was proposed by [2] as an effective way to reduce random interference, and applied to detecting both landing and departure times in a sequence of bees’ flower visitation data.

Digital videos or images are special cases of multi-way tensors. A r-way tensor can be expressed as $\mathcal{X}\in {\mathbb{R}}^{p_1\times \cdots \times p_r}$, where $\mathbb{R}$ denotes the real number line and $p_{\ell }$ represents the dimension of mode-ℓ of $\mathcal{X}$, $\ell =1,\dots ,r$. The elements of the tensor $\mathcal{X}$ can be accessed using r indices as in $x_{i_1,\dots ,i_r}$, varying $i_{\ell }$ from 1 to $p_{\ell }$, $\ell =1,\dots ,r$. A slice refers to a tensor subarray with one fixed index. For example, ${\mathit{X}}_{i_r}=\left\{x_{·,\dots ,·,r}\right\}$ is defined to be the $i_r$-th slice of $\mathcal{X}$ along mode r (abbreviated as the $i_r$-th mode-r slice), $i_r=1,\dots ,p_r$. Thus, $\mathcal{X}$ contains r different sets of slices. In modern statistical applications, tensors are commonly encountered in many fields. A color image can be represented as a three-way tensor, i.e., ${\mathbb{R}}^{p_1\times p_2\times 3}$, where $\left\{x_{·,·,i_3}\right\}$, $i_3=1,2,3$, are mode-3 slices, the combination of which determines the color of an image. Nevertheless, both [1,2] converted three-way tensors to one-way tensors by taking the average of $R,G,B$ mode-3 slices, which neglects the object’s color information.

In real life, one may also be interested in detecting targets with different colors. For example, detecting changes in the color of traffic lights may help daltonians reduce the limitations of visual impairment and be able to pass through traffic lights normally. Figure 1 shows a sequence of traffic light images containing different colors, such as green ($t=1,\dots ,10$), yellow ($t=11,\dots ,14$), and red ($t=15,\dots ,27$). Traffic light colors are dominated by $R,G,B$ mode-3 slices, not their average. In addition, detecting a change in the color of fruits or vegetables may help monitor their maturity stages and estimate their harvest time, which is important for building automated harvesting systems. For example, the ripening process of tomato fruits can be categorized into three stages: mature green (MG), breaker (BR), and light red (LR) [3,4]. Figure 2 displays 26 frames of these three stages, i.e., MG $(t=1,\dots ,8)$, BR $(t=9,\dots ,19)$, and LR $(t=20,\dots ,26)$, which are extracted from a video that recorded the tomato fruits’ maturation process from MG to LR. However, the pixel values of images or video frames are sensitive to light intensity. Figure 3 presents the same sequence of 26 frames, but the light intensity changes at $t=5,10,17,21$. All these disturbances make change-point detection more challenging.

Inspired by the above examples, we were interested in developing a change-point detection method for the multi-way tensor-based framework, which we present in this paper. Suppose an observation of an object can be represented as a sequence of r-way tensors. The features of an object are dominated by one or a few slices. One may encounter a situation where the distribution of one or some mode-ℓ slices suddenly changes, $\ell =1,\dots ,r$, say, mode-r slices. If so, taking the average over all mode-r slices may mask changes, such that some features of the object are no longer clearly visible. Following the graph-based change-point detection method in [2], we propose two detection methods based on the multi-way tensor framework. One is directly based on the elements of the slices, and the other is based on the histograms of the slices to reduce the influence of natural disturbances, such as lighting, in the image. Change-points occur when the value of some important dominant slices change suddenly. Without loss of generality, we take a three-way tensor as an example to intuitively illustrate the performance of the proposed method. We show through simulations and real-data analysis that the proposed methods are more capable than the method in [2] regardless of whether the sequence of tensors is affected by natural disturbances.

The main contributions of this study are summarized. First, to the best of our knowledge, few studies have addressed the problem of identifying temporal change-points in sequences of tensors. Therefore, we propose a graph-based change-point detection method to identify temporal changes under the framework of multi-way tensors. Second, we propose maximal and histogram-based edge weights to build graphs. The latter aims to downplay or remove natural distractions, such as lighting, in an image. Third, we conduct simulation studies in different scenarios with equal or unequal variances of the slices, with or without natural disturbances. Our simulation results demonstrate the robustness and efficiency of the proposed methods in change-point detection. Finally, our proposed methods are suitable for, but not limited to, detecting color changes of traffic lights and monitoring maturity stage changes in smart agriculture.

2. Methodology

2.1. Model Setup

Let ${\mathcal{X}}_t$ be a sequence of r-way tensors, i.e., ${\mathcal{X}}_t\in {\mathbb{R}}^{p_1\times \cdots \times p_r}$, where $p_{\ell }$, $\ell =1,\dots ,r$, are positive integers, and $t=1,\dots ,T$. ${\mathcal{X}}_t$ contains $p_{\ell }$ mode-ℓ slices, denoted as ${\mathit{X}}_{i_{\ell },t}^{(\ell )}\in {\mathbb{R}}^{p_1\times \cdots \times p_{\ell -1}\times p_{\ell +1}\times \cdots \times p_r}$, where the superscript ℓ denotes different modes, $\ell =1,\dots ,r$, and the subscript $i_{\ell }$ denotes the $i_{\ell }$-th slice along mode ℓ, $i_{\ell }=1,\dots ,p_{\ell }$. For the collection of tensors, assume that a time point $t^{*}$ divides the observations into two segments such that ${\mathcal{X}}_t$ in two segments are significantly different, whereby the mode-ℓ slices characterize the difference. Then $t^{*}$ is a change-point. For example, the color of a colorful image is dominated by mode-3 slices. A change of any mode-3 slice will result in a change in the color of this image. Generally, for the mode-ℓ slices, denote $\mathcal{S}=\{1,\dots ,p_{\ell }\}$. Let ${\mathcal{T}}_t^{(\ell )}$ and ${\mathcal{K}}_t^{(\ell )}$ be subsets of $\mathcal{S}$ for $t=1,\dots ,t^{*}$ and $t=t^{*}+1,\dots ,T$, respectively. Note that ${\mathcal{K}}_t^{(\ell )}=\varnothing$ for $t=1,\dots ,t^{*}$. Without loss of generality, make $\ell =r$. Define $\mathit{j}=\{j_1,\dots ,j_{r-1}\}\in {\mathbb{R}}^{r-1}$, an index label vector, where $j_{\ell }=1,\dots ,p_{\ell }$ with $\ell =1,\dots ,r-1$. Denote $\mathcal{J}=\{1,\dots ,p_1\}\times \cdots \times \{1,\dots ,p_{r-1}\}$. Let $x_{j,m,t}^{\left(r\right)}$ be the elements of ${\mathit{X}}_{m,t}^{\left(r\right)}$ at time t, $\mathit{j}\in \mathcal{J}$ and $m\in \{1,\dots ,p_r\}$. Suppose that the object area of these slices is represented as ${\mathcal{J}}_{1,t}^{\left(r\right)}\subset \mathcal{J}$ at time t. We use the following model to illustrate the time series with a change-point at time $t^{*}$:

(1)$x_{j,m,t}^{\left(r\right)}=\left\{\begin{array}{cc}{\mu }_{m,1}^{\left(r\right)}+{\sigma }_{m,1}^{\left(r\right)}ϵ,\hfill & j\in {\mathcal{J}}_{1,t}^{\left(r\right)},m\in {\mathcal{T}}_t^{\left(r\right)},m\notin {\mathcal{K}}_t^{\left(r\right)},\hfill \\ {\mu }_{m,2}^{\left(r\right)}+{\sigma }_{m,2}^{\left(r\right)}ϵ,\hfill & j\in {\mathcal{J}}_{1,t}^{\left(r\right)},m\in {\mathcal{K}}_t^{\left(r\right)},\hfill \end{array}\right.$

where ${\mu }_{m,i}^{\left(r\right)},{\sigma }_{m,i}^{\left(r\right)},i=1,2$, are unknown parameters, $ϵ$ is an independently identically distributed (iid) random error, with a mean of zero and a variance of one. The first part in model (1) corresponds to the mode-r slices with no change (initial state). The second part shows significant changes among these mode-r slices for $t>t^{*}$. For simplicity, we drop the suffix r in (1). Then, model (1) becomes

(2)$x_{j,m,t}=\left\{\begin{array}{cc}{\mu }_{m,1}+{\sigma }_{m,1}ϵ,\hfill & j\in {\mathcal{J}}_{1,t},m\in {\mathcal{T}}_t,m\notin {\mathcal{K}}_t,\hfill \\ {\mu }_{m,2}+{\sigma }_{m,2}ϵ,\hfill & j\in {\mathcal{J}}_{1,t},m\in {\mathcal{K}}_t.\hfill \end{array}\right.$

If there exists a change-point $t^{*}$, similar to [2], detecting the change-point of (1) is equivalent to testing the following hypothesis:

(3)$H_0:{\mathcal{K}}_t=\varnothing ,t=1,\dots ,T\mathrm{vs}{H}_a:\left\{\begin{array}{cc}{\mathcal{K}}_t=\varnothing ,\hfill & t=1,\dots ,t^{*},\hfill \\ {\mathcal{K}}_t\ne \varnothing ,\hfill & t=t^{*}+1,\dots ,T.\hfill \end{array}\right.$

Suppose that a time point t divides the observations into two segments, ‘past’ ($\le t$) and ‘future’ ($>t$), $t=1,\dots ,T$. In light of [2,5], we define the number of edges that connect points from the ‘past’ and ‘future’ segments over a graph $\mathcal{G}$, for any t, and $(t_1,t_2)\in \mathcal{E}\left(\mathcal{G}\left(\omega \right)\right)$,

(4)$C_t^{\mathcal{G}\left(\omega \right)}=\sum _{(t_1,t_2)\in \mathcal{E}\left(\mathcal{G}\left(\omega \right)\right)}I\{I\{t_1>t\}\ne I\{t_2>t\}\},$

where $I\left\{A\right\}$ is an indicator function that is equal to 1 if A is true, and 0 otherwise; and $\mathcal{G}$ is a connected, edge-weighted undirected graph with vertex set $\{1,\dots ,T\}$ and edge set $\mathcal{E}\left(\mathcal{G}\right)$. Many ways can be used to construct such a graph, such as minimum spanning tree (MST), minimum distance pairing (MDP), and shortest Hamiltonian path (SHP) [1,2,5]. Nevertheless, not all of them perform well in a graph-based hypothesis test. As is shown in [1], a test based on MST performed poorly in terms of power for a large dimension d. Moreover, Chen and Zhang [5] argue that MDP achieves the desirable property of being truly distribution-free. However, Biswas et al. [6] show that the generalized run test using the SHP is distribution-free and consistent as a dimension d goes to infinity. In our study, we thus use the graph $\mathcal{G}$ that is obtained using SHP, denoted as $\mathrm{SHP}\left(\omega \right)$. Small values of $C_t^{\mathcal{G}\left(\omega \right)}$ are against the null hypothesis $H_0$ in (3), which is equivalent to constructing the graph that attains the minimum of the sum of edge weights among all of the spanning paths. Therefore, it is key to establish suitable edge weights ${\omega }_{t_1,t_2}$ between any two nodes $t_1,t_2$ in the construction of graph $\mathcal{G}$. We propose two edge weights, given in (7) or (8) of the following two subsections.

To test the null hypothesis, an SHP-based test was proposed in [1], with the test statistic

(5)$S_T^{\mathrm{SHP}\left(\omega \right)}=\frac{1}{T-1}\sum _{t=1}^{T-1}{\left(Z_t^{\mathrm{SHP}\left(\omega \right)}\right)}^2,$

where $Z_t^{\mathrm{SHP}\left(\omega \right)}$ is the standardization of $C_t^{\mathrm{SHP}\left(\omega \right)}$, $Z_t^{\mathrm{SHP}\left(\omega \right)}=(C_t^{\mathrm{SHP}\left(\omega \right)}-E_0)/\sqrt{{\mathrm{var}}_0}$, $E_0=2t(T-t)/T$; and ${\mathrm{var}}_0=2t(T-t)\{2t(T-t)-T\}/(T^3-T^2)$. We reject the null hypothesis at the significant level $\alpha$ if the statistic $S_T^{\mathrm{SHP}\left(\omega \right)}$ is larger than the simulated critical value. When rejecting $H_0$, the change-point estimate is given by

(6)$\arg \underset{1\le t\le T}{\min }{C}_t^{\mathrm{SHP}\left(\omega \right)}/\left\{t(T-t)\right\}.$

Under the null hypothesis, the distribution of $S_T^{\mathrm{SHP}\left(\omega \right)}$ is distribution-free. The critical values are calculated via the permutation method with 100,000 replications based on various d and significance levels $\alpha$. The details are given in the Appendix A.

2.2. Maximum Edge Weight

As mentioned earlier, it is possible to encounter a mode-r slice change, such as the first mode-r slice. Taking the average of all mode-r slices may mask the importance of the first slice and thus the variation in important features of the object. For example, when a study focuses on detecting time points of color change in a sequence of images, averaging three mode-3 slices removes the color features of these images. Undoubtedly, the method of [2] will fail to detect it. Inspired by the problem of detecting color changes, we thus propose maximum edge weights to enforce the importance of considering the mode-r slices.

Let $\mathcal{E}\left(\mathcal{G}\right)$ be a set of edges of the undirected edge-weighted graph, the nodes of which are $\{1,\cdots ,T\}$. The maximum edge weights of nodes $t_1,t_2$ are defined as

(7)${\omega }_{t_1,t_2}=\underset{m\in \{1,\dots ,p_r\}}{\max }\left|\sum _{j\in \mathcal{J}}(x_{j,m,t_1}-x_{j,m,t_2})\right|,$

where $j\in \mathcal{J}$ means that $j_{\ell }\in \{1,\dots ,p_{\ell }\}$ for $\ell =1,\dots ,r-1$. The methods based on the maximum edge weights and the non-Euclidean edge weights of [2] are named Maxima-SHP and nonE-SHP, respectively.

2.3. Histogram-Based Edge Weight

Both the nonE-SHP and Maxima-SHP are directly based on the differences between tensors’ elements, which can easily be affected by some natural factors. For example, the pixel values of the video’s frames are sensitive to light intensity, which makes the video’s frames or images either over- or under-exposed, resulting in a narrow range of intensity values of pixels. In such a case, using the method of nonE-SHP or Maxima-SHP directly may fail to detect the underlying true change-points. Histogram equalization is useful in images where the background and foreground are both light and dark, by effectively spreading highly populated intensity values. Motivated by the histogram equalization, we propose a new weight based on the histograms of all elements of the tensors rather than all elements directly. For the tensor ${\mathcal{X}}_{m,t}$, let $f_{m,h_i,t}$ be the empirical probability of occurrence of intensity level $h_i$ in the m-th mode-r slice ($m=1,\dots ,p_r$), where $h_i$, $i=1,\dots ,L$, denote the intensity levels, and L is the number of possible intensity levels (e.g., L = 256 for an 8-bit image). We propose a histogram-based edge weight of nodes $t_1,t_2$,

(8)${\omega }_{t_1,t_2}=\underset{\begin{array}{c}k=1,\dots ,L\\ m\in \{1,\dots ,p_r\}\end{array}}{\max }L\left|\sum _{i=1}^k(f_{m,h_i,t_1}-f_{m,h_i,t_2})\right|.$

The weight is in line with the histogram equalization technique that can dilute or remove the effects of disturbances, such as the effects of light intensity on images or videos. The method using the histogram-based edge weight is named HistEq-SHP.

3. Simulations

3.1. Comparative Study of the Performance of NonE-SHP and Maxima-SHP

We generated three-way tensor samples, ${\mathcal{X}}_t\in {\mathbb{R}}^{p_1\times p_2\times 3}$, using model (2). Under the null hypothesis, the model’s settings are ${\mu }_{m,1}=\mathbf{0},{\sigma }_{m,1}=1,ϵ\stackrel{\mathrm{iid}}{\sim }N(0,1)$ for $m=1,2,3$, and $d=p_1{p}_2=5$, 10, 100, 500, 1000, 5000, 10,000, 50,000. We carried out 10,000 simulations with $\alpha =0.05$ and T = 20, 40, 60, 80, 100, 200. Table 1 displays the estimated type I errors via nonE-SHP and the proposed Maxima-SHP. All the estimated type I errors are around 0.05, consistent with the significance level $\alpha =$ 0.05.

Additionally, we examined the powers of Maxima-SHP and nonE-SHP under the alternative hypothesis. For simplicity, we also considered three-way tensor samples generated using model (2) with $r=3$. Suppose that $t^{*}$ is the preset change-point, and ${\mathcal{K}}_t=\{1,3\}$ for $t>t^{*}$, indicating that the distribution of the first and third mode-3 slices ${\mathit{X}}_{1,t}$ change after $t^{*}$. When $t\le t^{*}$, for the third mode-3 slice ${\mu }_{3,1}=0.2$, whereas for the first and second mode-3 slices ${\mu }_{1,1}={\mu }_{2,1}=0$. When $t>t^{*}$, the distribution of the second mode-3 slice remains unchanged, whereas both distributions of the first and third mode-3 slices change, ${\mu }_{1,2}=0.2$ and ${\mu }_{3,2}=0$. Furthermore, let ${\sigma }_{m,1}={\sigma }_{m,2}=1,ϵ\stackrel{\mathrm{iid}}{\sim }N(0,1)$ for $m=1,2,3$. Figure 4 visually shows the generated three-way tensors for $t\le t^{*}$ and after $t^{*}$, i.e., $t>t^{*}$.

We performed the simulations via 10,000 repetitions at the significance level of 0.05. Figure 5 shows the estimated powers of Maxima-SHP and nonE-SHP by setting the change-point at $T/2$. Clearly, as the dimension d increases, the powers of nonE-SHP are all around 0.05, implying that it fails to reject the null hypothesis when the alternative hypothesis is true. However, the powers of Maxima-SHP tend to one for the whole T, empirically showing the strong power consistency. The power consistency of Maxima-SHP is mainly affected by the dimension d. Figure 6 shows similar results as Figure 5 when ${\mu }_{3,1}={\mu }_{1,2}=0.3$ and keeping the other values unchanged. We conducted two more simulations by setting the location of change-point at $T/4$. The results are given in the Appendix B.

Additionally, we carried out other simulations under the scenario of unequal variances for different slices. The variance of the second mode-3 slice was equal to 1.5, whereas the other settings were the same as above. Table 2 shows that the estimated type I errors are still around 0.05 under the null hypothesis for both Maxima-SHP and nonE-SHP. Figure 7 gives the estimated powers under the alternative hypothesis. These results indicate that the proposed Maxima-SHP still outperforms the nonE-SHP, whether the variances of the slices are equal or not.

3.2. Comparative Study of the Performance of NonE-SHP and HistEq-SHP

In order to investigate the performance of HistEq-SHP, we first performed change-point detection by generating a sequence of synthetic gray images (r = 2) under different T and d. Figure 8 is an example of T = 40, d = 10,000, r = 2. In Figure 8, we depict images constructed using a normal distribution with a mean of 0.8 and a standard deviation of 0.05 for $t=1,\dots ,9$ (see Figure 8a ), and using a normal distribution with a mean of 0.5 and a standard deviation of 0.05 for $t=10,\dots ,19$ (see Figure 8b). Furthermore, we added an object, the shape of a butterfly, to the images constructed using the normal distribution with a mean of 0.5 and a standard deviation of 0.05 for $t=20,\dots ,29$ (see Figure 8c). Finally, the illustration of the image in Figure 8d was generated on the basis of Figure 8a for $t=30,\dots ,40$. The time point $t=19$ is the change-point. Under various T and d, we calculated the empirical powers based on 10,000 repetitions. We remark that we preprocessed the images using the histogram equalization technique before using the nonE-SHP method. Table 3 displays the powers of HistEq-SHP and nonE-SHP, which shows that the powers of both methods are ones when d = 5000 and 10,000 regardless of T. For d = 50,000, the powers of HistEq-SHP are ones, but those of the nonE-SHP method are close to one, implying the proposed method outperforms the nonE-SHP method for high dimension d.

We further examined the performance of these methods on three-way tensors by extending gray images to color images. As we discussed in the introduction, lighting can easily affect images, making change-point detection even more challenging. We performed another simulation to check the stability of the proposed methods by generating synthetic images under different light intensities. Figure 9 displays four types of images: Figure 9a is generated from a normal distribution with a mean of 0.8 and a standard deviation of 0.05 for three mode-3 slices, and a red object is added; Figure 9b is generated in the same way as in Figure 9a except that the mean of the normal distribution is 0.5; Figure 9c,d are generated in the same way as in Figure 9b and Figure 9a, respectively, except that blue targets replaced the red ones. Note that Figure 9a,d are in the same light intensity, and so are Figure 9b,c. It is obvious that the time change-point is at $t^{*}=19$. Table 4 gives the powers of nonE-SHP and HistEq-SHP. It shows that the powers of nonE-SHP are close to 0.05 in all cases, and, hence, the method failed to detect the real change-point, i.e., where the colors of the object are not the same, and the images receive different light intensities. On the contrary, the powers of HistEq-SHP are all ones. The results demonstrate that although the images are affected by different light intensities, the proposed HistEq-SHP method can successfully identify the true change-point.

4. Case Studies

4.1. Example 1: Color Change in a Traffic Light

Our proposed method has important implications in real life. An application that recognizes the color change of traffic lights may help daltonians reduce the limitations of their visual impairment and allow them to navigate traffic light intersections. We extracted 27 frames per second from a short video (27 s) taken at a traffic light intersection, recording the entire traffic light transition from green to red. We cropped each frame to size $73\times 40$. Figure 1 displays three frames containing different colors of the traffic light, green ($t=1,\dots ,10$), yellow ($t=11,\dots ,14$), and red ($t=15,\dots ,27$). Clearly, based on the hypothesis test in (3), two change-points exist: $t^{*}=10$ and $t^{*}=14$. In this case, we aim to detect the moments when the traffic light has changed its color, e.g., $t^{*}=10$ and 14.

We transformed the three-way tensor of the R,G,B slices into three vectors and normalized the pixel values. According to Equation (7), we extracted the maximum edge weights of the three color slices to construct $\mathrm{SHP}\left(\omega \right)$. The test statistic $S_T^{\mathrm{SHP}\left(\omega \right)}$ in Equation (5) was 10.5787, larger than the corresponding critical value 2.1491 ($T=27,d=2920$), leading to the rejection of the null hypothesis at the significance level 0.05. The estimated location of the change-point was $t^{*}=14$. To further test if other change-points exist, we considered the two segments: $\{{\mathcal{X}}_t,t=1,\dots ,13\}$ (Segment I) and $\{{\mathcal{X}}_t,t=15,\dots ,27\}$ (Segment II). Following the same procedure as above, the second change-point was estimated at $t^{*}=10$ in Segment I, whereas there was no change-point in Segment II. The estimated results are given in Figure 10 (upper panel), which agrees with the real situation.

To compare Maxima-SHP with nonE-SHP, we also constructed the $\mathrm{SHP}\left(\omega \right)$ via the non-Euclidean weight given by [2]. By following the same procedure, although the ratio cut was minimized at location 19, the statistic $S_T^{\mathrm{SHP}\left(\omega \right)}$ was 0.6278, less than the critical value, resulting in failing to reject the null hypothesis. The results are given in Figure 10 (lower panel). As expected, the nonE-SHP failed to detect the real change-points in such a scenario because it disregarded the main feature in three slices in constructing its non-Euclidean weights.

4.2. Example 2: Tomato Fruit Color Change

Nowadays, automatic harvesting systems have become a powerful technique for smart agriculture [7]. Monitoring the maturity stages of fruits or vegetables and estimating their harvest time are important steps in building an automatic harvesting system. Based on video recordings of fruit’s or vegetable’s maturation processes, the problem of monitoring the maturity stages and estimating the harvest times of fruit or vegetable can be transformed into a change-point detection problem.

Figure 2 shows three stages of the ripening process of the tomato fruit, MG $(t=1,\dots ,8)$, BR $(t=9,\dots ,19)$, and LR $(t=20,\dots ,26)$, containing 26 frames extracted from a video. Each of them was cropped to size 149 × 149. Obviously, $t^{*}=8$ and $t^{*}=19$ are considered as the change-points. Applying the change-point detection methods of HistEq-SHP and nonE-SHP, the results are displayed in Figure 11. As expected, both methods successfully detected the real change-points.

However, videos or images are easily affected by light intensity, which makes change-point detection more challenging. Here, we present another example to illustrate that our proposed method is more robust than the nonE-SHP when the recorded videos or frames are recorded in different light intensities. We darkened the frames of $t=6,\dots ,10$ and lightened the frames of $t=18,\dots ,21$, shown in Figure 3. Note that the change-points are still at $t^{*}=8$ and $t^{*}=19$, the detection of which is easily affected by the false change-points $t=5$, $t=10$, $t=17$, and $t=21$, where the light intensity changes. By applying nonE-SHP, three false change-points $t^{*}=5$, $t^{*}=10$, and $t^{*}=17$ were detected (see the lower panel of Figure 12). In contrast, the proposed HistEq-SHP detected two change-points at $t^{*}=8$ and $t^{*}=19$ (see the upper panel of Figure 12), consistent with the real ones. The nonE-SHP failed to detect the real change-points when the videos or frames were recorded in different light intensities. However, our proposed HistEq-SHP remained unaffected by disturbance(s) and successfully detected the real change-points.

5. Conclusions

Nowadays, videos or images are ubiquitously used in real life. This paper proposes a general class of graph-based change-point detection methods for checking whether objects with different characteristics and sequences of tensors are affected by natural disturbances. Simulation studies empirically showed the power consistency of the proposed methods. Furthermore, the proposed methods are shown to detect changes in the color of traffic lights at intersections and monitor changes in fruit ripening stages in smart farming. All numerical studies demonstrated the effectiveness of the proposed methods.

Author Contributions

Conceptualization, Y.W. and S.Q.; methodology, Y.W. and S.Q.; software, S.Q.; validation, S.Q. and G.Z.; formal analysis, S.Q.; investigation, S.Q.; resources, S.Q.; data curation, S.Q. and G.Z.; writing—original draft preparation, S.Q. and G.Z.; writing—review and editing, Y.W. and S.Q.; visualization, G.Z.; supervision, Y.W. and S.Q.; project administration, S.Q. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. Three different colors of traffic lights: green (left panel, [Forumla omitted. See PDF.]), yellow (middle panel, [Forumla omitted. See PDF.]), and red (right panel, [Forumla omitted. See PDF.]).

Figure 2. Three ripening stages: MG (left panel, [Forumla omitted. See PDF.]), BR (middle panel, [Forumla omitted. See PDF.]), and LR (right panel, [Forumla omitted. See PDF.]).

Figure 3. Three ripening stages where the light intensity changes at [Forumla omitted. See PDF.]: (a) [Forumla omitted. See PDF.], (b) [Forumla omitted. See PDF.], (c) [Forumla omitted. See PDF.], (d) [Forumla omitted. See PDF.], (e) [Forumla omitted. See PDF.], (f) [Forumla omitted. See PDF.], (g) [Forumla omitted. See PDF.].

Figure 4. Illustration of the generated three-way tensors for [Forumla omitted. See PDF.] and [Forumla omitted. See PDF.] in the middle and on the right, respectively.

Figure 5. Estimated powers of Maxima-SHP and nonE-SHP over 10,000 simulations by setting equal slice variance; [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.]; and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.].

Figure 6. Estimated powers of Maxima-SHP and nonE-SHP over 10,000 simulations by setting [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.]; and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.].

Figure 7. Estimated powers of Maxima-SHP and nonE-SHP over 10,000 simulations with unequal variances of slices by setting [Forumla omitted. See PDF.], [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.]; and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.].

Figure 8. Illustrations of a sequence of synthetic gray images with T = 40, d = 10,000, [Forumla omitted. See PDF.]: (a) [Forumla omitted. See PDF.]; (b) [Forumla omitted. See PDF.]; (c) [Forumla omitted. See PDF.]; (d) [Forumla omitted. See PDF.].

Figure 9. Illustrations of a sequence of synthetic color images with T = 40, d = 10,000, r = 3: (a) [Forumla omitted. See PDF.]; (b) [Forumla omitted. See PDF.]; (c) [Forumla omitted. See PDF.]; (d) [Forumla omitted. See PDF.]. (a,d) are in the same light intensity, and so are (b,c).

Figure 10. The change-point estimation using Maxima-SHP (upper panel) and nonE-SHP (lower panel).

Figure 11. Change-point detection via HistEq-SHP (upper panel) and nonE-SHP (lower panel).

Figure 12. Change-points detected by HistEq-SHP (upper panel) and nonE-SHP (lower panel), light intensity changes at [Forumla omitted. See PDF.].

Table 1

Comparison of type I error rates using nonE-SHP and Maxima-SHP based on various T and d.

T	Method	d
		10	50	100	500	1000	5000	10,000	50,000
20	Maxima-SHP	0.0519	0.0505	0.0493	0.0495	0.0524	0.0495	0.0507	0.0513
	nonE-SHP	0.0446	0.0506	0.0502	0.0510	0.0535	0.0494	0.0496	0.0463
40	Maxima-SHP	0.0512	0.0495	0.0519	0.0500	0.0561	0.0503	0.0460	0.0531
	nonE-SHP	0.0529	0.0498	0.0484	0.0496	0.0478	0.0530	0.0502	0.0530
60	Maxima-SHP	0.0507	0.0491	0.0479	0.0508	0.0483	0.0477	0.0497	0.0497
	nonE-SHP	0.0487	0.0491	0.0489	0.0518	0.0460	0.0504	0.0507	0.0469
80	Maxima-SHP	0.0487	0.0495	0.0508	0.0479	0.0565	0.0468	0.0505	0.0514
	nonE-SHP	0.0522	0.0513	0.0493	0.0538	0.0522	0.0480	0.0519	0.0500
100	Maxima-SHP	0.0459	0.0498	0.0465	0.0476	0.0517	0.0481	0.0484	0.0484
	nonE-SHP	0.0522	0.0506	0.0521	0.0458	0.0497	0.0456	0.0496	0.0483
200	Maxima-SHP	0.0456	0.0507	0.0480	0.0514	0.0510	0.0513	0.0500	0.0540
	nonE-SHP	0.0476	0.0514	0.0473	0.0489	0.0466	0.0519	0.0434	0.0503

Table 2

Comparison of type I error rates of nonE-SHP and Maxima-SHP with unequal variances of slices, based on various T and d.

T	Method	d
		10	50	100	500	1000	5000	10,000	50,000
20	Maxima-SHP	0.0532	0.0479	0.0537	0.0484	0.0464	0.0520	0.0516	0.0497
	nonE-SHP	0.0489	0.0468	0.0533	0.0471	0.0511	0.0525	0.0494	0.0468
40	Maxima-SHP	0.0475	0.0519	0.0501	0.0473	0.0516	0.0464	0.0533	0.0525
	nonE-SHP	0.0490	0.0495	0.0542	0.0478	0.0529	0.0500	0.0498	0.0527
60	Maxima-SHP	0.0518	0.0531	0.0496	0.0492	0.0476	0.0508	0.0532	0.0521
	nonE-SHP	0.0469	0.0471	0.0456	0.0514	0.0538	0.0464	0.0565	0.0487
80	Maxima-SHP	0.0485	0.0493	0.0462	0.0455	0.0530	0.0472	0.0504	0.0521
	nonE-SHP	0.0498	0.0476	0.0446	0.0487	0.0501	0.0481	0.0466	0.0504
100	Maxima-SHP	0.0495	0.0472	0.0514	0.0508	0.0534	0.0494	0.0530	0.0503
	nonE-SHP	0.0505	0.0496	0.0483	0.0441	0.0513	0.0504	0.0477	0.0534
200	Maxima-SHP	0.0489	0.0527	0.0537	0.0502	0.0521	0.0479	0.0543	0.0487
	nonE-SHP	0.0461	0.0528	0.0516	0.0523	0.0515	0.0510	0.0501	0.0462

Table 3

Comparison of the powers of nonE-SHP and HistEq-SHP based on gray images with various T and d.

T	Method	d
		5000	10,000	50,000
40	nonE-SHP	1.0000	1.0000	0.9110
	HistEq-SHP	1.0000	1.0000	1.0000
100	nonE-SHP	1.0000	1.0000	0.9991
	HistEq-SHP	1.0000	1.0000	1.0000

Table 4

Comparison of the powers of nonE-SHP and HistEq-SHP based on color images with various T and d.

T	Method	d
		5000	10,000	50,000
40	nonE-SHP	0.0503	0.0485	0.0499
	HistEq-SHP	1.0000	1.0000	1.0000
100	nonE-SHP	0.0527	0.0507	0.0494
	HistEq-SHP	1.0000	1.0000	1.0000

Appendix A. Simulated Critical Values of Both Maxima-SHP and HistEq-SHP

Appendix A.1. Simulated Critical Values of Maxima-SHP

Under the null hypothesis, the distribution of $S_T^{\mathrm{SHP}\left(\omega \right)}$ defined in (5) is distribution-free. The critical values are obtained from simulations via the permutation method with 100,000 replications based on various d and significance levels $\alpha$. Table A1 lists the estimated critical values under the null hypothesis. We generated data using model (2) with ${\mathcal{K}}_t=\varnothing$ and $T=20,r=3,{\mu }_{m,1}=0,{\sigma }_{m,1}=1,ϵ\stackrel{\mathrm{iid}}{\sim }N(0,1)$ for $m=1,2,3$. The significance levels mainly indicate changes in the critical values. There is little difference among the $c_{\alpha }$ in response to changing the dimension d and the length of tensor sequences T. Table A2–Table A4 present the estimated $c_{\alpha }$ by letting $T=60,100,200$, respectively.

Table A1

The estimated critical values ($c_{\alpha }$) of the Maxima-SHP based on different d and significance levels $\alpha$ for $T=20$.

d	10%	5%	2.5%	1%	0.5%	0.1%
10	1.7491	2.1163	2.4878	2.9904	3.3718	4.2241
50	1.7518	2.1321	2.4972	2.9871	3.3772	4.2879
100	1.7491	2.1203	2.4990	2.9992	3.3752	4.2060
500	1.7506	2.1254	2.5020	2.9799	3.3375	4.1512
1000	1.7537	2.1194	2.5027	3.0056	3.3562	4.2720
5000	1.7524	2.1200	2.4859	2.9723	3.3488	4.2147
10,000	1.7658	2.1307	2.5027	3.0002	3.3875	4.2840
50,000	1.7555	2.1269	2.4926	2.9829	3.3603	4.2390

Table A2

The estimated critical values ($c_{\alpha }$) of the Maxima-SHP based on different d and significance levels $\alpha$ for $T=60$.

d	10%	5%	2.50%	1%	0.50%	0.10%
10	1.7726	2.1602	2.5744	3.1198	3.5629	4.5688
50	1.7630	2.1617	2.5717	3.1458	3.5821	4.5475
100	1.7790	2.1814	2.5877	3.1514	3.6000	4.6520
500	1.7682	2.1564	2.5540	3.1161	3.5231	4.3641
1000	1.7744	2.1652	2.5785	3.1312	3.5226	4.6107
5000	1.7821	2.1858	2.5948	3.1566	3.5853	4.4944
10,000	1.7607	2.1471	2.5483	3.0943	3.5304	4.4988
50,000	1.7652	2.1552	2.5569	3.1253	3.5456	4.5816

Table A3

The estimated critical values ($c_{\alpha }$) of the Maxima-SHP based on different d and significance levels $\alpha$ for T = 100.

d	10%	5%	2.50%	1%	0.50%	0.10%
10	1.7637	2.1659	2.5594	3.1031	3.5163	4.4318
50	1.7646	2.1612	2.5491	3.0839	3.5053	4.4586
100	1.7681	2.1662	2.5509	3.1026	3.5370	4.5026
500	1.7789	2.1791	2.5795	3.1361	3.5555	4.5226
1000	1.7667	2.1700	2.5823	3.1372	3.5414	4.5186
5000	1.7700	2.1596	2.5664	3.0797	3.5040	4.5572
10,000	1.7613	2.1526	2.5711	3.1216	3.5611	4.5922
50,000	1.7657	2.1685	2.5609	3.1098	3.5059	4.4325

Table A4

The estimated critical values ($c_{\alpha }$) of the Maxima-SHP based on different d and significance levels $\alpha$ for T = 200.

d	10%	5%	2.50%	1%	0.50%	0.10%
10	1.7584	2.1543	2.5425	3.0915	3.4645	4.5578
50	1.7476	2.1284	2.5239	3.0532	3.4679	4.4469
100	1.7513	2.1404	2.5414	3.0683	3.5084	4.5517
500	1.7526	2.1420	2.5245	3.0276	3.4349	4.3104
1000	1.7575	2.1340	2.5359	3.0681	3.4754	4.4134
5000	1.7578	2.1457	2.5428	3.0905	3.5153	4.5126
10,000	1.7598	2.1489	2.5446	3.0879	3.4847	4.4418
50,000	1.7476	2.1336	2.5343	3.0567	3.4472	4.4326

Appendix A.2. Simulated Critical Values for the HistEq-SHP

According to the intensity levels of the 8-bit image, let L equal 256. We replaced the weight in $S_T^{\mathrm{SHP}\left(\omega \right)}$ with Equation (8) to obtain the critical values ($c_{\alpha }^{{}^{\prime }}$) the same way. Table A5 lists the estimated critical values with $T=40$, d = 5000, 10,000, 50,000. Significant differences of $c_{\alpha }^{{}^{\prime }}$ are only evident among different $\alpha$ values. The critical values are slightly different as the value of d changes. Other settings of the critical values with $T=100$, d = 5000, 10,000, 50,000 are presented in Table A6, in which the same phenomena as in Table A5 can be observed.

Table A5

The estimated critical values ($c_{\alpha }^{{}^{\prime }}$) of the HistEq-SHP based on different d and significance levels $\alpha$ for $T=40$.

d	10%	5%	2.5%	1%	0.5%	0.1%
5000	1.7857	2.1754	2.5571	3.1191	3.5116	4.6093
10,000	1.7775	2.1704	2.5683	3.1237	3.5465	4.4774
50,000	1.7680	2.1591	2.5433	3.0833	3.4894	4.4746

Table A6

The estimated critical values ($c_{\alpha }^{{}^{\prime }}$) of the HistEq-SHP based on different d and significance levels $\alpha$ for T = 100.

d	10%	5%	2.50%	1%	0.50%	0.10%
5000	1.7895	2.2013	2.6125	3.1743	3.6417	4.6668
10,000	1.7827	2.1841	2.6033	3.1570	3.5595	4.5371
50,000	1.7742	2.1755	2.5914	3.1428	3.5968	4.5675

Appendix B. Empirical Powers of Maxima-SHP and NonE-SHP

We examined the powers of Maxima-SHP and nonE-SHP under the alternative hypothesis by setting the change-point at $T/4$. Figure A1 and Figure A2 show similar results as Figure 5 and Figure 6, respectively.

Figure A1. Empirical powers of both Maxima-SHP and nonE-SHP based on 10,000 simulations with [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.]; and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.].

Figure A2. Empirical powers of both Maxima-SHP and nonE-SHP based on 10,000 simulations with [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.]; and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.].

References

1. Shi, X.; Wu, Y.; Rao, C.R. Consistent and powerful graph-based change-point test for high-dimensional data. Proc. Natl. Acad. Sci. USA; 2017; 114, pp. 3873-3878. [DOI: https://dx.doi.org/10.1073/pnas.1702654114] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/28356520]

2. Shi, X.; Wu, Y.; Rao, C.R. Consistent and powerful non-Euclidean graph-based change-point test with applications to segmenting random interfered video data. Proc. Natl. Acad. Sci. USA; 2018; 115, pp. 5914-5919. [DOI: https://dx.doi.org/10.1073/pnas.1804649115] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/29784801]

3. Gonzalez, C.; Ré, M.D.; Sossi, M.L.; Valle, E.M.; Boggio, S.B. Tomato cv. ‘Micro-Tom’ as a model system to study postharvest chilling tolerance. Sci. Hortic.; 2015; 253, pp. 412-421. [DOI: https://dx.doi.org/10.1016/j.scienta.2014.12.020]

4. Reissig, G.N.; Posso, D.A.; Borella, J.; da Silveira, R.V.D.; Rombaldi, C.V.; Bacarin, M.A. High MT-sHSP23.6 expression and moderate water deficit influence the antioxidant system in ‘Micro-Tom’ tomato fruit under hypoxia. Sci. Hortic.; 2020; 242, pp. 127-136. [DOI: https://dx.doi.org/10.1016/j.scienta.2018.07.035]

5. Chen, H.; Zhang, N. Graph-Based Change-Point Detection. Ann. Stat.; 2015; 43, pp. 139-176. [DOI: https://dx.doi.org/10.1214/14-AOS1269]

6. Biswas, M.; Mukhopadhyay, M.; Ghosh, A.K. A distribution-free two-sample run test applicable to high-dimensional data. Biometrika; 2014; 101, pp. 913-926. [DOI: https://dx.doi.org/10.1093/biomet/asu045]

7. Fujinaga, T.; Yasukawa, S.; Ishii, K. Tomato growth state map for the automation of monitoring and harvesting. J. Robot. Mechatronics; 2020; 32, pp. 1279-1291. [DOI: https://dx.doi.org/10.20965/jrm.2020.p1279]