# Computer Vision Based Planogram Compliance Evaluation
## 2 Materials And Methods
### Planogram Compliance Evaluation  
Initially, we tested a maximum common subgraph-based approach [13] for the planogram compliance evaluation. However, while this approach works well for images that contain only a few products, such as in the GP-180 dataset, it is computationally infeasible for the more realistic scenario where images span whole shelves. This is due to the computational complexity of the algorithm proposed by [PERSON] and [PERSON] [13]. If we have a reference planogram with at most \(r\) instances of a single product and an observed planogram with at most \(o\) instances of a single product, and if the intersection of the  
Figure 11: The PatchGAN discriminator given in the official PyTorch implementation of [PERSON] et al. [32]. The input is an image, with shape \(3\times H\times W\). Downsampling is implemented via a stride of 2 in all but the two final convolution layers. The output is a scalar: the confidence that the input image is real, that is, not generated by the generator. This scalar is calculated by averaging the elements of the last, \(1\times H/8\times W/8\) feature map. products in these two planograms includes \(N\) products, the proposed _CreateHypotheses_ routine creates \(O(P^{2}N)\) hypotheses where \(P=\max(r,o)\). With a hypothesis set this big, assuming that finding the best hypothesis always requires only constant time (which is quite optimistic) and that each product is resolved completely before moving on to the next product, _FindSolution_ requires \(N\sum_{1}^{P}P^{2}=O(P^{3}N)\) iterations to clear the hypotheses related to the first product. As the first product is now cleared, the next product requires \(O(P^{3}(N-1))\) iterations and the product after that \(O(P^{3}(N-2))\) iterations all the way to \(O(P^{3})\) iterations for the final product; therefore, the full computational complexity of the first _FindSolution_ run is \(O(P^{3}\sum_{1}^{N}N)=O(P^{3}N^{2})\). This is then repeated for each hypothesis (of which there are \(O(P^{2}N)\)) with a slowly shrinking input set. It is therefore obvious that the proposed algorithm of [PERSON] [13] is fine for a dataset such as the planograms in GP-180 introduced by them, where the largest values for \(P\) and \(N\) are 6 and 9, respectively, but that it is not suitable for full shelf planograms with tens of different products and tens of facings for each product. To overcome this prohibitive complexity, we started by calculating an arbitrary common subgraph instead of a maximal one and then utilizing RANSAC pose estimation [26] for determining the presence of the majority of products. We further evolved this approach with the realization that, in fact, the whole subgraph comparison is unnecessary --RANSAC is computationally performant and very resistant to outliers, so we can instead just match _all_ detected products of some class to all expected products of the matching class. Ultimately, our planogram compliance evaluation approach is as follows: We take as input the bounding boxes and classes of products in the reference planogram and the bounding boxes and classes of products detected in the image under evaluation. Then, we calculate a Cartesian product of planogram bounding boxes and detect bounding boxes for which the classification matches. Out of each pairing generated by the Cartesian product, we create nine pointwise matches: one match between each matching corner of the planogram and the detected bounding box, one match between each matching midpoint of a side of the planogram and the detected bounding box, and one match between the centers of the bounding boxes. We feed these pointwise matches to a RANSAC algorithm, and get an estimated pose as an output. We utilize the estimated pose to transform the reference planogram's bounding boxes to image coordinates. Then, we check whether each bounding box in the reference planogram has a good enough matching detection in the image by determining whether there is a detected bounding box with a matching class and an IoU between the boxes larger than 0.5.