Implementacja algorytmu DeepDream w pakiecie Keras
Zaczniemy od konwolucyjnej sieci neuronowej wytrenowanej na zbiorze obrazów ImageNet. Pakiet Keras zawiera wiele takich sieci. Są to między innymi: VGG16, VGG19, Xception i Res-Net50. Algorytm DeepDream może zostać zaimplementowany przy użyciu każdej z tych sieci, ale wybór sieci będzie miał oczy-wiście wpływ na generowane wizualizacje. Wynika to z tego, że różne architektury sieci konwolucyjnych uczą się różnych cech. W oryginalnym algorytmie DeepDream zastosowano model Inception. Wykorzystanie tego modelu pozwala na wygenerowanie ładnie wyglądających grafik, a więc skorzystamy z modelu In-ception V3 dołączonego do pakietu Keras.
r
r library(keras) # We will not be training our model, # so we use this command to disable all training-specific operations k_set_learning_phase(0)
Using TensorFlow backend.
r
r # Build the InceptionV3 network. # The model will be loaded with pre-trained ImageNet weights. model <- application_inception_v3( weights = , include_top = FALSE, )
2017-11-28 10:27:24.639177: I tensorflow/core/platform/cpu_feature_guard.cc:137] Your CPU supports instructions that this TensorFlow binary was not compiled to use: SSE4.1 SSE4.2 AVX AVX2 FMA
Następnie musimy zająć się obliczaniem straty — wartości, którą będziemy starali się maksymalizować w procesie wzrostu gradientu. W rozdziale 5. podczas filtrowania wizualizacji staraliśmy się maksymalizować wartość określonego filtra wybranej warstwy sieci. Tym razem będziemy jednocześnie maksymalizować aktywacje wszystkich filtrów wielu warstw, a konkretnie rzecz biorąc, będziemy maksymalizować sumę normy L2 aktywacji zbioru warstw wysokiego poziomu. Wybór warstw (a także dokładanie się poszczególnych warstw do finalnej wartości straty) ma największy wpływ na generowane wizualizacje. W związku z tym chcemy, aby parametry te można było z łatwością modyfikować. Niższe warstwy odpowiadają za wzorce geometryczne, a wyższe warstwy odpowiadają za elementy obrazu pozwalające na rozpoznawanie klas zbioru ImageNet (np. ptaków lub psów). Zaczniemy od niezbyt optymalnej konfiguracji czterech warstw, ale z pewnością warto wypróbować później działanie wielu innych konfiguracji.
r
r # Named mapping layer names to a coefficient # quantifying how much the layer’s activation # will contribute to the loss we will seek to maximize. # Note that these are layer names as they appear # in the built-in InceptionV3 application. # You can list all layer names using summary(model)
. layer_contributions <- list( mixed2 = 0.2, mixed3 = 3, mixed4 = 2, mixed5 = 1.5 )
Teraz czas zdefiniować tensor zawierający wartość straty: ważoną sumę normy L2 aktywacji warstw z poprzedniego listingu.
r
r # Get the symbolic outputs of each layer (we gave them unique names). layer_dict <- model\(layers names(layer_dict) <- lapply(layer_dict, function(layer) layer\)name) # Define the loss. loss <- k_variable(0) for (layer_name in names(layer_contributions)) { # Add the L2 norm of the features of a layer to the loss. coeff <- layer_contributions[[layer_name]] activation <- layer_dict[[layer_name]]$output scaling <- k_prod(k_cast(k_shape(activation), 32)) loss <- loss + (coeff * k_sum(k_square(activation)) / scaling) }
Teraz możemy uruchomić proces wzrostu gradientu.
r
r # This holds our generated image dream <- model$input # Normalize gradients. grads <- k_gradients(loss, dream)[[1]] grads <- grads / k_maximum(k_mean(k_abs(grads)), 1e-7) # Set up function to retrieve the value # of the loss and gradients given an input image. outputs <- list(loss, grads) fetch_loss_and_grads <- k_function(list(dream), outputs) eval_loss_and_grads <- function(x) { outs <- fetch_loss_and_grads(list(x)) loss_value <- outs[[1]] grad_values <- outs[[2]] list(loss_value, grad_values) } gradient_ascent <- function(x, iterations, step, max_loss = NULL) { for (i in 1:iterations) { c(loss_value, grad_values) %<-% eval_loss_and_grads(x) if (!is.null(max_loss) && loss_value > max_loss) break cat(...Loss value at, i, :, loss_value, \n) x <- x + (step * grad_values) } x }
Na koniec możemy zająć się właściwym algorytmem DeepDream.
Na początku definiowana jest lista skal (nazywanych również ok-tawami), które są używane podczas przetwarzania obrazów. Każda kolejna skala jest większa od poprzedniej o współczynnik równy 1,4 (jest o 40% większa) — zaczynamy od przetwarzania małego obrazu, a następnie zwiększamy jego skalę (patrz rysu-nek 8.4).
Po każdej kolejnej operacji skalowania (od najmniejszej do największej) uruchamiany jest algorytm wzrostu gradientu w celu maksymalizacji zdefiniowanej wcześniej straty przy danej skali. Po każdym zakończeniu pracy tego algorytmu skala obrazu jest zwiększana o 40%.
W celu uniknięcia utraty dużej ilości szczegółów obrazu po każdej operacji skalowania (w wyniku tych operacji otrzymywany jest coraz bardziej rozmyty i rozpikselowany obraz) możemy wykonać prosty zabieg polegający na ponownym dodaniu utraconych szczegółów do obrazu. Jest to możliwe do wykonania, ponieważ wiemy, jak powinien wyglądać oryginalny obraz w większej rozdzielczości. Dysponując obrazem S o małym rozmiarze i obrazem L o większym rozmiarze, możemy przekształcić obraz L do rozmiaru obrazu S i określić różnice między tymi obrazami — różnica ta będzie wskazywać utracone szczegóły.
r
r resize_img <- function(img, size) { image_array_resize(img, size[[1]], size[[2]]) } save_img <- function(img, fname) { img <- deprocess_image(img) image_array_save(img, fname) } # Util function to open, resize, and format pictures into appropriate tensors preprocess_image <- function(image_path) { image_load(image_path) %>% image_to_array() %>% array_reshape(dim = c(1, dim(.))) %>% inception_v3_preprocess_input() } # Util function to convert a tensor into a valid image deprocess_image <- function(img) { img <- array_reshape(img, dim = c(dim(img)[[2]], dim(img)[[3]], 3)) img <- img / 2 img <- img + 0.5 img <- img * 255
dims <- dim(img) img <- pmax(0, pmin(img, 255)) dim(img) <- dims img }
r
r # Playing with these hyperparameters will also allow you to achieve new effects step <- 0.01 # Gradient ascent step size num_octave <- 3 # Number of scales at which to run gradient ascent octave_scale <- 1.4 # Size ratio between scales iterations <- 20 # Number of ascent steps per scale # If our loss gets larger than 10, # we will interrupt the gradient ascent process, to avoid ugly artifacts max_loss <- 10
# Fill this to the path to the image you want to use dir.create() base_image_path <- ~/Downloads/creative_commons_elephant.jpg
# Load the image into an array img <- preprocess_image(base_image_path) # We prepare a list of shapes # defining the different scales at which we will run gradient ascent original_shape <- dim(img)[-1] successive_shapes <- list(original_shape) for (i in 1:num_octave) { shape <- as.integer(original_shape / (octave_scale ^ i)) successive_shapes[[length(successive_shapes) + 1]] <- shape } # Reverse list of shapes, so that they are in increasing order successive_shapes <- rev(successive_shapes) # Resize the array of the image to our smallest scale original_img <- img shrunk_original_img <- resize_img(img, successive_shapes[[1]]) for (shape in successive_shapes) { cat(image shape, shape, \n) img <- resize_img(img, shape) img <- gradient_ascent(img, iterations = iterations, step = step, max_loss = max_loss) upscaled_shrunk_original_img <- resize_img(shrunk_original_img, shape) same_size_original <- resize_img(original_img, shape) lost_detail <- same_size_original - upscaled_shrunk_original_img
img <- img + lost_detail shrunk_original_img <- resize_img(original_img, shape) save_img(img, fname = sprintf(/at_scale_%s.png, paste(shape, collapse = ))) }
Processsing image shape 218 327 1
...Loss value at 1 : 3.419769
...Loss value at 2 : 3.799137
...Loss value at 3 : 4.646163
...Loss value at 4 : 5.828026
...Loss value at 5 : 7.018764
...Loss value at 6 : 8.187927
...Loss value at 7 : 9.277216
Processsing image shape 306 458 1
/Users/jjallaire/.virtualenvs/r-tensorflow/lib/python2.7/site-packages/scipy/ndimage/interpolation.py:616: UserWarning: From scipy 0.13.0, the output shape of zoom() is calculated with round() instead of int() - for these inputs the size of the returned array has changed.
\the returned array has changed.\, UserWarning)
...Loss value at 1 : 3.83497
...Loss value at 2 : 5.329614
...Loss value at 3 : 6.632971
...Loss value at 4 : 7.771207
...Loss value at 5 : 8.825724
...Loss value at 6 : 9.87993
Processsing image shape 428 642 2
...Loss value at 1 : 3.489022
...Loss value at 2 : 4.858512
...Loss value at 3 : 6.09081
...Loss value at 4 : 7.162714
...Loss value at 5 : 8.194179
...Loss value at 6 : 9.169289
Processsing image shape 600 899 3
...Loss value at 1 : 3.440316
...Loss value at 2 : 4.793736
...Loss value at 3 : 5.956376
...Loss value at 4 : 7.03718
...Loss value at 5 : 8.050757
...Loss value at 6 : 9.029609
...Loss value at 7 : 9.968752
r
r save_img(img, fname = /final_dream.png)
r
r plot(as.raster(deprocess_image(img) / 255))
LS0tDQp0aXRsZTogIkRlZXAgRHJlYW0iDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOiANCiAgICB0aGVtZTogY2VydWxlYW4NCiAgICBoaWdobGlnaHQ6IHRleHRtYXRlDQotLS0NCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQod2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UpDQpgYGANCg0KDQoNCiMjIEltcGxlbWVudGFjamEgYWxnb3J5dG11IERlZXBEcmVhbSB3IHBha2llY2llIEtlcmFzDQoNClphY3puaWVteSBvZCBrb253b2x1Y3lqbmVqIHNpZWNpIG5ldXJvbm93ZWogd3l0cmVub3dhbmVqIG5hIHpiaW9yemUgb2JyYXrDs3cgSW1hZ2VOZXQuIFBha2lldCBLZXJhcyB6YXdpZXJhIHdpZWxlIHRha2ljaCBzaWVjaS4gU8SFIHRvIG1pxJlkenkgaW5ueW1pOiBWR0cxNiwgVkdHMTksIFhjZXB0aW9uIGkgUmVzLU5ldDUwLiBBbGdvcnl0bSBEZWVwRHJlYW0gbW/FvGUgem9zdGHEhyB6YWltcGxlbWVudG93YW55IHByenkgdcW8eWNpdSBrYcW8ZGVqIHogdHljaCBzaWVjaSwgYWxlIHd5YsOzciBzaWVjaSBixJlkemllIG1pYcWCIG9jenktd2nFm2NpZSB3cMWCeXcgbmEgZ2VuZXJvd2FuZSB3aXp1YWxpemFjamUuIFd5bmlrYSB0byB6IHRlZ28sIMW8ZSByw7PFvG5lIGFyY2hpdGVrdHVyeSBzaWVjaSBrb253b2x1Y3lqbnljaCB1Y3rEhSBzacSZIHLDs8W8bnljaCBjZWNoLiBXIG9yeWdpbmFsbnltIGFsZ29yeXRtaWUgRGVlcERyZWFtIHphc3Rvc293YW5vIG1vZGVsIEluY2VwdGlvbi4gV3lrb3J6eXN0YW5pZSB0ZWdvIG1vZGVsdSBwb3p3YWxhIG5hIHd5Z2VuZXJvd2FuaWUgxYJhZG5pZSB3eWdsxIVkYWrEhWN5Y2ggZ3JhZmlrLCBhIHdpxJljIHNrb3J6eXN0YW15IHogbW9kZWx1IEluLWNlcHRpb24gVjMgZG/FgsSFY3pvbmVnbyBkbyBwYWtpZXR1IEtlcmFzLg0KDQpgYGB7cn0NCmxpYnJhcnkoa2VyYXMpDQoNCiMgTmllIGLEmWR6aWVteSB0cmVub3dhxIcgbW9kZWx1LiANCiMgUG9sZWNlbmllIHRvIHd5xYLEhWN6YSB3c3p5c3RraWUgb3BlcmFjamUgdcW8eXdhbmUgdHlsa28gcG9kY3phcyB0cmVub3dhbmlhLg0Ka19zZXRfbGVhcm5pbmdfcGhhc2UoMCkNCg0KIyBTaWXEhyBJbmNlcHRpb24gVjMgamVzdCBidWRvd2FuYSBiZXogc3dvamVqIGtvbndvbHVjeWpuZWogYmF6eS4gDQojIE1vZGVsIHpvc3RhbmllIHphxYJhZG93YW55IHogd2FnYW1pIHd5dHJlbm93YW55bWkgbmEgemJpb3J6ZSBJbWFnZU5ldC4NCm1vZGVsIDwtIGFwcGxpY2F0aW9uX2luY2VwdGlvbl92MygNCiAgd2VpZ2h0cyA9ICJpbWFnZW5ldCIsIA0KICBpbmNsdWRlX3RvcCA9IEZBTFNFLA0KKQ0KYGBgDQoNCk5hc3TEmXBuaWUgbXVzaW15IHphasSFxIcgc2nEmSBvYmxpY3phbmllbSBzdHJhdHkg4oCUIHdhcnRvxZtjaSwga3TDs3LEhSBixJlkemllbXkgc3RhcmFsaSBzacSZIG1ha3N5bWFsaXpvd2HEhyB3IHByb2Nlc2llIHd6cm9zdHUgZ3JhZGllbnR1LiBXIHJvemR6aWFsZSA1LiBwb2RjemFzIGZpbHRyb3dhbmlhIHdpenVhbGl6YWNqaSBzdGFyYWxpxZtteSBzacSZIG1ha3N5bWFsaXpvd2HEhyB3YXJ0b8WbxIcgb2tyZcWbbG9uZWdvIGZpbHRyYSB3eWJyYW5laiB3YXJzdHd5IHNpZWNpLiBUeW0gcmF6ZW0gYsSZZHppZW15IGplZG5vY3plxZtuaWUgbWFrc3ltYWxpem93YcSHIGFrdHl3YWNqZSB3c3p5c3RraWNoIGZpbHRyw7N3IHdpZWx1IHdhcnN0dywgYSBrb25rcmV0bmllIHJ6ZWN6IGJpb3LEhWMsIGLEmWR6aWVteSBtYWtzeW1hbGl6b3dhxIcgc3VtxJkgbm9ybXkgTDIgYWt0eXdhY2ppIHpiaW9ydSB3YXJzdHcgd3lzb2tpZWdvIHBvemlvbXUuIFd5YsOzciB3YXJzdHcgKGEgdGFrxbxlIGRva8WCYWRhbmllIHNpxJkgcG9zemN6ZWfDs2xueWNoIHdhcnN0dyBkbyBmaW5hbG5laiB3YXJ0b8WbY2kgc3RyYXR5KSBtYSBuYWp3acSZa3N6eSB3cMWCeXcgbmEgZ2VuZXJvd2FuZSB3aXp1YWxpemFjamUuIFcgendpxIV6a3UgeiB0eW0gY2hjZW15LCBhYnkgcGFyYW1ldHJ5IHRlIG1vxbxuYSBiecWCbyB6IMWCYXR3b8WbY2nEhSBtb2R5Zmlrb3dhxIcuIE5pxbxzemUgd2Fyc3R3eSBvZHBvd2lhZGFqxIUgemEgd3pvcmNlIGdlb21ldHJ5Y3puZSwgYSB3ecW8c3plIHdhcnN0d3kgb2Rwb3dpYWRhasSFIHphIGVsZW1lbnR5IG9icmF6dSBwb3p3YWxhasSFY2UgbmEgcm96cG96bmF3YW5pZSBrbGFzIHpiaW9ydSBJbWFnZU5ldCAobnAuIHB0YWvDs3cgbHViIHBzw7N3KS4gWmFjem5pZW15IG9kIG5pZXpieXQgb3B0eW1hbG5laiBrb25maWd1cmFjamkgY3p0ZXJlY2ggd2Fyc3R3LCBhbGUgeiBwZXdub8WbY2nEhSB3YXJ0byB3eXByw7Nib3dhxIcgcMOzxbpuaWVqIGR6aWHFgmFuaWUgd2llbHUgaW5ueWNoIGtvbmZpZ3VyYWNqaS4NCg0KYGBge3J9DQojIExpc3RhIHogbmF6d2FtaSBwcnp5cGlzdWrEhWNhIG5hend5IHdhcnN0dyBkbyB3c3DDs8WCY3p5bm5pa8OzdyB3cMWCeXd1IGFrdHl3YWNqaSB3YXJzdHcgbmEgDQojIHdhcnRvxZvEhyBzdHJhdHksIGt0w7NyxIUgY2hjZW15IG1ha3N5bWFsaXpvd2HEhy4gDQojIFphdXdhxbwsIMW8ZSBuYXp3eSB3YXJzdHcgc8SFIHdwcm93YWR6b25lIG5hIHN0YcWCZSB3IHdidWRvd2FuZWogYXBsaWthY2ppIEluY2VwdGlvbiBWMy4NCiMgTGlzdMSZIG5hencgd3N6eXN0a2ljaCB3YXJzdHcgbW9kZWx1IG1vxbxuYSB3ecWbd2lldGxpxIcgemEgcG9tb2PEhSBwb2xlY2VuaWEgc3VtbWFyeShtb2RlbCkuDQpsYXllcl9jb250cmlidXRpb25zIDwtIGxpc3QoDQogIG1peGVkMiA9IDAuMiwNCiAgbWl4ZWQzID0gMywNCiAgbWl4ZWQ0ID0gMiwNCiAgbWl4ZWQ1ID0gMS41DQopDQpgYGANCg0KVGVyYXogY3phcyB6ZGVmaW5pb3dhxIcgdGVuc29yIHphd2llcmFqxIVjeSB3YXJ0b8WbxIcgc3RyYXR5OiB3YcW8b27EhSBzdW3EmSBub3JteSBMMiBha3R5d2Fjamkgd2Fyc3R3IHogcG9wcnplZG5pZWdvIGxpc3Rpbmd1Lg0KDQpgYGB7cn0NCiMgVHdvcnp5IGxpc3TEmSBwcnp5cGlzdWrEhWPEhSBuYXp3eSB3YXJzdHcgZG8gaW5zdGFuY2ppIHdhcnN0dy4NCmxheWVyX2RpY3QgPC0gbW9kZWwkbGF5ZXJzDQpuYW1lcyhsYXllcl9kaWN0KSA8LSBsYXBwbHkobGF5ZXJfZGljdCwgZnVuY3Rpb24obGF5ZXIpIGxheWVyJG5hbWUpIA0KDQojIFN0cmF0YSBixJlkemllIGRlZmluaW93YW5hIHByemV6IGRvZGFuaWUgd2FydG/Fm2NpIGNoYXJha3Rlcnl6dWrEhWN5Y2ggd3DFgnl3IHBvc3pjemVnw7NsbnljaCB3YXJzdHcgbmEgc3RyYXTEmS4NCmxvc3MgPC0ga192YXJpYWJsZSgwKSANCmZvciAobGF5ZXJfbmFtZSBpbiBuYW1lcyhsYXllcl9jb250cmlidXRpb25zKSkgew0KICAjIERvZGFqZSBub3JtxJkgTDIgY2VjaCB3YXJzdHd5IGRvIHN0cmF0eS4NCiAgY29lZmYgPC0gbGF5ZXJfY29udHJpYnV0aW9uc1tbbGF5ZXJfbmFtZV1dDQogIGFjdGl2YXRpb24gPC0gbGF5ZXJfZGljdFtbbGF5ZXJfbmFtZV1dJG91dHB1dA0KICBzY2FsaW5nIDwtIGtfcHJvZChrX2Nhc3Qoa19zaGFwZShhY3RpdmF0aW9uKSwgImZsb2F0MzIiKSkNCiAgbG9zcyA8LSBsb3NzICsgKGNvZWZmICoga19zdW0oa19zcXVhcmUoYWN0aXZhdGlvbikpIC8gc2NhbGluZykNCn0NCmBgYA0KDQpUZXJheiBtb8W8ZW15IHVydWNob21pxIcgcHJvY2VzIHd6cm9zdHUgZ3JhZGllbnR1Lg0KDQpgYGB7cn0NCiMgVyB0eW0gdGVuc29yemUgem5hamR1amUgc2nEmSB3eWdlbmVyb3dhbnkgb2JyYXogKHdpemphKS4NCmRyZWFtIDwtIG1vZGVsJGlucHV0DQoNCiMgTm9ybWFsaXp1amUgZ3JhZGllbnR5ICh0byB3YcW8bnkgemFiaWVnKS4NCmdyYWRzIDwtIGtfZ3JhZGllbnRzKGxvc3MsIGRyZWFtKVtbMV1dDQpncmFkcyA8LSBncmFkcyAvIGtfbWF4aW11bShrX21lYW4oa19hYnMoZ3JhZHMpKSwgMWUtNykNCg0KIyBLb25maWd1cnVqZSBmdW5rY2rEmSBLZXJhcyBzxYJ1xbzEhWPEhSBkbyB1enlza2l3YW5pYSB3YXJ0b8WbY2kgc3RyYXR5IGkgZ3JhZGllbnTDs3cgDQojIG5hIHBvZHN0YXdpZSBvYnJhenUgd2VqxZtjaW93ZWdvLg0Kb3V0cHV0cyA8LSBsaXN0KGxvc3MsIGdyYWRzKQ0KZmV0Y2hfbG9zc19hbmRfZ3JhZHMgPC0ga19mdW5jdGlvbihsaXN0KGRyZWFtKSwgb3V0cHV0cykNCg0KZXZhbF9sb3NzX2FuZF9ncmFkcyA8LSBmdW5jdGlvbih4KSB7DQogIG91dHMgPC0gZmV0Y2hfbG9zc19hbmRfZ3JhZHMobGlzdCh4KSkNCiAgbG9zc192YWx1ZSA8LSBvdXRzW1sxXV0NCiAgZ3JhZF92YWx1ZXMgPC0gb3V0c1tbMl1dDQogIGxpc3QobG9zc192YWx1ZSwgZ3JhZF92YWx1ZXMpDQp9DQoNCmdyYWRpZW50X2FzY2VudCA8LSBmdW5jdGlvbih4LCBpdGVyYXRpb25zLCBzdGVwLCBtYXhfbG9zcyA9IE5VTEwpIHsNCiAgZm9yIChpIGluIDE6aXRlcmF0aW9ucykgew0KICAgIGMobG9zc192YWx1ZSwgZ3JhZF92YWx1ZXMpICU8LSUgZXZhbF9sb3NzX2FuZF9ncmFkcyh4KQ0KICAgIGlmICghaXMubnVsbChtYXhfbG9zcykgJiYgbG9zc192YWx1ZSA+IG1heF9sb3NzKQ0KICAgICAgYnJlYWsNCiAgICBjYXQoIi4uLldhcnRvxZvEhyBzdHJhdHkiLCBpLCAiOiIsIGxvc3NfdmFsdWUsICJcbiIpDQogICAgeCA8LSB4ICsgKHN0ZXAgKiBncmFkX3ZhbHVlcykNCiAgfQ0KICB4DQp9DQpgYGANCg0KTmEga29uaWVjIG1vxbxlbXkgemFqxIXEhyBzacSZIHfFgmHFm2Npd3ltIGFsZ29yeXRtZW0gRGVlcERyZWFtLiANCg0KTmEgcG9jesSFdGt1IGRlZmluaW93YW5hIGplc3QgbGlzdGEgc2thbCAobmF6eXdhbnljaCByw7N3bmllxbwgb2stdGF3YW1pKSwga3TDs3JlIHPEhSB1xbx5d2FuZSBwb2RjemFzIHByemV0d2FyemFuaWEgb2JyYXrDs3cuIEthxbxkYSBrb2xlam5hIHNrYWxhIGplc3Qgd2nEmWtzemEgb2QgcG9wcnplZG5pZWogbyB3c3DDs8WCY3p5bm5payByw7N3bnkgMSw0IChqZXN0IG8gNDAlIHdpxJlrc3phKSDigJQgemFjenluYW15IG9kIHByemV0d2FyemFuaWEgbWHFgmVnbyBvYnJhenUsIGEgbmFzdMSZcG5pZSB6d2nEmWtzemFteSBqZWdvIHNrYWzEmSAocGF0cnogcnlzdS1uZWsgOC40KS4NCg0KIVtkZWVwIGRyZWFtIHByb2Nlc3NdKGltZ1w4XzIucG5nKQ0KDQpQbyBrYcW8ZGVqIGtvbGVqbmVqIG9wZXJhY2ppIHNrYWxvd2FuaWEgKG9kIG5ham1uaWVqc3plaiBkbyBuYWp3acSZa3N6ZWopIHVydWNoYW1pYW55IGplc3QgYWxnb3J5dG0gd3pyb3N0dSBncmFkaWVudHUgdyBjZWx1IG1ha3N5bWFsaXphY2ppIHpkZWZpbmlvd2FuZWogd2N6ZcWbbmllaiBzdHJhdHkgcHJ6eSBkYW5laiBza2FsaS4gUG8ga2HFvGR5bSB6YWtvxYRjemVuaXUgcHJhY3kgdGVnbyBhbGdvcnl0bXUgc2thbGEgb2JyYXp1IGplc3QgendpxJlrc3phbmEgbyA0MCUuDQoNClcgY2VsdSB1bmlrbmnEmWNpYSB1dHJhdHkgZHXFvGVqIGlsb8WbY2kgc3pjemVnw7PFgsOzdyBvYnJhenUgcG8ga2HFvGRlaiBvcGVyYWNqaSBza2Fsb3dhbmlhICh3IHd5bmlrdSB0eWNoIG9wZXJhY2ppIG90cnp5bXl3YW55IGplc3QgY29yYXogYmFyZHppZWogcm96bXl0eSBpIHJvenBpa3NlbG93YW55IG9icmF6KSBtb8W8ZW15IHd5a29uYcSHIHByb3N0eSB6YWJpZWcgcG9sZWdhasSFY3kgbmEgcG9ub3dueW0gZG9kYW5pdSB1dHJhY29ueWNoIHN6Y3plZ8OzxYLDs3cgZG8gb2JyYXp1LiBKZXN0IHRvIG1vxbxsaXdlIGRvIHd5a29uYW5pYSwgcG9uaWV3YcW8IHdpZW15LCBqYWsgcG93aW5pZW4gd3lnbMSFZGHEhyBvcnlnaW5hbG55IG9icmF6IHcgd2nEmWtzemVqIHJvemR6aWVsY3pvxZtjaS4gRHlzcG9udWrEhWMgb2JyYXplbSBTIG8gbWHFgnltIHJvem1pYXJ6ZSBpIG9icmF6ZW0gTCBvIHdpxJlrc3p5bSByb3ptaWFyemUsIG1vxbxlbXkgcHJ6ZWtzenRhxYJjacSHIG9icmF6IEwgZG8gcm96bWlhcnUgb2JyYXp1IFMgaSBva3JlxZtsacSHIHLDs8W8bmljZSBtacSZZHp5IHR5bWkgb2JyYXphbWkg4oCUIHLDs8W8bmljYSB0YSBixJlkemllIHdza2F6eXdhxIcgdXRyYWNvbmUgc3pjemVnw7PFgnkuDQoNCmBgYHtyfQ0KcmVzaXplX2ltZyA8LSBmdW5jdGlvbihpbWcsIHNpemUpIHsNCiAgaW1hZ2VfYXJyYXlfcmVzaXplKGltZywgc2l6ZVtbMV1dLCBzaXplW1syXV0pDQp9DQoNCnNhdmVfaW1nIDwtIGZ1bmN0aW9uKGltZywgZm5hbWUpIHsNCiAgaW1nIDwtIGRlcHJvY2Vzc19pbWFnZShpbWcpDQogIGltYWdlX2FycmF5X3NhdmUoaW1nLCBmbmFtZSkNCn0NCg0KIyBGdW5rY2phIG5hcnrEmWR6aW93YSAgemFtaWVuaWFqxIVjYSBvYnJhenkgdyB0ZW5zb3J5Lg0KcHJlcHJvY2Vzc19pbWFnZSA8LSBmdW5jdGlvbihpbWFnZV9wYXRoKSB7DQogIGltYWdlX2xvYWQoaW1hZ2VfcGF0aCkgJT4lIA0KICAgIGltYWdlX3RvX2FycmF5KCkgJT4lIA0KICAgIGFycmF5X3Jlc2hhcGUoZGltID0gYygxLCBkaW0oLikpKSAlPiUgDQogICAgaW5jZXB0aW9uX3YzX3ByZXByb2Nlc3NfaW5wdXQoKQ0KfQ0KDQojIEZ1bmtjamEgcG9tb2NuaWN6YSB6bWllbmlhasSFY2EgdGVuc29yeSB3IG9icmF6eQ0KZGVwcm9jZXNzX2ltYWdlIDwtIGZ1bmN0aW9uKGltZykgew0KICBpbWcgPC0gYXJyYXlfcmVzaGFwZShpbWcsIGRpbSA9IGMoZGltKGltZylbWzJdXSwgZGltKGltZylbWzNdXSwgMykpDQogIGltZyA8LSBpbWcgLyAyDQogIGltZyA8LSBpbWcgKyAwLjUNCiAgaW1nIDwtIGltZyAqIDI1NQ0KICANCiAgZGltcyA8LSBkaW0oaW1nKQ0KICBpbWcgPC0gcG1heCgwLCBwbWluKGltZywgMjU1KSkNCiAgZGltKGltZykgPC0gZGltcw0KICBpbWcNCn0NCmBgYA0KDQpgYGB7cn0NCiMgTW9keWZpa2FjamEgdHljaCBwYXJhbWV0csOzdyBwb3p3YWxhIG5hIHV6eXNrYW5pZSBpbm55Y2ggZWZla3TDs3cgd2l6dWFsbnljaC4NCg0Kc3RlcCA8LSAwLjAxICAgICAgICAgICMgUm96bWlhciBrcm9rdSBhbGdvcnl0bXUgd3pyb3N0dSBncmFkaWVudHUuDQpudW1fb2N0YXZlIDwtIDMgICAgICAgIyBMaWN6YmEgb3BlcmFjamkgc2thbG93YW5pYSwgcHJ6eSBrdMOzcnljaCBuYWxlxbx5IHVydWNob21pxIcgYWxnb3J5dG0gd3pyb3N0dSBncmFkaWVudHUuDQpvY3RhdmVfc2NhbGUgPC0gMS40ICAgIyBSw7PFvG5pY2EgbWnEmWR6eSByb3ptaWFyYW1pIGtvbGVqbnljaCB3ZXJzamkgb2JyYXp1Lg0KaXRlcmF0aW9ucyA8LSAyMCAgICAgICMgTGljemJhIGtyb2vDs3cgd3pyb3N0dSB3eWtvbnl3YW55Y2ggcHJ6eSBrYcW8ZGVqIG9wZXJhY2ppIHNrYWxvd2FuaWEuDQoNCiMgSmXFvGVsaSBzdHJhdGEgcHJ6ZWtyb2N6eSB3YXJ0b8WbxIcgcsOzd27EhSAxMCwgdG8gcHJvY2VzIHd6cm9zdHUgZ3JhZGllbnR1IA0KIyB6b3N0YW5pZSBwcnplcndhbnkgdyBjZWx1IHphcG9iaWVnbmnEmWNpYSBwb3dzdGF3YW5pYSBicnp5ZGtpY2ggYXJ0ZWZha3TDs3cuDQptYXhfbG9zcyA8LSAxMCAgDQoNCiMgVHUgbmFsZcW8eSB1bWllxZtjacSHIMWbY2llxbxrxJkgb2JyYXp1LCBrdMOzcnkgY2hjZW15IHByemV0d2FyemHEhy4NCmRpci5jcmVhdGUoImRyZWFtIikNCmJhc2VfaW1hZ2VfcGF0aCA8LSAifi9Eb3dubG9hZHMvY3JlYXRpdmVfY29tbW9uc19lbGVwaGFudC5qcGciDQoNCiMgxYFhZG93YW5pZSBvYnJhenUgZG8gdGFibGljeSAoZnVua2NqxJkgdMSZIHpkZWZpbmlvd2FubyB3IGxpc3Rpbmd1IDguMTMpLg0KaW1nIDwtIHByZXByb2Nlc3NfaW1hZ2UoYmFzZV9pbWFnZV9wYXRoKQ0KDQojIFByenlnb3Rvd3l3YW5pZSBsaXN0eSBrc3p0YcWCdMOzdyBkZWZpbml1asSFY3ljaCBza2Fsb3dhbmlhLA0KIyBwcnp5IGt0w7NyeWNoIHVydWNob21pb255IHpvc3RhbmllIGFsZ29yeXRtIHd6cm9zdHUgZ3JhZGllbnR1Lg0Kb3JpZ2luYWxfc2hhcGUgPC0gZGltKGltZylbLTFdDQpzdWNjZXNzaXZlX3NoYXBlcyA8LSBsaXN0KG9yaWdpbmFsX3NoYXBlKQ0KZm9yIChpIGluIDE6bnVtX29jdGF2ZSkgeyANCiAgc2hhcGUgPC0gYXMuaW50ZWdlcihvcmlnaW5hbF9zaGFwZSAvIChvY3RhdmVfc2NhbGUgXiBpKSkNCiAgc3VjY2Vzc2l2ZV9zaGFwZXNbW2xlbmd0aChzdWNjZXNzaXZlX3NoYXBlcykgKyAxXV0gPC0gc2hhcGUgDQp9DQoNCiMgT2R3cmFjYW5pZSBsaXN0eSBrc3p0YcWCdMOzdyB0YWssIGFieSB6bmFsYXrFgnkgc2nEmSB3IGtvbGVqbm/Fm2NpIHJvc27EhWNlai4NCg0Kc3VjY2Vzc2l2ZV9zaGFwZXMgPC0gcmV2KHN1Y2Nlc3NpdmVfc2hhcGVzKSANCg0KIyBabWlhbmEgcm96bWlhcnUgdGFibGljeSBvYnJhenUgdyBjZWx1IHptbmllanN6ZW5pYSBqZWdvIHNrYWxpLg0Kb3JpZ2luYWxfaW1nIDwtIGltZyANCnNocnVua19vcmlnaW5hbF9pbWcgPC0gcmVzaXplX2ltZyhpbWcsIHN1Y2Nlc3NpdmVfc2hhcGVzW1sxXV0pDQoNCmZvciAoc2hhcGUgaW4gc3VjY2Vzc2l2ZV9zaGFwZXMpIHsNCiAgY2F0KCJabWlhbmEga3N6dGHFgnR1IG9icmF6dSIsIHNoYXBlLCAiXG4iKQ0KICBpbWcgPC0gcmVzaXplX2ltZyhpbWcsIHNoYXBlKQ0KICBpbWcgPC0gZ3JhZGllbnRfYXNjZW50KGltZywNCiAgICAgICAgICAgICAgICAgICAgICAgICBpdGVyYXRpb25zID0gaXRlcmF0aW9ucywNCiAgICAgICAgICAgICAgICAgICAgICAgICBzdGVwID0gc3RlcCwNCiAgICAgICAgICAgICAgICAgICAgICAgICBtYXhfbG9zcyA9IG1heF9sb3NzKQ0KICB1cHNjYWxlZF9zaHJ1bmtfb3JpZ2luYWxfaW1nIDwtIHJlc2l6ZV9pbWcoc2hydW5rX29yaWdpbmFsX2ltZywgc2hhcGUpDQogIHNhbWVfc2l6ZV9vcmlnaW5hbCA8LSByZXNpemVfaW1nKG9yaWdpbmFsX2ltZywgc2hhcGUpDQogIGxvc3RfZGV0YWlsIDwtIHNhbWVfc2l6ZV9vcmlnaW5hbCAtIHVwc2NhbGVkX3NocnVua19vcmlnaW5hbF9pbWcNCiAgDQogIGltZyA8LSBpbWcgKyBsb3N0X2RldGFpbA0KICBzaHJ1bmtfb3JpZ2luYWxfaW1nIDwtIHJlc2l6ZV9pbWcob3JpZ2luYWxfaW1nLCBzaGFwZSkNCiAgc2F2ZV9pbWcoaW1nLCBmbmFtZSA9IHNwcmludGYoImRyZWFtL2F0X3NjYWxlXyVzLnBuZyIsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBhc3RlKHNoYXBlLCBjb2xsYXBzZSA9ICJ4IikpKQ0KfQ0KDQpzYXZlX2ltZyhpbWcsIGZuYW1lID0gImRyZWFtL2ZpbmFsX2RyZWFtLnBuZyIpDQpgYGANCg0KYGBge3J9DQpwbG90KGFzLnJhc3RlcihkZXByb2Nlc3NfaW1hZ2UoaW1nKSAvIDI1NSkpDQpgYGA=