Evaluation of Categorical Generative Models -- Bridging the Gap Between Real and Synthetic Data

The machine learning community has mainly relied on real data to benchmark algorithms as it provides compelling evidence of model applicability. Evaluation on synthetic datasets can be a powerful tool to provide a better understanding of a model's strengths, weaknesses, and overall capabilities. Gaining these insights can be particularly important for generative modeling as the target quantity is completely unknown. Multiple issues related to the evaluation of generative models have been reported in the literature. We argue those problems can be avoided by an evaluation based on ground truth. General criticisms of synthetic experiments are that they are too simplified and not representative of practical scenarios. As such, our experimental setting is tailored to a realistic generative task. We focus on categorical data and introduce an appropriately scalable evaluation method. Our method involves tasking a generative model to learn a distribution in a high-dimensional setting. We then successively bin the large space to obtain smaller probability spaces where meaningful statistical tests can be applied. We consider increasingly large probability spaces, which correspond to increasingly difficult modeling tasks and compare the generative models based on the highest task difficulty they can reach before being detected as being too far from the ground truth. We validate our evaluation procedure with synthetic experiments on both synthetic generative models and current state-of-the-art categorical generative models.

INTRODUCTION
In the machine learning community, evaluation of generative models is an ongoing topic of research [1,2,3,4,5,6,7,8]. The most common method is to evaluate the (usually upper bounded) log-likelihood on held out test data; the model with the highest log-likelihood is declared the better model. Although principled, this method of evaluation has some known drawbacks as highlighted in [6]. A simple example from [9] shows how good likelihood models can generate poor samples. Simply put, the learned model is far from the true distribution.
Another observation, possibly symptomatic of this issue, is the out-of-distribution (OOD) problem. A notable finding by [10] is that high likelihood and good sample generation do not guarantee good OOD detection. The task of OOD detection is an important application of generative modeling. If a Fig. 1: Overview of our proposed binning procedure. The initial distribution p has s = 3 flat regions on the Ω space contained in S = {S 1 , S 2 , S 3 } . For a granularity level k = 4, our binning procedure finds that cutting Hypothesis testing can then be conducted over the induced distributions p B * 4 , q B * 4 on the 4 event probability space B * 4 .
model is an appropriate approximation of the true distribution, then it should be able to detect low-probability samples. One approach taken in the literature to mitigate this problem is to adopt a more comprehensive and task-oriented methods of evaluation. By assessing over multiple metrics and designing task-oriented metrics, one can better assess the true capabilities of a generative model [6,3,11]. Nonetheless, this remains a heuristic approach that is unavoidably tied to the application at hand and therefore cannot be applied to the general problem of generative model evaluation.
In this work, we propose to return to a synthetic setting where the evaluation of a generative model can be framed as a statistical identity testing problem. This allows us to draw from statistical testing literature. This approach alleviates the problems associated with log-likelihood evaluation. Rather than testing whether high log-likelihood is assigned to unseen samples, we can directly evaluate whether the model assigns the correct probability mass to each element in the space. We can then directly answer questions about OOD capability, sample generation quality, and overall generative modeling performance. This approach also provides better insight into which types of distributions a particular generative model can fit.
The synthetic task must be representative of the actual task a generative model would be called to solve. In almost all cases, generative models in machine learning target a (very) high dimensional setting. One challenge induced by such set-tings is that statistical tests based on samples become meaningless. We simply cannot collect enough samples for a test to reject a null hypothesis. In this work, to address this issue, we propose an algorithm to bin the probability space at various granularity levels. We then consider the induced distributions on the smaller probability spaces as a testing proxy for our generative model quality, observing that the error for the induced distributions is a lower bound on the error in the original space. Figure 1 provides an overview of our procedure. Random binning is not successful and we explain how we construct bins to maximize the lower bound on the error.
We validate our binning procedure through synthetic experiments, ensuring it can preserve the correct ranking of synthetic generative models. We then show that our testing procedure correctly ranks state-of-the-art generative models trained on our synthetic task by comparing with the empirical total variation on the initial space Ω and with visual inspection of the learned distributions.

METHODOLOGY
We aim to design an evaluation method or metric that can rank generative models reliably for a very large scale discrete distribution space |Ω|, given the ground truth distribution p. Given samples from unknown distributions q 1 , q 2 , we wish to distinguish which distribution is closer to a reference distribution p (thus achieving a ranking of generative models).

Distribution Testing
This setting is analogous to a fundamental problem in statistical distribution testing: identity testing. In this setting, given sample access to an unknown distribution q, an identity test declares if q is -close to a reference distribution p with probability at least 1 − δ. See [12,13] for a more formal definition and [14] for a review on this topic. In this field, closeness of discrete distributions p, q on a discrete sample space Ω is formalized as the total variation distance: (with p x used as a shorthand for p(x)). The 2 or Hellinger can also be used. For relatively small sized Ω, results from the identity testing literature can be applied directly. However, we target large Ω where the practical number of samples is m |Ω|. At this scale, algorithms for identity testing are unusable; the provably most powerful test has a |Ω| term in its required number of samples [13].

Binning the space
We propose to move from the probability space Ω to a smaller space B by binning the elements x in partitioning sets of Ω: We then assess the distributions induced by this binning to evaluate the models.
We denote all partitions of Ω by ρ(Ω). The 'binned' distribution of the ground truth p is p B , and the 'binned' distribution of the generative model q becomes q B , where p B A = x∈A p x . This binning operation naturally introduces a new total variation error on the B space : Binning also introduces an error between the initial distribution p and its binned version p B that can be defined as: At the cost of introducing error, binning allows us to reduce the space to a workable size, so that we can use tools from the distribution testing literature. In particular, we can design a hypothesis test that aims to reject H 0 : d(p B , q B ) < at a probability significance level δ.
We can see that d T V (p B , q B ) is a lower bound for d T V (p, q), but the result of such test in the binned space does not provide an direct indication of the outcome in the original space. The intuition is that, if the test fails for some binning B, this suggests that a generative model is poor, in the sense that it cannot achieve the easier task of representing the binned distribution to within a required error. In the following section, we describe how we select the binning.

Choosing the bins
When moving from p, q to p B , q B , information is inevitably lost. Additionally, a smaller numbers of bins k = |B| will result in greater information loss. Therefore, for a given granularity level k, bins are chosen such that the least possible error on B k is introduced for the reference distribution p.
Minimizing the binning error of p→p B : We start by considering bins that minimize the error from going to p to p B . Denote by B p k (λ) the set of all k partitions of Ω s.t. p→p B is at most λ: where ρ k (Ω) denotes the set of all partitions of Ω of size k.
It is easy to test whether a particular B lies in B p k (λ) for any p, but B p k (λ) may be very large solution space. For the particular case where no error is tolerated B p k (λ = 0), however, the space is much smaller (and may be empty).
We take advantage of our ability to specify the synthetic distribution p, and construct p so that the pmf has s unique values and places all elements with a common value in bins S i to form the binning S = {S 1 , . . . , S s }. With a judicious choice of s, such a reference distribution is sufficient to provide a stern test of generative models. Given a p with s = |S| flat regions, we have that : where ci ∈ N is the cardinally of the partitioning that can be made on Si. The set { S i ∈S Pi; Pi ∈ ρ c j (Si), j cj = k} is all possible Algorithm 1 Highest granularity level k of q Input: p with flat regions s = |S|, sampling access from q, error threshold test , significance level δ.
Return the granularity k at which the test failed. Maximizing the binning error of p B , q B : By the triangle inequality, we can see that true error will always be greater than B . Hence, given the choice of binning from (B p k (0)), we can select the binning that maximizes the error between the induced binned distribution p B and the induced binned distribution q B : This concludes how we select bins at a specific granularity level B * k . For a given flat region A i , if we seek a k = 2 bingranularity: ρ 2 (S i ), the unique solution that maximises the error is to split the positive error region {x ∈ S i ; q x − p x > 0} from the negative error region {x ∈ S i ; q x − p x < 0}. If there is no positive or negative error, then every bin is equivalent. Thus, different and tractable solutions for the granularity k = {s, . . . , 2s} can be obtained: We have presented the discussion in terms of q and q B , but we assume that we only have sample access to q (and hence to q B ). Hence, only the empirical pmf of q is accessible. We can approximate with: . A limitation of this procedure is that it is tied to the number of flat regions s of the distribution p. However, since we have control over p, we can choose p with a number of flat regions that achieves a trade off between (i) posing a suitably demanding challenge and (ii) generating a test that does not require too many samples. In general, in very high dimensions, such as those of protein sequences, for example, structured distributions can be very challenging to learn even if there are only three unique values.

Hypothesis testing
We now have a sequence of binnings of increasingly difficult granularity levels, ranging from k = s to k = 2s : B * s , B * s+1 , . . . , B * 2s . At each granularity level k, we can use a hypothesis test to detect poor approximation of the ground truth. Since the sampling complexity of the test scales with the probability space and we control the granularity level k, we can easily generate O(k) samples. Our null hypothesis is that the binned generative model q B * k is within some error test of the ground truth distribution p B * k ; i.e.
We use the 2 distance as it is more practical to test for. If the test is able to reject at some granularity k, we stop and return this k as the highest granularity level reached by the generative model q. For the hypothesis testing, we use the closeness test from [15], which tests the distance between two distributions, both of which only have sample access. To make the test applicable to our context, we simply replace the statistical estimates for unknown p by our known statistics for p. The complete testing procedure is outlined in Algorithm 1.

