## 2 Proposed Segmentation Methodology
### Clustering of Points  
Once the locations of the two origins are determined, the attributes of all of the points in the dataset are computed (according to the methods explained in the previous sub-sections) and recorded in the accumulator array. Afterwards, clustering of points with similar attributes is conducted while considering the points' proximity and co-planarity. Figure 7 is a flow chart of the clustering procedure proposed in this research. The points belonging to different planes in the object space are expected to form different accumulated peaks in the attribute space. Figure 8 illustrates an example of planar patch segmentation. A laser dataset over a region that includes a building with two planar patches (e.g., a gable roof) is selected; see Figure 8a,b. The points that belong to the patches produce, through the voting scheme, two peaks in the accumulator array; see Figure 8c. Afterwards, the points contributing to the highest peak cell are identified. Here, the cell size of the accumulator array is determined based on the noise level of the laser scanning data utilized (e.g., two times the accuracy of the laser data in the depth direction to cover around 95% of the laser points on the plane). Using these points, plane fitting is conducted through the least squares adjustment procedure. Then, the quality of plane fitting is evaluated by checking the RMS (Root Mean Square) of the shortest Euclidean distances between the points and the plane determined. The acceptable quality of plane fitting is determined while considering the noise level of the laser data utilized. More specifically, the quality of plane fitting will be accepted when the RMS of the distances is less than the accuracy of the laser data. Poor plane fitting will occur when the ambiguity mentioned in the attribute computation procedure exists, though that possibility is extremely low. In other words, the points belonging to the planes with different slopes and aspects might contribute to the highest peak, thus leading to the  
Figure 5: Locations of two origins. Figure 6: Example of ambiguity from two origins (side view). \[\left( \begin{array}{c}X_{new}\\ Y_{new}\\ Z_{new}\end{array} \right)=\left( \begin{array}{c}X_{original}\\ Y_{original}\\ Z_{original}\end{array} \right)+\left( \begin{array}{c}Range\times Rand\_X\\ Range\times Rand\_Y\\ Range\times Rand\_Z\end{array} \right) \tag{7}\]  
where, \((X_{new},Y_{new},Z_{new})\) are the locations of the new origin, \((X_{original},Y_{original},Z_{original})\) are the locations of the original one, Range is a threshold according to which the new origin is located within a certain range (_i.e._, 5 m), and \((Rand\_X,Rand\_Y,Rand\_Z)\) are the random values between 0 to 1 for the (\(X\), \(Y\), \(Z\)) coordinates. Afterwards, a small accumulator array for only the points (causing the ambiguity) located at the peak is constructed using their attributes recomputed from the two new origins. One should note that once the original attributes are computed, re-calculating the attributes from the new origins does not need much computational load. This is expected to lead to the separation of the points causing the ambiguity into different peaks in the accumulator array. Then, plane fitting using the points contributing to the highest peak cell is again conducted. This process is repeated until a good quality of plane fitting is acquired. In the case where the iteration number reaches the maximum (_i.e._, 5 iterations) without finding a plane fitting result of adequate quality, the next-highest peak cell is detected from the original accumulator array and a plane fitting quality test is carried out. To verify the performance of the process, two origins were intentionally located at a position having the same XY coordinates (from the center of the gable roof ride line) but different Z coordinates. Figure 9 shows a scatter plot incorporating the magnitudes of the normal position vectors for all of the relevant points on the gable roof.