text:
Resting State fMRI (RS-fMRI) is a method where the brain's functionality is investigated during rest, i.e. when the subject is not performing an explicit task. The data consists of a series of 3D volumes, where the data points within a volume are called "voxels" (instead of "pixels").

A common research field within RS-fMRI is functional connectivity, where the temporal correlation between a "seed voxel" and all other voxels are measured. The result for a given seed voxel is a "seed map", showing the correlation level with all other voxels.

For a given "seed map", the sum of all voxels correlating positively with the seed voxel will then give the degree of connectivity for the seed voxel. A low value indicates a low connectivity, whereas a high value indicates a high level of connectivity. By calculating the degree of connectivity for each voxel, a "Global Brain Connectivity" (GBC) map is obtained. A commonly used tool for GBC is AFNI's 3dTcorrMap.

This tool (DE10GBC) is an alternative GBC tool for running on a Terasic DE10-Standard, where the calculations are accelerated on the FPGA. A speed comparison shows that DE10GBC on the Terasic DE10-Standard is faster than 3dTcorrMap on a MacBook Pro 2016 quad core, even when running the OpenMP version of 3dTCorrMap with 8 threads.

## Terasic DE10-Standard

The Terasic DE10-Standard is a great low-powered development platform built around the largest Cyclone-V SoC with a dual-core ARM processor and a FPGA device with 110K LE. Terasic provides a BSP (Board Support Package) for Intel FPGA SDK OpenCL, making it a perfect entry board for OpenCL on FPGA. The current price is $350 ($259 academic price):

<http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=167&No=1081>

## Installation

### Compiling from source

The following text assumes you have installed a valid OpenCL environment on a Linux machine for the DE10-Standard developer board. Start with copying the gbc folder to the de10\_standard/examples folder on your Linux developer machine. Go to the de10\_standard/examples folder. To compile the host software, type "make". To synthesise the OpenCL device software into FPGA logic, type "./synthesise". This will generate the necessary software in the bin directory. You will have two files in the bin directory:

  - gbc (the host file)
  - gbckernel.aocx (the device file)

Compiling from source is optional. You can also use the precompiled binaries found in the bin directory of this distribution.

### Installing the binaries

Copy the bin directory to a directory of your choice on the DE10-Standard, e.g. ~/gbc/bin.

## Running

You need a NIfTI 4D image with an fMRI timeseries and optionally a mask image to run this software. You can obtain an example from public databases such as ABIDE. The NIfTI file must not be compressed, so nii.gz files must first be decompressed before running. Here is a direct link to an example file from ABIDE, that you can use as indata file (after decompressing it):

<https://s3.amazonaws.com/fcp-indi/data/Projects/ABIDE_Initiative/Outputs/cpac/filt_global/func_preproc/KKI_0050822_func_preproc.nii.gz>

Here are two examples of how to run the software:

- gbc indata.nii outdata.nii
- gbc indata.nii mask.nii outdata.nii

In the first example, the mask will be automatically calculated by only including non-zero voxels in the indata.nii file. In the second example, a mask.nii file is used as the mask. The indata.nii file is the 4D fMRI dataset and the outdata.nii file is the 3D output. The second example corresponds to the following expression in 3dTcorrMap:

- 3dTcorrMap -input indata.nii -mask mask.nii -Sexpr 'step(r)*r' outdata.nii

## YouTube comparison video

This YouTube video compares the speed between running DE10GBC and AFNI's 3dTcorrMap. The result shows that the DE10GBC custom software requires 392 seconds whereas the OpenMP version of 3dTcorrMap running with 8 threads on a MacBook Pro (2016) requires 423 seconds for the given dataset. The end results are the same.