EXPERIMENTS 3.1. Datasets
Our synthetic experiments are designed to emulate real world datasets. The most important characteristic is that the sampling space is several orders larger than the number of generated samples m. Second, the support of the targeted distribution (that we denote Ω + = {x ∈ Ω; p x > 0}) is believed to be much smaller than the whole space, i.e. Ω + /Ω ≈ 0. The intuition behind this feature is that uniform random sampling is very unlikely to give a valid sample. This is a characteristic of most applications of high-dimensional generative models. Nonetheless, the positive space is still generally believed to be very large and scales with the size of the space. We choose the ratio of approximately |Ω + |/|Ω| ≈ c!/c c as it loosely approaches an estimate given in [16] of the size of a family's sequence space. Since we want to keep the number of flat regions small (as explained in the previous section), we choose to model p by a stair distribution with s stairs, where the last stair is a assigned zero probability mass. Hence for a given s, we have

Baselines
Synthetic q: Even though we could scale to high Ω, for visualisation purposes, we set |Ω| = 6 6 and generate a smaller number of samples m = 1000. We define a stair distribution p with s = 4 flat regions. We produce 4 synthetic generative models q 1 , q 2 , q 3 , q 4 by increasingly perturbing the ground truth distribution: Generative models q: We evaluate our evaluation method on state-of-the-art generative models for categorical data. We set |Ω| = 6 6 and define a stair distribution p with s = 3 flat regions. CNF [17] is a normalizing flow method that learns a mapping from the categorical space to a continuous representation. CDM [18] is a diffusion-based model that operates in the discrete space. argmaxAR [19] is a normalizing flow method that uses an argmax operation to map a continuous representation to the discrete space. For each trial, we generate m = 10, 000 samples.

Experiment Details
We begin by validating our algorithm for choosing B * k . We verify the ordering of the empirical total variation given by emp ) of the synthetically created q 1 , q 2 , q 3 , q 4 aligns with the correct ranking: q 1 < q 2 < q 3 < q 4 . We compare the ordering provided by the empirical total variation derived form our binning algorithm B * k d T V (p B * k ,q B * k emp ) with the empirical total variation derived from some random binning B k d T V (p B k ,q B k emp ). To compare raking accuracy, we compute the Kendall Tau correlation coefficient which measures the piece-wise displacements between two rankings. A higher value corresponds to a more closely matched rank. Results can be viewed in Figure 2. Next, we test our evaluation procedure outlined in Algorithm 1 on state-ofthe-art categorical generative models. We validate that the generative model reaching the highest granularity level k with our test is the generative model with the lowest empirical total variation on Ω d T V (p,q emp ). We set the significance level of the hypothesis testing to δ = 0.05 and test for test = 0.1. We train each model on a dataset of 10, 000 training samples generated from p for 1000 epochs. For each baseline, a hyperparameter search is conducted over the hidden size =  Figure 2 shows the binning procedure we propose is sensible. In Figure 3, we show the empirical distribution generated from one trial of the generative models that were trained on the synthetic dataset as described in Section 3.3. Visually, we see that the CNF baseline distribution is a very poor approximation of the ground truth distribution. This is also reflected in its empirical total variation error d T V (p,q emp ). The argmaxAR and CDM baselines are closer, with the CDM slightly outperforming argmaxAR based on d T V (p,q emp ). This is reflected in our hypothesis testing ranking in Figure 4, where we see that all trials of the CDM pass the test at k = 4, whereas only a fraction of the argmaxAR trials pass the same test. Every CNF trial is rejected.

CONCLUSION
In conclusion, we have introduced an alternative way to evaluate generative models for categorical data. Even though our approach is based on statistical tests, it remains applicable for very large distribution space which is the setting of interest for those models. In future work, we plan on providing theoretical guarantee of our procedure and to further exploit our control over p to design an even more powerful test. pagebreak 6. COPYRIGHT FORMS © 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.


The WaveDAQ integrated Trigger and Data Acquisition System for the MEG II experiment

The WaveDAQ is a newly-designed digitization Trigger and Data AcQuisition system (TDAQ) allowing Multi-gigasample waveform recording on a large amount of channels (up to 16384) by using the DRS4 analog switched capacitor array as downconverting ASIC. A high bandwidth, programmable input stage has been coupled with a bias generator to allow SiPM operation without need of any other external apparatus. The trigger generation is tightly coupled within the system to limit the required depth of the analog memory, allowing faster digitization speeds. This system has been designed for the MEG experiment upgrade but also proved to be highly scalable and already found other applications.

I. INTRODUCTION
The MEG experiment [1] pioneered the use of multigigasample digitizer to achieve the stringent timing and charge resolutions needed to disentangle the high pileup environment the detectors face. In the framework of the global upgrade plan [2], that aims to a factor 10 higher sensitivity on µ + → e + γ (current limit was set by MEG to BR < 4.2 · 10 −13 at 90% CL), a global redesign of the trigger and data acquisition systems was needed. In particular the number of channels increased by a factor of 4 by switching from PMTs to SiPMs while the electronics had to fit in the same rack space. Built on the experience gained with the former Trigger [3] and DAQ [4] systems, the new WaveDAQ can exploit the features of DRS4 analog switched capacitor array to an unprecedented level, in particular the readout time will be decreased by moving from the VME standard to gigabit ethernet interfaces and and by merging the two former systems in a single, tightly integrated system to ease the interplay.

II. SYSTEM DESCRIPTION
While designing the new system no available standard delivered the required compactness, connection topology and clock distribution requirements. Therefore, a system with a fully custom backplane had to be designed. This system features a fully custom backplane with dual-star serial link capability and a skew-compensated low jitter clock distribution. In a standard 3U rack format, 16 slave boards are connected to the two central slots for trigger and data processing as shown in figure 1 where we also highlighted the various connections between the boards fully described in the next sections.
The crate housekeeping is accomplished by a microcontroller board integrated into the 360W crate power supply, rightmost in picture 1, that handles the shared power lines and the temperature-controlled fans while providing a low level interface to the boards in the crate for slow control and configuration though a dedicated Ethernet network connection.

A. WaveDREAM Frontend Board
Usually slave positions in a crate are occupied by the Waveform Drs4 REadout Module (WaveDREAM), pictured in figure 2. That board contains two DRS4 chips, capable of 0.5-5 GSPS sampling speeds, together with 900MHz bandwidth variable gain amplifiers to allow direct connection of detector signals. The same 80MSPS ADC used to digitize analog amplitudes stored in the DRS4 will provide also an independent sampling while the analog digitizer is running, to be used inside the trigger logic in combination with fast analog comparators. The information from the analog comparators is also fed to a time to digital conversion logic implemented in the readout FPGA by means of high speed shift registers to result in low resource usage while achieving 450ps time resolution, limited by the fastest available clock in the FPGA. A voltage bias generator may provide channel-by-channel biasing for single SiPM or for multi-SiPM arrays without requiring any external power supply. When inside the crate up to 256 channels on 16 boards can be digitized simultaneously.
The WaveDREAM can be used outside a crate using the onboard Gbit Ethernet interface. In this configuration a single board provides a benchtop DAQ platform with 16 acquisition channels.

B. Data Concentrator Board and Trigger Concentrator Board
The two central slots in a crate are reserved for custom designed boards that take care of crate-level functions mandatory for multi-board DAQ operation:  figure 3b, receives all trigger informations from the WaveDREAMs using low-latency serial links to generate a shared trigger signal when amplitude and time based algorithms detect an event of interest. All online selection strategies for MEG II will be based on the ones used in MEG [5] with the necessary modifications and improvements by the different detector segmentations.

C. Use in experiments
In experiments which require more than 256 channels, a shared trigger generation and distribution is necessary. trigger generation, a dedicated so-called trigger concentrator crate crate filled with TCBs in slave and master positions can collect data from TCBs sitting in up to 64 crates by using high speed serial cables on the front panel. The TCB in the master position of the trigger concentration crate can receive trigger informations from all boards in the system and eventually generate the trigger signal.
Another crate, using fanout cards, will account for the clock generation and the trigger signal distribution. Using such a design 16384 channels can fit in ten 21U racks, resulting in more than 4 times the channel density achieved in MEG.

III. PROTOTYPE OPERATION
Several tests with prototype systems were performed during the last two years, ranging from single board tests, for signal checks or small detector tests, to 6-crate multi-detector systems used during beam tests of the upgraded detectors. One of those systems is shown in figure 4. Even if smaller than the final MEG II system, lots of features such as board synchronization, busy handling and trigger communications have been studied and optimized in this setup before the final system production.
The two crate system of picture 4 showed very good timing characteristics when tested with the new MEG II Timing Counter detector [6], made by scintillating tiles readout by SIPMs: the electronics contribution have been measured to be of the order of 10 ps and have proved to be stable over a few month period. During the beam test period the Timing Counter detector has achieved its goal of about 35ps time resolution on positron tracks without being limited by digitizer performances (for details see [2]).
During the same test beam four crates have been devoted to readout a subset of the Liquid Xenon detectors [7], so that the full trigger reconstruction, involving pedestal-subtraction,  weighted sum and discrimination with veto, has been tested and proved to generate a trigger within 700ns, as visible from the recorded DRS4 waveform shown in figure 5. Using such logic we succeeded in selecting beam-induced photon events, cosmics, and other photon calibration sources. The latency will be improved by ∼ 200ns in the next WaveDREAM board revision by using an ADC with a shorter pipeline.
Outside the MEG experiment, a single crate system has been chosen to readout the dE/TOF Detector of the FOOT Experiment [8], few prototypes have been tested with single-board

