Development of Sensing and Processing Technologies for Optimal Portion Control in an Automated Can Filling System by Farag Omar B.A.Sc. Garyouns University, Benghazi, Libya, 1989 M.A.Sc. University of Waterloo, 1994 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES M E C H A N I C A L ENGINNERING We accept this thesis as conforming to the required^standard THE UNIVERSITY OF BRITISH COLUMBIA June, 2000 © Farag Omar, 2000 In presenting degree freely at this the thesis in University of available for copying of this department or publication of by this for his and Columbia, study. for her of requirements that agree may be It is representatives. financial the I agree I further scholarly purposes or thesis fulfilment British reference thesis partial gain shall not the that of Me' c Wtt i-l,' c^-( ' y : T hp The I lni\«»rcit\/ rsi University of Rt-itiel-. British Vancouver, Canada Date DE-6 (2/88) fi^j j, rColumbia ~^l..~U:~ Z.-).-3c: I: l^-f, ry i- l.e*&\ granted by allowed /lA. ^ an shall permission for permission. Department Library understood be for s the that without head advanced make it extensive of my copying or my written Abstract This thesis investigates the problem of portion control of natural objects such as fish and meat for packaging, and develops a new method for optimal portioning. Food portions that are processed for packaging or canning should be optimized with respect to a specified "target" portion, for reasons such as wastage reduction, regulatory requirements, consumer appeal, and aesthetic considerations. The approach of optimal portion control that is developed involves cutting a set of objects into pieces by taking into account the weight distribution of each object and grouping the pieces into package portions according to a weight-based optimality criterion. First, a general optimization model is developed for the portioning control problem. Next, the model is made specific to a practical and innovative approach for can-filling of fish. An optimization model is developed for the portion control of fish where the objective is to minimize the weight deviation of the canned portions from the target net weight of a can. The portioning process is then refined by incorporating realistic assumptions and constraints that exist in industrial fish portioning processes. The modified model is further checked again for feasibility, and the model refinement process is continued until a feasible optimization model that can be implemented on-line in an industrial plant, is achieved. The model that is developed in this manner provides a computational speed for portion control that is consistent with the typical industrial requirements of the process speed and filling accuracy. ii Clearly, the weight accuracy of the processed portions can be further improved by providing the capability of adjustable blade spacing in portion cutting. In particular, during cutting of fish into can-filling portions, if one were to start from one end of the optimally arranged placement of fish and integrate the overall optimal weight distribution function such that the weight between two adjacent blades equals the target weight of portion, then the portion error will be zero. However, there are practical constraints on portion dimensions. Also, it was found that the portion accuracy can be further improved by specifying not just one target weight rate, but rather an interval of lower and upper bounds. This optimization problem with adjustable blade spacing is analyzed and evaluated through computer simulations. A comparison is made with the optimization model that uses fixed blade spacing. In the practical process of portion control that is developed here, the fish are placed in a linear overlapped arrangement according to the optimality criterion and cut into canning portions using an array of gang knives. To determine the optimal placement the weight distribution function of each incoming fish has to be measured on-line. The accuracy of a portion weight is greatly influenced by the accuracy of the weight distribution sensor itself. A high-level sensing approach is developed for this purpose. It involves the off-line development of nondimensional structural models of fish which contain correlations between the weight distribution function and simple geometric parameters that can be measured at high speed and high accuracy. Then the on-line sensing involves measurement of the geometric parameters for each incoming fish and matching them to a fish model in the model-base. iii To analyze the performance of the optimal portioning process of fish, a comprehensive model of fish body is developed, based on real data on salmon. The model is used to generate large quantities of realistic data, which are used in a computer simulation of the optimal portioning process. The results of simulation, which incorporates such practical influences as measurement error, show that the developed sensor technique is able to provide good accuracy in sensing weight distribution. Results further show that the optimal portion control developed in this research, for can-filling of fish, is quite feasible and provides adequate production speed, and good accuracy and quality of the product. iv Table of Contents Abstract ii List of Figures ix List of Tables xii Nomenclature Acknowledgment 1 Introduction » xiii xvii 1 1.1 Research Objectives 3 1.2 Application of Optimal Portion Control in Fish Processing 4 1.2.1 Motivation 4 1.2.2 An Innovative Can-Filling System 5 1.2.3 Optimal Fish Portion Control 7 1.3 Research Approach 1.3.1 Estimation of the Weight Distribution Function 1.3.2 Model Refinement and Optimization 1.4 Thesis Outline 8 9 10 10 2 Literature Review and Background 12 2.1 Food Packaging 13 2.1.1 Filling Methods and Machinery 13 2.1.2 Process and Machines of Salmon Canning 15 2.1.3 Minimum-Wastage Food Packaging 20 2.2 Optimization Techniques 23 2.2.1 Mathematical Programming 23 2.2.2 Global Optimization 28 2.2.3 Real Time Optimization 29 2.3 Sensor Technology 30 3 Theory of Optimal Portion Control 33 3.1 Introduction 33 3.2 General Formulation 34 3.2.1 Problem Formulation 35 3.2.2 Model Development 38 3.3 Cannery Portioning of Fish 38 3.3.1 Fish Portioning Model 39 3.3.2 Overlapped Fish Model 42 3.3.3 Decoupled Overlapped Fish Model 44 3.3.4 Illustrative Example 52 3.4 Study of Optimal Fish Patterns 56 3.4.1 Simplified Uncoupled Model 60 3.4.2 Comparison and Discussion 62 3.5 Model with Specified Weight Rate Band and Adjustable Cutter Spacing 3.5.1 Mathematical Model 63 64 3.5.2 Comparison Between Models With Fixed and Adjustable Blade Spacing . . . 67 3.6 Global Optimal Aspects of Fish Portion Control vi 70 3.6.1 Branch and Bound Algorithm 70 3.6.2 Global optimality of LP and NLP Problems 72 3.6.3 Global optimality in the Overlapped Fish Models 75 4 On-line Sensing of the Weight Distribution Function 80 4.1 Introduction 81 4.2 Sensor Structure 83 4.3 Modeling of Fish Body 86 4.4 Estimating the Weight Distribution Function 91 4.5 Sensor Performance and Results 94 5 Simulation of the Optimal Portioning Process 5.1 Introduction 98 99 5.2 Process Description 100 5.3 Simulation Results for the Simplified Uncoupled Model 102 5.4 Simulation Results for the Adjustable Cutter Spacing Model 104 6 Conclusions and Recommendations 107 6.1 Conclusions 108 6.2 Recommendations for Future Work 110 Bibliography 112 A Measurement of Cross-Sectional Area Distribution 123 A.l Introduction 123 A.2 Cross-sectional Area of Fish 124 A.3 Validation of the Experimental Setup 128 A.3.1 Setup Uncertainty . 128 A.3.2 Example Cases 129 A.4 Measurement of Cross-sectional Area of Fish vii 132 B Laser/Vision System 135 B . l System Components and Specifications 135 B.2 Feature Point Coordinates 136 B.3 Computation of Feature Parameters 139 viii List of Figures 1.1 Schematic Representation of an Automated System for Fish Canning 2.1 Schematic Diagram of a Conventional Fish Canning Line 15 2.2 A Gang-Knife Machine for Portion Cutting 16 2.3 The Main Steps of Operation in the American Can-Filling Machine, (a) Steps are marked as 1 through 4. (b) Details of Step 2 7 17 3.1 Cutting Surfaces on Object j 36 3.2 A Schematic Diagram of the Model Development Procedure 39 3.3 Parallel Planar Cutting Surfaces for Fish Processing 40 3.4 The Overlapped Arrangement of Fish 42 3.5 Relative Placement of Fish 46 3.6 An Example of a Weight Rate Function w'(x) 54 3.7 The Optimal Overlapping Arrangement of Fish 56 3.8 Example of Generating Different Sizes of Weight Distribution Functions From Fish . 58 ix 3.9 Comparison Between the Standard Uncoupled and the Simplified Uncoupled Models, (a) Computational Time, (b) Production Speed 63 3.10 Error Function in the Overlapped Fish Model, Expressed as Absolute Deviation from a Specified Interval on Target Weight Rate 64 3.11 Can Weight Distribution Where the Specified Target Weight Rate is (a) Constant (Fixed Blade Spacing) (b) Bounded (Variable Blade Spacing) 69 3.12 Classification of Fish Size According to Net Can Weight, Using Real Data 70 3.13 The Branch and Bound Method 73 3.14 Equation (3.28)a and Its Second Derivative for the Overlapped Fish Pair #1 and 2. . . 75 3.15 Cost Function (3.54) for Different Sizes of Fish 77 3.16 Sub-Cost Function (3.69) for Different Combination of Fish Size 77 3.17 Sub-Cost Function of Equation (3.28) for Overlapped Fish Pairs of Different Sizes with the Orientation (a) H = 1 and Hj=l, (b) H, = 0 and H •= 1, (c) H = 0 and H = 0 t ] t } 79 4.1 The Structure and Cross-Sectional Area of a Cannery Dressed Fish 83 4.2 Schematic Diagram of the On-Line Sensor for Fish Weight Distribution 86 4.3 Fish Body Model 88 4.4 An Example of the Characteristic Functions of a Structural Model of Fish 88 4.5 Weight Distribution Functions Generated from Statistical Distributions of Fish Data (shifted to the origin) . 91 4.6 Models of Cross-Sectional Area 94 4.7 Normalized Density Function of Fish Fillets (shifted to the origin) 95 4.8 Histogram of the Estimation Error (a) Without Sensors Error (b) With Sensors Error. 97 5.1 Schematic Diagram of the Physical Portioning Process for Can-Filling of Fish 100 5.2 Flow Diagram of the Tasks in the Optimal Portioning Process 101 5.3 Statistical Distributions of Can Weights for Different Upper Limit Values of the Peak of Weight Distribution Functions of Fish 5.4 104 Statistical Distribution of Can Weights Produced Using the Adjustable Cutter Spacing Model (a) Coarse Resolution (b) Fine Resolution 106 A. 1 Partial Volume of Fish 124 A.2 An Experimental Setup for Measuring the Partial Volume Function 125 A.3 Measurement of Fish Partial Volume 126 A.4 Partial Volume of a Cylindrical Object 130 A.5 Partial Volume Estimation of the Triangular Object 132 A.6 Estimation Errors for the Triangular Object 133 A. 7 (a) Partial Volume Function of Fish ( + Experimental data; Curve fitting function), (b) Estimated cross-sectional area, A(x), of fish 134 B. 1 Vision/Laser System for the Measurement of Fish Body Features 136 B.2 Three-Dimensional Coordinates of a Feature Point 137 B.3 Measurement of a Fish Geometry 139 B.4 A Feature Point and Its Image 140 xi L i s t of Tables 3.1 The Optimal Values of Equation (3.28) and the Corresponding Values of x' M grams /cm, cm] for the Example Batch of Fish 2 [1000 55 3.2 The Optimal Placement Results for the Example Batch of Fish 56 3.3 Computational Times and Production Speeds for Different Batch Sizes 56 3.4 Optimization Results for a and a < 0.95 (Target Weight Rate = 47.92 grams/cm).... 59 x 2 3.5 Optimization Results for a, > 0.95 (Target Weight Rate = 47.92 grams/cm) 59 4.1 Parameter Values of Fish 91 5.1 Simulation Results Using the Simplified Uncoupled Model 103 5.2 Simulation Results Using the Variable Cutter Spacing Model 106 xii Nomenclature A Cross-sectional area of the tank (cm ) A(x) Cross-sectional area of a fish as a function of the position along the fish 2 c length (cm ) 2 Ape) Cross-sectional area of fish j (cm ) A(x) Estimated cross-sectional area of a fish (cm ) A (X) Non-dimensional model function of the cross-sectional area of fish (-) 2 2 m A (x), A (x), A (x) Cross-sectional area of muscle, bone, and skin, respectively, of fish (cm ) 2 m b A- s Peak index of fish weight distribution function for the fixed cutter spacing model b Peak index of fish weight distribution function for the adjustable cutter { spacing model C Total squared error for a batch of objects (e.g., fish) (gm ) C(X) Normalized cross-sectional circumference function of fish body (-) C" Reduced cost function of the squared error of overlapped fish i and i+1; 2 HH fish oriented head first; i denotes the order of fish in the overlapping chain (gm ) 2 C * HH i} The minimum value of C," HH for fish i andy"; i and j denote the location of fish as received by the portioning line (gm ) 2 Xlll CWj(h) Can weight as a function of the portion thickness (gm) Dj, Normalized average diameter of the backbone of fish (-) Hfix), H (x) Height and internal cavity height functions, respectively, of fish body (cm) H (X), HJX) Normalized height and internal cavity height functions, respectively, of fish c f body (cm) Ufa* W/a Height and width, respectively, of fish body at the anal feature point (cm) Hj, Tj Binary variables representing the fish orientation (-) h Fill height of a can h* Optimal portion thickness of can i (cm) h Maximum allowable value of steak thickness (cm) h Minimum allowable value of steak thickness (cm) L Total length of the overlapped fish chain (cm) max min L Fork length of a fish (cm) / Length of a fish (cm) /, Length of fish i (cm) l Scaled fish length m Number of objects (e.g., fish) per batch (-) n Number of portions per object (-) q Number of packages per batch (-) Ts Normalized thickness of fish skin (-) TW Target weight of can (gm) k Si xiv V Volume of fish fillet (cm ) W Weight of fish fillet (gm) w'(x) Total weight distribution function of the overlapped fish chain (gm.cnr ) w*(x) Integrated weight distribution function of the optimal overlapped fish chain 3 1 (gm) Wf(x), W (x) Width and internal cavity width functions, respectively, of fish body (cm) WfiC), WJX) Normalized width and internal cavity width functions, respectively, of fish c body (cm) Wy Weight of portion i from object j (gm) w'j(x) Weight distribution function of fish j (gm.crrr ) w'j(x) Estimated weight distribution function of fish j (gm.cnr ) w' Ideal (target) value of fish weight rate (gm.cnr ) 1 1 1 a 'min> 'max Upper and lower bounds for acceptable weight rate values (gm.cnr ) w' j(x) Scaled weight distribution function of fishy (gm.cnr ) w w 1 S x, x, x a p 1 mh Positions of the front point of pectoral fin, minimum height at the tail side, and the anal feature point, respectively (cm) x Portion position for can / as measured along the overlapped fish chain (cm) x , x, Positions of head cut and tail cut, respectively (cm) Xj Position of fish / along the overlapped fish chain (cm) X/j Position of cutting surface plane i for fish j (cm) ci h XV x) Position of fish i relative to the preceded fish (cm) Binary variable for assigning the overlapped fish pair, i and j (-) y£ Binary variable for assigning the overlapped fish pair, i and j while both h having head forward (-) y Binary variable to assign portion i from object j to package k (-) a,, P, Scaling factors for weight distribution function and length of fish (-) p• Density of object j (gm.cnr ) p Average density of fish body (gm.cm") p(x) Cross-sectional density function of a fish (gm.cm") P m ' Ph P.s Density of muscle, bone, and skin, respectively, of fish (gm.cm") y(x) Non-dimensional density function of a fish (-) ijk 3 3 3 b, 8 h f 3 Tolerances on head cut position and tail cut position, respectively, of fish fillet (cm) Ce> C/Z' Cs Elongation, flatness, and slenderness factors, respectively, of fish body (-) XVI Acknowledgment First, I wish to express my sincere gratitude to my supervisor Prof. Clarence de Silva for his constant encouragement, patience and delightful guidance throughout my research. Also, I wish to express my appreciation to Dr. Elizabeth Croft for her good advice on my research work. I would also like to thank all my colleagues in the Industrial Automation Laboratory (IAL) and all other friends for their help and discussion. Grants from the Natural Sciences and Engineering Research Council of Canada through a Chair in Industrial Automation, B.C. Packers, Ltd., and the Garfield Weston Foundation, held by Prof, de Silva are gratefully acknowledged. Last, but not the least, I wish to thank my family; my wife Fatma and my children Mohammed and Malick, for their understanding, encouragement and patience throughout my M.A.Sc and Ph.D. programs. XVII Chapter 1 Introduction Material wastage problem is a great concern in manufacturing and process industries and has a direct impact on process efficiency, cost, and productivity. In the present thesis, wastage refers to the loss of raw material during the process of preparing portions of raw material for filling into cans or other packages. The problem of material wastage, which primarily represents a loss of revenue, arises in the processing of such material as sheet metal, glass, wood, textile, leather, and food. In the processing of biological material such as fish, the wastage is also related to live-stock management and can have significant environmental and social effects. Except in food processing the problem of material portioning is usually referred as the cutting stock problem and sometimes the geometric packing or nesting problem [1]. The goal here is to find the best way of grouping or nesting some desired shapes of material that will yield the best utilization of the raw material. In the case of food processing the 1 Chapter 1. Introduction 2 portioning of products or raw material is often referred as minimum wastage problem, and the objective is to minimize the degree of overfill or underfill of the packages. In any type of portioning problem the solution usually has to satisfy certain constraints related to the process goal and strategy. The reduction of overfilling in packages is important from the point of view of revenue loss, while the reduction of underfilling is governed primarily by regulation requirements and customer satisfaction. In all these situations, however, the goal can be formulated as an optimization problem where a cost function may be defined in terms of optimization parameters, and a set of constraints may be specified. The solution method generally depends on the degree of complexity of the problem. Factors such as mathematical modeling, computational speed, and degree of nonlinearity of the problem greatly influence the choice of the solution method. In general a mathematical programming approach is preferable when a mathematical model is feasible, the level of nonlinearity is low, and the computational speed is not a concern. However, if mathematical representation is difficult other techniques such as simulated annealing, genetic algorithms, or heuristic methods may be used [2,3]. Optimization problems that require an on-line solution pose significant challenges especially when application to fast production processes is envisaged. The randomness in the size and shape of incoming raw material increases the complexity of the problem. A practical example of this type of problem is the optimal food packaging process. Food in this context includes items of moderate to large size such as vegetables, fruits, poultry, meat, and fish. Depending Chapter 1. Introduction 3 on the process goal and the end market, these food items may have to be portioned (i.e., grouped into target packing portions) before packaging. In this process, typically, the overfill should be minimized while the package portion should not be less than a specific regulatory limit. The research presented in this thesis deals primarily with food types that require portioning before packaging. The process that is investigated is the weight-based portioning for packaging of such food items as poultry, meat, and fish. Structural properties and processing information of the material are useful in solving this complex optimization problem. In particular, the weight distribution and the shape of the processed material may be required. 1.1 R e s e a r c h O b j e c t i v e s The main objective of the present research is to develop an industrially feasible method for optimal portion control of natural objects. Here, optimal portioning is intended to mean the process of cutting incoming objects in a production line into pieces and grouping them according to a suitable optimal criterion, to form packages of a specified target weight or shape. The main goal, therefore, is to develop a general model for the problem of optimal portion control and then apply it to a specific food processing task. This will require facilitation of the acquisition of knowledge about the structure of the processed object, and enhancement of procedures of the optimization model to meet practical processing specifications. Accordingly, the development of a method for fast and on-line extraction of complex processing information of the processed object using conventional sensors is an important sub-goal of Chapter 1. Introduction 4 this research. Evaluation of the developed technology through statistical analysis of the optimal portioning process using computer simulations using real data, is another sub-goal of the work. 1.2 A p p l i c a t i o n of O p t i m a l P o r t i o n C o n t r o l i n F i s h P r o c e s s i n g 1.2.1 Motivation The salmon processing industry is economically important for many regions in North America. For example, in the province of British Columbia, Canada, the annual wholesale value of salmon products is about $580 million, and 25% of this figure is related to canned salmon [4]. Due to dwindling salmon stocks there exist serious concerns of fishery management. In view of increased cost and restrictions of harvesting, market price of salmon is on the rise. Also, the competition with overseas fish processors is becoming increasingly fierce. The fish processing industry has to consider efficient and cost-effective processing techniques in order to meet the associated challenges. In particular, it should reduce the wastage of meat segments of fish during processing, and simultaneously address the consumer desire for quality, variety, and low cost. In view of this situation, technology innovation in the canning process of fish (salmon), which accounts for a major share of the overall processing operations, is desirable. The existing canning systems by and large use fixed machinery that are dedicated only for the canning process of a single species of fish, which is salmon in the provence of British Columbia. These machines are rather outdated, somewhat slow, inflexible, and tend to be inaccurate. Chapter 1. Introduction 5 Also, the salmon processing industry is seasonal and the operation is limited to about three months in a year. Under these circumstances it is not economical to maintain a trained labor force on a year-round basis. On the other hand, there is no guarantee that the same trained workers will return to work in subsequent seasons, on a part-time basis. All these factors contribute to increased production cost. It follows that a fast, accurate, and flexible canning system that can be used for processing two or more products with minimal changeover times and minimal wastage would be a significant benefit. In addition to filling accuracy, the filling presentation (visual quality) is also unsatisfactory in the existing can-filling machinery. Extensive repatching of cans is labor-intensive, slow, and costly. Design limitations of the existing machinery present obstacles for high-speed operation, thereby limiting the throughput. These machinery cannot be modified in an economical manner, so as to resolve the existing problems as outlined in this section [5]. In view of the shortcomings of the existing technology, an entirely new, flexible, accurate, and fast approach for the can-filling process is investigated and developed in the present research. 1.2.2 A n Innovative C a n - F i l l i n g System Research in the Industrial Automation Laboratory at the University of British Columbia aims to develop innovative technology that is applicable in automated processing of fish. In this realm, the present thesis addresses the aspect of can-filling automation. The motivation of the research has been the problems of existing technology, as outlined before. The application of Chapter 1. Introduction 6 the optimal portioning method that is developed in the present work is expected to result in significant improvements in canning operations; particularly, achieving higher production rates (about 500 cans per minute), improved weight accuracy of filling (within ± 5%), excellent presentation or aesthetic quality of the product (no skin or bones appearing at the top of the fill), minimal wastage, and incorporation of process flexibility (e.g., capability of handling different sizes and shapes of cans and various species of fish). In addressing these considerations, a new design for an automated can filling system is considered, which involves dividing the can-filling process into the following three steps: 1. Pre-filling step: This step includes arranging the fish and cutting them into steaks of optimal size, and if necessary, grouping two or more steaks to accurately form the can-filling portions. 2. Filling step: Filling the cans with pre-weighed portions. 3. Post-filling step: Automatic inspection for product quality (presentation and weight) and carrying out product repair (e.g., patching for weight compensation, removal of skin and segments that protrude from the can opening). This scheme will allow better control of each process action (measuring, cutting, forming, and filling) by separating and individually monitoring them. The process starts by estimating (sensing) a weight distribution function for each fish. Then, fish are optimally arranged and sliced into steaks according to a suitable optimality criterion. Each filling portion is then sent to the filler on a conveyor belt. At the filler, a portion of steaks is first enclosed into a filling Chapter I. Introduction 7 compartment by a forming mechanism, and after forming into can shape, it is gradually pushed into a can by means of a plunger. The quality and weight of canned portions will be monitored in the third step using for example, a vision system, load cell, and possibly fillheight sensor. The cans that do not meet the quality requirements and weight specifications will be transferred to a patching unit. The patching unit will consist of intelligent, autonomous and intelligence-assisted workcells. The defect type will determine the workcell to which a defective can should be sent. A schematic diagram of the overall system is given in Figure 1.1. The research presented in this thesis focuses on the first step, particularly on the application of optimal portion control in the pre-filling step. Control Conveying Weight Distribution Estimation Optimal Grouping and Flexible Cutting Automated Filling Post-Filling Inspection and Repair ttt Sensors Figure 1.1 Schematic Representation of an Automated System for Fish Canning. 1.2.3 O p t i m a l F i s h Portion Control An optimal portion control technique is developed for application in the automated can-filling process of fish. The starting operation of the system includes scanning of fish using simple online sensors such as a laser/vision module and a load cell, and utilization of knowledge about the fish structure, to determine the weight distribution of each processed fish. The weight Chapter I. Introduction 8 distribution of a fish is a complex piece of structural information which cannot be determined through computer vision alone. To facilitate the on-line measurement process, fish models are developed off-line using prior knowledge about fish structure and actual data of both weight distribution functions and simple geometric attributes that can be correlated to the weight distribution, for batches of fish. The chosen geometric attributes should be easily measurable on-line using a laser/vision system. In the process line then, the geometric attributes of each incoming fish are measured and matched to a fish model, which includes a weight distribution function. This amounts to model-based (high-level) sensing of the weight distribution of each fish in the process line. The measured weight distribution functions of the incoming fish are fed to an optimization solver to determine the required optimal arrangement of the fish for the portioning process. The fish are arranged accordingly and cut into optimal portions for can filling. The process should be capable of carrying out on-line at a sufficiently fast speed to accommodate a production rate of about 500 cans per minute. 1.3 R e s e a r c h A p p r o a c h First, a mathematical model for the general portion control problem is developed. It is generally not possible to solve such a model in a closed form due to the fact that each application has specific constraints and requirements and that process information (e.g., fish data) is quite complex. The process requirements and constraints are defined by the specific strategy of portioning/packaging. In view of the infeasibility of solving the general problem of portion Chapter 1. Introduction 9 control, the present research will concentrate on the can-filling process of fish as a specific application. However, it should be clear that the overall procedure is applicable to any portioning problem in the particular class. The research focuses on two main problems: estimation (measurement) of the weight distribution of the processed object (fish) and solution of the portion optimization problem. 1.3.1 Estimation of the Weight Distribution Function As stated before, in the optimal portioning process, first the weight distribution of the processed object is estimated/measured. Since the weight distribution function is quite complex and cannot be measured on-line using a conventional sensor, the model-based approach that was outlined previously is employed. Specifically, simple on-line measurements on each fish in the process line together with prior knowledge about the fish are employed. The on-line measurements are representative features of a fish, which are fed into a knowledge-based system containing multiple models of fish weight distribution functions, which are developed off-line. The knowledge-based system is used in this manner to identify the model that matches the particular fish in the process line. The primary information that is contained in the model is the weight distribution function of the representative fish. The weight distribution function is expressed in a parametric form. The parameters of the weight distribution functions and corresponding models are generated by off-line analysis of the structure of fish and using fish data that are collected on batches of representative fish that cover the entire spectrum of operation of the industrial can-filling system. Chapter I. Introduction 10 1.3.2 M o d e l Refinement and Optimization The general model of the optimization problem associated with portion control is refined first to suit the specific application. Additional constraints are introduced to reflect the requirements in a typical industrial fish portioning process. The model refinement starts by developing a mixed integer nonlinear programming (MINLP) model. Through mathematical analysis the model is simplified to a two-stage optimization problem consisting of nonlinear programming (NLP) and nonlinear integer programming (NIP) problems. Further simplifications and refinements of the model are carried out by analyzing results of actual data on fish. The overall portioning model is further simplified to a two-stage optimization problem now consisting of an N L P problem and an integer programming (IP) problem. The solution of the resulting model is computationaly feasible, guarantees global optimality, and can meet industrial specifications. 1.4 T h e s i s O u t l i n e Chapter 2 describes the literature relevant to this research. Included are a review of optimal packaging of food, optimization techniques, and sensor technology. Chapter 3 develops the theory of optimal portion control. First the portion control model is developed for the general case and then applied to the fish portioning process. Chapter 4 describes the method used for the development of the on-line sensor for measuring the weight distribution function of fish. In particular, the procedure for developing the models of weight distribution functions of fish using actual data of fish and prior knowledge about Chapter 1. Introduction 11 fish structure a n d w e i g h t d i s t r i b u t i o n , is presented. C h a p t e r 5 presents c o m p u t e r s i m u l a t i o n and statistical analysis o f the p o r t i o n i n g process for p r o d u c i n g packages. C h a p t e r 6 c o n c l u d e s the thesis, w h e r e m a i n c o n t r i b u t i o n s are h i g h l i g h t e d a n d s u g g e s t i o n s w o r k in the research area. are m a d e f o r further Chapter 2 L i t e r a t u r e Review a n d B a c k g r o u n d This chapter starts, in Section 2.1, with an overview of the existing methods and machinery for food packaging with particular emphasis on the process of salmon canning. Details of the existing can-filling process of salmon, the associated problems, and limitations are discussed. The chapter then outlines the previous research in the area of food packaging with consideration on optimization. The proposed approach for optimal food packaging, as developed in the present thesis, requires research in two areas; namely, optimization and sensor technology. Section 2.2 outlines some optimization techniques that are available in the literature, which may be used in optimal portion control. Section 2.3 gives an overview on advanced sensor technology, as relevant to the present work. 12 Chapter 2. Literature Review and Background 2.1 Food P a c k a g i n g In this Section, existing machinery and techniques that are relevant to canning and packing of food are discussed. Particular attention is given to salmon processing, which is the application emphasis of this thesis. The topic of minimum-wastage food packaging is outlined, indicating related literature. 2.1.1 Filling Methods and Machinery Filling of a specific portion of material into a container or package is a common process in industrial applications. In principle, such a filling operation would use one of the following methods: 1. Time filling; which involves filling the product into containers at a fixed flow rate for a specified period of time. 2. Weight filling; which is used to achieve a target net weight of a package, with some tolerance, by systematically adding small quantities of the product to a container that is initially made to be sufficient under-weight. 3. Volumetric filling; where the product is filled (squeezed) into a measuring jar and then transferred into a container, for example, using a plunger. The first method is mainly used for filling liquid products such as milk, juice, and soft drink. The second method is very rarely used in industry. A few examples such as "Weighmax" [6], which uses the method of weight-based filling, are found. The normal approach here is to have a primary filler and a secondary filler. First the primary filler is used to fill a can 13 Chapter 2. Literature Review and Background 14 sufficiently below the label weight to avoid an overfill, which is uneconomical. The secondary filler will add the required additional quantity into the can, based on the weight deficit as determined by weighing machine. A similar idea has been patented in 1975 [7]. The main advantage of this method is the possibility of achieving a fine filling weight resolution. But, the product presentation could be compromised because the finer adjustments made by adding less presentable material on the surface region of the gross product in the container, will degrade the aesthetic appeal. The third method is commonly used in industry for filling either semi-liquid or meat-like products. The method of volumetric filling can be classified into three subgroups: a) Semi-liquid filling: In this method the product is fed into buckets either by gravity [8] which may be termed "passive filling", or using a pump [9] which may be termed "active filling". Pump filling is fast, and can achieve up to 1200 cans per minute [9], with good accuracy in filling weight. This method is used in the can filling of food products like soups. b) Chunk filling: This method of filling is extensively used in the canning of chunk tuna. Recently, a local fish processing company has started to use it in the can filling of bonelessskinless salmon. An application example of this method is the Carruther machine [10]. The filling rate of this machine is about 250 cans/minute. The main disadvantage in this machine is the high wastage and associated poor efficiency. c) Solid filling: This type of filling is mainly used in the can filling of tuna and salmon. In the pre-cooked form, tuna is firmer than salmon, which makes the former easier to handle and Chapter 2. Literature Review and Background 15 process. An industrial application of this approach is Carruther's solid-tuna filling machine [11]. This machine has a series of buckets arranged in a chain-like manner, which form tuna fillets into circular steaks. The steaks are then plunged into cans. Another machine of this class was developed by Mencacci [12]. The machine first cuts tuna into steaks, perpendicular to the fish backbone, and then transfers the steaks into an open bucket which encloses them for forming into circular portions. Subsequently, a plunger pushes each portion into a can. These two types of machines cannot be used in salmon canning due to the delicate and soft nature of this species of fish. Furthermore, the Carruther machine is unable to provide the desired filling presentation. The Mencacci machine, while capable of producing a satisfactory presentation for the canned product, may not provide adequate operating speeds due to speed limitations of the cutting device. 2.1.2 Process a n d Machines of Salmon C a n n i n g A schematic diagram of the operations that are involved in a typical canning line of a fish processing plant, is shown in Figure 2.1. Fish are "cannery dressed" first by removing their heads using an Iron Butcher machine [13], and then further cleaning by gutting and trimming the tail and the fins. Typically, four workers are needed to feed fish into the Iron Butcher, and one technician to monitor and adjust the machine operation. Feeding (4 People) Cannery Dressing Feeding Feeding Portion Filler (Iron Butcher Cutter Unit (2 to 4 * (2 to 4 and Gutter) People) People) (1 Monitoring (1 Monitoring (2 Monitoring Technician) Technician) Technicians) Inspection and To Seamer Repair • (Patching Table) (4 to 7 People) Figure 2.1 Schematic Diagram of a Conventional Fish Canning Line. Chapter 2. Literature Review and Background Subsequently, the cannery dressed fish are fed into a cutter unit consisting of a row of gang knives (See Figure 2.2). The blades of the cutter unit are equally spaced. Consequently, the cut width of the fish portions is fixed. Figure 2.3 shows the operation of the American Can-Filling Machine [14]. The fish portions are mechanically transmitted through a tunnel and forced into the filler pockets of a rotary-turret filler unit. A tumbler fork mechanism assists in pushing fish portions into a filler bucket. Each bucket has a movable half, which closes while the fish portions are forced in by the tumbler fork mechanism, thereby forming the desired cylindrical shape for can filling. Excessive meat is forced out of the bucket during this forming process, and trimmed off by means of a rotary knife. Empty cans are fed at another end of the filler table, salt is placed in the cans, and are conveyed to locations just underneath filled pockets. The cylindrical portion of fish is then pressed into the can by means of a cam-driven plunger which is synchronized with the rotating bucket. y Fish Portions to the Filler Figure 2.2 A Gang-Knife Machine for Portion Cutting. 16 Chapter 2. Literature Review and Background (I) 17 (II) (III) Figure 2.3 The Main Steps of Operation in the American Can-Filling Machine, (a) Steps are marked as 1 through 4. (b) Details of Step 2. The filling operation of the American Can Filling Machine can be summarized as the following steps (step numbers are marked in Figure 2.3-a): Chapter 2. Literature Review and Background 1. An empty can enters the machine, beneath the bucket, and the plunger retracts to the top of the bucket. The movable jaw of the bucket starts moving to widen the bucket opening. 2. The tumbler fork pushes the steaks from the feeding tunnel to the bucket. The rotary knife starts to slice off the residual portion of fish while the turret rotates and the follower slide moves to close the bucket opening (Figure 2.3-b). 3. The movable jaw closes the bucket. When the bucket arrives at a position of about 45° rotation of the turret from the feeding tunnel, the plunger starts to push the contents into the can below it. 4. In the final step, the can is discharged from the machine after completing almost a full turret rotation. One to two people are needed for the pre-filling inspection and one technician to monitor the operation of the filling machine. Filled cans are transported to the post-filling station for inspection and quality assurance. Here, each can is automatically weighed, and the underweight cans are diverted to a separate line, where weight compensation is carried out manually by inserting pieces of fish into an under-weight can. Also, the filled portions are repaired for aesthetic defects such as "cross packs" where a large portion of skin appears on top of a fill. Other regulatory defects such as overhanging pieces (bone, meat, skin) over the flange of a can, which may result in improper sealing and subsequent health hazards are spotted and manually corrected as well. Quality defects can be as high as 25% [13]. Four to seven workers are needed for the associated "patching" operations. Filled and inspected cans are then ready for placement of lids. Since the typical throughput rate is about 4 cans/s, there 18 Chapter 2. Literature Review and Background 19 is no guarantee that all defects in the filling operation can be spotted and corrected consistently throughout a day's operation, at the patching table. Most canneries in the province of British Columbia, Canada, use the American Can Filling Machine for salmon filling [15]. Another machine, "Troyer-Fox", built by the American company Continental Can, is being used at a few sites, but is no longer available in the market. This machine is also used for salmon filling. The working principle of the machine is similar to that of the American Can Filling Machine, except the plunger motion is horizontal. It is accepted in the industry that the American Can Filling Machine is quite appropriate for salmon steak filling, and consequently this machine is used in most salmon canneries in North America. Even though the performance of the machine is acceptable, it has problems related to the quality of presentation and the filling weight accuracy, particularly at high production rates (e.g., 250 cans per minute). Also, it cannot achieve higher throughput rates due to limitations of its mechanical design. These problems were closely investigated as a preamble to this research. The effect of each moving part on the canning process and the product quality was investigated in consultation with expert technicians of a local fish processing company. It was found that much of the problems were due to the actions of Step 2 (See Figure 2.3-b). The actions are: filling of the bucket (this is a volumetric filling action); trimming of the residual; and formation of the fish portion inside the bucket. All these actions are carried out under the forces exerted on salmon by the tumbler fork and the feeding conveyor. These actions press on the salmon meat and squeeze some of it out through the clearance gaps between movable parts. Also feeding under pressure causes some bones and skin to stick to the edges of Chapter 2. Literature Review and Background 20 machine parts causing jams (machine malfunctions) and flipping of steaks while pushing them into the bucket (cross-packing). 2.1.3 M i n i m u m - W a s t a g e Food Packaging The problem of under-weight and over-weight filling is a matter of concern in the FixedWeight-Fixed-Price (FWFP) packaging industry. Under-weight (underfill) situations should be avoided as they can violate weight labeling laws and other regulatory requirements. Also, they can tarnish the reputation of the food processing company among the consumers. The over-weight (overfill) problem has direct economic consequences. In particular, the cost of the excess product is considered a production loss. Furthermore, factors such as the transportation cost of the extra weight should be considered a loss as well. Besides, the wastage of fish meat has a bearing on the fishery management. In beverage filling the operation is rather straightforward and mostly controlled by filling valves through proper timing. Recently, work has been reported on the use of vision sensors in conjunction with a knowledge base to achieve a precise filling height [16]. In most can filling processes the filling portion is controlled, either manually or automatically, by manipulating the product flow into the can and/or by adjusting the size of the filling pockets. In the packaging of fresh produce such as fruit and vegetable, fixed-portion packaging is quite difficult as it may not be desirable to cut produce items in order to avoid overfilling and underfilling. The problem can be more severe in the case of large fruits such as grapefruit. In such cases variable-weight labeled packaging is the inevitable choice. Chapter 2. Literature Review and Background 21 In 1980, a computer controlled packaging machine was developed in Netherlands by the company, Zakkencentrale B.V. [17]. The machine, named "Computerpak", is still commercially available and is distributed in North America by Tomac Corporation. The machine incorporates load cells for weight measurement of product items. The individually-weighed items are retained within the machine while the machine computer chooses the items that will make the desired package weight, within a specified tolerance. The machine packs 25 bags (5 lb bags of orange) per minute. No information is available on the grouping algorithm that is used in the machine. In particular, it is not known whether the selection is based on an optimal criterion. The machine has been used in Florida's fresh citrus packaging industry. A packaging strategy of this type may be modeled as a binary programming problem or more specifically as a knapsack problem. Solution schemes for this problem are available, but the associated processing time can be too long for on-line processing, particularly for large-scale problems with hundreds of variables. Extensive cost analysis studies have been carried out on Computerpak by Miller, Muraro, and Wardouski [18-20] on that basis significant cost savings have been reported. The machine is known to reduce the labor requirement in the packaging process, and it is also claimed to significantly reduce the degree of overfill compared to what is typical in a conventional packaging process. In this context, a conventional packaging process is to fill a bag with items until the labeled weight is satisfied regardless of the size of the last item. In 1990 Khodabandehloo reported a system for FWFP packaging of chicken. The system Chapter 2. Literature Review and Background 22 packages chicken portions of a particular type to meet a predetermined yet fixed weight [21]. The objective therein is to maximize productivity and minimize excess weight per package or tray. The method first chooses the number of trays to be filled, and then weighs an incoming chicken portion and assigns it to a tray according to the following strategy: First fill the tray that has the least deviation from the target weight, but would reach that weight with least overfill upon adding the present item. If this cannot be achieved, try the second least deviation, and so on. After considering all the operational trays in this manner, if a successful fill could not be achieved, then, the item should be added to the tray with the maximum deviation from the target weight. Simulation results of this logic, using normally distributed data for chicken breast fillet (mean = 101 grams and standard deviation in the range of 5 - 26 grams), have been reported. The results have shown good product savings compared to what would be possible from a random filling process (e.g., pick up any three pieces randomly). Nothing has been reported on the simulation time and whether the filling logic corresponds to an optimal criterion. In a work reported by Jacobs [22], an image processing system with a CCD camera and structured laser light is used to estimate object volume. A water jet cutter is then used to cut the object into equal-volume (weight) portions. The method assumes homogenous objects where volume can be determined from the shape of the visible top surface. Although this method would produce equal weight portions, it does not attempt to reduce the overall wastage by reducing the overall leftovers. It is concluded that the main objective here is Chapter 2. Literature Review and Background 23 customer satisfaction by having equal and exact portions. This method is limited to objects having dome like (convex) top surfaces with no hollow parts inside. The bottom surface is assumed to be flat. 2.2 O p t i m i z a t i o n T e c h n i q u e s Optimization can be defined as the process of regulating the control variables (manipulated parameters) to find the values that accomplish the best possible outcome of a desired objective. In the absence of systematic approaches the optimization is done by trial-and-error or by altering one control variable at a time while retaining the rest constant. Such methods are neither fast nor efficient in finding the true optimum. However, many efficient techniques are available for either a single problem or a general class of problems. This section gives an overview of some of the available optimization techniques with emphasis on those that may be used in the optimal portion control problem. The present research is not intended to develop an entirely new optimization technique but rather to facilitate or extend the use of existing methods for solving the portion control problem. 2.2.1 M a t h e m a t i c a l P r o g r a m m i n g Mathematical programming is a class of tools for solving optimization problems. The problem of mathematical programming is one of finding the minimum or maximum of a real function of real or integer variables, subject to a set of constraints on the variables. Four types of mathematical programming problems are relevant in the present work and are discussed below. Chapter 2. Literature Review and Background 24 2.2.1.1 Linear Programming (LP) In using linear programming (LP) to solve an optimization problem, one attempts to maximize (or minimize) a linear objective function of the decision variables, which must conform to a group of constraints of linear equations and/or linear inequalities. The standard form of the LP problem is given by -T- maximize (or minimize) f(x) = C x such that A x = B T ( ) 2>1 x>0 Matrix A and vectors B and C have known coefficients. These coefficients are parameters of the optimization problem. The LP method has been used to solve optimization problems in industries, finance, and transportation. About 50 years ago George Dantzig introduced an efficient method, the simplex algorithm, for solving linear programming problems [23]. Later in 1984, Karmarkar developed a more efficient method named after him as Karmarkar's method for solving LPs. These methods represent the bases of many algorithms used today for solving LPs. The present research uses LINDO software, which uses a modified version of the simplex method [24]. The simplex method can be viewed as moving on the boundary edges of the feasible region. The optimal solution is then a solution such that no adjacent solution would lead to a better value for the objective function. The simplex method guarantees a global optimal solution as the feasible region for any LP problem is a convex set [25]. Chapter 2. Literature Review and Background 25 2.2.1.2 Integer Programming (IP) An integer programming (IP) problem is an LP problem in which some or all variables are required to be non-negative integers. If only some variables are integers, then the problem is called mixed integer linear programming (MILP or MIP), whereas if all the variables are required to be integers then the problem is referred to as a pure integer programming (IP) problem. In binary MIPs or IPs their integer variables have to be restricted to the values zero and one. Many real life problems may be modelled as integer programming problems. Examples are Traveling Salesperson, vehicle routing, facility allocation, and network design. Branch-andbound method is a general purpose and most widely used technique for solving IP problems. This method finds the optimal solution to an IP problem by efficiently enumerating the points in a feasible region. Clearly, full enumeration of the feasible region guarantees finding the optimal solution; however, the branch-and-bound method does not enumerate all possible solutions, yet still guarantees optimal solution. The method was initiated by Land and Doig in 1960 [26]. 2.2.1.3 Nonlinear Programming (NLP) A nonlinear programming (NLP) problem is an optimization problem whose objective function may not be linear or some of the constraints may not be linear. The NLP problem can be modelled as Chapter 2. Literature Review and Background 26 m a x m i z ie (or m n im i z ie ) f(x) s u c ht h a t g(x)<B (2.2) h(x) = D W h e r e f(x) is a s i n g l e v a l u e do b j e c t i v ef u n c t i o n , x is a v e c t o r of d e c i s i o nv a r i a b l e s , B and D are v e c t o r s of k n o w nc o e f f i c i e n t s , and g and h are i n e q u a l i t y and e q u a l i t yc o n s t r a i n t s ,r e s p e c - tively. T h e r e are s o m es p e c i a lc a s e s of NLP w h e r et h e r e are no c o n s t r a i n t s .T h e s ep r o b e lm s are caled u n c o n s t r a n ie d N L P s . Also, an NLP w i t h l i n e a r g and h is caled a linearly c o n s t r a n ie do p t i m i z a t i o n . If, as well, the o b j e c t i v ef u n c t i o n is q u a d r a t i c ,t h i sp r o b e lm is c a le d q u a d r a t c i p r o g r a m m n ig (QP). T h e r e are m a n ya g lo r t i h m st h a th a v eb e e nd e v e o lp e d for s o l v i n g NLP p r o b e lm s .D e t a i l s s u c h a l g o r i t h m s can be f o u n d in s t a n d a r db o o k s on n o n l i n e a rp r o g r a m m n ig [ 2 7 , 2 8 , 3 0 ] . E x a m p e ls of t h e s em e t h o d s are g o d le n s e c t i o n , s m i p e lx s e a r c h , s t e e p e s t d e s c e n t , q u a s i N e w t o n , and L e v e n b e r g M a r q u a r d t . The c h o c ie of the s u i t a b l em e h to dr e l i e sp r i m a r i l y on the o p t i m i z a t i o np r o b e lm itself. O t h e rf a c t o r ss u c h as d a t as t o r a g er e q u r ie m e n t and r o b u s t n e s s ar c o n s d ie r e d too. N o n n i le a rp r o g r a m m n ig t e c h n q iu e sc a n n o tg u a r a n t e eg l o b a l o p t i m a lu n e ls s f(x) is a c o n v e x or p s e u d o c o n v e xf u n c t i o n and x b e o ln g s to a c o n v e x set in the r e g i o n of i n t e r e s t [37]. The p r e s e n tr e s e a r c hu s e s the golden section m e h to dc o m b n ie dw i t hp a r a b o l i ci n t e r p o l a t i o n for s o l v i n go n e d m i e n s o in a l NLP p r o b e lm s . The m e h to d first r e d u c e s the r a n g ee n c o ls n i g the local m n im i u m (or m a x m i u m ) and t h e n u s e s p a r a b o l i c i n t e r p o l a t i o n to e s t m i a t e the local o p m t i u m [29]. For m u l t i d i m e n s i o n a l N L P s the g e n e r a l i z e d r e d u c e d g r a d i e n t (GRG) Chapter 2. Literature Review and Background 27 algorithm is used. The G R G method converts the constrained problem into an unconstrained problem. The new point in the space optimization parameters is calculated as - Xfr+i = k Xk + aS (2.3) where S is the search direction, which is evaluated using the generalized reduced gradient, a k combination of the gradient of the objective function and a pseudo-gradient derived from the equality constraints. A search direction is found such that any active constraint remains exactly active for some small move in this direction [30]. 2.2.1.4 Mixed Integer Nonlinear Programming (MINLP) A n M I N L P problem is an N L P problem in which some variables are constrained to be binary. It should be noted in this context that any integer variable in a defined interval can be replaced by a set of binary variables and a constraint. Key applications of M I N L P approaches are found in the area of design, scheduling, and planing of batch processes in chemical engineering [31]. Other applications of M I N L P include optimal unit scheduling in an electric power system [32], electric network topology [33,34], product design [35], and leather processing [36]. There are some algorithms that have been developed for solving M I N L P problems. Examples of these algorithms are outer approximation, feasibility approach, generalized cross decomposition, and branch and bound, a description of which and the underlying principles are found, for example, in Floudas [37]. The application of these algorithms to solve an M I N L P problem with hundreds of variables and constraints will require an extensive computational effort, and hence they have been primarily used in off-line applications. Chapter 2. Literature Review and Background 28 Two difficulties are associated with M I N L P problems; namely, the combinatorial domain (the binary variables) and the continuous domain. As the number of binary variables increases the problem becomes a large combinatorial problem, which could be characterized as N P complete problems [38]. These problems are nondeterministic polynomial-time (NP) problems, in the sense that the time required to reach an optimal solution may grow exponentially with the number of variables. Also, the nonlinearities of the M I N L P problems are in general non-convex, and the global optimization of an N L P problem can be NP-hard, where NP-hard problems are at least as hard as NP-complete problems [39]. In this research Lingo software is used for solving the M I N L P problems [24]. Lingo uses branch and bound approach which is the same approach that is used in solving M I P except that in each subproblem one has an N L P problem rather that an L P problem. For the N L P subproblem, Lingo uses the generalized reduced gradient algorithm. 2.2.2 Global Optimization Global optimization is the task of finding absolutely the best set of decision variables to optimize an objective function. A local optimal solution in linear optimization or convex nonlinear optimization is indeed the unique global optimal solution. However, in general nonlinear optimization problems, multiple local optimal can be found and the global optimal is the best one of them. Consequently, the global optimization problem is usually difficult to solve. A n obvious solution procedure is to use any local search algorithm and start from several points distributed over the entire search. This procedure is normally not practical and Chapter 2. Literature Review and Background is considered an inefficient global search. In general global optimization algorithms can be classified into deterministic methods and probabilistic methods. Deterministic methods use a procedure that is guaranteed to reach the global optimal. Examples of these methods are branch and bound and interval analysis [40,41]. Probabilistic methods use a random factor and rely on a statistical argument to prove their convergence. Typically, stochastic methods are applied to unconstrained problems. The main disadvantage of these methods is that they do not guarantee finding a global solution; however, they often reach a global optimum or a near optimum. Examples of these methods are simulated annealing, genetic algorithms, and clustering techniques [2,3,42,43]. 2.2.3 R e a l T i m e Optimization Real time (or on-line) optimization is an optimization problem that has to be solved on-line within a limited time interval, in synchronism with a physical process. In this type of problems the optimization model is usually fixed and the values of its parameters are determined by on-line measurement of an appropriate set of system parameters. For solving small-scale problems with relatively moderate operating speeds, the currently available computational hardware and standard processing algorithms may be adequate. An example of implementing an integer programming algorithm for on-line optimization of a power distribution system has been proposed by Roytelman, et al. [44]. The algorithm was used to optimize within seconds the power demand and losses for a distribution subnetwork containing 399 29 Chapter 2. Literature Review and Background 30 feeder sections and 318 transformers. Analog circuits have been used for solving optimization problems for their speed advantages over digital computing. Cichocki and Unbehauen used switched-capacitor architectures for on-line solution of nonlinear optimization problems [45]. Urahama implemented an analog circuit based on probabilistic relaxation and Hopfield neural network for an elementary combinatorial optimization [46]. Jelonek et al. have used an analog-circuit technique based on the simulated annealing algorithm for real-time global optimization [47]. It has been noticed in these approaches that the size and type of optimization problem can limit the implementation of analog-circuits for its solution. Moreover, none of these techniques have been used in mixed integer programming problems. Lustig and Rothberg used the advantage of parallel processors and developed an implementation strategy for a linear programming solver on a parallel computer [48]. Their results show a reduction in processing time by up to a factor of ten by using 16 parallel processors instead of one. These parallelization techniques are still in their early stages of development and are costly in general. Also, the problem type will have a considerable influence on the associated solution time. 2.3 S e n s o r T e c h n o l o g y A sensor can be viewed as a device or system that incorporates some element or mechanism whose internal behavior and response are conditioned by a variable that needs to be obtained (the target variable). Sensors vary from simple conventional measuring devices to complex Chapter 2. Literature Review and Background and intelligent ones. Conventional sensors are general purpose measurement tools, and their internal mechanisms can be easily modelled and designed. Examples of conventional sensors are thermocouples, strain gages, proximity sensors, photoelectric sensors, laser sensors, and C C D cameras [49]. Complex sensors are those that integrate conventional sensors with complex signal processing hardware and software. Complex sensors are usually special purpose devices and may include knowledge-based or pattern recognition tools. Examples of complex sensors are modern medical imaging systems such as computed tomography (CT) and magnetic resonance imaging (MRI) [50,51], gas-mixture measurement devices [52], bread fermentation sensor [53], and water pollutant characterization system [54]. Different types of complex sensors are described in the proceedings of the International Society for Optical Engineering [55]. The optimal portioning technique that is developed in the present work relies on the measurement of density variation along each processed object. Three-dimensional (3D) measurement of density variation is possible using techniques similar to those used in modern medical imaging; for example, computed tomography (CT), positron emission tomography (PET), and magnetic resonance imaging (MRI) [50,51]. Rheingans and Nichols used an M R I system to create a 3D visualization of the anatomy and internal tissues of fish [56]. A strong linear correlation between CT numbers (gray levels of CT image) and material density has been reported by many researchers [57-59]. Although, these techniques are suitable for measurement of the density variation of an object, they could be expensive and slow for on-line processing applications. 31 Chapter 2. Literature Review and Background 32 On-line measurement of properties of a complex object may be achieved indirectly by measuring simple on-line features that potentially have a good correlation with the target property. The correlation, if exists, can be extracted through off-line analysis of measurement data of the target property together with a simple set of representative features. The problem becomes straightforward if a direct relation between the measured features and the object property can be established. However, if such a relation is practically unachievable, techniques such as pattern recognition and fuzzy logic may be used in realizing a high-level correlation. Gamage and de Silva used a vision sensor in conjunction with a rule-based system to estimate cutting contour profiles for fish, in a robotic head cutting process [60]. Their system uses a fuzzy logic technique to match simple on-line measurements with a suitable cutting contour profile for the fish under processing. The cutting contours were generated offline and stored in the system. With this review of the background and relevant literature, the task of theoretical formulation and modelling of the research problem is undertaken in Chapter 3. Chapter 3 T h e o r y of O p t i m a l P o r t i o n C o n t r o l In this Chapter, several models are developed for optimal portion control, with specific application in the canning process of fish. First a model that is quite general is developed and the difficulties of optimizing and practically implementing such a model is pointed out. Next, the model is made specific to a particular approach of cannery processing of fish. Practical specifications of process speed require fast computational techniques. The model is further refined to achieve such practical goals. Further practical enhancements are made to the model where bounds are introduced to the height of the canned portions. Extensive evaluations and comparisons of the developed techniques are made using data on real fish. 3.1 I n t r o d u c t i o n In the context of the present work, portion control is the procedure of controlling the quantity 33 Chapter 3. Theory of Optimal Portion Control 34 of a product that goes into a package or container. Portion control may be applied to the packaging process of food items such as meat, fish, and poultry. Different sizes and shapes of packing containers may be involved. In optimal portion control the goal is to optimize the packaged portion according to a suitable optimality criterion. It may be achieved, as developed in this thesis, in the following manner. First the weight distribution of the processed object is estimated, then a group of objects is placed according to the optimality criterion, and this group is cut into optimal portions along some cutting surfaces. Generally, the cutting surfaces are optimally positioned in the object group so as to minimize the overfilling and underfilling, while satisfying a required set of constraints in consistent with some packaging strategy. This chapter presents a general formulation of the portion control process. A s a case study, the formulation is applied to a fish canning process. The portion control model is further developed and refined to improve the optimization procedure in order to satisfy practical process requirements of fish canning. 3.2 General Formulation In portioning of food items, typically, the cutting process is carried out as a sequence of steps; first performing primary cuts, then secondary cuts, and so on, depending on the nature of the processed objects and the desired properties of the final product. Under these conditions, the cutting surfaces can be considered as non-intersecting surfaces within an object. Cutting according to predetermined profiles of cut surfaces, is essentially a process of volumetric Chapter 3. Theory of Optimal Portion Control 35 portioning. But, as typical in food packaging, portion control has to be accomplished by weight. Then, in order to establish the optimal positions of the cutting surfaces, according to some weight optimization criterion for the cut portions, the density function of the processed object will be required. The density function is a single-valued function that is defined over the entire volume of the object, and represents the local weight per unit volume at any point in the object. It may be expressed as a function with respect to a cartesian (xyz) body frame, as shown in Figure 3.1. 3.2.1 Problem Formulation Consider an object denoted by j that is subjected to a cutting process, as shown in Figure 3.1. The weight of portion i in object j may be expressed as (3.1) where P (> > ) is the density function of object j. Also, V,-.- is the volume of the object x v z portion separated by the cutting surfaces S^.iy and 5,y. The basic goal of the optimal portioning problem is to determine the cutting surface parameters that minimize both overfill and underfill in the packages. Mathematically this goal may be written as (3.2) while Chapter 3. Theory of Optimal Portion Control 36 • • H Portion /' Figure 3.1 Cutting Surfaces on Object/ Q g e (3.3) where, Yyyte = 0 or 1, and is a variable used to assign the portion i from the object j to the package k of type e. n = maximum possible number of portions that can be generated from any object. m = total number of objects considered in each optimization process. q = maximum possible number of packages of type e. Q = total number of package types. e TW = the target weight for package type e. e The parentheses in the objective function enclose the deviation of the weight of each package from the target value TW . T h e constraint (3.3) is required to assign each portion to one e Chapter 3. Theory of Optimal Portion Control 37 package only. The number of packages q is selected based on some production plan, and this number is e bounded according to Q m £<7 x7W <£w, e « (3.4) e j where Wj is the weight of object j. Other constraints may be introduced to handle the requirements of a specific packaging process. These may include constraints on size, volume, and portion placement. Even though the main goal is to optimize the filling (net) weight of a package, other indices including qualitative ones may be included in the objective function that is optimized. The type and significance of these indices depend on the specific product and process. A practical example for optimal portioning is provided by the process of cutting beef loin or sirloin sections to generate steaks for packaging. Each package may contain one, two, or three steaks, yet the total weight of each package should not deviate significantly from a fixed target. The packages may be of different types; e.g., 7W, = 1 lb and TW = 2 lb. In this 2 example the cutting surfaces are planes. An additional constraint is required to set the allowable minimum and maximum thicknesses of the produced steaks. For a typical portioning process, the general formulation of the optimal portioning problem may be slightly modified to accommodate the needs of the specific application. In extreme cases, major modifications might be required to achieve a feasible solution. However, in any Chapter 3. Theory of Optimal Portion Control 38 portioning application, the main objective of optimization in general would be to minimize the total overfill and underfill. 3.2.2 Model Development The formulation of the optimal portioning problem, as described in the previous section, is a mixed integer nonlinear programming (MINLP) problem. Large and complex models that are formulated in this manner may not be computationally tractable. Often the computation time that is needed to reach a solution would be far excessive, thereby making the approach unsuitable in practice. If this general formulation is not directly solvable due to computational limitations, the portioning process should be re-modeled by introducing reasonable assumptions and constraints that are appropriately defined for the specific type of product and portioning process. The new model should be checked again for feasibility. The process of model refinement should be continued in this manner until a feasible model is achieved. A schematic diagram that represents the model development procedure is given in Figure 3.2. 3.3 Cannery Portioning of Fish It is clear that the general portion control problem as formulated before, cannot be completely solved unless it is applied to a particular packaging process. Next, the general theory of portion control is applied to the process of fish canning. The problem is formulated by giving details of the specific development procedure of an optimal model for the fish portioning process. Chapter 3. Theory of Optimal Portion Control 39 P r o b l e m Formulation I ^* M o d e l A n a l y s i s and Solution r Feasibility C h e c k for A d d i n g E x t r a Constraints and Re-modeling M e c h a n i c a l D e s i g n and M o d e l " Not Computation T i m e Feasible Feasible Accept M o d e l Figure 3.2 A Schematic Diagram of the Model Development Procedure. 3.3.1 Fish Portioning Model First the general portioning theory that has been presented, is applied to the fish canning process. In this application, the objects of interest are cannery-dressed fish. The cutting surfaces are planes parallel to the y-z. plane, as in Figure 3.3. Accordingly, equation (3.1) can be modified as u x ij = JIJP/*'> y w V ' z ) d V= IJ w (x) dx - (3 5) (i-DJ x where w'j(x) is the weight of the fish per unit length, which is termed the weight distribution function or weight rate function. Also, x- is a continuous variable representing the position of ti the cutting plane. Chapter 3. Theory of Optimal Portion Control 40 F i g u r e 3.3 Parallel Planar C u t t i n g Surfaces for F i s h P r o c e s s i n g . C o n s i d e r the case o f fish p o r t i o n i n g for cans o f a specified single size. B y a p p l y i n g the general f o r m u l a t i o n o f the o p t i m i z a t i o n p r o b l e m , a n d u s i n g equation (3.5), the m a t h e m a t i c a l o p t i m i - zation m o d e l o f fish p o r t i o n i n g m a y be expressed as 1 f m n min C = X subject to zZzZ ij ijk-' w k \ j i X yuk * v rw (3.6) (3.7) i k In v i e w o f the d i m e n s i o n a l restrictions o f the cans, the steak thickness o f p o r t i o n e d fish s h o u l d l i e w i t h i n s o m e a l l o w a b l e l i m i t s , o r else the steak t h i c k n e s s s h o u l d be set to z e r o w h i c h c o r r e s p o n d s to n o steak. T h i s r e q u i r e m e n t c a n be e x p r e s s e d b y u s i n g the f o l l o w i n g set o f either-or constraints: U X X 0-Dj - X i j + X ( i - l ) j X . J - X ^ J hmax — + MOCjj h m i n ^ M < X <M(l-a, ) ;/ i j (3.8) Chapter 3. Theory of Optimal Portion Control 41 Here, M is a large positive number and may be chosen as the maximum length of fish, and a,-,is a binary variable, which can take the values 0 or 1. Also, h mjn and h max are the minimum and maximum allowable values, respectively, for the thickness of a steak. Although, algorithms and software are available to solve this optimization problem, they are not suitable in the present application, due to the following reasons: 1. The M I N L P problem belongs to the class of non-deterministic polynomial time (NP) problems, in the sense that the time required to reach an optimal solution may grow exponentially with the number of variables [37]. The number of variables and equations in a typical fish portioning model can be several hundreds. This would make the current optimal formulation rather slow even for off-line computation. This formulation would be practically applicable, however, in processes where the number of portions per object is small and/or the process speed is low (e.g., portioning of chicken or beef). In the present application of fish portioning, fast portioning (typically up to 10 cans/s) will be required. 2. Application of the general portioning model, as formulated above, in cannery processing of fish will require an additional step where the individual portions are grouped to form the can-fill quantities. This would be difficult to achieve at high speeds due to design limitations of mechanical devices that are involved. Consequently, an alternative formulation that is practically applicable in fish canning would be required. Such a formulation is presented next. Chapter 3. Theory of Optimal Portion Control 42 3.3.2 Overlapped F i s h Model An appropriate and industrially feasible portioning process may be realized by overlapping the fish in the longitudinal direction, prior to cutting as shown in Figure 3.4. Then, the order, the orientation, and the degree of overlap of the fish are chosen according to a suitable optimality criterion. This approach will lead to an optimization model that has a fewer number of equations and variables than that for the previous general model. The optimally overlapped fish are cut using planar cutting surfaces, which are placed perpendicularly to the backbones of the fish. Spacing between the cutting planes (i.e., blade spacing of the gang knives) may be arranged in one of two possible ways: fixed spacing and adjustable (variable) spacing. In this section the first arrangement of constant blade spacing is considered. Figure 3.4 The Overlapped Arrangement of Fish. Chapter 3. Theory of Optimal Portion Control 43 The objective function of the present model constitutes minimization of the total squared error of the overall weight distribution (rate) function with respect to an ideal (target) weight distribution, as illustrated in Figure 3.4. The ideal weight distribution is indeed a constant value w'„, and it is given by the desired can weight (target weight) divided by the desired steak thickness which is slightly less that the can height. This optimization model can be expressed mathematically as L min C = j(w\x)-w ) dx (3.9) 2 0 where w \x) ^ = -*,.) + T.wfa + x -x) t (3-10) subject to H +T =] i i (3.11) with H , 7; =0 or 1 i (3.12) and , TW w„=— h (3.13) Note that H and T are binary variables which can assume a value of 0 or 1, and they represent t { the orientation of fish i (H denotes head first, i.e. head pointing to the left, and T denotes tail first, i.e. tail pointing to the left). Also, x is a continuous variable representing the fish t placement along the overlapped arrangement, L is the overall processed interval of overlapped fish, TW is the target net weight of a can, and h is the fill height of a can (blade separation or portion length). Equation (3.10) represents the overall weight distribution function. Constraint (3.11) is used to ensure that only one term of equation (3.10) is used per fish; hence, the same Chapter 3. Theory of Optimal Portion Control 44 fish is not arranged in two opposite orientations. Note that w' {x) = 0 i unless 0 < X< I (3.14) where Z, is the length of the ith fish. If needed, a requirement of no gaps between adjacent fish may be stipulated as well, by (3.15) This formulation also represents an MINLP problem. The size of this modified optimization problem, however, is substantially smaller than before, but it is still not quite suitable for real time implementation, as the solution time can be quite high. It follows that, the formulation needs to be modified further. 3.3.3 Decoupled Overlapped F i s h M o d e l In order to realize practical implementation where there are process constraints and where computational speed is a decisive factor, the optimization model is further refined by introducing an additional constraint on the smallest size of fish that is processed. This constraint, which is quite natural and used in the existing can-filling processes as well, will guarantee that no more than two fish are overlapped at any location along the chain of overlapped fish. Accordingly, the optimal overlap between any two adjacent fish, for a given orientation, will not depend on the configuration of the rest of the fish chain. This fact is mathematically proved now. Objective function (3.9) is written as Chapter 3. Theory of Optimal Portion Control 45 L c = J(vw' (x)-2w>'(x) + min 2 w' )±lx 2 a (3.16) o or L min C = jw' (x)dx -2w' 2 () (3.17) o Now equation (3.10) is substituted, to get (3.18) The second integral term on the right hand side of equation (3.18) represents the weight of all fish, which is a constant value during the process of optimization. Hence, it can be dropped from the objective function. Furthermore, it is quite realistic to assume that none of the previous fish along the chain would extend beyond the last fish. Hence, L is equal to x + l . m m In view of these observations, the objective function (3.18) may be expressed as + 'o ( m w 2 x + m) l (3.19) This may be rewritten as 0 (=1.7=1 X [Hj w'j(x - Xj) + Tj w'j(lj + Xj - x)]dx + 'o( m W X + D (3.20) Chapter 3. Theory of Optimal Portion Control 46 According to the present overlapping constraint, when the weight distribution of a particular fish is not zero at a given location x, then, only an adjacent fish and no others may also have a non-zero weight distribution at that location. It follows that the product terms with \i-j\ > 1 in equation (3.20) will vanish. Furthermore, when i = j the product term in equation (3.20) is simply the square of the weight distribution of fish i, whose integral along the fish chain is a constant, which does not change during optimization. Hence, the terms corresponding to i = j also can be dropped from the objective function. It follows that equation (3.20) can be refined to give the following equivalent optimization problem: 1 m-1 min C" = 2 £ x + X, + 1: ' J [HiW'tx-xd (x-x )+T i+l + Trfdi w/ i+l + w' (x +1 + x + Xi-x)] t -x)]dx +] +1 ) 2 (3.21) Now, a new variable, x\, is defined as the difference in the placement position between two adjacent fish, and measure the level of overlap see Figure 3.5; thus, M X ~ i+i X A i ' X 1+1 Figure 3.5 Relative Placement of Fish. (3.22) Chapter 3. Theory of Optimal Portion Control 47 Then, x can be written as m m X m X + = m- 1 m X X + X m-\ + m-2 X (3.23) zZ 'i+ x i= 1 According to the reference coordinate frame which is defined as in Figure 3.4, it is noted that x, is zero. Next, a change of variable is introduced to equation (3.21), where x - x is represented by the t new dummy variable x'. As a result, and in view of equation (3.22), the limits of integration become x' j+] becomes and /,. Also,'/, + x' becomes /,• becomes x' - x';x - x i+i and - x' ; i+j +x j+l -x m ( in c" = ^ min i, 2 \ [ H y ^ + x ry^-x')] l • w' M'-x'i +] t - x'. Accordingly, equation(3.23) is substituted for x to get M i= +'x - x i+ + ,) +T w' (li i+l i+i + 1 +x] -x')]dx' + + 1 w'Jx'i + j + >2i w (3.24) or, \ fm-l (3.25) + w' l min C" = \i=\ 2 o m J where C; = 2 j [H '{x') + T w' (l -x')]x iW i i i i+i x \.H w' (x'-x' ) i+1 i+1 +T w' (l i+l i+] i+l +x' -x')}dx' i+] i+x + w x' , 2 0 i+l (3.26) This may be rewritten as C'l =H H ,cf + H? H i i+ + T H cf" T T l i+ l + i cf T l+ x cf T l + l (3.27) Chapter 3. Theory of Optimal Portion Control 48 where . C'f = 2 J w.(x)w . (x - x ; r =2 J V V ^ C X O M A +1 + ^ + (+ ,)dx + w / x - + 1 -x')dx' + I w' x' 2 0 i+l (3.28) C ' f " = 2 J w' {l -x')w' i x C'f r i {x -x' {)dx' , i + l i+ 2 , i + l i+ 1 = 2 J wV/j.-JcV'j+iC/j+i x + w' x i+ -x')dx' + w' x' 2 0 i+l 1 Note that only one of the / / and T products in equation (3.27) is unity, the remaining three automatically becoming zero. Hence inclusion of the term w' x'• j in each of the four parts 2 + of equation (3.28) is equivalent to including it just once, as required in equation (3.26). It is seen that the optimization problem is decoupled into 4(m-l) NLP problems, each one consisting of just one continuous variable x' i+[ of optimization. Then, the goal of each uncoupled optimization subtask would be to determine the placement separation of a pair of adjacent fish (x', ) for the given orientation of these two fish. It should be clear that T and T +1 t are not independent variables, and are completely determined by H, and H , j+l M in view of equation (3.11). These uncoupled optimization subtasks can be solved separately, which will reduce the solution time significantly. To avoid the solution of equation (3.25) ml times, it is recast as a nonlinear integer programming (NIP) problem. This would require the solution of equation (3.28) P times only. m 2 Chapter 3. Theory of Optimal Portion Control 49 Now define the overlapped z'th fish as the primary one and the /th+1 fish as the secondary one. Equation (3.28) can be evaluated for all possible permutations a pair of fish can be overlapped (total number of permutations of selection and placement of primary and secondary fish = n P o , where P; J •). A table is generated from equation (3.28) which includes the (i-jV- optimal value of each individual component and the corresponding value of the fish placement separation, x' . The nonlinear integer programming model is i+l m (m ( m V j \ (3.29) min J or min££y /C f i /2, i y (3.30) - y«) W J where C. = H;H C" + H T c"? i j 'J i j IJ + T;H C™ '« j ij H ; subject to ; ; ; + T T.C J J IJ T 1 : (3.31) (3.32) m (3.33) (3.34) « J H i + T =1 t (3.35) (3.36) H„ T. and y.. = 0 or 1 (3.37) Note that equation (3.31) contains the optimal values of the components of equation (3.28), with fish i followed by fish j. Here, i and j denote the original sequence of fish in which they 50 Chapter 3. Theory of Optimal Portion Control are received by the portioning system. Also, y,j is a binary decision variable for overlapping the two fish i and j. Constraints (3.32)-(3.34) are used to insure that each fish is overlapped with one fish from either side except for the two extreme fish which are overlapped from one side only. These constraints force the overlapped fish to form an open chain. It is important to note that the solution of the NIP model that is described in this section may contain sub-loops of fish chains. This problem is similar to the sub-tour problem in the Traveling Salesperson problem [25]. The remedy for this problem is to add an extra constraint that will break the sub-loop. For example, if the fish i,j, k, and e form a sub-loop, the additional constraint will be yij yjk y e y i + + = + k e 3 (- ) 3 38 It should be noted here that the NIP model does not guarantee a global optimal solution because of the nonlinear terms in the objective function (3.30). To guarantee a global optimal solution the nonlinear terms in the NIP model are replaced by linear ones using new variables, which are substituted for a product of assignment and orientation variables. The new variables are defined as follows: y'u = u = y >j i i y H n ij i i y H T yij = yij i j y'u - >u i i. T H T T The assignment variable y j in the linear terms of the NIP model can be replaced by the sum of t the four new variables. This is achieved by combining the equations in (3.39) as Chapter 3. Theory of Optimal Portion Control 51 +y!j) = yiji^Hj + iifi) + 7;// + r ^ o y (3.40) From equation (3.35) it is clear that the terms in the parentheses of the right hand side of equation (3.40) always add up to one. Hence, equation (3.40) is reduced to hh y ht th tl = >•„• + y , / + v l} ( / +y (3.41) ( / Using equations (3.39) and (3.41), the new IP model is given by ( ij ~ c min II i subject to ic"/ hh ht th tt yij yi] y^ w oh) - 'l i) w l (3.42) yij_ j X T - I v-i "V hh ht th tt . . (3.43) hh ht th tt . , (3.44) hh 1 ht th tt hh ht th tt , (3.46) A 3'««»>'»'3'/«»ory . = 0 i| hh ht th j tt , n v, , v, ,y, ,andy = 0 or 1 7 7 7 (3.45) (3.47) y The solution of this model may also contain sub-loops. The problem can be resolved by adding an extra constraint that will break the sub-loop. Here, the orientation is also included in the additional constraint. For example, if the fish /, j, k, and e form a sub-loop, with their orientations such that fish i has head side first, / has tail side first, k has tail side first, and e has head side first, then the additional constraint will be ht v y yjk + tt + th yke + hh ~ yi e = 3 (3.48) Chapter 3. Theory of Optimal Portion Control 52 The solution procedure that is based on the model developed in this section is outlined below: 1. Generate an mXm table containing the solutions of equation (3.28) for all possible combinations of fish. 2. Solve the IP model, equations (3.42) through (3.47), using the data from the generated table, and determine the optimal fish placement (sequence and orientation) from the result, j. hh ht th , tt ing values of y - , y , y , and y- -. i tj tj ; 3. If a sub-loop is produced from the optimal solution, solve again the IP model with an additional constraint that is similar to equation (3.48). 4. Read the corresponding values of x' , for each (ij) cell where the variable y'jj , yf/, y 1 i+l u u or u y . equals 1. This represents the optimal overlapping placement of fish /' as measured H from the leading side (head or tail) of fish i. 5. Arrange the fish chain by overlapping the fish according to their optimal placement. For practical implementation of this model the solution should be fast enough to accommodate the targeted production speed (~ 500 cans/min.). The solution time for different size of fish batches is investigated in the illustrative example that is given in the next section. 3.3.4 Illustrative E x a m p l e Consider a batch of 10 salmon that are to be cut for canning, so as to achieve a target (net) can weight of 115 grams and a steak thickness of 2.4 cm. These represent a realistic set of requirements in the salmon canning industry. In order to apply the optimal procedure outlined in the Chapter 3. Theory of Optimal Portion Control 53 previous section, it is necessary to know the weight distribution function w'j(x) for each fish. The weight distribution functions of the ten fish are measured using the experimental setup described in Appendix A, and assuming that fish fillets have a uniform density. The weight distribution functions of these fish are presented in a matrix form, along with the fish length as follows: A= 7.0e-6 -2.0e-5 -7.0e-5 -1.0e-4 3.0e-5 2.0e-5 1.0e-5 -2.0e-5 -2.0e-5 -8.0e-5 0.0032 0.0043 0.0081 0.0102 0.0026 0.0028 0.0038 0.0040 0.0045 0.0085 -0.2666 -0.2506 -0.3496 -0.3892 -0.3111 -0.3193 -0.3297 -0.2508 -0.2646 -0.3580 4.3506 4.1372 4.8310 4.8370 5.3812 5.3996 5.3744 4.1768 4.2700 4.8200 32.5122 31.0618 38.5512 40.1671 39.4059 39.8100 40.1583 31.2371 32.2487 38.8326 34.5' 40.5 42.2 37.5 34.5 31.5 36.5 39.2 39.5 38.5 (3.49) The first five elements of each row of the matrix give the coefficients of a 4th order polynomial function (the highest-order coefficient given first) representing the weight distribution function, and the last element gives the length of the fish. An example of these functions is illustrated in Figure 3.6. Table 3.1 includes data produced by equation (3.28). A computer code was written for this purpose, which uses the golden section search method [29] to find the minimum values of equation (3.28). Each cell in Table 3.1 contains four pairs of values given column wise, corresponding to the four equations (3.28) taken in the given order. The first value in each pair is the optimal value of the corresponding sub-equation in (3.28) and the second value in the pair gives the corresponding value of x' j+l (the measure of optimal overlap). The row and column numbers of the table depict the primary and secondary fish numbers, respectively. Chapter 3. Theory of Optimal Portion Control 60 0 1 54 I i i i , . 1 0 5 10 15 1 1 r , 20 . 25 . 30 1 35 Position along the fish length (cm) Figure 3.6 An Example of a Weight Rate Function w'(x). Note that overlapping of a fish with itself does not enter into the optimization procedure in view of equation (3.46). The optimal overlapping arrangement of fish is determined by solving the IP problem using the data given in Table 3.1. The computer code, programmed in C language, is integrated with the Lingo software to solve the IP problem. The computer code includes all the steps of the solution procedure mentioned in the previous section. Table 3.2 shows the optimal placement of fish, as determined by the procedure developed here, for the present example. The location in the optimal chain to which a particular fish is assigned, its orientation, and the relative position with respect to the adjacent fish, are given in the table. This optimal arrangement is shown in Figure 3.7. In order to realize a practical implementation, one needs to critically assess the required computational time and the possible production speed from the procedure developed in the Chapter 3. Theory of Optimal Portion Control 55 Table 3.1: The Optimal Values of Equation (3.28) and the Corresponding Values of J C ' , [1000 grams /cm, cm] for the Example Batch of Fish. 2 + 1 Fish N u m - 1 ber 2 4 3 1 70.61,26.05 56.99, 18.26 79.16, 34.50 70.61, 26.05 70.14, 61.16, 79.16, 76.14, 25.71 19.21 34.50 28.45 72.12,27.18 56.78, 17.56 79.16,34.5(1 71.22, 25.91 72.36, 62.03, 79.16, 75.68, 2 89.90, 34.45 74.93, 25.21 92.92, 40.50 83.91,31.71 89.40, 78.52, 92.92, 89.40, 33.86 25.24 40.50 33.86 91.32,36.34 74.35, 24.03 92.92, 40.50 84.48, 31.49 91.55,36.64 80.02, 26.97 92.92, 40.50 89.06, 34.86 3 88.89, 74.45, 96.82, 89.78, 33.61 25.26 42.20 34.88 88.38, 78.25, 96.82, 95.22, 33.19 25.73 42.20 38.04 90.48, 35.02 74.00, 24.33 96.82,42.20 90.48, 35.(12 4 82.57, 68.92, 86.04, 79.24, 32.28 23.44 37.50 30.32 82.17, 73.14, 86.04, 84.67, 31.86 23.97 37.50 33.64 5 70.45, 26.83 58.03, 19.58 79.16, 34.50 72.61,27.68 6 64.38, 52.95, 72.27, 65.79, 7 70.63, 58.15, 83.75, 77.30, 27.68 19.58 34.50 26.83 8 9 10 72.71,27.73 53.56, 17.56 79.16,34.50 66.04, 24.83 70.22, 53.94, 79.16, 68.02, 25.77 16.50 34.50 24.46 70.51,25.99 60.1(1, 18.84 79.16,34.50 74.97,27.51 72.15,27.19 57.01, 18.31 79.16, 34.50 70.57, 26.42 91.62, 37.04 76.38, 27.07 92.92,40.50 83.82, 32.55 91.68, 37.11 78.47, 28.64 92.92, 40.50 84.71,33.79 91.72, 37.15 71.87,25.03 92.92, 40.50 79.41, 30.55 89.48, 33.96 71.64, 23.21 92.92, 40.50 81.28,30.10 89.80, 34.32 77.52, 25.09 92.92, 40.5(1 88.21, 32.99 91.35, 75.00, 92.92, 83.90, 90.73, 35.18 79.5(1, 27.23 96.82, 42.2(1 94.52, 38.25 90.98, 75.80, 96.82, 89.38, 35.62 26.89 42.20 35.43 91.05,35.67 77.80, 28.3(1 96.82, 42.2(1 89.93, 36.51 91.09, 71.30, 96.82, 84.99, 35.69 24.85 42.20 33.44 88.46, 33.27 71.24, 23.39 96.82, 42.2(1 87.31, 33.42 88.78, 33.54 77.23, 25.48 96.82,42.20 94.21,36.94 90.51,35.03 74.49, 25.26 96.82, 42.20 89.62, 35.27 83.74,33.55 68.72, 22.53 86.04, 37.5(1 79.95, 30.48 83.95,33.75 74.13,25.51 86.04, 37.50 83.95, 33.75 84.00, 33.96 69.89,24.91 86.04, 37.50 78.82, 30.87 84.05, 34.02 71.69, 26.36 86.04, 37.50 79.34,31.94 84.09, 65.42, 86.04, 7443, 34.05 22.89 37.50 28.87 82.23, 31.93 65.85,21.60 86.04, 37.50 76.77, 28.85 82.48,32.19 72.04, 23.68 86.04, 37.50 83.69, 32.46 83.77, 69.00, 86.04, 79.07, 33.57 23.47 37.50 30.72 70.05, 26.55 62.61,21.07 79.16, 34.50 77.86, 31.04 71.71,27.73 58.13, 19.19 79.16,34.50 73.31,27.92 71.93,27.87 63.01,21.91 79.16, 34.50 77.12, 30.96 72.09, 58.61, 79.16, 72.09, 28.08 20.52 34.50 28.(18 72.15,28.12 60.1(1,21.65 79.16, 34.5(1 72.52, 29.06 72.19, 28.14 54.18, 18.52 79.16, 34.50 67.73,26.10 70.11, 26.59 55.21, 18.00 79.16, 34.5(1 70.20, 26.28 70.36, 26.77 61.53,20.59 79.16, 34.50 76.96, 29.98 71.74, 58.01, 79.16, 72.36, 27.75 19.66 34.50 28.02 25.04 17.87 31.50 24.72 64.06, 24.79 57.82, 19.64 72.27,31.50 71.03,28.11 65.38,25.81 53.25, 17.60 72.27, 31.50 66.50, 24.97 65.57, 25.94 57.93, 20.36 72.27,31.50 70.28, 28.02 65.64, 26.06 53.22, 18.65 72.27,31.50 65.27,25.12 65.69, 26.10 54.48, 19.75 72.27, 31.50 65.69, 26.1(1 65.72, 26.12 48.81, 16.66 72.27, 31.5(1 60.90,23.13 64.11,24.83 50.25, 16.33 72.27,31.50 63.39, 23.32 64.31, 24.99 56.72, 19.08 72.27,31.5(1 70.14, 27.04 65.41,25.83 52.91, 17.99 72.27,31.50 65.54, 25.06 26.83 19.56 36.50 29.73 70.23, 26.55 62.69,21.03 83.75, 36.50 82.54,33.15 71.92,27.74 58.22, 19.15 83.75, 36.5(1 78.01,29.99 72.14,27.87 63.13,21.89 83.75, 36.50 81.79, 33.05 72.32,28.1(1 58.77, 20.52 83.75, 36.50 76.77,30.14 72.37,28.13 60.28,21.66 83.75, 36.50 77.19,31.12 72.41,28.15 54.33, 18.52 83.75, 36.50 72.41,28.15 70.29, 55.31, 83.75, 74.90, 26.59 17.97 36.50 28.33 70.55, 26.77 61.61,20.55 83.75, 36.50 81.65, 32.07 71.95,27.76 58.12, 19.64 83.75, 36.50 77.05, 30.08 8 78.80,29.16 64.73,21.20 89.94, 39.20 81.01), 30.47 78.30, 28.80 68.65,21.91 89.94, 39.20 86.5(1, 32.66 80.42, 64.36, 89.94, 81.57, 80.67, 30.55 69.75, 23.30 89.94, 39.20 86.13,33.63 80.99, 30.98 65.99, 22.70 89.94, 39.2(1 80.89, 31.29 81.05,31.02 67.92, 24.03 89.94, 39.20 81.78,32.53 81.09, 31.03 61.50, 20.67 89.94, 39.2(1 76.49, 29.29 78.38,28.87 61.57,19.37 89.94, 39.20 78.38, 28.87 78.70,29.11 67.62,21.60 89.94, 39.20 85.31, 31.78 80.45, 30.42 64.75,21.24 89.94, 39.20 80.98, 30.83 9 86.44,32.51 71.57,23.84 90.63, 39.50 81.99, 30.99 85.91,31.99 75.22, 24.09 90.63, 39.5(1 87.50, 33.32 88.01,34.24 71.03, 22.78 90.63, 39.5(1 82.58, 30.84 88.28, 76.62, 90.63, 87.(17, 34.46 25.68 39.50 34.19 88.43, 34.98 73.00, 25.59 90.63, 39.5(1 81.83,31.77 88.49, 75.08, 90.63, 82.67, 35.04 27.08 39.50 32.99 88.53, 68.50, 90.63, 77.43, 35.07 23.55 39.50 29.77 86.00, 32.08 68.31, 21.90 90.63, 39.50 79.39,29.41 86.33, 74.22, 90.63, 86.33, 32.41 23.90 39.50 32.41 88.05, 34.26 71.62, 23.79 90.63, 39.5(1 81.95, 31.35 10 79.75, 30.42 66.19, 22.31 88.33, 38.50 81.33,31.19 79.31, 70.41, 88.33, 86.76, 81.13,31.57 66.00, 21.56 88.33, 38.50 82.02,31.33 81.36, 31.72 71.29, 24.47 88.33,38.50 86.06, 34.57 81.54,32.02 67.18,23.66 88.33,38.50 80.92,31.75 81.60, 32.06 68.97, 24.99 88.33, 38.5(1 81.47, 32.83 81.64, 62.71, 88.33, 76.54, 32.08 21.64 38.50 29.76 79.38,30.13 63.15,20.54 88.33,38.50 78.85, 29.72 79.66, 30.35 69.33, 22.79 88.33,38.50 85.76,33.26 81.16, 31.58 66.23, 22.35 88.33, 38.5(1 81.16,31.58 30.06 23.14 38.50 34.38 72.61, 58.03, 79.16, 70.45, 7 27.72 20.87 34.50 28.04 30.42 20.39 39.20 30.27 27.32 20.44 34.50 29.28 6 5 72.67, 59.83, 79.16, 71.26, 36.38 25.14 40.50 32.06 present chapter. This evaluation is carried out now for several batches of fish of different size. The results are given in Table 3.3. The production speed is calculated by dividing the total number of produced cans from each batch of fish by the required computational time. Table 3.3 clearly indicates that the computational time increases as the number of fish per batch increases. Moreover, the computational time can increase considerably if more runs are required due to the formation of sub-loops. In view of this possibility, which can make the present procedure unsatisfactory for industrial application, the model should be refined Chapter 3. Theory of Optimal Portion Control 56 Table 3.2: The Optimal Placement Results for the Example Batch of Fish. Optimal Orientation Relative Optimal Position of Fish, of Fish *'/+i(cm) (Pointing to left) Fish Number (As Received) (0 Optimal Location of Fish 1 4 tail 22.31 2 7 head 36.5 3 10 tail 20.39 4 5 head 34.5 5 1 head 0 6 2 tail 21.65 7 6 tail 22.89 8 9 head 39.5 9 8 tail 25.09 10 3 head 31.5 Table 3.3: Computational Times and Production Speeds for Different Batch Sizes. No. of Fish per Batch No. of Runs per Solution Total Solution Time [Seconds] Computational Production Speed [cans/min.] 4 1 1.5 2080 6 2 4.7 944 18 326 92.8 79 8 3 10 5 ' ^ 6 1 lOV^ Figure 3.7 The Optimal Overlapping Arrangement of Fish. further. This aspect is considered in the next section. 3.4 S t u d y o f O p t i m a l F i s h P a t t e r n s Formation of an interesting pattern of fish placement was repeatedly observed from the results of optimal overlapping arrangement, by applying the uncoupled model to various batch sizes of fish. In this optimal pattern, the fish are aligned in pairs with overlaps only in the tail sides Chapter 3. Theory of Optimal Portion Control 57 while the head sides are just touching without any overlap. In particular, two adjacent fish were found to be neither be both head first nor tail first. A random test was conducted to verify the stability of this fish pattern for different sizes of fish. In order to have an unlimited number of different sizes of fish, each fish in matrix A was altered by introducing a scale factor to the weight distribution function as w' {x) = a , V . ( j r ) Sl ( - °) 3 5 with the scaled length given by hi = (V; O- ) 51 Figure 3.8 illustrates the generation of different sizes of fish by applying different values of scale factor to the first fish in matrix A. Note that in applying these two parameters to scale the fish in a batch, the target weight rate should be kept unchanged. Otherwise, for example, if all the fish and also the target weight rate are all scaled by the same value, the optimal solution will not change. To accommodate this consideration, a parameter, peak index of fish weight distribution a is defined as h = ' Peak weight distribution of fish i —: Target weight rate (3.52) Using the two scaling factors, new batches of different sizes of fish were generated from equation (3.49). These generated fish have a, values in the range from 0.7 to 2.0. The developed solution procedure is applied to these generated batches to determine the optimal overlapping arrangement of fish. The pattern of fish placement of each batch is then examined for the formation of the optimal pattern. It was noticed that the optimal pattern of fish arrangement persists in the case where a, is larger that 0.95 for all the processed fish in all batches. If Chapter 3. Theory of Optimal Portion Control 58 a,- is smaller than 0.95 for at least one fish in a processed batch, overlapping of three fish may be a possibility in the optimal fish arrangement and therefore, will violate the size constraint on fish for the uncoupled model. Table 3.4 shows an example of optimal placement of fish when a, is smaller than 0.95. The numbers encircled with the broken line indicate the existence of three overlapped fish. P, 0 10 20 30 40 =1.73 50 60 Position along fish length [cm] Figure 3.8 Example of Generating Different Sizes of Weight Distribution Functions From Fish #1. The results presented in Table 3.2 are now recast in the format of Table 3.4 and presented in Table 3.5. Note that the fish size is not scaled, hence all a,-, p\- = 1 in this case. Furthermore it is noted that the parameters a, have values greater than 0.95, which correspond to a typical batch. In this case, as shown before, the maximum number of overlapped fish at a given point along the chain of optimal arrangement is two, thereby satisfying the condition of decoupling for the refined optimal formulation. Chapter 3. Theory of Optimal Portion Control 59 Table 3.4: Optimization Results for aiand a < 0.95 (Target Weight Rate = 47.92 grams/cm). 2 Fish Number Optimal Location of (As Received) Fish (0 1 5 a,-, P« i a Absolute Optimal Optimal Orientation Position of Fish, jc,-[cm] of Fish x +k t [cm] i, i 0.7, 0.7 1.18 head 0 35.5 0.8 tail 21.0 45.15 1, 1 1.03 tail 37.5 head ^69.0 2 1 3 6 4 4 5 2 1, 1 0.7, 0.7 1.02 0.9 head 6 8 1, 1 1.17 tail 7 3 1, 1 1.04 head 8 7 1, 1 1.05 tail 9 9 1, 1 1.29 10 10 1, 1 1.29 / y 72.4 \ 82.0 69.0 106^5 \ 100.75 121.2/ 121^2 ~~ — - 1 6 3 . 4 139.7 176.2 head 176.2 215.7 tail 194.6 233.1 Table 3.5: Optimization Results for a,- > 0.95 (Target Weight Rate = 47.92 grams/cm). Fish Number Optimal Location of (As Received) Fish (0 a,-, P,- i a Absolute Optimal Optimal Orientation Position of Fish, x,[cm] of Fish Xi + h [cm] 1 5 i, i 1.18 head 0 34.5 2 6 i, i 1.03 tail 21.65 53.15 3 10 l, i 1.29 head 53.15 91.65 4 1 i, i 1.14 tail 75.46 109.96 5 4 l, i 1.02 head 109.96 147.46 6 7 i, i 1.05 tail 132.85 169.35 7 2 i, i 1.28 head 169.35 209.85 8 9 i, i 1.29 tail 194.44 233.94 9 8 i, i 1.17 head 233.94 273.44 10 3 i,i 1.04 tail 254.33 296.53 N 7 6 0 Chapter 3. Theory of Optimal Portion Control 3.4.1 Simplified Uncoupled M o d e l In the optimization results obtained by analyzing typical batches for fish, as presented previously, it is known that in an optimal arrangement of fish two adjacent fish cannot be oriented in the same direction. Hence the combinations HH and TT do not occur for two adjacent fish. Furthermore, in the TH arrangement the two heads just touch without an overlap. Accordingly, equation (3.27) is reduced to C; = HT i j C" + TH HT i + i , C'f (3.53) H i + where h -x')dx' + w'lx' C"" = 2 j" w' (x')w' (l +x' T i i+l i = i+1 o w i i + i x i + 1 = + l h o w (3.54) (- ) 3 55 This indicates that, under typical conditions, only one sub-cost function needs to be optimized. This will reduce the run time significantly. The objective function (3.25) now becomes fm -1 \ X ^ min M + 1 c f r + r ; / 7 / + 1 H / 2 / = i l . -+' < 2 ; L (3-56) ; An immediate advantage of this optimal fish pattern, when considering an even number of fish per batch, is that half the mating will be of the type HT and the other half TH. Then, the orientation variables are not needed, and the objective function (3.56) is rewritten as m i n X C'£-x + < hi i= 1 2 (- ) 3 57 Equation (3.57) represents an NLP problem consisting of m/2 uncoupled nonlinear sub- 61 Chapter 3. Theory of Optimal Portion Control functions each of which containing just one variable. This problem should be solved m! times, for all possible arrangements of m fish, in order to find the optimal overlapping arrangement. Alternatively, it can be recast in an IP formulation as m m ™n j, * yijicf T XX( 0 (3-58) J i m m Z >•/+ !>;<• = j 1 (- ) 3 59 j ya = 0 y = 0 or 1 tj (3.60) (3.61) HT* Note that C - is the optimal value of equation (3.54), for the case of two fish / and j where t fish i is followed by fish j. The constraint (3.59) is used to insure that a given fish overlaps with no more than one other. This formulation does not require any extra constraints as there is no possibility of forming sub-loops in the solution. The model has a linear cost function and linear constraints, and can be solved faster than the previous model. The solution procedure is as follows: 1. Generate an mXm table containing the solution of equation (3.54) and the associated value 2 of w' L for all possible combinations of fish. Here, /• is the length of the secondary fish (second fish of the mating pair). 2. Solve the IP model, equations (3.58) through (3.61), using the data from the generated table, and determine the optimal combinations of fish pairs from the resulting values y^-. 3. Read the corresponding values of x' , j+l for each (ij) cell where the variable equals 1. This represents the optimal overlapping placement of fish j as measured from the leading Chapter 3. Theory of Optimal Portion Control head side of fish i. 4. Arrange the fish pairs in a chain, where the order of placement of these pairs will not affect the optimal result. 3.4.2 C o m p a r i s o n and Discussion The solution procedures of the uncoupled and simplified uncoupled models were applied to different batch sizes of fish using the data contained in matrix A of equation (3.49). Figure 3.9 shows a comparison between the two models. It is seen that the computational time reduces significantly when the simplified uncoupled model is applied (and it produces the same solution as the uncoupled model). The simplified uncoupled model is suitable for practical implementation of the portion control technology that is developed in this work, particularly for high-speed packaging applications such as can-filling of fish. The statistical weight distribution of cans that results through optimal portion control depends on the size of the processed fish. Fish weight distribution that are closer to the target weight rate will produce a sharper statistical distribution for can weight, with the mode (peak value) lying close to the target weight, which is desirable. If large variations in size exist, then the fish should be divided into several groups, each group having fish of similar size, and the groups should be processed separately for different can sizes; smaller fish being used for smaller cans. When processing fish that have relatively large variations in size, a sharper statistical distribution in net can weight may be realized by using variable cutter spacing. This possibility is discussed in the next section. 62 Chapter 3. Theory of Optimal Portion Control 1000 63 10000.0 100 1000.0 to c o 10 ra D. )(—— * — E o O - 7K - - * ^• I N— ) "> 1 0 0 . 0 0.1 10.0 6 8 10 12 14 6 8 10 No. of fish per batch No. of fish per batch (a) (b) •Uncoupled model X 12 14 Simplified uncoupled model Figure 3.9 Comparison Between the Standard Uncoupled and the Simplified Uncoupled Models, (a) Computational Time, (b) Production Speed. 3.5 M o d e l w i t h Specified W e i g h t R a t e B a n d a n d A d j u s t a b l e C u t t e r S p a c i n g Clearly, the weight accuracy of the processed portions can be further improved by providing the capability of adjustable blade spacing in portion cutting. In particular, during cutting of fish into can-filling portions, if one were to start from one end of the optimally arranged placement of fish and integrate the overall optimal weight distribution function such that the weight between two adjacent blades equals the target weight of portion, then the portion error will be zero. However, there are practical constraints on portion dimensions. Also, the portion accuracy can be further improved by specifying not just one target weight rate, but rather an interval of lower and upper bounds. This optimization problem with adjustable blade spacing is analyzed now and evaluated through computer simulations of practical data on salmon. A comparison is made with the optimization model that uses fixed blade spacing. Chapter 3. Theory of Optimal Portion Control 64 3.5.1 Mathematical M o d e l The objective function of this model seeks to minimize the total absolute deviation of the overall weight distribution function from a range of acceptable weight rate values. This situation is shown in Figure 3.10, where the shaded area is to be minimized. The acceptable range of w'(x) is bounded by w' and w' , which are determined primarily on the basis of min max the can dimensions and the firmness and handling issues of a steak. The optimization model can be expressed mathematically as L min 0.5j(|w'(x) - w' \ + w\x) - w' ) + (|w'(x) - w' \ + w' max max min min - w'{x))dx o which may be simplified to L min 0.5\{\w\x) - w' \ + \w'(x) - w' \ + w' min max min - w' )dx max o Figure 3.10 Error Function in the Overlapped Fish Model, Expressed as Absolute Deviation from a Specified Interval on Target Weight Rate. (3.62) Chapter 3. Theory of Optimal Portion Control 65 where, as before, the weight distribution function is given by m w'(x) = XHrfix-x,) + 7>;(Z,. + x, -x) (3-63) subject to H.+T.=l (3.64) with H. , T. = 0 or 1 (3.65) and the specified bounds of the target weight rate may be expressed as "'min = T P (3-66) max and TW w' max Here h =— (3.67) j, v . j min is the maximum allowable steak thickness (or, fill height, or cutter blade spacing) max and is equal to the can height minus a fixed clearance. Also h min is the minimum allowable steak thickness and may be specified according to firmness requirements of a fish steak for proper handling, process limitations, regulatory requirements, and so on, as mentioned before. The optimal fish pattern that was determined and verified in the previous section is assumed in this section. Hence, the objective function, for an even number of fish per batch, can be rewritten as m/2 min i= 1 where C is the sub-function for an adjacent overlapped pair of fish, but now minimized in v t Chapter 3. Theory of Optimal Portion Control 66 \ accordance with the specified bounds on the target weight rate, and is given by x C\ = 0.5 i + i + h+ 1 j" (\w' (x) - w' \ + \w' (x') - w' \ + w' Pi min Pi max min - w' )dx' max (3.69) where w' (x) pi = w'i(x') + w' (l +x' -x') i+x i+x i+x (3.70) Equation (3.68) is similar to equation (3.57) and represents an NLP problem consisting of m/2 (assume thatrais even which can be easily incorporated in a practical process) uncoupled nonlinear sub-functions each of which containing just one variable. This problem should be solvedra!times, for all possible arrangements ofrafish. Alternatively, it can be recast in an IP formulation as mm y* Y^yifij min (3.7i) such that m I m yu + X^, j = 1 (3.72) j yu = 0 y . = 0 or 1 y (3.73) (3.74) v* where is the minimum value of (3.69), for the case of two fish i and j where fish i is followed by fish j. Note that i and j denote the numbers of fish as received by the portioning process. This IP model has a linear cost function and linear constraints, and can be solved at the same fast speed as the simplified uncoupled model. The solution procedure is as follows: 1. Generate an raXra table containing the solution of equation (3.69) for all possible combina- Chapter 3. Theory of Optimal Portion Control 67 tions of fish. 2. Solve the IP model, equations (3.71) through (3.74), using the data from the generated table, and determine the optimal combinations of fish pairs from the resulting values y,j. 3. Read the corresponding values of J C ' , - , for each a cell (ij) in the data table where the vari+1 able y j equals 1. This represents the optimal overlapping placement of fish j as measured { from the leading head side of fish i. Once the fish are arranged according to the optimal solution, as given by these steps, next the portions are cut using an adjustable array of cutting blades or water jets. Specifically, a simple integration of the overall optimal weight distribution function is made from one end of the fish arrangement such that the weight between two adjacent blades is exactly equal to the target weight of the portion. If the blade spacing obtained in this manner exceeds the upper or the lower bound, then the spacing is set at the limiting value. 3.5.2 C o m p a r i s o n Between Models W i t h Fixed and Adjustable Blade Spacing The solution procedures of the two models, one with a single specified value for target weight rate and utilizing a cutter system with fixed blade spacing and the other with upper and lower bounds on the target weight rate and accommodating adjustments of cutter blade spacing, were applied to the same fish data. The comparison given here is based on the resulting statistical distribution of the can weight. The portion between two adjacent cutter blades represents the can fill amount. Hence, the can weight can be expressed as, CW (h) = w*(x + h)-w*(x ) t ci ci (3.75) Chapter 3. Theory of Optimal Portion Control 68 where CW is the weight of can i, and h is the portion thickness (blade spacing). Also, w*(x) t denotes the integrated weight distribution function of the optimal overlapped arrangement of fish, and is given by, X w*(x) = \w'(x)dx o (3.76) where w'(x) is the overall weight rate function of the optimal arrangement of fish. Also, x is ci the portion position (or blade position) for can i, and may be evaluated recursively as, = ci i X c(i+1) X (- ) +h 3 77 Note that the portion position for the first can, x , is zero, and h is the thickness of the ith cl { portion. For the model with fixed target weight rate, the blade spacing is constant, (h = h = t constant). For the model with specified bounds on the target weight rate, as discussed previously, the blade spacing (h) itself is allowed to vary only in the range h min to h , the max optimal portion thickness, h*, is calculated as, h* = {h:CW (h)-TW= i 0} (3.78) Considering the constraints on the portion thickness, for the adjustable model, the value of h t is taken according to; • if h<h • h r i min h = t h min if h- >h max i (3.79) max V K < iweight < Kaxdistribution J Figure 3.11 shows a comparison betweenKin the can using the two models. if h The batch of fish used in this example has the weight distribution function as given by the data Chapter 3. Theory of Optimal Portion Control 69 in matrix A of equation (3.49). The specified bounds on the target weight rate are w' min gm/cm and w' max = 42.59 = 54.76 gm/cm. It is seen that the model with fixed target weight rate gives a wider statistical distribution in can weight. This is expected because of the fact that the variation in portion error in the fixed blade spacing case is clearly larger than that for the adjustable model. Figure 3.11b has a fewer underfill cans but the overfill cans are about 25% of the total number of the produced cans. This is due to the processing of large size fish, as indicated in Figure 3.12. In order to further reduce the amount of overfills, the processed fish should be first classified according to the target can size. Figure 3.12 shows a classification of ranges of weight distribution functions of fish and the corresponding recommended can sizes. The classification is made according to the peak point of the weight distribution function. Such a classification of fish could almost entirely eliminate the overfills and underfills when used in conjunction with the adjustable model, in industrial can-filling operations. 00 45 80- 90- 100- 110- 120- 130- 14090 100 110 120 130 140 150 Weight (gm) (a) 90- 100- 110- 120- 130- 140- 150100 110 120 130 140 150 160 Weight (gm) (b) Figure 3.11 Can Weight Distribution Where the Specified Target Weight Rate is (a) Constant (Fixed Blade Spacing) (b) Bounded (Variable Blade Spacing). Chapter 3. Theory of Optimal Portion Control 70 Figure 3.12 Classification of Fish Size According to Net Can Weight, Using Real Data. 3.6 G l o b a l O p t i m a l A s p e c t s of F i s h P o r t i o n C o n t r o l Since no formal proof has been given on the global optimality of the portion control techniques that were developed in this chapter, it is appropriate to address this issue here. Even though analysis of a large number of sets of real data did not produce any results that were not globally optimal, a formal investigation of the global optimality of the results is given in this section. 3.6.1 B r a n c h and B o u n d A l g o r i t h m The Branch and bound method is used in the present work to solve the optimization models for the fish portioning process. This method implicitly enumerates all possible combinations Chapter 3. Theory of Optimal Portion Control 71 of the associated binary variables. The algorithm can be used to solve any mathematical programming problem that contains binary (or integer) variables, and this includes MINLP, NIP, MIP, and IP problems. The basic concept of the branch and bound method is outlined below. First, relax the binary constraint of all the variables and solve the problem as a continuous NLP or LP (e.g., by adding the constraint 0 < y. < 1, where y, is a continuous variable). If the solution gives binary values (0 or 1) to all the original (binary) variables, then the optimal solution to the relaxed (non-binary) problem is indeed the optimal solution to the original problem. This is clearly true due to the fact that the feasible solution of the original problem is a subset of the feasible solution of the relaxed one. It follows that the optimal value of the original problem cannot be better than the optimal value of the relaxed problem. If the solution does not result in binary values for the binary variables, then the problem is separated (branched) into two nodes (two candidate subproblems) by setting one of the binary variables equal to 0 and 1, separately. Select one of the subproblems and relax all remaining binary variables as before. Solve the new sub-problem and if its solution results in binary values for the binary variables, set aside this solution as a candidate solution. Otherwise, separate the current subproblem into two additional subproblems by setting one of the remaining binary variable to 0 and 1, add these two subproblems to the set of candidate subproblems, and solve as before. Continue this process until the set of candidate subproblems is exhausted, and report as the optimal solution the current node. Chapter 3. Theory of Optimal Portion Control 72 To avoid the enumeration of all candidate subproblems, a fathoming test is applied after solving each subproblem. This test allows one to eliminate any further steps of branching a tested subproblem. The subproblem is fathomed if: it is infeasible; it yields an optimal value that is not better than the optimal value of the candidate optimal solution, or a new optimal solution is found. If a new optimal solution is found, the candidate optimal solution is updated with the new one. Figure 3.13 gives a simplified flowchart for the branch and bound method. It is clear that the branch and bound method is simply a procedure of full enumeration of all possible binary combinations of the binary variables, but it is carried out in an efficient way. Consequently, the resultant optimal solution is indeed a global optimal solution provided that any feasible relaxed sub-problem would yield a global solution. Also, it should be noted here that if the first relaxed subproblem (the root sub-problem) yields a global optimal solution, then any subsequent sub-problem would do the same. This is due to the fact that subsets that result by adding a linear equality constraint to a convex set are also convex sets. Therefore, the only check for global optimality that is required here would be to prove global optimality of the root relaxed sub-problem itself. 3.6.2 G l o b a l optimality of L P and N L P Problems -* Assuming a minimization problem, the solution x is said to be a global minimum of f(x) if the following condition is satisfied: f(x*)<f(x) \/xeS (3.80) One way of guaranteeing a global minimum is by showing that the optimization problem is er 3. Theory of Optimal Portion Control Optimization model (MINLP, MIR NIP, or IP) Relax all the binary variables and add the subproblem(s) to the list Infeasible Yes Optimal solution is found (x, y, optimal value)/ Yes Solve the most recently added sub-problem (Last-In-First-Out selection approach) STOP Yes Branch the current subproblem into two new sub-problems Do all binary variables have binar values? Yes Is this solution better than the candidate" optimal solution?. Yes Update the candidate optimal solution F i g u r e 3.13 T h e B r a n c h and B o u n d M e t h o d . Chapter 3. Theory of Optimal Portion Control 74 convex. It is known that If/fx) is a convex function on a convex set S, then any local minimum is also a global minimum [30]. In an LP problem, the feasible region is a convex set. Also, the cost function is linear, and hence is a convex function. Therefore, the LP problem is convex, and if an optimal solution exists, it is the global optimum. For the case of NLP, the problem may be modeled as follows: maximize (or minimize) f(x) such that g.(x)<0, i = 1 to p (3.81) hj(x) = OJ = 1 to q Accordingly, the feasible solution set of (3.81) is defined as S = {x: g (x) < 0, i = 1 to p; hj(x) = 0, j = 1 to q} (3.82) t The set 5 is a convex if the functions g, are convex and hj are linear. The function/(x) is convex if and only if its Hessian matrix is positive semidefinite or positive definite. The Hessian matrix of/(x) is defined as H = V2/(x) = j£r=f(x) (3.83) axax Also, the global optimality of an NLP can be guaranteed if the objective function is a pseudoconvex function within the convex set S of a feasible solution [37]. The function/(x) is pseudo-convex if for every x , x i (x -x ) V/U2)<0 r 1 2 e 2 ^> t n e condition /(x )</(x ) implies that ] 2 Chapter 3. Theory of Optimal Portion Control 75 3.6.3 G l o b a l optimality i n the Overlapped F i s h Models The overlapped fish models that have been developed in Sections 3.4, and 3.5 are formulated as IP models. Therefore, any optimal solution is a global optimum provide that the sub-cost functions of the corresponding model, (e.g., equation (3.54) or (3.69)) yield global optimal solutions for any combination of fish pairs. For example consider equation (3.54) for overlapping fish numbers 1 and 2. Figure 3.14 shows the sub-cost function and its second derivative as a function of the overlapping position, varying from 0 to l . It is clear from Figure 3.14b that the Hessian is not positive for { all values of the overlapping position, and therefore the sub-cost function is not convex. However, according to the definition of the pseudo-convex function, it is indeed a pseudoconvex function. Hence its local minimum is also a global minimum. To check global optimality of the solution for the specified range of fish, equations (3.54) and (3.69) are computed for different sizes of fish. The fish size is altered using the scaling factors, Figure 3.14 Equation (3.28)a and Its Second Derivative for the Overlapped Fish Pair #1 and 2. Chapter 3. Theory of Optimal Portion Control 76 with respect to the target weight rate of filled portions, introduced through equation (3.52). Figure 3.15 shows the sub-cost functions computed using different sizes of fish. It is evident that there is only one local minimum for any value of peak index ct It is also clear that for the r specified range of fish, which is a > 0.95, the optimal overlapping position has a non-zero t value. Figure 3.16 shows the sub-cost functions (3.69) for overlapped fish of different sizes. The fish size in this case is characterized by a new parameter b for the fish weight distribution function t that is suitable for the adjustable cutter spacing model. This parameter is defined as the ratio of the peak value of the fish weight distribution to the lower limit of the target weight rate w' • . ,v nun' b- = Peak weight distribution of fish / ; w (3.84) min It is clear that there is only one minimum point in each sub-cost function. It is also noticed that the best minimum value occurs when overlapping two fish with sizes close to the upper limit of the target weight rate w' . max The pattern of optimal arrangement of fish (//, = 1 and Hj = 0), which was established by examining the optimal solution of the IP model of equations (3.42) to (3.47), depends on the solution of each sub-cost function of equations (3.28). Therefore, it is important to make sure that the three remaining sub-cost functions of equations (3.28) would yield global minimum solutions as well. Figure 3.17 presents these three functions for overlapped fish of different sizes. For a peak index value of 0.95 or more, it is evident that there are two local minima, Chapter 3. Theory of Optimal Portion Control Figure 3.15 Cost Function (3.54) for Different Sizes of Fish. Figure 3.16 Sub-Cost Function (3.69) for Different Combination of Fish Size. 77 Chapter 3. Theory of Optimal Portion Control 78 zero being one of them. To insure global optimal solution, the optimization code was forced to find these two local minima and then choose the better one of them. It should be noted here that this effort is made only during the analysis of the pattern of the optimal fish arrangement. It is clear that fast on-line measurement of the weight distribution function of each incoming fish for processing is essential for the industrial implementation of the optimal portion control procedure that was developed in this chapter. Next chapter investigates the associated sensing considerations. Chapter 3. Theory of Optimal Portion Control 79 700 0 10 20 30 40 50 60 70 50 60 70 50 60 70 Overlapped Distance [cm] (a) 700 0 10 20 30 40 Overlapped Distance [cm] (b) 700 0 10 20 30 40 Overlapped Distance [cm] (c) Figure 3.17 Sub-Cost Function of Equation (3.28) for Overlapped Fish Pairs of Different Sizes with the Orientation (a) H = 1 and t Hj=\, (b) ^ = 0 and Hj=l, (c) H = 0 and Hj = 0. { Chapter 4 O n - l i n e Sensing of the Weight D i s t r i b u t i o n F u n c t i o n The techniques of optimal portion control that are developed in the present work depend on fast on-line measurement of the weight distribution function of each incoming fish. Direct measurement of these functions, which are known to be complex, is not feasible by conventional means, particularly in view of the cost considerations and the needed production speeds. This chapter develops a suitable procedure for on-line measurement of the weight distribution of fish. The approach depends on off-line experimentation and model development, and use of these models on-line in conjunction with fast on-line measurements of simple geometric attributes of each incoming fish. Examples are given to illustrate the associated procedures, using real data on fish. Issues related to measurement error are studied based on the measured results. 80 Chapter 4. On-line Sensing ofthe Weight Distribution Function 81 4.1 I n t r o d u c t i o n The weight distribution function of an object depends on the density characteristics of the object. The density distribution function of an object is a single valued function and is defined as the weight per unit volume at any location within the object boundaries. This function is quite simple for homogenous material, and equals one single value. However, for a non homogeneous material, such as meat, vegetable, or fruit, the density function is rather complex. In order to estimate the density distribution function for a non homogenous object, knowledge regarding the structure of the object and the density of the internal components in the object is required. Computed tomography, positron emission tomography, and magnetic resonance imaging are examples of techniques that can be used to estimate the density variations within an object [50,51]. These techniques are known to be very costly and slow, and are not suitable for on-line measurements. In food processing it may not be required to estimate the density function in all dimensions. For example, in fish portioning process as developed in the present work, it is the weight distribution function of a fish along its length is what is required. This function, which gives the weight rate (i.e., the local weight per unit length), has to be measured accurately (or estimated) on-line, at a high speed. One possible approach for accomplishing this would be to measure on-line some simple features that would have a good correlation with the weight distribution function of fish, and use these measurements to select a suitable model, that is developed off-line, which gives the necessary weight distribution function. Chapter 4. On-line Sensing of the Weight Distribution Function Correlation between geometric features and weight of salmon is of interest in many research applications [61-65]. The motivation in several of these applications is to reduce the level of handling of fish. Typically, image processing technology has been considered in related procedures of sensing and data acquisition. Different regression models have been developed by Beddow and Ross to estimate weight of a fish from the lateral dimensions [65]. These measured dimensions are related to morphological features that are homologous throughout a salmon population. Despite good estimation results that have been possible by these techniques, a variety of models would be required for different fish groups of different species, age, and catch place. This is due to natural variations in the morphology of salmon body even among fish from the same species [66,67]. However, the correlation between the morphological features and weight of fish provides good rationale for using such features to estimate the weight distribution function of fish. Moreover, cannery dressed fish are precleaned and deheaded, and consist of muscle, bone, and skin only. Also, the weight of a cannery dressed fish can be measured on-line, say using a load cell [68]. These advantages would lead to enhanced correlation between the morphological features and the weight distribution function of a fish. This chapter develops and evaluates a high-level sensor for on-line measurement of the weight distribution function of a fish. The on-line sensor utilizes different non-dimensional geometric models, and simple on-line load sensors and vision sensors for the fast extraction of the weight distribution function. Non-dimensional models are developed off-line, which are unique and representative of a particular group of fish. During the on-line process, a model is 82 Chapter 4. On-line Sensing ofthe Weight Distribution Function 83 selected by matching the on-line measurements with the model data-base, using a decision making engine. Pattern recognition or rule-based techniques may be used to develop the necessary decision making engine. Information regarding the muscle and bone structures of different fish groups and the related morphological landmarks are required in the present development. 4.2 Sensor Structure The weight distribution function of a cannery dressed fish may be expressed as w'(x) = A(x)p(x) (4.1) where, A(x) and p(x) are the cross-sectional area and the average density across that area, respectively. These two functions are defined only in the interval of x < x < x , as indicated h t in Figure 4.1. The first function depends on the structural geometry of fish and the second one depends on the weight distribution of fish. X Figure 4.1 The Structure and Cross-Sectional Area of a Cannery Dressed Fish. Chapter 4. On-line Sensing of the Weight Distribution Function 84 The average density function p(x) is expressed in terms of a non-dimensional density function as Y« = ^ P (4.2) where p is the average density of a fish, which is given by the ratio of the weight W and the corresponding body volume of the fish; thus, ^ W (4.3) A(x)dx Using equations (4.2) and (4.3), equation (4.1) is rewritten as > w {x) = Mx)xy(x) Wx ( 4 4 ) J* A{x)dx Hence, one may write, for example w'(x) = Wx _ ^ A(x) X (x) (4.5) J* A(x)dx where A{x) = ^ (4.6) o A and A is the area of cross section of the fish at a defined feature point (e.g., anal feature point, (l see Figure 4.3) which can be easily measured on-line. The weight distribution function is decomposed into two sub-functions A(x) and y(x), as given by equation (4.5). Here y(x) is a non-dimensional density function which depends on the structural geometry of fish and the relative density values of the components of fish body (primarily muscle, bone, and skin). The weight W of fish can be easily measured on-line using Chapter 4. On-line Sensing of the Weight Distribution Function 85 conventional load cell. But, it is difficult and sometimes impossible to measure or estimate the functions A(x) and y(jc) using conventional sensors, computer vision inclusive. Direct sensing approach may either limit the processing speed or the achievable accuracy, due to the complex nature of information that is required. Consequently, an alternative approach for extracting this processing information is required, and a model-based approach is developed here for this purpose. This method utilizes a laser/vision sensor and a load cell in conjunction with nondimensional models of fish, to estimate the non-dimensional cross-sectional function A(x) and the relative density function y(x). This sensor will measure simple on-line features that are expected to have good correlation with the two required functions A(x) and y(x). These features are then used to select the proper fish model, by using the model selection engine. The selected model is then dimensionalized using the measured geometric parameters, to estimate the weight distribution function of the processed fish. This procedure is shown by the flow chart in Figure 4.2. Non-dimensional models of A(x) and y(x) are stored in the sensor data-base. First these models have to be developed off-line from representative samples of fish. To generate a variety of models that are accurately representing any item of processed fish, many fish have to be sensed and analyzed off-line. Alternatively, for preliminary development, first a structural model is developed for fish body, and this model is then used to generate the necessary data for developing the non-dimensional models that are needed for the weight distribution sensor. The details of the structural model of fish body are explained in the next section. Chapter 4. On-line Sensing ofthe Weight Distribution Function 86 To portioning controller Computation of w\x) Dimensionalizing of Model Parameters Fish Weight W Model DataBase Model Selection (A(x) & y(x)) Engine Measured Geometric Parameters Signal Pre-processing Image Processing and Feature Extraction Load Cell Vision Sensor Figure 4.2 Schematic Diagram of the On-Line Sensor for Fish Weight Distribution. 4.3 M o d e l i n g of F i s h B o d y The purpose here is to build a structural model for fish body (synthetic fish) that can be used to generate weight rate functions of fish with natural variations of size and properties. Also, the model should be used to produce dimensional features that are easily measurable using a laser/vision system. These features will be used as an input to the weight rate sensor. A cannery dressed fish (de-headed, gutted, cleaned fish) mainly consists of three components; muscle, skin, and bone. Hence, the weight distribution function of a fish can be expressed as w'(x) = P A (x) + P A (x) + P A (x) m or m b b s s (4.7) Chapter 4. On-line Sensing of the Weight Distribution Function w'(x) where A (x), m = P A(x) m + (P -PjA (x) b 87 + (P -P )A (x) b s m (4.8) s and A (x) are the cross-sectional area of muscle, bone, and skin of fish, A {x), b s respectively, and p , p , and m are the corresponding densities. The overall cross-sectional b area, A(x), can be modeled as an area enclosed between two ellipses, as shown in Figure 4.3. Hence, A(x) = ?(HJ(X)WJ(X)-H (X)W (X)) C (4.9) C or, A(x) where Hf(X), (4.10) = ^(Hjix/L^Wjix/L^-H^x/L^W^x/L^) and W^iX) are the normalized functions of height, width, internal Wf(X), HjiX), cavity height, and internal cavity width, respectively, which characterize the body structure of a fish. These functions are normalized with respect to the fork length L of fish such that Hf= k H /L , f k Wf = W /L , f k He - H IL , c k W^. = W /L , c k and X = xlL . k The four characteristic functions represent a geometric structural model of a fish from the same species and age group. It should be noted here that Hf(X) and Wf(X) are defined in the interval of X < X < X , while p HfiX) and WJX) are defined only in the interval of X p < X < X. a The quantities X mh ,X , mh and X are the normalized positions of the front point of the pectoral fin, minimum height at the a tail side, and the anal feature point, respectively. Normalized position of the dorsal feature point, X is also included in the model. In the present work, fish structural models for different d species of salmon are developed using information on the anatomy of salmon, obtained from the literature [69-72]. Figure 4.4 shows the four characteristic functions of one such model. Chapter 4. On-line Sensing of the Weight Distribution Function Section A - A (Normalized Dimensions) Dorsal Feature Point Caudal Fin Figure 4.3 Fish Body Model. 0.16 c o c 0.12 0.08 si U 0.04 0.00 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 N o r m a l i z e d Position A l o n g the F i s h Length Figure 4 4 A n Example of the Characteristic Functions of a Structural Model of Fish. Chapter 4. On-line Sensing ofthe Weight Distribution Function 89 Other characteristic factors such as flatness, elongation, and slenderness can be included as well in the geometric model of fish. These factors would allow the representation of various natural variations in the fish body dimensions. Slenderness factor represents the slenderness of the fillet flaps (see Figure 4.3). The cross-sectional area including these three factor is A where C, , e M . ^ j ( ^ j ^ j . t W e ( ^ j ^ J 4.„) ( and C, are the elongation, flatness, and slenderness factors. The cross-sectional s area of a fish bone is modeled as, bW A = \ » \= (4.12) where D is the normalized average diameter of the backbone of the fish, and can be considb ered constant along the fillet length of the fish. The cross-sectional area of skin is defined in terms of the skin thickness and the crosssectional circumference at point x as, A (x) = T x C O ) = L\T_ x cl^j-j s s (4.13) s where T is the normalized thickness of skin, and C(X) is the normalized cross-sectional s circumference and defined as an ellipse of circumference given by "•^2 /~~2 2 2 ~2 2 C(Z) = 4 x J ^//tf/Wsin(0 +WJ(X)cos(0 dt (4.14) o where t is a parameter, which is defined in the interval 0 < t < n/2. The quantities and T are to be included in the fish structural model that is obtained from the literature of salmon f Chapter 4. On-line Sensing of the Weight Distribution Function 90 anatomy. Substitution of equations (4.11), (4.12), and (4.13) in (4.8) will yield a general weight distribution function for fish fillet, which is defined in the interval x <x<x h (4.15) t where x is the head cut position and x is the tail cut position (see Figure 4.1). These positions h t are computed using the fish body structural model as, X k t ' X ' * \ ~ mh x (4.16, "r x where h is the tolerance on the head cut position farther from the pectoral position, and 8 is h f the tolerance on the tail cut position ahead of the minimum height position. These tolerances can be considered as the allowable errors in the processes of head cutting and fish cleaning. Note that x and x p mh are the positions of the front point of the pectoral fin and the minimum height of a fish, respectively, and may be expressed in terms of model parameters as, n X p The parameters L , p , p , p , k m b s X L,„L = n _ k (4.17) p Q , and £ should be defined to generate a single weight 7 5 distribution function for fish. These parameters may be chosen from normal distributions of real data of fish, reported in the literature [72,73]. Figure 4.5 shows several of weight distribution function produced in this manner using the data provided in Table 4.1. 91 Chapter 4. On-line Sensing ofthe Weight Distribution Function 35.0 Fish -x-Fish Fish Fish -9-Fish Fish E o e C o c 3 30.0 25.0 20.0 #1 #2 #3 #4 #5 #6 OH e o •c J3 bo 15.0 V s 10.0 5.0 0.0 1 1 0.0 5.0 10.0 1 15.0 1 1 20.0 25.0 30.0 35.0 40.0 Position Along the Fish Length [cm] Figure 4.5 Weight Distribution Functions Generated from Statistical Distributions of Fish Data (shifted to the origin). Table 4.1: Parameter Values of Fish. [cm] Fish No. M- rj 50 3 Pm Pb c. P, [gm/cm ] [gm/cm ] [gm/cm ] 3 a 3 o a a 1.11 0.02 1.29 0.02 1.06 0.02 1 0.053 a 1 0.066 a 1 0.05 1 51.1 1.104 1.287 1.056 0.942 0.973 1.029 2 50.4 1.103 1.302 1.065 0.994 1.089 0.984 3 52.5 1.132 1.333 1.06 1.063 0.979 1.024 4 50.4 1.132 1.130 1.074 0.911 1.144 0.998 5 44.5 1.106 1.260 1.062 1.025 1.114 1.042 6 46.2 1.119 1.300 1.051 0.936 0.899 0.999 4.4 Estimating the Weight Distribution Function As described in Section 4.2, the weight distribution function of a fish i can be estimated using w'Xx) = PA(x)J(x) (4.18) Chapter 4. On-line Sensing of the Weight Distribution Function 92 where A(x), p , and y(x) are the estimated values of the cross-sectional area, average density, and the normalized density function, respectively. Note that p and A(x) are evaluated using the geometric features measured on-line and the fillet weight. Six features are selected to represent a fish, and are evaluated using the body structural model and parameters of the fish as, F = (4.19) These features are chosen to represent three dimensional measurements of fish using visible feature points. In real processing of fish these features are to be measured directly from processed fish using a 3D measurement system such as the arrangement presented in Appendix B. In the present simulation, a small random value is added to each feature in order to represent the measurement uncertainty. Now, p, and A(x) are evaluated using W P = (4.20) X, where, A W = JH W A (xX(X -X )/(x -x )) m fa fa a d a d (4.21) Chapter 4. On-line Sensing of the Weight Distribution Function 93 The hat sign " - " in each parameter of the measured features indicates that it contains an error value and hence some form of estimation is involved. Note that A (X) is the non-dimensional m model function representing the cross-sectional area of fish which is equivalent to A(x) that is included in equation (4.5). This function is normally evaluated using real fish data generated off-line, as described in Appendix A. However, in the present research, due to the limited number of fish samples that are available, it is extracted from the structural model of fish presented in the previous section as, Figure 4.6 shows four models of A (X) determined for four different species of salmon. It is m clear from the figure that each curve can be easily distinguished from the rest. More models would be required for proper development of the model selection engine. Specifically, models for different age groups but from the same salmon species should be considered. This is valid due to the fact that, in the can-filling process of fish, only one salmon species is processed at a time. Moreover, as discussed in Chapter 3, limits on the fish size would be applied depending on the can size. Hence, one may need only a few models to choose from during on-line processing. Consequently, the step of model selection in on-line sensing is omitted here and only one model is considered for the processed fish. Also, the normalized density function y(x) is assumed to be constant and equals one. The error that results from this assumption is found to not exceed 0.7%. This is verified by evaluating the normalized density function of the fish as presented in Table 4.1, using the Chapter 4. On-line Sensing ofthe Weight Distribution Function 94 2.0 1.5 1.0 u o z 0.5 0.0 0.0 0.2 0.4 0.6 0.8 1.0 Normalized Position Along the Fish Length Figure 4.6 Models of Cross-Sectional Area. following equation: I YO) A(x)dx w'{x) *h A{x) (4.23) {x)dx Which is an equivalent form of equation (4.4). Figure 4.7 indicates that y(x) has the highest deviation from unity in the tail region of the fish body. It is clear from the chart that the average error would not exceed typically 0.1%. This is due to the fact that muscles are occupying a large share in the body structure of fish. 4.5 Sensor Performance and Results To examine the accuracy of the weight distribution sensor that has been developed in this chapter, the sensor estimation error is calculated as outline below: 1. A number of 500 weight distribution functions are generated using the fish structural model, equations (4.8), the characteristic functions of the coho model (See Figure 4.4), and Chapter 4, On-line Sensing of the Weight Distribution Function K" | 3 tt. 'I 95 1.008 — - Fish #1 Fish #3 1.004 - - s - Fish #5 Fish #2 Fish #4 Fish #6 1.000 - Q N 0.996 ^ Z, 0.992 -I 0.0 1 1 1 1 1 1 1 5.0 10.0 15.0 20.0 25.0 30.0 35.0 Position Along the Fish Length x [cm] Figure 4.7 Normalized Density Function of Fish Fillets (shifted to the origin). the statistical distributions of fish data provided in Table 4.1. 2. For each generated weight distribution functions, a set of feature items are calculated using equation (4.19). These items consider the exact feature values as they are calculated using the fish structural model (i.e., no measurement error). 3. The weight of each fish is computed using the generated weight rate function in step 1 and the first two features calculated in step 2 as X (4.24) 4. Normally distributed random values are then added to the feature values and the computed fish weight to represent measurement errors. For features that are measured using the laser/ vision system, normally distributed error values with |i = 0 mm and a = 0.5 mm is used. The load cell error is assumed to be normally distributed with |i = 0 grams and a = 3 grams. Chapter 4. On-line Sensing ofthe Weight Distribution Function 96 5. The estimated weight distribution function for each fish is then computed using equation (4.18) and the feature values with and without the measurement errors (i.e., steps 2, 3, and 4). 6. Each estimated weight distribution function is then compared with the exact one and the sensor error is computed based on the corresponding deviation. The percentage error of the sensor is expressed as J \w (x) - w' {x)\dx t Sensor estimation error = t r j" x 100 (4.25) w' (x)dx i Where vv'-(x) is the estimated weight distribution function and w',•(*) is the actual weight distribution function of fish i. Figure 4.8a shows the histogram of the estimation error values for the 500 fish when the sensor error is neglected. In this case the mean error is 0.31% and the standard deviation is 0.22%. Figure 4.8b shows the histogram of the estimation error when the sensor error is included. The estimation error, when the error in the vision sensor and load sensor, are included, has a mean value of 0.81% and a standard deviation of 0.38%. Thus far, satisfactory models have been developed for optimal portion control of fish for can filling applications. Also, models have been developed for fish, and have been validated. These models are useful in on-line sensing of the weight distribution function, which is essential for practical implementation of the portion control technology. Also, these models are useful for generating realistic data for fish, in large-scale simulation studies. Next chapter Chapter 4. On-line Sensing of the Weight Distribution Function undertakes computer simulation and evaluation of the optimal portion control process. 200 u B U 3 cr 150 i 100 u 50 1 n 0 1 - r — ! 0 0.4 0.8 1.2 1.6 Estimation Error [%] (a) ; r More 0 0.4 0.8 1.2 1.6 Estimation Error [%] (b) Figure 4.8 Histogram of the Estimation Error (a) Without Sensors Error (b) With Sensors Error. More Chapter 5 S i m u l a t i o n of the O p t i m a l P o r t i o n i n g Process In this chapter, computer simulation of the optimal portioning process that has been developed in the present work, are carried out. The large quantities of practical data that are needed for simulations are generated by using the fish structural models which themselves are developed using actual data on fish and properly verified. The two process models that are simulated in this chapter are the one with a fixed-value target weight rate and the one where bounds on the target weight rate are included. The latter case is treated as the situation where the spacing of the cutter blades is adjustable. Simulation results are evaluated and compared, particularly with regard to the accuracy and quality of the fill, and the speed and convergence of the optimal computational procedure. 98 Chapter 5. Simulation ofthe Optimal Portioning Process 99 5.1 I n t r o d u c t i o n The ultimate test of the optimal portion control technique that has been developed in the present work entails implementation in an industrial process and through evaluation of the performance. Such a task is known to be very costly, time consuming, and is beyond the scope of the research that is undertaken in this thesis. Instead, in the present chapter, the optimal portioning process is simulated and the results are evaluated. Such simulation studies should represent the physical process with reasonable accuracy. In order to analyze the performance of the optimal portion control process, the process should be tested using a large set of real data on fish. However, such a process of data gathering would be difficult and costly. Particularly, according to practices of fish processing industry, if fish is handled for measurement, then that fish is removed from the process line and discarded. To overcome this situation, and yet develop a representative set of realistic data, first realistic models of fish are developed as described in chapter 4, using actual data, and then these models are used with some natural variations, to generate further data. For this purpose, the parameter values for the models are chosen using statistical data that is available in the literatureof salmon industry [73]. Computer codes, that are written in Matlab environment, is used to simulate the fish portioning process. The two models of the fish optimal portioning process, as developed in this work, are simulated. The performance of each model is examined in terms of the produced can weight histogram, can-fill quality, weight and length of the processed fish fillets, and optimal solution convergence. The chapter ends with a comparison between the performance of the two models. Chapter 5. Simulation of the Optimal Portioning Process 100 5.2 Process Description As described in Section 1.2.3, the optimal portioning process of fish mainly consists of three steps: on-line sensing (estimation) of the weight distribution functions of the processed fish; placement of the fish according to the optimal overlapping arrangement; and cutting the fish into fill portions. In the process simulation the same layout is incorporated, but with an addition of a synthetic fish generator. The synthetic fish generator produces fish randomly based on the developed fish models which are realistic, and with realistic values for the model parameters which are also selected randomly. Each synthetic fish that is generated provides two groups of data, one group representing the measurable features that are expressed in equation (4.19) and the fillet weight, and the second group representing the structure of a real fish body, which includes the weight distribution function and the fillet length. Details of the fish model have been presented in Section 4.3. Figure 5.1 shows a schematic diagram of the physical portioning process. Figure 5.2 gives a flow diagram of the associated tasks. Structured Laser Light Cleaned Deheaded Fish to Filler Image Processing Hardware and Software, and Optimal Portioning Controller Cutting Machine Figure 5.1 Schematic Diagram of the Physical Portioning Process for Can-Filling of Fish. Chapter 5. Simulation ofthe Optimal Portioning Process Fish Structural i Body Model , 1 1 1 Cross-Sectional 1 i Area Model i H On-Line Sensing (Errors Added) 101 I Estimation of Fish Weight Distribution Function Filtering of Fish Weight Distribution Function Determination of the Optimal Arrangement of Fish Fish Features Synthetic Fish Generator Weight Distribution Function and Fillet length Fish Sorting Process Optimal Overlapped Placement of a Batch of Fish Portion Cutting Can-Fill Portions Figure 5.2 Flow Diagram of the Tasks in the Optimal Portioning Process. The main steps of the process simulation are given below: 1. Generate synthetic fish randomly according to the data provided in Table 4.1, except for the fork length. The fork length is set to be a uniform random value between 45 and 75 cm. This is done to generate a wide range of fish of different sizes. Here, two groups of data are generated for each fish, first group includes the on-line measurable features and the second group includes the weight distribution function and length of the fish fillet. 2. Add random values to the feature data group to represent the measurement error of the online sensors (laser/vision sensor and load sensor). 3. Estimate the weight distribution function of fish, as described in Section 4.4, and shift it to the origin. 4. Sort fish according to the peak values of the estimated weight distribution functions. For example, when simulating the portioning process using the variable cutter spacing model, upper and lower limits of the peaks of the weight distribution functions are set according Chapter 5. Simulation of the Optimal Portioning Process 102 to the upper and lower bounds of the target weight rate limits of the target weight rate w' ry mm and w' " maxv 5. Solve for the optimal overlapping arrangement of a batch of fish using the solution procedure outlined on Section 3.4.1 or Section 3.5.1, depending on the optimal overlapping model that is used (i.e., fixed cutter spacing and adjustable cutter spacing). 6. Cut the fish into portions according to the optimal solution and compute the exact can weights using the weight distribution functions (as shifted to the origin) and lengths included in the data group that represents the real fish body as described in Section 3.5.2. 5.3 S i m u l a t i o n Results f o r the S i m p l i f i e d U n c o u p l e d M o d e l The simplified uncoupled model, which incorporates fixed-value target weight rate of filling, is used here. The lower limit of the peaks of the weight distribution function is set to 0.95 of the ideal weight rate w'„, as indicated in Section 3.4. This value is 45.52 grams/cm for 115 gram cans with a fill height (steak thickness) of 2.4 cm. In order to realize a practical application of the optimal portion control model that is considered here, different upper limits for the peaks of the weight distribution function are selected. These values are 50, 52, 54, 56, 58, and 60 grams/cm. A total of 500 fish are sorted for each limit and are processed in batches of 10 fish, for optimal placement. Figure 5.3 presents the statistical distributions (histograms) of the can weight for different upper limit values. It is clear from the histograms that the number of overfilled cans is increased as the upper limit of the peaks of the weight distribution function increases. Table 5.1 summarizes the simulation results for various values of the upper peak Chapter 5. Simulation ofthe Optimal Portioning Process 103 limit. The results indicate that the percentage of the acceptable cans decreases when the upper limit of the peak of the weight distribution function increases while the filling quality (defined here as having only one steak in a can) increases slightly. It is also noticed that the number of over-filled cans increases with increase in the upper limit; however, there is a slight decrease in the number of under-filled cans. These results lead to the conclusion that the smaller the upper limit of the peak the better the productivity. However, this choice of upper limit on the peak of the weight distribution function will limit the size of the processed fish. Table 5.1 indicates that for an upper limit of 50 grams/cm in the peak of the weight distribution function, the processed fillet weight is limited only to fillets 1 kg to 1.6 kg. Table 5.1:Simulation Results Using the Simplified Uncoupled Model. %of Upper L i m i t on Acceptable the Peak of w'(x) [gm/cm] Cans a %of OverFilled Cans % of UnderFilled Cans %of Good Quality Cans b Processed Fillet Weight [gms] u rj Processed Computational Time Fillet Length [seconds] [cm] 0 a M- a Max. 50 69.8 1.84 28.4 58.7 1296 81 36.4 2.2 17.9 0.9 20.3 52 68.0 8.64 23.4 64.7 1337 101 36.8 2.5 17.6 0.7 19.4 54 63.1 16.7 20.2 67.0 1385 116 37.4 2.6 17.6 0.9 20.0 56 57.8 24.2 18.0 67.1 1422 137 37.6 2.7 18.1 0.9 20.5 58 53.4 30.1 16.5 66.8 . 1464 149 38.1 2.7 18.8 0.8 21.3 60 50.1 36.6 13.4 66.8 1520 174 38.6 2.7 19.4 1.0 22.4 a. Within +/- 5% of the target weight of can. b. The percentage of acceptable cans that contain one steak only. c. Time required to converge to an optimal solution. Chapter 5. Simulation of the Optimal Portioning Process 104 4000 4000 3000 c a 2000 £ 3000 a 3 2000 cr a" £ T 1000 £ n 0 10 40 70 lis 1000 nil 0 10 100 130 160 190 40 70 100 (b) 4000 I I 30 160 190 Can Weight Can Weight [grams] (a) £ n 1 1 1 1 1 1 grams] 4000 1 3000 S3 3 2000 3 2000 cr £ cr n 1000 -nfl- 0 10 40 70 | I" i 1 i i i i H 1000 0 i i 100 130 160 190 nl 1 n 10 40 Can Weight [grams] 4000 4000 3000 g" 3000 H a I e 2000 3 2000 1000 0 100 130 160 190 Can Weight [grams] (d) (c) cr u 70 n £ 1—i—i—i—i—i—i—i 10 40 70 i i i i i i—i—n—rr 100 130 160 190 Can Weight [grams] (e) Fl 1000 i 0 10 i i i 40 i i i 70 i i , 100 i 1 I I I I I 1 1 30 160 190 Can Weight [grams] (f) Figure 5.3 Statistical Distributions of Can Weights for Different Upper Limit Values of the Peak of Weight Distribution Functions of Fish (a) 50, (b) 52, (c) 54, (d) 56, (e) 58, (f) 60 grams/cm. 5.4 Simulation Results for the Adjustable Cutter Spacing Model This model corresponds to the case of specifing a lower and an upper bound on the target weight rate of filling. In using this model, the lower and upper limits of the peak value of the Chapter 5. Simulation ofthe Optimal Portioning Process weight distribution function of fish are set according to the lower and upper bounds of the target weight rate, w' min and w' , for the specified can size. For a target weight of 115 gram/ max can, the lower and upper bounds on the target weight rate are 42.59 and 54.76 grams/cm, respectively. A batch of 500 fish was generated and processed for optimal portioning in 50 separate batches each containing 10 fish. Figure 5.4 shows the statistical distribution of the produced can weights. This includes a fish placement error of u\ = 0 and rj = 0.03 cm, and cutter error of |i = 0 and o = 0.015 cm. It is clear that the percentage of acceptable cans is very high in this example and there are no over-filled cans, as indicated in Table 5.2. The weight range of the processed fish is approximately from 0.78 kg to 1.82 kg. Comparing the two models that have been developed and used in the present simulations, it is clear that for the same upper limit of the peak value of the weight distribution function of fish (the upper limit of 56 gm/cm in Table 5.1), the adjustable cutter spacing model yields a better percentage of acceptable cans, and process a larger range of fish fillets. This model also produces better filling quality. As indicated in Table 5.1 and Table 5.2, the required computational time interval is fairly stable and within 23 seconds per batch. This indicates that the optimal portioning process is computationally stable and feasible. It should be noted here that under-filled cans should be rerouted for weight compensation. The weight compensation of an under-filled can is easier than the adjustment of an over-filled one. Figure 5.4 shows that most of the under-filled cans weigh more than 90 grams. The insertion of the correct adjustment amount can be established easily in the present procedure, which 105 Chapter 5. Simulation of the Optimal Portioning Process 106 will result in faster and automated repatching. The present work developed optimal procedures for portion control of fish, which are applicable in can-filling. On-line sensing and modelling issues were investigated and appropriate techniques were developed. Simulation studies were carried out to determine the feasibility and evaluate the performance of the developed technology. Next chapter concludes the work by outlining the significance and primary contributions of the work and indicate directions for farther investigation. 6000 y 5000 -o c 4000 -- | 3000 -- S 20001000 -- o 410 40 70 100 "130 160 190 100 103 Can Weight [grams] 106 109 112 115 118 Can Weight [grams] (a) (b) Figure 5.4 Statistical Distribution of Can Weights Produced Using the Adjustable Cutter Spacing Model (a) Coarse Resolution (b) Fine Resolution. Table 5.2: Simulation Results Using the Variable Cutter Spacing Model. Peak Values of % of acceptable w \x) [gm/cm] Cans Limits of the 42.6 to 54.76 91.2 a %of OverFilled Cans 0 % of % of Processed Processed Computational Time Under- Good Fillet Weight Fillet Length Filled Quality [seconds] [cm] [gm] Cans Cans 0 5 8.8 54.7 1290 O It a It a Max. 159 36.4 2.7 19.4 0.28 20 a. Within +/- 5% of the target weight of can. b. The percentage of acceptable cans that contain one steak only. c. Time required to converge to an optimal solution. Chapter 6 Conclusions and Recommendations Manual portioning of products such as fish and meat is a monotonous, tiring, unpleasant and slow process. Automation of this process unquestionably leads to many benefits, both social and economical. The existing portioning machines by and large use volume-based technique even for weight-based packaging. Their accuracy is often unsatisfactory leading to underfills that can violate regulatory requirements and generate customer dissatisfaction, and overfills that can have negative economic implications. Also, product wastage during processing is an important consideration. The research carried out and presented in this thesis represents an important advancement in the field of portioning of food products for canning and packaging. A research project of this scale has not been reported in the particular application of optimal portion control. The present work has developed an analytical framework for the industrial process and has 107 Chapter 6. Conclusions and Recommendations 108 extended it to d e v e l o p industrially feasible m o d e l s . A s s o c i a t e d o p t i m i z a t i o n p r o c e d u r e s have b e e n d e v e l o p e d . T e c h n o l o g y has b e e n d e v e l o p e d for m o d e l l i n g a n d o n - l i n e s e n s i n g o f fish w h i c h f o r m a n i m p o r t a n t part i n the a p p l i c a t i o n o f the d e v e l o p e d p r o c e d u r e s . S t u d i e s h a v e been c a r r i e d out u s i n g realistic data on fish to validate the m o d e l s a n d p r o c e d u r e s d e v e l o p e d in this w o r k . T h e results have s h o w n m u c h potential a n d p r o m i s e o f i n d u s t r i a l a p p l i c a t i o n o f the d e v e l o p e d technology. 6.1 C o n c l u s i o n s T h e m a i n a c c o m p l i s h m e n t s o f this research are s u m m a r i z e d b e l o w : 1. A general p r o c e d u r e was d e v e l o p e d for o p t i m a l portion c o n t r o l o f natural objects s u c h as fish a n d meat. T h i s procedure is a weight-based p o r t i o n i n g m e t h o d u n l i k e the v o l u m e b a s e d approaches w h i c h are less accurate. It was demonstrated that the d e v e l o p e d approach can be i m p l e m e n t e d o n - l i n e i n an industrial process for o p t i m i z a t i o n o f f o o d portions in packaging. 2. A n i n n o v a t i v e c a n - f i l l i n g system for fish p r o c e s s i n g that satisfies the industrial requirements o n c o m p u t a t i o n a l speed a n d p o r t i o n i n g accuracy was c o n c e p t u a l l y d e v e l o p e d . T h e s y s t e m consists o f three m a i n steps; namely, p r e - f i l l i n g , f i l l i n g , a n d p o s t - f i l l i n g w h i c h are integrated u s i n g a hierarchical intelligent controller. T h i s new system a l l o w s fast, flexible, and accurate c a n - f i l l i n g o f fish portions, resulting i n high-quality products. 3. P r a c t i c a l procedures were d e v e l o p e d for o p t i m a l portion control o f natural objects. A p p l i c a t i o n o f the m e t h o d i n an innovative a n d automated c a n - f i l l i n g process technique was investigated. T h e o p t i m a l portion control was a p p l i e d to the p r e - f i l l i n g step o f the n e w c a n - Chapter 6. Conclusions and Recommendations 109 filling system. Significant accomplishments in this context include the following: • A model-based system was developed for fast on-line extraction (sensing) of the weight distribution functions of the processed fish fillets. The developed high-level sensor system utilizes laser/vision sensor and load sensor for on-line three-dimensional measurement of geometric features of fish and fillet weight, respectively. Low-level vision sensing was implemented in the laboratory and tested off-line. • A n experimental setup for off-line measurement of the cross-sectional variation of fish fillets was built. The accuracy of the experimental setup was tested using objects of known shape. The setup was used in off-line data acquisition of salmon, for use in the model development. • Several different models where developed for determining the optimal overlapping arrangement of fish, in the portioning process. Two of the developed models were found particularly applicable in industry, and also computationally tractable with regard to the industrial specifications on process speed. • A realistic structural model for fish body was developed to synthesize large-scale data on fish. The model uses information available in the literature of salmon anatomy. The fish data synthesized in the manner was used in the development of a model base for online sensing of the weight distribution function of fish and in simulating and evaluating the performance of the developed optimal portioning process of fish. • Statistical analysis of the performance of the optimal portion control method was conducted. The results showed good filling accuracy and quality of the produced cans. Chapter 6. Conclusions and Recommendations 110 6.2 R e c o m m e n d a t i o n s f o r F u t u r e W o r k The following are some recommendations for future directions of activities in the area of optimal portion control of food items and its application in can-filling of fish. 1. Non-destructive method for off-line measurement of the weight distribution function of fish (or, in general, for any food item) should be investigated. Medical imaging, such as computed tomography and ultrasound should be considered here. Developments toward cost effective use of such a technique would be particularly useful. 2. Development of practical and fast techniques for handling and overlapped placement of fish are essential in the practical implementation of the optimal portioning process that has been developed in this work. The fish have to be overlapped and positioned accurately at a rate of about one fish per second, for the approach to be commercially viable. 3. The design of a high speed filler is needed, but in the optimal portioning process developed in this work, the filling operation is simpler as it does not require forming of fish portions into filler packets that serve as portion measuring units. The primary task of the filler in the present process is to deliver the optimal portions into cans at high speed. 4. The net weights of the produced cans contain valuable information regarding the accuracy of the on-line sensing (estimation) process of the weight distribution functions. This information can be used in feedback to adjust the models of fish in the model-base. In fact, the use of feedback information will result in reducing the size of the data base of fish models. Specifically, by tuning the models using feedback information, inaccurate models can be removed and more accurate models can be further enhanced and retained. Also, models can Chapter 6. Conclusions and Recommendations 111 be generated on-line with the help of the weight data of the produced cans. Moreover, the information on can weight can be used to diagnose problems in the portioning process (e.g., cutting position and quality of fish portioning). 5. The application of the present optimal portion control method in the portioning of other types of food such as meat and poultry, should be investigated. Such applications will facilitate process automation of these industries, leading to considerable benefits. Bibliography [1] Cheng, C. H., Feiring, B. R., and Cheng, T. C. E., "The Cutting Stock Problem - A Sur- vey", International Journal of Production Economics, Vol. 36, pp. 291-305, 1994. [2] Davis, Lawrence, Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publishers, Inc., Los Altos, CA, [3] Davis, Lawrence, Handbook of Genetic Algorithms, Van Nostrand Reinhold, New NY, [4] 1987. York, 1991. Province of British Columbia Ministry of Agriculture, Fisheries & Food, British Colum- bia Seafood Industry Year in Review, pp. 2-3, July 1995. [5] De Silva, C. W., "Research Laboratory for Fish Processing Automation", International Journal of Robotics and Computer-Integrated Manufacturing, Vol. 9, No.l, pp. 49-60, 1992. 112 Bibliography 113 [6] Promation Incorporated, Weighmax Operating Manual, 5245 Shilshole ave. N.W. Seattle, WA 98107, 1987. [7] Ross, Henry M., "Can-filling Method for Meat-caning Process", United States Patent No. 3,874,426 April 1, 1975. [8] Sud-Est Equipment, Z.I. de Coutine 84000, Avignon, France, 1995. [9] PRC, 2582 South Tejon Street, Englewood, Colorado 80110, 1995. [10] Carruthers Equipment Comp., P.O. Box 40 Warrenton, OR 97146, 1995. [11] Milton, Gutterson, Food Canning Techniques, Noyes Data Corporation, Park Ridge, NJ, 1972. [12] Mencacci, Samuel A., "Apparatus for Canning Fish", United States Patent No. 3,700,386 Oct. 24, 1972. [13] De Silva, C. W. and Omar, F., "Automation and Optimization of the Can-Filling Process of Fish", Proceedings of the International Federation of Automatic Control Symposium on Large Scale Systems Theory and Applications, Patras, Greece, Vol. 1, pp. 342-347, July 1998. [14] American National Can Company, Operating and Maintenance Manual of the Canco Rotary Fish Filler - Model II, Chicago, IL, 1984. Bibliography 114 [15]Footitt, R. J. and Lewis, A. S., The Canning of Fish and Meat, Van Nostrand Reinhold Publisher, UK, 1995. [16] Ley, Dietmar and Braune, Ingolf, "Vision-based Level Control for Beverage-Filling Processes", Proceedings of SPIE - The International Society for Optical Engineering, Vol. 2247, pp. 245-252, 1994. [17] Thomson, Tad, "Computerpak Guarantees Package Weight, Cuts Overcompensation", The Packer, page 3, May 8 1982. [18]Muraro, R. P. and Wardowski, W. F , "Economics of Weight Bagging Machines for Florida Citrus Packing-houses", Proceedings ofthe Florida State Horticultural Society Vol. 97, pp.103-105, 1984. [19] Miller, W. M., "Non-Parametric Estimation of Automated Weight-Filling Machin-ery for Fresh Citrus", Journal of Food Engineering, Vol. 5, pp. 95-107, 1986. [20] Miller, W. M., Muraro, R. P., and Wardowski, W. F. "Analysis of Automatic Weight-Fill Bagging Machinery for Fresh Citrus", Applied Engineering in Agriculture, Vol.2, No.2, pp. 252-256, Nov 1986. [21]Khodabandehloo, K., "Robotic Handling and Packaging of Poultry Products", Robotica, Vol. 8, pp. 285-297, 1990. [22] Jacobs, Jonathan, "Machine Vision for Meat Processing: Making the Cut Automatic", Bibliography 115 Advanced Imaging, Woodbury, N.Y., Vol. 11, No.ll, pp. 21-24, 1996. [23]Dantzig, George, "Application of the Simplex Method to a Transportation Problem in Activity Analysis of Production and Allocation", Proceedings of Linear Conference Programming (June, 1949), John Wiley and Sons, New York, pp. 359-373, 1951. [24]LLNDO System Inc. Solver Suite: Software Mannual, Chicago, IL, 1996. [25] Winston, Wayne. L., Operations Research Applications and Algorithms, 2nd ed., PwsKent, Boston, MA, 1991 [26] Land, A. H. and Doig, A. G., "An Automatic Method for Solving Discrete Programming Problems", Econometrica, Vol. 28, pp. 497, 1960. [27] Nash, Stephen G. and Sofer, Ariela, Linear and Nonlinear Programming, McGraw-Hill, New York, NY, 1996. [28]Bazaraa, Mokhtar S., Sherali, Hanif D., and Shetty, C. M., Nonlinear Programming: Theory and Algorithms, John Wiley & Sons Inc., New York, NY, 1993. [29] Press, William H., Numerical Recipes in C: the Art of Scientifc Computing, Cambridge University Press, New York, NY, 1992. [30]Arora, Jasbir S., Introduction to Optimum Design, McGraw-Hill, Inc., New York, NY, 1989. Bibliography 116 [31] Turkay, Metin and Grossmann, Ignacio E. "Logic-Based MINLP Algorithms for Optimal Synthesis of Process Networks", Computers and Chemical Engineering, Vol. 20, No. 8, pp. 959-978, Aug 1996. [32] Bertsekas, D. L., Lower, G. S., Sandell, N. R., and Posbergh, T. A., "Optimal Short Term Scheduling of Large-Scale Power Systems", IEEE Transactions on Automatic Control, Vol. 28, pp. 1-5, 1983. [33]Fumagalli A., Balestra, G., and Valcarenghi, L., "Optimal amplifier placement in multiwavelength optical networks based on simulated annealing", Proceedings of SPIE TheInternational Society for Optical Engineering, SPIE, Bellingham, WA, Vol. 3531, pp. 268-279, 1998. [34]Maulik P. C., Carley, L. R., and Rutenbar, R. A., "Programming Based Topology Selection of Cell-Level Analog Circuits", IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 14, No. 4, pp. 401-412, April 1995. [35] Hunt D. O. and Sturger, R. H., "Application of an Information-Based Design for Assembly Theory to Assembly Workstation Design", Advances in Design Automation American Society of Mechanical Engineers Design Engineering Division, New York, NY, Vol. 65, Part l,pp. 173-182, 1993. [36]Graells M., Espuna, A., and Puigjaner, L., "Optimization of Process Operations in the Leather Industry", Computers and Chemical Engineering, Vol. 16, pp. S221-S228, 1992. Bibliography 117 [37] Floudas, Christodoulos A., Nonlinear and Mixed-Integer Optimization Fundamentals and Applications, Oxford University Press, New York, NY, 1995. [38]Nemhauser, G. L. and Wolsey, L. A., Integer and Combinatorial Optimization, J. Wiley, New York, NY, 1988. [39]Murty, K. G. and Kabadi, S. N., "Some NP-Complete Problems in Quadratic and Nonlinear Programming", Mathematical Programming, Vol. 39, No. 2, pp. 117-129, 1987. [40]Zamora, Juan. M. and Grossmann, Ignacio E., "Continuous Global Optimization of Structured Process Systems Models", Computers and Chemical Engineering, Vol. 22, No. 12, pp. 1749-1770, 1998. [41] Hansen, Eldon R., Global Optimization Using Interval Analysis, Marcel Dekker, New York, NY, 1992. [42]Rinnooy, Kan. A. and Timmer, G. T , "Stochastic Global Optimization Methods: Part I: Clustering Methods", Mathematical Prog ramming,Vol. 39, No.l, pp. 27-56, 1987. [43] Huang, Yun, Wu, Ning Jing, and Rundensteiner, Elke. A. "Effective Graph Clustering for Path Queries in Digital Map Databases", Proceedings of the International Conference on Information and-Know ledge Management, pp. 215-222, 1996. [44] Roytelman, I., Wee, B. K., and Lugtu, R. L., "Volt/Var Control Algorithm for Modern Distribution Managment System", IEEE Transactions on Power Systems, Vol. 10, No. 3, Bibliography 118 pp. 1454-1460, August 1995. [45] Cichocki, Andrzej and Unbehauen, Rolf, "Switched-Capacitor Artificial Neural Networks for Non-linear Optimization with Constraints", Proceedings ofthe IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 2809-2812, May 1990. [46]Urahama, Kiichi, "Equivalence Between Some Dynamical Systems for Optimization", IEICE Transactions on Fundamentals of Electronics, Sciences, Communications and Computer Vol. E78-A, No.2, pp. 268-271, February 1995. [47] Jelonek, Thomas, Reilly, James R, and Wu, Qiang, "Real Time Analog Global Optimization with Constraints: Application to the Direction of Arrival Estimation Problem", IEEE Transactions on Circuits and Systems II; Analog and Digital Signal Processing, Vol. 42, No. 4, pp. 233-244, April 1995. [48] Lustig, Irvin J. and Rothberg, Edward, "Gigaflops in Linear Programming", Operations Research Letters, Vol. 18, pp. 157-165, 1996. [49] Soloman, Sabrie, Sensors and Control Systems, McGraw-Hill, Inc., New York, NY, 1994. [50] Smith, Brian J. and Adhami, Reza R., "Medical Imaging", IEEE Potentials, Vol. 17, No. 5, pp. 9-12, 1998. [51]Wu, Jia, Sarkar, Fazlul H., Singh, Harpreet, and Shah, Shishir, "Positron Emission Tomography", IEEE Potentials, Vol. 17, No. 5, pp. 13-16, 1998. Bibliography 119 [52] Lammerink, Theo S. J., Fred Dijkstra, Zweitze Houkes, and Joost van Kuijk, "Intelligent gas-mixture flow sensor", Sensors and Actuators, Part A, Vol. 47, pp. 380-384, 1995. [53] Wide, P., "A Human-Knowledge-Based Sensor Implemented in an Intelligent Fermentation-Sensor System", Sensors and Actuators, Part B, Vol 32, pp. 227-231, 1996. [54] Yatsenko, Vitaly, "Determining the Characteristics of Water Pollutants by Neural Sensors and Pattern Recognition Methods", Journal of Chromatography, Vol. 722, pp. 233-243, 1996. [55] Otmar, Loffeld, "Sensors, Sensor Systems, and Sensor Data Processing", Proceedings of SPIE-The International Society for Optical Engineering, Vol. 3100, Munich, FRG, June 1997. [56] Rheingans, Penny and Nichols, John, "Interactive 3D Visualization of Actual Anatomy and Simulated Chemical Time-Course Data for Fish", Proceeding of the IEEE Visualization Conference, Los Alamitos, CA, pp. 393-396, 1995. [57] Coshell, Lee, Ralph G. Mclver, and Ray Chang, "X-ray Computed Tomography of Australian Oil Shales: Non-destructive Visualization and Density Determination", Fuel, Vol. 73, No. 8, pp. 1317-1321, 1994. [58] Orshi, Thomas H., Anderson, Aubrey L., Leonard, John N., and Bryant, William R., "Use of X-ray Computed Tomography in the Study of Marine Sediments", Civil Engineering in the Oceans V: Proceedings of the International Conference, College Station, Texas, pp. Bibliography 120 968-982, November 1992. [59] Phillips, D. H. and Lannutti, J. J., "Measuring Physical Density with X-ray Computed Tomography", NDT & E International: Independent Nondestructive Testing and Evaluation, Vol. 30, No. 6 pp. 339-350, 1997. [60] Gamage, L . B. and de Silva, C. W., "A Model-Based Approach for On-line Extraction of Complex Feature Through Image Processing", Proc. ASME Winter Annual Meeting, Atlanta, GA, DSC-Vol. 30, pp. 59-64, December 1991. [61]Bilton, H. T , "Length-Weight Relations for Adult Sockeye, Chum, and Pink Salmon", Canadian Manuscript Report of Fisheries and Aquatic Sciences, No. 1846, Department of Fisheries and Oceans, Pacific Biological Station, Nanaimo, BC, November 1985. [62] Storbeck, Frank and Daan, Berent, "Weight Estimation of Flatfish by Means of Structured Light and Image Analysis", Fisheries Research, Vol. 11, pp. 99-108, 1991. [63]Naiberg, A., Petrell, R. J., Savage, C. R., and Neufeld, T. P., "A Non-Invasive Fish Size Assessment Method for Tanks and Sea Cages Using Stereo Video", Proceedings of the Aquacultural Engineering Conference, Spokane, WA, pp. 372-381, June 1993. [64] Boyle, William A., Asgeirsson, A., and Pigott, George M., "Advances in the Development of Computer Vision Fish Biomass Measurement Procedure for Use in Aquaculture", Proceedings of the Aquacultural Engineering Conference, Spokane, WA, pp. 382-392, June 1993. Bibliography 121 [65] Beddow, T. A. and Ross, L. G., "Predicting Biomass of Atlantic Salmon From Morphometric Lateral Measurements", Journal of Fish Biology, Vol. 49, pp. 469-482, 1996. [66]Beacham, Terry D., Murray, Clyde B., and Withler, Ruth E., "Age, Morphology, and Biochemical Variation of Yukon River Chinook Salmon", Transactions of the American Fisheries Society, Vol. 118, pp. 46-63, 1989. [67] Swain, D. P., "Morphological Differences Between Hatchery and Wild Populations of Coho Salmon (Oncorhynchus Kisutch): Environmental Versus Genetic Origin", Canadian Journal of Fisheries and Aquatic Sciences, Vol. 48, pp. 1783-1791, 1991. [68] De Silva, C.W., Control Sensors and Actuators, Prentice Hall, Inc., Englewood Cliffs, NJ, 1989. [69] Smith, L. S. and Bell, G. R., A Practical Guide to The Anatomy and Physiology of Pacific Salmon, Department of The Environment Fisheries and Marine Service, Miscellaneous special publication 27, Northern Miner Press Limited, Ottawa, Canada, 1975. [70] Shaw, W, Biological Sampling Manual for Salmonids - A Standardized Approach for the Pacific Region, Canadian Technical Report of Fisheries and Aquatic Sciences, Nanaimo, BC, 1998, [71]Einen, O., Waagan, B., and Thomassen, Magny S., "Starvation Prior to Slaughter in Atlantic Salmon (Salmo Salar) I. Effects on Weight Loss, Body Shape, Slaughter and Fillet Yields, Proximate and Fatty Acid Composition", Aquaculture, Vol. 166, pp. 85-104, Bibliography 122 1998. [72] Gjerde, Bjarne, "Body Traits in Rainbow Trout. I. Phenotypic Means and Standard Deviations and Sex Effects", Aquaculture, Vol. 80, pp. 7-24, 1989. [73] Rye, M. and Refstie, T., "Phenotypic and Genetic Parameters of Body Size Traits in Atlantic Salmon Salmo Salar L.", Aquaculture Research, Vol. 26, pp. 875-885, 1995. Appendix A Measurement of Cross-Sectional Area Distribution A . l Introduction Direct measurement of the distribution of the cross-sectional area of fish can be done by scanning technique such as computed tomography. This technique can produce multiple images of the cross-section of a fish along its length. The area of each cross-section is measured by integrating the gray pixels of each cross-section. The distribution of the crosssectional area is then estimated by curve fitting the area values with the corresponding positions along the fish length. Although the accuracy of this CT technique is high, it is too costly for use in the present research. In this appendix, a simpler and less costly approach, which was developed for measuring the variation of the cross-sectional area of fish, is outlined. 123 Appendix A. Measurement of Cross-Sectional Area Distribution 124 Mathematically, the cross-sectional area distribution of a fish is the volume rate with respect to length of the fish. An experimental setup is developed and used to measure the volumetric variation of a fish, as required in the present approach. A.2 Cross-sectional A r e a of Fish Define the partial volume as the accumulated volume from the point JC, to x, (See Figure A.l). (A.1) x Figure A.l Partial Volume of Fish. The partial volume v{x) can be easily measured using the experimental setup illustrated in Figure A.4, which has been developed. The system consists of a water container, a stepper motor with drum, a laser transducer, and a host computer with data acquisition hardware and software. Appendix A. Measurement of Cross-Sectional Area Distribution 125 Stepper Motor Computer / Data Acquisition System Figure A.2 A n Experimental Setup for Measuring the Partial Volume Function. Figure A . 5 describes the immersing process of fish where the fish initially positioned above the water surface. In the immersed position, the water level in the cylinder is given by X. The water level is also referred by x as measured from a moving coordinate frame, that is attached to the fish body and located at a distance q from a fixed reference frame X. The volume of the fish portion, that is submerged in the water (partial volume), is equal to the volume of the cylinder corresponding to the raised water level due to the plunging of the fish into the cylinder. As the water level raises from X to X, the partial volume of the fish at x as defined in 0 Figure A. 1, can be calculated as v(x) = A x(X-X ) c Q where A is the cross-sectional area of the cylinder. c (A.2) Appendix A. Measurement of Cross-Sectional Area Distribution 126 Figure A.3 Measurement of Fish Partial Volume. The water level as measured with respect to the moving coordinate frame q is given by X-q x = (A.3) The position of the moving coordinate frame q is controlled and measured by the host computer through the stepper motor. The water level X is measured using the laser transducer. By incrementally plunging the fish from an initial position q , one can generate two vectors 0 containing the partial volume v(x) of the fish and the corresponding location x as follows: A x(X -X ) c f 0 A x(X-X ) v = c 0 A x(X -X )=0 c and 0 0 (A.4) Appendix A. Measurement of Cross-Sectional Area Distribution 127 X -q f f (A.5) X-q Where and < y j are the final water level and the final position of the moving coordinate frame, respectively, such that the fish is totally submerged. The partial volume function is then evaluated by curve fitting of the data x and v. The cross-sectional area of fish is then calculated using equation (A.l), for example, the cross-sectional area of fish is assumed to fit a polynomial function of fourth order (n = 4). The polynomial coefficients of A(x) are then evaluated by curve fitting of the data x and v. This is illustrated as follows: A(x) = 4 + ax (ZQX 3 x + ax 2 2 +a x + a 3 (A.6) 4 substitute in equation (A.l) 0 5 a >(x) = A(x)dx = —x where l a 4 + —x 2 a 3 + —x 3 a 2 + —x (AJ) +a x - c 4 (A.8) v(x) = e a 15 |5 X 1 4| \~4 X e = 1 3| \3 X 1 2| \~2 X , and a = (A.9) \a A Appendix A. Measurement of Cross-Sectional Area Distribution 128 Note that, although A(x) is defined only in the interval x <x <Xp the coefficient c is a 0 constant representing the virtual volume generated by the continuous polynomial function (A.6) from x = 0 to x = x . The size of the vector x is determined by the number of incremental 0 movements of the moving coordinate frame during the immersing process of fish in the interval x < x < xy. By substituting each element of x, and the corresponding element of v in 0 equation (A.8), a number of equations are generated, which can be solved to determine the a, as follows: r - T - T a = Ea v = T a = (EE) -1 T _ E v (A. 10) (A.11) Here e, denotes the values of e evaluated using the ith element in x. This represents the least squares solution for the curve fitting of data. In the next section the accuracy and resolution of the experimental setup are determined and examined. A . 3 V a l i d a t i o n o f the E x p e r i m e n t a l Setup A.3.1 Setup Uncertainty In order to examine the uncertainty in the measurements from the experimental setup first the laser/data acquisition resolution of the data from the laser sensor is determined by taking several readings from a steady water surface. The readings were found to be normally distrib- Appendix A. Measurement of Cross-Sectional Area Distribution 129 uted with a standard deviation a, of 0.000174 cm. The accuracy of laser-data acquisition for a 99.73% confidence interval is given by [68] R = ±3 ai = ±0.000522 (cm) (A. 12) t The expected resolution of the calculated v(x) values, using equation (A.2), is twice the R, multiplied by the tank cross-sectional area A . But due to the presence of the laser reflector c and the uncertainty of the response of the water surface, the resolution of V(JC) should be experimentally evaluated. This can be achieved by submerging an object of known volume several times and measuring the change in the laser readings. The volume is calculated using equation (A.2). The result is found to be normally distributed with a standard deviation of 1.12 cm . The accuracy of the volume measurement is given by 3 R = ±3cj = ±3.36 (cm ) (A. 13) 3 v v It is important to mention here that the resolution of the estimated A(x) of an object would be better than (A. 13) as a result of averaging in the curve fitting process that is used. The larger the amount of data collected during the plunging process, the better the estimation accuracy of A(x). A.3.2 Example Cases A.3.2.1 Steady Cross-Sectional Object This test is performed using a cylindrical metal block of a diameter of 7.63 cm and length of 7.6 cm as the object. The block is first placed in the tank (A = 506.71 cm ) above the water 3 c level, and then lowered in displacement steps of 3.02 mm size (the step size is governed by the Appendix A. Measurement of Cross-Sectional Area Distribution 130 motor step angle and the drum diameter). Two vectors v and x are calculated using equations (A.2) and (A.3) respectively. For a cylindrical object, the cross-sectional area is a constant value given by A(x) = a . Hence, 0 a= a 0 c _ ,e = X (A. 14) -1_ Applying equation (A. 11), the estimated cross-sectional area is a = 46A cm . The actual 2 0 2 value is given by nD /4 = 45.7 cm . Hence, the estimation error is calculated as, 2 Estimation error = 46.1 -45.7 = 0.0088 - 0.9 % 45.7 Figure A.4 compares the partial volume of the cylindrical object as measured using the experimental setup with the actual one. 350 * Measured using the experimental setup —Theoretical values 0 2 4 6 Body coordinate of fish x (cm) 8 Figure A.4 Partial Volume of a Cylindrical Object. Appendix A. Measurement of Cross-Sectional Area Distribution 131 A.3.2.2 Varying Cross-Sectional Object This test is performed using a triangular object with a tip angle of 6 = 49.51° and thickness 1.15 cm. The object is immersed in the water, tip head first, in incremental steps of 3 mm. In this case the cross-sectional area is a linear function, given by A(x) = a$i + a,. Hence, 1 a 2 Q 2 X a = a (A.15) x X c -1 The cross-sectional area is estimated by applying equation (A.l 1) to the collected data, to obtain, A(x) = 1.0506x-0.5598 = 1.0602(x - 0.5328) (A. 16) The value 0.5328 represents x which is the starting position above the water surface. 0 The actual cross-sectional area and the partial volume are calculated from the object dimensions as A(x) = (^2tan(^y^)x 1.15^ x ( X - J C ) = 1.0605(x-x ) 0 0 (A.17) v(x) = 0.53025(X-JC ) 2 0 Figure A.5 shows the experimental data, curve fitted results, and the actual function of the triangular partial volume. The associated errors are the deviations of the experimental data or the curve fitted function from the actual partial volume of the object. The error of the estimated cross-sectional area is Appendix A. Measurement of Cross-Sectional Area Distribution 132 200 4 1 5 1 r 10 15 20 Distance along the object length (cm) Figure A.5 Partial Volume Estimation of the Triangular Object. ( * Experimental data; nActual partial volume; Curve-fitted partial volume) Estimation error = 1.0506(x-x )- 1.0605 (x-x ) , = -0.0093 = 0.93 % 1.0605(x-x ) n n (A.18) 0 It is clear from Figure A.6 that the percentage of the experimental error is rather high for small values of the partial volume function, but by curve fitting the data it has been possible to virtually eliminate the error. A.4 Measurement of Cross-sectional Area of Fish First a fish is vertically suspended from its tail side, with the head end at a distance of x above 0 the water surface. Initially the body coordinate frame of the fish is assumed to be touching the water surface; i.e. q = X (See Figure A.3). Data is collected during the immersing process, 0 0 while the fish is lowered in steps of 6.04 mm. The two vectors x and v are computed using Appendix A. Measurement of Cross-Sectional Area Distribution o 133 10 i ftf-V 5 r 0 1 1 1 5 10 15 20 Distance along the object length (cm) Figure A.6 Estimation Errors for the Triangular Object (—*— Experimental results; —•-Curve-fitted results). equations (A.2) and (A.3). First the data were plotted to select only the points within the interval x < x < Xf. There is no need to measure x as it can be obtained from the collected Q 0 data. The polynomial coefficients are calculated using equation (A. 11). Then, by substituting in equation (A.6), the cross-sectional area of this sample fish is determined as, A(x) = 0.0000001x + 0.0024x -0.1894x + 2.8024x +26.152 4 3 2 Figure A.7 shows the collected data, estimated partial volume function v(x), and the estimated cross-sectional area A(x), for a sample of pink salmon. Appendix A. Measurement of Cross-Sectional Area Distribution Figure A.7 (a) Partial Volume Function of Fish ( + Experimental data;—Curve fitting function), (b) Estimated cross-sectional area, A(x), of fish. Appendix B Laser/Vision System Sensing of three-dimensional coordinates of the surface of fish body is important in the implementation of the technology that is developed in this thesis. In the course of the present research a laser/vision system was built for this purpose. This system can identify 3D coordinates of feature points that appear on the top surface of a processed object (fish). The system consists of a CCD camera, a structured laser light, and image processing hardware and software. Figure B . l illustrates the configuration of the laser/vision system and the placement of the object under investigation. B . l S y s t e m C o m p o n e n t s a n d Specifications 1. A JVC CCD color video camera, model number TK-1070U. 2. Laser structured light manufactured by Lasiris Inc., Canada. It is a multiple-line structured laser light with a wave length of approximately 635 (nm). The laser diode generates 11 135 136 Appendix B. Laser/Vision System parallel lines with an interbeam angle of 1.5 degrees. 3. Sharp GPB-2 image processing board located in to a 486 PC host computer. The board is used only to capture gray images. To Host Computer Contains Image Processing Hardware and Software x' Figure B. 1 Vision/Laser System for the Measurement of Fish Body Features. B.2 F e a t u r e P o i n t C o o r d i n a t e s The intersection of the laser lines with the fish body appear as curved lines in the captured image. The 3D coordinates of any point on these lines can be calculated using the image coordinates, parameters of camera and laser light, and image coordinates of the laser lines. The position vector of a point F on the body surface that coincides with a laser plane, is defined as OF with respect to the origin O of the system coordinate frame and can be Appendix B. Laser/Vision System 137 expressed as, (See Figure B.2) OF = OC+CF (B.l) Here CF is a percentage of CP. Accordingly, OF = O C + p , C P (B.2) Now substitute the fact that CP = OP-OC (B.3) into equation (B.2), which gives OF = OC+ (3, (OP-OC) (B.4) Image Plane C L / Camera Position Laser Light Position Focal Length Figure B.2 Three-Dimensional Coordinates of a Feature Point. Appendix B. Laser/Vision System 138 or, OF = (1 - p ] ) O C + p , O P (B.5) Also the position vector of F can be expressed using the laser diode position as, 0~F = 0~L + L~F (B.6) Similarly, it can be expressed in terms of the point L and d as, OF = (1 -(3 )OL+fJ aD 2 (B.7) 2 Solving equations (B.5) and (B.7) the components of OF are obtained as, {x (\-z /z )-x )x d L c L d~ p^ L^ C>~ L x x z z x d- p^L c)- L y F x X /z x z ( - d) x L Zp = x p d~ p( L ' c)~ L x x z / z x where x , y , and x are computed using the captured image as, p d _ G, p ~ j x x F' y = jy' > p (B.9) F c , d ~j e X X The ratio C/f can be computed by taking an image of a reference length L Then one has r C r 7 = TT L (B.10) where L is the actual reference length and L' is the corresponding reference length in the r image. r Appendix B. Laser/Vision System 139 B.3 C o m p u t a t i o n o f Feature Parameters The feature parameters that are to be measured on-line are written in a vector format as, x FP = (B.U) x where x , x„ x , and x are the positions of the head side of fillet, tail side of fillet, the dorsal h d a feature point, and the anal feature point, respectively. Also, H and W are the height and the fa fa width of the fillet, respectively, at the anal feature point (See Figure B.3). The first four feature parameters are computed using their equivalent image points and the z-component of the associated lower and upper curves (See Figure B.4). y Upper Curve > x' 11 Lower Curve Thickness Curve 3 2 1 Figure B.3 Measurement of a Fish Geometry. Appendix B. Laser/Vision System 140 C Camera Position e Feature Point e' Feaure Point Image Lo (x), or U (x) z z Figure B.4 A Feature Point and Its Image. Using Figure B.4, the feature positions are evaluated as, x = \x\T_ (x) + ^-x-C =0 x = lx\T (x)+^rx-C =0 h t z (B.12) x = \x\U (x) + ^-x-C d z =0 x = | x\Lo (x) + -£-x - C = 0 a z where T (x), U (x), and Lo (x) are the z-components of the fillet thickness, the upper curve, z z z and the lower curve, respectively. These curves are estimated by curve fitting the zcomponents and the x-components of the related points, U T or Lo Equations (B.8) and h h r Appendix B. Laser/Vision System 141 (B.9) are used to extract the 3 D coordinates of these points from the corresponding image coordinates. The remaining two feature parameters H and W are computed using the fillet curves as, fa fa H =U (x )-Lo (x ) fa W fa y a y a = T (x ) z a where U (x) and Lo (x) are estimated in a manner similar to what is used for U (x) and Lo (x). y y z z
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Development of sensing and processing technologies...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Development of sensing and processing technologies for optimal portion control in an automated can filling… Omar, Farag 2000
pdf
Page Metadata
Item Metadata
Title | Development of sensing and processing technologies for optimal portion control in an automated can filling system |
Creator |
Omar, Farag |
Date Issued | 2000 |
Description | This thesis investigates the problem of portion control of natural objects such as fish and meat for packaging, and develops a new method for optimal portioning. Food portions that are processed for packaging or canning should be optimized with respect to a specified "target" portion, for reasons such as wastage reduction, regulatory requirements, consumer appeal, and aesthetic considerations. The approach of optimal portion control that is developed involves cutting a set of objects into pieces by taking into account the weight distribution of each object and grouping the pieces into package portions according to a weight-based optimality criterion. First, a general optimization model is developed for the portioning control problem. Next, the model is made specific to a practical and innovative approach for can-filling of fish. An optimization model is developed for the portion control of fish where the objective is to minimize the weight deviation of the canned portions from the target net weight of a can. The portioning process is then refined by incorporating realistic assumptions and constraints that exist in industrial fish portioning processes. The modified model is further checked again for feasibility, and the model refinement process is continued until a feasible optimization model that can be implemented on-line in an industrial plant, is achieved. The model that is developed in this manner provides a computational speed for portion control that is consistent with the typical industrial requirements of the process speed and filling accuracy. Clearly, the weight accuracy of the processed portions can be further improved by providing the capability of adjustable blade spacing in portion cutting. In particular, during cutting of fish into can-filling portions, if one were to start from one end of the optimally arranged placement of fish and integrate the overall optimal weight distribution function such that the weight between two adjacent blades equals the target weight of portion, then the portion error will be zero. However, there are practical constraints on portion dimensions. Also, it was found that the portion accuracy can be further improved by specifying not just one target weight rate, but rather an interval of lower and upper bounds. This optimization problem with adjustable blade spacing is analyzed and evaluated through computer simulations. A comparison is made with the optimization model that uses fixed blade spacing. In the practical process of portion control that is developed here, the fish are placed in a linear overlapped arrangement according to the optimality criterion and cut into canning portions using an array of gang knives. To determine the optimal placement the weight distribution function of each incoming fish has to be measured on-line. The accuracy of a portion weight is greatly influenced by the accuracy of the weight distribution sensor itself. A high-level sensing approach is developed for this purpose. It involves the off-line development of nondimensional structural models of fish which contain correlations between the weight distribution function and simple geometric parameters that can be measured at high speed and high accuracy. Then the on-line sensing involves measurement of the geometric parameters for each incoming fish and matching them to a fish model in the model-base. To analyze the performance of the optimal portioning process of fish, a comprehensive model of fish body is developed, based on real data on salmon. The model is used to generate large quantities of realistic data, which are used in a computer simulation of the optimal portioning process. The results of simulation, which incorporates such practical influences as measurement error, show that the developed sensor technique is able to provide good accuracy in sensing weight distribution. Results further show that the optimal portion control developed in this research, for can-filling of fish, is quite feasible and provides adequate production speed, and good accuracy and quality of the product. |
Extent | 9638126 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-10-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0090808 |
URI | http://hdl.handle.net/2429/13872 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mechanical Engineering |
Affiliation |
Applied Science, Faculty of Mechanical Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2001-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2001-726487.pdf [ 9.19MB ]
- Metadata
- JSON: 831-1.0090808.json
- JSON-LD: 831-1.0090808-ld.json
- RDF/XML (Pretty): 831-1.0090808-rdf.xml
- RDF/JSON: 831-1.0090808-rdf.json
- Turtle: 831-1.0090808-turtle.txt
- N-Triples: 831-1.0090808-rdf-ntriples.txt
- Original Record: 831-1.0090808-source.json
- Full Text
- 831-1.0090808-fulltext.txt
- Citation
- 831-1.0090808.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0090808/manifest