# Detection of Household Furniture Storage Space in Depth Images
## 3 Methods
### Empty Storage Volume Detection Algorithm
#### 3.1.1 Free Space Core Detection  
The first step of the proposed algorithm is to create a voxelized reprezentation of the input 3D mesh. A voxel grid with dimensions \(n\times n\times n\) voxels is defined on the bounding cube of the input 3D mesh. Each voxel in this grid is assigned a binary value. The unoccupied voxels are assigned the value \"1\", and are referred to as _free voxels_. Voxels occupied by the furniture structure are assigned the value \"0\", and they are referred to as _occupied voxels_. This binary voxel grid is called the _occupancy grid_. In this section, \(v\) denotes the position of a voxel in the voxel grid, where \(v=(x,y,z)\in\mathbb{R}^{3}\) with the components \(x\), \(y\), and \(z\), which represent the coordinates of the voxel in the voxel grid. Preforming the 3D chessboard distance transform (CDT) [32] of the voxel grid assigns to every free voxel \(v\) the chessboard distance to the closest occupied voxel \(v\)[21]. The chessboard distance between two voxels \(v\) and \(v^{\prime}\) is defined by  
\[d(v,v^{\prime})=\max(|x^{\prime}-x|,|y^{\prime}-y|,|z^{\prime}-z|)\]  
value \(D(v)\) assigned to voxel \(v\) by the CDT is defined by  
\[D(v)=\min_{v^{\prime}\in V_{0}}(d(v,v^{\prime}))\]where \(V_{0}\) is the set of all occupied voxels. This value is referred to as _occupancy distance_.  
Connected subsets of voxels corresponding to local maxima of the CDT with equal occupancy distances \(\delta\) indicate the centers of empty volumes that can potentially be used as storage volumes. To isolate such groups of voxels, the algorithm determines local maxima of CDT in the \(3\times 3\times 3\) neighborhood of each voxel and creates a new binary grid. Voxels corresponding to the local maxima of the CDT are assigned the value \"1\", while all other voxels are assigned the value \"0\". The local maximum voxels are grouped using the connected component labeling. The groups of voxels obtained this way are referred to in this paper as _free space cores_ (FSC). An example of a FSC is shown in Figure 2a,b.  
Dilating a free space core by \(\delta\), i.e., using a cube of dimensions \(s\times s\times s\), where \(s=2\cdot\delta+1\), as the structuring element, yields an empty volume, which can be considered as an empty storage volume candidate. The proposed algorithm generates one storage volume candidate from one free space core. However, free space cores do not necessarily have to be cuboidal; rather, they resemble the shape of the environment they were detected in. Figure 2a shows an example of storage furniture with a non-cuboid storage space. This model will be used for further explanation.  
The problem is that if the free space cores are not cuboidal, neither is the storage volume obtained by dilatation, which was the original assumption. Therefore, further processing is required. The proposed algorithm is based on the assumption that storage volumes are axis-aligned cuboids. Consequently, the free space cores must be adjusted to a rectangular shape so that the described dilation procedure can be used.