IV. CONCLUSION
We showed a new digitizing Trigger and Data Acquisition system being assembled for the MEG II experiment. The system allows the use of several DRS4 digitizers on a large number of channels and is easy to scale from a 16 channel single board setup to ∼ 16000 channels. Several configurations involving smaller size systems have been tested and all underlying functionalities have been proved to be operational.


Implementation and integration of image processing blocks in a real-time bottle classification system

A practical solution to the problems caused by the water, air, and soil pollution produced by the large volumes of waste is recycling. Plastic and glass bottle recycling is a practical solution but sometimes unfeasible in underdeveloped countries. In this paper, we propose a high-performance real-time hardware architecture for bottle classification, that process input image bottles to generate a bottle color as output. The proposed architecture was implemented on a Spartan-6 Field Programmable Gate Array, using a Hardware Description Language. The proposed system was tested for several input resolutions up to 1080 p, but it is flexible enough to support input video resolutions up to 8 K. There is no evidence of a high-performance bottle classification system in the state-of-the-art. The main contribution of this paper is the implementation and integration of a set of dedicated image processing blocks in a high-performance real-time bottle classification system. These hardware modules were integrated into a compact and tunable architecture, and was tested in a simulated environment. Concerning the image processing algorithm implemented in the FPGA, the maximum processing rate is 60 frames per second. In practice, the maximum number of bottles that can be processed would be limited by the mechanical aspects of the bottle transportation system.

There are many problems caused by water, air, and soil pollution, mainly produced by the large volumes of waste that receive inappropriate treatment. Recycling is a practical solution but sometimes unfeasible in underdeveloped countries, due to the lack of technical knowledge or economic resources required to carry out this task 1 . In recent years, plastic and glass bottles waste recycling is a critical issue, even when recycling is a relatively simple process. A typical bottle recycling process begins with cleaning and removal of contaminants. Next, it is required a manual separation by color. In the recycling field, a manual classification implies many security and health risks for the people performing the waste separation 2 .
Computer vision systems have three levels: the lower level includes the image capture and simple pixel-based functions such as arithmetical operations between images; the intermediate level includes more complex functions such as segmentation, matching, preprocessing, convolution, or motion estimation; the upper level typically is applied to recognize, classify or capture scene interpretation. Currently, there are a lot of FPGA-based computer vision systems that mainly employ parallel computing to increase the processing speed in these computationally intensive applications 3 . There are several implementations of color waste separation systems, but most of them have not been tested in a real environment with high accuracy and performance. A dedicated hardware solution has not being explored for solving this specific problem.
Commercial automated color sorting systems are expensive because the companies sell the vision system, the conveyor belts, and mechanical actuators in a single package. Usually, an automated system requires an industrial computer or a processing unit to classify bottles in one single line, because of the real-time limitations of sensors (cameras) and actuators to perform the object separation. The aforementioned implies more space and high power consumption, so the performance of the computer running the classification systems is not constant because of the lack of control in the number of concurrent processes. Although modern high-performance computer systems, including GPU devices, can be used to accurately classify glass or plastic bottles, these devices are not commonly used in recycling plants because both GPU and host computer require a lot of power.

Related work
Many waste separator systems found in the literature are mainly focused on the mechanics of their systems. Other works are focused on the design of machine learning or computer vision systems. In this paper, those works based on the mechanical design are not reviewed.
An early bottle classification system did not use color information, but only the shape of each bottle using the height information using a laser range finder 4 . . They also developed an algorithm to detect stickers, which provides additional information to a classification system. Their approach was successfully applied when bottles have the same size, and slightly different shape. Other work proposes a mechanical system for separating cans, glass, and plastic bottles, aided by a computer vision system that sorts bottles by color 5 . The system classifies the cans into steel and aluminum and the plastic bottles by color and material. The authors do not provide details about the image processing algorithm.
Alternative approaches are separation systems consisting of magnet separation, particle size classification, vibration wind classification, bottle color separators, and plastic bottle separators 6 . The reported work focuses on the description of the separation of bottles and plastic. The authors reported a reflex-type discriminating system to handle non-opaque bottles frequently used for non-beverage products. A machine vision-based automated sorting was proposed 7 . They propose an image preprocessing stage, followed by feature extraction, bounding box computation, segmentation, and linear discriminant analysis (LDA). A dataset with 300 plastic bottle images is utilized, divided into two groups (PET and Non-PET).
The combination of near-infrared spectroscopy and color images in separated classifiers was done 8 . The first classification stage is the plastic-type classification using Near-infrared spectroscopy, while the second stage is color classification using machine vision techniques fed by a CCD camera. The plastic bottle type uses the power of a NIR signal, and a fusion of both quadratic discriminant function-based classifier and decision tree classifier to achieve the color recognition of the plastic bottles. The design and integration of the mechanical elements for automated sorting were addressed, but information about its physical testing with real-world images is missing 9 . Systems dedicated to identifying and extracting plastic bottles out of a conveyor belt using machine vision were explored 10 . The recognition system was tested on a set of 50 different bottles, obtaining an accuracy of about 97% on bottle identification, but the authors do not mention aspects related to the execution time.
Classifying recycled polycoat and PET materials was addressed by implementing a system based on the processing of gray images 11 . Image histograms are combined with an SVM classifier to segregate the input images. The authors report a high accuracy in the classification task, but, the complexity of the proposed classifiers makes their system unsuitable for real-time classification tasks. A system for sorting plastic and paper waste was proposed 12 . The proposed system processes high-resolution images later resized to a smaller resolution for its management. The system performs simple thresholding to separate objects from the background and a Feed-Forward (FF) Neural Network classifier to separate the waste. The thermoplastic-based recycling technique was explored 13 . The proposed system utilizes inductive, computer vision in the visible spectrum, and a NIR hyperspectral sensor to acquire the images required by a system that classifies thermoplastic using Artificial Neural Networks and PCA techniques. An Intelligent Waste Separator (IWS) to sort inorganic waste like plastic bottles, aluminum cans, plastic cutlery, and other kinds of materials was proposed 14 . The system classifies the target based on the first two Hu's Invariant Moments (HIM) in conjunction with the k-Nearest Neighbor (k-NN) algorithm using euclidean distance. A system to classify a given plastic bottle image as PET or non-PET type was proposed 15 . Five feature extraction methods were implemented, including Principal Component Analysis (PCA), Kernel PCA (KPCA), Fisher's Linear Discriminant Analysis (FLDA), Singular Value Decomposition (SVD), and Laplacian Eigenmaps (LEMAP). A Support Vector Machine (SVM) classifier performs the classification and a majority voting technique performs the final decision mechanism. The exploration of a Convolutional Neural Network (CNN) architecture named RecycleNet for classification of selected recyclable object classes was done 16 . The proposed approach reduces the parameters required in conventional CNNs architectures, but its drawback is the amount of data required for training, even with the optimized version proposed by the authors.
Many related works focus on the classification of multiple types of materials, requiring complex classifiers to achieve this task. On the other hand, few works focus their efforts on classifying only bottles (plastic or glass). Most of these works process low-resolution images. About the learning techniques, most works use complex learning techniques, whose main drawback is parameter tuning to reach high accuracies. One common choice is techniques based on deep learning which requires training using a large image dataset. Other works proposed systems that require small image datasets for training, but the accuracy is low. Most works perform offline processing, which generates higher accuracies, but information about the processing speed. In this work, we propose a compact and tunable solution based on reconfigurable hardware, as an alternative to microcomputers or PC based systems, that avoids the performance issues and high power consumption of the latter. The proposed system does not require a training stage, since we designed a hardware architecture with minimal resources to perform the high-performance bottle sorting. The classifier is very simple since it is based on a default threshold set or new thresholds that a system administrator inputs using a remote interface. The previous preprocessing stage to analyze the input image and isolate the bottle pixels is implemented on dedicated hardware to guarantee real-time performance. The classifier is the last step in the processes pipeline. The proposed system analyzes the bottle image, and the classifier obtains the bottle color based on the predominant color in the bottle pixels using the provided image thresholds. The rotation or flipping of input bottle images does not affect the processing, www.nature.com/scientificreports/ analysis, or classification stages. Augmentation is not required since there is not a formal training phase. Data diversity is desirable but not necessary for the proposed system. The system uses a controlled illumination, so the default or user-defined thresholds do not change too much and, the systems perform the bottle classification task with acceptable accuracy levels.

