Kỷ yếu công trình khoa học 2015 - Phần I<br />
<br />
THIẾT KẾ, PHÂN TÍCH VÀ PHÁT TRIỂN MỘT THUẬT<br />
TOÁN DI TRUYỀN TƢƠNG TÁC ĐỂ TẠO SINH ẢNH<br />
DỰA THEO HƢỚNG DẪN ĐÁNH GIÁ CỦA CON NGƢỜI :<br />
DỰ ÁN PERMUTOPAINTER<br />
Đào Thị Duyên<br />
Khoa Toán-Tin, Đại học Thăng Long<br />
Email: dtduyen90@gmail.com<br />
Tóm tắt: Dự án PermutoPainter dựa trên ý tưởng của bộ sưu tập<br />
“Arrangement avec le hasard” (Sắp xếp ngẫu nhiên) được triển lãm tại Paris vào<br />
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ư<br />
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<br />
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<br />
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<br />
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<br />
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<br />
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ử<br />
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<br />
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 ý<br />
muốn của người dùng.<br />
Từ khóa: Giải thuật di truyền, phân cụm, Rừng ngẫu nhiên, Xử lý ảnh, KMedoids.<br />
1. Mở đầu<br />
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.<br />
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<br />
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,<br />
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<br />
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<br />
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<br />
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ệ<br />
thuật sử dụng trí thông mình nhân tạo AARON năm 1973 [1].<br />
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<br />
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<br />
“The Blind Watchmaker” [2] được viết bởi nhà sinh học tiến hóa Richard Dawkins. Sau<br />
đó, 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<br />
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<br />
một lĩnh vực nghệ thuật mới, đó là “Nghệ thuật tiến hóa” [5].<br />
<br />
Trường Đại học Thăng Long<br />
<br />
1<br />
<br />
Kỷ yếu công trình khoa học 2015 - Phần I<br />
<br />
Trong bài báo này, chúng tôi sẽ trình bày về dự án PermutoPainter được phát<br />
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ó<br />
đượ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<br />
đườ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<br />
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.<br />
<br />
Hình 1- Ví dụ một kiểu sắp xếp<br />
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 ý<br />
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<br />
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<br />
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<br />
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<br />
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ả<br />
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<br />
(Feng & Ting, 2014). Trước tiên, một ảnh được cắt ra thành 6x4 phần bằng nhau, sau<br />
đó 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à<br />
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<br />
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<br />
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<br />
ả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<br />
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<br />
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<br />
tính mà người dùng yêu cầu.<br />
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ơ<br />
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<br />
đượ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<br />
cùng là phần 5 kết luận và hướng phát triển<br />
2. Các nghiên cứu liên quan<br />
<br />
Trường Đại học Thăng Long<br />
<br />
2<br />
<br />
Kỷ yếu công trình khoa học 2015 - Phần I<br />
<br />
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.<br />
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ả<br />
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<br />
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<br />
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<br />
diễn ảnh.<br />
2.1 Hệ thống EvoEco – một ví dụ về tạo sinh ảnh<br />
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ó<br />
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à<br />
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<br />
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<br />
tranh trong suốt quá trình sống của chúng.<br />
Quá trình tiến hóa của EvoEco để tạo sinh ảnh gồm các giai đoạn sau:<br />
1. Xác định ngẫu nhiên màu nền cho mỗi nhiễm sắc thể.<br />
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<br />
quá trình sống của chúng.<br />
3. Đột biến và lai tạo trên các nhiễm sắc thể vừa tạo ra.<br />
<br />
Hình 2- Giao diện hệ thống EvoEco và một vài ảnh đã được đánh giá<br />
2.2. Nghệ thuật thị giác và trừu tượng<br />
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<br />
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<br />
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ễ<br />
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<br />
<br />
Trường Đại học Thăng Long<br />
<br />
3<br />
<br />
Kỷ yếu công trình khoa học 2015 - Phần I<br />
<br />
đ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<br />
Kandinsky (Gortais, 2003).<br />
<br />
<br />
Đối với Kandinsky, mọi sự vật, hiện tượng trên trái đất đều được biểu diễn<br />
bởi 3 yếu tố chủ yếu là điểm, đường nét và mặt phẳng.<br />
<br />
<br />
<br />
Đ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<br />
trong hội họa. Nó thể hiện sự im lặng, hướng nội, đồng tâm và tĩnh.<br />
<br />
<br />
<br />
Đườ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<br />
xúc khác nhau. Chẳng hạn, một đường thẳng nằm ngang thể hiện dòng thời<br />
gian, màu đen, tĩnh lặng và lạnh. Nhưng đối với 1 đường thẳng đứng, nó gây<br />
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<br />
đường chéo chính là sự kết hợp cảm xúc của đường nằm ngang và thẳng<br />
đứng. Một đường cong thể hiện tính trữ tình…<br />
<br />
<br />
<br />
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ừ<br />
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à<br />
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<br />
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<br />
<br />
Albrecht Dürer. Bản gốc ở phía bên trái. Xem từng ảnh bằng cách che<br />
khuất ảnh còn lại và cảm nhận có hay không một sự khác biệt trong<br />
nhận thức.<br />
<br />
Hình 3 - Tác phẩm điêu khắc “ Cái chết, ma quỷ và hiệp sĩ „<br />
<br />
Trường Đại học Thăng Long<br />
<br />
4<br />
<br />
Kỷ yếu công trình khoa học 2015 - Phần I<br />
<br />
2.3. Biểu diễn ảnh<br />
Để 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à<br />
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<br />
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<br />
trưng toàn cục (global features) như phân bố màu (histograme), moment bất biến Hu,<br />
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<br />
features) như SIFT [7], BRIEF [8] hoặc ORB [9].<br />
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<br />
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<br />
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<br />
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<br />
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à<br />
chúng ta lựa chọn phương pháp phù hợp.<br />
3. Phƣơng pháp đề xuất<br />
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 ô<br />
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<br />
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 ô<br />
của ảnh ban đầu như mô hình dưới đây:<br />
<br />
Hình 4 – Mô phỏng thuật toán sinh ảnh ngẫu nhiên<br />
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<br />
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<br />
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 =<br />
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<br />
90o, 180o hoặc 270o để tạo ra các ảnh mới.<br />
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<br />
ả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<br />
<br />
Trường Đại học Thăng Long<br />
<br />
5<br />
<br />