1 Introduction
Volume is one of the important issues in the production and processing of food product. Volume together with other physical properties plays an important role in calculating water loss, heat transfer, quantity of pesticide applications, respiration rates, etc. In food processing, volume is useful for size sorting, quality grading, and microbial concentration [1]. If volume of a food product can be determined, then the other physical properties such as mass and density can be easily estimated [2],[3]. In egg, volume is related to many important things in bird life such as female mass, female social status, lay date, egg composition, nesting success, hatchling size, and nestling survival [4]. In bread, volume is a good indicator for gas retention properties of dough, quality of flour
protein, quality of gluten development, and balancing recipe and processing requirement [5]. Therefore research in volume measurement is an important task.
Traditionally the volume of an object can be measured using water displacement method based on Archimedes' principle. The object is immersed into water that placed in a container until all surfaces are immersed. Displaced water is collected in another container and its volume is measured. The volume of displaced water is considered as the volume of the object. Water displacement method is inaccurate, especially for porous or fragile object [3], [6]. For example in bread volume measurement, water displacement method fails because it can damage the bread. Moreover the water will be absorbed by the bread. In measuring bread volume water displacement method is modified using seed displacement. Usually rape seed or pearl barley is used to replace water. This method is less in accuracy because the bread may be compressed when it is merged in the seed [7].
Currently, volume measurement instrument using laser scanner for food product, especially bread, has been introduced to market, such as TexVol instruments BVM-L series (http://www.texvol.com) or Volscan Profiler from Stable Micro Systems (http://www.stablemicrosystems.com). However, this instrument is expensive and cannot be applied directly in production line.
Computer vision offers an accurate and nondestructive method in measuring volume of food product [8]. It has been widely applied to solve real problem in various fields including optical character recognition (OCR), machine inspection, object recognition, 3-D model building, automotive safety, match move, motion capture, surveillance, fingerprint recognition and biometric [9]. In addition, computer vision provides innovative solution for industrial automation.
Various industrial activities have been getting benefits from application of computer vision in manufacturing process such as electronic component, textile, metal, granite, glass, printing, pharmaceutical tablet, bottling, etc [10]-[13]. Computer vision has been used for automated visual inspection of food product in many countries [14]. Automated visual inspection using computer vision is nondestructive method and has been used in various agriculture and food industries, such as fruits, vegetables, beef, pork, etc [15],[16].
Previous studies in volume measurement of food product using computer vision have been done by many researchers and can be classified into two types of measurement. The first one is volume measurement for axi-symmetric object [2],[3],[17]-[19] and the second one is volume measurement for irregular shape
object [1],[6],[20],[21]. In previous researches, volume measurement of irregular shape object was performed by 3-D object reconstruction. The volume was approximated from the reconstructed 3-D object by mathematical formulation or counting the number of voxel. This process is time consuming in computation. Furthermore previous researches in volume measurement are not implemented to measure volume of object in production line.
In mathematical perspective [22], the volume of solid object can be calculated using triple integral over a region with boundary the surface of object. If the surface equation of object is known then the integral can be evaluate analytically or by numerical approximation. Otherwise the surface of object must be reconstructed first before evaluating the integral by numerical approximation. In 3-D computer vision for volume measurement, this process is done by 3-D object reconstruction. Another method for evaluating volume is Monte Carlo integration. Monte Carlo method evaluates the integral by generating random points. Only information whether generated points fall inside or outside the object is needed for evaluating volume, without knowing the surface of object.
The aim of this paper is to propose algorithm for volume measurement of irregular shape food product using computer vision based on Monte Carlo method. Monte Carlo method provides easier way in volume measurement of irregular shape object. Moreover Monte Carlo method does not require 3-D reconstruction of irregular object for volume measurement.
2 Related Works
2.1 Volume Measurement of Axi-symmetric Object
An object is considered as axi-symmetric if the cross sections of the object which are perpendicular to its major axis are circular shape. Some example of axi-symmetric food products are eggs, watermelons, oranges, lemons, limes, tamarillos, cantaloupes, etc. The object can be modeled as solid of revolution obtained by rotating half of its projected area around its major axis. With this modeling volume of the object can be approximated using disk method or frustum cone method. Table 1 shows summary of related works in volume measurement of axi-symmetric object.
Koc [2] has approximated volume of watermelon using disk method. Image of watermelon was acquired in RGB color space using a camera and then converted to gray scale image. Threshold technique was used to produce binary image from gray scale image. The threshold value was determined by experiment. The boundary of watermelon was extracted from its binary image
using ImageJ custom edge detection technique. Area inside boundary image was assumed as sum of rectangles. Rotating half of each rectangle around major axis of watermelon produced cylindrical disk. The volume of watermelon was estimated by the sum of all cylindrical disk volume.
| Table 1 | Related works in volume | measurement of axi-s | vmmetric obiec |
|---|
| Methods | Measured objects | Accuracy |
|---|---|---|
| Disk [2] | Watermelon | 7.7%a |
| Conical frustum [3] | Egg | 3.2%a |
| Lemon | 4.2% a | |
| Lime | 6.7%a | |
| Tamarillo | 4.4% a | |
| Modified conical frustum [17] | Ham | -1.8%b |
| Elliptic conical frustum [18]-[19] | Orange | \(0.985^{c}\) |
| Lemon | \(0.962^{c}\) | |
| Lime | \(0.957^{c}\) | |
| Tangerine | 0.959c |
<sup>a</sup>Average relative absolute error/difference
Wang and Nguang [3] have designed low cost sensor to measure volume of axi-symmetric agriculture product, such as eggs, lemons, limes, and tamarilos. A low cost image sensor was used to capture the image of object in black/white mode. Gaussian filter was applied to captured image for noise removal and followed by edges detection using gradient method. The object was modeled as sum of elementary right conical frustums and its volume was approximated by the sum of all frustum volume. The top diameter, bottom diameter, and height of each frustum were determined from edges of the object. Du and Sun [17] have modified conical frustum method to estimate the volume of ellipsoidal ham. They assumed that ellipsoidal ham was the sum of right conical frustum except its two end portions. The two end portions were modeled as spherical caps.
To increase the accuracy of conical frustum method, Khojastehnazhand, et al. [18] and Omid, et al. [19] assumed the cross sections of conical frustum is elliptical. Two cameras were used to capture the image of object in RGB color space. After image acquisition background segmentation and image enhancement were performed on these two images. To remove background from the images, the RGB values of the images were compared with the RGB
<sup>b</sup>Average relative error
<sup>c</sup>Coefficient of determination \((R^2)\)
values of background, which have been stored in the database. Image enhancement was used to remove slight shadows produced in background segmentation. Information about the shadow histogram was used to correct the images. Two perpendicular diameter of each cross section were obtained from the two images and used to calculate the area of the cross section. The volume of each frustum was determined using this area. Total volume of the object was estimated by summing them up.
2.2 Volume Measurement of Irregular Shape Object
Volume measurement for irregular shape object has been done by 3-D object reconstruction. The 3-D object is reconstructed using silhouettes of object from multiple views. The volume of object is measured from reconstructed 3-D object using either mathematical formulation or counting the number of voxel in reconstructed 3-D object. Table 2 shows summary of related works in volume measurement of irregular shape object.
| Methods | Measured object | Accuracy |
|---|---|---|
| Wire frame model [1] | Apple, cantaloupe, strawberry, | 2.5%d |
| tomato | \(0.956^{\rm e}\) | |
| Space carving [20] | Mango (SS size) | 8.89%d |
| Mango (S size) | \(9.96\%^{\mathrm{d}}\) | |
| Mango (L size) | 9.63%d | |
| Lofting [21] | Granny Smith apple | \(0.992^{e}\) |
| Red delicious apple | \(0.998^{e}\) | |
| Meat | \(0.995^{\rm e}\) | |
| Volume intersection [6] | Agglomerated milk | \(4.4\%^{\mathrm{d}}\) |
<sup>d</sup>Average relative absolute error/difference
Lee, et al. [1] have proposed non destructive method to measure volume of irregular shape object using multiple silhouettes. Either 30 or 60 images of object were taken from multiple views by a camera and rotating object in a fixed angular interval using a turntable. By assuming 0.5 second is needed to capture one image then at least 15 seconds are needed for capturing image. This process is time consuming. The captured images were then segmented to separate object from background using threshold method. Threshold value was determined either manually by user or automatically using image histogram. Eight-neighborhood clockwise boundary tracking was developed and implemented to produce 2-D object contours. Based on their center line and angular position, 2-D object contours were then converted to 3-D and assembled to
<sup>e</sup>Coefficient of determination
construct 3-D wire frame model. Linear interpolation was applied to corresponding boundary points from two adjacent contours. Mathematical formulation was built from 3-D wire frame model to approximate the volume of object.
Chalidabhongse, et al. [20] have developed vision system to measure mango's volume. Four cameras were used to image acquisition and stored in RGB format. A camera captured image from the top of object and three cameras captured image from surrounding object. Camera calibration was performed before image acquisition to obtain intrinsic and extrinsic cameras parameters. Some images were selected and segmented manually. RGB values of object in image sample were used to obtain hue value and object's hue surface model. Object and background were segmented using object's hue surface model and chromaticity similarity, followed by closing and opening morphological operations to form silhouette. 3-D object reconstruction was done with space carving based on object silhouettes and camera parameters. The volume of object was estimated by counting the number of voxel in reconstructed 3-D object.
Goñi, et al. [21] have proposed volume measurement of irregular foodstuffs using three-dimensional reconstruction based on reverse engineering technique. Object was sliced into 10-18 slices along selected axis before image acquisition. The images of object cross section were captured from sliced object slice by slice. This process is time consuming and considered as destructive. Median filter was used to enhance image quality after converted original RGB image to gray scale format. Image was segmented using threshold value which obtained by analyzing gray scale image histogram and the boundary of object was detected. Interpolation of a subset of boundary pixels by closed B-spline curve was used to make continuous approximation to the discrete boundary of binary images. B-spline curves were correctly assembled using lofting technique. A closed Non-Uniform Rational B-Spline (NURBS) surface was constructed through B-spline cross section curves. The resulting surface was then transformed into a 3D solid object. A Finite Element Method (FEM) approach was developed to estimate volume of reconstructed object. A mesh was generated using curved mesh elements and Delaunay algorithm. Gaussian integration 4th order was used over all domains to obtain estimated volume values.
Castillo-Castaneda and Turchiuli [6] have presented methodology and experimental result about volume estimation of small particles using threedimensional reconstruction from multiple views. They used the same technique using by Lee, et al. [1] for image acquisition. Thresholding was used to extract object silhouette from image. Two dimensional coordinates of each silhouette were used to describe three dimensional coordinate of the points that belong to the projection plane. The coordinates of partial volume were generated by translations that are normal to projection plane. The total volume was given by intersection of partial volume and the volume of object was approximated by counting the number of voxels belonging to the intersections.
3 Monte Carlo Method
Monte Carlo method is a numerical method for solving mathematical problems by simulation of random variables. The name Monte Carlo is taken from a city in the Principality of Monaco that famous with its casino. This is because one of the simplest mechanical devices to generate random number is the roulette wheel in the casino [23]. The invention of games of chance whose behavior and outcome can be used to some interesting phenomena is the essence of the method. The name Monte Carlo was firstly used as mathematical method in the 1940s, by scientist who developed nuclear weapons in Los Alamos [24].
Figure 1 Area approximation using Monte Carlo Method.
The simplest application of Monte Carlo method is the determination of the area of arbitrary plane. Suppose an arbitrary plane S is completely contained in a square [a, b]×[c, d], as shown in Figure 1. Monte Carlo algorithm to obtain the area of S is as follows [23], [25]:
- 1. Generate N random points in the square. Two random numbers x and y in the range [a, b] and [c, d] respectively are used to generate coordinates of a point in the square. The larger N the more accurate approximation of the area is obtained.
- 2. Calculate the number of points that fall inside S and indicate as N0.
- 3. Approximate the area of S by (b a)(d c)N0/N.
Monte Carlo method is computationally effective method compared with deterministic method in solving multidimensional problems [24]. Monte Carlo method has been widely used to solve both mathematics and real problems, such as multidimensional integral, linear equation, nonlinear equation, eigen value problem, boundary value problem, integral equations, path integral, operations research, transport modeling in semiconductors and nanowires, radiation transport, statistical physics and chemistry, nuclear physics, traffic pattern modeling, and economics [24]-[26].
4 Proposed Algorithm
The computer vision system used to implement the volume measurement algorithm consists of hardware and software. The hardware is developed to simulate volume measurement of irregular shape object such that the measurement similar to real production line. The hardware structure consists of five cameras, light source, conveyor belt, and personal computer, as shown in Figure 2. One camera is located on the top of object while four cameras located on surrounding object. The cameras are connected to computer using USB cable. Personal computer is used to process acquired images using developed software. Measured object moves on conveyor belt during images acquisition. The conveyor belt uses black color and is equipped with black background on both sides. Black background is chosen in order to simplify segmentation process. Room light locating on the top of conveyor is used as light source.
The software is developed to process the images of object and to perform volume measurement using information extracted from processed images. The main processing step for volume measurement consists of camera calibration, image acquisition, image enhancement, image segmentation, and volume measurement based on Monte Carlo method, as shown in Figure 3. Camera calibration is used to determine intrinsic and extrinsic cameras parameters. Intrinsic camera parameters consist of focal length in x and y direction fx and fy; and the center of image (cx, cy), while extrinsic camera parameter consist of rotation matrix R and translation vector t. These parameters are used in bounding box construction and to project point in real world coordinate system into image coordinate system. Zhang's method [27] is used to perform camera calibration. A flat chessboard patter is used as calibration object. Ten images of chessboard pattern are taken from ten different views to estimate intrinsic camera parameters while one image is taken to estimate extrinsic camera parameters. In estimating extrinsic camera parameters, chessboard pattern is located at conveyor belt and assumed lie on plane z = 0 in real world coordinate system.
Figure 2 The hardware of computer vision for volume measurement.
Figure 3 The main processing step for volume measurement.
Image acquisition is performed using five calibrated cameras to capture object from the top and surrounding of object. The images of object are captured in certain time interval in RGB color space while object are moving on the conveyor belt at predefined speed. Image enhancement is performed to improve image quality by removing noise and increasing contrast. The images are firstly transformed to gray scale before image enhancement. Enhanced images are then segmented to extract the silhouettes of object from background. Image thresholding is performed to segment the images of object. Iterative procedure [28] is used to determine threshold value T automatically. A pixel in grayscale
image with intensity greater than T is assigned as object pixel (white) with binary value 1 and otherwise as background pixel (black) with binary value 0. Morphological opening and closing are used to remove white spot in background and black spot in object respectively. The result of image segmentation step is silhouette of object.
To perform volume measurement using Monte Carlo method a bounding box in real world coordinate system is firstly created. The bounding box is constructed from the silhouettes of object and camera parameters, such that the object is completely contained in the box. The bounding rectangle for silhouette of object from top view is re-projected onto a plane \(z = z_l\) located under the object in real world coordinate system. This plane is the lower bound of bounding box in z direction. From re-projected bounding rectangle, the lower and upper bound of bounding box in x and y direction are determined. Suppose the lower and upper bound of bounding box in x and y directions are \(x_l\), \(x_u\), \(y_l\), and \(y_u\). The upper bound of bounding box \(z_u\) is obtained by re-projected the middle top of bounding rectangle for silhouette of object from one of side view onto one of plane \(x = x_l\), \(x = x_u\), \(y = y_l\), or \(y = y_u\) in real world coordinate system that closest to the point. The algorithm proposed by Siswantoro, \(et \ al. \ [29]\) is used to reproject point and bounding rectangle in silhouette onto real world coordinate system. The illustration of bounding box construction is shown in Figure 4.
To generate 3-D random points inside bounding box, three independent random numbers, x, y, and z uniformly distributed on \([x_l, x_u]\), \([y_l, y_u]\), and \([z_l, z_u]\) respectively are generated N times. Therefore, 3-D random point (x, y, z) is uniformly distributed on the box. Each 3-D random point is then projected onto all images using corresponding camera parameters. If all projected points of a 3-D random point fall inside the silhouettes (white pixel) then the original 3-D random point is considered as a point in outside of the object. Suppose \(N_0\) is the number of random points in the object then the volume V of the object is approximated by:
\[V = (x_u - x_l)(y_u - y_l)(z_u - z_l)\frac{N_0}{N}\] (1)
Figure 4 The illustration of bounding box construction.
Since proposed algorithm only uses five image of object taken from five different views then in performing Monte Carlo, there is possibility that a 3-D point located outside the object will be recognized as object point. As a consequence the result of volume measurement will be greater than actual volume. Therefore to obtain accurate result, measurement adjustment is provided. The amount of measurement adjustment depends on the type of measured object. Algorithm 1 explains volume measurement based on Monte Carlo method from the silhouette of object.
Algorithm 1 Algorithm to perform volume measurement based on Monte Carlo method.
Input: silhouettes of object \(S_1\), \(S_2\), \(S_3\), \(S_4\), \(S_5\); camera parameters \(CP_1\), \(CP_2\), \(CP_3\), \(CP_4\), \(CP_5\); bounds of bounding box \(x_l\), \(x_u\), \(y_l\), \(y_u\), \(z_l\), \(z_u\), number of random point N; number of view M, measurement adjustment adj.
Output: volume of object V
N_0 \leftarrow 0 for i from 1 to N x \leftarrow GenerateUniformRandom(x_l, x_u) y \leftarrow GenerateUniformRandom(y_l, y_u) z \leftarrow GenerateUniformRandom(z_l, z_u) f \leftarrow 1 for j from 1 to M (x\_im_j, y\_im_j) \leftarrow ProjectToSilhouette(x, y, z, S_j, CP_j) f_j \leftarrow GetBinaryValue(S_j, x\_im_j, y\_im_j) f \leftarrow f^*f_j \nend for N_0 \leftarrow N_0 + f
end for \[V \leftarrow adj^*(x_u - x_l)^*(y_u - y_l)^*(z_u - z_u)^*N_0/N\]
5 Simulation
The experiment to validate proposed algorithm is currently carried out in laboratory using food products with irregular shape such as mango, apple, and tomato. For initial study in validating proposed algorithm, a simulation has been done in laboratory using the image of ball. Five image of ball with radius 3.68 cm acquired using five calibrated web cameras were used in the simulation, as shown in Figure 5. The computer used for the simulation was a 3.00 GHz Pentium(R) Dual-Core personal computer with 2.00 GB RAM and Windows 7 operating system. Proposed algorithm was implemented in Visual C++ 2010 using Open Source Computer Vision Library OpenCV231 [30].
Figure 5 The images of ball used in simulation.
Acquired images were then processed to obtain silhouettes of object and used to construct bounding box of object, as shown in Figure 6 and Figure 7. In this simulation the volume of object was measured 100 times using proposed algorithm with the number of generated random points (N) \(10^2\), \(10^3\), \(10^4\), \(2\times10^4\), \(3\times10^4\), \(4\times10^4\), \(5\times10^4\), \(6\times10^4\), \(7\times10^4\), \(8\times10^4\), \(9\times10^4\), and \(10^5\). The accuracy of volume measurement result was assessed by comparing with the exact volume of ball using absolute relative error, while coefficient of variation (CV) was used to measure the precision of volume measurement result. Absolute relative error and CV were calculated using the following equations
absolute relative error = \[\frac{\left|V_{Exact} - V_{MM}\right|}{V_{Exact}} \times 100\%\] (2)
\[CV = \frac{std.dev.}{mean} 100\% \tag{3}\] where VExact is exact volume of ball, VMM is volume measured using proposed algorithm, std.dev. and mean are standard deviation and mean of VMM from 100 measurements. In this simulation, comparison with space carving [20] was performed to compare measurement accuracy and processing time. The method was chosen for comparison because it used almost similar experimental setup.
Figure 6 The silhouettes of object.
Figure 7 Constructed bounding box.
6 Result and Discussion
Volume measurement result using proposed algorithm together with absolute relative error, CV, and processing time are tabulated in Table 3. The exact value of ball volume used in this simulation is 208.75 cm3 . The simulation result shows that increasing the number of random points (N) used in volume measurement will increase volume measurement accuracy. This can be shown by decreasing mean absolute relative error if N increases. This result agrees with the basic principle in Monte Carlo method, that the approximation using Monte Carlo method will be convergent to exact value for N sufficiently large [26].
For N greater than or equal to 10000 points mean absolute relative error was less than 1% compared to exact volume, while CV was less than 1% for N greater than or equal to 20000 points. Finally, for N equal to 100000 point proposed algorithm produce mean absolute relative error 0.36% and CV 0.32%. This result shows that proposed algorithm can perform volume measurement with high accuracy and precision. Mean processing time was less than 0.80 sec for all N with maximum processing time was 1.87 sec occurred for N = 100000.
In comparison with space carving method, by divided bounding box into 100000 voxels the result of volume measurement using space carving was 235.04 cm³ with absolute relative error 12.59%. Mean processing time for 100 times measurement was 20.20 sec with maximum processing time was 23.49 sec. Therefore, volume measurement using proposed algorithm is more accurate compared with volume measurement using space carving method. Moreover processing time for volume measurement using proposed algorithm is faster than space carving method.
| No. of random points (N) | Mean \(V_{MM}\) (cm3) | Mean abs. rel. error (%) | CV (%) | Mean processing time (sec) |
|---|---|---|---|---|
| 1000 | 209.82 | 2.92 | 3.43 | 0.53 |
| 10000 | 209.07 | 0.85 | 1.08 | 0.57 |
| 20000 | 209.54 | 0.76 | 0.87 | 0.65 |
| 30000 | 209.74 | 0.65 | 0.64 | 0.63 |
| 40000 | 209.49 | 0.57 | 0.63 | 0.68 |
| 50000 | 209.49 | 0.54 | 0.54 | 0.68 |
| 60000 | 209.54 | 0.49 | 0.48 | 0.79 |
| 70000 | 209.48 | 0.44 | 0.39 | 0.71 |
| 80000 | 209.43 | 0.41 | 0.37 | 0.75 |
| 90000 | 209.49 | 0.40 | 0.34 | 0.70 |
| 100000 | 209.40 | 0.36 | 0.32 | 0.73 |
Table 3 Volume measurement result using proposed algorithm.
7 Conclusion
In this paper, volume measurement algorithm for irregular shape object using computer vision based on Monte Carlo method is presented. The computer vision system used to implement the algorithm consists of hardware and software. The hardware is developed to simulate volume measurement of irregular shape object such that the measurement similar to real production line. The software is developed to process the images of object and to perform
volume measurement using information extracted from processed images. Simulation results using five images of ball taken using five calibrated web cameras from different views show that proposed algorithm produced mean absolute relative error 0.36% and CV 0.34% for the number of random points 100000 with mean processing time less than 0.80 sec. Moreover, proposed algorithm is more accurate and faster compared with volume measurement using space carving method. Therefore it is expected that volume measurement using Monte Carlo method can reduce computation time in volume measurement of irregular shape object and can be implemented in real production line.
Acknowledgment
The authors would like to thanks Ministry of Higher Education Malaysia and Universiti Kebangsaan Malaysia for providing facilities and financial support under Grants No. ERGS/1/2013/ICT07/UKM/02/2.