Materials and methods
Motivation of using FPGAs. The main advantage of using an FPGA is that the system guarantees a realtime processing of each frame of the input, while other systems implemented in Single Board Computers (SBC) or microcomputers, can not guarantee this performance. The FPGA development kit used in this work has a daughter board that acquires video from the camera, while the FPGA performs the decoding and processing without requiring external peripherals. We choose an FPGA for the proposed system because it allows us to implement custom hardware blocks for the image processing operators required in this project. The small disadvantage is that FPGAs are harder to program, compared to microcontrollers or microcomputers, since the programmer requires domain of digital hardware and microprocessor design concepts not required in high level languages. Related to power consumption, it is true that embedded computers (such as microcontrollers or SBC) consume less power compared to FPGA devices, however they do not provide the performance of dedicated hardware elements offered by FPGA devices. In the literature, a performance increase is always reported when using FPGAs for the implementation of image or video processing, compared to equivalent systems implemented in embedded computers. In the other hand, it is possible to use a PC with a powerful GPU to boost the performance of a system, but the power consumption will considerably increase, and the size of these systems is bigger and unsuitable for embedded applications.
Hardware and software components. The validation of the proposed bottle color classification system was carried out on a Spartan-6 Industrial Video Processing Kit (S6IVPK), which hosts a Spartan-6 LX150T FPGA device. The S6IVPK is a targeted design platform. It includes two daughter boards based on the industrystandard FPGA Mezzanine Card (FCM) specification. The first one is the FMC-DVI, which allows the video processing generated by any video or still camera with HDMI output, and displays the resulting video in any video monitor with a DVI or HDMI input port. The second board is the FMC-IMAGEOV, which allows the video processing generated by an Omnivision OV7715 image sensor, and displays the resulting video in any video monitor with a DVI or HDMI input port. As a capture device, a high-resolution digital camcorder connected to the FMC-DVI card was used. The HDMI output resolution was set to an image format of 1920 × 1080 pixels at 60 frames per second, also known as 1080 p. An LCD monitor was connected to the FMC-DVI output port. From the S6IVPK, the RS-232 port with a DB9 connector receives the signal from the presence detector. The other RS-232 port was connected, through a USB converter bridge, to a computer to receive the configurable parameter using a 9600 bps serial protocol, and a data width of 8 bits. On the side of the host computer, a Python script sends the data with the proper format and configuration. The camera captures the bottle images from a stage with controlled illumination and white background (simulating a chamber), where several types of bottles were placed to determine their color. In the preliminary tests, the bottles were placed manually in front of the camera, but currently a fruit grading conveyor is being modified to accept bottles and install the proposed classification system.
A Laptop PC was used to configure, design, implement and debug the hardware blocks of the FPGA of the system. This Laptop requires the Xilinx ISE design suite installed. A Python script was programmed to send the configuration parameters to the FPGA device and to retrieve the output image processed by the FPGA, for debugging purposes.

Required computer vision operations.
For the implementation of the proposed bottle classification system, the following image processing operations were implemented.
• Morphological processing. A morphological process extracts the shape or structure of the objects in an image.
• Spatial filtering. The main objective of image enhancement is to process an image so, the result is more convenient than the original image for a specific application. • Color space conversion. A color space is a method used to specify, create and visualize color. Brightness, tone, and color intensity features define a color. Usually, a color is specified using three coordinates or parameters. These parameters describe the location of the color in the chosen color space. he HSL color space represents a wealth of similar color spaces, whose alternative names include HSI (intensity), HSV (value), HCI (chroma/ colorfulness), HVC, TSD (hue, saturation, and darkness), etc. Most of these color spaces are linear transforms from RGB and are therefore device-dependent and nonlinear. Their advantage lies in the extremely intuitive manner of specifying color.
Proposed hardware blocks. Following the general schema of a typical computer vision system, a structure composed of several concurrent blocks working simultaneously was adopted to take advantage of the benefits offered by a custom hardware-implemented system. The architecture contains processing modules organized into groups depending on their function. Figure 1 shows the block diagram of the complete architecture.
The capture block is the main input interface, where the video signal is received. This module captures a video stream from an HDMI source and configures a predefined capture module using the I2C protocol. This design was adapted from 17 , using a provided reference design by the target board manufacturer and does not alter the video data, but only makes a passthrough function between the input and output HDMI ports. It provides a bus that carries the data signal in a 24-bit RGB format and the synchronization signals obtained by the camcorder. The processing block performs all the digital image processing tasks. The processing block consists of modules that perform image processing tasks. The capture device generates the image without performing any modifications. This stage aims to process the image to facilitate further analysis. The suitable operators for the desired tasks were selected based on off-line tests. Figure 2 shows the block diagram of the image processing stage.
The communication block is an interface that receives data from a computer to configure parameters in the processing block and receives the signal from an external presence detector. The analysis block decides the membership group of the bottles being captured based on the data generated by the processing block. Finally, the display block generates the video signals displayed on an external monitor. In the final installation of the proposed bottle classification system both, system configuration and debug visualizer components, can be removed from the system.
Three main hardware blocks work in parallel in the processing stage. The first one receives the original image data and perform a noise reduction operation by using the intensity slice technique for each color channel.
The next module performs a color space conversion from the RGB to HSL color space. The module works only with the Hue channel, in order to process less information.
Another noise reduction filter used was the median filter, which uses a convolution scheme. To simplify the circuit, a modified version of the noise reduction filter is used. The original algorithm sorts all the pixels within the processing window in a decremental or incremental way, and then, the median is selected. The proposed method groups the pixels within the window into smaller groups, and each subgroup passes through comparisons blocks to obtain the median from each group. The resulting medians feed another comparison block that gives the median value as the output for this process.
The morphological filters were designed in order to be flexible concerning the data width, so the filter adaption to binary or grayscale images is straightforward. The dilation and erosion filters work similarly to convolution, using a processing window. In the proposed median filter implementation, the dilation uses a comparison block that receives all the inputs from the processing mask. The comparison returns the maximum value as the dilation output. The erosion block returns the minimum value, having the same organization as the dilation block.
To prepare a mask for segmentation, the first step in this processing branch is the conversion from RGB components to the luminance component of the HSL color space.
This conversion generates a grayscale image. The dedicated processing module receives the 24-bit data signal from the RGB channels, 8-bit each. A control block obtains the maximum and minimum values and performs a right shift to finally add the values and generate an 8-bit result for the luminance channel representation.
This module uses the corrected image to generate a binary mask to ignore all those pixels out of the region of interest. After obtaining the last grayscale image, the module segments this image using a constant thresholding www.nature.com/scientificreports/ level. The mask image determines object regions using a 1-value for those pixels that belong to the object and a 0-value otherwise. This module also applies the resulting mask to the last image from the first processing step. The third stage of the processing module receives the synchronization signals from the external capture device. Two binary counters (column and row counters) use the horizontal and vertical synchronization pulses as clock signals. These counters compute the display coordinates of the current pixel. In this block, the video data is not affected. The information about columns and rows limits the object area in the image mask.
An image window performs filtering operations. In the proposed implementation, a shift register that stores four rows of the input image to have full access to the first five rows of the input image is used. The latter is required to keep the input image in external memory, so the length of the registers depends on the target resolution. Figure 3 shows the architecture of the proposed shift register. The output of this shift register feeds the mean filtering block in the processing block.
A communication block to establish communication between the FPGA board and an external device was designed. This block is composed of two functions. The first one provides a source signal to a presence detector and receives the response signal indicating if there is a bottle or not. The second one establishes serial communication with a computer using the RS-232 protocol to receive parameters information. To interface the  www.nature.com/scientificreports/ proposed architecture with an external bottle detection circuit, one input/output port available in the board to connect the FPGA is used. This circuit was built using an infrared sensor with a phototransistor and an IR LED. The sensor delivers a logic signal when an object obstructs the transmitter-receiver vision line. Internally, this presence signal is used in the analysis stage to determine when a bottle is present. The USB-UART bridge available on the FPGA development kit was used to implement an RS-232 protocol with a finite state machine (FSM). It receives 8-bit data to configure the threshold value as a variable parameter. The FSM has nine states, one is used for the idle state, including the start and stops bits and saves the needed number of states. The other eight states are used to store each bit of the transmitted data. When the FSM reaches the idle state, the module sends the stored byte to the processing block to configure the corresponding parameter. The FSM works under its clock domain at a speed of 9.6 kHz for a data transmission rate of 9600 bps. The FPGA generates this clock from the FPGA clock signal that oscillates at 100 MHz. Figure 4 shows a block diagram including the presence sensor and the serial communication block. This analysis block receives the processed image to compute the classification of the object depending on its predominant color. Input data is analyzed to establish the color of each pixel. Later, this module generates a histogram to compare occurrences of each intensity level considered. When a bottle is detected, and once classified by color, a counter will increase its value. The counters keep a record of the total quantity of bottles of each color group. Figure 5 shows the block diagram for the analysis module. The processed image is compared in the tone range selector to assign a color group based on the input pixels. The four possible groups are: brown, green, blue, and transparent. Before the implementation of the proposed architecture, we determine the hue range for each color. This block uses this range to classify each pixel color. When the module cannot compute the predominant  www.nature.com/scientificreports/ color, the transparent color is assigned. The histogram generator block reads each 4-bit register that stores the color counters to determine the final classification. The histogram generator uses the signal generated by the presence detector to obtain the current pixel color. The module obtained the predominant color group once the module analyzed the current frame. One 4-bit register stores the bottle color classification, with a single bit of this register corresponding to each group to be classified. The next block uses the final classification register to count the number of bottles of each group. The bottle counter block has a binary counter with a programmable delay based on the bottle speed. This delay can be adjusted in execution time depending on the hardware capabilities of the conveyor band attached to the vision system.
The display module receives data from the processing block, the classification variable, synchronization signals, and it has a connection with an external DIP switch. This block performs a final mask adjustment and generates the data signals for on-screen information display. Figure 6 shows the block diagram for the display module.
The final mask adjustment receives the binary image and gives output data according to the color of the classification made for the previous frame. Internally, this is done through a multiplexer with constant inputs representing the classification colors in a 24-bit RGB format for each group. The classification register controls the output selector, and it is enabled when the signal from the mask has a value of 1.
The display module information block generates a graphical representation of the information obtained in the previous processes. It selects the color data sent to the output as a video signal. A set of ROM blocks (ROM32X1 elements) were instantiated with the required values to display the digits for counting the bottles. The system uses an array of 32 × 16 bits to show digital information, where a 0-value represents background pixels and a 1-value the foreground. The current bottle counter reads data from eight ROM instances (ROM32X1) that contain the 32 × 8 pixels icon. The color of the icon is selected depending on the classification of the bottle in the capture area. The system displays this icon in the same row as the corresponding bottle counter to identify the quantity of bottles of each group.

