{"cells":[{"metadata":{"_uuid":"3f33e585ea62cb5fdeca01902d21f557337bbec5","_cell_guid":"fa89d75e-9575-4e2d-8970-b47eee42289d"},"cell_type":"markdown","source":"# Table of Contents\n\n1. The competition\n2. Summary of my approach and results\n3. Algorithm details\n4. Instructions for running my code\n5. What I've learned about competing"},{"metadata":{"_uuid":"b149d78b6ed70eb891d6ca2590c4f86ee27bfb59","_cell_guid":"4a778310-a5e8-4ee3-9484-5e8fa2de8736"},"cell_type":"markdown","source":"# 1. The competition\n\nIn the [Kaggle Passenger Description Algorithm Challenge](https://www.kaggle.com/c/passenger-screening-algorithm-challenge), competitors were asked to identify and locate hidden threats in millimeter-wave 3D body scans. A typical scan had 0-3 threats distributed among 17 predefined body zones. The train and test datasets were each comprised of about 1200 scans. Multiple image formats were provided, from 2D datasets that were order 10GB in size, to 3D datsets that were order 1TB in size. Competitors were asked to predict the probability of threats in all 17 body zones for each scan."},{"metadata":{"_uuid":"e9c9a26283c8bfd83b9546360c5d304acf5fc7f6","_cell_guid":"595b4e4e-692e-47ba-a2ab-3317e65966f2"},"cell_type":"markdown","source":"# 2. Summary of my approach and results\n\nYou can download [my complete solution on github](https://github.com/naterm60/KagglePassengerScreening). Instructions for running it can be found in section 4 of this writeup.\n\nNote that this is my first full Python project, first project in the cloud, and my first use of transfer learning. Any suggestions are welcome. My background includes math/physics, optimal methods, and extensive use of Mathematica, along with some software engineering and high performance computing.\n\nI chose to develop a way of representing a passenger's body surface in 2D, since it's topologically 2D to begin with. I made the 2D representation independent of body type and pose, so that body zones were in dependable positions in the output images. Image channels corresponded to surface characteristics, as describe in the section \"Algorithm details\".\n\nNext, threats needed to be detected. I planned to start simple and progress to more complex approaches as I learned more about deep CNN's. The very simplest approach was to get color histograms of body zones and then identify threats with a binary classifier. Next, I would try the simplest type of transfer learning. The ultimate approach, I thought, would be to generate hand-drawn masks for the entire train dataset, train a network to duplicate the masks, and then train some top layers for threat identification and localization.\n\nMy simplest approach (color histograms + logistic regression) worked suprisingly well in stage 1, putting me in the top 20% of contestants. So even without using shape and texture information in the processed images, the technique performed well.\n\nI ran out of time because this is my first project done fully in Python, I started with only 2 months to go, I have no CNN experience, yada yada. I made late submissions after the competition closed, and found that the color histogram approach did not generalize at all to stage 2 data. Transfer learning did generalize, however, giving a score of 0.22494, which would have been in the bronze medal range."},{"metadata":{"_uuid":"19849d5f0a7f62c1fd94da28b420c9ac445584c1","_cell_guid":"6a3f2751-f14c-4c36-b6ac-1af4d137e24f"},"cell_type":"markdown","source":"# 3. Algorithm details\n\nI'll now discuss my algorithm in more detail. For full detail, refer to the code. I did something a bit different from most competitors. Using .a3d files as input, I \"unwrapped\" a passenger's body surface into a 2 dimensional representation using a cylindrical coordinate system for each body-part. The 7 body-parts were the 2 legs, 1 trunk, 2 biceps, and 2 forearms, as drawn in Figure 1. A cylinder's axis was allowed to curve but slices were parallel to one other.\n\n\nFigure 1. The seven body parts and the assumed coordinate frame\n
\n\nCylindrical coordinate systems were registered to body-parts using estimates of the positions of wrists, elbows, shoulders, feet, the buttock/leg meeting point, and the center of mass.\n\nShoulder height was estimated as follows. Scans were understood to be in the standard reference frame, with the first array dimensions being x, the second y, and the third z, with the passenger placed as shown in Figure 1. The y dimension was averaged over, binarized, and negated, yielding an array like Figure 2. Summing over the y dimension of this array gives a list like the one plotted in Figure 3. Shoulder height was determined by finding the first list element with a value greater than a threshold value.\n\n\nFigure 2. Shoulder region of a passenger, summed over the y dimension, binarized, and negated.\n
\n\n\nFigure 3. The array in Figure 2, summed over the z axis.\n
\n\nGroin height was estimated as follows. A scan was averaged along the x direction and then binarized. A side profile of the buttock was found by getting, for each z coordinate, the largest y coordinate with array value over a threshold. This list of y coordinates is shown in Figure 4. Groin height was determined from this list by taking the derivative and finding the position of the maximum. This method proved to be much more reliable than direct methods of determining groin height. More direct methods failed due to the the effect of sexual organs, contraband, and thigh gap variation.\n\n\nFigure 4. Side profile of a buttock.\n
\n\nThe positions of elbows and wrists were determined using techniques similar to those used for estimating groin and shoulder height. The head was erased prior to elbow and wrist position estimation to prevent interference.\n\nA cylindrical coordinate system was then fitted to each body part. This representation of a body segment's geometry was called a \"waffle stack\", or just \"waffles\", and is depicted in Figure 5. It was determined as follows. First a basis (**u**, **v**, **w**) was chosen for each body part. There was no rotation for the legs and trunk, so (**u**, **v**, **w**) = (**x**, **y**, **z**) for the legs and trunk. Basii for arm segments were determined using the positions of shoulders, elbows, and wrists. Arm segments were rotated volumetrically to align basii with array axes. For all the body segments, ellipses were then fitted at about 100 positions along the **w** direction. Fitting an ellipse involved determining the offsets and axis lengths in the (**u**, **v**) plane. Ellipse axes were aligned with the **u** and **v** axes. The lists of ellipse offsets and ellipse axis lengths were median filtered to remove spikes and then Savitzky-Golay smoothed.\n\n\nFigure 5. Two types of waffle stacks.\n
\n\nEach body part was transformed to a cylindrical coordinate representation using that body part's waffle stack. This gave an array with dimensions (r, θ, w), where r is radius, θ is the angular coordinate, and w is the axial coordinate. For each (θ, w) coordinate, I found the peaks along the r direction. The tallest peak's height, position, and width are the surface reflectivity, radius (AKA surface height), and thickness, respectively, for coordinate (θ, w). That's not a precise description, by the way, since the determination of peak height, position and width (I.e. zeroeth, first and second moments) needs to be tweeked to give good results. Anyway, I end up with surface reflectivity, radius and thickness for each (θ, w) coordinate. This can be respresented as an image with coordinates (θ, w) and 3 channels containing the reflectivity, radius and thickness.\n\nAll 7 body-part images were joined into one image and saved. The entire proces reduced a 330GB volumetric dataset to 500MB, a 660 times decrease in size. Throughput was 1 scan every 35 seconds. Although 35s is too slow for passenger screening, the algorithm is not parallelized at all. The body segments could be processed in parallel for a 7x speedup, and waffles could be processed in parallel for another order 10x speedup.\n\nI call the combined image a \"body image\". Each body zone defines a rectangular region of the body image. For each scan and each body zone, the zone's rectangular region was extracted. (The sensitive area, region 9, actually consisted of 4 rectangular regions: 2 on the trunk and 1 on each leg. These regions were extracted and joined into a single image.) \n\nFor each body zone, PCA was performed on all the images that did not contain threats. Projection of an image into the subspace defined by the top few principal components allowed estimation of an image's \"background\", or the normal non-threat variation. Subtraction of this variation removed differences due to weight, gender, pose, etc. Threats pop out in the resulting images as areas of saturated color on a gray backghround. I would show the images if I could, but competition rules don't permit it.\n\nAll the background-subtracted images were resized to (139,139) and fed to InceptionV3 for bottleneck feature extraction. The resulting 3x3x2048 vectors were average pooled, yielding a vector of length 2048 per image. These vectors and the known threat probabilities were used to fit a logistic regression binary classifier."},{"metadata":{"_uuid":"726781efe9b32ea05b4f99a75d36b10de91f7e12","_cell_guid":"aa3727a1-2349-4384-89db-0870d5bcc5c7"},"cell_type":"markdown","source":"# 4. Instructions for running my code\n\nThese instructions assume that you were a competitor and have access to the competition's bucket. After the competition closes you won't have access to the dataset, but you can still look at the code. \n\n1. Copy stage1_a3d and stage2_a3d to your own bucket.\n2. Create a Google Cloud Compute Engine VM instance. I used 8vCPUs, 52GB RAM.\n3. Install Google Cloud Datalab on the VM.\n4. Download my [github repository](https://github.com/naterm60/KagglePassengerScreening)\n5. Upload my project to a folder on your Datalab VM\n6. Create the following empty subfolders within the project folder: embedded2D/stage1/, embedded2D/stage2/, highlight/stage1/, log/.\n7. Upload these competition files to the project folder: stage1_labels.csv, stage1_sample_submission.csv, stage1_solution.csv, stage2_sample_submission.csv\n8. Open the notebook embed2D.ipynb\n9. In the section titled \"Project-specific imports and initializations\", change the bucket name to your own bucket.\n10. Run the entire notebook, using python 3. It takes about 30 hours to embed all the stage 1 and 2 scans.\n11. Open the notebook transferLearning.ipynb\n12. Run all the cells in transferLearning.ipynb, which takes about an hour."},{"metadata":{"_uuid":"e7548f2964b6dec457bf30bdfd0a542488f3bcf0","_cell_guid":"6bfb4bc7-d89f-48cd-a64e-e6406de1a969"},"cell_type":"markdown","source":"# 5. What I've learned about competing\n\nFor whatever it's worth, here's what I've learned to do to place well in competitions:\n\n1. Approach competitions with a \"must-win\" attitude. Ruthlessly make the best choices in each area of a model and learn technologies where necessary. \n\n2. Prefer general-purpose existing tools over large, custom codebases developed for fun. There's nothing wrong with the latter if one is aiming for a discovery, but it's not a good strategy for placing well.\n\n3. Take a sink-or-swim approach. I have probably learned more by throwing myself into actual competitions than I could have learned by wading in practice problems. Practice problems are great if you're absolutely new to coding or data science. But if you have experience with math, coding, and crunching data, it's better to skip the pedantic approach. Live competitions are far more motivating and entertaining, and you can still look at practice problems and tutorials for guidance.\n\n4. Do extensive exploratory data analysis. Create methods for finding and investigating a model's worst deficiencies.\n\n5. Start working as soon as a competition is announced. This gives more time to think of improved approaches. Hopefully, one could be finished halfway through the competition, with months remaining to tweak the model.\n\n6. Get a prototype running as quickly as possible, and start making submissions.\n\n7. Do everything to make the cross-validation (CV) train vs. test difference similar to the stage 1 vs. stage 2 difference. Rely exclusively on CV to check a model's performance, rather than using the 1st stage leaderboard for that.\n\nIn this competition I did well with items 1 and 3 above. In the [Web Traffic Time Series Forecasting Competition](https://www.kaggle.com/c/web-traffic-time-series-forecasting/leaderboard), where I placed 5th and won gold, I did well with everything except item 5. "}],"metadata":{"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":1}