#!/bin/sh
#description: find dominant colors in images
#usage: dcolors image-file

#example: dcolors black-and-white-image.png
#output 3 dominant colors in rgb format
#191,191,191
#80,80,80
#185,185,185

#original python implementation
#http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/

VERSION="2026.09.12-23:15"

PROGNAME="$(expr "${0}" : '.*/\([^/]*\)')"

_usage() {
    printf "Usage: %s\\n" "${PROGNAME} [options] image-file ..."
    printf "%s\\n" "Find dominant colors in images."
    printf "\\n"
    printf "%s\\n" "  -d, --deviation   deviation, higher value, faster computation, default 1"
    printf "%s\\n" "  -k, --kmeans      output colors, default 3"
    printf "%s\\n" "  -r, --resize      resize before procedure, lower value, faster computation, default 25x25"
    printf "%s\\n" "  -f, --format      output format [rgb|hex], default rgb"
    printf "%s\\n" "  -h, --help        show this help message and exit"
}

_die() {
    [ -z "${1}" ] || printf "%s\\n" "${*}" >&2
    _usage >&2; exit 1
}

_is_int() {
    #look for an integer, returns 0 on success, 1 otherwise
    #http://www.unix.com/shell-programming-and-scripting/172070-help-scripting-command.html
    case "${1}" in
        *[!0-9]*|"") return 1 ;;
    esac
}

_false() {
    return 1
}

_kmeans_awk() {
    awk_prog='
    function _euclidean(p1,p2) {
        split(p1, p1_coordinates, ",")
        split(p2, p2_coordinates, ",")
        _euclidean__distance=0
        for (coordinate=1; coordinate <= 3; coordinate++) {
                        #skip alpha channels
            remains=p1_coordinates[coordinate] - p2_coordinates[coordinate]
            _euclidean__distance+=remains * remains
            #_euclidean__distance+=remains^2 #doesnt work on ubuntu busybox awk
        }
        return _euclidean__distance
    }

    function _calculate_center(plist) {
        split(plist, plist_array)
        count=0; sumX=0; sumY=0; sumZ=0;
        for (point in plist_array) {
            split(plist_array[point], coordinates, ",")
            for (coordinate in coordinates) {
                if (coordinate == 1) {
                    split(coordinates[coordinate], composed_coordinate, ":")
                    times=composed_coordinate[1]
                    coordinateX=composed_coordinate[2]
                    count+=times
                    sumX+=coordinateX*times
                }
                else if (coordinate == 2) sumY+=coordinates[coordinate] * times
                else if (coordinate == 3) sumZ+=coordinates[coordinate] * times
            }
        }

        //avoid division by zero
        if(count) {
            sumX=int(sumX/count)
            sumY=int(sumY/count)
            sumZ=int(sumZ/count)
        }
        return sumX "," sumY "," sumZ
    }

    function _max(value1, value2) {
        if (value1 > value2) return value1
        else return value2
    }

    function _randint(n) { return 1 + int(rand() * n) }

    { points_times=points_times $0 " " }

    END {
        #print points_times
        points=points_times
        #remove time field to improve computation performance
        gsub(/[0-9]?[0-9]?[0-9]?[0-9]?[0-9]?[0-9]?:/,"", points)

        points_times_array_len=split(points_times, points_times_array)
        split(points, points_array)

        #get random sample
        srand(); for (i = 1; i <= kmeans; i++) {
            clusters_array[i]=points_array[_randint(points_times_array_len)]
            #print clusters_array[i]
        }

        while (1) {
            for (p in points_array) {
                distance=0; for (i = 1; i<= kmeans; i++) {
                    distance = _euclidean(points_array[p], clusters_array[i])
                    if (i == 1) { smallest_distance=distance; idx=1 }
                    else if (distance < smallest_distance) {
                        smallest_distance=distance
                        idx=i
                    }
                    #print points_array[p] " " clusters_array[i] " " distance " " smallest_distance
                }
                plists[idx]=plists[idx] points_times_array[p] " "
                #print idx
                #print "============"
            }

            #print plists[1]
            #print "======================"
            #print plists[2]
            #print "======================"
            #print plists[3]
            #print "======================"
            #print plists[4]
            #print "======================"

            diff = 0; for (item in clusters_array) old_clusters_array[item]=clusters_array[item]
            for (c in clusters_array) {
                clusters_array[c] = _calculate_center(plists[c])
                diff = _max(diff, _euclidean(old_clusters_array[c], clusters_array[c]))
            }

            #if (1) break
            if (diff < deviation) {
                for (c in clusters_array) {
                    if (format == "rgb") print clusters_array[c]
                    else {
                        split(clusters_array[c], cluster, ",")
                        printf "#"
                        for (coordinate in cluster) printf "%02X", cluster[coordinate]
                        print ""
                    }
                }
                break
            }
        }
    }'

    for image; do
        if [ -f "${image}" ]; then
            image_points_times="$(convert "${image}" -resize "${resize}" \
                -colorspace RGB -depth 8 -format %c histogram:info:- |   \
                ${awk_bin} \
                'NF {sub(/\).*/,"");sub(/\(/,"");gsub(/ /,"");print $0}')"

            printf "%s" "${image_points_times}" | ${awk_bin}      \
                -v kmeans="${kmeans}" -v deviation="${deviation}" \
                -v format="${format}" "${awk_prog}"
        else
            printf "%s\\n" "Warning: '${image}' doesn't exist, skipping..." >&2
            _false
        fi
    done
}