Results and discussion
When the target FPGA uses the default switch configuration, the displayed image shows the final classification result resulting from the processing and analysis tasks. The image contains a set of graphical elements to show the total quantity of processed bottles, as well as, the quantity by groups, including an indicator icon for each group and the current classification of the bottle being processed. The biggest image area displays the last color classification after the processing. Figure 7 shows the default image, and the results generated by all the previous modules. We considered four different bottle colors for testing because these colors were available. The proposed system is configurable to sort several bottle colors by using a software application that connects to the FPGA board using a serial connection. The system's administrator loads an image set that contains the bottle color to be added, and the software solution analyses the image dataset to estimate the image thresholds. Finally, these thresholds are transferred to the FPGA board. For testing purposes, we tested with four different bottle colors.
The final report of the FPGA hardware design yields a low consumption of slice registers. The required LUTs, used mainly for logic and memory purposes, represent only 4% of the total available. The occupied slices represent an utilization of less than 7% of the total number of available slices. The IOBs are resources for input and output signals, mainly used in the capture module to connect to the input camera and the output monitor and to interface the communication module with the serial ports. The RAM16BWER is a memory resource used only for the capture module. The DSP48A1s are resources with adders and multipliers on its internal structure; two of these resources are used in the final implementation to perform the multiplication operations required by the color space conversion block.
Final experimentation test were made on the video resolutions shown in Table 1. For each resolution, the time to complete the bottle classification was estimated based on the pixel frequency. Even when the processing www.nature.com/scientificreports/ time is short, the performance of the system is limited by the video frame rate, which for all the tested resolutions, was around 16.7 ms. For comparison purposes, an equivalent processing pipeline was programmed in a PC, using the C++ language and the OpenCV library. When using a 480 p resolution, a 188 ms execution time was obtained, that translates in a processing rate of 5.319 frames per second. In the FPGA implementation, if a higher resolution input video is used, the processing speed of the whole frame remains constant. In opposition, in the software implementation, the processing time will proportionally increase with the input frame resolution. In the FPGA implementation, if a higher resolution input video is used, the processing speed of the whole frame remains constant. In opposition, in the software implementation, the processing time will proportionally increase with the input frame resolution. For each implemented video resolution, we estimate the used logic resources, which are summarized in Table 2.
Comparison with related work. The main contribution of this paper is the implementation of a high performance image processing system for bottle classification. The image processing techniques presented in this article were chosen so they could be implemented in hardware modules and achieve real-time performance. Additionally, the proposed system does not require a training stage and the "model" is stored as a set of threshold values instead of a complex representation that cannot be updated by the final user. Moreover, it does not require to reduce image resolution before the image processing stage. These hardware modules were integrated into a compact architecture and tested in a simulated environment. The architecture allows the user to choose the bottle colors to be classified using a PC application that communicates with the FPGA through a serial port.
The system was tested in a simulated scenario that emulates bottles on a conveyor. To keep the hardware resources for the implementation of the proposed classification system as low as possible, a scheme to keep a low number of steps for the selected classification was adopted. Complex classification techniques based on supervised algorithms have been discarded because of the added complexity to the system  www.nature.com/scientificreports/ in detriment of the performance. In the proposed approach, the image preprocessing tasks to enhance the input images were simplified to reduce the final hardware requirements.
To compare the proposed work with existing systems, we have summarized in Table 3 the remarkable points. Some works use complex learning techniques, such as NN 7,12,16,18 , LDA 9 , Decision Tree classifiers 8 , SVM 11,15 , KNN 14 and SOM 10 , applied in different domains. The main problem with this techniques is the tuning of the parameters to reach useful accuracies. The image processing techniques used in this work were chosen so they could be tunable and reliably programmed in hardware, without sacrificing the overall performance. Some works use deep learning approaches (DL) 16,19 , which must be trained with a great number of images. Although, multiple resources are available on the internet, a customized DL solution needs the labeling of hundreds or perhaps thousands of images, which involves time and resources that are not available at the time of the system development. Moreover, the power requirements of these systems are high. On the other hand, the proposed approach is based on the selection of color thresholds that can be selected by the final user and does not require a training stage. Additionally, the power requirements are low, thanks to the use of an FPGA as processing unit. Some works proposed a minimal system using few training images 4,7,10,11,14,15,18 , but the resulting classifier accuracy is low. Some related systems do not provide information about the used classifiers or the images used to train those classifiers 5,8,12,20 . The proposed system does not require a training stage. It was tested in controlled conditions with bottles of four different colors and, in all cases the classification results were correct. Some works process images offline 4,7,[9][10][11][12]15,16,18 , while the proposed work process video in real-time. This offline processing gives the proposed system an advantage since they report higher accuracies, but information about the processing speed does not guarantees a real-time performance with their current implementation. Some related works process video at small resolutions 5,6,20 , however they do not provide information about the video format or the type of interpolation applied. The proposed approach processes video in its native resolution, so interpolation techniques are not needed. Some of the related works process still images at low resolutions 7,12,15,16,18 . Furthermore, they trained their classifiers with these low-resolution images. They probably do not test their implementation at higher resolutions because the complexity of the required operations does not allow them to reach real-time performance. Nevertheless, our approach is able to process video at 60 fps at the full camera resolution. The proposed architecture can be reconfigured to separate several types of bottles based on the requirements of the waste separation authority, by only tuning some parameters, avoiding the need to retrain the whole system. The proposed system is based on a FPGA. FPGAs are useful in several domains that require the high-performance image processing and low power consumption. Related works found in the literature do not use FPGAs. We suppose that this is because the time and effort required to learn to program FPGAS are longer, compared to programming PCs or microcontrollers.
Due to the image processing operators, the proposed system is able to classify only non-deformable containers, such as rigid cans, or plastic and glass bottles, and it would not be possible to classify plastic bags, organic waste or compacted materials. www.nature.com/scientificreports/ The proposed system is not able to process unsorted bottle groups or overlapped bottles. It can only process images of individual bottles. Hence the need to use a transport density in the conveyor of 25% to ensure the processing of one bottle per image.
The proposed system is more expensive than SBC and microcontroller based systems, but it is still affordable compared to other systems requiring PC with or without GPU, which are also more power demanding and bulkier.

Conclusion and future work
A hardware architecture for the classification of bottle images for a recycling line was developed. The architecture contains several processing modules, which can be used as individual blocks or black boxes to perform specific tasks and be included in other designs.
The image processing tasks implemented on an FPGA are fast enough to be part of a real-time processing system. This hardware-based processing saves time because the storage of the complete image is not necessary. It also saves memory resources because the architecture only requires the storage of data needed for the window processing tasks, in this case, four lines and five pixels from the image. Compared to state-of-the art implementations on PC, the variations in the results produced by algorithm modifications for their implementation in FPGAs are minimal.
The hardware architecture designed is an efficient solution for object classification by color, and presents a high performance and enough features to be integrated into an industrial image processing system, not only for color sorting. The classification parameters can be easily adjusted using a laptop computer, and modifications to the target recognition colors for recognizing several types of targets are straightforward.
The proposed hardware architecture was synthesized for several standard video resolutions to give the final user flexibility about the image sensors that could be used in the implementation of the system. The target architecture was tested for several video resolutions, but the architecture adaptation to process higher resolutions such as 4 K or 8 K is straightforward when this technology will be available to be included in some system.
As future work, the communication block functionality to configure several parameters could be modified to be able to transfer information from the FPGA about the current values for the different parameters and data resulting from the analysis tasks. Another improvement is to explore the FPGA internal clock to perform intermediate operations faster because the image processing module works under the video clock domain.
Additionally, from the state-of-the-art related work, we are going to explore the adaptation of the proposed system to a machine similar to that reported in 6 , where bottles travel lying down, since we have access to a fruit grading machinery that would require only sightly modifications to the conveyor to be able to transport bottles.


1-Perfect Codes Over the Quad-Cube

