全國電子音樂交流中心

Glitch Sort Pixels!

LOONGINT2019-12-02 13:43:25

Pixelsorting

Based on Openframeworks_0.9.3(C++)

2016/9/10 @Hong Kong




【Description】



像素排序 - FFT數據觸發效果


Tutorial


????首先呢,要普及一下排序的概念,排序是將一串無序的數據通過某個規則進行有序化,例如數組[1,5,7,9,2],按照從大到小的規則排序,就是[9,7,5,2,1],排序算法有很多,例如冒泡、選擇、歸并、快速排序、堆排序等等。但是在P5和OF里,都有內置的sort函數,所以不用我們自己去寫排序算法啦(福利呢)

????那么既然我們可以對數字進行排序,我們也可以對像素進行排序,像素其實就是一個包含rgba/hsb數據的[模塊]。

????當我們拿到一張圖片,這張圖片所包含的像素量就是分辨率的乘積,比如640*480的圖片,就一共包含了307200個像素,那么對這么多數據進行排序,會不會好慢呢?答案是不會,現在的排序算法可以達到O(nlogn)的時間復雜度,也就是說3881500次普通運算就可以排好啦,對于計算機來說,1s可以執行10^8以上的運算(這個數據還是我七八年前學OI的時候的標準),所以完全不用擔心我們的CPU處理效率。


???但是如果我們單純的將所有數據排列好呈現出來,那么其實圖片就被完全的破壞了,因為圖片分為行和列,行和列的圖像數據在排列上都是有意義的。所以換一個角度,我們對每一個行/每一個列進行排序,這個時間復雜度是多少呢!(答對的朋友直接公眾號里發我,答對了有驚喜)。這樣排序之后就會變得可愛多了。

????

????那么我們可以再想,如果我們保留圖中的一些元素,只排序我們想排序的內容,是不是更好看!(咻咻,這就涉及到了一個圖像識別的算法。作為一個設計師,我們肯定不會去跑機器學習那種算法,所以有個叫做Kim Asendorf的可愛coder提供了一種思路:通過設定一個threhold來將每一行/列數據進行分割,我們只處理其中的一部分。


????這個思路其實來自于一種叫做Floodfill的概念,這邊呢Loongint簡單介紹一下Floodfill的原理:Floodfill是一種染色算法,是CV里面比較常見的思路,是用來填充區域的。就好比在一個地方一直倒水,水會往四周滿延開,直到高地阻擋。Flood Fill就是從一個點開始往四周尋找相同的點填充,直到有不同的點為止。這個思路屬于BFS(廣度優先搜索)。


????
假設在(i,j)滴好大一滴紅墨水,然后水開始漫開,向它的上下左右染色,也就是(i-1,j),(i+1,j),(i,j-1),(i,j+1)這四個點.然后在分別再從這四個點開始向周圍染色...直到碰到某種邊界為止。把這個轉化為BFS的思想,就是隊列中初始元素是(i,j),然后把(i,j)擴展狀態,得到(i-1,j),(i+1,j),(i,j-1),(i,j+1)這四個狀態,加入隊列.把(i,j)出列,繼續擴展下一個結點...


????

????那么現在我們的思路又可以更新了!我們提前對圖片進行FloodFill,將圖片進行區塊劃分,我們只對其中的某些區塊進行像素排序(行/列形式)。最后這種思路的代碼非常歡迎大家來實現一下,實現成功的小伙伴,私信給[email protected],將獲得Loongint送出的小禮物喲!

????(第三種思路的OF代碼請點閱讀原文)



尤龍(Loongint You)

HCI | Media Designer

www.loongint.com

Hong Kong

loongint.you@outlook.com



体彩19051627