Thiết kế, phân tích và phát triển một thuật toán di truyền tương tác để tạo sinh ảnh dựa theo hướng dẫn đánh giá của con người : Dự án Permutopainter

THIẾT KẾ, PHÂN TÍCH VÀ PHÁT TRIỂN MỘT THUẬT TOÁN DI TRUYỀN TƢƠNG TÁC ĐỂ TẠO SINH ẢNH DỰA THEO HƢỚNG DẪN ĐÁNH GIÁ CỦA CON NGƢỜI : DỰ ÁN PERMUTOPAINTER Đào Thị Duyên Khoa Toán-Tin, Đại học Thăng Long Email: dtduyen90@gmail.com Tóm tắt: Dự án PermutoPainter dựa trên ý tưởng của bộ sưu tập “Arrangement avec le hasard” (Sắp xếp ngẫu nhiên) được triển lãm tại Paris vào tháng 11 năm 2014 của họa sĩ người pháp Bernard Gortais. Bộ sưu tập này giống như việc nghiên cứu thứ tự sắp xếp của 6x4 ô vuông trong một bức tranh bằng cách xoay quay chúng một góc 90o hoặc tráo đổi vị trí giữa các ô cho nhau. Mục đích chính của dự án này là tạo ra những cấu trúc thú vị bằng cách kết hợp ngẫu nhiên 24 ô của bức tranh. Vì với mỗi cách bố trí đường nét (lên, xuống, ngang, dọc), màu sắc và bố cục khác nhau, nó sẽ đem lại cho người xem những cảm xúc khác nhau. Trong bài báo này,chúng tôi sử dụng một số kỹ thuật nhằm trích rút đặc trưng của từng ảnh, sau đó sử dụng thuật toán K-medoids để phân cụm ảnh. Cuối cùng là sử dụng thuật toán rừng ngẫu nhiên kết hợp với sự tương tác của người dùng tạo ra các hình ảnh giống với ý muốn của người dùng. Từ khóa: Giải thuật di truyền, phân cụm, Rừng ngẫu nhiên, Xử lý ảnh, K- Medoids. 1. Mở đầu Hội họa là điều mà chúng ta không nghĩ rằng một chiếc máy tính có thể tạo ra. Bởi nó trừu tượng, biểu cảm, gắn liền với các nền văn hóa, tâm lý học và chủ quan. Còn máy tính thì khách quan, chính xác và chi phối bởi các nguyên tắc toán học. Tuy nhiên, trong thực tế, hội họa và các lĩnh vực nghệ thuật thị giác khác sử dụng rất nhiều toán học như hình học, luật phối cảnh, thuật toán, cái mà máy tính có thể hiểu được để tạo ra những hình ảnh đa dạng, tinh tế giống như người họa sĩ. Một người tiên phong trong lĩnh vực này là họa sĩ Harold Cohen. Ông đã xây dựng một chương trình sáng tạo nghệ thuật sử dụng trí thông mình nhân tạo AARON năm 1973 [1]. Việc sử dụng các thuật toán tiến hóa tương tác như giải thuật di truyền để tạo sinh ảnh đã trở nên khá phổ biến mà nguốn gốc của nó được tìm thấy trong cuốn sách “The Blind Watchmaker” [2] được viết bởi nhà sinh học tiến hóa Richard Dawkins. Sau đó, là các hệ thống được phát triển bởi [3] và [4]. Chúng được xem là các tác phẩm nghệ thuật có ảnh hưởng nhất trong lĩnh vực nghệ thuật thị giác. Trào lưu này đã mở ra một lĩnh vực nghệ thuật mới, đó là “Nghệ thuật tiến hóa” [5]. Trong bài báo này, chúng tôi sẽ trình bày về dự án PermutoPainter được phát triển trong bộ sưu tập “Sắp xếp ngẫu nhiên” của họa sĩ người pháp Bernard Gortais. Nó được triển lãm tại Paris vào tháng 11 năm 2014. Một tác phẩm hội họa (ví dụ như một đường trải dài trên bức tranh như hình 1) được căt ra thành 24 ô vuông bằng nhau rồi lại được ghép lại một cách ngẫu nhiên, hoàn toàn độc lập với ảnh ban đầu. Hình 1- Ví dụ một kiểu sắp xếp Yêu cầu của người dùng là xây dựng một công cụ cho phép khám phá một ý kiến khách quan mang tính nghệ thuật với một số lượng lớn các hoán vị có thể trên một tập không gian (khái niệm không gian ở đây chính là bố cục của một bức ảnh) kết hợp với sự phát hiện những tính chất nổi bật của từng hoán vị, cái được xác định bởi người sử dụng. Đó là lý do chúng tôi đi xây dựng dự án PermutoPainter. Bằng cách phân tích và cài đặt một thuật toán tiến hóa nhằm giúp tìm kiếm và xác định một cách hiệu quả các kết hợp “interesting” từ các mảnh nhỏ của ảnh với sự tương tác của người dùng (Feng & Ting, 2014). Trước tiên, một ảnh được cắt ra thành 6x4 phần bằng nhau, sau đó chúng được chuyển sang dạng nhị phân, tính toán các điểm đặc trưng trên ảnh và biểu diễn các đặc trưng này thành một véctơ mô tả n-chiều. Các véctơ này được phân nhóm vào k-cụm (cluster) bởi thuật toán K-medoids. Những ảnh là trung tâm của mỗi cụm sẽ được hiển thị cho người dùng đánh giá độ thú vị (interest) và định tính của từng ảnh (ví dụ: buồn, vui, tĩnh mịch hay sôi động). Tiếp đến, chúng tôi sử dụng thuật toán rừng ngẫu nhiên để huấn luyện. Thuật toán này thường phù hợp với các bộ dữ liệu có số chiều rất lớn. Cuối cùng, chương trình sẽ tạo sinh ra những ảnh thuộc lớp thuộc tính mà người dùng yêu cầu. Phần còn lại của bài báo được tổ chức như sau: phần 2 mô tả các nghiên cứu, cơ sở lý thuyết liên quan tới đề tài; phần 3 mô tả khái quát về các phương pháp nghiên cứu được áp dụng trong đề tài. Sau đó là kết quả thực nghiệm được trình bày ở phần 4. Cuối cùng là phần 5 kết luận và hướng phát triển 2. Các nghiên cứu liên quan Trong mục này chúng tôi phân tích các cơ sở lý thuyết liên quan tới bài báo. Trước tiên là một ứng dụng tạo sinh ảnh dựa trên giải thuật di truyền của nhóm tác giả người Đài Loan [6]. Tiếp đến, với mục đích giúp người đọc hiểu được cái thú vị trong từng bức tranh, là phần mô tả ngắn gọn về nghệ thuật thị giác, các thành phần tạo nên cảm xúc trong hội họa. Cuối cùng là một số kỹ thuật có thể sử dụng trong việc biểu diễn ảnh. 2.1 Hệ thống EvoEco – một ví dụ về tạo sinh ảnh EvoEco là hệ thống được xây dựng dựa trên nền tảng đa tác tử (multi-agent). Nó gồm hai giai đoạn chính: sinh sản (tạo ra các đối tượng ảnh) và tiến hóa (lựa chọn và làm tiến hóa các nhiễm sắc thể). Một ảnh được biểu diễn như một nhiễm sắc thể với thành phần gồm k tác tử (agent). Các tác tử này sẽ thực hiện việc sơn màu cho bức tranh trong suốt quá trình sống của chúng. Quá trình tiến hóa của EvoEco để tạo sinh ảnh gồm các giai đoạn sau: 1. Xác định ngẫu nhiên màu nền cho mỗi nhiễm sắc thể. 2. Các nhiễm sắc thể được xây dựng nhờ quá trình sơn của các tác tử trong suốt quá trình sống của chúng. 3. Đột biến và lai tạo trên các nhiễm sắc thể vừa tạo ra. Hình 2- Giao diện hệ thống EvoEco và một vài ảnh đã được đánh giá 2.2. Nghệ thuật thị giác và trừu tượng Thuật Nghệ thuật thị giác là nghệ thuật mà chúng ta nhìn thấy, giống như các bức tranh, hình ảnh nó mang lại cảm xúc, trực giác về những gì diễn ra quanh chúng ta hoặc những gì tiềm ẩn bên trong con người, cái mà không thể mô tả một cách dễ dàng bằng lời. Sự trừu tượng này được tạo nên bởi màu sắc, cấu trúc, sự kết hợp, nhịp điệu, đối xứng, sự tương phản của từng nét vẽ. Nó được mô tả chi tiết trong hệ thống Kandinsky (Gortais, 2003).  Đối với Kandinsky, mọi sự vật, hiện tượng trên trái đất đều được biểu diễn bởi 3 yếu tố chủ yếu là điểm, đường nét và mặt phẳng.  Điểm: là một hình dạng nhỏ nhất và cũng chính là một thành phần chính trong hội họa. Nó thể hiện sự im lặng, hướng nội, đồng tâm và tĩnh.  Đường nét: với các hướng và hình dạng khác nhau, nó gợi lên những cảm xúc khác nhau. Chẳng hạn, một đường thẳng nằm ngang thể hiện dòng thời gian, màu đen, tĩnh lặng và lạnh. Nhưng đối với 1 đường thẳng đứng, nó gây ra cảm giác về sự ngắt quãng, ý tưởng mới, cảm xúc tỉnh táo, nóng. Một đường chéo chính là sự kết hợp cảm xúc của đường nằm ngang và thẳng đứng. Một đường cong thể hiện tính trữ tình  Mặt phẳng: Bốn phía của mặt phẳng có sự cộng hưởng đặc biệt. Hướng từ trên xuống tạo cảm giác rơi xuống nhẹ nhàng. Hướng về bên phải có nghĩa là sự khởi hành, hướng về bên trái tạo cảm giác trở về. Chúng ta có thể cảm nhận được sự khác biệt này thông qua tác phẩm điêu khắc nổi tiếng của Albrecht Dürer. Bản gốc ở phía bên trái. Xem từng ảnh bằng cách che khuất ảnh còn lại và cảm nhận có hay không một sự khác biệt trong nhận thức. Hình 3 - Tác phẩm điêu khắc “ Cái chết, ma quỷ và hiệp sĩ „ 2.3. Biểu diễn ảnh Để bắt đầu dự án, chúng tôi thực hiện bước đầu tiên đó là biểu diễn ảnh. Đây là một bước quan trọng trong phân loại ảnh. Nó ảnh hưởng rất lớn tới kết quả phân loại cuối cùng. Hiện nay, có hai cách tiếp cận chính về biểu diễn ảnh là: sử dụng nét đặc trưng toàn cục (global features) như phân bố màu (histograme), moment bất biến Hu, phép chiếu (projection), phép biến đổi profile hoặc sử dụng nét đặc trưng cục bộ (local features) như SIFT [7], BRIEF [8] hoặc ORB [9]. Cách tiếp cận thứ nhất đơn giản nhưng không hiệu quả với những biến đổi về góc nhìn, tỉ lệ, tịnh tiến, phép quay, độ sáng, không có khả năng chịu đựng những thay đổi về độ sáng, sự che khuất hoặc nhiễu. Ngược lại, cách tiếp cận thứ hai xử lý tốt trong các trường hợp đó và đem lại hiểu quả cao trong phân loại và nhận diện ảnh. Vì vậy, tùy thuộc vào đặc điểm của đối tượng trích rút ví dụ như khuôn mặt, chữ viết tay mà chúng ta lựa chọn phương pháp phù hợp. 3. Phƣơng pháp đề xuất Do đặc điểm của dự án là tạo sinh ra ảnh bằng cách hoán đổi vị trí của 6x4 ô nhỏ được chia cắt từ một ảnh ban đầu. Chính vì vậy, bước đầu tiên của dự án là tạo ra một tập dữ liệu trên 1000 ảnh dựa trên phép tráo đổi vị trí, phép xoay ngẫu nhiên các ô của ảnh ban đầu như mô hình dưới đây: Hình 4 – Mô phỏng thuật toán sinh ảnh ngẫu nhiên Từ ảnh ban đầu I0, với mỗi phép tráo đổi vị trí của 2 ô vuông với nhau (tối thiểu là 1 ô có đường), ta được một ảnh mới có khoảng cách d = 1 với ảnh gốc. Từ ảnh mới này, ta lại tiếp tục thay đổi vị trí của 2 ô khác, ta sẽ được 1 ảnh mới có khoảng cách d = 2 với ảnh gốc. Tại các ảnh vừa tạo ra, ta thực hiện phép xoay các ô có đường một góc 90 o , 180 o hoặc 270o để tạo ra các ảnh mới. Với tập dữ liệu ảnh vừa tạo ra, chúng tôi thực hiện trích rút đặc trưng của từng ảnh và biểu diễn chúng dưới dạng một véctơ 264 chiều. Do N ảnh này được tạo ra từ 1 ảnh ban đầu nên các điểm ảnh hoàn toàn giống nhau, chúng chỉ khác nhau về vị trí. Chính vì lý do này, việc sử dụng nét đặc trưng cục bộ và một số phương pháp nghiên cứu phía trên là không hiệu quả. Chúng tôi thực hiện trích rút các đặc trưng của từng đường nét như sau:  Đặc trưng cục bộ (xét trên từng ô nhỏ của ảnh): tính toán tọa độ giao điểm của đường và 4 cạnh của ô, độ dài, độ rộng, hướng và bounding box của đường.  Đặc trưng toàn cục (xét trên toàn bộ bức ảnh): tính toán số lượng đường, số lượng đường xiên chéo lên, số lượng vòng tròn, số lượng đường nằm ở ½ phía dưới ảnh, số đường nằm ngang nằm ở nửa bên trái. Sau khi biểu diễn ảnh dưới dạng véctơ đặc trưng, chúng tôi sử dụng thuật toán K-medoids [10] nhằm chọn ra những ảnh đặc trưng nhất của mỗi cụm để hiển thi cho người dùng nhằm giúp người dùng có cái nhìn tổng quan nhất về tập ảnh được sinh ra. Từ đó người dùng sẽ có sự đánh giá khách quan, hiệu quả cho việc huấn luyện mô hình học tự động bằng thuật toán rừng ngẫu nhiên. 3.1. Phân cụm bằng thuật toán K-Medoids Phân cụm là một kỹ thuật quan trọng trong khai phá dữ liệu, nó thuộc lớp các phương pháp học không giám sát trong học máy. Một thuật toán được sử dụng khá phổ biến trong kỹ thuật phân cụm đó là thuật toán K-means. Tuy nhiên, thuật toán này không có khả năng tìm ra các cụm lồi hoặc cụm có hình dạng phức tạp, rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Chính vì lý do này, chúng tôi lựa chọn K-medoids – một biến thể của K-means. Nó có khả năng khắc phục nhiễu bằng cách chọn đối tượng ở gần cụm nhất làm trung tâm của cụm đó (medoid). Ý tưởng của thuật toán được thể hiện qua hình sau: Hình 4 – Minh họa thuật toán K-medoids trong [11] 3.2. Rừng ngẫu nhiên Rừng ngẫu nhiên [12] là một phương pháp phân lớp và hồi quy dựa trên việc kết hợp kết quả dự đoán của một số lượng lớn các cây quyết định không cắt nhánh. Mỗi cây được xây dựng trên tập mẫu bootstrap (như Bagging), được lấy ngẫu nhiên từ tập dữ liệu ban đầu, tại mỗi nút con được phân hoạch tốt nhất từ việc chọn ngẫu nhiên một không gian con các thuộc tính. Lỗi tổng quát của rừng phụ thuộc vào độ chính xác của từng cây và sự tương quan giữa các cây. Do mỗi cây là không cắt nhánh nên ta thu được cây với độ lệch thấp, giảm thiểu thành phần lỗi bias. Ngoài ra, do việc xây dựng các không gian con thuộc tính một cách ngẫu nhiên nên mối tương quan giữa các cây cũng được giảm thiểu. Khi so sánh với các giải thuật học máy có giám sát hiện nay như SVM, Boosting thì rừng ngẫu nhiên có độ chính xác cao hơn. Như Breiman đã đề cập trong [12], rừng ngẫu nhiên học nhanh, chịu đựng nhiễu tốt, tránh được tình trạng học vẹt. 4. Kết quả thực nghiệm Trong phần thực nghiệm, chúng tôi sử dụng ngôn ngữ lập trình c/c++ cùng với thư viện mã nguồn mở OpenCV để xử lý ảnh và IDE QtCreator 5.3 để xây dựng giao diện. Chương trình hoạt động tốt trên Linux và Mac OS X. Ba giao diện chính của chương trình được minh họa trong hình 5:  Giao diện 1: Người dùng có thể thao tác trực tiếp trên ảnh gốc để quay hoặc cháo đổi vị trí của các ô cho nhau.  Giao diện 2: Hệ thống tạo N ảnh và sử dụng thuật toán K-Medoids để phân cụm và hiển thị trung tâm mỗi cụm cho người dùng. Người dùng đánh giá độ thú vị của từng ảnh.  Giao diện 3: Những ảnh thú vị sẽ được người dùng gán cho một cảm xúc tương ứng với sự cảm nhận của họ. Sau nhiều lần đánh giá, hệ thống sẽ xây dựng một mô hình học và tạo ra những ảnh mới theo tiêu chí là một cảm xúc mà người dùng yêu cầu. Kết quả hiển thị ở giao diện 2. Quá trình này được lặp đi lặp lại cho đến khi người dùng muốn dừng. Người dùng đánh giá một bố cục mà có các đường tập trung tạo thành một đường chéo trong không gian là một bố cục “sôi động”. Người dùng mong muốn rằng hệ thống sẽ đề suất ra một sự sắp xếp ngẫu nhiên thú vị. Xuất phát từ một đường nét đơn giản, người dùng có thể chọn một sự sắp xếp sao cho có nhiều nhất hoặc ít nhất các đường tập trung tại đường chéo của bức tranh. Người dùng sẽ gán cho bức tranh một giá trị đánh giá độ thú vị và một cái nhãn tương ứng là “sôi động”. Chương trình sẽ lựa chọn và tạo ra những ảnh phù hợp nhất với cách mà người dùng mong muốn. Hình 6, hình 7, hình 8 là minh họa về sự đánh giá và kết quả thu được của người dùng. Hình 5 – Hệ thống PermutoPainter Sau quá trình sử dụng chương trình, người dùng đã thu được các bức tranh có bố cục sôi động, yên tĩnh và bi kịch theo tiêu chí đánh giá của họ. Dưới đây là kết quả thu được: Hình 6- Bernard Gortais – Ví dụ về bố cục sôi động Hình 7- Bernard Gortais – Ví dụ về bố cục yên tĩnh Hình 8- Bernard Gortais – Ví dụ về bố cục bi kịch 5. Kết luận và hƣớng phát triển Chương trình tuy còn đơn giản nhưng đã đáp ứng được những yêu cầu ban đầu của người dùng. Vì sự hoán vị xảy ra một cách ngẫu nhiên nên không gian ảnh khá đa dạng, giúp người dùng phát hiện nhiều trường hợp hoán vị thú vị. Tuy nhiên, chương trình còn một số hạn chế như mất nhiều thời gian để tạo sinh ảnh, người dùng phải thực hiện đánh giá nhiều lần để tạo ra một số lượng ảnh tương đối tốt cho quá trình học và phương thức trích rút đặc trưng ảnh chưa thực sự tốt. Trong tương lai, chúng tôi sẽ cố gắng cải tiến những nhược điểm trên, áp dụng nhiều phương thức biểu diễn ảnh khác nhau để chọn ra được phương thức phù hợp nhất. Đặc biệt, chúng tôi sẽ cố gắng cải tiến chương trình để có thể xử lý với ảnh đầu vào trừu tượng hơn. 6. Tài liệu tham khảo [1]. Boden, M. A. (1998). Creativity and artificial intelligence. Artificial Intelligence, 103(1–2), 347–356. [2]. Boden, M. A. (2009). Computer Models of Creativity. AI Magazine, 30(3), 23. [3]. Breiman, L. (2001). Random Forests. Machine Learning, 45(1), 5–32. [4]. Calonder, M., Lepetit, V., Strecha, C., & Fua, P. (2010). BRIEF: Binary Robust Independent Elementary Features. In K. Daniilidis, P. Maragos, & N. Paragios (Eds.), Computer Vision – ECCV 2010 (pp. 778–792). [5]. Dawkins, R. (2006). Blind Watchmaker (Fifth edition). London: Penguin UK. [6]. Feng, S.-Y., & Ting, C.-K. (2014). Painting Using Genetic Algorithm with Aesthetic Evaluation of Visual Quality. In S.-M. Cheng & M.-Y. Day (Eds.), Technologies and Applications of Artificial Intelligence (pp. 124–135). [7]. Gopi Gandhi, R. S. (2014). Review Paper: A Comparative Study on Partitioning Techniques of Clustering Algorithms, 87(9). [8]. Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2), 91–110. [9]. Park, H., Lee, J., & Jun, C. (2006). Abstract A K-means-like Algorithm for K- medoids Clustering and Its Performance. [10]. Rublee, E., Rabaud, V., Konolige, K., & Bradski, G. (2011). ORB: An efficient alternative to SIFT or SURF. In 2011 IEEE International Conference on Computer Vision (ICCV) (pp. 2564–2571). [11]. Sims, K. (1991). Artificial Evolution for Computer Graphics. Computer Graphics, 319–328. [12]. Todd, S., & Latham, W. (1994). Evolutionary Art and Computers. Orlando, FL, USA: Academic Press, Inc. DESIGN, DEVELOPMENT AND ANALYSIS OF GENETIC ALGORITHM INTERACTIVE TO GENERATE IMAGES GUIDED BY HUMAN EVALUATION: THE PERMUTOPAINTER PROJECT Abstract: The project PermutoPainter is based on the idea of the series “Arrangement avec le hasard” (Random Arrangement) was exhibited in Paris in November 2014 by the French painter Bernard Gortais. It looks like looking for an order in the chaos of possible 6x4 square arrangements on a picture that can be rotated on themselves 90o or swap positions between each cell. The main purpose of this project is to create interesting structures by combining random 24 boxes of painting. As the line position (up, down, horizontal, vertical), color and layout on a picture is changed, it will give the viewer the different emotions. This topic is concerning with the two popular domains like image processing and machine learning. In this project, I used several techniques to extract features of each image, then using the K-Medoids algorithms for clustering and finally using the random forest and Genetic algorithms with interaction of users to create user expected pictures. Keywords: Algorithm genetic, Clustering, Random Forest, Image Processing, K-Medoids.