A vertex subset <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> of a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> constitutes a 1-perfect code if the one-balls centered at the nodes in <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> effect a vertex partition of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. This paper considers the quad-cube <inline-formula> <tex-math notation="LaTeX">$CQ_{m}$ </tex-math></inline-formula> that is a connected <inline-formula> <tex-math notation="LaTeX">$(m+2)$ </tex-math></inline-formula>-regular spanning subgraph of the hypercube <inline-formula> <tex-math notation="LaTeX">$Q_{4m+2}$ </tex-math></inline-formula>, and shows that <inline-formula> <tex-math notation="LaTeX">$CQ_{m}$ </tex-math></inline-formula> admits a vertex partition into 1-perfect codes iff <inline-formula> <tex-math notation="LaTeX">$m=2^{k}-3$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$k\ge 2$ </tex-math></inline-formula>. The scheme for that purpose makes use of a procedure by Jha and Slutzki that constructs Hamming codes using a Latin square. The result closely parallels the existence of a 1-perfect code over the dual-cube, which is another derivative of the hypercube.

I. INTRODUCTION
A 1-PERFECT code has the capability to correct a single error, and detect two or fewer errors. Applications abound in areas such as communication systems, network systems, multiprocessor systems, and computer architecture in the wide digital world. Not surprisingly, the topic commands a rich literature [10]. Among various codes, the 1-perfect Hamming codes and 3-perfect Golay codes based on the topology of the hypercube, are the foremost [10], [15].
A quad-cube (formally defined below) is a special version of a more general network topology called the metacube, devised by Li et al. [19], that itself is derivable from the hypercube. The basic idea is to mitigate the problem of the rapid increase in the degree of the hypercube when the node size exceeds several million. It retains most good characteristics of the hypercube, notably, efficient collective communication, high connectivity, fault tolerance, low diameter, and easy routing [19]. This paper adds another significant property to that list, viz., a vertex partition of the graph into 1-perfect codes.
In an analogous study, the author [14] earlier presented a perfect code over the dual-cube that is another (relatively simpler) version of the metacube.
Motivation: Assuming that there is a maximum of one error, any possible word in a message transmission can, in a unique way, be corrected to one of the words in a 1-perfect code. Optimal resource placement in an interconnection network is another area of application. In particular, elements of a 1-perfect code may be viewed as nodes that Manuscript  house (expensive) resources such as power sources, function libraries and algorithmic information, whereas other nodes are users of the resources. Since every user node is adjacent to a unique resource node, optimality is achieved in the number of resource nodes. A closely related concept is that of domination. Indeed, a 1-perfect code corresponds to a smallest (independent) dominating set in the graph in an obvious way. Other applications include construction of an efficient backbone for routing and partition of a network into small clusters.

A. Related Studies
Apart from the study of perfect codes on hypercube-like networks, there have been a number of such studies in other settings, too. For example, Biggs [2] presented codes on the topology of general graphs, and Kratochvil [17], [18] later followed with several useful results. The stimulus comes from applications of the idea in engineering, computer science and the related disciplines.
Products of graphs [6] are natural candidates where to seek perfect codes. Not surprisingly, they command a rich literature. In particular, the famous r-perfect Lee metric codes by Golomb and Welch [7] are over the Cartesian product of finitely many cycles. For later studies in this area, see Špacapan [22] and Mollard [21]. For r-perfect codes over the Kronecker product (also known as direct product and tensor product) of finitely many cycles, the author [11]- [13] presented several results that eventually led to a complete characterization by Žerovnik [25]. For analogous studies over the strong product and the lexicographic product, see Abay-Asmerom et al. [1] and Taylor [23], respectively.