[![IMAGE ALT TEXT](http://img.youtube.com/vi/N8zh7ErCZ8o/0.jpg)](https://www.youtube.com/watch?v=N8zh7ErCZ8o "Terasic DE10 Standard running OpenCL")


text:
Due to number of reasons TeaVM does not rely on Java class library of host JVM.
Instead, TeaVM comes with its own implementation of subset of Java class library.
Of course, it's a subset of Java class library.
The list of supported classes is available [here](/jcl-report/recent/jcl.html).

Java class library was not designed for efficiency with AOT compiler producing code for a limited
environment like JavaScript, that's why only a limited subset is available.
Some of the classes in TeaVM don't behave 100% similar to JVM, for the sake of efficiency.
However, you can tune their behaviour to be closer to normal JVM.
This section provides description of such cases.

# Timezone detection

JavaScript does not provide API to get current timezone.
Only timezone offset is available, which is not enough.
TeaVM has heuristic algorithm that tries to detect timezone using offset history.
However, this algorithm may slow down boot time, so it's disable by default.
To enable it, you should set `java.util.TimeZone.autodetect` TeaVM compiler property to `true`.
If you use Maven, the configuration would look like this:

```xml
<plugin>
  <groupId>org.teavm</groupId>
  <artifactId>teavm-maven-plugin</artifactId>
  <executions>
    <execution>
      ...
      <configuration>
        ...
        <properties>
          <java.util.TimeZone.autodetect>true</java.util.TimeZone.autodetect>
        </properties>
      </configuration>
    </execution>
  </executions>
</plugin>
```

or in Gradle:

```kotlin
teavm {
   all {
      properties.put("java.util.TimeZone.autodetect", "true")
   }
}
```

# Locales

JavaScript does not provide full access to locales.
To emulate Java APIs for locales, TeaVM embeds [Unicode CLDR](http://cldr.unicode.org/) data into JavaScript.
However, this data is huge, so for the sake of efficiency the only locale embedded into JavaScript is en_EN.
To include more locales, specify them as a comma-separated string to `java.util.Locale.available` property.
For example, in Maven configuration:

```xml
  <plugin>
    <groupId>org.teavm</groupId>
    <artifactId>teavm-maven-plugin</artifactId>
    <executions>
      <execution>
        ...
        <configuration>
          ...
          <properties>
            <java.util.Locale.available>en_EN, en_US, ru_RU</java.util.Locale.available>
          </properties>
        </configuration>
      </execution>
    </executions>
  </plugin>
```

or in Gradle:

```kotlin
teavm {
   all {
      properties.put("java.util.Locale.available", "en_EN, en_US, ru_RU")
   }
}
```

# Reflection

Reflection API is not friendly to ahead-of-time compilers like TeaVM.
That's why TeaVM provides only limited support for reflection.
By default, you can access metadata of classes and methods,
but any attempt to call methods from reflection will produce `SecurityException`.
To enable reflective access to certain methods, you should follow these steps:

1. Implement `ReflectionSupplier` interface
2. Create a resource file named `META-INF/services/org.teavm.classlib.ReflectionSupplier`
   with a single line containing fully-qualified name of your implementation

Example:

```java
package org.teavm.classlib.support;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import org.teavm.classlib.ReflectionContext;
import org.teavm.classlib.ReflectionSupplier;
import org.teavm.model.ClassReader;
import org.teavm.model.FieldReader;
import org.teavm.model.MethodDescriptor;
import org.teavm.model.MethodReader;

public class ReflectionSupplierImpl implements ReflectionSupplier {
    @Override
    public Collection<String> getAccessibleFields(ReflectionContext context, String className) {
        var cls = context.getClassSource().get(className);
        var fields = new HashSet<String>();
        for (var field : cls.getFields()) {
            if (field.getAnnotations().get(Reflectable.class.getName()) != null) {
                fields.add(field.getName());
            }
        }
        return fields;
    }

    @Override
    public Collection<MethodDescriptor> getAccessibleMethods(ReflectionContext context, String className) {
        var cls = context.getClassSource().get(className);
        var methods = new HashSet<MethodDescriptor>();
        for (var method : cls.getMethods()) {
            if (method.getAnnotations().get(Reflectable.class.getName()) != null) {
                methods.add(method.getDescriptor());
            }
        }
        return methods;
    }
}
```

and corresponding `META-INF/services/org.teavm.classlib.ReflectionSupplier`:

```
org.teavm.classlib.support.ReflectionSupplierImpl
```

Note that syntax for `MethodDescriptor` constructor is following.
Consider you have method `String foo(int bar, Object baz)`.
Corresponding `MethodDescriptor` should look like:

```java
new MethodDescriptor("foo", int.class, Object.class, String.class);
```

You can apply whatever rule you like, for example:

```java
     method.getAnnotations().get(MyReflectable.class.getName()) != null
     method.getName().startsWith("canReflect");
     method.getParameterTypes().length == 2 && method.getResultType() == ValueType.parse(void.class);
```

Please, not that you should keep the number of reflectable methods as small as possible!

license: MIT

repository: konsoletyper/teavm-site

branch_name: refs/heads/master

extension: md

gha_language: Kotlin

gha_license_id: MIT

license_type: permissive

repo_name: konsoletyper/teavm-site


text:
# Basic main window

There is no fancy stuff here !

![Main tool bar](/docs/main-win-tool-bar.png)

This window is just here to support and launch sub-windows that provide each feature independently

For now, it only support two features / buttons:

* Some sort of monitoring window that provide neighbor status (still need to be improved),
* Flowspec window,


text:
---
name: Question about using VMRaid/VMRaid Apps
about: This is not the appropriate channel
labels: invalid
---

Please post on our forums:

for questions about using the `VMRaid Framework`: ~~https://discuss.vmraid.io~~ => [stackoverflow](https://stackoverflow.com/questions/tagged/vmraid) tagged under `vmraid`

for questions about using `ERPAdda`: https://discuss.erpadda.com

for questions about using `bench`, probably the best place to start is the [bench repo](https://github.com/vmraid/bench)

For documentation issues, use the [VMRaid Framework Documentation](https://vmraidframework.com/docs) or the [developer cheetsheet](https://github.com/vmraid/vmraid/wiki/Developer-Cheatsheet)

For a slightly outdated yet informative developer guide: https://www.youtube.com/playlist?list=PL3lFfCEoMxvzHtsZHFJ4T3n5yMM3nGJ1W

> **Posts that are not bug reports or feature requests will not be addressed on this issue tracker.**

repository: sowrisurya/vmraid

branch_name: refs/heads/main

repo_name: sowrisurya/vmraid


text:
---
layout: article
title: "Souliss, what's next?"
categories: articles
author: plinio_seniore
excerpt: "Lets see what will be available in the next releases."
tags: [arduino, android, smart home, internet of things, home automation, souliss]
modified: 2013-04-01
ads: false
redirect_from: "2013/04/souliss-whats-next.html"
---

It's again time to point out where we are and where we would go next. It was just last summer when we released Souliss Alpha 3, it was the first step into the expansion of the supported boards, because included in Souliss a software TCP/IP stack required by most (but not all) of Ethernet controller.

The release Alpha 3 wasn't enough, the stack were working but the performances was too low, due to the few kilobytes of RAM available we was obliged to split the IP packet sent to the user interface, that gives a slowly response. At that time, the only protocol available for user interfaces was HTTP/JSON and it's ASCII nature makes the exchanged frames too big for a low performance device.

This was the spark for the new Souliss, the release Alpha 4 came out near six month later with a new concept behind, the MaCaco binary protocol that up to A3 were used only between boards was extended to the user interfaces (so the SoulissApp Android application) and a new data structure and Modbus support was added. That's the new Souliss.

Is now time to complete and hopefully came out from the Alpha stage, Souliss will include in few time a nice number of boards, most of them were previewed and are from different manufactured like Olimex, AirQ and some will be from Open Electronics. The next step will be the configuration.

Starting from release Alpha 4.1, that include different (but still not all) Olimex boards, there is a QuickConfiguration tool, that has a single entry point for the configuration needed before the compilation and loading on the board, but this is still not enough.
The main goal is make Souliss pre-loadable, to let load the code and then configure the network parameters later, in the future the standard functionality will not require to compile and load the board if is pre-loaded. One more important point will be a new concept of gateway node, that will allow pass-throught, saving RAM and increasing the number of nodes that can join a network.

So, we are starting now the design for the new Alpha 5, we hope to be fast enough to have it in few months, in the while there will be probably some sub-release for Alpha 4 including bugfix and additional hardware support.

Stay tuned and have a good Easter!

gha_language: SCSS


text:
# Tutorial 2

This is a tutorial for the April competition.

In the competition, your job is mainly to control blimps and together, as a team, win the competition. Therefore, you are not just a volunteer to us, but also this makes you a part of this team. As main crew member of this team, I would like to say thank everyone for your helps and efforts.

## Content

- [1 Prerequisite](#1-Prerequisite)
- [2 Software setup](#2-Software-setup)
- [3 Airship introduction](#3-Airship-introduction)
- [4 Game controller introduction](#4-Game-controller-introduction)

## 1 Prerequisite

Prerequisite is something you should finish before you show up on.

- You'll need to bring your **laptop** with **windows 10** or **Linux ubuntu 20 or ubuntu 18**. (We haven't tested MacOS but if that is your only laptop, then follow the tutorial first and if you encounter any problems, we will figure it out on Monday)

  - If your laptop has only type-c interface, then please also bring your 'type-c to USB' converter, we can't offer that.

- python 3

  - If you don't have python 3 on your laptop, I will strongly recommend to install [Anaconda](https://docs.anaconda.com/anaconda/install/), it will make your life easier, especially for beginners.

- pygame library

  - Use one of the following commands:

    ```
    pip3 install pygame
    ```

- pyserial library:

  - Use one of the following commands:

    ```
    pip3 install pyserial
    ```

- To use the code, please clone our git repo a head of time. We will continue to uploading our git, so please pull that latest update by tomorrow morning.

  - To clone our code, open your terminal in a folder where you want to store it and type the following commands:

    ```
    git clone https://github.com/zhz03/Tutorial-Controlling-multiple-control-boards-through-game-controllers
    ```

- Enter that directory: `cd Tutorial-Controlling-multiple-control-boards-through-game-controllers`

- **For MacOS users**: `git checkout mac`

## 2 Software and hardware setup

To control the corresponding blimp. There are three things need to do:

1. Plug the game controller into your laptop
2. Plug the esp32 receiver to your laptop
3. Run the joystick.py program

Then you should be able to control the blimp.

### for MacOS users

Please down load the Mac drivers for NodeMCU ESP8266 using the link:
[Silcon Labs CP210x USB to UART Bridge](https://www.silabs.com/products/development-tools/software/usb-to-uart-bridge-vcp-drivers)

Once installed, plug in the NodeMCU and check the port /dev/co.SLAB_USBtoUART exists.

Also install:

https://github.com/360Controller/360Controller/releases/download/v1.0.0-alpha.6/360ControllerInstall_1.0.0-alpha.6.dmg

## 3 Airship introduction

In the competition, we will have a ready-to-go box, which is shown in the following figure:

![](pics/box.jpg)

The check list can be found in [here]()

The bottom view of our blimp is shown in the figure:

![](pics/new.jpg)

## 4 Game controller introduction

In the competition, we will use the XBox game controller to control our airships. The illustration figure of game controller is shown in the figure:

![](E:\UCLA\Blimp_project\Public_git_files\Tutorial-Controlling-multiple-control-boards-through-game-controllers\pics\Xbox-360_controller.svg.png)

The corresponding mapping between game controller and function of the airship is in the following table:

| Game controller                                            | Airship functions                                 |
| ---------------------------------------------------------- | ------------------------------------------------- |
| Left stick ($\uparrow,\downarrow,\leftarrow,\rightarrow$)  | forward, backward,turn left, turn right           |
| Right stick ($\uparrow,\downarrow,\leftarrow,\rightarrow$) | Go up, go down, head up, tail up                  |
| left bumper (LB)                                           | 50% speed                                         |
| Right bumper (RB)                                          | 100% full speed                                   |
| Y                                                          | To set searching camera back to forward position  |
| X,Y                                                        | To turn the searching camera to the left or right |
|                                                            |                                                   |


text:
### Additional exercises

You can try out the exercises below to get acquainted with these validation libraries:

* Parse a JSON Schema and create validation rules dynamically: https://json-schema.org/

* Validator for Graph Query Language: https://graphql.org/learn/validation/

* Implement a password validator:
    - At least 12 characters
    - Minimum 1 digit, 1 special character, 1 uppercase character
    - Repeated password field should have the same value with original password field.

repository: emagine-epython/workshop-validation

repo_name: emagine-epython/workshop-validation


text:
---
layout: post
title: Summary of Automatic Colorization
subtitle: Color space, Network Architecture, Loss function and Evaluation
date: 2020-05-26
author: Rasin
header-img: img/post-colorization-insight-9.jpg
catalog: true
tags:
  - Computer Vision
  - Colorization
  - Deep Learning
  - Papers
---

> Header Image: Reddit: [Schoolgirls text messaging in the 40s
> ](https://www.reddit.com/r/Colorization/comments/g9tapw/schoolgirls_text_messaging_in_the_40s/)

# Colorization Problem

Color prediction is inherently multimodal – many objects can take on several plausible colorizations. For example, an apple is typically red, green, or yellow, but unlikely to be blue or orange.

Evaluating synthesized images is notoriously difficult. Since our ultimate goal is to make results that are compelling to a human observer, we should introduce a novel way of evaluating colorization results, directly testing their perceptual realism.

# Color Space Choosing

## YUV

YUV is mostly used in video encoding. Y channel contains the luminance information, which is the content of one image/frame. U and V are chrominance channels, which are contain the color information. The YUV color space is employed, since the color space minimize the correlation between the three coordinates axes of the color space.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526110114.png)

YUV and its each components. The image is from Wikipedia.

Cheng [^1], Varga[^10], and Cao[^11] uses YUV as their training and inference color space.

## YCbCr

YcbCr is the scaled and offset version of YUV. Cb represents blue component and Cr represents red components. YCbCr colorspace is linear, simple and widely used (e.g., by JPEG).

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526105836.png)

For example, That the white snow is represented as a middle value in both Cr and Cb; that the brown barn is represented by weak Cb and strong Cr; that the green grass is represented by weak Cb and weak Cr; and that the blue sky is represented by strong Cb and weak Cr. This photo is form the Internet.

Guadarrama [^12] discretize the Cb and Cr channels separately into 32 bins.

## RGB

RGB is the most popular color space in our daily life, it is related to the human eyes perception. But in colorization, none of these channels contains pure image content of pure color information. Only if you put them together, you can see the whole image information.

For the representation of color predictions, using RGB is overdetermined, as lightness L is already known.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526110222.png)

This picture indicate the RGB color space. It is from David Briggs.

Zhu [^14] use RGB as his training color space.

## HSL

Hue-based spaces, such as HSL, can be thought of as a color cylinder, with angular coordinate H (hue), radial distance S (saturation), and height L (lightness). The values of S and H are unstable at the bottom (black) and top (white) of the cylinder. HSV describes a similar color cylinder which is only unstable at the bottom. However, L is no longer one of the channels. He wish to avoid both instabilities and still retain L as a channel. The solution is a color bicone, where chroma (C) takes the place of saturation.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526110503.png)

HSL color space. This picture is from Canon Inc.

Larsson [^8] also used HLS in his experiment.

## Lab

CIE Lab is the most usually used color space in colorization. Lab is designed to be perceptually linear. The color vector (a, b) defines a Euclidean space where the distance to the origin determines chroma.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526110931.png)

In the L* a* b* color space, L* indicates lightness and a* and b* are chromaticity coordinates. a* and b* are color directions: +a* is the red axis, -a’ is the green axis, +b* is the yellow axis and -b\* is the blue axis. Area around the center represents achromatic colors and moving outwards, color saturation increases. The photo is from Konica Minolta.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526111355.png)

Apple in Lab. The photo is from Konica Minolta.

Aditya [^2], Lal [^3], Baldassarre[^4], Royer[^5], Zhang [^6] [^7], Larsson [^8] [^9], Deshpande [^13], Ozbulak[^15], Vitoria[^16], Nguyen-Quynh[^17], Iitsuka[^18] and Su[^19] all use Lab as their training and inferencing color space.

## Comparison on Color Space

Iitsuka[^18] has compared the effect of using various color spaces. In particular,
they compare RGB, YUV and L* a* b* color spaces.

In the case of RGB, the output of the model is 3 instead of 2 corresponding to the red, green and blue channels. He trained directly using the RGB values; however, for testing, he converted the RGB image to YUV and substitute the input grayscale image as the Y channel of the image. This ensures that the output images of all the models have
the same luminance. For all different color spaces, they normalize the values to lie in the [0, 1] range of the Sigmoid transfer function of the output layer.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200521110209.png)

In general, results are very similar.
However, they did find some cases in which the L* a* b* gives the most perceptionally reasonable approach in comparison with RGB
and YUV.

# Neural Network

Most colorization problem can be form into this equation: Given a set of \\(\Lambda=\{\overrightarrow{G}, \overrightarrow{C}\}\\), where \\(\overrightarrow{G}\\) are grayscale images and \\(\overrightarrow{C}\\) are corresponding color images respectively, the method is based on a premise: there exists a complex gray-to-color mapping function \\(\mathcal{F}\\) that can map the features extracted at each pixel in \\(\overrightarrow{G}\\) to the corresponding chrominance values in \\(\overrightarrow{C}\\). We aim at learning such a mapping function from \\(\Lambda\\) so that the conversion from a new gray image to color image can be achieved by using \\(\mathcal{F}\\).

## non-Generative

### Fully Connected

Cheng [^1] maybe the first one propose an automatic colorization method using neural network. In the early stage of deep learning, feature extraction are mostly borrowed from traditional computer vision. The network structure is also based on fully connected layers, which means there are no convolution or other filters. In his model, the number of neurons in the input layer is equal to the dimension of the feature descriptor extracted from each pixel location in a grayscale image and the output layer has two neurons which output the U and V channels of the corresponding color value, respectively. He perceptually set the number of neurons in the hidden layer to half of that in the input layer. Each neuron in the hidden or output layer is connected to all the neurons in the proceeding layer and each connection is associated with a weight.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/1.png)

#### Feature Descriptor

1. Low-level Patch Feature:
   the array containing the sequential grayscale values in a 7×7 patch center at pixel _p_.

2. Mid-level DAISY Feature:
   DAISY is a fast local descriptor for dense matching.DAISY can achieve a more accurate discriminative description of a local patch and thus can improve the colorization quality on complex scenarios.

3. High-level Semantic Feature:
   He adopted the state-of-art scene parsing algorithm to annotate each pixel with its category label, and obtain a semantic map for the input image.

### End-to-End Convolution + Fully Connected

Iizuka & Simo-Serra[^18] propose a network that concatenates two separate paths, specializing in global and local features, respectively. They called it Joint Global and Local Model, which means the network is formed by several subcomponents that form a Directed Acyclic Graph (DAG) and contain important discrepancies with widely-used standard models. In particular:

1. can process images of any resolution (which is not unless they discard the global features network)
2. incorporates global image priors for local predictions
3. can directly transfer the style of an image into the colorization of another (End-to-End)

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200521094546.png)

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200521100834.png)

