Patcher and Expander Internals

Basically “patching” can be divided in two main processes: choosing a patch seed and forming the patch itself.

Choosing the patch seed, which we call a pivot cell, involves collecting the probabilities of all cells were that transition is possible, sorting them by their probabilities, and them keeping only the subset of cells with the highest probabilities. We call that “pruning”. The number of cells to keep, after the “pruning” phase is completed, is calculated multiplying the number of expected transitions by the prune factor parameter. The resulting cells are the pivot candidate cells.

To choose a new seed, one cell is randomly selected from the pool of pivot candidates. Then, a rejection test is applied to see if a cell will be accepted or not. If the cells passes the test, the cell is used as a base to form a new patch. Otherwise the process continues until a pivot cell is found.

Once a pivot cell is found, the patch formation process starts and the pivot neighbors are selected using a window whose number of lines and columns are defined as a patcher parameter. The window is centered on the pivot cell and all neighbors where the transitions are possible are collected and placed on a patch formation pool. A cell is drawn from that pool using the same approach used to select a pivot cell, but the pools are different. If that cell passes the rejection test, the cell is used as part of the patch and its neighbors are collected and placed in the same patch formation pool. If a cell is already in that pool, its probability is increased (or decreased) using the isometry as a factor. Then, a new cell is drawn from the pool, the rejection test is applied, its neighbors are collected and the process continues until the number of cells expected for that patch is reached. BTW, the number of cells in a patch is chosen as random number from a normal distribution defined using the mean and variance patch sizes.