B. Definitions and Preliminaries
A graph connotes a finite, simple, undirected and connected graph. Let G be a graph, and let dist(u, v) denote the (shortest) distance between vertices u and v in G [24]. Further, let dia(G) denote the diameter of G, i.e., the largest of the distances between any two nodes in G.
For a vertex subset S of a graph G, let S denote its closed neighborhood, i.e., S ∪ {x ∈ V (G) | x is adjacent to some vertex in S}. S is said to constitute a dominating set of G if S = V (G). If, in addition, the distance between any two distinct elements of S is at least three, then S constitutes a 1-perfect code. Thus the closed neighborhoods of the vertices This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ in a 1-perfect code are mutually exclusive and collectively exhaustive.
The problem of obtaining a smallest dominating set is NP-complete, and so is the problem of deciding whether or not a graph admits a 1-perfect code [18]. For any undefined term, see West [24].
For n-bit binary strings x and y, let Ham(x, y) denote the Hamming distance between the two, i.e., the number of bit positions in which they differ from each other. The n-dimensional hypercube Q n (also called the n-cube) is the graph on the vertex set {0, 1} n , where nodes x and y are adjacent iff Ham(x, y) = 1.
Let x · y (or xy) denote the concatenation of the binary strings x and y, and for sets X and Y of binary strings, let X • Y := {xy | x ∈ X and y ∈ Y }. Meanwhile let a := 1 − a, where a ∈ {0, 1}. Definition 1.1: For an n-bit binary string x = b n−1 . . . b 0 (so 0 ≤ x ≤ 2 n − 1 in decimal), let x (a) be the n-bit integer obtainable from x by replacing b a by b a , where 0 ≤ a ≤ n−1.
It is clear that x (0) , . . . , x (n−1) are precisely the neighbors of x in Q n . See Table I for an illustration, where n = 3, and x, x (0) , x (1) , and x (2) are in decimal. Definition 1.2: For n-bit binary strings x and y, let x y denote the n-bit string obtainable by the bitwise XOR operation between x and y. Further, for integers r and s, where 0 ≤ r, s ≤ 2 n − 1, let r s denote the integer N (b(r) b(s)), where b(r) and b(s) are n-bit strings that represent r and s, respectively.
Note: A precise definition of N (x) appears below, x being a binary string. Proposition 1.1 (Gale [5]): 1) is commutative as well as associative.
Remark: The XOR operation between two bits is viewable as an addition modulo two. Proposition 1.2: Let x and y be n-bit binary strings, and let 0 ≤ a, b ≤ n − 1. Then Proposition 1.3: Let X and Y be sets of n-bit strings of equal cardinality. Then 1) X (a) = Y iff Y (a) = X, and 2) If X (a) = Y , then there exists a "perfect" matching between X and Y , given by x ↔ x (a) . Definition 1.4: For m ≥ 1, the quad-cube CQ m is a spanning subgraph of the hypercube Q 4m+2 . Its edge set is given by The nodes of CQ m are distinguishable into four types, as follows: • Type 0: those that are of the form u00 (binary) or 4i + 0 (decimal) • Type 1: those that are of the form u01 (binary) or 4i + 1 (decimal) • Type 2: those that are of the form u10 (binary) or 4i + 2 (decimal), and • Type 3: those that are of the form u11 (binary) or 4i + 3 (decimal). Let e ∈ E(CQ m ). Call e an edge of Type i if e ∈ E i , 0 ≤ i ≤ 3, and call e a cross edge if e ∈ E 4 . See Figure 1 for a depiction of the five edge types. Meanwhile, a node of the hypercube/quad-cube is viewable both as a binary string, say, x and as the corresponding nonnegative integer N (x). A formula for the latter appears below.
Proof: CQ m is a regular graph of degree m + 2, so the closed neighborhood of each vertex in it consists of m+3 vertices. In that light, the existence of a 1-perfect code requires that m + 3 divide |V (CQ m )| = 2 2m+1 , i.e., m + 3 must be a power of two. Hence the result.
The central objective of this paper is to prove that the converse of Corollary 1.5 holds true. For the special case of CQ 1 , see Figure 2, where nodes that are circled constitute a 1-perfect code of the graph. It is further clear from the depiction that this graph admits a vertex partition into such codes.  Proposition 1.6 ( [19]): CQ m admits a vertex partition into a total of 2 3m+2 m-cubes, segregated into four kinds as follows.
• Collection 0 (based on the nodes of Type 0) in which the i-th cube is on the vertex set • Collection 1 (based on the nodes of Type 1) in which the i-th cube is on the vertex set {2 2m+2 q + 4r • Collection 2 (based on the nodes of Type 2) in which the i-th cube is on the vertex set {2 3m+2 q + 4r , and r = i mod 2 2m . • Collection 3 (based on the nodes of Type 3) in which the i-th cube is on the vertex set {4i Figure 3 for a set of certain 5-cubes in CQ 5 . Definition 1.6: For an integer i and a set S of integers, let

C. A Special Latin Square
An r × r Latin square is a matrix, in which each of 0, . . . , r − 1 appears exactly once in each row and each column. Let r be a power of two. For a permutation 0 1 . . . r − 1 p 0 p 1 . . . p r−1 , let L(p 0 , . . . , p r−1 ) be the Latin square, defined below.
See Table II for M 4 and M 8 .

D. A Permutation Function π
Definition 1.8: Let r be a power of two, r ≥ 4, and let Here is how the π 2r -array is obtainable from the π r -array: • Copy the elements in the leftmost r/2 cells of the π r -array to the leftmost cells (indexed 0 to (r/2) − 1) of the π 2r -array • Copy the elements in the rightmost r/2 cells of the π r -array to the rightmost cells (indexed 3r/2 to 2r − 1) of the π 2r -array, and • Add r to each element of the π r -array, and systematically copy the resulting elements to the cells in the "middle" segment (indexed r/2 to (3r/2) − 1) of the π 2r -array. Let P r = L(π r ). See Figure 4 for the recursive structure of P 2r vis-à-vis P r . Further, π 4 , π 8 and π 16 appear in Equation (1), shown at the bottom of the page, whereas P 4 and P 8 appear in Table III.
Lemma 1.8: The i-th element and the (r − 1 − i)-th element of the π r -array differ in exactly the rightmost bit, i.e., (π r (i) Proof: Use induction on r. For r = 4, the claim follows by an inspection of π 4 . For the induction step, recall the construction of the π 2r -array from the π r -array that follows Definition 1.8, and make use of the fact that (r + π r (i)) (0) = r + (π r (i)) (0) , since r = 2 k , k ≥ 2.
Observe next that the way P r is obtainable from π r is identical to the way M r is obtainable from the identity permutation, hence the following result.
For the second identity, use induction on r to show that P r [i, r−2] = (π r (i)) (1) . To that end, first check to see that the following hold with respect to P 4 (that appears in Table III (1) . Consider P r , whose structure appears in Figure 4(a), and notice that each of L and L is an (r/2)× (r/2) matrix, where r is a power of two. The following properties are immediate: Examine P 2r next, whose structure appears in Figure 4(b). (1) (1) . Accordingly, P 2r [i, 2r − 2] = j (1) . (1) . It follows that P 2r [i, 2r−2] = r+x (1) = (r+x) (1) .
The rest of the argument is similar to that in (2) above.
. The rest of the argument is similar to that in (1) above.

E. A Distinguishing Function φ
Let k ≥ 3 and m = 2 k − 3. Definition 1.9: Let p 0 = 0, and let p 1 , . . . , p m−k be the integers between 1 and m that are not powers of two.
The statement of Definition 1.9 itself is well-defined in view of the fact that there are exactly k integers between 1 and m that are powers of two, viz., 2 0 , . . . , 2 k−1 . Here are p 0 , p 1 , . . . , p m−k for k = 4: where p 1 , . . . , p m−k are as in Definition 1.9.

F. Method of Attack
The evolution of the 1-perfect code in this paper crucially relies upon a number of concepts and results. To that end, let n = 2 k − 1, k ≥ 3, and m = n − 2.
At heart of the code construction is a scheme [15] that constructs Hamming codes using a Latin square. See Section II for the scheme itself. In a nutshell, it returns a partition of V (Q n ) into Hamming codes, say, V 0 , . . . , V n , each of cardinality 2 n−k .
Other major concepts/results employed are as follows: . Section III presents the theoretical foundation of the overall procedure. It systematically builds upon the scheme of Section II, and derives a number of results that are crucial to the correctness of the claims in the sequel.
The code construction itself relies on a vertex partition of CQ m into 2 3m subsets, each of cardinality 2 m+2 , where exactly 2 m−k+2 elements of each such subset are carefully designated as code elements, which themselves come from a set among V 0 , . . . , V m+2 . Figure 5 depicts this idea.
The foregoing vertex partition is further refined in Section IV that also presents the scheme itself. (See Figure 10.) The four sections that come next are then devoted to proving that the set returned by the main scheme is indeed a 1-perfect code of the graph.
Section IX takes the final step of proving that CQ m admits a vertex partition into 1-perfect codes, whereas Section X presents certain concluding remarks.

II. A SCHEME TO CONSTRUCT HAMMING CODES
This section recapitulates a scheme [15] that builds Hamming codes over Q n . See Algorithm 1.
Theorem 2.1: [15] For n = 2 k − 1, k ≥ 2, Algorithm 1 returns a partition, say, V 0 , . . . , V n of V (Q n ) having the following properties: 1) |V i | = 2 n /(n + 1), 0 ≤ i ≤ n, and 2) Every pair of two distinct elements in each set is at a Hamming distance of at least three, and the set is maximal with respect to this property. 9: where b i,j = 0 if u i,j is of even parity, 10: and b i,j = 1 if u i,j is of odd parity 11: end for 12: Comment: The sets C 0 , . . . , C n , and D 0 , . . . , D n together constitute a partition of V (Q n+1 ). 13: let T = (t i,j ) be the (n + 1) × (n + 1) Latin square on the identity permutation, vide Definition 1.7 14: return the sequence of sets Whereas any (n + 1) × (n + 1) Latin square (at Step 13 of Algorithm 1) would lead to a partition of V (Q n ) into Hamming codes, the schemes in this paper exclusively employ the Latin square on the identity permutation, viz., M r . (See Definition 1.7 and Table II in Section I-C.) Further, the resulting vertex partition V 0 , . . . , V n of Q n is referred to as the canonical partition, where V i = {v i,0 , . . . , v i,r−1 }, r = 2 n /(n + 1) and 0 ≤ i ≤ n. Additionally, each V i is deemed to be sorted into the ascending order. See Tables V, VI and VII that illustrate the working of the algorithm. Remark: Algorithm 1 is extendable to a scheme that leads to an upper bound on the (independent) domination number of the hypercube that is within twice the optimal [15].

III. THEORETICAL FOUNDATION This section derives a number of useful properties relating to the canonical partition
Lemma 3.1: There exists a "perfect matching" between each pair of distinct V i and V j .
Because of the distance-three property of each V j and the degree of v being equal to n, it is easy to see that v has a unique neighbor in

1) It is clear that there exists a matching between sets
It is clear that u i,k and u j,k differ in exactly the a-th bit position, so they are of different parities. Therefore, b i, j , where C i , D i , and U j are as in Algorithm 1, and where 0 ≤ i, j ≤ n. Proof: Each binary string in C i (resp. D i ) is of length n+1, whereas that in U j is of length n. The claim then follows from the fact that a is between 0 and n − 1.
Proof: Note that n The following is a key result.
Proof: Use induction on n, and make use of the notations as in Algorithm 1. For n = 3, see Figure 6 where 0 ≤ i ≤ n and 0 ≤ a ≤ n − 1, whereas the induction step calls for proving that V There are four cases.
Step 14 of Algorithm 1. Note here that each of i and a + 1 is between 0 and n = 2 k − 1, so each is a k-bit number, hence so must be i (a + 1). It follows that i (a + 1) is between 0 and n.
Note that i (a + 1) in this case is of the form 1u (binary), where u is a k-bit number. Therefore, i (a+1) is between n + 1 and 2n + 1 (decimal).
by a reasoning as in (2) Notice at this point that i and a + 1, in this case, are representable in binary as 1u and 1v, respectively, where u and v are k-bit numbers that denote (i − (n + 1)) and (a − n), respectively. In that light, i (a + 1) = (1u) (1v) = u v that is equal to (i−(n+1)) (a−n).
in this case, is between 0 and n. Figure 7 illustrates the four cases in the proof of Theorem 3.7 for the collection V 0 , . . . , V 7 with respect to Q 7 . (See Table VII in Section II for descriptions . It is clear that each of (i (a + 1)) and (i (b + 1)) is between 0 and n. Also, 4a+3 ) of four consecutive nodes in each V i contains one element each of Type 0, Type 1, Type 2, and Type 3 (not necessarily in that order), where 0 ≤ i ≤ n.
Proof: Use induction on n. For n = 7, the claim follows by an inspection of the sets in Table VII in Section II. Using the notations as in Algorithm 1, each element of V i is of the form u · v (binary), where u ∈ C p (or u ∈ D p ) and v ∈ U q for some p and q, with |u| = n + 1 and By induction hypothesis, every block of four nodes (starting at an index divisible by four) in U q has the stated property. That property is, in turn, inherited by the set C p • U q (or D p • U q ) and the union of such disjoint sets.
The next result shows that the elements in each V i are uniformly "spread out." Theorem 3.10: Recall that each element of each V i is between 0 and 2 n − 1. Therefore, the sets W i , X i , Y i and Z i are welldefined. (See Figure 8 for an illustration.) To prove the claim, use induction on n, the basis being clear from the sets that appear in Table VII in Section II. For the induction step, first examine the sets C i and D i in the "for" loop at Steps 6 − 11 in Algorithm 1, where 0 ≤ i ≤ n. The elements in each such set are between 0 and 2 n+1 − 1.
By induction hypothesis, each of U 0 , . . . , U n (appearing at Step 5 of the algorithm) has the stated property. Note next that 1) If x ∈ U i , then either 2x ∈ C i and 2x + 1 ∈ D i , or 2x + 1 ∈ C i and 2x ∈ D i , and 2) For It follows that each C i or D i admits a partition into four (sub)sets in which the elements range (i) from 0 to 2 n−1 − 1, (ii) from 2 n−1 to 2·2 n−1 −1, (iii) from 2·2 n−1 to 3·2 n−1 −1, and (iv) from 3 · 2 n−1 to 4 · 2 n−1 − 1, respectively. Consider next the sets C a • U b and D a • U b that appear in the unions at Step 14 of Algorithm 1, where 0 ≤ a, b ≤ n, and note that ) if x is in the first quarter (resp. second quarter, third quarter or fourth quarter) of C a or D a , and y ∈ U b , then 2 n x + y is in the respective quarter of It follows that each of C a •U b and D a •U b admits a partition into four subsets having the stated property. Finally, this property is seamlessly inherited by each union appearing at Step 14 of Algorithm 1.
See Figure 9 for an illustration of Definition 3.1.