Zhang [^7] implemented a CNN to map from a grayscale input to a distribution over quantized color value outputs using the architecture.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200522100022.png)

The system is not quite end-to-end trainable, but note that the mapping H operates on each pixel independently, with a single parameter,and can be implemented as part of a feed-forward pass of the CNN. The network was trained from scratch with k-means initialization, using the ADAM solver for
approximately 450k iterations.

### Fully Convolution

Larsson [^8] proposed a fully convolution version of VGG-16 with two changes:

1. the classification layer (fc8) is discarded
2. the first filter layer (conv1_1) operates on a single intensity channel instead of mean-subtracted RGB.

He extract a hypercolumn descriptor for a pixel by concatenating the features at its spatial location in all layers, from data to conv7 (fc7), resulting in a 12417 channel descriptor. He fed this hypercolumn into a fully connected layer with 1024 channels (h fc1 in Figure 2), to which he connected output predictors.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526210657.png)

### Multi-Network

Guadarrama [^12] propose a new method that employs a PixelCNN probabilistic model to produce a coherent joint distribution over color images given a grayscale input.

That is, he turned colorization into a **sequential decision making task**, where pixels are colored **sequentially**, and the color of each pixel **is conditioned on the input image and previously colored pixels**.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200523214010.png)

After chrominance of low resolution images, he used bilinear interpolation for upsampling instead of learned upsampling.

The refinement network is trained on a 28x28 downsampling of the ground truth chroma images. The reason he did not train it end-to-end with the PixelCNN is the following: the PixelCNN can generate multiple samples, all of which might be quite far from the true chroma image; if he forced the refinement network to map these to the true RGB image, it might learn to ignore these “irrelevant” color “hints”, and just use the input grayscale image. By contrast, when he trained using the true low-resolution chroma images, he forced the refinement network to focus its efforts on learning how to combine these “hints” with the edge boundaries which are encoded in the grayscale image.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200524102310.png)

### Multi-Module Network

Su proposed both instance colorization network and full-image colorization network. The two networks share the same architecture but different weights.

First, he leveraged an off-the-shelf pre-trained object detector to obtain multiple object bounding boxes \\(\{B_i\}^N_{i=1}\\) from the grayscale image, where \\(N\\) is the number of instances. He then generate a set of instance images \\(\{X_i\}^N_{i=1}\\) by resizing the images
cropped from the grayscale image using the detected bounding boxes. Next, he fed each instance image \\(X_i\\) and input grayscale image \\(X\\) to the instance colorization network and full-image colorization network, respectively. Finally, he employed a fusion module that fuses all the instance features with the full-image feature at each layer. This step repeats until the last layer and ob- tains the predict color image \\(Y\\).

He adopt a sequential approach that first trains the full-image network, followed by the instance network, and finally trains the feature fusion module by freezing the above two networks.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527192037.png)

In this work, he adopt the main colorization network introduced in Zhang [^20] as our backbones.

The fusion module is shown below

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527194756.png)

## Generative Model

### Autoencoder

Zhang [^6] propose split-brain autoencoder architecture for unsupervised representation learning.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527102626.png)

Here is an application on colorization:

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527102929.png)

### VAE (Variation Autoencoder)

Deshpande [^2] proposed that a natural approach to solve the problem is to learn a conditional model \\(P(C|G)\\) for a color field \\(C\\) conditioned on the input grey-level image \\(G\\).

He can then draw samples from this conditional model \\({C_k}^N_{k=1} ~ P(C|G)\\) to obtain diverse colorizations.

The overall architecture of the network he proposed:

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526214402.png)

Deshpande's strategy is to represent \\(C\\) by its low-dimensional latent variable embedding \\(z\\). This embedding is learned by a generative model VAE.The encoder network is roughly the mirror of decoder network.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526214655.png)

He leveraged a Mixture Density Network (MDN) to learn a multi-modal conditional model \\(P(z|G)\\).
MDN can get a Gaussian Mixture Model (GMM) that generates the low-dimensional embedding. In testing procesdure, he used the VAE decoder to generate the corresponding diverse color fields.

### GAN

#### Single-Module GAN
Cao [^11] used conditional GANs to generate diverse colorization for a single grayscale image while maintaining their reality. Conditional GAN is a much more suitable framework to handle diverse colorization than other CNNs. Meanwhile, as the discriminator only needs the signal of whether a training instance is real or generated, which is directly provided without any human annotation during the training phase, the task is in an unsupervised learning fashion.

He build a fully convolutional generator and each convolutional layer is splinted by a concatenate layer to continuously render the conditional grayscale information. Additionally, to maintain the spatial information, he set all convo- lution stride to 1 to avoid downsizing data. He also concatenate noise channels to the first half convolutional layers of the generator to attain more diversity in the color image generation process. As the generator G would capture the color distribution, he can alter the colorization result by changing the input noise.

Traditional GANs and conditional GANs receive noise information at the very start layer, during the continuous data transformation through the network, the noise information is attenuated a lot. To overcome this problem and make the colorization results more diversified, he concatenated the noise channel onto the first half of the generator layers (the first three layers in our case).

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527102119.png)

#### Multi-Module GAN

Vitoria [^16] proposed the ChromaGAN. It contains three distinct parts. The first two, belonging to the genera- tor, focus on geometrically and semantically generating a color image information (a, b) and classifying its semantic content. The third one belongs to the discriminator network learning to distinguish between real and fake data.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527110608.png)

*The generator is similar to Iitsuka's model architecture.*

# Objective Function

## Regression

### MSE (Least Squares Minimization/RMSE)

$$
\arg \min \sum_{p=1}^n ||\hat{Y} - Y||^2
$$

where \\(\hat{Y}\\) means the predicted result, and \\(Y\\) is the groundtruth.

However, the results from these previous attempts tend to look desaturated. This loss is not robust to the inherent ambiguity and multimodal nature of the colorization problem. If an object can take on a set of distinct ab values, the optimal solution to the Euclidean loss will be the mean of the
set. In color prediction, this averaging effect favors grayish, desaturated results.
Additionally, if the set of plausible colorizations is non-convex, the solution will
in fact be out of the set, giving implausible results.

Cheng [^1], Iizuka & Simo-Serra[^18] used it as the basic colorization loss.

### smooth-L1 loss (Huber loss)

Zhang [^20] proposed the smooth-L1 loss with δ = 1:

$$
l_\delta(x,y)=\frac{1}{2}(x-y)^2 \mathbb{1}_{\{|x-y|<\delta\}}+\delta(|x-y|-\frac{1}{2}\sigma)  \mathbb{1}_{\{|x-y|\geq\delta\}}
$$

The original huber loss is:

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200527195244.png)

When \\(\delta\\) approching 0, huber loss will be MAE; Otherwise, huber loss will be MSE.

### KL Divergence

Larsson [^8] predict distributions over a set of color bins, using

$$
L_{hist}(x,y)=D_{KL}(y||f(x))
$$

where *y* describes a histogram over \\(K\\) bins. The ground-truth histogram y is set as the empirical distribution in a rectangular region of size R around the center pixel.We simply set R = 1. For histogram predictions, the last layer of neural network f is always a softmax.

He bin the Lab axes by evenly spaced Gaussian quantiles (µ = 0, σ = 25). They can be encoded separately for a and b (as marginal distributions), in which case our loss becomes the sum of two separate terms. They can also be encoded as a joint distribution over a and b, in which case he let the quantiles form a 2D grid of bins. In our experiments, he set K = 32 for marginal distributions and K = 16 × 16 for joint. He determined these numbers, along with σ, to offer a good compromise of output fidelity and output complexity.

## Classification

### Corss-Entropy loss
Iizuka & Simo-Serra[^18] finds that the MSE criterion makes obvious mistake due to not properly learning the global context of the image. So they facilitate the optimization by also training for classification jointly with the colorization. Classification labels correspond to a global image tag and thus can be used to train for global image feature. They introduced the cross-entropy loss, jointly with the MSE loss for the colorization network.

Thus, the global loss becomes:

$$
L(y^{color}, y^{class}) = ||y^{color} - y^{groundtruth}||^2_{FRO} - \alpha \large(y^{class}_{l^{class}} - \log \large(\sum_{i=0}^N \exp(y^{class}_i)\large)\large)
$$

### Multinomial Classification

Zhang [^7] treated the colorization problem as multinomial classification. Instead, he treat the problem as multinomial classification. He quantized the *ab* output space into bins with grid size 10 and keep the Q = 313 values which are in-gamut. For a given input \\(X\\), he learned a mapping \\(\hat{Z}=\mathcal{G}(X)\\) to a probability distribution over possible color \\(\hat{Z} \in [0, 1]^{H\times W\times Q}\\), where *Q* is the number of quantized ab values.

To compare predicted \\(\hat{Z}\\) against ground truth, we define function \\(\hat{Z}=\mathcal{H}_{gt}^{-1}(Y)\\), which converts ground truth color *Y* to vector *Z*, using a soft-encoding scheme.

For soft-enconding scheme:

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200522102840.png)

He then used multinomial cross entropy loss:

$$
L_{cl}(\hat{Z}, Z) = -\sum_{h,w}v(Z_h, w)\sum_q Z_{h,w,q} \log(\hat{Z}_{h,w,q})
$$

where \\(v(\cdot)\\) is a weighting term that can be used to rebalance the loss based on color-class rarity. Finally, he mapped probability distribution \\(\hat{Z}\\) to color values \\(\hat{Y}\\) with function \\(\hat{Y} = \mathcal{H}(\hat{Z})\\).

He accounted for the class imbalance problem by re-weighting the loss of each pixel at train time based on the pixel color rarity. Each pixel is weighed by factor \\(w\in R^Q\\), based on its closest ab bin.

$$
v(Z_{h,w}) = w_{q^*},\ where\ q^*=\arg \max_q Z_{h,w,q}\\
w \propto \large( (1-\lambda) \tilde{p} + \frac{\lambda}{Q}\large)^{-1},\ \mathbb{E}[w] = \sum_q \tilde{p}_qw_q=1
$$

To obtain smoothed empirical distribution \\(p \in \Delta^Q\\), he estimated the empirical training set and smooth the distribution with a Gaussian kernel \\(G\sigma \\). He then mix the distribution with a uniform distribution with weight \\(\lambda \in [0,1]\\), take the reciprocal, and normalize so the weighting factor is 1 on expectation. He found that values of \\(\lambda = \frac{1}{2}\\) and \\(\sigma = 5\\) worked well.

He defined \\(\mathcal(H)\\), which maps the predicted distribution \\(\hat(Z)\\) to point estimate \\(\hat(Y)\\) in ab space. One choice is to take the mode of the predicted distribution for each pixel. On the other hand, takeing the mean of the predicted distribution, but desaturated result. To try to get the best of both worlds, he interpolated by re-adjusting the temperature \\(T\\) of the softmax distribution, and taking the mean of the result.

$$
\mathcal{H}(Z_{h,w}) =\mathbb{E}[f_T(Z_{h,w})], \ f_T(z)=\frac{\exp(\log(z)/T)}{\sum_q\exp(\log(z_q)/T)}
$$

He found that temperature \\(T=0.38\\) captures the virancy of the mode while maintaining the spatial coherence of the mean.

### Pixel CNN Loss

Guadarrama [^12] discretized the Cb and Cr channels separately into 32 bins. Thus the model has the following the following form:

$$
p(y|x)=\prod_i p(y(i, r) | y(1:i-1, :), x)p(y(i,b)|y(i,r), y(1:i-1, :), x)
$$

