Tag: python

kmeans1d: Globally Optimal Efficient 1D k‑means Clustering

Post author By Daniel
Post date July 4, 2019
No Comments on kmeans1d: Globally Optimal Efficient 1D k‑means Clustering

I implemented kmeans1d, a Python library for performing k-means clustering on 1D data, based on the algorithm from Xiaolin (1991), as presented by Grønlund et al. (2017, Section 2.2).

Globally optimal k-means clustering is NP-hard for multi-dimensional data. Lloyd’s algorithm is a popular approach for finding a locally optimal solution. For 1-dimensional data, there are polynomial time algorithms.

kmeans1d contains an O(kn + n log n) dynamic programming algorithm for finding the globally optimal k clusters for n 1D data points. The code is written in C++—for faster execution than a pure Python implementation—and wrapped in Python.

The source code is available on GitHub:
https://github.com/dstein64/kmeans1d

Tags c++, k-means clustering, machine learning, python

Uncategorized

Style Transfer Medley

I used the pastiche style transfer program—discussed in a prior post—to create the video shown above. The content image is a photo I took in Boston in 2015, and the style images were randomly sampled from the test images of the Painter by Numbers Kaggle competition.

The frames used in the video were retained during gradient descent by using pastiche‘s --workspace option.

The Python script for generating the video is on GitHub:
https://gist.github.com/dstein64/5dcc67fa43cc0d13d6d4d544095a1382

Tags neural networks, neural style transfer, pastiche, python

Uncategorized

pastiche

Post author By Daniel
Post date June 16, 2019
No Comments on pastiche

pastiche A literary, artistic, musical, or architectural work that imitates the style of previous work.
―Merriam-Webster dictionary

Update 1/20/2021: The command line usage snippets were updated in accordance with v1.1.0.

I recently implemented pastiche, a PyTorch-based Python program for applying neural style transfer [1]. Given a content image C and a style image S, neural style transfer (NST) synthesizes a new image I that retains the content from C and style from S. This is achieved by iteratively updating I so that relevant properties of its representation within the VGG neural network [3] approach the corresponding properties for C and S.

The library is available on PyPI and can be installed with pip.

$ pip3 install pastiche

The example image above was synthesized by applying the style from Vincent van Gogh’s The Starry Night to a photo I took in Boston in 2015.

Tags neural networks, neural style transfer, pastiche, python, pytorch

Uncategorized

LC4

Post author By Daniel
Post date May 11, 2019
No Comments on LC4

About a year ago I wrote a Python library that implements ElsieFour (LC4) encryption (Alan Kaminsky 2017). LC4 is designed for human-to-human communication, without requiring a computer.

I’ve recently updated the library to include color-coded verbose output that shows the steps of the algorithm. This can be helpful for learning to manually encrypt and decrypt messages. The verbose output is accessible through both the Python API and the command-line interface (using --verbose).