IV. THE MAIN SCHEME
This section presents the main scheme that returns a 1-perfect code of CQ m . See Algorithm 2. The scheme itself relies on successive vertex partitions of the graph, depicted in Figure 10 that, in turn, is viewable as a refinement of the partition that appeared in Figure 5 in Section I. As stated earlier, the smallest unit in the vertex partition is a set of the form 2 m+2 x + {0, . . . , 2 m+2 − 1}, of which a subset 2 m+2 x + V i is designated as a set of code elements, The next four sections are devoted to proving that the set returned by the main scheme is indeed a 1-perfect code of the graph.
consists of the following sets that are mutually disjoint: . Then x = uv01 (binary) where u = 2 m c+d (decimal); |u| = m+k; |v| = m; and v01 ∈ B π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" replaced by "01". Note that x ≡ 1 (mod 4). Here are the m + 2 neighbors of uv01 in CQ m : • uv11 and uv00 (binary), and Notice next that d is an m-bit integer, hence so must be each of d (0) , . . . , d (m−1) . In that light, (2 m+2 Finally, it is easy to see that the sets involved are mutually disjoint. Figure 13 illustrates the argument in the proof of Lemma 5.5 for the case where m = 5. Meanwhile, the following result is analogous to Corollary 5.4. Corollary 5. 6: c2 δ(d2)) are mutually disjoint. Proof: First note that each element of 2 m+2 d + (B x ∪ D y ∪ A z ) is smaller than 2 2m+2 , and so is each element In that light, if c 1 = c 2 , then 2 m+2 (2 m c 1 + d 1 ) + B π(c1 δ(d1)) and 2 m+2 (2 m c 2 + d 2 ) + B π(c2 δ(d2)) are mutually disjoint, vide Lemma 5.5.
Let c 1 = c 2 and d 1 = d 2 next.

Lemma 5.9:
consists of the following sets that are mutually disjoint: ) . Then x = uv10 (binary), where u = 2 m c + d (decimal), |v| = m and v10 ∈ C π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" replaced by "10". Note that x ≡ 2 (mod 4). Here are the m + 2 neighbors of uv10 in CQ m , vide Definition 1.4: • uv00 and uv11 (binary) , the count being k, and Since c is a k-bit integer, so must be each of c (0) , . . . , c (k−1) . The rest of the argument is similar to that in the proof of Lemma 5.5. Figure 15 illustrates the argument in the proof of Lemma 5.9 for the case where m = 5.
Corollary 5.10: c2 δ(d2)) are mutually disjoint.  Proof: . This and the fact that each element of C x , D y or A z is smaller than 2 m+2 together imply that 2 m+2 (2 m p + d 1 ) + X and
Proof: Similar to that of Corollary 5.8. Remark: The expression c (t−1) may be replaced by c 2 t−1 , vide Prop. 1.2(1). Figure 16 illustrates the argument in the proof of Corollary 5.11 for the case where m = 5, where '?' indicates that the respective sets are yet to be dominated. Lemma 5.12: consists of the following sets that are mutually disjoint: (c δ(d)) . Then x = uv11 (binary), where u = 2 m c + d (decimal), |v| = m and v11 ∈ D π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" • uv10 and uv01 (binary), and The rest of the argument is similar to that in the proof of Lemma 5.9. Figure 17 illustrates the argument in the proof of Lemma 5.12 for m = 5, whereas Figure 18 depicts the statements of Lemmas 5.1(1)/5.5(1)/5.9(1)/5.12(1) for m = 5. Based on the distance-three property, c1 δ(d1)) and 2 m+2 (2 m c 2 + d 2 ) + D π(c2 δ(d2)) are mutually disjoint.
Proof: Similar to that of Corollary 5.10. Theorem 5.14: Algorithm 3 returns the set that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0 between 0 and 2 2m+k+2 − 1, the count being 2 2m+k . 2) The set of all elements of Type 1 between 0 and 2 2m+k+2 − 1, the count being 2 2m+k .
Example: Let m = 5, and consider the set VI. STEP 2 The objective of the present section is to slowly "spread the wings" beyond what appeared in Section V. See Algorithm 4 that subsumes Algorithm 3. In particular, it returns a code set that is a subset of that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0 between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, the count being 2 2m+k . 2) The set of all elements of Type 1 between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, the count being 2 2m+k .
The following is analogous to Corollary 5.15. Corollary 6.2: Among the elements between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, those in the following sets are not dominated by the set returned by Algorithm 4: , the number of elements being equal to (m − k)2 2m , and and p 1 , . . . , p m−k are as in Definition 1.9.

VII. STEP 3
This section focuses on the inner three loops of the main scheme, viz., Algorithm 2 of Section IV. In the process, it builds a code set that is a subset of See Figure 21 for the basic element used in Algorithm 5.
consists of the following sets that are mutually disjoint: . Proof: Similar to that of Lemma 5.1.
Proof: Make use of an argument as in the proof of Corollary 7.2, and invoke Corollary 5.6.
Lemma 7.5: consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 5.9. The following result is analogous to Corollary 5.8.
Proof: First note the following: , then the claim follows from Corollary 5.10.
In what follows, let 1 ≤ Ham(b 1 , b 2 ) ≤ 2, and assume that 2 2m+k+2 b 1 + 2 m+2 (2 m c 1 + d 1 ) + C π(φ(b1) c1 δ(d1)) and 2 2m+k+2 b 2 + 2 m+2 (2 m c 2 + d 2 ) + C π(φ(b2) c2 δ(d2)) are not disjoint. Using notations as in the statement of Lemma 7.5 and the fact that b 1 = b 2 , it is easy to see that c 2 , d 2 ). Accordingly, there are two essential possibilities: b1) c1 δ(d1)) . The conditions on various parameters are such that the following hold: , which leads to p s+1 = 0, a contradiction, vide Definition 1.9. (Notice that Ham(b 1 , b 2 . Again, the conditions on various parameters are such that the following hold: For this equality to hold, p s+1 = 2 t . However, p s+1 is not a power of two, vide Definition 1.9; a contradiction. (Notice that Ham(b 1 , b 2 ) = 2 in this case.) consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 5.12. Corollary 7.9: , then the claim follows from Corollary 5.13. On the other hand, if b 1 = b 2 , then the claim follows from the fact that 2 2m+k+2 is greater than the maximum of 2 m+2 (2 m c + d) + 2 m+2 − 1; and 2 m+2 is greater than each element of D Theorem 7.10: Algorithm 5 returns the set that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0, between 0 and 2 3m+2 − 1, the count being 2 3m . 2) The set of all elements of Type 1, between 0 and 2 3m+2 − 1, the count being 2 3m .
3) The set returned by Algorithm 5 is a superset of that returned by Algorithm 4. Next, of the m + 3 sets, viz., m+2)) , the following are exactly those not dominated by the set returned by Algorithm 4, vide Corollary 6.2(1): In that light, it suffices to show that the foregoing sets are dominated by the set returned by Algorithm 5. To that end, use Corollary 7.6 and the fact that φ(b (t−1) ) = φ(b) p t (vide Lemma 1.13), whence The disjointness of the sets in this case follows from Corollary 7.7. 4) a) Immediate from Lemmas 7.8(1), 7.3(1) and 7.5(1). b) Immediate from Lemmas 7.8 (2). The disjointness of various sets in this case follows from Corollary 7.9. Figure 22 presents the count of the elements of Type 3, dominated by the set returned by Algorithm 5. Meanwhile the following is analogous to Corollary 5.15 and Corollary 6.2.

VIII. STEP 4
This section zeroes in on the main result. See Algorithm 6 that is a miniature of Algorithm 2 in Section IV. Further, see Figure 23 for the element used in this section. As usual, k ≥ 3 and m = 2 k − 3.
Proof: Similar to that of Corollary 7.2.
Proof: Similar to that of Corollary 7.4. a) φ(b) c δ(d)) consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 7.5.
2) The (independent) domination number of CQ m is equal to the theoretical minimum of 2 4m−k+2 .

IX. VERTEX PARTITION OF THE QUAD-CUBE INTO 1-PERFECT CODES
It turns out that the main scheme admits a generalization. See Algorithm 7, where a new parameter t has been introduced, 0 ≤ t ≤ 2 k − 1.
By symmetry, every claim relating to the set returned by Algorithm 6 holds true with respect to the set returned by Algorithm 7. Hence the result.
Proof: See Figure 2 in Section I for a vertex partition of CQ 1 (m = 3 and k = 2) into 1-perfect codes. In what follows, let k ≥ 3.

X. CONCLUDING REMARKS
A quad-cube CQ m is a special case of a more general topology, called the metacube [19] that itself is derivable from the hypercube. This paper presents a vertex partition of CQ m into 1-perfect codes, where m = 2 k − 3, k ≥ 2. In an earlier study [14], the author presented an analogous result over the dual-cube that is a simpler version of the metacube.
There exist other more complex versions of the metacube, notably, the oct-cube that merit a similar study.

ACKNOWLEDGMENT
The author sincerely thanks the anonymous referees and Associate Editor Xiande Zhang for their helpful comments on the earlier draft that led to an improvement in the presentation of the article.