_check_deps() {
    if command -v "awk" >/dev/null 2>&1; then
        awk_bin="awk"
    elif busybox awk 1 /dev/null >/dev/null 2>&1; then
        awk_bin="busybox awk"
    else
        printf "%s\\n" "install 'awk' to run this program" >&2
        exit 1
    fi

    if ! command -v "convert" >/dev/null 2>&1; then
        printf "%s\\n" "install 'convert' to run this program" >&2
        exit 1
    fi
}

_sanitize_parameters(){
    if [ -z "${kmeans}" ]; then
        kmeans="3"
    else
        _is_int "${kmeans}" || _die "Option -k|--kmeans requires a number parameter '${kmeans}'"
    fi

    if [ -z "${deviation}" ]; then
        deviation="1"
    else
        _is_int "${deviation}" || _die "Option -d|--deviation requires a number parameter '${deviation}'"
    fi

    if [ -z "${format}" ]; then
        format="rgb"
    else
        case "${format}" in
            rgb|hex) : ;;
            *) _die "Output valid formats are rgb|hex: '${format}'" ;;
        esac
    fi

    [ -z "${resize}" ] && resize="25x25"
}

_update() { #replace this file with the one in the repo, when that one is newer
    _u__current_file="$(cd "$(dirname "${0}")" && pwd)/${PROGNAME}"

    #a link into a checkout is not ours to overwrite: mv would put a regular
    #file where the link was and quietly detach it from the repo that owns it,
    #leaving a copy nobody updates again
    if [ -L "${_u__current_file}" ]; then
        _u__target="$(readlink "${_u__current_file}" 2>/dev/null)"
        printf "%s\\n" "ERROR: ${_u__current_file} is a link to ${_u__target:-somewhere else}" >&2
        #naming shundle here is duplication, and it is worth it: this branch is
        #only ever reached when the file already is a link inside a bundle, so
        #shundle is there by definition. Anyone who downloaded this script on
        #its own never gets here, and never reads about a tool they lack
        case "${_u__target}" in
            "${SHUNDLE_HOME:-/dev/null}"/bundle/*|*/.shundle/bundle/*)
                printf "%s\\n" "INFO : shundle update ${PROGNAME}" >&2 ;;
            *)  printf "%s\\n" "INFO : update the file it points at, replacing the link would orphan it" >&2 ;;
        esac
        return 1
    fi

    _u__current_version_long="$(awk -F\" \
        '/VERSION=/{print $2;exit}' "${_u__current_file}" 2>/dev/null)"
    _u__current_version="$(printf "%s\\n" "${_u__current_version_long}" | \
        awk '{gsub(/[\.:]/,"");gsub(/-/,"");print;exit}' 2>/dev/null)"
    [ -z "${_u__current_version}" ] && printf "%s\\n%s\\n%s\\n"           \
        "ERROR: Failed to detect current version, please update manually" \
        "${PROGNAME}         = ${_u__current_file}"                       \
        "${PROGNAME} version = ${_u__current_version}" >&2 && return 1

    command -v "wget" >/dev/null 2>&1 || command -v "curl" >/dev/null 2>&1 || \
        { printf "%s\\n" "ERROR: Install either 'wget' or 'curl' to upgrade" >&2; return 1; }

    _u__url="https://raw.githubusercontent.com/javier-lopez/learn/master/sh/tools/${PROGNAME}"

    #it never lands in /tmp. A predictable name in a world writable directory
    #is a file somebody else can turn into a link before we write through it,
    #and this one gets chmod +x and becomes the program. It is held in a
    #variable, and only written next to the file it is going to replace, where
    #the rename is atomic because it never crosses a filesystem. The
    #certificate is checked and curl is told to fail on a 404 instead of
    #handing over the error page. stderr is left alone so you read why it failed
    _u__new="$(wget -q -O- "${_u__url}" || curl -fsS "${_u__url}")" || { \
        printf "%s\\n" \
        "ERROR: Failed to fetch update, please try later or update manually" >&2
        return 1; }

    #and what came down has to look like the program, not like a web page
    case "${_u__new}" in
        "#!"*) ;;
        *) printf "%s\\n" "ERROR: what came down is not a script, not touching ${PROGNAME}" >&2
           return 1 ;;
    esac

    _u__update_version_long="$(printf "%s\\n" "${_u__new}" | awk -F\" \
        '/VERSION=/{print $2;exit}' 2>/dev/null)"
    _u__update_version="$(printf "%s" "${_u__update_version_long}" | awk \
        '{gsub(/[\.:]/,"");gsub(/-/,"");print;exit}' 2>/dev/null)"
    #no VERSION upstream is not the same as being current, and saying
    #up-to-date there is the most expensive kind of lie: the one you believe
    [ -z "${_u__update_version}" ] && printf "%s\\n" \
        "ERROR: the copy upstream carries no VERSION, cannot tell if it is newer" >&2 && return 1

    if [ "${_u__current_version}" -lt "${_u__update_version}" ]; then
        printf "%s %s\\n" "Updating from version" \
            "${_u__current_version_long} to ${_u__update_version_long} ..."

        #checked again, right here: between the check at the top and this line
        #the file could have become a link, and this is the moment it matters
        [ -L "${_u__current_file}" ] && printf "%s\\n" \
            "ERROR: ${_u__current_file} became a link, not replacing it" >&2 && return 1

        _u__tmpfile="${_u__current_file}.update"
        if printf "%s\\n" "${_u__new}" > "${_u__tmpfile}" 2>/dev/null; then
            chmod +x "${_u__tmpfile}"
            mv -f "${_u__tmpfile}" "${_u__current_file}" 2>/dev/null || { \
                rm -f "${_u__tmpfile}"
                printf "%s\\n" "ERROR: cannot replace ${_u__current_file}" >&2
                return 1; }
        else
            #no write permission in that directory, so the file has to be
            #staged somewhere we do own, and mktemp is what makes that name
            #unguessable and the file ours alone
            printf "%s\\n" "ERROR: no write permissions on ${_u__current_file}" >&2
            printf "%s\\n" "INFO : trying with sudo ..." >&2
            command -v "sudo" >/dev/null 2>&1 || { \
                printf "%s\\n" "ERROR: sudo isn't available, exiting ..." >&2; return 1; }
            _u__tmpfile="$(mktemp "${TMPDIR:-/tmp}/${PROGNAME}.XXXXXX")" || return 1
            printf "%s\\n" "${_u__new}" > "${_u__tmpfile}" || { \
                rm -f "${_u__tmpfile}"; return 1; }
            chmod +x "${_u__tmpfile}"
            sudo mv "${_u__tmpfile}" "${_u__current_file}" || { \
                rm -f "${_u__tmpfile}"; return 1; }
        fi
        printf "%s\\n" "${PROGNAME} is up-to-date (${_u__update_version_long})"
        return 0
    fi
    printf "%s\\n" "${PROGNAME} is up-to-date (${_u__current_version_long})"
}

if [ ! -t 0 ]; then
    #there is input comming from pipe or file, add to the end of $@
    set -- "${@}" $(cat)
fi

for arg in "${@}"; do #parse options
    case "${arg}" in
        -U|--update)  _update; exit "${?}" ;;
        -v|--version) printf "%s\\n" "${PROGNAME} ${VERSION}"; exit ;;
        -h|--help) _usage && exit ;;
        '-d'|'--deviation')
            if [ "${#}" -gt "1" ]; then
                case "${2}" in
                    -*) _die "Option '${arg}' requires a parameter" ;;
                esac
                shift; deviation="${1}"; [ "${1}" ] && shift
            else
                _die "Option '${arg}' requires a parameter"
            fi ;;
        -d*) deviation="${1#-d}"; shift ;;
        --deviation*) deviation="${1#--deviation}"; shift ;;
        '-k'|'--kmeans')
            if [ "${#}" -gt "1" ]; then
                case "${2}" in
                    -*) _die "Option '${arg}' requires a parameter" ;;
                esac
                shift; kmeans="${1}"; [ "${1}" ] && shift
            else
                _die "Option '${arg}' requires a parameter"
            fi ;;
        -k*) kmeans="${1#-k}"; shift ;;
        --kmeans*) kmeans="${1#--kmeans}"; shift ;;
        '-r'|'--resize')
            if [ "${#}" -gt "1" ]; then
                case "${2}" in
                    -*) _die "Option '${arg}' requires a parameter"
                esac
                shift; resize="${1}"; [ "${1}" ] && shift
            else
                _die "Option '${arg}' requires a parameter"
            fi ;;
        -r*) resize="${1#-r}"; shift ;;
        --resize*) resize="${1#--resize}"; shift ;;
        '-f'|'--format')
            if [ "${#}" -gt "1" ]; then
                case "${2}" in
                    -*) _die "Option '${arg}' requires a parameter"
                esac
                shift; format="${1}"; [ "${1}" ] && shift
            else
                _die "Option '${arg}' requires a parameter"
            fi ;;
        -f*) format="${1#-f}"; shift ;;
        --format*) format="${1#--format}"; shift ;;
        -*) _die "${PROGNAME}: unrecognized option '${arg}'" ;;
    esac
done

_check_deps && _sanitize_parameters && [ "${#}" -eq "0" ] && _die

_kmeans_awk "${@}"