where \\(y(i,r)\\) is the Cr value for pixel i, and \\(y(i,b)\\) is the Cb value.

He trained this model using maximum likelihood, with a cross-entropy loss per pixel. Because of the sequential nature of the model, each prediction is conditioned on previous pixels.

## VAE loss

### Decoder loss

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526220122.png)

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526220137.png)

#### MDN loss

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526220230.png)

Loss comparison：

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200526220348.png)

## GAN loss

### Pure GAN loss

The objective of a GAN can be expressed as

$$
\mathcal{L}_{GAN}(G,D)=\mathbb{E}_{x~P_{data}(x)}[\log D(x)] + \mathbb{E}_{z~P_z(z)}[\log (1-D(G(z)))]
$$

### Conditional GAN loss

while the objective of a conditional GAN is

$$
\mathcal{L}_{cGAN}(G,D)=\mathbb{E}_{x~P_{data}(x)}[\log D(x)] + \mathbb{E}_{y~P_{gray}(y), z~P_z(z)}[\log (1-D(G(y,z)))]
$$

where G tries to minimize this objective against an adversarial D that tries to maximize it

$$
G^* = \arg \min_G \max_D \mathcal{L}_{cGAN}(G,D)
$$

Without z, the generator could still learn a mapping from y to x, but would produce deterministic outputs.

### GAN loss combination

Vitoria [^16] proposed ChromaGAN which contains multipal loss. The generator model combines two different modules. So there will be \\(G_{\theta 1}^1, G_{\theta 2}^2\\) Its objective loss is defined by:

$$
\mathcal{L}(G_\theta, D_w)=\mathcal{L}_e(G_{\theta 1}^1)+ \lambda_g \mathcal{L}_g(G_{\theta 1}^1, D_w) + \lambda_s\mathcal{L}_s(G_{\theta 2}^2)
$$

The first term denotes the color error loss, using Euclidean Loss.

The last item is

$$
\mathcal{L}_s(G_{\theta 2}^2)=\mathbb{E}_{L~\mathbb{P}_{rg}}[KL(y_v||G_{theta 2}^2(L))]
$$

denotes the class distribution loss, where \\(\mathbb{P}_{rg}\\) denotes the distribution of grayscale input images, and \\(y_v\\) the output distribution vector of a pre-trained VGG-16 model applied to the grayscale image.

Finally, \\(L_g\\) denotes the WGAN loss which consists of an adversarial Wasserstein GAN loss. Leverage the WGAN instead of other GAN losses favours nice properties such as avoiding vanishing gradients and mode collapse, and achieves more stable training.

$$
\mathcal{L}_g(G_{\theta 1}^1, D_w) = \mathbb{E}_{\tilde{I}~\mathbb{P}_r}[D_w(\tilde{I})] -\mathbb{E}_{(a,b)~\mathbb{P}_G_{\theta 1}^1}[D_w(L,a,b)]-\mathbb{E}_{\tilde{I}~\mathbb{P}_\tilde{I}}[(||\triangledown_\tilde{I} D_w(\tilde{I})||_2 -1)^2]
$$

where \\(\mathbb{P}_G_{\theta 1}^1\\) is the model distribution of \\(G_{\theta 1}^1(L)\\), with \\(L~\mathbb{P}_{rg}\\). \\(\mathbb{P}_{\tilde{I}}\\) is implicitly defined sampling uniformly along striaight line between pairs of points sampled from the data distribution \\(\mathbb{P}_r\\) and the generator distribution

# Evaluation Methods

## Objective Evaluation

### Raw Accuracy

As a low-level test, Richard [^7] computed the percentage of predicted pixel colors within a thresholded L2 distance of the ground truth in ab color space. But note that this AuC metric measures raw prediction
accuracy, whereas our method aims for plausibility. So this evaluation method may not quite fit for colorization task.

### PSNR

Peak signal-to-noise ratio, often abbreviated **PSNR**, is an engineering term for the ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation.

PSNR is most easily defined via MSE, so most MSE loss model are using PSNR as their evaluation index. But in fact, PSNR is not the suitable index for colorization. Due to the multimodel characteristic of colorization output, PSNR can only compare to the groudtruth, but not the perceptual level.

### SSIM Family

The structural similarity (SSIM) index is a method for predicting the perceived quality of images. SSIM is designed to improve on traditional methods such as peak signal-to-noise ratio (PSNR) and mean squared error (MSE).

Since the mapping from gray to color is one-to-many, we cannot evaluate performance by comparing the predicted color image to the ”ground truth” color image in terms of perceptual similarity metrics such as SSIM.

![](https://raw.githubusercontent.com/rasin-tsukuba/blog-images/master/img/20200524105356.png)

### Semantic Interpretability (VGG classification)

Richard [^7] tested this by feeding our fake colorized images to a VGG network that was trained to predict ImageNet classes from real color photos. Using an off-the-shelf classifier to assess the realism of synthesized data.

## Subjective Evaluation

### Perceptual Realism (User Study)

Iizuka & Simo-Serra[^18] has performed a user study asking the question “Does this image look natural to you?” to evaluate the naturalness of the ground- truth validation images, the results of our baseline, and the results of our model.

Richard [^7] ran a real vs. fake two-alternative forced choice experiment on Amazon Mechanical Turk (AMT).

# Reference

[^1]: Cheng, Z., Yang, Q., & Sheng, B. (2015). Deep colorization. Proceedings of the IEEE International Conference on Computer Vision, 2015 Inter, 415–423. https://doi.org/10.1109/ICCV.2015.55
[^2]: Deshpande, A., Lu, J., Yeh, M. C., Chong, M. J., & Forsyth, D. (2017). Learning diverse image colorization. Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017-Janua, 2877–2885. https://doi.org/10.1109/CVPR.2017.307
[^3]: Lal, S., Garg, V., & Verma, O. P. (2017). Automatic image colorization using adversarial training. ACM International Conference Proceeding Series, 84–88. https://doi.org/10.1145/3163080.3163104
[^4]: Baldassarre, F., Morín, D. G., & Rodés-Guirao, L. (2017). Deep Koalarization: Image Colorization using CNNs and Inception-ResNet-v2. June 2017, 1–12. http://arxiv.org/abs/1712.03400
[^5]: Royer, A., Kolesnikov, A., & Lampert, C. H. (2017). Probabilistic image colorization. British Machine Vision Conference 2017, BMVC 2017, 1–15. https://doi.org/10.5244/c.31.85
[^6]: Zhang, R., & Efros, A. A. (2017). Split-Brain Autoencoders: Unsupervised Learning by Cross-Channel Prediction. 1058–1067.
[^7]: Zhang, R., Isola, P., & Efros, A. A. (2016). Colorful image colorization. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9907 LNCS, 649–666. https://doi.org/10.1007/978-3-319-46487-9_40
[^8]: Larsson, G., Maire, M., & Shakhnarovich, G. (2016). Learning representations for automatic colorization. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9908 LNCS, 577–593. https://doi.org/10.1007/978-3-319-46493-0_35
[^9]: Larsson, G., Maire, M., & Shakhnarovich, G. (2016). Learning representations for automatic colorization. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9908 LNCS, 577–593. https://doi.org/10.1007/978-3-319-46493-0_35
[^10]: Varga, D., & Szirányi, T. (2017). Convolutional Neural Networks for automatic image colorization. 5, 1–15. http://eprints.sztaki.hu/9292/1/Varga_1_3306455_ny.pdf
[^11]: Cao, Y., Zhou, Z., Zhang, W., & Yu, Y. (2017). Unsupervised Diverse Colorization via Generative Adversarial Networks. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10534 LNAI, 151–166. https://doi.org/10.1007/978-3-319-71249-9_10
[^12]: Guadarrama, S., Dahl, R., Bieber, D., Norouzi, M., Shlens, J., & Murphy, K. (2017). Pixcolor: Pixel recursive colorization. British Machine Vision Conference 2017, BMVC 2017, 1–17. https://doi.org/10.5244/c.31.112
[^13]: Deshpande, A., Lu, J., Yeh, M. C., Chong, M. J., & Forsyth, D. (2017). Learning diverse image colorization. Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017-Janua, 2877–2885. https://doi.org/10.1109/CVPR.2017.307
[^14]: Zhu, L., & Funt, B. (2018). Colorizing color images. IS and T International Symposium on Electronic Imaging Science and Technology, 1–6. https://doi.org/10.2352/ISSN.2470-1173.2018.14.HVEI-541
[^15]: Ozbulak, G. (2019). Image colorization by capsule networks. IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2019-June, 2150–2158. https://doi.org/10.1109/CVPRW.2019.00268
[^16]: Vitoria, P., Raad, L., & Ballester, C. (2019). ChromaGAN: Adversarial Picture Colorization with Semantic Class Distribution. 2445–2454. http://arxiv.org/abs/1907.09837
[^17]: Nguyen-Quynh, T. T., Do, N. T., & Kim, S. H. (2020). MLEU: Multi-level embedding u-net for fully automatic image colorization. ACM International Conference Proceeding Series, 119–121. https://doi.org/10.1145/3380688.3380720
[^18]: Iizuka, S., Simo-Serra, E., & Ishikawa, H. (2016). Let there be color! ACM Transactions on Graphics, 35(4), 1–11. https://doi.org/10.1145/2897824.2925974
[^19]: Su, J.-W., Chu, H.-K., & Huang, J.-B. (2020). Instance-aware Image Colorization. http://arxiv.org/abs/2005.10825

[^20]: Zhang, R., Zhu, J. Y., Isola, P., Geng, X., Lin, A. S., Yu, T., & Efros, A. A. (2017). Real-time user-guided image colorization with learned deep priors. ACM Transactions on Graphics, 36(4). https://doi.org/10.1145/3072959.3073703


text:
---
layout    : post
title     : "[译] 拨乱反正：Ken Thompson 才是 UTF-8 的设计者（2003）"
date      : 2019-12-22
lastupdate: 2019-12-22
categories: utf-8
---

### 译者序

本文翻译自 2003 年的一份网页存档：[UTF-8
history](https://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt)。

2003 年 4 月的最后一个夜晚即将从键盘上溜走时，作为 UTF-8 设计
过程的亲眼见证者，坐在电脑前的 Rob Pike 终于决定写一封邮件来阻止 “UTF-8 编码是
IBM 设计的” 这一错误的继续传播，本文的故事由此展开。

Rob 在邮件中非常谦虚地隐去了自己作为联合设计者的功劳，只是轻描淡写地说了一句自己
期间承担了 Ken 的鼓励师的角色。

### 几封邮件及时间线

* `2003.04.30 22:32:32`: [1. Rob Pike：不要再说 UTF-8 是 IBM 设计的了](#ch_1)
* `2003.06.07 18:44:05`: [2. Rob Pike：我请了 Russ Cox 去存档中找当时的往来邮件](#ch_2)
* `2003.06.07  7:46 PM`: [3. Russ Cox：找到的相关邮件](#ch_3)
* `1992.09.04 03:37:39`: [4. Ken：能否让 utf.c 实现更整洁（存档邮件)](#ch_4)
* `1992.09.08 03:22:07`: [5. Ken：UTF-8 提案及代码（存档邮件)](#ch_5)
* `1992.09.08 03:24:58`: [6. Ken：抄送我自己的邮件还没收到（存档邮件)](#ch_6)
* `1992.09.08 03:42:43`: [7. Ken：终于收到抄送了（存档邮件)](#ch_7)
* `1992.09.02         `: [8. 第一份 UTF-8 提案：直接追加在原始 FSS-UTF 提案后面（存档邮件)](#ch_8)

**由于译者水平有限，本文不免存在遗漏或错误之处。如有疑问，请查阅原文。**

以下是译文。

----

# 1. Rob Pike：不要再说 UTF-8 是 IBM 设计的了

```
Subject: UTF-8 history
From: "Rob 'Commander' Pike" <r (at) google.com>
Date: Wed, 30 Apr 2003 22:32:32 -0700 (Thu 06:32 BST)
To: mkuhn (at) acm.org, henry (at) spsystems.net
Cc: ken (at) entrisphere.com
```

回望 UTF-8 的过去，我看到一个错误的故事在不断传播。这个故事说：

1. IBM 设计了 UTF-8
1. Plan 9 实现了这份设计方案

这不是事实。

**时间回到 1992 年 9 月前后，在新泽西（New Jersey）的某次晚餐上，我亲眼见
证了 UTF-8 在一张餐桌纸上的诞生**。

下面这些才是事实：

> 我们曾用最初的 ISO 10646 UTF 使 Plan 9 支持 16-bit 字符，但结果令我们非常不满
> 意。在 Plan 9 系统即将交付的某个傍晚，我接到了几个人打来的一通电话，这些人应
> 该是 IBM 的 —— 我记得他们当时在 Austin —— 正在参加一个 X/Open 委员会会议。他们
> 打电话的目的是希望 Ken 和我评审他们的 FSS/UTF 设计方案。我们当时知道他们为什么
> 要引入一个新的设计，**更重要的是，Ken 和我当时突然意识到，这是一个充分利用我俩
> 的经验来设计一个真正优秀的标准的好机会，而标准推进的事情可以交给他们**。
>
> 我们向对方表达了这种想法，得到的答复是：**只要我们能在尽量短的时间内给出一套方
> 案，他们愿意去推进这件事情**。然后，我俩就去餐厅吃饭了，**Ken 在吃饭期间确定了
> bit-packing 的设计**，当吃完回到实验室时，我们打给了 X/Open 的这几位朋友，向他
> 们解释了我们的设计方案。
>
> 我们以邮件的形式将这套规范的大纲（outline of our spec）发给了他们，**他们回复
> 说这比他们自己设计的版本好多了**（我压根就没真正见过他们的提案；反正我是想
> 不起来），并询问我们最快什么时候能实现它？我记得这是一个周三的晚上，我们回复
> 说下周一之前一定可以提供一个完整的、可运行的系统，因为我记得下周一是他们投票表
> 决的时间。
>
> 因此，那个晚上 Ken 编写了 packing 和 unpacking 的代码，我将这些代码拆分成了 C 和
> graphics 库。第二天所有的代码都好了之后，我们开始将系统上所有的文本文件转换成
> UTF-8 编码格式。到了周五的某个时刻，**Plan 9 运行起来了，并且完全运行在这种名为
> UTF-8 的编码之上**。然后我们打给了 X/Open 和其他一些人，但他们后来对此事的描述，
> 却是一段略微修改过的历史。

为什么我们不直接用他们的 FSS/UTF 设计方案呢？根据我的记忆，是因为在他们第一次打
电话过来时，我提出了几个这类编码方案应该解决的问题， 而其中**至少有一个问题是
FSS/UTF 方案无法解决的** —— 对于从中间开始获取的字节流，**在读取不超过一个字
符的前提下就能对字节流进行同步的能力**（synchronize a byte stream picked up
mid-run, with less that one character being consumed before synchronization）。
正是因为缺乏这种能力，所以我们才可以自由地 —— 他们也给了我们自由 —— 来设计我们自
己的方案。

我认为“IBM 设计了 UTF-8，Plan 9 实现了它”的故事最初是从 RFC2279 中来的。当时
看到 UTF-8 如此流行我们非常高兴，因此就没有去纠正这段误传的历史。现在我和 Ken 都
已经不在当初的实验室了，但我相信存档中一定有当时的邮件可以证明前面讲的内容，我
也许能找人把这些邮件捞出来。

最后，**将 UTF-8 变成标准并且推广开来确实是 X/Open 和 IBM 那些人的功劳，但不管历
史书上怎么说，UTF-8 都是 Ken 设计的**（我的贡献是期间中充当了 Ken 的鼓励师）。

（邮件落款）- rob

# 2. Rob Pike：我请了 Russ Cox 去存档中找当时的往来邮件

```
Date: Sat, 07 Jun 2003 18:44:05 -0700
From: "Rob `Commander' Pike" <r (at) google.com>
To: Markus Kuhn <Markus.Kuhn (at) cl.cam.ac.uk>
cc: henry (at) spsystems.net, ken (at) entrisphere.com, Greger Leijonhufvud <greger (at) friherr.com>
Subject: Re: UTF-8 history
```

我请了 Russ Cox 帮忙去存档中寻找当时这些资料。下面附录了他的邮件。
相信这些内容会让你相信之前邮件中所述均确有其事。

我们发给 X/Open 的邮件（我记得是 Ken 编辑和发送的那份设计文档）包括一个新的 设计
考虑： `#6` 关于检测字符边界（discovering character boundaries）。我们无从知道
X/Open 最初的提案如何影响了我们；这两份提案差别非常大，但确实也有某些相同点（
very different but do share some characteristics）。我不记得我曾仔细地看过他们的
提案，这已经是很久之前的事情了。但我非常清楚地记得 Ken 在餐桌纸上完成了设计
，我多么希望我们把那张纸保存了下来！

（邮件落款）- rob

## 3. Russ Cox：找到的相关邮件

```
From: Russ Cox <rsc (at) plan9.bell-labs.com>
To: r (at) google.com
Subject: utf digging
Date-Sent: Saturday, June 07, 2003 7:46 PM -0400
```

----

* `1992.09.04 19:51:55`：`/sys/src/libc/port/rune.c` 文件的编码格式从原来老的大
  量使用除法（division-heavy）的 UTF 格式转换成了新的 UTF-8 格式
* `1992.09.04`：`/sys/src/libc/port/rune.c` 添加了注释，然后就没有再修改过了，直到 `1996.11.14`
* `1996.11.14`：对 `runelen` 做了加速优化：显式检查 rune 而不是使用 `runetochar` 的返回值
* `2001.5.26`：下一次也是最后一次修改，添加了 `runenlen()` 函数

下面是在你的邮箱中 `grep` utf 找到的几封邮件。第一封是关于 `utf.c`，这个文件基本
上是照抄了 `wctomb` 和 `mbtowc`，用于处理 32 bit rune 的 full 6-byte utf-8 编码。
这段代码非常丑陋，全部逻辑都在控制流中。**我认为在第一封邮件之后，这段代码变成了
提案中的代码**。

在 `/usr/ken/utf/xutf` 目录中，我找到了一份似乎是最初的无法自同步的（
not-self-synchronizing）编码提案，而 **utf-8 方案追加到了这
份文件的末尾**（从 "We define 7 byte types" 开始）。这些内容也附在了下面。

下面贴的是第一版的邮件，时间是 `1992.09.02 23:44:10`。经过几次修改，在
`1992.09.08` 号形成了第二封邮件，见下面。

邮件日志显式了第二封邮件发了出去，以及过了一段时间后抄送给 Ken 的邮件到达了。

```
helix: Sep  8 03:22:13: ken: upas/sendmail: remote inet!xopen.co.uk!xojig
> From ken Tue Sep  8 03:22:07 EDT 1992<EMAIL_ADDRESS>6833
helix: Sep  8 03:22:13: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:22:07 EDT 1992 6833
helix: Sep  8 03:22:16: ken: upas/sendmail: remote pyxis!andrew From ken Tue Sep  8 03:22:07 EDT 1992 (andrew) 6833
helix: Sep  8 03:22:19: ken: upas/sendmail: remote coma!dmr From ken Tue Sep  8 03:22:07 EDT 1992 (dmr) 6833
helix: Sep  8 03:25:52: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:24:58 EDT 1992 141
helix: Sep  8 03:36:13: ken: upas/sendmail: delivered ken From ken Tue Sep 8 03:36:12 EDT 1992 6833
```

# 4. Ken：能否让 utf.c 实现更整洁

```
>From ken Fri Sep  4 03:37:39 EDT 1992
```

你可能需要看看 `/usr/ken/utf/utf.c`，以及能否让代码更整洁一点。

# 5. Ken：UTF-8 提案及代码

```
>From ken Tue Sep  8 03:22:07 EDT 1992
```

下面是我们修改之后的 FSS-UTF 提案。其中所用的术语和原提案中一样。我要为此向原提
案的作者致歉。提案中的代码已经经过一定程度的测试（tested to some degree），比较
整洁（should be pretty good shape）。我们已经设置 Plan 9 接下来使用这种编码格式
（converted Plan 9 to use this encoding），并考虑发布一个版本（
issue a distribution）给一部分大学用户使用。

```
File System Safe Universal Character Set Transformation Format (FSS-UTF)
--------------------------------------------------------------------------

With the approval of ISO/IEC 10646 (Unicode) as an international
standard and the anticipated wide spread use of this universal coded
character set (UCS), it is necessary for historically ASCII based
operating systems to devise ways to cope with representation and
handling of the large number of characters that are possible to be
encoded by this new standard.

There are several challenges presented by UCS which must be dealt with
by historical operating systems and the C-language programming
environment.  The most significant of these challenges is the encoding
scheme used by UCS. More precisely, the challenge is the marrying of
the UCS standard with existing programming languages and existing
operating systems and utilities.

The challenges of the programming languages and the UCS standard are
being dealt with by other activities in the industry.  However, we are
still faced with the handling of UCS by historical operating systems
and utilities.  Prominent among the operating system UCS handling
concerns is the representation of the data within the file system.  An
underlying assumption is that there is an absolute requirement to
maintain the existing operating system software investment while at
the same time taking advantage of the use the large number of
characters provided by the UCS.

UCS provides the capability to encode multi-lingual text within a
single coded character set.  However, UCS and its UTF variant do not
protect null bytes and/or the ASCII slash ("/") making these character
encodings incompatible with existing Unix implementations.  The
following proposal provides a Unix compatible transformation format of
UCS such that Unix systems can support multi-lingual text in a single
encoding.  This transformation format encoding is intended to be used
as a file code.  This transformation format encoding of UCS is
intended as an intermediate step towards full UCS support.  However,
since nearly all Unix implementations face the same obstacles in
supporting UCS, this proposal is intended to provide a common and
compatible encoding during this transition stage.

Goal/Objective
--------------

With the assumption that most, if not all, of the issues surrounding
the handling and storing of UCS in historical operating system file
systems are understood, the objective is to define a UCS
transformation format which also meets the requirement of being usable
on a historical operating system file system in a non-disruptive
manner.  The intent is that UCS will be the process code for the
transformation format, which is usable as a file code.

Criteria for the Transformation Format
--------------------------------------

Below are the guidelines that were used in defining the UCS
transformation format:

    1) Compatibility with historical file systems:

	Historical file systems disallow the null byte and the ASCII
	slash character as a part of the file name.

    2) Compatibility with existing programs:

	The existing model for multibyte processing is that ASCII does
	not occur anywhere in a multibyte encoding.  There should be
	no ASCII code values for any part of a transformation format
	representation of a character that was not in the ASCII
	character set in the UCS representation of the character.

    3) Ease of conversion from/to UCS.

    4) The first byte should indicate the number of bytes to
	follow in a multibyte sequence.

    5) The transformation format should not be extravagant in
	terms of number of bytes used for encoding.

    6) It should be possible to find the start of a character
	efficiently starting from an arbitrary location in a byte
	stream.

Proposed FSS-UTF
----------------

The proposed UCS transformation format encodes UCS values in the range
[0,0x7fffffff] using multibyte characters of lengths 1, 2, 3, 4, 5,
and 6 bytes.  For all encodings of more than one byte, the initial
byte determines the number of bytes used and the high-order bit in
each byte is set.  Every byte that does not start 10xxxxxx is the
start of a UCS character sequence.

An easy way to remember this transformation format is to note that the
number of high-order 1's in the first byte signifies the number of
bytes in the multibyte character:

   Bits  Hex Min  Hex Max  Byte Sequence in Binary
1    7  00000000 0000007f 0vvvvvvv
2   11  00000080 000007FF 110vvvvv 10vvvvvv
3   16  00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv
4   21  00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv
5   26  00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv
6   31  04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv

The UCS value is just the concatenation of the v bits in the multibyte
encoding.  When there are multiple ways to encode a value, for example
UCS 0, only the shortest encoding is legal.

Below are sample implementations of the C standard wctomb() and
mbtowc() functions which demonstrate the algorithms for converting
from UCS to the transformation format and converting from the
transformation format to UCS. The sample implementations include error
checks, some of which may not be necessary for conformance:

typedef
struct
{
	int	cmask;
	int	cval;
	int	shift;
	long	lmask;
	long	lval;
} Tab;

static
Tab	tab[] =
{
	0x80,	0x00,	0*6,	0x7F,		0,		/* 1 byte sequence */
	0xE0,	0xC0,	1*6,	0x7FF,		0x80,		/* 2 byte sequence */
	0xF0,	0xE0,	2*6,	0xFFFF,		0x800,		/* 3 byte sequence */
	0xF8,	0xF0,	3*6,	0x1FFFFF,	0x10000,	/* 4 byte sequence */
	0xFC,	0xF8,	4*6,	0x3FFFFFF,	0x200000,	/* 5 byte sequence */
	0xFE,	0xFC,	5*6,	0x7FFFFFFF,	0x4000000,	/* 6 byte sequence */
	0,							/* end of table */
};

int
mbtowc(wchar_t *p, char *s, size_t n)
{
	long l;
	int c0, c, nc;
	Tab *t;

	if(s == 0)
		return 0;

	nc = 0;
	if(n <= nc)
		return -1;
	c0 = *s & 0xff;
	l = c0;
	for(t=tab; t->cmask; t++) {
		nc++;
		if((c0 & t->cmask) == t->cval) {
			l &= t->lmask;
			if(l < t->lval)
				return -1;
			*p = l;
			return nc;
		}
		if(n <= nc)
			return -1;
		s++;
		c = (*s ^ 0x80) & 0xFF;
		if(c & 0xC0)
			return -1;
		l = (l<<6) | c;
	}
	return -1;
}

int
wctomb(char *s, wchar_t wc)
{
	long l;
	int c, nc;
	Tab *t;

	if(s == 0)
		return 0;

	l = wc;
	nc = 0;
	for(t=tab; t->cmask; t++) {
		nc++;
		if(l <= t->lmask) {
			c = t->shift;
			*s = t->cval | (l>>c);
			while(c > 0) {
				c -= 6;
				s++;
				*s = 0x80 | ((l>>c) & 0x3F);
			}
			return nc;
		}
	}
	return -1;
}
```

# 6. Ken：抄送我自己的邮件还没收到

```
From ken Tue Sep  8 03:24:58 EDT 1992
```

邮件我已经发出并抄送了自己，但它好像进入了黑洞。我还没收到（i didnt get my copy）。
一定是彗星来临或天降异象，导致我的邮件卡在互联网上了。

# 7. Ken：终于收到抄送了

```
From ken Tue Sep  8 03:42:43 EDT 1992
```

终于收到抄送了（i finally got my copy）。

## 8. 第一份 UTF-8 提案：直接追加在原始 FSS-UTF 提案后面（存档邮件）

> 以 "We define 7 byte types" 为分割点，之前的是原始提案，后面是 Ken 和 Pike
> 添加的。 - 译者注

--- /usr/ken/utf/xutf from dump of Sep 2 1992 ---

```
File System Safe Universal Character Set Transformation Format (FSS-UTF)
--------------------------------------------------------------------------

With the approval of ISO/IEC 10646 (Unicode) as an international
standard and the anticipated wide spread use of this universal coded
character set (UCS), it is necessary for historically ASCII based
operating systems to devise ways to cope with representation and
handling of the large number of characters that are possible to be
encoded by this new standard.

There are several challenges presented by UCS which must be dealt with
by historical operating systems and the C-language programming
environment. The most significant of these challenges is the encoding
scheme used by UCS.  More precisely, the challenge is the marrying of
the UCS standard with existing programming languages and existing
operating systems and utilities.

The challenges of the programming languages and the UCS standard are
being dealt with by other activities in the industry.	However, we are
still faced with the handling of UCS by historical operating systems and
utilities. Prominent among the operating system UCS handling concerns is
the representation of the data within the file system. An underlying
assumption is that there is an absolute requirement to maintain the
existing operating system software investment while at the same time
taking advantage of the use the large number of characters provided by
the UCS.

UCS provides the capability to encode multi-lingual text within a single
coded character set.  However, UCS and its UTF variant do not protect
null bytes and/or the ASCII slash ("/") making these character encodings
incompatible with existing Unix implementations.  The following proposal
provides a Unix compatible transformation format of UCS such that Unix
systems can support multi-lingual text in a single encoding.  This
transformation format encoding is intended to be used as a file code.
This transformation format encoding of UCS is intended as an
intermediate step towards full UCS support.  However, since nearly all
Unix implementations face the same obstacles in supporting UCS, this
proposal is intended to provide a common and compatible encoding during
this transition stage.

Goal/Objective
--------------

With the assumption that most, if not all, of the issues surrounding the
handling and storing of UCS in historical operating system file systems
are understood, the objective is to define a UCS transformation format
which also meets the requirement of being usable on a historical
operating system file system in a non-disruptive manner. The intent is
that UCS will be the process code for the transformation format, which
is usable as a file code.

Criteria for the Transformation Format
--------------------------------------

Below are the guidelines that were used in defining the UCS
transformation format:

    1) Compatibility with historical file systems:

   Historical file systems disallow the null byte and the ASCII
   slash character as a part of the file name.

    2) Compatibility with existing programs:

   The existing model for multibyte processing is that ASCII does
   not occur anywhere in a multibyte encoding.  There should be no
   ASCII code values for any part of a transformation format
   representation of a character that was not in the ASCII character
   set in the UCS representation of the character.

    3) Ease of conversion from/to UCS.

    4) The first byte should indicate the number of bytes to follow in a
   multibyte sequence.

    5) The transformation format should not be extravagant in terms of
   number of bytes used for encoding.

Proposed FSS-UTF
----------------

The proposed UCS transformation format encodes UCS values in the range
[0,0x7fffffff] using multibyte characters of lengths 1, 2, 3, 4, and 5
bytes.  For all encodings of more than one byte, the initial byte
determines the number of bytes used and the high-order bit in each byte
is set.

An easy way to remember this transformation format is to note that the
number of high-order 1's in the first byte is the same as the number of
subsequent bytes in the multibyte character:

   Bits  Hex Min  Hex Max         Byte Sequence in Binary
1    7  00000000 0000007f 0zzzzzzz
2   13  00000080 0000207f 10zzzzzz 1yyyyyyy
3   19  00002080 0008207f 110zzzzz 1yyyyyyy 1xxxxxxx
4   25  00082080 0208207f 1110zzzz 1yyyyyyy 1xxxxxxx 1wwwwwww
5   31  02082080 7fffffff 11110zzz 1yyyyyyy 1xxxxxxx 1wwwwwww 1vvvvvvv

The bits included in the byte sequence is biased by the minimum value
so that if all the z's, y's, x's, w's, and v's are zero, the minimum
value is represented.	In the byte sequences, the lowest-order encoded
bits are in the last byte; the high-order bits (the z's) are in the
first byte.

This transformation format uses the byte values in the entire range of
0x80 to 0xff, inclusive, as part of multibyte sequences.  Given the
assumption that at most there are seven (7) useful bits per byte, this
transformation format is close to minimal in its number of bytes used.

Below are sample implementations of the C standard wctomb() and
mbtowc() functions which demonstrate the algorithms for converting from
UCS to the transformation format and converting from the transformation
format to UCS.  The sample implementations include error checks, some
of which may not be necessary for conformance:

#define OFF1   0x0000080
#define OFF2   0x0002080
#define OFF3   0x0082080
#define OFF4   0x2082080

int wctomb(char *s, wchar_t wc)
{
       if (s == 0)
	       return 0;       /* no shift states */
#ifdef wchar_t_is_signed
       if (wc < 0)
	       goto bad;
#endif
       if (wc <= 0x7f)         /* fits in 7 bits */
       {
	       s[0] = wc;
	       return 1;
       }
       if (wc <= 0x1fff + OFF1)        /* fits in 13 bits */
       {
	       wc -= OFF1;
	       s[0] = 0x80 | (wc >> 7);
	       s[1] = 0x80 | (wc & 0x7f);
	       return 2;
       }
       if (wc <= 0x7ffff + OFF2)       /* fits in 19 bits */
       {
	       wc -= OFF2;
	       s[0] = 0xc0 | (wc >> 14);
	       s[1] = 0x80 | ((wc >> 7) & 0x7f);
	       s[2] = 0x80 | (wc & 0x7f);
	       return 3;
       }
       if (wc <= 0x1ffffff + OFF3)     /* fits in 25 bits */
       {
	       wc -= OFF3;
	       s[0] = 0xe0 | (wc >> 21);
	       s[1] = 0x80 | ((wc >> 14) & 0x7f);
	       s[2] = 0x80 | ((wc >> 7) & 0x7f);
	       s[3] = 0x80 | (wc & 0x7f);
	       return 4;
       }
#if !defined(wchar_t_is_signed) || defined(wchar_t_is_more_than_32_bits)
       if (wc > 0x7fffffff)
	       goto bad;
#endif
       wc -= OFF4;
       s[0] = 0xf0 | (wc >> 28);
       s[1] = 0x80 | ((wc >> 21) & 0x7f);
       s[2] = 0x80 | ((wc >> 14) & 0x7f);
       s[3] = 0x80 | ((wc >> 7) & 0x7f);
       s[4] = 0x80 | (wc & 0x7f);
       return 5;
bad:;
       errno = EILSEQ;
       return -1;
}

int mbtowc(wchar_t *p, const char *s, size_t n)
{
       unsigned char *uc;      /* so that all bytes are nonnegative */

       if ((uc = (unsigned char *)s) == 0)
	       return 0;               /* no shift states */
       if (n == 0)
	       return -1;
       if ((*p = uc[0]) < 0x80)
	       return uc[0] != '\0';   /* return 0 for '\0', else 1 */
       if (uc[0] < 0xc0)
       {
	       if (n < 2)
		       return -1;
	       if (uc[1] < 0x80)
		       goto bad;
	       *p &= 0x3f;
	       *p <<= 7;
	       *p |= uc[1] & 0x7f;
	       *p += OFF1;
	       return 2;
       }
       if (uc[0] < 0xe0)
       {
	       if (n < 3)
		       return -1;
	       if (uc[1] < 0x80 || uc[2] < 0x80)
		       goto bad;
	       *p &= 0x1f;
	       *p <<= 14;
	       *p |= (uc[1] & 0x7f) << 7;
	       *p |= uc[2] & 0x7f;
	       *p += OFF2;
	       return 3;
       }
       if (uc[0] < 0xf0)
       {
	       if (n < 4)
		       return -1;
	       if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80)
		       goto bad;
	       *p &= 0x0f;
	       *p <<= 21;
	       *p |= (uc[1] & 0x7f) << 14;
	       *p |= (uc[2] & 0x7f) << 7;
	       *p |= uc[3] & 0x7f;
	       *p += OFF3;
	       return 4;
       }
       if (uc[0] < 0xf8)
       {
	       if (n < 5)
		       return -1;
	       if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80 || uc[4] < 0x80)
		       goto bad;
	       *p &= 0x07;
	       *p <<= 28;
	       *p |= (uc[1] & 0x7f) << 21;
	       *p |= (uc[2] & 0x7f) << 14;
	       *p |= (uc[3] & 0x7f) << 7;
	       *p |= uc[4] & 0x7f;
	       if (((*p += OFF4) & ~(wchar_t)0x7fffffff) == 0)
		       return 5;
       }
bad:;
       errno = EILSEQ;
       return -1;
}

We define 7 byte types:

T0	0xxxxxxx	7 free bits
Tx	10xxxxxx	6 free bits
T1	110xxxxx	5 free bits
T2	1110xxxx	4 free bits
T3	11110xxx	3 free bits
T4	111110xx	2 free bits
T5	111111xx	2 free bits

Encoding is as follows.

>From hex	Thru hex	Sequence		Bits
00000000	0000007f	T0			7
00000080	000007FF	T1 Tx			11
00000800	0000FFFF	T2 Tx Tx		16
00010000	001FFFFF	T3 Tx Tx Tx		21
00200000	03FFFFFF	T4 Tx Tx Tx Tx		26
04000000	FFFFFFFF	T5 Tx Tx Tx Tx Tx	32

Some notes:

1. The 2 byte sequence has 2^11 codes, yet only 2^11-2^7
are allowed. The codes in the range 0-7f are illegal.
I think this is preferable to a pile of magic additive
constants for no real benefit. Similar comment applies
to all of the longer sequences.

2. The 4, 5, and 6 byte sequences are only there for
political reasons. I would prefer to delete these.

3. The 6 byte sequence covers 32 bits, the FSS-UTF
proposal only covers 31.

4. All of the sequences synchronize on any byte that is
not a Tx byte.
```

gha_language: CSS


text:
OpenLS Geocode request parser
=============================

This utility parses OpenLS geocode request xml files into JavaScript Objects.

Usage
-----
Include the openLSParser in your script and pass a Geocoderesponse to it.

```javascript
var openLSParser = require("openls-geocode-parser");

openLSparser(
    '<xls:GeocodeResponse xmlns:xls="http://www.opengis.net/xls" xmlns:gml="http://www.opengis.net/gml"> ... </xls:GeocodeResponse>',
    function onSuccess(geocodeResponse) {
        console.log(geocodeResponse);
    },
    function onFail() {
        console.log('Something went wrong!');
    }
);
```

The GeocodeResponse is categorized into different 'depths':
* Country
* CountrySubdivision
* Municipality
* MunicipalitySubdivision
* Street
* Building

A fully featured GeocodedAddress has the following structure:

```javascript
geocodeResponse = {
    Building?: [
            {
            Country: string,
            Depth: string (= Building)
            Place: {
                CountrySubdivision?: string,
                Municipality?: string,
                MunicipalitySubdivision?: string
            },
            Point: {
                srsName: string,
                pos: [number, number]
            },
            PostalCode?: string,
            StreetAddress? {
                Building?: {
                    number: number,
                    subdivision?: string
                },
                Street: string
            }
        },
        {
        ...
        },
        ...
    ],
    Street? [
        ...
    ],
    ...
}
```

repository: geoloep/openls-geocode-parser

repo_name: geoloep/openls-geocode-parser


text:
fork from: <https://github.com/uber-go/zap> v1.12.0

Do not set `time.Now` for low level logs.

8x faster than origin zap when you emit huge number of low level logs.
(such as you set log level to INFO then emit DEBUG logs)

![benchmark](https://s3.laisky.com/uploads/2019/02/zap_benchmark.jpeg)

Usage: Replace `"github.com/uber-go/zap"` to `"github.com/Laisky/zap"`.

## New Features

### Hook with fields

New hook `HooksWithFields` is: `func(e zapcore.Entry, fs []zapcore.Field) (err error)`

Example:

* <https://github.com/Laisky/go-utils/blob/fc5d8c9f5e419e64d4779758f6666dd60cfa6eb4/logger_test.go#L138>
* <https://github.com/Laisky/go-utils/blob/261a79711965d859e6292183b50084e3ab881a12/logger.go#L312>

repository: Laisky/zap

gha_language: Go

repo_name: Laisky/zap


text:
---
layout: post
title: Document classification with K-means
---

## An example of job advertisement unsupervised classification using K-means.

*Keywords*: Information retrieval, clustering, recommendations, Tf-IDF, classification

Imagine a user reading a book description, reading job advertisings, or looking at images of houses. We would like to recommend similar books, jobs or houses. Formally, we want to have a structured representation of our data, where we can easily navigate the feature space and find neighbouring points to be used as suggestions.

If you are familiar with text represantation and K-means, and are more interested in the [job adverstiment classification with k-means](#JobExample), jump directly to the [example](#JobExample).

## Clustering and unsupervised classification

The goal of clustering is to discover groups of data that share similar features. For example, you want to find job descriptions that are similar to a description you already read. The job classification labels may not be available or may be to broad (scientist, manager, etc), and therefore useless when you want to find similar jobs. We want to structure the data (job descriptions) in our database, so that we can suggest other jobs. Moreover, in the presence of feedback, we can use it to learn preferences.

Looking for similar features in a dataset can be done with KD-Trees or K-nearest neighbours, for example. Clustering can be done with K-means, LDA, among others. I will cover only one deterministic clustering technique (K-means ) and one probabilistic clustering technique (LDA).

### Text representation  ( a little bit of NLP )

I will not go into details of text representation or bag of words, but will only briefly highlight what seems essential to understand the features we will cluster. For the text representation we will use **TF - IDF **(Term frequency - inverse document frequency) to extract features from each text $$d_i$$ in our database.

TF-IDF is a bag-of-words representation, with smart scalings for each word. The key concepts here are:

- The **vocabulary**  is the set of unique (1,2,..,n)-grams appearing in the corpus (collection of all texts). Let $$N$$ denote the size of the vocabulary. Each entry represents an n-gram.

- The occurrences of each vocabulary element in article $$d_i$$ is the **term frequency (TF)**. For example,  consider we have a vocabulary of $$N$$ words, and article  $$d_i$$ = 'Row row row your boat gently down the stream'.  If all the words in $$d_i$$ are present in the vocabulary, the term frequency vector $$d_i$$ would be a vector of size $$N$$, with 7 non-zero entries.  If there are $$L$$ documents in the corpus, the feature representation is a sparse matrix $$X$$ of dimension $$L \times N$$.
- The **inverse document frequency (IDF)** is a scaling factor applied to each entry in the TF vector. The goal is to down-weight words that appear many times in all documents since those words will not help perform a good classification. For example, all the stop-words in english ( this, that, in, the, ...) , appear very often in any type of text, and are generally uninformative of the context.  The IDF is defined as:

$$
IDF  =  \log \frac{ \# documents}{1 + \text{ #documents  using  that   word}}.
$$

-  It should now be intuitive that using **TF-IDF = TF\*IDF** is a good feature representation. There are several variations:
  - Normaiizlng TF-IDF to make each representation independent of the length of the document.
  - Expanding the vocabulary to consider not only single words but pairs of consecutive words. This is often referred to as bi-gram bag of words representation. For example, 2-grams (bigrams) are useful to distinguish between occurrences of "applied mathematician" and "pure mathematician", or "not good" and "very good". Looking for n-grams can help understand the text. In my example, I will be using 1,2,3-grams to create the vocabulary.

  -  In Python, the *scikit-learn* package has bag-of-words feature extraction methods, including TF-IDF: **sklearn.feature_extraction.text.TfidfVectorizer**. This comes with various options, including $$n-gram$$ range, tokenization, stop-word removal, accent removal, normalisation type (l1,l2,none), maximum features, among others, and provides as output a **sparse matrix representation**.

# K means:

K-means is a clustering algorithm that assigns a cluster label $$l_j$$ to each document $$d_i$$. This labelling is known as a hard assignment, as each document belongs to only one label $$j$$.

Each cluster is characterised by :

- a centroid $$c_i$$

- the shape of each cluster in the feature space (The vanilla K-means, will assume all clusters are symmetrical in all dimensions).

Denote $$z_j$$ the cluster labels, $$c_j$$ the cluster centres, and $$x_i$$ the observations.

With clustering, the objective is to minimize the distance to the cluster centers:

$$
\phi =  \sum_{j=1}^k \sum_{x_i \in C( z_j)} d(x_i, c_j)
$$

**Algorithm**:

1. Initialize cluster centres.

   $$ \mu_1,…,\mu_k$$.

2. While not converged:

   1. Assign each observation $$x_i$$ to one cluster, $$z$$:

      	$$z_j = \arg min_j\ \  d(c_j, x_i) $$, where  $$d(,)$$ is a distance function, i.e: $$l_2$$ norm.

   2. Update the cluster centers with the observations assigned in previous step.

      	$$ \mu_j = \frac{1}{n_j} \sum_{x_i \in C( z_j)} x_i $$

Because the k-means objective function is not convex, we are never guaranteed to find the global optimum. K-means will converge to a local optimum and, as any iterative optimization of a non-convex  function, the value we converge to will depend on the initial values of the cluster centres. This gives rise to **k-means++**, which is the same as k-means, but with a smart cluster initialisation.

The algorithm for cluster center initialisation is as follows:

1. Choose the first cluster center randomly.

2. While the number of cluster centres is less than then number of clusters:

   1. for each  $$x_i$$,  for each cluster center $$c_j$$,

          compute $$d(x_i,c_j)$$, keep the distance to the nearest cluster centre $$b_i$$

                 if $$d(x_i,c_j)<b_i$$ then $$b_i = d(x_i,c_j) $$

   2. Choose a new cluster center with probability proportional to $$b_i^2$$, to favour choosing a cluster center away from other clusters.

**How many clusters do we need?**

Note that until now we have assumed that the number of clusters $$k$$ is fixed. In reality, we do not know how many cluster centres are needed to best represent our data. With more centres, $$\phi$$ in equation (1) is lower, but will not generalise well. When plotting the misfit $$\phi \ Vs.  k $$,  it will typically resemble an L-curve. The best number of clusters can usually be found in the elbow of the L-curve.

#  Example : Job advertisement clustering

If you have ever looked for jobs, you will know that keyword search is clearly not enough to make an efficient search. For example, if you search for jobs as "data scientist", you will find that the focus varies with financial applications, health related, o marketing and retail stores, in research institutions, etc.  Although you can try to refine your keyword search, it is time consuming to open and close job offerings when you realise they don't have the focus you're interested in.

I decided to cluster the job advertisements, and depending on the most important features of each cluster, decide which job offers are more aligned with my interests. It straight forward, but it can save you a lot of time and make you more efficient in your job search. The Jupyter notebook, that runs on Python3, can be found [here](!https://raw.githubusercontent.com/whatisAI/Classification_Adds/master/Indeed_JobClassificationKmeans.ipynb). The outline is as follows:

* [Step 1](#step1): Query the job advertisement aggregator, such as Indeed, for the jobs you are interested in, in a specific city, sorted by date (most recent first). Read all the job advertisements and create a corpus.
* [Step 2](#step2):  Do a little pre-processing: tokenise, remove stop-words and words in the indeed webpage by default, use TF-IDF to create the feature representation.
* [Step 3](#step3):  Use a k-means algorithm.
* [Step 4](#step4):  Look at the most important features in each cluster.
* Step 5: Looking at the features in each cluster, retain only job offers in the cluster where you feel identified! Done!

## Step 1: Gather job advertisements from Indeed, and create a corpus.

Query the job advertisement aggregator, such as Indeed, for the jobs you are interested in, in a specific city, sorted by date (most recent first). Read all the job advertisements and create a corpus.

For the first step, I used what was done in [this great notebook](https://jessesw.com/Data-Science-Skills/ ), and only did some minor tweaks to sort by date. The main parts are to read contents from a website:

```python
site = urllib.request.urlopen(website).read()
```

and use the package *BeautifulSoup* to extract html from the site:

```python
soup_obj = BeautifulSoup(site, "lxml")
```

##  Step 2: Feature extraction

Do a little pre-processing: tokenise, remove stop-words and words in the indeed webpage by default, use TF-IDF to create the feature representation.

```python
def create_features(corpus, nmin=1,nmax=3,nfeat=5000):
    vectorizer = TfidfVectorizer(ngram_range=(nmin,nmax), min_df = 1,
                                 sublinear_tf = True, max_features = nfeat)
    job_features = vectorizer.fit_transform(corpus)
    return vectorizer, job_features # End of the function
```

##  Step 3: Use a k-means algorithm.

K-means clustering call.  Specify the k-means++ initialization, number of cluster and maximum number of iterations.  For large datasets, and to make k-means scalable, Clustering can be done in batches. The two methods will not converge to the same results. In this case, because we do not have a large dataset, we do not need to use batches.

```python
def do_clustering(some_features,true_k=2, do_svd=0):
    kmeans_minibatch = 0
    if kmeans_minibatch:
        km = MiniBatchKMeans(n_clusters=true_k, init='k-means++', n_init=1,
                             init_size=1000, batch_size=1000, verbose=1)
    else:
        km = KMeans(n_clusters=true_k, init='k-means++', max_iter=100, n_init=1,
                    verbose=1)

    print("Clustering sparse data with %s" % km)
    km.fit(X)
    return km
```

##  Step 4: Look at the most important features in each cluster.

For each cluster center, which can be accessed in *km.__dict__['cluster_centers_']*, we can look at the features that have the highest weights:

```python
def importance_features(feat_names, km, perc=99.9):
    res=km.__dict__
    for iclass in set(km.labels_):
        print('\n****** \nImportant features for class ',iclass,'\n')
        for ii,iv in enumerate(res['cluster_centers_'][iclass]):
            if iv > np.percentile(res['cluster_centers_'][iclass],perc)  :
                print('{0:<30s}{1}'.format(feat_names[ii],iv))
```

For example, searching for jobs as **data scientist** the clusters, have the following features for each class:

```python
******
Important features for class  0
analyst
quantitative
quantitative analyst
research analyst
symbasync

******
Important features for class  1
data
data scientist
learning
machine learning
scientist

******
Important features for class  2
analytics
business
data
learning
machine learning
******
Important features for class  3
customers
data scientist
pm
scale
shopping
******
Important features for class  4
development
employment
health
healthcare
support
******
Important features for class  5
developer
engineer
insurance
product
software
```

Which can be summarised as:

 **Cluster 0** : analyst, quant

**Cluster 1:**  data scientist, machine learning

**Cluster 2:** analytics, business

**Cluster 3:** customer, data science, shopping

**Cluster 4:** health, development

**Cluster 5:** developer, engineer, insurance

## Final Comments and further improvements:

- The number of clusters has been arbitrarily chosen here. Feel free to increase or decrease them, according to the level of granularity you are looking for. When plotting the misfit $$\phi \ Vs.  k $$,  it will typically resemble an L-curve. The $k$ where the curve bends is usually a good tradeoff between reducing $$\phi$$ and keeping the number of clusters small.

- Remember that every time you run k-means you will get a different clustering result.

- This classification is far from perfect. As long as removing stop words, I removed some common names of recruiters, or words that appear in job offerings from some groups, but that remain un-informative. For example, some job offerings explain benefits, other don't. Either way, this word is not important in our classification, so I remove it. A lot more can be done in this sense.

- K-means clustering assumes all clusters are symetrical in all dimensions (all features have the same spread). This is not necessarily true, or a good approximation. In the next post we will see how to improve on this.

- A **probabilistic labelling** makes more sense in this example. Some job offerings may intersect two categories. This will be the topic of the next post.


text:
# Flight Notes
An application for logging flight information during drone operations.

Use `npm run dev` for to start development server.

Project boilerplate from:

#bootstrap create-react-app and electron

https://medium.freecodecamp.com/building-an-electron-application-with-create-react-app-97945861647c#.ze6c9qin1


text:
Lightswitch Rave - a simple, fast web frontend to your music library for Linux
==============================================================================

Lightswitch Rave is a way to easily share a music collection over the
world wide web.  It provides a dead-simple web application enabling
authorized users to browse your music by artist or album.  Songs are
played using the 'html5' audio tag.  This means that support for
mp3/aac/ogg audio is dependent on your browser.  Firefox doesn't come
with the codecs for mp3 or aac, so unless your music library is all
ogg, use Chrome

I originally designed it so that I could access the music I had on my
desktop at home from my laptop at work, and at this point it performs
the task admirably.

![Lightswitch Rave in chrome](https://github.com/bpowers/lightswitchrave/raw/master/doc/cnote_in_use.png "Lightswitch Rave in Chrome")

Lightswitch Rave uses inotify to watch for new/changed files, so it is
currently linux only.  kqueue provides similar functionality on
Mac/BSD, so abstracting this out would be possible, but I don't have
plans to do that right now.

highlights
----------

- A sweet login page.

status
------

It is somewhat a work in progress.  I had a previous project
[cnote](https://github.com/bpowers/cnote/) which provided the
API/sqlite indexing of my music library.  In order to easily add new
features like authentication and uploading, I've switched to Go.
However, I haven't finished the music indexing part, so lightswitch
proxies /api to cnote.  With this said, the two of them running
together work excellently.

license
-------

Lightswitch Rave is offered under the MIT license, see COPYING for details.

repository: bpowers/lightswitchrave

repo_name: bpowers/lightswitchrave


text:
# Node configuration

To start atomic swap process, Zeon and Bitcoin Testnet nodes should be configured in right way.
This page contains configuration manual for nodes.
This configuration is applicable for both cryptocurrencies.

#### Testnet

First of all, **testnet** should be activated. Add `testnet=1` to conf file both of nodes.
Or type it into command line while starting the nodes, e.g. `bitcoind -testnet`

#### RPC credentials

Add RPC credentials to conf files like this:

```
rpcuser=my_user_name
rpcpassword=my_awesome_password
```

##### or

Type it to command line like this:

`zeond ... -rpcuser=my_user_name -rpcpassword=my_awesome_password`

Where `my_user_name` and `my_awesome_password` are your own username and password.

#### ZMQ

Add ZMQ host and port number for notifications from node in file:

```
zmqpubhashblock=tcp://<IP_ADDRESS>:dddd
zmqpubhashtx=tcp://<IP_ADDRESS>:dddd
```

##### or

Command line:

`zeond ... -zmqpubhashblock=tcp://<IP_ADDRESS>:dddd -zmqpubhashtx=tcp://<IP_ADDRESS>:dddd`

Where `dddd` is a port number (Numbers from 1024 to 65535 except numbers
from [this table](https://en.wikipedia.org/wiki/List_of_TCP_and_UDP_port_numbers)).

#### Starting as a daemon

It's optional item. Enable it if you want start node as a daemon.

```
daemon=1
```

#### Conclusion

If all configurations are set your conf file should be similar to this:

```
daemon=1
testnet=1
rpcuser=my_user_name
rpcpassword=my_awesome_password
zmqpubhashblock=tcp://<IP_ADDRESS>:dddd
zmqpubhashtx=tcp://<IP_ADDRESS>:dddd
```

Or command line like this:

```
zeond  -rpcuser=my_user_name -rpcpassword=my_awesome_password \
-zmqpubhashblock=tcp://<IP_ADDRESS>:dddd -zmqpubhashtx=tcp://<IP_ADDRESS>:dddd
```


text:
# System Integrity Verificator
A simple console application, that ensures the integrity of the system files on disk. For Windows only.

### Standard usage instructional:
- [Download the latest release](https://github.com/DevilXD/System_Integrity_Verificator/releases/) and run it as administrator
- Choose one of the 1-3 options (1st recommended)
- Wait for it to complete
- Restart your PC if prompted
- Run the utility again
- Choose the 4th option (SFC check)
- Wait for it to complete
- Restart your PC if prompted (might not prompt you if everything was intact)
- Optional: Choose the 5th option

### Manual instructions (for advanced users):
- Make sure all non-important applications are closed, and all your important work saved
- Open up `cmd` as administrator
- Assuming the `C:` partition is where you have your system installed, run `chkdsk C: /f`. Substitute `C:` for any other partition letter, if your system would be installed elsewhere. The command might prompt you for a check on the next computer restart, shortly after running it. If that would happen, **agree** to it, then restart your PC. __Make sure to not press any buttons during boot up to not skip the check.__
- Find out on which partition you have Paladins installed on. Usually it's either the same as system partition (`C:`), or something like a data partition (`D:`, `E:`, etc.). __If this partition is the same as the system partition, you can skip this step entirely.__ Otherwise, run `chkdsk _: /f /x`, where `_` is the partition letter of where you have Paladins installed on. (example: `chkdsk D: /f /x`, for an installation on `D:`). Wait for it to complete - this one should continue without prompting for restart. If you'd be unsure which partition you have Paladins installed on, it's safe to run this command on every partition you'd have in the system.
- After all partition checking has completed, restart your PC
- Once the computer reboots, open up cmd as administrator again - run `sfc /scannow`. This will verify the integrity of all important system files, and restore those that might've been removed as corrupted during the previous check. Restart your PC if prompted (usually not necessary if all files have been verified successfully, if not, it'll prompt you for restart itself).

### Manual build instructions (for advanced users):
- Install Python 3.8+ (may work on lower versions too)
- Run `pip install -r requirements.txt`
- Run `build.bat` - the built exe can be found in the `/dist` folder


text:
# sway-cwd

> WIP! This was literally written in 15min to scratch my own itch. I'm sure it
> can be improved, use at own risk. It needs tests too.

This is a simple tool to get the current working directory in
[sway](https://swaywm.org/). The idea is that the current working dir can be
passed to a new terminal instance, so it opens in the same directory.

For example, is using [kitty](https://sw.kovidgoyal.net/kitty/), add this to
`~/.config/sway/config`:

```
# Start a terminal in same directory
bindsym $mod+Return exec kitty -d "$(sway-cwd)"
```

Note that `sway-cmd` must be on the `$PATH`, which won't include any additions
set by your shell. You could place the binary in `/usr/local/bin` or include
the full path:

```
bindsym $mod+Return exec kitty -d "$(/home/akupila/go/bin/sway-cwd)"
```

The inspiration came from
[here](https://github.com/swaywm/sway/issues/1973#issuecomment-419504059).
Unlike the shell script, this the `sway-cwd` binary is statically linked and
thus has no external dependencies, such as `jq`.

repository: akupila/sway-cwd

repo_name: akupila/sway-cwd